Volume

Dagstuhl Seminar Proceedings, Volume 8381

Publication Details

  • published at: 2008-12-11
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.08381.1
08381 Abstracts Collection – Computational Complexity of Discrete Problems

Authors: Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek

Abstract
From the 14th of September to the 19th of September, the Dagstuhl Seminar 08381 ``Computational Complexity of Discrete Problems'' was held in Schloss Dagstuhl - Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work as well as open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this report. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Abstracts Collection – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{miltersen_et_al:DagSemProc.08381.1,
  author =	{Miltersen, Peter Bro and Reischuk, R\"{u}diger and Schnitger, Georg and van Melkebeek, Dieter},
  title =	{{08381 Abstracts Collection – Computational Complexity of Discrete Problems}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.1},
  URN =		{none},
  doi =		{10.4230/DagSemProc.08381.1},
  annote =	{Keywords: Computational complexity, discrete problems, Turing machines, circuits, proof complexity, pseudorandomness, derandomization, cryptography, computational learning, communication complexity, query complexity, hardness of approximation}
}
Document
DOI: 10.4230/DagSemProc.08381.2
08381 Executive Summary – Computational Complexity of Discrete Problems

Authors: Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek

Abstract
Estimating the computational complexity of discrete problems constitutes one of the central and classical topics in the theory of computation. Mathematicians and computer scientists have long tried to classify natural families of Boolean relations according to fundamental complexity measures like time and space, both in the uniform and in the nonuniform setting. Several models of computation have been developed in order to capture the various capabilities of digital computing devices, including parallelism, randomness, and quantum interference.
Cite as

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Executive Summary – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{miltersen_et_al:DagSemProc.08381.2,
  author =	{Miltersen, Peter Bro and Reischuk, R\"{u}diger and Schnitger, Georg and van Melkebeek, Dieter},
  title =	{{08381 Executive Summary – Computational Complexity of Discrete Problems}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.2},
  URN =		{urn:nbn:de:0030-drops-17789},
  doi =		{10.4230/DagSemProc.08381.2},
  annote =	{Keywords: Computational complexity, discrete problems, Turing machines, circuits, proof complexity, pseudorandomness, derandomization, cryptography, computational learning, communication complexity, query complexity, hardness of approximation}
}
Document
DOI: 10.4230/DagSemProc.08381.3
Approximation norms and duality for communication complexity lower bounds

Authors: Troy Lee and Adi Shraibman

Abstract
Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound quantity phrased as a maximization problem, which can be more convenient to work with in showing lower bounds. We discuss two applications of this approach. 1. The approximation rank of a matrix A is the minimum rank of a matrix close to A in ell_infty norm. The logarithm of approximation rank lower bounds quantum communication complexity and is one of the most powerful techniques available, albeit difficult to compute in practice. We show that an approximation norm known as gamma_2 is polynomially related to approximation rank. This results in a polynomial time algorithm to approximate approximation rank, and also shows that the logarithm of approximation rank lower bounds quantum communication complexity even with entanglement which was previously not known. 2. By means of an approximation norm which lower bounds multiparty number-on-the-forehead complexity, we show non-trivial lower bounds on the complexity of the disjointness function for up to c log log n players, c <1.
Cite as

Troy Lee and Adi Shraibman. Approximation norms and duality for communication complexity lower bounds. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:DagSemProc.08381.3,
  author =	{Lee, Troy and Shraibman, Adi},
  title =	{{Approximation norms and duality for communication complexity lower bounds}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.3},
  URN =		{urn:nbn:de:0030-drops-17768},
  doi =		{10.4230/DagSemProc.08381.3},
  annote =	{Keywords: Communication complexity, lower bounds}
}
Document
DOI: 10.4230/DagSemProc.08381.4
Depth Reduction for Circuits with a Single Layer of Modular Counting Gates

Authors: Kristoffer Arnsfelt Hansen

Abstract
We consider the class of constant depth AND/OR circuits augmented with a layer of modular counting gates at the bottom layer, i.e ${AC}^0 circ {MOD}_m$ circuits. We show that the following holds for several types of gates $G$: by adding a gate of type $G$ at the output, it is possible to obtain an equivalent randomized depth 2 circuit of quasipolynomial size consisting of a gate of type $G$ at the output and a layer of modular counting gates, i.e $G circ {MOD}_m$ circuits. The types of gates $G$ we consider are modular counting gates and threshold-style gates. For all of these, strong lower bounds are known for (deterministic) $G circ {MOD}_m$ circuits.
Cite as

Kristoffer Arnsfelt Hansen. Depth Reduction for Circuits with a Single Layer of Modular Counting Gates. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{hansen:DagSemProc.08381.4,
  author =	{Hansen, Kristoffer Arnsfelt},
  title =	{{Depth Reduction for Circuits with a Single Layer of Modular Counting Gates}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.4},
  URN =		{urn:nbn:de:0030-drops-17824},
  doi =		{10.4230/DagSemProc.08381.4},
  annote =	{Keywords: Boolean Circuits, Randomized Polynomials, Fourier sums}
}
Document
DOI: 10.4230/DagSemProc.08381.5
Fast polynomial factorization and modular composition

Authors: Kiran Kedlaya and Christopher Umans

Abstract
We obtain randomized algorithms for factoring degree $n$ univariate polynomials over $F_q$ requiring $O(n^{1.5 + o(1)} log^{1+o(1)} q+ n^{1 + o(1)}log^{2+o(1)} q)$ bit operations. When $log q < n$, this is asymptotically faster than the best previous algorithms (von zur Gathen & Shoup (1992) and Kaltofen & Shoup (1998)); for $log q ge n$, it matches the asymptotic running time of the best known algorithms. The improvements come from new algorithms for modular composition of degree $n$ univariate polynomials, which is the asymptotic bottleneck in fast algorithms for factoring polynomials over finite fields. The best previous algorithms for modular composition use $O(n^{(omega + 1)/2})$ field operations, where $omega$ is the exponent of matrix multiplication (Brent & Kung (1978)), with a slight improvement in the exponent achieved by employing fast rectangular matrix multiplication (Huang & Pan (1997)). We show that modular composition and multipoint evaluation of multivariate polynomials are essentially equivalent, in the sense that an algorithm for one achieving exponent $alpha$ implies an algorithm for the other with exponent $alpha + o(1)$, and vice versa. We then give two new algorithms that solve the problem optimally (up to lower order terms): an algebraic algorithm for fields of characteristic at most $n^{o(1)}$, and a nonalgebraic algorithm that works in arbitrary characteristic. The latter algorithm works by lifting to characteristic 0, applying a small number of rounds of {em multimodular reduction}, and finishing with a small number of multidimensional FFTs. The final evaluations are reconstructed using the Chinese Remainder Theorem. As a bonus, this algorithm produces a very efficient data structure supporting polynomial evaluation queries, which is of independent interest. Our algorithms use techniques which are commonly employed in practice, so they may be competitive for real problem sizes. This contrasts with all previous subquadratic algorithsm for these problems, which rely on fast matrix multiplication. This is joint work with Kiran Kedlaya.
Cite as

Kiran Kedlaya and Christopher Umans. Fast polynomial factorization and modular composition. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kedlaya_et_al:DagSemProc.08381.5,
  author =	{Kedlaya, Kiran and Umans, Christopher},
  title =	{{Fast polynomial factorization and modular composition}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--33},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.5},
  URN =		{urn:nbn:de:0030-drops-17771},
  doi =		{10.4230/DagSemProc.08381.5},
  annote =	{Keywords: Modular composition; polynomial factorization; multipoint evaluation; Chinese Remaindering}
}
Document
DOI: 10.4230/DagSemProc.08381.6
Understanding space in resolution: optimal lower bounds and exponential trade-offs

