| Publication | Date of Publication | Type |
|---|
| Certification with an NP oracle | 2024-09-25 | Paper |
| A generalization of the satisfiability coding lemma and its applications | 2024-07-12 | Paper |
| The composition complexity of majority | 2024-07-05 | Paper |
| Reconstructing decision trees | 2024-06-24 | Paper |
Properly learning decision trees in almost polynomial time
Journal of the ACM | 2024-06-06 | Paper |
| Single-pass streaming algorithms for correlation clustering | 2024-05-14 | Paper |
| Superpolynomial lower bounds for decision tree learning and testing | 2024-05-14 | Paper |
| Lifting uniform learners via distributional decomposition | 2024-05-08 | Paper |
scientific article; zbMATH DE number 7788437 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
The query complexity of certification
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
The query complexity of certification
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
| Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma. | 2023-11-20 | Paper |
Decision Tree Heuristics Can Fail, Even in the Smoothed Setting
(available as arXiv preprint) | 2023-11-20 | Paper |
On the power and limitations of branch and cut
(available as arXiv preprint) | 2023-07-12 | Paper |
| scientific article; zbMATH DE number 7650112 (Why is no real title available?) | 2023-02-03 | Paper |
scientific article; zbMATH DE number 7650392 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
| Non-malleability against polynomial tampering | 2022-12-07 | Paper |
scientific article; zbMATH DE number 7528580 (Why is no real title available?)
Theory of Computing | 2022-05-18 | Paper |
Fooling Polytopes
Journal of the ACM | 2022-03-31 | Paper |
Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits
(available as arXiv preprint) | 2021-08-04 | Paper |
Adaptivity is exponentially powerful for testing monotonicity of halfspaces
(available as arXiv preprint) | 2021-07-28 | Paper |
Fooling Gaussian PTFs via local hyperconcentration
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Settling the query complexity of non-adaptive junta testing
(available as arXiv preprint) | 2020-05-26 | Paper |
Fooling polytopes
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Pseudorandomness for read-\(k\) DNF formulas
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Hypercontractive inequalities via SOS, and the Frankl–Rödl graph
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Settling the query complexity of non-adaptive junta testing
Journal of the ACM | 2019-02-25 | Paper |
An average-case depth hierarchy theorem for Boolean circuits
Journal of the ACM | 2018-05-17 | Paper |
| What circuit classes can be learned with non-trivial savings? | 2018-05-03 | Paper |
Approximate resilience, monotonicity, and the complexity of agnostic learning
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Poly-logarithmic Frege depth lower bounds via an expander switching lemma
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Near-optimal small-depth lower bounds for small distance connectivity
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Learning circuits with few negations
(available as arXiv preprint) | 2017-08-31 | Paper |
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
Discrete Analysis | 2016-10-10 | Paper |
Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
Stochastic Processes and their Applications | 2016-08-08 | Paper |
scientific article; zbMATH DE number 6537946 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 2016-02-01 | Paper |
Approximating Boolean functions with depth-2 circuits
SIAM Journal on Computing | 2015-11-18 | Paper |
Algorithmic signaling of features in auction design
Algorithmic Game Theory | 2015-11-04 | Paper |
Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
A regularity lemma and low-weight approximators for low-degree polynomial threshold functions
Theory of Computing | 2014-10-06 | Paper |
scientific article; zbMATH DE number 6351506 (Why is no real title available?)
Theory of Computing | 2014-10-06 | Paper |
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
On DNF approximators for monotone Boolean functions
Automata, Languages, and Programming | 2014-07-01 | Paper |
Average sensitivity and noise sensitivity of polynomial threshold functions
SIAM Journal on Computing | 2014-06-04 | Paper |
On the average sensitivity and density of \(k\)-CNF formulas
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
A composition theorem for the Fourier entropy-influence conjecture
Automata, Languages, and Programming | 2013-08-06 | Paper |
| On the Distribution of the Fourier Spectrum of Halfspaces | 2012-02-29 | Paper |
| Study on non-coding DNA | 2007-06-06 | Paper |
Term Rewriting and Applications
Lecture Notes in Computer Science | 2005-11-11 | Paper |
Design of a robust estimator for nonlinear kinetic modelling
International Journal of Systems Science. Principles and Applications of Systems and Integration | 1995-12-13 | Paper |
