Ben lee Volk

activity

20242026

collaborators

4 papers

cs.CC2026

A Lower Bound for Read-Once Parity Branching Programs

Ben Lee Volk

We prove an $I^~ c ◯ (n^{2})$ lower bound for read-once parity branching programs computing an explicit boolean function on $n$ variables. The previous best lower bound was $\tildeÎ©…

cs.DS2025

On Deterministically Finding an Element of High Order Modulo a Composite

Ziv Oznovich, Ben Lee Volk

We give a deterministic algorithm that, given a composite number $N$ and a target order $D \geq N^{1/6}$ , runs in time $D^{1/2 + o (1)}$ and finds either an element $a \in \mathbb{Z}_N…

cs.CC2024

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi +1

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial $f$ computed by a constant-depth circuit over rational numbers, and outputs a…

cs.CC2024

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk

We construct explicit pseudorandom generators that fool $n$ -variate polynomials of degree at most $d$ over a finite field $F_{q}$ . The seed length of our generators is $O(d…