3 papers
cs.CC2023
Perspective on complexity measures targetting read-once branching programs
Yaqiao Li, Pierre McKenzie
A model of computation for which reasonable yet still incomplete lower bounds are known is the read-once branching program. Here variants of complexity measures successful in the s…
cs.CC2016
Trading information complexity for error
Yuval Dagan, Yuval Filmus, Hamed Hatami +1
We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of .…
math.CO2014
A characterization of functions with vanishing averages over products of disjoint sets
Hamed Hatami, Pooya Hatami, Yaqiao Li
Given , we characterize all integrable functions satisfying for any collection of disjoint…