Madhu Sudan - RankMe

379 papers A* 87A 29B 8Journal 229Unranked 19

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Markov Chains with Rewinding. CoRR Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Madhu Sudan
2025	J	`jnl`	A Near-Optimal Polynomial Distance Lemma Over Boolean Slices. CoRR Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan
2025	J	`jnl`	A Near-Optimal Polynomial Distance Lemma Over Boolean Slices. Electron. Colloquium Comput. Complex. Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan
2025	A*	`conf`	A Near-Optimal Polynomial Distance Lemma over Boolean Slices. ICALP Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan
2025	A*	`conf`	A Theory of Spectral CSP Sparsification. ICALP Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2025	J	`jnl`	A Theory of Spectral CSP Sparsification. CoRR Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2025	J	`jnl`	Algebra in Algorithmic Coding Theory. Electron. Colloquium Comput. Complex. Madhu Sudan
2025	A*	`conf`	Efficient Algorithms and New Characterizations for CSP Sparsification. STOC Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2025	J	`jnl`	Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications. CoRR Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan
2025	J	`jnl`	Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications. Electron. Colloquium Comput. Complex. Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan
2025	A	`conf`	Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications. APPROX/RANDOM Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan
2025	J	`jnl`	Ideals, Gröbner Bases, and PCPs. CoRR Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
2025	J	`jnl`	Ideals, Gröbner Bases, and PCPs. Electron. Colloquium Comput. Complex. Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard
2025	A*	`conf`	Improved PIR Schemes using Matching Vectors and Derivatives. STOC Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan
2025	A*	`conf`	Low Degree Local Correction Over the Boolean Cube. SODA Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan
2025	A*	`conf`	Lower Bounds for Non-adaptive Local Computation Algorithms. FOCS Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Madhu Sudan
2025	J	`jnl`	Lower Bounds for Non-adaptive Local Computation Algorithms. CoRR Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, Madhu Sudan
2025	A*	`conf`	Near-Optimal Hypergraph Sparsification in Insertion-Only and Bounded-Deletion Streams. ICALP Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2025	J	`jnl`	Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams. CoRR Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2025	J	`jnl`	On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction. IEEE Trans. Inf. Theory Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu
2025	J	`jnl`	Quality control in sublinear time: a case study via random graphs. CoRR Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan
2025	A*	`conf`	Streaming Algorithms via Local Algorithms for Maximum Directed Cut. SODA Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
2025	A	`conf`	Testing Tensor Products of Algebraic Codes. APPROX/RANDOM Sumegha Garg, Madhu Sudan, Gabriel Wu
2024	A*	`conf`	Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. ICALP Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2024	J	`jnl`	Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. CoRR Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2024	A*	`conf`	An Improved Line-Point Low-Degree Test. FOCS Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan
2024	J	`jnl`	Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs. CoRR Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2024	A*	`conf`	Code Sparsification and its Applications. SODA Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2024	J	`jnl`	Decoding Multivariate Multiplicity Codes on Product Sets. IEEE Trans. Inf. Theory Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
2024	A*	`conf`	Errors are Robustly Tamed in Cumulative Knowledge Processes. COLT Anna M. Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan
2024	J	`jnl`	Finding the root in random nearest neighbor trees. CoRR Anna M. Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan
2024	J	`jnl`	Ideal-Theoretic Explanation of Capacity-Achieving Decoding. IEEE Trans. Inf. Theory Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
2024	J	`jnl`	Improved PIR Schemes using Matching Vectors and Derivatives. CoRR Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan
2024	J	`jnl`	Improved PIR Schemes using Matching Vectors and Derivatives. Electron. Colloquium Comput. Complex. Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan
2024	J	`jnl`	Improved PIR Schemes using Matching Vectors and Derivatives. IACR Cryptol. ePrint Arch. Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan
2024	A*	`conf`	Local Correction of Linear Functions over the Boolean Cube. STOC Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan
2024	J	`jnl`	Local Correction of Linear Functions over the Boolean Cube. CoRR Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan
2024	J	`jnl`	Local Correction of Linear Functions over the Boolean Cube. Electron. Colloquium Comput. Complex. Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan
2024	J	`jnl`	Low Degree Local Correction Over the Boolean Cube. CoRR Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan
2024	J	`jnl`	Low Degree Local Correction Over the Boolean Cube. Electron. Colloquium Comput. Complex. Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan
2024	A*	`conf`	Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. FOCS Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2024	J	`jnl`	Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. CoRR Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2024	B	`conf`	On $k$-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction. ISIT Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu
2024	J	`jnl`	Sketching Approximability of All Finite CSPs. J. ACM Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2024	J	`jnl`	Streaming Algorithms via Local Algorithms for Maximum Directed Cut. CoRR Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
2024	J	`jnl`	Streaming approximation resistance of every ordering CSP. Comput. Complex. Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
2024	J	`jnl`	Testing Tensor Products of Algebraic Codes. CoRR Sumegha Garg, Madhu Sudan, Gabriel Wu
2023	J	`jnl`	An Improved Line-Point Low-Degree Test. CoRR Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan
2023	J	`jnl`	An Improved Line-Point Low-Degree Test. Electron. Colloquium Comput. Complex. Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan
2023	J	`jnl`	Code Sparsification and its Applications. CoRR Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2023	J	`jnl`	Combinative Cumulative Knowledge Processes. CoRR Anna M. Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan
2023	A*	`conf`	Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots. FOCS Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan, Santhoshini Velusamy
2023	A	`conf`	Is This Correct? Let's Check! ITCS Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan
2023	J	`jnl`	Low-Degree Testing Over Grids. CoRR Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan
2023	A	`conf`	Low-Degree Testing over Grids. APPROX/RANDOM Prashanth Amireddy, Srikanth Srinivasan, Madhu Sudan
2023	J	`jnl`	On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction. CoRR Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu
2023	A*	`conf`	Streaming complexity of CSPs with randomly ordered constraints. SODA Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
2022	J	`jnl`	General Strong Polarization. J. ACM Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
2022	J	`jnl`	Is this correct? Let's check! CoRR Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan
2022	J	`jnl`	Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance. IEEE Trans. Inf. Theory Elena Grigorescu, Madhu Sudan, Minshen Zhu
2022	A*	`conf`	Linear space streaming lower bounds for approximating CSPs. STOC Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
2022	J	`jnl`	Point-hyperplane Incidence Geometry and the Log-rank Conjecture. ACM Trans. Comput. Theory Noah Singer, Madhu Sudan
2022	A	`conf`	Sketching Approximability of (Weak) Monarchy Predicates. APPROX/RANDOM Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
2022	J	`jnl`	Sketching Approximability of (Weak) Monarchy Predicates. CoRR Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
2022	J	`jnl`	Sketching Approximability of (Weak) Monarchy Predicates. Electron. Colloquium Comput. Complex. Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy
2022	A*	`conf`	Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk). ICALP Madhu Sudan
2022	J	`jnl`	Streaming and Sketching Complexity of CSPs: A survey. CoRR Madhu Sudan
2022	J	`jnl`	Streaming and Sketching Complexity of CSPs: A survey. Electron. Colloquium Comput. Complex. Madhu Sudan
2022	J	`jnl`	Streaming beyond sketching for Maximum Directed Cut. CoRR Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
2022	J	`jnl`	Streaming beyond sketching for Maximum Directed Cut. Electron. Colloquium Comput. Complex. Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
2022	J	`jnl`	Streaming complexity of CSPs with randomly ordered constraints. CoRR Raghuvansh R. Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
2022	J	`jnl`	Streaming complexity of CSPs with randomly ordered constraints. Electron. Colloquium Comput. Complex. Raghuvansh Saxena, Noah Singer, Madhu Sudan, Santhoshini Velusamy
2021	J	`jnl`	Approximability of all finite CSPs in the dynamic streaming setting. CoRR Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2021	J	`jnl`	Approximability of all finite CSPs in the dynamic streaming setting. Electron. Colloquium Comput. Complex. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2021	A*	`conf`	Approximability of all finite CSPs with linear sketches. FOCS Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2021	J	`jnl`	Classification of the streaming approximability of Boolean CSPs. CoRR Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2021	J	`jnl`	Classification of the streaming approximability of Boolean CSPs. Electron. Colloquium Comput. Complex. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
2021	A*	`conf`	Decoding multivariate multiplicity codes on product sets. STOC Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
2021	—	`conf`	Ideal-Theoretic Explanation of Capacity-Achieving Decoding. APPROX-RANDOM Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
2021	J	`jnl`	Ideal-theoretic Explanation of Capacity-achieving Decoding. CoRR Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
2021	J	`jnl`	Ideal-theoretic Explanation of Capacity-achieving Decoding. Electron. Colloquium Comput. Complex. Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
2021	J	`jnl`	Information Spread with Error Correction. CoRR Omri Ben-Eliezer, Elchanan Mossel, Madhu Sudan
2021	B	`conf`	Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance. ISIT Elena Grigorescu, Madhu Sudan, Minshen Zhu
2021	J	`jnl`	Linear Space Streaming Lower Bounds for Approximating CSPs. CoRR Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
2021	J	`jnl`	Linear Space Streaming Lower Bounds for Approximating CSPs. Electron. Colloquium Comput. Complex. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy
2021	J	`jnl`	Point-hyperplane incidence geometry and the log-rank conjecture. CoRR Noah Singer, Madhu Sudan
2021	—	`conf`	Streaming Approximation Resistance of Every Ordering CSP. APPROX-RANDOM Noah Singer, Madhu Sudan, Santhoshini Velusamy
2021	J	`jnl`	Streaming approximation resistance of every ordering CSP. CoRR Noah Singer, Madhu Sudan, Santhoshini Velusamy
2021	J	`jnl`	Streaming approximation resistance of every ordering CSP. Electron. Colloquium Comput. Complex. Noah Singer, Madhu Sudan, Santhoshini Velusamy
2020	J	`jnl`	Communication for Generating Correlation: A Unifying Survey. IEEE Trans. Inf. Theory Madhu Sudan, Himanshu Tyagi, Shun Watanabe
2020	J	`jnl`	Decoding Multivariate Multiplicity Codes on Product Sets. CoRR Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
2020	J	`jnl`	Decoding Multivariate Multiplicity Codes on Product Sets. Electron. Colloquium Comput. Complex. Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan
2020	J	`jnl`	Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance. CoRR Elena Grigorescu, Madhu Sudan, Minshen Zhu
2020	J	`jnl`	Local decoding and testing of polynomials over grids. Random Struct. Algorithms Mitali Bafna, Srikanth Srinivasan, Madhu Sudan
2020	J	`jnl`	Optimality of Correlated Sampling Strategies. Theory Comput. Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan
2020	A*	`conf`	Round Complexity of Common Randomness Generation: The Amortized Setting. SODA Noah Golowich, Madhu Sudan
2019	J	`jnl`	A Self-contained Analysis of the Lempel-Ziv Compression Algorithm. CoRR Madhu Sudan, David Xiang
2019	A	`conf`	Algorithmic Polarization for Hidden Markov Models. ITCS Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan
2019	J	`jnl`	Communication for Generating Correlation: A Survey. CoRR Madhu Sudan, Himanshu Tyagi, Shun Watanabe
2019	A*	`conf`	Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. SODA Madhu Sudan, Badih Ghazi, Noah Golowich, Mitali Bafna
2019	A*	`conf`	Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. FOCS Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan
2019	J	`jnl`	Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. CoRR Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, Madhu Sudan
2019	J	`jnl`	Round Complexity of Common Randomness Generation: The Amortized Setting. CoRR Noah Golowich, Madhu Sudan
2018	J	`jnl`	Algorithmic Polarization for Hidden Markov Models. CoRR Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan
2018	J	`jnl`	Communication with Contextual Uncertainty. Comput. Complex. Badih Ghazi, Ilan Komargodski, Pravesh K. Kothari, Madhu Sudan
2018	J	`jnl`	Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. CoRR Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan
2018	J	`jnl`	Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation. Electron. Colloquium Comput. Complex. Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan
2018	J	`jnl`	General Strong Polarization. CoRR Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
2018	J	`jnl`	General Strong Polarization. Electron. Colloquium Comput. Complex. Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
2018	A*	`conf`	General strong polarization. STOC Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
2018	A	`conf`	Local Decoding and Testing of Polynomials over Grids. ITCS Srikanth Srinivasan, Madhu Sudan
2018	—	`conf`	Polar Codes with Exponentially Small Error at Finite Block Length. APPROX-RANDOM Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan
2018	J	`jnl`	Polar Codes with exponentially small error at finite block length. CoRR Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan
2018	A*	`conf`	Synchronization Strings: List Decoding for Insertions and Deletions. ICALP Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan
2018	J	`jnl`	Synchronization Strings: List Decoding for Insertions and Deletions. CoRR Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan
2017	A*	`conf`	(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. SODA Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker
2017	J	`jnl`	Communication With Imperfectly Shared Randomness. IEEE Trans. Inf. Theory Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
2017	A	`conf`	Compression in a Distributed Setting. ITCS Badih Ghazi, Elad Haramaty, Pritish Kamath, Madhu Sudan
2017	J	`jnl`	Local decoding and testing of polynomials over grids. CoRR Srikanth Srinivasan, Madhu Sudan
2017	J	`jnl`	Local decoding and testing of polynomials over grids. Electron. Colloquium Comput. Complex. Srikanth Srinivasan, Madhu Sudan
2017	J	`jnl`	Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem. SIAM J. Comput. David Gamarnik, Madhu Sudan
2017	J	`jnl`	Sparse affine-invariant linear codes are locally testable. Comput. Complex. Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan
2017	A*	`conf`	The Power of Shared Randomness in Uncertain Communication. ICALP Badih Ghazi, Madhu Sudan
2017	J	`jnl`	The Power of Shared Randomness in Uncertain Communication. CoRR Badih Ghazi, Madhu Sudan
2017	J	`jnl`	The Power of Shared Randomness in Uncertain Communication. Electron. Colloquium Comput. Complex. Badih Ghazi, Madhu Sudan
2016	A*	`conf`	Communication Complexity of Permutation-Invariant Functions. SODA Badih Ghazi, Pritish Kamath, Madhu Sudan
2016	A*	`conf`	Communication with Contextual Uncertainty. SODA Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan
2016	J	`jnl`	Decidability of Non-Interactive Simulation of Joint Distributions. CoRR Badih Ghazi, Pritish Kamath, Madhu Sudan
2016	J	`jnl`	Decidability of Non-Interactive Simulation of Joint Distributions. Electron. Colloquium Comput. Complex. Badih Ghazi, Pritish Kamath, Madhu Sudan
2016	A*	`conf`	Decidability of Non-interactive Simulation of Joint Distributions. FOCS Badih Ghazi, Pritish Kamath, Madhu Sudan
2016	J	`jnl`	Deterministic Compression with Uncertain Priors. Algorithmica Elad Haramaty, Madhu Sudan
2016	A	`ed.`	Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016 ITCS Madhu Sudan
2016	J	`jnl`	The Optimality of Correlated Sampling. CoRR Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan
2016	J	`jnl`	The Optimality of Correlated Sampling. Electron. Colloquium Comput. Complex. Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan
2015	J	`jnl`	Absolutely Sound Testing of Lifted Codes. Theory Comput. Elad Haramaty, Noga Ron-Zewi, Madhu Sudan
2015	J	`jnl`	Communication Complexity of Permutation-Invariant Functions. CoRR Badih Ghazi, Pritish Kamath, Madhu Sudan
2015	J	`jnl`	Communication Complexity of Permutation-Invariant Functions. Electron. Colloquium Comput. Complex. Badih Ghazi, Pritish Kamath, Madhu Sudan
2015	J	`jnl`	Communication with Contextual Uncertainty. CoRR Ilan Komargodski, Pravesh Kothari, Madhu Sudan
2015	J	`jnl`	Communication with Contextual Uncertainty. Electron. Colloquium Comput. Complex. Ilan Komargodski, Pravesh Kothari, Madhu Sudan
2015	A	`conf`	Communication with Imperfectly Shared Randomness. ITCS Clément Louis Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
2015	A*	`conf`	Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. SODA Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang
2015	A*	`conf`	Robust Testing of Lifted Codes with Applications to Low-Degree Testing. FOCS Alan Guo, Elad Haramaty, Madhu Sudan
2015	J	`jnl`	Robust testing of lifted codes with applications to low-degree testing. Electron. Colloquium Comput. Complex. Alan Guo, Elad Haramaty, Madhu Sudan
2015	A*	`conf`	Streaming Lower Bounds for Approximating MAX-CUT. SODA Michael Kapralov, Sanjeev Khanna, Madhu Sudan
2014	A*	`conf`	Approximating matching size from random streams. SODA Michael Kapralov, Sanjeev Khanna, Madhu Sudan
2014	J	`jnl`	Communication with Imperfectly Shared Randomness. CoRR Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
2014	J	`jnl`	Communication with Imperfectly Shared Randomness. Electron. Colloquium Comput. Complex. Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
2014	A	`conf`	Deterministic compression with uncertain priors. ITCS Elad Haramaty, Madhu Sudan
2014	J	`jnl`	Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang
2014	A	`conf`	Limits of local algorithms over sparse random graphs. ITCS David Gamarnik, Madhu Sudan
2014	—	`conf`	List Decoding Group Homomorphisms Between Supersolvable Groups. APPROX-RANDOM Alan Guo, Madhu Sudan
2014	J	`jnl`	List decoding group homomorphisms between supersolvable groups. CoRR Alan Guo, Madhu Sudan
2014	A*	`conf`	Optimal error rates for interactive coding I: adaptivity and other settings. STOC Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan
2014	J	`jnl`	Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem. CoRR David Gamarnik, Madhu Sudan
2014	J	`jnl`	Streaming Lower Bounds for Approximating MAX-CUT. CoRR Michael Kapralov, Sanjeev Khanna, Madhu Sudan
2013	J	`jnl`	2-Transitivity is Insufficient for Local Testability. Comput. Complex. Elena Grigorescu, Tali Kaufman, Madhu Sudan
2013	J	`jnl`	A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes. Theory Comput. Noga Ron-Zewi, Madhu Sudan
2013	—	`conf`	Absolutely Sound Testing of Lifted Codes. APPROX-RANDOM Elad Haramaty, Noga Ron-Zewi, Madhu Sudan
2013	J	`jnl`	Absolutely Sound Testing of Lifted Codes. Electron. Colloquium Comput. Complex. Elad Haramaty, Noga Ron-Zewi, Madhu Sudan
2013	J	`jnl`	Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. SIAM J. Comput. Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan
2013	J	`jnl`	Limits of local algorithms over sparse random graphs CoRR David Gamarnik, Madhu Sudan
2013	J	`jnl`	Limits of local algorithms over sparse random graphs. Electron. Colloquium Comput. Complex. David Gamarnik, Madhu Sudan
2013	A	`conf`	New affine-invariant codes from lifting. ITCS Alan Guo, Swastik Kopparty, Madhu Sudan
2013	J	`jnl`	Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings. CoRR Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan
2013	J	`jnl`	Optimal Testing of Multivariate Polynomials over Small Prime Fields. SIAM J. Comput. Elad Haramaty, Amir Shpilka, Madhu Sudan
2013	J	`jnl`	Queueing with future information. SIGMETRICS Perform. Evaluation Rev. Joel Spencer, Madhu Sudan, Kuang Xu
2013	J	`jnl`	Some Improvements to Total Degree Tests. CoRR Katalin Friedl, Madhu Sudan
2012	—	`conf`	A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes. APPROX-RANDOM Noga Ron-Zewi, Madhu Sudan
2012	J	`jnl`	A new upper bound on the query complexity for testing generalized Reed-Muller codes CoRR Noga Ron-Zewi, Madhu Sudan
2012	J	`jnl`	A new upper bound on the query complexity for testing generalized Reed-Muller codes. Electron. Colloquium Comput. Complex. Madhu Sudan, Noga Zewi
2012	J	`jnl`	A theory of goal-oriented communication. J. ACM Oded Goldreich, Brendan Juba, Madhu Sudan
2012	B	`conf`	Communication amid uncertainty. ITW Madhu Sudan
2012	J	`jnl`	Deterministic Compression with Uncertain Priors CoRR Elad Haramaty, Madhu Sudan
2012	J	`jnl`	Deterministic Compression with Uncertain Priors. Electron. Colloquium Comput. Complex. Elad Haramaty, Madhu Sudan
2012	J	`jnl`	New affine-invariant codes from lifting CoRR Alan Guo, Madhu Sudan
2012	J	`jnl`	New affine-invariant codes from lifting. Electron. Colloquium Comput. Complex. Alan Guo, Swastik Kopparty, Madhu Sudan
2012	J	`jnl`	New affine-invariant codes from lifting. Electron. Colloquium Comput. Complex. Alan Guo, Madhu Sudan
2012	J	`jnl`	Queueing with Future Information CoRR Joel Spencer, Madhu Sudan, Kuang Xu
2012	J	`jnl`	Some closure features of locally testable affine-invariant properties. Electron. Colloquium Comput. Complex. Alan Guo, Madhu Sudan
2012	A*	`conf`	Sparse Affine-Invariant Linear Codes Are Locally Testable. FOCS Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan
2012	J	`jnl`	Sparse affine-invariant linear codes are locally testable. Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan
2012	J	`jnl`	Succinct Representation of Codes with Applications to Testing. SIAM J. Discret. Math. Elena Grigorescu, Tali Kaufman, Madhu Sudan
2011	A*	`conf`	A theory of goal-oriented communication. PODC Oded Goldreich, Brendan Juba, Madhu Sudan
2011	A	`conf`	Compression without a common prior: an information-theoretic justification for ambiguity in language. ICS Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, Madhu Sudan
2011	A*	`conf`	Delays and the Capacity of Continuous-Time Channels. FOCS Sanjeev Khanna, Madhu Sudan
2011	J	`jnl`	Delays and the Capacity of Continuous-time Channels CoRR Sanjeev Khanna, Madhu Sudan
2011	J	`jnl`	Derandomization of auctions. Games Econ. Behav. Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan
2011	A	`conf`	Efficient Semantic Communication via Compatible Beliefs. ICS Brendan Juba, Madhu Sudan
2011	—	`ch.`	From Logarithmic Advice to Single-Bit Advice. Studies in Complexity and Cryptography Oded Goldreich, Madhu Sudan, Luca Trevisan
2011	J	`jnl`	Guest column: testing linear properties: some general theme. SIGACT News Madhu Sudan
2011	—	`conf`	Limits on the Rate of Locally Testable Affine-Invariant Codes. APPROX-RANDOM Eli Ben-Sasson, Madhu Sudan
2011	—	`conf`	On Sums of Locally Testable Affine Invariant Properties. APPROX-RANDOM Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan
2011	J	`jnl`	On Sums of Locally Testable Affine Invariant Properties. Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan
2011	A*	`conf`	Optimal Testing of Multivariate Polynomials over Small Prime Fields. FOCS Elad Haramaty, Amir Shpilka, Madhu Sudan
2011	J	`jnl`	Optimal testing of multivariate polynomials over small prime fields. Electron. Colloquium Comput. Complex. Elad Haramaty, Amir Shpilka, Madhu Sudan
2011	J	`jnl`	Patterns hidden from simple algorithms: technical perspective. Commun. ACM Madhu Sudan
2011	—	`conf`	Physical limits of Communication (Invited Talk). FSTTCS Madhu Sudan
2011	A	`conf`	Property Testing via Set-Theoretic Operations. ICS Victor Chen, Madhu Sudan, Ning Xie
2011	A	`conf`	Symmetric LDPC Codes are not Necessarily Locally Testable. CCC Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan
2011	J	`jnl`	Testing Linear Properties: Some general themes. Electron. Colloquium Comput. Complex. Madhu Sudan
2011	J	`jnl`	Testing Linear-Invariant Non-Linear Properties. Theory Comput. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie
2010	J	`jnl`	Efficient Semantic Communication via Compatible Beliefs. Electron. Colloquium Comput. Complex. Brendan Juba, Madhu Sudan
2010	—	`ch.`	Invariance in Property Testing. Property Testing Madhu Sudan
2010	J	`jnl`	Invariance in Property Testing. Electron. Colloquium Comput. Complex. Madhu Sudan
2010	J	`jnl`	Limits on the rate of locally testable affine-invariant codes. Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Madhu Sudan
2010	J	`jnl`	Locally Testable Codes Require Redundant Testers. SIAM J. Comput. Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman
2010	J	`jnl`	Optimal Error Correction for Computationally Bounded Noise. IEEE Trans. Inf. Theory Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson
2010	A*	`conf`	Optimal Testing of Reed-Muller Codes. FOCS Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman
2010	—	`ch.`	Optimal Testing of Reed-Muller Codes. Property Testing Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman
2010	J	`jnl`	Property Testing via Set-Theoretic Operations CoRR Victor Chen, Madhu Sudan, Ning Xie
2010	J	`jnl`	Property Testing via Set-Theoretic Operations. Electron. Colloquium Comput. Complex. Victor Chen, Madhu Sudan, Ning Xie
2010	J	`jnl`	Symmetric LDPC codes are not necessarily locally testable. Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan
2010	—	`ch.`	Testing Linear-Invariant Non-linear Properties: A Short Report. Property Testing Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie
2010	J	`jnl`	Testing linear-invariant non-linear properties: A short report. Electron. Colloquium Comput. Complex. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie
2010	B	`conf`	Tight asymptotic bounds for the deletion channel with small deletion probabilities. ISIT Adam Kalai, Michael Mitzenmacher, Madhu Sudan
2009	J	`jnl`	A Theory of Goal-Oriented Communication. Electron. Colloquium Comput. Complex. Oded Goldreich, Brendan Juba, Madhu Sudan
2009	A*	`conf`	Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. FOCS Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan
2009	J	`jnl`	Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers. Electron. Colloquium Comput. Complex. Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan
2009	A	`conf`	Locally Testable Codes Require Redundant Testers. CCC Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman
2009	J	`jnl`	Locally Testable Codes Require Redundant Testers. Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman
2009	J	`jnl`	Optimal Testing of Reed-Muller Codes CoRR Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman
2009	J	`jnl`	Optimal testing of Reed-Muller codes. Electron. Colloquium Comput. Complex. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman
2009	J	`jnl`	Probabilistically checkable proofs. Commun. ACM Madhu Sudan
2009	J	`jnl`	Succinct Representation of Codes with Applications to Testing CoRR Elena Grigorescu, Tali Kaufman, Madhu Sudan
2009	—	`conf`	Succinct Representation of Codes with Applications to Testing. APPROX-RANDOM Elena Grigorescu, Tali Kaufman, Madhu Sudan
2009	J	`jnl`	Succinct Representation of Codes with Applications to Testing. Electron. Colloquium Comput. Complex. Elena Grigorescu, Tali Kaufman, Madhu Sudan
2009	A	`conf`	Testing Linear-Invariant Non-Linear Properties. STACS Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie
2008	A	`conf`	2-Transitivity Is Insufficient for Local Testability. CCC Elena Grigorescu, Tali Kaufman, Madhu Sudan
2008	J	`jnl`	2-Transitivity is Insufficient for Local Testability. Electron. Colloquium Comput. Complex. Elena Grigorescu, Tali Kaufman, Madhu Sudan
2008	B	`conf`	Algebraic algorithms and coding theory. ISSAC Madhu Sudan
2008	A*	`conf`	Algebraic property testing: the role of invariance. STOC Tali Kaufman, Madhu Sudan
2008	J	`jnl`	Decodability of Group Homomorphisms beyond the Johnson Bound. Electron. Colloquium Comput. Complex. Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan
2008	A*	`conf`	Decodability of group homomorphisms beyond the johnson bound. STOC Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan
2008	J	`jnl`	Short PCPs with Polylog Query Complexity. SIAM J. Comput. Eli Ben-Sasson, Madhu Sudan
2008	J	`jnl`	Testing Linear-Invariant Non-Linear Properties. Electron. Colloquium Comput. Complex. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie
2008	J	`jnl`	Universal Semantic Communication II: A Theory of Goal-Oriented Communication. Electron. Colloquium Comput. Complex. Brendan Juba, Madhu Sudan
2008	A*	`conf`	Universal semantic communication I. STOC Brendan Juba, Madhu Sudan
2007	J	`jnl`	Algebraic Property Testing: The Role of Invariance. Electron. Colloquium Comput. Complex. Tali Kaufman, Madhu Sudan
2007	A*	`conf`	Amplifying Collision Resistance: A Complexity-Theoretic Treatment. CRYPTO Ran Canetti, Ronald L. Rivest, Madhu Sudan, Luca Trevisan, Salil P. Vadhan, Hoeteck Wee
2007	J	`jnl`	Guessing secrets efficiently via list decoding. ACM Trans. Algorithms Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan
2007	A*	`conf`	Sparse Random Linear Codes are Locally Decodable and Testable. FOCS Tali Kaufman, Madhu Sudan
2007	J	`jnl`	Sparse Random Linear Codes are Locally Decodable and Testable. Electron. Colloquium Comput. Complex. Tali Kaufman, Madhu Sudan
2007	J	`jnl`	Universal Semantic Communication I. Electron. Colloquium Comput. Complex. Brendan Juba, Madhu Sudan
2006	J	`jnl`	A Fuzzy Vault Scheme. Des. Codes Cryptogr. Ari Juels, Madhu Sudan
2006	J	`jnl`	Harmonic broadcasting is bandwidth-optimal assuming constant bit rate. Networks Lars Engebretsen, Madhu Sudan
2006	—	`conf`	Local Decoding and Testing for Homomorphisms. APPROX-RANDOM Elena Grigorescu, Swastik Kopparty, Madhu Sudan
2006	J	`jnl`	Locally testable codes and PCPs of almost-linear length. J. ACM Oded Goldreich, Madhu Sudan
2006	B	`conf`	Modelling Errors and Recovery for Communication. LATIN Madhu Sudan
2006	—	`conf`	Robust Local Testability of Tensor Products of LDPC Codes. APPROX-RANDOM Irit Dinur, Madhu Sudan, Avi Wigderson
2006	J	`jnl`	Robust Local Testability of Tensor Products of LDPC Codes. Electron. Colloquium Comput. Complex. Irit Dinur, Madhu Sudan, Avi Wigderson
2006	J	`jnl`	Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM J. Comput. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan
2006	J	`jnl`	Robust locally testable codes and products of codes. Random Struct. Algorithms Eli Ben-Sasson, Madhu Sudan
2006	J	`jnl`	Special Issue on Randomness and Complexity. SIAM J. Comput. Oded Goldreich, Madhu Sudan
2005	A*	`conf`	Derandomization of auctions. STOC Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan
2005	A	`conf`	Distributed Computing with Imperfect Randomness. DISC Shafi Goldwasser, Madhu Sudan, Vinod Vaikuntanathan
2005	B	`conf`	Optimal Error Correction Against Computationally Bounded Noise. TCC Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson
2005	A	`conf`	Short PCPs Verifiable in Polylogarithmic Time. CCC Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan
2005	A*	`conf`	Simple PCPs with poly-log rate and query complexity. STOC Eli Ben-Sasson, Madhu Sudan
2004	J	`jnl`	From logarithmic advice to single-bit advice Electron. Colloquium Comput. Complex. Oded Goldreich, Madhu Sudan, Luca Trevisan
2004	—	`ch.`	Probabilistically checkable proofs. Computational Complexity Theory Madhu Sudan
2004	J	`jnl`	Robust Locally Testable Codes and Products of Codes CoRR Eli Ben-Sasson, Madhu Sudan
2004	J	`jnl`	Robust Locally Testable Codes and Products of Codes Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Madhu Sudan
2004	—	`conf`	Robust Locally Testable Codes and Products of Codes. APPROX-RANDOM Eli Ben-Sasson, Madhu Sudan
2004	J	`jnl`	Robust PCPs of Proximity, Shorter PCPs and Applications to Coding Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan
2004	A*	`conf`	Robust pcps of proximity, shorter pcps and applications to coding. STOC Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan
2004	J	`jnl`	Simple PCPs with Poly-log Rate and Query Complexity Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Madhu Sudan
2003	—	`conf`	Bounds on 2-Query Codeword Testing. RANDOM-APPROX Eli Ben-Sasson, Oded Goldreich, Madhu Sudan
2003	J	`jnl`	Bounds on 2-Query Codeword Testing. Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Oded Goldreich, Madhu Sudan
2003	J	`jnl`	Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inf. Theory Ilya Dumer, Daniele Micciancio, Madhu Sudan
2003	J	`jnl`	Improved Low-Degree Testing and its Applications. Comb. Sanjeev Arora, Madhu Sudan
2003	A*	`conf`	Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. STOC Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson
2003	A*	`conf`	Reconstructing curves in three (and higher) dimensional space from noisy data. STOC Don Coppersmith, Madhu Sudan
2002	J	`jnl`	A Fuzzy Vault Scheme. IACR Cryptol. ePrint Arch. Ari Juels, Madhu Sudan
2002	J	`jnl`	Combinatorial bounds for list decoding. IEEE Trans. Inf. Theory Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman
2002	A	`conf`	Decoding Concatenated Codes using Soft Information. CCC Venkatesan Guruswami, Madhu Sudan
2002	J	`jnl`	Foreword. J. Comput. Syst. Sci. Madhu Sudan
2002	A*	`conf`	Guessing secrets efficiently via list decoding. SODA Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan
2002	J	`jnl`	Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. Venkatesan Guruswami, Johan Håstad, Madhu Sudan
2002	A*	`conf`	Harmonic broadcasting is optimal. SODA Lars Engebretsen, Madhu Sudan
2002	J	`jnl`	Locally Testable Codes and PCPs of Almost-Linear Length Electron. Colloquium Comput. Complex. Oded Goldreich, Madhu Sudan
2002	A*	`conf`	Locally Testable Codes and PCPs of Almost-Linear Length. FOCS Oded Goldreich, Madhu Sudan
2001	J	`jnl`	Adversarial queuing theory. J. ACM Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
2001	A*	`conf`	Coding Theory: Tutorial and Survey. FOCS Madhu Sudan
2001	—	`book`	Complexity classifications of Boolean constraint satisfaction problems. Nadia Creignou, Sanjeev Khanna, Madhu Sudan
2001	—	`conf`	Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms. AAECC Madhu Sudan
2001	J	`jnl`	Linear-Consistency Testing. J. Comput. Syst. Sci. Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan
2001	J	`jnl`	On representations of algebraic-geometry codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Madhu Sudan
2001	J	`jnl`	Pseudorandom Generators without the XOR Lemma. J. Comput. Syst. Sci. Madhu Sudan, Luca Trevisan, Salil P. Vadhan
2001	A	`conf`	Small PCPs with Low Query Complexity. STACS Prahladh Harsha, Madhu Sudan
2000	A*	`conf`	"Soft-decision" Decoding of Chinese Remainder Codes. FOCS Venkatesan Guruswami, Amit Sahai, Madhu Sudan
2000	J	`jnl`	Chinese remaindering with errors. IEEE Trans. Inf. Theory Oded Goldreich, Dana Ron, Madhu Sudan
2000	J	`jnl`	Gadgets, Approximation, and Linear Programming. SIAM J. Comput. Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
2000	A*	`conf`	Hardness of Approximate Hypergraph Coloring. FOCS Venkatesan Guruswami, Johan Håstad, Madhu Sudan
2000	J	`jnl`	Hardness of approximate hypergraph coloring Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Johan Håstad, Madhu Sudan
2000	J	`jnl`	Learning Polynomials with Queries: The Highly Noisy Case. SIAM J. Discret. Math. Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
2000	—	`conf`	List Decoding: Algorithms and Applications. IFIP TCS Madhu Sudan
2000	A*	`conf`	List decoding algorithms for certain concatenated codes. STOC Venkatesan Guruswami, Madhu Sudan
2000	J	`jnl`	List decoding: algorithms and applications. SIGACT News Madhu Sudan
2000	A	`conf`	On Representations of Algebraic-Geometric Codes for List Decoding. ESA Venkatesan Guruswami, Madhu Sudan
2000	A*	`conf`	Random walks with "back buttons" (extended abstract). STOC Ronald Fagin, Anna R. Karlin, Jon M. Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, Andrew Tomkins
2000	J	`jnl`	Small PCPs with low query complexity Electron. Colloquium Comput. Complex. Prahladh Harsha, Madhu Sudan
2000	J	`jnl`	Small PCPs with low query complexity. Comput. Complex. Prahladh Harsha, Madhu Sudan
2000	J	`jnl`	The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson
1999	A*	`conf`	Chinese Remaindering with Errors. STOC Oded Goldreich, Dana Ron, Madhu Sudan
1999	J	`jnl`	Chinese Remaindering with Errors. IACR Cryptol. ePrint Arch. Oded Goldreich, Dana Ron, Madhu Sudan
1999	J	`jnl`	Computational Indistinguishability: A Sample Hierarchy. J. Comput. Syst. Sci. Oded Goldreich, Madhu Sudan
1999	J	`jnl`	Hardness of Approximating the Minimum Distance of a Linear Code Electron. Colloquium Comput. Complex. Ilya Dumer, Daniele Micciancio, Madhu Sudan
1999	A*	`conf`	Hardness of Approximating the Minimum Distance of a Linear Code. FOCS Ilya Dumer, Daniele Micciancio, Madhu Sudan
1999	J	`jnl`	Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Madhu Sudan
1999	J	`jnl`	Linear Consistency Testing Electron. Colloquium Comput. Complex. Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan
1999	—	`conf`	Linear Consistency Testing. RANDOM-APPROX Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan
1999	A*	`conf`	Pseudorandom Generators Without the XOR Lemma (Extended Abstract). STOC Madhu Sudan, Luca Trevisan, Salil P. Vadhan
1999	A	`conf`	Pseudorandom Generators without the XOR Lemma (Abstract). CCC Madhu Sudan, Luca Trevisan, Salil P. Vadhan
1998	J	`jnl`	A Geometric Approach to Betweenness. SIAM J. Discret. Math. Benny Chor, Madhu Sudan
1998	A*	`conf`	A Tight Characterization of NP with 3 Query PCPs. FOCS Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan
1998	J	`jnl`	A tight characterization of NP with 3 query PCPs Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan
1998	J	`jnl`	Approximate Graph Coloring by Semidefinite Programming CoRR David R. Karger, Rajeev Motwani, Madhu Sudan
1998	J	`jnl`	Approximate Graph Coloring by Semidefinite Programming. J. ACM David R. Karger, Rajeev Motwani, Madhu Sudan
1998	J	`jnl`	Approximating Minimum Feedback Sets and Multicuts in Directed Graphs. Algorithmica Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan
1998	J	`jnl`	Chinese Remaindering with Errors Electron. Colloquium Comput. Complex. Oded Goldreich, Dana Ron, Madhu Sudan
1998	J	`jnl`	Computational Indistinguishability: A Sample Hierarchy Electron. Colloquium Comput. Complex. Oded Goldreich, Madhu Sudan
1998	A	`conf`	Computational Indistinguishability: A Sample Hierarchy. CCC Oded Goldreich, Madhu Sudan
1998	J	`jnl`	Free Bits, PCPs, and Nonapproximability-Towards Tight Results. SIAM J. Comput. Mihir Bellare, Oded Goldreich, Madhu Sudan
1998	J	`jnl`	Guaranteeing Fair Service to Persistent Dependent Tasks. SIAM J. Comput. Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan
1998	A*	`conf`	Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. FOCS Venkatesan Guruswami, Madhu Sudan
1998	J	`jnl`	Improved decoding of Reed-Solomon and algebraic-geometric codes. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Madhu Sudan
1998	J	`jnl`	Learning Polynomials with Queries - The Highly Noisy Case. Electron. Colloquium Comput. Complex. Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
1998	J	`jnl`	On Syntactic versus Computational Views of Approximability. SIAM J. Comput. Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani
1998	J	`jnl`	Private Information Retrieval. J. ACM Benny Chor, Eyal Kushilevitz, Oded Goldreich, Madhu Sudan
1998	A*	`conf`	Probabilistically Checkable Proofs with Low Amortized Query Complexity. FOCS Madhu Sudan, Luca Trevisan
1998	J	`jnl`	Probabilistically checkable proofs with low amortized query complexity Electron. Colloquium Comput. Complex. Madhu Sudan, Luca Trevisan
1998	J	`jnl`	Proof Verification and the Hardness of Approximation Problems. J. ACM Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
1998	J	`jnl`	Proof verification and the hardness of approximation problems. Electron. Colloquium Comput. Complex. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
1998	J	`jnl`	Pseudorandom generators without the XOR Lemma Electron. Colloquium Comput. Complex. Madhu Sudan, Luca Trevisan, Salil P. Vadhan
1998	J	`jnl`	Reconstructing Algebraic Functions from Mixed Data. SIAM J. Comput. Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan
1997	A*	`conf`	A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. STOC Sanjeev Khanna, Madhu Sudan, David P. Williamson
1997	J	`jnl`	A statistical perspective on data mining. Future Gener. Comput. Syst. Jonathan R. M. Hosking, Edwin P. D. Pednault, Madhu Sudan
1997	—	`conf`	Algorithmic Issues in Coding Theory. FSTTCS Madhu Sudan
1997	A	`conf`	Constraint Satisfaction: The Approximability of Minimization Problems. CCC Sanjeev Khanna, Madhu Sudan, Luca Trevisan
1997	J	`jnl`	Decoding of Reed Solomon Codes beyond the Error-Correction Bound. J. Complex. Madhu Sudan
1997	A*	`conf`	Improved Low-Degree Testing and its Applications. STOC Sanjeev Arora, Madhu Sudan
1997	J	`jnl`	Improved low-degree testing and its applications Electron. Colloquium Comput. Complex. Sanjeev Arora, Madhu Sudan
1996	J	`jnl`	A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction Electron. Colloquium Comput. Complex. Sanjeev Khanna, Madhu Sudan, David P. Williamson
1996	A*	`conf`	Adversarial Queueing Theory. STOC Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David P. Williamson
1996	J	`jnl`	Constraint satisfaction: The approximability of minimization problems. Electron. Colloquium Comput. Complex. Sanjeev Khanna, Madhu Sudan, Luca Trevisan
1996	J	`jnl`	Efficient Routing in Optical Networks. J. ACM Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
1996	A*	`conf`	Gadgets, Approximation, and Linear Programming (extended abstract). FOCS Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
1996	J	`jnl`	Linearity testing in characteristic two. IEEE Trans. Inf. Theory Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan
1996	A*	`conf`	Maximum Likelihood Decoding of Reed Solomon Codes. FOCS Madhu Sudan
1996	J	`jnl`	Priority encoding transmission. IEEE Trans. Inf. Theory Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby, Madhu Sudan
1996	J	`jnl`	Robust Characterizations of Polynomials with Applications to Program Testing. SIAM J. Comput. Ronitt Rubinfeld, Madhu Sudan
1996	J	`jnl`	The Optimization Complexity of Constraint Satisfaction Problems Electron. Colloquium Comput. Complex. Sanjeev Khanna, Madhu Sudan
1995	A	`conf`	A Geometric Approach to Betweenness. ESA Benny Chor, Madhu Sudan
1995	B	`conf`	Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs. IPCO Guy Even, Joseph Naor, Baruch Schieber, Madhu Sudan
1995	—	`book`	Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems Madhu Sudan
1995	J	`jnl`	Free Bits, PCP and Non-Approximability - Towards Tight Results Electron. Colloquium Comput. Complex. Mihir Bellare, Oded Goldreich, Madhu Sudan
1995	A*	`conf`	Free Bits, PCPs and Non-Approximability - Towards Tight Results. FOCS Mihir Bellare, Oded Goldreich, Madhu Sudan
1995	A*	`conf`	Guaranteeing Fair Service to Persistent Dependent Tasks. SODA Amotz Bar-Noy, Alain J. Mayer, Baruch Schieber, Madhu Sudan
1995	A*	`conf`	Learning Polynomials with Queries: The Highly Noisy Case. FOCS Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan
1995	A*	`conf`	Linearity Testing in Characteristic Two. FOCS Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, Madhu Sudan
1995	J	`jnl`	On Syntactic versus Computational Views of Approximability Electron. Colloquium Comput. Complex. Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani
1995	A*	`conf`	Private Information Retrieval. FOCS Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan
1995	—	`conf`	Some Improvements to Total Degree Tests. ISTCS Katalin Friedl, Madhu Sudan
1994	A*	`conf`	Approximate Graph Coloring by Semidefinite Programming FOCS David R. Karger, Rajeev Motwani, Madhu Sudan
1994	J	`jnl`	Computing Roots of Graphs Is Hard. Discret. Appl. Math. Rajeev Motwani, Madhu Sudan
1994	A*	`conf`	Efficient Routing and Scheduling Algorithms for Optical Networks. SODA Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan
1994	A*	`conf`	Improved non-approximability results. STOC Mihir Bellare, Madhu Sudan
1994	A*	`conf`	Motion Planning on a Graph (Extended Abstract) FOCS Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki
1994	A*	`conf`	On Syntactic versus Computational Views of Approximability FOCS Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani
1994	J	`jnl`	On the minimum latency problem. CoRR Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan
1994	J	`jnl`	On-Line Algorithms for Locating Checkpoints. Algorithmica Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan
1994	A*	`conf`	Priority Encoding Transmission FOCS Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby, Madhu Sudan
1994	A*	`conf`	The minimum latency problem. STOC Avrim Blum, Prasad Chalasani, Don Coppersmith, William R. Pulleyblank, Prabhakar Raghavan, Madhu Sudan
1992	J	`jnl`	Highly Resilient Correctors for Polynomials. Inf. Process. Lett. Peter Gemmell, Madhu Sudan
1992	A*	`conf`	Proof Verification and Hardness of Approximation Problems FOCS Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
1992	A*	`conf`	Reconstructing Algebraic Functions from Mixed Data FOCS Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan
1992	A*	`conf`	Self-Testing Polynomial Functions Efficiently and Over Rational Domains. SODA Ronitt Rubinfeld, Madhu Sudan
1991	A*	`conf`	Self-Testing/Correcting for Polynomials and for Approximate Functions STOC Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, Avi Wigderson
1990	A*	`conf`	Online Algorithms for Locating Checkpoints STOC Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan