| Publication | Date of Publication | Type |
|---|
Low-degree testing over grids
| 2025-01-14 | Paper |
Code sparsification and its applications
| 2024-11-28 | Paper |
Is this correct? Let's check!
| 2024-09-25 | Paper |
Sketching approximability of (weak) monarchy predicates
| 2024-08-22 | Paper |
Streaming approximation resistance of every ordering CSP
Computational Complexity | 2024-08-01 | Paper |
Ideal-theoretic explanation of capacity-achieving decoding
IEEE Transactions on Information Theory | 2024-07-22 | Paper |
Decoding multivariate multiplicity codes on product sets
IEEE Transactions on Information Theory | 2024-07-21 | Paper |
Streaming and sketching complexity of CSPs: a survey (invited talk)
| 2024-06-24 | Paper |
Streaming complexity of CSPs with randomly ordered constraints
| 2024-05-14 | Paper |
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance
IEEE Transactions on Information Theory | 2024-03-14 | Paper |
Linear space streaming lower bounds for approximating CSPs
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Streaming approximation resistance of every ordering CSP
| 2023-11-20 | Paper |
scientific article; zbMATH DE number 7768401 (Why is no real title available?)
| 2023-11-20 | Paper |
Decoding multivariate multiplicity codes on product sets
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
A geometric approach to betweenness
Lecture Notes in Computer Science | 2023-05-08 | Paper |
Is this correct? Let's check!
| 2022-11-22 | Paper |
Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
Integer Programming and Combinatorial Optimization | 2022-08-30 | Paper |
Algorithmic polarization for hidden Markov models
| 2022-07-18 | Paper |
General strong polarization
Journal of the ACM | 2022-03-31 | Paper |
Polar codes with exponentially small error at finite block length
| 2021-08-04 | Paper |
Synchronization strings: list decoding for insertions and deletions
| 2021-07-28 | Paper |
Information Spread with Error Correction
| 2021-07-13 | Paper |
Local decoding and testing of polynomials over grids
| 2021-06-15 | Paper |
Round Complexity of Common Randomness Generation: The Amortized Setting
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Elementary analysis of isolated zeroes of a polynomial system
| 2021-01-31 | Paper |
Point-hyperplane incidence geometry and the log-rank conjecture
| 2021-01-23 | Paper |
Optimality of correlated sampling strategies
Theory of Computing | 2020-12-17 | Paper |
Local decoding and testing of polynomials over grids
Random Structures \& Algorithms | 2020-11-30 | Paper |
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance
| 2020-11-27 | Paper |
The Power of Shared Randomness in Uncertain Communication
| 2020-05-27 | Paper |
Communication for Generating Correlation: A Unifying Survey
IEEE Transactions on Information Theory | 2020-01-28 | Paper |
Communication-rounds tradeoffs for common randomness and secret key generation
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
General strong polarization
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Approximating matching size from random streams
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Communication with contextual uncertainty
Computational Complexity | 2018-11-07 | Paper |
Guessing secrets efficiently via list decoding
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Polar Codes with exponentially small error at finite block length
| 2018-10-09 | Paper |
Algorithmic Polarization for Hidden Markov Models
| 2018-10-03 | Paper |
Communication complexity of permutation-invariant functions
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
\((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Communication with contextual uncertainty
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Communication With Imperfectly Shared Randomness
IEEE Transactions on Information Theory | 2018-06-27 | Paper |
scientific article; zbMATH DE number 6866309 (Why is no real title available?)
| 2018-05-03 | Paper |
Synchronization Strings: List Decoding for Insertions and Deletions
| 2018-02-23 | Paper |
Limits of local algorithms over sparse random graphs
The Annals of Probability | 2017-10-05 | Paper |
Streaming Lower Bounds for Approximating MAX-CUT
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Sparse affine-invariant linear codes are locally testable
Computational Complexity | 2017-07-28 | Paper |
Optimal Error Correction for Computationally Bounded Noise
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
Limits of local algorithms over sparse random graphs
Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
Deterministic compression with uncertain priors
Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
Communication with imperfectly shared randomness
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
New affine-invariant codes from lifting
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
List decoding group homomorphisms between supersolvable groups
| 2017-03-22 | Paper |
Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem
SIAM Journal on Computing | 2017-03-10 | Paper |
Deterministic compression with uncertain priors
Algorithmica | 2016-11-29 | Paper |
Pseudorandom generators without the XOR lemma (extended abstract)
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Chinese remaindering with errors
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Improved non-approximability results
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
The minimum latency problem
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Adversarial queuing theory
Journal of the ACM | 2015-09-20 | Paper |
Absolutely sound testing of lifted codes
Theory of Computing | 2015-08-21 | Paper |
Optimal error rates for interactive coding. I: Adaptivity and other settings
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
A new upper bound on the query complexity of testing generalized Reed-Muller codes
Theory of Computing | 2014-10-06 | Paper |
List decoding algorithms for certain concatenated codes
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Random walks with “back buttons” (extended abstract)
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Queuing with future information
The Annals of Applied Probability | 2014-09-25 | Paper |
Optimal Testing of Multivariate Polynomials over Small Prime Fields
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Delays and the Capacity of Continuous-Time Channels
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Extensions to the method of multiplicities, with applications to Kakeya sets and mergers
SIAM Journal on Computing | 2014-04-11 | Paper |
A theory of goal-oriented communication
Journal of the ACM | 2014-02-17 | Paper |
Performance of the Survey Propagation-guided decimation algorithm for the random NAE-K-SAT problem
| 2014-02-01 | Paper |
Absolutely sound testing of lifted codes
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Optimal testing of multivariate polynomials over small prime fields
SIAM Journal on Computing | 2013-07-24 | Paper |
2-transitivity is insufficient for local testability
Computational Complexity | 2013-04-11 | Paper |
Succinct representation of codes with applications to testing
SIAM Journal on Discrete Mathematics | 2013-04-09 | Paper |
A new upper bound on the query complexity for testing generalized Reed-Muller codes
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Testing linear-invariant non-linear properties
| 2012-04-24 | Paper |
Quick and Dirty Refereeing?
Science | 2011-11-28 | Paper |
Kakeya-type sets in finite vector spaces
Journal of Algebraic Combinatorics | 2011-11-07 | Paper |
From logarithmic advice to single-bit advice
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Limits on the Rate of Locally Testable Affine-Invariant Codes
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
On Sums of Locally Testable Affine Invariant Properties
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Testing linear-invariant non-linear properties
Theory of Computing | 2011-05-24 | Paper |
Derandomization of auctions
Games and Economic Behavior | 2011-05-16 | Paper |
Locally Testable Codes Require Redundant Testers
SIAM Journal on Computing | 2011-04-04 | Paper |
Optimal testing of Reed-Muller codes
Property Testing | 2010-10-12 | Paper |
Testing Linear-Invariant Non-linear Properties: A Short Report
Property Testing | 2010-10-12 | Paper |
Invariance in property testing
Property Testing | 2010-10-12 | Paper |
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Derandomization of auctions
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Simple PCPs with poly-log rate and query complexity
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Reconstructing curves in three (and higher) dimensional space from noisy data
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Robust PSPs of proximity, shorter PSPs and applications to coding
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Bounds on \(2\)-query codeword testing
Lecture Notes in Computer Science | 2010-05-26 | Paper |
Succinct Representation of Codes with Applications to Testing
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
An improved lower bound on the size of Kakeya sets over finite fields
Analysis \& PDE | 2009-09-17 | Paper |
Short PCPs with Polylog Query Complexity
SIAM Journal on Computing | 2009-04-30 | Paper |
Amplifying Collision Resistance: A Complexity-Theoretic Treatment
Advances in Cryptology - CRYPTO 2007 | 2009-03-10 | Paper |
Algebraic algorithms and coding theory
Proceedings of the twenty-first international symposium on Symbolic and algebraic computation | 2009-01-20 | Paper |
Algebraic property testing: the role of invariance
| 2009-01-05 | Paper |
scientific article; zbMATH DE number 5485539 (Why is no real title available?)
| 2009-01-05 | Paper |
scientific article; zbMATH DE number 5485523 (Why is no real title available?)
| 2009-01-05 | Paper |
Locally testable codes and PCPs of almost-linear length
Journal of the ACM | 2008-12-21 | Paper |
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
SIAM Journal on Computing | 2007-09-07 | Paper |
Robust Local Testability of Tensor Products of LDPC Codes
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Local Decoding and Testing for Homomorphisms
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
On Dinur’s proof of the PCP theorem
Bulletin of the American Mathematical Society | 2007-03-21 | Paper |
Distributed Computing
Lecture Notes in Computer Science | 2006-11-01 | Paper |
Robust locally testable codes and products of codes
Random Structures \& Algorithms | 2006-09-06 | Paper |
Improved low-degree testing and its applications
Combinatorica | 2006-06-27 | Paper |
Harmonic broadcasting is bandwidth-optimal assuming constant bit rate
Networks | 2006-06-06 | Paper |
A fuzzy vault scheme
Designs, Codes and Cryptography | 2006-05-29 | Paper |
Theory of Cryptography
Lecture Notes in Computer Science | 2005-12-07 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Hardness of approximating the minimum distance of a linear code
IEEE Transactions on Information Theory | 2005-05-31 | Paper |
Combinatorial bounds for list decoding
IEEE Transactions on Information Theory | 2005-05-11 | Paper |
scientific article; zbMATH DE number 2134909 (Why is no real title available?)
| 2005-02-18 | Paper |
Proof verification and the hardness of approximation problems
Journal of the ACM | 2005-01-25 | Paper |
Private information retrieval
Journal of the ACM | 2005-01-25 | Paper |
scientific article; zbMATH DE number 2119669 (Why is no real title available?)
| 2004-11-29 | Paper |
scientific article; zbMATH DE number 2119693 (Why is no real title available?)
| 2004-11-29 | Paper |
scientific article; zbMATH DE number 2081120 (Why is no real title available?)
| 2004-08-04 | Paper |
Random walks with ``back buttons
The Annals of Applied Probability | 2003-05-06 | Paper |
Pseudorandom generators without the XOR lemma
Journal of Computer and System Sciences | 2003-02-04 | Paper |
scientific article; zbMATH DE number 1759459 (Why is no real title available?)
| 2002-11-25 | Paper |
Hardness of Approximate Hypergraph Coloring
SIAM Journal on Computing | 2002-09-29 | Paper |
On representations of algebraic-geometry codes
IEEE Transactions on Information Theory | 2002-08-04 | Paper |
Linear-consistency testing.
Journal of Computer and System Sciences | 2002-07-02 | Paper |
scientific article; zbMATH DE number 1256636 (Why is no real title available?)
| 2002-01-17 | Paper |
scientific article; zbMATH DE number 1688375 (Why is no real title available?)
| 2002-01-09 | Paper |
scientific article; zbMATH DE number 1670663 (Why is no real title available?)
| 2001-11-11 | Paper |
Small PCPs with low query complexity
Computational Complexity | 2001-10-14 | Paper |
Complexity classifications of Boolean constraint satisfaction problems
SIAM Monographs on Discrete Mathematics and Applications | 2001-07-03 | Paper |
The approximability of constraint satisfaction problems
SIAM Journal on Computing | 2001-03-19 | Paper |
Learning polynomials with queries: The highly noisy case
SIAM Journal on Discrete Mathematics | 2001-03-19 | Paper |
scientific article; zbMATH DE number 1559564 (Why is no real title available?)
| 2001-02-28 | Paper |
scientific article; zbMATH DE number 1559517 (Why is no real title available?)
| 2001-02-28 | Paper |
scientific article; zbMATH DE number 1418270 (Why is no real title available?)
| 2000-12-18 | Paper |
Gadgets, Approximation, and Linear Programming
SIAM Journal on Computing | 2000-10-18 | Paper |
Improved decoding of Reed-Solomon and algebraic-geometry codes
IEEE Transactions on Information Theory | 2000-09-07 | Paper |
Chinese remaindering with errors
IEEE Transactions on Information Theory | 2000-09-07 | Paper |
scientific article; zbMATH DE number 1306875 (Why is no real title available?)
| 2000-04-26 | Paper |
scientific article; zbMATH DE number 1261806 (Why is no real title available?)
| 2000-04-26 | Paper |
scientific article; zbMATH DE number 1306876 (Why is no real title available?)
| 2000-04-26 | Paper |
scientific article; zbMATH DE number 1256755 (Why is no real title available?)
| 2000-04-04 | Paper |
Computational indistinguishability: A sample hierarchy
Journal of Computer and System Sciences | 2000-01-17 | Paper |
scientific article; zbMATH DE number 1256688 (Why is no real title available?)
| 1999-11-08 | Paper |
scientific article; zbMATH DE number 1335877 (Why is no real title available?)
| 1999-09-13 | Paper |
scientific article; zbMATH DE number 1306862 (Why is no real title available?)
| 1999-08-31 | Paper |
Approximate graph coloring by semidefinite programming
Journal of the ACM | 1999-01-11 | Paper |
On Syntactic versus Computational Views of Approximability
SIAM Journal on Computing | 1998-09-21 | Paper |
A Geometric Approach to Betweenness
SIAM Journal on Discrete Mathematics | 1998-09-21 | Paper |
Reconstructing Algebraic Functions from Mixed Data
SIAM Journal on Computing | 1998-09-21 | Paper |
Guaranteeing Fair Service to Persistent Dependent Tasks
SIAM Journal on Computing | 1998-09-20 | Paper |
Probabilistic verification of proofs
Documenta Mathematica | 1998-08-05 | Paper |
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
SIAM Journal on Computing | 1998-05-10 | Paper |
Efficient routing in optical networks
Journal of the ACM | 1998-01-22 | Paper |
Approximating minimum feedback sets and multicuts in directed graphs
Algorithmica | 1998-01-01 | Paper |
Decoding of Reed Solomon codes beyond the error-correction bound
Journal of Complexity | 1997-09-16 | Paper |
Linearity testing in characteristic two
IEEE Transactions on Information Theory | 1997-08-07 | Paper |
Priority encoding transmission
IEEE Transactions on Information Theory | 1997-06-12 | Paper |
scientific article; zbMATH DE number 1003273 (Why is no real title available?)
| 1997-06-02 | Paper |
scientific article; zbMATH DE number 1104164 (Why is no real title available?)
| 1997-01-01 | Paper |
scientific article; zbMATH DE number 910880 (Why is no real title available?)
| 1996-10-13 | Paper |
Robust Characterizations of Polynomials with Applications to Program Testing
SIAM Journal on Computing | 1996-08-18 | Paper |
Efficient checking of polynomials and proofs and the hardness of approximation problems
Lecture Notes in Computer Science | 1996-01-24 | Paper |
scientific article; zbMATH DE number 742944 (Why is no real title available?)
| 1995-04-11 | Paper |
Computing roots of graphs is hard
Discrete Applied Mathematics | 1994-11-03 | Paper |
On-line algorithms for locating checkpoints
Algorithmica | 1994-01-19 | Paper |
Highly resilient correctors for polynomials
Information Processing Letters | 1993-01-17 | Paper |
Errors are Robustly Tamed in Cumulative Knowledge Processes
| N/A | Paper |
Spectral non-concentration near the top for unimodular random graphs
| N/A | Paper |
