2 Search Results for "Barrington, David Mix"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.102
Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis

Authors: Armin Weiß

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Goldmann and Russell (2002) initiated the study of the complexity of the equation satisfiability problem in finite groups by showing that it is in 𝖯 for nilpotent groups while it is 𝖭𝖯-complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups of Fitting length two. In this work, we present the first lower bounds for the equation satisfiability problem in finite solvable groups: under the assumption of the exponential time hypothesis, we show that it cannot be in 𝖯 for any group of Fitting length at least four and for certain groups of Fitting length three. Moreover, the same hardness result applies to the equation identity problem.
Cite as

Armin Weiß. Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 102:1-102:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wei:LIPIcs.ICALP.2020.102,
  author =	{Wei{\ss}, Armin},
  title =	{{Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{102:1--102:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.102},
  URN =		{urn:nbn:de:0030-drops-125093},
  doi =		{10.4230/LIPIcs.ICALP.2020.102},
  annote =	{Keywords: equations in groups, solvable groups, exponential time hypothesis}
}
Document
DOI: 10.4230/DagSemRep.172
Complexity of Boolean Functions (Dagstuhl Seminar 9711)

Authors: David Mix Barrington, Noam Nisan, Rüdiger Reischuk, and Ingo Wegener

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

David Mix Barrington, Noam Nisan, Rüdiger Reischuk, and Ingo Wegener. Complexity of Boolean Functions (Dagstuhl Seminar 9711). Dagstuhl Seminar Report 172, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{barrington_et_al:DagSemRep.172,
  author =	{Barrington, David Mix and Nisan, Noam and Reischuk, R\"{u}diger and Wegener, Ingo},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 9711)}},
  pages =	{1--26},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{172},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.172},
  URN =		{urn:nbn:de:0030-drops-150594},
  doi =		{10.4230/DagSemRep.172},
}
  • Refine by Author
  • 1 Barrington, David Mix
  • 1 Nisan, Noam
  • 1 Reischuk, Rüdiger
  • 1 Wegener, Ingo
  • 1 Weiß, Armin

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

  • Refine by Keyword
  • 1 equations in groups
  • 1 exponential time hypothesis
  • 1 solvable groups

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 1997
  • 1 2020

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