15 Search Results for "Besc�s, Javier Oliv�n"


Document
Isomorphism Problem for S_d-Graphs

Authors: Deniz Ağaoğlu and Petr Hliněný

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
An H-graph is the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró, Hujter and Tuza (1992). We focus on S_d-graphs as a special case generalizing interval graphs. A graph G is an S_d-graph iff it is the intersection graph of connected subgraphs of a subdivision of a star S_d with d rays. We give an FPT algorithm to solve the isomorphism problem for S_d-graphs with the parameter d. This solves an open problem of Chaplick, Töpfer, Voborník and Zeman (2016). In the course of our proof, we also show that the isomorphism problem of S_d-graphs is computationally at least as hard as the isomorphism problem of posets of bounded width.

Cite as

Deniz Ağaoğlu and Petr Hliněný. Isomorphism Problem for S_d-Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{agaoglu_et_al:LIPIcs.MFCS.2020.4,
  author =	{A\u{g}ao\u{g}lu, Deniz and Hlin\v{e}n\'{y}, Petr},
  title =	{{Isomorphism Problem for S\underlined-Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.4},
  URN =		{urn:nbn:de:0030-drops-126754},
  doi =		{10.4230/LIPIcs.MFCS.2020.4},
  annote =	{Keywords: intersection graph, isomorphism testing, interval graph, H-graph}
}
Document
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Authors: Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most k. We call this the Dyck_{k,n} problem. We prove a lower bound of Ω(c^k √n), showing that the complexity of this problem increases exponentially in k. Here n is the length of the word. When k is a constant, this is interesting as a representative example of star-free languages for which a surprising Õ(√n) query quantum algorithm was recently constructed by Aaronson et al. [Scott Aaronson et al., 2018]. Their proof does not give rise to a general algorithm. When k is not a constant, Dyck_{k,n} is not context-free. We give an algorithm with O(√n(log n)^{0.5k}) quantum queries for Dyck_{k,n} for all k. This is better than the trival upper bound n for k = o({log(n)}/{log log n}). Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of Ω(n^{1.5-ε}) for the directed 2D grid and Ω(n^{2-ε}) for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.

Cite as

Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs. Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.MFCS.2020.8,
  author =	{Ambainis, Andris and Balodis, Kaspars and Iraids, J\={a}nis and Khadiev, Kamil and K\c{l}evickis, Vladislavs and Pr\={u}sis, Kri\v{s}j\={a}nis and Shen, Yixin and Smotrovs, Juris and Vihrovs, Jevg\={e}nijs},
  title =	{{Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.8},
  URN =		{urn:nbn:de:0030-drops-126774},
  doi =		{10.4230/LIPIcs.MFCS.2020.8},
  annote =	{Keywords: Quantum query complexity, Quantum algorithms, Dyck language, Grid path}
}
Document
A Special Case of Rational Identity Testing and the Brešar-Klep Theorem

Authors: V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
We explore a special case of rational identity testing and algorithmic versions of two theorems on noncommutative polynomials, namely, Amitsur's theorem [S.A Amitsur, 1966] and the Brešar-Klep theorem [Brešar and Klep, 2008] when the input polynomial is given by an algebraic branching program (ABP). Let f be a degree-d n-variate noncommutative polynomial in the free ring Q<x_1,x_2,...,x_n> over rationals. 1) We consider the following special case of rational identity testing: Given a noncommutative ABP as white-box, whose edge labels are linear forms or inverses of linear forms, we show a deterministic polynomial-time algorithm to decide if the rational function computed by it is equivalent to zero in the free skew field Q<(X)>. Given black-box access to the ABP, we give a deterministic quasi-polynomial time algorithm for this problem. 2) Amitsur's theorem implies that if a noncommutative polynomial f is nonzero on k x k matrices then, in fact, f(M_1,M_2,...,M_n) is invertible for some matrix tuple (M_1,M_2,...,M_n) in (M_k(ℚ))^n. While a randomized polynomial time algorithm to find such (M_1,M_2,...,M_n) given black-box access to f is simple, we obtain a deterministic s^{O(log d)} time algorithm for the problem with black-box access to f, where s is the minimum ABP size for f and d is the degree of f. 3) The Brešar-Klep Theorem states that the span of the range of any noncommutative polynomial f on k x k matrices over Q is one of the following: zero, scalar multiples of I_k, trace-zero matrices in M_k(Q), or all of M_k(Q). We obtain a deterministic polynomial-time algorithm to decide which case occurs, given white-box access to an ABP for f. We also give a deterministic s^{O(log d)} time algorithm given black-box access to an ABP of size s for f. Our algorithms work when k >= d. Our techniques are based on some automata theory combined with known techniques for noncommutative ABP identity testing [Ran Raz and Amir Shpilka, 2005; Michael A. Forbes and Amir Shpilka, 2013].

Cite as

V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. A Special Case of Rational Identity Testing and the Brešar-Klep Theorem. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.MFCS.2020.10,
  author =	{Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha},
  title =	{{A Special Case of Rational Identity Testing and the Bre\v{s}ar-Klep Theorem}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.10},
  URN =		{urn:nbn:de:0030-drops-126807},
  doi =		{10.4230/LIPIcs.MFCS.2020.10},
  annote =	{Keywords: Rational identity testing, ABP with inverses, Bre\v{s}ar-Klep Theorem, Invertible image, Amitsur’s theorem}
}
Document
Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming

