Dagstuhl Seminar Proceedings, Volume 7411

Document

07411 Abstracts Collection – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf

Abstract

From 07.10. to 12.10., the Dagstuhl Seminar 07411 ``Algebraic Methods in Computational Complexity'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and 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 paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf. 07411 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.07411.1,
  author =	{Agrawal, Manindra and Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas},
  title =	{{07411 Abstracts Collection – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.1},
  URN =		{urn:nbn:de:0030-drops-13072},
  doi =		{10.4230/DagSemProc.07411.1},
  annote =	{Keywords: Computational complexity, algebra, quantum computing, (de-) randomization}
}

Document

DOI: 10.4230/DagSemProc.07411.2

07411 Executive Summary – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf

Abstract

The seminar brought together almost 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed once again the great importance of algebraic techniques for theoretical computer science. We had almost 30 talks of length between 15 and 45 minutes. This left enough room for discussions. We had an open problem session that was very much appreciated.

Cite as

Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf. 07411 Executive Summary – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.07411.2,
  author =	{Agrawal, Manindra and Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas},
  title =	{{07411 Executive Summary – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.2},
  URN =		{urn:nbn:de:0030-drops-13061},
  doi =		{10.4230/DagSemProc.07411.2},
  annote =	{Keywords: Computational complexity, algebra, quantum computing, (de-) randomization}
}

Document

DOI: 10.4230/DagSemProc.07411.3

Classical Simulation Complexity of Quantum Branching Programs

Authors: Farid Ablayev

Abstract

We present classical simulation techniques for measure once quantum branching programs. For bounded error syntactic quantum branching program of width $w$ that computes a function with error $delta$ we present a classical deterministic branching program of the same length and width at most $(1+2/(1-2delta))^{2w}$ that computes the same function. Second technique is a classical stochastic simulation technique for bounded error and unbounded error quantum branching programs. Our result is that it is possible stochastically-classically simulate quantum branching programs with the same length and almost the same width, but we lost bounded error acceptance property.

Cite as

Farid Ablayev. Classical Simulation Complexity of Quantum Branching Programs. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{ablayev:DagSemProc.07411.3,
  author =	{Ablayev, Farid},
  title =	{{Classical Simulation Complexity of  Quantum  Branching Programs}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.3},
  URN =		{urn:nbn:de:0030-drops-13107},
  doi =		{10.4230/DagSemProc.07411.3},
  annote =	{Keywords: Quantum algorithms, Branching Programs, Complexity}
}

Document

DOI: 10.4230/DagSemProc.07411.4

Diagonal Circuit Identity Testing and Lower Bounds

Authors: Nitin Saxena

Abstract

In this talk we give a deterministic polynomial time algorithm for testing whether a {em diagonal} depth-$3$ circuit $C(arg{x}{n})$ (i.e. $C$ is a sum of powers of linear functions) is zero.

Cite as

Nitin Saxena. Diagonal Circuit Identity Testing and Lower Bounds. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{saxena:DagSemProc.07411.4,
  author =	{Saxena, Nitin},
  title =	{{Diagonal Circuit Identity Testing and Lower Bounds}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--1},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.4},
  URN =		{urn:nbn:de:0030-drops-13087},
  doi =		{10.4230/DagSemProc.07411.4},
  annote =	{Keywords: Arithmetic circuit, identity testing, depth 3, depth 4, determinant, permanent, lower bound}
}

Document

DOI: 10.4230/DagSemProc.07411.5

High Entropy Random Selection Protocols

Authors: Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir

Abstract

We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n - O(1) and has 4log^* n rounds, improving over the protocol of Goldwasser et al. that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n^2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits of communication and yields entropy n- O(log n) and min-entropy n/2 - O(log n). Our protocol achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al., however achieves much higher min-entropy: n/2 - O(log n) versus O(log n). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n -o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.

