5 Search Results for "Kautz, Henry"

Document
DOI: 10.4230/LIPIcs.CP.2024.10
Anytime Weighted Model Counting with Approximation Guarantees for Probabilistic Inference

Authors: Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Weighted model counting (WMC) plays a central role in probabilistic reasoning. Given that this problem is #P-hard, harder instances can generally only be addressed using approximate techniques based on sampling, which provide statistical convergence guarantees: the longer a sampling process runs, the more accurate the WMC is likely to be. In this work, we propose a deterministic search-based approach that can also be stopped at any time and provides hard lower- and upper-bound guarantees on the true WMC. This approach uses a value heuristic that guides exploration first towards models with a high weight and leverages Limited Discrepancy Search to make the bounds converge faster. The validity, scalability, and convergence of our approach are tested and compared with state-of-the-art baseline methods on the problem of computing marginal probabilities in Bayesian networks and reliability estimation in probabilistic graphs.
Cite as

Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen. Anytime Weighted Model Counting with Approximation Guarantees for Probabilistic Inference. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dubray_et_al:LIPIcs.CP.2024.10,
  author =	{Dubray, Alexandre and Schaus, Pierre and Nijssen, Siegfried},
  title =	{{Anytime Weighted Model Counting with Approximation Guarantees for Probabilistic Inference}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.10},
  URN =		{urn:nbn:de:0030-drops-206956},
  doi =		{10.4230/LIPIcs.CP.2024.10},
  annote =	{Keywords: Projected Weighted Model Counting, Limited Discrepancy Search, Approximate Method, Probabilistic Inference}
}
Document
DOI: 10.4230/LIPIcs.SAT.2024.26
Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits

Authors: Irfansha Shaik and Jaco van de Pol

Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)

Abstract
Layout synthesis is mapping a quantum circuit to a quantum processor. SWAP gate insertions are needed for scheduling 2-qubit gates only on connected physical qubits. With the ever-increasing number of qubits in NISQ processors, scalable layout synthesis is of utmost importance. With large optimality gaps observed in heuristic approaches, scalable exact methods are needed. While recent exact and near-optimal approaches scale to moderate circuits, large deep circuits are still out of scope. In this work, we propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. Using domain-specific information, we maintain optimality in parallel plans while scaling to large and deep circuits. From our results, we show the scalability of our approach which significantly outperforms leading exact and near-optimal approaches (up to 100x). For the first time, we can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit platforms with up to 17 SWAPs. While adding optimal SWAPs, we also report near-optimal depth in our mapped circuits.
Cite as

Irfansha Shaik and Jaco van de Pol. Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shaik_et_al:LIPIcs.SAT.2024.26,
  author =	{Shaik, Irfansha and van de Pol, Jaco},
  title =	{{Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits}},
  booktitle =	{27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-334-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{305},
  editor =	{Chakraborty, Supratik and Jiang, Jie-Hong Roland},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.26},
  URN =		{urn:nbn:de:0030-drops-205487},
  doi =		{10.4230/LIPIcs.SAT.2024.26},
  annote =	{Keywords: Layout Synthesis, Transpiling, Qubit Mapping and Routing, Quantum Circuits, Propositional Satisfiability, Parallel Plans}
}
Document
DOI: 10.4230/DagRep.1.4.1
Plan Recognition (Dagstuhl Seminar 11141)

Authors: Robert P. Goldman, Christopher W. Geib, Henry Kautz, and Tamim Asfour

Published in: Dagstuhl Reports, Volume 1, Issue 4 (2011)

Abstract
This Dagstuhl seminar brought together researchers with a wide range of interests and backgrounds related to plan and activity recognition. It featured a substantial set of longer tutorials on aspects of plan and activity recognition, and related topics and useful methods, as a way of establishing a common vocabulary and shared basis of understanding. Building on this shared understanding, individual researchers presented talks about their work in the area. There were also panel discussions which addressed questions about how to best foster progress in the field --- specifically how to improve our ability to compare different plan and activity recognition algorithms --- and address the question of whether to assume rationality in the modeled agents (a question that is of great concern in many fields at this time). This report presents a summary of the talks and discussions at the seminar.
Cite as

