Pekka Orponen

TCS Journal 2014 Journal Article

Editorial for Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities

• Amotz Bar-Noy
• Thomas Erlebach
• Magnús M. Halldórsson
• Sotiris Nikoletseas
• Pekka Orponen

MFCS Conference 2012 Conference Paper

Unordered Constraint Satisfaction Games

• Lauri Ahlroth
• Pekka Orponen

Abstract We consider two-player constraint satisfaction games on systems of Boolean constraints, in which the players take turns in selecting one of the available variables and setting it to true or false, with the goal of maximising (for Player I) or minimising (for Player II) the number of satisfied constraints. Unlike in standard QBF-type variable assignment games, we impose no order in which the variables are to be played. This makes the game setup more natural, but also more challenging to control. We provide polynomial-time, constant-factor approximation strategies for Player I when the constraints are parity functions or threshold functions with a threshold that is small compared to the arity of the constraints. Also, we prove that the problem of determining if Player I can satisfy all constraints is PSPACE-complete even in this unordered setting, and when the constraints are disjunctions of at most 6 literals (an unordered-game analogue of 6-QBF).

TCS Journal 2005 Journal Article

Exact and approximate balanced data gathering in energy-constrained sensor networks

• Patrik Floréen
• Petteri Kaski
• Jukka Kohonen
• Pekka Orponen

We consider the problem of gathering data from a wireless multi-hop network of energy-constrained sensor nodes to a common base station. Specifically, we aim to balance the total amount of data received from the sensor network during its lifetime against a requirement of sufficient coverage for all the sensor locations surveyed. Our main contribution lies in formulating this balanced data gathering task, studying the effects of balancing, and proposing an approximation algorithm for the problem. Based on an LP network flow formulation, we present experimental results on both optimal and approximate data routing designs, in open transmission ranges and with impenetrable obstacles between the nodes.

SAT Conference 2005 Conference Paper

Threshold Behaviour of WalkSAT and Focused Metropolis Search on Random 3-Satisfiability

• Sakari Seitz
• Mikko Alava
• Pekka Orponen

Abstract An important heuristic in local search algorithms for Satisfiability is focusing, i. e. restricting the selection of flipped variables to those appearing in presently unsatisfied clauses. We consider the behaviour on large randomly generated 3-SAT instances of two focused solution methods: WalkSAT and Focused Metropolis Search. The algorithms turn out to have qualitatively quite similar behaviour. Both are sensitive to the proper choice of their “noise” and “temperature” parameters, but with appropriately chosen values, both achieve solution times that scale linearly in the number of variables even for clauses-to-variables ratios α > 4. 2. This is much closer to the satisfiability transition threshold α c ≈ 4. 267 than has generally been assumed possible for local search algorithms.

TCS Journal 2003 Journal Article

Exponential transients in continuous-time Liapunov systems

• Jiřı́ Šı́ma
• Pekka Orponen

We consider the convergence behavior of a class of continuous-time dynamical systems corresponding to so-called symmetric Hopfield nets studied in neural networks theory. We prove that such systems may have transient times that are exponential in the system dimension (i. e. number of “neurons”), despite the fact that their dynamics are controlled by Liapunov functions. This result stands in contrast to many proposed uses of such systems in, e. g. combinatorial optimization applications, in which it is often implicitly assumed that their convergence is rapid. An additional interesting observation is that our example of an exponential-transient continuous-time system (a simulated binary counter) in fact converges more slowly than any discrete-time Hopfield system of the same representation size. This suggests that continuous-time systems may be worth investigating for gains in descriptional efficiency as compared to their discrete-time counterparts.

STOC Conference 2001 Conference Paper

Computing with continuous-time Liapunov systems

• Jirí Síma
• Pekka Orponen

We establish a fundamental result in the theory of computation by continuous-time dynamical systems, by showing that systems corresponding to so called continuous-time symmetric Hopfield nets are capable of general computation. More precisely, we prove that any function computed by a discrete-time asymmetric recurrent network of n threshold gates can also be computed by a continuous-time symmetrically-coupled Hopfield system of dimension 18 n +7. Moreover, if the threshold logic network has maximum weight w _{\max} and converges in discrete time t ^*, then the corresponding Hopfield system can be designed to operate in continuous time Θ( t ^*/ε), for any value 0<ε<0.0025 such that w _{\max}2^{3 n }\leq\ε 2^{1/ε}.

