All reports by Author Hanlin Ren:

__
TR21-089
| 25th June 2021
__

Hanlin Ren, Rahul Santhanam#### A Relativization Perspective on Meta-Complexity

__
TR21-082
| 16th June 2021
__

Rahul Ilango, Hanlin Ren, Rahul Santhanam#### Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

__
TR21-057
| 23rd April 2021
__

Hanlin Ren, Rahul Santhanam#### Hardness of KT Characterizes Parallel Cryptography

Revisions: 1

__
TR20-010
| 12th February 2020
__

Lijie Chen, Hanlin Ren#### Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

Revisions: 1

Hanlin Ren, Rahul Santhanam

Meta-complexity studies the complexity of computational problems about complexity theory, such as the Minimum Circuit Size Problem (MCSP) and its variants. We show that a relativization barrier applies to many important open questions in meta-complexity. We give relativized worlds where:

* MCSP can be solved in deterministic polynomial time, but ... more >>>

Rahul Ilango, Hanlin Ren, Rahul Santhanam

We show that one-way functions exist if and only if there is some samplable distribution D such that it is hard to approximate the Kolmogorov complexity of a string sampled from D. Thus we characterize the existence of one-way functions by the average-case hardness of a natural \emph{uncomputable} problem on ... more >>>

Hanlin Ren, Rahul Santhanam

A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity K^t is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures:

1. We show, perhaps surprisingly, that the ... more >>>

Lijie Chen, Hanlin Ren

We prove that for all constants a, NQP = NTIME[n^{polylog(n)}] cannot be (1/2 + 2^{-log^a n})-approximated by 2^{log^a n}-size ACC^0 of THR circuits (ACC^0 circuits with a bottom layer of THR gates). Previously, it was even open whether E^NP can be (1/2+1/sqrt{n})-approximated by AC^0[2] circuits. As a straightforward application, ... more >>>