• Essential Coding Theory
  Venkatesan Guruswami Atri Rudra and Madhu Sudan
  Book under preparation.


• Sparse Approximation List Decoding, and Uncertainty Principles
  Mahmoud Abo Khamis Anna C. Gilbert, Hung Q. Ngo and Atri Rudra
  [arXiv]


• Biological screens from linear codes: theory and tools
  Yaniv Erlich, Anna Gilbert, Hung Ngo, Atri Rudra, Nicolas Thierry-Mieg, Mary Wootters, Dina Zielinski and Or Zuk
  [bioRxiv]


• Implementation of Tetris as a Model Counter
  Jimmy Dobler and Atri Rudra
  [arXiv]


• Covering the Relational Join
  Shi Li, Sai Vikneshwar Mani Jayaraman and Atri Rudra
  [arXiv]

• FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds
  Aaron Huber, Boris Glavic, Oliver A Kennedy, Atri Rudra and Zhuoyue Zhao.
  Proceedings of the International Conference on Management of Data (SIGMOD) June 2025.

• Simple linear attention language models balance the recall-throughput tradeoff
  Simran Arora, Sabri Eyuboglu, Michael Zhang, Aman Timalsina, Silas Alberti, Dylan Zinsley, James Zou, Atri Rudra, Christopher Re.
  Proceedings of the 41st International Conference on Machine Learning (ICML) July 2024.
  Spotlight
  ES-FoMo@ICML2024 Best Paper Award
  [arXiv], [Code], [Blogpost: one, two]


• Zoology: Measuring and Improving Recall in Efficient Language Models
  Simran Arora, Sabri Eyuboglu, Aman Timalsina, Isys Johnson, Michael Poli, James Zou, Atri Rudra, Christopher Re.
  Proceedings of 12th International Conference on Learning Representations (ICLR) May 2024.
  [arXiv], [Code], [Blogpost: one, two]

• Monarch Mixer: A Simple Sub-Quadratic GEMM-Based Architecture
  Daniel Y. Fu, Simran Arora, Jessica Grogan, Isys Johnson, Sabri Eyuboglu, Armin W. Thomas, Benjamin Spector, Michael Poli, Atri Rudra and Christopher Re.
  Proceedings of the 36th Neural Information Processing Systems Conference (NeurIPS) December 2023.
  Oral
  [arXiv], [Code], [Blogpost]


• Laughing Hyena Distillery: Extracting Compact Recurrences From Convolutions
  Stefano Massaroli, Michael Poli, Daniel Y. Fu, Hermann Kumbong, Rom N. Parnichkun, Aman Timalsina, David W. Romero, Quinn McIntyre, Beidi Chen, Atri Rudra, Ce Zhang, Christopher Re, Stefano Ermon and Yoshua Bengio
  Proceedings of the 36th Neural Information Processing Systems Conference (NeurIPS) December 2023.
  [arXiv]


• Simple Hardware-Efficient Long Convolutions for Sequence Modeling
  Daniel Y. Fu, Elliot L. Epstein, Eric Nguyen, Armin W. Thomas, Michael Zhang, Tri Dao, Atri Rudra and Christopher Re.
  Proceedings of the 40th International Conference on Machine Learning (ICML) July 2023.
  [arXiv], [Code]


• Hungry Hungry Hippos: Towards Language Modeling with State Space Models
  Tri Dao, Daniel Y. Fu, Khaled K. Saab, Armin W. Thomas, Atri Rudra and Christopher Re.
  Proceedings of the 11th International Conference on Learning Representations (ICLR) May 2023.
  Spotlight
  [arXiv], [Code]


• How to Train Your HiPPO: State Space Models with Generalized Orthogonal Basis Projections
  Albert Gu^*, Isys Johnson^*, Aman Timalsina, Atri Rudra and Christopher Re.
  Proceedings of the 11th International Conference on Learning Representations (ICLR) May 2023.
  [arXiv], [Code]


• Arithmetic Circuits, Structured Matrices and (not so) Deep Learning
  Atri Rudra
  Theory of Computing Systems, volume 67, pages 592-626, 2023.
  [arXiv]


• Technical Perspective: (Pre-) Semirings Come to the Recursion Party
  Atri Rudra
  SIGMOD Record, March 2023.

• FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness
  Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra and Christopher Re.
  Proceedings of the 35th Neural Information Processing Systems Conference (NeurIPS) December 2022.
  [arXiv] [Code] [IEEE Specturm article] [Known usage]


