Madhur Tulsiani

According to our database, Madhur Tulsiani authored at least 56 papers between 2006 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

Inapproximability of Matrix p → q Norms.

Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

SIAM J. Comput., February, 2023

Ellipsoid fitting up to constant via empirical covariance estimation.

Madhur Tulsiani, June Wu

CoRR, 2023

Concentration of polynomial random matrices via Efron-Stein inequalities.

Goutham Rajendran, Madhur Tulsiani

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

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

Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani

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

2022

Explicit Abelian Lifts and Quantum LDPC Codes.

Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani

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

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

Vijay Bhattiprolu, Euiwoong Lee, Madhur Tulsiani

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

2021

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

Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani

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

Explicit SoS Lower Bounds from High-Dimensional Expanders.

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

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

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

Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu

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.

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2020

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

Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani

CoRR, 2020

List Decoding of Direct Sum Codes.

Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani

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

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

Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani

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.

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

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

Approximating Constraint Satisfaction Problems on High-Dimensional Expanders.

Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani

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.

Mrinalkanti Ghosh, Madhur Tulsiani

Theory Comput., 2018

Approximating Operator Norms via Generalized Krivine Rounding.

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2018

Inapproximability of Matrix p→q Norms.

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2018

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

Pooya Hatami, Madhur Tulsiani

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

2017

Finding Pseudorandom Colorings of Pseudorandom Graphs.

Akash Kumar, Anand Louis, Madhur Tulsiani

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.

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

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

2016

From Weak to Strong LP Gaps for all CSPs.

Mrinalkanti Ghosh, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2016

Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere.

Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2016

Proving Weak Approximability Without Algorithms.

Ridwan Syed, Madhur Tulsiani

Proceedings of the Approximation, 2016

2015

Algorithmic regularity for polynomials and applications.

Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani

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

2014

Linear Programming Hierarchies Suffice for Directed Steiner Tree.

Zachary Friggstad, Jochen Könemann, Young Kun-Ko, Anand Louis, Mohammad Shadravan, Madhur Tulsiani

Proceedings of the Integer Programming and Combinatorial Optimization, 2014

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

Madhur Tulsiani, John Wright, Yuan Zhou

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

2013

A Characterization of Approximation Resistance.

Subhash Khot, Madhur Tulsiani, Pratik Worah

Electron. Colloquium Comput. Complex., 2013

A Characterization of Strong Approximation Resistance.

Subhash Khot, Madhur Tulsiani, Pratik Worah

Electron. Colloquium Comput. Complex., 2013

An Arithmetic Analogue of Fox's Triangle Removal Argument

Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani

CoRR, 2013

LS+ Lower Bounds from Pairwise Independence.

Madhur Tulsiani, Pratik Worah

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

SDP Gaps from Pairwise Independence.

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

Theory Comput., 2012

$LS_+$ Lower Bounds from Pairwise Independence.

Madhur Tulsiani, Pratik Worah

Electron. Colloquium Comput. Complex., 2012

The Complexity of Somewhat Approximation Resistant Predicates.

Subhash Khot, Madhur Tulsiani, Pratik Worah

Electron. Colloquium Comput. Complex., 2012

Towards An Optimal Query Efficient PCP?

Subhash Khot, Muli Safra, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2012

Sampling-based proofs of almost-periodicity results and algorithmic applications.

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf

Electron. Colloquium Comput. Complex., 2012

Graph densification.

Moritz Hardt, Nikhil Srivastava, Madhur Tulsiani

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

Quadratic Goldreich-Levin Theorems.

Madhur Tulsiani, Julia Wolf

Electron. Colloquium Comput. Complex., 2011

Cuts in Cartesian Products of Graphs

Sushant Sachdeva, Madhur Tulsiani

CoRR, 2011

On LP-Based Approximability for Strict CSPs.

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi

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

Algorithms and Hardness for Subspace Approximation.

Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi

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

2010

Reductions Between Expansion Problems.

Prasad Raghavendra, David Steurer, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2010

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

Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu

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

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

Anindya De, Luca Trevisan, Madhur Tulsiani

Proceedings of the Advances in Cryptology, 2010

2009

Local Constraints in Combinatorial Optimization.

Madhur Tulsiani

PhD thesis, 2009

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

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi

Electron. Colloquium Comput. Complex., 2009

Optimal Sherali-Adams Gaps from Pairwise Independence.

Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2009

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

Anindya De, Luca Trevisan, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2009

Improved Pseudorandom Generators for Depth 2 Circuits.

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2009

Algorithms and Hardness for Subspace Approximation

Amit Deshpande, Kasturi R. Varadarajan, Madhur Tulsiani, Nisheeth K. Vishnoi

CoRR, 2009

2008

CSP Gaps and Reductions in the Lasserre Hierarchy.

Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2008

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

Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2008

Dense Subsets of Pseudorandom Sets.

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2008

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

Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi

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

2006

Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut.

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2006

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

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2006