About: Bounded-depth Circuits: Separating Wires from Gates     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

AttributesValues
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
  • 257;265
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
  • 514141
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
  • [D361FCDC8CE8]
http://linked.open...v/mistoKonaniAkce
  • Baltimore
http://linked.open...i/riv/mistoVydani
  • Baltimore
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
  • ACM Press
https://schema.org/isbn
  • 1-58113-960-8
Faceted Search & Find service v1.16.118 as of Jun 21 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software