Madhu Sudan

CoRR, August, 2025

Lower Bounds for Non-adaptive Local Computation Algorithms.

[BibT_eX]

[DOI]

CoRR, May, 2025

Efficient Algorithms and New Characterizations for CSP Sparsification.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Improved PIR Schemes using Matching Vectors and Derivatives.

[BibT_eX]

[DOI]

Fatemeh Ghasemi

Swastik Kopparty

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Streaming Algorithms via Local Algorithms for Maximum Directed Cut.

[BibT_eX]

[DOI]

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Low Degree Local Correction Over the Boolean Cube.

[BibT_eX]

[DOI]

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Near-Optimal Hypergraph Sparsification in Insertion-Only and Bounded-Deletion Streams.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

A Theory of Spectral CSP Sparsification.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

A Near-Optimal Polynomial Distance Lemma over Boolean Slices.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Testing Tensor Products of Algebraic Codes.

[BibT_eX]

[DOI]

Sumegha Garg

Gabriel Wu

Proceedings of the Approximation, 2025

Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2025

2024

Sketching Approximability of All Finite CSPs.

[BibT_eX]

[DOI]

J. ACM, April, 2024

Finding the root in random nearest neighbor trees.

[BibT_eX]

[DOI]

Anna M. Brandenberger

CoRR, 2024

Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs.

[BibT_eX]

[DOI]

Aaron (Louie) Putterman

CoRR, 2024

Local Correction of Linear Functions over the Boolean Cube.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Code Sparsification and its Applications.

[BibT_eX]

[DOI]

Aaron (Louie) Putterman

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

On $k$-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2024

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs.

[BibT_eX]

[DOI]

Aaron (Louie) Putterman

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

An Improved Line-Point Low-Degree Test.

[BibT_eX]

[DOI]

Prahladh Harsha

Mrinal Kumar

Ramprasad Saptharishi

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Errors are Robustly Tamed in Cumulative Knowledge Processes.

[BibT_eX]

[DOI]

Anna M. Brandenberger

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Combinative Cumulative Knowledge Processes.

[BibT_eX]

[DOI]

Anna M. Brandenberger

CoRR, 2023

Streaming complexity of CSPs with randomly ordered constraints.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Is This Correct? Let's Check!

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Low-Degree Testing over Grids.

[BibT_eX]

[DOI]

Prashanth Amireddy

Srikanth Srinivasan

Proceedings of the Approximation, 2023

2022

Point-hyperplane Incidence Geometry and the Log-rank Conjecture.

[BibT_eX]

[DOI]

Noah Singer

ACM Trans. Comput. Theory, 2022

Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance.

[BibT_eX]

[DOI]

Minshen Zhu

IEEE Trans. Inf. Theory, 2022

