Dagstuhl Seminar Proceedings 06111

Complexity of Boolean Functions

M. Krause, P. Pudlák, R. Reischuk, D. v. Melkebeek (Eds.)

published by LZI
Host

ISSN  1862 - 4405

Dagstuhl Seminar 06111, 12.03. - 17.03.2006
Additional Information
Seminar Homepage
License
Search Publication Server

Authors
  • Allender, Eric
  • Andreev, Alexander E.
  • Arpe, Jan
  • Bürgisser, Peter
  • Balbach, Frank J.
  • Carlet, Claude
  • Diehl, Scott
  • Ford, Jeff
  • Gál, Anna
  • Gomulkiewicz, Marcin
  • Hayashi, Masahito
  • Iwama, Kazuo
  • Jakoby, Andreas
  • Jukna, Stasys
  • Kiltz, Eike
  • Kjeldgaard-Pedersen, Johan
  • Koucký, Michal
  • Krause, Matthias
  • Kutylowski, Miroslaw
  • Liskiewicz, Maciej
  • Madry, Aleksander
  • Manthey, Bodo
  • McKenzie, Pierre
  • Miltersen, Peter Bro
  • Nishimura, Harumichi
  • Pervyshev, Konstantin
  • Pudlák, Pavel
  • Raymond, Rudy
  • Reischuk, Rüdiger
  • Sauerhoff, Martin
  • Shparlinski, Igor E.
  • Tantau, Till
  • van Melkebeek, Dieter
  • Viola, Emanuele
  • Weinreb, Enav
  • Wlaz, Pawel
  • Yamashita, Shigeru
  • Zeugmann, Thomas

  •   
    06111 Abstracts Collection -- Complexity of Boolean Functions
    Authors: Krause, Matthias ; Pudlák, Pavel ; Reischuk, Rüdiger ; van Melkebeek, Dieter

    Abstract | Document (310 KB) | BibTeX

    06111 Executive Summary -- Complexity of Boolean Functions
    Authors: Krause, Matthias ; van Melkebeek, Dieter ; Pudlák, Pavel ; Reischuk, Rüdiger

    Abstract | Document (98 KB) | BibTeX

    A Generic Time Hierarchy for Semantic Models With One Bit of Advice
    Authors: van Melkebeek, Dieter ; Pervyshev, Konstantin

    Abstract | Document (403 KB) | BibTeX

    Approximability of Minimum AND-Circuits
    Authors: Arpe, Jan ; Manthey, Bodo

    Abstract | Document (331 KB) | BibTeX

    Bounds on the Fourier Coefficients of the Weighted Sum Function
    Authors: Shparlinski, Igor E.

    Abstract | Document (298 KB) | BibTeX

    Computing Shortest Paths in Series-Parallel Graphs in Logarithmic Space
    Authors: Jakoby, Andreas ; Tantau, Till

    Abstract | Document (161 KB) | BibTeX

    Fault Jumping Attacks against Shrinking Generator
    Authors: Gomulkiewicz, Marcin ; Kutylowski, Miroslaw ; Wlaz, Pawel

    Abstract | Document (140 KB) | BibTeX

    Graphs and Circuits: Some Further Remarks
    Authors: Jukna, Stasys

    Abstract | Document (254 KB) | BibTeX

    Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity
    Authors: Ford, Jeff ; Gál, Anna

    Abstract | Document (216 KB) | BibTeX

    Incremental branching programs
    Authors: Gál, Anna ; McKenzie, Pierre ; Koucký, Michal

    Abstract | Document (355 KB) | BibTeX

    On Probabilistic Time versus Alternating Time
    Authors: Viola, Emanuele

    Abstract | Document (306 KB) | BibTeX

    On the Complexity of Numerical Analysis
    Authors: Allender, Eric ; Bürgisser, Peter ; Kjeldgaard-Pedersen, Johan ; Miltersen, Peter Bro

    Abstract | Document (184 KB) | BibTeX

    On the Teachability of Randomized Learners
    Authors: Balbach, Frank J. ; Zeugmann, Thomas

    Abstract | Document (268 KB) | BibTeX

    Quantum Network Coding
    Authors: Hayashi, Masahito ; Iwama, Kazuo ; Nishimura, Harumichi ; Raymond, Rudy ; Yamashita, Shigeru

    Abstract | Document (388 KB) | BibTeX

    Quantum vs. Classical Read-Once Branching Programs
    Authors: Sauerhoff, Martin

    Abstract | Document (257 KB) | BibTeX

    Secure Linear Algebra Using Linearly Recurrent Sequences
    Authors: Kiltz, Eike ; Weinreb, Enav

    Abstract | Document (205 KB) | BibTeX

    The Cell Probe Complexity of Succinct Data Structures
    Authors: Gál, Anna ; Miltersen, Peter Bro

    Abstract | Document (267 KB) | BibTeX

    The complexity of Boolean functions from cryptographic viewpoint
    Authors: Carlet, Claude

    Abstract | Document (259 KB) | BibTeX

    The optimal sequence compression
    Authors: Andreev, Alexander E.

    Abstract | Document (139 KB) | BibTeX

    Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines
    Authors: Diehl, Scott ; van Melkebeek, Dieter

    Abstract | Document (351 KB) | BibTeX

    Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment
    Authors: Jakoby, Andreas ; Liskiewicz, Maciej ; Madry, Aleksander

    Abstract | Document (278 KB) | BibTeX

    Very Large Cliques are Easy to Detect
    Authors: Andreev, Alexander E. ; Jukna, Stasys

    Abstract | Document (189 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint
    Published by LZI