4 papers
Constructive Separations from Gate Elimination
Marco Carmosino, Ngu Dang, Tim Jackman
Gate elimination is the primary technique for proving explicit lower bounds against general Boolean circuits, including Li and Yang's state-of-the-art bound for affin…
Convergent Gate Elimination and Constructive Circuit Lower Bounds
Marco Carmosino, Ngu Dang, Tim Jackman
Towards better understanding of gate elimination, the only method known that can prove complexity lower bounds for explicit functions against unrestricted Boolean circuits, this wo…
Simple Circuit Extensions for XOR in PTIME
Marco Carmosino, Ngu Dang, Tim Jackman
The Minimum Circuit Size Problem for Partial Functions () is hard assuming the Exponential Time Hypothesis (ETH) (Ilango, 2020). This breakthrough hardness result leveraged…
Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release
Mark Bun, Marco Carmosino, Palak Jain +2
The technical literature about data privacy largely consists of two complementary approaches: formal definitions of conditions sufficient for privacy preservation and attacks that…