research
∙
09/12/2023
An improved protocol for ExactlyN with more than 3 players
The ExactlyN problem in the number-on-forehead (NOF) communication setti...
share
research
∙
08/30/2023
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
We present a simple and provably optimal non-adaptive cell probe data st...
research
∙
05/30/2023
On the algebraic proof complexity of Tensor Isomorphism
The Tensor Isomorphism problem (TI) has recently emerged as having conne...
research
∙
03/22/2023
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
The notion of replicable algorithms was introduced in Impagliazzo et al....
research
∙
12/27/2022
Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions
Rigorous guarantees about the performance of predictive algorithms are n...
research
∙
10/26/2022
Learning versus Refutation in Noninteractive Local Differential Privacy
We study two basic statistical tasks in non-interactive local differenti...
research
∙
01/20/2022
Reproducibility in Learning
We introduce the notion of a reproducible algorithm in the context of le...
research
∙
11/15/2021
Tradeoffs for small-depth Frege proofs
We study the complexity of small-depth Frege proofs and give the first t...
research
∙
02/09/2021
On the Power and Limitations of Branch and Cut
The Stabbing Planes proof system was introduced to model the reasoning c...
research
∙
01/30/2021
Size and Depth Separation in Approximating Natural Functions with Neural Networks
When studying the expressive power of neural networks, a main challenge ...
research
∙
10/14/2020
Theoretical bounds on estimation error for meta-learning
Machine learning models have traditionally been developed under the assu...
research
∙
07/06/2020
KRW Composition Theorems via Lifting
One of the major open problems in complexity theory is proving super-log...
research
∙
04/17/2020
Automating Cutting Planes is NP-Hard
We show that Cutting Planes (CP) proofs are hard to find: Given an unsat...
research
∙
03/04/2020
Towards a Complexity-theoretic Understanding of Restarts in SAT solvers
Restarts are a widely-used class of techniques integral to the efficienc...
research
∙
01/07/2020
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
We significantly strengthen and generalize the theorem lifting Nullstell...
research
∙
09/18/2019
Causal Modeling for Fairness in Dynamical Systems
In this work, we present causal directed acyclic graphs (DAGs) as a unif...
research
∙
06/06/2019
Flexibly Fair Representation Learning by Disentanglement
We consider the problem of learning representations that achieve group a...
research
∙
04/30/2019
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Lifting theorems are theorems that relate the query complexity of a func...
research
∙
04/30/2019
Query-to-communication lifting for BPP using inner product
We prove a new query-to-communication lifting for randomized protocols, ...
research
∙
09/07/2018
Fairness Through Causal Awareness: Learning Latent-Variable Models for Biased Data
How do we learn from biased data? Historical datasets often reflect hist...
research
∙
02/17/2018
Learning Adversarially Fair and Transferable Representations
In this work, we advocate for representation learning as the key to miti...
research
∙
11/17/2017
Predict Responsibly: Increasing Fairness by Learning To Defer
Machine learning systems, which are often used for high-stakes decisions...
research
∙
10/09/2017
Stabbing Planes
We introduce and develop a new semi-algebraic proof system, called Stabb...
research
∙
01/15/2014
Solving #SAT and Bayesian Inference with Backtracking Search
Inference in Bayes Nets (BAYES) is an important problem with numerous ap...
research
∙
10/19/2012