default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMadhur Tulsiani
Person information
SPARQL queries 
🛈 Please note that only 53% of the records listed on this page have a DOI. Therefore, DOI-based queries can only provide partial results.
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c40]Ainesh Bakshi, Pravesh K. Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan:
Efficient Certificates of Anti-Concentration Beyond Gaussians. FOCS 2024: 970-987- [i45]Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan:
Efficient Certificates of Anti-Concentration Beyond Gaussians. CoRR abs/2405.15084 (2024) - 2023
- [j4]Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee
, Madhur Tulsiani:
Inapproximability of Matrix p → q Norms. SIAM J. Comput. 52(1): 132-155 (2023) - [c39]Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani:
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates. FOCS 2023: 1682-1693 - [c38]Goutham Rajendran, Madhur Tulsiani:
Concentration of polynomial random matrices via Efron-Stein inequalities. SODA 2023: 3614-3653 - [i44]Madhur Tulsiani, June Wu:
Ellipsoid fitting up to constant via empirical covariance estimation. CoRR abs/2307.10941 (2023) - [i43]Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani:
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates. CoRR abs/2311.02263 (2023) - 2022
- [c37]Vijay Bhattiprolu, Euiwoong Lee, Madhur Tulsiani:
Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem. ITCS 2022: 22:1-22:17 - [c36]Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani:
Explicit Abelian Lifts and Quantum LDPC Codes. ITCS 2022: 88:1-88:21 - [i42]Goutham Rajendran, Madhur Tulsiani:
Concentration of polynomial random matrices via Efron-Stein inequalities. CoRR abs/2209.02655 (2022) - 2021
- [c35]Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu:
Sum-of-Squares Lower Bounds for Sparse Independent Set. FOCS 2021: 406-416 - [c34]Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani:
Explicit SoS Lower Bounds from High-Dimensional Expanders. ITCS 2021: 38:1-38:16 - [c33]Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani:
Near-linear time decoding of Ta-Shma's codes via splittable regularity. STOC 2021: 1527-1536 - [i41]Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu:
Sum-of-Squares Lower Bounds for Sparse Independent Set. CoRR abs/2111.09250 (2021) - [i40]Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani:
Explicit Abelian Lifts and Quantum LDPC Codes. CoRR abs/2112.01647 (2021) - 2020
- [c32]Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani:
Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound. FOCS 2020: 434-445 - [c31]Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani:
List Decoding of Direct Sum Codes. SODA 2020: 1412-1425 - [e1]Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy:
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. ACM 2020, ISBN 978-1-4503-6979-4 [contents] - [i39]Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani:
Explicit SoS lower bounds from high-dimensional expanders. CoRR abs/2009.05218 (2020) - [i38]Vedat Levi Alev, Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani:
List Decoding of Direct Sum Codes. CoRR abs/2011.05467 (2020) - [i37]Fernando Granha Jeronimo, Dylan Quintana, Shashank Srivastava, Madhur Tulsiani:
Unique Decoding of Explicit ε-balanced Codes Near the Gilbert-Varshamov Bound. CoRR abs/2011.05500 (2020) - [i36]Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani:
Explicit and structured sum of squares lower bounds from high dimensional expanders. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [c30]Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani:
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. FOCS 2019: 180-201 - [c29]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. SODA 2019: 1358-1368 - [i35]Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani:
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. CoRR abs/1907.07833 (2019) - 2018
- [j3]Mrinalkanti Ghosh, Madhur Tulsiani:
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems. Theory Comput. 14(1): 1-33 (2018) - [c28]Pooya Hatami, Madhur Tulsiani:
Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius. SODA 2018: 663-679 - [i34]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Inapproximability of Matrix p→q Norms. CoRR abs/1802.07425 (2018) - [i33]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Approximating Operator Norms via Generalized Krivine Rounding. CoRR abs/1804.03644 (2018) - [i32]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Inapproximability of Matrix p→q Norms. Electron. Colloquium Comput. Complex. TR18 (2018) - [i31]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Approximating Operator Norms via Generalized Krivine Rounding. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c27]Mrinalkanti Ghosh, Madhur Tulsiani:
From Weak to Strong LP Gaps for All CSPs. CCC 2017: 11:1-11:27 - [c26]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. FOCS 2017: 1008-1019 - [c25]Akash Kumar, Anand Louis, Madhur Tulsiani:
Finding Pseudorandom Colorings of Pseudorandom Graphs. FSTTCS 2017: 37:1-37:12 - 2016
- [c24]Ridwan Syed, Madhur Tulsiani:
Proving Weak Approximability Without Algorithms. APPROX-RANDOM 2016: 20:1-20:15 - [i30]Mrinalkanti Ghosh, Madhur Tulsiani:
From Weak to Strong LP Gaps for all CSPs. CoRR abs/1608.00497 (2016) - [i29]Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Euiwoong Lee, Venkatesan Guruswami, Madhur Tulsiani:
Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. CoRR abs/1611.05998 (2016) - [i28]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. TR16 (2016) - [i27]Mrinalkanti Ghosh, Madhur Tulsiani:
From Weak to Strong LP Gaps for all CSPs. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [c23]Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani:
Algorithmic regularity for polynomials and applications. SODA 2015: 1870-1889 - 2014
- [j2]Madhur Tulsiani, Julia Wolf:
Quadratic Goldreich-Levin Theorems. SIAM J. Comput. 43(2): 730-766 (2014) - [c22]Subhash Khot, Madhur Tulsiani, Pratik Worah:
The Complexity of Somewhat Approximation Resistant Predicates. ICALP (1) 2014: 689-700 - [c21]Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf:
Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications. ICALP (1) 2014: 955-966 - [c20]Madhur Tulsiani, John Wright, Yuan Zhou:
Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs. ICALP (1) 2014: 1003-1014 - [c19]Zachary Friggstad, Jochen Könemann, Young Kun-Ko, Anand Louis, Mohammad Shadravan, Madhur Tulsiani:
Linear Programming Hierarchies Suffice for Directed Steiner Tree. IPCO 2014: 285-296 - [c18]Subhash Khot, Madhur Tulsiani, Pratik Worah:
A characterization of strong approximation resistance. STOC 2014: 634-643 - 2013
- [c17]Madhur Tulsiani, Pratik Worah:
LS+ Lower Bounds from Pairwise Independence. CCC 2013: 121-132 - [c16]Subhash Khot, Muli Safra, Madhur Tulsiani:
Towards an optimal query efficient PCP? ITCS 2013: 173-186 - [i26]Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani:
An Arithmetic Analogue of Fox's Triangle Removal Argument. CoRR abs/1304.4921 (2013) - [i25]Subhash Khot, Madhur Tulsiani, Pratik Worah:
A Characterization of Strong Approximation Resistance. CoRR abs/1305.5500 (2013) - [i24]Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani:
Algorithmic regularity for polynomials and applications. CoRR abs/1311.5090 (2013) - [i23]Subhash Khot, Madhur Tulsiani, Pratik Worah:
A Characterization of Strong Approximation Resistance. Electron. Colloquium Comput. Complex. TR13 (2013) - [i22]Subhash Khot, Madhur Tulsiani, Pratik Worah:
A Characterization of Approximation Resistance. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j1]Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, Madhur Tulsiani:
SDP Gaps from Pairwise Independence. Theory Comput. 8(1): 269-289 (2012) - [c15]Prasad Raghavendra, David Steurer, Madhur Tulsiani:
Reductions between Expansion Problems. CCC 2012: 64-73 - [c14]Moritz Hardt, Nikhil Srivastava, Madhur Tulsiani:
Graph densification. ITCS 2012: 380-392 - [i21]Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf:
Sampling-based proofs of almost-periodicity results and algorithmic applications. CoRR abs/1210.6917 (2012) - [i20]Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf:
Sampling-based proofs of almost-periodicity results and algorithmic applications. Electron. Colloquium Comput. Complex. TR12 (2012) - [i19]Subhash Khot, Muli Safra, Madhur Tulsiani:
Towards An Optimal Query Efficient PCP? Electron. Colloquium Comput. Complex. TR12 (2012) - [i18]Subhash Khot, Madhur Tulsiani, Pratik Worah:
The Complexity of Somewhat Approximation Resistant Predicates. Electron. Colloquium Comput. Complex. TR12 (2012) - [i17]Madhur Tulsiani, Pratik Worah:
$LS_+$ Lower Bounds from Pairwise Independence. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [c13]Madhur Tulsiani, Julia Wolf:
Quadratic Goldreich-Levin Theorems. FOCS 2011: 619-628 - [c12]Amit Deshpande, Madhur Tulsiani, Nisheeth K. Vishnoi:
Algorithms and Hardness for Subspace Approximation. SODA 2011: 482-496 - [c11]Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi:
On LP-Based Approximability for Strict CSPs. SODA 2011: 1560-1573 - [i16]Sushant Sachdeva, Madhur Tulsiani:
Cuts in Cartesian Products of Graphs. CoRR abs/1105.3383 (2011) - [i15]Madhur Tulsiani, Julia Wolf:
Quadratic Goldreich-Levin Theorems. CoRR abs/1105.4372 (2011) - [i14]Madhur Tulsiani, Julia Wolf:
Quadratic Goldreich-Levin Theorems. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [c10]Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani:
Improved Pseudorandom Generators for Depth 2 Circuits. APPROX-RANDOM 2010: 504-517 - [c9]Anindya De, Luca Trevisan, Madhur Tulsiani:
Time Space Tradeoffs for Attacks against One-Way Functions and PRGs. CRYPTO 2010: 649-665 - [c8]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: 617-628 - [i13]Prasad Raghavendra, David Steurer, Madhur Tulsiani:
Reductions Between Expansion Problems. CoRR abs/1011.2586 (2010) - [i12]Prasad Raghavendra, David Steurer, Madhur Tulsiani:
Reductions Between Expansion Problems. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [b1]Madhur Tulsiani:
Local Constraints in Combinatorial Optimization. University of California, Berkeley, USA, 2009 - [c7]Konstantinos Georgiou, Avner Magen, Madhur Tulsiani:
Optimal Sherali-Adams Gaps from Pairwise Independence. APPROX-RANDOM 2009: 125-139 - [c6]Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. CCC 2009: 126-136 - [c5]Madhur Tulsiani:
CSP gaps and reductions in the lasserre hierarchy. STOC 2009: 303-312 - [i11]Amit Deshpande, Kasturi R. Varadarajan, Madhur Tulsiani, Nisheeth K. Vishnoi:
Algorithms and Hardness for Subspace Approximation. CoRR abs/0912.1403 (2009) - [i10]Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi:
On the Optimality of a Class of LP-based Algorithms. CoRR abs/0912.1776 (2009) - [i9]Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani:
Improved Pseudorandom Generators for Depth 2 Circuits. Electron. Colloquium Comput. Complex. TR09 (2009) - [i8]Anindya De, Luca Trevisan, Madhur Tulsiani:
Non-uniform attacks against one-way functions and PRGs. Electron. Colloquium Comput. Complex. TR09 (2009) - [i7]Konstantinos Georgiou, Avner Magen, Madhur Tulsiani:
Optimal Sherali-Adams Gaps from Pairwise Independence. Electron. Colloquium Comput. Complex. TR09 (2009) - [i6]Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi:
On the Optimality of a Class of LP-based Algorithms. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [c4]Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
Dense Subsets of Pseudorandom Sets. FOCS 2008: 76-85 - [c3]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: 21-28 - [i5]Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
Dense Subsets of Pseudorandom Sets. Electron. Colloquium Comput. Complex. TR08 (2008) - [i4]Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. Electron. Colloquium Comput. Complex. TR08 (2008) - [i3]Madhur Tulsiani:
CSP Gaps and Reductions in the Lasserre Hierarchy. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [c2]Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. CCC 2007: 205-216 - [c1]Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
Tight integrality gaps for Lovasz-Schrijver LP relaxations of vertex cover and max cut. STOC 2007: 302-310 - 2006
- [i2]Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. Electron. Colloquium Comput. Complex. TR06 (2006) - [i1]Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut. Electron. Colloquium Comput. Complex. TR06 (2006)
Coauthor Index
Vijay Bhattiprolu
aka: Vijay V. S. P. Bhattiprolu
aka: Vijay V. S. P. Bhattiprolu
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-10 20:45 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
