6 Search Results for "Taylor, David"

Document
DOI: 10.4230/LIPIcs.MFCS.2023.66
On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras

Authors: Peter Mayr

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
For a fixed finite algebra 𝐀, we consider the decision problem SysTerm(𝐀): does a given system of term equations have a solution in 𝐀? This is equivalent to a constraint satisfaction problem (CSP) for a relational structure whose relations are the graphs of the basic operations of 𝐀. From the complexity dichotomy for CSP over fixed finite templates due to Bulatov [Bulatov, 2017] and Zhuk [Zhuk, 2017], it follows that SysTerm(𝐀) for a finite algebra 𝐀 is in P if 𝐀 has a not necessarily idempotent Taylor polymorphism and is NP-complete otherwise. More explicitly, we show that for a finite algebra 𝐀 in a congruence modular variety (e.g. for a quasigroup), SysTerm(𝐀) is in P if the core of 𝐀 is abelian and is NP-complete otherwise. Given 𝐀 by the graphs of its basic operations, we show that this condition for tractability can be decided in quasi-polynomial time.
Cite as

Peter Mayr. On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mayr:LIPIcs.MFCS.2023.66,
  author =	{Mayr, Peter},
  title =	{{On the Complexity Dichotomy for the Satisfiability of Systems of Term Equations over Finite Algebras}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{66:1--66:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.66},
  URN =		{urn:nbn:de:0030-drops-186007},
  doi =		{10.4230/LIPIcs.MFCS.2023.66},
  annote =	{Keywords: systems of equations, general algebras, constraint satisfaction}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.108
Polynomial-Time Approximation of Zero-Free Partition Functions

Authors: Penghui Yao, Yitong Yin, and Xinyuan Zhang

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Zero-free based algorithms are a major technique for deterministic approximate counting. In Barvinok’s original framework [Barvinok, 2017], by calculating truncated Taylor expansions, a quasi-polynomial time algorithm was given for estimating zero-free partition functions. Patel and Regts [Patel and Regts, 2017] later gave a refinement of Barvinok’s framework, which gave a polynomial-time algorithm for a class of zero-free graph polynomials that can be expressed as counting induced subgraphs in bounded-degree graphs. In this paper, we give a polynomial-time algorithm for estimating classical and quantum partition functions specified by local Hamiltonians with bounded maximum degree, assuming a zero-free property for the temperature. Consequently, when the inverse temperature is close enough to zero by a constant gap, we have a polynomial-time approximation algorithm for all such partition functions. Our result is based on a new abstract framework that extends and generalizes the approach of Patel and Regts.
Cite as

Penghui Yao, Yitong Yin, and Xinyuan Zhang. Polynomial-Time Approximation of Zero-Free Partition Functions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 108:1-108:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{yao_et_al:LIPIcs.ICALP.2022.108,
  author =	{Yao, Penghui and Yin, Yitong and Zhang, Xinyuan},
  title =	{{Polynomial-Time Approximation of Zero-Free Partition Functions}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{108:1--108:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.108},
  URN =		{urn:nbn:de:0030-drops-164494},
  doi =		{10.4230/LIPIcs.ICALP.2022.108},
  annote =	{Keywords: partition function, zero-freeness, local Hamiltonian}
}
Document
DOI: 10.4230/LIPIcs.FSCD.2019.31
Cubical Syntax for Reflection-Free Extensional Equality

Authors: Jonathan Sterling, Carlo Angiuli, and Daniel Gratzer

Published in: LIPIcs, Volume 131, 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)

Abstract
We contribute XTT, a cubical reconstruction of Observational Type Theory [Altenkirch et al., 2007] which extends Martin-Löf’s intensional type theory with a dependent equality type that enjoys function extensionality and a judgmental version of the unicity of identity proofs principle (UIP): any two elements of the same equality type are judgmentally equal. Moreover, we conjecture that the typing relation can be decided in a practical way. In this paper, we establish an algebraic canonicity theorem using a novel extension of the logical families or categorical gluing argument inspired by Coquand and Shulman [Coquand, 2018; Shulman, 2015]: every closed element of boolean type is derivably equal to either true or false.
Cite as

Jonathan Sterling, Carlo Angiuli, and Daniel Gratzer. Cubical Syntax for Reflection-Free Extensional Equality. In 4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 131, pp. 31:1-31:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{sterling_et_al:LIPIcs.FSCD.2019.31,
  author =	{Sterling, Jonathan and Angiuli, Carlo and Gratzer, Daniel},
  title =	{{Cubical Syntax for Reflection-Free Extensional Equality}},
  booktitle =	{4th International Conference on Formal Structures for Computation and Deduction (FSCD 2019)},
  pages =	{31:1--31:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-107-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{131},
  editor =	{Geuvers, Herman},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2019.31},
  URN =		{urn:nbn:de:0030-drops-105387},
  doi =		{10.4230/LIPIcs.FSCD.2019.31},
  annote =	{Keywords: Dependent type theory, extensional equality, cubical type theory, categorical gluing, canonicity}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.41
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers

Authors: Dean Doron, François Le Gall, and Amnon Ta-Shma

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
A recent series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system Lx=b, where L is the normalized Laplacian of an undirected graph. In this paper we study the space complexity of the problem. Surprisingly we are able to show a probabilistic, logspace algorithm solving the problem. We further extend the algorithm to other families of graphs like Eulerian graphs (and directed regular graphs) and graphs that mix in polynomial time. Our approach is to pseudo-invert the Laplacian, by first "peeling-off" the problematic kernel of the operator, and then to approximate the inverse of the remaining part by using a Taylor series. We approximate the Taylor series using a previous work and the special structure of the problem. For directed graphs we exploit in the analysis the Jordan normal form and results from matrix functions.
Cite as

Dean Doron, François Le Gall, and Amnon Ta-Shma. Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.APPROX-RANDOM.2017.41,
  author =	{Doron, Dean and Le Gall, Fran\c{c}ois and Ta-Shma, Amnon},
  title =	{{Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.41},
  URN =		{urn:nbn:de:0030-drops-75908},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.41},
  annote =	{Keywords: Laplacian solvers, Randomized logspace, Bounded-space complexity classes, Random walks, Matrix computation}
}
Document
DOI: 10.4230/DagSemProc.07461.6
Erlangian Approximation to Finite Time Ruin Probabilities in Perturbed Risk Models

Authors: Kaiqi Yu, David A. Stanford, and Jiandong Ren

Published in: Dagstuhl Seminar Proceedings, Volume 7461, Numerical Methods for Structured Markov Chains (2008)

Abstract
In this work-in-progress, we consider perturbed risk processes that have an underlying Markovian structure, including Markovian risk processes, and Sparre-Andersen risk processes when both inter claim times and claim sizes are phase-type. We apply the Erlangization method to this risk process in order to obtain an accurate approximation of the finite time ruin probability. In addition, we recognize a repeating structure in the probability matrices we work with. This is the key element in developing more efficent algorithms for the computation of the ruin probabilities. Several numerical examples are present to illustrate the model.
Cite as

Kaiqi Yu, David A. Stanford, and Jiandong Ren. Erlangian Approximation to Finite Time Ruin Probabilities in Perturbed Risk Models. In Numerical Methods for Structured Markov Chains. Dagstuhl Seminar Proceedings, Volume 7461, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{yu_et_al:DagSemProc.07461.6,
  author =	{Yu, Kaiqi and Stanford, David A. and Ren, Jiandong},
  title =	{{Erlangian Approximation to Finite Time Ruin Probabilities in Perturbed Risk Models}},
  booktitle =	{Numerical Methods for Structured Markov Chains},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7461},
  editor =	{Dario Bini and Beatrice Meini and Vaidyanathan Ramaswami and Marie-Ange Remiche and Peter Taylor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07461.6},
  URN =		{urn:nbn:de:0030-drops-13999},
  doi =		{10.4230/DagSemProc.07461.6},
  annote =	{Keywords: Perturbed risk processes, finite-time ruin probability, phase-type distribution, fluid flow models, Erlangization}
}
Document
DOI: 10.4230/DagSemProc.06121.3
06121 Report: Break Out Session on Guaranteed Execution