Authors: Eli Ben-Sasson and Jakob Nordström

Abstract
We continue the study of tradeoffs between space and length of resolution proofs and focus on two new results: begin{enumerate} item We show that length and space in resolution are uncorrelated. This is proved by exhibiting families of CNF formulas of size $O(n)$ that have proofs of length $O(n)$ but require space $Omega(n / log n)$. Our separation is the strongest possible since any proof of length $O(n)$ can always be transformed into a proof in space $O(n / log n)$, and improves previous work reported in [Nordstr"{o}m 2006, Nordstr"{o}m and H{aa}stad 2008]. item We prove a number of trade-off results for space in the range from constant to $O(n / log n)$, most of them superpolynomial or even exponential. This is a dramatic improvement over previous results in [Ben-Sasson 2002, Hertel and Pitassi 2007, Nordstr"{o}m 2007]. end{enumerate} The key to our results is the following, somewhat surprising, theorem: Any CNF formula $F$ can be transformed by simple substitution transformation into a new formula $F'$ such that if $F$ has the right properties, $F'$ can be proven in resolution in essentially the same length as $F$ but the minimal space needed for $F'$ is lower-bounded by the number of variables that have to be mentioned simultaneously in any proof for $F$. Applying this theorem to so-called pebbling formulas defined in terms of pebble games over directed acyclic graphs and analyzing black-white pebbling on these graphs yields our results.
Cite as

Eli Ben-Sasson and Jakob Nordström. Understanding space in resolution: optimal lower bounds and exponential trade-offs. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bensasson_et_al:DagSemProc.08381.6,
  author =	{Ben-Sasson, Eli and Nordstr\"{o}m, Jakob},
  title =	{{Understanding space in resolution: optimal lower bounds and exponential trade-offs}},
  booktitle =	{Computational Complexity of Discrete Problems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.6},
  URN =		{urn:nbn:de:0030-drops-17815},
  doi =		{10.4230/DagSemProc.08381.6},
  annote =	{Keywords: Proof complexity, Resolution, Pebbling.}
}

Filters

  • Authors
  • B
  • Ben-Sasson, Eli
  • H
  • Hansen, Kristoffer Arnsfelt
  • K
  • Kedlaya, Kiran
  • L
  • Lee, Troy
  • M
  • Miltersen, Peter Bro
  • N
  • Nordström, Jakob
  • R
  • Reischuk, Rüdiger
  • S
  • Schnitger, Georg
  • Shraibman, Adi
  • U
  • Umans, Christopher
  • V
  • van Melkebeek, Dieter

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact