Haoxing Lin

collaborators

2 papers

cs.CC2026

Fine-Grained AC $^{0}$ Lower Bounds for $k$ -OV, $k$ -XOR, and $k$ -SUM via Colored Subgraph Isomorphism

Haoxing Lin

We prove lower bounds for $k$ -OV, $k$ -XOR, and $k$ -SUM in nonuniform AC $^{0}$ , tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framew…

cs.CR2024

On Wagner's k-Tree Algorithm Over Integers

Haoxing Lin, Prashant Nalini Vasudevan

The k-Tree algorithm [Wagner 02] is a non-trivial algorithm for the average-case k-SUM problem that has found widespread use in cryptanalysis. Its input consists of k lists, each c…

Fine-Grained AC0 Lower Bounds for k-OV, k-XOR, and k-SUM via Colored Subgraph Isomorphism

On Wagner's k-Tree Algorithm Over Integers

Fine-Grained AC $^{0}$ Lower Bounds for $k$ -OV, $k$ -XOR, and $k$ -SUM via Colored Subgraph Isomorphism