DROPS

Document

Systems and Algorithms for Large-scale Graph Analytics (Dagstuhl Seminar 14462)

Authors: Eiko Yoneki, Amitabha Roy, and Derek Murray

Published in: Dagstuhl Reports, Volume 4, Issue 11 (2015)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 14462 "Systems and Algorithms for Large-scale Graph Analytics". The seminar was a successful gathering of computer scientists from the domains of systems, algorithms, architecture and databases all of whom are interested in graph processing.

Cite as

Eiko Yoneki, Amitabha Roy, and Derek Murray. Systems and Algorithms for Large-scale Graph Analytics (Dagstuhl Seminar 14462). In Dagstuhl Reports, Volume 4, Issue 11, pp. 59-77, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{yoneki_et_al:DagRep.4.11.59,
  author =	{Yoneki, Eiko and Roy, Amitabha and Murray, Derek},
  title =	{{Systems and Algorithms for Large-scale Graph Analytics (Dagstuhl Seminar 14462)}},
  pages =	{59--77},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{11},
  editor =	{Yoneki, Eiko and Roy, Amitabha and Murray, Derek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.11.59},
  URN =		{urn:nbn:de:0030-drops-49700},
  doi =		{10.4230/DagRep.4.11.59},
  annote =	{Keywords: Large-scale graph processing, Graph structured data, Database, Graph algorithms, Parallel I/O, Parallel programming, Storage, Distributed systems, GPU}
}

Document

DOI: 10.4230/DagSemProc.07411.7

Uniqueness of Optimal Mod 3 Circuits for Parity

Authors: Frederic Green and Amitabha Roy

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

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}
}

Search Results

Documents authored by Roy, Amitabha

Systems and Algorithms for Large-scale Graph Analytics (Dagstuhl Seminar 14462)

Abstract

Cite as

Uniqueness of Optimal Mod 3 Circuits for Parity

Abstract

Cite as

Thanks for your feedback!

Could not send message