• Monarch: Expressive Structured Matrices for Efficient and Accurate Training
  Tri Dao, Beidi Chen, Nimit Sohoni, Arjun Desai, Michael Poli, Jessica Grogan, Alexander Liu, Aniruddh Rao, Atri Rudra and Christopher Re.
  Proceedings of the 39th International Conference on Machine Learning (ICML) July 2022.
  Long talk
  Outstanding Paper Runner Up
  [arXiv] [Code]


• A qualitative, network-centric method for modeling socio-technical systems, with applications to evaluating interventions on social media platforms to increase social equality
  Kenneth Joseph, Huei-Yen Winnie Chen, Stefania Ionescu, Yuhao Du, Pranav Sankhe, Aniko Hannak and Atri Rudra
  Applied Network Science volume 7, Number 49 (2022)


• Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
  Beidi Chen, Tri Dao, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra and Christopher Re.
  Proceedings of the 10th International Conference on Learning Representations (ICLR) May 2022.
  Spotlight
  [arXiv] [Code] [Blogpost]

• Combining Recurrent, Convolutional, and Continuous-time Models with Linear State Space Layers
  Albert Gu, Isys Johnson, Karan Goel, Khaled Kamal Saab, Tri Dao, Atri Rudra and Christopher Re
  Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS) December 2021.
  [arXiv][Code]


• Scatterbrain: Unifying Sparse and Low-rank Attention
  Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra and Christopher Re
  Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS) December 2021.
  [arXiv][Code]

• HiPPO: Recurrent Memory with Optimal Polynomial Projections
  Albert Gu Tri Dao, Stefano Ermon, Atri Rudra and Christopher Re
  To appear in the Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS) December 2020.
  Spotlight.
  [arXiv][Code][Blog post]


• Transformative Social Innovation as a Lens for ML for Good
  Melanie Sage, Atri Rudra, Kenneth Joseph, Huei-Yen Chen and Varun Chandola
  In CSCW 2020 Workshop: Collective Organizing and Social Responsibility, October 2020.
  Not peer-reviewed


• Sparse Recovery for Orthogonal Polynomial Transforms
  Anna Gilbert Albert Gu, Christopher Re, Atri Rudra and Mary Wootters
  In the Proceedings of 47th International Colloquium on Automata Languages and Programming (ICALP), July 2020.
  [arXiv]


• Kaleidoscope: An Efficient Learnable Representation For All Structured Linear Maps
  Tri Dao Nimit Sohoni, Albert Gu, Matthew Eichhorn, Amit Blonder, Megan Leszczynski, Atri Rudra, Christopher Re
  In the Proceedings of 8th International Conference on Learning Representations (ICLR) April 2020.
  Spotlight.
  [Code][Blog post]

• Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations
  Tri Dao Albert Gu, Matthew Eichhorn, Atri Rudra, Christopher Re
  In the Proceedings of the 36th International Conference on Machine Learning (ICML) June 2019.
  Full Oral presentation.
  [arXiv][Code][Blog post]


• Topology Dependent Bounds for FAQs
  Michael Langberg Shi Li, Sai Vikneshwar Mani Jayaraman, Atri Rudra
  In the Proceedings of the 38th Symposium on Principles of Database Systems (PODS) July 2019.
  [arXiv]

• Learning Compressed Transforms with Low Displacement Rank
  Anna T. Thomas* Albert Gu*, Tri Dao, Atri Rudra, Christopher Re
  Proceedings of the 31st Neural Information Processing Systems Conference (NeurIPS) December 2018.
  [arXiv][Code]


• Hypertree Decompositions Revisited for PGMs
  Aarthy Shivram Arun Sai Vikneshwar Mani Jayaraman, Christopher Re and Atri Rudra
  Star AI July 2018.
  [arXiv]


• General Strong Polarization
  Jaroslaw Blasiok Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra and Madhu Sudan
  Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC) June 2018.
  [arXiv ECCC]


• Learning Invariance with Compact Transforms
  Anna T. Thomas Albert Gu, Tri Dao, Atri Rudra and Christopher Re
  ICLR Workshop Track April 2018.
  Full version in NeurIPS 2018 above.


• A Two-pronged Progress in Structured Dense Matrix Vector Multiplication
  Christopher De Sa Albert Gu, Rohan Puttagunta, Christopher Re and Atri Rudra
  Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) January 2018.
  [arXiv]


• Average-radius list-recoverability of random linear codes
  Atri Rudra and Mary Wootters
  Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) January 2018.
  [arXiv]

• Juggling Functions Inside a Database
  Mahmoud Abo Khamis Hung Q. Ngo and Atri Rudra
  SIGMOD Record March 2017. (Survey accompanying the 2016 ACM SIGMOD Research Highlights award for the PODS 2016 paper.)
  [arXiv]


