All reports by Author Daniel Mitropolsky:

__
TR22-133
| 20th September 2022
__

Prahladh Harsha, Daniel Mitropolsky, Alon Rosen#### Downward Self-Reducibility in TFNP

Revisions: 1
,
Comments: 1

__
TR20-153
| 6th October 2020
__

Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou#### Total Functions in the Polynomial Hierarchy

Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

A problem is downward self-reducible if it can be solved efficiently given an oracle that returns

solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is

well studied and it is known that all downward self-reducible problems are in PSPACE. In this

paper, we initiate the study of ...
more >>>

Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou

We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string ... more >>>