Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NEHA KUNTEWAR:
All reports by Author Neha Kuntewar:

TR25-034 | 20th March 2025
Neha Kuntewar, Jayalal Sarma

Range Avoidance in Boolean Circuits via Turan-type Bounds

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). It is known that deterministic polynomial time algorithms (even with access ... more >>>




ISSN 1433-8092 | Imprint