PreviousNext

__
TR23-192
| 28th November 2023
__

Noam Mazor, Rafael Pass#### A Note On the Universality of Black-box MKtP Solvers

Revisions: 1

__
TR23-191
| 2nd December 2023
__

HervĂ© Fournier, Nutan Limaye, Srikanth Srinivasan, SĂ©bastien Tavenas#### On the Power of Homogeneous Algebraic Formulas

__
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

PreviousNext

Noam Mazor, Rafael Pass

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 >>>

HervĂ© Fournier, Nutan Limaye, Srikanth Srinivasan, SĂ©bastien Tavenas

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 >>>

Leonid Gurvits, Nathan Klein, Jonathan Leake

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 >>>

PreviousNext