| Publication | Date of Publication | Type |
|---|
Probabilism versus Alternation for Automata
Adventures Between Lower Bounds and Higher Altitudes | 2023-06-30 | 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 |
A comparison of two lower bound methods for communication complexity (extended abstract)
Mathematical Foundations of Computer Science 1994 | 2022-08-18 | Paper |
On the complexity of approximating the independent set problem (extended abstract)
STACS 89 | 2022-08-16 | Paper |
Rounds versus time for the two person pebble game (extended abstract)
STACS 89 | 2022-08-16 | Paper |
Randomized variants of Johnson's algorithm for MAX SAT
| 2017-09-29 | Paper |
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
SIAM Journal on Computing | 2017-06-28 | Paper |
On the optimality of Bellman-Ford-Moore shortest path algorithm
Theoretical Computer Science | 2016-04-13 | Paper |
Cutting planes cannot approximate some integer programs
Operations Research Letters | 2012-09-18 | Paper |
Fast equality test for straight-line compressed strings
Information Processing Letters | 2012-07-20 | Paper |
Ambiguity and communication
| 2012-04-24 | Paper |
Min-rank conjecture for log-depth circuits
Journal of Computer and System Sciences | 2012-01-11 | Paper |
Yet harder knapsack problems
Theoretical Computer Science | 2012-01-09 | Paper |
Ambiguity and communication
Theory of Computing Systems | 2011-05-23 | Paper |
On probabilistic pushdown automata
Information and Computation | 2010-08-19 | 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 |
FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
Lecture Notes in Computer Science | 2009-08-06 | 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 |
Regular Expressions and NFAs Without ε-Transitions
STACS 2006 | 2008-03-19 | Paper |
Minimizing nfa's and regular expressions
Journal of Computer and System Sciences | 2007-08-23 | Paper |
Comparing the size of NFAs with and without \(\epsilon\)-transitions
Theoretical Computer Science | 2007-07-16 | Paper |
On the Greedy Superstring Conjecture
SIAM Journal on Discrete Mathematics | 2007-05-22 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
On the power of randomized multicounter machines
Theoretical Computer Science | 2005-02-22 | 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 |
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 |
Nondeterministic Communication with a Limited Number of Advice Bits
SIAM Journal on Computing | 2004-01-08 | Paper |
scientific article; zbMATH DE number 1870232 (Why is no real title available?)
| 2003-06-26 | 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 |
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 |
scientific article; zbMATH DE number 1670824 (Why is no real title available?)
| 2001-11-11 | Paper |
scientific article; zbMATH DE number 1405658 (Why is no real title available?)
| 2000-04-25 | 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 |
A comparison of two lower-bound methods for communication complexity
Theoretical Computer Science | 1997-02-27 | Paper |
scientific article; zbMATH DE number 953286 (Why is no real title available?)
| 1996-12-01 | Paper |
scientific article; zbMATH DE number 774000 (Why is no real title available?)
| 1996-04-16 | Paper |
Communication complexity of matrix computation over finite fields
Mathematical Systems Theory | 1995-06-08 | Paper |
scientific article; zbMATH DE number 683527 (Why is no real title available?)
| 1994-11-08 | Paper |
Two tapes versus one for off-line Turing machines
Computational Complexity | 1994-05-08 | Paper |
The Probabilistic Communication Complexity of Set Intersection
SIAM Journal on Discrete Mathematics | 1993-04-01 | Paper |
On the complexity of approximating the independent set problem
Information and Computation | 1992-06-28 | Paper |
The communication complexity of several problems in matrix computation
Journal of Complexity | 1992-06-28 | Paper |
On the power of white pebbles
Combinatorica | 1992-06-27 | Paper |
The complexity of matrix transposition on one-tape off-line Turing machines
Theoretical Computer Science | 1991-01-01 | Paper |
Rounds versus time for the two person pebble game
Information and Computation | 1990-01-01 | Paper |
On the Performance of the Minimum Degree Ordering for Gaussian Elimination
SIAM Journal on Matrix Analysis and Applications | 1990-01-01 | Paper |
Parallel computation with threshold functions
Journal of Computer and System Sciences | 1988-01-01 | Paper |
Checking local optimality in constrained quadratic programming is NP- hard
Operations Research Letters | 1988-01-01 | Paper |
Lower bounds on communication complexity
Information and Computation | 1987-01-01 | Paper |
scientific article; zbMATH DE number 3988712 (Why is no real title available?)
| 1986-01-01 | Paper |
scientific article; zbMATH DE number 3988711 (Why is no real title available?)
| 1986-01-01 | Paper |
A family of graphs with expensive depth-reduction
Theoretical Computer Science | 1982-01-01 | Paper |
scientific article; zbMATH DE number 3802825 (Why is no real title available?)
| 1982-01-01 | Paper |
scientific article; zbMATH DE number 3716807 (Why is no real title available?)
| 1981-01-01 | Paper |
