default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMadhu Sudan 0001
Person information
- affiliation: Harvard University, School of Engineering and Applied Sciences, Boston, MA, USA
- affiliation: Microsoft Research New England, Cambridge, MA, USA
- award (2001): Gödel Prize
Other persons with the same name
- Madhu Sudan (aka: Madhusudan) — disambiguation page
- Madhu Sudan 0002 — SRI International, Menlo Park, CA, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j73]Noah G. Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming approximation resistance of every ordering CSP. Comput. Complex. 33(1): 6 (2024)- [j72]Chi-Ning Chou
, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy:
Sketching Approximability of All Finite CSPs. J. ACM 71(2): 15:1-15:74 (2024) - [j71]Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Decoding Multivariate Multiplicity Codes on Product Sets. IEEE Trans. Inf. Theory 70(1): 154-169 (2024) - [j70]Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Ideal-Theoretic Explanation of Capacity-Achieving Decoding. IEEE Trans. Inf. Theory 70(2): 1107-1123 (2024) - [c130]Anna M. Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan:
Errors are Robustly Tamed in Cumulative Knowledge Processes. COLT 2024: 630-631 - [c129]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. ICALP 2024: 98:1-98:17 - [c128]Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu:
On $k$-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction. ISIT 2024: 879-884 - [c127]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Code Sparsification and its Applications. SODA 2024: 5145-5168 - [c126]Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan:
Local Correction of Linear Functions over the Boolean Cube. STOC 2024: 764-775 - [i135]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. CoRR abs/2402.13151 (2024) - [i134]Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan:
Local Correction of Linear Functions over the Boolean Cube. CoRR abs/2403.20305 (2024) - [i133]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs. CoRR abs/2404.06327 (2024) - [i132]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. CoRR abs/2407.03934 (2024) - [i131]Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan:
Local Correction of Linear Functions over the Boolean Cube. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c125]Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan:
Low-Degree Testing over Grids. APPROX/RANDOM 2023: 41:1-41:22 - [c124]Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy:
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. FOCS 2023: 855-870 - [c123]Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan:
Is This Correct? Let's Check! ITCS 2023: 15:1-15:11 - [c122]Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming complexity of CSPs with randomly ordered constraints. SODA 2023: 4083-4103 - [i130]Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan:
Low-Degree Testing Over Grids. CoRR abs/2305.04983 (2023) - [i129]Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu:
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction. CoRR abs/2308.14993 (2023) - [i128]Anna M. Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan:
Combinative Cumulative Knowledge Processes. CoRR abs/2309.05638 (2023) - [i127]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Code Sparsification and its Applications. CoRR abs/2311.00788 (2023) - [i126]Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan:
An Improved Line-Point Low-Degree Test. CoRR abs/2311.12752 (2023) - [i125]Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan:
An Improved Line-Point Low-Degree Test. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j69]Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan:
General Strong Polarization. J. ACM 69(2): 11:1-11:67 (2022) - [j68]Elena Grigorescu, Madhu Sudan, Minshen Zhu:
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance. IEEE Trans. Inf. Theory 68(10): 6790-6801 (2022) - [j67]Noah Singer, Madhu Sudan:
Point-hyperplane Incidence Geometry and the Log-rank Conjecture. ACM Trans. Comput. Theory 14(2): 7:1-7:16 (2022) - [c121]Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy:
Sketching Approximability of (Weak) Monarchy Predicates. APPROX/RANDOM 2022: 35:1-35:17 - [c120]Madhu Sudan:
Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk). ICALP 2022: 5:1-5:20 - [c119]Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy:
Linear space streaming lower bounds for approximating CSPs. STOC 2022: 275-288 - [i124]Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy:
Sketching Approximability of (Weak) Monarchy Predicates. CoRR abs/2205.02345 (2022) - [i123]Madhu Sudan:
Streaming and Sketching Complexity of CSPs: A survey. CoRR abs/2205.02744 (2022) - [i122]Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming complexity of CSPs with randomly ordered constraints. CoRR abs/2207.07158 (2022) - [i121]Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming beyond sketching for Maximum Directed Cut. CoRR abs/2211.03916 (2022) - [i120]Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan:
Is this correct? Let's check! CoRR abs/2211.12301 (2022) - [i119]Madhu Sudan:
Streaming and Sketching Complexity of CSPs: A survey. Electron. Colloquium Comput. Complex. TR22 (2022) - [i118]Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy:
Sketching Approximability of (Weak) Monarchy Predicates. Electron. Colloquium Comput. Complex. TR22 (2022) - [i117]Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming complexity of CSPs with randomly ordered constraints. Electron. Colloquium Comput. Complex. TR22 (2022) - [i116]Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming beyond sketching for Maximum Directed Cut. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c118]Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming Approximation Resistance of Every Ordering CSP. APPROX-RANDOM 2021: 17:1-17:19 - [c117]Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Ideal-Theoretic Explanation of Capacity-Achieving Decoding. APPROX-RANDOM 2021: 56:1-56:21 - [c116]Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy:
Approximability of all finite CSPs with linear sketches. FOCS 2021: 1197-1208 - [c115]Elena Grigorescu, Madhu Sudan, Minshen Zhu:
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance. ISIT 2021: 2531-2536 - [c114]Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Decoding multivariate multiplicity codes on product sets. STOC 2021: 1489-1501 - [i115]Noah Singer, Madhu Sudan:
Point-hyperplane incidence geometry and the log-rank conjecture. CoRR abs/2101.09592 (2021) - [i114]Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy:
Classification of the streaming approximability of Boolean CSPs. CoRR abs/2102.12351 (2021) - [i113]Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Ideal-theoretic Explanation of Capacity-achieving Decoding. CoRR abs/2103.07930 (2021) - [i112]Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy:
Approximability of all finite CSPs in the dynamic streaming setting. CoRR abs/2105.01161 (2021) - [i111]Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming approximation resistance of every ordering CSP. CoRR abs/2105.01782 (2021) - [i110]Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy:
Linear Space Streaming Lower Bounds for Approximating CSPs. CoRR abs/2106.13078 (2021) - [i109]Omri Ben-Eliezer, Elchanan Mossel, Madhu Sudan:
Information Spread with Error Correction. CoRR abs/2107.06362 (2021) - [i108]Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Ideal-theoretic Explanation of Capacity-achieving Decoding. Electron. Colloquium Comput. Complex. TR21 (2021) - [i107]Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy:
Classification of the streaming approximability of Boolean CSPs. Electron. Colloquium Comput. Complex. TR21 (2021) - [i106]Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy:
Approximability of all finite CSPs in the dynamic streaming setting. Electron. Colloquium Comput. Complex. TR21 (2021) - [i105]Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy:
Linear Space Streaming Lower Bounds for Approximating CSPs. Electron. Colloquium Comput. Complex. TR21 (2021) - [i104]Noah Singer, Madhu Sudan, Santhoshini Velusamy:
Streaming approximation resistance of every ordering CSP. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j66]Mitali Bafna, Srikanth Srinivasan, Madhu Sudan:
Local decoding and testing of polynomials over grids. Random Struct. Algorithms 57(3): 658-694 (2020) - [j65]Madhu Sudan, Himanshu Tyagi, Shun Watanabe:
Communication for Generating Correlation: A Unifying Survey. IEEE Trans. Inf. Theory 66(1): 5-37 (2020) - [j64]Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan:
Optimality of Correlated Sampling Strategies. Theory Comput. 16: 1-18 (2020) - [c113]Noah Golowich, Madhu Sudan:
Round Complexity of Common Randomness Generation: The Amortized Setting. SODA 2020: 1076-1095 - [i103]Elena Grigorescu, Madhu Sudan, Minshen Zhu:
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance. CoRR abs/2011.13737 (2020) - [i102]Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Decoding Multivariate Multiplicity Codes on Product Sets. CoRR abs/2012.01530 (2020) - [i101]Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Decoding Multivariate Multiplicity Codes on Product Sets. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [c112]Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan:
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. FOCS 2019: 382-405 - [c111]Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan:
Algorithmic Polarization for Hidden Markov Models. ITCS 2019: 39:1-39:19 - [c110]Madhu Sudan, Badih Ghazi, Noah Golowich, Mitali Bafna:
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. SODA 2019: 1861-1871 - [i100]Madhu Sudan, Himanshu Tyagi, Shun Watanabe:
Communication for Generating Correlation: A Survey. CoRR abs/1904.09563 (2019) - [i99]Noah Golowich, Madhu Sudan:
Round Complexity of Common Randomness Generation: The Amortized Setting. CoRR abs/1909.00323 (2019) - [i98]Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan:
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. CoRR abs/1909.03478 (2019) - [i97]Madhu Sudan, David Xiang:
A Self-contained Analysis of the Lempel-Ziv Compression Algorithm. CoRR abs/1910.00941 (2019) - 2018
- [j63]Badih Ghazi, Ilan Komargodski, Pravesh K. Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. Comput. Complex. 27(3): 463-509 (2018) - [c109]Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan:
Polar Codes with Exponentially Small Error at Finite Block Length. APPROX-RANDOM 2018: 34:1-34:17 - [c108]Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan:
Synchronization Strings: List Decoding for Insertions and Deletions. ICALP 2018: 76:1-76:14 - [c107]Srikanth Srinivasan, Madhu Sudan:
Local Decoding and Testing of Polynomials over Grids. ITCS 2018: 26:1-26:14 - [c106]Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan:
General strong polarization. STOC 2018: 485-492 - [i96]Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan:
General Strong Polarization. CoRR abs/1802.02718 (2018) - [i95]Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan:
Synchronization Strings: List Decoding for Insertions and Deletions. CoRR abs/1802.08663 (2018) - [i94]Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan:
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. CoRR abs/1808.08907 (2018) - [i93]Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan:
Algorithmic Polarization for Hidden Markov Models. CoRR abs/1810.01969 (2018) - [i92]Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan:
Polar Codes with exponentially small error at finite block length. CoRR abs/1810.04298 (2018) - [i91]Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan:
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. Electron. Colloquium Comput. Complex. TR18 (2018) - [i90]Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan:
General Strong Polarization. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j62]Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan:
Sparse affine-invariant linear codes are locally testable. Comput. Complex. 26(1): 37-77 (2017) - [j61]David Gamarnik, Madhu Sudan:
Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem. SIAM J. Comput. 46(2): 590-619 (2017) - [j60]Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan:
Communication With Imperfectly Shared Randomness. IEEE Trans. Inf. Theory 63(10): 6799-6818 (2017) - [c105]Badih Ghazi, Madhu Sudan:
The Power of Shared Randomness in Uncertain Communication. ICALP 2017: 49:1-49:14 - [c104]Badih Ghazi, Elad Haramaty, Pritish Kamath, Madhu Sudan:
Compression in a Distributed Setting. ITCS 2017: 19:1-19:22 - [c103]Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker:
(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. SODA 2017: 1703-1722 - [i89]Badih Ghazi, Madhu Sudan:
The Power of Shared Randomness in Uncertain Communication. CoRR abs/1705.01082 (2017) - [i88]Srikanth Srinivasan, Madhu Sudan:
Local decoding and testing of polynomials over grids. CoRR abs/1709.06036 (2017) - [i87]Badih Ghazi, Madhu Sudan:
The Power of Shared Randomness in Uncertain Communication. Electron. Colloquium Comput. Complex. TR17 (2017) - [i86]Srikanth Srinivasan, Madhu Sudan:
Local decoding and testing of polynomials over grids. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j59]Elad Haramaty, Madhu Sudan:
Deterministic Compression with Uncertain Priors. Algorithmica 76(3): 630-653 (2016) - [c102]Badih Ghazi, Pritish Kamath, Madhu Sudan:
Decidability of Non-interactive Simulation of Joint Distributions. FOCS 2016: 545-554 - [c101]Badih Ghazi, Pritish Kamath, Madhu Sudan:
Communication Complexity of Permutation-Invariant Functions. SODA 2016: 1902-1921 - [c100]Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. SODA 2016: 2072-2085 - [e1]Madhu Sudan:
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016. ACM 2016, ISBN 978-1-4503-4057-1 [contents] - [i85]Badih Ghazi, Pritish Kamath, Madhu Sudan:
Decidability of Non-Interactive Simulation of Joint Distributions. CoRR abs/1607.04322 (2016) - [i84]Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan:
The Optimality of Correlated Sampling. CoRR abs/1612.01041 (2016) - [i83]Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan:
The Optimality of Correlated Sampling. Electron. Colloquium Comput. Complex. TR16 (2016) - [i82]Badih Ghazi, Pritish Kamath, Madhu Sudan:
Decidability of Non-Interactive Simulation of Joint Distributions. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j58]Elad Haramaty, Noga Ron-Zewi, Madhu Sudan:
Absolutely Sound Testing of Lifted Codes. Theory Comput. 11: 299-338 (2015) - [c99]Alan Guo, Elad Haramaty, Madhu Sudan:
Robust Testing of Lifted Codes with Applications to Low-Degree Testing. FOCS 2015: 825-844 - [c98]Clément Louis Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan:
Communication with Imperfectly Shared Randomness. ITCS 2015: 257-262 - [c97]Michael Kapralov, Sanjeev Khanna, Madhu Sudan:
Streaming Lower Bounds for Approximating MAX-CUT. SODA 2015: 1263-1282 - [c96]Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang:
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. SODA 2015: 1312-1325 - [i81]Ilan Komargodski, Pravesh Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. CoRR abs/1504.04813 (2015) - [i80]Badih Ghazi, Pritish Kamath, Madhu Sudan:
Communication Complexity of Permutation-Invariant Functions. CoRR abs/1506.00273 (2015) - [i79]Badih Ghazi, Pritish Kamath, Madhu Sudan:
Communication Complexity of Permutation-Invariant Functions. Electron. Colloquium Comput. Complex. TR15 (2015) - [i78]Alan Guo, Elad Haramaty, Madhu Sudan:
Robust testing of lifted codes with applications to low-degree testing. Electron. Colloquium Comput. Complex. TR15 (2015) - [i77]Ilan Komargodski, Pravesh Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c95]Alan Guo, Madhu Sudan:
List Decoding Group Homomorphisms Between Supersolvable Groups. APPROX-RANDOM 2014: 737-747 - [c94]David Gamarnik, Madhu Sudan:
Limits of local algorithms over sparse random graphs. ITCS 2014: 369-376 - [c93]Elad Haramaty, Madhu Sudan:
Deterministic compression with uncertain priors. ITCS 2014: 377-386 - [c92]Michael Kapralov, Sanjeev Khanna, Madhu Sudan:
Approximating matching size from random streams. SODA 2014: 734-751 - [c91]Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan:
Optimal error rates for interactive coding I: adaptivity and other settings. STOC 2014: 794-803 - [i76]David Gamarnik, Madhu Sudan:
Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem. CoRR abs/1402.0052 (2014) - [i75]Alan Guo, Madhu Sudan:
List decoding group homomorphisms between supersolvable groups. CoRR abs/1404.4273 (2014) - [i74]Michael Kapralov, Sanjeev Khanna, Madhu Sudan:
Streaming Lower Bounds for Approximating MAX-CUT. CoRR abs/1409.2138 (2014) - [i73]Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan:
Communication with Imperfectly Shared Randomness. CoRR abs/1411.3603 (2014) - [i72]Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan:
Communication with Imperfectly Shared Randomness. Electron. Colloquium Comput. Complex. TR14 (2014) - [i71]Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang:
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j57]Elena Grigorescu, Tali Kaufman, Madhu Sudan:
2-Transitivity is Insufficient for Local Testability. Comput. Complex. 22(1): 137-158 (2013) - [j56]Elad Haramaty, Amir Shpilka, Madhu Sudan:
Optimal Testing of Multivariate Polynomials over Small Prime Fields. SIAM J. Comput. 42(2): 536-562 (2013) - [j55]Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan:
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. SIAM J. Comput. 42(6): 2305-2328 (2013) - [j54]Joel Spencer, Madhu Sudan, Kuang Xu:
Queueing with future information. SIGMETRICS Perform. Evaluation Rev. 41(3): 40-42 (2013) - [j53]Noga Ron-Zewi, Madhu Sudan:
A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes. Theory Comput. 9: 783-807 (2013) - [c90]Elad Haramaty, Noga Ron-Zewi, Madhu Sudan:
Absolutely Sound Testing of Lifted Codes. APPROX-RANDOM 2013: 671-682 - [c89]Alan Guo, Swastik Kopparty, Madhu Sudan:
New affine-invariant codes from lifting. ITCS 2013: 529-540 - [i70]David Gamarnik, Madhu Sudan:
Limits of local algorithms over sparse random graphs. CoRR abs/1304.1831 (2013) - [i69]Katalin Friedl, Madhu Sudan:
Some Improvements to Total Degree Tests. CoRR abs/1307.3975 (2013) - [i68]Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan:
Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings. CoRR abs/1312.1764 (2013) - [i67]David Gamarnik, Madhu Sudan:
Limits of local algorithms over sparse random graphs. Electron. Colloquium Comput. Complex. TR13 (2013) - [i66]Elad Haramaty, Noga Ron-Zewi, Madhu Sudan:
Absolutely Sound Testing of Lifted Codes. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j52]Oded Goldreich, Brendan Juba, Madhu Sudan:
A theory of goal-oriented communication. J. ACM 59(2): 8:1-8:65 (2012) - [j51]Elena Grigorescu, Tali Kaufman, Madhu Sudan:
Succinct Representation of Codes with Applications to Testing. SIAM J. Discret. Math. 26(4): 1618-1634 (2012) - [c88]Noga Ron-Zewi, Madhu Sudan:
A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes. APPROX-RANDOM 2012: 639-650 - [c87]Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan:
Sparse Affine-Invariant Linear Codes Are Locally Testable. FOCS 2012: 561-570 - [c86]Madhu Sudan:
Communication amid uncertainty. ITW 2012: 158-161 - [i65]Noga Ron-Zewi, Madhu Sudan:
A new upper bound on the query complexity for testing generalized Reed-Muller codes. CoRR abs/1204.5467 (2012) - [i64]Alan Guo, Madhu Sudan:
New affine-invariant codes from lifting. CoRR abs/1208.5413 (2012) - [i63]Joel Spencer, Madhu Sudan, Kuang Xu:
Queueing with Future Information. CoRR abs/1211.0618 (2012) - [i62]Elad Haramaty, Madhu Sudan:
Deterministic Compression with Uncertain Priors. CoRR abs/1211.5718 (2012) - [i61]Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan:
Sparse affine-invariant linear codes are locally testable. Electron. Colloquium Comput. Complex. TR12 (2012) - [i60]Alan Guo, Swastik Kopparty, Madhu Sudan:
New affine-invariant codes from lifting. Electron. Colloquium Comput. Complex. TR12 (2012) - [i59]Alan Guo, Madhu Sudan:
Some closure features of locally testable affine-invariant properties. Electron. Colloquium Comput. Complex. TR12 (2012) - [i58]Alan Guo, Madhu Sudan:
New affine-invariant codes from lifting. Electron. Colloquium Comput. Complex. TR12 (2012) - [i57]Elad Haramaty, Madhu Sudan:
Deterministic Compression with Uncertain Priors. Electron. Colloquium Comput. Complex. TR12 (2012) - [i56]Madhu Sudan, Noga Zewi:
A new upper bound on the query complexity for testing generalized Reed-Muller codes. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j50]Madhu Sudan:
Patterns hidden from simple algorithms: technical perspective. Commun. ACM 54(4): 107 (2011) - [j49]Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan:
Derandomization of auctions. Games Econ. Behav. 72(1): 1-11 (2011) - [j48]Madhu Sudan:
Guest column: testing linear properties: some general theme. SIGACT News 42(1): 59-80 (2011) - [j47]Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
Testing Linear-Invariant Non-Linear Properties. Theory Comput. 7(1): 75-99 (2011) - [c85]Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
On Sums of Locally Testable Affine Invariant Properties. APPROX-RANDOM 2011: 400-411 - [c84]Eli Ben-Sasson, Madhu Sudan:
Limits on the Rate of Locally Testable Affine-Invariant Codes. APPROX-RANDOM 2011: 412-423 - [c83]Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
Symmetric LDPC Codes are not Necessarily Locally Testable. CCC 2011: 55-65 - [c82]Elad Haramaty, Amir Shpilka, Madhu Sudan:
Optimal Testing of Multivariate Polynomials over Small Prime Fields. FOCS 2011: 629-637 - [c81]Sanjeev Khanna, Madhu Sudan:
Delays and the Capacity of Continuous-Time Channels. FOCS 2011: 758-767 - [c80]Madhu Sudan:
Physical limits of Communication (Invited Talk). FSTTCS 2011: 4-5 - [c79]Brendan Juba, Madhu Sudan:
Efficient Semantic Communication via Compatible Beliefs. ICS 2011: 22-31 - [c78]Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, Madhu Sudan:
Compression without a common prior: an information-theoretic justification for ambiguity in language. ICS 2011: 79-86 - [c77]Victor Chen, Madhu Sudan, Ning Xie:
Property Testing via Set-Theoretic Operations. ICS 2011: 211-222 - [c76]Oded Goldreich, Brendan Juba, Madhu Sudan:
A theory of goal-oriented communication. PODC 2011: 299-300 - [p5]Oded Goldreich, Madhu Sudan, Luca Trevisan:
From Logarithmic Advice to Single-Bit Advice. Studies in Complexity and Cryptography 2011: 109-113 - [i55]Sanjeev Khanna, Madhu Sudan:
Delays and the Capacity of Continuous-time Channels. CoRR abs/1105.3425 (2011) - [i54]Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
On Sums of Locally Testable Affine Invariant Properties. Electron. Colloquium Comput. Complex. TR11 (2011) - [i53]Elad Haramaty, Amir Shpilka, Madhu Sudan:
Optimal testing of multivariate polynomials over small prime fields. Electron. Colloquium Comput. Complex. TR11 (2011) - [i52]Madhu Sudan:
Testing Linear Properties: Some general themes. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j46]Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman:
Locally Testable Codes Require Redundant Testers. SIAM J. Comput. 39(7): 3230-3247 (2010) - [j45]Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson:
Optimal Error Correction for Computationally Bounded Noise. IEEE Trans. Inf. Theory 56(11): 5673-5680 (2010) - [c75]Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman:
Optimal Testing of Reed-Muller Codes. FOCS 2010: 488-497 - [c74]Adam Kalai, Michael Mitzenmacher, Madhu Sudan:
Tight asymptotic bounds for the deletion channel with small deletion probabilities. ISIT 2010: 997-1001 - [p4]Madhu Sudan:
Invariance in Property Testing. Property Testing 2010: 211-227 - [p3]Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
Testing Linear-Invariant Non-linear Properties: A Short Report. Property Testing 2010: 260-268 - [p2]Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman:
Optimal Testing of Reed-Muller Codes. Property Testing 2010: 269-275 - [i51]Victor Chen, Madhu Sudan, Ning Xie:
Property Testing via Set-Theoretic Operations. CoRR abs/1010.4925 (2010) - [i50]Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan:
Symmetric LDPC codes are not necessarily locally testable. Electron. Colloquium Comput. Complex. TR10 (2010) - [i49]Eli Ben-Sasson, Madhu Sudan:
Limits on the rate of locally testable affine-invariant codes. Electron. Colloquium Comput. Complex. TR10 (2010) - [i48]Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
Testing linear-invariant non-linear properties: A short report. Electron. Colloquium Comput. Complex. TR10 (2010) - [i47]Victor Chen, Madhu Sudan, Ning Xie:
Property Testing via Set-Theoretic Operations. Electron. Colloquium Comput. Complex. TR10 (2010) - [i46]Brendan Juba, Madhu Sudan:
Efficient Semantic Communication via Compatible Beliefs. Electron. Colloquium Comput. Complex. TR10 (2010) - [i45]Madhu Sudan:
Invariance in Property Testing. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j44]Madhu Sudan:
Probabilistically checkable proofs. Commun. ACM 52(3): 76-84 (2009) - [c73]Elena Grigorescu, Tali Kaufman, Madhu Sudan:
Succinct Representation of Codes with Applications to Testing. APPROX-RANDOM 2009: 534-547 - [c72]Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman:
Locally Testable Codes Require Redundant Testers. CCC 2009: 52-61 - [c71]Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan:
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. FOCS 2009: 181-190 - [c70]Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
Testing Linear-Invariant Non-Linear Properties. STACS 2009: 135-146 - [i44]Elena Grigorescu, Tali Kaufman, Madhu Sudan:
Succinct Representation of Codes with Applications to Testing. CoRR abs/0905.2919 (2009) - [i43]Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman:
Optimal Testing of Reed-Muller Codes. CoRR abs/0910.0641 (2009) - [i42]Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman:
Locally Testable Codes Require Redundant Testers. Electron. Colloquium Comput. Complex. TR09 (2009) - [i41]Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman:
Optimal testing of Reed-Muller codes. Electron. Colloquium Comput. Complex. TR09 (2009) - [i40]Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan:
Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers. Electron. Colloquium Comput. Complex. TR09 (2009) - [i39]Oded Goldreich, Brendan Juba, Madhu Sudan:
A Theory of Goal-Oriented Communication. Electron. Colloquium Comput. Complex. TR09 (2009) - [i38]Elena Grigorescu, Tali Kaufman, Madhu Sudan:
Succinct Representation of Codes with Applications to Testing. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j43]Eli Ben-Sasson, Madhu Sudan:
Short PCPs with Polylog Query Complexity. SIAM J. Comput. 38(2): 551-607 (2008) - [c69]Elena Grigorescu, Tali Kaufman, Madhu Sudan:
2-Transitivity Is Insufficient for Local Testability. CCC 2008: 259-267 - [c68]Madhu Sudan:
Algebraic algorithms and coding theory. ISSAC 2008: 337 - [c67]Brendan Juba, Madhu Sudan:
Universal semantic communication I. STOC 2008: 123-132 - [c66]Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan:
Decodability of group homomorphisms beyond the johnson bound. STOC 2008: 275-284 - [c65]Tali Kaufman, Madhu Sudan:
Algebraic property testing: the role of invariance. STOC 2008: 403-412 - [i37]Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
Testing Linear-Invariant Non-Linear Properties. Electron. Colloquium Comput. Complex. TR08 (2008) - [i36]Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan:
Decodability of Group Homomorphisms beyond the Johnson Bound. Electron. Colloquium Comput. Complex. TR08 (2008) - [i35]Elena Grigorescu, Tali Kaufman, Madhu Sudan:
2-Transitivity is Insufficient for Local Testability. Electron. Colloquium Comput. Complex. TR08 (2008) - [i34]Brendan Juba, Madhu Sudan:
Universal Semantic Communication II: A Theory of Goal-Oriented Communication. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j42]Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan:
Guessing secrets efficiently via list decoding. ACM Trans. Algorithms 3(4): 42 (2007) - [c64]Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee:
Amplifying Collision Resistance: A Complexity-Theoretic Treatment. CRYPTO 2007: 264-283 - [c63]Tali Kaufman, Madhu Sudan:
Sparse Random Linear Codes are Locally Decodable and Testable. FOCS 2007: 590-600 - [i33]Brendan Juba, Madhu Sudan:
Universal Semantic Communication I. Electron. Colloquium Comput. Complex. TR07 (2007) - [i32]Tali Kaufman, Madhu Sudan:
Sparse Random Linear Codes are Locally Decodable and Testable. Electron. Colloquium Comput. Complex. TR07 (2007) - [i31]Tali Kaufman, Madhu Sudan:
Algebraic Property Testing: The Role of Invariance. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j41]Ari Juels, Madhu Sudan:
A Fuzzy Vault Scheme. Des. Codes Cryptogr. 38(2): 237-257 (2006) - [j40]Oded Goldreich, Madhu Sudan:
Locally testable codes and PCPs of almost-linear length. J. ACM 53(4): 558-655 (2006) - [j39]Lars Engebretsen, Madhu Sudan:
Harmonic broadcasting is bandwidth-optimal assuming constant bit rate. Networks 47(3): 172-177 (2006) - [j38]Eli Ben-Sasson, Madhu Sudan:
Robust locally testable codes and products of codes. Random Struct. Algorithms 28(4): 387-402 (2006) - [j37]Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput. 36(4): 889-974 (2006) - [j36]Oded Goldreich, Madhu Sudan:
Special Issue on Randomness and Complexity. SIAM J. Comput. 36(4) (2006) - [c62]Irit Dinur, Madhu Sudan, Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes. APPROX-RANDOM 2006: 304-315 - [c61]Elena Grigorescu, Swastik Kopparty, Madhu Sudan:
Local Decoding and Testing for Homomorphisms. APPROX-RANDOM 2006: 375-385 - [c60]Madhu Sudan:
Modelling Errors and Recovery for Communication. LATIN 2006: 25-25 - [i30]Irit Dinur, Madhu Sudan, Avi Wigderson:
Robust Local Testability of Tensor Products of LDPC Codes. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c59]Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Short PCPs Verifiable in Polylogarithmic Time. CCC 2005: 120-134 - [c58]Eli Ben-Sasson, Madhu Sudan:
Simple PCPs with poly-log rate and query complexity. STOC 2005: 266-275 - [c57]Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan:
Derandomization of auctions. STOC 2005: 619-625 - [c56]Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson:
Optimal Error Correction Against Computationally Bounded Noise. TCC 2005: 1-16 - [c55]Shafi Goldwasser, Madhu Sudan, Vinod Vaikuntanathan:
Distributed Computing with Imperfect Randomness. DISC 2005: 288-302 - 2004
- [c54]Eli Ben-Sasson, Madhu Sudan:
Robust Locally Testable Codes and Products of Codes. APPROX-RANDOM 2004: 286-297 - [c53]Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Robust pcps of proximity, shorter pcps and applications to coding. STOC 2004: 1-10 - [p1]Madhu Sudan:
Probabilistically checkable proofs. Computational Complexity Theory 2004: 349-389 - [i29]Eli Ben-Sasson, Madhu Sudan:
Robust Locally Testable Codes and Products of Codes. CoRR cs.IT/0408066 (2004) - [i28]Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Robust PCPs of Proximity, Shorter PCPs and Applications to Coding. Electron. Colloquium Comput. Complex. TR04 (2004) - [i27]Eli Ben-Sasson, Madhu Sudan:
Robust Locally Testable Codes and Products of Codes. Electron. Colloquium Comput. Complex. TR04 (2004) - [i26]Eli Ben-Sasson, Madhu Sudan:
Simple PCPs with Poly-log Rate and Query Complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - [i25]Oded Goldreich, Madhu Sudan, Luca Trevisan:
From logarithmic advice to single-bit advice. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j35]Sanjeev Arora, Madhu Sudan:
Improved Low-Degree Testing and its Applications. Comb. 23(3): 365-426 (2003) - [j34]Ilya Dumer, Daniele Micciancio, Madhu Sudan:
Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inf. Theory 49(1): 22-37 (2003) - [c52]Eli Ben-Sasson, Oded Goldreich, Madhu Sudan:
Bounds on 2-Query Codeword Testing. RANDOM-APPROX 2003: 216-227 - [c51]Don Coppersmith, Madhu Sudan:
Reconstructing curves in three (and higher) dimensional space from noisy data. STOC 2003: 136-142 - [c50]Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson:
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. STOC 2003: 612-621 - [i24]Eli Ben-Sasson, Oded Goldreich, Madhu Sudan:
Bounds on 2-Query Codeword Testing. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j33]Madhu Sudan:
Foreword. J. Comput. Syst. Sci. 65(4): 611 (2002) - [j32]Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. 31(6): 1663-1686 (2002) - [j31]Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman:
Combinatorial bounds for list decoding. IEEE Trans. Inf. Theory 48(5): 1021-1034 (2002) - [c49]Venkatesan Guruswami, Madhu Sudan:
Decoding Concatenated Codes using Soft Information. CCC 2002: 148-157 - [c48]Oded Goldreich, Madhu Sudan:
Locally Testable Codes and PCPs of Almost-Linear Length. FOCS 2002: 13-22 - [c47]Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan:
Guessing secrets efficiently via list decoding. SODA 2002: 254-262 - [c46]Lars Engebretsen, Madhu Sudan:
Harmonic broadcasting is optimal. SODA 2002: 431-432 - [i23]Oded Goldreich, Madhu Sudan:
Locally Testable Codes and PCPs of Almost-Linear Length. Electron. Colloquium Comput. Complex. TR02 (2002) - [i22]Ari Juels, Madhu Sudan:
A Fuzzy Vault Scheme. IACR Cryptol. ePrint Arch. 2002: 93 (2002) - 2001
- [b2]Nadia Creignou, Sanjeev Khanna, Madhu Sudan:
Complexity classifications of Boolean constraint satisfaction problems. SIAM monographs on discrete mathematics and applications 7, SIAM 2001, ISBN 978-0-89871-479-1, pp. I-XII, 1-106 - [j30]Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson:
Adversarial queuing theory. J. ACM 48(1): 13-38 (2001) - [j29]Madhu Sudan, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci. 62(2): 236-266 (2001) - [j28]Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan:
Linear-Consistency Testing. J. Comput. Syst. Sci. 62(4): 589-607 (2001) - [j27]Venkatesan Guruswami, Madhu Sudan:
On representations of algebraic-geometry codes. IEEE Trans. Inf. Theory 47(4): 1610-1613 (2001) - [c45]Madhu Sudan:
Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms. AAECC 2001: 36-45 - [c44]Madhu Sudan:
Coding Theory: Tutorial and Survey. FOCS 2001: 36-53 - [c43]Prahladh Harsha, Madhu Sudan:
Small PCPs with Low Query Complexity. STACS 2001: 327-338 - 2000
- [j26]Prahladh Harsha, Madhu Sudan:
Small PCPs with low query complexity. Comput. Complex. 9(3-4): 157-201 (2000) - [j25]Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson:
Gadgets, Approximation, and Linear Programming. SIAM J. Comput. 29(6): 2074-2097 (2000) - [j24]Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson:
The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. 30(6): 1863-1920 (2000) - [j23]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries: The Highly Noisy Case. SIAM J. Discret. Math. 13(4): 535-570 (2000) - [j22]Madhu Sudan:
List decoding: algorithms and applications. SIGACT News 31(1): 16-27 (2000) - [j21]Oded Goldreich, Dana Ron, Madhu Sudan:
Chinese remaindering with errors. IEEE Trans. Inf. Theory 46(4): 1330-1338 (2000) - [c42]Venkatesan Guruswami, Madhu Sudan:
On Representations of Algebraic-Geometric Codes for List Decoding. ESA 2000: 244-255 - [c41]Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
Hardness of Approximate Hypergraph Coloring. FOCS 2000: 149-158 - [c40]Venkatesan Guruswami, Amit Sahai, Madhu Sudan:
"Soft-decision" Decoding of Chinese Remainder Codes. FOCS 2000: 159-168 - [c39]Madhu Sudan:
List Decoding: Algorithms and Applications. IFIP TCS 2000: 25-41 - [c38]Venkatesan Guruswami, Madhu Sudan:
List decoding algorithms for certain concatenated codes. STOC 2000: 181-190 - [c37]Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins:
Random walks with "back buttons" (extended abstract). STOC 2000: 484-493 - [i21]Prahladh Harsha, Madhu Sudan:
Small PCPs with low query complexity. Electron. Colloquium Comput. Complex. TR00 (2000) - [i20]Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
Hardness of approximate hypergraph coloring. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [j20]Oded Goldreich, Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy. J. Comput. Syst. Sci. 59(2): 253-269 (1999) - [j19]Venkatesan Guruswami, Madhu Sudan:
Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Trans. Inf. Theory 45(6): 1757-1767 (1999) - [c36]Madhu Sudan, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Generators without the XOR Lemma (Abstract). CCC 1999: 4 - [c35]Ilya Dumer, Daniele Micciancio, Madhu Sudan:
Hardness of Approximating the Minimum Distance of a Linear Code. FOCS 1999: 475-485 - [c34]Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan:
Linear Consistency Testing. RANDOM-APPROX 1999: 109-120 - [c33]Oded Goldreich, Dana Ron, Madhu Sudan:
Chinese Remaindering with Errors. STOC 1999: 225-234 - [c32]Madhu Sudan, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Generators Without the XOR Lemma (Extended Abstract). STOC 1999: 537-546 - [i19]Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan:
Linear Consistency Testing. Electron. Colloquium Comput. Complex. TR99 (1999) - [i18]Ilya Dumer, Daniele Micciancio, Madhu Sudan:
Hardness of Approximating the Minimum Distance of a Linear Code. Electron. Colloquium Comput. Complex. TR99 (1999) - [i17]Oded Goldreich, Dana Ron, Madhu Sudan:
Chinese Remaindering with Errors. IACR Cryptol. ePrint Arch. 1999: 2 (1999) - 1998
- [j18]Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan:
Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. Algorithmica 20(2): 151-174 (1998) - [j17]David R. Karger, Rajeev Motwani, Madhu Sudan:
Approximate Graph Coloring by Semidefinite Programming. J. ACM 45(2): 246-265 (1998) - [j16]Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy:
Proof Verification and the Hardness of Approximation Problems. J. ACM 45(3): 501-555 (1998) - [j15]Benny Chor, Eyal Kushilevitz, Oded Goldreich, Madhu Sudan:
Private Information Retrieval. J. ACM 45(6): 965-981 (1998) - [j14]Mihir Bellare, Oded Goldreich, Madhu Sudan:
Free Bits, PCPs, and Nonapproximability-Towards Tight Results. SIAM J. Comput. 27(3): 804-915 (1998) - [j13]Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan:
Guaranteeing Fair Service to Persistent Dependent Tasks. SIAM J. Comput. 27(4): 1168-1189 (1998) - [j12]Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability. SIAM J. Comput. 28(1): 164-191 (1998) - [j11]Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan:
Reconstructing Algebraic Functions from Mixed Data. SIAM J. Comput. 28(2): 487-510 (1998) - [j10]Benny Chor, Madhu Sudan:
A Geometric Approach to Betweenness. SIAM J. Discret. Math. 11(4): 511-523 (1998) - [c31]Oded Goldreich, Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy. CCC 1998: 24-33 - [c30]Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan:
A Tight Characterization of NP with 3 Query PCPs. FOCS 1998: 8-17 - [c29]Madhu Sudan, Luca Trevisan:
Probabilistically Checkable Proofs with Low Amortized Query Complexity. FOCS 1998: 18-27 - [c28]Venkatesan Guruswami, Madhu Sudan:
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. FOCS 1998: 28-39 - [i16]David R. Karger, Rajeev Motwani, Madhu Sudan:
Approximate Graph Coloring by Semidefinite Programming. CoRR cs.DS/9812008 (1998) - [i15]Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy:
Proof verification and the hardness of approximation problems. Electron. Colloquium Comput. Complex. TR98 (1998) - [i14]Oded Goldreich, Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy. Electron. Colloquium Comput. Complex. TR98 (1998) - [i13]Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan:
A tight characterization of NP with 3 query PCPs. Electron. Colloquium Comput. Complex. TR98 (1998) - [i12]Madhu Sudan, Luca Trevisan:
Probabilistically checkable proofs with low amortized query complexity. Electron. Colloquium Comput. Complex. TR98 (1998) - [i11]Venkatesan Guruswami, Madhu Sudan:
Improved decoding of Reed-Solomon and algebraic-geometric codes. Electron. Colloquium Comput. Complex. TR98 (1998) - [i10]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries - The Highly Noisy Case. Electron. Colloquium Comput. Complex. TR98 (1998) - [i9]Oded Goldreich, Dana Ron, Madhu Sudan:
Chinese Remaindering with Errors. Electron. Colloquium Comput. Complex. TR98 (1998) - [i8]Madhu Sudan, Luca Trevisan, Salil P. Vadhan:
Pseudorandom generators without the XOR Lemma. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j9]Jonathan R. M. Hosking, Edwin P. D. Pednault, Madhu Sudan:
A statistical perspective on data mining. Future Gener. Comput. Syst. 13(2-3): 117-134 (1997) - [j8]Madhu Sudan:
Decoding of Reed Solomon Codes beyond the Error-Correction Bound. J. Complex. 13(1): 180-193 (1997) - [c27]Sanjeev Khanna, Madhu Sudan, Luca Trevisan:
Constraint Satisfaction: The Approximability of Minimization Problems. CCC 1997: 282-296 - [c26]Madhu Sudan:
Algorithmic Issues in Coding Theory. FSTTCS 1997: 184-199 - [c25]Sanjeev Khanna, Madhu Sudan, David P. Williamson:
A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. STOC 1997: 11-20 - [c24]Sanjeev Arora, Madhu Sudan:
Improved Low-Degree Testing and its Applications. STOC 1997: 485-495 - [i7]Sanjeev Arora, Madhu Sudan:
Improved low-degree testing and its applications. Electron. Colloquium Comput. Complex. TR97 (1997) - 1996
- [j7]Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan:
Efficient Routing in Optical Networks. J. ACM 43(6): 973-1001 (1996) - [j6]Ronitt Rubinfeld, Madhu Sudan:
Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. 25(2): 252-271 (1996) - [j5]Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby, Madhu Sudan:
Priority encoding transmission. IEEE Trans. Inf. Theory 42(6): 1737-1744 (1996) - [j4]Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan:
Linearity testing in characteristic two. IEEE Trans. Inf. Theory 42(6): 1781-1795 (1996) - [c23]Madhu Sudan:
Maximum Likelihood Decoding of Reed Solomon Codes. FOCS 1996: 164-172 - [c22]Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson:
Gadgets, Approximation, and Linear Programming (extended abstract). FOCS 1996: 617-626 - [c21]Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson:
Adversarial Queueing Theory. STOC 1996: 376-385 - [i6]Sanjeev Khanna, Madhu Sudan:
The Optimization Complexity of Constraint Satisfaction Problems. Electron. Colloquium Comput. Complex. TR96 (1996) - [i5]Sanjeev Khanna, Madhu Sudan, David P. Williamson:
A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. Electron. Colloquium Comput. Complex. TR96 (1996) - [i4]Sanjeev Khanna, Madhu Sudan, Luca Trevisan:
Constraint satisfaction: The approximability of minimization problems. Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [b1]Madhu Sudan:
Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems. Lecture Notes in Computer Science 1001, Springer 1995, ISBN 3-540-60615-7 - [c20]Benny Chor, Madhu Sudan:
A Geometric Approach to Betweenness. ESA 1995: 227-237 - [c19]Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan:
Private Information Retrieval. FOCS 1995: 41-50 - [c18]Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan:
Learning Polynomials with Queries: The Highly Noisy Case. FOCS 1995: 294-303 - [c17]Mihir Bellare, Oded Goldreich, Madhu Sudan:
Free Bits, PCPs and Non-Approximability - Towards Tight Results. FOCS 1995: 422-431 - [c16]Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan:
Linearity Testing in Characteristic Two. FOCS 1995: 432-441 - [c15]Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan:
Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs. IPCO 1995: 14-28 - [c14]Katalin Friedl, Madhu Sudan:
Some Improvements to Total Degree Tests. ISTCS 1995: 190-198 - [c13]Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan:
Guaranteeing Fair Service to Persistent Dependent Tasks. SODA 1995: 243-252 - [i3]Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability. Electron. Colloquium Comput. Complex. TR95 (1995) - [i2]Mihir Bellare, Oded Goldreich, Madhu Sudan:
Free Bits, PCP and Non-Approximability - Towards Tight Results. Electron. Colloquium Comput. Complex. TR95 (1995) - 1994
- [j3]Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan:
On-Line Algorithms for Locating Checkpoints. Algorithmica 11(1): 33-52 (1994) - [j2]Rajeev Motwani, Madhu Sudan:
Computing Roots of Graphs Is Hard. Discret. Appl. Math. 54(1): 81-88 (1994) - [c12]David R. Karger, Rajeev Motwani, Madhu Sudan:
Approximate Graph Coloring by Semidefinite Programming. FOCS 1994: 2-13 - [c11]Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki:
Motion Planning on a Graph (Extended Abstract). FOCS 1994: 511-520 - [c10]Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby, Madhu Sudan:
Priority Encoding Transmission. FOCS 1994: 604-612 - [c9]Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability. FOCS 1994: 819-830 - [c8]Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan:
Efficient Routing and Scheduling Algorithms for Optical Networks. SODA 1994: 412-423 - [c7]Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan:
The minimum latency problem. STOC 1994: 163-171 - [c6]Mihir Bellare, Madhu Sudan:
Improved non-approximability results. STOC 1994: 184-193 - [i1]Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan:
On the minimum latency problem. CoRR abs/math/9409223 (1994) - 1992
- [j1]Peter Gemmell, Madhu Sudan:
Highly Resilient Correctors for Polynomials. Inf. Process. Lett. 43(4): 169-174 (1992) - [c5]Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy:
Proof Verification and Hardness of Approximation Problems. FOCS 1992: 14-23 - [c4]Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan:
Reconstructing Algebraic Functions from Mixed Data. FOCS 1992: 503-512 - [c3]Ronitt Rubinfeld, Madhu Sudan:
Self-Testing Polynomial Functions Efficiently and Over Rational Domains. SODA 1992: 23-32 - 1991
- [c2]Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson:
Self-Testing/Correcting for Polynomials and for Approximate Functions. STOC 1991: 32-42 - 1990
- [c1]Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan:
Online Algorithms for Locating Checkpoints. STOC 1990: 359-368
Coauthor Index
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-10-13 18:04 CEST 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:
