Aravindan Vijayaraghavan

Liren Shan

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

Error-Tolerant E-Discovery Protocols.

[BibT_eX]

[DOI]

Jinshuo Dong

Jason D. Hartline

Liren Shan

Proceedings of the Symposium on Computer Science and Law, 2024

2023

A hierarchy of eigencomputations for polynomial optimization on the sphere.

[BibT_eX]

[DOI]

Nathaniel Johnston

Benjamin Lovitz

CoRR, 2023

Agnostic Learning of General ReLU Activation Using Gradient Descent.

[BibT_eX]

[DOI]

Alex Tang

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond.

[BibT_eX]

[DOI]

Nathaniel Johnston

Benjamin Lovitz

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Smoothed analysis for tensor methods in unsupervised learning.

[BibT_eX]

[DOI]

Aidan Perreault

Math. Program., 2022

The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound.

[BibT_eX]

[DOI]

Liam O'Carroll

Vaidehi Srinivas

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

Training Subset Selection for Weak Supervision.

[BibT_eX]

[DOI]

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

Effective and Inconspicuous Over-the-Air Adversarial Examples with Adaptive Filtering.

[BibT_eX]

[DOI]

Patrick O'Reilly

Bryan Pardo

Proceedings of the IEEE International Conference on Acoustics, 2022

Classification Protocols with Minimal Disclosure.

[BibT_eX]

[DOI]

Jinshuo Dong

Jason D. Hartline

Proceedings of the 2022 Symposium on Computer Science and Law, 2022

Algorithms for learning a mixture of linear classifiers.

[BibT_eX]

[DOI]

Anindya De

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

Understanding Simultaneous Train and Test Robustness.

[BibT_eX]

[DOI]

Sivaraman Balakrishnan

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

2021

Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations.

[BibT_eX]

[DOI]

Alex Tang

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

Graph Cuts Always Find a Global Optimum for Potts Models (With a Catch).

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Adversarially Robust Low Dimensional Representations.

[BibT_eX]

[DOI]

Vaggos Chatziafratis

Xue Chen

Proceedings of the Conference on Learning Theory, 2021

Learning a mixture of two subspaces over finite fields.

[BibT_eX]

[DOI]

Anindya De

Proceedings of the Algorithmic Learning Theory, 2021

Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances.

[BibT_eX]

[DOI]

Aravind Reddy

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

Graph cuts always find a global optimum (with a catch).

[BibT_eX]

[DOI]

CoRR, 2020

Efficient Tensor Decomposition.

[BibT_eX]

[DOI]

CoRR, 2020

Adversarial robustness via robust low rank representations.

[BibT_eX]

[DOI]

Himanshu Jain

Ankit Singh Rawat

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

Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay.

[BibT_eX]

[DOI]

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

Estimating Principal Components under Adversarial Perturbations.

[BibT_eX]

[DOI]

Xue Chen

Proceedings of the Conference on Learning Theory, 2020

Efficient Tensor Decompositions.

[BibT_eX]

[DOI]

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

2019

On Robustness to Adversarial Examples and Polynomial Optimization.

[BibT_eX]

[DOI]

Abhratanu Dutta

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

Smoothed Analysis in Unsupervised Learning via Decoupling.

[BibT_eX]

[DOI]

Aidan Perreault

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

Block Stability for MAP Inference.

[BibT_eX]

[DOI]

Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019

2018

Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue.

[BibT_eX]

[DOI]

Qin Zhang

ACM Trans. Algorithms, 2018

Clustering Semi-Random Mixtures of Gaussians.

[BibT_eX]

[DOI]

Proceedings of the 35th International Conference on Machine Learning, 2018

Towards Learning Sparsely Used Dictionaries with Arbitrary Supports.

[BibT_eX]

[DOI]

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

Optimality of Approximate Inference Algorithms on Stable Instances.

[BibT_eX]

[DOI]

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

2017

Alpha-expansion is Exact on Stable Instances.

[BibT_eX]

[DOI]

CoRR, 2017

Approximation Algorithms for Label Cover and The Log-Density Threshold.

[BibT_eX]

[DOI]

Eden Chlamtác

Pasin Manurangsi

Dana Moshkovitz

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Clustering Stable Instances of Euclidean k-means.

[BibT_eX]

[DOI]

Abhratanu Dutta

Alex Wang

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

On Learning Mixtures of Well-Separated Gaussians.

[BibT_eX]

[DOI]

Oded Regev

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

2016

Approximation Algorithms and Hardness of the k-Route Cut Problem.

[BibT_eX]

[DOI]

Julia Chuzhoy

ACM Trans. Algorithms, 2016

Learning Communities in the Presence of Errors.

[BibT_eX]

[DOI]

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

[BibT_eX]

[DOI]

David Witmer

John Wright

Electron. Colloquium Comput. Complex., 2015

Correlation Clustering with Noisy Partial Information.

[BibT_eX]

[DOI]

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Algorithms for Semi-random Correlation Clustering.

[BibT_eX]

[DOI]

CoRR, 2014

Constant factor approximation for balanced cut in the PIE model.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Smoothed analysis of tensor decompositions.

[BibT_eX]

[DOI]

Ankur Moitra

Proceedings of the Symposium on Theory of Computing, 2014

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut.

[BibT_eX]

[DOI]

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

Learning Mixtures of Ranking Models.

[BibT_eX]

[DOI]

Avrim Blum

Or Sheffet

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability.

[BibT_eX]

[DOI]

Proceedings of The 27th Conference on Learning Theory, 2014

Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold?

[BibT_eX]

[DOI]

Ankur Moitra

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Bilu-Linial Stable Instances of Max Cut

[BibT_eX]

[DOI]

CoRR, 2013

Sorting noisy data with partial information.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Approximation Algorithms for Semi-random Graph Partitioning Problems

[BibT_eX]

[DOI]

CoRR, 2012

Approximation algorithms for semi-random partitioning problems.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph.

[BibT_eX]

[DOI]

Venkatesan Guruswami

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

On Quadratic Programming with a Ratio Objective.

[BibT_eX]

[DOI]

Rajsekar Manokaran

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

2011

Approximation Algorithms and Hardness of the k-Route Cut Problem

[BibT_eX]

[DOI]

Julia Chuzhoy

CoRR, 2011

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

[BibT_eX]

[DOI]

Venkatesan Guruswami

CoRR, 2011

Approximating Matrix p-norms.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph

[BibT_eX]

[DOI]

CoRR, 2010

Computing the Matrix p-norm

[BibT_eX]

[DOI]

CoRR, 2010

Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph.

[BibT_eX]

[DOI]