Cite as

Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir. High Entropy Random Selection Protocols. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{vereshchagin_et_al:DagSemProc.07411.5,
  author =	{Vereshchagin, Nikolai K. and Buhrman, Harry and Cristandl, Matthias and Koucky, Michal and Lotker, Zvi and Patt-Shamir, Boaz},
  title =	{{High Entropy Random Selection Protocols}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.5},
  URN =		{urn:nbn:de:0030-drops-13091},
  doi =		{10.4230/DagSemProc.07411.5},
  annote =	{Keywords: Shannon entropy, Random string ds}
}

Document

DOI: 10.4230/DagSemProc.07411.6

The Unique Games Conjecture with Entangled Provers is False

Authors: Julia Kempe, Oded Regev, and Ben Toner

Abstract

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program. Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel `quantum rounding technique', showing how to take a solution to an SDP and transform it to a strategy for entangled provers.

Cite as

Julia Kempe, Oded Regev, and Ben Toner. The Unique Games Conjecture with Entangled Provers is False. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kempe_et_al:DagSemProc.07411.6,
  author =	{Kempe, Julia and Regev, Oded and Toner, Ben},
  title =	{{The Unique Games Conjecture with Entangled Provers is False}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.6},
  URN =		{urn:nbn:de:0030-drops-13048},
  doi =		{10.4230/DagSemProc.07411.6},
  annote =	{Keywords: Unique games, entanglement}
}

Document

DOI: 10.4230/DagSemProc.07411.7

Uniqueness of Optimal Mod 3 Circuits for Parity

Authors: Frederic Green and Amitabha Roy

Abstract

We prove that the quadratic polynomials modulo $3$ with the largest correlation with parity are unique up to permutation of variables and constant factors. As a consequence of our result, we completely characterize the smallest MAJ~$circ mbox{MOD}_3 circ { m AND}_2$ circuits that compute parity, where a MAJ~$circ mbox{MOD}_3 circ { m AND}_2$ circuit is one that has a majority gate as output, a middle layer of MOD$_3$ gates and a bottom layer of AND gates of fan-in $2$. We also prove that the sub-optimal circuits exhibit a stepped behavior: any sub-optimal circuits of this class that compute parity must have size at least a factor of $frac{2}{sqrt{3}}$ times the optimal size. This verifies, for the special case of $m=3$, two conjectures made by Due~{n}ez, Miller, Roy and Straubing (Journal of Number Theory, 2006) for general MAJ~$circ mathrm{MOD}_m circ { m AND}_2$ circuits for any odd $m$. The correlation and circuit bounds are obtained by studying the associated exponential sums, based on some of the techniques developed by Green (JCSS, 2004). We regard this as a step towards obtaining tighter bounds both for the $m ot = 3$ quadratic case as well as for higher degrees.

Cite as

Frederic Green and Amitabha Roy. Uniqueness of Optimal Mod 3 Circuits for Parity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{green_et_al:DagSemProc.07411.7,
  author =	{Green, Frederic and Roy, Amitabha},
  title =	{{Uniqueness of Optimal Mod 3 Circuits  for Parity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.7},
  URN =		{urn:nbn:de:0030-drops-13059},
  doi =		{10.4230/DagSemProc.07411.7},
  annote =	{Keywords: Circuit complexity, correlations, exponential sums}
}

Dagstuhl Seminar Proceedings, Volume 7411

Publication Details

Access Numbers

Documents

07411 Abstracts Collection – Algebraic Methods in Computational Complexity

Abstract

Cite as

07411 Executive Summary – Algebraic Methods in Computational Complexity

Abstract

Cite as

Classical Simulation Complexity of Quantum Branching Programs

Abstract

Cite as

Diagonal Circuit Identity Testing and Lower Bounds

Abstract

Cite as

High Entropy Random Selection Protocols

Abstract

Cite as

The Unique Games Conjecture with Entangled Provers is False

Abstract

Cite as

Uniqueness of Optimal Mod 3 Circuits for Parity

Abstract

Cite as

Filters

Thanks for your feedback!

Could not send message