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 ![]() |
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 ![]() |
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.