23 citations · 85 across the 22 of their papers we have counts for
29 papers
TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability
Vincent Cohen-Addad, Dimitris Paparas, Ernest van Wijland +13
We introduce TCS-Bench, a benchmark for evaluating Large Language Models (LLMs) on research-level Theoretical Computer Science (TCS) proof generation. TCS-Bench consists of theorem…
Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity
Rajesh Jayaram, Honghao Lin, Vahab Mirrokni +1
Multi-vector embeddings represent items by point clouds and compare query and document point clouds using Chamfer similarity, whereas single-vector embeddings use ordinary inner pr…
Towards Automating Scientific Review with Google's Paper Assistant Tool
Rajesh Jayaram, Drew Tyler, David Woodruff +4
Artificial intelligence is driving a revolution in scientific discovery, accelerating everything from hypothesis generation to mathematical theorem proving. However, this rapid acc…
Streaming Algorithms with Few State Changes
Rajesh Jayaram, David P. Woodruff, Samson Zhou
In this paper, we study streaming algorithms that minimize the number of changes made to their internal state (i.e., memory contents). While the design of streaming algorithms typi…
HyperAttention: Long-context Attention in Near-Linear Time
Insu Han, Rajesh Jayaram, Amin Karbasi +3
We present an approximate attention mechanism named HyperAttention to address the computational challenges posed by the growing complexity of long contexts used in Large Language M…
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan +1
We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set of points, the goal i…
Fully Dynamic Consistent -Center Clustering
Jakub Łącki, Bernhard Haeupler, Christoph Grunau +2
We study the consistent k-center clustering problem. In this problem, the goal is to maintain a constant factor approximate -center solution during a sequence of point inser…
A Near-Linear Time Algorithm for the Chamfer Distance
Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram +2
For any two point sets of size up to , the Chamfer distance from to is defined as , whe…
Optimal Fully Dynamic -Center Clustering for Adaptive and Oblivious Adversaries
MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger +4
In fully dynamic clustering problems, a clustering of a given data set in a metric space must be maintained while it is modified through insertions and deletions of individual poin…
Stars: Tera-Scale Graph Building for Clustering and Graph Learning
CJ Carey, Jonathan Halcrow, Rajesh Jayaram +3
A fundamental procedure in the analysis of massive datasets is the construction of similarity graphs. Such graphs play a key role for many downstream tasks, including clustering, c…
Streaming Euclidean MST to a Constant Factor
Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram +2
We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an -point set .…
Adore: Differentially Oblivious Relational Database Operators
Lianke Qin, Rajesh Jayaram, Elaine Shi +3
There has been a recent effort in applying differential privacy on memory access patterns to enhance data privacy. This is called differential obliviousness. Differential oblivious…
Optimal Fully Dynamic -Centers Clustering
MohammadHossein Bateni, Hossein Esfandiari, Rajesh Jayaram +1
We present the first algorithm for fully dynamic -centers clustering in an arbitrary metric space that maintains an optimal approximation in $O(k \cdot \operatorname{polyl…
New Streaming Algorithms for High Dimensional EMD and MST
Xi Chen, Rajesh Jayaram, Amit Levi +1
We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an -point set , and com…
Truly Perfect Samplers for Data Streams and Sliding Windows
Rajesh Jayaram, David P. Woodruff, Samson Zhou
In the -sampling problem, the goal is to output an index of a vector , such that for all coordinates , \[\textbf{Pr}[i=j] = (1 \pm ε) \frac{G(f…
In-Database Regression in Input Sparsity Time
Rajesh Jayaram, Alireza Samadian, David P. Woodruff +1
Sketching is a powerful dimensionality reduction technique for accelerating algorithms for data analysis. A crucial step in sketching methods is to compute a subspace embedding (SE…
An Optimal Algorithm for Triangle Counting in the Stream
Rajesh Jayaram, John Kallaugher
We present a new algorithm for approximating the number of triangles in a graph whose edges arrive as an arbitrary order stream. If is the number of edges in , the n…
When is Approximate Counting for Conjunctive Queries Tractable?
Marcelo Arenas, Luis Alberto Croquevielle, Rajesh Jayaram +1
Conjunctive queries are one of the most common class of queries used in database systems, and the best studied in the literature. A seminal result of Grohe, Schwentick, and Segoufi…
Testing Positive Semi-Definiteness via Random Submatrices
Ainesh Bakshi, Nadiia Chepurko, Rajesh Jayaram
We study the problem of testing whether a matrix with bounded entries () is positive semi-definite (PSD), or…
Learning and Testing Junta Distributions with Subcube Conditioning
Xi Chen, Rajesh Jayaram, Amit Levi +1
We study the problems of learning and testing junta distributions on with respect to the uniform distribution, where a distribution is a -junta if its probabili…
A Framework for Adversarially Robust Streaming Algorithms
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff +1
We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chose…
Span Recovery for Deep Neural Networks with Applications to Input Obfuscation
Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang
The tremendous success of deep neural networks has motivated the need to better understand the fundamental properties of these networks, but many of the theoretical results propose…
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
Huaian Diao, Rajesh Jayaram, Zhao Song +2
We study the Kronecker product regression problem, in which the design matrix is a Kronecker product of two or more matrices. Given for $i=1,2…
Towards Optimal Moment Estimation in Streaming and Distributed Models
Rajesh Jayaram, David P. Woodruff
One of the oldest problems in the data stream model is to approximate the -th moment of an underlying vector $\mathcal{X}…