Daniel M. Kane

Anthony Ostuni

Kewen Wu

Electron. Colloquium Comput. Complex., 2024

Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination.

[BibT_eX]

[DOI]

CoRR, 2024

Statistical Query Lower Bounds for Learning Truncated Gaussians.

[BibT_eX]

[DOI]

CoRR, 2024

Online Robust Mean Estimation.

[BibT_eX]

[DOI]

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

2023

Agnostically Learning Multi-index Models with Queries.

[BibT_eX]

[DOI]

CoRR, 2023

Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation.

[BibT_eX]

[DOI]

CoRR, 2023

Testing Closeness of Multivariate Distributions via Ramsey Theory.

[BibT_eX]

[DOI]

Sihan Liu

CoRR, 2023

New Lower Bounds for Testing Monotonicity and Log Concavity of Distributions.

[BibT_eX]

[DOI]

Yuqian Cheng

Zhicheng Zheng

CoRR, 2023

Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials.

[BibT_eX]

[DOI]

CoRR, 2023

SQ Lower Bounds for Learning Bounded Covariance GMMs.

[BibT_eX]

[DOI]

CoRR, 2023

Do PAC-Learners Learn the Marginal Distribution?

[BibT_eX]

[DOI]

CoRR, 2023

Gaussian Mean Testing Made Simple.

[BibT_eX]

[DOI]

Ankit Pensia

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Sampling Equilibria: Fast No-Regret Learning in Structured Games.

[BibT_eX]

[DOI]

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

SQ Lower Bounds for Learning Mixtures of Linear Classifiers.

[BibT_eX]

[DOI]

Yuxin Sun

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

SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions.

[BibT_eX]

[DOI]

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

Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression.

[BibT_eX]

[DOI]

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

A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm.

[BibT_eX]

[DOI]

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

Efficient Testable Learning of Halfspaces with Adversarial Label Noise.

[BibT_eX]

[DOI]

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

Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise.

[BibT_eX]

[DOI]

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

Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals.

[BibT_eX]

[DOI]

Lisheng Ren

Proceedings of the International Conference on Machine Learning, 2023

Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Exponential Hardness of Reinforcement Learning with Linear Function Approximation.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Statistical and Computational Limits for Tensor-on-Tensor Association Detection.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

vqSGD: Vector Quantized Stochastic Gradient Descent.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2022

A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning.

[BibT_eX]

[DOI]

Christos Tzamos

Electron. Colloquium Comput. Complex., 2022

Near-Optimal Bounds for Testing Histogram Distributions.

[BibT_eX]

[DOI]

CoRR, 2022

Computational-Statistical Gaps in Reinforcement Learning.

[BibT_eX]

[DOI]

CoRR, 2022

Learning general halfspaces with general Massart noise under the Gaussian distribution.

[BibT_eX]

[DOI]

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

Clustering mixture models in almost-linear time via list-decodable mean estimation.

[BibT_eX]

[DOI]

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

Robustly learning mixtures of k arbitrary Gaussians.

[BibT_eX]

[DOI]

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

SQ Lower Bounds for Learning Single Neurons with Massart Noise.

[BibT_eX]

[DOI]

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

Cryptographic Hardness of Learning Halfspaces with Massart Noise.

[BibT_eX]

[DOI]

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

Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions.

[BibT_eX]

[DOI]

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

List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering.

[BibT_eX]

[DOI]

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

Nearly-Tight Bounds for Testing Histogram Distributions.

[BibT_eX]

[DOI]

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

Outlier-Robust Sparse Estimation via Non-Convex Optimization.

[BibT_eX]

[DOI]

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

Streaming Algorithms for High-Dimensional Robust Statistics.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Computational-Statistical Gap in Reinforcement Learning.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models.

[BibT_eX]

[DOI]

Yuxin Sun

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Robust Sparse Mean Estimation via Sum of Squares.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Non-Gaussian Component Analysis via Lattice Basis Reduction.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Coresets for Data Discretization and Sine Wave Fitting.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

Hardness of Learning a Single Neuron with Adversarial Label Noise.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Quantum Money from Quaternion Algebras.

[BibT_eX]

[DOI]

Shahed Sharif

