| Publication | Date of Publication | Type |
|---|
| The Zero-Rate Threshold for Adversarial Bit-Deletions is Less Than 1/2 | 2024-03-19 | Paper |
| Improved Maximally Recoverable LRCs Using Skew Polynomials | 2024-03-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6192473 | 2024-02-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6147247 | 2024-01-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6147248 | 2024-01-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6147277 | 2024-01-15 | Paper |
| Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random | 2023-12-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6090915 | 2023-11-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6059366 | 2023-11-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6062158 | 2023-10-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6084352 | 2023-10-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6176154 | 2023-07-25 | Paper |
| Efficient Linear and Affine Codes for Correcting Insertions/Deletions | 2023-06-14 | Paper |
| Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms | 2023-04-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875456 | 2023-02-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875467 | 2023-02-03 | Paper |
| CNF satisfiability in a subspace and related problems | 2022-10-27 | Paper |
| Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy | 2022-08-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5091226 | 2022-07-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5091253 | 2022-07-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5090416 | 2022-07-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5090431 | 2022-07-18 | Paper |
| Arıkan Meets Shannon: Polar Codes With Near-Optimal Convergence to Channel Capacity | 2022-07-13 | Paper |
| Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations | 2022-06-08 | Paper |
| Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes | 2022-03-31 | Paper |
| General Strong Polarization | 2022-03-31 | Paper |
| Beating Fredman-Komlós for perfect \(k\)-hashing | 2022-02-24 | Paper |
| Threshold Rates for Properties of Random Codes | 2022-02-17 | Paper |
| Bounds for List-Decoding and List-Recovery of Random Linear Codes | 2022-02-17 | Paper |
| Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound | 2022-02-17 | Paper |
| Optimally Resilient Codes for List-Decoding From Insertions and Deletions | 2022-02-17 | Paper |
| An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes | 2022-02-17 | Paper |
| The Quest for Strong Inapproximability Results with Perfect Completeness | 2022-02-16 | Paper |
| Lossless dimension expanders via linearized polynomials and subspace designs | 2021-10-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5009529 | 2021-08-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5009537 | 2021-08-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5002604 | 2021-07-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5002610 | 2021-07-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5002634 | 2021-07-28 | Paper |
| Locality via Partially Lifted Codes | 2021-07-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5002653 | 2021-07-28 | Paper |
| Symmetric Polymorphisms and Efficient Decidability of Promise CSPs | 2021-02-02 | Paper |
| Optimally resilient codes for list-decoding from insertions and deletions | 2021-01-19 | Paper |
| Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity | 2021-01-19 | Paper |
| The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems | 2020-12-04 | Paper |
| Maximally Recoverable LRCs: A Field Size Lower Bound and Constructions for Few Heavy Parities | 2020-12-04 | Paper |
| Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields | 2020-12-04 | Paper |
| ϵ-MSR Codes: Contacting Fewer Code Blocks for Exact Repair | 2020-12-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5136325 | 2020-11-25 | Paper |
| Coding Against Deletions in Oblivious and Online Models | 2020-09-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5121892 | 2020-09-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5111417 | 2020-05-27 | Paper |
| Rainbow Coloring Hardness via Low Sensitivity Polymorphisms | 2020-02-26 | Paper |
| Bridging between 0/1 and linear programming via random walks | 2020-01-30 | Paper |
| CSPs with global modular constraints: algorithms and hardness via polynomial representations | 2020-01-30 | Paper |
| An exponential lower bound on the sub-packetization of MSR codes | 2020-01-30 | Paper |
| An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel | 2020-01-28 | Paper |
| An Algorithmic Blend of LPs and Ring Equations for Promise CSPs | 2019-10-15 | Paper |
| Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness | 2019-10-15 | Paper |
| Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities | 2019-10-15 | Paper |
| General Strong Polarization | 2019-08-22 | Paper |
| Polynomial Time Decodable Codes for the Binary Deletion Channel | 2019-07-19 | Paper |
| How Long Can Optimal Locally Repairable Codes Be? | 2019-07-19 | Paper |
| Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets | 2019-06-20 | Paper |
| Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes | 2019-05-15 | Paper |
| Approximating Non-Uniform Sparsest Cut via Generalized Spectra | 2019-05-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5743431 | 2019-05-10 | Paper |
| Optimal Column-Based Low-Rank Matrix Reconstruction | 2019-05-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5743407 | 2019-05-10 | Paper |
| Strong inapproximability results on balanced rainbow-colorable hypergraphs | 2019-02-01 | Paper |
| Guessing secrets efficiently via list decoding | 2018-11-05 | Paper |
| Bypassing UGC from Some Optimal Geometric Inapproximability Results | 2018-10-30 | Paper |
| Subspace designs based on algebraic function fields | 2018-10-18 | Paper |
| MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth | 2018-09-19 | Paper |
| Efficient Low-Redundancy Codes for Correcting Multiple Deletions | 2018-09-14 | Paper |
| Nearly Optimal NP-Hardness of Unique Coverage | 2018-07-16 | Paper |
| Efficient Low-Redundancy Codes for Correcting Multiple Deletions | 2018-07-16 | Paper |
| An improved bound on the fraction of correctable deletions | 2018-07-16 | Paper |
| MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth | 2018-07-16 | Paper |
| Communication With Imperfectly Shared Randomness | 2018-06-27 | Paper |
| Coding against deletions in oblivious and online models | 2018-03-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4608006 | 2018-03-15 | Paper |
| An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets | 2018-01-24 | Paper |
| Repairing Reed-Solomon Codes | 2017-11-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5368904 | 2017-10-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5368740 | 2017-10-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5368748 | 2017-10-10 | Paper |
| $(2+\varepsilon)$-Sat Is NP-hard | 2017-10-06 | Paper |
| Limitations on Testable Affine-Invariant Codes in the High-Rate Regime | 2017-10-05 | Paper |
| Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs | 2017-10-05 | Paper |
| Repairing Reed-solomon codes | 2017-09-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5365140 | 2017-09-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5365143 | 2017-09-29 | Paper |
| Efficiently List-Decodable Punctured Reed-Muller Codes | 2017-09-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5351896 | 2017-08-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5351907 | 2017-08-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5351908 | 2017-08-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5351936 | 2017-08-31 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5351940 | 2017-08-31 | Paper |
| Explicit subspace designs | 2017-08-25 | Paper |
| Inapproximability of $H$-Transversal/Packing | 2017-08-14 | Paper |
| Better Binary List Decodable Codes Via Multilevel Concatenation | 2017-08-08 | Paper |
| Deletion Codes in the High-Noise and High-Rate Regimes | 2017-07-27 | Paper |
| Soft Decoding, Dual BCH Codes, and Better List-Decodable $\varepsilon$-Biased Codes | 2017-07-27 | Paper |
| On the List-Decodability of Random Linear Codes | 2017-07-27 | Paper |
| A Lower Bound on List Size for List Decoding | 2017-07-27 | Paper |
| The Existence of Concatenated Codes List-Decodable up to the Hamming Bound | 2017-07-27 | Paper |
| Nearly Optimal NP-Hardness of Unique Coverage | 2017-06-28 | Paper |
| Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes | 2017-06-08 | Paper |
| Capacity of non-malleable codes | 2017-05-19 | Paper |
| Complexity of approximating CSP with balance / hard constraints | 2017-05-19 | Paper |
| Communication with Imperfectly Shared Randomness | 2017-05-19 | Paper |
| Combinatorial Limitations of Average-Radius List-Decoding | 2017-05-16 | Paper |
| An Improved Bound on the Fraction of Correctable Deletions | 2017-05-02 | Paper |
| Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs | 2017-04-28 | Paper |
| Capacity of Non-Malleable Codes | 2017-04-28 | Paper |
| Polar Codes: Speed of Polarization and Polynomial Gap to Capacity | 2017-04-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2969660 | 2017-03-22 | Paper |
| Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes | 2017-03-10 | Paper |
| Non-malleable coding against bit-wise and split-state tampering | 2017-03-02 | Paper |
| Superlinear lower bounds for multipass graph processing | 2016-11-29 | Paper |
| List decoding subspace codes from insertions and deletions | 2016-10-07 | Paper |
| Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems | 2016-09-29 | Paper |
| Complexity of approximating CSP with balance/hard constraints | 2016-09-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2816412 | 2016-08-22 | Paper |
| A natural family of optimization problems with arbitrarily small approximation thresholds | 2016-06-09 | Paper |
| Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs | 2015-11-27 | Paper |
| PCPs via the low-degree long code and hardness for constrained hypergraph coloring | 2015-11-16 | Paper |
| Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes | 2015-11-11 | Paper |
| Hardness of Solving Sparse Overdetermined Linear Systems | 2015-09-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5501335 | 2015-08-03 | Paper |
| Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes | 2015-06-26 | Paper |
| Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems | 2015-04-08 | Paper |
| List Decoding Tensor Products and Interleaved Codes | 2015-02-04 | Paper |
| Artin automorphisms, cyclotomic function fields, and folded list-decodable codes | 2015-02-04 | Paper |
| MaxMin allocation via degree lower-bounded arborescences | 2015-02-04 | Paper |
| Explicit capacity-achieving list-decodable codes | 2014-11-25 | Paper |
| Optimal rate algebraic list decoding using narrow ray class fields | 2014-11-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2921702 | 2014-10-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2921790 | 2014-10-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3191580 | 2014-10-06 | Paper |
| List decoding algorithms for certain concatenated codes | 2014-09-26 | Paper |
| Query strategies for priced information (extended abstract) | 2014-09-26 | Paper |
| On the list-decodability of random linear codes | 2014-08-13 | Paper |
| List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound | 2014-08-07 | Paper |
| Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives | 2014-07-30 | Paper |
| Agnostic Learning of Monomials by Halfspaces Is Hard | 2014-07-25 | Paper |
| Folded codes from function field towers and improved optimal rate list decoding | 2014-05-13 | Paper |
| Non-malleable coding against bit-wise and split-state tampering | 2014-02-18 | Paper |
| Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes | 2014-02-04 | Paper |
| Combinatorial Limitations of Average-Radius List Decoding | 2013-10-04 | Paper |
| Agnostic Learning of Monomials by Halfspaces Is Hard | 2013-03-19 | Paper |
| Approximating Bounded Occurrence Ordering CSPs | 2012-11-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2913811 | 2012-09-27 | Paper |
| The query complexity of estimating weighted averages | 2012-03-23 | Paper |
| List Decoding Tensor Products and Interleaved Codes | 2012-02-11 | Paper |
| Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs | 2011-12-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3096712 | 2011-11-11 | Paper |
| Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant | 2011-10-18 | Paper |
| Optimal Rate List Decoding via Derivative Codes | 2011-08-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002775 | 2011-05-24 | Paper |
| Locally Testable Codes Require Redundant Testers | 2011-04-04 | Paper |
| Hardness amplification within NP against deterministic algorithms | 2011-01-18 | Paper |
| On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs | 2010-09-07 | Paper |
| SDP Gaps for 2-to-1 and Other Label-Cover Variants | 2010-09-07 | Paper |
| A new multilayered PCP and the hardness of hypergraph vertex cover | 2010-08-16 | Paper |
| Linear time encodable and list decodable codes | 2010-08-16 | Paper |
| Limits to list decoding Reed-Solomon codes | 2010-08-16 | Paper |
| Correlation clustering with a fixed number of clusters | 2010-08-16 | Paper |
| Better extractors for better codes? | 2010-08-15 | Paper |
| Almost Euclidean subspaces of \ell_1^N via expander codes | 2010-08-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3579474 | 2010-08-06 | Paper |
| Limits to list decodability of linear codes | 2010-08-05 | Paper |
| Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets | 2010-08-05 | Paper |
| Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate | 2010-07-23 | Paper |
| Hardness of Learning Halfspaces with Noise | 2010-04-29 | Paper |
| Hardness amplification via space-efficient direct products | 2010-03-15 | Paper |
| Improved Inapproximability Results for Maximum k-Colorable Subgraph | 2009-10-28 | Paper |
| Iterative Decoding of Low-Density Parity Check Codes (A Survey) | 2009-09-19 | Paper |
| List Decoding of Binary Codes–A Brief Survey of Some Recent Results | 2009-07-23 | Paper |
| Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy | 2009-02-24 | Paper |
| Better Binary List-Decodable Codes Via Multilevel Concatenation | 2009-02-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549611 | 2009-01-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549614 | 2009-01-05 | Paper |
| List decoding from erasures: bounds and code constructions | 2008-12-21 | Paper |
| Linear-Time Encodable/Decodable Codes With Near-Optimal Rate | 2008-12-21 | Paper |
| Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard | 2008-12-21 | Paper |
| Limits to List Decoding Reed–Solomon Codes | 2008-12-21 | Paper |
| Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness | 2008-11-27 | Paper |
| Euclidean Sections of $\ell_1^N$ with Sublinear Randomness and Error-Correction over the Reals | 2008-11-27 | Paper |
| Algorithms for Modular Counting of Roots of Multivariate Polynomials | 2008-09-18 | Paper |
| Hardness Amplification Via Space-Efficient Direct Products | 2008-09-18 | Paper |
| Algorithmic Results in List Decoding | 2008-09-01 | Paper |
| On 2-Query Codeword Testing with Near-Perfect Completeness | 2008-04-24 | Paper |
| Algorithms for modular counting of roots of multivariate polynomials | 2008-04-23 | Paper |
| List Decoding and Pseudorandom Constructions | 2008-04-17 | Paper |
| Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets | 2007-11-30 | Paper |
| Algorithmic Results in List Decoding | 2007-03-07 | Paper |
| Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques | 2006-07-07 | Paper |
| Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques | 2006-07-07 | Paper |
| Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques | 2006-07-07 | Paper |
| The complexity of the covering radius problem | 2006-02-07 | Paper |
| Clustering with qualitative information | 2005-10-10 | Paper |
| A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover | 2005-09-16 | Paper |
| Automata, Languages and Programming | 2005-08-24 | Paper |
| List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition | 2005-06-13 | Paper |
| Constructions of codes from number fields | 2005-05-31 | Paper |
| Combinatorial bounds for list decoding | 2005-05-11 | Paper |
| On the Hardness of 4-Coloring a 3-Colorable Graph | 2005-02-28 | Paper |
| Is constraint satisfaction over two variables always easy? | 2005-01-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4828940 | 2004-11-29 | Paper |
| Inapproximability results for set splitting and satisfiability problems with no mixed clauses | 2004-09-22 | Paper |
| Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems | 2004-08-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4474218 | 2004-08-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4474248 | 2004-08-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4471341 | 2004-07-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4471368 | 2004-07-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4440440 | 2003-12-17 | Paper |
| Hardness of Approximate Hypergraph Coloring | 2002-09-29 | Paper |
| Query strategies for priced information | 2002-09-12 | Paper |
| On representations of algebraic-geometry codes | 2002-08-04 | Paper |
| The \(K_r\)-packing problem | 2002-01-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2753735 | 2001-11-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2753940 | 2001-11-11 | Paper |
| Algorithmic aspects of clique-transversal and clique-independent sets | 2000-11-30 | Paper |
| Improved decoding of Reed-Solomon and algebraic-geometry codes | 2000-09-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252398 | 2000-06-13 | Paper |
| Enumerative aspects of certain subclasses of perfect graphs | 2000-04-26 | Paper |
| Maximum cut on line and total graphs | 1999-11-23 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4232775 | 1999-08-17 | Paper |
