| Publication | Date of Publication | Type |
|---|
| Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance | 2024-03-14 | Paper |
| Linear space streaming lower bounds for approximating CSPs | 2023-12-08 | Paper |
| Streaming approximation resistance of every ordering CSP | 2023-11-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6090914 | 2023-11-20 | Paper |
| Decoding multivariate multiplicity codes on product sets | 2023-11-14 | Paper |
| A geometric approach to betweenness | 2023-05-08 | Paper |
| Is this correct? Let's check! | 2022-11-22 | Paper |
| Approximating minimum feedback sets and multi-cuts in directed graphs | 2022-08-30 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5090416 | 2022-07-18 | Paper |
| General Strong Polarization | 2022-03-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5009529 | 2021-08-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5002755 | 2021-07-28 | Paper |
| Information Spread with Error Correction | 2021-07-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4993289 | 2021-06-15 | Paper |
| Round Complexity of Common Randomness Generation: The Amortized Setting | 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 | 2020-12-17 | Paper |
| Local decoding and testing of polynomials over grids | 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 | 2020-01-28 | Paper |
| Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation | 2019-10-15 | Paper |
| General Strong Polarization | 2019-08-22 | Paper |
| Approximating matching size from random streams | 2019-06-20 | Paper |
| Communication with contextual uncertainty | 2018-11-07 | Paper |
| Guessing secrets efficiently via list decoding | 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 with contextual uncertainty | 2018-07-16 | Paper |
| Communication Complexity of Permutation-Invariant Functions | 2018-07-16 | Paper |
| (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space | 2018-07-16 | Paper |
| Communication With Imperfectly Shared Randomness | 2018-06-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4638068 | 2018-05-03 | Paper |
| Synchronization Strings: List Decoding for Insertions and Deletions | 2018-02-23 | Paper |
| Limitations on Testable Affine-Invariant Codes in the High-Rate Regime | 2017-10-05 | Paper |
| Streaming Lower Bounds for Approximating MAX-CUT | 2017-10-05 | Paper |
| Limits of local algorithms over sparse random graphs | 2017-10-05 | Paper |
| Sparse affine-invariant linear codes are locally testable | 2017-07-28 | Paper |
| Optimal Error Correction for Computationally Bounded Noise | 2017-07-27 | Paper |
| Limits of local algorithms over sparse random graphs | 2017-05-19 | Paper |
| Deterministic compression with uncertain priors | 2017-05-19 | Paper |
| Communication with Imperfectly Shared Randomness | 2017-05-19 | Paper |
| New affine-invariant codes from lifting | 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 | 2017-03-10 | Paper |
| Deterministic compression with uncertain priors | 2016-11-29 | Paper |
| Chinese remaindering with errors | 2016-09-29 | Paper |
| Pseudorandom generators without the XOR Lemma (extended abstract) | 2016-09-29 | Paper |
| The minimum latency problem | 2016-09-01 | Paper |
| Improved non-approximability results | 2016-09-01 | Paper |
| Adversarial queuing theory | 2015-09-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2941633 | 2015-08-21 | Paper |
| Optimal error rates for interactive coding I | 2015-06-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3191595 | 2014-10-06 | Paper |
| List decoding algorithms for certain concatenated codes | 2014-09-26 | Paper |
| Random walks with “back buttons” (extended abstract) | 2014-09-26 | Paper |
| Queuing with future information | 2014-09-25 | Paper |
| Optimal Testing of Multivariate Polynomials over Small Prime Fields | 2014-07-30 | Paper |
| Delays and the Capacity of Continuous-Time Channels | 2014-07-30 | Paper |
| Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers | 2014-07-25 | Paper |
| Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers | 2014-04-11 | Paper |
| A theory of goal-oriented communication | 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 | 2013-10-04 | Paper |
| Optimal Testing of Multivariate Polynomials over Small Prime Fields | 2013-07-24 | Paper |
| 2-transitivity is insufficient for local testability | 2013-04-11 | Paper |
| Succinct Representation of Codes with Applications to Testing | 2013-04-09 | Paper |
| A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes | 2012-11-02 | Paper |
| Testing Linear-Invariant Non-Linear Properties | 2012-04-24 | Paper |
| Quick and Dirty Refereeing? | 2011-11-28 | Paper |
| Kakeya-type sets in finite vector spaces | 2011-11-07 | Paper |
| From Logarithmic Advice to Single-Bit Advice | 2011-08-19 | Paper |
| On Sums of Locally Testable Affine Invariant Properties | 2011-08-17 | Paper |
| Limits on the Rate of Locally Testable Affine-Invariant Codes | 2011-08-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002831 | 2011-05-24 | Paper |
| Derandomization of auctions | 2011-05-16 | Paper |
| Locally Testable Codes Require Redundant Testers | 2011-04-04 | Paper |
| Invariance in Property Testing | 2010-10-12 | Paper |
| Testing Linear-Invariant Non-linear Properties: A Short Report | 2010-10-12 | Paper |
| Optimal Testing of Reed-Muller Codes | 2010-10-12 | Paper |
| Derandomization of auctions | 2010-08-16 | Paper |
| Randomness-efficient low degree tests and short PCPs via epsilon-biased sets | 2010-08-16 | Paper |
| Reconstructing curves in three (and higher) dimensional space from noisy data | 2010-08-16 | Paper |
| Simple PCPs with poly-log rate and query complexity | 2010-08-16 | Paper |
| Robust pcps of proximity, shorter pcps and applications to coding | 2010-08-15 | Paper |
| Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques | 2010-05-26 | Paper |
| Succinct Representation of Codes with Applications to Testing | 2009-10-28 | Paper |
| An improved lower bound on the size of Kakeya sets over finite fields | 2009-09-17 | Paper |
| Short PCPs with Polylog Query Complexity | 2009-04-30 | Paper |
| Amplifying Collision Resistance: A Complexity-Theoretic Treatment | 2009-03-10 | Paper |
| Algebraic algorithms and coding theory | 2009-01-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549692 | 2009-01-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549711 | 2009-01-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549724 | 2009-01-05 | Paper |
| Locally testable codes and PCPs of almost-linear length | 2008-12-21 | Paper |
| Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding | 2007-09-07 | Paper |
| Local Decoding and Testing for Homomorphisms | 2007-08-28 | Paper |
| Robust Local Testability of Tensor Products of LDPC Codes | 2007-08-28 | Paper |
| On Dinur’s proof of the PCP theorem | 2007-03-21 | Paper |
| Distributed Computing | 2006-11-01 | Paper |
| Robust locally testable codes and products of codes | 2006-09-06 | Paper |
| Improved low-degree testing and its applications | 2006-06-27 | Paper |
| Harmonic broadcasting is bandwidth-optimal assuming constant bit rate | 2006-06-06 | Paper |
| A fuzzy vault scheme | 2006-05-29 | Paper |
| Theory of Cryptography | 2005-12-07 | Paper |
| Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2005-08-25 | Paper |
| Hardness of approximating the minimum distance of a linear code | 2005-05-31 | Paper |
| Combinatorial bounds for list decoding | 2005-05-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4650575 | 2005-02-18 | Paper |
| Proof verification and the hardness of approximation problems | 2005-01-25 | Paper |
| Private information retrieval | 2005-01-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4828940 | 2004-11-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4828964 | 2004-11-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4474234 | 2004-08-04 | Paper |
| Random walks with ``back buttons | 2003-05-06 | Paper |
| Pseudorandom generators without the XOR lemma | 2003-02-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4536409 | 2002-11-25 | Paper |
| Hardness of Approximate Hypergraph Coloring | 2002-09-29 | Paper |
| On representations of algebraic-geometry codes | 2002-08-04 | Paper |
| Linear-consistency testing. | 2002-07-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4230322 | 2002-01-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2762515 | 2002-01-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2753940 | 2001-11-11 | Paper |
| Small PCPs with low query complexity | 2001-10-14 | Paper |
| Complexity Classifications of Boolean Constraint Satisfaction Problems | 2001-07-03 | Paper |
| The Approximability of Constraint Satisfaction Problems | 2001-03-19 | Paper |
| Learning Polynomials with Queries: The Highly Noisy Case | 2001-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4526965 | 2001-02-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527016 | 2001-02-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4941830 | 2000-12-18 | Paper |
| Gadgets, Approximation, and Linear Programming | 2000-10-18 | Paper |
| Chinese remaindering with errors | 2000-09-07 | Paper |
| Improved decoding of Reed-Solomon and algebraic-geometry codes | 2000-09-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4231909 | 2000-04-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252727 | 2000-04-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252728 | 2000-04-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228491 | 2000-04-04 | Paper |
| Computational indistinguishability: A sample hierarchy | 2000-01-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4230375 | 1999-11-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4258568 | 1999-09-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252714 | 1999-08-31 | Paper |
| Approximate graph coloring by semidefinite programming | 1999-01-11 | Paper |
| On Syntactic versus Computational Views of Approximability | 1998-09-21 | Paper |
| Reconstructing Algebraic Functions from Mixed Data | 1998-09-21 | Paper |
| A Geometric Approach to Betweenness | 1998-09-21 | Paper |
| Guaranteeing Fair Service to Persistent Dependent Tasks | 1998-09-20 | Paper |
| Probabilistic verification of proofs | 1998-08-05 | Paper |
| Free Bits, PCPs, and Nonapproximability---Towards Tight Results | 1998-05-10 | Paper |
| Efficient routing in optical networks | 1998-01-22 | Paper |
| Approximating minimum feedback sets and multicuts in directed graphs | 1998-01-01 | Paper |
| Decoding of Reed Solomon codes beyond the error-correction bound | 1997-09-16 | Paper |
| Linearity testing in characteristic two | 1997-08-07 | Paper |
| Priority encoding transmission | 1997-06-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3128902 | 1997-06-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4370031 | 1997-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4886054 | 1996-10-13 | Paper |
| Robust Characterizations of Polynomials with Applications to Program Testing | 1996-08-18 | Paper |
| Efficient checking of polynomials and proofs and the hardness of approximation problems | 1996-01-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4763385 | 1995-04-11 | Paper |
| Computing roots of graphs is hard | 1994-11-03 | Paper |
| On-line algorithms for locating checkpoints | 1994-01-19 | Paper |
| Highly resilient correctors for polynomials | 1993-01-17 | Paper |
