research
∙
11/30/2022
On Disperser/Lifting Properties of the Index and Inner-Product Functions
Query-to-communication lifting theorems, which connect the query complex...
share
research
∙
09/10/2020
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality
Non-signaling strategies are a generalization of quantum strategies that...
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
∙
02/20/2020
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
The class FORMULA[s] ∘𝒢 consists of Boolean functions computable by size...
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