122 Search Results for "Marion, Jean-Yves"

Volume

LIPIcs, Volume 5

27th International Symposium on Theoretical Aspects of Computer Science

STACS 2010, March 4-6, 2010, Nancy, France

Editors: Jean-Yves Marion and Thomas Schwentick

Volume

LIPIcs, Volume 3

26th International Symposium on Theoretical Aspects of Computer Science

STACS 2009, February 26-28, 2009, Freiburg, Germany

Editors: Susanne Albers and Jean-Yves Marion

Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2009
LIPIcs, Volume 3, STACS'09, Complete Volume

Authors: Susanne Albers and Jean-Yves Marion

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
LIPIcs, Volume 3, STACS'09, Complete Volume
Cite as

26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{albers_et_al:LIPIcs.STACS.2009,
  title =	{{LIPIcs, Volume 3, STACS'09, Complete Volume}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009},
  URN =		{urn:nbn:de:0030-drops-40975},
  doi =		{10.4230/LIPIcs.STACS.2009},
  annote =	{Keywords: LIPIcs, Volume 3, STACS'09, Complete Volume}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2010
LIPIcs, Volume 5, STACS'10, Complete Volume

Authors: Jean-Yves Marion and Thomas Schwentick

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
LIPIcs, Volume 5, STACS'10, Complete Volume
Cite as

27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Proceedings{marion_et_al:LIPIcs.STACS.2010,
  title =	{{LIPIcs, Volume 5, STACS'10, Complete Volume}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010},
  URN =		{urn:nbn:de:0030-drops-40996},
  doi =		{10.4230/LIPIcs.STACS.2010},
  annote =	{Keywords: LIPIcs, Volume 5, STACS'10, Complete Volume}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2505
Table of Contents -- 27th International Symposium on Theoretical Aspects of Computer Science

Authors: Jean-Yves Marion and Thomas Schwentick

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Table of contents
Cite as

Jean-Yves Marion and Thomas Schwentick. Table of Contents -- 27th International Symposium on Theoretical Aspects of Computer Science. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 7-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{marion_et_al:LIPIcs.STACS.2010.2505,
  author =	{Marion, Jean-Yves and Schwentick, Thomas},
  title =	{{Table of Contents -- 27th International Symposium on Theoretical Aspects of Computer Science}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{7--10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2505},
  URN =		{urn:nbn:de:0030-drops-25059},
  doi =		{10.4230/LIPIcs.STACS.2010.2505},
  annote =	{Keywords: Table of contents}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2010.2439
Foreword -- 27th International Symposium on Theoretical Aspects of Computer Science

Authors: Jean-Yves Marion and Thomas Schwentick

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
The STACS conference of March 4-6, 2010, held in Nancy, is the 27th in this series. The STACS 2010 call for papers led to over 238 submissions from 40 countries. Each paper was assigned to three program committee members. The committee selected 54 papers during a two-week electronic meeting held in November.
Cite as

27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. i-vi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{marion_et_al:LIPIcs.STACS.2010.2439,
  author =	{Marion, Jean-Yves and Schwentick, Thomas},
  title =	{{Foreword -- 27th International Symposium on Theoretical Aspects of Computer Science}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{i--vi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2439},
  URN =		{urn:nbn:de:0030-drops-24393},
  doi =		{10.4230/LIPIcs.STACS.2010.2439},
  annote =	{Keywords: Foreword}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2440
Beyond omega-Regular Languages

Authors: Mikolaj Bojanczyk

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
The paper presents some automata and logics on $\omega$-words, which capture all $\omega$-regular languages, and yet still have good closure and decidability properties.
Cite as

Mikolaj Bojanczyk. Beyond omega-Regular Languages. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 11-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bojanczyk:LIPIcs.STACS.2010.2440,
  author =	{Bojanczyk, Mikolaj},
  title =	{{Beyond omega-Regular Languages}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{11--16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2440},
  URN =		{urn:nbn:de:0030-drops-24409},
  doi =		{10.4230/LIPIcs.STACS.2010.2440},
  annote =	{Keywords: Automata, monadic second-order logic}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2495
Reflections on Multivariate Algorithmics and Problem Parameterization

Authors: Rolf Niedermeier

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Research on parameterized algorithmics for NP-hard problems has steadily grown over the last years. We survey and discuss how parameterized complexity analysis naturally develops into the field of multivariate algorithmics. Correspondingly, we describe how to perform a systematic investigation and exploitation of the ``parameter space'' of computationally hard problems.
Cite as

Rolf Niedermeier. Reflections on Multivariate Algorithmics and Problem Parameterization. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 17-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{niedermeier:LIPIcs.STACS.2010.2495,
  author =	{Niedermeier, Rolf},
  title =	{{Reflections on Multivariate Algorithmics and Problem Parameterization}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{17--32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2495},
  URN =		{urn:nbn:de:0030-drops-24952},
  doi =		{10.4230/LIPIcs.STACS.2010.2495},
  annote =	{Keywords: Multivariate algorithmics, problem parameterization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2441
Mathematics, Cryptology, Security

Authors: Jacques Stern

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
In this talk, I will review some of the work performed by the research community in cryptology and security since the invention of public key cryptography by Diffie and Hellman in 1976. This community has developped many challenging lines of research. I will only focus on some of these, and moreover I will adopt an extremely specific perspective: for each chosen example, I will try to trace the original mathematics that underly the methods in use. Over the years, maybe due to my original training as a mathematician, I have come to consider that linking recent advances and challenges in cryptology and security to the work of past mathematicians is indeed fascinating. The range of examples will span both theory and practice: I will show that the celebrated RSA algorithm is intimately connected to mathematics that go back to the middle of the XVIIIth century. I will also cover alternatives to RSA, the method of "provable security", as well as some aspects of the security of electronic payments.
Cite as

Jacques Stern. Mathematics, Cryptology, Security. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 33-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{stern:LIPIcs.STACS.2010.2441,
  author =	{Stern, Jacques},
  title =	{{Mathematics, Cryptology, Security}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{33--34},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2441},
  URN =		{urn:nbn:de:0030-drops-24416},
  doi =		{10.4230/LIPIcs.STACS.2010.2441},
  annote =	{Keywords: Mathematics, Cryptology, Security}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2442
Large-Girth Roots of Graphs

Authors: Anna Adamaszek and Michal Adamaszek

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We study the problem of recognizing graph powers and computing roots of graphs. We provide a polynomial time recognition algorithm for $r$-th powers of graphs of girth at least $2r+3$, thus improving a bound conjectured by Farzad et al. (STACS 2009). Our algorithm also finds all $r$-th roots of a given graph that have girth at least $2r+3$ and no degree one vertices, which is a step towards a recent conjecture of Levenshtein that such root should be unique. On the negative side, we prove that recognition becomes an NP-complete problem when the bound on girth is about twice smaller. Similar results have so far only been attempted for $r=2,3$.
Cite as

Anna Adamaszek and Michal Adamaszek. Large-Girth Roots of Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 35-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{adamaszek_et_al:LIPIcs.STACS.2010.2442,
  author =	{Adamaszek, Anna and Adamaszek, Michal},
  title =	{{Large-Girth Roots of Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{35--46},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2442},
  URN =		{urn:nbn:de:0030-drops-24429},
  doi =		{10.4230/LIPIcs.STACS.2010.2442},
  annote =	{Keywords: Graph roots, Graph powers, NP-completeness, Recognition algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2443
The Tropical Double Description Method

Authors: Xavier Allamigeon, Stéphane Gaubert, and Éric Goubault

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We develop a tropical analogue of the classical double description method allowing one to compute an internal representation (in terms of vertices) of a polyhedron defined externally (by inequalities). The heart of the tropical algorithm is a characterization of the extreme points of a polyhedron in terms of a system of constraints which define it. We show that checking the extremality of a point reduces to checking whether there is only one minimal strongly connected component in an hypergraph. The latter problem can be solved in almost linear time, which allows us to eliminate quickly redundant generators. We report extensive tests (including benchmarks from an application to static analysis) showing that the method outperforms experimentally the previous ones by orders of magnitude. The present tools also lead to worst case bounds which improve the ones provided by previous methods.
Cite as

Xavier Allamigeon, Stéphane Gaubert, and Éric Goubault. The Tropical Double Description Method. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 47-58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{allamigeon_et_al:LIPIcs.STACS.2010.2443,
  author =	{Allamigeon, Xavier and Gaubert, St\'{e}phane and Goubault, \'{E}ric},
  title =	{{The Tropical Double Description Method}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{47--58},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2443},
  URN =		{urn:nbn:de:0030-drops-24435},
  doi =		{10.4230/LIPIcs.STACS.2010.2443},
  annote =	{Keywords: Convexity in tropical algebra, algorithmics and combinatorics of tropical polyhedra, computational geometry, discrete event systems, static analysis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2444
The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

Authors: Vikraman Arvind and Srikanth Srinivasan

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Using $\varepsilon$-bias spaces over $\F_2$, we show that the Remote Point Problem (RPP), introduced by Alon et al \cite{APY09}, has an $\NC^2$ algorithm (achieving the same parameters as \cite{APY09}). We study a generalization of the Remote Point Problem to groups: we replace $\F_2^n$ by $\mcG^n$ for an arbitrary fixed group $\mcG$. When $\mcG$ is Abelian we give an $\NC^2$ algorithm for RPP, again using $\varepsilon$-bias spaces. For nonabelian $\mcG$, we give a deterministic polynomial-time algorithm for RPP. We also show the connection to construction of expanding generator sets for the group $\mcG^n$. All our algorithms for the RPP achieve essentially the same parameters as \cite{APY09}.
Cite as

Vikraman Arvind and Srikanth Srinivasan. The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 59-70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.STACS.2010.2444,
  author =	{Arvind, Vikraman and Srinivasan, Srikanth},
  title =	{{The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{59--70},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2444},
  URN =		{urn:nbn:de:0030-drops-24449},
  doi =		{10.4230/LIPIcs.STACS.2010.2444},
  annote =	{Keywords: Small Bias Spaces, Expander Graphs, Cayley Graphs, Remote Point Problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2445
Evasiveness and the Distribution of Prime Numbers

Authors: László Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
A Boolean function on $N$ variables is called \emph{evasive} if its decision-tree complexity is $N$. A sequence $B_n$ of Boolean functions is \emph{eventually evasive} if $B_n$ is evasive for all sufficiently large $n$. We confirm the eventual evasiveness of several classes of monotone graph properties under widely accepted number theoretic hypotheses. In particular we show that Chowla's conjecture on Dirichlet primes implies that (a) for any graph $H$, ``forbidden subgraph $H$'' is eventually evasive and (b) all nontrivial monotone properties of graphs with $\le n^{3/2-\epsilon}$ edges are eventually evasive. ($n$ is the number of vertices.) While Chowla's conjecture is not known to follow from the Extended Riemann Hypothesis (ERH, the Riemann Hypothesis for Dirichlet's $L$ functions), we show (b) with the bound $O(n^{5/4-\epsilon})$ under ERH. We also prove unconditional results: (a$'$) for any graph $H$, the query complexity of ``forbidden subgraph $H$'' is $\binom{n}{2} - O(1)$; (b$'$) for some constant $c>0$, all nontrivial monotone properties of graphs with $\le cn\log n+O(1)$ edges are eventually evasive. Even these weaker, unconditional results rely on deep results from number theory such as Vinogradov's theorem on the Goldbach conjecture. Our technical contribution consists in connecting the topological framework of Kahn, Saks, and Sturtevant (1984), as further developed by Chakrabarti, Khot, and Shi (2002), with a deeper analysis of the orbital structure of permutation groups and their connection to the distribution of prime numbers. Our unconditional results include stronger versions and generalizations of some result of Chakrabarti et al.
Cite as

László Babai, Anandam Banerjee, Raghav Kulkarni, and Vipul Naik. Evasiveness and the Distribution of Prime Numbers. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{babai_et_al:LIPIcs.STACS.2010.2445,
  author =	{Babai, L\'{a}szl\'{o} and Banerjee, Anandam and Kulkarni, Raghav and Naik, Vipul},
  title =	{{Evasiveness and the Distribution of Prime Numbers}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{71--82},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2445},
  URN =		{urn:nbn:de:0030-drops-24451},
  doi =		{10.4230/LIPIcs.STACS.2010.2445},
  annote =	{Keywords: Decision tree complexity, evasiveness, graph property, group action, Dirichlet primes, Extended Riemann Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2446
Dynamic Sharing of a Multiple Access Channel

Authors: Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, and Dariusz R. Kowalski

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, $n$ processes perform a concurrent program which occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource in such a way that in any time there is at most one process accessing it. We consider both the classic and a slightly weaker version of mutual exclusion, called $\ep$-mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most $\ep$. We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while $\ep$-mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker $\ep$-exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.
Cite as

Marcin Bienkowski, Marek Klonowski, Miroslaw Korzeniowski, and Dariusz R. Kowalski. Dynamic Sharing of a Multiple Access Channel. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 83-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.STACS.2010.2446,
  author =	{Bienkowski, Marcin and Klonowski, Marek and Korzeniowski, Miroslaw and Kowalski, Dariusz R.},
  title =	{{Dynamic Sharing of a Multiple Access Channel}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{83--94},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2446},
  URN =		{urn:nbn:de:0030-drops-24467},
  doi =		{10.4230/LIPIcs.STACS.2010.2446},
  annote =	{Keywords: Distributed algorithms, multiple access channel, mutual exclusion}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2447
Exact Covers via Determinants

Authors: Andreas Björklund

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Given a $k$-uniform hypergraph on $n$ vertices, partitioned in $k$ equal parts such that every hyperedge includes one vertex from each part, the $k$-Dimensional Matching problem asks whether there is a disjoint collection of the hyperedges which covers all vertices. We show it can be solved by a randomized polynomial space algorithm in $O^*(2^{n(k-2)/k})$ time. The $O^*()$ notation hides factors polynomial in $n$ and $k$. The general Exact Cover by $k$-Sets problem asks the same when the partition constraint is dropped and arbitrary hyperedges of cardinality $k$ are permitted. We show it can be solved by a randomized polynomial space algorithm in $O^*(c_k^n)$ time, where $c_3=1.496, c_4=1.642, c_5=1.721$, and provide a general bound for larger $k$. Both results substantially improve on the previous best algorithms for these problems, especially for small $k$. They follow from the new observation that Lov\'asz' perfect matching detection via determinants (Lov\'asz, 1979) admits an embedding in the recently proposed inclusion--exclusion counting scheme for set covers, \emph{despite} its inability to count the perfect matchings.
Cite as

Andreas Björklund. Exact Covers via Determinants. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 95-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bjorklund:LIPIcs.STACS.2010.2447,
  author =	{Bj\"{o}rklund, Andreas},
  title =	{{Exact Covers via Determinants}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{95--106},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2447},
  URN =		{urn:nbn:de:0030-drops-24474},
  doi =		{10.4230/LIPIcs.STACS.2010.2447},
  annote =	{Keywords: Moderately Exponential Time Algorithms, Exact Set Cover, \$k\$-Dimensional Matching}
}
  • Refine by Author
  • 6 Marion, Jean-Yves
  • 4 Fomin, Fedor V.
  • 4 Schwentick, Thomas
  • 3 de Wolf, Ronald
  • 2 Albers, Susanne
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 9 Computational complexity
  • 4 Logic in computer science
  • 3 Algorithms
  • 3 Approximation algorithms
  • 3 Automata
  • Show More...

  • Refine by Type
  • 120 document
  • 2 volume

  • Refine by Publication Year
  • 60 2010
  • 59 2009
  • 2 2013
  • 1 2008

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact