| No. |
Title |
Author |
Year |
| 1 |
Beating Fredman-Komlós for Perfect k-Hashing |
Guruswami, Venkatesan et al. |
2019 |
| 2 |
Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields |
Guruswami, Venkatesan et al. |
2019 |
| 3 |
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms |
Guruswami, Venkatesan et al. |
2019 |
| 4 |
Streaming Hardness of Unique Games |
Guruswami, Venkatesan et al. |
2019 |
| 5 |
Algorithmic Polarization for Hidden Markov Models |
Guruswami, Venkatesan et al. |
2018 |
| 6 |
Hardness of Rainbow Coloring Hypergraphs |
Guruswami, Venkatesan et al. |
2018 |
| 7 |
How Long Can Optimal Locally Repairable Codes Be? |
Guruswami, Venkatesan et al. |
2018 |
| 8 |
Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs |
Guruswami, Venkatesan et al. |
2018 |
| 9 |
Polar Codes with Exponentially Small Error at Finite Block Length |
Blasiok, Jaroslaw et al. |
2018 |
| 10 |
Secret Sharing with Binary Shares |
Lin, Fuchun et al. |
2018 |
| 11 |
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231) |
Grohe, Martin et al. |
2018 |
| 12 |
Efficiently Decodable Codes for the Binary Deletion Channel |
Guruswami, Venkatesan et al. |
2017 |
| 13 |
Locality via Partially Lifted Codes |
Frank-Fischer, S. Luna et al. |
2017 |
| 14 |
Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph |
Guruswami, Venkatesan et al. |
2017 |
| 15 |
Subspace Designs Based on Algebraic Function Fields |
Guruswami, Venkatesan et al. |
2017 |
| 16 |
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere |
Bhattiprolu, Vijay et al. |
2017 |
| 17 |
The Quest for Strong Inapproximability Results with Perfect Completeness |
Brakensiek, Joshua et al. |
2017 |
| 18 |
New Hardness Results for Graph and Hypergraph Colorings |
Brakensiek, Joshua et al. |
2016 |
| 19 |
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301) |
Bulatov, Andrei A. et al. |
2016 |
| 20 |
Tight Bounds for Communication-Assisted Agreement Distillation |
Guruswami, Venkatesan et al. |
2016 |
| 21 |
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets |
Guruswami, Venkatesan et al. |
2015 |
| 22 |
Approximate Hypergraph Coloring under Low-discrepancy and Related Promises |
Bhattiprolu, Vijay V. S. P. et al. |
2015 |
| 23 |
Deletion Codes in the High-noise and High-rate Regimes |
Guruswami, Venkatesan et al. |
2015 |
| 24 |
Dimension Expanders via Rank Condensers |
Forbes, Michael A. et al. |
2015 |
| 25 |
Inapproximability of H-Transversal/Packing |
Guruswami, Venkatesan et al. |
2015 |
| 26 |
Towards a Characterization of Approximation Resistance for Symmetric CSPs |
Guruswami, Venkatesan et al. |
2015 |
| 27 |
Evading Subspaces Over Large Fields and Explicit List-decodable Rank-metric Codes |
Guruswami, Venkatesan et al. |
2014 |
| 28 |
Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk) |
Guruswami, Venkatesan |
2013 |
