Author name cluster

Beate Bollig

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers

2 author rows

TCS Journal 2014 Journal Article

Implicit computation of maximum bipartite matchings by sublinear functional operations

Beate Bollig
Marc Gillé
Tobias Pröger

The maximum bipartite matching problem, an important problem in combinatorial optimization, has been studied for a long time. In order to solve problems for very large structured graphs in reasonable time and space, implicit algorithms have been investigated. Any object to be manipulated is binary encoded and problems have to be solved mainly by functional operations on the corresponding Boolean functions. OBDDs are a popular data structure for Boolean functions, therefore, OBDD-based algorithms have been used as a heuristic approach to handle large input graphs. Here, two OBDD-based maximum bipartite matching algorithms are presented, which are the first ones using only a sublinear number of operations (with respect to the number of vertices of the input graph) for a problem unknown to be in NC, the complexity class that contains all problems computable in deterministic polylogarithmic time with polynomially many processors. Furthermore, the algorithms are experimentally evaluated.

Details DOI

I&C Journal 2014 Journal Article

On efficient implicit OBDD-based algorithms for maximal matchings

Beate Bollig
Tobias Pröger

The maximal matching problem, i. e. , the computation of a matching that is not a proper subset of another matching, is a fundamental optimization problem, and maximal matching algorithms have been used as submodules for problems like maximal node-disjoint paths or maximum flow. Since in some applications very large graphs have to be processed, a research branch has emerged which is concerned with the design and analysis of implicit algorithms for classical graph problems. Input graphs are given as characteristic Boolean functions of their edge sets, and problems have to be solved by functional operations. As OBDDs, which are closely related to deterministic finite automata, are a well-known data structure for Boolean functions, OBDD-based algorithms are used as a heuristic approach to handle very large graphs. Here, an implicit OBDD-based maximal matching algorithm is presented that uses only a polylogarithmic number of functional operations with respect to the number of vertices of the input graph. In order to investigate the algorithm's behavior on large and structured networks, it is analyzed on grid graphs. It is shown that the overall running time and the space requirement is also polylogarithmic. Furthermore, we present another algorithm similar to the well-known Karp–Sipser approach and we investigate the representation size of maximal matchings.

Details DOI

TCS Journal 2012 Journal Article

On symbolic OBDD-based algorithms for the minimum spanning tree problem

Beate Bollig

The minimum spanning tree problem is one of the most fundamental algorithmic graph problems and OBDDs are a very common dynamic data structure for Boolean functions. Since in some applications graphs become larger and larger, a research branch has emerged which is concerned with the design and analysis of so-called symbolic algorithms for classical graph problems on OBDD-represented graph instances. Here, a symbolic minimum spanning tree algorithm using O ( log 3 | V | ) functional operations is presented, where V is the set of vertices of the input graph. Moreover, the computation of the transitive closure is investigated and it is proved that there can be an exponential blow-up from input to output size. Furthermore, answering an open problem posed by Sawitzki [37] it is shown that every symbolic OBDD-based algorithm for the minimum spanning tree problem needs exponential space (with respect to the OBDD size of the input graph). This result even holds for planar input graphs.

Details DOI

I&C Journal 2011 Journal Article

Larger lower bounds on the OBDD complexity of integer multiplication

Beate Bollig

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Recently, the question whether the OBDD complexity of the most significant bit of integer multiplication is exponential has been answered affirmatively. In this paper a larger general lower bound is presented using a simpler proof. Furthermore, we prove a larger lower bound for the variable order assumed to be one of the best ones for the most significant bit. Moreover, the best known lower bound on the OBDD complexity for the so-called graph of integer multiplication is improved.

Details DOI

TCS Journal 2011 Journal Article

On the OBDD complexity of the most significant bit of integer multiplication

Beate Bollig

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations. Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, and symbolic graph algorithms. In this paper it is shown that the OBDD complexity of the most significant bit of integer multiplication is exponential answering an open question posed by Wegener (2000) [18].

Details DOI

MFCS Conference 2010 Conference Paper

Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks

Beate Bollig

Abstract The maximum flow problem is a central problem in graph algorithms and optimization and OBDDs are one of the most common dynamic data structures for Boolean functions. Since in some applications graphs become larger and larger, a research branch has emerged which is concerned with the theoretical design and analysis of symbolic algorithms for classical graph problems on OBDD-represented graph instances. The algorithm for the maximum flow problem in 0-1 networks by Hachtel and Somenzi (1997) has been one of the first of these symbolic algorithms. Typically problems get harder when their input is represented symbolically, nevertheless not many concrete non-trivial lower bounds are known. Here, answering an open question posed by Sawitzki (2006) the first exponential lower bound on the space complexity of OBDD-based algorithms for the maximum flow problem in 0-1 networks is presented.

Details

TCS Journal 2006 Journal Article

Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication

Beate Bollig
Stephan Waack
Philipp Woelfel

Branching programs are a well-established computation model for Boolean functions, especially read-once branching programs have been studied intensively. Exponential lower bounds for read-once branching programs are known for a long time. On the other hand, the problem of proving superpolynomial lower bounds for parity read-once branching programs is still open. In this paper restricted parity read-once branching programs are considered and an exponential lower bound on the size of the so-called well-structured parity graph-driven read-once branching programs for integer multiplication is proven. This is the first strongly exponential lower bound on the size of a parity nonoblivious read-once branching program model for an explicitly defined Boolean function. In addition, more insight into the structure of integer multiplication is yielded.

Details DOI

MFCS Conference 2002 Conference Paper

