Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > HAOXING LIN:
All reports by Author Haoxing LIN:

TR26-139 | 9th August 2026
Haoxing LIN

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

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 framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k\log n)$, without increasing depth ... more >>>




ISSN 1433-8092 | Imprint