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:

TR23-144 | 22nd September 2023
Lijie Chen, Shuichi Hirahara, Hanlin Ren

Symmetric Exponential Time Requires Near-Maximum Circuit Size

We show that there is a language in $\mathrm{S}_2\mathrm{E}/_1$ (symmetric exponential time with one bit of advice) with circuit complexity at least $2^n/n$. In particular, the above also implies the same near-maximum circuit lower bounds for the classes $\Sigma_2\mathrm{E}$, $(\Sigma_2\mathrm{E}\cap\Pi_2\mathrm{E})/_1$, and $\mathrm{ZPE}^{\mathrm{NP}}/_1$. Previously, only "half-exponential" circuit lower bounds for these ... more >>>

TR23-076 | 24th May 2023
Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam

Polynomial-Time Pseudodeterministic Construction of Primes

A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.

... more >>>

TR23-072 | 18th May 2023
Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren

Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms

The *range avoidance problem*, denoted as $\mathcal{C}$-$\rm Avoid$, asks to find a non-output of a given $\mathcal{C}$-circuit $C:\{0,1\}^n\to\{0,1\}^\ell$ with stretch $\ell>n$. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit ... more >>>

TR23-070 | 9th May 2023
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Bounded Relativization

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called *bounded relativization*. For a complexity class $C$, we say that a statement is *$C$-relativizing* if the statement holds relative ... more >>>

TR23-046 | 13th April 2023
Yizhi Huang, Rahul Ilango, Hanlin Ren

NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

It is a long-standing open problem whether the Minimum Circuit Size Problem ($\mathrm{MCSP}$) and related meta-complexity problems are NP-complete. Even for the rare cases where the NP-hardness of meta-complexity problems are known, we only know very weak hardness of approximation.

In this work, we prove NP-hardness of approximating meta-complexity with ... more >>>

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