Satyajeet Nagargoje

collaborators

2 papers

cs.CC2024

Hilbert Functions and Low-Degree Randomness Extractors

Alexander Golovnev, Zeyu Guo, Pooya Hatami +2

For $S \subseteq F^{n}$ , consider the linear space of restrictions of degree- $d$ polynomials to $S$ . The Hilbert function of $S$ , denoted $h_{S} (d, F)$ , is the…

cs.CC2023

Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje +1

Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit $C : {0, 1}^{n} \to {0, 1}^{m}$ , $m > n$ , the task is to find a $y \in {0, 1}^{m}$ outside the range of $…