Atri Rudra

Orcid: 0000-0003-4136-4719

Affiliations:
  • University at Buffalo, USA


According to our database1, Atri Rudra authored at least 116 papers between 2001 and 2024.

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 of three.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Simple linear attention language models balance the recall-throughput tradeoff.
CoRR, 2024

2023
Arithmetic Circuits, Structured Matrices and (not so) Deep Learning.
Theory Comput. Syst., June, 2023

Foreword: a Commemorative Issue for Alan L. Selman.
Theory Comput. Syst., June, 2023

Technical Perspective: (Pre-) Semirings Come to the Recursion Party.
SIGMOD Rec., 2023

Zoology: Measuring and Improving Recall in Efficient Language Models.
CoRR, 2023

Teaching Responsible Computing in Context: Models, Practices, and Tools.
Proceedings of the 54th ACM Technical Symposium on Computer Science Education, Volume 2, 2023

Laughing Hyena Distillery: Extracting Compact Recurrences From Convolutions.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Monarch Mixer: A Simple Sub-Quadratic GEMM-Based Architecture.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Simple Hardware-Efficient Long Convolutions for Sequence Modeling.
Proceedings of the International Conference on Machine Learning, 2023

How to Train your HIPPO: State Space Models with Generalized Orthogonal Basis Projections.
Proceedings of the Eleventh International Conference on Learning Representations, 2023

Hungry Hungry Hippos: Towards Language Modeling with State Space Models.
Proceedings of the Eleventh International Conference on Learning Representations, 2023

2022
General Strong Polarization.
J. ACM, 2022

Computing expected multiplicities for bag-TIDBs with bounded multiplicities.
CoRR, 2022

A qualitative, network-centric method for modeling socio-technical systems, with applications to evaluating interventions on social media platforms to increase social equality.
Appl. Netw. Sci., 2022

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Monarch: Expressive Structured Matrices for Efficient and Accurate Training.
Proceedings of the International Conference on Machine Learning, 2022

Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models.
Proceedings of the Tenth International Conference on Learning Representations, 2022

2021
Worst-case Optimal Binary Join Algorithms under General 𝓁<sub>p</sub> Constraints.
CoRR, 2021

Scatterbrain: Unifying Sparse and Low-rank Attention Approximation.
CoRR, 2021

Combining Recurrent, Convolutional, and Continuous-time Models with Linear State Space Layers.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Scatterbrain: Unifying Sparse and Low-rank Attention.
Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

2020
Covering the Relational Join.
CoRR, 2020

HiPPO: Recurrent Memory with Optimal Polynomial Projections.
Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 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

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.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2014

Topology matters in communication.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 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<sup> + </sup> 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.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2008

Soft decoding, dual BCH codes, and better list-decodable eps-biased codes.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 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
Electron. Colloquium Comput. Complex., 2005

On the Robust Testability of Product of Codes
Electron. Colloquium Comput. Complex., 2005

Tolerant Locally Testable Codes
Electron. Colloquium Comput. Complex., 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


  Loading...