Alice Silverberg

IACR Cryptol. ePrint Arch., 2021

Threshold Phenomena in Learning Halfspaces with Massart Noise.

[BibT_eX]

[DOI]

CoRR, 2021

Fooling Gaussian PTFs via Local Hyperconcentration.

[BibT_eX]

[DOI]

CoRR, 2021

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals.

[BibT_eX]

[DOI]

CoRR, 2021

Highway: Efficient Consensus with Flexible Finality.

[BibT_eX]

[DOI]

CoRR, 2021

Prisoners, Rooms, and Light Switches.

[BibT_eX]

[DOI]

Scott Duke Kominers

Electron. J. Comb., 2021

Robustness meets algorithms.

[BibT_eX]

[DOI]

Commun. ACM, 2021

Efficiently learning halfspaces with Tsybakov noise.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Robust Learning of Mixtures of Gaussians.

[BibT_eX]

[DOI]

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

Forster Decomposition and Learning Halfspaces with Noise.

[BibT_eX]

[DOI]

Christos Tzamos

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

Statistical Query Lower Bounds for List-Decodable Linear Regression.

[BibT_eX]

[DOI]

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

List-Decodable Mean Estimation in Nearly-PCA Time.

[BibT_eX]

[DOI]

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

The Entropy of Lies: Playing Twenty Questions with a Liar.

[BibT_eX]

[DOI]

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

Bounded Memory Active Learning through Enriched Queries.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Outlier-Robust Learning of Ising Models Under Dobrushin's Condition.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Agnostic Proper Learning of Halfspaces under Gaussian Marginals.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

The Sample Complexity of Robust Covariance Testing.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Boosting in the Presence of Massart Noise.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Testing Bayesian Networks.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2020

Optimal Testing of Discrete Distributions with High Probability.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Hardness of Learning Halfspaces with Massart Noise.

[BibT_eX]

[DOI]

CoRR, 2020

Robustly Learning Mixtures of k Arbitrary Gaussians.

[BibT_eX]

[DOI]

CoRR, 2020

A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise.

[BibT_eX]

[DOI]

CoRR, 2020

Prisoners, Rooms, and Lightswitches.

[BibT_eX]

[DOI]

Scott Duke Kominers

CoRR, 2020

Robustly Learning any Clusterable Mixture of Gaussians.

[BibT_eX]

[DOI]

CoRR, 2020

The Power of Comparisons for Actively Learning Linear Classifiers.

[BibT_eX]

[DOI]

Max Hopkins

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

Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals.

[BibT_eX]

[DOI]

Nikos Zarifis

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

Outlier Robust Mean Estimation with Subgaussian Rates via Stability.

[BibT_eX]

[DOI]

Ankit Pensia

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

The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise.

[BibT_eX]

[DOI]

Pasin Manurangsi

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

List-Decodable Mean Estimation via Iterative Multi-Filtering.

[BibT_eX]

[DOI]

Daniel Kongsgaard

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

Point Location and Active Learning: Learning Halfspaces Almost Optimally.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Noise-tolerant, Reliable Active Classification with Comparison Queries.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

Robust High-Dimensional Statistics.

[BibT_eX]

[DOI]

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

2019

Three-dimensional Floorplan Representations by Using Corner Links and Partial Order.

[BibT_eX]

[DOI]

Evangeline F. Y. Young

Chung-Kuan Cheng

Ronald L. Graham

ACM Trans. Design Autom. Electr. Syst., 2019

The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes.

[BibT_eX]

[DOI]

Sankeerth Rao

SIAM J. Comput., 2019

Robust Estimators in High-Dimensions Without the Computational Intractability.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Near-optimal Linear Decision Trees for k-SUM and Related Problems.

[BibT_eX]

[DOI]

Shay Moran

J. ACM, 2019

Recent Advances in Algorithmic High-Dimensional Robust Statistics.

[BibT_eX]

[DOI]

CoRR, 2019

Waring's Theorem for Binary Powers.

[BibT_eX]

[DOI]

Carlo Sanna

Jeffrey O. Shallit

Comb., 2019

Degree-푑 chow parameters robustly determine degree-푑 PTFs (and algorithmic applications).

