Atri Rudra

Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh: Improved Approximation Algorithms for the Spanning Star Forest Problem. Algorithmica 65(3): 498-516 (2013)

Swapnoneel Roy, Atri Rudra, Akshat Verma: An energy complexity model for algorithms. ITCS 2013: 283-304

Hung Q. Ngo, Dung T. Nguyen, Christopher Re, Atri Rudra: Towards Instance Optimal Join Algorithms for Data in Indexes. CoRR abs/1302.0914 (2013)

Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra, Martin J. Strauss: L2/L2-foreach sparse recovery with low risk. CoRR abs/1304.6232 (2013)

Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra: When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. Algorithmica 63(4): 733-762 (2012)

Anna C. Gilbert, Brett Hemenway, Atri Rudra, Martin J. Strauss, Mary Wootters: Recovering simple signals. ITA 2012: 382-391

Hung Q. Ngo, Ely Porat, Christopher Ré, Atri Rudra: Worst-case optimal join algorithms: [extended abstract]. PODS 2012: 37-48

Mohammad Iftekhar Husain, Steve Uurtamo, Steven Y. Ko, Atri Rudra, Ramalingam Sridhar: PGV: A Storage Enforcing Remote Verification Scheme. SRDS 2012: 390-395

Hung Q. Ngo, Ely Porat, Atri Rudra: Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion. STACS 2012: 230-241

Richard J. Lipton, Kenneth W. Regan, Atri Rudra: Simulating Special but Natural Quantum Circuits. CoRR abs/1201.3306 (2012)

Hung Q. Ngo, Ely Porat, Christopher Ré, Atri Rudra: Worst-case Optimal Join Algorithms. CoRR abs/1203.1952 (2012)

Hung Q. Ngo, Atri Rudra, Anh N. Le, Thanh-Nhan Nguyen: Analyzing Nonblocking Switching Networks using Linear Programming (Duality). CoRR abs/1204.3180 (2012)

Mohammad Iftekhar Husain, Steven Y. Ko, Atri Rudra, Steve Uurtamo: Almost Universal Hash Families are also Storage Enforcing. CoRR abs/1205.1462 (2012)

Charanjit S. Jutla, Vijay Kumar, Atri Rudra: On the Circuit Complexity of Composite Galois Field Transformations. Electronic Colloquium on Computational Complexity (ECCC) 19: 93 (2012)

Xiaozhou Li, Atri Rudra, Ram Swaminathan: Flexible coloring. Inf. Process. Lett. 111(11): 538-540 (2011)

Robert Krauthgamer, Aranyak Mehta, Atri Rudra: Pricing commodities. Theor. Comput. Sci. 412(7): 602-613 (2011)

Venkatesan Guruswami, Atri Rudra: Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes. IEEE Transactions on Information Theory 57(2): 705-717 (2011)

Atri Rudra: Limits to List Decoding of Random Codes. IEEE Transactions on Information Theory 57(3): 1398-1408 (2011)

Hung Q. Ngo, Ely Porat, Atri Rudra: Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications - (Extended Abstract). ICALP (1) 2011: 557-568

Murat Demirbas, Serafettin Tasci, Hanifi Gunes, Atri Rudra: Singlehop Collaborative Feedback Primitives for Threshold Querying in Wireless Sensor Networks. IPDPS 2011: 322-333

Richard J. Lipton, Kenneth W. Regan, Atri Rudra: Symmetric Functions Capture General Functions. MFCS 2011: 436-447

Andrew McGregor, Atri Rudra, Steve Uurtamo: Polynomial Fitting of Data Streams with Applications to Codeword Testing. STACS 2011: 428-439

Atri Rudra, Swapnoneel Roy: An FPTAS for the Lead-Based Multiple Video Transmission LMVT Problem. CoRR abs/1102.4129 (2011)

Mohammad Iftekhar Husain, Steven Y. Ko, Atri Rudra, Steve Uurtamo: Storage Enforcement with Kolmogorov Complexity and List Decoding. CoRR abs/1104.3025 (2011)

Mohammad Iftekhar Husain, Steven Y. Ko, Atri Rudra, Steve Uurtamo: Storage Enforcement with Kolmogorov Complexity and List Decoding. Electronic Colloquium on Computational Complexity (ECCC) 18: 80 (2011)

