1 Search Results for "Høgh, Kasper"


Document
Track A: Algorithms, Complexity and Games
Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem

Authors: Eleni Batziou, Kristoffer Arnsfelt Hansen, and Kasper Høgh

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
In the consensus halving problem we are given n agents with valuations over the interval [0,1]. The goal is to divide the interval into at most n+1 pieces (by placing at most n cuts), which may be combined to give a partition of [0,1] into two sets valued equally by all agents. The existence of a solution may be established by the Borsuk-Ulam theorem. We consider the task of computing an approximation of an exact solution of the consensus halving problem, where the valuations are given by distribution functions computed by algebraic circuits. Here approximation refers to computing a point that is ε-close to an exact solution, also called strong approximation. We show that this task is polynomial time equivalent to computing an approximation to an exact solution of the Borsuk-Ulam search problem defined by a continuous function that is computed by an algebraic circuit. The Borsuk-Ulam search problem is the defining problem of the complexity class BU. We introduce a new complexity class BBU to also capture an alternative formulation of the Borsuk-Ulam theorem from a computational point of view. We investigate their relationship and prove several structural results for these classes as well as for the complexity class FIXP.

Cite as

Eleni Batziou, Kristoffer Arnsfelt Hansen, and Kasper Høgh. Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{batziou_et_al:LIPIcs.ICALP.2021.24,
  author =	{Batziou, Eleni and Hansen, Kristoffer Arnsfelt and H{\o}gh, Kasper},
  title =	{{Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.24},
  URN =		{urn:nbn:de:0030-drops-140939},
  doi =		{10.4230/LIPIcs.ICALP.2021.24},
  annote =	{Keywords: Consensus halving, Computational Complexity, Borsuk-Ulam}
}
  • Refine by Author
  • 1 Batziou, Eleni
  • 1 Hansen, Kristoffer Arnsfelt
  • 1 Høgh, Kasper

  • Refine by Classification
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Borsuk-Ulam
  • 1 Computational Complexity
  • 1 Consensus halving

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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