[BibT_eX]

[DOI]

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

Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin.

[BibT_eX]

[DOI]

Pasin Manurangsi

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Private Testing of Distributions via Sample Permutations.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

The Orthogonal Vectors Conjecture for Branching Programs and Formulas.

[BibT_eX]

[DOI]

Richard Ryan Williams

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

Sever: A Robust Meta-Algorithm for Stochastic Optimization.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Learning Ising Models with Independent Failures.

[BibT_eX]

[DOI]

Surbhi Goel

Adam R. Klivans

Proceedings of the Conference on Learning Theory, 2019

Testing Identity of Multidimensional Histograms.

[BibT_eX]

[DOI]

John Peebles

Proceedings of the Conference on Learning Theory, 2019

Communication and Memory Efficient Testing of Discrete Distributions.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

The Optimal Approximation Factor in Density Estimation.

[BibT_eX]

[DOI]

Olivier Bousquet

Shay Moran

Proceedings of the Conference on Learning Theory, 2019

2018

Pseudorandomness via the Discrete Fourier Transform.

[BibT_eX]

[DOI]

Parikshit Gopalan

SIAM J. Comput., 2018

Generalized comparison trees for point-location problems.

[BibT_eX]

[DOI]

Shay Moran

Electron. Colloquium Comput. Complex., 2018

Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Quantum Money from Modular Forms.

[BibT_eX]

[DOI]

CoRR, 2018

Learning geometric concepts with nasty noise.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

List-decodable robust mean estimation and learning mixtures of spherical gaussians.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Testing conditional independence of discrete distributions.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Robustly Learning a Gaussian: Getting Optimal Error, Efficiently.

[BibT_eX]

[DOI]

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

Robust Learning of Fixed-Structure Bayesian Networks.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n.

[BibT_eX]

[DOI]

Sankeerth Rao

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Labeling the complete bipartite graph with no zero cycles.

[BibT_eX]

[DOI]

Sankeerth Rao

Electron. Colloquium Comput. Complex., 2017

Active classification with comparison queries.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

On Communication Complexity of Classification Problems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

A Polynomial Restriction Lemma with Applications.

[BibT_eX]

[DOI]

Valentine Kabanets

Zhenjian Lu

Electron. Colloquium Comput. Complex., 2017

Sharp Bounds for Generalized Uniformity Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

A Bound on Partitioning Clusters.

[BibT_eX]

[DOI]

Terence Tao

Electron. J. Comb., 2017

Being Robust (in High Dimensions) Can Be Practical.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

Near-Optimal Closeness Testing of Discrete Histogram Distributions.

[BibT_eX]

[DOI]

Vladimir Nikishkin

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Robust Polynomial Regression up to the Information Theoretic Limit.

[BibT_eX]

[DOI]

Sushrut Karmalkar

Eric Price

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

Learning Multivariate Log-concave Distributions.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Big-Key Symmetric Encryption: Resisting Key Exfiltration.

[BibT_eX]

[DOI]

Mihir Bellare

Phillip Rogaway

IACR Cryptol. ePrint Arch., 2016

Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

A New Approach for Testing Properties of Discrete Distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Efficient Robust Proper Learning of Log-concave Distributions.

[BibT_eX]

[DOI]

CoRR, 2016

A Short Implicant of a CNF Formula with Many Satisfying Assignments.

[BibT_eX]

[DOI]

Osamu Watanabe

Algorithmica, 2016

The fourier transform of poisson multinomial distributions and its algorithmic applications.

[BibT_eX]

[DOI]

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

Fourier-Sparse Interpolation without a Frequency Gap.

[BibT_eX]

[DOI]

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

Properly Learning Poisson Binomial Distributions in Almost Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 29th Conference on Learning Theory, 2016

Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables.

[BibT_eX]

[DOI]

Proceedings of the 29th Conference on Learning Theory, 2016

3D floorplan representations: Corner links and partial order.

[BibT_eX]

[DOI]

Proceedings of the 2016 IEEE International 3D Systems Integration Conference, 2016

2015

Mass-surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks.

[BibT_eX]

[DOI]

Mihir Bellare

Joseph Jaeger

IACR Cryptol. ePrint Arch., 2015

Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits.

