We study weighted pseudorandom generators (WPRGs) and derandomizations for read-once branching programs (ROBPs), which are key problems towards answering the fundamental open question $\mathbf{BPL} ?{=} \mathbf{L}$.
Denote $n$ and $w$ as the length and the width of a ROBP.
We have the following results.

For standard ROBPs, there exists an ... more >>>

Relaxations for the constraint satisfaction problem (CSP) include bounded width (BW), linear program (LP), semidefinite program (SDP), affine integer program (AIP), and their combinations. Tightening relaxations systematically leads to hierarchies and stronger algorithms. For LP+AIP and SDP+AIP hierarchies, various lower bounds were shown by Ciardo and Živný (STOC 2023, STOC ... more >>>

We extend the bounded degree graph model for property testing introduced by Goldreich and Ron (Algorithmica, 2002) to hypergraphs. In this framework, we analyse the query complexity of three fundamental hypergraph properties: colorability, $k$-partiteness, and independence number. We present a randomized algorithm for testing $k$-partiteness within families of $k$-uniform $n$-vertex ... more >>>