Madhur Tulsiani

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