Hierarchies of Complexity Classes
- Stathis Zachos (National Technical University of Athens)
Computational Complexity theory deals with the classification of problems into classes of hardness called complexity classes. In Abstract Complexity (in contrast to Concrete Complexity) we define complexity classes according to general structural properties, such as the model of computation (Turing Machine, RAM, Finite Automaton, PDA, LBA, PRAM, monotone circuits), the mode of computation (deterministic, nondeterministic, probabilistic, alternating, uniform parallel), the kind of the automaton (decider, acceptor, generator, transducer, counting), the resources (time, space, # of processors, circuit size and depth) and also randomness, oracles, interactivity, promise, advice, operators. Inclusion and separation relations between complexity classes constitute central research goals and form some of the most important open questions in theory. This research has led to definitions of scores of complexity classes, as well as sequences of classes known as "complexity hierarchies". We will review some of the most interesting ones, including the Polynomial-Time Hierarchy, a Counting Hierarchy and an Approximability Hierarchy.
On the Fourier Spectrum of Symmetric Boolean Functions (with applications to learning symmetric juntas)- Vangelis Markakis (University of Toronto)
We prove a structural result on the low order spectrum of symmetric functions. In particular, we show that every symmetric boolean function on k variables, other than the constant and the parity functions, has a nonzero Fourier coefficient of order at least 1 and at most 4k/logk. Our work is motivated by the problem of learning juntas in the PAC model. A k-junta is a function of n variables that depends only on an unknown set of k variables. Our result implies the first n^{o(k)} algorithm for learning symmetric k-juntas under the uniform distribution.
(Joint work with Mihalis Kolountzakis, Richard Lipton, Aranyak Mehta and Nisheeth Vishnoi)
On the Relation between Vehicle Scheduling and Path Coloring- Michael Lampis (National Technical University of Athens)
We introduce a vehicle scheduling problem, which aims in generating a periodic timetable for a given set of routes and a given time period, in such a way that the minimum time distance between any two successive vehicles that pass from the same point of the network is maximized. We show a relation of this new problem to the Path Coloring problem and present exact and approximation algorithms for basic network topologies such as chains, rings, stars and trees.
(Joint work with Evangelos Bampas, Georgia Kaouri and Aris Pagourtzis)
Mobile Agent Rendezvous in Graphs- Euripides Markou (University of Athens)
We consider the rendezvous problem for identical mobile agents (i.e., running the same deterministic algorithm) with tokens in a synchronous torus with a sense of direction and show that there is a striking {\em computational difference} between one and more tokens. More specifically, we show that 1) two agents with a constant number of unmovable tokens, or with one movable token, each cannot rendezvous if they have $o(\log n)$ memory, while they can perform rendezvous with detection as long as they have one unmovable token and $O(\log n)$ memory; in contrast, 2) when two agents have two movable tokens each then rendezvous (respectively, rendezvous with detection) is possible with constant memory in an arbitrary $n \times m$ (respectively, $n \times n$) torus; and finally, 3) two agents with three movable tokens each and constant memory can perform rendezvous with detection in a $n \times m$ torus.
We also discuss recent results on rendezvous (or gathering) of multiple oblivious and asynchronous mobile agents without tokens on a ring. We explore a nice relation of this last problem with the leader election problem.
Fast Leader-Election Protocols with Bounded Cheaters' Edge- Spyridon Antonakopoulos (Columbia University)
We study the leader election problem on n players in the asynchronous full-information model. Our main contention is that the most commonly used performance measure for leader-election protocols, called resilience, is unable to discern whether a small number of players can exercise disproportionate influence on the outcome of a protocol, or not. As a remedy we propose a new quantity, named cheaters' edge, which roughly describes by what multiplicative factor malicious players may increase, through cheating, their probability of getting elected. Arguably, a good protocol must have bounded cheaters' edge.
We present polynomial-time constructions of new leader-election protocols that are fast, in terms of the rounds required (5, 5 log n, and polylog(n) rounds, respectively), but moreover exhibit bounded cheaters' edge under progressively looser restrictions on the number t of malicious players: t <= O(n / log n), t <= O(n / sqrt(log n log log n)), and, eventually, no restriction at all---without relying on any a priori knowledge of t. The latter of these three protocols constitutes the first constructive solution to a problem posed by Alon and Naor more than a decade ago.
Applications of Random Matrices to Spectral Computations and Machine Learning- Dimitris Achlioptas (UC Santa Cruz)
We will show carefully crafted random matrices can be used to enhance a wide variety of computational tasks, including: dimensionality reduction, spectral computations, and kernel methods in machine learning. Several examples will be considered, including the following two.
Imagine that we want to compute the top few eigenvectors of a matrix A, hoping to extract the "important" features in A. We will prove that either this is not worth doing, or that we can begin by randomly throwing away a large fraction of A's entries.
A famous result of Johnson and Lindenstrauss asserts that any set of n points in d-dimensional Euclidean space can be embedded in k- dimensional Euclidean space, where k=O(log n), such that all pairwise distances are preserved with arbitrarily good accuracy. We prove that to construct such an embedding it suffices to multiply the n x d matrix of points with a random d x k matrix, whose entries are set to ±1 independently, with equal probability.
The emphasis of the talk will be on Euclidean intuition. In particular, no prior knowledge on random matrices and/or linear algebra will be assumed.
Optimization Problems in Multifiber Optical Networks- Katerina Potika (National Technical University of Athens)
We study a path coloring problem with applications to wavelength assignment in all-optical networks with multiple fibers. In contrast to classical path coloring, it is, in this setting, possible to assign a color more than once to paths that pass through the same edge; the number of allowed repetitions per edge is given and the goal is to minimize the number of colors used.
We present algorithms and hardness results for tree topologies of special interest. Our algorithms achieve approximation ratio of $2$ for spiders and $3$ for caterpillars, whereas the best algorithm for trees so far, achieves an approximation ratio of $4$. Additionally, for trees of rings we present an $8$ approximation algorithm. We also study the directed version of the problem and show that is remains $NP$-hard in caterpillars admitting a $3$-approximation algorithm, while it can be solved exactly in spiders.
Norm, Point, and Distance Estimation Over Multiple Signals Using Max--Stable Distributions- George Kollios (Boston University)
Consider a set of signals $f_1, f_2, ..., f_s$ appearing as a stream of tuples $(i, f_j(i))$ in arbitrary order of $i$ and $j$. We would like to devise one pass approximate algorithms for estimating various functionals on the dominant signal $f_{max}$, defined as the maximum value for each $i$. For example, the ``worst case influence'' which is the $F_1$-norm of the dominant signal, general $F_p$-norms, and special types of distances between dominant signals. The only known previous work in this setting are the algorithms of Cormode and Muthukrishnan and Pavan and Tirthapura which can only estimate the $F_1$-norm over $f_{max}$. No previous work addressed more general norms or distance estimation.
In this work, we use a novel sketch, based on the properties of max-stable distributions, for these more general problems. The Max-Stable sketch is a significant improvement over previous alternatives in terms of simplicity of implementation, space requirements, and insertion cost, while providing similar approximation guarantees. To assert our statements, we also conduct an experimental evaluation using real datasets.
(Joint work with Stilian Stoev, Marios Hadjieleftheriou and Murad Taqqu)
On the Complexity of Polynomial Real Solving- Elias P. Tsigaridas (University of Athens)
We present algorithmic and complexity results concerning the problem of real root isolation of univariate integer polynomials. The algorithms are exact, are based either on subdivision schemes or on the continued fraction expansion of real numbers and achieve the best, up to now, complexity bound. Finally, we present ongoing work towards improving the complexity bound.
On mechanisms for scheduling on unrelated machines- Elias Koutsoupias (University of Athens)
The mechanism design problem of scheduling tasks on $n$ unrelated machines, in which the machines are the players of the mechanism, was proposed and studied in the seminal paper of Nisan and Ronen about ten years ago. It was shown there that the approximation ratio of mechanisms is between 2 and $n$. Despite the central role of the problem in the new area of Algorithmic Mechanism Design, there was no improvement on these bounds. In this talk, I will present some recent approaches and results.
(Joint work with George Christodoulou and Angelina Vidali)
Optimal Phylogenetic Reconstruction
- Costis Daskalakis (UC Berkeley)
One of the major tasks of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on the true evolutionary tree and the goal is to reconstruct the tree, when only samples from the Markov chain at the leaves are available.
It is well known that, if the tree has n leaves, sequences of length at least logarithmic in n are required. In fact, if the mutation rate is high, the number of characters must be at least polynomial in n. Yet, all immediate approaches require an exponential number of characters and only recently algorithms that match the polynomial lower bound have been discovered.
This leaves open the question of whether reconstruction can be done with fewer characters for models with small mutation rates where the polynomial lower bound does not apply. We prove a conjecture of M. Steel that a logarithmic number of characters suffices if and only if the mutation rate is below some threshold value, known in statistical physics as the reconstruction threshold for the Ising Model on the tree. Our result establishes a sharp transition on the information required for phylogenetic reconstruction and provides an interesting connection with statistical physics and probability theory.
(Joint work with Elchanan Mossel and Sebastien Roch)
Quantum vs. classical one-way communication complexity- Iordanis Kerenidis (Centre National de la Recherche Scientifique)
The first exponential separation between quantum and randomized one-way communication complexity was proved by Bar-Yossef, Jayram, Kerenidis [BJK04] for the Relational Hidden Matching Problem. In this problem, Alice gets as input an n-bit string and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) such that the edge (i,j) belongs to the matching M and b=x_i \oplus x_j. They proved that the quantum one-way communication complexity of this relation is O(log n), yet any randomized one-way protocol with bounded error must use Omega(\sqrt{n}) bits of communication. It was an open question to prove a similar exponential separation for a partial function instead of a relation.
Here, we define a boolean version of the Hidden Matching Problem and give a tight lower bound of Omega(\sqrt{n}) for its randomized one-way communication complexity. Since there is a quantum one-way protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for partial functions. Our lower bound is obtained by Fourier analysis, using the Fourier coefficients inequality of Kahn Kalai and Linial [KKL88].
(Joint work with Ran Raz)
On the Complexity of Counting when Decision is Easy- Aris Pagourtzis (National Technical University of Athens)
We study the complexity of counting problems that belong to the complexity class #P and have an easy decision version. Well-known representatives of this class are #Perfect Matchings, #DNF-Sat, and NonNegative Permanent. We study these problems in respect to the complexity class TotP, which contains functions that count the number of all compuation paths of a poly-time nondeterministic Turing machine. We show that the above mentioned problems, as well as several other #P problems with easy decision belong to TotP. Moreover, we provide a necessary and sufficient condition, in terms of a self-reducibility property for inclusion of such problems in TotP.
(Joint work with Stathis Zachos)
Probabilistic Models for the Steiner Tree Problem- Vangelis Paschos (Unversité Paris-Dauphine)
We consider probabilistic models for \textsc{probabilistic steiner tree}. Under these models, the problem is defined in a two-stage setting over a complete weighted graph whose vertices are associated with a probability of presence in the second stage. A first-stage feasible solution on the input graph might become infeasible in the second stage, when certain vertices of the graph fail (with the specified probability). Therefore, a well defined {\em modification strategy} is devised which transforms a partial solution to a feasible second-stage solution. The objective is to devise an algorithm for the first-stage solution (sometimes called the {\em a priori} or \emph{anticipatory} solution) so that the expected second-stage solution cost is minimized. An important feature of this framework is that the modification strategy is essentially a part of the problem, while algorithmic treatment is required in the construction of the anticipatory solution. We provide approximation results regarding two modification strategies.
Implications of Selfish Neighbor Selection in Overlay Networks- Nikos Laoutaris (Boston University-University of Athens)
In a typical overlay network for routing or content sharing, each node must select a fixed number of immediate overlay neighbors for routing traffic or requests for content. A selfish node entering such a network would select neighbors so as to minimize the weighted sum of expected access costs to all destinations. Previous work on selfish neighbor selection has built intuition with simple models where edges are undirected, access costs are modelled by hop-counts, and nodes have potentially unbounded degree. In practice however, important side constraints not captured by these models lead to richer games with substantively and fundamentally different outcomes. Our work models neighbor selection as a game involving directed links, constraints on the number of allowed neighbors, and costs reflecting both network latency and node preference. We express a node's (best response) wiring strategy to a directed version of the $k$-median problem and use this observation to obtain pure Nash equilibria. We study the performance of such wirings analytically and also experimentaly on synthetic topologies as well as on measurements and maps collected from PlanetLab and the AS-level Internet, respectively. Our results indicate that selfish nodes can reap substantial performance benefits when connecting to overlay networks composed of non-selfish nodes. On the other hand, in overlays that are dominated by selfish nodes, the resulting stable wirings are optimized to such great extent, that even non-selfish newcomers can extract near-optimal performance through naive wiring strategies.
On-line Models for Set-Covering: the Power of Greediness- Aristotelis Giannakos (Unversité Paris-Dauphine)
We study an on-line model for set-covering implying that elements of the ground set of size $n$ arrive one-by-one and with any such element $\sigma_i$, arrive also the names of the sets containing it in the final instance. Any new element has to be processed irrevocably before the arrival of the next element. We study limits on the competitiveness of several greedy rules solving several alternatives of this basic model. For any of them we give lower and upper bounds for the competitive ratio achieved. We finally deal with the maximum budget saving problem. Here, an initial budget is allotted that is destined to cover the cost of an algorithm for solving set-covering and the objective is to maximize the savings on the initial budget.
(Joint work with Giorgio Ausiello and Vangelis Th. Paschos)