95 Search Results for "Potapov, Igor"

Volume

LIPIcs, Volume 117

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

MFCS 2018, August 27-31, 2018, Liverpool, GB

Editors: Igor Potapov, Paul Spirakis, and James Worrell

Document
DOI: 10.4230/LIPIcs.MFCS.2022.8
The Complexity of Periodic Energy Minimisation

Authors: Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, and Igor Potapov

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
The computational complexity of pairwise energy minimisation of N points in real space is a long-standing open problem. The idea of the potential intractability of the problem was supported by a lack of progress in finding efficient algorithms, even when restricted the integer grid approximation. In this paper we provide a firm answer to the problem on ℤ^d by showing that for a large class of pairwise energy functions the problem of periodic energy minimisation is NP-hard if the size of the period (known as a unit cell) is fixed, and is undecidable otherwise. We do so by introducing an abstraction of pairwise average energy minimisation as a mathematical problem, which covers many existing models. The most influential aspects of this work are showing for the first time: 1) undecidability of average pairwise energy minimisation in general 2) computational hardness for the most natural model with periodic boundary conditions, and 3) novel reductions for a large class of generic pairwise energy functions covering many physical abstractions at once. In particular, we develop a new tool of overlapping digital rhombuses to incorporate the properties of the physical force fields, and we connect it with classical tiling problems. Moreover, we illustrate the power of such reductions by incorporating more physical properties such as charge neutrality, and we show an inapproximability result for the extreme case of the 1D average energy minimisation problem.
Cite as