• Tight Network Topology Dependent Bounds on Rounds of Communication
  Arkadev Chattopadhyay Michael Langberg, Shi Li and Atri Rudra
  Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms January 2017.
  [ECCC arXiv]
  


• Answering FAQs in CSPs probabilistic graphical models, databases, logic and matrix operations (invited talk)
  Atri Rudra
  Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) June 2017.
  Accompanying paper to the Plenary invited talk at STOC 2017 Theory Fest for the PODS 2016 paper.
  
  [Slides for the talk: PPTX]

• FAQ: Questions Asked Frequently
  Mahmoud Abo Khamis Hung Q. Ngo and Atri Rudra
  Proceedings of PODS June 2016.
  Best paper award winner
  2016 ACM SIGMOD Research Highlights award
  Invited as a Plenary invited talk at STOC 2017 Theory Fest
  [Talk: @Simons (Video Slides)]
  [arXiv]

• The Range of Topological Effects on Communication
  Arkadev Chattopadhyay and Atri Rudra
  Proceedings of ICALP (Track C) July 2015.
  [arXiv]


• A Multiple Server Scheme for Fingerprint Fuzzy Vaults
  Jesse Hartloff Matthew Morse, Bingsheng Zhang, Thomas Effland, Jennifer Cordaro, Jim Schuler, Sergey Tulyakov, Atri Rudra and Venu Govindaraju
  Proceedings of CVPR Workshop on Biometrics June 2015.
  [PDF]


• Join Processing for Graph Patterns: An Old Dog with New Tricks
  Dung Nguyen Molham Aref, Martin Bravenboer, George Kollias, Hung Q. Ngo, Christopher Re and Atri Rudra
  Proceedings of GRADES 2015 (co-located with SIGMOD/PODS 2015) June 2015.
  [arXiv]


• Joins via Geometric Resolutions: Worst-case and Beyond
  Mahmoud Abo Khamis Hung Q. Ngo, Christopher Re and Atri Rudra
  Proceedings of the 34th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) June 2015.
  Journal version: ACM Transactions on Database Systems (TODS) 41(4), December 2016.
  [arXiv]
  [TODS version]


• It'll probably work out: improved list-decoding through random operations
  Atri Rudra and Mary Wootters
  Proceedings of 6th Innovations in Theoretical Computer Science (ITCS) January 2015.
  [arXiv ECCC]

• Secure fingerprint hashes using subsets of local structures
  Tom Effland Mariel Schneggenburger, Jim Schuler, Bingsheng Zhang, Jesse Hartloff, Jimmy Dobler, Sergey Tulyakov, Atri Rudra and Venu Govindaraju
  Proceedings of SPIE 9075 Biometric and Surveillance Technology for Human and Activity Identification XI, May 2014.
  [PDF]


• Beyond worst-case analysis for joins with minesweeper
  Hung Q. Ngo Dung T. Nguyen, Christopher Re and Atri Rudra
  Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) June 2014.
  [arXiv]


• Every list-decodable code for high noise has abundant near-optimal rate puncturings
  Atri Rudra and Mary Wootters
  Proceedings of the 46th Annual Symposium on the Theory of Computing (STOC) June 2014.
  (Blog mentions: one two)
  [arXiv ECCC]


• Secure Fingerprint MatchingWith Generic Local Structures
  Matthew Morse Jesse Hartloff, Thomas Effland, Jim Schuler, Jennifer Cordaro Sergey Tulyakov, Atri Rudra and Venu Govindaraju
  Proceedings of IEEE Computer Society Workshop on Biometrics (CVPR-W) June 2014.
  [PDF]


• Energy Aware Algorithmic Engineering
  Swapnoneel Roy Atri Rudra and Akshat Verma
  Proceedings of the IEEE 22nd International Symposium on Modeling Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), September 2014.
  [PDF]


• Topology matters in communication
  Arkadev Chattopadhyay Jaikumar Radhakrishnan and Atri Rudra
  Proceedings of 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS) October 2014.
  [ECCC]

• An energy complexity model for algorithms
  Swapnoneel Roy Atri Rudra and Akshat Verma
  Proceedings of the 4th Innovations in Theoretical Computer Science (ITCS) January 2013.
  [PDF]


• Security analysis for fingerprint fuzzy vaults
  Jesse Hartloff Maxwell Bileschi, Sergey Tulyakov, Jimmy Dobler, Atri Rudra and Venu Govindaraju
  SPIE (Conference on Biometric and Surveillance Technology for Human and Activity Identification X) volume 8712, May 2013.
  [PDF]


