Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DISCRETE COMPLEXITY:
Reports tagged with discrete complexity:
TR25-033 | 18th March 2025
Bruno Pasqualotto Cavalar, Igor Oliveira

Boolean Circuit Complexity and Two-Dimensional Cover Problems

We reduce the problem of proving deterministic and nondeterministic Boolean circuit size lower bounds to the analysis of certain two-dimensional combinatorial cover problems. This is obtained by combining results of Razborov (1989), Karchmer (1993), and Wigderson (1993) in the context of the fusion method for circuit lower bounds with the ... more >>>




ISSN 1433-8092 | Imprint