| Publication | Date of Publication | Type |
|---|
| Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations | 2024-10-01 | Paper |
| Comparing descriptional and computational complexity of infinite words | 2024-01-29 | Paper |
| Gossiping in vertex-disjoint paths mode in interconnection networks | 2024-01-05 | Paper |
| Two-Way Non-Uniform Finite Automata | 2023-08-15 | Paper |
| Optimal algorithms for broadcast and gossip in the edge-disjoint path modes | 2022-12-09 | Paper |
| Effective systolic algorithms for gossiping in cycles and two-dimensional grids | 2022-12-09 | Paper |
| Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations | 2022-11-09 | Paper |
| Translating regular expressions into small ε-free nondeterministic finite automata | 2022-11-09 | Paper |
| Two lower bounds on distributive generation of languages | 2022-08-18 | Paper |
| A nonlinear lower bound on the practical combinational complexity | 2022-08-18 | Paper |
| A comparison of two lower bound methods for communication complexity | 2022-08-18 | Paper |
| Two-way non-uniform finite automata | 2022-03-25 | Paper |
| Roots and Powers in Regular Languages: Recognizing Nonregular Properties by Finite Automata | 2021-05-20 | Paper |
| On the advice complexity of the online dominating set problem | 2021-03-09 | Paper |
| Probability theory 2. From standard deviation to statistical inference | 2020-06-17 | Paper |
| What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\) | 2019-11-29 | Paper |
| Online Graph Coloring Against a Randomized Adversary | 2018-07-24 | Paper |
| On the Size of Two-Way Reasonable Automata for the Liveness Problem | 2018-05-15 | Paper |
| Alan Turing and the Foundation of Computer Science | 2018-04-18 | Paper |
| What one has to know when attacking \(\mathsf {P}\) vs. \(\mathsf {NP}\) (extended abstract) | 2017-11-22 | Paper |
| Stochastics. Discrete probability and combinatorics | 2017-06-30 | Paper |
| Advice Complexity of the Online Search Problem | 2016-09-29 | Paper |
| Approximation algorithms for the TSP with sharpened triangle inequality | 2016-06-16 | Paper |
| Online Graph Coloring with Advice and Randomized Adversary | 2016-03-10 | Paper |
| On the Power of Laconic Advice in Communication Complexity | 2016-03-10 | Paper |
| The Complexity of Paging Against a Probabilistic Adversary | 2016-03-10 | Paper |
| On the Size of Two-Way Reasonable Automata for the Liveness Problem | 2015-11-10 | Paper |
| A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey | 2015-09-08 | Paper |
| Online coloring of bipartite graphs with and without advice | 2015-01-19 | Paper |
| On the Power of Advice and Randomization for the Disjoint Path Allocation Problem | 2015-01-13 | Paper |
| Einführung in die Kryptologie | 2014-12-03 | Paper |
| Corrigendum to ``On the approximability and hardness of minimum topic connected overlay and its special instances | 2014-12-02 | Paper |
| On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles | 2014-10-06 | Paper |
| The string guessing problem as a method to prove lower bounds on the advice complexity | 2014-10-06 | Paper |
| DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ | 2014-08-04 | Paper |
| On the Advice Complexity of the Online L(2,1)-Coloring Problem on Paths and Cycles | 2013-06-11 | Paper |
| The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity | 2013-06-11 | Paper |
| Determinism vs. Nondeterminism for Two-Way Automata | 2012-11-02 | Paper |
| On the Power of Randomness versus Advice in Online Computation | 2012-11-01 | Paper |
| Online Coloring of Bipartite Graphs with and without Advice | 2012-09-25 | Paper |
| On the approximability and hardness of minimum topic connected overlay and its special instances | 2012-05-30 | Paper |
| Steiner tree reoptimization in graphs with sharpened triangle inequality | 2012-05-11 | Paper |
| Ambiguity and Communication | 2012-04-24 | Paper |
| On the Hardness of Reoptimization with Multiple Given Solutions | 2011-11-22 | Paper |
| On the Approximability of Minimum Topic Connected Overlay and Its Special Instances | 2011-08-17 | Paper |
| Knowing All Optimal Solutions Does Not Help for TSP Reoptimization | 2011-06-24 | Paper |
| Improved Approximations for Hard Optimization Problems via Problem Instance Classification | 2011-05-27 | Paper |
| Ambiguity and communication | 2011-05-23 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3079180 | 2011-03-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3075859 | 2011-02-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3060334 | 2010-12-02 | Paper |
| Information Complexity of Online Problems | 2010-09-03 | Paper |
| On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks | 2010-08-27 | Paper |
| On probabilistic pushdown automata | 2010-08-19 | Paper |
| Algorithmics – Is There Hope for a Unified Theory? | 2010-06-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3565453 | 2010-06-04 | Paper |
| The Steiner Tree Reoptimization Problem with Sharpened Triangle Inequality | 2010-05-28 | Paper |
| Reoptimization of Steiner trees: changing the terminal set | 2009-08-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5192988 | 2009-08-10 | Paper |
| On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's | 2009-08-07 | Paper |
| On \(k\)-connectivity problems with sharpened triangle inequality | 2009-02-23 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5505179 | 2009-01-26 | Paper |
| Algorithmic Adventures | 2009-01-16 | Paper |
| On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes | 2008-10-30 | Paper |
| Reoptimization of Steiner Trees | 2008-07-15 | Paper |
| On the Hardness of Reoptimization | 2008-03-07 | Paper |
| Stability of approximation algorithms or parameterization of the approximation ratio | 2008-03-06 | Paper |
| The parameterized approximability of TSP with deadlines | 2007-12-19 | Paper |
| Efficient Algorithms for the Spoonerism Problem | 2007-11-15 | Paper |
| On the Approximation Hardness of Some Generalizations of TSP | 2007-09-07 | Paper |
| Job shop scheduling with unit length tasks: bounds and algorithms | 2007-08-13 | Paper |
| Comparing the size of NFAs with and without \(\epsilon\)-transitions | 2007-07-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5292492 | 2007-06-21 | Paper |
| On the stability of approximation for Hamiltonian path problems | 2007-01-18 | Paper |
| Gossiping in vertex-disjoint paths mode in \(d\)-dimensional grids and planar graphs | 2006-10-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5485986 | 2006-09-06 | Paper |
| Automata, Languages and Programming | 2006-01-10 | Paper |
| SOFSEM 2005: Theory and Practice of Computer Science | 2005-12-07 | Paper |
| Design and analysis of randomized algorithms. Introduction to design paradigms. | 2005-05-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4673626 | 2005-05-06 | Paper |
| Stability of Approximation in Discrete Optimization | 2005-04-29 | Paper |
| Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance. | 2005-04-27 | Paper |
| Algorithmics for hard problems. | 2005-04-26 | Paper |
| On the power of randomized multicounter machines | 2005-02-22 | Paper |
| On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality | 2005-01-11 | Paper |
| On multi-partition communication complexity | 2004-11-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4737913 | 2004-08-11 | Paper |
| On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata | 2004-08-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4739596 | 2004-08-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4465337 | 2004-05-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4448359 | 2004-02-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4449194 | 2004-02-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4449165 | 2004-02-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4501548 | 2004-01-27 | Paper |
| Nondeterministic Communication with a Limited Number of Advice Bits | 2004-01-08 | Paper |
| Theoretical computer science. Introduction to automata, computability, complexity, algorithmics, randomization, communication, and cryptography. | 2003-12-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4437508 | 2003-12-02 | Paper |
| The power of nondeterminism and randomness for oblivious branching programs | 2003-08-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4415244 | 2003-07-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4788609 | 2003-06-02 | Paper |
| On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata | 2003-01-14 | Paper |
| Communication complexity method for measuring nondeterminism in finite automata | 2003-01-14 | Paper |
| Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. | 2002-08-05 | Paper |
| Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata | 2002-07-02 | Paper |
| On the power of Las Vegas II: Two-way finite automata | 2002-03-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2762506 | 2002-01-09 | Paper |
| Algorithmic concepts of informatics. Computability, complexity theory, algorithmics, cryptography. An introduction | 2001-11-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2754144 | 2001-11-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4496241 | 2001-06-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4503938 | 2001-05-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4501529 | 2001-04-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2701740 | 2001-02-19 | Paper |
| Communication Complexity and Lower Bounds on Multilective Computations | 2000-10-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4938639 | 2000-04-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4941164 | 2000-04-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4699286 | 1999-11-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228510 | 1999-10-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4260384 | 1999-09-19 | Paper |
| Optimal algorithms for broadcast and gossip in the edge-disjoint modes | 1998-01-04 | Paper |
| The complexity of systolic dissemination of information in interconnection networks | 1997-12-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4337605 | 1997-05-21 | Paper |
| A nonlinear lower bound on the practical combinational complexity | 1997-02-28 | Paper |
| A comparison of two lower-bound methods for communication complexity | 1997-02-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4874656 | 1996-04-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4870160 | 1996-04-09 | Paper |
| On embeddings in cycles | 1995-07-10 | Paper |
| Note on optimal gossiping in some weak-connected graphs | 1995-02-09 | Paper |
| Optimal algorithms for dissemination of information in generalized communication modes | 1994-12-11 | Paper |
| Deterministic versus nondeterministic space in terms of synchronized alternating machines | 1994-09-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4281632 | 1994-06-20 | Paper |
| Some hierarchies for the communication complexity measures of cooperating grammar systems | 1994-05-15 | Paper |
| Optimal algorithms for dissemination of information in some interconnection networks | 1993-09-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4036773 | 1993-05-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4035242 | 1993-05-18 | Paper |
| A note on realtime one-way synchronized alternating one-counter automata | 1993-05-16 | Paper |
| ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE | 1993-01-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4016418 | 1992-12-14 | Paper |
| Lower bounds on the area complexity of Boolean circuits | 1992-09-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4009550 | 1992-09-27 | Paper |
| Abstract symbol systems (an exercise of the bottom-up approach in artificial intelligence) | 1992-08-13 | Paper |
| Nonlinear lower bounds on the number of processors of circuits with sublinear separators | 1992-06-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3984739 | 1992-06-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3975141 | 1992-06-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3982063 | 1992-06-26 | Paper |
| On the power of synchronization in parallel computations | 1991-01-01 | Paper |
| On problems for which no oracle can help | 1991-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3197313 | 1991-01-01 | Paper |
| Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3359735 | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3829071 | 1990-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3197770 | 1990-01-01 | Paper |
| Lower bounds for language recognition on two-dimensional alternating multihead machines | 1989-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3832044 | 1989-01-01 | Paper |
| Tradeoffs for language recognition on alternating machines | 1989-01-01 | Paper |
| A leaf-time hierarchy of two-dimensional alternating turing machines | 1989-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3468610 | 1989-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3827543 | 1989-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3787930 | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3827544 | 1988-01-01 | Paper |
| The advantages of a new approach to defining the communication complexity for VLSI | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3809264 | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3809265 | 1988-01-01 | Paper |
| The advantages of a new approach to defining the communication complexity for VLSI | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3795232 | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3795614 | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3817620 | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3758246 | 1987-01-01 | Paper |
| Reversal-bounded nondeterministic multicounter machines and complementation | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3785943 | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3756527 | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3780434 | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3725549 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3768423 | 1986-01-01 | Paper |
| Communication complexity hierarchy | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3753482 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3746886 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3751041 | 1986-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3768406 | 1986-01-01 | Paper |
| Fooling a two-way nondeterministic multihead automaton with reversal number restriction | 1985-01-01 | Paper |
| Alternating multicounter machines with constant number of reversals | 1985-01-01 | Paper |
| On the power of alternation in automata theory | 1985-01-01 | Paper |
| Linear lower bounds on unbounded fan-in Boolean circuits | 1985-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3702514 | 1985-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3742753 | 1985-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3702513 | 1985-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3693450 | 1985-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5186738 | 1985-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3335687 | 1984-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3687716 | 1984-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3704912 | 1984-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3216143 | 1984-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3339318 | 1984-01-01 | Paper |
| One way multihead deterministic finite automata | 1983-01-01 | Paper |
| One-way simple multihead finite automata are not closed under concatenation | 1983-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3945614 | 1982-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3925894 | 1981-01-01 | Paper |
