6 Search Results for "Gla�er, Christian"


Document
Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP

Authors: Fabian Egidy, Christian Glaßer, and Martin Herold

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


Abstract
We study the existence of optimal and p-optimal proof systems for classes in the Boolean hierarchy over NP. Our main results concern DP, i.e., the second level of this hierarchy: - If all sets in DP have p-optimal proof systems, then all sets in coDP have p-optimal proof systems. - The analogous implication for optimal proof systems fails relative to an oracle. As a consequence, we clarify such implications for all classes 𝒞 and 𝒟 in the Boolean hierarchy over NP: either we can prove the implication or show that it fails relative to an oracle. Furthermore, we show that the sets SAT and TAUT have p-optimal proof systems, if and only if all sets in the Boolean hierarchy over NP have p-optimal proof systems which is a new characterization of a conjecture studied by Pudlák.

Cite as

Fabian Egidy, Christian Glaßer, and Martin Herold. Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{egidy_et_al:LIPIcs.MFCS.2023.44,
  author =	{Egidy, Fabian and Gla{\ss}er, Christian and Herold, Martin},
  title =	{{Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{44:1--44: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.44},
  URN =		{urn:nbn:de:0030-drops-185784},
  doi =		{10.4230/LIPIcs.MFCS.2023.44},
  annote =	{Keywords: Computational Complexity, Boolean Hierarchy, Proof Complexity, Proof Systems, Oracle Construction}
}
Document
Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP

Authors: Anton Ehrmanntraut, Fabian Egidy, and Christian Glaßer

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
We construct an oracle relative to which P = NP ∩ coNP, but there are no many-one complete sets in UP, no many-one complete disjoint NP-pairs, and no many-one complete disjoint coNP-pairs. This contributes to a research program initiated by Pudlák [P. Pudlák, 2017], which studies incompleteness in the finite domain and which mentions the construction of such oracles as open problem. The oracle shows that NP ∩ coNP is indispensable in the list of hypotheses studied by Pudlák. Hence one should consider stronger hypotheses, in order to find a universal one.

Cite as

Anton Ehrmanntraut, Fabian Egidy, and Christian Glaßer. Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ehrmanntraut_et_al:LIPIcs.MFCS.2022.45,
  author =	{Ehrmanntraut, Anton and Egidy, Fabian and Gla{\ss}er, Christian},
  title =	{{Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.45},
  URN =		{urn:nbn:de:0030-drops-168435},
  doi =		{10.4230/LIPIcs.MFCS.2022.45},
  annote =	{Keywords: computational complexity, promise classes, proof complexity, complete sets, oracle construction}
}
Document
NP-Completeness, Proof Systems, and Disjoint NP-Pairs

Authors: Titus Dose and Christian Glaßer

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
The article investigates the relation between three well-known hypotheses. - H_{union}: the union of disjoint ≤^p_m-complete sets for NP is ≤^p_m-complete - H_{opps}: there exist optimal propositional proof systems - H_{cpair}: there exist ≤^{pp}_m-complete disjoint NP-pairs The following results are obtained: - The hypotheses are pairwise independent under relativizable proofs, except for the known implication H_{opps} ⇒ H_{cpair}. - An answer to Pudlák’s question for an oracle relative to which ¬H_{cpair}, ¬H_{opps}, and UP has ≤^p_m-complete sets. - The converse of Köbler, Messner, and Torán’s implication NEE ∩ TALLY ⊆ coNEE ⇒ H_{opps} fails relative to an oracle, where NEE =^{df} NTIME(2^O(2ⁿ)). - New characterizations of H_{union} and two variants in terms of coNP-completeness and p-producibility of the set of hard formulas of propositional proof systems.

Cite as

Titus Dose and Christian Glaßer. NP-Completeness, Proof Systems, and Disjoint NP-Pairs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{dose_et_al:LIPIcs.STACS.2020.9,
  author =	{Dose, Titus and Gla{\ss}er, Christian},
  title =	{{NP-Completeness, Proof Systems, and Disjoint NP-Pairs}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.9},
  URN =		{urn:nbn:de:0030-drops-118707},
  doi =		{10.4230/LIPIcs.STACS.2020.9},
  annote =	{Keywords: NP-complete, propositional proof system, disjoint NP-pair, oracle}
}
Document
Emptiness Problems for Integer Circuits

Authors: Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, and Marc Technau

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)


Abstract
We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, addition, and multiplication is allowed turns out to be equivalent to the complement of polynomial identity testing (PIT). Our results imply the following improvements and insights on problems studied in earlier papers. We improve the bounds for the membership problem MC(\cup,\cap,¯,+,×) studied by McKenzie and Wagner 2007 and for the equivalence problem EQ(\cup,\cap,¯,+,×) studied by Glaßer et al. 2010. Moreover, it turns out that the following problems are equivalent to PIT, which shows that the challenge to improve their bounds is just a reformulation of a major open problem in algebraic computing complexity: 1. membership problem MC(\cap,+,×) studied by McKenzie and Wagner 2007 2. integer membership problems MC_Z(+,×), MC_Z(\cap,+,×) studied by Travers 2006 3. equivalence problem EQ(+,×) studied by Glaßer et al. 2010

Cite as

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, and Marc Technau. Emptiness Problems for Integer Circuits. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.MFCS.2017.33,
  author =	{Barth, Dominik and Beck, Moritz and Dose, Titus and Gla{\ss}er, Christian and Michler, Larissa and Technau, Marc},
  title =	{{Emptiness Problems for Integer Circuits}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.33},
  URN =		{urn:nbn:de:0030-drops-80641},
  doi =		{10.4230/LIPIcs.MFCS.2017.33},
  annote =	{Keywords: computational complexity, integer expressions, integer circuits, polynomial identity testing}
}
Document
Music Information Retrieval Meets Music Education

