Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Polynomial Local Search:
TR03-051 | 20th June 2003
Tsuyoshi Morioka

The Relative Complexity of Local Search Heuristics and the Iteration Principle

Johnson, Papadimitriou and Yannakakis introduce the class $\PLS$
consisting of optimization problems for which efficient local-
search heuristics exist. We formulate a type-2 problem $\iter$
that characterizes $\PLS$ in style of Beame et al., and prove
a criterion for type-2 problems to be nonreducible to $\iter$.
As a corollary, ... more >>>

TR13-149 | 28th October 2013
Albert Atserias, Neil Thapen

The Ordering Principle in a Fragment of Approximate Counting

The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk ... more >>>

ISSN 1433-8092 | Imprint