3 citations · 3 across the 12 of their papers we have counts for
17 papers
On the Accuracy of Approximate Leave-One-Out with Blockwise Nonsmooth Regularization in High-dimensions
Honghao Lin, Songbin Liu, Arian Maleki +5
Approximate leave-one-out (ALO) refers to methods that provide computationally efficient and statistically accurate approximations to leave-one-out risk estimation. These methods h…
Optimal and Efficient Online Inverse Optimization
Anupam Gupta, Guru Guruganesh, Honghao Lin +3
In online inverse linear optimization, a learner recommends an action and then observes the choice of an expert who maximizes a fixed, unknown linear objective on ;…
A Proof of the Most Informative Boolean Function Conjecture
Zijie Chen, Amin Gohari, Adel Javanmard +4
Let be uniform on , let be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability , and let $g:\{-1,…
Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science
Honghao Lin, David P. Woodruff, Yuan Deng +3
Language models can produce plausible short proofs, but may still be unreliable on long-horizon research problems, where progress depends on a sequence of uncertain and interdepend…
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…
Nearly Optimal Strong Coresets for Subspace Approximation
Honghao Lin, Vahab Mirrokni, David P. Woodruff
We study strong coresets for subspace approximation. Given a matrix , the goal is to sample and rescale a small number of its rows to obtain $S…
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,…
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…
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…
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…
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…
Aletheia tackles FirstProof autonomously
Tony Feng, Junehyuk Jung, Sang-hyun Kim +14
We report the performance of Aletheia (Feng et al., 2026b), a mathematics research agent powered by Gemini 3 Deep Think, on the inaugural FirstProof challenge. Within the allowed t…
Accelerating Scientific Research with Gemini: Case Studies and Common Techniques
David P. Woodruff, Vincent Cohen-Addad, Lalit Jain +33
Recent advances in large language models (LLMs) have opened new avenues for accelerating scientific research. While models are increasingly capable of assisting with routine tasks,…
Solving an Open Problem in Theoretical Physics using AI-Assisted Discovery
Michael P. Brenner, Vincent Cohen-Addad, David Woodruff
This paper demonstrates that artificial intelligence can accelerate mathematical discovery by autonomously solving an open problem in theoretical physics. We present a neuro-symbol…
Adversarial Robustness on Insertion-Deletion Streams
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While robust algorithms exist for in…
Progress on the Courtade-Kumar Conjecture: Optimal High-Noise Entropy Bounds and Generalized Coordinate-wise Mutual Information
Adel Javanmard, David P. Woodruff
The Courtade-Kumar conjecture posits that dictatorship functions maximize the mutual information between the function's output and a noisy version of its input over the Boolean hyp…