Authors: Calton Pu, Jim Johnson, Rogerio de Lemos, Andreas Reuter, David Taylor, and Irfan Zakiuddin

Published in: Dagstuhl Seminar Proceedings, Volume 6121, Atomicity: A Unifying Concept in Computer Science (2006)

Abstract
The break out session discussed guaranteed properties during program execution. Using a workflow example application, we discussed several research topics that form part of the guaranteed properties, including declarative specifications, generation of workflow program, generation of invariant guards, automated failure analysis, automated repair, and automated reconfiguration of workflow.
Cite as

Calton Pu, Jim Johnson, Rogerio de Lemos, Andreas Reuter, David Taylor, and Irfan Zakiuddin. 06121 Report: Break Out Session on Guaranteed Execution. In Atomicity: A Unifying Concept in Computer Science. Dagstuhl Seminar Proceedings, Volume 6121, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{pu_et_al:DagSemProc.06121.3,
  author =	{Pu, Calton and Johnson, Jim and de Lemos, Rogerio and Reuter, Andreas and Taylor, David and Zakiuddin, Irfan},
  title =	{{06121 Report: Break Out Session on Guaranteed Execution}},
  booktitle =	{Atomicity: A Unifying Concept in Computer Science},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6121},
  editor =	{Clifford B. Jones and David Lomet and Alexander Romanovsky and Gerhard Weikum},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06121.3},
  URN =		{urn:nbn:de:0030-drops-6410},
  doi =		{10.4230/DagSemProc.06121.3},
  annote =	{Keywords: Guaranteed properties, declarative specifications, generation of workflow program, generation of invariant guards, automated failure analysis, automat}
}
  • Refine by Author
  • 1 Angiuli, Carlo
  • 1 Doron, Dean
  • 1 Gratzer, Daniel
  • 1 Johnson, Jim
  • 1 Le Gall, François
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Algebraic semantics
  • 1 Theory of computation → Denotational semantics
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Type theory

  • Refine by Keyword
  • 1 Bounded-space complexity classes
  • 1 Dependent type theory
  • 1 Erlangization
  • 1 Guaranteed properties
  • 1 Laplacian solvers
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 1 2006
  • 1 2008
  • 1 2017
  • 1 2019
  • 1 2022
  • 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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact