Daniel Stefankovic - Publications

String graphs, graph drawing, computing with curves on surfaces

Abstract: We show that string graphs can be recognized in NEXP by giving an exponential upper bound on the number of intersections for a drawing realizing the string graph in the plane. This upper bound confirms a conjecture by Kratochvil and Matousek and settles the long-standing open problem of the decidability of string graph recognition. Finally we show how to apply the result to solve another old open problem: deciding the existence of Euler diagrams. The decidability of string graphs was independently proved by Pach and Toth (Graph Drawing 2001, Discrete Comput. Geom. 28 (2002), no. 4, 593-606.)

Abstract: We show that string graphs can be recognized in NP. The recognition problem was not known to be decidable until very recently. The result has consequences for the computational complexity of problems in graph drawing, and topological inference.

Abstract: We give polynomial-time algorithms for the following problems for simple (multi) curves given by normal coordinates in a triangulation T of a surface M.
• Compute coordinates of a multi-curve A in a minimal triangulation T' of M.
• Count the algebraic intersection number of multi-curves A and B.
• Count the number of connected components of a multi curve A.
• List the non-isotopic connected components of a multi curve A together with their multiplicities in A.
• Find an arc connecting two points in M-A disjoint from A.

Abstract: We give polynomial-time algorithms for the following problems for simple (multi) curves given by normal coordinates or by Dehn-Thurston coordinates.
• Compute Dehn twist of a curve A along a curve B.
• Compute geometric intersection number of two curves A and B.

Abstract: Confluent graphs are a natural generalization of planar graphs. The complexity of recognition of confluent graphs is not well understood. We introduce a variant called strongly confluent graphs and show that recognition of strongly confluent graphs is in NP. We also give a natural elimination ordering characterization of tree-confluent graphs which shows they form a subclass of the chordal bipartite graphs.

Combinatorics

Abstract: We study set systems satisfying Frankl--Wilson-type conditions modulo prime powers. We prove that the size of such set systems is polynomially bounded, in contrast with V. Grolmusz's recent result that for non-prime-power moduli, no polynomial bound exists.

Fourier Transform

Abstract: We survey proofs of five Theorems which have applicationsin the Theory of Computing. The common theme of the proofs is the use of various variants of harmonic analysis. The proofs of following theorems are included:
• Theorem of Linial, Mansour and Nisan on the concentration of the Fourier coefficients of AC0 functions.
• Theorem of Kahn, Kalai and Linial on the influence of variables on Boolean functions
• The analysis of Margulis' expander graph by Gabber and Galil
• Transference Theorem of Banaszczyk
• Theorem of Therien on the column sums in matrices (mod m)

Abstract: Given real numbers al_1,...,al_n, a simultaneous diophantine eps-approximation is a sequence of integers P_1,...,P_n,Q such that Q>0 and for all j\in {1,...,n}, |Q al_j-P_j|<=eps. A simultaneous diophantine approximation is said to exclude the prime p if Q is not divisible by p. Given real numbers al_1,...,al_n, a prime p and eps>0 we show that at least one of the following holds

(A) there is a simultaneous diophantine eps-approximation which excludes p, or

(B) there exist integers a_1,...,a_n,t such that sum a_j al_j=1/p+t and sum |a_j|<= n^{3/2}/eps.

Note that in case (B) the a_j witness that there is no simultaneous diophantine eps/(n^{3/2}p)-approximation excluding p.

As an application we show that for p a prime and bounded d | p-1 the ring Z/P^kZ contains a number all of whose d-th roots modulo p^k are small.

Coding Theory

Abstract: Cyclic linear codes of block length n over a finite field F_q are the linear subspace of F_q^n that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in the family have constant rate and constant normalized distance (distance divided by block length). It is a long-standing open problem whether there exists a good family of cyclic linear codes (cf. [MS, p. 270]). A code C is r-testable if there exist a randomized algorithm which, given a word x in F_q^n, adaptively selects r positions, checks the entries of x in the selected positions, and makes a decision (accept or reject x) based on the positions selected and the numbers found, such that
• if x then x is surely accepted;
• if dist(x,C)>=eps.n then x is probably rejected. ("dist" refers to Hamming distance.)
A family of codes is locally testable if all members of the family are r-testable for some some constant r. This concept arose from holographic proofs/PCPs. Goldreich and Sudan [GS] asked whether there exist good, locally testable families of codes. It is an open problem whether there exists a good locally testable. Theorem: There is no family of good locally testable cyclic codes.

Markov Chains

Abstract: We improve the running time from O*(n^10) to O*(n^7). Our improvement comes from an improved “cooling schedule” for the simulated annealing algorithm, and a refined analysis of the underlying Markov chain.

Game Theory

Abstract: Are games with simple payoffs simpler than general games? Suppose that each player can only win or lose. Can a Nash equilibrium be computed in polynomial time? Theorem: Deciding whether a 0-1 bimatrix game has more than one Nash Equilibrium is NP-hard.

Graph Equations

Abstract: We investigate a new kind of graph inequality which allows graph variables with labeled vertices, and edges and vertices to connect them. We present a simple equation which is unsolvable (though not obviously so). The solvability of graph inequalities in general turns out to be undecidable. However, if we restrict the inequalities to the case of one variable (with one labeled vertex), there is a decision procedure in NEXP.

Routing

Abstract: We consider the problem of designing deadlock-free shortest-path routing algorithms. A design technique based on acyclic orientations has proven to be useful for many important topologies e.g. meshes, tori, trees and hypercubes. It was not known whether this technique always leads to algorithms using asymptotically optimal number of buffers. We show this is not the case by presenting a graph of size N which has deadlock-free shortest-path routing algorithm using O(1) buffers, but every deadlock-free shortest-path routing algorithm based on acyclic orientations requires Omega(log N/ log log N) buffers.

Abstract: We show the following negative results about shortest path interval routing. Shuffle exchange graph of size M requires Omega(M^(1/2-eps)) intervals per edge. Cube connected cycles and butterfly graphs of size M require Omega(sqrt(M/log M)) intervals per edge. Previous lower bounds for these networks were only constant. For the dilation bounded interval routing we give a routing algorithm with the dilation (3/2)D using O(sqrt(M log M)) intervals per edge on any M-node network with the diameter D. It is the first nontrivial upper bound on the dilation bounded interval routing on general networks.

Abstract: We compare two different models of multi-dimensional interval routing schemes (MIRS) on the usual interconnection networks. We give an upper bound on the tradeoff between congestion and space complexity of multipath MIRS for general graphs. For any graph G and given 1<= s<= |V(G)| there exists a multipath (2+|V|/2s,1)-MIRS with congestion F+|V|.Delta.s, where F is the forwarding index of the graph G and Delta is the maximum degree of G. As a consequence, for planar graphs of constant bounded degree there exists a multipath (O(sqrt(|V(G)|)),1)-MIRS with asymptotically optimal congestion.