Discrete Mathematics Seminar

Department of Mathematics
University of Crete


Organizer: Theo Garefalakis and Mihalis Kolountzakis.

Schedule of talks

More recent up.

List of talks

31 July 2008 Evangelos Markakis Algorithms for approximate Nash equlibria for two-player games
17 Feb 2006 Evangelos Markakis Inapproximability Results for Maximizing the Social Welfare in Combinatorial Auctions
7 Dec 2005 Yannis Michos On the support of the free Lie algebra: the Schutzenberger problems, continued
6 Dec 2005 Yannis Michos On the support of the free Lie algebra : the Schutzenberger problems
15 Nov 2005 Menelaos Karavelas On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of $ d$-dimensional spheres
12 Oct 2005 Mihalis Kolountzakis On the spectrum of symmetric boolean functions
6 Oct 2005 Georgios Georgakopoulos How to search almost optimally by ``chain-splaying''
29 Aug 2005 Sinai Robins Integer linear programming via analytic number theory
21 Jul 2005 Theodoulos Garefalakis The hidden number problem with non-prime modulus
14 Jul 2005 Máté Matolcsi The disproof of Fuglede's conjecture
28 June 2005 Evangelos Markakis Computational Aspects of Game Theory and Microeconomics
   

Details

Time: 11:15, Thu, Jul 31, 2008
Place: Z301
Title: Algorithms for approximate Nash equlibria for two-player games
Speaker: Evangelos Markakis
Affiliation: CWI

Abstract

A Nash equilibrium of a noncooperative game is a pair of strategies such

that no player has an incentive to unilaterally deviate from his current strategy. Recent results (e.g. Daskalakis, Goldberg, Papadimitriou '06 and Chen, Deng, Teng '06) indicate that polynomial time algorithms for finding

an exact Nash equilibrium are unlikely to exist.

In this talk we will consider the question of computing approximate Nash equilibrium strategies in bimatrix games. In particular, given a bimatrix game where the entries of both payoff matrices are in the interval [0,1],

we will say that a pair of strategies is an epsilon-Nash equilibrium if no player can gain more than epsilon by deviating. After summarizing the existing results on the complexity of the problem, I will present a new polynomial time approximation algorithm, based on

linear programming.

No previous knowledge on game theory is required.

Time: 17:15, Fri, Feb 17, 2006
Place: Z301
Title: Inapproximability Results for Maximizing the Social Welfare in Combinatorial Auctions
Speaker: Evangelos Markakis
Affiliation: Department of Computer Science, Univ. of Toronto

Abstract

We consider the following optimization problem that arises in the context of combinatorial auctions: a set of indivisible goods is to be allocated to a set of agents who express preferences over combinations of goods through their utility function. The objective is to find an allocation that maximizes the total utility derived, i.e., the social welfare. In the case when the utility of each agent is a submodular function, we show that there is no polynomial time approximation algorithm with an approximation factor better than 1-1/e, unless P = NP. Our result is based on reductions from multi-prover proof systems, similar in spirit to the reductions for the hardness of Set Cover by Lund-Yannakakis and Feige. No previous knowledge or background will be required.

This is joint work with Subhash Khot, Richard Lipton and Aranyak Mehta.

Time: 19:15, Wed, Dec 7, 2005
Place: Z301
Title: On the support of the free Lie algebra: the Schutzenberger problems, continued
Speaker: Yannis Michos
Affiliation: Department of Mathematics and Statistics, University of Cyprus

Time: 18:15, Tue, Dec 6, 2005
Place: Z301
Title: On the support of the free Lie algebra : the Schutzenberger problems
Speaker: Yannis Michos
Affiliation: Department of Mathematics and Statistics, University of Cyprus

Abstract

Let $ A$ be a finite alphabet and $ L(A)$ be the free Lie algebra on $ A$ over the ring of the integers $ {\mathbb{Z}}_{n}$ modulo a non-negative integer $ n$. The support of $ L(A)$ is the subset $ S$ of $ A^{*}$ consisting of all the words that appear (with a non-zero coefficient) in some Lie polynomial in $ L(A)$.

For each word $ w \in A^{*}$ let $ c(w)$ be the smallest non-negative integer that appears as a coefficient in some Lie polynomial over the integers $ \mathbb{Z}$. For a given $ n$ Schutzenberger posed the problem of characterizing the language $ {\mathcal L}_{n}$ of all words with the property that $ c(w)$ lies in the ideal $ (n)$ of $ \mathbb{Z}$, when $ n \neq 1$, or $ c(w) = 1$ when $ n = 1$. Clearly, for $ n \neq 1$ $ {\mathcal L}_{n}$ is the complement of the support of $ L(A)$ over $ {\mathbb{Z}}_{n}$. The only case settled so far is when $ n=0$ by Duchamp and Thibon who showed that $ {\mathcal L}_{0}$ consists of all words that are either powers of a letter or palindromes of even length.

Schutzenberger posed also the problem of finding all twin (anti-twin) words, i.e., words $ u$ and $ v$ with the property that in each Lie polynomial $ u$ and $ v$ appear with equal (opposite) coefficients.

