Search Results

Documents authored by Gasarch, William

Document
DOI: 10.4230/LIPIcs.FUN.2018.15
A Muffin-Theorem Generator

Authors: Guangqi Cui, John Dickerson, Naveen Durvasula, William Gasarch, Erik Metz, Jacob Prinz, Naveen Raman, Daniel Smolyak, and Sung Hyun Yoo

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Consider the following FUN problem. Given m,s you want to divide m muffins among s students so that everyone gets m/(s) muffins; however, you want to maximize the minimum piece so that nobody gets crumbs. Let f(m,s) be the size of the smallest piece in an optimal procedure. We study the case where ceil(2m/s)=3 because (1) many of our hardest open problems were of this form until we found this method, (2) we have used the technique to generate muffin-theorems, and (3) we conjecture this can be used to solve the general case. We give (1) an algorithm to find an upper bound for f(m,s) when ceil(2m/s)(and some ways to speed up that algorithm if certain conjectures are true), (2) an algorithm that uses the information from (1) to try to find a lower bound on f(m,s) (a procedure) which matches the upper bound, (3) an algorithm that uses the information from (1) to generate muffin-theorems, and (4) an algorithm that we think works well in practice to find f(m,s) for any m,s.
Cite as

Guangqi Cui, John Dickerson, Naveen Durvasula, William Gasarch, Erik Metz, Jacob Prinz, Naveen Raman, Daniel Smolyak, and Sung Hyun Yoo. A Muffin-Theorem Generator. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cui_et_al:LIPIcs.FUN.2018.15,
  author =	{Cui, Guangqi and Dickerson, John and Durvasula, Naveen and Gasarch, William and Metz, Erik and Prinz, Jacob and Raman, Naveen and Smolyak, Daniel and Yoo, Sung Hyun},
  title =	{{A Muffin-Theorem Generator}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.15},
  URN =		{urn:nbn:de:0030-drops-88062},
  doi =		{10.4230/LIPIcs.FUN.2018.15},
  annote =	{Keywords: Fair Division, Theorem Generation}
}
Document
DOI: 10.4230/DagSemProc.04421.3
Finding Isolated Cliques by Queries – An Approach to Fault Diagnosis with Many Faults

Authors: William Gasarch and Frank Stephan

Published in: Dagstuhl Seminar Proceedings, Volume 4421, Algebraic Methods in Computational Complexity (2005)

Abstract
A well-studied problem in fault diagnosis is to identify the set of all good processors in a given set $\{p_1,p_2,\ldots,p_n\}$ of processors via asking some processors $p_i$ to test whether processor $p_j$ is good or faulty. Mathematically, the set $C$ of the indices of good processors forms an isolated clique in the graph with the edges $E = \{(i,j):$ if you ask $p_i$ to test $p_j$ then $p_i$ states that ``$p_j$ is good''$\}$; where $C$ is an isolated clique iff it holds for every $i \in C$ and $j \neq i$ that $(i,j) \in E$ iff $j \in C$. In the present work, the classical setting of fault diagnosis is modified by no longer requiring that $C$ contains at least $\frac{n+1}{2}$ of the $n$ nodes of the graph. Instead, one is given a lower bound $a$ on the size of $C$ and the number $n$ of nodes and one has to find a list of up to $n/a$ candidates containing all isolated cliques of size $a$ or more where the number of queries whether a given edge is in $E$ is as small as possible. It is shown that the number of queries necessary differs at most by $n$ for the case of directed and undirected graphs. Furthermore, for directed graphs the lower bound $n^2/(2a-2)-3n$ and the upper bound $2n^2/a$ are established. For some constant values of $a$, better bounds are given. In the case of parallel queries, the number of rounds is at least $n/(a-1)-6$ and at most $O(\log(a)n/a)$.
Cite as

William Gasarch and Frank Stephan. Finding Isolated Cliques by Queries – An Approach to Fault Diagnosis with Many Faults. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 4421, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{gasarch_et_al:DagSemProc.04421.3,
  author =	{Gasarch, William and Stephan, Frank},
  title =	{{Finding Isolated Cliques by Queries – An Approach to Fault Diagnosis with Many Faults}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4421},
  editor =	{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.04421.3},
  URN =		{urn:nbn:de:0030-drops-1066},
  doi =		{10.4230/DagSemProc.04421.3},
  annote =	{Keywords: Isolated Cliques , Query-Complexity , Fault Diagnosis}
}
Document
DOI: 10.4230/DagSemProc.04421.6
The communication complexity of the Exact-N Problem revisited

Authors: William Gasarch, James Glenn, and Andre Utis

Published in: Dagstuhl Seminar Proceedings, Volume 4421, Algebraic Methods in Computational Complexity (2005)

Abstract
If Alice has x, y, Bob has x, z and Carol has y, z can they determine if x+y+z=N? They can if (say) Alice broadcasts x to Bob and Carol; can they do better? Chandra, Furst, and Lipton studied this problem and showed sublinear upper bounds. They also had matching (up to an additive constant) lower bounds. We give an exposition of their result with some attention to what happens for particular values of N.
Cite as

William Gasarch, James Glenn, and Andre Utis. The communication complexity of the Exact-N Problem revisited. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 4421, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{gasarch_et_al:DagSemProc.04421.6,
  author =	{Gasarch, William and Glenn, James and Utis, Andre},
  title =	{{The communication complexity of the Exact-N Problem revisited}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4421},
  editor =	{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.04421.6},
  URN =		{urn:nbn:de:0030-drops-1026},
  doi =		{10.4230/DagSemProc.04421.6},
  annote =	{Keywords: Communication Complexity , Exact-N problem , Arithmetic Sequences}
}
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