2 Search Results for "Matveev, Alexander"

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/LIPIcs.DISC.2017.28

Extending Hardware Transactional Memory Capacity via Rollback-Only Transactions and Suspend/Resume

Authors: Shady Issa, Pascal Felber, Alexander Matveev, and Paolo Romano

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract

Transactional memory (TM) aims at simplifying concurrent programming via the familiar abstraction of atomic transactions. Recently, Intel and IBM have integrated hardware based TM (HTM) implementations in commodity processors, paving the way for the mainstream adoption of the TM paradigm. Yet, existing HTM implementations suffer from a crucial limitation, which hampers the adoption of HTM as a general technique for regulating concurrent access to shared memory: the inability to execute transactions whose working sets exceed the capacity of CPU caches. In this paper we propose P8TM, a novel approach that mitigates this limitation on IBM's POWER8 architecture by leveraging a key combination of techniques: uninstrumented read-only transactions, Rollback Only Transaction-based update transactions, HTM-friendly (software-based) read-set tracking, and self-tuning. P8TM can dynamically switch between different execution modes to best adapt to the nature of the transactions and the experienced abort patterns. In-depth evaluation with several benchmarks indicates that P8TM can achieve striking performance gains in workloads that stress the capacity limitations of HTM, while achieving performance on par with HTM even in unfavourable workloads.

Cite as

Shady Issa, Pascal Felber, Alexander Matveev, and Paolo Romano. Extending Hardware Transactional Memory Capacity via Rollback-Only Transactions and Suspend/Resume. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{issa_et_al:LIPIcs.DISC.2017.28,
  author =	{Issa, Shady and Felber, Pascal and Matveev, Alexander and Romano, Paolo},
  title =	{{Extending Hardware Transactional Memory Capacity via Rollback-Only Transactions and Suspend/Resume}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.28},
  URN =		{urn:nbn:de:0030-drops-79811},
  doi =		{10.4230/LIPIcs.DISC.2017.28},
  annote =	{Keywords: hardware transactional memory, self tuning, parallel programming}
}

Refine by Author
1 Bürgisser, Peter
1 Doğan, Mahmut Levent
1 Felber, Pascal
1 Issa, Shady
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 abc-conjecture
1 closest vector problem
1 computational invariant theory
1 geometric complexity theory
1 hardware transactional memory
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2017
1 2024