default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDVenkatesan Guruswami
Person information
- affiliation: University of Berkeley, Department of EECS, Berkeley, CA, USA
- affiliation (former): Carnegie Mellon University, Pittsburgh, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c198]Venkatesan Guruswami, Hsin-Po Wang:
Capacity-Achieving Gray Codes. APPROX/RANDOM 2024: 65:1-65:9- [c197]Venkatesan Guruswami, Xuandi Ren, Sai Sandeep:
Baby PIH: Parameterized Inapproximability of Min CSP. CCC 2024: 27:1-27:17 - [c196]Vipul Arora, Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, Esty Kelman:
Outlier Robust Multivariate Polynomial Regression. ESA 2024: 12:1-12:17 - [c195]Omar Alrabiah, Venkatesan Guruswami, Ray Li:
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. SODA 2024: 1367-1378 - [c194]Venkatesan Guruswami
, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis. STOC 2024: 24-35 - [c193]Omar Alrabiah, Venkatesan Guruswami, Ray Li:
Randomly Punctured Reed-Solomon Codes Achieve List-Decoding Capacity over Linear-Sized Fields. STOC 2024: 1458-1469 - [e3]Venkatesan Guruswami:
15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA. LIPIcs 287, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024, ISBN 978-3-95977-309-6 [contents] - [i243]Vipul Arora, Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, Esty Kelman:
Outlier Robust Multivariate Polynomial Regression. CoRR abs/2403.09465 (2024) - [i242]Venkatesan Guruswami, Rishi Saket:
Hardness of Learning Boolean Functions from Label Proportions. CoRR abs/2403.19401 (2024) - [i241]Omar Alrabiah, Venkatesan Guruswami:
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. CoRR abs/2404.05864 (2024) - [i240]Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. CoRR abs/2404.08870 (2024) - [i239]Venkatesan Guruswami, Jun-Ting Hsieh, Prasad Raghavendra:
Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the √n Dimension Threshold. CoRR abs/2405.05373 (2024) - [i238]Hsin-Po Wang, Venkatesan Guruswami:
How Many Matrices Should I Prepare To Polarize Channels Optimally Fast? CoRR abs/2405.16360 (2024) - [i237]Hsin-Po Wang, Ryan Gabrys, Venkatesan Guruswami:
Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett and Cheraghchi-Nakos's Nonadaptive Splitting with Explicit Scalars. CoRR abs/2405.16370 (2024) - [i236]Hsin-Po Wang, Venkatesan Guruswami:
Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically. CoRR abs/2405.16373 (2024) - [i235]Hsin-Po Wang, Venkatesan Guruswami:
Isolate and then Identify: Rethinking Adaptive Group Testing. CoRR abs/2405.16374 (2024) - [i234]Venkatesan Guruswami, Rhea Jain:
Exponential Time Approximation for Coloring 3-Colorable Graphs. CoRR abs/2406.15563 (2024) - [i233]Venkatesan Guruswami, Hsin-Po Wang:
Capacity-Achieving Gray Codes. CoRR abs/2406.17669 (2024) - [i232]Meghal Gupta, Venkatesan Guruswami, Mihir Singhal:
Tight bounds for stream decodable error-correcting codes. CoRR abs/2407.06446 (2024) - [i231]Louis Golowich, Venkatesan Guruswami:
Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates. CoRR abs/2408.09254 (2024) - [i230]Hsin-Po Wang, Venkatesan Guruswami:
Geno-Weaving: Low-Complexity Capacity-Achieving DNA Storage. CoRR abs/2409.00889 (2024) - [i229]Omar Alrabiah, Venkatesan Guruswami:
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. Electron. Colloquium Comput. Complex. TR24 (2024) - [i228]Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. Electron. Colloquium Comput. Complex. TR24 (2024) - [i227]Surendra Ghentiyala, Venkatesan Guruswami:
New constructions of pseudorandom codes. IACR Cryptol. ePrint Arch. 2024: 1425 (2024) - 2023
- [j111]Vijay Bhattiprolu, Mrinal Kanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Inapproximability of Matrix p → q Norms. SIAM J. Comput. 52(1): 132-155 (2023) - [j110]Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li:
Efficient Linear and Affine Codes for Correcting Insertions/Deletions. SIAM J. Discret. Math. 37(2): 748-778 (2023) - [j109]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
Conditional Dichotomy of Boolean Ordered Promise CSPs. TheoretiCS 2 (2023) - [j108]Ryan Gabrys, Venkatesan Guruswami, João Ribeiro, Ke Wu:
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. IEEE Trans. Inf. Theory 69(1): 169-186 (2023) - [j107]Venkatesan Guruswami, Xiaoyu He, Ray Li:
The Zero-Rate Threshold for Adversarial Bit-Deletions is Less Than 1/2. IEEE Trans. Inf. Theory 69(4): 2218-2239 (2023) - [c192]Venkatesan Guruswami, Shilun Li:
A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. APPROX/RANDOM 2023: 50:1-50:10 - [c191]Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar:
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. FOCS 2023: 307-327 - [c190]Venkatesan Guruswami, Rishi Saket:
Hardness of Learning Boolean Functions from Label Proportions. FSTTCS 2023: 37:1-37:15 - [c189]Hsin-Po Wang, Venkatesan Guruswami:
How Many Matrices Should I Prepare To Polarize Channels Optimally Fast? ISIT 2023: 1556-1561 - [c188]Hsin-Po Wang, Ryan Gabrys, Venkatesan Guruswami:
Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett's Nonadaptive Splitting with Explicit Scalars. ISIT 2023: 1609-1614 - [c187]Michael Rudow, Venkatesan Guruswami, K. V. Rashmi:
On expanding the toolkit of locality-based coded computation to the coordinates of inputs. ISIT 2023: 2171-2176 - [c186]Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro:
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms. STOC 2023: 553-566 - [c185]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
SDPs and Robust Satisfiability of Promise CSP. STOC 2023: 609-622 - [c184]Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. STOC 2023: 1438-1448 - [c183]Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang:
Binary Error-Correcting Codes with Minimal Noiseless Feedback. STOC 2023: 1475-1487 - [i226]Omar Alrabiah, Venkatesan Guruswami, Ray Li:
Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields. CoRR abs/2304.09445 (2023) - [i225]Venkatesan Guruswami, Shilun Li:
A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. CoRR abs/2305.02484 (2023) - [i224]Nouédyn Baspin, Venkatesan Guruswami, Anirudh Krishna, Ray Li:
Improved rate-distance trade-offs for quantum codes with restricted connectivity. CoRR abs/2307.03283 (2023) - [i223]Omar Alrabiah, Venkatesan Guruswami, Ray Li:
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. CoRR abs/2308.13424 (2023) - [i222]Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. CoRR abs/2308.15403 (2023) - [i221]Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar:
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. CoRR abs/2309.16897 (2023) - [i220]Venkatesan Guruswami, Xuandi Ren, Sai Sandeep:
Baby PIH: Parameterized Inapproximability of Min CSP. CoRR abs/2310.16344 (2023) - [i219]Venkatesan Guruswami, Hsin-Po Wang:
Noise-Resilient Group Testing with Order-Optimal Tests and Fast-and-Reliable Decoding. CoRR abs/2311.08283 (2023) - [i218]Louis Golowich, Venkatesan Guruswami:
Quantum Locally Recoverable Codes. CoRR abs/2311.08653 (2023) - [i217]Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
Parameterized Inapproximability Hypothesis under ETH. CoRR abs/2311.16587 (2023) - [i216]Omar Alrabiah, Venkatesan Guruswami, Ray Li:
Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields. Electron. Colloquium Comput. Complex. TR23 (2023) - [i215]Omar Alrabiah, Venkatesan Guruswami, Ray Li:
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. Electron. Colloquium Comput. Complex. TR23 (2023) - [i214]Louis Golowich, Venkatesan Guruswami:
Quantum Locally Recoverable Codes. Electron. Colloquium Comput. Complex. TR23 (2023) - [i213]Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
Parameterized Inapproximability Hypothesis under ETH. Electron. Colloquium Comput. Complex. TR23 (2023) - [i212]Venkatesan Guruswami, Xuandi Ren, Sai Sandeep:
Baby PIH: Parameterized Inapproximability of Min CSP. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j106]Vikraman Arvind, Venkatesan Guruswami:
CNF Satisfiability in a Subspace and Related Problems. Algorithmica 84(11): 3276-3299 (2022) - [j105]Venkatesan Guruswami, Chaoping Xing:
Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes. J. ACM 69(2): 10:1-10:48 (2022) - [j104]Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan:
General Strong Polarization. J. ACM 69(2): 11:1-11:67 (2022) - [j103]Venkatesan Guruswami, Andrii Riazanov:
Beating Fredman-Komlós for perfect k-hashing. J. Comb. Theory A 188: 105580 (2022) - [j102]Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami:
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. SIAM J. Comput. 51(3): 577-626 (2022) - [j101]Venkatesan Guruswami, Jonathan Moshieff, Nicolas Resch, Shashwat Silas, Mary Wootters:
Threshold Rates for Properties of Random Codes. IEEE Trans. Inf. Theory 68(2): 905-922 (2022) - [j100]Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters:
Bounds for List-Decoding and List-Recovery of Random Linear Codes. IEEE Trans. Inf. Theory 68(2): 923-939 (2022) - [j99]Venkatesan Guruswami, Andrii Riazanov, Min Ye:
Arıkan Meets Shannon: Polar Codes With Near-Optimal Convergence to Channel Capacity. IEEE Trans. Inf. Theory 68(5): 2877-2919 (2022) - [j98]Sivakanth Gopi, Venkatesan Guruswami:
Improved Maximally Recoverable LRCs Using Skew Polynomials. IEEE Trans. Inf. Theory 68(11): 7198-7214 (2022) - [c182]Ryan Gabrys, Venkatesan Guruswami, João Ribeiro, Ke Wu:
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. APPROX/RANDOM 2022: 8:1-8:17 - [c181]Iwan M. Duursma, Ryan Gabrys, Venkatesan Guruswami, Ting-Chun Lin, Hsin-Po Wang:
Accelerating Polarization via Alphabet Extension. APPROX/RANDOM 2022: 17:1-17:15 - [c180]Venkatesan Guruswami, Xin Lyu, Xiuhan Wang:
Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness. APPROX/RANDOM 2022: 20:1-20:21 - [c179]Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. APPROX/RANDOM 2022: 42:1-42:7 - [c178]Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff:
ℓp-Spread and Restricted Isometry Properties of Sparse Random Matrices. CCC 2022: 7:1-7:17 - [c177]Venkatesan Guruswami, Jonathan Mosheiff:
Punctured Low-Bias Codes Behave Like Random Linear Codes. FOCS 2022: 36-45 - [c176]Venkatesan Guruswami, Sai Sandeep:
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture. SODA 2022: 927-944 - [c175]Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. STOC 2022: 678-689 - [e2]Anuj Dawar, Venkatesan Guruswami:
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, December 18-20, 2022, IIT Madras, Chennai, India. LIPIcs 250, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022, ISBN 978-3-95977-261-7 [contents] - [i211]Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff:
Sparsity and 𝓁p-Restricted Isometry. CoRR abs/2205.06738 (2022) - [i210]Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. CoRR abs/2205.06739 (2022) - [i209]Iwan M. Duursma, Ryan Gabrys, Venkatesan Guruswami, Ting-Chun Lin, Hsin-Po Wang:
Accelerating Polarization via Alphabet Extension. CoRR abs/2207.04522 (2022) - [i208]Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro:
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all 𝓁p Norms. CoRR abs/2211.07900 (2022) - [i207]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
SDPs and Robust Satisfiability of Promise CSP. CoRR abs/2211.08373 (2022) - [i206]Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang:
Binary Error-Correcting Codes with Minimal Noiseless Feedback. CoRR abs/2212.05673 (2022) - [i205]Martin Grohe, Venkatesan Guruswami, Dániel Marx, Stanislav Zivný:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201). Dagstuhl Reports 12(5): 112-130 (2022) - [i204]Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar:
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. Electron. Colloquium Comput. Complex. TR22 (2022) - [i203]Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, João Ribeiro:
Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all ℓp Norms. Electron. Colloquium Comput. Complex. TR22 (2022) - [i202]Venkatesan Guruswami, Xin Lyu, Xiuhan Wang:
Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j97]Venkatesan Guruswami, Nicolas Resch, Chaoping Xing:
Lossless Dimension Expanders Via Linearized Polynomials and Subspace Designs. Comb. 41(4): 545-579 (2021) - [j96]Joshua Brakensiek, Venkatesan Guruswami:
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. SIAM J. Comput. 50(6): 1663-1700 (2021) - [j95]Joshua Brakensiek, Venkatesan Guruswami:
The Quest for Strong Inapproximability Results with Perfect Completeness. ACM Trans. Algorithms 17(3): 27:1-27:35 (2021) - [j94]Venkatesan Guruswami, Johan Håstad:
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound. IEEE Trans. Inf. Theory 67(10): 6384-6394 (2021) - [j93]Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi:
Optimally Resilient Codes for List-Decoding From Insertions and Deletions. IEEE Trans. Inf. Theory 67(12): 7837-7856 (2021) - [j92]Omar Alrabiah, Venkatesan Guruswami:
An Exponential Lower Bound on the Sub-Packetization of Minimum Storage Regenerating Codes. IEEE Trans. Inf. Theory 67(12): 8086-8093 (2021) - [c174]Omar Alrabiah, Venkatesan Guruswami:
Visible Rank and Codes with Locality. APPROX-RANDOM 2021: 57:1-57:18 - [c173]Venkatesan Guruswami, Xiaoyu He, Ray Li:
The zero-rate threshold for adversarial bit-deletions is less than 1/2. FOCS 2021: 727-738 - [c172]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
Conditional Dichotomy of Boolean Ordered Promise CSPs. ICALP 2021: 37:1-37:15 - [c171]Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters:
Sharp Threshold Rates for Random Codes. ITCS 2021: 5:1-5:20 - [c170]Venkatesan Guruswami, Vinayak Kumar:
Pseudobinomiality of the Sticky Random Walk. ITCS 2021: 48:1-48:19 - [c169]Venkatesan Guruswami, Andrii Riazanov:
Linear Shannon Capacity of Cayley Graphs. ISIT 2021: 988-992 - [c168]Michael Rudow, K. V. Rashmi, Venkatesan Guruswami:
A locality-based lens for coded computation. ISIT 2021: 1070-1075 - [c167]Venkatesan Guruswami, Andrii Riazanov:
Linear Programming Bounds for Almost-Balanced Binary Codes. ISIT 2021: 1302-1307 - [c166]Vikraman Arvind, Venkatesan Guruswami:
CNF Satisfiability in a Subspace and Related Problems. IPEC 2021: 5:1-5:15 - [c165]Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li:
Efficient Linear and Affine Codes for Correcting Insertions/Deletions. SODA 2021: 1-20 - [c164]Venkatesan Guruswami, Johan Håstad:
Explicit two-deletion codes with redundancy matching the existential bound. SODA 2021: 21-32 - [c163]Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari:
Strongly refuting all semi-random Boolean CSPs. SODA 2021: 454-472 - [i201]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
Conditional Dichotomy of Boolean Ordered Promise CSPs. CoRR abs/2102.11854 (2021) - [i200]Venkatesan Guruswami, Xiaoyu He, Ray Li:
The zero-rate threshold for adversarial bit-deletions is less than 1/2. CoRR abs/2106.05250 (2021) - [i199]Venkatesan Guruswami, Andrii Riazanov:
Linear Programming Bounds for Almost-Balanced Binary Codes. CoRR abs/2107.07672 (2021) - [i198]Vikraman Arvind, Venkatesan Guruswami:
CNF Satisfiability in a Subspace and Related Problems. CoRR abs/2108.05914 (2021) - [i197]Omar Alrabiah, Venkatesan Guruswami:
Visible Rank and Codes with Locality. CoRR abs/2108.12687 (2021) - [i196]Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff:
𝓁p-Spread Properties of Sparse Matrices. CoRR abs/2108.13578 (2021) - [i195]Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar:
Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random". CoRR abs/2109.04415 (2021) - [i194]Venkatesan Guruswami, Jonathan Mosheiff:
Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity. CoRR abs/2109.11725 (2021) - [i193]Ryan Gabrys, Venkatesan Guruswami, João Ribeiro, Ke Wu:
Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. CoRR abs/2112.09971 (2021) - [i192]Omar Alrabiah, Venkatesan Guruswami:
Visible Rank and Codes with Locality. Electron. Colloquium Comput. Complex. TR21 (2021) - [i191]Omar Alrabiah, Venkatesan Guruswami:
Revisiting a Lower Bound on the Redundancy of Linear Batch Codes. Electron. Colloquium Comput. Complex. TR21 (2021) - [i190]Vikraman Arvind, Venkatesan Guruswami:
CNF Satisfiability in a Subspace and Related Problems. Electron. Colloquium Comput. Complex. TR21 (2021) - [i189]Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep:
Conditional Dichotomy of Boolean Ordered Promise CSPs. Electron. Colloquium Comput. Complex. TR21 (2021) - [i188]Sivakanth Gopi, Venkatesan Guruswami:
Improved Maximally Recoverable LRCs using Skew Polynomials. Electron. Colloquium Comput. Complex. TR21 (2021) - [i187]Venkatesan Guruswami, Xiaoyu He, Ray Li:
The zero-rate threshold for adversarial bit-deletions is less than 1/2. Electron. Colloquium Comput. Complex. TR21 (2021) - [i186]Venkatesan Guruswami, Jonathan Mosheiff:
Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j91]Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný:
The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems. SIAM J. Comput. 49(6): 1232-1248 (2020) - [j90]Venkatesan Guruswami, Sai Sandeep:
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms. SIAM J. Discret. Math. 34(1): 520-537 (2020) - [j89]Marco Dalai, Venkatesan Guruswami, Jaikumar Radhakrishnan:
An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel. IEEE Trans. Inf. Theory 66(2): 749-756 (2020) - [j88]