Ingo Wegener
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Ingo Wegener has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Matthias Krause
Theoretische Informatik, University of Mannheim, 68131 Mannheim, Germany
2 shared publications - Philipp Woelfel
Department of Computer Science, University of Calgary, Calgary, Canada
2 shared publications - Jonathan E. Rowe
University of Birmingham
1 shared publication - Martin Dietzfelbinger
Technische Universität Ilmenau
1 shared publication - Petr Savický
Institute of Computer Science, Academy of Sciences of Czech Republic, Pod vodárenskou věžı́ 2, 182 07 Praha 8, Czech Republic
1 shared publication - Tobias Storch
University of Dortmund
1 shared publication
Latest Publications
- 28 June 2010
- Published by Cambridge University Press (CUP)
- p. 506-530
Circuit Complexity
Introduction The theory on efficient algorithms and complexity theory is software oriented. Their hardware-oriented counterpart is the theory on combinational circuits or, simply, circuits. The main difference is that circuits are a nonuniform model. A circuit is designed for one Boolean function f Є Bn,m , that is, f: {0, 1} n → {0, 1} m . However, most circuit designs lead to sequences of circuits realizing a sequence of functions. Typical adders are sequences of adders, one for each input length. If there is an efficient algorithm computing for each n the circuit for input length n, the circuit family is called uniform. However, for basic functions like arithmetic functions or storage access the circuit model is more adequate than software models. Moreover, circuits are a very simple and natural computation model reflecting all aspects of efficiency. A circuit model needs a basis of elementary functions that can be realized by simple gates. In the basic circuitmodel, a basis is a finite set. Then a circuit for input size n is a finite sequence of instructions or gates and, therefore, a straight-line program: the ith instruction consists of a function g from the chosen basis and, if g Є Bj ≔ Bj,1 , a sorted list I i,1, …, Ii, j of inputs. The constants 0 and 1, the variables x 1, …, x n , and the results r1, …, r i–1 of the first i – 1 instructions are possible inputs.
- 28 June 2010
- Published by Cambridge University Press (CUP)
- p. 506-530
Circuit Complexity
Introduction The theory on efficient algorithms and complexity theory is software oriented. Their hardware-oriented counterpart is the theory on combinational circuits or, simply, circuits. The main difference is that circuits are a nonuniform model. A circuit is designed for one Boolean function f Є Bn,m , that is, f: {0, 1} n → {0, 1} m . However, most circuit designs lead to sequences of circuits realizing a sequence of functions. Typical adders are sequences of adders, one for each input length. If there is an efficient algorithm computing for each n the circuit for input length n, the circuit family is called uniform. However, for basic functions like arithmetic functions or storage access the circuit model is more adequate than software models. Moreover, circuits are a very simple and natural computation model reflecting all aspects of efficiency. A circuit model needs a basis of elementary functions that can be realized by simple gates. In the basic circuitmodel, a basis is a finite set. Then a circuit for input size n is a finite sequence of instructions or gates and, therefore, a straight-line program: the ith instruction consists of a function g from the chosen basis and, if g Є Bj ≔ Bj,1 , a sorted list I i,1, …, Ii, j of inputs. The constants 0 and 1, the variables x 1, …, x n , and the results r1, …, r i–1 of the first i – 1 instructions are possible inputs.
- 7 August 2008
- Published by Springer Nature
- p. 517-527
Metropolis Versus Simulated Annealing and the Black-Box-Complexity of Optimization Problems
- 7 August 2008
- Published by Springer Nature
- p. 517-527
Metropolis Versus Simulated Annealing and the Black-Box-Complexity of Optimization Problems
- Open Access
Tight Bounds for Blind Search on the Integers
We analyze a simple random process in which a token is moved in the interval $A=\{0,...,n\$: Fix a probability distribution $\mu$ over $\{1,...,n\$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $\mu$. If the token is in position $a\geq d$, then it is moved to position $a-d$. Otherwise it stays put. Let $T$ be the number of rounds until the token reaches position 0. We show tight bounds for the expectation of $T$ for the optimal distribution $\mu$. More precisely, we show that $\min_\mu\{E_\mu(T)\=\Theta((\log n)^2)$. For the proof, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over $[0,1]$ with a ``blind'' optimization strategy.Open AccessTight Bounds for Blind Search on the Integers
We analyze a simple random process in which a token is moved in the interval $A=\{0,...,n\$: Fix a probability distribution $\mu$ over $\{1,...,n\$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $\mu$. If the token is in position $a\geq d$, then it is moved to position $a-d$. Otherwise it stays put. Let $T$ be the number of rounds until the token reaches position 0. We show tight bounds for the expectation of $T$ for the optimal distribution $\mu$. More precisely, we show that $\min_\mu\{E_\mu(T)\=\Theta((\log n)^2)$. For the proof, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over $[0,1]$ with a ``blind'' optimization strategy. - 5 October 2007
- Published by Springer Nature in computational complexity
- Vol. 16 (3) , 298-323
New Results on the Complexity of the Middle Bit of Multiplication
- 5 October 2007
- Published by Springer Nature in computational complexity
- Vol. 16 (3) , 298-323
New Results on the Complexity of the Middle Bit of Multiplication
- 3 August 2005
- Published by Elsevier in Information and Computation
- Vol. 201 (2) , 160-177
On the influence of the variable ordering for algorithmic learning using OBDDs
- 3 August 2005
- Published by Elsevier in Information and Computation
- Vol. 201 (2) , 160-177
On the influence of the variable ordering for algorithmic learning using OBDDs
- 1 April 2005
- Published by Springer Nature in Informatik Spektrum
- Vol. 28 (2) , 129-130
Rankings oder Ratings: Warum, wie und durch wen?
- 1 April 2005
- Published by Springer Nature in Informatik Spektrum
- Vol. 28 (2) , 129-130
Rankings oder Ratings: Warum, wie und durch wen?
- 1 June 2004
- Published by Elsevier in Theoretical Computer Science
- Vol. 320 (1) , 123-134
Real royal road functions for constant population size*1
- 1 June 2004
- Published by Elsevier in Theoretical Computer Science
- Vol. 320 (1) , 123-134
Real royal road functions for constant population size*1