Anindya De

CoRR, 2023

Testing Convex Truncation.

[BibT_eX]

[DOI]

Eshwar Ram Arunachaleswaran

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

Approximate Trace Reconstruction from a Single Trace.

[BibT_eX]

[DOI]

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

Reconstructing Ultrametric Trees from Noisy Experiments.

[BibT_eX]

[DOI]

Sampath Kannan

Proceedings of the International Conference on Algorithmic Learning Theory, 2023

2022

Nearly Tight Bounds for Discrete Search under Outlier Noise.

[BibT_eX]

[DOI]

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

Approximating Sumset Size.

[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

Convex Influences.

[BibT_eX]

[DOI]

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

Algorithms for learning a mixture of linear classifiers.

[BibT_eX]

[DOI]

Aidao Chen

Aravindan Vijayaraghavan

Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022

2021

Robust testing of low-dimensional functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Polynomial-time trace reconstruction in the smoothed complexity model.

[BibT_eX]

[DOI]

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

Approximate optimization of convex functions with outlier noise.

[BibT_eX]

[DOI]

MohammadHesam NikpeySalekde

Sanjeev Khanna

Huan Li

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Quantitative Correlation Inequalities via Semigroup Interpolation.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 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

Weak learning convex sets under normal distributions.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Learning sparse mixtures of permutations from noisy information.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Reconstructing weighted voting schemes from partial information about their power indices.

[BibT_eX]

[DOI]

Huck Bennett

Emmanouil-Vasileios Vlatakis-Gkaragkounis

Proceedings of the Conference on Learning Theory, 2021

Learning a mixture of two subspaces over finite fields.

[BibT_eX]

[DOI]

Aidao Chen

Aravindan Vijayaraghavan

Proceedings of the Algorithmic Learning Theory, 2021

2020

Sharp Bounds for Population Recovery.

[BibT_eX]

[DOI]

Theory Comput., 2020

Testing noisy linear functions for sparsity.

[BibT_eX]

[DOI]

Xue Chen

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

Reconstruction under outliers for Fourier-sparse functions.

[BibT_eX]

[DOI]

Xue Chen

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

Learning from satisfying assignments under continuous distributions.

[BibT_eX]

[DOI]

Clément L. Canonne

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

An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Noise Stability is Computable and Approximately Low-Dimensional.

[BibT_eX]

[DOI]

Theory Comput., 2019

Kruskal-Katona for convex sets, with applications.

[BibT_eX]

[DOI]

CoRR, 2019

Density Estimation for Shift-Invariant Multidimensional Distributions.

[BibT_eX]

[DOI]

Philip M. Long

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Junta Correlation is Testable.

[BibT_eX]

[DOI]

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

Is your function low dimensional?

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Simple and efficient pseudorandom generators from Gaussian processes.

[BibT_eX]

[DOI]

Eshan Chattopadhyay

Electron. Colloquium Comput. Complex., 2018

Learning sparse mixtures of rankings from noisy information.

[BibT_eX]

[DOI]

CoRR, 2018

Is your data low-dimensional?

[BibT_eX]

[DOI]

CoRR, 2018

Non interactive simulation of correlated distributions is decidable.

[BibT_eX]

[DOI]

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

Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack.

[BibT_eX]

[DOI]

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

Learning Sums of Independent Random Variables with Sparse Collective Support.

[BibT_eX]

[DOI]

Philip M. Long

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Noise Stability is computable and low dimensional.

[BibT_eX]

[DOI]

CoRR, 2017

Optimal mean-based algorithms for trace reconstruction.

[BibT_eX]

[DOI]

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

2016

Majority is Stablest: Discrete and SoS.

[BibT_eX]

[DOI]

Theory Comput., 2016

A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2016

Noisy population recovery in polynomial time.

[BibT_eX]

[DOI]

Michael E. Saks

Sijian Tang

Electron. Colloquium Comput. Complex., 2016

A size-free CLT for poisson multinomials and its applications.

[BibT_eX]

[DOI]

Constantinos Daskalakis

Gautam Kamath

Christos Tzamos

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

2015

Boolean Function Monotonicity Testing Requires (Almost) n<sup>1/2</sup> Non-adaptive Queries.

[BibT_eX]

[DOI]

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

Learning from satisfying assignments.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces.

[BibT_eX]

[DOI]

J. ACM, 2014

Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage.

[BibT_eX]

[DOI]

Constantinos Daskalakis

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

2013

Efficient deterministic approximate counting for low degree polynomial threshold functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

Trevisan's Extractor in the Presence of Quantum Side Information.

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

Explicit Optimal hardness via Gaussian stability results.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

The Inverse Shapley Value Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Inverse Problems in Approximate Uniform Generation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Lower Bounds in Differential Privacy.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 9th Theory of Cryptography Conference, 2012

2011

Extractors and Lower Bounds for Locally Samplable Sources.

[BibT_eX]

[DOI]

Thomas Watson

Electron. Colloquium Comput. Complex., 2011

Pseudorandomness for Permutation and Regular Branching Programs.

[BibT_eX]

[DOI]

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

2010

Time Space Tradeoffs for Attacks against One-Way Functions and PRGs.

[BibT_eX]

[DOI]

Luca Trevisan

Madhur Tulsiani

Proceedings of the Advances in Cryptology, 2010

2009

Near-optimal extractors against quantum storage.

[BibT_eX]

[DOI]

Thomas Vidick

Electron. Colloquium Comput. Complex., 2009

Non-uniform attacks against one-way functions and PRGs.

[BibT_eX]

[DOI]

Luca Trevisan

Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2009

Improved Pseudorandom Generators for Depth 2 Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Extractors Using Hardness Amplification.

[BibT_eX]

[DOI]

Luca Trevisan

Proceedings of the Approximation, 2009

2008

Fast Integer Multiplication using Modular Arithmetic.

[BibT_eX]

[DOI]