All reports by Author Jyun-Jie Liao:

__
TR23-130
| 8th September 2023
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Recursive Error Reduction for Regular Branching Programs

Revisions: 1

__
TR22-153
| 8th November 2022
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Hardness against Linear Branching Programs and More

__
TR21-147
| 22nd October 2021
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Extractors for Sum of Two Sources

Revisions: 1

__
TR21-075
| 4th June 2021
__

Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao#### Affine Extractors for Almost Logarithmic Entropy

__
TR20-069
| 4th May 2020
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Optimal Error Pseudodistributions for Read-Once Branching Programs

Revisions: 1

__
TR20-023
| 10th February 2020
__

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan#### Non-Malleability against Polynomial Tampering

Revisions: 1

Eshan Chattopadhyay, Jyun-Jie Liao

In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Their result is based on a clever modification to the inverse Laplacian perspective of space-bounded derandomization, which was originally introduced by Ahmadinejad, Kelner, ... more >>>

Eshan Chattopadhyay, Jyun-Jie Liao

In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once

branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is

a branching program where each node is allowed to make $\mathbb{F}_2$-linear queries, and are read-once in the ...
more >>>

Eshan Chattopadhyay, Jyun-Jie Liao

We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An $(n,k,C)$-sumset source $\mathbf{X}$ is a distribution on $\{0,1\}^n$ of the form $\mathbf{X}_1 + \mathbf{X}_2 + \ldots + \mathbf{X}_C$, where $\mathbf{X}_i$'s are independent sources on $n$ bits ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao

We give an explicit construction of an affine extractor (over $\mathbb{F}_2$) that works for affine sources on $n$ bits with min-entropy $k \ge~ \log n \cdot (\log \log n)^{1 + o(1)}$. This improves prior work of Li (FOCS'16) that requires min-entropy at least $\mathrm{poly}(\log n)$.

Our construction is ...
more >>>

Eshan Chattopadhyay, Jyun-Jie Liao

In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$ and width $w$ read-once branching programs with seed length $O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$ and error $\varepsilon$. It remains a central question to reduce the seed length to $O(\log (nw/\varepsilon))$, which would prove that $\mathbf{BPL}=\mathbf{L}$. However, there has ... more >>>

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable ... more >>>