Atri Rudra's Publications by Research Area* (by
year)
This page is horribly out-of-date and not maintained. See this page for a current list of papers.
[DBLP Listing] [Co-authors]
Coding Theory
Algorithmic Game Theory
Sublinear Algorithms
Approximation and Online Algorithms
Lower bounds and other Complexity results
Other work
(Within each topic, the papers are ordered in reverse chronological
order of first publication)
Coding Theory
- Algorithmic Coding Theory
-
Atri Rudra
-
Book Chapter to appear in Attalah, Blanton (Eds.), CRC Handbook on Algorithms and Theory of Computation.
- Efficiently Decodable Non-adaptive
Group Testing
-
Piotr Indyk, Hung Q. Ngo and Atri Rudra
-
To Appear in 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). January 2010.
- Error Correction Up to the Information-Theoretic Limit
-
Venkatesan Guruswami and Atri Rudra
-
Communications of the ACM (Research Highlights Section), Pgs. 87-95. March 2009.
- Limits to List Decoding Random Codes
-
Atri Rudra
-
Proceedings of the 15th International Computing and Combinatorics Conference (COCOON), Pgs. 27-36. July 2009.
-
ECCC Tech Report TR09-013.
- Soft decoding, dual BCH codes, and better list-decodable e-biased codes
-
Venkatesan Guruswami and Atri Rudra
-
Proceeding of the 23rd IEEE Conference on
Computational Complexity (CCC), Pgs. 163-174. June 2008.
- Efficient List Decoding of Explicit Codes with Optimal Redundancy
-
Atri Rudra
-
Proceedings of the 7th Symposium on Applied algebra, Algebraic algorithms, and Error Correcting Codes (AAECC), Pgs. 38-46. December 2007.
-
Companion paper to an invited talk.
- Concatenated codes can achieve list-decoding capacity
-
Venkatesan Guruswami and Atri Rudra
-
Proceeding of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pgs. 258-267. January 2008.
-
Better Binary List-Decodable Codes via Multilevel Concatenation
-
Venkatesan Guruswami and Atri Rudra
-
Proceedings of the 11th International Workshop on Randomization and Computation (RANDOM), Pgs. 554-568. August 2007.
- List Decoding and Property Testing of Error Correcting Codes
-
Atri Rudra
-
Ph.D. thesis, University of Washington. August 2007.
- Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy
-
Venkatesan Guruswami and Atri Rudra
-
IEEE Transactions on Information Theory, 54(1), Pgs. 135 - 150. January 2008.
-
Preliminary version in Proceedings of the 38th ACM Symposium on Theory of Computing (STOC), Pgs. 1-10. May 2006.
-
Also invited paper, Forty-Fourth Annual Allerton Conference on Communication, Control, and Computing.
- On the Robust Testability of Product of Codes
-
Don Coppersmith and Atri Rudra
-
Electronic Colloquium on Computational Complexity (ECCC) Tech Report TR05-104. 2005.
-
Tolerant Locally Testable codes
-
Venkatesan Guruswami and Atri Rudra
-
Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM), Pgs. 306-317. August 2005.
- Limits to list decoding Reed-Solomon codes
-
Venkatesan Guruswami and Atri Rudra
-
IEEE Transactions on Information Theory 52(8), Pgs. 3642-3649. August 2006.
-
Preliminary version in the Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), Pgs 602-609. May 2005.
-
Testing Low-Degree Polynomials Over Prime Fields
-
Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra and David Zuckerman
-
Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Pgs 423-432. October 2004.
Algorithmic Game Theory
- Approximating Matches Made in Heaven
-
Ning Chen, Nicole Immorlica, Anna Karlin, Mohammad Mahdian, and Atri Rudra
-
Proceedings of the 36th International Colloquium on
Automata, Languages and
Programming (ICALP), Pgs. 266-278. July 2009.
- Pricing commodities, or How to sell when buyers have restricted valuations
-
Robert Krauthgamer, Aranyak Mehta and Atri Rudra
-
Proceedings of the 5th Workshop on Approximation and Online Algorithms (WAOA), Pgs. 1-14. October 2007.
-
Invited to a special issue of Theoretical Computer Science on WAOA07.
-
Dynamic Pricing for Impatient Bidders
-
Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber and Maxim Sviridenko
-
Accepted for publication in ACM Transactions on Algorithms (TALG), 2008.
-
Preliminary version in Proceeding of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pgs. 726-735. January 2007.
-
Walrasian Equilibrium: Hardness, Approximations and Tractable Instances
-
Ning Chen and Atri Rudra
-
Proceedings of the 1st Workshop on Internet and Network Economics (WINE), Pgs 141-150. December 2005.
- Coalition Games on Graphs: core structure, substitutes and frugality
-
Rahul Garg, Vijay Kumar, Atri Rudra and Akshat Verma
-
Proceedings of the ACM Conference on Electronic Conference (EC), Pgs 248-249. June 2003.
- Online Learning in Online Auctions
-
Avrim Blum, Vijay Kumar, Atri Rudra and Felix Wu
-
Theoretical Computer Science (Special Issue on Online Algorithms) 324(2-3), Pgs 137-146. September 2004.
-
Preliminary version in the Proceeding of 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pgs 202-204. January 2003.
Sublinear Algorithms
Approximation and Online Algorithms
- See Approximating Matches Made in Heaven
-
Greedy List Intersection
-
Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman and Atri Rudra
-
Proceedings of the 24th International Conference on Data Engineering (ICDE), Pgs. 1033-1042. April 2008.
-
Improved Approximation Algorithms for the Spanning Star Forest Problem
-
Ning Chen, Roee Engelberg, Cam Thach Nguyen, Prasad Ragahvendra, Atri Rudra
and Gyanit Singh
-
Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Pgs. 44-58. August 2007.
- See Pricing commodities, or How to sell when buyers have restricted valuations
- See
Dynamic Pricing for Impatient Bidders
-
Ordering by Weighted Number of Wins Gives a Good Ranking for Weighted Tournaments
-
Don Coppersmith, Lisa Fleischer and Atri Rudra
-
Accepted for publication in ACM Transactions on Algorithms (TALG), 2008.
-
Preliminary version in Proceeding of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pgs 776-782. January 2006.
-
Approximation Algorithms for Wavelength Assignment
-
Vijay Kumar and Atri Rudra
-
Proceedings of the 25th Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), Pgs 152-163.
- December 2005.
Lower bounds and other Complexity results
- k+ Decision Trees
-
James Aspnes, Eric Blias, Murat Demirbas, Ryan O'Donnell, Atri Rudra and Steve Uurtamo
-
Proceedings of the 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), Pgs. 74-88. July, 2010.
- See Lower Bounds for Randomized Read/Write Stream Algorithms
- Floodlight Illumination of Infinite Wedges
-
Matthew Cary, Ashish Sabharwal , Atri Rudra and Erik Vee
-
Abstract in the 14th Annual Fall Workshop on Computational Geometry. November 2004.
-
Full version invited to Computation Geometry: Theory and Applications (CGTA)
-
On the Relativization of Probabilistically Checkable Proofs
-
Charanjit S. Jutla, Anindya C. Patthak and Atri Rudra
-
Manuscript, 2005.
-
On the Circuit Complexity of Isomorphic Galois Field Transformations
-
Charanjit S. Jutla, Vijay Kumar and Atri Rudra
-
IBM Research Report RC22652.
Other work
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.