Matthew Cary, Atri Rudra, Ashish Sabharwal, Erik Vee: Floodlight illumination of infinite wedges. Comput. Geom. 43(1): 23-34 (2010)

Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko: Dynamic pricing for impatient bidders. ACM Transactions on Algorithms 6(2) (2010)

Don Coppersmith, Lisa Fleischer, Atri Rudra: Ordering by weighted number of wins gives a good ranking for weighted tournaments. ACM Transactions on Algorithms 6(3) (2010)

Venkatesan Guruswami, Atri Rudra: The existence of concatenated codes list-decodable up to the hamming bound. IEEE Transactions on Information Theory 56(10): 5195-5206 (2010)

James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, Steve Uurtamo: k ⁺ Decision Trees - (Extended Abstract). ALGOSENSORS 2010: 74-88

Atri Rudra, Steve Uurtamo: Two Theorems on List Decoding - (Extended Abstract). APPROX-RANDOM 2010: 696-709

Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra: When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings - (Extended Abstract). ESA (2) 2010: 218-229

Atri Rudra, Steve Uurtamo: Data Stream Algorithms for Codeword Testing. ICALP (1) 2010: 629-640

Hung Q. Ngo, Atri Rudra, Anh N. Le, Thanh-Nhan Nguyen: Analyzing Nonblocking Switching Networks using Linear Programming (Duality). INFOCOM 2010: 2696-2704

Piotr Indyk, Hung Q. Ngo, Atri Rudra: Efficiently Decodable Non-adaptive Group Testing. SODA 2010: 1126-1142

Atri Rudra, Steve Uurtamo: Two Theorems in List Decoding. CoRR abs/1001.1781 (2010)

Nikhil Bansal, Anupam Gupta, Viswanath Nagarajan, Atri Rudra: When LP is the Cure for Your Matching Woes: Approximating Stochastic Matchings. CoRR abs/1003.0167 (2010)

Atri Rudra, Steve Uurtamo: Data Stream Algorithms for Codeword Testing. CoRR abs/1004.4601 (2010)

Nikhil Bansal, Anupam Gupta, Jian Li, Julián Mestre, Viswanath Nagarajan, Atri Rudra: When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. CoRR abs/1008.5356 (2010)

Atri Rudra, Steve Uurtamo: Two Theorems in List Decoding. Electronic Colloquium on Computational Complexity (ECCC) 17: 7 (2010)

Venkatesan Guruswami, Atri Rudra: Error correction up to the information-theoretic limit. Commun. ACM 52(3): 87-95 (2009)

Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman: Testing low-degree polynomials over prime fields. Random Struct. Algorithms 35(2): 163-193 (2009)

Venkatesan Guruswami, Atri Rudra: Better Binary List Decodable Codes Via Multilevel Concatenation. IEEE Transactions on Information Theory 55(1): 19-26 (2009)

Atri Rudra: Limits to List Decoding Random Codes. COCOON 2009: 27-36

Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Atri Rudra: Approximating Matches Made in Heaven. ICALP (1) 2009: 266-278

Murat Demirbas, Carole Rudra, Atri Rudra, Murat Ali Bayir: iMAP: Indirect Measurement of Air Pollution with Cellphones. PerCom Workshops 2009: 1-6

Atri Rudra: Limits to List Decoding Random Codes. Electronic Colloquium on Computational Complexity (ECCC) 16: 13 (2009)

Ning Chen, Atri Rudra: Walrasian Equilibrium: Hardness, Approximations and Tractable Instances. Algorithmica 52(1): 44-64 (2008)

Venkatesan Guruswami, Atri Rudra: Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy. IEEE Transactions on Information Theory 54(1): 135-150 (2008)

Venkatesan Guruswami, Atri Rudra: Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes. IEEE Conference on Computational Complexity 2008: 163-174

Robert Krauthgamer, Aranyak Mehta, Vijayshankar Raman, Atri Rudra: Greedy List Intersection. ICDE 2008: 1033-1042

Venkatesan Guruswami, Atri Rudra: Concatenated codes can achieve list-decoding capacity. SODA 2008: 258-267

Atri Rudra: List Decoding near Capacity: Folded RS Codes. Encyclopedia of Algorithms 2008

Venkatesan Guruswami, Atri Rudra: Soft decoding, dual BCH codes, and better list-decodable eps-biased codes. Electronic Colloquium on Computational Complexity (ECCC) 15(036) (2008)

