| Publication | Date of Publication | Type |
|---|
Kolmogorov complexity and nondeterminism versus determinism for polynomial time computations
Theoretical Computer Science | 2024-10-01 | Paper |
Comparing descriptional and computational complexity of infinite words
Lecture Notes in Computer Science | 2024-01-29 | Paper |
Gossiping in vertex-disjoint paths mode in interconnection networks
Graph-Theoretic Concepts in Computer Science | 2024-01-05 | Paper |
Two-Way Non-Uniform Finite Automata
International Journal of Foundations of Computer Science | 2023-08-15 | Paper |
Optimal algorithms for broadcast and gossip in the edge-disjoint path modes
Algorithm Theory — SWAT '94 | 2022-12-09 | Paper |
Effective systolic algorithms for gossiping in cycles and two-dimensional grids
Fundamentals of Computation Theory | 2022-12-09 | Paper |
Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
Lecture Notes in Computer Science | 2022-11-09 | Paper |
Translating regular expressions into small \(\epsilon \)-free nondeterministic finite automata
Lecture Notes in Computer Science | 2022-11-09 | Paper |
Two lower bounds on distributive generation of languages
Mathematical Foundations of Computer Science 1994 | 2022-08-18 | Paper |
A nonlinear lower bound on the practical combinational complexity
STACS 92 | 2022-08-18 | Paper |
A comparison of two lower bound methods for communication complexity (extended abstract)
Mathematical Foundations of Computer Science 1994 | 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
Fundamenta Informaticae | 2021-05-20 | Paper |
On the advice complexity of the online dominating set problem
Theoretical Computer Science | 2021-03-09 | Paper |
Probability theory 2. From standard deviation to statistical inference
Grundstudium Mathematik | 2020-06-17 | Paper |
What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\)
Journal of Computer and System Sciences | 2019-11-29 | Paper |
Online graph coloring against a randomized adversary
International Journal of Foundations of Computer Science | 2018-07-24 | Paper |
On the size of two-way reasonable automata for the liveness problem
International Journal of Foundations of Computer Science | 2018-05-15 | Paper |
Alan Turing and the foundation of computer science
Turing’s Revolution | 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
Grundstudium Mathematik | 2017-06-30 | Paper |
Advice complexity of the online search problem
Lecture Notes in Computer Science | 2016-09-29 | Paper |
Approximation algorithms for the TSP with sharpened triangle inequality
Information Processing Letters | 2016-06-16 | Paper |
Online graph coloring with advice and randomized adversary (extended abstract)
Lecture Notes in Computer Science | 2016-03-10 | Paper |
On the power of laconic advice in communication complexity
Lecture Notes in Computer Science | 2016-03-10 | Paper |
The complexity of paging against a probabilistic adversary
Lecture Notes in Computer Science | 2016-03-10 | Paper |
On the size of two-way reasonable automata for the liveness problem
Developments in Language Theory | 2015-11-10 | Paper |
A technique to obtain hardness results for randomized online algorithms -- a survey
Computing with New Resources | 2015-09-08 | Paper |
Online coloring of bipartite graphs with and without advice
Algorithmica | 2015-01-19 | Paper |
On the power of advice and randomization for the disjoint path allocation problem
SOFSEM 2014: Theory and Practice of Computer Science | 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
Theoretical Computer Science | 2014-12-02 | Paper |
On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
Theoretical Computer Science | 2014-10-06 | Paper |
The string guessing problem as a method to prove lower bounds on the advice complexity
Theoretical Computer Science | 2014-10-06 | Paper |
Determinism vs. nondeterminism for two-way automata: representing the meaning of states by logical formulæ
International Journal of Foundations of Computer Science | 2014-08-04 | Paper |
On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
Lecture Notes in Computer Science | 2013-06-11 | Paper |
The string guessing problem as a method to prove lower bounds on the advice complexity (extended abstract)
Lecture Notes in Computer Science | 2013-06-11 | Paper |
Determinism vs. nondeterminism for two-way automata. Representing the meaning of states by logical formulæ
Developments in Language Theory | 2012-11-02 | Paper |
On the power of randomness versus advice in online computation
Lecture Notes in Computer Science | 2012-11-01 | Paper |
Online coloring of bipartite graphs with and without advice
Lecture Notes in Computer Science | 2012-09-25 | Paper |
On the approximability and hardness of minimum topic connected overlay and its special instances
Theoretical Computer Science | 2012-05-30 | Paper |
Steiner tree reoptimization in graphs with sharpened triangle inequality
Journal of Discrete Algorithms | 2012-05-11 | Paper |
| Ambiguity and communication | 2012-04-24 | Paper |
On the Hardness of Reoptimization with Multiple Given Solutions
Fundamenta Informaticae | 2011-11-22 | Paper |
On the approximability of minimum topic connected overlay and its special instances
Mathematical Foundations of Computer Science 2011 | 2011-08-17 | Paper |
Knowing all optimal solutions does not help for TSP reoptimization
Computation, Cooperation, and Life | 2011-06-24 | Paper |
Improved approximations for hard optimization problems via problem instance classification
Lecture Notes in Computer Science | 2011-05-27 | Paper |
Ambiguity and communication
Theory of Computing Systems | 2011-05-23 | Paper |
| scientific article; zbMATH DE number 5859273 (Why is no real title available?) | 2011-03-01 | Paper |
| Computability. Logic, reasoning, computer and Assembler, infinity, limits of automatizability. Textbook for class-room and self-study | 2011-02-17 | Paper |
| scientific article; zbMATH DE number 5822605 (Why is no real title available?) | 2010-12-02 | Paper |
Information complexity of online problems
Mathematical Foundations of Computer Science 2010 | 2010-09-03 | Paper |
On the size of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks
SIAM Journal on Discrete Mathematics | 2010-08-27 | Paper |
On probabilistic pushdown automata
Information and Computation | 2010-08-19 | Paper |
Algorithmics -- is there hope for a unified theory? (Invited talk)
Computer Science – Theory and Applications | 2010-06-22 | Paper |
| scientific article; zbMATH DE number 5716807 (Why is no real title available?) | 2010-06-04 | Paper |
The Steiner tree reoptimization problem with sharpened triangle inequality (extended abstract)
Lecture Notes in Computer Science | 2010-05-28 | Paper |
Reoptimization of Steiner trees: changing the terminal set
Theoretical Computer Science | 2009-08-21 | Paper |
| Lower bounds on the size of sweeping automata | 2009-08-10 | Paper |
On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's
Theoretical Computer Science | 2009-08-07 | Paper |
On \(k\)-connectivity problems with sharpened triangle inequality
Journal of Discrete Algorithms | 2009-02-23 | Paper |
| scientific article; zbMATH DE number 5497557 (Why is no real title available?) | 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
Developments in Language Theory | 2008-10-30 | Paper |
Reoptimization of Steiner Trees
Algorithm Theory – SWAT 2008 | 2008-07-15 | Paper |
On the Hardness of Reoptimization
SOFSEM 2008: Theory and Practice of Computer Science | 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
Theory of Computing Systems | 2007-12-19 | Paper |
Efficient Algorithms for the Spoonerism Problem
Lecture Notes in Computer Science | 2007-11-15 | Paper |
On the Approximation Hardness of Some Generalizations of TSP
Algorithm Theory – SWAT 2006 | 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
Theoretical Computer Science | 2007-07-16 | Paper |
| scientific article; zbMATH DE number 5166135 (Why is no real title available?) | 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
Information and Computation | 2006-10-10 | Paper |
| scientific article; zbMATH DE number 5051559 (Why is no real title available?) | 2006-09-06 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
SOFSEM 2005: Theory and Practice of Computer Science
Lecture Notes in Computer Science | 2005-12-07 | Paper |
Design and analysis of randomized algorithms. Introduction to design paradigms.
Texts in Theoretical Computer Science. An EATCS Series | 2005-05-26 | Paper |
| scientific article; zbMATH DE number 2166299 (Why is no real title available?) | 2005-05-06 | Paper |
Stability of Approximation in Discrete Optimization
IFIP International Federation for Information Processing | 2005-04-29 | Paper |
Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
Texts in Theoretical Computer Science. An EATCS Series | 2005-04-27 | Paper |
Algorithmics for hard problems.
Texts in Theoretical Computer Science. An EATCS Series | 2005-04-26 | Paper |
On the power of randomized multicounter machines
Theoretical Computer Science | 2005-02-22 | Paper |
On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
Theoretical Computer Science | 2005-01-11 | Paper |
On multi-partition communication complexity
Information and Computation | 2004-11-12 | Paper |
| scientific article; zbMATH DE number 2087229 (Why is no real title available?) | 2004-08-11 | Paper |
On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
Journal of Computer and System Sciences | 2004-08-10 | Paper |
| scientific article; zbMATH DE number 2083798 (Why is no real title available?) | 2004-08-06 | Paper |
| scientific article; zbMATH DE number 2068876 (Why is no real title available?) | 2004-05-27 | Paper |
| scientific article; zbMATH DE number 2044495 (Why is no real title available?) | 2004-02-18 | Paper |
| scientific article; zbMATH DE number 2038729 (Why is no real title available?) | 2004-02-08 | Paper |
| scientific article; zbMATH DE number 2038700 (Why is no real title available?) | 2004-02-08 | Paper |
| scientific article; zbMATH DE number 1500530 (Why is no real title available?) | 2004-01-27 | Paper |
Nondeterministic Communication with a Limited Number of Advice Bits
SIAM Journal on Computing | 2004-01-08 | Paper |
Theoretical computer science. Introduction to automata, computability, complexity, algorithmics, randomization, communication, and cryptography.
Texts in Theoretical Computer Science. An EATCS Series | 2003-12-03 | Paper |
| scientific article; zbMATH DE number 2011856 (Why is no real title available?) | 2003-12-02 | Paper |
The power of nondeterminism and randomness for oblivious branching programs
Theory of Computing Systems | 2003-08-26 | Paper |
| scientific article; zbMATH DE number 1954373 (Why is no real title available?) | 2003-07-28 | Paper |
| scientific article; zbMATH DE number 1857650 (Why is no real title available?) | 2003-06-02 | Paper |
On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
Information and Computation | 2003-01-14 | Paper |
Communication complexity method for measuring nondeterminism in finite automata
Information and Computation | 2003-01-14 | Paper |
Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
Theoretical Computer Science | 2002-08-05 | Paper |
Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
Journal of Computer and System Sciences | 2002-07-02 | Paper |
On the power of Las Vegas II: Two-way finite automata
Theoretical Computer Science | 2002-03-03 | Paper |
| scientific article; zbMATH DE number 1688365 (Why is no real title available?) | 2002-01-09 | Paper |
| Algorithmic concepts of informatics. Computability, complexity theory, algorithmics, cryptography. An introduction | 2001-11-26 | Paper |
| scientific article; zbMATH DE number 1670824 (Why is no real title available?) | 2001-11-11 | Paper |
| scientific article; zbMATH DE number 1489999 (Why is no real title available?) | 2001-06-06 | Paper |
| scientific article; zbMATH DE number 1507218 (Why is no real title available?) | 2001-05-28 | Paper |
| scientific article; zbMATH DE number 1500514 (Why is no real title available?) | 2001-04-26 | Paper |
| scientific article; zbMATH DE number 1566497 (Why is no real title available?) | 2001-02-19 | Paper |
Communication Complexity and Lower Bounds on Multilective Computations
RAIRO - Theoretical Informatics and Applications | 2000-10-17 | Paper |
| scientific article; zbMATH DE number 1405658 (Why is no real title available?) | 2000-04-25 | Paper |
| scientific article; zbMATH DE number 1408349 (Why is no real title available?) | 2000-04-03 | Paper |
| scientific article; zbMATH DE number 1361468 (Why is no real title available?) | 1999-11-10 | Paper |
| scientific article; zbMATH DE number 1256774 (Why is no real title available?) | 1999-10-04 | Paper |
| scientific article; zbMATH DE number 1333610 (Why is no real title available?) | 1999-09-19 | Paper |
Optimal algorithms for broadcast and gossip in the edge-disjoint modes
Information and Computation | 1998-01-04 | Paper |
The complexity of systolic dissemination of information in interconnection networks
RAIRO - Theoretical Informatics and Applications | 1997-12-17 | Paper |
| scientific article; zbMATH DE number 1011685 (Why is no real title available?) | 1997-05-21 | Paper |
A nonlinear lower bound on the practical combinational complexity
Theoretical Computer Science | 1997-02-28 | Paper |
A comparison of two lower-bound methods for communication complexity
Theoretical Computer Science | 1997-02-27 | Paper |
| scientific article; zbMATH DE number 871242 (Why is no real title available?) | 1996-04-28 | Paper |
| scientific article; zbMATH DE number 857072 (Why is no real title available?) | 1996-04-09 | Paper |
On embeddings in cycles
Information and Computation | 1995-07-10 | Paper |
Note on optimal gossiping in some weak-connected graphs
Theoretical Computer Science | 1995-02-09 | Paper |
Optimal algorithms for dissemination of information in generalized communication modes
Discrete Applied Mathematics | 1994-12-11 | Paper |
Deterministic versus nondeterministic space in terms of synchronized alternating machines
Theoretical Computer Science | 1994-09-25 | Paper |
| scientific article; zbMATH DE number 512920 (Why is no real title available?) | 1994-06-20 | Paper |
Some hierarchies for the communication complexity measures of cooperating grammar systems
Theoretical Computer Science | 1994-05-15 | Paper |
Optimal algorithms for dissemination of information in some interconnection networks
Algorithmica | 1993-09-01 | Paper |
| scientific article; zbMATH DE number 176937 (Why is no real title available?) | 1993-05-18 | Paper |
| scientific article; zbMATH DE number 176141 (Why is no real title available?) | 1993-05-18 | Paper |
A note on realtime one-way synchronized alternating one-counter automata
Theoretical Computer Science | 1993-05-16 | Paper |
ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE
International Journal of Foundations of Computer Science | 1993-01-16 | Paper |
| scientific article; zbMATH DE number 79114 (Why is no real title available?) | 1992-12-14 | Paper |
Lower bounds on the area complexity of Boolean circuits
Theoretical Computer Science | 1992-09-27 | Paper |
| scientific article; zbMATH DE number 61460 (Why is no real title available?) | 1992-09-27 | Paper |
Abstract symbol systems (an exercise of the bottom-up approach in artificial intelligence)
Journal of Experimental & Theoretical Artificial Intelligence | 1992-08-13 | Paper |
Nonlinear lower bounds on the number of processors of circuits with sublinear separators
Information and Computation | 1992-06-28 | Paper |
| scientific article; zbMATH DE number 29610 (Why is no real title available?) | 1992-06-27 | Paper |
| scientific article; zbMATH DE number 17800 (Why is no real title available?) | 1992-06-26 | Paper |
| scientific article; zbMATH DE number 23771 (Why is no real title available?) | 1992-06-26 | Paper |
On the power of synchronization in parallel computations
Discrete Applied Mathematics | 1991-01-01 | Paper |
On problems for which no oracle can help
Mathematical Systems Theory | 1991-01-01 | Paper |
| scientific article; zbMATH DE number 4172378 (Why is no real title available?) | 1991-01-01 | Paper |
Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits
Information and Computation | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4213420 (Why is no real title available?) | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4104386 (Why is no real title available?) | 1990-01-01 | Paper |
| scientific article; zbMATH DE number 4172915 (Why is no real title available?) | 1990-01-01 | Paper |
Lower bounds for language recognition on two-dimensional alternating multihead machines
Journal of Computer and System Sciences | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4108150 (Why is no real title available?) | 1989-01-01 | Paper |
Tradeoffs for language recognition on alternating machines
Theoretical Computer Science | 1989-01-01 | Paper |
A leaf-time hierarchy of two-dimensional alternating turing machines
Theoretical Computer Science | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4135399 (Why is no real title available?) | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4102489 (Why is no real title available?) | 1989-01-01 | Paper |
| scientific article; zbMATH DE number 4051518 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4102490 (Why is no real title available?) | 1988-01-01 | Paper |
The advantages of a new approach to defining the communication complexity for VLSI
Theoretical Computer Science | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4078801 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4078802 (Why is no real title available?) | 1988-01-01 | Paper |
The advantages of a new approach to defining the communication complexity for VLSI
Theoretical Computer Science | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4060726 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4061153 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4090811 (Why is no real title available?) | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4007730 (Why is no real title available?) | 1987-01-01 | Paper |
Reversal-bounded nondeterministic multicounter machines and complementation
Theoretical Computer Science | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4049051 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4005620 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4043241 (Why is no real title available?) | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 3956444 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 4026854 (Why is no real title available?) | 1986-01-01 | Paper |
Communication complexity hierarchy
Theoretical Computer Science | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3990864 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3982518 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3988743 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 4026835 (Why is no real title available?) | 1986-01-01 | Paper |
Fooling a two-way nondeterministic multihead automaton with reversal number restriction
Acta Informatica | 1985-01-01 | Paper |
Alternating multicounter machines with constant number of reversals
Information Processing Letters | 1985-01-01 | Paper |
On the power of alternation in automata theory
Journal of Computer and System Sciences | 1985-01-01 | Paper |
Linear lower bounds on unbounded fan-in Boolean circuits
Information Processing Letters | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3928351 (Why is no real title available?) | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3978428 (Why is no real title available?) | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3928350 (Why is no real title available?) | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3918272 (Why is no real title available?) | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3894478 (Why is no real title available?) | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3867232 (Why is no real title available?) | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3911710 (Why is no real title available?) | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3932419 (Why is no real title available?) | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3881884 (Why is no real title available?) | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3872716 (Why is no real title available?) | 1984-01-01 | Paper |
One way multihead deterministic finite automata
Acta Informatica | 1983-01-01 | Paper |
One-way simple multihead finite automata are not closed under concatenation
Theoretical Computer Science | 1983-01-01 | Paper |
| scientific article; zbMATH DE number 3763331 (Why is no real title available?) | 1982-01-01 | Paper |
| scientific article; zbMATH DE number 3740784 (Why is no real title available?) | 1981-01-01 | Paper |
