| Publication | Date of Publication | Type |
|---|
| Low degree testing over the reals | 2024-05-14 | Paper |
Model counting meets \(F_0\) estimation
ACM Transactions on Database Systems | 2023-11-29 | Paper |
Near-optimal learning of tree-structured distributions by Chow-Liu
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
SIAM Journal on Computing | 2023-07-06 | Paper |
scientific article; zbMATH DE number 7650433 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
Parameterized Intractability of Even Set and Shortest Vector Problem
Journal of the ACM | 2022-12-08 | Paper |
| Property testing. Problems and techniques | 2022-02-21 | Paper |
Predicting winner and estimating margin of victory in elections using sampling
Artificial Intelligence | 2021-11-02 | Paper |
Lower bounds for 2-query LCCs over large alphabet
(available as arXiv preprint) | 2021-07-28 | Paper |
Parameterized intractability of even set and shortest vector problem from Gap-ETH
(available as arXiv preprint) | 2021-07-28 | Paper |
A formal methods approach to predicting new features of the eukaryotic vesicle traffic system
Acta Informatica | 2021-04-28 | Paper |
Improved learning of \(k\)-parities
Theoretical Computer Science | 2020-09-17 | Paper |
Lower bounds for constant query affine-invariant LCCs and LTCs
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
Combinatorial lower bounds for 3-query LDCs
(available as arXiv preprint) | 2019-11-24 | Paper |
Testing low complexity affine-invariant properties
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| Testing odd-cycle-freeness in Boolean functions | 2019-05-10 | Paper |
| Transitive-closure spanners | 2019-05-06 | Paper |
An optimal algorithm for \(\ell_1\)-heavy hitters in insertion streams and related problems
ACM Transactions on Algorithms | 2019-03-28 | Paper |
Improved learning of \(k\)-parities
Lecture Notes in Computer Science | 2018-10-04 | Paper |
| On higher-order Fourier analysis over non-prime fields | 2018-04-19 | Paper |
On the hardness of learning sparse parities
(available as arXiv preprint) | 2018-03-02 | Paper |
Lower bounds for constant query affine-invariant LCCs and LTCs
(available as arXiv preprint) | 2017-10-10 | Paper |
Algorithmic regularity for polynomials and applications
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
On the convergence of the Hegselmann-Krause system
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin.
Combinatorica | 2017-03-31 | Paper |
Lower bounds for testing triangle-freeness in Boolean functions
Computational Complexity | 2015-07-08 | Paper |
| Using higher-order Fourier analysis over general fields | 2015-05-04 | Paper |
A unified framework for testing linear-invariant properties
Random Structures & Algorithms | 2015-04-09 | Paper |
Polynomial decompositions in polynomial time
Algorithms - ESA 2014 | 2014-10-08 | Paper |
A bipartite graph with non-unimodal independent set sequence
The Electronic Journal of Combinatorics | 2014-08-14 | Paper |
A bipartite graph with non-unimodal independent set sequence
The Electronic Journal of Combinatorics | 2014-08-14 | Paper |
Steiner transitive-closure spanners of low-dimensional posets
Combinatorica | 2014-08-14 | Paper |
Every locally characterized affine-invariant property is testable
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Tight Lower Bounds for 2-query LCCs over Finite Fields
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
| Lower bounds for testing triangle-freeness in Boolean functions | 2014-05-22 | Paper |
An algebraic characterization of testable Boolean CSPs
Automata, Languages, and Programming | 2013-08-06 | Paper |
Approximation algorithms for spanner problems and directed Steiner forest
Information and Computation | 2013-06-06 | Paper |
Transitive-closure spanners
SIAM Journal on Computing | 2013-03-19 | Paper |
Testing permanent oracles -- revisited
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Testing Odd-Cycle-Freeness in Boolean Functions
Combinatorics, Probability and Computing | 2012-10-31 | Paper |
Lower bounds for local monotonicity reconstruction from transitive-closure spanners
SIAM Journal on Discrete Mathematics | 2012-09-12 | Paper |
| Testing linear-invariant non-linear properties | 2012-04-24 | Paper |
Testing linear-invariant non-linear properties
(available as arXiv preprint) | 2012-04-24 | Paper |
Improved approximation for the directed spanner problem
Automata, Languages and Programming | 2011-07-06 | Paper |
Steiner transitive-closure spanners of low-dimensional posets
Automata, Languages and Programming | 2011-07-06 | Paper |
Testing linear-invariant non-linear properties
Theory of Computing | 2011-05-24 | Paper |
Optimal testing of Reed-Muller codes
Property Testing | 2010-10-12 | Paper |
Testing Linear-Invariant Non-linear Properties: A Short Report
Property Testing | 2010-10-12 | Paper |
Lower bounds for local monotonicity reconstruction from transitive-closure spanners
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Learning bounded-degree polytrees with known skeleton
(available as arXiv preprint) | N/A | Paper |
