Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Explicit Lower Bounds:
TR12-008 | 30th January 2012
Marek Karpinski, Richard Schmied

On Approximation Lower Bounds for TSP with Bounded Metrics

Revisions: 1

We develop a new method for proving explicit approximation lower bounds for TSP problems with bounded metrics improving on the best up to now known bounds. They almost match the best known bounds for unbounded metric TSP problems. In particular, we prove the best known lower bound for TSP with ... more >>>

TR21-023 | 20th February 2021
Jiatu Li, Tianqi Yang

$3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions

Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function $f:\mathbb{F}_2^n\to\mathbb{F}_2$ requires circuit of size $\Omega(2^n/n)$ by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in $NP$) not computable ... more >>>

ISSN 1433-8092 | Imprint