Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Hanlin Ren:

TR21-089 | 25th June 2021
Hanlin Ren, Rahul Santhanam

A Relativization Perspective on Meta-Complexity

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

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

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

TR21-057 | 23rd April 2021
Hanlin Ren, Rahul Santhanam

Hardness of KT Characterizes Parallel Cryptography

Revisions: 1

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

TR20-010 | 12th February 2020
Lijie Chen, Hanlin Ren

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

Revisions: 1

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

ISSN 1433-8092 | Imprint