Xi Chen

Yuhao Li

Electron. Colloquium Comput. Complex., 2024

Lower Bounds for Convexity Testing.

[BibT_eX]

[DOI]

CoRR, 2024

Relative-error monotonicity testing.

[BibT_eX]

[DOI]

CoRR, 2024

Testing Sumsets is Hard.

[BibT_eX]

[DOI]

CoRR, 2024

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries.

[BibT_eX]

[DOI]

Yumou Fei

Shyamal Patel

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Uniformity Testing over Hypergrids with Subcube Conditioning.

[BibT_eX]

[DOI]

Cassandra Marcussen

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Smoothed Complexity of SWAP in Local Graph Partitioning.

[BibT_eX]

[DOI]

Emmanouil V. Vlatakis-Gkaragkounis

Chenghao Guo

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Testing Intersecting and Union-Closed Families.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Trace Reconstruction from Local Statistical Queries.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Reducing Tarski to Unique Tarski (in the Black-box Model).

[BibT_eX]

[DOI]

Yuhao Li

Electron. Colloquium Comput. Complex., 2023

Memory-Query Tradeoffs for Randomized Convex Optimization.

[BibT_eX]

[DOI]

CoRR, 2023

Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Streaming Euclidean MST to a Constant Factor.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Approximate Trace Reconstruction from a Single Trace.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Subset Sum in Time 2n/2 / poly(n).

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

A Lower Bound on Cycle-Finding in Sparse Digraphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for a Unit-Demand Buyer.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

SoK: Play-to-Earn Projects.

[BibT_eX]

[DOI]

CoRR, 2022

On the complexity of dynamic submodular maximization.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

New streaming algorithms for high dimensional EMD and MST.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Average-Case Subset Balancing Problems.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Computational Hardness of the Hylland-Zeckhauser Scheme.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Improved Upper Bounds for Finding Tarski Fixed Points.

[BibT_eX]

[DOI]

Yuhao Li

Proceedings of the EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11, 2022

Memory Bounds for Continual Learning.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Throttling Equilibria in Auction Markets.

[BibT_eX]

[DOI]

Christian Kroer

Rachitesh Kumar

Proceedings of the Web and Internet Economics - 17th International Conference, 2021

Polynomial-time trace reconstruction in the smoothed complexity model.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Complexity of Pacing for Second-Price Auctions.

[BibT_eX]

[DOI]

Christian Kroer

Rachitesh Kumar

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Learning and testing junta distributions with sub cube conditioning.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Learning and Testing Junta Distributions with Subcube Conditioning.

[BibT_eX]

[DOI]

CoRR, 2020

Smoothed complexity of local max-cut and binary max-CSP.

[BibT_eX]

[DOI]

Emmanouil V. Vlatakis-Gkaragkounis

Chenghao Guo

Xinzhi Zhang

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Nearly optimal edge estimation with independent set queries.

[BibT_eX]

[DOI]

Amit Levi

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Hedging in games: Faster convergence of external and swap regrets.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

2019

Distribution-free Junta Testing.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights.

[BibT_eX]

[DOI]

Comput. Complex., 2019

Testing unateness nearly optimally.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Detecting Customer Complaint Escalation with Recurrent Neural Networks and Manually-Engineered Features.

[BibT_eX]

[DOI]

Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2019

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

An Axiomatic Approach to Block Rewards.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Tim Roughgarden

Proceedings of the 1st ACM Conference on Advances in Financial Technologies, 2019

2018

The complexity of optimal multidimensional pricing for a unit-demand buyer.

[BibT_eX]

[DOI]

Games Econ. Behav., 2018

On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

The Complexity of Non-Monotone Markets.

[BibT_eX]

[DOI]

Dimitris Paparas

J. ACM, 2017

Complexity of Counting CSP with Complex Weights.

[BibT_eX]

[DOI]

J. ACM, 2017

Settling the query complexity of non-adaptive junta testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

On the Complexity of Bundle-Pricing and Simple Mechanisms.

[BibT_eX]

[DOI]

CoRR, 2017

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness.

[BibT_eX]

[DOI]

Jinyu Xie

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Boolean Unateness Testing with Õ(n3/4) Adaptive Queries.

[BibT_eX]

[DOI]

Jinyu Xie

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

Sample-Based High-Dimensional Convexity Testing.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

Non-approximability of Bimatrix Nash Equilibria.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Complexity Dichotomies for Counting Graph Homomorphisms.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

A Note on Teaching for VC Classes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Near-optimal small-depth lower bounds for small distance connectivity.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions.

[BibT_eX]

[DOI]

Jinyu Xie

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On the Recursive Teaching Dimension of VC Classes.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

