Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Optimal Unambiguous DNFs and Alon-Saks-Seymour
Chirag Pabbaraju
We construct unambiguous DNFs having width but -certificate complexity . By utilizing the special structure of these DNFs, we prove a lifting theorem with a const…
cs.CC2026
A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
Sumegha Garg, Jabari Hastings, Chirag Pabbaraju +1
We present a unified framework for proving memory lower bounds for multi-pass streaming algorithms that detect planted structures. Planted structures -- such as cliques or biclique…