Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UNIFORM LOWER BOUNDS:
Reports tagged with uniform lower bounds:
TR24-115 | 14th July 2024
Zhenjian Lu, Igor Oliveira, Hanlin Ren, Rahul Santhanam

On the Complexity of Avoiding Heavy Elements

We introduce and study the following natural total search problem, which we call the {\it heavy element avoidance} (Heavy Avoid) problem: for a distribution on $N$ bits specified by a Boolean circuit sampling it, and for some parameter $\delta(N) \ge 1/\poly(N)$ fixed in advance, output an $N$-bit string that has ... more >>>




ISSN 1433-8092 | Imprint