**Department of Mathematics
University of Crete**

*Organizer:* Theo Garefalakis and
Mihalis Kolountzakis.

*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 -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 be a finite alphabet and be the free Lie algebra on over the ring of the integers modulo a non-negative integer . The support of is the subset of consisting of all the words that appear (with a non-zero coefficient) in some Lie polynomial in .

For each word let be the smallest non-negative integer that appears as a coefficient in some Lie polynomial over the integers . For a given Schutzenberger posed the problem of characterizing the language of all words with the property that lies in the ideal of , when , or when . Clearly, for is the complement of the support of over . The only case settled so far is when by Duchamp and Thibon who showed that 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 and with the property that in each Lie polynomial and appear with equal (opposite) coefficients.

We handle these problems with the notion of the adjoint endomorphism of the left-normed Lie bracketing in over . We show that consists of all words that lie in the kernel of . The polynomial is calculated in terms of the shuffle product of words and is the greatest common divisor of the coefficients of its monomials. Finally, we conjecture that two words and that do not lie in form a twin pair if either or is equal to the reversal of when their common length is odd, whereas they form an anti-twin pair when their common length is even and is equal to the reversal of .

Time: |
18:15, Tue, Nov 15, 2005 |

Place: |
Z301 |

Title: |
On the combinatorial complexity of Euclidean Voronoi cells and
convex hulls of -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 , power diagrams in and convex hulls of spheres in . An immediate consequence of this equivalence relationship is a tight bound on the complexity of: (1) a single additively weighted Voronoi cell in dimension ; (2) the convex hull of a set of -dimensional spheres. In particular, given a set of spheres in dimension , 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 . The equivalence between additively weighted Voronoi cells and convex hulls of spheres permits us to compute a single additively weighted Voronoi cell in dimension in worst case optimal time . 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 variables
(that is a function
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
, improving on previous upper bounds which were
of the form . 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 of items (members of a linear order) and we are facing a sequence of elements - a ``history'' - that have to be sequentially searched for, and located, in . Which is the optimal way to perform this sequence 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 . 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 (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 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 , 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 , 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 . We prove the same result in the case that the multipliers are chosen from and 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 be a -dimensional Lebesgue measureable set of finite non-zero measure.
A discrete -dimensional set is said to be a spectrum of if the characters
corresponding to (and restricted to ) form an orthogonal basis in the space of
square-integrable functions on .
If such an exists, is said to be spectral.
The set is said to be a (translational) tile if it is possible to tile the
whole -dimensional space with a family of translates of
(ignoring overlaps and gaps of measure zero).
Then, Fuglede formulated the following Conjecture:
*A set 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 or
the translation set 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