4 Search Results for "Smith, Matthew"

Document
DOI: 10.4230/LIPIcs.MFCS.2023.57
Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs

Authors: Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen

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

Abstract
For any finite set ℋ = {H_1,…,H_p} of graphs, a graph is ℋ-subgraph-free if it does not contain any of H_1,…,H_p as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed conditions, their complexity can be classified on classes of ℋ-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most 3 and examine their complexity on H-subgraph-free graph classes where H is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems. We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree 3. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.
Cite as

Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{johnson_et_al:LIPIcs.MFCS.2023.57,
  author =	{Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan},
  title =	{{Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{57:1--57:15},
  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.57},
  URN =		{urn:nbn:de:0030-drops-185914},
  doi =		{10.4230/LIPIcs.MFCS.2023.57},
  annote =	{Keywords: forbidden subgraphs, independent feedback vertex set, treewidth}
}
Document
DOI: 10.4230/LIPIcs.TQC.2022.9
Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension

Authors: Suchetan Dontha, Shi Jie Samuel Tan, Stephen Smith, Sangheon Choi, and Matthew Coudron

Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)

Abstract
We present a classical algorithm that, for any D-dimensional geometrically-local, quantum circuit C of polylogarithmic-depth, and any bit string x ∈ {0,1}ⁿ, can compute the quantity |<x|C|0^{⊗ n}>|² to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension D. This is an extension of the result [Nolan J. Coble and Matthew Coudron, 2021], which originally proved this result for D = 3. To see why this is interesting, note that, while the D = 1 case of this result follows from a standard use of Matrix Product States, known for decades, the D = 2 case required novel and interesting techniques introduced in [Sergy Bravyi et al., 2020]. Extending to the case D = 3 was even more laborious, and required further new techniques introduced in [Nolan J. Coble and Matthew Coudron, 2021]. Our work here shows that, while handling each new dimension has historically required a new insight, and fixed algorithmic primitive, based on known techniques for D ≤ 3, we can now handle any fixed dimension D > 3. Our algorithm uses the Divide-and-Conquer framework of [Nolan J. Coble and Matthew Coudron, 2021] to approximate the desired quantity via several instantiations of the same problem type, each involving D-dimensional circuits on about half the number of qubits as the original. This division step is then applied recursively, until the width of the recursively decomposed circuits in the D^{th} dimension is so small that they can effectively be regarded as (D-1)-dimensional problems by absorbing the small width in the D^{th} dimension into the qudit structure at the cost of a moderate increase in runtime. The main technical challenge lies in ensuring that the more involved portions of the recursive circuit decomposition and error analysis from [Nolan J. Coble and Matthew Coudron, 2021] still hold in higher dimensions, which requires small modifications to the analysis in some places. Our work also includes some simplifications, corrections and clarifications of the use of block-encodings within the original classical algorithm in [Nolan J. Coble and Matthew Coudron, 2021].
Cite as

Suchetan Dontha, Shi Jie Samuel Tan, Stephen Smith, Sangheon Choi, and Matthew Coudron. Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dontha_et_al:LIPIcs.TQC.2022.9,
  author =	{Dontha, Suchetan and Tan, Shi Jie Samuel and Smith, Stephen and Choi, Sangheon and Coudron, Matthew},
  title =	{{Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.9},
  URN =		{urn:nbn:de:0030-drops-165163},
  doi =		{10.4230/LIPIcs.TQC.2022.9},
  annote =	{Keywords: Low-Depth Quantum Circuits, Matrix Product States, Block-Encoding}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.1
Separating Local & Shuffled Differential Privacy via Histograms

Authors: Victor Balcer and Albert Cheu

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Recent work in differential privacy has highlighted the shuffled model as a promising avenue to compute accurate statistics while keeping raw data in users' hands. We present a protocol in this model that estimates histograms with error independent of the domain size. This implies an arbitrarily large gap in sample complexity between the shuffled and local models. On the other hand, we show that the models are equivalent when we impose the constraints of pure differential privacy and single-message randomizers.
Cite as

Victor Balcer and Albert Cheu. Separating Local & Shuffled Differential Privacy via Histograms. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{balcer_et_al:LIPIcs.ITC.2020.1,
  author =	{Balcer, Victor and Cheu, Albert},
  title =	{{Separating Local \& Shuffled Differential Privacy via Histograms}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.1},
  URN =		{urn:nbn:de:0030-drops-121068},
  doi =		{10.4230/LIPIcs.ITC.2020.1},
  annote =	{Keywords: Differential Privacy, Distributed Protocols, Histograms}
}
Document
DOI: 10.4230/DagRep.9.6.1
Empirical Evaluation of Secure Development Processes (Dagstuhl Seminar 19231)

Authors: Adam Shostack, Matthew Smith, Sam Weber, and Mary Ellen Zurko

Published in: Dagstuhl Reports, Volume 9, Issue 6 (2020)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19231 "Empirical Evaluation of Secure Development Processes". It includes a discussion of the motivation and overall seminar organization, the abstracts of the talks and a report of each working group.
Cite as

Adam Shostack, Matthew Smith, Sam Weber, and Mary Ellen Zurko. Empirical Evaluation of Secure Development Processes (Dagstuhl Seminar 19231). In Dagstuhl Reports, Volume 9, Issue 6, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{shostack_et_al:DagRep.9.6.1,
  author =	{Shostack, Adam and Smith, Matthew and Weber, Sam and Zurko, Mary Ellen},
  title =	{{Empirical Evaluation of Secure Development Processes (Dagstuhl Seminar 19231)}},
  pages =	{1--25},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{6},
  editor =	{Shostack, Adam and Smith, Matthew and Weber, Sam and Zurko, Mary Ellen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.6.1},
  URN =		{urn:nbn:de:0030-drops-114598},
  doi =		{10.4230/DagRep.9.6.1},
  annote =	{Keywords: security, security engineering, secure development lifecycle, empirical software engineering, empirical security engineering}
}
  • Refine by Author
  • 1 Balcer, Victor
  • 1 Cheu, Albert
  • 1 Choi, Sangheon
  • 1 Coudron, Matthew
  • 1 Dontha, Suchetan
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Security and privacy → Privacy-preserving protocols
  • 1 Theory of computation → Divide and conquer
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 1 Block-Encoding
  • 1 Differential Privacy
  • 1 Distributed Protocols
  • 1 Histograms
  • 1 Low-Depth Quantum Circuits
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2019
  • 1 2020
  • 1 2022
  • 1 2023

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