Filters
Bounded depth circuits: separating wires from gates
We develop a new method to analyze the flow of communication in constant-depth circuits. This point of view allows us to prove new lower bounds on the number of wires required to recognize certain languages....
BA - Obecná matematika
- 2005 •
- D
Rok uplatnění
D - Stať ve sborníku
The polynomial and linear time hierarchies in V-0
We show that the bounded arithmetic theory V-0 does not prove that the polynomial time hierarchy collapses to the linear time hierarchy (without parameters). The result follows from a lower bound for bounded depth ...
BA - Obecná matematika
- 2009 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Near-Optimal Small-Depth Lower Bounds for Small
We prove a lower bound for the s-t connectivity restricted to distance k for depth d circuits. Our lower bound is almost optimal....
BA - Obecná matematika
- 2016 •
- D •
- Link
Rok uplatnění
D - Stať ve sborníku
Výsledek na webu
Circuits with medium fan-in
-On-Forehead model in communication complexity, or for bounded depth circuits in AC_0 to being layered and depth 2, we prove a lower bound of ... on the number of non-input gates. When the circuit...
BA - Obecná matematika
- 2015 •
- D •
- Link
Rok uplatnění
D - Stať ve sborníku
Výsledek na webu
Threshold circuits of bounded depth.
Annotation not available...
BA - Obecná matematika
- 1993 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Communication in bounded depth circuits.
Annotation not available...
BA - Obecná matematika
- 1994 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CC-CIRCUITS AND THE EXPRESSIVE POWER OF NILPOTENT ALGEBRAS
We show that CC-circuits of bounded depth have the same expressive power as circuits over finite nilpotent algebras from congruence modular varieties. We use conjecture, which states that CC-circuits of
Pure mathematics
- 2022 •
- Jimp •
- Link
Rok uplatnění
Jimp - Článek v periodiku v databázi Web of Science
Výsledek na webu
The canonical pairs of bounded depth Frege systems
. In particular, depth 1 games are essentially monotone Boolean circuits. Thus we get to lower bounds on the size of monotone Boolean circuits. However, we do not have a method yet for proving lower bounds...
Pure mathematics
- 2021 •
- Jimp •
- Link
Rok uplatnění
Jimp - Článek v periodiku v databázi Web of Science
Výsledek na webu
Top-down lower bounds for depth 3 circuits.
Annotation not available...
BA - Obecná matematika
- 1993 •
- D
Rok uplatnění
D - Stať ve sborníku
Top-down lower bounds for depth-three circuits.
Annotation not available...
BA - Obecná matematika
- 1995 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
- 1 - 10 out of 33 331