Atri Rudra's Publications in Chronological Order ^* (by research area)
[DBLP Listing] [Co-authors]

(Papers are ordered in reverse chronological order of first publication)

Unpublished

• Algorithmic Coding Theory
  Atri Rudra
  Book Chapter to appear in Attalah, Blanton (Eds.), CRC Handbook on Algorithms and Theory of Computation.

2010

• 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.
• 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.

2009

• 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.


• 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.

2008

• 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.


• 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.


• 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.

2007

• 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.


• 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.


• 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.


• 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.


• Lower Bounds for Randomized Read/Write Stream Algorithms
  Paul Beame, T. S. Jayram and Atri Rudra
  Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC07), Pgs. 689-698. June 2007.


• 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.

2006

• 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.


• 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.
  Prelimnary version in Proceeding of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pgs 776-782. January 2006.

2005

• 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.


• 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.


• 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.

2004

• 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)


• 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.

2003

• 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.


• Efficient Galois Field Arithmetic on SIMD Architectures
  Raghav Bhaskar, Pradeep Dubey, Vijay Kumar, Atri Rudra and Animesh Sharma
  Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Pgs 256-257. 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.

2001

• Efficient Implementation of Rijndael Encryption with Composite Field Arithmetic
  Atri Rudra, Pradeep K. Dubey, Charanjit S. Jutla, Vijay Kumar, Josyula R. Raoand Pankaj Rohatgi
  Proceedings of Workshop of Cryptographic Hardware and Embedded Systems (CHES), Pgs 171-184. May 2001.

Unpublished Manuscripts and Technical Reports

• 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.

---

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.

---