All reports by Author Jiatu Li:

__
TR24-083
| 18th April 2024
__

Lijie Chen, Jiatu Li, Igor Carboni Oliveira#### On the Unprovability of Circuit Size Bounds in Intuitionistic $S^1_2$

__
TR24-060
| 4th April 2024
__

Lijie Chen, Jiatu Li, Igor Carboni Oliveira#### Reverse Mathematics of Complexity Lower Bounds

__
TR23-206
| 9th December 2023
__

Yilei Chen, Jiatu Li#### Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography

Revisions: 1

__
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-038
| 28th March 2023
__

Rahul Ilango, Jiatu Li, Ryan Williams#### Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

__
TR23-022
| 11th March 2023
__

Jiatu Li, Igor Carboni Oliveira#### Unprovability of strong complexity lower bounds in bounded arithmetic

__
TR22-086
| 9th June 2022
__

Lijie Chen, Jiatu Li, Tianqi Yang#### Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs

Revisions: 1

__
TR21-125
| 23rd August 2021
__

Zhiyuan Fan, Jiatu Li, Tianqi Yang#### The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs

Revisions: 1

__
TR21-023
| 20th February 2021
__

Jiatu Li, Tianqi Yang#### $3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

We show that there is a constant $k$ such that Buss's intuitionistic theory $\mathbf{IS}^1_2$ does not prove that SAT requires co-nondeterministic circuits of size at least $n^k$. To our knowledge, this is the first unconditional unprovability result in bounded arithmetic in the context of worst-case fixed-polynomial size circuit lower bounds. ... more >>>

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are necessary to prove a given theorem. In this work, we systematically explore the reverse mathematics of complexity lower bounds. We explore reversals in the setting of bounded arithmetic, with Cook's theory $\mathbf{PV}_1$ as the base ... more >>>

Yilei Chen, Jiatu Li

A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. Avoid) and the remote point problem (abbrev. RPP). The upper and lower bounds for these meta problems provide a unified ... 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 >>>

Rahul Ilango, Jiatu Li, Ryan Williams

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit $C:\{0,1\}^n\to\{0,1\}^m$, where $m>n$. Although at least half of the strings of length $m$ are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS'21) ... more >>>

Jiatu Li, Igor Carboni Oliveira

While there has been progress in establishing the unprovability of complexity statements in lower fragments of bounded arithmetic, understanding the limits of Jerabek's theory $\textbf{APC}_1$ (2007) and of higher levels of Buss's hierarchy $\textbf{S}^i_2$ (1986) has been a more elusive task. Even in the more restricted setting of Cook's theory ... more >>>

Lijie Chen, Jiatu Li, Tianqi Yang

In a recent work, Fan, Li, and Yang (STOC 2022) constructed a family of almost-universal hash functions such that each function in the family is computable by $(2n + o(n))$-gate circuits of fan-in $2$ over the $B_2$ basis. Applying this family, they established the existence of pseudorandom functions computable by ... more >>>

Zhiyuan Fan, Jiatu Li, Tianqi Yang

How much computational resource do we need for cryptography? This is an important question of both theoretical and practical interests. In this paper, we study the problem on pseudorandom functions (PRFs) in the context of circuit complexity. Perhaps surprisingly, we prove extremely tight upper and lower bounds in various circuit ... more >>>

Jiatu Li, Tianqi Yang

Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function $f:\mathbb{F}_2^n\to\mathbb{F}_2$ requires circuit of size $\Omega(2^n/n)$ by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in $NP$) not computable ... more >>>