9 papers
Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time
Jakob Nogler, Agnès Totschnig, Virginia Vassilevska Williams
In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in…
The Complexity of Justified Representation with Additive Utilities
Carmel Baharav, Jakob de Raaij, Agnès Totschnig
We study the computational complexity of satisfying proportional representation -- in particular proportional, extended, and fully justified representation (PJR, EJR, and FJR) -- i…
Almost perfect graph classes
Cicely Henderson, Hidde Koerts, Taite LaGrange +4
A graph is perfect if for each induced subgraph of . In 2002, Chudnovsky, Robertson, Seymour, and Thomas famously proved the Strong Perfect Graph Theorem.…
Fair Division of Graphs: Beyond Traceability
Nicolas Bousquet, Frank Connor, Agnès Totschnig +1
In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally al…
The Tiered Clinching Auction with Applications to Carbon Offset Markets
Tessa Davis, Agnès Totschnig, Adrian Vetta
Voluntary carbon offsetting is a strategy which has been pursued globally by corporations to reduce their effective carbon emissions. Carbon offset markets currently suffer from lo…
The Popular Dimension of Matchings
Frank Connor, Louis-Roy Langevin, Ndiamé Ndiaye +3
We study popular matchings in three classical settings: the house allocation problem, the marriage problem, and the roommates problem. In the popular matching problem, (a subset of…
Every graph with no -minor is -colorable
Sergey Norin, Agnes Totschnig
Let denote the graph obtained from the complete graph on seven vertices by deleting two edges with a common end. Motivated by Hadwiger's conjecture, we prove that ever…
Matrix Rationalization via Partial Orders
Agnes Totschnig, Rohit Vasishta, Adrian Vetta
A preference matrix has an entry for each pair of candidates in an election whose value represents the proportion of voters that prefer candidate over candidate $j…
Fair Algorithm Design: Fair and Efficacious Machine Scheduling
April Niu, Agnes Totschnig, Adrian Vetta
Motivated by a plethora of practical examples where bias is induced by automated-decision making algorithms, there has been strong recent interest in the design of fair algorithms.…