We study the question of explicitly constructing variety-evasive subspace families, a pseudorandom primitive introduced by Guo (Computational Complexity 2024) that generalizes both hitting sets and lossless rank condensers. Roughly speaking, a variety-evasive subspace family $\mathcal{H}$ is a collection of subspaces such that for every algebraic variety $V$ in a fixed ... more >>>

The problem of recognizing $(k,l)$-tight graphs is a fundamental problem that has close connections to well studied problems
like graph rigidity. The problem is better understood for planar graphs as compared to general graphs. For example, deterministic
NC-algorithms for the problem are known for planar graphs, but no such ... more >>>

Since the introduction of the Ideal Proof System (IPS) by Grochow and Pitassi (J. ACM 2018), a substantial body of work has established size lower bounds for IPS and its fragments. In particular, Forbes, Shpilka, Tzameret, and Wigderson (Theory Comput. 2021) developed the main lower-bound frameworks for restricted IPS fragments, ... more >>>