Arrow Research search

Author name cluster

Stephan Waack

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.

10 papers
2 author rows

Possible papers

10

EUMAS Conference 2016 Conference Paper

Agent-Based Simulation for Software Development Processes

  • Tobias Ahlbrecht
  • Jürgen Dix
  • Niklas Fiekas
  • Jens Grabowski
  • Verena Herbold
  • Daniel Honsel
  • Stephan Waack
  • Marlon Welter

Abstract Software development is a costly process and requires serious quality control on the management level: Managing a project with more than 10 programmers over several years is a highly nontrivial task. We are building tools for helping the manager to predict the future development of the project based on certain adjustable parameters. The main idea is to view the software process as agent-based simulation in a multiagent system (MAS). This approach requires combining three different areas: (1) mining patterns from past projects, (2) modeling the software development process in a multiagent environment, and (3) running the simulation on a scalable multiagent platform.

Details DOI

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 2003 Conference Paper

Lower Bounds for General Graph-Driven Read-Once Parity Branching Programs

  • Henrik Brosenne
  • Matthias Homeister
  • Stephan Waack

Abstract We prove the first exponential lower bounds on the size of graph–driven read–once parity branching programs. The functions used are linear codes, permutation matrices and a function that has small unrestricted read–once parity branching programs. Moreover, we characterize all BP1s that are guided by graph orderings. The latter is the case if and only if for each input there is a variable ordering that is compatible with each computation path for the input.

Details

MFCS Conference 2001 Conference Paper

Graph-Driven Free Parity BDDs: Algorithms and Lower Bounds

  • Henrik Brosenne
  • Matthias Homeister
  • Stephan Waack

Abstract We investigate graph-driven free parity BDDs, which strictly generalize the two well-known models parity OBDDs and graph-driven free BDDs. The first main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a graph-driven free parity BDD. The second main result is an exponential lower bound on the size of graph-driven free parity BDD for linear code functions.

Details

MFCS Conference 1991 Conference Paper

Upper and Lower Bounds for Certain Graph-Accessibility Problems on Bounded Alternating Omega-Branching Programs

  • Christoph Meinel
  • Stephan Waack

Abstract In the following we investigate the computational complexity of various ω- GRAPH ACCESSIBILITY PROBLEMs on the most general restricted type of ω-branching programs for for which, up to now, exponential lower bounds on the size can be proved. By means of exponential lower bounds on various ranks of certain communication matrices we prove that ωGRAPH ACCESSIBILITY PROBLEMs can not be computed by bounded alternating ω-branching programs within polynomial size In contrast, ω- GRAPH ACCESSIBILITY PROBLEMs restricted to monotone graphs can by computed by such devices.

Details

FOCS Conference 1991 Conference Paper

Variation Ranks of Communication Matrices and Lower Bounds for Depth Two Circuits Having Symmetric Gates with Unbounded Fan-In

  • Matthias Krause 0001
  • Stephan Waack

An exponential lower bound for depth two circuits with arbitrary symmetric gates in the bottom level and with a MOD/sub m/-gate in the top level is proved. This solves a problem posed by R. Smolensky (1990). The method uses the variation rank of communication matrices. A variant of this method is used for deriving lower bounds for the size of depth-two circuits having a threshold gate at the top. >

Details