133 citations · 208 across the 5 of their papers we have counts for
6 papers
Flexibly Fair Representation Learning by Disentanglement
Elliot Creager, David Madras, Jörn-Henrik Jacobsen +4
We consider the problem of learning representations that achieve group and subgroup fairness with respect to multiple sensitive attributes. Taking inspiration from the disentangled…
Query-to-Communication Lifting for BPP
Mika Göös, Toniann Pitassi, Thomas Watson
For any -bit boolean function , we show that the randomized communication complexity of the composed function , where is an index gadget, is characterized by…
Random CNFs are Hard for Cutting Planes
Noah Fleming, Denis Pankratov, Toniann Pitassi +1
The random k-SAT model is the most important and well-studied distribution over k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for satis…
Algebraic Proof Complexity: Progress, Frontiers and Challenges
Tonnian Pitassi, Iddo Tzameret
We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to…
Value Elimination: Bayesian Inference via Backtracking Search
Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi
Backtracking search is a powerful algorithmic paradigm that can be used to solve many problems. It is in a certain sense the dual of variable elimination; but on many problems, e.g…
Separating NOF communication complexity classes RP and NP
Matei David, Toniann Pitassi
We provide a non-explicit separation of the number-on-forehead communication complexity classes RP and NP when the number of players is up to δlog(n) for any δ<1. Recent lower boun…