Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

RSS-Feedprevious PreviousNext next

TR23-192 | 28th November 2023
Noam Mazor, Rafael Pass

A Note On the Universality of Black-box MKtP Solvers

Revisions: 1

The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta-complexity problems relate to one another, and to the task of function ... more >>>

TR23-191 | 2nd December 2023
Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

On the Power of Homogeneous Algebraic Formulas

Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking ... more >>>

TR23-190 | 15th November 2023
Leonid Gurvits, Nathan Klein, Jonathan Leake

From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP

We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of ... more >>>

previous PreviousNext next

ISSN 1433-8092 | Imprint