Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > HAO WU:
All reports by Author Hao Wu:

TR24-086 | 24th April 2024
Hao Wu

A nearly-$4\log n$ depth lower bound for formulas with restriction on top

One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the $\mathbf{P}$ versus $\mathbf{NC^1}$ problem. The current best depth lower bound is $(3-o(1))\cdot \log n$, and it is widely open how to prove a super-$3\log n$ depth lower bound. ... more >>>


TR23-151 | 11th October 2023
Hao Wu

An Improved Composition Theorem of a Universal Relation and Most Functions via Effective Restriction

Revisions: 1

One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, to tackle this problem Karchmer, Raz and Wigderson proposed the KRW conjecture about composition of two functions. While this conjecture seems out of our current reach, some relaxed conjectures are ... more >>>


TR22-114 | 16th August 2022
Hao Wu

Direct Sum Theorems From Fortification

Revisions: 1

We revisit the direct sum theorems in communication complexity which askes whether the resource to solve $n$ communication problems together is (approximately) the sum of resources to solve these problems separately. Our work starts with the observation that Meir and Dinur's fortification lemma for protocol size over rectangles can be ... more >>>




ISSN 1433-8092 | Imprint