Publications of Venkatesan
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.
Following
is a list of papers (co)-authored by me, arranged 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.
Recent Papers
- Correlation Clustering with a fixed number of clusters, Manuscript, 2005. (With I. Giotis)
- Tolerant Locally Testable Codes, Manuscript, ECCC TR05-19, 2005. (With A. Rudra)
- Limits to List Decoding Reed-Solomon Codes, STOC 2005, to appear. (With A. Rudra)
- Hardness of Max 3SAT with no mixed clauses,
Complexity 2005, to appear. (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)
- Error-correcting Codes and Expander Graphs,
SIGACT News, 35(3): 25-41, Sep 2004..
- Linear
time list decoding in error-free settings, ICALP
2004. (With Piotr Indyk)
- The
Complexity of the Covering Radius Problem on Lattices and Codes,
Complexity
2004, Invited and accepted to Computational Complexity (With D. Micciancio and O. Regev)
- Better Extractors for Better Codes?, STOC
2004.
- Efficiently Decodable Codes meeting
Gilbert-Varshamov bound for Low Rates, SODA 2004. (With
Piotr Indyk)
- Clustering with Qualitative Information,
FOCS 2003, To appear in JCSS special issue. (With
Moses Charikar and Anthony Wirth)
- List Decoding with Side Information,
Complexity 2003.
- Linear time encodable and list decodable
codes, STOC 2003. (With Piotr Indyk)
- A new multilayered PCP and the hardness of
hypergraph vertex cover , STOC 2003. (With Irit Dinur,
Subhash Khot, and Oded Regev)
- Vertex Cover on k-uniform hypergraphs
is hard to approximate within factor (k-3-eps),
ECCC Technical Report TR02-027. (With Irit Dinur and Subhash Khot)
- Embeddings and non-approximability of
geometric problems, SODA 2003. (With Piotr Indyk)
- Unconditional Proof of Tightness of
Johnson Bound, SODA 2003. (With Igor Shparlinski)
- Is Constraint Satisfaction over two
variables always easy? , RANDOM 2002. (With Lars
Engebretsen)
- Limits to list decodability of linear codes ,
STOC 2002.
- Near-optimal linear time codes for
unique decoding and new list
decodable codes over smaller alphabets, STOC 2002.
(With Piotr Indyk)
- Rapidly
Mixing Markov Chains: A Comparison of Techniques. (Survey)
Coding
Theory
- V.
Guruswami.
Error-correcting codes and
Expander
graphs
SIGACT News, 35(3): 25-41,
September 2004.
- V.
Guruswami and A. Vardy.
Maximum-Likelihood Decoding of
Reed-Solomon Codes is NP-hard
To appear in
SODA 2005. Also appears as ECCC Report TR04-040.
- V.
Guruswami and P. Indyk.
Linear time list decoding in error-free settings
Proceedings of ICALP 2004.
- V.
Guruswami, D. Micciancio, and O. Regev.
The Complexity of the Covering
Radius
Problem on Lattices and Codes
Proceedings of Complexity 2004. Submitted to
special issue of Computational Complexity.
- Venkatesan
Guruswami.
Better Extractors for Better Codes?
Proceedings of STOC 2004.
- Venkatesan Guruswami and Piotr Indyk.
Efficiently Decodable Codes meeting Gilbert-Varshamov bound for
Low Rates
Proceedings of SODA 2004. Invited paper at Allerton
2003.
- Venkatesan Guruswami.
List
Decoding with Side Information
Proceedings of Complexity 2003.
- Venkatesan Guruswami and Piotr Indyk.
Linear time encodable and list
decodable codes
Proceedings of STOC 2003.
- Venkatesan Guruswami and Igor Shparlinski.
Unconditional Proof of
Tightness of Johnson Bound
Proceedings of SODA 2003.
- V. Guruswami.
Limits to list decodability of
linear codes
Proceedings of STOC 2002.
- V. Guruswami and P. Indyk.
Linear time encodable/decodable
codes with near-optimal
rate
IEEE Transactions on Information Theory, to appear.
- V. Guruswami and P. Indyk.
Near-optimal linear time codes
for unique decoding and new list
decodable codes over smaller alphabets
Proceedings of STOC 2002.
- Noga Alon, Venkatesan Guruswami, Tali Kaufman, and Madhu Sudan.
Guessing secrets efficiently
via list decoding
Proceedings of SODA 2002. Submitted to special issue of J.
Algorithms for SODA'02 papers.
- V. Guruswami and P. Indyk.
Linear time codes to correct a
maximum possible fraction of errors .
Invited to Allerton 2001.
- Venkatesan Guruswami and Madhu Sudan.
Decoding concatenated codes using
soft information
Proceedings of 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
Proceedings of 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.
(Here is a 2 page
summary.)
- V. Guruswami.
List
Decoding of Error-Correcting Codes
Ph.D thesis, MIT, August
2001.
- 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
Proceedings of 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
Proceedings of 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.
Approximation
Algorithms, Hardness of
Approximations, PCPs
- V.
Guruswami, D. Micciancio, and O. Regev.
The Complexity of the Covering
Radius
Problem on Lattices and Codes
Proceedings of Complexity 2004. Submitted to special issue of Computational Complexity.
- Moses
Charikar, Venkatesan Guruswami, and Anthony Wirth.
Clustering with Qualitative
Information
Proceedings of FOCS 2003.
- I.
Dinur, V. Guruswami, S. Khot and O. Regev.
- A new multilayered PCP and the
hardness of hypergraph vertex cover
Proceedings of STOC 2003.
(Journal version submitted to SICOMP.)
- I.
Dinur, V. Gurusswami 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
Proceedings of 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
Proceedings of SODA 1999.
- Venkatesan
Guruswami, Daniel Lewin,
Madhu Sudan and Luca Trevisan
A
tight characterization of NP with 3 query PCPs
Proceedings of FOCS 1998. Also available as ECCC Technical
Report TR98-034.
[Warning: The technical content of this paper (even
the ECCC version) is still very difficult to read without familiarity
with Hastad's paper. A more self-contained version
can be found
below in the form of my Master's thesis.]
- V.
Guruswami.
Query-efficient Checking of
Proofs
and Improved PCP Characterizations of NP
Master's Thesis, MIT, May 1999. Here is an 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.
Other
Theory Papers
Surveys,
Thesis and Reports
- V.
Guruswami. Error-correcting codes
and Expander graphs, SIGACT News, 2004, to appear.
- V.
Guruswami. Rapidly
Mixing Markov Chains: A Comparison of Techniques. (A Survey),
May 2000.
- V.
Guruswami. Evidence for a flat,
accelerating Universe and
the $\Lambda$CDM Model. (Cosmology term paper).
- V.
Guruswami.Query-efficient
Checking of Proofs and Improved PCP Characterizations of NP,
Master's thesis, MIT, May 1999.
Here is an HTML
abstract.
- V.
Guruswami.
Intractability Results for Certain Graph-theoretic Optimization and
Approximation Problems, Senior Thesis, Indian Institute of
Technology, Madras, May 1997.
Algorithmic and Structural Graph
Theory
- 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, Proceedings of WG'98,
Smolenice Castle, Slovakia, June 1998. Journal version to appear in 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.