Madhu Sudan

Santhoshini Velusamy

Comput. Complex., June, 2024

Sketching Approximability of All Finite CSPs.

[BibT_eX]

[DOI]

J. ACM, April, 2024

Improved PIR Schemes using Matching Vectors and Derivatives.

[BibT_eX]

[DOI]

Fatemeh Ghasemi

Swastik Kopparty

Electron. Colloquium Comput. Complex., 2024

Low Degree Local Correction Over the Boolean Cube.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

Local Correction of Linear Functions over the Boolean Cube.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs.

[BibT_eX]

[DOI]

Aaron (Louie) Putterman

CoRR, 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]

Aaron Putterman

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

Cassandra Marcussen

Elchanan Mossel

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

2023

An Improved Line-Point Low-Degree Test.

[BibT_eX]

[DOI]

Prahladh Harsha

Mrinal Kumar

Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2023

Combinative Cumulative Knowledge Processes.

[BibT_eX]

[DOI]

Anna M. Brandenberger

Cassandra Marcussen

Elchanan Mossel

CoRR, 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 complexity of CSPs with randomly ordered constraints.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Sketching Approximability of (Weak) Monarchy Predicates.

[BibT_eX]

[DOI]

Chi-Ning Chou

Alexander Golovnev

Amirbehshad Shahrasbi

Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

Streaming and Sketching Complexity of CSPs: A survey.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

2021

Linear Space Streaming Lower Bounds for Approximating CSPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Ideal-theoretic Explanation of Capacity-achieving Decoding.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Information Spread with Error Correction.

[BibT_eX]

[DOI]

Omri Ben-Eliezer

Elchanan Mossel

CoRR, 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

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

Decoding Multivariate Multiplicity Codes on Product Sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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]

Electron. Colloquium Comput. Complex., 2018

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Communication with Contextual Uncertainty.

[BibT_eX]

[DOI]

Comput. Complex., 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

Local decoding and testing of polynomials over grids.

[BibT_eX]

[DOI]

Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2017

The Power of Shared Randomness in Uncertain Communication.

[BibT_eX]

[DOI]

Badih Ghazi

Electron. Colloquium Comput. Complex., 2017

Sparse affine-invariant linear codes are locally testable.

[BibT_eX]

[DOI]

Noga Ron-Zewi

Comput. Complex., 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

2016

Decidability of Non-Interactive Simulation of Joint Distributions.

[BibT_eX]

[DOI]

Badih Ghazi

Pritish Kamath

Electron. Colloquium Comput. Complex., 2016

The Optimality of Correlated Sampling.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

2015

Communication with Contextual Uncertainty.

[BibT_eX]

[DOI]

Ilan Komargodski

Pravesh Kothari

Electron. Colloquium Comput. Complex., 2015

Robust testing of lifted codes with applications to low-degree testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Communication Complexity of Permutation-Invariant Functions.

[BibT_eX]

[DOI]

Badih Ghazi

Pritish Kamath

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

2014

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Communication with Imperfectly Shared Randomness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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

Optimal Testing of Multivariate Polynomials over Small Prime Fields.

[BibT_eX]

[DOI]

Amir Shpilka

SIAM J. Comput., 2013

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Absolutely Sound Testing of Lifted Codes.

[BibT_eX]

[DOI]

Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2013

Limits of local algorithms over sparse random graphs.

[BibT_eX]

[DOI]

David Gamarnik

Electron. Colloquium Comput. Complex., 2013

2-Transitivity is Insufficient for Local Testability.

[BibT_eX]

[DOI]

Comput. Complex., 2013

2012

A new upper bound on the query complexity for testing generalized Reed-Muller codes.

[BibT_eX]

[DOI]

Noga Zewi

Electron. Colloquium Comput. Complex., 2012

Deterministic Compression with Uncertain Priors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

New affine-invariant codes from lifting.

[BibT_eX]

[DOI]

Swastik Kopparty

Electron. Colloquium Comput. Complex., 2012

Communication amid uncertainty.

[BibT_eX]

[DOI]

Proceedings of the 2012 IEEE Information Theory Workshop, 2012

2011

Guest column: testing linear properties: some general theme.

[BibT_eX]

[DOI]

SIGACT News, 2011

Derandomization of auctions.

[BibT_eX]

[DOI]

Games Econ. Behav., 2011

Testing Linear Properties: Some general themes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

On Sums of Locally Testable Affine Invariant Properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Patterns hidden from simple algorithms: technical perspective.

[BibT_eX]

[DOI]

Commun. ACM, 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

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

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

Locally Testable Codes Require Redundant Testers.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Invariance in Property Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Efficient Semantic Communication via Compatible Beliefs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Property Testing via Set-Theoretic Operations.

[BibT_eX]

[DOI]

Victor Chen

