3 Search Results for "Christiansen, Henning"

Document
DOI: 10.4230/LIPIcs.STACS.2025.7
Faster Edge Coloring by Partition Sieving

Authors: Shyan Akmal and Tomohiro Koana

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
In the Edge Coloring problem, we are given an undirected graph G with n vertices and m edges, and are tasked with finding the smallest positive integer k so that the edges of G can be assigned k colors in such a way that no two edges incident to the same vertex are assigned the same color. Edge Coloring is a classic NP-hard problem, and so significant research has gone into designing fast exponential-time algorithms for solving Edge Coloring and its variants exactly. Prior work showed that Edge Coloring can be solved in 2^mpoly(n) time and polynomial space, and in graphs with average degree d in 2^{(1-ε_d)m}⋅poly(n) time and exponential space, where ε_d = (1/d)^Θ(d³). We present an algorithm that solves Edge Coloring in 2^{m-3n/5}⋅poly(n) time and polynomial space. Our result is the first algorithm for this problem which simultaneously runs in faster than 2^m⋅poly(m) time and uses only polynomial space. In graphs of average degree d, our algorithm runs in 2^{(1-6/(5d))m}⋅poly(n) time, which has far better dependence in d than previous results. We also consider a generalization of Edge Coloring called List Edge Coloring, where each edge e in the input graph comes with a list L_e ⊆ {1, …, k} of colors, and we must determine whether we can assign each edge a color from its list so that no two edges incident to the same vertex receive the same color. We show that this problem can be solved in 2^{(1-6/(5k))m}⋅poly(n) time and polynomial space. The previous best algorithm for List Edge Coloring took 2^m⋅poly(n) time and space. Our algorithms are algebraic, and work by constructing a special polynomial P based off the input graph that contains a multilinear monomial (i.e., a monomial where every variable has degree at most one) if and only if the answer to the List Edge Coloring problem on the input graph is YES. We then solve the problem by detecting multilinear monomials in P. Previous work also employed such monomial detection techniques to solve Edge Coloring. We obtain faster algorithms both by carefully constructing our polynomial P, and by improving the runtimes for certain structured monomial detection problems using a technique we call partition sieving.
Cite as

Shyan Akmal and Tomohiro Koana. Faster Edge Coloring by Partition Sieving. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.STACS.2025.7,
  author =	{Akmal, Shyan and Koana, Tomohiro},
  title =	{{Faster Edge Coloring by Partition Sieving}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.7},
  URN =		{urn:nbn:de:0030-drops-228328},
  doi =		{10.4230/LIPIcs.STACS.2025.7},
  annote =	{Keywords: Coloring, Edge coloring, Chromatic index, Matroid, Pfaffian, Algebraic algorithm}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.47
A Rewriting Theory for Quantum λ-Calculus

Authors: Claudia Faggian, Gaetan Lopez, and Benoît Valiron

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
Quantum lambda calculus has been studied mainly as an idealized programming language - the evaluation essentially corresponds to a deterministic abstract machine. Very little work has been done to develop a rewriting theory for quantum lambda calculus. Recent advances in the theory of probabilistic rewriting give us a way to tackle this task with tools unavailable a decade ago. Our primary focus are standardization and normalization results.
Cite as

Claudia Faggian, Gaetan Lopez, and Benoît Valiron. A Rewriting Theory for Quantum λ-Calculus. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{faggian_et_al:LIPIcs.CSL.2025.47,
  author =	{Faggian, Claudia and Lopez, Gaetan and Valiron, Beno\^{i}t},
  title =	{{A Rewriting Theory for Quantum \lambda-Calculus}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{47:1--47:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.47},
  URN =		{urn:nbn:de:0030-drops-228046},
  doi =		{10.4230/LIPIcs.CSL.2025.47},
  annote =	{Keywords: quantum lambda-calculus, probabilistic rewriting, operational semantics, asymptotic normalization, principles of quantum programming languages}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2011.220
Bayesian Annotation Networks for Complex Sequence Analysis

Authors: Henning Christiansen, Christian Theil Have, Ole Torp Lassen, and Matthieu Petit

Published in: LIPIcs, Volume 11, Technical Communications of the 27th International Conference on Logic Programming (ICLP'11) (2011)

Abstract
Probabilistic models that associate annotations to sequential data are widely used in computational biology and a range of other applications. Models integrating with logic programs provide, furthermore, for sophistication and generality, at the cost of potentially very high computational complexity. A methodology is proposed for modularization of such models into sub-models, each representing a particular interpretation of the input data to be analysed. Their composition forms, in a natural way, a Bayesian network, and we show how standard methods for prediction and training can be adapted for such composite models in an iterative way, obtaining reasonable complexity results. Our methodology can be implemented using the probabilistic-logic PRISM system, developed by Sato et al, in a way that allows for practical applications.
Cite as

Henning Christiansen, Christian Theil Have, Ole Torp Lassen, and Matthieu Petit. Bayesian Annotation Networks for Complex Sequence Analysis. In Technical Communications of the 27th International Conference on Logic Programming (ICLP'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 11, pp. 220-230, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{christiansen_et_al:LIPIcs.ICLP.2011.220,
  author =	{Christiansen, Henning and Theil Have, Christian and Torp Lassen, Ole and Petit, Matthieu},
  title =	{{Bayesian Annotation Networks for Complex Sequence Analysis}},
  booktitle =	{Technical Communications of the 27th International Conference on Logic Programming (ICLP'11)},
  pages =	{220--230},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-31-6},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{11},
  editor =	{Gallagher, John P. and Gelfond, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2011.220},
  URN =		{urn:nbn:de:0030-drops-31649},
  doi =		{10.4230/LIPIcs.ICLP.2011.220},
  annote =	{Keywords: Probabilistic Logic Bayesian Sequence Analysis}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2011

  • Refine by Author
  • 1 Akmal, Shyan
  • 1 Christiansen, Henning
  • 1 Faggian, Claudia
  • 1 Koana, Tomohiro
  • 1 Lopez, Gaetan
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Equational logic and rewriting
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Linear logic
  • 1 Theory of computation → Operational semantics
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 1 Algebraic algorithm
  • 1 Chromatic index
  • 1 Coloring
  • 1 Edge coloring
  • 1 Matroid
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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