[BibT_eX]

[DOI]

Ryan Williams

Electron. Colloquium Comput. Complex., 2015

Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables.

[BibT_eX]

[DOI]

CoRR, 2015

Central limit theorems for some set partition statistics.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2015

Testing Identity of Structured Distributions.

[BibT_eX]

[DOI]

Vladimir Nikishkin

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

Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions.

[BibT_eX]

[DOI]

Vladimir Nikishkin

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

A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Sparser Johnson-Lindenstrauss Transforms.

[BibT_eX]

[DOI]

J. ACM, 2014

Pseudorandomness for concentration bounds and signed majorities.

[BibT_eX]

[DOI]

Parikshit Gopalan

CoRR, 2014

The correct exponent for the Gotsman-Linial Conjecture.

[BibT_eX]

[DOI]

Comput. Complex., 2014

The average sensitivity of an intersection of half spaces.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

A Pseudorandom Generator for Polynomial Threshold Functions of Gaussian with Subpolynomial Seed Length.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta.

[BibT_eX]

[DOI]

Theory Comput., 2013

A Short Implicant of CNFs with Relatively Many Satisfying Assignments.

[BibT_eX]

[DOI]

Osamu Watanabe

Electron. Colloquium Comput. Complex., 2013

A PRG for lipschitz functions of polynomials with applications to sparsest cut.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching.

[BibT_eX]

[DOI]

Adam R. Klivans

Proceedings of the COLT 2013, 2013

2012

A Low-Depth Monotone Function that is not an Approximate Junta

[BibT_eX]

[DOI]

CoRR, 2012

A Structure Theorem for Poorly Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions.

[BibT_eX]

[DOI]

CoRR, 2012

Counting Arbitrary Subgraphs in Data Streams.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Tight Bounds for Testing k-Linearity.

[BibT_eX]

[DOI]

Eric Blais

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Quantum interpolation of polynomials.

[BibT_eX]

[DOI]

Samuel A. Kutin

Quantum Inf. Comput., 2011

The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Comput. Complex., 2011

Fast moment estimation in data streams in optimal space.

[BibT_eX]

[DOI]

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

A Small PRG for Polynomial Threshold Functions of Gaussians.

[BibT_eX]

[DOI]

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

k-Independent Gaussians Fool Polynomial Threshold Functions.

[BibT_eX]

[DOI]

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

Almost Optimal Explicit Johnson-Lindenstrauss Families.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

On Solving Games Constructed Using Both Short and Long Conjunctive Sums.

[BibT_eX]

[DOI]

Integers, 2010

A Derandomized Sparse Johnson-Lindenstrauss Transform.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Almost Optimal Explicit Johnson-Lindenstrauss Transformations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

A Sparser Johnson-Lindenstrauss Transform

[BibT_eX]

[DOI]

CoRR, 2010

Unary Subset-Sum is in Logspace

[BibT_eX]

[DOI]

CoRR, 2010

On the Exact Space Complexity of Sketching and Streaming Small Norms.

[BibT_eX]

[DOI]

David P. Woodruff

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

An optimal algorithm for the distinct elements problem.

[BibT_eX]

[DOI]

David P. Woodruff

Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Bounded Independence Fools Degree-2 Threshold Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials

[BibT_eX]

[DOI]

CoRR, 2009

Dynamic ham-sandwich cuts in the plane.

[BibT_eX]

[DOI]

Comput. Geom., 2009

The geometry of binary search trees.

[BibT_eX]

[DOI]

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

A Pseudopolynomial Algorithm for Alexandrov's Theorem.

[BibT_eX]

[DOI]

Gregory Nathan Price

Erik D. Demaine

Proceedings of the Computational Geometry, 08.03. - 13.03.2009, 2009

2008

Revisiting Norm Estimation in Data Streams

[BibT_eX]

[DOI]

David P. Woodruff

CoRR, 2008

On the Sn-Modules Generated by Partitions of a Given Shape.

[BibT_eX]

[DOI]

Steven Sivek

Electron. J. Comb., 2008

2005

On the Complexity of Two-PlayerWin-Lose Games.

[BibT_eX]

[DOI]

Timothy G. Abbott