Stop the war!Остановите войну!
for scientists:
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
Books and Theses
- 2004
[b2]Venkatesan Guruswami:
List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition). Lecture Notes in Computer Science 3282, Springer 2004, ISBN 3-540-24051-9, pp. 1-350- 2001
- [b1]Venkatesan Guruswami:
List decoding of error correcting codes. Massachusetts Institute of Technology, 2001, pp. 1-315
Journal Articles
- 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) - 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, Ser. 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) - 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) - 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]Venkatesan Guruswami, Ray Li:
Coding Against Deletions in Oblivious and Online Models. IEEE Trans. Inf. Theory 66(4): 2352-2374 (2020) - [j87]Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin:
Maximally Recoverable LRCs: A Field Size Lower Bound and Constructions for Few Heavy Parities. IEEE Trans. Inf. Theory 66(10): 6066-6083 (2020) - [j86]Venkatesan Guruswami, Lingfei Jin, Chaoping Xing:
Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields. IEEE Trans. Inf. Theory 66(10): 6133-6143 (2020) - [j85]Venkatesan Guruswami, Satyanarayana V. Lokam, Sai Vikneshwar Mani Jayaraman:
ϵ-MSR Codes: Contacting Fewer Code Blocks for Exact Repair. IEEE Trans. Inf. Theory 66(11): 6749-6761 (2020) - 2019
- [j84]Venkatesan Guruswami, Ray Li:
Polynomial Time Decodable Codes for the Binary Deletion Channel. IEEE Trans. Inf. Theory 65(4): 2171-2178 (2019) - [j83]Venkatesan Guruswami, Chaoping Xing, Chen Yuan:
How Long Can Optimal Locally Repairable Codes Be? IEEE Trans. Inf. Theory 65(6): 3662-3670 (2019) - 2018
- [j82]Venkatesan Guruswami, Euiwoong Lee:
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. Comb. 38(3): 547-599 (2018) - [j81]Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky:
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. IEEE Trans. Inf. Theory 64(5): 3403-3410 (2018) - [j80]Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko:
MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth. IEEE Trans. Inf. Theory 64(10): 6506-6525 (2018) - 2017
- [j79]Mahdi Cheraghchi, Venkatesan Guruswami:
Non-malleable Coding Against Bit-Wise and Split-State Tampering. J. Cryptol. 30(1): 191-241 (2017) - [j78]Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma:
Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes. SIAM J. Comput. 46(1): 132-159 (2017) - [j77]Venkatesan Guruswami, Euiwoong Lee:
Nearly Optimal NP-Hardness of Unique Coverage. SIAM J. Comput. 46(3): 1018-1028 (2017) - [j76]Per Austrin, Venkatesan Guruswami, Johan Håstad:
(2+ε)-Sat Is NP-hard. SIAM J. Comput. 46(5): 1554-1573 (2017) - [j75]Venkatesan Guruswami, Euiwoong Lee:
Inapproximability of H-Transversal/Packing. SIAM J. Discret. Math. 31(3): 1552-1571 (2017) - [j74]Boris Bukh, Venkatesan Guruswami, Johan Håstad:
An Improved Bound on the Fraction of Correctable Deletions. IEEE Trans. Inf. Theory 63(1): 93-103 (2017) - [j73]Venkatesan Guruswami, Carol Wang:
Deletion Codes in the High-Noise and High-Rate Regimes. IEEE Trans. Inf. Theory 63(4): 1961-1970 (2017) - [j72]Venkatesan Guruswami, Lingfei Jin, Chaoping Xing:
Efficiently List-Decodable Punctured Reed-Muller Codes. IEEE Trans. Inf. Theory 63(7): 4317-4324 (2017) - [j71]Venkatesan Guruswami, Mary Wootters:
Repairing Reed-Solomon Codes. IEEE Trans. Inf. Theory 63(9): 5684-5698 (2017) - [j70]Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan:
Communication With Imperfectly Shared Randomness. IEEE Trans. Inf. Theory 63(10): 6799-6818 (2017) - [j69]Venkatesan Guruswami, Euiwoong Lee:
Towards a Characterization of Approximation Resistance for Symmetric CSPs. Theory Comput. 13(1): 1-24 (2017) - 2016
- [j68]Venkatesan Guruswami, Krzysztof Onak:
Superlinear Lower Bounds for Multipass Graph Processing. Algorithmica 76(3): 654-683 (2016) - [j67]Venkatesan Guruswami, Swastik Kopparty:
Explicit subspace designs. Comb. 36(2): 161-185 (2016) - [j66]Venkatesan Guruswami, Adam D. Smith:
Optimal Rate Code Constructions for Computationally Simple Channels. J. ACM 63(4): 35:1-35:37 (2016) - [j65]Venkatesan Guruswami, Euiwoong Lee:
Complexity of Approximating CSP with Balance / Hard Constraints. Theory Comput. Syst. 59(1): 76-98 (2016) - [j64]Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu:
Bypassing UGC from Some Optimal Geometric Inapproximability Results. ACM Trans. Algorithms 12(1): 6:1-6:25 (2016) - [j63]Mahdi Cheraghchi, Venkatesan Guruswami:
Capacity of Non-Malleable Codes. IEEE Trans. Inf. Theory 62(3): 1097-1118 (2016) - [j62]Venkatesan Guruswami, Carol Wang, Chaoping Xing:
Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs. IEEE Trans. Inf. Theory 62(5): 2707-2718 (2016) - [j61]Venkatesan Guruswami, Euiwoong Lee:
Simple Proof of Hardness of Feedback Vertex Set. Theory Comput. 12(1): 1-11 (2016) - 2015
- [j60]Venkatesan Guruswami, Chaoping Xing:
Optimal rate algebraic list decoding using narrow ray class fields. J. Comb. Theory, Ser. A 129: 160-183 (2015) - [j59]Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket:
Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs. SIAM J. Discret. Math. 29(1): 36-58 (2015) - [j58]Venkatesan Guruswami, Patrick Xia:
Polar Codes: Speed of Polarization and Polynomial Gap to Capacity. IEEE Trans. Inf. Theory 61(1): 3-16 (2015) - 2014
- [j57]Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou:
Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems. SIAM J. Optim. 24(4): 1698-1717 (2014) - [j56]Venkatesan Guruswami, Srivatsan Narayanan:
Combinatorial Limitations of Average-Radius List-Decoding. IEEE Trans. Inf. Theory 60(10): 5827-5842 (2014) - 2013
- [j55]Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker:
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. SIAM J. Comput. 42(5): 1888-1914 (2013) - [j54]Venkatesan Guruswami, Carol Wang:
Linear-Algebraic List Decoding for Variants of Reed-Solomon Codes. IEEE Trans. Inf. Theory 59(6): 3257-3268 (2013) - [j53]Venkatesan Guruswami, Ali Kemal Sinop:
Improved Inapproximability Results for Maximum k-Colorable Subgraph. Theory Comput. 9: 413-435 (2013) - 2012
- [j52]Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu:
Agnostic Learning of Monomials by Halfspaces Is Hard. SIAM J. Comput. 41(6): 1558-1590 (2012) - [j51]Venkatesan Guruswami, Yuan Zhou:
Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set. Theory Comput. 8(1): 239-267 (2012) - 2011
- [j50]Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth:
The query complexity of estimating weighted averages. Acta Informatica 48(7-8): 417-426 (2011) - [j49]Parikshit Gopalan, Venkatesan Guruswami:
Hardness amplification within NP against deterministic algorithms. J. Comput. Syst. Sci. 77(1): 107-121 (2011) - [j48]Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar:
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. SIAM J. Comput. 40(3): 878-914 (2011) - [j47]Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra:
List Decoding Tensor Products and Interleaved Codes. SIAM J. Comput. 40(5): 1432-1462 (2011) - [j46]Shuchi Chawla, Cynthia Dwork, Venkatesan Guruswami:
Special Section on the Fortieth Annual ACM Symposium On Theory Of Computing (STOC 2008). SIAM J. Comput. 40(6): 1738 (2011) - [j45]Venkatesan Guruswami, Atri Rudra:
Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes. IEEE Trans. Inf. Theory 57(2): 705-717 (2011) - [j44]Venkatesan Guruswami, Johan Håstad, Swastik Kopparty:
On the List-Decodability of Random Linear Codes. IEEE Trans. Inf. Theory 57(2): 718-725 (2011) - 2010
- [j43]Venkatesan Guruswami, James R. Lee, Alexander A. Razborov:
Almost Euclidean subspaces of l 1N VIA expander codes. Comb. 30(1): 47-68 (2010) - [j42]Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang:
Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs. Comb. 30(5): 485-520 (2010) - [j41]Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman:
Locally Testable Codes Require Redundant Testers. SIAM J. Comput. 39(7): 3230-3247 (2010) - [j40]Venkatesan Guruswami, Atri Rudra:
The existence of concatenated codes list-decodable up to the hamming bound. IEEE Trans. Inf. Theory 56(10): 5195-5206 (2010) - [j39]Venkatesan Guruswami, Salil P. Vadhan:
A Lower Bound on List Size for List Decoding. IEEE Trans. Inf. Theory 56(11): 5681-5688 (2010) - 2009
- [j38]Venkatesan Guruswami, Atri Rudra:
Error correction up to the information-theoretic limit. Commun. ACM 52(3): 87-95 (2009) - [j37]Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM 56(4): 20:1-20:34 (2009) - [j36]Venkatesan Guruswami, Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise. SIAM J. Comput. 39(2): 742-765 (2009) - [j35]Venkatesan Guruswami, Atri Rudra:
Better Binary List Decodable Codes Via Multilevel Concatenation. IEEE Trans. Inf. Theory 55(1): 19-26 (2009) - [j34]Venkatesan Guruswami, Prasad Raghavendra:
Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. ACM Trans. Comput. Theory 1(2): 6:1-6:20 (2009) - 2008
- [j33]Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton:
Algorithms for Modular Counting of Roots of Multivariate Polynomials. Algorithmica 50(4): 479-496 (2008) - [j32]Venkatesan Guruswami, Valentine Kabanets:
Hardness Amplification via Space-Efficient Direct Products. Comput. Complex. 17(4): 475-500 (2008) - [j31]Venkatesan Guruswami, Anindya C. Patthak:
Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets. Math. Comput. 77(261): 447-473 (2008) - [j30]Venkatesan Guruswami, Atri Rudra:
Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy. IEEE Trans. Inf. Theory 54(1): 135-150 (2008) - 2007
- [j29]Venkatesan Guruswami, Valentine Kabanets:
Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword. Comput. Complex. 16(2): 113-114 (2007) - [j28]Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan:
Guessing secrets efficiently via list decoding. ACM Trans. Algorithms 3(4): 42 (2007) - 2006
- [j27]Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes. Bull. EATCS 90: 53-88 (2006) - [j26]Venkatesan Guruswami:
Algorithmic Results in List Decoding. Found. Trends Theor. Comput. Sci. 2(2) (2006) - [j25]Venkatesan Guruswami, Atri Rudra:
Limits to List Decoding Reed-Solomon Codes. IEEE Trans. Inf. Theory 52(8): 3642-3649 (2006) - [j24]Ioannis Giotis, Venkatesan Guruswami:
Correlation Clustering with a Fixed Number of Clusters. Theory Comput. 2(13): 249-266 (2006) - 2005
- [j23]Venkatesan Guruswami, Daniele Micciancio, Oded Regev:
The complexity of the covering radius problem. Comput. Complex. 14(2): 90-121 (2005) - [j22]Moses Charikar, Venkatesan Guruswami, Anthony Wirth:
Clustering with qualitative information. J. Comput. Syst. Sci. 71(3): 360-383 (2005) - [j21]Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev:
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. SIAM J. Comput. 34(5): 1129-1146 (2005) - [j20]Venkatesan Guruswami, Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. IEEE Trans. Inf. Theory 51(7): 2249-2256 (2005) - [j19]Venkatesan Guruswami, Piotr Indyk:
Linear-time encodable/decodable codes with near-optimal rate. IEEE Trans. Inf. Theory 51(10): 3393-3400 (2005) - 2004
- [j18]Venkatesan Guruswami:
Inapproximability Results for Set Splitting and Satisfiability Problems with No Mixed Clauses. Algorithmica 38(3): 451-469 (2004) - [j17]Edith Cohen, Venkatesan Guruswami:
Guest Editors' foreword. J. Comput. Syst. Sci. 68(4): 701 (2004) - [j16]Lars Engebretsen, Venkatesan Guruswami:
Is constraint satisfaction over two variables always easy? Random Struct. Algorithms 25(2): 150-178 (2004) - [j15]Venkatesan Guruswami, Sanjeev Khanna:
On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM J. Discret. Math. 18(1): 30-40 (2004) - [j14]Venkatesan Guruswami:
Guest column: error-correcting codes and expander graphs. SIGACT News 35(3): 25-41 (2004) - 2003
- [j13]Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis:
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3): 473-496 (2003) - [j12]Venkatesan Guruswami:
Constructions of codes from number fields. IEEE Trans. Inf. Theory 49(3): 594-603 (2003) - [j11]Venkatesan Guruswami:
List decoding from erasures: bounds and code constructions. IEEE Trans. Inf. Theory 49(11): 2826-2833 (2003) - 2002
- [j10]Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai:
Query Strategies for Priced Information. J. Comput. Syst. Sci. 64(4): 785-819 (2002) - [j9]Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
Hardness of Approximate Hypergraph Coloring. SIAM J. Comput. 31(6): 1663-1686 (2002) - [j8]Venkatesan Guruswami, Johan Håstad, Madhu Sudan, David Zuckerman:
Combinatorial bounds for list decoding. IEEE Trans. Inf. Theory 48(5): 1021-1034 (2002) - 2001
- [j7]Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong:
The Kr-Packing Problem. Computing 66(1): 79-89 (2001) - [j6]Venkatesan Guruswami, Madhu Sudan:
On representations of algebraic-geometry codes. IEEE Trans. Inf. Theory 47(4): 1610-1613 (2001) - 2000
- [j5]Venkatesan Guruswami, C. Pandu Rangan:
Algorithmic aspects of clique-transversal and clique-independent sets. Discret. Appl. Math. 100(3): 183-202 (2000) - 1999
- [j4]Venkatesan Guruswami:
Maximum Cut on Line and Total Graphs. Discret. Appl. Math. 92(2-3): 217-221 (1999) - [j3]Venkatesan Guruswami:
Enumerative aspects of certain subclasses of perfect graphs. Discret. Math. 205(1-3): 97-117 (1999) - [j2]Venkatesan Guruswami, Madhu Sudan:
Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Trans. Inf. Theory 45(6): 1757-1767 (1999) - 1998
- [j1]Venkatesan Guruswami, C. Pandu Rangan:
A Natural Family of Optimization Problems with Arbitrarily Small Approximation Thresholds. Inf. Process. Lett. 68(5): 241-248 (1998)
Conference and Workshop Papers
- 2024
- [c193]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 - 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 - 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 - 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 - 2020
- [c162]Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters:
Bounds for List-Decoding and List-Recovery of Random Linear Codes. APPROX-RANDOM 2020: 9:1-9:21 - [c161]Venkatesan Guruswami, Jakub Oprsal, Sai Sandeep:
Revisiting Alphabet Reduction in Dinur's PCP. APPROX-RANDOM 2020: 34:1-34:14 - [c160]Venkatesan Guruswami, Sai Sandeep:
d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors. ICALP 2020: 62:1-62:12 - [c159]Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang:
Leakage-Resilient Secret Sharing in Non-Compartmentalized Models. ITC 2020: 7:1-7:24 - [c158]Joshua Brakensiek, Venkatesan Guruswami:
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. SODA 2020: 297-304 - [c157]Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi:
Optimally resilient codes for list-decoding from insertions and deletions. STOC 2020: 524-537 - [c156]Venkatesan Guruswami, Andrii Riazanov, Min Ye:
Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity. STOC 2020: 552-564 - 2019
- [c155]Venkatesan Guruswami, Runzhou Tao:
Streaming Hardness of Unique Games. APPROX-RANDOM 2019: 5:1-5:12 - [c154]Venkatesan Guruswami, Sai Sandeep:
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms. APPROX-RANDOM 2019: 15:1-15:17 - [c153]Venkatesan Guruswami, Lingfei Jin, Chaoping Xing:
Constructions of Maximally Recoverable Local Reconstruction Codes via Function Fields. ICALP 2019: 68:1-68:14 - [c152]Venkatesan Guruswami, Andrii Riazanov:
Beating Fredman-Komlós for Perfect k-Hashing. ICALP 2019: 92:1-92:14 - [c151]Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan:
Algorithmic Polarization for Hidden Markov Models. ITCS 2019: 39:1-39:19 - [c150]Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang:
Secret Sharing with Binary Shares. ITCS 2019: 53:1-53:20 - [c149]Venkatesan Guruswami, Haotian Jiang:
Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization. ISIT 2019: 1077-1081 - [c148]Joshua Brakensiek, Venkatesan Guruswami:
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. SODA 2019: 436-455 - [c147]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Approximability of p → q Matrix Norms: Generalized Krivine Rounding and Hypercontractive Hardness. SODA 2019: 1358-1368 - [c146]Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin:
Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities. SODA 2019: 2154-2170 - [c145]Joshua Brakensiek, Venkatesan Guruswami:
Bridging between 0/1 and linear programming via random walks. STOC 2019: 568-577 - [c144]Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami:
CSPs with global modular constraints: algorithms and hardness via polynomial representations. STOC 2019: 590-601 - [c143]Omar Alrabiah, Venkatesan Guruswami:
An exponential lower bound on the sub-packetization of MSR codes. STOC 2019: 979-985 - 2018
- [c142]Allison Beemer, Ryan Coatney, Venkatesan Guruswami, Hiram H. Lopez, Fernando Piñero:
Explicit optimal-length locally repairable codes of distance 5. Allerton 2018: 800-804 - [c141]Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan:
Polar Codes with Exponentially Small Error at Finite Block Length. APPROX-RANDOM 2018: 34:1-34:17 - [c140]Venkatesan Guruswami, Chaoping Xing, Chen Yuan:
How Long Can Optimal Locally Repairable Codes Be?. APPROX-RANDOM 2018: 41:1-41:11 - [c139]Venkatesan Guruswami, Nicolas Resch, Chaoping Xing:
Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs. CCC 2018: 4:1-4:16 - [c138]Venkatesan Guruswami, Nicolas Resch:
On the List-Decodability of Random Linear Rank-Metric Codes. ISIT 2018: 1505-1509 - [c137]Venkatesan Guruswami, Satyanarayana V. Lokam, Sai Vikneshwar Mani Jayaraman:
∊-MSR Codes: Contacting Fewer Code Blocks for Exact Repair. ISIT 2018: 2371-2375 - [c136]Venkatesan Guruswami, Ray Li:
Coding against deletions in oblivious and online models. SODA 2018: 625-643 - [c135]Joshua Brakensiek, Venkatesan Guruswami:
Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy. SODA 2018: 1782-1801 - [c134]Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan:
General strong polarization. STOC 2018: 485-492 - 2017
- [c133]Joshua Brakensiek, Venkatesan Guruswami:
The Quest for Strong Inapproximability Results with Perfect Completeness. APPROX-RANDOM 2017: 4:1-4:20 - [c132]Venkatesan Guruswami, Ameya Velingker, Santhoshini Velusamy:
Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph. APPROX-RANDOM 2017: 8:1-8:19 - [c131]Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee:
Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. APPROX-RANDOM 2017: 31:1-31:20 - [c130]S. Luna Frank-Fischer, Venkatesan Guruswami, Mary Wootters:
Locality via Partially Lifted Codes. APPROX-RANDOM 2017: 43:1-43:17 - [c129]Venkatesan Guruswami, Ray Li:
Efficiently Decodable Codes for the Binary Deletion Channel. APPROX-RANDOM 2017: 47:1-47:13 - [c128]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. FOCS 2017: 1008-1019 - [c127]Venkatesan Guruswami, Rishi Saket:
Hardness of Rainbow Coloring Hypergraphs. FSTTCS 2017: 33:33-33:15 - [c126]Venkatesan Guruswami, Chaoping Xing, Chen Yuan:
Subspace Designs Based on Algebraic Function Fields. ICALP 2017: 86:1-86:10 - [c125]Marco Dalai, Venkatesan Guruswami, Jaikumar Radhakrishnan:
An improved bound on the zero-error list-decoding capacity of the 4/3 channel. ISIT 2017: 1658-1662 - [c124]Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko:
∊-MSR codes with small sub-packetization. ISIT 2017: 2043-2047 - [c123]Venkatesan Guruswami, Ankit Singh Rawat:
MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth. SODA 2017: 2109-2122 - 2016
- [c122]Venkatesan Guruswami, Jaikumar Radhakrishnan:
Tight Bounds for Communication-Assisted Agreement Distillation. CCC 2016: 6:1-6:17 - [c121]Joshua Brakensiek, Venkatesan Guruswami:
New Hardness Results for Graph and Hypergraph Colorings. CCC 2016: 14:1-14:27 - [c120]Venkatesan Guruswami, David Zuckerman:
Robust Fourier and Polynomial Curve Fitting. FOCS 2016: 751-759 - [c119]Venkatesan Guruswami, Ray Li:
Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes. ISIT 2016: 620-624 - [c118]Venkatesan Guruswami, Euiwoong Lee:
Nearly Optimal NP-Hardness of Unique Coverage. SODA 2016: 1724-1730 - [c117]Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky:
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. SODA 2016: 1884-1892 - [c116]Boris Bukh, Venkatesan Guruswami:
An improved bound on the fraction of correctable deletions. SODA 2016: 1893-1901 - [c115]Venkatesan Guruswami, Mary Wootters:
Repairing Reed-solomon codes. STOC 2016: 216-226 - 2015
- [c114]Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee:
Approximate Hypergraph Coloring under Low-discrepancy and Related Promises. APPROX-RANDOM 2015: 152-174 - [c113]Venkatesan Guruswami, Euiwoong Lee:
Inapproximability of H-Transversal/Packing. APPROX-RANDOM 2015: 284-304 - [c112]Venkatesan Guruswami, Euiwoong Lee:
Towards a Characterization of Approximation Resistance for Symmetric CSPs. APPROX-RANDOM 2015: 305-322 - [c111]Michael A. Forbes, Venkatesan Guruswami:
Dimension Expanders via Rank Condensers. APPROX-RANDOM 2015: 800-814 - [c110]Venkatesan Guruswami, Carol Wang:
Deletion Codes in the High-noise and High-rate Regimes. APPROX-RANDOM 2015: 867-880 - [c109]Venkatesan Guruswami, Ameya Velingker:
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. CCC 2015: 42-57 - [c108]Clément Louis Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan:
Communication with Imperfectly Shared Randomness. ITCS 2015: 257-262 - [c107]Venkatesan Guruswami, Euiwoong Lee:
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. SODA 2015: 822-836 - [c106]Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang:
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. SODA 2015: 1312-1325 - 2014
- [c105]Venkatesan Guruswami, Carol Wang:
Evading Subspaces Over Large Fields and Explicit List-decodable Rank-metric Codes. APPROX-RANDOM 2014: 748-761 - [c104]Venkatesan Guruswami, Chaoping Xing:
Hitting Sets for Low-Degree Polynomials with Optimal Density. CCC 2014: 161-168 - [c103]Per Austrin, Johan Håstad, Venkatesan Guruswami:
(2 + epsilon)-Sat Is NP-Hard. FOCS 2014: 1-10 - [c102]Mahdi Cheraghchi, Venkatesan Guruswami:
Capacity of non-malleable codes. ITCS 2014: 155-168 - [c101]Venkatesan Guruswami, Euiwoong Lee:
Complexity of approximating CSP with balance / hard constraints. ITCS 2014: 439-448 - [c100]Venkatesan Guruswami, Chaoping Xing:
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. SODA 2014: 1858-1866 - [c99]Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma:
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. STOC 2014: 614-623 - [c98]Mahdi Cheraghchi, Venkatesan Guruswami:
Non-malleable Coding against Bit-Wise and Split-State Tampering. TCC 2014: 440-464 - 2013
- [c97]Venkatesan Guruswami, Srivatsan Narayanan:
Combinatorial Limitations of Average-Radius List Decoding. APPROX-RANDOM 2013: 591-606 - [c96]Venkatesan Guruswami, Krzysztof Onak:
Superlinear Lower Bounds for Multipass Graph Processing. CCC 2013: 287-298 - [c95]Venkatesan Guruswami, Patrick Xia:
Polar Codes: Speed of Polarization and Polynomial Gap to Capacity. FOCS 2013: 310-319 - [c94]Irit Dinur, Venkatesan Guruswami:
PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring. FOCS 2013: 340-349 - [c93]Venkatesan Guruswami, Swastik Kopparty:
Explicit Subspace Designs. FOCS 2013: 608-617 - [c92]Venkatesan Guruswami:
Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity (Invited Talk). FSTTCS 2013: 1-1 - [c91]Venkatesan Guruswami, Ali Kemal Sinop:
Approximating Non-Uniform Sparsest Cut Via Generalized Spectra. SODA 2013: 295-305 - [c90]Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker:
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. SODA 2013: 432-442 - [c89]Venkatesan Guruswami, Chaoping Xing:
List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound. STOC 2013: 843-852 - [c88]Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, Christos Faloutsos:
CopyCatch: stopping group attacks by spotting lockstep behavior in social networks. WWW 2013: 119-130 - 2012
- [c87]Venkatesan Guruswami, Yuan Zhou:
Approximating Bounded Occurrence Ordering CSPs. APPROX-RANDOM 2012: 158-169 - [c86]Venkatesan Guruswami, Ali Kemal Sinop:
Faster SDP Hierarchy Solvers for Local Rounding Algorithms. FOCS 2012: 197-206 - [c85]Venkatesan Guruswami, Srivatsan Narayanan, Carol Wang:
List decoding subspace codes from insertions and deletions. ITCS 2012: 183-189 - [c84]Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou:
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. SODA 2012: 388-405 - [c83]Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu:
Bypassing UGC from some optimal geometric inapproximability results. SODA 2012: 699-717 - [c82]Venkatesan Guruswami, Ali Kemal Sinop:
Optimal column-based low-rank matrix reconstruction. SODA 2012: 1207-1214 - [c81]Venkatesan Guruswami, Chaoping Xing:
Folded codes from function field towers and improved optimal rate list decoding. STOC 2012: 339-350 - 2011
- [c80]Venkatesan Guruswami, Carol Wang:
Optimal Rate List Decoding via Derivative Codes. APPROX-RANDOM 2011: 593-604 - [c79]Venkatesan Guruswami:
Linear-Algebraic List Decoding of Folded Reed-Solomon Codes. CCC 2011: 77-85 - [c78]Venkatesan Guruswami, Ali Kemal Sinop:
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. FOCS 2011: 482-491 - [c77]Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou:
Finding Almost-Perfect Graph Bisections. ICS 2011: 321-337 - [c76]Venkatesan Guruswami, Yuan Zhou:
Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set. SODA 2011: 1574-1589 - [c75]Venkatesan Guruswami, Ali Kemal Sinop:
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. SODA 2011: 1615-1626 - 2010
- [c74]Venkatesan Guruswami, Adam D. Smith:
Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. FOCS 2010: 723-732 - [c73]Venkatesan Guruswami, Rishi Saket:
On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs. ICALP (1) 2010: 360-371 - [c72]Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu:
SDP Gaps for 2-to-1 and Other Label-Cover Variants. ICALP (1) 2010: 617-628 - [c71]Venkatesan Guruswami, Johan Håstad, Swastik Kopparty:
On the list-decodability of random linear codes. STOC 2010: 409-416 - 2009
- [c70]Venkatesan Guruswami, James R. Lee, Avi Wigderson:
Expander codes over reals, Euclidean sections, and compressed sensing. Allerton 2009: 1231-1234 - [c69]Venkatesan Guruswami, Ali Kemal Sinop:
Improved Inapproximability Results for Maximum k-Colorable Subgraph. APPROX-RANDOM 2009: 163-176 - [c68]Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman:
Locally Testable Codes Require Redundant Testers. CCC 2009: 52-61 - [c67]Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran:
Every Permutation CSP of arity 3 is Approximation Resistant. CCC 2009: 62-73 - [c66]Venkatesan Guruswami:
List Decoding of Binary Codes-A Brief Survey of Some Recent Results. IWCC 2009: 97-106 - [c65]Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu:
Agnostic Learning of Monomials by Halfspaces Is Hard. FOCS 2009: 385-394 - [c64]Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra:
List decoding tensor products and interleaved codes. STOC 2009: 13-22 - [c63]Venkatesan Guruswami:
Artin automorphisms, cyclotomic function fields, and folded list-decodable codes. STOC 2009: 23-32 - [c62]MohammadHossein Bateni, Moses Charikar, Venkatesan Guruswami:
MaxMin allocation via degree lower-bounded arborescences. STOC 2009: 543-552 - 2008
- [c61]Venkatesan Guruswami, Prasad Raghavendra:
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness. APPROX-RANDOM 2008: 77-90 - [c60]Venkatesan Guruswami, James R. Lee, Avi Wigderson:
Euclidean Sections of with Sublinear Randomness and Error-Correction over the Reals. APPROX-RANDOM 2008: 444-454 - [c59]Parikshit Gopalan, Venkatesan Guruswami:
Hardness Amplification within NP against Deterministic Algorithms. CCC 2008: 19-30 - [c58]Venkatesan Guruswami, Atri Rudra:
Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes. CCC 2008: 163-174 - [c57]Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra:
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. FOCS 2008: 573-582 - [c56]Venkatesan Guruswami:
List Error-Correction with Optimal Information Rate (Invited Talk). ICITS 2008: 118-119 - [c55]Venkatesan Guruswami, Widad Machmouchi:
Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction. ISIT 2008: 1968-1972 - [c54]Venkatesan Guruswami, Atri Rudra:
Concatenated codes can achieve list-decoding capacity. SODA 2008: 258-267 - [c53]Venkatesan Guruswami, James R. Lee, Alexander A. Razborov:
Almost Euclidean subspaces of lN1 via expander codes. SODA 2008: 353-362 - 2007
- [c52]Venkatesan Guruswami:
List Decoding and Pseudorandom Constructions. AAECC 2007: 1-6 - [c51]Venkatesan Guruswami, Atri Rudra:
Better Binary List-Decodable Codes Via Multilevel Concatenation. APPROX-RANDOM 2007: 554-568 - [c50]Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. CCC 2007: 96-108 - [c49]Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar:
Hardness of routing with congestion in directed graphs. STOC 2007: 165-178 - [c48]Venkatesan Guruswami, Prasad Raghavendra:
A 3-query PCP over integers. STOC 2007: 198-206 - 2006
- [c47]Venkatesan Guruswami, Anindya C. Patthak:
Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. FOCS 2006: 227-238 - [c46]Venkatesan Guruswami, Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise. FOCS 2006: 543-552 - [c45]Venkatesan Guruswami:
On 2-Query Codeword Testing with Near-Perfect Completeness. ISAAC 2006: 267-276 - [c44]Venkatesan Guruswami:
List Decoding in Average-Case Complexity and Pseudorandomness. ITW 2006: 32-36 - [c43]Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton:
Algorithms for Modular Counting of Roots of Multivariate Polynomials. LATIN 2006: 544-555 - [c42]Venkatesan Guruswami, Valentine Kabanets:
Hardness Amplification Via Space-Efficient Direct Products. LATIN 2006: 556-568 - [c41]Ioannis Giotis, Venkatesan Guruswami:
Correlation clustering with a fixed number of clusters. SODA 2006: 1167-1176 - [c40]Venkatesan Guruswami, Atri Rudra:
Explicit capacity-achieving list-decodable codes. STOC 2006: 1-10 - 2005
- [c39]Venkatesan Guruswami, Luca Trevisan:
The Complexity of Making Unique Choices: Approximating 1-in- k SAT. APPROX-RANDOM 2005: 99-110 - [c38]Venkatesan Guruswami, Atri Rudra:
Tolerant Locally Testable Codes. APPROX-RANDOM 2005: 306-317 - [c37]Venkatesan Guruswami, Salil P. Vadhan:
A Lower Bound on List Size for List Decoding. APPROX-RANDOM 2005: 318-329 - [c36]Venkatesan Guruswami, Subhash Khot:
Hardness of Max 3SAT with No Mixed Clauses. CCC 2005: 154-162 - [c35]Venkatesan Guruswami, Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. SODA 2005: 470-478 - [c34]Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry:
On profit-maximizing envy-free pricing. SODA 2005: 1164-1173 - [c33]Venkatesan Guruswami, Atri Rudra:
Limits to list decoding Reed-Solomon codes. STOC 2005: 602-609 - 2004
- [c32]Venkatesan Guruswami, Daniele Micciancio, Oded Regev:
The Complexity of the Covering Radius Problem on Lattices and Codes. CCC 2004: 161-173 - [c31]Venkatesan Guruswami, Piotr Indyk:
Linear-Time List Decoding in Error-Free Settings: (Extended Abstract). ICALP 2004: 695-707 - [c30]Venkatesan Guruswami, Piotr Indyk:
Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. SODA 2004: 756-757 - [c29]Venkatesan Guruswami:
Better extractors for better codes? STOC 2004: 436-444 - 2003
- [c28]Venkatesan Guruswami:
List Decoding with Side Information. CCC 2003: 300- - [c27]Moses Charikar, Venkatesan Guruswami, Anthony Wirth:
Clustering with Qualitative Information. FOCS 2003: 524-533 - [c26]Venkatesan Guruswami, Piotr Indyk:
Embeddings and non-approximability of geometric problems. SODA 2003: 537-538 - [c25]Venkatesan Guruswami, Igor E. Shparlinski:
Unconditional proof of tightness of Johnson bound. SODA 2003: 754-755 - [c24]Venkatesan Guruswami, Piotr Indyk:
Linear time encodable and list decodable codes. STOC 2003: 126-135 - [c23]Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev:
A new multilayered PCP and the hardness of hypergraph vertex cover. STOC 2003: 595-601 - 2002
- [c22]Venkatesan Guruswami, Madhu Sudan:
Decoding Concatenated Codes using Soft Information. CCC 2002: 148-157 - [c21]Lars Engebretsen, Venkatesan Guruswami:
Is Constraint Satisfaction Over Two Variables Always Easy? RANDOM 2002: 224-238 - [c20]Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan:
Guessing secrets efficiently via list decoding. SODA 2002: 254-262 - [c19]Venkatesan Guruswami:
Limits to list decodability of linear codes. STOC 2002: 802-811 - [c18]Venkatesan Guruswami, Piotr Indyk:
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. STOC 2002: 812-821 - 2001
- [c17]Venkatesan Guruswami:
Constructions of Codes from Number Fields. AAECC 2001: 129-140 - [c16]Venkatesan Guruswami, Piotr Indyk:
Expander-Based Constructions of Efficiently Decodable Codes. FOCS 2001: 658-667 - [c15]Venkatesan Guruswami:
List Decoding from Erasures: Bounds and Code Constructions. FSTTCS 2001: 195-206 - 2000
- [c14]Venkatesan Guruswami:
Inapproximability results for set splitting and satisfiability problems with no mixed clauses. APPROX 2000: 155-166 - [c13]Venkatesan Guruswami, Sanjeev Khanna:
On the Hardness of 4-Coloring a 3-Colorable Graph. CCC 2000: 188-197 - [c12]Venkatesan Guruswami, Madhu Sudan:
On Representations of Algebraic-Geometric Codes for List Decoding. ESA 2000: 244-255 - [c11]Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
Hardness of Approximate Hypergraph Coloring. FOCS 2000: 149-158 - [c10]Venkatesan Guruswami, Amit Sahai, Madhu Sudan:
"Soft-decision" Decoding of Chinese Remainder Codes. FOCS 2000: 159-168 - [c9]Moses Charikar, Venkatesan Guruswami, Ravi Kumar, Sridhar Rajagopalan, Amit Sahai:
Combinatorial feature selection problems. FOCS 2000: 631-640 - [c8]Venkatesan Guruswami, Madhu Sudan:
List decoding algorithms for certain concatenated codes. STOC 2000: 181-190 - [c7]Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon M. Kleinberg, Prabhakar Raghavan, Amit Sahai:
Query strategies for priced information (extended abstract). STOC 2000: 582-591 - 1999
- [c6]Venkatesan Guruswami, Amit Sahai:
Multiclass Learning, Boosting, and Error-Correcting Codes. COLT 1999: 145-155 - [c5]Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna:
The 2-Catalog Segmentation Problem. SODA 1999: 897-898 - [c4]Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis:
Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. STOC 1999: 19-28 - 1998
- [c3]Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan:
A Tight Characterization of NP with 3 Query PCPs. FOCS 1998: 8-17 - [c2]Venkatesan Guruswami, Madhu Sudan:
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. FOCS 1998: 28-39 - [c1]Venkatesan Guruswami, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, C. K. Wong:
The Vertex-Disjoint Triangles Problem. WG 1998: 26-37
Editorship
- 2024
- [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] - 2022
- [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] - 2015
- [e1]Venkatesan Guruswami:
IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. IEEE Computer Society 2015, ISBN 978-1-4673-8191-8 [contents]
Reference Works
- 2016
- [r2]Venkatesan Guruswami:
Decoding Reed-Solomon Codes. Encyclopedia of Algorithms 2016: 502-506 - 2008
- [r1]Venkatesan Guruswami:
Decoding Reed-Solomon Codes. Encyclopedia of Algorithms 2008
Informal and Other Publications
- 2024
- [i228]Vipul Arora, Arnab Bhattacharyya, Mathews Boban, Venkatesan Guruswami, Esty Kelman:
Outlier Robust Multivariate Polynomial Regression. CoRR abs/2403.09465 (2024) - [i227]Venkatesan Guruswami, Rishi Saket:
Hardness of Learning Boolean Functions from Label Proportions. CoRR abs/2403.19401 (2024) - 2023
- [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
- [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
- [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
- [i185]Michael Rudow, K. V. Rashmi, Venkatesan Guruswami:
A locality-based approach for coded computation. CoRR abs/2002.02440 (2020) - [i184]Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters:
Bounds for list-decoding and list-recovery of random linear codes. CoRR abs/2004.13247 (2020) - [i183]Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li:
Efficient Linear and Affine Codes for Correcting Insertions/Deletions. CoRR abs/2007.09075 (2020) - [i182]Venkatesan Guruswami, Johan Håstad:
Explicit two-deletion codes with redundancy matching the existential bound. CoRR abs/2007.10592 (2020) - [i181]Venkatesan Guruswami, Sai Sandeep:
An Algorithmic Study of the Hypergraph Turán Problem. CoRR abs/2008.07344 (2020) - [i180]Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters:
Sharp threshold rates for random codes. CoRR abs/2009.04553 (2020) - [i179]Venkatesan Guruswami, Andrii Riazanov:
Linear Shannon Capacity of Cayley Graphs. CoRR abs/2009.05685 (2020) - [i178]Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari:
Strongly refuting all semi-random Boolean CSPs. CoRR abs/2009.08032 (2020) - [i177]Sivakanth Gopi, Venkatesan Guruswami:
Improved Maximally Recoverable LRCs using Skew Polynomials. CoRR abs/2012.07804 (2020) - [i176]Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný:
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. Electron. Colloquium Comput. Complex. TR20 (2020) - [i175]Venkatesan Guruswami, Vinayak Kumar:
Pseudobinomiality of the Sticky Random Walk. Electron. Colloquium Comput. Complex. TR20 (2020) - [i174]Venkatesan Guruswami, Sai Sandeep:
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture. Electron. Colloquium Comput. Complex. TR20 (2020) - [i173]Venkatesan Guruswami, Chaoping Xing:
Optimal rate list decoding over bounded alphabets using algebraic-geometric codes. Electron. Colloquium Comput. Complex. TR20 (2020) - 2019
- [i172]Omar Alrabiah, Venkatesan Guruswami:
An Exponential Lower Bound on the Sub-Packetization of MSR Codes. CoRR abs/1901.05112 (2019) - [i171]Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami:
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. CoRR abs/1902.04740 (2019) - [i170]Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang:
Non-Malleable Secret Sharing against Affine Tampering. CoRR abs/1902.06195 (2019) - [i169]Joshua Brakensiek, Venkatesan Guruswami:
Bridging between 0/1 and Linear Programming via Random Walks. CoRR abs/1904.04860 (2019) - [i168]Venkatesan Guruswami, Haotian Jiang:
Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization. CoRR abs/1907.03931 (2019) - [i167]Joshua Brakensiek, Venkatesan Guruswami:
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. CoRR abs/1907.04383 (2019) - [i166]Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi:
Optimally Resilient Codes for List-Decoding from Insertions and Deletions. CoRR abs/1909.10683 (2019) - [i165]Venkatesan Guruswami, Andrii Riazanov, Min Ye:
Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity. CoRR abs/1911.03858 (2019) - [i164]Omar Alrabiah, Venkatesan Guruswami:
An Exponential Lower Bound on the Sub-Packetization of MSR Codes. Electron. Colloquium Comput. Complex. TR19 (2019) - [i163]Joshua Brakensiek, Venkatesan Guruswami:
Bridging between 0/1 and Linear Programming via Random Walks. Electron. Colloquium Comput. Complex. TR19 (2019) - [i162]Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami:
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. Electron. Colloquium Comput. Complex. TR19 (2019) - [i161]Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi:
Optimally Resilient Codes for List-Decoding from Insertions and Deletions. Electron. Colloquium Comput. Complex. TR19 (2019) - [i160]Venkatesan Guruswami, Jakub Oprsal, Sai Sandeep:
Revisiting Alphabet Reduction in Dinur's PCP. Electron. Colloquium Comput. Complex. TR19 (2019) - [i159]Venkatesan Guruswami, Andrii Riazanov, Min Ye:
Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity. Electron. Colloquium Comput. Complex. TR19 (2019) - [i158]Venkatesan Guruswami, Sai Sandeep:
Rainbow coloring hardness via low sensitivity polymorphisms. Electron. Colloquium Comput. Complex. TR19 (2019) - [i157]Venkatesan Guruswami, Sai Sandeep:
$d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [i156]Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan:
General Strong Polarization. CoRR abs/1802.02718 (2018) - [i155]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Inapproximability of Matrix p→q Norms. CoRR abs/1802.07425 (2018) - [i154]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Approximating Operator Norms via Generalized Krivine Rounding. CoRR abs/1804.03644 (2018) - [i153]Venkatesan Guruswami, Andrii Riazanov:
Beating Fredman-Komlós for perfect k-hashing. CoRR abs/1805.04151 (2018) - [i152]Venkatesan Guruswami, Chaoping Xing, Chen Yuan:
How long can optimal locally repairable codes be? CoRR abs/1807.01064 (2018) - [i151]Venkatesan Guruswami, Satyanarayana V. Lokam, Sai Vikneshwar Mani Jayaraman:
ε-MSR Codes: Contacting Fewer Code Blocks for Exact Repair. CoRR abs/1807.01166 (2018) - [i150]Joshua Brakensiek, Venkatesan Guruswami:
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. CoRR abs/1807.05194 (2018) - [i149]Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang:
Secret Sharing with Binary Shares. CoRR abs/1808.02974 (2018) - [i148]Venkatesan Guruswami, Lingfei Jin, Chaoping Xing:
Constructions of maximally recoverable local reconstruction codes via function fields. CoRR abs/1808.04539 (2018) - [i147]Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan:
Algorithmic Polarization for Hidden Markov Models. CoRR abs/1810.01969 (2018) - [i146]Allison Beemer, Ryan Coatney, Venkatesan Guruswami, Hiram H. López, Fernando Piñero:
Explicit optimal-length locally repairable codes of distance 5. CoRR abs/1810.03980 (2018) - [i145]Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan:
Polar Codes with exponentially small error at finite block length. CoRR abs/1810.04298 (2018) - [i144]Venkatesan Guruswami, Runzhou Tao:
Streaming Hardness of Unique Games. CoRR abs/1811.04607 (2018) - [i143]Martin Grohe, Venkatesan Guruswami, Stanislav Zivný:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231). Dagstuhl Reports 8(6): 1-18 (2018) - [i142]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Inapproximability of Matrix p→q Norms. Electron. Colloquium Comput. Complex. TR18 (2018) - [i141]Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Approximating Operator Norms via Generalized Krivine Rounding. Electron. Colloquium Comput. Complex. TR18 (2018) - [i140]Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan:
General Strong Polarization. Electron. Colloquium Comput. Complex. TR18 (2018) - [i139]Joshua Brakensiek, Venkatesan Guruswami:
Combining LPs and Ring Equations via Structured Polymorphisms. Electron. Colloquium Comput. Complex. TR18 (2018) - [i138]Venkatesan Guruswami, Andrii Riazanov:
Beating Fredman-Komlós for perfect k-hashing. Electron. Colloquium Comput. Complex. TR18 (2018) - [i137]Venkatesan Guruswami, Nicolas Resch, Chaoping Xing:
Lossless dimension expanders via linearized polynomials and subspace designs. Electron. Colloquium Comput. Complex. TR18 (2018) - [i136]Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang:
Secret Sharing with Binary Shares. IACR Cryptol. ePrint Arch. 2018: 746 (2018) - 2017
- [i135]Joshua Brakensiek, Venkatesan Guruswami:
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. CoRR abs/1704.01937 (2017) - [i134]Venkatesan Guruswami, Chaoping Xing, Chen Yuan:
Subspace Designs based on Algebraic Function Fields. CoRR abs/1704.05992 (2017) - [i133]S. Luna Frank-Fischer, Venkatesan Guruswami, Mary Wootters:
Locality via Partially Lifted Codes. CoRR abs/1704.08627 (2017) - [i132]Venkatesan Guruswami, Ray Li:
Efficiently decodable codes for the binary deletion channel. CoRR abs/1705.01963 (2017) - [i131]Venkatesan Guruswami, Chaoping Xing:
Optimal rate list decoding over bounded alphabets using algebraic-geometric codes. CoRR abs/1708.01070 (2017) - [i130]Ankit Singh Rawat, Itzhak Tamo, Venkatesan Guruswami, Klim Efremenko:
MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth. CoRR abs/1709.08216 (2017) - [i129]Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin:
On Maximally Recoverable Local Reconstruction Codes. CoRR abs/1710.10322 (2017) - [i128]Venkatesan Guruswami, Nicolas Resch:
On the List-Decodability of Random Linear Rank-Metric Codes. CoRR abs/1710.11516 (2017) - [i127]Joshua Brakensiek, Venkatesan Guruswami:
The Quest for Strong Inapproximability Results with Perfect Completeness. Electron. Colloquium Comput. Complex. TR17 (2017) - [i126]Joshua Brakensiek, Venkatesan Guruswami:
A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover. Electron. Colloquium Comput. Complex. TR17 (2017) - [i125]Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin:
On Maximally Recoverable Local Reconstruction Codes. Electron. Colloquium Comput. Complex. TR17 (2017) - [i124]Venkatesan Guruswami, Rishi Saket:
Hardness of Rainbow Coloring Hypergraphs. Electron. Colloquium Comput. Complex. TR17 (2017) - [i123]Venkatesan Guruswami, Chaoping Xing, Chen Yuan:
Subspace Designs based on Algebraic Function Fields. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i122]Venkatesan Guruswami:
Rapidly Mixing Markov Chains: A Comparison of Techniques (A Survey). CoRR abs/1603.01512 (2016) - [i121]Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee:
Certifying Random Polynomials over the Unit Sphere via Sum of Squares Hierarchy. CoRR abs/1605.00903 (2016) - [i120]Venkatesan Guruswami, Ray Li:
Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes. CoRR abs/1605.04611 (2016) - [i119]Venkatesan Guruswami, Ankit Singh Rawat:
New MDS codes with small sub-packetization and near-optimal repair bandwidth. CoRR abs/1608.00191 (2016) - [i118]Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Euiwoong Lee, Venkatesan Guruswami, Madhur Tulsiani:
Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. CoRR abs/1611.05998 (2016) - [i117]Venkatesan Guruswami, Ray Li:
Codes correcting deletions in oblivious and random models. CoRR abs/1612.06335 (2016) - [i116]Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. Electron. Colloquium Comput. Complex. TR16 (2016) - [i115]Joshua Brakensiek, Venkatesan Guruswami:
New hardness results for graph and hypergraph colorings. Electron. Colloquium Comput. Complex. TR16 (2016) - [i114]Joshua Brakensiek, Venkatesan Guruswami:
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. Electron. Colloquium Comput. Complex. TR16 (2016) - [i113]Venkatesan Guruswami, Jaikumar Radhakrishnan:
Tight bounds for communication assisted agreement distillation. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i112]Venkatesan Guruswami, Euiwoong Lee:
Inapproximability of $H$-Transversal/Packing. CoRR abs/1506.06302 (2015) - [i111]Vijay V. S. P. Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee:
Approximate Hypergraph Coloring under Low-discrepancy and Related Promises. CoRR abs/1506.06444 (2015) - [i110]Boris Bukh, Venkatesan Guruswami:
An improved bound on the fraction of correctable deletions. CoRR abs/1507.01719 (2015) - [i109]Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky:
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. CoRR abs/1507.06175 (2015) - [i108]Venkatesan Guruswami, Lingfei Jin, Chaoping Xing:
Efficient list decoding of punctured Reed-Muller codes. CoRR abs/1508.00603 (2015) - [i107]Venkatesan Guruswami, Mary Wootters:
Repairing Reed-Solomon Codes. CoRR abs/1509.04764 (2015) - [i106]Andrei A. Bulatov, Venkatesan Guruswami, Andrei A. Krokhin, Dániel Marx:
The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301). Dagstuhl Reports 5(7): 22-41 (2015) - [i105]Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky:
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. Electron. Colloquium Comput. Complex. TR15 (2015) - [i104]Boris Bukh, Venkatesan Guruswami:
An improved bound on the fraction of correctable deletions. Electron. Colloquium Comput. Complex. TR15 (2015) - [i103]Venkatesan Guruswami, Euiwoong Lee:
Towards a Characterization of Approximation Resistance for Symmetric CSPs. Electron. Colloquium Comput. Complex. TR15 (2015) - [i102]Venkatesan Guruswami, Euiwoong Lee:
Nearly Optimal NP-Hardness of Unique Coverage. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i101]Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan:
Communication with Imperfectly Shared Randomness. CoRR abs/1411.3603 (2014) - [i100]Venkatesan Guruswami, Carol Wang:
Deletion codes in the high-noise and high-rate regimes. CoRR abs/1411.6667 (2014) - [i99]Venkatesan Guruswami, Ameya Velingker:
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. CoRR abs/1411.6993 (2014) - [i98]Michael A. Forbes, Venkatesan Guruswami:
Dimension Expanders via Rank Condensers. CoRR abs/1411.7455 (2014) - [i97]Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan:
Communication with Imperfectly Shared Randomness. Electron. Colloquium Comput. Complex. TR14 (2014) - [i96]Michael A. Forbes, Venkatesan Guruswami:
Dimension Expanders via Rank Condensers. Electron. Colloquium Comput. Complex. TR14 (2014) - [i95]Venkatesan Guruswami, Euiwoong Lee:
Inapproximability of Feedback Vertex Set for Bounded Length Cycles. Electron. Colloquium Comput. Complex. TR14 (2014) - [i94]Venkatesan Guruswami, Euiwoong Lee:
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. Electron. Colloquium Comput. Complex. TR14 (2014) - [i93]Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang:
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. Electron. Colloquium Comput. Complex. TR14 (2014) - [i92]Venkatesan Guruswami, Ameya Velingker:
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i91]Venkatesan Guruswami, Chaoping Xing:
Optimal rate algebraic list decoding using narrow ray class fields. CoRR abs/1302.6660 (2013) - [i90]Venkatesan Guruswami, Patrick Xia:
Polar Codes: Speed of polarization and polynomial gap to capacity. CoRR abs/1304.4321 (2013) - [i89]Mahdi Cheraghchi, Venkatesan Guruswami:
Capacity of Non-Malleable Codes. CoRR abs/1309.0458 (2013) - [i88]Mahdi Cheraghchi, Venkatesan Guruswami:
Non-Malleable Coding Against Bit-wise and Split-State Tampering. CoRR abs/1309.1151 (2013) - [i87]Venkatesan Guruswami, Carol Wang:
Explicit rank-metric codes list-decodable with optimal redundancy. CoRR abs/1311.7084 (2013) - [i86]Venkatesan Guruswami, Johan Håstad, Prahladh Harsha, Srikanth Srinivasan, Girish Varma:
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. CoRR abs/1311.7407 (2013) - [i85]Venkatesan Guruswami, Ali Kemal Sinop:
Rounding Lasserre SDPs using column selection and spectrum-based approximation schemes for graph partitioning and Quadratic IPs. CoRR abs/1312.3024 (2013) - [i84]Per Austrin, Venkatesan Guruswami, Johan Håstad:
(2+ε)-SAT is NP-hard. Electron. Colloquium Comput. Complex. TR13 (2013) - [i83]Mahdi Cheraghchi, Venkatesan Guruswami:
Capacity of Non-Malleable Codes. Electron. Colloquium Comput. Complex. TR13 (2013) - [i82]Mahdi Cheraghchi, Venkatesan Guruswami:
Non-Malleable Coding Against Bit-wise and Split-State Tampering. Electron. Colloquium Comput. Complex. TR13 (2013) - [i81]Irit Dinur, Venkatesan Guruswami:
PCPs via low-degree long code and hardness for constrained hypergraph coloring. Electron. Colloquium Comput. Complex. TR13 (2013) - [i80]Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma:
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. Electron. Colloquium Comput. Complex. TR13 (2013) - [i79]Venkatesan Guruswami, Swastik Kopparty:
Explicit Subspace Designs. Electron. Colloquium Comput. Complex. TR13 (2013) - [i78]Venkatesan Guruswami, Euiwoong Lee:
Complexity of approximating CSP with Balance / Hard Constraints. Electron. Colloquium Comput. Complex. TR13 (2013) - [i77]Venkatesan Guruswami, Krzysztof Onak:
Superlinear lower bounds for multipass graph processing. Electron. Colloquium Comput. Complex. TR13 (2013) - [i76]Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket:
Inapproximability of Minimum Vertex Cover on k-uniform k-partite Hypergraphs. Electron. Colloquium Comput. Complex. TR13 (2013) - [i75]Venkatesan Guruswami, Carol Wang:
Explicit rank-metric codes list-decodable with optimal redundancy. Electron. Colloquium Comput. Complex. TR13 (2013) - [i74]Venkatesan Guruswami, Chaoping Xing:
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. Electron. Colloquium Comput. Complex. TR13 (2013) - [i73]Venkatesan Guruswami, Patrick Xia:
Polar Codes: Speed of polarization and polynomial gap to capacity. Electron. Colloquium Comput. Complex. TR13 (2013) - [i72]Venkatesan Guruswami, Chaoping Xing:
Hitting Sets for Low-Degree Polynomials with Optimal Density. Electron. Colloquium Comput. Complex. TR13 (2013) - [i71]Mahdi Cheraghchi, Venkatesan Guruswami:
Capacity of Non-Malleable Codes. IACR Cryptol. ePrint Arch. 2013: 564 (2013) - [i70]Mahdi Cheraghchi, Venkatesan Guruswami:
Non-Malleable Coding Against Bit-wise and Split-State Tampering. IACR Cryptol. ePrint Arch. 2013: 565 (2013) - 2012
- [i69]Venkatesan Guruswami, Srivatsan Narayanan, Carol Wang:
List decoding subspace codes from insertions and deletions. CoRR abs/1202.0535 (2012) - [i68]Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou:
Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems. CoRR abs/1202.6071 (2012) - [i67]Venkatesan Guruswami, Srivatsan Narayanan:
Combinatorial limitations of a strong form of list decoding. CoRR abs/1202.6086 (2012) - [i66]Venkatesan Guruswami, Chaoping Xing:
Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding. CoRR abs/1204.4209 (2012) - [i65]Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker:
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. CoRR abs/1207.1140 (2012) - [i64]Venkatesan Guruswami, Ali Kemal Sinop:
Faster SDP hierarchy solvers for local rounding algorithms. CoRR abs/1207.4372 (2012) - [i63]Venkatesan Guruswami, Krzysztof Onak:
Superlinear lower bounds for multipass graph processing. CoRR abs/1212.6925 (2012) - [i62]Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker:
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. Electron. Colloquium Comput. Complex. TR12 (2012) - [i61]Venkatesan Guruswami, Srivatsan Narayanan:
Combinatorial limitations of a strong form of list decoding. Electron. Colloquium Comput. Complex. TR12 (2012) - [i60]Venkatesan Guruswami, Ali Kemal Sinop:
Faster SDP hierarchy solvers for local rounding algorithms. Electron. Colloquium Comput. Complex. TR12 (2012) - [i59]Venkatesan Guruswami, Carol Wang:
Linear-algebraic list decoding for variants of Reed-Solomon codes. Electron. Colloquium Comput. Complex. TR12 (2012) - [i58]Venkatesan Guruswami, Chaoping Xing:
Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding. Electron. Colloquium Comput. Complex. TR12 (2012) - [i57]Venkatesan Guruswami, Chaoping Xing:
List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound. Electron. Colloquium Comput. Complex. TR12 (2012) - [i56]Venkatesan Guruswami, Yuan Zhou:
Approximating Bounded Occurrence Ordering CSPs. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i55]Venkatesan Guruswami, Ali Kemal Sinop:
Optimal Column-Based Low-Rank Matrix Reconstruction. CoRR abs/1104.1732 (2011) - [i54]Venkatesan Guruswami, Ali Kemal Sinop:
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives. CoRR abs/1104.4746 (2011) - [i53]Venkatesan Guruswami:
Linear-algebraic list decoding of folded Reed-Solomon codes. CoRR abs/1106.0436 (2011) - [i52]Venkatesan Guruswami, Carol Wang:
Optimal rate list decoding via derivative codes. CoRR abs/1106.3951 (2011) - [i51]Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou:
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. CoRR abs/1110.1360 (2011) - [i50]Venkatesan Guruswami, Ali Kemal Sinop:
Certifying Graph Expansion and Non-Uniform Sparsity via Generalized Spectra. CoRR abs/1112.4109 (2011) - [i49]Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar:
Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant. Electron. Colloquium Comput. Complex. TR11 (2011) - [i48]Venkatesan Guruswami, Ali Kemal Sinop:
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [i47]Venkatesan Guruswami, Johan Håstad, Swastik Kopparty:
On the List-Decodability of Random Linear Codes. CoRR abs/1001.1386 (2010) - [i46]Venkatesan Guruswami, Adam D. Smith:
Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. CoRR abs/1004.4017 (2010) - [i45]Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu:
Agnostic Learning of Monomials by Halfspaces is Hard. CoRR abs/1012.0729 (2010) - [i44]Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu:
Agnostic Learning of Monomials by Halfspaces is Hard. Electron. Colloquium Comput. Complex. TR10 (2010) - [i43]Venkatesan Guruswami, Johan Håstad, Swastik Kopparty:
On the List-Decodability of Random Linear Codes. Electron. Colloquium Comput. Complex. TR10 (2010) - [i42]Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu:
Bypassing UGC from some optimal geometric inapproximability results. Electron. Colloquium Comput. Complex. TR10 (2010) - [i41]Venkatesan Guruswami, Adam D. Smith:
Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate. Electron. Colloquium Comput. Complex. TR10 (2010) - [i40]Venkatesan Guruswami, Ali Kemal Sinop:
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. Electron. Colloquium Comput. Complex. TR10 (2010) - [i39]Venkatesan Guruswami, Yuan Zhou:
Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}. Electron. Colloquium Comput. Complex. TR10 (2010) - 2009
- [i38]Venkatesan Guruswami, Ali Kemal Sinop:
Improved Inapproximability Results for Maximum k-Colorable Subgraph. CoRR abs/0910.2271 (2009) - [i37]Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman:
Locally Testable Codes Require Redundant Testers. Electron. Colloquium Comput. Complex. TR09 (2009) - [i36]Venkatesan Guruswami:
Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes. Electron. Colloquium Comput. Complex. TR09 (2009) - [i35]Venkatesan Guruswami, Prasad Raghavendra:
Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. Electron. Colloquium Comput. Complex. TR09 (2009) - [i34]Venkatesan Guruswami, Ali Kemal Sinop:
Improved Inapproximability Results for Maximum k-Colorable Subgraph. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [i33]Venkatesan Guruswami:
Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes. CoRR abs/0811.4139 (2008) - [i32]Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra:
List Decoding Tensor Products and Interleaved Codes. CoRR abs/0811.4395 (2008) - [i31]Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra:
List Decoding Tensor Products and Interleaved Codes. Electron. Colloquium Comput. Complex. TR08 (2008) - [i30]Venkatesan Guruswami, Prasad Raghavendra:
Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness. Electron. Colloquium Comput. Complex. TR08 (2008) - [i29]Venkatesan Guruswami, Atri Rudra:
Soft decoding, dual BCH codes, and better list-decodable eps-biased codes. Electron. Colloquium Comput. Complex. TR08 (2008) - [i28]Venkatesan Guruswami, Atri Rudra:
Concatenated codes can achieve list-decoding capacity. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [i27]Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang:
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Electron. Colloquium Comput. Complex. TR07 (2007) - [i26]Parikshit Gopalan, Venkatesan Guruswami:
Deterministic Hardness Amplification via Local GMD Decoding. Electron. Colloquium Comput. Complex. TR07 (2007) - [i25]Venkatesan Guruswami, James R. Lee, Alexander A. Razborov:
Almost Euclidean subspaces of ℓ1N via expander codes. Electron. Colloquium Comput. Complex. TR07 (2007) - [i24]Venkatesan Guruswami, Atri Rudra:
Better Binary List-Decodable Codes via Multilevel Concatenation. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [i23]Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes (A Survey). CoRR abs/cs/0610022 (2006) - [i22]Venkatesan Guruswami:
Iterative Decoding of Low-Density Parity Check Codes (A Survey). Electron. Colloquium Comput. Complex. TR06 (2006) - [i21]Venkatesan Guruswami, Prasad Raghavendra:
Hardness of Learning Halfspaces with Noise. Electron. Colloquium Comput. Complex. TR06 (2006) - [i20]Venkatesan Guruswami, Kunal Talwar:
Hardness of Low Congestion Routing in Directed Graphs. Electron. Colloquium Comput. Complex. TR06 (2006) - [i19]Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Extractors and condensers from univariate polynomials. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [i18]Ioannis Giotis, Venkatesan Guruswami:
Correlation Clustering with a Fixed Number of Clusters. CoRR abs/cs/0504023 (2005) - [i17]Venkatesan Guruswami, Atri Rudra:
Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy. CoRR abs/cs/0511072 (2005) - [i16]Venkatesan Guruswami, Atri Rudra:
Tolerant Locally Testable Codes. Electron. Colloquium Comput. Complex. TR05 (2005) - [i15]Venkatesan Guruswami, Valentine Kabanets:
Hardness amplification via space-efficient direct products. Electron. Colloquium Comput. Complex. TR05 (2005) - [i14]Venkatesan Guruswami:
Algebraic-geometric generalizations of the Parvaresh-Vardy codes. Electron. Colloquium Comput. Complex. TR05 (2005) - [i13]Venkatesan Guruswami, Atri Rudra:
Explicit Capacity-Achieving List-Decodable Codes. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [i12]Venkatesan Guruswami, Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard. CoRR cs.CC/0405005 (2004) - [i11]Venkatesan Guruswami, Alexander Vardy:
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [i10]Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev:
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover. CoRR cs.CC/0304026 (2003) - [i9]Venkatesan Guruswami:
Better Extractors for Better Codes? Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [i8]Irit Dinur, Venkatesan Guruswami, Subhash Khot:
Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-epsilon). Electron. Colloquium Comput. Complex. TR02 (2002) - [i7]Lars Engebretsen, Venkatesan Guruswami:
Is Constraint Satisfaction Over Two Variables Always Easy? Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [i6]Venkatesan Guruswami:
Constructions of Codes from Number Fields. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [i5]Venkatesan Guruswami, Johan Håstad, Madhu Sudan:
Hardness of approximate hypergraph coloring. Electron. Colloquium Comput. Complex. TR00 (2000) - [i4]Venkatesan Guruswami, Sanjeev Khanna:
On the Hardness of 4-coloring a 3-colorable Graph. Electron. Colloquium Comput. Complex. TR00 (2000) - 1999
- [i3]Venkatesan Guruswami:
The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [i2]Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan:
A tight characterization of NP with 3 query PCPs. Electron. Colloquium Comput. Complex. TR98 (1998) - [i1]Venkatesan Guruswami, Madhu Sudan:
Improved decoding of Reed-Solomon and algebraic-geometric codes. Electron. Colloquium Comput. Complex. TR98 (1998)
Coauthor Index
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-11 22:45 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
