2 citations · 2 across the 13 of their papers we have counts for
13 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…
Beyond the Library: An Agentic Framework for Autoformalizing Research Mathematics
Arshia Soltani Moakhar, Iman Gholami, Max Springer +2
While Large Language Models (LLMs) have demonstrated exceptional capabilities in mathematical reasoning, they frequently produce subtle errors that evade human detection. Formal ma…
Beyond the Half-Approximation: Fair and Efficient Online Class Matching
Sander Borst, Max Springer
Online bipartite matching, where agents are known in advance but items arrive sequentially and must be irrevocably assigned, is fundamental to problems ranging from ride-sharing to…
Bi-Criteria Metric Distortion
Kiarash Banihashem, Diptarka Chakraborty, Shayan Chashm Jahan +4
Selecting representatives based on voters' preferences is a fundamental problem in social choice theory. While cardinal utility functions offer a detailed representation of prefere…
Fairness and Efficiency in Online Class Matching
MohammadTaghi Hajiaghayi, Shayan Chashm Jahan, Mohammad Sharifi +2
The online bipartite matching problem, extensively studied in the literature, deals with the allocation of online arriving vertices (items) to a predetermined set of offline vertic…
Dynamic Metric Embedding into Space
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski +2
We give the first non-trivial decremental dynamic embedding of a weighted, undirected graph into space. Given a weighted graph undergoing a sequence of edge weight…
Fair Polylog-Approximate Low-Cost Hierarchical Clustering
Marina Knittel, Max Springer, John Dickerson +1
Research in fair machine learning, and particularly clustering, has been crucial in recent years given the many ethical controversies that modern intelligent systems have posed. Ah…
An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Suho Shin +1
We present an oracle-efficient relaxation for the adversarial contextual bandits problem, where the contexts are sequentially drawn i.i.d from a known distribution and the cost seq…
Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements
MohammadTaghi Hajiaghayi, Max Springer, Hadi Yami
We here address the problem of fairly allocating indivisible goods or chores to agents with weights that define their entitlement to the set of indivisible resources. Stemming…
Optimal Sparse Recovery with Decision Stumps
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Max Springer
Decision trees are widely used for their low computational cost, good predictive performance, and ability to assess the importance of features. Though often used in practice for fe…
Online Algorithms for the Santa Claus Problem
MohammadTaghi Hajiaghayi, MohammadReza Khani, Debmalya Panigrahi +1
The Santa Claus problem is a fundamental problem in fair division: the goal is to partition a set of heterogeneous items among heterogeneous agents so as to maximize the minimum va…
Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost
Marina Knittel, Max Springer, John P. Dickerson +1
Clustering is a fundamental building block of modern statistical analysis pipelines. Fair clustering has seen much attention from the machine learning community in recent years. We…
Analysis of a Learning Based Algorithm for Budget Pacing
MohammadTaghi Hajiaghayi, Max Springer
In this paper, we analyze a natural learning algorithm for uniform pacing of advertising budgets, equipped to adapt to varying ad sale platform conditions. On the demand side, adve…