Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.17114 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916841397420032 |
|---|---|
| author | Kuntewar, Neha Sarma, Jayalal |
| author_facet | Kuntewar, Neha Sarma, Jayalal |
| contents | Given a circuit $C : \{0,1\}^n \to \{0,1\}^m$ from a circuit class $F$, with $m > n$, finding a $y \in \{0,1\}^m$ such that $\forall x \in \{0,1\}^n$, $C(x) \ne y$, is the range avoidance problem (denoted by $F$-$avoid$). Deterministic polynomial time algorithms (even with access to $NP$ oracles) solving this problem is known to imply explicit constructions of various pseudorandom objects like hard Boolean functions, linear codes, PRGs etc. Deterministic polynomial time algorithms are known for $NC^0_2$-$avoid$ when $m > n$, and for $NC^0_3$-$avoid$ when $m \ge \frac{n^2}{\log n}$, where $NC^0_k$ is the class of circuits with bounded fan-in which have constant depth and the output depends on at most $k$ of the input bits. On the other hand, it is also known that $NC^0_3$-$avoid$ when $m = n+O\left(n^{2/3}\right)$ is at least as hard as explicit construction of rigid matrices.
In this paper, we propose a new approach to solving 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 use our approach to show (using known Turan-type bounds) that there is a constant $c$ such that $mon$-$NC^0_3$-$avoid$ can be solved in deterministic polynomial time when $m > cn^2$. To improve the stretch constraint to linear, we show a new Turan-type theorem for a hypergraph structure (which we call the the loose $chi$-cycles) and use it to show that $mon$-$NC^0_3$-$avoid$ can be solved in deterministic polynomial time when $m > n$, thus improving the known bounds of $NC^0_3$-avoid for the case of monotone circuits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_17114 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Range Avoidance in Boolean Circuits via Turan-type Bounds Kuntewar, Neha Sarma, Jayalal Computational Complexity Given a circuit $C : \{0,1\}^n \to \{0,1\}^m$ from a circuit class $F$, with $m > n$, finding a $y \in \{0,1\}^m$ such that $\forall x \in \{0,1\}^n$, $C(x) \ne y$, is the range avoidance problem (denoted by $F$-$avoid$). Deterministic polynomial time algorithms (even with access to $NP$ oracles) solving this problem is known to imply explicit constructions of various pseudorandom objects like hard Boolean functions, linear codes, PRGs etc. Deterministic polynomial time algorithms are known for $NC^0_2$-$avoid$ when $m > n$, and for $NC^0_3$-$avoid$ when $m \ge \frac{n^2}{\log n}$, where $NC^0_k$ is the class of circuits with bounded fan-in which have constant depth and the output depends on at most $k$ of the input bits. On the other hand, it is also known that $NC^0_3$-$avoid$ when $m = n+O\left(n^{2/3}\right)$ is at least as hard as explicit construction of rigid matrices. In this paper, we propose a new approach to solving 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 use our approach to show (using known Turan-type bounds) that there is a constant $c$ such that $mon$-$NC^0_3$-$avoid$ can be solved in deterministic polynomial time when $m > cn^2$. To improve the stretch constraint to linear, we show a new Turan-type theorem for a hypergraph structure (which we call the the loose $chi$-cycles) and use it to show that $mon$-$NC^0_3$-$avoid$ can be solved in deterministic polynomial time when $m > n$, thus improving the known bounds of $NC^0_3$-avoid for the case of monotone circuits. |
| title | Range Avoidance in Boolean Circuits via Turan-type Bounds |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2503.17114 |