Venkatesan Guruswami

612 papers A* 111A 42B 23Journal 389Unranked 42

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case. SODA Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan
2026	J	`jnl`	Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\boldsymbol{\sqrt {n}}$ Dimension Threshold. SIAM J. Comput. Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra
2026	J	`jnl`	Classification of Non-redundancy of Boolean Predicates of Arity 4. CoRR Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
2026	J	`jnl`	Maximal Recoverability: A Nexus of Coding Theory. CoRR Joshua Brakensiek, Venkatesan Guruswami
2026	A*	`conf`	New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs. SODA Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivný
2026	J	`jnl`	New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs. CoRR Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivný
2025	J	`jnl`	A Deterministic Construction of a Large Distance Code From the Wozencraft Ensemble. IEEE Trans. Inf. Theory Venkatesan Guruswami, Shilun Li
2025	J	`jnl`	A Locality-Based Lens for Coded Computation. IEEE Trans. Inf. Theory Michael Rudow, K. V. Rashmi, Venkatesan Guruswami
2025	J	`jnl`	AG Codes Have No List-Decoding Friends: Approaching the Generalized Singleton Bound Requires Exponential Alphabets. IEEE Trans. Inf. Theory Omar Alrabiah, Venkatesan Guruswami, Ray Li
2025	A*	`conf`	Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. STOC Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
2025	J	`jnl`	Approximate Hypergraph Vertex Cover and Generalized Tuza's Conjecture. SIAM J. Discret. Math. Venkatesan Guruswami, Sai Sandeep
2025	A*	`conf`	Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates. STOC Louis Golowich, Venkatesan Guruswami
2025	J	`jnl`	Binary Error-Correcting Codes With Minimal Noiseless Feedback. IEEE Trans. Inf. Theory Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang
2025	J	`jnl`	Block Length Gain for Nanopore Channels. CoRR Yu-Ting Lin, Hsin-Po Wang, Venkatesan Guruswami
2025	J	`jnl`	Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case. CoRR Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan
2025	A	`conf`	Density Frankl-Rödl on the Sphere. APPROX/RANDOM Venkatesan Guruswami, Shilun Li
2025	J	`jnl`	Geno-Weaving: A Framework for Low-Complexity Capacity-Achieving DNA Data Storage. IEEE J. Sel. Areas Inf. Theory Hsin-Po Wang, Venkatesan Guruswami
2025	A*	`conf`	Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices. FOCS Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, Xuandi Ren
2025	A*	`conf`	Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks. FOCS Louis Golowich, Venkatesan Guruswami
2025	J	`jnl`	Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks. CoRR Louis Golowich, Venkatesan Guruswami
2025	A	`conf`	New Constructions of Pseudorandom Codes. APPROX/RANDOM Surendra Ghentiyala, Venkatesan Guruswami
2025	J	`jnl`	New Spectral Algorithms for Refuting Smoothed k-SAT. Commun. ACM Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2025	J	`jnl`	Obituary for Luca Trevisan. Bull. EATCS Andrea Clementi, Venkatesan Guruswami, Kristin Kane, Alon Rosen, Nikhil Srivastava, Salil P. Vadhan, Riccardo Zecchina
2025	J	`jnl`	Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes. Electron. Colloquium Comput. Complex. Rohan Goyal, Venkatesan Guruswami
2025	J	`jnl`	Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes. IACR Cryptol. ePrint Arch. Rohan Goyal, Venkatesan Guruswami
2025	J	`jnl`	PCP-free APX-Hardness of Nearest Codeword and Minimum Distance. CoRR Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren
2025	J	`jnl`	PCP-free APX-Hardness of Nearest Codeword and Minimum Distance. Electron. Colloquium Comput. Complex. Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren
2025	J	`jnl`	PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs. CoRR Venkatesan Guruswami, Xuandi Ren, Kewen Wu
2025	J	`jnl`	Parameterized Inapproximability Hypothesis under ETH. J. ACM Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
2025	A	`conf`	Quantum LDPC Codes of Almost Linear Distance via Iterated Homological Products. CCC Louis Golowich, Venkatesan Guruswami
2025	A*	`conf`	Quantum Locally Recoverable Codes. SODA Louis Golowich, Venkatesan Guruswami
2025	J	`jnl`	Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness. ACM Trans. Comput. Theory Venkatesan Guruswami, Xin Lyu, Xiuhan Wang
2025	A*	`conf`	Redundancy Is All You Need. STOC Joshua Brakensiek, Venkatesan Guruswami
2025	J	`jnl`	SDPs and Robust Satisfiability of Promise CSP. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2025	J	`jnl`	Scheduling Problems with Constrained Rejections. CoRR Sami Davies, Venkatesan Guruswami, Xuandi Ren
2025	B	`conf`	Semirandom Planted Clique via 1-Norm Isometry Property. IPCO Venkatesan Guruswami, Hsin-Po Wang
2025	J	`jnl`	Semirandom Planted Clique via 1-norm Isometry Property. CoRR Venkatesan Guruswami, Hsin-Po Wang
2025	J	`jnl`	Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes. CoRR Rohan Goyal, Venkatesan Guruswami
2025	J	`jnl`	Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes. Electron. Colloquium Comput. Complex. Rohan Goyal, Venkatesan Guruswami
2025	J	`jnl`	The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 25211). Dagstuhl Reports Manuel Bodirsky, Venkatesan Guruswami, Dániel Marx, Stanislav Zivný, Zaneta Semanisinová
2025	J	`jnl`	The Richness of CSP Non-redundancy. CoRR Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen, Victor Lagerkvist, Magnus Wahlström
2025	J	`jnl`	Tight Bounds for Sparsifying Random CSPs. CoRR Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
2025	A	`conf`	Tight Bounds for Stream Decodable Error-Correcting Codes. CCC Meghal Gupta, Venkatesan Guruswami, Mihir Singhal
2024	A	`ed.`	15th Innovations in Theoretical Computer Science Conference, ITCS 2024, Berkeley, CA, USA, January 30 - February 2, 2024 ITCS Venkatesan Guruswami
2024	A*	`conf`	AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. SODA Omar Alrabiah, Venkatesan Guruswami, Ray Li
2024	J	`jnl`	Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. CoRR Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
2024	J	`jnl`	Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
2024	J	`jnl`	Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates. CoRR Louis Golowich, Venkatesan Guruswami
2024	A	`conf`	Baby PIH: Parameterized Inapproximability of Min CSP. CCC Venkatesan Guruswami, Xuandi Ren, Sai Sandeep
2024	A	`conf`	Capacity-Achieving Gray Codes. APPROX/RANDOM Venkatesan Guruswami, Hsin-Po Wang
2024	J	`jnl`	Capacity-Achieving Gray Codes. CoRR Venkatesan Guruswami, Hsin-Po Wang
2024	A*	`conf`	Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold. FOCS Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra
2024	J	`jnl`	Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold. CoRR Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra
2024	A*	`conf`	Decoding Quasi-Cyclic Quantum LDPC Codes. FOCS Louis Golowich, Venkatesan Guruswami
2024	J	`jnl`	Decoding Quasi-Cyclic Quantum LDPC Codes. CoRR Louis Golowich, Venkatesan Guruswami
2024	J	`jnl`	Exponential Time Approximation for Coloring 3-Colorable Graphs. CoRR Venkatesan Guruswami, Rhea Jain
2024	J	`jnl`	Geno-Weaving: Low-Complexity Capacity-Achieving DNA Storage. CoRR Hsin-Po Wang, Venkatesan Guruswami
2024	J	`jnl`	Hardness of Learning Boolean Functions from Label Proportions. CoRR Venkatesan Guruswami, Rishi Saket
2024	J	`jnl`	How Many Matrices Should I Prepare To Polarize Channels Optimally Fast? CoRR Hsin-Po Wang, Venkatesan Guruswami
2024	B	`conf`	Isolate and then Identify: Rethinking Adaptive Group Testing. ISIT Hsin-Po Wang, Venkatesan Guruswami
2024	J	`jnl`	Isolate and then Identify: Rethinking Adaptive Group Testing. CoRR Hsin-Po Wang, Venkatesan Guruswami
2024	A*	`conf`	Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. FOCS Omar Alrabiah, Venkatesan Guruswami
2024	J	`jnl`	Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. CoRR Omar Alrabiah, Venkatesan Guruswami
2024	J	`jnl`	Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. Electron. Colloquium Comput. Complex. Omar Alrabiah, Venkatesan Guruswami
2024	J	`jnl`	New constructions of pseudorandom codes. CoRR Surendra Ghentiyala, Venkatesan Guruswami
2024	J	`jnl`	New constructions of pseudorandom codes. IACR Cryptol. ePrint Arch. Surendra Ghentiyala, Venkatesan Guruswami
2024	A	`conf`	Outlier Robust Multivariate Polynomial Regression. ESA Vipul Arora, Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, Esty Kelman
2024	J	`jnl`	Outlier Robust Multivariate Polynomial Regression. CoRR Vipul Arora, Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, Esty Kelman
2024	A*	`conf`	Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis. STOC Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
2024	J	`jnl`	Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ${\ell_{{p}}}$ Norms. SIAM J. Comput. Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro
2024	J	`jnl`	Quantum LDPC Codes of Almost Linear Distance via Homological Products. CoRR Louis Golowich, Venkatesan Guruswami
2024	J	`jnl`	Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett and Cheraghchi-Nakos's Nonadaptive Splitting with Explicit Scalars. CoRR Hsin-Po Wang, Ryan Gabrys, Venkatesan Guruswami
2024	A*	`conf`	Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields. STOC Omar Alrabiah, Venkatesan Guruswami, Ray Li
2024	J	`jnl`	Redundancy Is All You Need. CoRR Joshua Brakensiek, Venkatesan Guruswami
2024	B	`conf`	Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically. ISIT Hsin-Po Wang, Venkatesan Guruswami
2024	J	`jnl`	Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically. CoRR Hsin-Po Wang, Venkatesan Guruswami
2024	J	`jnl`	Tight bounds for stream decodable error-correcting codes. CoRR Meghal Gupta, Venkatesan Guruswami, Mihir Singhal
2023	A	`conf`	A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. APPROX/RANDOM Venkatesan Guruswami, Shilun Li
2023	J	`jnl`	A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. CoRR Venkatesan Guruswami, Shilun Li
2023	A*	`conf`	A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. STOC Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2023	J	`jnl`	A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. CoRR Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2023	J	`jnl`	AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. CoRR Omar Alrabiah, Venkatesan Guruswami, Ray Li
2023	J	`jnl`	AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. Electron. Colloquium Comput. Complex. Omar Alrabiah, Venkatesan Guruswami, Ray Li
2023	J	`jnl`	Baby PIH: Parameterized Inapproximability of Min CSP. CoRR Venkatesan Guruswami, Xuandi Ren, Sai Sandeep
2023	J	`jnl`	Baby PIH: Parameterized Inapproximability of Min CSP. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Xuandi Ren, Sai Sandeep
2023	J	`jnl`	Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. IEEE Trans. Inf. Theory Ryan Gabrys, Venkatesan Guruswami, João Ribeiro, Ke Wu
2023	A*	`conf`	Binary Error-Correcting Codes with Minimal Noiseless Feedback. STOC Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang
2023	J	`jnl`	Conditional Dichotomy of Boolean Ordered Promise CSPs. TheoretiCS Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2023	A*	`conf`	Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. FOCS Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar
2023	J	`jnl`	Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. CoRR Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar
2023	J	`jnl`	Efficient Linear and Affine Codes for Correcting Insertions/Deletions. SIAM J. Discret. Math. Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
2023	—	`conf`	Hardness of Learning Boolean Functions from Label Proportions. FSTTCS Venkatesan Guruswami, Rishi Saket
2023	B	`conf`	How Many Matrices Should I Prepare To Polarize Channels Optimally Fast? ISIT Hsin-Po Wang, Venkatesan Guruswami
2023	J	`jnl`	Improved rate-distance trade-offs for quantum codes with restricted connectivity. CoRR Nouédyn Baspin, Venkatesan Guruswami, Anirudh Krishna, Ray Li
2023	J	`jnl`	Inapproximability of Matrix p → q Norms. SIAM J. Comput. Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
2023	J	`jnl`	Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding. CoRR Venkatesan Guruswami, Hsin-Po Wang
2023	B	`conf`	On expanding the toolkit of locality-based coded computation to the coordinates of inputs. ISIT Michael Rudow, Venkatesan Guruswami, K. V. Rashmi
2023	J	`jnl`	Parameterized Inapproximability Hypothesis under ETH. CoRR Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
2023	J	`jnl`	Parameterized Inapproximability Hypothesis under ETH. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu
2023	A*	`conf`	Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ STOC Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro
2023	J	`jnl`	Quantum Locally Recoverable Codes. CoRR Louis Golowich, Venkatesan Guruswami
2023	J	`jnl`	Quantum Locally Recoverable Codes. Electron. Colloquium Comput. Complex. Louis Golowich, Venkatesan Guruswami
2023	B	`conf`	Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett's Nonadaptive Splitting with Explicit Scalars. ISIT Hsin-Po Wang, Ryan Gabrys, Venkatesan Guruswami
2023	J	`jnl`	Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields. CoRR Omar Alrabiah, Venkatesan Guruswami, Ray Li
2023	J	`jnl`	Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields. Electron. Colloquium Comput. Complex. Omar Alrabiah, Venkatesan Guruswami, Ray Li
2023	A*	`conf`	SDPs and Robust Satisfiability of Promise CSP. STOC Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2023	J	`jnl`	The Zero-Rate Threshold for Adversarial Bit-Deletions is Less Than 1/2. IEEE Trans. Inf. Theory Venkatesan Guruswami, Xiaoyu He, Ray Li
2022	—	`ed.`	42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, IIT Madras, Chennai, India, December 18-20, 2022 FSTTCS Anuj Dawar, Venkatesan Guruswami
2022	J	`jnl`	A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. Electron. Colloquium Comput. Complex. Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar
2022	A	`conf`	Accelerating Polarization via Alphabet Extension. APPROX/RANDOM Iwan M. Duursma, Ryan Gabrys, Venkatesan Guruswami, Ting-Chun Lin, Hsin-Po Wang
2022	J	`jnl`	Accelerating Polarization via Alphabet Extension. CoRR Iwan M. Duursma, Ryan Gabrys, Venkatesan Guruswami, Ting-Chun Lin, Hsin-Po Wang
2022	A*	`conf`	Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. STOC Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2022	A*	`conf`	Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture. SODA Venkatesan Guruswami, Sai Sandeep
2022	J	`jnl`	Arıkan Meets Shannon: Polar Codes With Near-Optimal Convergence to Channel Capacity. IEEE Trans. Inf. Theory Venkatesan Guruswami, Andrii Riazanov, Min Ye
2022	J	`jnl`	Beating Fredman-Komlós for perfect J. Comb. Theory A Venkatesan Guruswami, Andrii Riazanov
2022	A	`conf`	Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. APPROX/RANDOM Ryan Gabrys, Venkatesan Guruswami, João Ribeiro, Ke Wu
2022	J	`jnl`	Binary Error-Correcting Codes with Minimal Noiseless Feedback. CoRR Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang
2022	J	`jnl`	Bounds for List-Decoding and List-Recovery of Random Linear Codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters
2022	A	`conf`	Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. APPROX/RANDOM Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2022	J	`jnl`	Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. CoRR Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2022	J	`jnl`	CNF Satisfiability in a Subspace and Related Problems. Algorithmica Vikraman Arvind, Venkatesan Guruswami
2022	J	`jnl`	Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. SIAM J. Comput. Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
2022	J	`jnl`	General Strong Polarization. J. ACM Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
2022	J	`jnl`	Improved Maximally Recoverable LRCs Using Skew Polynomials. IEEE Trans. Inf. Theory Sivakanth Gopi, Venkatesan Guruswami
2022	J	`jnl`	Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes. J. ACM Venkatesan Guruswami, Chaoping Xing
2022	J	`jnl`	Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓ Electron. Colloquium Comput. Complex. Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro
2022	J	`jnl`	Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all 𝓁 CoRR Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro
2022	A*	`conf`	Punctured Low-Bias Codes Behave Like Random Linear Codes. FOCS Venkatesan Guruswami, Jonathan Mosheiff
2022	A	`conf`	Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness. APPROX/RANDOM Venkatesan Guruswami, Xin Lyu, Xiuhan Wang
2022	J	`jnl`	Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Xin Lyu, Xiuhan Wang
2022	J	`jnl`	SDPs and Robust Satisfiability of Promise CSP. CoRR Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2022	J	`jnl`	Sparsity and 𝓁 CoRR Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
2022	J	`jnl`	The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). Dagstuhl Reports Martin Grohe, Venkatesan Guruswami, Dániel Marx, Stanislav Zivný
2022	J	`jnl`	Threshold Rates for Properties of Random Codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters
2022	A	`conf`	ℓ CCC Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
2021	B	`conf`	A locality-based lens for coded computation. ISIT Michael Rudow, K. V. Rashmi, Venkatesan Guruswami
2021	J	`jnl`	Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random". CoRR Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2021	J	`jnl`	An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes. IEEE Trans. Inf. Theory Omar Alrabiah, Venkatesan Guruswami
2021	J	`jnl`	Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. CoRR Ryan Gabrys, Venkatesan Guruswami, João Ribeiro, Ke Wu
2021	B	`conf`	CNF Satisfiability in a Subspace and Related Problems. IPEC Vikraman Arvind, Venkatesan Guruswami
2021	J	`jnl`	CNF Satisfiability in a Subspace and Related Problems. CoRR Vikraman Arvind, Venkatesan Guruswami
2021	J	`jnl`	CNF Satisfiability in a Subspace and Related Problems. Electron. Colloquium Comput. Complex. Vikraman Arvind, Venkatesan Guruswami
2021	A*	`conf`	Conditional Dichotomy of Boolean Ordered Promise CSPs. ICALP Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2021	J	`jnl`	Conditional Dichotomy of Boolean Ordered Promise CSPs. CoRR Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2021	J	`jnl`	Conditional Dichotomy of Boolean Ordered Promise CSPs. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2021	A*	`conf`	Efficient Linear and Affine Codes for Correcting Insertions/Deletions. SODA Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
2021	J	`jnl`	Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound. IEEE Trans. Inf. Theory Venkatesan Guruswami, Johan Håstad
2021	A*	`conf`	Explicit two-deletion codes with redundancy matching the existential bound. SODA Venkatesan Guruswami, Johan Håstad
2021	J	`jnl`	Improved Maximally Recoverable LRCs using Skew Polynomials. Electron. Colloquium Comput. Complex. Sivakanth Gopi, Venkatesan Guruswami
2021	B	`conf`	Linear Programming Bounds for Almost-Balanced Binary Codes. ISIT Venkatesan Guruswami, Andrii Riazanov
2021	J	`jnl`	Linear Programming Bounds for Almost-Balanced Binary Codes. CoRR Venkatesan Guruswami, Andrii Riazanov
2021	B	`conf`	Linear Shannon Capacity of Cayley Graphs. ISIT Venkatesan Guruswami, Andrii Riazanov
2021	J	`jnl`	Lossless Dimension Expanders Via Linearized Polynomials and Subspace Designs. Comb. Venkatesan Guruswami, Nicolas Resch, Chaoping Xing
2021	J	`jnl`	Optimally Resilient Codes for List-Decoding From Insertions and Deletions. IEEE Trans. Inf. Theory Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
2021	J	`jnl`	Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. SIAM J. Comput. Joshua Brakensiek, Venkatesan Guruswami
2021	A	`conf`	Pseudobinomiality of the Sticky Random Walk. ITCS Venkatesan Guruswami, Vinayak M. Kumar
2021	J	`jnl`	Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity. CoRR Venkatesan Guruswami, Jonathan Mosheiff
2021	J	`jnl`	Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Jonathan Mosheiff
2021	J	`jnl`	Revisiting a Lower Bound on the Redundancy of Linear Batch Codes. Electron. Colloquium Comput. Complex. Omar Alrabiah, Venkatesan Guruswami
2021	A	`conf`	Sharp Threshold Rates for Random Codes. ITCS Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters
2021	A*	`conf`	Strongly refuting all semi-random Boolean CSPs. SODA Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari
2021	J	`jnl`	The Quest for Strong Inapproximability Results with Perfect Completeness. ACM Trans. Algorithms Joshua Brakensiek, Venkatesan Guruswami
2021	A*	`conf`	The zero-rate threshold for adversarial bit-deletions is less than 1/2. FOCS Venkatesan Guruswami, Xiaoyu He, Ray Li
2021	J	`jnl`	The zero-rate threshold for adversarial bit-deletions is less than 1/2. CoRR Venkatesan Guruswami, Xiaoyu He, Ray Li
2021	J	`jnl`	The zero-rate threshold for adversarial bit-deletions is less than 1/2. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Xiaoyu He, Ray Li
2021	—	`conf`	Visible Rank and Codes with Locality. APPROX-RANDOM Omar Alrabiah, Venkatesan Guruswami
2021	J	`jnl`	Visible Rank and Codes with Locality. CoRR Omar Alrabiah, Venkatesan Guruswami
2021	J	`jnl`	Visible Rank and Codes with Locality. Electron. Colloquium Comput. Complex. Omar Alrabiah, Venkatesan Guruswami
2021	J	`jnl`	𝓁 CoRR Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff
2020	J	`jnl`	A locality-based approach for coded computation. CoRR Michael Rudow, K. V. Rashmi, Venkatesan Guruswami
2020	J	`jnl`	An Algorithmic Study of the Hypergraph Turán Problem. CoRR Venkatesan Guruswami, Sai Sandeep
2020	J	`jnl`	An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel. IEEE Trans. Inf. Theory Marco Dalai, Venkatesan Guruswami, Jaikumar Radhakrishnan
2020	J	`jnl`	Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Sai Sandeep
2020	A*	`conf`	Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity. STOC Venkatesan Guruswami, Andrii Riazanov, Min Ye
2020	—	`conf`	Bounds for List-Decoding and List-Recovery of Random Linear Codes. APPROX-RANDOM Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters
2020	J	`jnl`	Bounds for list-decoding and list-recovery of random linear codes. CoRR Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters
2020	J	`jnl`	Coding Against Deletions in Oblivious and Online Models. IEEE Trans. Inf. Theory Venkatesan Guruswami, Ray Li
2020	J	`jnl`	Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields. IEEE Trans. Inf. Theory Venkatesan Guruswami, Lingfei Jin, Chaoping Xing
2020	J	`jnl`	Efficient Linear and Affine Codes for Correcting Insertions/Deletions. CoRR Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
2020	J	`jnl`	Explicit two-deletion codes with redundancy matching the existential bound. CoRR Venkatesan Guruswami, Johan Håstad
2020	J	`jnl`	Improved Maximally Recoverable LRCs using Skew Polynomials. CoRR Sivakanth Gopi, Venkatesan Guruswami
2020	A	`conf`	Leakage-Resilient Secret Sharing in Non-Compartmentalized Models. ITC Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang
2020	J	`jnl`	Linear Shannon Capacity of Cayley Graphs. CoRR Venkatesan Guruswami, Andrii Riazanov
2020	J	`jnl`	Maximally Recoverable LRCs: A Field Size Lower Bound and Constructions for Few Heavy Parities. IEEE Trans. Inf. Theory Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin
2020	J	`jnl`	Optimal rate list decoding over bounded alphabets using algebraic-geometric codes. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Chaoping Xing
2020	A*	`conf`	Optimally resilient codes for list-decoding from insertions and deletions. STOC Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
2020	J	`jnl`	Pseudobinomiality of the Sticky Random Walk. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Vinayak M. Kumar
2020	J	`jnl`	Rainbow Coloring Hardness via Low Sensitivity Polymorphisms. SIAM J. Discret. Math. Venkatesan Guruswami, Sai Sandeep
2020	—	`conf`	Revisiting Alphabet Reduction in Dinur's PCP. APPROX-RANDOM Venkatesan Guruswami, Jakub Oprsal, Sai Sandeep
2020	J	`jnl`	Sharp threshold rates for random codes. CoRR Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters
2020	J	`jnl`	Strongly refuting all semi-random Boolean CSPs. CoRR Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari
2020	A*	`conf`	Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. SODA Joshua Brakensiek, Venkatesan Guruswami
2020	J	`jnl`	The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný
2020	J	`jnl`	The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems. SIAM J. Comput. Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný
2020	A*	`conf`	d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors. ICALP Venkatesan Guruswami, Sai Sandeep
2020	J	`jnl`	ϵ-MSR Codes: Contacting Fewer Code Blocks for Exact Repair. IEEE Trans. Inf. Theory Venkatesan Guruswami, Satyanarayana V. Lokam, Sai Vikneshwar Mani Jayaraman
2019	J	`jnl`	$d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Sai Sandeep
2019	A	`conf`	Algorithmic Polarization for Hidden Markov Models. ITCS Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan
2019	A*	`conf`	An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. SODA Joshua Brakensiek, Venkatesan Guruswami
2019	J	`jnl`	An Exponential Lower Bound on the Sub-Packetization of MSR Codes. CoRR Omar Alrabiah, Venkatesan Guruswami
2019	J	`jnl`	An Exponential Lower Bound on the Sub-Packetization of MSR Codes. Electron. Colloquium Comput. Complex. Omar Alrabiah, Venkatesan Guruswami
2019	A*	`conf`	An exponential lower bound on the sub-packetization of MSR codes. STOC Omar Alrabiah, Venkatesan Guruswami
2019	A*	`conf`	Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. SODA Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
2019	J	`jnl`	Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Andrii Riazanov, Min Ye
2019	J	`jnl`	Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity. CoRR Venkatesan Guruswami, Andrii Riazanov, Min Ye
2019	A*	`conf`	Beating Fredman-Komlós for Perfect k-Hashing. ICALP Venkatesan Guruswami, Andrii Riazanov
2019	J	`jnl`	Bridging between 0/1 and Linear Programming via Random Walks. CoRR Joshua Brakensiek, Venkatesan Guruswami
2019	J	`jnl`	Bridging between 0/1 and Linear Programming via Random Walks. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2019	A*	`conf`	Bridging between 0/1 and linear programming via random walks. STOC Joshua Brakensiek, Venkatesan Guruswami
2019	J	`jnl`	CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. CoRR Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
2019	J	`jnl`	CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
2019	A*	`conf`	CSPs with global modular constraints: algorithms and hardness via polynomial representations. STOC Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
2019	A*	`conf`	Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields. ICALP Venkatesan Guruswami, Lingfei Jin, Chaoping Xing
2019	J	`jnl`	How Long Can Optimal Locally Repairable Codes Be? IEEE Trans. Inf. Theory Venkatesan Guruswami, Chaoping Xing, Chen Yuan
2019	A*	`conf`	Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities. SODA Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin
2019	B	`conf`	Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization. ISIT Venkatesan Guruswami, Haotian Jiang
2019	J	`jnl`	Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization. CoRR Venkatesan Guruswami, Haotian Jiang
2019	J	`jnl`	Non-Malleable Secret Sharing against Affine Tampering. CoRR Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang
2019	J	`jnl`	Optimally Resilient Codes for List-Decoding from Insertions and Deletions. CoRR Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
2019	J	`jnl`	Optimally Resilient Codes for List-Decoding from Insertions and Deletions. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi
2019	J	`jnl`	Polynomial Time Decodable Codes for the Binary Deletion Channel. IEEE Trans. Inf. Theory Venkatesan Guruswami, Ray Li
2019	—	`conf`	Rainbow Coloring Hardness via Low Sensitivity Polymorphisms. APPROX-RANDOM Venkatesan Guruswami, Sai Sandeep
2019	J	`jnl`	Rainbow coloring hardness via low sensitivity polymorphisms. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Sai Sandeep
2019	J	`jnl`	Revisiting Alphabet Reduction in Dinur's PCP. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Jakub Oprsal, Sai Sandeep
2019	A	`conf`	Secret Sharing with Binary Shares. ITCS Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang
2019	—	`conf`	Streaming Hardness of Unique Games. APPROX-RANDOM Venkatesan Guruswami, Runzhou Tao
2019	J	`jnl`	Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. CoRR Joshua Brakensiek, Venkatesan Guruswami
2018	J	`jnl`	Algorithmic Polarization for Hidden Markov Models. CoRR Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan
2018	J	`jnl`	An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. CoRR Joshua Brakensiek, Venkatesan Guruswami
2018	J	`jnl`	Approximating Operator Norms via Generalized Krivine Rounding. CoRR Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
2018	J	`jnl`	Approximating Operator Norms via Generalized Krivine Rounding. Electron. Colloquium Comput. Complex. Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
2018	J	`jnl`	Beating Fredman-Komlós for perfect k-hashing. CoRR Venkatesan Guruswami, Andrii Riazanov
2018	J	`jnl`	Beating Fredman-Komlós for perfect k-hashing. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Andrii Riazanov
2018	A*	`conf`	Coding against deletions in oblivious and online models. SODA Venkatesan Guruswami, Ray Li
2018	J	`jnl`	Combining LPs and Ring Equations via Structured Polymorphisms. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2018	J	`jnl`	Constructions of maximally recoverable local reconstruction codes via function fields. CoRR Venkatesan Guruswami, Lingfei Jin, Chaoping Xing
2018	J	`jnl`	Efficient Low-Redundancy Codes for Correcting Multiple Deletions. IEEE Trans. Inf. Theory Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
2018	—	`conf`	Explicit optimal-length locally repairable codes of distance 5. Allerton Allison Beemer, Ryan Coatney, Venkatesan Guruswami, Hiram H. Lopez, Fernando Piñero
2018	J	`jnl`	Explicit optimal-length locally repairable codes of distance 5. CoRR Allison Beemer, Ryan Coatney, Venkatesan Guruswami, Hiram H. López, Fernando Piñero
2018	J	`jnl`	General Strong Polarization. CoRR Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
2018	J	`jnl`	General Strong Polarization. Electron. Colloquium Comput. Complex. Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
2018	A*	`conf`	General strong polarization. STOC Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan
2018	—	`conf`	How Long Can Optimal Locally Repairable Codes Be?. APPROX-RANDOM Venkatesan Guruswami, Chaoping Xing, Chen Yuan
2018	J	`jnl`	How long can optimal locally repairable codes be? CoRR Venkatesan Guruswami, Chaoping Xing, Chen Yuan
2018	J	`jnl`	Inapproximability of Matrix p→q Norms. CoRR Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
2018	J	`jnl`	Inapproximability of Matrix p→q Norms. Electron. Colloquium Comput. Complex. Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
2018	A	`conf`	Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs. CCC Venkatesan Guruswami, Nicolas Resch, Chaoping Xing
2018	J	`jnl`	Lossless dimension expanders via linearized polynomials and subspace designs. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Nicolas Resch, Chaoping Xing
2018	J	`jnl`	MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth. IEEE Trans. Inf. Theory Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko
2018	B	`conf`	On the List-Decodability of Random Linear Rank-Metric Codes. ISIT Venkatesan Guruswami, Nicolas Resch
2018	—	`conf`	Polar Codes with Exponentially Small Error at Finite Block Length. APPROX-RANDOM Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan
2018	J	`jnl`	Polar Codes with exponentially small error at finite block length. CoRR Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan
2018	A*	`conf`	Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy. SODA Joshua Brakensiek, Venkatesan Guruswami
2018	J	`jnl`	Secret Sharing with Binary Shares. CoRR Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang
2018	J	`jnl`	Secret Sharing with Binary Shares. IACR Cryptol. ePrint Arch. Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang
2018	J	`jnl`	Streaming Hardness of Unique Games. CoRR Venkatesan Guruswami, Runzhou Tao
2018	J	`jnl`	Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. Comb. Venkatesan Guruswami, Euiwoong Lee
2018	J	`jnl`	The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231). Dagstuhl Reports Martin Grohe, Venkatesan Guruswami, Stanislav Zivný
2018	J	`jnl`	ε-MSR Codes: Contacting Fewer Code Blocks for Exact Repair. CoRR Venkatesan Guruswami, Satyanarayana V. Lokam, Sai Vikneshwar Mani Jayaraman
2018	B	`conf`	∊-MSR Codes: Contacting Fewer Code Blocks for Exact Repair. ISIT Venkatesan Guruswami, Satyanarayana V. Lokam, Sai Vikneshwar Mani Jayaraman
2017	J	`jnl`	(2+ε)-Sat Is NP-hard. SIAM J. Comput. Per Austrin, Venkatesan Guruswami, Johan Håstad
2017	J	`jnl`	A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2017	J	`jnl`	An Improved Bound on the Fraction of Correctable Deletions. IEEE Trans. Inf. Theory Boris Bukh, Venkatesan Guruswami, Johan Håstad
2017	B	`conf`	An improved bound on the zero-error list-decoding capacity of the 4/3 channel. ISIT Marco Dalai, Venkatesan Guruswami, Jaikumar Radhakrishnan
2017	J	`jnl`	Communication With Imperfectly Shared Randomness. IEEE Trans. Inf. Theory Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
2017	J	`jnl`	Deletion Codes in the High-Noise and High-Rate Regimes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Carol Wang
2017	—	`conf`	Efficiently Decodable Codes for the Binary Deletion Channel. APPROX-RANDOM Venkatesan Guruswami, Ray Li
2017	J	`jnl`	Efficiently List-Decodable Punctured Reed-Muller Codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Lingfei Jin, Chaoping Xing
2017	J	`jnl`	Efficiently decodable codes for the binary deletion channel. CoRR Venkatesan Guruswami, Ray Li
2017	—	`conf`	Hardness of Rainbow Coloring Hypergraphs. FSTTCS Venkatesan Guruswami, Rishi Saket
2017	J	`jnl`	Hardness of Rainbow Coloring Hypergraphs. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Rishi Saket
2017	J	`jnl`	Inapproximability of H-Transversal/Packing. SIAM J. Discret. Math. Venkatesan Guruswami, Euiwoong Lee
2017	—	`conf`	Locality via Partially Lifted Codes. APPROX-RANDOM S. Luna Frank-Fischer, Venkatesan Guruswami, Mary Wootters
2017	J	`jnl`	Locality via Partially Lifted Codes. CoRR S. Luna Frank-Fischer, Venkatesan Guruswami, Mary Wootters
2017	A*	`conf`	MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth. SODA Venkatesan Guruswami, Ankit Singh Rawat
2017	J	`jnl`	MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth. CoRR Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko
2017	J	`jnl`	Nearly Optimal NP-Hardness of Unique Coverage. SIAM J. Comput. Venkatesan Guruswami, Euiwoong Lee
2017	J	`jnl`	Non-malleable Coding Against Bit-Wise and Split-State Tampering. J. Cryptol. Mahdi Cheraghchi, Venkatesan Guruswami
2017	J	`jnl`	On Maximally Recoverable Local Reconstruction Codes. CoRR Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin
2017	J	`jnl`	On Maximally Recoverable Local Reconstruction Codes. Electron. Colloquium Comput. Complex. Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin
2017	J	`jnl`	On the List-Decodability of Random Linear Rank-Metric Codes. CoRR Venkatesan Guruswami, Nicolas Resch
2017	J	`jnl`	Optimal rate list decoding over bounded alphabets using algebraic-geometric codes. CoRR Venkatesan Guruswami, Chaoping Xing
2017	J	`jnl`	Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. CoRR Joshua Brakensiek, Venkatesan Guruswami
2017	J	`jnl`	Repairing Reed-Solomon Codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Mary Wootters
2017	—	`conf`	Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. APPROX-RANDOM Venkatesan Guruswami, Ameya Velingker, Santhoshini Velusamy
2017	A*	`conf`	Subspace Designs Based on Algebraic Function Fields. ICALP Venkatesan Guruswami, Chaoping Xing, Chen Yuan
2017	J	`jnl`	Subspace Designs based on Algebraic Function Fields. CoRR Venkatesan Guruswami, Chaoping Xing, Chen Yuan
2017	J	`jnl`	Subspace Designs based on Algebraic Function Fields. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Chaoping Xing, Chen Yuan
2017	—	`conf`	Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. APPROX-RANDOM Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee
2017	J	`jnl`	Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes. SIAM J. Comput. Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma
2017	—	`conf`	The Quest for Strong Inapproximability Results with Perfect Completeness. APPROX-RANDOM Joshua Brakensiek, Venkatesan Guruswami
2017	J	`jnl`	The Quest for Strong Inapproximability Results with Perfect Completeness. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2017	J	`jnl`	Towards a Characterization of Approximation Resistance for Symmetric CSPs. Theory Comput. Venkatesan Guruswami, Euiwoong Lee
2017	A*	`conf`	Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. FOCS Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
2017	B	`conf`	∊-MSR codes with small sub-packetization. ISIT Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko
2016	A*	`conf`	An improved bound on the fraction of correctable deletions. SODA Boris Bukh, Venkatesan Guruswami
2016	J	`jnl`	Bypassing UGC from Some Optimal Geometric Inapproximability Results. ACM Trans. Algorithms Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
2016	J	`jnl`	Capacity of Non-Malleable Codes. IEEE Trans. Inf. Theory Mahdi Cheraghchi, Venkatesan Guruswami
2016	J	`jnl`	Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy. CoRR Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee
2016	J	`jnl`	Codes correcting deletions in oblivious and random models. CoRR Venkatesan Guruswami, Ray Li
2016	J	`jnl`	Complexity of Approximating CSP with Balance / Hard Constraints. Theory Comput. Syst. Venkatesan Guruswami, Euiwoong Lee
2016	—	`ch.`	Decoding Reed-Solomon Codes. Encyclopedia of Algorithms Venkatesan Guruswami
2016	A*	`conf`	Efficient Low-Redundancy Codes for Correcting Multiple Deletions. SODA Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
2016	B	`conf`	Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes. ISIT Venkatesan Guruswami, Ray Li
2016	J	`jnl`	Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes. CoRR Venkatesan Guruswami, Ray Li
2016	J	`jnl`	Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs. IEEE Trans. Inf. Theory Venkatesan Guruswami, Carol Wang, Chaoping Xing
2016	J	`jnl`	Explicit subspace designs. Comb. Venkatesan Guruswami, Swastik Kopparty
2016	J	`jnl`	Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. CoRR Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Euiwoong Lee, Venkatesan Guruswami, Madhur Tulsiani
2016	J	`jnl`	Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. Electron. Colloquium Comput. Complex. Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani
2016	A*	`conf`	Nearly Optimal NP-Hardness of Unique Coverage. SODA Venkatesan Guruswami, Euiwoong Lee
2016	A	`conf`	New Hardness Results for Graph and Hypergraph Colorings. CCC Joshua Brakensiek, Venkatesan Guruswami
2016	J	`jnl`	New MDS codes with small sub-packetization and near-optimal repair bandwidth. CoRR Venkatesan Guruswami, Ankit Singh Rawat
2016	J	`jnl`	New hardness results for graph and hypergraph colorings. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2016	J	`jnl`	Optimal Rate Code Constructions for Computationally Simple Channels. J. ACM Venkatesan Guruswami, Adam D. Smith
2016	J	`jnl`	Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2016	J	`jnl`	Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey). CoRR Venkatesan Guruswami
2016	A*	`conf`	Repairing Reed-solomon codes. STOC Venkatesan Guruswami, Mary Wootters
2016	A*	`conf`	Robust Fourier and Polynomial Curve Fitting. FOCS Venkatesan Guruswami, David Zuckerman
2016	J	`jnl`	Simple Proof of Hardness of Feedback Vertex Set. Theory Comput. Venkatesan Guruswami, Euiwoong Lee
2016	J	`jnl`	Superlinear Lower Bounds for Multipass Graph Processing. Algorithmica Venkatesan Guruswami, Krzysztof Onak
2016	A	`conf`	Tight Bounds for Communication-Assisted Agreement Distillation. CCC Venkatesan Guruswami, Jaikumar Radhakrishnan
2016	J	`jnl`	Tight bounds for communication assisted agreement distillation. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Jaikumar Radhakrishnan
2015	A	`conf`	An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. CCC Venkatesan Guruswami, Ameya Velingker
2015	J	`jnl`	An improved bound on the fraction of correctable deletions. CoRR Boris Bukh, Venkatesan Guruswami
2015	J	`jnl`	An improved bound on the fraction of correctable deletions. Electron. Colloquium Comput. Complex. Boris Bukh, Venkatesan Guruswami
2015	—	`conf`	Approximate Hypergraph Coloring under Low-discrepancy and Related Promises. APPROX-RANDOM Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee
2015	J	`jnl`	Approximate Hypergraph Coloring under Low-discrepancy and Related Promises. CoRR Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee
2015	A	`conf`	Communication with Imperfectly Shared Randomness. ITCS Clément Louis Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
2015	—	`conf`	Deletion Codes in the High-noise and High-rate Regimes. APPROX-RANDOM Venkatesan Guruswami, Carol Wang
2015	—	`conf`	Dimension Expanders via Rank Condensers. APPROX-RANDOM Michael A. Forbes, Venkatesan Guruswami
2015	J	`jnl`	Efficient Low-Redundancy Codes for Correcting Multiple Deletions. CoRR Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
2015	J	`jnl`	Efficient Low-Redundancy Codes for Correcting Multiple Deletions. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
2015	J	`jnl`	Efficient list decoding of punctured Reed-Muller codes. CoRR Venkatesan Guruswami, Lingfei Jin, Chaoping Xing
2015	A*	`ed.`	IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015 FOCS Venkatesan Guruswami
2015	J	`jnl`	Inapproximability of $H$-Transversal/Packing. CoRR Venkatesan Guruswami, Euiwoong Lee
2015	—	`conf`	Inapproximability of H-Transversal/Packing. APPROX-RANDOM Venkatesan Guruswami, Euiwoong Lee
2015	J	`jnl`	Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs. SIAM J. Discret. Math. Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket
2015	A*	`conf`	Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. SODA Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang
2015	J	`jnl`	Nearly Optimal NP-Hardness of Unique Coverage. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Euiwoong Lee
2015	J	`jnl`	Optimal rate algebraic list decoding using narrow ray class fields. J. Comb. Theory A Venkatesan Guruswami, Chaoping Xing
2015	J	`jnl`	Polar Codes: Speed of Polarization and Polynomial Gap to Capacity. IEEE Trans. Inf. Theory Venkatesan Guruswami, Patrick Xia
2015	J	`jnl`	Repairing Reed-Solomon Codes. CoRR Venkatesan Guruswami, Mary Wootters
2015	A*	`conf`	Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. SODA Venkatesan Guruswami, Euiwoong Lee
2015	J	`jnl`	The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). Dagstuhl Reports Andrei A. Bulatov, Venkatesan Guruswami, Andrei A. Krokhin, Dániel Marx
2015	—	`conf`	Towards a Characterization of Approximation Resistance for Symmetric CSPs. APPROX-RANDOM Venkatesan Guruswami, Euiwoong Lee
2015	J	`jnl`	Towards a Characterization of Approximation Resistance for Symmetric CSPs. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Euiwoong Lee
2014	A*	`conf`	(2 + epsilon)-Sat Is NP-Hard. FOCS Per Austrin, Johan Håstad, Venkatesan Guruswami
2014	J	`jnl`	An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. CoRR Venkatesan Guruswami, Ameya Velingker
2014	J	`jnl`	An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Ameya Velingker
2014	A	`conf`	Capacity of non-malleable codes. ITCS Mahdi Cheraghchi, Venkatesan Guruswami
2014	J	`jnl`	Combinatorial Limitations of Average-Radius List-Decoding. IEEE Trans. Inf. Theory Venkatesan Guruswami, Srivatsan Narayanan
2014	J	`jnl`	Communication with Imperfectly Shared Randomness. CoRR Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
2014	J	`jnl`	Communication with Imperfectly Shared Randomness. Electron. Colloquium Comput. Complex. Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
2014	A	`conf`	Complexity of approximating CSP with balance / hard constraints. ITCS Venkatesan Guruswami, Euiwoong Lee
2014	J	`jnl`	Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems. SIAM J. Optim. Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou
2014	J	`jnl`	Deletion codes in the high-noise and high-rate regimes. CoRR Venkatesan Guruswami, Carol Wang
2014	J	`jnl`	Dimension Expanders via Rank Condensers. CoRR Michael A. Forbes, Venkatesan Guruswami
2014	J	`jnl`	Dimension Expanders via Rank Condensers. Electron. Colloquium Comput. Complex. Michael A. Forbes, Venkatesan Guruswami
2014	—	`conf`	Evading Subspaces Over Large Fields and Explicit List-decodable Rank-metric Codes. APPROX-RANDOM Venkatesan Guruswami, Carol Wang
2014	A	`conf`	Hitting Sets for Low-Degree Polynomials with Optimal Density. CCC Venkatesan Guruswami, Chaoping Xing
2014	J	`jnl`	Inapproximability of Feedback Vertex Set for Bounded Length Cycles. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Euiwoong Lee
2014	J	`jnl`	Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang
2014	B	`conf`	Non-malleable Coding against Bit-Wise and Split-State Tampering. TCC Mahdi Cheraghchi, Venkatesan Guruswami
2014	A*	`conf`	Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. SODA Venkatesan Guruswami, Chaoping Xing
2014	J	`jnl`	Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Euiwoong Lee
2014	A*	`conf`	Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. STOC Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma
2013	J	`jnl`	(2+ε)-SAT is NP-hard. Electron. Colloquium Comput. Complex. Per Austrin, Venkatesan Guruswami, Johan Håstad
2013	A*	`conf`	Approximating Non-Uniform Sparsest Cut Via Generalized Spectra. SODA Venkatesan Guruswami, Ali Kemal Sinop
2013	J	`jnl`	Capacity of Non-Malleable Codes. CoRR Mahdi Cheraghchi, Venkatesan Guruswami
2013	J	`jnl`	Capacity of Non-Malleable Codes. Electron. Colloquium Comput. Complex. Mahdi Cheraghchi, Venkatesan Guruswami
2013	J	`jnl`	Capacity of Non-Malleable Codes. IACR Cryptol. ePrint Arch. Mahdi Cheraghchi, Venkatesan Guruswami
2013	—	`conf`	Combinatorial Limitations of Average-Radius List Decoding. APPROX-RANDOM Venkatesan Guruswami, Srivatsan Narayanan
2013	J	`jnl`	Complexity of approximating CSP with Balance / Hard Constraints. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Euiwoong Lee
2013	A*	`conf`	CopyCatch: stopping group attacks by spotting lockstep behavior in social networks. WWW Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, Christos Faloutsos
2013	A*	`conf`	Explicit Subspace Designs. FOCS Venkatesan Guruswami, Swastik Kopparty
2013	J	`jnl`	Explicit Subspace Designs. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Swastik Kopparty
2013	J	`jnl`	Explicit rank-metric codes list-decodable with optimal redundancy. CoRR Venkatesan Guruswami, Carol Wang
2013	J	`jnl`	Explicit rank-metric codes list-decodable with optimal redundancy. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Carol Wang
2013	J	`jnl`	Hitting Sets for Low-Degree Polynomials with Optimal Density. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Chaoping Xing
2013	J	`jnl`	Improved Inapproximability Results for Maximum k-Colorable Subgraph. Theory Comput. Venkatesan Guruswami, Ali Kemal Sinop
2013	J	`jnl`	Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket
2013	J	`jnl`	Linear-Algebraic List Decoding for Variants of Reed-Solomon Codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Carol Wang
2013	A*	`conf`	List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound. STOC Venkatesan Guruswami, Chaoping Xing
2013	J	`jnl`	Non-Malleable Coding Against Bit-wise and Split-State Tampering. CoRR Mahdi Cheraghchi, Venkatesan Guruswami
2013	J	`jnl`	Non-Malleable Coding Against Bit-wise and Split-State Tampering. Electron. Colloquium Comput. Complex. Mahdi Cheraghchi, Venkatesan Guruswami
2013	J	`jnl`	Non-Malleable Coding Against Bit-wise and Split-State Tampering. IACR Cryptol. ePrint Arch. Mahdi Cheraghchi, Venkatesan Guruswami
2013	J	`jnl`	Optimal rate algebraic list decoding using narrow ray class fields CoRR Venkatesan Guruswami, Chaoping Xing
2013	J	`jnl`	Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Chaoping Xing
2013	A*	`conf`	PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring. FOCS Irit Dinur, Venkatesan Guruswami
2013	J	`jnl`	PCPs via low-degree long code and hardness for constrained hypergraph coloring. Electron. Colloquium Comput. Complex. Irit Dinur, Venkatesan Guruswami
2013	—	`conf`	Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk). FSTTCS Venkatesan Guruswami
2013	A*	`conf`	Polar Codes: Speed of Polarization and Polynomial Gap to Capacity. FOCS Venkatesan Guruswami, Patrick Xia
2013	J	`jnl`	Polar Codes: Speed of polarization and polynomial gap to capacity CoRR Venkatesan Guruswami, Patrick Xia
2013	J	`jnl`	Polar Codes: Speed of polarization and polynomial gap to capacity. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Patrick Xia
2013	A*	`conf`	Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. SODA Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
2013	J	`jnl`	Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. SIAM J. Comput. Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
2013	J	`jnl`	Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs. CoRR Venkatesan Guruswami, Ali Kemal Sinop
2013	J	`jnl`	Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. CoRR Venkatesan Guruswami, Johan Håstad, Prahladh Harsha, Srikanth Srinivasan, Girish Varma
2013	J	`jnl`	Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma
2013	A	`conf`	Superlinear Lower Bounds for Multipass Graph Processing. CCC Venkatesan Guruswami, Krzysztof Onak
2013	J	`jnl`	Superlinear lower bounds for multipass graph processing. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Krzysztof Onak
2012	J	`jnl`	Agnostic Learning of Monomials by Halfspaces Is Hard. SIAM J. Comput. Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
2012	—	`conf`	Approximating Bounded Occurrence Ordering CSPs. APPROX-RANDOM Venkatesan Guruswami, Yuan Zhou
2012	J	`jnl`	Approximating Bounded Occurrence Ordering CSPs. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Yuan Zhou
2012	A*	`conf`	Bypassing UGC from some optimal geometric inapproximability results. SODA Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
2012	J	`jnl`	Combinatorial limitations of a strong form of list decoding CoRR Venkatesan Guruswami, Srivatsan Narayanan
2012	J	`jnl`	Combinatorial limitations of a strong form of list decoding. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Srivatsan Narayanan
2012	J	`jnl`	Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems CoRR Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou
2012	A*	`conf`	Faster SDP Hierarchy Solvers for Local Rounding Algorithms. FOCS Venkatesan Guruswami, Ali Kemal Sinop
2012	J	`jnl`	Faster SDP hierarchy solvers for local rounding algorithms CoRR Venkatesan Guruswami, Ali Kemal Sinop
2012	J	`jnl`	Faster SDP hierarchy solvers for local rounding algorithms. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Ali Kemal Sinop
2012	J	`jnl`	Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding CoRR Venkatesan Guruswami, Chaoping Xing
2012	J	`jnl`	Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Chaoping Xing
2012	A*	`conf`	Folded codes from function field towers and improved optimal rate list decoding. STOC Venkatesan Guruswami, Chaoping Xing
2012	J	`jnl`	Linear-algebraic list decoding for variants of Reed-Solomon codes. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Carol Wang
2012	J	`jnl`	List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Chaoping Xing
2012	J	`jnl`	List decoding subspace codes from insertions and deletions CoRR Venkatesan Guruswami, Srivatsan Narayanan, Carol Wang
2012	A	`conf`	List decoding subspace codes from insertions and deletions. ITCS Venkatesan Guruswami, Srivatsan Narayanan, Carol Wang
2012	A*	`conf`	Optimal column-based low-rank matrix reconstruction. SODA Venkatesan Guruswami, Ali Kemal Sinop
2012	A*	`conf`	Polynomial integrality gaps for strong SDP relaxations of Densest SODA Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou
2012	J	`jnl`	Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes CoRR Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
2012	J	`jnl`	Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. Electron. Colloquium Comput. Complex. Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker
2012	J	`jnl`	Superlinear lower bounds for multipass graph processing CoRR Venkatesan Guruswami, Krzysztof Onak
2012	J	`jnl`	Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set. Theory Comput. Venkatesan Guruswami, Yuan Zhou
2011	J	`jnl`	Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM J. Comput. Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
2011	J	`jnl`	Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar
2011	J	`jnl`	Certifying Graph Expansion and Non-Uniform Sparsity via Generalized Spectra CoRR Venkatesan Guruswami, Ali Kemal Sinop
2011	A	`conf`	Finding Almost-Perfect Graph Bisections. ICS Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou
2011	J	`jnl`	Hardness amplification within NP against deterministic algorithms. J. Comput. Syst. Sci. Parikshit Gopalan, Venkatesan Guruswami
2011	A*	`conf`	Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. FOCS Venkatesan Guruswami, Ali Kemal Sinop
2011	J	`jnl`	Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives CoRR Venkatesan Guruswami, Ali Kemal Sinop
2011	J	`jnl`	Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Ali Kemal Sinop
2011	A	`conf`	Linear-Algebraic List Decoding of Folded Reed-Solomon Codes. CCC Venkatesan Guruswami
2011	J	`jnl`	Linear-algebraic list decoding of folded Reed-Solomon codes CoRR Venkatesan Guruswami
2011	J	`jnl`	List Decoding Tensor Products and Interleaved Codes. SIAM J. Comput. Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
2011	J	`jnl`	On the List-Decodability of Random Linear Codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
2011	J	`jnl`	Optimal Column-Based Low-Rank Matrix Reconstruction CoRR Venkatesan Guruswami, Ali Kemal Sinop
2011	—	`conf`	Optimal Rate List Decoding via Derivative Codes. APPROX-RANDOM Venkatesan Guruswami, Carol Wang
2011	J	`jnl`	Optimal rate list decoding via derivative codes CoRR Venkatesan Guruswami, Carol Wang
2011	J	`jnl`	Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph CoRR Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou
2011	J	`jnl`	Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Atri Rudra
2011	J	`jnl`	Special Section on the Fortieth Annual ACM Symposium On Theory Of Computing (STOC 2008). SIAM J. Comput. Shuchi Chawla, Cynthia Dwork, Venkatesan Guruswami
2011	A*	`conf`	The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. SODA Venkatesan Guruswami, Ali Kemal Sinop
2011	J	`jnl`	The query complexity of estimating weighted averages. Acta Informatica Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth
2011	A*	`conf`	Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set. SODA Venkatesan Guruswami, Yuan Zhou
2010	J	`jnl`	A Lower Bound on List Size for List Decoding. IEEE Trans. Inf. Theory Venkatesan Guruswami, Salil P. Vadhan
2010	J	`jnl`	Agnostic Learning of Monomials by Halfspaces is Hard CoRR Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
2010	J	`jnl`	Agnostic Learning of Monomials by Halfspaces is Hard. Electron. Colloquium Comput. Complex. Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
2010	J	`jnl`	Almost Euclidean subspaces of Comb. Venkatesan Guruswami, James R. Lee, Alexander A. Razborov
2010	J	`jnl`	Bypassing UGC from some optimal geometric inapproximability results. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
2010	J	`jnl`	Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate CoRR Venkatesan Guruswami, Adam D. Smith
2010	A*	`conf`	Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. FOCS Venkatesan Guruswami, Adam D. Smith
2010	J	`jnl`	Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Adam D. Smith
2010	J	`jnl`	Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs. Comb. Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang
2010	J	`jnl`	Locally Testable Codes Require Redundant Testers. SIAM J. Comput. Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman
2010	—	`conf`	On the Inapproximability of Vertex Cover on ICALP (1) Venkatesan Guruswami, Rishi Saket
2010	J	`jnl`	On the List-Decodability of Random Linear Codes CoRR Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
2010	J	`jnl`	On the List-Decodability of Random Linear Codes. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
2010	A*	`conf`	On the list-decodability of random linear codes. STOC Venkatesan Guruswami, Johan Håstad, Swastik Kopparty
2010	—	`conf`	SDP Gaps for 2-to-1 and Other Label-Cover Variants. ICALP (1) Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu
2010	J	`jnl`	The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Ali Kemal Sinop
2010	J	`jnl`	The existence of concatenated codes list-decodable up to the hamming bound. IEEE Trans. Inf. Theory Venkatesan Guruswami, Atri Rudra
2010	J	`jnl`	Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Yuan Zhou
2009	A*	`conf`	Agnostic Learning of Monomials by Halfspaces Is Hard. FOCS Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
2009	J	`jnl`	Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes. Electron. Colloquium Comput. Complex. Venkatesan Guruswami
2009	A*	`conf`	Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. STOC Venkatesan Guruswami
2009	J	`jnl`	Better Binary List Decodable Codes Via Multilevel Concatenation. IEEE Trans. Inf. Theory Venkatesan Guruswami, Atri Rudra
2009	J	`jnl`	Error correction up to the information-theoretic limit. Commun. ACM Venkatesan Guruswami, Atri Rudra
2009	A	`conf`	Every Permutation CSP of arity 3 is Approximation Resistant. CCC Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran
2009	—	`conf`	Expander codes over reals, Euclidean sections, and compressed sensing. Allerton Venkatesan Guruswami, James R. Lee, Avi Wigderson
2009	J	`jnl`	Hardness of Learning Halfspaces with Noise. SIAM J. Comput. Venkatesan Guruswami, Prasad Raghavendra
2009	J	`jnl`	Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Prasad Raghavendra
2009	J	`jnl`	Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. ACM Trans. Comput. Theory Venkatesan Guruswami, Prasad Raghavendra
2009	J	`jnl`	Improved Inapproximability Results for Maximum k-Colorable Subgraph CoRR Venkatesan Guruswami, Ali Kemal Sinop
2009	—	`conf`	Improved Inapproximability Results for Maximum k-Colorable Subgraph. APPROX-RANDOM Venkatesan Guruswami, Ali Kemal Sinop
2009	J	`jnl`	Improved Inapproximability Results for Maximum k-Colorable Subgraph. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Ali Kemal Sinop
2009	—	`conf`	List Decoding of Binary Codes-A Brief Survey of Some Recent Results. IWCC Venkatesan Guruswami
2009	A*	`conf`	List decoding tensor products and interleaved codes. STOC Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
2009	A	`conf`	Locally Testable Codes Require Redundant Testers. CCC Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman
2009	J	`jnl`	Locally Testable Codes Require Redundant Testers. Electron. Colloquium Comput. Complex. Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman
2009	A*	`conf`	MaxMin allocation via degree lower-bounded arborescences. STOC MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami
2009	J	`jnl`	Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan
2008	J	`jnl`	Algorithms for Modular Counting of Roots of Multivariate Polynomials. Algorithmica Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton
2008	A*	`conf`	Almost Euclidean subspaces of l SODA Venkatesan Guruswami, James R. Lee, Alexander A. Razborov
2008	J	`jnl`	Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes CoRR Venkatesan Guruswami
2008	A*	`conf`	Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. FOCS Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra
2008	A*	`conf`	Concatenated codes can achieve list-decoding capacity. SODA Venkatesan Guruswami, Atri Rudra
2008	J	`jnl`	Concatenated codes can achieve list-decoding capacity. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Atri Rudra
2008	—	`conf`	Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness. APPROX-RANDOM Venkatesan Guruswami, Prasad Raghavendra
2008	J	`jnl`	Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Prasad Raghavendra
2008	J	`jnl`	Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets. Math. Comput. Venkatesan Guruswami, Anindya C. Patthak
2008	—	`ch.`	Decoding Reed-Solomon Codes. Encyclopedia of Algorithms Venkatesan Guruswami
2008	—	`conf`	Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. APPROX-RANDOM Venkatesan Guruswami, James R. Lee, Avi Wigderson
2008	J	`jnl`	Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy. IEEE Trans. Inf. Theory Venkatesan Guruswami, Atri Rudra
2008	B	`conf`	Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction. ISIT Venkatesan Guruswami, Widad Machmouchi
2008	J	`jnl`	Hardness Amplification via Space-Efficient Direct Products. Comput. Complex. Venkatesan Guruswami, Valentine Kabanets
2008	A	`conf`	Hardness Amplification within NP against Deterministic Algorithms. CCC Parikshit Gopalan, Venkatesan Guruswami
2008	J	`jnl`	List Decoding Tensor Products and Interleaved Codes CoRR Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
2008	J	`jnl`	List Decoding Tensor Products and Interleaved Codes. Electron. Colloquium Comput. Complex. Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra
2008	—	`conf`	List Error-Correction with Optimal Information Rate (Invited Talk). ICITS Venkatesan Guruswami
2008	A	`conf`	Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes. CCC Venkatesan Guruswami, Atri Rudra
2008	J	`jnl`	Soft decoding, dual BCH codes, and better list-decodable eps-biased codes. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Atri Rudra
2007	A*	`conf`	A 3-query PCP over integers. STOC Venkatesan Guruswami, Prasad Raghavendra
2007	J	`jnl`	Almost Euclidean subspaces of ℓ Electron. Colloquium Comput. Complex. Venkatesan Guruswami, James R. Lee, Alexander A. Razborov
2007	—	`conf`	Better Binary List-Decodable Codes Via Multilevel Concatenation. APPROX-RANDOM Venkatesan Guruswami, Atri Rudra
2007	J	`jnl`	Better Binary List-Decodable Codes via Multilevel Concatenation. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Atri Rudra
2007	J	`jnl`	Deterministic Hardness Amplification via Local GMD Decoding. Electron. Colloquium Comput. Complex. Parikshit Gopalan, Venkatesan Guruswami
2007	J	`jnl`	Guessing secrets efficiently via list decoding. ACM Trans. Algorithms Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan
2007	A*	`conf`	Hardness of routing with congestion in directed graphs. STOC Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar
2007	J	`jnl`	Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Electron. Colloquium Comput. Complex. Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang
2007	—	`conf`	List Decoding and Pseudorandom Constructions. AAECC Venkatesan Guruswami
2007	J	`jnl`	Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword. Comput. Complex. Venkatesan Guruswami, Valentine Kabanets
2007	A	`conf`	Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. CCC Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan
2006	J	`jnl`	Algorithmic Results in List Decoding. Found. Trends Theor. Comput. Sci. Venkatesan Guruswami
2006	B	`conf`	Algorithms for Modular Counting of Roots of Multivariate Polynomials. LATIN Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton
2006	A*	`conf`	Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. FOCS Venkatesan Guruswami, Anindya C. Patthak
2006	J	`jnl`	Correlation Clustering with a Fixed Number of Clusters. Theory Comput. Ioannis Giotis, Venkatesan Guruswami
2006	A*	`conf`	Correlation clustering with a fixed number of clusters. SODA Ioannis Giotis, Venkatesan Guruswami
2006	A*	`conf`	Explicit capacity-achieving list-decodable codes. STOC Venkatesan Guruswami, Atri Rudra
2006	J	`jnl`	Extractors and condensers from univariate polynomials. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan
2006	B	`conf`	Hardness Amplification Via Space-Efficient Direct Products. LATIN Venkatesan Guruswami, Valentine Kabanets
2006	A*	`conf`	Hardness of Learning Halfspaces with Noise. FOCS Venkatesan Guruswami, Prasad Raghavendra
2006	J	`jnl`	Hardness of Learning Halfspaces with Noise. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Prasad Raghavendra
2006	J	`jnl`	Hardness of Low Congestion Routing in Directed Graphs. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Kunal Talwar
2006	J	`jnl`	Iterative Decoding of Low-Density Parity Check Codes (A Survey) CoRR Venkatesan Guruswami
2006	J	`jnl`	Iterative Decoding of Low-Density Parity Check Codes (A Survey). Electron. Colloquium Comput. Complex. Venkatesan Guruswami
2006	J	`jnl`	Iterative Decoding of Low-Density Parity Check Codes. Bull. EATCS Venkatesan Guruswami
2006	J	`jnl`	Limits to List Decoding Reed-Solomon Codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Atri Rudra
2006	B	`conf`	List Decoding in Average-Case Complexity and Pseudorandomness. ITW Venkatesan Guruswami
2006	B	`conf`	On 2-Query Codeword Testing with Near-Perfect Completeness. ISAAC Venkatesan Guruswami
2005	—	`conf`	A Lower Bound on List Size for List Decoding. APPROX-RANDOM Venkatesan Guruswami, Salil P. Vadhan
2005	J	`jnl`	A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. SIAM J. Comput. Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
2005	J	`jnl`	Algebraic-geometric generalizations of the Parvaresh-Vardy codes Electron. Colloquium Comput. Complex. Venkatesan Guruswami
2005	J	`jnl`	Clustering with qualitative information. J. Comput. Syst. Sci. Moses Charikar, Venkatesan Guruswami, Anthony Wirth
2005	J	`jnl`	Correlation Clustering with a Fixed Number of Clusters CoRR Ioannis Giotis, Venkatesan Guruswami
2005	J	`jnl`	Explicit Capacity-Achieving List-Decodable Codes Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Atri Rudra
2005	J	`jnl`	Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy CoRR Venkatesan Guruswami, Atri Rudra
2005	J	`jnl`	Hardness amplification via space-efficient direct products Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Valentine Kabanets
2005	A	`conf`	Hardness of Max 3SAT with No Mixed Clauses. CCC Venkatesan Guruswami, Subhash Khot
2005	A*	`conf`	Limits to list decoding Reed-Solomon codes. STOC Venkatesan Guruswami, Atri Rudra
2005	J	`jnl`	Linear-time encodable/decodable codes with near-optimal rate. IEEE Trans. Inf. Theory Venkatesan Guruswami, Piotr Indyk
2005	A*	`conf`	Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. SODA Venkatesan Guruswami, Alexander Vardy
2005	J	`jnl`	Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. IEEE Trans. Inf. Theory Venkatesan Guruswami, Alexander Vardy
2005	A*	`conf`	On profit-maximizing envy-free pricing. SODA Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry
2005	—	`conf`	The Complexity of Making Unique Choices: Approximating 1-in- k SAT. APPROX-RANDOM Venkatesan Guruswami, Luca Trevisan
2005	J	`jnl`	The complexity of the covering radius problem. Comput. Complex. Venkatesan Guruswami, Daniele Micciancio, Oded Regev
2005	J	`jnl`	Tolerant Locally Testable Codes Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Atri Rudra
2005	—	`conf`	Tolerant Locally Testable Codes. APPROX-RANDOM Venkatesan Guruswami, Atri Rudra
2004	A*	`conf`	Better extractors for better codes? STOC Venkatesan Guruswami
2004	A*	`conf`	Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. SODA Venkatesan Guruswami, Piotr Indyk
2004	J	`jnl`	Guest Editors' foreword. J. Comput. Syst. Sci. Edith Cohen, Venkatesan Guruswami
2004	J	`jnl`	Guest column: error-correcting codes and expander graphs. SIGACT News Venkatesan Guruswami
2004	J	`jnl`	Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses. Algorithmica Venkatesan Guruswami
2004	J	`jnl`	Is constraint satisfaction over two variables always easy? Random Struct. Algorithms Lars Engebretsen, Venkatesan Guruswami
2004	A*	`conf`	Linear-Time List Decoding in Error-Free Settings: (Extended Abstract). ICALP Venkatesan Guruswami, Piotr Indyk
2004	—	`book`	List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition) Venkatesan Guruswami
2004	J	`jnl`	Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard CoRR Venkatesan Guruswami, Alexander Vardy
2004	J	`jnl`	Maximum-likelihood decoding of Reed-Solomon codes is NP-hard Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Alexander Vardy
2004	J	`jnl`	On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM J. Discret. Math. Venkatesan Guruswami, Sanjeev Khanna
2004	A	`conf`	The Complexity of the Covering Radius Problem on Lattices and Codes. CCC Venkatesan Guruswami, Daniele Micciancio, Oded Regev
2003	J	`jnl`	A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover CoRR Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
2003	A*	`conf`	A new multilayered PCP and the hardness of hypergraph vertex cover. STOC Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
2003	J	`jnl`	Better Extractors for Better Codes? Electron. Colloquium Comput. Complex. Venkatesan Guruswami
2003	A*	`conf`	Clustering with Qualitative Information. FOCS Moses Charikar, Venkatesan Guruswami, Anthony Wirth
2003	J	`jnl`	Constructions of codes from number fields. IEEE Trans. Inf. Theory Venkatesan Guruswami
2003	A*	`conf`	Embeddings and non-approximability of geometric problems. SODA Venkatesan Guruswami, Piotr Indyk
2003	A*	`conf`	Linear time encodable and list decodable codes. STOC Venkatesan Guruswami, Piotr Indyk
2003	A	`conf`	List Decoding with Side Information. CCC Venkatesan Guruswami
2003	J	`jnl`	List decoding from erasures: bounds and code constructions. IEEE Trans. Inf. Theory Venkatesan Guruswami
2003	J	`jnl`	Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis
2003	A*	`conf`	Unconditional proof of tightness of Johnson bound. SODA Venkatesan Guruswami, Igor E. Shparlinski
2002	J	`jnl`	Combinatorial bounds for list decoding. IEEE Trans. Inf. Theory Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman
2002	A	`conf`	Decoding Concatenated Codes using Soft Information. CCC Venkatesan Guruswami, Madhu Sudan
2002	A*	`conf`	Guessing secrets efficiently via list decoding. SODA Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan
2002	J	`jnl`	Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. Venkatesan Guruswami, Johan Håstad, Madhu Sudan
2002	—	`conf`	Is Constraint Satisfaction Over Two Variables Always Easy? RANDOM Lars Engebretsen, Venkatesan Guruswami
2002	J	`jnl`	Is Constraint Satisfaction Over Two Variables Always Easy? Electron. Colloquium Comput. Complex. Lars Engebretsen, Venkatesan Guruswami
2002	A*	`conf`	Limits to list decodability of linear codes. STOC Venkatesan Guruswami
2002	A*	`conf`	Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. STOC Venkatesan Guruswami, Piotr Indyk
2002	J	`jnl`	Query Strategies for Priced Information. J. Comput. Syst. Sci. Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai
2002	J	`jnl`	Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon) Electron. Colloquium Comput. Complex. Irit Dinur, Venkatesan Guruswami, Subhash Khot
2001	J	`jnl`	Constructions of Codes from Number Fields Electron. Colloquium Comput. Complex. Venkatesan Guruswami
2001	—	`conf`	Constructions of Codes from Number Fields. AAECC Venkatesan Guruswami
2001	A*	`conf`	Expander-Based Constructions of Efficiently Decodable Codes. FOCS Venkatesan Guruswami, Piotr Indyk
2001	—	`conf`	List Decoding from Erasures: Bounds and Code Constructions. FSTTCS Venkatesan Guruswami
2001	—	`—`	List decoding of error correcting codes. Venkatesan Guruswami
2001	J	`jnl`	On representations of algebraic-geometry codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Madhu Sudan
2001	J	`jnl`	The K Computing Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong
2000	A*	`conf`	"Soft-decision" Decoding of Chinese Remainder Codes. FOCS Venkatesan Guruswami, Amit Sahai, Madhu Sudan
2000	J	`jnl`	Algorithmic aspects of clique-transversal and clique-independent sets. Discret. Appl. Math. Venkatesan Guruswami, C. Pandu Rangan
2000	A*	`conf`	Combinatorial feature selection problems. FOCS Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai
2000	A*	`conf`	Hardness of Approximate Hypergraph Coloring. FOCS Venkatesan Guruswami, Johan Håstad, Madhu Sudan
2000	J	`jnl`	Hardness of approximate hypergraph coloring Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Johan Håstad, Madhu Sudan
2000	—	`conf`	Inapproximability results for set splitting and satisfiability problems with no mixed clauses. APPROX Venkatesan Guruswami
2000	A*	`conf`	List decoding algorithms for certain concatenated codes. STOC Venkatesan Guruswami, Madhu Sudan
2000	A	`conf`	On Representations of Algebraic-Geometric Codes for List Decoding. ESA Venkatesan Guruswami, Madhu Sudan
2000	A	`conf`	On the Hardness of 4-Coloring a 3-Colorable Graph. CCC Venkatesan Guruswami, Sanjeev Khanna
2000	J	`jnl`	On the Hardness of 4-coloring a 3-colorable Graph Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Sanjeev Khanna
2000	A*	`conf`	Query strategies for priced information (extended abstract). STOC Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai
1999	J	`jnl`	Enumerative aspects of certain subclasses of perfect graphs. Discret. Math. Venkatesan Guruswami
1999	J	`jnl`	Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Trans. Inf. Theory Venkatesan Guruswami, Madhu Sudan
1999	J	`jnl`	Maximum Cut on Line and Total Graphs. Discret. Appl. Math. Venkatesan Guruswami
1999	A*	`conf`	Multiclass Learning, Boosting, and Error-Correcting Codes. COLT Venkatesan Guruswami, Amit Sahai
1999	A*	`conf`	Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. STOC Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis
1999	A*	`conf`	The 2-Catalog Segmentation Problem. SODA Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna
1999	J	`jnl`	The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses Electron. Colloquium Comput. Complex. Venkatesan Guruswami
1998	J	`jnl`	A Natural Family of Optimization Problems with Arbitrarily Small Approximation Thresholds. Inf. Process. Lett. Venkatesan Guruswami, C. Pandu Rangan
1998	A*	`conf`	A Tight Characterization of NP with 3 Query PCPs. FOCS Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan
1998	J	`jnl`	A tight characterization of NP with 3 query PCPs Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan
1998	A*	`conf`	Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. FOCS Venkatesan Guruswami, Madhu Sudan
1998	J	`jnl`	Improved decoding of Reed-Solomon and algebraic-geometric codes. Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Madhu Sudan
1998	B	`conf`	The Vertex-Disjoint Triangles Problem. WG Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong