| Publication | Date of Publication | Type |
|---|
| Clustering with qualitative information | 2026-05-29 | Paper |
| Correlated algebraic-geometric codes: improved list decoding over bounded alphabets | 2026-05-29 | Paper |
| Hardness of learning halfspaces with noise | 2026-05-29 | Paper |
| Outlier robust multivariate polynomial regression | 2026-05-26 | Paper |
| Conditional dichotomy of Boolean ordered promise CSPs | 2026-05-12 | Paper |
| Hardness of approximate hypergraph coloring | 2026-05-08 | Paper |
| ''Soft-decision'' decoding of Chinese remainder codes | 2026-05-08 | Paper |
| Combinatorial feature selection problems | 2026-05-08 | Paper |
| Expander-based constructions of efficiently decodable codes | 2026-05-08 | Paper |
| Sharp threshold rates for random codes | 2026-04-15 | Paper |
| Pseudobinomiality of the sticky random walk | 2026-04-15 | Paper |
| d-to-1 hardness of coloring 3-colorable graphs with o(1) colors | 2026-03-18 | Paper |
Certifying Euclidean sections and finding planted sparse vectors beyond the \(\sqrt{n}\) dimension threshold
SIAM Journal on Computing | 2026-03-11 | Paper |
| Baby PIH: Parameterized inapproximability of min CSP | 2026-01-28 | Paper |
| Semirandom planted clique via 1-norm isometry property | 2025-12-22 | Paper |
Parameterized inapproximability hypothesis under ETH
Journal of the ACM | 2025-11-27 | Paper |
| Improved decoding of Reed-Solomon and algebraic-geometric codes | 2025-10-29 | Paper |
| Capacity-achieving gray codes | 2025-10-06 | Paper |
SDPs and robust satisfiability of promise CSP
Discrete Analysis | 2025-09-19 | Paper |
Punctured low-bias codes behave like random linear codes
Discrete Analysis | 2025-09-12 | Paper |
| Efficient algorithms for semirandom planted CSPs at the refutation threshold | 2025-08-15 | Paper |
| Punctured low-bias codes behave like random linear codes | 2025-08-15 | Paper |
| The zero-rate threshold for adversarial bit-deletions is less than 1/2 | 2025-08-13 | Paper |
| Weak decoupling, polynomial folds and approximate optimization over the sphere | 2025-08-06 | Paper |
| Robust Fourier and polynomial curve fitting | 2025-08-06 | Paper |
| (2 + )-SAT is NP-hard | 2025-08-05 | Paper |
Range avoidance for low-depth circuits and connections to pseudorandomness
ACM Transactions on Computation Theory | 2025-08-01 | Paper |
| Hardness of learning Boolean functions from label proportions | 2025-07-28 | Paper |
A locality-based lens for coded computation
IEEE Transactions on Information Theory | 2025-07-14 | Paper |
Binary error-correcting codes with minimal noiseless feedback
IEEE Transactions on Information Theory | 2025-07-11 | Paper |
AG codes have no list-decoding friends: approaching the generalized Singleton bound requires exponential alphabets
IEEE Transactions on Information Theory | 2025-07-11 | Paper |
Approximate hypergraph vertex cover and generalized Tuza's conjecture
SIAM Journal on Discrete Mathematics | 2025-06-25 | Paper |
| PCPs via low-degree long code and hardness for constrained hypergraph coloring | 2025-05-20 | Paper |
| Polar codes: speed of polarization and polynomial gap to capacity | 2025-05-20 | Paper |
| Explicit subspace designs | 2025-05-20 | Paper |
| Faster SDP hierarchy solvers for local rounding algorithms | 2025-05-05 | Paper |
| Codes for computationally simple channels: explicit constructions with optimal rate | 2025-04-29 | Paper |
Obituary for Luca Trevisan
Bulletin of the European Association for Theoretical Computer Science EATCS | 2025-04-22 | Paper |
A deterministic construction of a large distance code from the Wozencraft ensemble
IEEE Transactions on Information Theory | 2025-02-27 | Paper |
| A deterministic construction of a large distance code from the Wozencraft ensemble | 2025-01-14 | Paper |
| AG codes have no list-decoding friends: approaching the generalized Singleton bound requires exponential alphabets | 2024-11-28 | Paper |
Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms
SIAM Journal on Computing | 2024-10-21 | Paper |
| Beyond single-deletion correcting codes: substitutions and transpositions | 2024-08-22 | Paper |
| Accelerating polarization via alphabet extension | 2024-08-22 | Paper |
| Range avoidance for low-depth circuits and connections to pseudorandomness | 2024-08-22 | Paper |
| Bypassing the XOR trick: stronger certificates for hypergraph clique number | 2024-08-22 | Paper |
| Approximate hypergraph vertex cover and generalized Tuza's conjecture | 2024-07-19 | Paper |
| _p-spread and restricted isometry properties of sparse random matrices | 2024-07-05 | Paper |
Conditional dichotomy of Boolean ordered promise CSPs
TheoretiCS | 2024-07-03 | Paper |
| Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms | 2024-05-08 | Paper |
| SDPs and robust satisfiability of promise CSP | 2024-05-08 | Paper |
The Zero-Rate Threshold for Adversarial Bit-Deletions is Less Than 1/2
IEEE Transactions on Information Theory | 2024-03-19 | Paper |
Improved Maximally Recoverable LRCs Using Skew Polynomials
IEEE Transactions on Information Theory | 2024-03-14 | Paper |
| CNF satisfiability in a subspace and related problems | 2024-02-12 | Paper |
| scientific article; zbMATH DE number 7788339 (Why is no real title available?) | 2024-01-15 | Paper |
| scientific article; zbMATH DE number 7788340 (Why is no real title available?) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788366 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
scientific article; zbMATH DE number 7768402 (Why is no real title available?)
(available as arXiv preprint) | 2023-11-20 | Paper |
| Leakage-Resilient Secret Sharing in Non-Compartmentalized Models. | 2023-11-02 | Paper |
| scientific article; zbMATH DE number 7758311 (Why is no real title available?) | 2023-10-31 | Paper |
| Revisiting alphabet reduction in Dinur’s PCP. | 2023-10-31 | Paper |
| A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation | 2023-08-29 | Paper |
| scientific article; zbMATH DE number 7716602 (Why is no real title available?) | 2023-07-25 | Paper |
Efficient Linear and Affine Codes for Correcting Insertions/Deletions
SIAM Journal on Discrete Mathematics | 2023-06-14 | Paper |
| A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble | 2023-05-03 | Paper |
Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
SIAM Journal on Computing | 2023-04-04 | Paper |
| Rainbow Coloring Hardness via Low Sensitivity Polymorphisms | 2023-02-03 | Paper |
scientific article; zbMATH DE number 7650072 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
| Binary Error-Correcting Codes with Minimal Noiseless Feedback | 2022-12-11 | Paper |
CNF satisfiability in a subspace and related problems
Algorithmica | 2022-10-27 | Paper |
Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
SIAM Journal on Computing | 2022-08-17 | Paper |
Beating Fredman-Komlós for Perfect k-Hashing.
(available as arXiv preprint) | 2022-07-21 | Paper |
| scientific article; zbMATH DE number 7561561 (Why is no real title available?) | 2022-07-21 | Paper |
scientific article; zbMATH DE number 7559096 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-18 | Paper |
Algorithmic polarization for hidden Markov models
(available as arXiv preprint) | 2022-07-18 | Paper |
Arıkan Meets Shannon: Polar Codes With Near-Optimal Convergence to Channel Capacity
IEEE Transactions on Information Theory | 2022-07-13 | Paper |
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
SIAM Journal on Computing | 2022-06-08 | Paper |
Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes
Journal of the ACM | 2022-03-31 | Paper |
General strong polarization
Journal of the ACM | 2022-03-31 | Paper |
Beating Fredman-Komlós for perfect \(k\)-hashing
Journal of Combinatorial Theory. Series A | 2022-02-24 | Paper |
Bounds for List-Decoding and List-Recovery of Random Linear Codes
IEEE Transactions on Information Theory | 2022-02-17 | Paper |
Threshold Rates for Properties of Random Codes
IEEE Transactions on Information Theory | 2022-02-17 | Paper |
An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes
IEEE Transactions on Information Theory | 2022-02-17 | Paper |
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound
IEEE Transactions on Information Theory | 2022-02-17 | Paper |
Optimally Resilient Codes for List-Decoding From Insertions and Deletions
IEEE Transactions on Information Theory | 2022-02-17 | Paper |
The Quest for Strong Inapproximability Results with Perfect Completeness
ACM Transactions on Algorithms | 2022-02-16 | Paper |
Lossless dimension expanders via linearized polynomials and subspace designs
Combinatorica | 2021-10-25 | Paper |
| Punctured Low-Bias Codes Behave Like Random Linear Codes | 2021-09-23 | Paper |
| \ell_p-Spread and Restricted Isometry Properties of Sparse Random Matrices | 2021-08-30 | Paper |
| scientific article; zbMATH DE number 7378653 (Why is no real title available?) | 2021-08-04 | Paper |
Polar codes with exponentially small error at finite block length
(available as arXiv preprint) | 2021-08-04 | Paper |
Locality via partially lifted codes
(available as arXiv preprint) | 2021-07-28 | Paper |
Sum-of-squares certificates for maxima of random tensors on the sphere
(available as arXiv preprint) | 2021-07-28 | Paper |
| Efficiently decodable codes for the binary deletion channel | 2021-07-28 | Paper |
| Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph | 2021-07-28 | Paper |
| The quest for strong inapproximability results with perfect completeness | 2021-07-28 | Paper |
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Optimally resilient codes for list-decoding from insertions and deletions
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
SIAM Journal on Computing | 2020-12-04 | Paper |
Maximally Recoverable LRCs: A Field Size Lower Bound and Constructions for Few Heavy Parities
IEEE Transactions on Information Theory | 2020-12-04 | Paper |
Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields
IEEE Transactions on Information Theory | 2020-12-04 | Paper |
ϵ-MSR Codes: Contacting Fewer Code Blocks for Exact Repair
IEEE Transactions on Information Theory | 2020-12-04 | Paper |
| Hardness of rainbow coloring hypergraphs | 2020-11-25 | Paper |
Coding Against Deletions in Oblivious and Online Models
IEEE Transactions on Information Theory | 2020-09-29 | Paper |
| scientific article; zbMATH DE number 7250144 (Why is no real title available?) | 2020-09-22 | Paper |
| Linear Shannon Capacity of Cayley Graphs | 2020-09-11 | Paper |
Sharp threshold rates for random codes
(available as arXiv preprint) | 2020-09-09 | Paper |
| Subspace designs based on algebraic function fields | 2020-05-27 | Paper |
Rainbow coloring hardness via low sensitivity polymorphisms
SIAM Journal on Discrete Mathematics | 2020-02-26 | Paper |
Bridging between 0/1 and linear programming via random walks
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
CSPs with global modular constraints: algorithms and hardness via polynomial representations
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
An exponential lower bound on the sub-packetization of MSR codes
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel
IEEE Transactions on Information Theory | 2020-01-28 | Paper |
Maximally recoverable LRCs: a field size lower bound and constructions for few heavy parities
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
An algorithmic blend of LPs and ring equations for promise CSPs
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Approximability of \(p\rightarrow q\) matrix norms: generalized Krivine rounding and hypercontractive hardness
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 |
How Long Can Optimal Locally Repairable Codes Be?
IEEE Transactions on Information Theory | 2019-07-19 | Paper |
Polynomial Time Decodable Codes for the Binary Deletion Channel
IEEE Transactions on Information Theory | 2019-07-19 | Paper |
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets (extended abstract)
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Approximating non-uniform sparsest cut via generalized spectra
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Restricted isometry of Fourier matrices and list decodability of random linear codes
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
(available as arXiv preprint) | 2019-05-10 | Paper |
| Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph | 2019-05-10 | Paper |
Optimal column-based low-rank matrix reconstruction
(available as arXiv preprint) | 2019-05-10 | Paper |
| Optimal column-based low-rank matrix reconstruction | 2019-05-10 | Paper |
| scientific article; zbMATH DE number 7053310 (Why is no real title available?) | 2019-05-10 | Paper |
Strong inapproximability results on balanced rainbow-colorable hypergraphs
Combinatorica | 2019-02-01 | Paper |
Guessing secrets efficiently via list decoding
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Bypassing UGC from some optimal geometric inapproximability results
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Subspace designs based on algebraic function fields
Transactions of the American Mathematical Society | 2018-10-18 | Paper |
Subspace designs based on algebraic function fields
Transactions of the American Mathematical Society | 2018-10-18 | Paper |
Polar Codes with exponentially small error at finite block length
(available as arXiv preprint) | 2018-10-09 | Paper |
Algorithmic Polarization for Hidden Markov Models
(available as arXiv preprint) | 2018-10-03 | Paper |
MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth
IEEE Transactions on Information Theory | 2018-09-19 | Paper |
Efficient low-redundancy codes for correcting multiple deletions
IEEE Transactions on Information Theory | 2018-09-14 | Paper |
Secret Sharing with Binary Shares
(available as arXiv preprint) | 2018-08-08 | Paper |
MDS code constructions with small sub-packetization and near-optimal repair bandwidth
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
An improved bound on the fraction of correctable deletions
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Nearly optimal NP-hardness of unique coverage
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Efficient low-redundancy codes for correcting multiple deletions
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 |
| Approximating Operator Norms via Generalized Krivine Rounding | 2018-04-10 | Paper |
| Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy | 2018-03-15 | Paper |
| Coding against deletions in oblivious and online models | 2018-03-15 | Paper |
Coding against deletions in oblivious and online models
(available as arXiv preprint) | 2018-03-15 | Paper |
An entropy sumset inequality and polynomially fast convergence to Shannon capacity over all alphabets
(available as arXiv preprint) | 2018-01-24 | Paper |
Repairing Reed-Solomon Codes
IEEE Transactions on Information Theory | 2017-11-10 | Paper |
Towards a characterization of approximation resistance for symmetric CSPs
Theory of Computing | 2017-10-11 | Paper |
| New hardness results for graph and hypergraph colorings | 2017-10-10 | Paper |
| Tight bounds for communication-assisted agreement distillation | 2017-10-10 | Paper |
(2+)-Sat is NP-hard
SIAM Journal on Computing | 2017-10-06 | 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 |
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Repairing Reed-solomon codes
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
| The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number | 2017-09-29 | Paper |
| scientific article; zbMATH DE number 6783493 (Why is no real title available?) | 2017-09-29 | Paper |
Efficiently List-Decodable Punctured Reed-Muller Codes
IEEE Transactions on Information Theory | 2017-09-21 | Paper |
Dimension Expanders via Rank Condensers
(available as arXiv preprint) | 2017-08-31 | Paper |
Inapproximability of \(H\)-transversal/packing
(available as arXiv preprint) | 2017-08-31 | Paper |
Approximate hypergraph coloring under low-discrepancy and related promises
(available as arXiv preprint) | 2017-08-31 | Paper |
| Towards a characterization of approximation resistance for symmetric CSPs | 2017-08-31 | Paper |
| Deletion codes in the high-noise and high-rate regimes | 2017-08-31 | Paper |
Explicit subspace designs
Combinatorica | 2017-08-25 | Paper |
Inapproximability of \(H\)-transversal/packing
SIAM Journal on Discrete Mathematics | 2017-08-14 | Paper |
Better Binary List Decodable Codes Via Multilevel Concatenation
IEEE Transactions on Information Theory | 2017-08-08 | Paper |
Optimal rate list decoding over bounded alphabets using algebraic-geometric codes
(available as arXiv preprint) | 2017-08-03 | Paper |
A Lower Bound on List Size for List Decoding
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
On the List-Decodability of Random Linear Codes
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
Deletion Codes in the High-Noise and High-Rate Regimes
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
Soft Decoding, Dual BCH Codes, and Better List-Decodable $\varepsilon$-Biased Codes
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
The Existence of Concatenated Codes List-Decodable up to the Hamming Bound
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
Nearly optimal NP-hardness of unique coverage
SIAM Journal on Computing | 2017-06-28 | Paper |
Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
IEEE Transactions on Information Theory | 2017-06-08 | Paper |
Complexity of approximating CSP with balance / hard constraints
Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
Capacity of non-malleable codes
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 |
Combinatorial Limitations of Average-Radius List-Decoding
IEEE Transactions on Information Theory | 2017-05-16 | Paper |
An Improved Bound on the Fraction of Correctable Deletions
IEEE Transactions on Information Theory | 2017-05-02 | Paper |
Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs
IEEE Transactions on Information Theory | 2017-04-28 | Paper |
Capacity of non-malleable codes
IEEE Transactions on Information Theory | 2017-04-28 | Paper |
Polar Codes: Speed of Polarization and Polynomial Gap to Capacity
IEEE Transactions on Information Theory | 2017-04-28 | Paper |
| Evading subspaces over large fields and explicit list-decodable rank-metric codes | 2017-03-22 | Paper |
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
SIAM Journal on Computing | 2017-03-10 | Paper |
Non-malleable coding against bit-wise and split-state tampering
Journal of Cryptology | 2017-03-02 | Paper |
Superlinear lower bounds for multipass graph processing
Algorithmica | 2016-11-29 | Paper |
List decoding subspace codes from insertions and deletions
Proceedings of the 3rd Innovations in Theoretical Computer Science Conference | 2016-10-07 | Paper |
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Complexity of approximating CSP with balance/hard constraints
Theory of Computing Systems | 2016-09-21 | Paper |
Simple proof of hardness of feedback vertex set
Theory of Computing | 2016-08-22 | Paper |
A natural family of optimization problems with arbitrarily small approximation thresholds
Information Processing Letters | 2016-06-09 | Paper |
Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs
SIAM Journal on Discrete Mathematics | 2015-11-27 | Paper |
PCPs via the low-degree long code and hardness for constrained hypergraph coloring
Israel Journal of Mathematics | 2015-11-16 | Paper |
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
Journal of the ACM | 2015-11-11 | Paper |
Hardness of solving sparse overdetermined linear systems: a 3-query PCP over integers
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
| Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates | 2015-08-03 | Paper |
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Constant factor Lasserre integrality gaps for graph partitioning problems
SIAM Journal on Optimization | 2015-04-08 | Paper |
MaxMin allocation via degree lower-bounded arborescences
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Artin automorphisms, cyclotomic function fields, and folded list-decodable codes
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
List decoding tensor products and interleaved codes
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Explicit capacity-achieving list-decodable codes
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Optimal rate algebraic list decoding using narrow ray class fields
Journal of Combinatorial Theory. Series A | 2014-11-19 | Paper |
| On profit-maximizing envy-free pricing | 2014-10-13 | Paper |
| Maximum-likelihood decoding of Reed-Solomon codes is NP-hard | 2014-10-13 | Paper |
Improved inapproximability results for maximum k-colorable subgraph
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 |
Query strategies for priced information (extended abstract)
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
On the list-decodability of random linear codes
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Agnostic learning of monomials by halfspaces is hard
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Folded codes from function field towers and improved optimal rate list decoding
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Non-malleable coding against bit-wise and split-state tampering
Lecture Notes in Computer Science | 2014-02-18 | Paper |
Restricted isometry of Fourier matrices and list decodability of random linear codes
SIAM Journal on Computing | 2014-02-04 | Paper |
Restricted isometry of Fourier matrices and list decodability of random linear codes
SIAM Journal on Computing | 2014-02-04 | Paper |
Combinatorial Limitations of Average-Radius List Decoding
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Agnostic learning of monomials by halfspaces is hard
SIAM Journal on Computing | 2013-03-19 | Paper |
Approximating Bounded Occurrence Ordering CSPs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set
Theory of Computing | 2012-09-27 | Paper |
The query complexity of estimating weighted averages
Acta Informatica | 2012-03-23 | Paper |
List decoding tensor products and interleaved codes
SIAM Journal on Computing | 2012-02-11 | Paper |
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
Combinatorica | 2011-12-19 | Paper |
| Bridging Shannon and Hamming: list error-correction with optimal rate | 2011-11-11 | Paper |
Beating the random ordering is hard: every ordering CSP is approximation resistant
SIAM Journal on Computing | 2011-10-18 | Paper |
Optimal Rate List Decoding via Derivative Codes
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Correlation clustering with a fixed number of clusters
Theory of Computing | 2011-05-24 | Paper |
Locally Testable Codes Require Redundant Testers
SIAM Journal on Computing | 2011-04-04 | Paper |
Hardness amplification within NP against deterministic algorithms
Journal of Computer and System Sciences | 2011-01-18 | Paper |
On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
Automata, Languages and Programming | 2010-09-07 | Paper |
SDP gaps for 2-to-1 and other Label-Cover variants
Automata, Languages and Programming | 2010-09-07 | Paper |
A new multilayered {PCP} and the hardness of hypergraph vertex cover
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Correlation clustering with a fixed number of clusters
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Limits to list decoding Reed-Solomon codes
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Linear time encodable and list decodable codes
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Better extractors for better codes?
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Almost Euclidean subspaces of \ell₁N via expander codes
(available as arXiv preprint) | 2010-08-06 | Paper |
| scientific article; zbMATH DE number 5764881 (Why is no real title available?) | 2010-08-06 | Paper |
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Limits to list decodability of linear codes
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate
Algebra & Number Theory | 2010-07-23 | Paper |
Hardness of learning halfspaces with noise
SIAM Journal on Computing | 2010-04-29 | Paper |
Hardness amplification via space-efficient direct products
Computational Complexity | 2010-03-15 | Paper |
Improved Inapproximability Results for Maximum k-Colorable Subgraph
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Iterative Decoding of Low-Density Parity Check Codes (A Survey)
(available as arXiv preprint) | 2009-09-19 | Paper |
List Decoding of Binary Codes–A Brief Survey of Some Recent Results
Lecture Notes in Computer Science | 2009-07-23 | Paper |
Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
IEEE Transactions on Information Theory | 2009-02-24 | Paper |
Better Binary List-Decodable Codes Via Multilevel Concatenation
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
| scientific article; zbMATH DE number 5485449 (Why is no real title available?) | 2009-01-05 | Paper |
| A 3-query PCP over integers | 2009-01-05 | Paper |
List decoding from erasures: bounds and code constructions
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Limits to List Decoding Reed–Solomon Codes
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Euclidean Sections of $\ell_1^N$ with Sublinear Randomness and Error-Correction over the Reals
Lecture Notes in Computer Science | 2008-11-27 | Paper |
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
Lecture Notes in Computer Science | 2008-11-27 | Paper |
Hardness Amplification Via Space-Efficient Direct Products
LATIN 2006: Theoretical Informatics | 2008-09-18 | Paper |
Algorithms for Modular Counting of Roots of Multivariate Polynomials
LATIN 2006: Theoretical Informatics | 2008-09-18 | Paper |
Algorithmic Results in List Decoding
Foundations and Trends® in Theoretical Computer Science | 2008-09-01 | Paper |
On 2-Query Codeword Testing with Near-Perfect Completeness
Algorithms and Computation | 2008-04-24 | Paper |
Algorithms for modular counting of roots of multivariate polynomials
Algorithmica | 2008-04-23 | Paper |
List Decoding and Pseudorandom Constructions
Applied Algebra, Algebraic Algorithms and Error-Correcting Codes | 2008-04-17 | Paper |
Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets
Mathematics of Computation | 2007-11-30 | Paper |
Algorithmic Results in List Decoding
Foundations and Trends® in Theoretical Computer Science | 2007-03-07 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
The complexity of the covering radius problem
Computational Complexity | 2006-02-07 | Paper |
Clustering with qualitative information
Journal of Computer and System Sciences | 2005-10-10 | Paper |
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
SIAM Journal on Computing | 2005-09-16 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition
Lecture Notes in Computer Science | 2005-06-13 | Paper |
Constructions of codes from number fields
IEEE Transactions on Information Theory | 2005-05-31 | Paper |
Combinatorial bounds for list decoding
IEEE Transactions on Information Theory | 2005-05-11 | Paper |
On the Hardness of 4-Coloring a 3-Colorable Graph
SIAM Journal on Discrete Mathematics | 2005-02-28 | Paper |
Is constraint satisfaction over two variables always easy?
Random Structures & Algorithms | 2005-01-12 | Paper |
| scientific article; zbMATH DE number 2119669 (Why is no real title available?) | 2004-11-29 | Paper |
Inapproximability results for set splitting and satisfiability problems with no mixed clauses
Algorithmica | 2004-09-22 | Paper |
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
Journal of Computer and System Sciences | 2004-08-19 | Paper |
| scientific article; zbMATH DE number 2081105 (Why is no real title available?) | 2004-08-04 | Paper |
| scientific article; zbMATH DE number 2081130 (Why is no real title available?) | 2004-08-04 | Paper |
| scientific article; zbMATH DE number 2079382 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2079408 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2019637 (Why is no real title available?) | 2003-12-17 | Paper |
Hardness of Approximate Hypergraph Coloring
SIAM Journal on Computing | 2002-09-29 | Paper |
Query strategies for priced information
Journal of Computer and System Sciences | 2002-09-12 | Paper |
On representations of algebraic-geometry codes
IEEE Transactions on Information Theory | 2002-08-04 | Paper |
The \(K_r\)-packing problem
Computing | 2002-01-24 | Paper |
| scientific article; zbMATH DE number 1670663 (Why is no real title available?) | 2001-11-11 | Paper |
| scientific article; zbMATH DE number 1670538 (Why is no real title available?) | 2001-11-11 | Paper |
Algorithmic aspects of clique-transversal and clique-independent sets
Discrete Applied Mathematics | 2000-11-30 | Paper |
Improved decoding of Reed-Solomon and algebraic-geometry codes
IEEE Transactions on Information Theory | 2000-09-07 | Paper |
| scientific article; zbMATH DE number 1305507 (Why is no real title available?) | 2000-06-13 | Paper |
Enumerative aspects of certain subclasses of perfect graphs
Discrete Mathematics | 2000-04-26 | Paper |
Maximum cut on line and total graphs
Discrete Applied Mathematics | 1999-11-23 | Paper |
| scientific article; zbMATH DE number 1262785 (Why is no real title available?) | 1999-08-17 | Paper |
Explicit optimal-length locally repairable codes of distance 5
(available as arXiv preprint) | N/A | Paper |
Randomly punctured Reed--Solomon codes achieve list-decoding capacity over linear-sized fields
(available as arXiv preprint) | N/A | Paper |
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
(available as arXiv preprint) | N/A | Paper |
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
(available as arXiv preprint) | N/A | Paper |
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
(available as arXiv preprint) | N/A | Paper |
