Madhur Tulsiani

Santhoshini Velusamy

CoRR, September, 2025

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time.

[BibT_eX]

[DOI]

CoRR, April, 2025

Explicit Codes Approaching Generalized Singleton Bound using Expanders.

[BibT_eX]

[DOI]

Tushant Mittal

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Ellipsoid fitting up to constant via empirical covariance estimation.

[BibT_eX]

[DOI]

June Wu

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

Simple Norm Bounds for Polynomial Random Matrices via Decoupling.

[BibT_eX]

[DOI]

June Wu

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

2024

List Decodable Quantum LDPC Codes.

[BibT_eX]

[DOI]

Thiago Bergamaschi

Tushant Mittal

CoRR, 2024

Efficient Certificates of Anti-Concentration Beyond Gaussians.

[BibT_eX]

[DOI]

Aravindan Vijayaraghavan

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Inapproximability of Matrix p → q Norms.

[BibT_eX]

[DOI]

SIAM J. Comput., February, 2023

Concentration of polynomial random matrices via Efron-Stein inequalities.

[BibT_eX]

[DOI]

Goutham Rajendran

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

List Decoding of Tanner and Expander Amplified Codes from Distance Certificates.

[BibT_eX]

[DOI]

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

2022

Explicit Abelian Lifts and Quantum LDPC Codes.

[BibT_eX]

[DOI]

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

Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem.

[BibT_eX]

[DOI]

Vijay Bhattiprolu

Euiwoong Lee

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

2021

Near-linear time decoding of Ta-Shma's codes via splittable regularity.

[BibT_eX]

[DOI]

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

Explicit SoS Lower Bounds from High-Dimensional Expanders.

[BibT_eX]

[DOI]

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

Sum-of-Squares Lower Bounds for Sparse Independent Set.

[BibT_eX]

[DOI]

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

2020

Explicit and structured sum of squares lower bounds from high dimensional expanders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Unique Decoding of Explicit ε-balanced Codes Near the Gilbert-Varshamov Bound.

[BibT_eX]

[DOI]

Dylan Quintana

CoRR, 2020

List Decoding of Direct Sum Codes.

[BibT_eX]

[DOI]

Vedat Levi Alev

Dylan Quintana

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

Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound.

[BibT_eX]

[DOI]

Dylan Quintana

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

2019

Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Approximating Constraint Satisfaction Problems on High-Dimensional Expanders.

[BibT_eX]

[DOI]

Vedat Levi Alev

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

2018

From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Mrinalkanti Ghosh

Theory Comput., 2018

Approximating Operator Norms via Generalized Krivine Rounding.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Inapproximability of Matrix p→q Norms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius.

[BibT_eX]

[DOI]

Pooya Hatami

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

2017

Finding Pseudorandom Colorings of Pseudorandom Graphs.

[BibT_eX]

[DOI]

Akash Kumar

Anand Louis

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere.

[BibT_eX]

[DOI]

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

From Weak to Strong LP Gaps for All CSPs.

[BibT_eX]

[DOI]

Mrinalkanti Ghosh

Vijay V. S. P. Bhattiprolu

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Proving Weak Approximability Without Algorithms.

[BibT_eX]

[DOI]

Ridwan Syed

Proceedings of the Approximation, 2016

2015

Algorithmic regularity for polynomials and applications.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Pooya Hatami

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

2014

A characterization of strong approximation resistance.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Linear Programming Hierarchies Suffice for Directed Steiner Tree.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs.

[BibT_eX]

[DOI]

John Wright

Yuan Zhou

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

The Complexity of Somewhat Approximation Resistant Predicates.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

A Characterization of Approximation Resistance.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

An Arithmetic Analogue of Fox's Triangle Removal Argument

[BibT_eX]

[DOI]

Pooya Hatami

Sushant Sachdeva

CoRR, 2013

Towards an optimal query efficient PCP?

[BibT_eX]

[DOI]

Muli Safra

Proceedings of the Innovations in Theoretical Computer Science, 2013

LS+ Lower Bounds from Pairwise Independence.

[BibT_eX]

[DOI]

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

SDP Gaps from Pairwise Independence.

[BibT_eX]

[DOI]

Siavosh Benabbas

Konstantinos Georgiou

Avner Magen

Theory Comput., 2012

$LS_+$ Lower Bounds from Pairwise Independence.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Graph densification.

[BibT_eX]

[DOI]

Moritz Hardt

Nikhil Srivastava

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Reductions between Expansion Problems.

[BibT_eX]

[DOI]

Prasad Raghavendra

David Steurer

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Cuts in Cartesian Products of Graphs

[BibT_eX]

[DOI]

Sushant Sachdeva

CoRR, 2011

On LP-Based Approximability for Strict CSPs.

[BibT_eX]

[DOI]

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

Algorithms and Hardness for Subspace Approximation.

[BibT_eX]

[DOI]

Amit Deshpande

Nisheeth K. Vishnoi

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

Quadratic Goldreich-Levin Theorems.

[BibT_eX]

[DOI]

Julia Wolf

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

2010

SDP Gaps for 2-to-1 and Other Label-Cover Variants.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

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

[BibT_eX]

[DOI]

Anindya De

Proceedings of the Advances in Cryptology, 2010

Improved Pseudorandom Generators for Depth 2 Circuits.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2009

Local Constraints in Combinatorial Optimization.

[BibT_eX]

[DOI]

PhD thesis, 2009

On the Optimality of a Class of LP-based Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

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

[BibT_eX]

[DOI]

Anindya De

Electron. Colloquium Comput. Complex., 2009

Algorithms and Hardness for Subspace Approximation

[BibT_eX]

[DOI]

Amit Deshpande

Kasturi R. Varadarajan

Nisheeth K. Vishnoi

CoRR, 2009

CSP gaps and reductions in the lasserre hierarchy.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution.

[BibT_eX]

[DOI]

Salil P. Vadhan

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Optimal Sherali-Adams Gaps from Pairwise Independence.

[BibT_eX]

[DOI]

Konstantinos Georgiou

Avner Magen

Proceedings of the Approximation, 2009

2008

Unique games on expanding constraint graphs are easy: extended abstract.

[BibT_eX]

[DOI]

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

Dense Subsets of Pseudorandom Sets.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut.

[BibT_eX]

[DOI]

Grant Schoenebeck

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.

[BibT_eX]

[DOI]

Grant Schoenebeck