Atri Rudra

Corey Ropell

CoRR, 2021

Scatterbrain: Unifying Sparse and Low-rank Attention Approximation.

[BibT_eX]

[DOI]

CoRR, 2021

Combining Recurrent, Convolutional, and Continuous-time Models with Linear State Space Layers.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

2020

Covering the Relational Join.

[BibT_eX]

[DOI]

Shi Li

CoRR, 2020

HiPPO: Recurrent Memory with Optimal Polynomial Projections.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

Sparse Recovery for Orthogonal Polynomial Transforms.

[BibT_eX]

[DOI]

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

2019

Topology Dependent Bounds For FAQs.

[BibT_eX]

[DOI]

Michael Langberg

Shi Li

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

Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations.

[BibT_eX]

[DOI]

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

2018

Worst-case Optimal Join Algorithms.

[BibT_eX]

[DOI]

J. ACM, 2018

General Strong Polarization.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Hypertree Decompositions Revisited for PGMs.

[BibT_eX]

[DOI]

Aarthy Shivram Arun

Christopher Ré

CoRR, 2018

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

[BibT_eX]

[DOI]

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

Average-radius list-recoverability of random linear codes.

[BibT_eX]

[DOI]

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

Learning Compressed Transforms with Low Displacement Rank.

[BibT_eX]

[DOI]

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

Learning Invariance with Compact Transforms.

[BibT_eX]

[DOI]

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

2017

Juggling Functions Inside a Database.

[BibT_eX]

[DOI]

Mahmoud Abo Khamis

SIGMOD Rec., 2017

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

[BibT_eX]

[DOI]

CoRR, 2017

Implementation of Tetris as a Model Counter.

[BibT_eX]

[DOI]

Jimmy Dobler

CoRR, 2017

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

[BibT_eX]

[DOI]

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

2016

List Decoding near Capacity: Folded RS Codes.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Efficient Decodable Group Testing.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Joins via Geometric Resolutions: Worst Case and Beyond.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2016

Tight Network Topology Dependent Bounds on Rounds of Communication.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Michael Langberg

Shi Li

Electron. Colloquium Comput. Complex., 2016

Recurrence Width for Structured Dense Matrix Vector Multiplication.

[BibT_eX]

[DOI]

CoRR, 2016

FAQ: Questions Asked Frequently.

[BibT_eX]

[DOI]

Mahmoud Abo Khamis

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.

[BibT_eX]

[DOI]

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

The Range of Topological Effects on Communication.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

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

A multiple server scheme for fingerprint fuzzy vaults.

[BibT_eX]

[DOI]

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

2014

Bidirectional data verification for cloud storage.

[BibT_eX]

[DOI]

J. Netw. Comput. Appl., 2014

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Topology matters in communication.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Jaikumar Radhakrishnan

Electron. Colloquium Comput. Complex., 2014

Sparse Approximation, List Decoding, and Uncertainty Principles.

[BibT_eX]

[DOI]

CoRR, 2014

Beyond worst-case analysis for joins with minesweeper.

[BibT_eX]

[DOI]

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

Energy Aware Algorithmic Engineering.

[BibT_eX]

[DOI]

Swapnoneel Roy

Akshat Verma

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

Secure Fingerprint Matching with Generic Local Structures.

[BibT_eX]

[DOI]

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

2013

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

[BibT_eX]

[DOI]

Alexandr Andoni

Theory Comput., 2013

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

[BibT_eX]

[DOI]

Christopher Ré

SIGMOD Rec., 2013

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Towards Instance Optimal Join Algorithms for Data in Indexes

[BibT_eX]

[DOI]

CoRR, 2013

Improved Approximation Algorithms for the Spanning Star Forest Problem.

[BibT_eX]

[DOI]

Algorithmica, 2013

Accurate Decoding of Pooled Sequenced Data Using Compressed Sensing.

[BibT_eX]

[DOI]

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

An energy complexity model for algorithms.

[BibT_eX]

[DOI]

Swapnoneel Roy

Akshat Verma

Proceedings of the Innovations in Theoretical Computer Science, 2013

Towards fingerprints as strings: Secure indexing for fingerprint matching.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Biometrics, 2013

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

[BibT_eX]

[DOI]

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

2012

On the Circuit Complexity of Composite Galois Field Transformations.