TCS Journal 1997 Journal Article

Computing with truly asynchronous threshold logic networks

• Pekka Orponen

We present simulation mechanisms by which any network of threshold logic units with either symmetric or asymmetric interunit connections (i. e. a symmetric or asymmetric “Hopfield net”) can be simulated on a network of the same type, but without any a priori constraints on the order of updates of the units. Together with earlier constructions, the results show that the truly asynchronous network model is computationally equivalent to the seemingly more powerful models with either ordered sequential or fully parallel updates.

NeurIPS Conference 1996 Conference Paper

On the Effect of Analog Noise in Discrete-Time Analog Computations

• Wolfgang Maass
• Pekka Orponen

We introduce a model for noise-robust analog computations with discrete time that is flexible enough to cover the most important concrete cases, such as computations in noisy analog neural nets and networks of noisy spiking neurons. We show that the presence of arbitrarily small amounts of analog noise reduces the power of analog computational models to that of finite automata, and we also prove a new type of upper bound for the VC-dimension of computational models with analog noise.

AIJ Journal 1996 Journal Article

Probably approximately optimal satisficing strategies

• Russell Greiner
• Pekka Orponen

A satisficing search problem consists of a set of probabilistic experiments to be performed in some order, seeking a satisfying configuration of successes and failures. The expected cost of the search depends both on the success probabilities of the individual experiments, and on the search strategy, which specifies the order in which the experiments are to be performed. A strategy that minimizes the expected cost is optimal. Earlier work has provided “optimizing functions” that compute optimal strategies for certain classes of search problems from the success probabilities of the individual experiments. We extend those results by providing a general model of such strategies, and an algorithm pao that identifies an approximately optimal strategy when the probability values are not known. The algorithm first estimates the relevant probabilities from a number of trials of each undetermined experiment, and then uses these estimates, and the proper optimizing function, to identify a strategy whose cost is, with high probability, close to optimal. We also show that if the search problem can be formulated as an and-or tree, then the pao algorithm can also “learn while doing”, i. e. gather the necessary statistics while performing the search.

MFCS Conference 1992 Invited Paper

Neural Networks and Complexity Theory

• Pekka Orponen

Abstract We survey some of the central results in the complexity theory of neural networks, with pointers to the literature.

AIJ Journal 1990 Journal Article

Dempster's rule of combination is #P-complete

• Pekka Orponen

We consider the complexity of combining bodies of evidence according to the rules of the Dempster-Shafer theory of evidence. We prove that, given as input a set of tables representing basic probability assignments m1, …, mn over a frame of discernment Θ, and a set A ⊆ Θ, the problem of computing the combined basic probability value (m1 ⊕ … ⊕ mn)(A) is #P-complete. As a corollary, we obtain that while the simple belief, plausibility, and commonality values Bel(A), Pl(A), and Q(A) can be computed in polynomial time, the problems of computing the combinations (Bel1 ⊕ … ⊕ Beln(A), (Pl1 ⊕ … ⊕ Pln)(A), and (Q1 ⊕ … ⊕ Qn)(A) are #P-complete.

TCS Journal 1986 Journal Article

A classification of complexity core lattices

• Pekka Orponen

Lynch (1975) has shown that every recursive set A not in P contains an infinite polynomial complexity core: a set of elements C ⊂ A such that any algorithm deciding A needs more than polynomial time almost everywhere on C. Actually, any A not in P contains infinitely many different cores, the collection of which forms a lattice under inclusion. We study the structure of this lattice, proving that, surprisingly, there are only three possibilities: assuming the lattice is not trivial (which happens if A is in P), its shape depends only on whether A is ‘almost P-immune’ or not. It is known that the natural intractable sets usually do not have this property.

MFCS Conference 1984 Conference Paper

The Structure of Polynomial Complexity Cores (Extended Abstract)

• Pekka Orponen
• Uwe Schöning