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

__
TR23-076
| 24th May 2023
__

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam#### Polynomial-Time Pseudodeterministic Construction of Primes

__
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

__
TR23-070
| 9th May 2023
__

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren#### Bounded Relativization

__
TR23-046
| 13th April 2023
__

Yizhi Huang, Rahul Ilango, Hanlin Ren#### NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

__
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

Lijie Chen, Shuichi Hirahara, Hanlin Ren

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

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam

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 >>>Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren

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

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

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

Yizhi Huang, Rahul Ilango, Hanlin Ren

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

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