Attributes | Values |
---|
rdf:type
| |
Description
| - Pomocí nové analýzy komunikace v Booleovských obvodech dokážeme dolní odhady na počet hradel v obvodech konstantní hloubky. (cs)
- 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. We are able to provide explicit languages that can be recognized by AC0 circuits with O(n) gates but not with O(n) wires, and similarly for ACC0 circuits. We are also able to characterize exactly the regular languages that can be recognized with O(n) wires, both in AC0 and ACC0 framework.
- 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. We are able to provide explicit languages that can be recognized by AC0 circuits with O(n) gates but not with O(n) wires, and similarly for ACC0 circuits. We are also able to characterize exactly the regular languages that can be recognized with O(n) wires, both in AC0 and ACC0 framework. (en)
|
Title
| - Bounded-depth Circuits: Separating Wires from Gates
- Obvody konstantní hloubky: separace hran od hradel (cs)
- Bounded-depth Circuits: Separating Wires from Gates (en)
|
skos:prefLabel
| - Bounded-depth Circuits: Separating Wires from Gates
- Obvody konstantní hloubky: separace hran od hradel (cs)
- Bounded-depth Circuits: Separating Wires from Gates (en)
|
skos:notation
| - RIV/67985840:_____/05:00041316!RIV07-AV0-67985840
|
http://linked.open.../vavai/riv/strany
| |
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| - P(1M0545), P(GA201/05/0124), P(IAA1019401), Z(AV0Z10190503)
|
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/67985840:_____/05:00041316
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - constant depth circuits; communication complexity; gates (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...v/mistoKonaniAkce
| |
http://linked.open...i/riv/mistoVydani
| |
http://linked.open...i/riv/nazevZdroje
| - Proceedings of the 37th Annual ACM Symposium on Theory of Computing ( STOC )
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...iv/tvurceVysledku
| - Koucký, Michal
- Pudlák, Pavel
- Thérien, D.
|
http://linked.open...vavai/riv/typAkce
| |
http://linked.open.../riv/zahajeniAkce
| |
http://linked.open...n/vavai/riv/zamer
| |
number of pages
| |
http://purl.org/ne...btex#hasPublisher
| |
https://schema.org/isbn
| |