[BibT_eX]

[DOI]

Charanjit S. Jutla

Vijay Kumar

Electron. Colloquium Comput. Complex., 2012

Almost Universal Hash Families are also Storage Enforcing

[BibT_eX]

[DOI]

Steven Y. Ko

CoRR, 2012

Simulating Special but Natural Quantum Circuits

[BibT_eX]

[DOI]

Richard J. Lipton

Kenneth W. Regan

CoRR, 2012

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

[BibT_eX]

[DOI]

Algorithmica, 2012

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

[BibT_eX]

[DOI]

Ely Porat

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

PGV: A Storage Enforcing Remote Verification Scheme.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

Recovering simple signals.

[BibT_eX]

[DOI]

Proceedings of the 2012 Information Theory and Applications Workshop, 2012

2011

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

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2011

Pricing commodities.

[BibT_eX]

[DOI]

Robert Krauthgamer

Aranyak Mehta

Theor. Comput. Sci., 2011

Flexible coloring.

[BibT_eX]

[DOI]

Xiaozhou Li

Ram Swaminathan

Inf. Process. Lett., 2011

Storage Enforcement with Kolmogorov Complexity and List Decoding.

[BibT_eX]

[DOI]

Steven Y. Ko

Electron. Colloquium Comput. Complex., 2011

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

[BibT_eX]

[DOI]

Swapnoneel Roy

CoRR, 2011

Polynomial Fitting of Data Streams with Applications to Codeword Testing.

[BibT_eX]

[DOI]

Andrew McGregor

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

Symmetric Functions Capture General Functions.

[BibT_eX]

[DOI]

Richard J. Lipton

Kenneth W. Regan

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Ely Porat

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

2010

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

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2010

Dynamic pricing for impatient bidders.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Two Theorems in List Decoding.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Floodlight illumination of infinite wedges.

[BibT_eX]

[DOI]

Comput. Geom., 2010

Efficiently Decodable Non-adaptive Group Testing.

[BibT_eX]

[DOI]

Piotr Indyk

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

Analyzing Nonblocking Switching Networks using Linear Programming (Duality).

[BibT_eX]

[DOI]

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

Data Stream Algorithms for Codeword Testing.

[BibT_eX]

[DOI]

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

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

Two Theorems on List Decoding - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

k<sup> + </sup> Decision Trees - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Sensor Systems, 2010

2009

Testing low-degree polynomials over prime fields.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2009

Limits to List Decoding Random Codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Error correction up to the information-theoretic limit.

[BibT_eX]

[DOI]

Commun. ACM, 2009

iMAP: Indirect Measurement of Air Pollution with Cellphones.

[BibT_eX]

[DOI]

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

Approximating Matches Made in Heaven.

[BibT_eX]

[DOI]

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

2008

List Decoding near Capacity: Folded RS Codes.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

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

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2008

Concatenated codes can achieve list-decoding capacity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Walrasian Equilibrium: Hardness, Approximations and Tractable Instances.

[BibT_eX]

[DOI]

Ning Chen

Algorithmica, 2008

Greedy List Intersection.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

2007

Better Binary List-Decodable Codes via Multilevel Concatenation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

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

[BibT_eX]

[DOI]

Robert Krauthgamer

Aranyak Mehta

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

Lower bounds for randomized read/write stream algorithms.

[BibT_eX]

[DOI]

Paul Beame

T. S. Jayram

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

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

[BibT_eX]

[DOI]

Matthew Cary

Ashish Sabharwal

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

Efficient List Decoding of Explicit Codes with Optimal Redundancy.

[BibT_eX]

[DOI]

Proceedings of the Applied Algebra, 2007

2006

Limits to List Decoding Reed-Solomon Codes.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2006

2005

Explicit Capacity-Achieving List-Decodable Codes

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

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

[BibT_eX]

[DOI]

Don Coppersmith

Lisa Fleischer

Electron. Colloquium Comput. Complex., 2005

On the Robust Testability of Product of Codes

[BibT_eX]

[DOI]

Don Coppersmith

Electron. Colloquium Comput. Complex., 2005

Tolerant Locally Testable Codes

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Approximation Algorithms for Wavelength Assignment.

[BibT_eX]

[DOI]

Vijay Kumar