49 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…
A Near-Optimal Lower Bound for Prefix-Matrix Factorizations
Honghao Lin, Vahab Mirrokni, David P. Woodruff
For the lower-triangular all-ones matrix , we prove a near-optimal lower bound \[ γ_{2,1}(Q) := \inf_{Q=AB} \|A\|_{2\to\infty}\|B\|_{1\to1} = Ω\!\left( \frac{\log^{3…
SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant
Adel Javanmard, David P. Woodruff, Vahab Mirrokni
Achieving local differential privacy in distributed optimization while maintaining low communication cost remains challenging. Existing vector quantization methods, such as vqSGD,…
The Condition-Number Barrier in Sparse Least Squares
Honghao Lin, Vahab Mirrokni, David P. Woodruff
In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time al…
Pairwise-Independent Dithering for Single-Stage Hadamard Quantization
Honghao Lin, Vahab Mirrokni, David P. Woodruff
Quantizing high-dimensional vectors is fundamental to similarity search, distributed learning, and model compression. Feng, Indyk, Kapralov, Krachun, and Prokhorov established shar…
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…