Ning Xie

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Limits on the rate of locally testable affine-invariant codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Symmetric LDPC codes are not necessarily locally testable.

[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

2009

Succinct Representation of Codes with Applications to Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

A Theory of Goal-Oriented Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Optimal testing of Reed-Muller codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Probabilistically checkable proofs.

[BibT_eX]

[DOI]

Commun. ACM, 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

Decodability of Group Homomorphisms beyond the Johnson Bound.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Testing Linear-Invariant Non-Linear Properties.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Algebraic algorithms and coding theory.

[BibT_eX]

[DOI]

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

2007

Guessing secrets efficiently via list decoding.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

Algebraic Property Testing: The Role of Invariance.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Sparse Random Linear Codes are Locally Decodable and Testable.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Universal Semantic Communication I.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.

[BibT_eX]

[DOI]

SIAM J. Comput., 2006

Harmonic broadcasting is bandwidth-optimal assuming constant bit rate.

[BibT_eX]

[DOI]

Lars Engebretsen

Networks, 2006

Robust Local Testability of Tensor Products of LDPC Codes.

[BibT_eX]

[DOI]

Irit Dinur

Avi Wigderson

Electron. Colloquium Comput. Complex., 2006

A Fuzzy Vault Scheme.

[BibT_eX]

[DOI]

Ari Juels

Des. Codes Cryptogr., 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

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

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

Simple PCPs with Poly-log Rate and Query Complexity

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Robust Locally Testable Codes and Products of Codes

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Probabilistically checkable proofs.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity Theory., 2004

2003

Bounds on 2-Query Codeword Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

2002

Combinatorial bounds for list decoding.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2002

Hardness of Approximate Hypergraph Coloring.

[BibT_eX]

[DOI]

Johan Håstad

SIAM J. Comput., 2002

Foreword.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Locally Testable Codes and PCPs of Almost-Linear Length

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

Harmonic broadcasting is optimal.

[BibT_eX]

[DOI]

Lars Engebretsen

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Pseudorandom Generators without the XOR Lemma.

[BibT_eX]

[DOI]

Salil P. Vadhan

J. Comput. Syst. Sci., 2001

Linear-Consistency Testing.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

Adversarial queuing theory.

[BibT_eX]

[DOI]

J. ACM, 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

List decoding: algorithms and applications.

[BibT_eX]

[DOI]

SIGACT News, 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

Small PCPs with low query complexity.

[BibT_eX]

[DOI]

Prahladh Harsha

Comput. Complex., 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

"Soft-decision" Decoding of Chinese Remainder Codes.

[BibT_eX]

[DOI]

Amit Sahai

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

Computational Indistinguishability: A Sample Hierarchy.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1999

Hardness of Approximating the Minimum Distance of a Linear Code

[BibT_eX]

[DOI]

Ilya Dumer

Daniele Micciancio

Electron. Colloquium Comput. Complex., 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

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

A Geometric Approach to Betweenness.

[BibT_eX]

[DOI]

Benny Chor

SIAM J. Discret. Math., 1998

On Syntactic versus Computational Views of Approximability.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

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

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Guaranteeing Fair Service to Persistent Dependent Tasks.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Reconstructing Algebraic Functions from Mixed Data.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Approximate Graph Coloring by Semidefinite Programming.

[BibT_eX]

[DOI]

David R. Karger

Rajeev Motwani

J. ACM, 1998

Private Information Retrieval.

[BibT_eX]

[DOI]

J. ACM, 1998

Chinese Remaindering with Errors

[BibT_eX]

[DOI]

Dana Ron

Electron. Colloquium Comput. Complex., 1998

Learning Polynomials with Queries - The Highly Noisy Case.

[BibT_eX]

[DOI]

Ronitt Rubinfeld

Electron. Colloquium Comput. Complex., 1998

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Probabilistically checkable proofs with low amortized query complexity

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

A tight characterization of NP with 3 query PCPs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Proof verification and the hardness of approximation problems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Approximating Minimum Feedback Sets and Multicuts in Directed Graphs.

[BibT_eX]

[DOI]

Algorithmica, 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

Improved low-degree testing and its applications

[BibT_eX]

[DOI]

Sanjeev Arora

Electron. Colloquium Comput. Complex., 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

Algorithmic Issues in Coding Theory.

[BibT_eX]

[DOI]

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

1996

Linearity testing in characteristic two.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1996

Priority encoding transmission.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1996

Robust Characterizations of Polynomials with Applications to Program Testing.

[BibT_eX]

[DOI]

Ronitt Rubinfeld

SIAM J. Comput., 1996

Efficient Routing in Optical Networks.

[BibT_eX]

[DOI]

J. ACM, 1996

Constraint satisfaction: The approximability of minimization problems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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

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

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 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

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]

Ronitt Rubinfeld