9 papers
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,…
Dueling over Multiple Pieces of Dessert
Simina Brânzei, Reed Phillips
We study the dynamics of repeated fair division between two players, Alice and Bob, where Alice partitions a cake into two subsets and Bob chooses his preferred one over rounds…
The Query Complexity of Local Search in Rounds on General Graphs
Simina Brânzei, Ioannis Panageas, Dimitris Paparas
We analyze the query complexity of finding a local minimum in rounds on general graphs. More precisely, given a graph and oracle access to an unknown function $f :…
The Query Complexity of Local Search and Brouwer in Rounds
Simina Brânzei, Jiawei Li
We consider the query complexity of finding a local minimum of a function defined on a graph. This abstract problem is fundamental to many optimization tasks, such as finding a loc…
Computing Envy-Free up to Any Good (EFX) Allocations via Local Search
Simina Brânzei
We present a simple local search algorithm for computing EFX (envy-free up to any good) allocations of indivisible goods among agents with additive valuations. EFX is a com…
The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
Simina Brânzei, Reed Phillips, Nicholas Recker
The Knaster-Tarski theorem, also known as Tarski's theorem, guarantees that every monotone function defined on a complete lattice has a fixed point. We analyze the query complexity…