We handle these problems with the notion of the adjoint endomorphism $ l^{*}$ of the left-normed Lie bracketing in $ L(A)$ over $ {\mathbb{Z}}_{n}$. We show that $ {\mathcal L}_{n}$ consists of all words that lie in the kernel of $ l^{*}$. The polynomial $ l^{*}(w)$ is calculated in terms of the shuffle product of words and $ c(w)$ is the greatest common divisor of the coefficients of its monomials. Finally, we conjecture that two words $ u$ and $ v$ that do not lie in $ {\mathcal L}_{0}$ form a twin pair if either $ u=v$ or $ u$ is equal to the reversal of $ v$ when their common length is odd, whereas they form an anti-twin pair when their common length is even and $ u$ is equal to the reversal of $ v$.

Time: 18:15, Tue, Nov 15, 2005
Place: Z301
Title: On the combinatorial complexity of Euclidean Voronoi cells and convex hulls of $ d$-dimensional spheres
Speaker: Menelaos Karavelas
Affiliation: Department of Applied Mathematics, University of Crete

Abstract

We present an equivalence relationship between additively weighted Voronoi cells in $ R^d$, power diagrams in $ R^d$ and convex hulls of spheres in $ R^d$. An immediate consequence of this equivalence relationship is a tight bound on the complexity of: (1) a single additively weighted Voronoi cell in dimension $ d$; (2) the convex hull of a set of $ d$-dimensional spheres. In particular, given a set of $ n$ spheres in dimension $ d$, we show that the worst case complexity of both a single additively weighted Voronoi cell and the convex hull of the set of spheres is $ \Theta(n^{\lceil\frac{d}{2} \rceil})$. The equivalence between additively weighted Voronoi cells and convex hulls of spheres permits us to compute a single additively weighted Voronoi cell in dimension $ d$ in worst case optimal time $ O (n \log n + n^{\lceil\frac{d}{2}\rceil})$. This work is joint work with Jean-Daniel Boissonnat.

Time: 19:15, Wed, Oct 12, 2005
Place: Z301
Title: On the spectrum of symmetric boolean functions
Speaker: Mihalis Kolountzakis
Affiliation: Department of Mathematics, University of Crete

Abstract

