Research Publications
Recent book: ALGORITHMIC
RESULTS IN LIST DECODING Foundations and TrendsŪ in
Theoretical Computer Science , Volume 2, Issue 2, 2007.personal use only) here .
A printed and bound version of this article is available at
a 40% discount from Now Publishers.TCS002002 on the
order form at now publishers.
You will then pay only $48.00 + shipping.
Following
is a list of papers (co)-authored by me, arranged by
topic. Recent papers (since 2005 or so) are not (yet) categorized by topic. Within each topic, the papers are ordered more or less in
reverse
chronological order of date of first publication. I also usually try
to make only the most recent version (eg. the journal
version/submission, if one exists) of the paper available.
DBLP listing of publications
Artin automorphisms, cyclotomic
function fields, and folded list-decodable codes , In preparation , 2008.
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph FOCS 2008
Euclidean sections with sublinear randomness and error-correction over the reals , RANDOM 2008
Constraint Satisfaction over a Non-Boolean domain: Approximation algorithms and Unique Games hardness APPROX 2008 ECCC Report TR08-08 . (With P. Raghavendra)
Explicit interleavers for a Repeat Accumulate Accumulate (RAA) code construction ISIT 2008
Soft decoding, dual BCH codes, and better eps-biased list-decodable codes CCC 2008 ECCC Report TR08-36 . (With A. Rudra)
Hardness amplification within NP against deterministic algorithms , CCC 2008 ECCC Report TR07-089
Concatenated codes can achieve list decoding capacity , SODA 2008 . (With A. Rudra)Almost Euclidean sections of L_1^N via expander codes SODA 2008 . (With J. Lee and A. Razborov)Inaproximability
of edge-disjoint paths and low congestion routing on undirected
graphs ECCC Report TR07-113 ; Submitted to
Combinatorica , 2007. (With M. Andrews, J. Chuzhoy, S. Khanna,
K. Talwar, and L. Zhang)
Better binary list-decodable codes via multilevel concatenation, RANDOM 2007 ; Submitted to IEEE Trans. Info. Theory . (With A. Rudra)
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes Submitted , June 2008. (With C. Umans and S. Vadhan)
Conference version: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes CCC'07 (received the best paper award ).
Hardness of solving sparse overdetermined linear systems: A 3-query PCP over integers , Submitted , 2008. Conference version in STOC 2007 . (With P. Raghavendra)
Hardness of routing with congestion in directed graphs STOC 2007 . (With J. Chuzhoy, S. Khanna, and K. Talwar)
Iterative Decoding of Low-Density Parity Check Codes (A Survey) , Issue 90 of Bulletin of the EATCS.
Achieving list decoding capacity using folded Reed-Solomon codes Allerton 2006
Hardness of learning halfspaces with noise SIAM J. Computing ; Preliminary version in FOCS 2006 . (With P. Raghavendra)
Correlated Algebraic-Geometric Codes: Improved list decoding over bounded alphabets Mathematics of Computation , 77(2008), 447-473. Extended abstract appeared in FOCS 2006 . (With A. Patthak)
On 2-Query Codeword Testing with Near-Perfect Completeness ISAAC 2006 . Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy IEEE Trans. on Info. Theory, 54(1), Jan 2008. (With A. Rudra)
Algebraic-geometric generalizations of the Parvaresh-Vardy codes ECCC Report TR05-132 (Subsumed by correlated AG codes paper above)List Decoding in Average-Case Complexity and Pseudorandomness ITW 2006 . Hardness Amplification via Space-Efficient Direct Products Computational Complexity , to appear. (With V. Kabanets) Algorithms for Modular Counting of Roots of Multivariate Polynomials LATIN 2006 , Invited to Algorithmica . (With P. Gopalan and R. Lipton)
Correlation
Clustering with a fixed number of clusters Theory of Computing , 2(13) (2006). Conference version in SODA 2006 . (With I. Giotis)
A lower bound on list size for List Decoding RANDOM 2005 . (With S. Vadhan)
The Complexity of Making Unique Choices: Approximating 1-in-kSAT APPROX 2005 .
(With L. Trevisan) Tolerant Locally Testable Codes ECCC TR05-19, 2005; RANDOM 2005 . (With A. Rudra)
Linear time encodable/decodable
codes with near-optimal
rate
IEEE Trans. on Info. Theory , Oct. 2005. (With P. Indyk)
Limits to List Decoding Reed-Solomon Codes IEEE Trans. Info. Theory, Aug. 2006; STOC 2005 . (With A. Rudra) Hardness
of Max 3SAT with no mixed clauses CCC 2005 . (With S. Khot) Maximum-Likelihood Decoding of Reed-Solomon
Codes is NP-hard SODA 2005; accepted to IEEE Trans. Info. Theory. (With
Alex Vardy) On
Profit-Maximizing Envy-free Pricing SODA 2005 . (With
J. Hartline, A. Karlin, D. Kempe, C. Kenyon, and F.
McSherry)
Iterative Decoding of Low-Density Parity Check Codes Bulletin of the EATCS.
List decoding and pseudorandom constructions AAECC 2007
Algorithmic Results in List Decoding Foundations and TrendsŪ in
Theoretical Computer Science , Volume 2, Issue 2, 2007.List Decoding in Average-Case Complexity and Pseudorandomness ITW 2006 .
Error-correcting codes and
Expander graphs SIGACT News ,35(3): 25-41,
September 2004 .
Reflections on "Improved
Decoding of Reed-Solomon and
Algebraic-geometric Codes" IEEE Information Theory Newsletter , 2002. (With M. Sudan)
Rapidly
Mixing Markov Chains: A Comparison of Techniques Unpublished , 2000. Evidence for a flat,
accelerating Universe and
the $\Lambda$CDM Model , Unpublished , 2000.
(see above for papers since 2005)
Venkatesan
Guruswami.Better Extractors for Better Codes? STOC 2004 .
Venkatesan Guruswami and Piotr Indyk.Efficiently Decodable Codes
meeting Gilbert-Varshamov bound for
Low Rates SODA 2004 .
Venkatesan Guruswami.List
Decoding with Side Information Complexity 2003 .
Venkatesan Guruswami and Piotr Indyk.Linear time encodable and list
decodable codes STOC 2003 .
Venkatesan Guruswami and Igor Shparlinski.Unconditional Proof of
Tightness of Johnson Bound SODA 2003.
V. Guruswami.Limits to list decodability of
linear codes STOC 2002 .
V. Guruswami and P. Indyk.Linear time encodable/decodable
codes with near-optimal
rate IEEE Trans. on Info. Theory
V. Guruswami and P. Indyk.Near-optimal linear time codes
for unique decoding and new list
decodable codes over smaller alphabets STOC 2002 .
Noga Alon, Venkatesan Guruswami, Tali Kaufman, and Madhu Sudan.Guessing secrets efficiently
via list decoding SODA 2002 . To appear in special issue of ACM Transactions on Algorithms for SODA'02 papers.
V. Guruswami and P. Indyk.Linear time codes to correct a
maximum possible fraction of errors Allerton 2001 .
Venkatesan Guruswami and Madhu Sudan.Decoding concatenated codes using
soft information Complexity 2002 .
V. Guruswami and Madhu Sudan.Reflections on "Improved
Decoding of Reed-Solomon and
Algebraic-geometric Codes" IEEE Information Theory Newsletter, March 2002 .
V. Guruswami and P. Indyk.Expander-based
Constructions of Efficiently Decodable Codes FOCS
2001 .
V. Guruswami.List Decoding from Erasures: Bounds
and Code
Constructions IEEE Trans. on Info. Theory , November
2003.
V. Guruswami.Constructions
of Codes from Number Fields IEEE Trans. on Info. Theory , 2003.2 page
summary .)
V. Guruswami.List
Decoding of Error-Correcting Codes
V. Guruswami and M. Sudan.Extensions to the Johnson
Bound Manuscript , February 2001.
V. Guruswami, J. Hastad, M. Sudan and D. Zuckerman.Combinatorial
Bounds for List Decoding IEEE Trans. on Information
Theory , May 2002.Preliminary version invited
to the 38th Annual Allerton
Conference on Communication, Control and Computing .
V. Guruswami, A. Sahai and M. Sudan.Soft-decision
Decoding of Chinese Remainder Codes FOCS
2000 .
V. Guruswami and Madhu
Sudan .On Representations of
Algebraic-Geometric Codes for List Decoding IEEE
Transactions on Information Theory , May 2001.
V. Guruswami and M.
Sudan .List
decoding algorithms for certain concatenated codes STOC
2000 .
Venkatesan Guruswami and Madhu Sudan .Improved
Decoding of Reed-Solomon and Algebraic-Geometric codes IEEE Transactions on
Information Theory , 45 (1999), pp. 1757-1767.
(see above for papers 2005 onwards)
V.
Guruswami, D. Micciancio, and O. Regev.The Complexity of the Covering
Radius
Problem on Lattices and Codes CCC 2004 ; Journal version in special issue of
Computational Complexity . Moses
Charikar, Venkatesan Guruswami, and Anthony Wirth.Clustering with Qualitative
Information JCSS, October 2005 (Special issue). Preliminary version in FOCS 2003 . I.
Dinur, V. Guruswami, S. Khot and O. Regev. A new multilayered PCP and the
hardness of hypergraph vertex cover STOC 2003.
(Journal version submitted to SICOMP .) I.
Dinur, V. Guruswami and S. Khot. Vertex Cover on k -uniform hypergraphs
is hard to approximate within factor (k-3-eps) ECCC Technical Report TR02-027. V.
Guruswami and P. Indyk.Embeddings and non-approximability
of geometric problems SODA 2003. L.
Engebretsen and V. Guruswami.Is Constraint Satisfaction over
two variables always easy? Random Structures and Algorithms , 2004..Preliminary version
in Proc. of RANDOM 2002. V.
Guruswami, J. Hastad
and M. Sudan.Hardness
of Approximate Hypergraph Coloring SIAM
J. Computing . Preliminary
version appeared in FOCS 2000 (the journal version is a significant
revision). M.
Charikar,
V. Guruswami, R. Kumar, S. Rajagopalan and A. Sahai. Combinatorial
Feature Selection Problems Proc. of FOCS 2000 . V.
Guruswami and S. Khanna On the
hardness of 4-coloring a 3-colorable graph SIAM J. Disc. Math , 2004. (Preliminary version in Proc.
of
Complexity 2000 , pp. 188-197.) V.
Guruswami.Inapproximability results for Set
Splitting and Satisfiability Problems
with no mixed clauses Algorithmica , 2003 (Special issue for selected papers from APPROX 2000. ) V.
Guruswami, S. Khanna ,
R. Rajaraman, F.B. Shepherd ,
M.
Yannakakis. Near-Optimal
Hardness Results and Approximation Algorithms for Edge-Disjoint Paths
and Related Problems JCSS , 67(3):473-496, 2003. (Preliminary
version in Proc. of STOC 1999 .) Yevgeniy Dodis ,
Venkatesan Guruswami and Sanjeev
Khanna The 2-Catalog Segmentation
Problem SODA 1999 . Venkatesan
Guruswami, Daniel Lewin,
Madhu Sudan and Luca TrevisanA
tight characterization of NP with 3 query PCPs FOCS 1998 . Also available as ECCC Technical
Report TR98-034 .below in the form of my Master's thesis.] V.
Guruswami.Query-efficient Checking of
Proofs
and Improved PCP Characterizations of NP HTML
abstract . V.
Guruswami and C. Pandu Rangan. A natural family of
Optimization Problems with arbitrarily small approximation
thresholds Information Processing Letters , 68 (1998),
pp. 241-248. V.
Guruswami and C.Pandu Rangan. Approximate Triclique Coloring for
Register Allocation Information Processing Letters , Vol. 60, 1996.
List Decoding of Error-Correcting Codes Query-efficient
Checking of Proofs and Improved PCP Characterizations of NP HTML
abstract of the thesis.
Intractability Results for Certain Graph-theoretic Optimization and
Approximation Problems , Senior Thesis, Indian Institute of
Technology, Madras, May 1997.
V.
Guruswami. Enumerative
Aspects of certain classes of Perfect Graphs Discrete
Mathematics , 205 (1999), pp. 97-117. V.
Guruswami, U.Rotics, M.S.Madanlal, J.A.Makowsky and
C.Pandu Rangan, Restrictions
of Minimum Spanner Problems Information and Computation ,
August 97. V.
Guruswami and C. Pandu Rangan. Algorithmic aspects of
clique-transversal and clique-independent sets , Discrete
Applied Mathematics , 100 (2000), pp. 183-202. V.
Guruswami. Maximum Cut on line and total graphs , Discrete
Applied Mathematics , 92 (1999), pp. 217-221. V.
Guruswami, C. Pandu Rangan, M.S. Chang, G.J. Chang and
C.K. Wong, The
Vertex-disjoint Triangles Problem Computing .
V.
Guruswami and C. Pandu Rangan. The Complexity of Graph
Packing Problems . Unpublished Manuscript . V.
Guruswami and C. Pandu Rangan. Algorithmic aspects of Edge
Dominating sets . Unpublished Manuscript . V.
Guruswami, G. Mohan and C. Siva Rama Murthy, Probabilistic Routing
on Wavelength-routed Multistage, Hypercube
and Debruijn Networks , Proc. of the Fourth
International Conference on High Performance Computing (HiPC '97). M.S.Madanlal,
V. Guruswami and C.Pandu Rangan, Tree
3-spanners on Interval, Permutation and Regular Bipartite graphs , Information
Processing Letters , Vol. 59, 1996. [Undergraduate
Thesis ] Intractability Results
for Certain Graph-theoretic Optimization
and
Approximation Problems , Indian Institute of Technology,
Madras, May 1997.
Copyright notice: The documents distributed by this server have
been
provided as a means to ensure timely dissemination of scholarly and
technical work on a non-commercial basis. Copyright © and all
rights therein are maintained by the authors or by other copyright
holders, notwithstanding that they have offered their works here
electronically. It is understood that all persons copying this
information will adhere to the terms and constraints invoked by each
author's copyright. These works may not be reposted without the
explicit permission of the copyright holders. ACM published documents
are ©
Copyright 199x by ACM, Inc. ; Springer-Verlag published documents
are ©
Springer-Verlag ; and IEEE published documents are ©
199x IEEE, under these
conditions . 