2015

The complexity of approximating conservative counting CSPs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

Addition is exponentially harder than counting for shallow monotone circuits.

[BibT_eX]

[DOI]

Igor Carboni Oliveira

Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2015

Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games.

[BibT_eX]

[DOI]

CoRR, 2015

Boolean Function Monotonicity Testing Requires (Almost) n1/2 Non-adaptive Queries.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

On the Complexity of Nash Equilibria in Anonymous Games.

[BibT_eX]

[DOI]

David Durfee

Anthi Orfanou

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

The Complexity of Optimal Multidimensional Pricing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

New Algorithms and Lower Bounds for Monotonicity Testing.

[BibT_eX]

[DOI]

Rocco A. Servedio

Li-Yang Tan

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Graph Homomorphisms with Complex Values: A Dichotomy Theorem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

How to Compress Interactive Communication.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems.

[BibT_eX]

[DOI]

Xiaorui Sun

Proceedings of the Symposium on Theory of Computing Conference, 2013

Faster Canonical Forms for Strongly Regular Graphs.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Inapproximability after Uniqueness Phase Transition in Two-Spin Systems.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2012

2011

Guest column: complexity dichotomies of counting problems.

[BibT_eX]

[DOI]

SIGACT News, 2011

Partial Derivatives in Arithmetic Complexity and Beyond.

[BibT_eX]

[DOI]

Neeraj Kayal

Avi Wigderson

Found. Trends Theor. Comput. Sci., 2011

On Incentive Compatible Competitive Selection Protocols.

[BibT_eX]

[DOI]

Becky Jie Liu

Algorithmica, 2011

A Complexity View of Markets with Social Influence.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

Non-negatively Weighted #CSP: An Effective Complexity Dichotomy.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

Non-negative Weighted #CSPs: An Effective Complexity Dichotomy

[BibT_eX]

[DOI]

CoRR, 2010

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic.

[BibT_eX]

[DOI]

Dong Li

Comput. Complex., 2010

Quantum Separation of Local Search and Fixed Point Computation.

[BibT_eX]

[DOI]

Xiaoming Sun

Algorithmica, 2010

On Tractable Exponential Sums.

[BibT_eX]

[DOI]

Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010

On the complexity of equilibria in markets with additively separable utilities.

[BibT_eX]

[DOI]

Proceedings of the Behavioral and Quantitative Game Theory, 2010

2009

Market equilibria with hybrid linear-Leontief utilities.

[BibT_eX]

[DOI]

Li-Sha Huang

Theor. Comput. Sci., 2009

On the complexity of 2D discrete fixed point problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Settling the complexity of computing two-player Nash equilibria.

[BibT_eX]

[DOI]

J. ACM, 2009

Direct Sums in Randomized Communication Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

A Simplicial Approach for Discrete Fixed Point Theorems.

[BibT_eX]

[DOI]

Algorithmica, 2009

Spending Is Not Easier Than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Non-approximability of Bimatrix Nash Equilibria.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Incentive Compatible Selection.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Complexity of Bimatrix Nash Equilibria.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Matching algorithmic bounds for finding a Brouwer fixed point.

[BibT_eX]

[DOI]

J. ACM, 2008

A quadratic lower bound for the permanent and determinant problem over any characteristic != 2.

[BibT_eX]

[DOI]

Dong Li

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

Complexity and approximation of the minimum recombinant haplotype configuration problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

On searching a table consistent with division poset.

[BibT_eX]

[DOI]

Yongxi Cheng

Yiqun Lisa Yin

Theor. Comput. Sci., 2007

Recent development in computational complexity characterization of Nash equilibrium.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2007

Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation

[BibT_eX]

[DOI]

CoRR, 2007

The approximation complexity of win-lose games.

[BibT_eX]

[DOI]

Paul Valiant

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Computing Exact p-Value for Structured Motif.

[BibT_eX]

[DOI]

Jing Zhang

Ming Li

Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, 2007

2006

Computing Nash Equilibria: Approximation and Smoothed Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Sparse Games Are Hard.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Settling the Complexity of Two-Player Nash Equilibrium.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

On Incentive Compatible Competitive Selection Protocol.

[BibT_eX]

[DOI]

Becky Jie Liu

Proceedings of the Computing and Combinatorics, 12th Annual International Conference, 2006

Lattice Embedding of Direction-Preserving Correspondence over Integrally Convex Set.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects in Information and Management, 2006

2005

Settling the Complexity of 2-Player Nash-Equilibrium

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

3-NASH is PPAD-Complete

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

On algorithms for discrete and approximate brouwer fixed points.

[BibT_eX]

[DOI]