| Publication | Date of Publication | Type |
|---|
Reducing Tarski to unique Tarski (in the black-box model)
SIAM Journal on Computing | 2026-02-04 | Paper |
| Testing intersecting and union-closed families | 2025-11-04 | Paper |
Computing a fixed point of contraction maps in polynomial queries
Journal of the ACM | 2025-10-23 | Paper |
| Trace reconstruction from local statistical queries | 2025-10-06 | Paper |
Polynomial-time trace reconstruction in the smoothed complexity model
ACM Transactions on Algorithms | 2025-10-01 | Paper |
| New lower bounds for adaptive tolerant junta testing | 2025-08-15 | Paper |
| Memory-query tradeoffs for randomized convex optimization | 2025-08-15 | Paper |
| Memory bounds for continual learning | 2025-08-15 | Paper |
| Subset sum in time \(2^{n/2}/\text{poly}(n)\) | 2025-01-14 | Paper |
| Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas | 2024-11-28 | Paper |
| Smoothed complexity of SWAP in local graph partitioning | 2024-11-28 | Paper |
| Reducing Tarski to unique Tarski (In the Black-Box model) | 2024-11-19 | Paper |
| Average-case subset balancing problems | 2024-07-19 | Paper |
| Near-optimal average-case approximate trace reconstruction from few traces | 2024-07-19 | Paper |
| Computational hardness of the Hylland-Zeckhauser scheme | 2024-07-19 | Paper |
| Approximate trace reconstruction from a single trace | 2024-05-14 | Paper |
| Streaming Euclidean MST to a constant factor | 2024-05-08 | Paper |
scientific article; zbMATH DE number 7788343 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788359 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
New streaming algorithms for high dimensional EMD and MST
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
A Lower Bound on Cycle-Finding in Sparse Digraphs
ACM Transactions on Algorithms | 2023-10-31 | Paper |
scientific article; zbMATH DE number 7650111 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer
SIAM Journal on Computing | 2022-05-31 | Paper |
Adaptivity is exponentially powerful for testing monotonicity of halfspaces
(available as arXiv preprint) | 2021-07-28 | Paper |
Sample-based high-dimensional convexity testing
(available as arXiv preprint) | 2021-07-28 | Paper |
A game-theoretic framework for autonomous vehicles velocity control: bridging microscopic differential games and macroscopic mean field games
Discrete and Continuous Dynamical Systems. Series B | 2021-05-20 | Paper |
Nearly optimal edge estimation with independent set queries
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
A Lower Bound on Cycle-Finding in Sparse Digraphs
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Smoothed complexity of local max-cut and binary max-CSP
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 |
| Learning and Testing Junta Distributions with Subcube Conditioning | 2020-04-26 | Paper |
Testing unateness nearly optimally
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
Computational Complexity | 2019-08-30 | Paper |
Distribution-free junta testing
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Efficient average-case population recovery in the presence of insertions and deletions
(available as arXiv preprint) | 2019-07-12 | Paper |
The complexity of optimal multidimensional pricing
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Distribution-free junta testing
ACM Transactions on Algorithms | 2019-03-28 | Paper |
Settling the query complexity of non-adaptive junta testing
Journal of the ACM | 2019-02-25 | Paper |
Tight bounds for the distribution-free testing of monotone conjunctions
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
The complexity of optimal multidimensional pricing for a unit-demand buyer
Games and Economic Behavior | 2018-07-12 | Paper |
Complexity of counting CSP with complex weights
Journal of the ACM | 2018-05-17 | Paper |
The Complexity of Non-Monotone Markets
Journal of the ACM | 2018-05-17 | Paper |
The Complexity of Non-Monotone Markets
Journal of the ACM | 2018-05-17 | Paper |
scientific article; zbMATH DE number 6866347 (Why is no real title available?)
(available as arXiv preprint) | 2018-05-03 | Paper |
| On the complexity of simple and optimal deterministic mechanisms for an additive buyer | 2018-03-15 | Paper |
On the complexity of simple and optimal deterministic mechanisms for an additive buyer
(available as arXiv preprint) | 2018-03-15 | Paper |
| Complexity Dichotomies for Counting Problems | 2018-01-02 | 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 |
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Addition is exponentially harder than counting for shallow monotone circuits
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
| The complexity of approximating conservative counting CSPs | 2017-01-30 | Paper |
Nonnegative weighted \#CSP: an effective complexity dichotomy
SIAM Journal on Computing | 2016-12-21 | Paper |
Settling the complexity of computing two-player Nash equilibria
Journal of the ACM | 2015-11-11 | Paper |
On the complexity of Nash equilibria in anonymous games
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | 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 |
| The approximation complexity of win-lose games | 2014-12-18 | Paper |
Recent development in computational complexity characterization of Nash equilibrium
Computer Science Review | 2014-10-07 | Paper |
The complexity of approximating conservative counting CSPs
Journal of Computer and System Sciences | 2014-09-22 | Paper |
How to compress interactive communication
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Multi-stage design for quasipolynomial-time isomorphism testing of Steiner 2-systems
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
The complexity of non-monotone markets
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Complexity of counting CSP with complex weights
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Partial derivatives in arithmetic complexity and beyond
Foundations and Trends in Theoretical Computer Science | 2014-01-15 | Paper |
Graph homomorphisms with complex values: a dichotomy theorem
SIAM Journal on Computing | 2013-09-25 | Paper |
How to compress interactive communication
SIAM Journal on Computing | 2013-09-25 | Paper |
Inapproximability after uniqueness phase transition in two-spin systems
Combinatorial Optimization and Applications | 2012-11-02 | Paper |
On incentive compatible competitive selection protocols
Algorithmica | 2011-09-20 | Paper |
Quadratic lower bound for permanent vs. determinant in any characteristic
Computational Complexity | 2011-02-07 | Paper |
On tractable exponential sums
Frontiers in Algorithmics | 2010-09-07 | Paper |
Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
Automata, Languages and Programming | 2010-09-07 | Paper |
On algorithms for discrete and approximate brouwer fixed points
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Quantum separation of local search and fixed point computation
Algorithmica | 2010-02-23 | Paper |
Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria
Algorithms and Computation | 2009-12-17 | Paper |
On the complexity of 2D discrete fixed point problem
Theoretical Computer Science | 2009-11-04 | Paper |
A simplicial approach for discrete fixed point theorems
Algorithmica | 2009-04-29 | Paper |
Market equilibria with hybrid linear-Leontief utilities
Theoretical Computer Science | 2009-04-29 | Paper |
On the Complexity of 2D Discrete Fixed Point Problem
Automata, Languages and Programming | 2009-03-12 | Paper |
| scientific article; zbMATH DE number 5485561 (Why is no real title available?) | 2009-01-05 | Paper |
Matching algorithmic bounds for finding a Brouwer fixed point
Journal of the ACM | 2008-12-21 | Paper |
Quantum Separation of Local Search and Fixed Point Computation
Lecture Notes in Computer Science | 2008-07-10 | Paper |
Computing Exact p-Value for Structured Motif
Combinatorial Pattern Matching | 2008-06-17 | Paper |
Lattice Embedding of Direction-Preserving Correspondence over Integrally Convex Set
Algorithmic Aspects in Information and Management | 2008-01-04 | Paper |
A Simplicial Approach for Discrete Fixed Point Theorems
Lecture Notes in Computer Science | 2007-09-10 | Paper |
On Incentive Compatible Competitive Selection Protocol
Lecture Notes in Computer Science | 2007-09-10 | Paper |
On searching a table consistent with division poset
Theoretical Computer Science | 2007-02-26 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2006-11-14 | Paper |
Testing Sumsets is Hard
(available as arXiv preprint) | N/A | Paper |
