Arrow Research search

Author name cluster

Pekka Orponen

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.

13 papers
2 author rows

Possible papers

13

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).

Details

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.

Details

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.

PDF Details