Improved decoding of Reed-Solomon and algebraic-geometry codes. Zbl 0958.94036
Guruswami, Venkatesan; Sudan, Madhu |
|
1999
|
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Zbl 1325.68169
Guruswami, Venkatesan; Umans, Christopher; Vadhan, Salil |
|
2009
|
Clustering with qualitative information. Zbl 1094.68075
Charikar, Moses; Guruswami, Venkatesan; Wirth, Anthony |
|
2005
|
On profit-maximizing envy-free pricing. Zbl 1297.91072
Guruswami, Venkatesan; Hartline, Jason D.; Karlin, Anna R.; Kempe, David; Kenyon, Claire; McSherry, Frank |
|
2005
|
A new multilayered PCP and the hardness of hypergraph vertex cover. Zbl 1079.68039
Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded |
|
2005
|
Explicit codes achieving list decoding capacity: error-correction with optimal redundancy. Zbl 1205.94125
Guruswami, Venkatesan; Rudra, Atri |
|
2008
|
Algorithmic aspects of clique-transversal and clique-independent sets. Zbl 0948.68135
Guruswami, Venkatesan; Rangan, C. Pandu |
|
2000
|
Capacity of non-malleable codes. Zbl 1366.68042
Cheraghchi, Mahdi; Guruswami, Venkatesan |
|
2014
|
Non-malleable coding against bit-wise and split-state tampering. Zbl 1326.94080
Cheraghchi, Mahdi; Guruswami, Venkatesan |
|
2014
|
List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound. Zbl 1293.94110
Guruswami, Venkatesan; Xing, Chaoping |
|
2013
|
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1114.68430
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis |
|
2003
|
Lasserre hierarchy, higher eigenvalues, and approximation schemes for graphs partitioning and quadratic integer programming with PSD objectives (extended abstract). Zbl 1292.90222
Guruswami, Venkatesan; Sinop, Ali Kemal |
|
2011
|
MaxMin Allocation via degree lower-bounded arborescences. Zbl 1304.91143
Bateni, MohammadHossein; Charikar, Moses; Guruswami, Venkatesan |
|
2009
|
Linear-time encodable/decodable codes with near-optimal rate. Zbl 1310.94209
Guruswami, Venkatesan; Indyk, Piotr |
|
2005
|
Beating the random ordering is hard: every ordering CSP is approximation resistant. Zbl 1235.68075
Guruswami, Venkatesan; Håstad, Johan; Manokaran, Rajsekar; Raghavendra, Prasad; Charikar, Moses |
|
2011
|
Explicit subspace designs. Zbl 1389.51003
Guruswami, Venkatesan; Kopparty, Swastik |
|
2016
|
List decoding of error-correcting codes. Winning thesis of the 2002 ACM Doctoral Dissertation Competition. Zbl 1075.94001
Guruswami, Venkatesan |
|
2004
|
Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph. Zbl 1423.68202
Bhaskara, Aditya; Charikar, Moses; Vijayaraghavan, Aravindan; Guruswami, Venkatesan; Zhou, Yuan |
|
2012
|
\((2+\varepsilon)\)-Sat is NP-hard. Zbl 1476.68188
Austrin, Per; Guruswami, Venkatesan; Håstad, Johan |
|
2017
|
Correlation clustering with a fixed number of clusters. Zbl 1213.68704
Giotis, Ioannis; Guruswami, Venkatesan |
|
2006
|
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Zbl 1346.68102
Guruswami, Venkatesan; Khanna, Sanjeev; Rajaraman, Rajmohan; Shepherd, Bruce; Yannakakis, Mihalis |
|
1999
|
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Zbl 1240.68113
Andrews, Matthew; Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal; Zhang, Lisa |
|
2010
|
Linear-algebraic list decoding for variants of Reed-Solomon codes. Zbl 1364.94607
Guruswami, Venkatesan; Wang, Carol |
|
2013
|
Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy. Zbl 1403.68074
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2018
|
New hardness results for graph and hypergraph colorings. Zbl 1380.68190
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2016
|
On the hardness of 4-coloring a 3-colorable graph. Zbl 1087.68071
Guruswami, Venkatesan; Khanna, Sanjeev |
|
2004
|
Optimal column-based low-rank matrix reconstruction. Zbl 1421.68227
Guruswami, Venkatesan; Sinop, Ali Kemal |
|
2012
|
Correlation clustering with a fixed number of clusters. Zbl 1194.62087
Giotis, Ioannis; Guruswami, Venkatesan |
|
2006
|
How long can optimal locally repairable codes be? Zbl 1432.94213
Guruswami, Venkatesan; Xing, Chaoping; Yuan, Chen |
|
2019
|
Hardness of approximate hypergraph coloring. Zbl 1008.68052
Guruswami, Venkatesan; Hastad, Johan; Sudan, Madhu |
|
2002
|
The complexity of the covering radius problem. Zbl 1085.68063
Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded |
|
2005
|
List decoding algorithms for certain concatenated codes. Zbl 1296.94170
Guruswami, Venkatesan; Sudan, Madhu |
|
2000
|
Superlinear lower bounds for multipass graph processing. Zbl 1353.68084
Guruswami, Venkatesan; Onak, Krzysztof |
|
2016
|
Folded codes from function field towers and improved optimal rate list decoding. Zbl 1286.94111
Guruswami, Venkatesan; Xing, Chaoping |
|
2012
|
Query strategies for priced information. Zbl 1015.68244
Charikar, Moses; Fagin, Ronald; Guruswami, Venkatesan; Kleinberg, Jon; Raghavan, Prabhakar |
|
2002
|
Linear time encodable and list decodable codes. Zbl 1192.94097
Guruswami, Venkatesan; Indyk, Piotr |
|
2003
|
Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. Zbl 1192.94132
Guruswami, Venkatesan; Indyk, Piotr |
|
2002
|
Agnostic learning of monomials by halfspaces is hard. Zbl 1261.68063
Feldman, Vitaly; Guruswami, Venkatesan; Raghavendra, Prasad; Wu, Yi |
|
2012
|
Restricted isometry of Fourier matrices and list decodability of random linear codes. Zbl 1321.94122
Cheraghchi, Mahdi; Guruswami, Venkatesan; Velingker, Ameya |
|
2013
|
A new multilayered {PCP} and the hardness of hypergraph vertex cover. Zbl 1192.68290
Dinur, Irit; Guruswami, Venkatesan; Khot, Subhash; Regev, Oded |
|
2003
|
List decoding from erasures: bounds and code constructions. Zbl 1301.94156
Guruswami, Venkatesan |
|
2003
|
Maximum cut on line and total graphs. Zbl 0935.68082
Guruswami, Venkatesan |
|
1999
|
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. Zbl 1310.94210
Guruswami, Venkatesan; Vardy, Alexander |
|
2005
|
Hardness of learning halfspaces with noise. Zbl 1198.68157
Guruswami, Venkatesan; Raghavendra, Prasad |
|
2009
|
An algorithmic blend of LPs and ring equations for promise CSPs. Zbl 1431.68043
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2019
|
Combinatorial bounds for list decoding. Zbl 1061.94074
Guruswami, Venkatesan; Håstad, Johan; Sudan, Madhu; Zuckerman, David |
|
2002
|
Explicit list-decodable rank-metric and subspace codes via subspace designs. Zbl 1359.94797
Guruswami, Venkatesan; Wang, Carol; Xing, Chaoping |
|
2016
|
Repairing Reed-Solomon codes. Zbl 1374.94829
Guruswami, Venkatesan; Wootters, Mary |
|
2017
|
Repairing Reed-Solomon codes. Zbl 1377.94074
Guruswami, Venkatesan; Wootters, Mary |
|
2016
|
Deletion codes in the high-noise and high-rate regimes. Zbl 1366.94595
Guruswami, Venkatesan; Wang, Carol |
|
2017
|
The vertex-disjoint triangles problem. Zbl 0918.68081
Guruswami, Venkatesan; Rangan, C. Pandu; Chang, M. S.; Chang, G. J.; Wong, C. K. |
|
1998
|
Subspace designs based on algebraic function fields. Zbl 1397.05031
Guruswami, Venkatesan; Xing, Chaoping; Yuan, Chen |
|
2018
|
The \(K_r\)-packing problem. Zbl 0978.05060
Guruswami, V.; Pandu Rangan, C.; Chang, M. S.; Chang, G. J.; Wong, C. K. |
|
2001
|
Locally testable codes require redundant testers. Zbl 1209.68265
Ben-Sasson, Eli; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu; Viderman, Michael |
|
2010
|
Optimal rate code constructions for computationally simple channels. Zbl 1407.94009
Guruswami, Venkatesan; Smith, Adam |
|
2016
|
Inapproximability of \(H\)-transversal/packing. Zbl 1371.68099
Guruswami, Venkatesan; Lee, Euiwoong |
|
2017
|
Embeddings and non-approximability of geometric problems. Zbl 1092.68690
Guruswami, Venkatesan; Indyk, Piotr |
|
2003
|
Algorithmic results in list decoding. Zbl 1203.94139
Guruswami, Venkatesan |
|
2006
|
The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems. Zbl 1496.68255
Brakensiek, Joshua; Guruswami, Venkatesan; Wrochna, Marcin; Živný, Stanislav |
|
2020
|
Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph. Zbl 1467.68064
Guruswami, Venkatesan; Velingker, Ameya; Velusamy, Santhoshini |
|
2017
|
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1398.68194
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi |
|
2016
|
Optimal rate list decoding via derivative codes. Zbl 1343.94101
Guruswami, Venkatesan; Wang, Carol |
|
2011
|
Explicit capacity-achieving list-decodable codes. Zbl 1301.94157
Guruswami, Venkatesan; Rudra, Atri |
|
2006
|
An improved bound on the fraction of correctable deletions. Zbl 1359.94907
Bukh, Boris; Guruswami, Venkatesan; Håstad, Johan |
|
2017
|
Inapproximability of \(H\)-transversal/packing. Zbl 1375.68059
Guruswami, Venkatesan; Lee, Euiwoong |
|
2015
|
Constructions of codes from number fields. Zbl 1063.94110
Guruswami, Venkatesan |
|
2003
|
Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy. Zbl 1494.68094
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2021
|
Tolerant locally testable codes. Zbl 1105.68347
Guruswami, Venkatesan; Rudra, Atri |
|
2005
|
On the inapproximability of Vertex Cover on \(k\)-partite \(k\)-uniform hypergraphs. Zbl 1288.68093
Guruswami, Venkatesan; Saket, Rishi |
|
2010
|
Sum-of-squares certificates for maxima of random tensors on the sphere. Zbl 1471.62565
Bhattiprolu, Vijay; Guruswami, Venkatesan; Lee, Euiwoong |
|
2017
|
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets (extended abstract). Zbl 1423.94174
Guruswami, Venkatesan; Xing, Chaoping |
|
2014
|
Strong inapproximability results on balanced rainbow-colorable hypergraphs. Zbl 1371.68208
Guruswami, Venkatesan; Lee, Euiwoong |
|
2015
|
A lower bound on list size for list decoding. Zbl 1366.94701
Guruswami, Venkatesan; Vadhan, Salil |
|
2010
|
Linear-time list decoding in error-free settings (extended abstract). Zbl 1099.94522
Guruswami, Venkatesan; Indyk, Piotr |
|
2004
|
Inapproximability results for set splitting and satisfiability problems with no mixed clauses. Zbl 1095.68036
Guruswami, Venkatesan |
|
2004
|
Guessing secrets efficiently via list decoding. Zbl 1058.94023
Alon, Noga; Guruswami, Venkatesan; Kaufman, Tali; Sudan, Madhu |
|
2002
|
On representations of algebraic-geometry codes. Zbl 1002.94041
Guruswami, Venkatesan; Sudan, Madhu |
|
2001
|
Limits to list decoding Reed-Solomon codes. Zbl 1283.94139
Guruswami, Venkatesan; Rudra, Atri |
|
2006
|
Hardness of routing with congestion in directed graphs. Zbl 1232.68062
Chuzhoy, Julia; Guruswami, Venkatesan; Khanna, Sanjeev; Talwar, Kunal |
|
2007
|
Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate. Zbl 1206.94113
Guruswami, Venkatesan |
|
2010
|
Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. Zbl 1318.94108
Guruswami, Venkatesan; Indyk, Piotr |
|
2004
|
Restricted isometry of Fourier matrices and list decodability of random linear codes. Zbl 1440.94105
Cheraghchi, Mahdi; Guruswami, Venkatesan; Velingker, Ameya |
|
2013
|
Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set. Zbl 1255.68303
Guruswami, Venkatesan; Zhou, Yuan |
|
2012
|
Efficient low-redundancy codes for correcting multiple deletions. Zbl 1395.94335
Brakensiek, Joshua; Guruswami, Venkatesan; Zbarsky, Samuel |
|
2018
|
On the list-decodability of random linear codes. Zbl 1366.94699
Guruswami, Venkatesan; Håstad, Johan; Kopparty, Swastik |
|
2011
|
Dimension expanders via rank condensers. Zbl 1375.68086
Forbes, Michael A.; Guruswami, Venkatesan |
|
2015
|
Polar codes: speed of polarization and polynomial gap to capacity. Zbl 1359.94699
Guruswami, Venkatesan; Xia, Patrick |
|
2015
|
Leakage-resilient secret sharing in non-compartmentalized models. Zbl 1525.94057
Lin, Fuchun; Cheraghchi, Mahdi; Guruswami, Venkatesan; Safavi-Naini, Reihaneh; Wang, Huaxiong |
|
2020
|
Capacity of non-malleable codes. Zbl 1359.94884
Cheraghchi, Mahdi; Guruswami, Venkatesan |
|
2016
|
Constraint satisfaction over a non-Boolean domain: Approximation algorithms and unique-games hardness. Zbl 1159.68665
Guruswami, Venkatesan; Raghavendra, Prasad |
|
2008
|
Better extractors for better codes? Zbl 1192.68363
Guruswami, Venkatesan |
|
2004
|
Constructions of maximally recoverable local reconstruction codes via function fields. Zbl 1452.94114
Guruswami, Venkatesan; Jin, Lingfei; Xing, Chaoping |
|
2020
|
Maximally recoverable LRCs: a field size lower bound and constructions for few heavy parities. Zbl 1452.94113
Gopi, Sivakanth; Guruswami, Venkatesan; Yekhanin, Sergey |
|
2020
|
Symmetric polymorphisms and efficient decidability of promise CSPs. Zbl 07304041
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2020
|
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1421.68062
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi |
|
2012
|
PCPs via the low-degree long code and hardness for constrained hypergraph coloring. Zbl 1330.68091
Dinur, Irit; Guruswami, Venkatesan |
|
2015
|
Tight bounds on the approximability of almost-satisfiable Horn SAT and exact hitting set. Zbl 1377.68094
Guruswami, Venkatesan; Zhou, Yuan |
|
2011
|
The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. Zbl 1376.68054
Guruswami, Venkatesan; Sinop, Ali Kemal |
|
2011
|
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. Zbl 1315.05052
Guruswami, Venkatesan; Harsha, Prahladh; Håstad, Johan; Srinivasan, Srikanth; Varma, Girish |
|
2014
|
Non-malleable coding against bit-wise and split-state tampering. Zbl 1370.94497
Cheraghchi, Mahdi; Guruswami, Venkatesan |
|
2017
|
Efficient linear and affine codes for correcting insertions/deletions. Zbl 1528.94107
Cheng, Kuan; Guruswami, Venkatesan; Haeupler, Bernhard; Li, Xin |
|
2023
|
A family of dictatorship tests with perfect completeness for 2-to-2 label cover. Zbl 07716602
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2023
|
A near-cubic lower bound for 3-query locally decodable codes from semirandom CSP refutation. Zbl 07844683
Alrabiah, Omar; Guruswami, Venkatesan; Kothari, Pravesh K.; Manohar, Peter |
|
2023
|
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. Zbl 07774370
Guruswami, Venkatesan; Kothari, Pravesh K.; Manohar, Peter |
|
2022
|
Beating Fredman-Komlós for perfect \(k\)-hashing. Zbl 1483.94025
Guruswami, Venkatesan; Riazanov, Andrii |
|
2022
|
Improved maximally recoverable LRCs using skew polynomials. Zbl 1534.94109
Gopi, Sivakanth; Guruswami, Venkatesan |
|
2022
|
Optimal rate list decoding over bounded alphabets using algebraic-geometric codes. Zbl 07500716
Guruswami, Venkatesan; Xing, Chaoping |
|
2022
|
Range avoidance for low-depth circuits and connections to pseudorandomness. Zbl 07900604
Guruswami, Venkatesan; Lyu, Xin; Wang, Xiuhan |
|
2022
|
Arıkan meets Shannon: polar codes with near-optimal convergence to channel capacity. Zbl 1497.94045
Guruswami, Venkatesan; Riazanov, Andrii; Ye, Min |
|
2022
|
Bounds for list-decoding and list-recovery of random linear codes. Zbl 1489.94176
Guruswami, Venkatesan; Li, Ray; Mosheiff, Jonathan; Resch, Nicolas; Silas, Shashwat; Wootters, Mary |
|
2022
|
CNF satisfiability in a subspace and related problems. Zbl 07608291
Arvind, V.; Guruswami, Venkatesan |
|
2022
|
\(\ell_p\)-spread and restricted isometry properties of sparse random matrices. Zbl 07877654
Guruswami, Venkatesan; Manohar, Peter; Mosheiff, Jonathan |
|
2022
|
Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy. Zbl 1494.68094
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2021
|
The quest for strong inapproximability results with perfect completeness. Zbl 07475107
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2021
|
Efficient linear and affine codes for correcting insertions/deletions. Zbl 07788339
Cheng, Kuan; Guruswami, Venkatesan; Haeupler, Bernhard; Li, Xin |
|
2021
|
Strongly refuting all semi-random Boolean CSPs. Zbl 07788366
Abascal, Jackson; Guruswami, Venkatesan; Kothari, Pravesh K. |
|
2021
|
Lossless dimension expanders via linearized polynomials and subspace designs. Zbl 1499.11360
Guruswami, Venkatesan; Resch, Nicolas; Xing, Chaoping |
|
2021
|
Approximate hypergraph vertex cover and generalized Tuza’s conjecture. Zbl 07883621
Guruswami, Venkatesan; Sandeep, Sai |
|
2021
|
Explicit two-deletion codes with redundancy matching the existential bound. Zbl 1487.94191
Guruswami, Venkatesan; Håstad, Johan |
|
2021
|
Optimally resilient codes for list-decoding from insertions and deletions. Zbl 1489.94175
Guruswami, Venkatesan; Haeupler, Bernhard; Shahrasbi, Amirbehshad |
|
2021
|
An exponential lower bound on the sub-packetization of minimum storage regenerating codes. Zbl 1489.94180
Alrabiah, Omar; Guruswami, Venkatesan |
|
2021
|
CNF satisfiability in a subspace and related problems. Zbl 07803583
Arvind, Vikraman; Guruswami, Venkatesan |
|
2021
|
The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems. Zbl 1496.68255
Brakensiek, Joshua; Guruswami, Venkatesan; Wrochna, Marcin; Živný, Stanislav |
|
2020
|
Leakage-resilient secret sharing in non-compartmentalized models. Zbl 1525.94057
Lin, Fuchun; Cheraghchi, Mahdi; Guruswami, Venkatesan; Safavi-Naini, Reihaneh; Wang, Huaxiong |
|
2020
|
Constructions of maximally recoverable local reconstruction codes via function fields. Zbl 1452.94114
Guruswami, Venkatesan; Jin, Lingfei; Xing, Chaoping |
|
2020
|
Maximally recoverable LRCs: a field size lower bound and constructions for few heavy parities. Zbl 1452.94113
Gopi, Sivakanth; Guruswami, Venkatesan; Yekhanin, Sergey |
|
2020
|
Symmetric polymorphisms and efficient decidability of promise CSPs. Zbl 07304041
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2020
|
Rainbow coloring hardness via low sensitivity polymorphisms. Zbl 1448.68356
Guruswami, Venkatesan; Sandeep, Sai |
|
2020
|
\(\varepsilon\)-MSR codes: contacting fewer code blocks for exact repair. Zbl 1453.94143
Guruswami, Venkatesan; Lokam, Satyanarayana V.; Mani Jayaraman, Sai Vikneshwar |
|
2020
|
An improved bound on the zero-error list-decoding capacity of the 4/3 channel. Zbl 1434.94048
Dalai, Marco; Guruswami, Venkatesan; Radhakrishnan, Jaikumar |
|
2020
|
Bounds for list-decoding and list-recovery of random linear codes. Zbl 07758311
Guruswami, Venkatesan; Li, Ray; Mosheiff, Jonathan; Resch, Nicolas; Silas, Shashwat; Wootters, Mary |
|
2020
|
Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity. Zbl 1487.94166
Guruswami, Venkatesan; Riazanov, Andrii; Ye, Min |
|
2020
|
Coding against deletions in oblivious and online models. Zbl 1448.94260
Guruswami, Venkatesan; Li, Ray |
|
2020
|
Optimally resilient codes for list-decoding from insertions and deletions. Zbl 1492.94217
Guruswami, Venkatesan; Haeupler, Bernhard; Shahrasbi, Amirbehshad |
|
2020
|
How long can optimal locally repairable codes be? Zbl 1432.94213
Guruswami, Venkatesan; Xing, Chaoping; Yuan, Chen |
|
2019
|
An algorithmic blend of LPs and ring equations for promise CSPs. Zbl 1431.68043
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2019
|
Secret sharing with binary shares. Zbl 07559096
Lin, Fuchun; Cheraghchi, Mahdi; Guruswami, Venkatesan; Safavi-Naini, Reihaneh; Wang, Huaxiong |
|
2019
|
Bridging between 0/1 and linear programming via random walks. Zbl 1433.68156
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2019
|
CSPs with global modular constraints: algorithms and hardness via polynomial representations. Zbl 1433.68270
Brakensiek, Joshua; Gopi, Sivakanth; Guruswami, Venkatesan |
|
2019
|
Beating Fredman-Komlós for perfect \(k\)-hashing. Zbl 07561585
Guruswami, Venkatesan; Riazanov, Andrii |
|
2019
|
Approximability of \(p\rightarrow q\) matrix norms: generalized Krivine rounding and hypercontractive hardness. Zbl 1431.68041
Bhattiprolu, Vijay; Ghosh, Mrinalkanti; Guruswami, Venkatesan; Lee, Euiwoong; Tulsiani, Madhur |
|
2019
|
An exponential lower bound on the sub-packetization of MSR codes. Zbl 1433.68130
Alrabiah, Omar; Guruswami, Venkatesan |
|
2019
|
Streaming hardness of unique games. Zbl 07650072
Guruswami, Venkatesan; Tao, Runzhou |
|
2019
|
Algorithmic polarization for hidden Markov models. Zbl 07559082
Guruswami, Venkatesan; Nakkiran, Preetum; Sudan, Madhu |
|
2019
|
Polynomial time decodable codes for the binary deletion channel. Zbl 1431.94148
Guruswami, Venkatesan; Li, Ray |
|
2019
|
Maximally recoverable LRCs: a field size lower bound and constructions for few heavy parities. Zbl 1432.68140
Gopi, Sivakanth; Guruswami, Venkatesan; Yekhanin, Sergey |
|
2019
|
Rainbow coloring hardness via low sensitivity polymorphisms. Zbl 07650082
Guruswami, Venkatesan; Sandeep, Sai |
|
2019
|
Constructions of maximally recoverable local reconstruction codes via function fields. Zbl 07561561
Guruswami, Venkatesan; Jin, Lingfei; Xing, Chaoping |
|
2019
|
Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy. Zbl 1403.68074
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2018
|
Subspace designs based on algebraic function fields. Zbl 1397.05031
Guruswami, Venkatesan; Xing, Chaoping; Yuan, Chen |
|
2018
|
Efficient low-redundancy codes for correcting multiple deletions. Zbl 1395.94335
Brakensiek, Joshua; Guruswami, Venkatesan; Zbarsky, Samuel |
|
2018
|
General strong polarization. Zbl 1427.94089
Błasiok, Jarosław; Guruswami, Venkatesan; Nakkiran, Preetum; Rudra, Atri; Sudan, Madhu |
|
2018
|
Lossless dimension expanders via linearized polynomials and subspace designs. Zbl 1441.68037
Guruswami, Venkatesan; Resch, Nicolas; Xing, Chaoping |
|
2018
|
Strong inapproximability results on balanced rainbow-colorable hypergraphs. Zbl 1424.05087
Guruswami, Venkatesan; Lee, Euiwoong |
|
2018
|
MDS code constructions with small sub-packetization and near-optimal repair bandwidth. Zbl 1401.94106
Rawat, Ankit Singh; Tamo, Itzhak; Guruswami, Venkatesan; Efremenko, Klim |
|
2018
|
Hardness of rainbow coloring hypergraphs. Zbl 1491.68144
Guruswami, Venkatesan; Saket, Rishi |
|
2018
|
How long can optimal locally repairable codes be? Zbl 1527.94094
Guruswami, Venkatesan; Xing, Chaoping; Yuan, Chen |
|
2018
|
Coding against deletions in oblivious and online models. Zbl 1417.94102
Guruswami, Venkatesan; Li, Ray |
|
2018
|
Polar codes with exponentially small error at finite block length. Zbl 1527.94084
Błasiok, Jarosław; Guruswami, Venkatesan; Sudan, Madhu |
|
2018
|
\((2+\varepsilon)\)-Sat is NP-hard. Zbl 1476.68188
Austrin, Per; Guruswami, Venkatesan; Håstad, Johan |
|
2017
|
Repairing Reed-Solomon codes. Zbl 1374.94829
Guruswami, Venkatesan; Wootters, Mary |
|
2017
|
Deletion codes in the high-noise and high-rate regimes. Zbl 1366.94595
Guruswami, Venkatesan; Wang, Carol |
|
2017
|
Inapproximability of \(H\)-transversal/packing. Zbl 1371.68099
Guruswami, Venkatesan; Lee, Euiwoong |
|
2017
|
Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph. Zbl 1467.68064
Guruswami, Venkatesan; Velingker, Ameya; Velusamy, Santhoshini |
|
2017
|
An improved bound on the fraction of correctable deletions. Zbl 1359.94907
Bukh, Boris; Guruswami, Venkatesan; Håstad, Johan |
|
2017
|
Sum-of-squares certificates for maxima of random tensors on the sphere. Zbl 1471.62565
Bhattiprolu, Vijay; Guruswami, Venkatesan; Lee, Euiwoong |
|
2017
|
Non-malleable coding against bit-wise and split-state tampering. Zbl 1370.94497
Cheraghchi, Mahdi; Guruswami, Venkatesan |
|
2017
|
The quest for strong inapproximability results with perfect completeness. Zbl 1467.68057
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2017
|
MDS code constructions with small sub-packetization and near-optimal repair bandwidth. Zbl 1409.68093
Guruswami, Venkatesan; Rawat, Ankit Singh |
|
2017
|
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. Zbl 1359.68104
Guruswami, Venkatesan; Harsha, Prahladh; Håstad, Johan; Srinivasan, Srikanth; Varma, Girish |
|
2017
|
Nearly optimal NP-hardness of unique coverage. Zbl 1371.68098
Guruswami, Venkatesan; Lee, Euiwoong |
|
2017
|
Communication with imperfectly shared randomness. Zbl 1390.94615
Canonne, Clément L.; Guruswami, Venkatesan; Meka, Raghu; Sudan, Madhu |
|
2017
|
Locality via partially lifted codes. Zbl 1467.94049
Frank-Fischer, S. Luna; Guruswami, Venkatesan; Wootters, Mary |
|
2017
|
Explicit subspace designs. Zbl 1389.51003
Guruswami, Venkatesan; Kopparty, Swastik |
|
2016
|
New hardness results for graph and hypergraph colorings. Zbl 1380.68190
Brakensiek, Joshua; Guruswami, Venkatesan |
|
2016
|
Superlinear lower bounds for multipass graph processing. Zbl 1353.68084
Guruswami, Venkatesan; Onak, Krzysztof |
|
2016
|
Explicit list-decodable rank-metric and subspace codes via subspace designs. Zbl 1359.94797
Guruswami, Venkatesan; Wang, Carol; Xing, Chaoping |
|
2016
|
Repairing Reed-Solomon codes. Zbl 1377.94074
Guruswami, Venkatesan; Wootters, Mary |
|
2016
|
Optimal rate code constructions for computationally simple channels. Zbl 1407.94009
Guruswami, Venkatesan; Smith, Adam |
|
2016
|
Bypassing UGC from some optimal geometric inapproximability results. Zbl 1398.68194
Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi |
|
2016
|
Capacity of non-malleable codes. Zbl 1359.94884
Cheraghchi, Mahdi; Guruswami, Venkatesan |
|
2016
|
Complexity of approximating CSP with balance/hard constraints. Zbl 1350.68142
Guruswami, Venkatesan; Lee, Euiwoong |
|
2016
|
Simple proof of hardness of feedback vertex set. Zbl 1343.68095
Guruswami, Venkatesan; Lee, Euiwoong |
|
2016
|
Efficient low-redundancy codes for correcting multiple deletions. Zbl 1415.94477
Brakensiek, Joshua; Guruswami, Venkatesan; Zbarsky, Samuel |
|
2016
|
An improved bound on the fraction of correctable deletions. Zbl 1417.94115
Bukh, Boris; Guruswami, Venkatesan |
|
2016
|
Tight bounds for communication-assisted agreement distillation. Zbl 1380.94067
Guruswami, Venkatesan; Radhakrishnan, Jaikumar |
|
2016
|
Nearly optimal NP-hardness of unique coverage. Zbl 1411.68189
Guruswami, Venkatesan; Lee, Euiwoong |
|
2016
|
Inapproximability of \(H\)-transversal/packing. Zbl 1375.68059
Guruswami, Venkatesan; Lee, Euiwoong |
|
2015
|
Strong inapproximability results on balanced rainbow-colorable hypergraphs. Zbl 1371.68208
Guruswami, Venkatesan; Lee, Euiwoong |
|
2015
|
Dimension expanders via rank condensers. Zbl 1375.68086
Forbes, Michael A.; Guruswami, Venkatesan |
|
2015
|
Polar codes: speed of polarization and polynomial gap to capacity. Zbl 1359.94699
Guruswami, Venkatesan; Xia, Patrick |
|
2015
|
PCPs via the low-degree long code and hardness for constrained hypergraph coloring. Zbl 1330.68091
Dinur, Irit; Guruswami, Venkatesan |
|
2015
|
Optimal rate algebraic list decoding using narrow ray class fields. Zbl 1361.94066
Guruswami, Venkatesan; Xing, Chaoping |
|
2015
|
Approximate hypergraph coloring under low-discrepancy and related promises. Zbl 1375.05085
Bhattiprolu, Vijay V. S. P.; Guruswami, Venkatesan; Lee, Euiwoong |
|
2015
|
Inapproximability of minimum vertex cover on \(k\)-uniform \(k\)-partite hypergraphs. Zbl 1331.68089
Guruswami, Venkatesan; Sachdeva, Sushant; Saket, Rishi |
|
2015
|
An entropy sumset inequality and polynomially fast convergence to Shannon capacity over all alphabets. Zbl 1378.94013
Guruswami, Venkatesan; Velingker, Ameya |
|
2015
|
Communication with imperfectly shared randomness. Zbl 1364.68192
Canonne, Clement Louis; Guruswami, Venkatesan; Meka, Raghu; Sudan, Madhu |
|
2015
|
Deletion codes in the high-noise and high-rate regimes. Zbl 1407.94191
Guruswami, Venkatesan; Wang, Carol |
|
2015
|
Towards a characterization of approximation resistance for symmetric CSPs. Zbl 1375.68103
Guruswami, Venkatesan; Lee, Euiwoong |
|
2015
|
Capacity of non-malleable codes. Zbl 1366.68042
Cheraghchi, Mahdi; Guruswami, Venkatesan |
|
2014
|
| ...and 117 more Documents |