A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications

Beate Bollig
Philipp Woelfel

Abstract We present a new lower bound technique for a restricted Branching Program model, namely for nondeterministic graph-driven read-once Branching Programs (g. d. -BP1s). The technique is derived by drawing a connection between ω -nondeterministic g. d. -BP1s and ω-nondeterministic communication complexity (for the nondeterministic acceptance modes \( \omega \in \{ \vee, \wedge, \oplus \} ) \) We apply the technique in order to prove an exponential lower bound for integer multiplication for ω-nondeterministic well-structured g. d. -BP1s. (For ω = ⊕ an exponential lower bound was already obtained in [ 5 ] by using a different technique.) Further, we use the lower bound technique to prove for an explicitly defined fnction which can be represented by polynomial size ω-nondeterministic BP1s that it has exponential complexity in the ω-nondeterministic well-structured g. d. -BP1 model for \( \omega \in \{ \vee, \oplus \} \). This answers an open question from Brosenne, Homeister, and Waack [ 7 ], whether the nondeterministic BP1 model is in fact more powerful than the well-structured graph-driven variant.

Details

I&C Journal 2002 Journal Article

On the Nonapproximability of Boolean Functions by OBDDs and Read-k-Times Branching Programs

Beate Bollig
Martin Sauerhoff
Ingo Wegener

Branching programs are considered as a nonuniform model of computation in complexity theory as well as a data structure for boolean functions in several applications. In many applications (e. g. , verification), exact representations are required. For learning boolean functions f on the basis of classified examples, it is sufficient to produce the representation of a function g approximating f. This motivates the investigation of the size of the smallest branching program approximating f. Although several nonapproximability results are contained in the papers on randomized branching programs, these results often do not work for the uniform distribution (which is the most important one in applications). Here, the following nonapproximability results are presented. (1) It is proven that two simple and well-known functions from the branching program literature require exponential size to be approximated with respect to the uniform distribution by OBDDs, which are the most important type of branching programs in applications. (2) The first truly exponential lower bound on the size of approximating syntactic read-k-times branching programs with respect to the uniform distribution and error probability 1/2−2−Ω(n), n the input size, is shown. In order to improve upon the best previous results for error probabilities smaller than 1/3, a strong combinatorial lemma from a paper of Ajtai on linear-length branching programs is exploited.

Details DOI

STOC Conference 2001 Conference Paper

A read-once branching program lower bound of Omega(2 n/4 ) for integer multiplication using universal

Beate Bollig
Philipp Woelfel

Branching programs (BPs) are a well-established computation and representation model for Boolean functions. Especially read-once branching programs (BP1s) have been studied intensively. Exponential lower bounds on the BP1 complexity of explicit functions have been known for a long time. Nevertheless, the proof of exponential lower bounds on the read-once branching program size of selected functions is sometimes difficult. Motivated by the applications the BP1 complexity of fundamental functions is of interest. It took quite a long time until Ponzio [16, 17] was able to prove a bound of 2^{Ω(\sqrt{n})} for integer multiplication. Combining results and methods for universal hashing with lower bound techniques for BP1s a lower bound of Ω(2^{n/4}) on the size of BP1s for integer multiplication is presented in this paper.

Details

MFCS Conference 2000 Conference Paper

Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Beate Bollig

Abstract Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, i. e. , the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once branching programs are defined and a lower bound method is presented. Furthermore, the first exponential lower bound for integer multiplication on the size of a nondeterministic nonoblivious read-once branching program model is proven.

Details

I&C Journal 1998 Journal Article

Completeness and Non-Completeness Results with Respect to Read-Once Projections

Beate Bollig
Ingo Wegener

Several models of restricted branching programs or binary decision diagrams have a lot of applications in hardware verification. These models are investigated here from a complexity theoretical viewpoint. Because of depth restrictions projections are not suitable as reduction type and have to be restricted to read-once projections. Several types of polynomial-size binary decision diagrams have complete problems with respect to polynomial read-once projections. On the contrary it can be proved that the classes of polynomial-size decision trees and polynomial-size read-once branching programs or free binary decision diagrams do not have such complete problems.

Details DOI

TCS Journal 1998 Journal Article

Hierarchy theorems for kOBDDs and kIBDDs

Beate Bollig
Martin Sauerhoff
Detlef Sieling
Ingo Wegener

Almost the same types of restricted branching programs (or binary decision diagrams BDDs) are considered in complexity theory and in applications like hardware verification. These models are read-once branching programs (free BDDs) and certain types of oblivious branching programs (ordered and indexed BDDs with k layers). The complexity of the satisfiability problem for these restricted branching programs is investigated and tight hierarchy results are proved for the classes of functions representable by k layers of ordered or indexed BDDs of polynomial size.

Details DOI

MFCS Conference 1997 Conference Paper

Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams

Beate Bollig
Ingo Wegener

Abstract Ordered binary decision diagrams (OBDDs) have found a lot of applications in the verification of combinational and sequential circuits, protocols, and the synthesis and analysis of systems. The applications are limited, since the expressive power of polynomial-size OBDDs is too restricted. Therefore, several more general BDD models are used. Partitioned OBDDs are an OBDD model allowing a restricted use of nondeterminism and different variable orderings. They are restricted enough such that the essential operations can be performed efficiently and they allow polynomial-size representations for many more functions than OBDDs. Here the expressive power of polynomial-size partitioned OBDDs is investigated. A tight hierarchy with respect to the number of parts in the partition is proved and partitioned OBDDs are compared with other BDD models.

Details