# Atri Rudra

According to our database

Collaborative distances:

^{1}, Atri Rudra authored at least 85 papers between 2001 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2018

Worst-case Optimal Join Algorithms.

J. ACM, 2018

General strong polarization.

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

A Two-pronged Progress in Structured Dense Matrix Vector Multiplication.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Average-radius list-recoverability of random linear codes.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Learning Compressed Transforms with Low Displacement Rank.

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Learning Invariance with Compact Transforms.

Proceedings of the 6th International Conference on Learning Representations, 2018

2017

Juggling Functions Inside a Database.

SIGMOD Record, 2017

Answering FAQs in CSPs, probabilistic graphical models, databases, logic and matrix operations (invited talk).

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Tight Network Topology Dependent Bounds on Rounds of Communication.

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

List Decoding near Capacity: Folded RS Codes.

Encyclopedia of Algorithms, 2016

Efficient Decodable Group Testing.

Encyclopedia of Algorithms, 2016

FAQ: Questions Asked Frequently.

Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016

2015

Join Processing for Graph Patterns: An Old Dog with New Tricks.

Proceedings of the Third International Workshop on Graph Data Management Experiences and Systems, 2015

Joins via Geometric Resolutions: Worst-case and Beyond.

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

It'll Probably Work Out: Improved List-Decoding Through Random Operations.

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

The Range of Topological Effects on Communication.

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

A multiple server scheme for fingerprint fuzzy vaults.

Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition Workshops, 2015

2014

Bidirectional data verification for cloud storage.

J. Network and Computer Applications, 2014

Every list-decodable code for high noise has abundant near-optimal rate puncturings.

Proceedings of the Symposium on Theory of Computing, 2014

Beyond worst-case analysis for joins with minesweeper.

Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2014

Energy Aware Algorithmic Engineering.

Proceedings of the IEEE 22nd International Symposium on Modelling, 2014

Topology Matters in Communication.

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Secure Fingerprint Matching with Generic Local Structures.

Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2014

2013

Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword.

Theory of Computing, 2013

Skew strikes back: new developments in the theory of join algorithms.

SIGMOD Record, 2013

Accurate Decoding of Pooled Sequenced Data Using Compressed Sensing.

Proceedings of the Algorithms in Bioinformatics - 13th International Workshop, 2013

An energy complexity model for algorithms.

Proceedings of the Innovations in Theoretical Computer Science, 2013

Towards fingerprints as strings: Secure indexing for fingerprint matching.

Proceedings of the International Conference on Biometrics, 2013

ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk.

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

On the Circuit Complexity of Composite Galois Field Transformations.

Electronic Colloquium on Computational Complexity (ECCC), 2012

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings.

Algorithmica, 2012

Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion.

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

PGV: A Storage Enforcing Remote Verification Scheme.

Proceedings of the IEEE 31st Symposium on Reliable Distributed Systems, 2012

Worst-case optimal join algorithms: [extended abstract].

Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

Recovering simple signals.

Proceedings of the 2012 Information Theory and Applications Workshop, 2012

2011

Limits to List Decoding of Random Codes.

IEEE Trans. Information Theory, 2011

Soft Decoding, Dual BCH Codes, and Better List-Decodable varepsilon-Biased Codes.

IEEE Trans. Information Theory, 2011

Pricing commodities.

Theor. Comput. Sci., 2011

Flexible coloring.

Inf. Process. Lett., 2011

Storage Enforcement with Kolmogorov Complexity and List Decoding.

Electronic Colloquium on Computational Complexity (ECCC), 2011

Polynomial Fitting of Data Streams with Applications to Codeword Testing.

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Symmetric Functions Capture General Functions.

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Singlehop Collaborative Feedback Primitives for Threshold Querying in Wireless Sensor Networks.

Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications - (Extended Abstract).

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

The existence of concatenated codes list-decodable up to the hamming bound.

IEEE Trans. Information Theory, 2010

Two Theorems in List Decoding.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Floodlight illumination of infinite wedges.

Comput. Geom., 2010

Efficiently Decodable Non-adaptive Group Testing.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Analyzing Nonblocking Switching Networks using Linear Programming (Duality).

Proceedings of the INFOCOM 2010. 29th IEEE International Conference on Computer Communications, 2010

Data Stream Algorithms for Codeword Testing.

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings - (Extended Abstract).

Proceedings of the Algorithms, 2010

Two Theorems on List Decoding - (Extended Abstract).

Proceedings of the Approximation, 2010

k

^{ + }Decision Trees - (Extended Abstract).
Proceedings of the Algorithms for Sensor Systems, 2010

2009

Error correction up to the information-theoretic limit.

Commun. ACM, 2009

iMAP: Indirect Measurement of Air Pollution with Cellphones.

Proceedings of the Seventh Annual IEEE International Conference on Pervasive Computing and Communications, 2009

Approximating Matches Made in Heaven.

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Limits to List Decoding Random Codes.

Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

2008

List Decoding near Capacity: Folded RS Codes.

Proceedings of the Encyclopedia of Algorithms, 2008

Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy.

IEEE Trans. Information Theory, 2008

Soft decoding, dual BCH codes, and better list-decodable eps-biased codes.

Electronic Colloquium on Computational Complexity (ECCC), 2008

Concatenated codes can achieve list-decoding capacity.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Greedy List Intersection.

Proceedings of the 24th International Conference on Data Engineering, 2008

Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes.

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Pricing Commodities, or How to Sell When Buyers Have Restricted Valuations.

Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

Lower bounds for randomized read/write stream algorithms.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Dynamic pricing for impatient bidders.

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics.

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Better Binary List-Decodable Codes Via Multilevel Concatenation.

Proceedings of the Approximation, 2007

Improved Approximation Algorithms for the Spanning Star Forest Problem.

Proceedings of the Approximation, 2007

Efficient List Decoding of Explicit Codes with Optimal Redundancy.

Proceedings of the Applied Algebra, 2007

2006

Explicit capacity-achieving list-decodable codes.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Ordering by weighted number of wins gives a good ranking for weighted tournaments.

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005

Explicit Capacity-Achieving List-Decodable Codes

Electronic Colloquium on Computational Complexity (ECCC), 2005

Ordering by weighted number of wins gives a good ranking for weighted tournaments

Electronic Colloquium on Computational Complexity (ECCC), 2005

On the Robust Testability of Product of Codes

Electronic Colloquium on Computational Complexity (ECCC), 2005

Tolerant Locally Testable Codes

Electronic Colloquium on Computational Complexity (ECCC), 2005

Walrasian Equilibrium: Hardness, Approximations and Tractable Instances.

Proceedings of the Internet and Network Economics, First International Workshop, 2005

Limits to list decoding Reed-Solomon codes.

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Approximation Algorithms for Wavelength Assignment.

Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

Tolerant Locally Testable Codes.

Proceedings of the Approximation, 2005

2004

Testing Low-Degree Polynomials over Prime Fields.

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Efficient galois field arithmetic on SIMD architectures.

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

Online learning in online auctions.

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Coalitional games on graphs: core structure, substitutes and frugality.

Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

2001

Efficient Rijndael Encryption Implementation with Composite Field Arithmetic.

Proceedings of the Cryptographic Hardware and Embedded Systems, 2001