| Title | : | Range Avoidance Problem over Groups |
| Speaker | : | Neha Kuntewar (IIT Madras) |
| Details | : | Wed, Nov 4, 2026 11:00 AM, @ SSB 334 (Turing Hall) |
| Abstract | : | (This talk is crosslisted as a PhD Seminar) The range avoidance problem is as follows: given a Boolean circuit C that computes a function from n bits to m bits with m > n, find a string that is outside the range of the circuit. Deterministic polynomial time algorithms (even with access to NP oracles) that solve this problem are known to imply explicit constructions of various pseudorandom objects like hard truth tables, linear codes, PRGs, etc. Deterministic polynomial time algorithms for range avoidance when each output function depends only on three input variables with m = n+O(n^{2/3}) already imply explicit construction of rigid matrices, which is another long-standing open problem in the area. We propose a new approach to solving the range avoidance problem by studying an algebraic variant of the problem using groups. We define a group circuit as a DAG where n inputs are elements from a fixed group G, the intermediate gates are multiplication and inverse gates, with m designated output gates. We define the group avoidance problem as follows: for a fixed group G, given a group circuit C, find a string which is outside the range of the circuit. As a first result, we show a deterministic polynomial time reduction from the range avoidance problem to the group avoidance problem. As a result, deterministic polynomial time algorithms for group avoidance, even for specific groups and restricted circuits where each output element of the group circuit depends only on four input variables, imply breakthrough lowerbounds. Restricting the underlying group G, we show deterministic polynomial time algorithms for the group avoidance problem for Abelian groups and imperfect groups. (Based on joint work with Jayalal Sarma) |