Voulez-vous effacer les recherches récentes ?

Toutes les recherches récentes seront supprimées

[METRIC 2011] Mark Braverman

il y a 8 ans190 views

METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 21, 15:00-16:00 - Mark Braverman (U. Toronto)
Poly-logarithmic independence fools bounded depth circuits
----
A Boolean circuit of depth d is a circuit comprised of AND, OR and NOT gates arranged in at most d layers. This class of circuits is one of the few complexity classes where unconditional lower bounds, i.e. computational impossibility results exist. Many of the bounds follow from a deep connection between bounded-depth circuits and low-degree multivariate polynomials.

In this talk we will discuss some of these connections. We will then present a proof of the 1990 Linial-Nisan conjecture on the computational power of bounded-depth circuits. The conjecture stated that bounded-depth Boolean circuits of size poly(n) cannot distinguish inputs drawn from a k-wise independent distributions from uniform inputs, where k=poly(log n).

The talk will be almost completely self-contained.

Signaler cette vidéo

Quel est le problème ?

  • Contenu à caractère sexuel
  • Contenu violent
  • Diffamation ou contenu haineux
  • Vidéo de désinformation

Intégrer la vidéo

[METRIC 2011] Mark Braverman
Lecture auto
<iframe frameborder="0" width="480" height="270" src="https://www.dailymotion.com/embed/video/xhwee1" allowfullscreen allow="autoplay"></iframe>
Intégrer la vidéo à votre site avec le code d'intégration ci-dessus

Signaler cette vidéo

Quel est le problème ?

  • Contenu à caractère sexuel
  • Contenu violent
  • Diffamation ou contenu haineux
  • Vidéo de désinformation

Intégrer la vidéo

[METRIC 2011] Mark Braverman
Lecture auto
<iframe frameborder="0" width="480" height="270" src="https://www.dailymotion.com/embed/video/xhwee1" allowfullscreen allow="autoplay"></iframe>
Intégrer la vidéo à votre site avec le code d'intégration ci-dessus