Venkatesan Guruswami, Atri Rudra: Concatenated codes can achieve list-decoding capacity. Electronic Colloquium on Computational Complexity (ECCC) 15(054) (2008)

Atri Rudra: Efficient List Decoding of Explicit Codes with Optimal Redundancy. AAECC 2007: 38-46

Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh: Improved Approximation Algorithms for the Spanning Star Forest Problem. APPROX-RANDOM 2007: 44-58

Venkatesan Guruswami, Atri Rudra: Better Binary List-Decodable Codes Via Multilevel Concatenation. APPROX-RANDOM 2007: 554-568

Matthew Cary, Atri Rudra, Ashish Sabharwal: Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics. ICALP 2007: 949

Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, Maxim Sviridenko: Dynamic pricing for impatient bidders. SODA 2007: 726-735

Paul Beame, T. S. Jayram, Atri Rudra: Lower bounds for randomized read/write stream algorithms. STOC 2007: 689-698

Robert Krauthgamer, Aranyak Mehta, Atri Rudra: Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations. WAOA 2007: 1-14

Venkatesan Guruswami, Atri Rudra: Better Binary List-Decodable Codes via Multilevel Concatenation. Electronic Colloquium on Computational Complexity (ECCC) 14(109) (2007)

Venkatesan Guruswami, Atri Rudra: Limits to List Decoding Reed-Solomon Codes. IEEE Transactions on Information Theory 52(8): 3642-3649 (2006)

Don Coppersmith, Lisa Fleischer, Atri Rudra: Ordering by weighted number of wins gives a good ranking for weighted tournaments. SODA 2006: 776-782

Venkatesan Guruswami, Atri Rudra: Explicit capacity-achieving list-decodable codes. STOC 2006: 1-10

Venkatesan Guruswami, Atri Rudra: Tolerant Locally Testable Codes. APPROX-RANDOM 2005: 306-317

Vijay Kumar, Atri Rudra: Approximation Algorithms for Wavelength Assignment. FSTTCS 2005: 152-163

Matthew Cary, Atri Rudra, Ashish Sabharwal: On the Hardness of Embeddings Between Two Finite Metrics. ICALP 2005: 1412-1423

Venkatesan Guruswami, Atri Rudra: Limits to list decoding Reed-Solomon codes. STOC 2005: 602-609

Ning Chen, Atri Rudra: Walrasian Equilibrium: Hardness, Approximations and Tractable Instances. WINE 2005: 141-150

Venkatesan Guruswami, Atri Rudra: Explicit Codes Achieving List Decoding Capacity: Error-correction with Optimal Redundancy. CoRR abs/cs/0511072 (2005)

Venkatesan Guruswami, Atri Rudra: Tolerant Locally Testable Codes. Electronic Colloquium on Computational Complexity (ECCC)(019) (2005)

Don Coppersmith, Atri Rudra: On the Robust Testability of Product of Codes. Electronic Colloquium on Computational Complexity (ECCC)(104) (2005)

Don Coppersmith, Lisa Fleischer, Atri Rudra: Ordering by weighted number of wins gives a good ranking for weighted tournaments. Electronic Colloquium on Computational Complexity (ECCC)(131) (2005)

Venkatesan Guruswami, Atri Rudra: Explicit Capacity-Achieving List-Decodable Codes. Electronic Colloquium on Computational Complexity (ECCC)(133) (2005)

Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu: Online learning in online auctions. Theor. Comput. Sci. 324(2-3): 137-146 (2004)

Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman: Testing Low-Degree Polynomials over Prime Fields. FOCS 2004: 423-432

Rahul Garg, Vijay Kumar, Atri Rudra, Akshat Verma: Coalitional games on graphs: core structure, substitutes and frugality. ACM Conference on Electronic Commerce 2003: 248-249

Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu: Online learning in online auctions. SODA 2003: 202-204

Raghav Bhaskar, Pradeep K. Dubey, Vijay Kumar, Atri Rudra: Efficient galois field arithmetic on SIMD architectures. SPAA 2003: 256-257

Atri Rudra, Pradeep K. Dubey, Charanjit S. Jutla, Vijay Kumar, Josyula R. Rao, Pankaj Rohatgi: Efficient Rijndael Encryption Implementation with Composite Field Arithmetic. CHES 2001: 171-184