# Atri Rudra

According to our database

Collaborative distances:

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

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2020

Covering the Relational Join.

CoRR, 2020

Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps.

Proceedings of the 8th International Conference on Learning Representations, 2020

Sparse Recovery for Orthogonal Polynomial Transforms.

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Topology Dependent Bounds For FAQs.

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations.

Proceedings of the 36th International Conference on Machine Learning, 2019

2018

Worst-case Optimal Join Algorithms.

J. ACM, 2018

General Strong Polarization.

Electronic Colloquium on Computational Complexity (ECCC), 2018

Hypertree Decompositions Revisited for PGMs.

CoRR, 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 Rec., 2017

Average-radius list-recovery of random linear codes: it really ties the room together.

CoRR, 2017

Implementation of Tetris as a Model Counter.

CoRR, 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

2016

List Decoding near Capacity: Folded RS Codes.

Encyclopedia of Algorithms, 2016

Efficient Decodable Group Testing.

Encyclopedia of Algorithms, 2016

Joins via Geometric Resolutions: Worst Case and Beyond.

ACM Trans. Database Syst., 2016

Tight Network Topology Dependent Bounds on Rounds of Communication.

Electronic Colloquium on Computational Complexity (ECCC), 2016

Recurrence Width for Structured Dense Matrix Vector Multiplication.

CoRR, 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

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. Netw. Comput. Appl., 2014

It'll probably work out: improved list-decoding through random operations.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Topology matters in communication.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Sparse Approximation, List Decoding, and Uncertainty Principles.

CoRR, 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

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 Comput., 2013

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

SIGMOD Rec., 2013

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

Electronic Colloquium on Computational Complexity (ECCC), 2013

Towards Instance Optimal Join Algorithms for Data in Indexes

CoRR, 2013

Improved Approximation Algorithms for the Spanning Star Forest Problem.

Algorithmica, 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

Almost Universal Hash Families are also Storage Enforcing

CoRR, 2012

Simulating Special but Natural Quantum Circuits

CoRR, 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

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

IEEE Trans. Inf. 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

An FPTAS for the Lead-Based Multiple Video Transmission LMVT Problem

CoRR, 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. Inf. Theory, 2010

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

ACM Trans. Algorithms, 2010

Dynamic pricing for impatient bidders.

ACM Trans. Algorithms, 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

Testing low-degree polynomials over prime fields.

Random Struct. Algorithms, 2009

Limits to List Decoding Random Codes.

Electronic Colloquium on Computational Complexity (ECCC), 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

2008

List Decoding near Capacity: Folded RS Codes.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

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

IEEE Trans. Inf. Theory, 2008

Concatenated codes can achieve list-decoding capacity.

Electronic Colloquium on Computational Complexity (ECCC), 2008

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

Electronic Colloquium on Computational Complexity (ECCC), 2008

Walrasian Equilibrium: Hardness, Approximations and Tractable Instances.

Algorithmica, 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

Better Binary List-Decodable Codes via Multilevel Concatenation.

Electronic Colloquium on Computational Complexity (ECCC), 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

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

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

Efficient List Decoding of Explicit Codes with Optimal Redundancy.

Proceedings of the Applied Algebra, 2007

2006

Limits to List Decoding Reed-Solomon Codes.

IEEE Trans. Inf. Theory, 2006

2005

Explicit Capacity-Achieving List-Decodable Codes

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

Approximation Algorithms for Wavelength Assignment.

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

2004

Online learning in online auctions.

Theor. Comput. Sci., 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

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