Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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-175 | 15th November 2023
Noam Mazor, Rafael Pass

The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False

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

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

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

TR23-143 | 22nd September 2023
Noam Mazor, Rafael Pass

Counting Unpredictable Bits: A Simple PRG from One-way Functions

Revisions: 1

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

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

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

ISSN 1433-8092 | Imprint