Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with log depth circuits:
TR10-101 | 25th June 2010
Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer

Counting Classes and the Fine Structure between NC$^1$ and L.

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

TR24-034 | 19th February 2024
Bruno Loff, Alexey Milovanov

The hardness of decision tree complexity

Let $f$ be a Boolean function given as either a truth table or a circuit. How difficult is it to find the decision tree complexity, also known as deterministic query complexity, of $f$ in both cases? We prove that this problem is $NC$-hard and PSPACE-hard, respectively. The second bound is ... more >>>

ISSN 1433-8092 | Imprint