All reports by Author Rafael Pass:

__
TR23-192
| 28th November 2023
__

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

Revisions: 1

__
TR23-175
| 15th November 2023
__

Noam Mazor, Rafael Pass#### The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False

__
TR23-152
| 14th October 2023
__

Yanyi Liu, Rafael Pass#### One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions

__
TR23-143
| 22nd September 2023
__

Noam Mazor, Rafael Pass#### Counting Unpredictable Bits: A Simple PRG from One-way Functions

Revisions: 1

__
TR23-103
| 12th July 2023
__

Yanyi Liu, Rafael Pass#### On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity

Revisions: 1

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

Noam Mazor, Rafael Pass

The Perebor (Russian for “brute-force search”) conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ? = P conjecture (which they predate) and state that for “meta-complexity” problems, such as the Time-bounded ... more >>>

Yanyi Liu, Rafael Pass

Consider the recently introduced notion of \emph{probabilistic

time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al,

CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k.

We show the equivalence of the following:

- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable

distribution $\D$;

- ...
more >>>

Noam Mazor, Rafael Pass

A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both ... more >>>

Yanyi Liu, Rafael Pass

Whether one-way functions (OWF) exist is arguably the most important

problem in Cryptography, and beyond. While lots of candidate

constructions of one-way functions are known, and recently also

problems whose average-case hardness characterize the existence of

OWFs have been demonstrated, the question of

whether there exists some \emph{worst-case hard problem} ...
more >>>