Authors: Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
Semidefinite programming (SDP) is a central topic in mathematical optimization with extensive studies on its efficient solvers. In this paper, we present a proof-of-principle sublinear-time algorithm for solving SDPs with low-rank constraints; specifically, given an SDP with m constraint matrices, each of dimension n and rank r, our algorithm can compute any entry and efficient descriptions of the spectral decomposition of the solution matrix. The algorithm runs in time O(m⋅poly(log n,r,1/ε)) given access to a sampling-based low-overhead data structure for the constraint matrices, where ε is the precision of the solution. In addition, we apply our algorithm to a quantum state learning task as an application. Technically, our approach aligns with 1) SDP solvers based on the matrix multiplicative weight (MMW) framework by Arora and Kale [TOC '12]; 2) sampling-based dequantizing framework pioneered by Tang [STOC '19]. In order to compute the matrix exponential required in the MMW framework, we introduce two new techniques that may be of independent interest: - Weighted sampling: assuming sampling access to each individual constraint matrix A₁,…,A_τ, we propose a procedure that gives a good approximation of A = A₁+⋯+A_τ. - Symmetric approximation: we propose a sampling procedure that gives the spectral decomposition of a low-rank Hermitian matrix A. To the best of our knowledge, this is the first sampling-based algorithm for spectral decomposition, as previous works only give singular values and vectors.

Cite as

Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.MFCS.2020.23,
  author =	{Chia, Nai-Hui and Li, Tongyang and Lin, Han-Hsuan and Wang, Chunhao},
  title =	{{Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.23},
  URN =		{urn:nbn:de:0030-drops-126919},
  doi =		{10.4230/LIPIcs.MFCS.2020.23},
  annote =	{Keywords: Spectral decomposition, Semi-definite programming, Quantum-inspired algorithm, Sublinear algorithm}
}
Document
Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs

Authors: Alessio Conte, Pierluigi Crescenzi, Andrea Marino, and Giulia Punzi

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
Temporal graphs are graphs in which arcs have temporal labels, specifying at which time they can be traversed. Motivated by recent results concerning the reliability analysis of a temporal graph through the enumeration of minimal cutsets in the corresponding line graph, in this paper we attack the problem of enumerating minimal s-d separators in s-d directed acyclic graphs (in short, s-d DAGs), also known as 2-terminal DAGs or s-t digraphs. Our main result is an algorithm for enumerating all the minimal s-d separators in a DAG with O(nm) delay, where n and m are respectively the number of nodes and arcs, and the delay is the time between the output of two consecutive solutions. To this aim, we give a characterization of the minimal s-d separators in a DAG through vertex cuts of an expanded version of the DAG itself. As a consequence of our main result, we provide an algorithm for enumerating all the minimal s-d cutsets in a temporal graph with delay O(m³), where m is the number of temporal arcs.

Cite as

