Madhur Tulsiani

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 39

Top Topics

Linear Programming

Decoding Algorithm

Constraint Satisfaction

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan
Efficient Certificates of Anti-Concentration Beyond Gaussians. CoRR (2024)
Madhur Tulsiani, June Wu
Ellipsoid fitting up to constant via empirical covariance estimation. CoRR (2023)
Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Inapproximability of Matrix p → q Norms. SIAM J. Comput. 52 (1) (2023)
Goutham Rajendran, Madhur Tulsiani
Concentration of polynomial random matrices via Efron-Stein inequalities. SODA (2023)
Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates. CoRR (2023)
Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates. FOCS (2023)
Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani
Explicit Abelian Lifts and Quantum LDPC Codes. ITCS (2022)
Goutham Rajendran, Madhur Tulsiani
Concentration of polynomial random matrices via Efron-Stein inequalities. CoRR (2022)
Vijay Bhattiprolu, Euiwoong Lee, Madhur Tulsiani
Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem. ITCS (2022)
Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu
Sum-of-Squares Lower Bounds for Sparse Independent Set. FOCS (2022)
Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu
Sum-of-Squares Lower Bounds for Sparse Independent Set. FOCS (2021)
Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani
Explicit Abelian Lifts and Quantum LDPC Codes. CoRR (2021)
Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu
Sum-of-Squares Lower Bounds for Sparse Independent Set. CoRR (2021)
Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani
Near-linear time decoding of Ta-Shma's codes via splittable regularity. STOC (2021)
Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani
Explicit SoS Lower Bounds from High-Dimensional Expanders. ITCS (2021)
Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani
List Decoding of Direct Sum Codes. SODA (2020)
Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani
Explicit SoS lower bounds from high-dimensional expanders. CoRR (2020)
Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani
Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound. FOCS (2020)
Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani
Unique Decoding of Explicit ε-balanced Codes Near the Gilbert-Varshamov Bound. CoRR (2020)
Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani
Explicit and structured sum of squares lower bounds from high dimensional expanders. Electron. Colloquium Comput. Complex. 27 (2020)
Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani
List Decoding of Direct Sum Codes. CoRR (2020)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. SODA (2019)
Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. CoRR (2019)
Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. FOCS (2019)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Approximating Operator Norms via Generalized Krivine Rounding. CoRR (2018)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Inapproximability of Matrix p→q Norms. Electron. Colloquium Comput. Complex. 25 (2018)
Mrinalkanti Ghosh, Madhur Tulsiani
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems. Theory Comput. 14 (1) (2018)
Pooya Hatami, Madhur Tulsiani
Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius. SODA (2018)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Approximating Operator Norms via Generalized Krivine Rounding. Electron. Colloquium Comput. Complex. 25 (2018)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Inapproximability of Matrix p→q Norms. CoRR (2018)
Akash Kumar, Anand Louis, Madhur Tulsiani
Finding Pseudorandom Colorings of Pseudorandom Graphs. FSTTCS (2017)
Mrinalkanti Ghosh, Madhur Tulsiani
From Weak to Strong LP Gaps for All CSPs. Computational Complexity Conference (2017)
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. FOCS (2017)
Mrinalkanti Ghosh, Madhur Tulsiani
From Weak to Strong LP Gaps for all CSPs. CoRR (2016)
Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. Electron. Colloquium Comput. Complex. 23 (2016)
Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Euiwoong Lee, Venkatesan Guruswami, Madhur Tulsiani
Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. CoRR (2016)
Ridwan Syed, Madhur Tulsiani
Proving Weak Approximability Without Algorithms. APPROX-RANDOM (2016)
Mrinalkanti Ghosh, Madhur Tulsiani
From Weak to Strong LP Gaps for all CSPs. Electron. Colloquium Comput. Complex. 23 (2016)
Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani
Algorithmic regularity for polynomials and applications. SODA (2015)
Subhash Khot, Madhur Tulsiani, Pratik Worah
The Complexity of Somewhat Approximation Resistant Predicates. ICALP (1) (2014)
Zachary Friggstad, Jochen Könemann, Young Kun-Ko, Anand Louis, Mohammad Shadravan, Madhur Tulsiani
Linear Programming Hierarchies Suffice for Directed Steiner Tree. IPCO (2014)
Subhash Khot, Madhur Tulsiani, Pratik Worah
A characterization of strong approximation resistance. STOC (2014)
Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf
Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications. ICALP (1) (2014)
Madhur Tulsiani, John Wright, Yuan Zhou
Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs. ICALP (1) (2014)
Madhur Tulsiani, Julia Wolf
Quadratic Goldreich-Levin Theorems. SIAM J. Comput. 43 (2) (2014)
Subhash Khot, Madhur Tulsiani, Pratik Worah
A Characterization of Approximation Resistance. Electron. Colloquium Comput. Complex. 20 (2013)
Madhur Tulsiani, Pratik Worah
LS+ Lower Bounds from Pairwise Independence. Computational Complexity Conference (2013)
Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani
Algorithmic regularity for polynomials and applications. CoRR (2013)
Subhash Khot, Madhur Tulsiani, Pratik Worah
A Characterization of Strong Approximation Resistance CoRR (2013)
Subhash Khot, Muli Safra, Madhur Tulsiani
Towards an optimal query efficient PCP? ITCS (2013)
Subhash Khot, Madhur Tulsiani, Pratik Worah
A Characterization of Strong Approximation Resistance. Electron. Colloquium Comput. Complex. 20 (2013)
Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani
An Arithmetic Analogue of Fox's Triangle Removal Argument CoRR (2013)
Madhur Tulsiani, Pratik Worah
$LS_+$ Lower Bounds from Pairwise Independence. Electron. Colloquium Comput. Complex. 19 (2012)
Subhash Khot, Muli Safra, Madhur Tulsiani
Towards An Optimal Query Efficient PCP? Electron. Colloquium Comput. Complex. 19 (2012)
Moritz Hardt, Nikhil Srivastava, Madhur Tulsiani
Graph densification. ITCS (2012)
Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf
Sampling-based proofs of almost-periodicity results and algorithmic applications. Electron. Colloquium Comput. Complex. 19 (2012)
Subhash Khot, Madhur Tulsiani, Pratik Worah
The Complexity of Somewhat Approximation Resistant Predicates. Electron. Colloquium Comput. Complex. 19 (2012)
Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf
Sampling-based proofs of almost-periodicity results and algorithmic applications CoRR (2012)
Prasad Raghavendra, David Steurer, Madhur Tulsiani
Reductions between Expansion Problems. Computational Complexity Conference (2012)
Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, Madhur Tulsiani
SDP Gaps from Pairwise Independence. Theory Comput. 8 (1) (2012)
Sushant Sachdeva, Madhur Tulsiani
Cuts in Cartesian Products of Graphs CoRR (2011)
Madhur Tulsiani, Julia Wolf
Quadratic Goldreich-Levin Theorems. Electron. Colloquium Comput. Complex. 18 (2011)
Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi
Algorithms and Hardness for Subspace Approximation. SODA (2011)
Madhur Tulsiani, Julia Wolf
Quadratic Goldreich-Levin Theorems CoRR (2011)
Madhur Tulsiani, Julia Wolf
Quadratic Goldreich-Levin Theorems. FOCS (2011)
Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi
On LP-Based Approximability for Strict CSPs. SODA (2011)
Prasad Raghavendra, David Steurer, Madhur Tulsiani
Reductions Between Expansion Problems CoRR (2010)
Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani
Improved Pseudorandom Generators for Depth 2 Circuits. APPROX-RANDOM (2010)
Anindya De, Luca Trevisan, Madhur Tulsiani
Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. CRYPTO (2010)
Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu
SDP Gaps for 2-to-1 and Other Label-Cover Variants. ICALP (1) (2010)
Prasad Raghavendra, David Steurer, Madhur Tulsiani
Reductions Between Expansion Problems. Electron. Colloquium Comput. Complex. 17 (2010)
Madhur Tulsiani
CSP gaps and reductions in the lasserre hierarchy. STOC (2009)
Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi
On the Optimality of a Class of LP-based Algorithms. Electron. Colloquium Comput. Complex. 16 (2009)
Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi
On the Optimality of a Class of LP-based Algorithms CoRR (2009)
Amit Deshpande, Kasturi R. Varadarajan, Madhur Tulsiani, Nisheeth K. Vishnoi
Algorithms and Hardness for Subspace Approximation CoRR (2009)
Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani
Improved Pseudorandom Generators for Depth 2 Circuits. Electron. Colloquium Comput. Complex. 16 (2009)
Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. Computational Complexity Conference (2009)
Konstantinos Georgiou, Avner Magen, Madhur Tulsiani
Optimal Sherali-Adams Gaps from Pairwise Independence. Electron. Colloquium Comput. Complex. 16 (2009)
Anindya De, Luca Trevisan, Madhur Tulsiani
Non-uniform attacks against one-way functions and PRGs. Electron. Colloquium Comput. Complex. 16 (2009)
Konstantinos Georgiou, Avner Magen, Madhur Tulsiani
Optimal Sherali-Adams Gaps from Pairwise Independence. APPROX-RANDOM (2009)
Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. Electron. Colloquium Comput. Complex. 15 (103) (2008)
Madhur Tulsiani
CSP Gaps and Reductions in the Lasserre Hierarchy. Electron. Colloquium Comput. Complex. 15 (104) (2008)
Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan
Dense Subsets of Pseudorandom Sets. Electron. Colloquium Comput. Complex. 15 (045) (2008)
Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan
Dense Subsets of Pseudorandom Sets. FOCS (2008)
Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi
Unique games on expanding constraint graphs are easy: extended abstract. STOC (2008)
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. STOC (2007)
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. Computational Complexity Conference (2007)
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut. Electron. Colloquium Comput. Complex. 13 (132) (2006)
Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. Electron. Colloquium Comput. Complex. 13 (098) (2006)