| Title | : | Avoiding Range via Turan-type Bounds in Hypergraphs |
| Speaker | : | Neha Kuntewar (IIT Madras) |
| Details | : | Thu, Aug 7, 2025 2:00 PM, @ SSB 334 |
| Abstract | : | The range avoidance problem (denoted by AVOID) is as follows: given a Boolean circuit C computing a function from {0,1}^n to {0,1}^m with m > n, find a string that is outside the range of the circuit. The problem has received much attention in complexity theory over the last couple of years due to its close connections with circuit lowerbounds and several important explicit construction problems that are central open questions in the area. Deterministic polynomial-time algorithms (even with access to NP oracles) solving this problem are known to imply explicit constructions of various pseudorandom objects like hard Boolean functions, linear codes, PRGs, etc. Given the central nature of the problem, it is natural to study the complexity for special circuit classes. Deterministic polynomial time algorithms are known for AVOID when m > n, when each output function depends only on at most two input variables, and for the case of dependency on three bits when m > n^2/log n. On the other hand, for the dependency three case, if we design an algorithm for m = n+O(n^{2/3}), it implies explicit construction of rigid matrices, which is another long-standing open problem in the area. In fact, algorithms for solving range avoidance, even when each output function depends on four input variables, imply new circuit lower bounds. We propose a new approach to solving the range avoidance problem via hypergraphs. We formulate the problem in terms of Turan-type problems in hypergraphs of the following kind: for a fixed k-uniform hypergraph H', what is the maximum number of edges that can exist in a k-uniform hypergraph H which does not have a sub-hypergraph isomorphic to H'? We apply this framework to design new algorithms for special cases of AVOID problem. Observing that even monotone cases of the problem are as hard as general, we use our framework to design polynomial time algorithms for monotone-AVOID when m>n, when each function depends on three input variables. We show a new Turan-type theorem for a hypergraph structure (which we call the loose X_2l cycles). More specifically, we prove that any connected 3-uniform linear hypergraph with m > n edges must contain a loose X_2l cycle. Using this, we obtain a deterministic polynomial time algorithm for monotone-AVOID when m>n, and each function depends on three input variables, thus improving the known bounds for this setting. We also present generalisations of our algorithm, using appropriately designed hypergraph structures, to solve other special cases of AVOID that might be of independent interest. |