Authors: Christian Dittmar, Estefanía Cano, Jakob Abeßer, and Sascha Grollmisch

Published in: Dagstuhl Follow-Ups, Volume 3, Multimodal Music Processing (2012)


Abstract
This paper addresses the use of Music Information Retrieval (MIR) techniques in music education and their integration in learning software. A general overview of systems that are either commercially available or in research stage is presented. Furthermore, three well-known MIR methods used in music learning systems and their state-of-the-art are described: music transcription, solo and accompaniment track creation, and generation of performance instructions. As a representative example of a music learning system developed within the MIR community, the Songs2See software is outlined. Finally, challenges and directions for future research are described.

Cite as

Christian Dittmar, Estefanía Cano, Jakob Abeßer, and Sascha Grollmisch. Music Information Retrieval Meets Music Education. In Multimodal Music Processing. Dagstuhl Follow-Ups, Volume 3, pp. 95-120, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InCollection{dittmar_et_al:DFU.Vol3.11041.95,
  author =	{Dittmar, Christian and Cano, Estefan{\'\i}a and Abe{\ss}er, Jakob and Grollmisch, Sascha},
  title =	{{Music Information Retrieval Meets Music Education}},
  booktitle =	{Multimodal Music Processing},
  pages =	{95--120},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-37-8},
  ISSN =	{1868-8977},
  year =	{2012},
  volume =	{3},
  editor =	{M\"{u}ller, Meinard and Goto, Masataka and Schedl, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol3.11041.95},
  URN =		{urn:nbn:de:0030-drops-34689},
  doi =		{10.4230/DFU.Vol3.11041.95},
  annote =	{Keywords: Music learning, music transcription, source separation, performance feedback}
}
Document
Applications of Discrepancy Theory in Multiobjective Approximation

Authors: Christian Glaßer, Christian Reitwießner, and Maximilian Witek

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)


Abstract
We apply a multi-color extension of the Beck-Fiala theorem to show that the multiobjective maximum traveling salesman problem is randomized 1/2-approximable on directed graphs and randomized 2/3-approximable on undirected graphs. Using the same technique we show that the multiobjective maximum satisfiablilty problem is 1/2-approximable.

Cite as

Christian Glaßer, Christian Reitwießner, and Maximilian Witek. Applications of Discrepancy Theory in Multiobjective Approximation. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 55-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{glaer_et_al:LIPIcs.FSTTCS.2011.55,
  author =	{Gla{\ss}er, Christian and Reitwie{\ss}ner, Christian and Witek, Maximilian},
  title =	{{Applications of Discrepancy Theory in Multiobjective Approximation}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{55--65},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.55},
  URN =		{urn:nbn:de:0030-drops-33233},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.55},
  annote =	{Keywords: Discrepancy Theory, Multiobjective Optimization, Satisfiability, Traveling Salesman}
}
  • Refine by Author
  • 5 Glaßer, Christian
  • 2 Dose, Titus
  • 2 Egidy, Fabian
  • 1 Abeßer, Jakob
  • 1 Barth, Dominik
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Oracles and decision trees
  • 3 Theory of computation → Proof complexity
  • 2 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 computational complexity
  • 1 Boolean Hierarchy
  • 1 Computational Complexity
  • 1 Discrepancy Theory
  • 1 Multiobjective Optimization
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 1 2011
  • 1 2012
  • 1 2017
  • 1 2020
  • 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