Robert P. Goldman, Christopher W. Geib, Henry Kautz, and Tamim Asfour. Plan Recognition (Dagstuhl Seminar 11141). In Dagstuhl Reports, Volume 1, Issue 4, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{goldman_et_al:DagRep.1.4.1,
  author =	{Goldman, Robert P. and Geib, Christopher W. and Kautz, Henry and Asfour, Tamim},
  title =	{{Plan Recognition (Dagstuhl Seminar 11141)}},
  pages =	{1--22},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{4},
  editor =	{Goldman, Robert P. and Geib, Christopher W. and Kautz, Henry and Asfour, Tamim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.4.1},
  URN =		{urn:nbn:de:0030-drops-31958},
  doi =		{10.4230/DagRep.1.4.1},
  annote =	{Keywords: Artificial intelligence, plan recognition, intent recognition, activity recognition}
}
Document
DOI: 10.4230/DagSemProc.05241.1
05241 Abstracts Collection – Synthesis and Planning

Authors: Henry Kautz, Wolfgang Thomas, and Moshe Y. Vardi

Published in: Dagstuhl Seminar Proceedings, Volume 5241, Synthesis and Planning (2006)

Abstract
From 12.06.05 to 17.06.2005 the Dagstuhl Seminar 05241 ``Synthesis and Planning'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Henry Kautz, Wolfgang Thomas, and Moshe Y. Vardi. 05241 Abstracts Collection – Synthesis and Planning. In Synthesis and Planning. Dagstuhl Seminar Proceedings, Volume 5241, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kautz_et_al:DagSemProc.05241.1,
  author =	{Kautz, Henry and Thomas, Wolfgang and Vardi, Moshe Y.},
  title =	{{05241 Abstracts Collection – Synthesis and Planning}},
  booktitle =	{Synthesis and Planning},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5241},
  editor =	{Henry Kautz and Wolfgang Thomas and Moshe Y. Vardi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05241.1},
  URN =		{urn:nbn:de:0030-drops-4531},
  doi =		{10.4230/DagSemProc.05241.1},
  annote =	{Keywords: AI planning, controller synthesis, partially observed domains, reactive computation, program analysis, games, model checking, satisfiability, Markov decision processes}
}
Document
DOI: 10.4230/DagSemProc.05241.2
05241 Executive Summary – Synthesis and Planning

Authors: Henry Kautz, Wolfgang Thomas, and Moshe Y. Vardi

Published in: Dagstuhl Seminar Proceedings, Volume 5241, Synthesis and Planning (2006)

Abstract
This seminar has brought together researchers working in two complementary fields: automatic synthesis of (control) programs, and methods for devising planning algorithms in artifical intelligence (AI). This combines a strong thread of current research in automata theory with an area of possible but so far unexplored applications.
Cite as

Henry Kautz, Wolfgang Thomas, and Moshe Y. Vardi. 05241 Executive Summary – Synthesis and Planning. In Synthesis and Planning. Dagstuhl Seminar Proceedings, Volume 5241, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kautz_et_al:DagSemProc.05241.2,
  author =	{Kautz, Henry and Thomas, Wolfgang and Vardi, Moshe Y.},
  title =	{{05241 Executive Summary – Synthesis and Planning}},
  booktitle =	{Synthesis and Planning},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5241},
  editor =	{Henry Kautz and Wolfgang Thomas and Moshe Y. Vardi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05241.2},
  URN =		{urn:nbn:de:0030-drops-4527},
  doi =		{10.4230/DagSemProc.05241.2},
  annote =	{Keywords: Synthesis, planning}
}
  • Refine by Author
  • 3 Kautz, Henry
  • 2 Thomas, Wolfgang
  • 2 Vardi, Moshe Y.
  • 1 Asfour, Tamim
  • 1 Dubray, Alexandre
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 AI planning
  • 1 Approximate Method
  • 1 Artificial intelligence
  • 1 Layout Synthesis
  • 1 Limited Discrepancy Search
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2006
  • 2 2024
  • 1 2011

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 About DROPS Imprint Privacy Contact