Alessio Conte, Pierluigi Crescenzi, Andrea Marino, and Giulia Punzi. Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{conte_et_al:LIPIcs.MFCS.2020.25,
  author =	{Conte, Alessio and Crescenzi, Pierluigi and Marino, Andrea and Punzi, Giulia},
  title =	{{Enumeration of s-d Separators in DAGs with Application to Reliability Analysis in Temporal Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.25},
  URN =		{urn:nbn:de:0030-drops-126932},
  doi =		{10.4230/LIPIcs.MFCS.2020.25},
  annote =	{Keywords: minimal cutset, temporal graph, minimal separator, directed acyclic graph}
}
Document
Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes

Authors: Palash Dey, Jaikumar Radhakrishnan, and Santhoshini Velusamy

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
We consider the bit-probe complexity of the set membership problem: represent an n-element subset S of an m-element universe as a succinct bit vector so that membership queries of the form "Is x ∈ S" can be answered using at most t probes into the bit vector. Let s(m,n,t) (resp. s_N(m,n,t)) denote the minimum number of bits of storage needed when the probes are adaptive (resp. non-adaptive). Lewenstein, Munro, Nicholson, and Raman (ESA 2014) obtain fully-explicit schemes that show that s(m,n,t) = 𝒪((2^t-1)m^{1/(t - min{2⌊log n⌋, n-3/2})}) for n ≥ 2,t ≥ ⌊log n⌋+1 . In this work, we improve this bound when the probes are allowed to be superlinear in n, i.e., when t ≥ Ω(nlog n), n ≥ 2, we design fully-explicit schemes that show that s(m,n,t) = 𝒪((2^t-1)m^{1/(t-{n-1}/{2^{t/(2(n-1))}})}), asymptotically (in the exponent of m) close to the non-explicit upper bound on s(m,n,t) derived by Radhakrishan, Shah, and Shannigrahi (ESA 2010), for constant n. In the non-adaptive setting, it was shown by Garg and Radhakrishnan (STACS 2017) that for a large constant n₀, for n ≥ n₀, s_N(m,n,3) ≥ √{mn}. We improve this result by showing that the same lower bound holds even for storing sets of size 2, i.e., s_N(m,2,3) ≥ Ω(√m).

Cite as

Palash Dey, Jaikumar Radhakrishnan, and Santhoshini Velusamy. Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.MFCS.2020.28,
  author =	{Dey, Palash and Radhakrishnan, Jaikumar and Velusamy, Santhoshini},
  title =	{{Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.28},
  URN =		{urn:nbn:de:0030-drops-126965},
  doi =		{10.4230/LIPIcs.MFCS.2020.28},
  annote =	{Keywords: Set membership, Bit-probe model, Fully-explicit data structures, Adaptive data structures, Error-correcting codes}
}
Document
Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach

Authors: Zeyu Guo

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
Let f̃(X) ∈ ℤ[X] be a degree-n polynomial such that f(X): = f̃(X)od p factorizes into n distinct linear factors over 𝔽_p. We study the problem of deterministically factoring f(X) over 𝔽_p given f̃(X). Under the generalized Riemann hypothesis (GRH), we give an improved deterministic algorithm that computes the complete factorization of f(X) in the case that the Galois group of f̃(X) is (permutation isomorphic to) a linear group G ≤ GL(V) on the set S of roots of f̃(X), where V is a finite-dimensional vector space over a finite field 𝔽 and S is identified with a subset of V. In particular, when |S| = |V|^{Ω(1)}, the algorithm runs in time polynomial in n^{log n/(log log log log n)^{1/3}} and the size of the input, improving Evdokimov’s algorithm. Our result also applies to a general Galois group G when combined with a recent algorithm of the author. To prove our main result, we introduce a family of objects called linear m-schemes and reduce the problem of factoring f(X) to a combinatorial problem about these objects. We then apply techniques from additive combinatorics to obtain an improved bound. Our techniques may be of independent interest.

Cite as

Zeyu Guo. Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{guo:LIPIcs.MFCS.2020.42,
  author =	{Guo, Zeyu},
  title =	{{Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.42},
  URN =		{urn:nbn:de:0030-drops-127082},
  doi =		{10.4230/LIPIcs.MFCS.2020.42},
  annote =	{Keywords: polynomial factoring, permutation group, finite field, algebraic combinatorics, additive combinatorics, derandomization}
}
Document
On LTL Model Checking for Low-Dimensional Discrete Linear Dynamical Systems

Authors: Toghrul Karimov, Joël Ouaknine, and James Worrell

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
Consider a discrete dynamical system given by a square matrix M ∈ ℚ^{d × d} and a starting point s ∈ ℚ^d. The orbit of such a system is the infinite trajectory ⟨ s, Ms, M²s, …⟩. Given a collection T₁, T₂, …, T_m ⊆ ℝ^d of semialgebraic sets, we can associate with each T_i an atomic proposition P_i which evaluates to true at time n if, and only if, M^ns ∈ T_i. This gives rise to the LTL Model-Checking Problem for discrete linear dynamical systems: given such a system (M,s) and an LTL formula over such atomic propositions, determine whether the orbit satisfies the formula. The main contribution of the present paper is to show that the LTL Model-Checking Problem for discrete linear dynamical systems is decidable in dimension 3 or less.

Cite as

Toghrul Karimov, Joël Ouaknine, and James Worrell. On LTL Model Checking for Low-Dimensional Discrete Linear Dynamical Systems. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{karimov_et_al:LIPIcs.MFCS.2020.54,
  author =	{Karimov, Toghrul and Ouaknine, Jo\"{e}l and Worrell, James},
  title =	{{On LTL Model Checking for Low-Dimensional Discrete Linear Dynamical Systems}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.54},
  URN =		{urn:nbn:de:0030-drops-127215},
  doi =		{10.4230/LIPIcs.MFCS.2020.54},
  annote =	{Keywords: Linear dynamical systems, Orbit Problem, LTL model checking}
}
Document
Sensitivity Lower Bounds from Linear Dependencies

Authors: Sophie Laplante, Reza Naserasr, and Anupa Sunny

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least √n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we show how to derive a proof of Huang’s result using only linear dependency and independence of vectors associated with the vertices of the hypercube. Our approach leads to several improvements of the result. In particular we prove that in any induced subgraph of H_n with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least n vertices at distance at most 2. As an application we show that for any Boolean function f, the polynomial degree of f is bounded above by s₀(f) s₁(f), a strictly stronger statement which implies the sensitivity conjecture.

Cite as

Sophie Laplante, Reza Naserasr, and Anupa Sunny. Sensitivity Lower Bounds from Linear Dependencies. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{laplante_et_al:LIPIcs.MFCS.2020.62,
  author =	{Laplante, Sophie and Naserasr, Reza and Sunny, Anupa},
  title =	{{Sensitivity Lower Bounds from Linear Dependencies}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.62},
  URN =		{urn:nbn:de:0030-drops-127320},
  doi =		{10.4230/LIPIcs.MFCS.2020.62},
  annote =	{Keywords: Boolean Functions, Polynomial Degree, Sensitivity}
}
Document
A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps

Authors: Raul Lopes and Ignasi Sau

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
In the Directed Disjoint Paths problem, we are given a digraph D and a set of requests {(s₁, t₁), …, (s_k, t_k)}, and the task is to find a collection of pairwise vertex-disjoint paths {P₁, …, P_k} such that each P_i is a path from s_i to t_i in D. This problem is NP-complete for fixed k = 2 and W[1]-hard with parameter k in DAGs. A few positive results are known under restrictions on the input digraph, such as being planar or having bounded directed tree-width, or under relaxations of the problem, such as allowing for vertex congestion. Good news are scarce, however, for general digraphs. In this article we propose a novel global congestion metric for the problem: we only require the paths to be "disjoint enough", in the sense that they must behave properly not in the whole graph, but in an unspecified large part of it. Namely, in the Disjoint Enough Directed Paths problem, given an n-vertex digraph D, a set of k requests, and non-negative integers d and s, the task is to find a collection of paths connecting the requests such that at least d vertices of D occur in at most s paths of the collection. We study the parameterized complexity of this problem for a number of choices of the parameter, including the directed tree-width of D. Among other results, we show that the problem is W[1]-hard in DAGs with parameter d and, on the positive side, we give an algorithm in time 𝒪(n^{d+2} ⋅ k^{d⋅ s}) and a kernel of size d ⋅ 2^{k-s}⋅ binom(k,s) + 2k in general digraphs. This latter result has consequences for the Steiner Network problem: we show that it is FPT parameterized by the number k of terminals and d, where d = n - c and c is the size of the solution.

Cite as

Raul Lopes and Ignasi Sau. A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{lopes_et_al:LIPIcs.MFCS.2020.68,
  author =	{Lopes, Raul and Sau, Ignasi},
  title =	{{A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{68:1--68:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.68},
  URN =		{urn:nbn:de:0030-drops-127378},
  doi =		{10.4230/LIPIcs.MFCS.2020.68},
  annote =	{Keywords: Parameterized complexity, directed disjoint paths, congestion, dual parameterization, kernelization, directed tree-width}
}
Document
Quick Separation in Chordal and Split Graphs

Authors: Pranabendu Misra, Fahad Panolan, Ashutosh Rai, Saket Saurabh, and Roohani Sharma

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
In this paper we study two classical cut problems, namely Multicut and Multiway Cut on chordal graphs and split graphs. In the Multicut problem, the input is a graph G, a collection of 𝓁 vertex pairs (s_i, t_i), i ∈ [𝓁], and a positive integer k and the goal is to decide if there exists a vertex subset S ⊆ V(G)⧵ {s_i,t_i : i ∈ [𝓁]} of size at most k such that for every vertex pair (s_i,t_i), s_i and t_i are in two different connected components of G-S. In Unrestricted Multicut, the solution S can possibly pick the vertices in the vertex pairs {(s_i,t_i): i ∈ [𝓁]}. An important special case of the Multicut problem is the Multiway Cut problem, where instead of vertex pairs, we are given a set T of terminal vertices, and the goal is to separate every pair of distinct vertices in T× T. The fixed parameter tractability (FPT) of these problems was a long-standing open problem and has been resolved fairly recently. Multicut and Multiway Cut now admit algorithms with running times 2^{{𝒪}(k³)}n^{{𝒪}(1)} and 2^k n^{{𝒪}(1)}, respectively. However, the kernelization complexity of both these problems is not fully resolved: while Multicut cannot admit a polynomial kernel under reasonable complexity assumptions, it is a well known open problem to construct a polynomial kernel for Multiway Cut. Towards designing faster FPT algorithms and polynomial kernels for the above mentioned problems, we study them on chordal and split graphs. In particular we obtain the following results. 1) Multicut on chordal graphs admits a polynomial kernel with {𝒪}(k³ 𝓁⁷) vertices. Multiway Cut on chordal graphs admits a polynomial kernel with {𝒪}(k^{13}) vertices. 2) Multicut on chordal graphs can be solved in time min {𝒪(2^{k} ⋅ (k³+𝓁) ⋅ (n+m)), 2^{𝒪(𝓁 log k)} ⋅ (n+m) + 𝓁 (n+m)}. Hence Multicut on chordal graphs parameterized by the number of terminals is in XP. 3) Multicut on split graphs can be solved in time min {𝒪(1.2738^k + kn+𝓁(n+m), 𝒪(2^{𝓁} ⋅ 𝓁 ⋅ (n+m))}. Unrestricted Multicut on split graphs can be solved in time 𝒪(4^{𝓁}⋅ 𝓁 ⋅ (n+m)).

Cite as

Pranabendu Misra, Fahad Panolan, Ashutosh Rai, Saket Saurabh, and Roohani Sharma. Quick Separation in Chordal and Split Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.MFCS.2020.70,
  author =	{Misra, Pranabendu and Panolan, Fahad and Rai, Ashutosh and Saurabh, Saket and Sharma, Roohani},
  title =	{{Quick Separation in Chordal and Split Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.70},
  URN =		{urn:nbn:de:0030-drops-127391},
  doi =		{10.4230/LIPIcs.MFCS.2020.70},
  annote =	{Keywords: chordal graphs, multicut, multiway cut, FPT, kernel}
}
Document
Palindromic k-Factorization in Pure Linear Time

Authors: Mikhail Rubinchik and Arseny M. Shur

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
Given a string s of length n over a general alphabet and an integer k, the problem is to decide whether s is a concatenation of k nonempty palindromes. Two previously known solutions for this problem work in time O(kn) and O(nlog n) respectively. Here we settle the complexity of this problem in the word-RAM model, presenting an O(n)-time online deciding algorithm. The algorithm simultaneously finds the minimum odd number of factors and the minimum even number of factors in a factorization of a string into nonempty palindromes. We also demonstrate how to get an explicit factorization of s into k palindromes with an O(n)-time offline postprocessing.

Cite as

Mikhail Rubinchik and Arseny M. Shur. Palindromic k-Factorization in Pure Linear Time. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 81:1-81:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{rubinchik_et_al:LIPIcs.MFCS.2020.81,
  author =	{Rubinchik, Mikhail and Shur, Arseny M.},
  title =	{{Palindromic k-Factorization in Pure Linear Time}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{81:1--81:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.81},
  URN =		{urn:nbn:de:0030-drops-127508},
  doi =		{10.4230/LIPIcs.MFCS.2020.81},
  annote =	{Keywords: stringology, palindrome, palindromic factorization, online algorithm}
}
Document
Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs

Authors: Ignasi Sau and Uéverton dos Santos Souza

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
For a fixed graph H, the H-IS-Deletion problem asks, given a graph G, for the minimum size of a set S ⊆ V(G) such that G⧵ S does not contain H as an induced subgraph. Motivated by previous work about hitting (topological) minors and subgraphs on bounded treewidth graphs, we are interested in determining, for a fixed graph H, the smallest function f_H(t) such that H-IS-Deletion can be solved in time f_H(t) ⋅ n^{𝒪(1)} assuming the Exponential Time Hypothesis (ETH), where t and n denote the treewidth and the number of vertices of the input graph, respectively. We show that f_H(t) = 2^{𝒪(t^{h-2})} for every graph H on h ≥ 3 vertices, and that f_H(t) = 2^{𝒪(t)} if H is a clique or an independent set. We present a number of lower bounds by generalizing a reduction of Cygan et al. [MFCS 2014] for the subgraph version. In particular, we show that when H deviates slightly from a clique, the function f_H(t) suffers a sharp jump: if H is obtained from a clique of size h by removing one edge, then f_H(t) = 2^{Θ(t^{h-2})}. We also show that f_H(t) = 2^{Ω(t^{h})} when H = K_{h,h}, and this reduction answers an open question of Mi. Pilipczuk [MFCS 2011] about the function f_{C₄}(t) for the subgraph version. Motivated by Cygan et al. [MFCS 2014], we also consider the colorful variant of the problem, where each vertex of G is colored with some color from V(H) and we require to hit only induced copies of H with matching colors. In this case, we determine, under the ETH, the function f_H(t) for every connected graph H on h vertices: if h ≤ 2 the problem can be solved in polynomial time; if h ≥ 3, f_H(t) = 2^{Θ(t)} if H is a clique, and f_H(t) = 2^{Θ(t^{h-2})} otherwise.

Cite as

Ignasi Sau and Uéverton dos Santos Souza. Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{sau_et_al:LIPIcs.MFCS.2020.82,
  author =	{Sau, Ignasi and Souza, U\'{e}verton dos Santos},
  title =	{{Hitting Forbidden Induced Subgraphs on Bounded Treewidth Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{82:1--82:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.82},
  URN =		{urn:nbn:de:0030-drops-127511},
  doi =		{10.4230/LIPIcs.MFCS.2020.82},
  annote =	{Keywords: parameterized complexity, induced subgraphs, treewidth, hitting subgraphs, dynamic programming, lower bound, Exponential Time Hypothesis}
}
Document
An Experience of Game-Based Learning in Web Applications Development Courses

Authors: Míriam Antón-Rodríguez, María Ángeles Pérez-Juárez, Francisco Javier Díaz-Pernas, David González-Ortega, Mario Martínez-Zarzuela, and Javier Manuel Aguiar-Pérez

Published in: OASIcs, Volume 81, First International Computer Programming Education Conference (ICPEC 2020)


Abstract
Preparing graduates for working in the software engineering industry is challenging and requires effective learning frameworks and methodologies. More specifically, the challenge of teaching programming languages and paradigms is a very complex task that needs innovative educational tools. This paper presents a game-based educational tool named eLiza, developed and used to support the teaching and learning of programming languages and paradigms related to the development of web applications. eLiza was initially developed as a Moodle-based web application because Moodle is the educational eLearning platform used at the University of Valladolid, but as the use of mobile devices is constantly increasing, Android and iOS versions were created later in order to facilitate the access of the students to the games. This paper describes the main elements and the mechanics in playing eLiza. And it also describes an experience of its use in two engineering courses related to web programming applications development, offered to students in two different engineering study programs at the University of Valladolid, during the academic years 2017-2018 and 2018-2019. The great majority of the students, more than 75%, considered that the use of the eLiza game-based educational tool was positive to improve the teaching and learning process of the topics covered by the courses.

Cite as

Míriam Antón-Rodríguez, María Ángeles Pérez-Juárez, Francisco Javier Díaz-Pernas, David González-Ortega, Mario Martínez-Zarzuela, and Javier Manuel Aguiar-Pérez. An Experience of Game-Based Learning in Web Applications Development Courses. In First International Computer Programming Education Conference (ICPEC 2020). Open Access Series in Informatics (OASIcs), Volume 81, pp. 3:1-3:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{antonrodriguez_et_al:OASIcs.ICPEC.2020.3,
  author =	{Ant\'{o}n-Rodr{\'\i}guez, M{\'\i}riam and P\'{e}rez-Ju\'{a}rez, Mar{\'\i}a \'{A}ngeles and D{\'\i}az-Pernas, Francisco Javier and Gonz\'{a}lez-Ortega, David and Mart{\'\i}nez-Zarzuela, Mario and Aguiar-P\'{e}rez, Javier Manuel},
  title =	{{An Experience of Game-Based Learning in Web Applications Development Courses}},
  booktitle =	{First International Computer Programming Education Conference (ICPEC 2020)},
  pages =	{3:1--3:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-153-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{81},
  editor =	{Queir\'{o}s, Ricardo and Portela, Filipe and Pinto, M\'{a}rio and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2020.3},
  URN =		{urn:nbn:de:0030-drops-122901},
  doi =		{10.4230/OASIcs.ICPEC.2020.3},
  annote =	{Keywords: eLearning, mLearning, Game-based Learning, Programming Languages, Web Applications Development}
}
Document
Patient-Specific Mappings between Myocardial and Coronary Anatomy

Authors: Maurice Termeer, Javier Oliván Bescós, Marcel Breeuwer, Anna Vilanova, and Frans Gerritsen

Published in: Dagstuhl Follow-Ups, Volume 1, Scientific Visualization: Advanced Concepts (2010)


Abstract
The segmentation of the myocardium based on the 17-segment model as recommended by the American Heart Association is widely used in medical practice. The patient-specific coronary anatomy does not play a role in this model. Due to large variations in coronary anatomy among patients, this can result in an inaccurate mapping between myocardial segments and coronary arteries. We present two approaches to include the patient-specific coronary anatomy in this mapping. The first approach adapts the 17-segment model to fit the patient. The second approach generates a less constrained mapping that does not necessarily conform to this model. Both approaches are based on a Voronoi diagram computation of the primary coronary arteries using geodesic distances along the epicardium in three-dimensional space. We demonstrate both our approaches with several patients and show how our first approach can also be used to fit volume data to the 17-segment model. Our technique gives detailed insight into the coronary anatomy in a single diagram. Based on the feedback provided by clinical experts we conclude that it has the potential to provide a more accurate relation between deficiencies in the myocardium and the supplying coronary arteries.

Cite as

Maurice Termeer, Javier Oliván Bescós, Marcel Breeuwer, Anna Vilanova, and Frans Gerritsen. Patient-Specific Mappings between Myocardial and Coronary Anatomy. In Scientific Visualization: Advanced Concepts. Dagstuhl Follow-Ups, Volume 1, pp. 196-209, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InCollection{termeer_et_al:DFU.SciViz.2010.196,
  author =	{Termeer, Maurice and Besc\'{o}s, Javier Oliv\'{a}n and Breeuwer, Marcel and Vilanova, Anna and Gerritsen, Frans},
  title =	{{Patient-Specific Mappings between Myocardial and Coronary Anatomy}},
  booktitle =	{Scientific Visualization: Advanced Concepts},
  pages =	{196--209},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-19-4},
  ISSN =	{1868-8977},
  year =	{2010},
  volume =	{1},
  editor =	{Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.SciViz.2010.196},
  URN =		{urn:nbn:de:0030-drops-27053},
  doi =		{10.4230/DFU.SciViz.2010.196},
  annote =	{Keywords: Voronoi Diagram, Segmentation, Myocardium}
}
  • Refine by Author
  • 2 Sau, Ignasi
  • 1 Aguiar-Pérez, Javier Manuel
  • 1 Ambainis, Andris
  • 1 Antón-Rodríguez, Míriam
  • 1 Arvind, V.
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Mathematics of computing → Combinatorial algorithms
  • Show More...

  • Refine by Keyword
  • 1 ABP with inverses
  • 1 Adaptive data structures
  • 1 Amitsur’s theorem
  • 1 Bit-probe model
  • 1 Boolean Functions
  • Show More...

  • Refine by Type
  • 15 document

  • Refine by Publication Year
  • 14 2020
  • 1 2010

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