| Publication | Date of Publication | Type |
|---|
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 |
| Density Frankl-Rödl on the sphere | 2026-09-11 | Paper |
| New constructions of pseudorandom codes | 2026-09-11 | Paper |
Hardness of learning Boolean functions from label proportions
ACM Transactions on Computation Theory | 2026-08-04 | Paper |
| 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 |
| Explicit subspace designs | 2025-05-20 | 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 |
| 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 |
| Revisiting alphabet reduction in Dinur’s PCP. | 2023-10-31 | Paper |
| scientific article; zbMATH DE number 7758311 (Why is no real title available?) | 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 |
scientific article; zbMATH DE number 7650072 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
| Rainbow Coloring Hardness via Low Sensitivity Polymorphisms | 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 |
| Constructions of maximally recoverable local reconstruction codes via function fields | 2022-07-21 | Paper |
Beating Fredman-Komlós for Perfect k-Hashing.
(available as arXiv preprint) | 2022-07-21 | Paper |
Algorithmic polarization for hidden Markov models
(available as arXiv preprint) | 2022-07-18 | Paper |
Secret sharing with binary shares
(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 |
Threshold Rates for Properties of Random Codes
IEEE Transactions on Information Theory | 2022-02-17 | Paper |
Bounds for List-Decoding and List-Recovery of Random Linear 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 |
An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes
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 |
Polar codes with exponentially small error at finite block length
(available as arXiv preprint) | 2021-08-04 | Paper |
| scientific article; zbMATH DE number 7378653 (Why is no real title available?) | 2021-08-04 | Paper |
