In this talk, we discuss the concept of so-called black-box complexity. The black-box complexity measures a problem's difficulty to be optimized by general purpose optimization algorithms. We enrich the two existing black-box complexity notions due to Wegener and other authors by the restrictions that not actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the algorithm. Many randomized search heuristics belong to this class of algorithms. We show that the new ranking-based model gives more realistic complexity estimates for some problems, while for others the low complexities of the previous models still hold.

This is joint work with Benjamin Doerr and will appear in the Proceedings of the 6th International Computer Science Symposium in Russia (CSR 2011).

We provide the first constant factor approximation for deterministic truthful mechanisms. In particular we come up with an approximation guarantee of 2+epsilon, significantly improving on the previous upper bound of min(m,(2+epsilon)s_m/s_1). Here epsilon is an arbitrarily small value, m is the number of machines, and s_i is the (reported) speed of machine i.

In this work, we analyze the performance of randomized rumor spreading on preferential attachment graphs, which are believed to be a good model for many real-world networks including social networks. We show that a natural randomized rumor spreading mechanism makes a rumor known to all nodes of the network in sublogarithmic time. This is faster than the logarithmic times needed in all previous works regarding, e.g., complete graphs, classical random graphs or hypercubes. We observe a similar behavior experimentally in real networks.

This is joint work with Mahmoud Fouz (Saarland University) and Tobias Friedrich (MPI) and will appear in the Proceedings of STOC 2011

One of the fundamental problems in extremal graph theory is the Turan problem which asks for the largest number of edges in a simple $n$-vertex graph $G$ not containing a given graph $H$ as a subgraph. This largest number is called the Turan number of $H$ and is denoted by $ex(n,H)$. The Turan number is well understood for nonbipartite graphs. For general bipartite graphs, however, the problem remains very difficult.
After a brief introduction to the current status of the Turan problem for bipartite graphs, we discuss some Turan type results for bipartite graphs obtained through edge subdivision. One of these is a so-called topological clique: a graph obtained from subdividing edges of a complete graph. For each $t$ and sufficiently large $n$, we show that every $n$-vertex graph with at least $a(t) n^{1+\epsilon}$ edges, where $a(t)$ is a constant depending on $t$, contains a subdivision of $K_t$ in which each edge of $K_t$ is subdivided at most $c\log (1/\epsilon)/\epsilon$ times, where $c$ is an absolute constant. This improves an earlier result of Kostochka and Pyber. We also show that if H is obtained from iteratively adding a path of odd length at least $2k-1$ between a pair of adjacent vertices then $ex(n,H)=O(n^{1+1/k})$, which substantially generalizes the known result on the Turan numbers of even cycles..

(http://www.users.muohio.edu/jiangt/)