• Towards fingerprints as strings: Secure indexing for fingerprint matching
  Jesse Hartloff Jimmy Dobler, Sergey Tulyakov, Atri Rudra and Venu Govindaraju
  Proceedings of the 6th IAPR International Conference on Biometrics (ICB) June 2013.
  [PDF]


• l₂/l₂-Foreach Sparse Recovery with Low Risk
  Anna C. Gilbert Hung Q. Ngo, Ely Porat, Atri Rudra and Martin J. Strauss
  Proceedings of the 40th International Colloquium on Automata Languages, and Programming (ICALP), July 2013.
  [arXiv]


• Accurate Decoding of Pooled Sequenced Data Using Compressed Sensing
  Denisa Duma Mary Wootters, Anna C. Gilbert, Hung Q. Ngo, Atri Rudra, Matthew Alpert, Timothy J. Close, Gianfranco Ciardo and Stefano Lonardi
  Proceedings of the 13th International Workshop on Algorithms in Bioinformatics (WABI) September 2013.
  [arXiv]


• Skew strikes back: new developments in the theory of join algorithms
  Hung Q. Ngo Christopher Re and Atri Rudra
  SIGMOD Record 42(4) Pgs. 5-16, December 2013.
  Invited paper.
  [Blog mention: one]
  [arXiv]

• Recovering simple signals
  Anna C. Gilbert Brett Hemenway, Atri Rudra, Martin J. Strauss and Mary Wootters
  Proceedings of 2012 Information Theory and Applications Workshop (ITA) February 2012.
  [PDF]


• Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion
  Hung Q. Ngo Ely Porat and Atri Rudra
  Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS) March 2012.
  [PDF]


• Worst-case optimal join algorithms
  Hung Q. Ngo Ely Porat, Christopher Re and Atri Rudra
  Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) May 2012.
  Best paper award winner
  Journal version: JACM 2018.
  [arXiv] (Read the SIGMOD RECORD version instead.)


• PGV: A Storage Enforcing Remote Verification Scheme
  Mohammad Iftekhar Husain Steve Uurtamo, Steven Y. Ko, Atri Rudra and Ramalingam Sridhar
  Proceedings of the IEEE 31st Symposium on Reliable Distributed Systems (SRDS) October 2012.
  [arXiv ECCC]

• Polynomial Fitting of Data Streams with Applications to Codeword Testing
  Andrew McGregor Atri Rudra and Steve Uurtamo
  Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS) March 2011.
  [PDF]


• Singlehop Collaborative Feedback Primitives for Threshold Querying in Wireless Sensor Networks
  Murat Demirbas Serafettin Tasci, Hanifi Gunes and Atri Rudra
  Proceedings of the 25th IEEE International Parallel & Distributed Processing Symposium (IPDPS) May 2011.
  [PDF]


• Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications
  Hung Q. Ngo Ely Porat and Atri Rudra
  Proceedings of 38th International Colloquium on Automata Languages and Programming (ICALP), July 2011.
  [PDF]


• Symmetric Functions Capture General Functions
  Richard J. Lipton Kenneth W. Regan and Atri Rudra
  Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS) August 2011.
  [PDF]


• Flexible coloring
  Xiaozhou Li Atri Rudra and Ram Swaminathan
  Information Processing Letters 111(11) Pgs. 538-540, 2011.
  [PDF]

• Efficiently Decodable Non-adaptive Group Testing
  Piotr Indyk Hung Q. Ngo and Atri Rudra
  Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). January 2010.
  [PDF]


• Analyzing Nonblocking Switching Networks using Linear Programming (Duality)
  Hung Q. Ngo Atri Rudra, Anh N. Le and Thanh-Nhan Nguyen
  Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM) March 2010.
  [arXiv]


• Data Stream Algorithms for Codeword Testing
  Atri Rudra and Steve Uurtamo
  Proceedings of the 37th International Colloquium on Automata Languages and Programming (ICALP), July 2010.
  [arXiv]


• k⁺ Decision Trees
  James Aspnes Eric Blais, 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.
  [Extended Abstract Full version]


• Two Theorems on List Decoding
  Atri Rudra and Steve Uurtamo
  Proceedings of the 14th International Workshop on Randomization and Computation (RANDOM) September 2010.
  [arXiv ECCC]


• When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
  Nikhil Bansal Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan and Atri Rudra
  Algorithmica 63(4) Pgs. 733-762, 2012. (ESA special issue)
  Preliminary version in Proceedings of the 18th Annual European Symposium on Algorithsm (ESA) September 2010.
  Co-winner of the ESA Best paper award
  [arXiv]

2009 and earlier (with abstracts)

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


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

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

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

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

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

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

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

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

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