Streaming beyond sketching for Maximum Directed Cut.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Streaming and Sketching Complexity of CSPs: A survey.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Linear space streaming lower bounds for approximating CSPs.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Streaming and Sketching Complexity of CSPs: A Survey (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Sketching Approximability of (Weak) Monarchy Predicates.

[BibT_eX]

[DOI]

Chi-Ning Chou

Alexander Golovnev

Amirbehshad Shahrasbi

Santhoshini Velusamy

Proceedings of the Approximation, 2022

2021

Approximability of all finite CSPs in the dynamic streaming setting.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Classification of the streaming approximability of Boolean CSPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Information Spread with Error Correction.

[BibT_eX]

[DOI]

Omri Ben-Eliezer

CoRR, 2021

Decoding multivariate multiplicity codes on product sets.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance.

[BibT_eX]

[DOI]

Minshen Zhu

Proceedings of the IEEE International Symposium on Information Theory, 2021

Approximability of all finite CSPs with linear sketches.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Streaming Approximation Resistance of Every Ordering CSP.

[BibT_eX]

[DOI]

Noah Singer

Santhoshini Velusamy

Proceedings of the Approximation, 2021

Ideal-Theoretic Explanation of Capacity-Achieving Decoding.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Optimality of Correlated Sampling Strategies.

[BibT_eX]

[DOI]

Theory Comput., 2020

Communication for Generating Correlation: A Unifying Survey.

[BibT_eX]

[DOI]

Himanshu Tyagi

Shun Watanabe

IEEE Trans. Inf. Theory, 2020

Local decoding and testing of polynomials over grids.

[BibT_eX]

[DOI]

Mitali Bafna

Srikanth Srinivasan

Random Struct. Algorithms, 2020

Round Complexity of Common Randomness Generation: The Amortized Setting.

[BibT_eX]

[DOI]

Noah Golowich

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

A Self-contained Analysis of the Lempel-Ziv Compression Algorithm.

[BibT_eX]

[DOI]

David Xiang

CoRR, 2019

Communication for Generating Correlation: A Survey.

[BibT_eX]

[DOI]

Himanshu Tyagi

Shun Watanabe

CoRR, 2019

Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Algorithmic Polarization for Hidden Markov Models.

[BibT_eX]

[DOI]

Preetum Nakkiran

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time.

[BibT_eX]

[DOI]

Soheil Behnezhad

Mahsa Derakhshan

MohammadTaghi Hajiaghayi

Cliff Stein

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

General strong polarization.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Local Decoding and Testing of Polynomials over Grids.

[BibT_eX]

[DOI]

Srikanth Srinivasan

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Synchronization Strings: List Decoding for Insertions and Deletions.

[BibT_eX]

[DOI]

Bernhard Haeupler

Amirbehshad Shahrasbi

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Polar Codes with Exponentially Small Error at Finite Block Length.

[BibT_eX]

[DOI]

Jaroslaw Blasiok

Proceedings of the Approximation, 2018

2017

Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem.

[BibT_eX]

[DOI]

David Gamarnik

SIAM J. Comput., 2017

(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Compression in a Distributed Setting.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

The Power of Shared Randomness in Uncertain Communication.

[BibT_eX]

[DOI]

Badih Ghazi

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

The Optimality of Correlated Sampling.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Communication Complexity of Permutation-Invariant Functions.

[BibT_eX]

[DOI]

Badih Ghazi

Pritish Kamath

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Communication with Contextual Uncertainty.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Decidability of Non-interactive Simulation of Joint Distributions.

[BibT_eX]

[DOI]

Badih Ghazi

Pritish Kamath

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Communication with Contextual Uncertainty.

[BibT_eX]

[DOI]

Ilan Komargodski

Pravesh Kothari

Electron. Colloquium Comput. Complex., 2015

Streaming Lower Bounds for Approximating MAX-CUT.

[BibT_eX]

[DOI]

Michael Kapralov

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Communication with Imperfectly Shared Randomness.

[BibT_eX]

[DOI]

Clément Louis Canonne

Raghu Meka

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Robust Testing of Lifted Codes with Applications to Low-Degree Testing.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem.

[BibT_eX]

[DOI]

David Gamarnik

CoRR, 2014

Optimal error rates for interactive coding I: adaptivity and other settings.

[BibT_eX]

[DOI]

Mohsen Ghaffari

Bernhard Haeupler

Proceedings of the Symposium on Theory of Computing, 2014

Approximating matching size from random streams.

[BibT_eX]

[DOI]

Michael Kapralov

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Deterministic compression with uncertain priors.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

Limits of local algorithms over sparse random graphs.

[BibT_eX]

[DOI]

David Gamarnik

Proceedings of the Innovations in Theoretical Computer Science, 2014

List Decoding Group Homomorphisms Between Supersolvable Groups.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

Queueing with future information.

[BibT_eX]

[DOI]

Joel Spencer

Kuang Xu

SIGMETRICS Perform. Evaluation Rev., 2013

New affine-invariant codes from lifting.

[BibT_eX]

[DOI]

Swastik Kopparty

Proceedings of the Innovations in Theoretical Computer Science, 2013

Absolutely Sound Testing of Lifted Codes.

[BibT_eX]

[DOI]

Noga Ron-Zewi

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

New affine-invariant codes from lifting.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Some closure features of locally testable affine-invariant properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Communication amid uncertainty.

[BibT_eX]

[DOI]

Proceedings of the 2012 IEEE Information Theory Workshop, 2012

Sparse Affine-Invariant Linear Codes Are Locally Testable.

[BibT_eX]

[DOI]

Noga Ron-Zewi

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes.

[BibT_eX]

[DOI]

Noga Ron-Zewi

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Guest column: testing linear properties: some general theme.

[BibT_eX]

[DOI]

SIGACT News, 2011

Testing Linear Properties: Some general themes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Patterns hidden from simple algorithms: technical perspective.

[BibT_eX]

[DOI]

Commun. ACM, 2011

A theory of goal-oriented communication.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Efficient Semantic Communication via Compatible Beliefs.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

Compression without a common prior: an information-theoretic justification for ambiguity in language.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

Property Testing via Set-Theoretic Operations.

[BibT_eX]

[DOI]

Victor Chen

Ning Xie

Proceedings of the Innovations in Computer Science, 2011

Physical limits of Communication (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

Delays and the Capacity of Continuous-Time Channels.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Optimal Testing of Multivariate Polynomials over Small Prime Fields.

[BibT_eX]

[DOI]

Amir Shpilka

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Symmetric LDPC Codes are not Necessarily Locally Testable.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Limits on the Rate of Locally Testable Affine-Invariant Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

On Sums of Locally Testable Affine Invariant Properties.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

From Logarithmic Advice to Single-Bit Advice.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010

Optimal Error Correction for Computationally Bounded Noise.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2010

Invariance in Property Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Testing linear-invariant non-linear properties: A short report.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Invariance in Property Testing.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Optimal Testing of Reed-Muller Codes.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Linear-Invariant Non-linear Properties: A Short Report.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Tight asymptotic bounds for the deletion channel with small deletion probabilities.

[BibT_eX]

[DOI]

Adam Kalai

Michael Mitzenmacher

Proceedings of the IEEE International Symposium on Information Theory, 2010

Optimal Testing of Reed-Muller Codes.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Probabilistically checkable proofs.

[BibT_eX]

[DOI]

Commun. ACM, 2009

Testing Linear-Invariant Non-Linear Properties.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Locally Testable Codes Require Redundant Testers.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Succinct Representation of Codes with Applications to Testing.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Short PCPs with Polylog Query Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Universal Semantic Communication II: A Theory of Goal-Oriented Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Algebraic property testing: the role of invariance.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Universal semantic communication I.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Decodability of group homomorphisms beyond the johnson bound.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Algebraic algorithms and coding theory.

[BibT_eX]

[DOI]

Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2008

2-Transitivity Is Insufficient for Local Testability.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Sparse Random Linear Codes are Locally Decodable and Testable.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

Amplifying Collision Resistance: A Complexity-Theoretic Treatment.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 2007

2006

Special Issue on Randomness and Complexity.

[BibT_eX]

SIAM J. Comput., 2006

Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.

[BibT_eX]

[DOI]

Lars Engebretsen

Networks, 2006

Modelling Errors and Recovery for Communication.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Local Decoding and Testing for Homomorphisms.

[BibT_eX]

[DOI]

Swastik Kopparty

Proceedings of the Approximation, 2006

Robust Local Testability of Tensor Products of LDPC Codes.

[BibT_eX]

[DOI]

Irit Dinur

Avi Wigderson

Proceedings of the Approximation, 2006

2005

Distributed Computing with Imperfect Randomness.

[BibT_eX]

[DOI]

Shafi Goldwasser

Vinod Vaikuntanathan

Proceedings of the Distributed Computing, 19th International Conference, 2005

Optimal Error Correction Against Computationally Bounded Noise.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography, Second Theory of Cryptography Conference, 2005

Simple PCPs with poly-log rate and query complexity.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Derandomization of auctions.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Short PCPs Verifiable in Polylogarithmic Time.

[BibT_eX]

[DOI]

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

From logarithmic advice to single-bit advice

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Robust pcps of proximity, shorter pcps and applications to coding.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Robust Locally Testable Codes and Products of Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2004

Probabilistically checkable proofs.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity Theory., 2004

2003

Reconstructing curves in three (and higher) dimensional space from noisy data.

[BibT_eX]

[DOI]

Don Coppersmith

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Bounds on 2-Query Codeword Testing.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2003

2002

Combinatorial bounds for list decoding.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2002

Foreword.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

A Fuzzy Vault Scheme.

[BibT_eX]

[DOI]

Ari Juels

IACR Cryptol. ePrint Arch., 2002

Harmonic broadcasting is optimal.

[BibT_eX]

[DOI]

Lars Engebretsen

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Guessing secrets efficiently via list decoding.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Locally Testable Codes and PCPs of Almost-Linear Length.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

Decoding Concatenated Codes using Soft Information.

[BibT_eX]

[DOI]

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

On representations of algebraic-geometry codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2001

Adversarial queuing theory.

[BibT_eX]

[DOI]

J. ACM, 2001

Small PCPs with Low Query Complexity.

[BibT_eX]

[DOI]

Prahladh Harsha

Proceedings of the STACS 2001, 2001

Coding Theory: Tutorial and Survey.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Ideal Error-Correcting Codes: Unifying Algebraic and Number-Theoretic Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Applied Algebra, 2001

Complexity classifications of Boolean constraint satisfaction problems.

[BibT_eX]

Nadia Creignou

SIAM monographs on discrete mathematics and applications 7, SIAM, ISBN: 978-0-89871-479-1, 2001

2000

Gadgets, Approximation, and Linear Programming.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

The Approximability of Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

List decoding algorithms for certain concatenated codes.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Random walks with "back buttons" (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

List Decoding: Algorithms and Applications.

[BibT_eX]

[DOI]

Proceedings of the Theoretical Computer Science, 2000

"Soft-decision" Decoding of Chinese Remainder Codes.

[BibT_eX]

[DOI]

Amit Sahai

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Hardness of Approximate Hypergraph Coloring.

[BibT_eX]

[DOI]

Johan Håstad

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

On Representations of Algebraic-Geometric Codes for List Decoding.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2000

1999

Improved decoding of Reed-Solomon and algebraic-geometry codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1999

Pseudorandom Generators Without the XOR Lemma (Extended Abstract).

[BibT_eX]

[DOI]

Salil P. Vadhan

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Chinese Remaindering with Errors.

[BibT_eX]

[DOI]

Dana Ron

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Linear Consistency Testing.

[BibT_eX]

[DOI]

Proceedings of the Randomization, 1999

Hardness of Approximating the Minimum Distance of a Linear Code.

[BibT_eX]

[DOI]

Ilya Dumer

Daniele Micciancio

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Pseudorandom Generators without the XOR Lemma (Abstract).

[BibT_eX]

[DOI]

Salil P. Vadhan

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

Free Bits, PCPs, and Nonapproximability-Towards Tight Results.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Pseudorandom generators without the XOR Lemma

[BibT_eX]

[DOI]

Salil P. Vadhan

Electron. Colloquium Comput. Complex., 1998

Approximating Minimum Feedback Sets and Multicuts in Directed Graphs.

[BibT_eX]

[DOI]

Algorithmica, 1998

Probabilistically Checkable Proofs with Low Amortized Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

A Tight Characterization of NP with 3 Query PCPs.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Computational Indistinguishability: A Sample Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Decoding of Reed Solomon Codes beyond the Error-Correction Bound.

[BibT_eX]

[DOI]

J. Complex., 1997

A statistical perspective on data mining.

[BibT_eX]

[DOI]

Jonathan R. M. Hosking

Edwin P. D. Pednault

Future Gener. Comput. Syst., 1997

A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction.

[BibT_eX]

[DOI]

David P. Williamson

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Improved Low-Degree Testing and its Applications.

[BibT_eX]

[DOI]

Sanjeev Arora

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Algorithmic Issues in Coding Theory.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1997

Constraint Satisfaction: The Approximability of Minimization Problems.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Robust Characterizations of Polynomials with Applications to Program Testing.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

Efficient Routing in Optical Networks.

[BibT_eX]

[DOI]

J. ACM, 1996

A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

[BibT_eX]

[DOI]

David P. Williamson

Electron. Colloquium Comput. Complex., 1996

The Optimization Complexity of Constraint Satisfaction Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

Adversarial Queueing Theory.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Gadgets, Approximation, and Linear Programming (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Maximum Likelihood Decoding of Reed Solomon Codes.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Free Bits, PCP and Non-Approximability - Towards Tight Results

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

Guaranteeing Fair Service to Persistent Dependent Tasks.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Some Improvements to Total Degree Tests.

[BibT_eX]

[DOI]

Katalin Friedl

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Approximating Minimum Feedback Sets and Multi-Cuts in Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 1995

Learning Polynomials with Queries: The Highly Noisy Case.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Private Information Retrieval.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Free Bits, PCPs and Non-Approximability - Towards Tight Results.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Linearity Testing in Characteristic Two.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

A Geometric Approach to Betweenness.

[BibT_eX]

[DOI]

Benny Chor

Proceedings of the Algorithms, 1995

Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems

[BibT_eX]

[DOI]

Lecture Notes in Computer Science 1001, Springer, ISBN: 3-540-60615-7, 1995

1994

Computing Roots of Graphs Is Hard.

[BibT_eX]

[DOI]

Rajeev Motwani

Discret. Appl. Math., 1994

On-Line Algorithms for Locating Checkpoints.

[BibT_eX]

[DOI]

Algorithmica, 1994

The minimum latency problem.

[BibT_eX]

[DOI]

Avrim Blum

Prasad Chalasani

Don Coppersmith

William R. Pulleyblank

Prabhakar Raghavan

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Improved non-approximability results.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Efficient Routing and Scheduling Algorithms for Optical Networks.

[BibT_eX]

[DOI]

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Motion Planning on a Graph (Extended Abstract)

[BibT_eX]

[DOI]

Prabhakar Raghavan

Hisao Tamaki

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

On Syntactic versus Computational Views of Approximability

[BibT_eX]

[DOI]

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Approximate Graph Coloring by Semidefinite Programming

[BibT_eX]

[DOI]

David R. Karger

Rajeev Motwani

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Priority Encoding Transmission

[BibT_eX]

[DOI]

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1992

Highly Resilient Correctors for Polynomials.

[BibT_eX]

[DOI]

Peter Gemmell

Inf. Process. Lett., 1992

Self-Testing Polynomial Functions Efficiently and Over Rational Domains.

[BibT_eX]

[DOI]