3 citations · 9 across the 9 of their papers we have counts for
10 papers
Terminal-Bench: Benchmarking Agents on Hard, Realistic Tasks in Command Line Interfaces
Mike A. Merrill, Alexander G. Shaw, Nicholas Carlini +82
AI agents may soon become capable of autonomously completing valuable, long-horizon tasks in diverse domains. Current benchmarks either do not measure real-world tasks, or are not…
On the Emergence of Thinking in LLMs I: Searching for the Right Intuition
Guanghao Ye, Khiem Duc Pham, Xinzhi Zhang +5
Recent AI advancements, such as OpenAI's new models, are transforming LLMs into LRMs (Large Reasoning Models) that perform reasoning during inference, taking extra time and compute…
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan +3
We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen kno…
Fast Algorithms for Separable Linear Programs
Sally Dong, Gramoz Goranci, Lawrence Li +2
In numerical linear algebra, considerable effort has been devoted to obtaining faster algorithms for linear systems whose underlying matrices exhibit structural properties. A promi…
Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
Sally Dong, Guanghao Ye
We present an algorithm for min-cost flow in graphs with vertices and edges, given a tree decomposition of width and size , and polynomially bounded, integral edge c…
Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity
Sally Dong, Haotian Jiang, Yin Tat Lee +2
Many fundamental problems in machine learning can be formulated by the convex program \[ \min_{θ\in R^d}\ \sum_{i=1}^{n}f_{i}(θ), \] where each is a convex, Lipschitz functio…
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
Sally Dong, Yu Gao, Gramoz Goranci +4
We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm fo…
A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions
Damek Davis, Dmitriy Drusvyatskiy, Yin Tat Lee +2
Zhang et al. introduced a novel modification of Goldstein's classical subgradient method, with an efficiency guarantee of for minimizing Lipschitz functions.…
A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path
Sally Dong, Yin Tat Lee, Guanghao Ye
Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms in various communities including combinatorics, integer-linear p…
Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time
Jerry Li, Guanghao Ye
Robust covariance estimation is the following, well-studied problem in high dimensional statistics: given samples from a -dimensional Gaussian $\mathcal{N}(\boldsymbol{0}, Σ…