Christian Glaßer

113 papers A* 1A 9B 14C 7Misc 3Journal 65Unranked 12

Year	Rank	Type	Title / Venue / Authors
2025	A*	`conf`	Optimal Proof Systems for Complex Sets Are Hard to Find. STOC Fabian Egidy, Christian Glaßer
2025	B	`conf`	The Complexity of Computing Second Solutions. MFCS Fabian Egidy, Christian Glaßer, Fynn Godau
2024	B	`conf`	An Oracle with no UP-Complete Sets, but NP = PSPACE. MFCS David Dingel, Fabian Egidy, Christian Glaßer
2024	J	`jnl`	An Oracle with no UP-Complete Sets, but NP=PSPACE. CoRR David Dingel, Fabian Egidy, Christian Glaßer
2024	J	`jnl`	Oracle without Optimal Proof Systems outside Nondeterministic Subexponential Time. CoRR Fabian Egidy, Christian Glaßer
2023	B	`conf`	Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP. MFCS Fabian Egidy, Christian Glaßer, Martin G. Herold
2023	J	`jnl`	Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP. CoRR Fabian Egidy, Christian Glaßer, Martin G. Herold
2022	B	`conf`	Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP. MFCS Anton Ehrmanntraut, Fabian Egidy, Christian Glaßer
2022	J	`jnl`	Oracle with P=NP∩coNP, but no Many-One Completeness in UP, DisjNP, and DisjCoNP. CoRR Anton Ehrmanntraut, Fabian Egidy, Christian Glaßer
2020	J	`jnl`	Emptiness problems for integer circuits. Theor. Comput. Sci. Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau
2020	A	`conf`	NP-Completeness, Proof Systems, and Disjoint NP-Pairs. STACS Titus Dose, Christian Glaßer
2019	J	`jnl`	NP-Completeness, Proof Systems, and Disjoint NP-Pairs. Electron. Colloquium Comput. Complex. Titus Dose, Christian Glaßer
2017	J	`jnl`	Autoreducibility and mitoticity of logspace-complete sets for NP and other classes. Inf. Comput. Christian Glaßer, Maximilian Witek
2017	J	`jnl`	Circuit satisfiability and constraint satisfaction around Skolem Arithmetic. Theor. Comput. Sci. Christian Glaßer, Peter Jonsson, Barnaby Martin
2017	B	`conf`	Emptiness Problems for Integer Circuits. MFCS Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau
2017	J	`jnl`	Emptiness Problems for Integer Circuits. Electron. Colloquium Comput. Complex. Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau
2017	—	`conf`	Introduction to Autoreducibility and Mitoticity. Computability and Complexity Christian Glaßer, Dung T. Nguyen, Alan L. Selman, Maximilian Witek
2016	C	`conf`	Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic. CiE Christian Glaßer, Peter Jonsson, Barnaby Martin
2016	J	`jnl`	Efficient algorithms for membership in boolean hierarchies of regular languages. Theor. Comput. Sci. Christian Glaßer, Heinz Schmitz, Victor L. Selivanov
2015	J	`jnl`	Constraint Satisfaction Problems around Skolem Arithmetic. CoRR Christian Glaßer, Peter Jonsson, Barnaby Martin
2014	—	`conf`	Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes. MFCS (2) Christian Glaßer, Maximilian Witek
2014	J	`jnl`	Disjoint NP-Pairs and Propositional Proof Systems. SIGACT News Christian Glaßer, Andrew Hughes, Alan L. Selman, Nils Wisiol
2014	J	`jnl`	Perfect correspondences between dot-depth and polynomial-time hierarchies. J. Comput. Syst. Sci. Christian Glaßer, Stephen D. Travers, Klaus W. Wagner
2014	J	`jnl`	Unions of Disjoint NP-Complete Sets. ACM Trans. Comput. Theory Christian Glaßer, John M. Hitchcock, Aduri Pavan, Stephen D. Travers
2013	J	`jnl`	Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes. Electron. Colloquium Comput. Complex. Christian Glaßer, Maximilian Witek
2013	—	`conf`	Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions. ICALP (1) Christian Glaßer, Dung T. Nguyen, Christian Reitwießner, Alan L. Selman, Maximilian Witek
2013	J	`jnl`	Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions. Electron. Colloquium Comput. Complex. Christian Glaßer, Dung T. Nguyen, Christian Reitwießner, Alan L. Selman, Maximilian Witek
2012	B	`conf`	Structural Complexity of Multiobjective NP Search Problems. LATIN Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek
2011	J	`jnl`	Applications of Discrepancy Theory in Multiobjective Approximation CoRR Christian Glaßer, Christian Reitwießner, Maximilian Witek
2011	—	`conf`	Applications of Discrepancy Theory in Multiobjective Approximation. FSTTCS Christian Glaßer, Christian Reitwießner, Maximilian Witek
2011	J	`jnl`	The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions. Electron. Colloquium Comput. Complex. Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek
2011	J	`jnl`	The fault tolerance of NP-hard problems. Inf. Comput. Christian Glaßer, Aduri Pavan, Stephen D. Travers
2011	J	`jnl`	The shrinking property for NP and coNP. Theor. Comput. Sci. Christian Glaßer, Christian Reitwießner, Victor L. Selivanov
2011	Misc	`conf`	Unions of Disjoint NP-Complete Sets. COCOON Christian Glaßer, John M. Hitchcock, Aduri Pavan, Stephen D. Travers
2010	—	`conf`	10501 Abstracts Collection - Advances and Applications of Automata on Words and Trees. Advances and Applications of Automata on Words and Trees Christian Glaßer, Jean-Eric Pin, Nicole Schweikardt, Victor L. Selivanov, Wolfgang Thomas
2010	—	`conf`	10501 Executive Summary - Advances and Applications of Automata on Words and Trees. Advances and Applications of Automata on Words and Trees Christian Glaßer, Jean-Eric Pin, Nicole Schweikardt, Victor L. Selivanov, Wolfgang Thomas
2010	—	`ed.`	Advances and Applications of Automata on Words and Trees, 12.12. - 17.12.2010 Advances and Applications of Automata on Words and Trees Christian Glaßer, Jean-Eric Pin, Nicole Schweikardt, Victor L. Selivanov, Wolfgang Thomas
2010	C	`conf`	Approximability and Hardness in Multi-objective Optimization. CiE Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek
2010	J	`jnl`	Balanced Combinations of Solutions in Multi-Objective Optimization CoRR Christian Glaßer, Christian Reitwießner, Maximilian Witek
2010	J	`jnl`	Equivalence Problems for Circuits over Sets of Natural Numbers. Theory Comput. Syst. Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen D. Travers, Matthias Waldherr
2010	J	`jnl`	Hardness and Approximability in Multi-Objective Optimization. Electron. Colloquium Comput. Complex. Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek
2010	J	`jnl`	Satisfiability of algebraic circuits over sets of natural numbers. Discret. Appl. Math. Christian Glaßer, Christian Reitwießner, Stephen D. Travers, Matthias Waldherr
2010	J	`jnl`	Space-efficient informational redundancy. J. Comput. Syst. Sci. Christian Glaßer
2009	J	`jnl`	Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman. Electron. Colloquium Comput. Complex. Christian Glaßer, Christian Reitwießner, Maximilian Witek
2009	J	`jnl`	Machines that Can Output Empty Words. Theory Comput. Syst. Christian Glaßer, Stephen D. Travers
2009	J	`jnl`	Non-mitotic sets. Theor. Comput. Sci. Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang
2009	C	`conf`	The Fault Tolerance of NP-Hard Problems. LATA Christian Glaßer, Aduri Pavan, Stephen D. Travers
2009	J	`jnl`	The Informational Content of Canonical Disjoint NP-Pairs. Int. J. Found. Comput. Sci. Christian Glaßer, Alan L. Selman, Liyu Zhang
2008	J	`jnl`	Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages CoRR Christian Glaßer, Heinz Schmitz, Victor L. Selivanov
2008	A	`conf`	Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages. STACS Christian Glaßer, Heinz Schmitz, Victor L. Selivanov
2008	J	`jnl`	Languages of Dot-Depth 3/2. Theory Comput. Syst. Christian Glaßer, Heinz Schmitz
2008	B	`conf`	Multiobjective Disk Cover Admits a PTAS. ISAAC Christian Glaßer, Christian Reitwießner, Heinz Schmitz
2008	B	`conf`	Space-Efficient Informational Redundancy. ISAAC Christian Glaßer
2008	J	`jnl`	Splitting NP-Complete Sets. SIAM J. Comput. Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
2008	C	`conf`	The Shrinking Property for NP and coNP. CiE Christian Glaßer, Christian Reitwießner, Victor L. Selivanov
2008	J	`jnl`	The Shrinking Property for NP and coNP. Electron. Colloquium Comput. Complex. Christian Glaßer, Christian Reitwießner, Victor L. Selivanov
2008	J	`jnl`	The complexity of unions of disjoint sets. J. Comput. Syst. Sci. Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner
2007	J	`jnl`	Autoreducibility, mitoticity, and immunity. J. Comput. Syst. Sci. Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang
2007	J	`jnl`	Canonical disjoint NP-pairs of propositional proof systems. Theor. Comput. Sci. Christian Glaßer, Alan L. Selman, Liyu Zhang
2007	J	`jnl`	Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages. Electron. Colloquium Comput. Complex. Christian Glaßer, Heinz Schmitz, Victor L. Selivanov
2007	Misc	`conf`	Equivalence Problems for Circuits over Sets of Natural Numbers. CSR Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen D. Travers, Matthias Waldherr
2007	J	`jnl`	Languages polylog-time reducible to dot-depth 1/2. J. Comput. Syst. Sci. Christian Glaßer
2007	—	`conf`	Non-mitotic Sets. FSTTCS Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang
2007	—	`conf`	Satisfiability of Algebraic Circuits over Sets of Natural Numbers. FSTTCS Christian Glaßer, Christian Reitwießner, Stephen D. Travers, Matthias Waldherr
2007	A	`conf`	The Complexity of Unions of Disjoint Sets. STACS Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner
2007	Misc	`conf`	The Informational Content of Canonical Disjoint NP-Pairs. COCOON Christian Glaßer, Alan L. Selman, Liyu Zhang
2007	J	`jnl`	The Informational Content of Canonical Disjoint NP-Pairs. Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Liyu Zhang
2006	J	`jnl`	Error-bounded probabilistic computations between MA and AM. J. Comput. Syst. Sci. Elmar Böhler, Christian Glaßer, Daniel Meister
2006	B	`conf`	Machines that Can Output Empty Words. MFCS Christian Glaßer, Stephen D. Travers
2006	C	`conf`	Mitosis in Computational Complexity. TAMC Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
2006	J	`jnl`	Non-Mitotic Sets. Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang
2006	C	`conf`	Perfect Correspondences Between Dot-Depth and Polynomial-Time Hierarchy. Developments in Language Theory Christian Glaßer, Stephen D. Travers, Klaus W. Wagner
2006	J	`jnl`	Properties of NP-Complete Sets. SIAM J. Comput. Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta
2006	A	`conf`	Redundancy in Complete Sets. STACS Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
2006	—	`conf`	Survey of Disjoint NP-pairs and Relations to Propositional Proof Systems. Essays in Memory of Shimon Even Christian Glaßer, Alan L. Selman, Liyu Zhang
2006	J	`jnl`	The Complexity of Unions of Disjoint Sets. Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner
2005	J	`jnl`	A Reducibility that Corresponds to Unbalanced Leaf-Language Classes Electron. Colloquium Comput. Complex. Christian Glaßer, Stephen D. Travers, Klaus W. Wagner
2005	J	`jnl`	Autoreducibility, Mitoticity, and Immunity Electron. Colloquium Comput. Complex. Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang
2005	B	`conf`	Autoreducibility, Mitoticity, and Immunity. MFCS Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang
2005	B	`conf`	Canonical Disjoint NP-Pairs of Propositional Proof Systems. MFCS Christian Glaßer, Alan L. Selman, Liyu Zhang
2005	J	`jnl`	Generation problems. Theor. Comput. Sci. Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner
2005	J	`jnl`	Machines that can Output Empty Words Electron. Colloquium Comput. Complex. Christian Glaßer, Stephen D. Travers
2005	A	`conf`	Polylog-Time Reductions Decrease Dot-Depth. STACS Christian Glaßer
2005	J	`jnl`	Reductions between disjoint NP-Pairs. Inf. Comput. Christian Glaßer, Alan L. Selman, Samik Sengupta
2005	J	`jnl`	Redundancy in Complete Sets Electron. Colloquium Comput. Complex. Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang
2005	J	`jnl`	Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Liyu Zhang
2005	J	`jnl`	The complexity of base station positioning in cellular networks. Discret. Appl. Math. Christian Glaßer, Steffen Reith, Heribert Vollmer
2004	B	`conf`	A Protocol for Serializing Unique Strategies. MFCS Marcel Crâsmaru, Christian Glaßer, Kenneth W. Regan, Samik Sengupta
2004	J	`jnl`	Canonical Disjoint NP-Pairs of Propositional Proof Systems Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Liyu Zhang
2004	J	`jnl`	Counting with Counterfree Automata Electron. Colloquium Comput. Complex. Christian Glaßer
2004	J	`jnl`	Disjoint NP-Pairs. SIAM J. Comput. Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang
2004	J	`jnl`	Generation Problems Electron. Colloquium Comput. Complex. Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner
2004	B	`conf`	Generation Problems. MFCS Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner
2004	J	`jnl`	Properties of NP-Complete Sets Electron. Colloquium Comput. Complex. Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta
2004	A	`conf`	Properties of NP-Complete Sets. CCC Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta
2004	A	`conf`	Reductions between Disjoint NP-Pairs. CCC Christian Glaßer, Alan L. Selman, Samik Sengupta
2003	J	`jnl`	Disjoint NP-Pairs Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang
2003	A	`conf`	Disjoint NP-Pairs. CCC Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang
2003	B	`conf`	Error-Bounded Probabilistic Computations between MA and AM. MFCS Elmar Böhler, Christian Glaßer, Daniel Meister
2003	J	`jnl`	Reductions between Disjoint NP-Pairs Electron. Colloquium Comput. Complex. Christian Glaßer, Alan L. Selman, Samik Sengupta
2003	J	`jnl`	Relativizing Function Classes. J. Univers. Comput. Sci. Christian Glaßer, Gerd Wechsung
2003	J	`jnl`	Small Bounded-Error Computations and Completeness Electron. Colloquium Comput. Complex. Elmar Böhler, Christian Glaßer, Daniel Meister
2001	—	`conf`	A polynomial-time approximation scheme for base station positioning in UMTS networks. DIAL-M Matthias Galota, Christian Glaßer, Steffen Reith, Heribert Vollmer
2001	—	`—`	Forbidden-patterns and word extensions for concatenation hierarchies. Christian Glaßer
2001	C	`conf`	Level 5/2 of the Straubing-Thérien Hierarchy for Two-Letter Alphabets. Developments in Language Theory Christian Glaßer, Heinz Schmitz
2001	J	`jnl`	The Boolean Structure of Dot-Depth One. J. Autom. Lang. Comb. Christian Glaßer, Heinz Schmitz
2000	J	`jnl`	A Moment of Perfect Clarity I: The Parallel Census Technique CoRR Christian Glaßer, Lane A. Hemaspaandra
2000	J	`jnl`	A Moment of Perfect Clarity II: Consequences of Sparse Sets Hard for NP with Respect to Weak Reductions CoRR Christian Glaßer, Lane A. Hemaspaandra
2000	J	`jnl`	A moment of perfect clarity I: the parallel census technique. SIGACT News Lane A. Hemaspaandra, Christian Glaßer
2000	J	`jnl`	A moment of perfect clarity II: consequences of sparse sets hard for NP with respect to weak reductions. SIGACT News Christian Glaßer, Lane A. Hemaspaandra
2000	—	`conf`	Decidable Hierarchies of Starfree Languages. FSTTCS Christian Glaßer, Heinz Schmitz
2000	A	`conf`	Languages of Dot-Depth 3/2. STACS Christian Glaßer, Heinz Schmitz
2000	—	`conf`	The Complexity of Base Station Positioning in Cellular Networks. ICALP Satellite Workshops Christian Glaßer, Steffen Reith, Heribert Vollmer