We study a problem coming from theoretical computer science. When one tries to ``learn'' a boolean function on $ k$ variables (that is a function $ f:\{0,1\}^k \to \{0,1\}$ it turns out that, for a certain learning algorithm, the crucial parameter of the function which determines the running time is the order of the first Fourier non-zero of the function. We show that if a symmetric boolean function (this means that the function does not depend on the order of its inputs) is not constant or a parity function then that quantity is bounded above by $ C k\bigl /\log k$, improving on previous upper bounds which were of the form $ C k$. The problem translates into a number-theoretic problem about binomial coefficients. This is joint work with E. Markakis and A. Mehta.

Time: 19:15, Thu, Oct 6, 2005
Place: Z301
Title: How to search almost optimally by ``chain-splaying''
Speaker: Georgios Georgakopoulos
Affiliation: Department of Computer Science, University of Crete

Abstract

The search problem is an omnipresent fundamental problem for computer science. Its formulation is deceivingly simple: we maintain a collection $ D$ of $ N$ items (members of a linear order) and we are facing a sequence $ H$ of elements - a ``history'' - that have to be sequentially searched for, and located, in $ D$. Which is the optimal way to perform this sequence $ H$ of accesses?

The problem was solved optimally per access already since 1962, but no one has yet (2005) offered a way to do it so per history $ H$. In 1983-85 Sleator and Tarjan offered a framework for dealing with this problem using relatively novel notions at the time, like self-adjustment, amortized cost and competitive analysis. They designed the so called splay trees and conjectured that splay trees are dynamically optimal, i.e. their efficiency is always the optimal one times an $ O(1)$ (constant) factor.

In FOCS 2004 a new variety of very loosely balanced search trees was announced, the ``tango'' trees. Tango trees approach the optimal behaviour by a factor of $ O(loglogN)$ for the first time, yet these trees do not use splaying - while there exist various theoretical reasons to expect that, in some sense, only splay-like trees can be candidates for optimality.

In 4th WEA05 the speaker presented ``chain-splay'' trees, a variant of splay trees that also behave optimally within a factor of $ O(loglogN)$, contributing thus the first progress w.r.t to the dynamic optimality conjecture for splaying, since 1983-85. A novel set of techniques, develop the last few years, was used: progress factors, cost transfer, reweigh techniques, ``zip'' operations, etc. One may hope that these techniques will be useful to the final settling of the afore-mentioned conjecture.

Time: 19:15, Mon, Aug 29, 2005
Place: Z301
Title: Integer linear programming via analytic number theory
Speaker: Sinai Robins
Affiliation: Department of Mathematics, Temple University

Abstract

We approach a basic question in integer linear programming, namely the problem of finding an integer point (or all of them) inside a polytope, given its facet description. We first develop new types of differentiable Dedekind sums, and reciprocity laws for them in all dimensions, and then use them to zero in on the location of integer points inside rational polytopes. This is work in progress, and the methods will be illustrated with certain instructive rational polygons and rational polytopes. Our approach presents an alternative approach to Barvinok's algorithm, using some new analytic functions that we call differentiable Dedekind sums. This work is joint with Helaman Ferguson.

Time: 19:15, Thu, Jul 21, 2005
Place: Z301
Title: The hidden number problem with non-prime modulus
Speaker: Theodoulos Garefalakis
Affiliation: Department of Mathematics, University of Crete

Abstract

The Hidden Number Problem (HNP) with prime modulus was introduced in 1996 by Boneh and Venkatesan in connection with the security of the Diffie-Hellman key. The problem was subsequently generalized in several directions and was proven to be related to the security of other discrete log based cryptosystems. We consider a generalization of the Hidden Number Problem for general moduli $ N$, and prove that it can be solved with high probability if the given approximations are sufficiently good and the multipliers are chosen uniformly at random from $ {\mathbf Z}/N{\mathbf Z}$. We prove the same result in the case that the multipliers are chosen from $ ({\mathbf Z}/N {\mathbf Z})^{\times}$ and $ N$ is a product of a constant number of distinct primes. We show that this generalization is related to the bit security of the RSA function.

Time: 19:15, Thu, Jul 14, 2005
Place: Z301
Title: The disproof of Fuglede's conjecture
Speaker: Máté Matolcsi
Affiliation: Alfréd Rényi Institute of Mathematics

Abstract

Fuglede's conjecture relates the notions of translational tiles and spectral sets in Euclidean spaces. Let $ T$ be a $ d$-dimensional Lebesgue measureable set of finite non-zero measure. A discrete $ d$-dimensional set $ L$ is said to be a spectrum of $ T$ if the characters corresponding to $ L$ (and restricted to $ T$) form an orthogonal basis in the space of square-integrable functions on $ T$. If such an $ L$ exists, $ T$ is said to be spectral. The set $ T$ is said to be a (translational) tile if it is possible to tile the whole $ d$-dimensional space with a family of translates $ t+T$ of $ T$ (ignoring overlaps and gaps of measure zero). Then, Fuglede formulated the following Conjecture: A set $ T$ of finite, non-zero Lebesgue measure is a tile if and only if it is spectral. Fuglede proved the conjecture in the special case when the spectrum $ L$ or the translation set $ T'$ is assumed to be a lattice. The general case of the conjecture was open for nearly 30 years, until last year Tao showed an example to disprove one direction of the conjecture in 5 and higher dimensions. Namely, he gave an example of a 5-dimensional spectral set which is not a tile. With a slight modification of Tao's arguments I reduced the dimension of the counterexample to 4, and subsequently (in a joint work with M. Kolountzakis) to 3. The 'tile -> spectral' direction, however, could not be tackled by Tao's arguments. A counterexample for this direction was found in dimension 5 during my visit to the University of Cretei in 2004 (joint with M. Kolountzakis). The proof is mainly based on Fourier analysis and combinatorics. Recently, in a joint work Szilárd Révész and Balint Farkas, we reduced this dimension to 4, and subsequently Balint Farkas and I reduced the dimension further to 3. At present the Conjecture is still open in dimensions 1 and 2. In dimension 1, the 'tile -> spectral' part of the conjecture would follow from a particular number theoretic conjecture (which is far from being settled).

Time: 19:15, Tue, June 28, 2005
Place: B211 (White building)
Title: Computational Aspects of Game Theory and Microeconomics
Speaker: Evangelos Markakis
Affiliation: College of Computing, Georgia Institute of Technology

Abstract

Game theory and economics provide a mathematical framework for analyzing interactions among self-interested agents. However, the outcomes proposed by the economic theory often involve optimization problems with no known efficient algorithms.

In this talk we investigate the computational complexity of various economic solution concepts. The first part of the talk will focus on the problem of allocating a set of indivisible goods to a set of agents, who express preferences over combinations of items through their utility functions. Several objectives have been considered in the economic literature in different contexts. In fair division theory, a desirable outcome is to find an allocation that minimizes the envy between the agents or achieves additional fairness criteria. A different goal, in the context of auctions, is to maximize the social welfare, i.e., the total utility derived by the agents. We use techniques from the theory of linear and integer programming as well as combinatorics to provide new approximation algorithms and hardness results for these objectives, for various types of utility functions.

The second part of the talk will focus on computing or approximating equilibrium concepts in games. We will present the first subexponential algorithm for computing an approximate Nash equilibrium in 2-player noncooperative games. We obtain generalizations to multi-player games and identify special cases in which exact equilibria are computable in polynomial time. Finally, if time permits, we will look at a class of coalitional games as an attempt to address incentive issues in interdomain routing. We propose a polynomial time algorithm, based on LP-Duality theory, for computing an equilibrium in such games.


Discrete Mathematics Seminar 2008-07-29