Duncan Adamson, Argyrios Deligkas, Vladimir V. Gusev, and Igor Potapov. The Complexity of Periodic Energy Minimisation. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 8:1-8:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{adamson_et_al:LIPIcs.MFCS.2022.8,
  author =	{Adamson, Duncan and Deligkas, Argyrios and Gusev, Vladimir V. and Potapov, Igor},
  title =	{{The Complexity of Periodic Energy Minimisation}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.8},
  URN =		{urn:nbn:de:0030-drops-168065},
  doi =		{10.4230/LIPIcs.MFCS.2022.8},
  annote =	{Keywords: Optimisation of periodic structures, tiling, undecidability, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.CPM.2021.4
Ranking Bracelets in Polynomial Time

Authors: Duncan Adamson, Vladimir V. Gusev, Igor Potapov, and Argyrios Deligkas

Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)

Abstract
The main result of the paper is the first polynomial-time algorithm for ranking bracelets. The time-complexity of the algorithm is O(k²⋅ n⁴), where k is the size of the alphabet and n is the length of the considered bracelets. The key part of the algorithm is to compute the rank of any word with respect to the set of bracelets by finding three other ranks: the rank over all necklaces, the rank over palindromic necklaces, and the rank over enclosing apalindromic necklaces. The last two concepts are introduced in this paper. These ranks are key components to our algorithm in order to decompose the problem into parts. Additionally, this ranking procedure is used to build a polynomial-time unranking algorithm.
Cite as

Duncan Adamson, Vladimir V. Gusev, Igor Potapov, and Argyrios Deligkas. Ranking Bracelets in Polynomial Time. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 4:1-4:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{adamson_et_al:LIPIcs.CPM.2021.4,
  author =	{Adamson, Duncan and Gusev, Vladimir V. and Potapov, Igor and Deligkas, Argyrios},
  title =	{{Ranking Bracelets in Polynomial Time}},
  booktitle =	{32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-186-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{191},
  editor =	{Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.4},
  URN =		{urn:nbn:de:0030-drops-139554},
  doi =		{10.4230/LIPIcs.CPM.2021.4},
  annote =	{Keywords: Bracelets, Ranking, Necklaces}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.83
On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond

Authors: Paul C. Bell, Igor Potapov, and Pavel Semukhin

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We consider the following variant of the Mortality Problem: given k x k matrices A_1, A_2, ...,A_{t}, does there exist nonnegative integers m_1, m_2, ...,m_t such that the product A_1^{m_1} A_2^{m_2} * ... * A_{t}^{m_{t}} is equal to the zero matrix? It is known that this problem is decidable when t <= 2 for matrices over algebraic numbers but becomes undecidable for sufficiently large t and k even for integral matrices. In this paper, we prove the first decidability results for t>2. We show as one of our central results that for t=3 this problem in any dimension is Turing equivalent to the well-known Skolem problem for linear recurrence sequences. Our proof relies on the Primary Decomposition Theorem for matrices that was not used to show decidability results in matrix semigroups before. As a corollary we obtain that the above problem is decidable for t=3 and k <= 3 for matrices over algebraic numbers and for t=3 and k=4 for matrices over real algebraic numbers. Another consequence is that the set of triples (m_1,m_2,m_3) for which the equation A_1^{m_1} A_2^{m_2} A_3^{m_3} equals the zero matrix is equal to a finite union of direct products of semilinear sets. For t=4 we show that the solution set can be non-semilinear, and thus it seems unlikely that there is a direct connection to the Skolem problem. However we prove that the problem is still decidable for upper-triangular 2 x 2 rational matrices by employing powerful tools from transcendence theory such as Baker’s theorem and S-unit equations.
Cite as

Paul C. Bell, Igor Potapov, and Pavel Semukhin. On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 83:1-83:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bell_et_al:LIPIcs.MFCS.2019.83,
  author =	{Bell, Paul C. and Potapov, Igor and Semukhin, Pavel},
  title =	{{On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{83:1--83:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.83},
  URN =		{urn:nbn:de:0030-drops-110279},
  doi =		{10.4230/LIPIcs.MFCS.2019.83},
  annote =	{Keywords: Linear recurrence sequences, Skolem’s problem, mortality problem, matrix equations, primary decomposition theorem, Baker’s theorem}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.MFCS.2018
LIPIcs, Volume 117, MFCS'18, Complete Volume

Authors: Igor Potapov, Paul Spirakis, and James Worrell

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
LIPIcs, Volume 117, MFCS'18, Complete Volume
Cite as

Igor Potapov, Paul Spirakis, and James Worrell. LIPIcs, Volume 117, MFCS'18, Complete Volume. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{potapov_et_al:LIPIcs.MFCS.2018,
  title =	{{LIPIcs, Volume 117, MFCS'18, Complete Volume}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018},
  URN =		{urn:nbn:de:0030-drops-97459},
  doi =		{10.4230/LIPIcs.MFCS.2018},
  annote =	{Keywords: Theory of computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.MFCS.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Igor Potapov, Paul Spirakis, and James Worrell

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

Igor Potapov, Paul Spirakis, and James Worrell. Front Matter, Table of Contents, Preface, Conference Organization. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 0:i-0:xx, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{potapov_et_al:LIPIcs.MFCS.2018.0,
  author =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.0},
  URN =		{urn:nbn:de:0030-drops-95824},
  doi =		{10.4230/LIPIcs.MFCS.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.1
Consensus Strings with Small Maximum Distance and Small Distance Sum

Authors: Laurent Bulteau and Markus L. Schmid

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
The parameterised complexity of consensus string problems (Closest String, Closest Substring, Closest String with Outliers) is investigated in a more general setting, i. e., with a bound on the maximum Hamming distance and a bound on the sum of Hamming distances between solution and input strings. We completely settle the parameterised complexity of these generalised variants of Closest String and Closest Substring, and partly for Closest String with Outliers; in addition, we answer some open questions from the literature regarding the classical problem variants with only one distance bound. Finally, we investigate the question of polynomial kernels and respective lower bounds.
Cite as

Laurent Bulteau and Markus L. Schmid. Consensus Strings with Small Maximum Distance and Small Distance Sum. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 1:1-1:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bulteau_et_al:LIPIcs.MFCS.2018.1,
  author =	{Bulteau, Laurent and Schmid, Markus L.},
  title =	{{Consensus Strings with Small Maximum Distance and Small Distance Sum}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{1:1--1:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.1},
  URN =		{urn:nbn:de:0030-drops-95834},
  doi =		{10.4230/LIPIcs.MFCS.2018.1},
  annote =	{Keywords: Consensus String Problems, Closest String, Closest Substring, Parameterised Complexity, Kernelisation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.2
Plain Stopping Time and Conditional Complexities Revisited

Authors: Mikhail Andreev, Gleb Posobin, and Alexander Shen

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
In this paper we analyze the notion of "stopping time complexity", the amount of information needed to specify when to stop while reading an infinite sequence. This notion was introduced by Vovk and Pavlovic [Vovk and Pavlovic, 2016]. It turns out that plain stopping time complexity of a binary string x could be equivalently defined as (a) the minimal plain complexity of a Turing machine that stops after reading x on a one-directional input tape; (b) the minimal plain complexity of an algorithm that enumerates a prefix-free set containing x; (c) the conditional complexity C(x|x*) where x in the condition is understood as a prefix of an infinite binary sequence while the first x is understood as a terminated binary string; (d) as a minimal upper semicomputable function K such that each binary sequence has at most 2^n prefixes z such that K(z)<n; (e) as maxC^X(x) where C^X(z) is plain Kolmogorov complexity of z relative to oracle X and the maximum is taken over all extensions X of x. We also show that some of these equivalent definitions become non-equivalent in the more general setting where the condition y and the object x may differ, and answer an open question from Chernov, Hutter and Schmidhuber [Alexey V. Chernov et al., 2007].
Cite as

Mikhail Andreev, Gleb Posobin, and Alexander Shen. Plain Stopping Time and Conditional Complexities Revisited. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 2:1-2:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{andreev_et_al:LIPIcs.MFCS.2018.2,
  author =	{Andreev, Mikhail and Posobin, Gleb and Shen, Alexander},
  title =	{{Plain Stopping Time and Conditional Complexities Revisited}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.2},
  URN =		{urn:nbn:de:0030-drops-95842},
  doi =		{10.4230/LIPIcs.MFCS.2018.2},
  annote =	{Keywords: Kolmogorov complexity, stopping time complexity, structured conditional complexity, algorithmic information theory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.3
Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph

Authors: Hasan Abasi

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We consider the problem of learning the hypergraph using edge-detecting queries. In this model, the learner is allowed to query whether a set of vertices includes an edge from a hidden hypergraph. Except a few, all previous algorithms assume that a query's result is always correct. In this paper we study the problem of learning a hypergraph where alpha -fraction of the queries are incorrect. The main contribution of this paper is generalizing the well-known structure CFF (Cover Free Family) to be Dense (we will call it DCFF - Dense Cover Free Family) while presenting three different constructions for DCFF. Later, we use these constructions wisely to give a polynomial time non-adaptive learning algorithm for a hypergraph problem with at most alpha-fracion incorrect queries. The hypergraph problem is also known as both monotone DNF learning problem, and complexes group testing problem.
Cite as

Hasan Abasi. Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 3:1-3:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abasi:LIPIcs.MFCS.2018.3,
  author =	{Abasi, Hasan},
  title =	{{Error-Tolerant Non-Adaptive Learning of a Hidden Hypergraph}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.3},
  URN =		{urn:nbn:de:0030-drops-95854},
  doi =		{10.4230/LIPIcs.MFCS.2018.3},
  annote =	{Keywords: Error Tolerant Algorithm, Hidden Hypergraph, Montone DNF, Group Testing, Non-Adaptive Learning}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.4
From Expanders to Hitting Distributions and Simulation Theorems

Authors: Alexander Kozachinskiy

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
In this paper we explore hitting distributions, a notion that arose recently in the context of deterministic "query-to-communication" simulation theorems. We show that any expander in which any two distinct vertices have at most one common neighbor can be transformed into a gadget possessing good hitting distributions. We demonstrate that this result is applicable to affine plane expanders and to Lubotzky-Phillips-Sarnak construction of Ramanujan graphs . In particular, from affine plane expanders we extract a gadget achieving the best known trade-off between the arity of outer function and the size of gadget. More specifically, when this gadget has k bits on input, it admits a simulation theorem for all outer function of arity roughly 2^(k/2) or less (the same was also known for k-bit Inner Product). In addition we show that, unlike Inner Product, underlying hitting distributions in our new gadget are "polynomial-time listable" in the sense that their supports can be written down in time 2^O(k), i.e. in time polynomial in size of gadget's matrix. We also obtain two results showing that with current technique no better trade-off between the arity of outer function and the size of gadget can be achieved. Namely, we observe that no gadget can have hitting distributions with significantly better parameters than Inner Product or our new affine plane gadget. We also show that Thickness Lemma, a place which causes restrictions on the arity of outer functions in proofs of simulation theorems, is unimprovable.
Cite as

Alexander Kozachinskiy. From Expanders to Hitting Distributions and Simulation Theorems. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 4:1-4:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kozachinskiy:LIPIcs.MFCS.2018.4,
  author =	{Kozachinskiy, Alexander},
  title =	{{From Expanders to Hitting Distributions and Simulation Theorems}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.4},
  URN =		{urn:nbn:de:0030-drops-95863},
  doi =		{10.4230/LIPIcs.MFCS.2018.4},
  annote =	{Keywords: simulation theorems, hitting distributions, expanders}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.5
Balance Problems for Integer Circuits

Authors: Titus Dose

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We investigate the computational complexity of balance problems for {-,*}-circuits computing finite sets of natural numbers. These problems naturally build on problems for integer expressions and integer circuits studied by Stockmeyer and Meyer (1973), McKenzie and Wagner (2007), and Glaßer et al. (2010). Our work shows that the balance problem for {-,*}-circuits is undecidable which is the first natural problem for integer circuits or related constraint satisfaction problems that admits only one arithmetic operation and is proven to be undecidable. Starting from this result we precisely characterize the complexity of balance problems for proper subsets of {-,*}. These problems turn out to be complete for one of the classes L, NL, and NP.
Cite as

Titus Dose. Balance Problems for Integer Circuits. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 5:1-5:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dose:LIPIcs.MFCS.2018.5,
  author =	{Dose, Titus},
  title =	{{Balance Problems for Integer Circuits}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.5},
  URN =		{urn:nbn:de:0030-drops-95874},
  doi =		{10.4230/LIPIcs.MFCS.2018.5},
  annote =	{Keywords: computational complexity, integer expressions, integer circuits}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.6
On Hadamard Series and Rotating Q-Automata

Authors: Louis-Marie Dando and Sylvain Lombardy

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
In this paper, we study rotating Q-automata, which are (memoryless) automata with weights in Q, that can read the input tape from left to right several times. We show that the series realized by valid rotating Q-automata are Q-Hadamard series (which are the closure of Q-rational series by pointwise inverse), and that every Q-Hadamard series can be realized by such an automaton. We prove that, although validity of rotating Q-automata is undecidable, the equivalence problem is decidable on rotating Q-automata. Finally, we prove that every valid two-way Q-automaton admits an equivalent rotating Q-automaton. The conversion, which is effective, implies the decidability of equivalence of two-way Q-automata.
Cite as

Louis-Marie Dando and Sylvain Lombardy. On Hadamard Series and Rotating Q-Automata. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 6:1-6:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dando_et_al:LIPIcs.MFCS.2018.6,
  author =	{Dando, Louis-Marie and Lombardy, Sylvain},
  title =	{{On Hadamard Series and Rotating Q-Automata}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.6},
  URN =		{urn:nbn:de:0030-drops-95881},
  doi =		{10.4230/LIPIcs.MFCS.2018.6},
  annote =	{Keywords: Rational series, Hadamard operations, Rotating automata, Two-way automata}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.7
One-Sided Error Communication Complexity of Gap Hamming Distance

Authors: Egor Klenin and Alexander Kozachinskiy

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Assume that Alice has a binary string x and Bob a binary string y, both strings are of length n. Their goal is to output 0, if x and y are at least L-close in Hamming distance, and output 1, if x and y are at least U-far in Hamming distance, where L < U are some integer parameters known to both parties. If the Hamming distance between x and y lies in the interval (L, U), they are allowed to output anything. This problem is called the Gap Hamming Distance. In this paper we study public-coin one-sided error communication complexity of this problem. The error with probability at most 1/2 is allowed only for pairs at Hamming distance at least U. In this paper we determine this complexity up to factors logarithmic in L. The protocol we construct for the upper bound is simultaneous.
Cite as

Egor Klenin and Alexander Kozachinskiy. One-Sided Error Communication Complexity of Gap Hamming Distance. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 7:1-7:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{klenin_et_al:LIPIcs.MFCS.2018.7,
  author =	{Klenin, Egor and Kozachinskiy, Alexander},
  title =	{{One-Sided Error Communication Complexity of Gap Hamming Distance}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.7},
  URN =		{urn:nbn:de:0030-drops-95893},
  doi =		{10.4230/LIPIcs.MFCS.2018.7},
  annote =	{Keywords: Communication Complexity, Gap Hamming Distance, one-sided error}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.8
Online Maximum Matching with Recourse

Authors: Spyros Angelopoulos, Christoph Dürr, and Shendan Jin

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter k. An online algorithm for this problem has to maintain a valid matching while edges of the underlying graph are presented one after the other. At any moment the algorithm can decide to include an edge into the matching or to exclude it, under the restriction that at most k such actions per edge take place, where k is typically a small constant. This problem was introduced and studied in the context of general online packing problems with recourse by Avitabile et al. [Avitabile et al., 2013], whereas the special case k=2 was studied by Boyar et al. [Boyar et al., 2017]. In the first part of this paper, we consider the edge arrival model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP given in [Avitabile et al., 2013], by exploiting the structure of the matching problem. In addition, we extend the result of [Boyar et al., 2017] and show that the greedy algorithm has competitive ratio 3/2 for every even k and ratio 2 for every odd k. Moreover, we present and analyze an improvement of the greedy algorithm which we call L-Greedy, and we show that for small values of k it outperforms the algorithm of [Avitabile et al., 2013]. In terms of lower bounds, we show that no deterministic algorithm better than 1+1/(k-1) exists, improving upon the lower bound of 1+1/k shown in [Avitabile et al., 2013]. The second part of the paper is devoted to the edge arrival/departure model, which is the fully dynamic variant of online matching with recourse. The analysis of L-Greedy and AMP carry through in this model; moreover we show a lower bound of (k^2-3k+6)/(k^2-4k+7) for all even k >= 4. For k in {2,3}, the competitive ratio is 3/2.
Cite as

Spyros Angelopoulos, Christoph Dürr, and Shendan Jin. Online Maximum Matching with Recourse. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 8:1-8:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{angelopoulos_et_al:LIPIcs.MFCS.2018.8,
  author =	{Angelopoulos, Spyros and D\"{u}rr, Christoph and Jin, Shendan},
  title =	{{Online Maximum Matching with Recourse}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.8},
  URN =		{urn:nbn:de:0030-drops-95908},
  doi =		{10.4230/LIPIcs.MFCS.2018.8},
  annote =	{Keywords: Competitive ratio, maximum cardinality matching, recourse}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.9
Linking Focusing and Resolution with Selection

Authors: Guillaume Burel

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Focusing and selection are techniques that shrink the proof search space for respectively sequent calculi and resolution. To bring out a link between them, we generalize them both: we introduce a sequent calculus where each occurrence of an atom can have a positive or a negative polarity; and a resolution method where each literal, whatever its sign, can be selected in input clauses. We prove the equivalence between cut-free proofs in this sequent calculus and derivations of the empty clause in that resolution method. Such a generalization is not semi-complete in general, which allows us to consider complete instances that correspond to theories of any logical strength. We present three complete instances: first, our framework allows us to show that ordinary focusing corresponds to hyperresolution and semantic resolution; the second instance is deduction modulo theory; and a new setting, not captured by any existing framework, extends deduction modulo theory with rewriting rules having several left-hand sides, which restricts even more the proof search space.
Cite as

Guillaume Burel. Linking Focusing and Resolution with Selection. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{burel:LIPIcs.MFCS.2018.9,
  author =	{Burel, Guillaume},
  title =	{{Linking Focusing and Resolution with Selection}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.9},
  URN =		{urn:nbn:de:0030-drops-95917},
  doi =		{10.4230/LIPIcs.MFCS.2018.9},
  annote =	{Keywords: logic in computer science, automated deduction, proof theory, sequent calculus, refinements of resolution, deduction modulo theory, polarization}
}
  • Refine by Author
  • 10 Potapov, Igor
  • 3 Deligkas, Argyrios
  • 3 Semukhin, Pavel
  • 2 Adamson, Duncan
  • 2 Erlebach, Thomas
  • Show More...

  • Refine by Classification
  • 9 Mathematics of computing → Graph algorithms
  • 8 Theory of computation → Problems, reductions and completeness
  • 7 Mathematics of computing → Graph theory
  • 6 Theory of computation → Complexity theory and logic
  • 5 Theory of computation → Formal languages and automata theory
  • Show More...

  • Refine by Keyword
  • 3 Kolmogorov complexity
  • 3 decidability
  • 2 Algorithms
  • 2 Approximation Algorithms
  • 2 Computational Complexity
  • Show More...

  • Refine by Type
  • 94 document
  • 1 volume

  • Refine by Publication Year
  • 88 2018
  • 2 2016
  • 1 2013
  • 1 2017
  • 1 2019
  • Show More...

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact