Catálogo de publicaciones - libros

Many models in theoretical computer science allow for computations or representations where the answer is only slightly biased in the right direction. The best-known of these is the complexity class PP, for “probabilistic polynomial time”. A language is in PP if there is a randomized polynomial-time Turing machine whose acceptance probability is greater than 1/2 if, and only if, its input is in the language.

Most computational complexity classes have an analogous class in communication complexity. The class PP in fact has two, a version with weakly restricted bias called PPcc, and a version with unrestricted bias called UPPcc. Ever since their introduction by Babai, Frankl, and Simon in 1986, it has been open whether these classes are the same. We show that PPcc is strictly included in UPPcc. Our proof combines a query complexity separation due to Beigel with a technique of Razborov that translates the acceptance probability of quantum protocols to polynomials. We will discuss some complexity theoretical consequences of this separation. This presentation is bases on joined work with Nikolay Vereshchagin and Ronald de Wolf.

A minimal perfect hash function for a set  ⊆  of size is a function that is one-to-one on . The complexity measures of interest are storage space for , evaluation time (which should be constant), and construction time. The talk gives an overview of several recent randomized constructions of minimal perfect hash functions, leading to space-efficient solutions that are fast in practice. A central issue is a method (“split-and-share”) that makes it possible to assume that fully random (hash) functions are available.

Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published “folk theorem” proving that quantum finite automata with mixed states are no more than super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable.

We prove that there is an infinite sequence of distinct integers such that there are languages such that there are quantum finite automata with mixed states with 5 states recognizing the language with probability while any deterministic finite automaton recognizing needs to have at least states.

Unfortunately, the alphabet for these languages grows with . In order to prove a similar result for languages in a fixed alphabet we consider a counterpart of Hamming codes for permutations of finite sets, i.e. sets of permutations such that any two distinct permutations in the set have Hamming distance at least . The difficulty arises from the fact that in the traditional Hamming codes for binary strings positions in the string are independent while positions in a permutation are not independent. For instance, any two permutations of the same set either coinside or their Hamming distance is at least 2. The main combinatorial problem still remains open.

We consider applications of probabilistic techniques in the framework of algorithmic game theory. We focus on three distinct case studies: (i) The exploitation of the probabilistic method to demonstrate the existence of approximate Nash equilibria of logarithmic support sizes in bimatrix games; (ii) the analysis of the statistical conflict that mixed strategies cause in network congestion games; (iii) the effect of coalitions in the quality of congestion games on parallel links.

Devices connected wirelessly, in various forms including computers, hand-held devices, networks, and embedded systems, are expected to become ubiquitous all around us. Wireless networks pose interesting new challenges, some of which do not arise in standard (wired) networks. This survey discusses some key probabilistic notions – both randomized algorithms and probabilistic analysis – in wireless networking.

We initiate studying the convergence time to Nash equilibria in player-specific singleton congestion games. We consider simple games that have natural representations as graphs as we assume that each player chooses between two resources. We are not able to present an analysis for general graphs. However, we present first results for interesting classes of graphs. For the class of games that are represented as trees, we show that every best-response schedule terminates after () steps. We also consider games that are represented as circles. We show that deterministic best response schedules may cycle, whereas the random best response schedule, which selects the next player to play a best response uniformly at random, terminates after () steps in expectation. These results imply that in player-specific congestion games in which each player chooses between two resources, and each resource is allocated by at most two players, the random best response schedule terminates quickly. Our analysis reveals interesting relationships between random walks on lines and the random best response schedule.

The is a network model introduced recently by Frieze et al. It considers wireless networks in which the underlying environment has a large number of obstacles and the communication can only take place between objects that are and are to one another. To capture the main properties of this model, Frieze et al. proposed a new in which nodes are randomly placed on an × grid and a node can communicate with all the nodes that are in at most a certain fixed distance and which are in the same row or column.

Frieze et al. concentrated their study on basic structural properties of the random line-of-sight networks and in this paper we focus on their communication aspects in the scenario of ad-hoc radio communication networks. We present efficient algorithms for two fundamental communication problems of and in the classical ad-hoc radio communication model adjusted to random line-of-sight networks.

In the layered-graph query model of network discovery, a query at a node  of an undirected graph discovers all edges and non-edges whose endpoints have different distance from . We study the number of queries at randomly selected nodes that are needed for approximate network discovery in Erdős-Rényi random graphs . We show that a constant number of queries is sufficient if is a constant, while () queries are needed if  = /, for arbitrarily small choices of  = 3 / (6 · + 5) with  ∈ ℕ. Note that > 0 is a constant depending only on . Our proof of the latter result yields also a somewhat surprising result on pairwise distances in random graphs which may be of independent interest: We show that for a random graph  with  = /, for arbitrarily small choices of > 0 as above, in any constant cardinality subset of the nodes the pairwise distances are all identical with high probability.

Motivated by an application in project portfolio analysis under uncertainty, we develop an algorithm S-VNS for solving stochastic combinatorial optimization (SCO) problems based on the Variable Neighborhood Search (VNS) metaheuristic, and show its theoretical soundness by a mathematical convergence result. S-VNS is the first general-purpose algorithm for SCO problems using VNS. It combines a classical VNS search strategy with a sampling approach with suitably increasing sample size. After the presentation of the algorithm, the considered application problem in project management, which combines a project portfolio decision on an upper level and project scheduling as well as staff assignment decisions on a lower level, is described. Uncertain work times require a treatment as an SCO problem. First experimental results on the application of S-VNS to this problem are outlined.

We introduce a new approach for randomizing the digit sets of binary integer representations used in elliptic curve cryptography, and present a formal analysis of the sparsity of such representations. The motivation is to improve the sparseness of integer representations and to provide a tool for defense against side channel attacks. Existing alternative digit sets such as  = {0,1, − 1} require a certain non-adjacency property (no two successive digits are non-zero) in order to attain the desired level of sparseness. Our digit sets do not rely on the non-adjacency property, which in any case is only possible for a certain very restricted class of digit sets, but nevertheless achieve better sparsity. For example, we construct a large explicit family of digit sets for which the resulting integer representations consist on average of 74% zeros, which is an improvement over the 67% sparsity available using non-adjacent form representations. Our proof of the sparsity result is novel and is dramatically simpler than the existing analyses of non-adjacent form representations available in the literature, in addition to being more general. We conclude with some performance comparisons and an analysis of the resilience of our implementation against side channel attacks under an attack model called the . We emphasize that our side channel analysis remains preliminary and that our attack model represents only a first step in devising a formal framework for assessing the security of randomized representations as a side channel attack countermeasure.