Paul Valiant

CoRR, 2024

Depth Separations in Neural Networks: Separating the Dimension from the Accuracy.

[BibT_eX]

[DOI]

Itay Safran

Daniel Reichman

CoRR, 2024

How Many Neurons Does it Take to Approximate the Maximum?

[BibT_eX]

[DOI]

Itay Safran

Daniel Reichman

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

2023

Minimax-Optimal Location Estimation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond 1+α Moments.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

2022

Finite-Sample Maximum Likelihood Estimation of Location.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Optimal Sub-Gaussian Mean Estimation in Very High Dimensions.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins.

[BibT_eX]

[DOI]

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

Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Optimal Sub-Gaussian Mean Estimation in R.

[BibT_eX]

[DOI]

CoRR, 2020

Worst-Case Analysis for Randomly Collected Data.

[BibT_eX]

[DOI]

Justin Y. Chen

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

Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

Instance Optimal Distribution Testing and Learning.

[BibT_eX]

[DOI]

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

How bad is worst-case data if you know where it comes from?

[BibT_eX]

[DOI]

Justin Y. Chen

CoRR, 2019

Uncertainty about Uncertainty: Near-Optimal Adaptive Algorithms for Estimating Binary Mixtures of Unknown Coins.

[BibT_eX]

[DOI]

CoRR, 2019

2017

An Automatic Inequality Prover and Instance Optimal Identity Testing.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Estimating the Unseen: Improved Estimators for Entropy and Other Properties.

[BibT_eX]

[DOI]

J. ACM, 2017

2016

Information Theoretically Secure Databases.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Instance optimal learning of discrete distributions.

[BibT_eX]

[DOI]

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

Optimizing Star-Convex Functions.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Instance Optimal Learning.

[BibT_eX]

[DOI]

CoRR, 2015

Beyond Convex Optimization: Star-Convex Functions.

[BibT_eX]

[DOI]

CoRR, 2015

2014

Evolvability of Real Functions.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

Optimal Algorithms for Testing Closeness of Discrete Distributions.

[BibT_eX]

[DOI]

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

2013

Instance-by-instance optimal identity testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Testing <i>k</i>-Modal Distributions: Optimal Algorithms via Reductions.

[BibT_eX]

[DOI]

Constantinos Daskalakis

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Size and Treewidth Bounds for Conjunctive Queries.

[BibT_eX]

[DOI]

J. ACM, 2012

The shifting sands algorithm.

[BibT_eX]

[DOI]

Andrew McGregor

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Testing Symmetric Properties of Distributions.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Testing $k$-Modal Distributions: Optimal Algorithms via Reductions

[BibT_eX]

[DOI]

Constantinos Daskalakis

CoRR, 2011

Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

The Power of Linear Estimators.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Estimating the unseen: A sublinear-sample canonical estimator of distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

A CLT and tight lower bounds for estimating entropy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Testing monotonicity of distributions over general partial orders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Robustly Leveraging Collusion in Combinatorial Auctions.

[BibT_eX]

[DOI]

Jing Chen

Silvio Micali

Proceedings of the Innovations in Computer Science, 2010

2009

Size Bounds for Conjunctive Queries with General Functional Dependencies

[BibT_eX]

[DOI]

CoRR, 2009

On the complexity of Nash equilibria of action-graph games.

[BibT_eX]

[DOI]

Constantinos Daskalakis

Grant Schoenebeck

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

Testing symmetric properties of distributions.

[BibT_eX]

[DOI]

PhD thesis, 2008

Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography, Fifth Theory of Cryptography Conference, 2008

2007

The approximation complexity of win-lose games.

[BibT_eX]

[DOI]

Xi Chen

Shang-Hua Teng

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

2006

How to Construct a Correct and Scalable iBGP Configuration.

[BibT_eX]

[DOI]

Proceedings of the INFOCOM 2006. 25th IEEE International Conference on Computer Communications, 2006

2005

Polynomial Representations of Symmetric Partial Boolean Functions.

[BibT_eX]

[DOI]

Mart de Graaf

SIAM J. Discret. Math., 2005

On the Complexity of Two-PlayerWin-Lose Games.

[BibT_eX]

[DOI]

Timothy G. Abbott

Daniel Kane

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

The Tensor Product of Two Codes Is Not Necessarily Robustly Testable.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2005

2004

The Log-Rank Conjecture and low degree polynomials.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2004

Linear bounds on the North-East model and higher-dimensional analogs.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2004

2002

Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds

[BibT_eX]

[DOI]

Mart de Graaf