2 Search Results for "Eger, Markus"

Document

DOI: 10.4230/LIPIcs.CCC.2024.14

Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture

Authors: Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract

When a group acts on a set, it naturally partitions it into orbits, giving rise to orbit problems. These are natural algorithmic problems, as symmetries are central in numerous questions and structures in physics, mathematics, computer science, optimization, and more. Accordingly, it is of high interest to understand their computational complexity. Recently, Bürgisser et al. (2021) gave the first polynomial-time algorithms for orbit problems of torus actions, that is, actions of commutative continuous groups on Euclidean space. In this work, motivated by theoretical and practical applications, we study the computational complexity of robust generalizations of these orbit problems, which amount to approximating the distance of orbits in ℂⁿ up to a factor γ ≥ 1. In particular, this allows deciding whether two inputs are approximately in the same orbit or far from being so. On the one hand, we prove the NP-hardness of this problem for γ = n^Ω(1/log log n) by reducing the closest vector problem for lattices to it. On the other hand, we describe algorithms for solving this problem for an approximation factor γ = exp(poly(n)). Our algorithms combine tools from invariant theory and algorithmic lattice theory, and they also provide group elements witnessing the proximity of the given orbits (in contrast to the algebraic algorithms of prior work). We prove that they run in polynomial time if and only if a version of the famous number-theoretic abc-conjecture holds - establishing a new and surprising connection between computational complexity and number theory.

Cite as

Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson. Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 14:1-14:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{burgisser_et_al:LIPIcs.CCC.2024.14,
  author =	{B\"{u}rgisser, Peter and Do\u{g}an, Mahmut Levent and Makam, Visu and Walter, Michael and Wigderson, Avi},
  title =	{{Complexity of Robust Orbit Problems for Torus Actions and the abc-Conjecture}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{14:1--14:48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.14},
  URN =		{urn:nbn:de:0030-drops-204100},
  doi =		{10.4230/LIPIcs.CCC.2024.14},
  annote =	{Keywords: computational invariant theory, geometric complexity theory, orbit problems, abc-conjecture, closest vector problem}
}

Document

DOI: 10.4230/OASIcs.CMN.2015.45

Impulse: a Formal Characterization of Story

Authors: Markus Eger, Camille Barot, and R. Michael Young

Published in: OASIcs, Volume 45, 6th Workshop on Computational Models of Narrative (CMN 2015)

Abstract

We present a novel representation of narratives at the story level called Impulse. It combines a temporal representation of a story’s actions and events with a representation of the mental models of the story’s characters into a cohesive, logic-based language. We show the expressiveness of this approach by encoding a story fragment, and compare it to other formal story representations in terms of representational dimensions. We also acknowledge the computational complexity of our approach and argue that a restricted subset still provides a high degree of expressive power

Cite as

Markus Eger, Camille Barot, and R. Michael Young. Impulse: a Formal Characterization of Story. In 6th Workshop on Computational Models of Narrative (CMN 2015). Open Access Series in Informatics (OASIcs), Volume 45, pp. 45-53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{eger_et_al:OASIcs.CMN.2015.45,
  author =	{Eger, Markus and Barot, Camille and Young, R. Michael},
  title =	{{Impulse: a Formal Characterization of Story}},
  booktitle =	{6th Workshop on Computational Models of Narrative (CMN 2015)},
  pages =	{45--53},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-93-4},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{45},
  editor =	{Finlayson, Mark A. and Miller, Ben and Lieto, Antonio and Ronfard, Remi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CMN.2015.45},
  URN =		{urn:nbn:de:0030-drops-52800},
  doi =		{10.4230/OASIcs.CMN.2015.45},
  annote =	{Keywords: Narrative, logic, representation, mental models, time}
}

Refine by Author
1 Barot, Camille
1 Bürgisser, Peter
1 Doğan, Mahmut Levent
1 Eger, Markus
1 Makam, Visu
Show More...

Refine by Classification
1 Computing methodologies → Algebraic algorithms
1 Computing methodologies → Combinatorial algorithms
1 Theory of computation → Algebraic complexity theory

Refine by Keyword
1 Narrative
1 abc-conjecture
1 closest vector problem
1 computational invariant theory
1 geometric complexity theory
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2015
1 2024