Qi Ge and Daniel Stefankovic. The Complexity of Counting Eulerian Tours in 4Regular Graphs

Abstract: We investigate the complexity of counting Eulerian tours ({\sc \#ET}) and its variations from two perspectivesthe complexity of exact counting and the complexity w.r.t. approximationpreserving reductions (APreductions~\cite{MR2044886}). We prove that {\sc \#ET} is \#Pcomplete even for planar $4$regular graphs.
A closely related problem is that of counting Atrails ({\sc \#Atrails}) in graphs with rotational embedding schemes (so called maps). Kotzig~\cite{MR0248043} showed that {\sc \#Atrails} can be computed in polynomial time for $4$regular plane graphs (embedding in the plane is equivalent to giving a rotational embedding scheme). We show that for $4$regular maps the problem is \#Phard. Moreover, we show that from the approximation viewpoint {\sc \#Atrails} in $4$regular maps captures the essence of {\sc \#ET}, that is, we give an APreduction from {\sc \#ET} in general graphs to {\sc \#Atrails} in $4$regular maps. The reduction uses a fast mixing result for a card shuffling problem~\cite{MR2023023}.

Jérémy Barbay, Francisco Claude and Gonzalo Navarro. Compact RichFunctional Binary Relation Representations

Abstract: Binary relations are an important abstraction arising in a number of data representation problems. There data structures that exist for them have focused on a few basic operations that have been traditionally needed. However, as the research on (especially compressed) data structures evolves, more advanced binary relation functionalities are required. The attempt of this paper is to start a fundamental study of the relation between advanced operations on binary relations and their compressibility. We define an extended set of operations, show how some reduce to others, extend an existing representation and propose a novel one, and in both cases show how to handle as much of the new functionality as possible. While the novel representation is shown to be weaker in functionality, its space requirement is close to the entropy of the binary relation, and it turns out to be further compressible when the binary representation exhibits some regularities that arise in reallife.

Johannes Fischer. Optimal Succinctness for Range Minimum Queries 
Abstract: For a static array A of n totally ordered objects, a range minimum query asks for the position of the minimum between two specified array indices. We show how to preprocess A into a scheme of size 2n+o(n) bits that allows to answer range minimum queries on A in constant time. This space is asymptotically optimal in the important setting where access to A is not permitted after the preprocessing step. Our scheme can be computed in linear time, using only n + o(n) additional bits for construction. We also improve on LCAcomputation in BPS or DFUDSencoded trees. 
Beate Bollig. A larger lower bound on the OBDD complexity of the most significant bit of multiplication 
Abstract: Ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. The reachability problem, i.e., computing the set of nodes reachable from some source $s\in V$ in a digraph $G=(V,E)$, is an important problem in computeraided design, hardware verification, and model checking. Sawitzki (2006) has presented exponential lower bounds on the space complexity of a restricted class of symbolic OBDDbased algorithms for the reachability problem. Here, these lower bounds are improved by presenting a larger lower bound on the OBDD complexity of the most significant bit of integer multiplication. 
Atlas F. Cook IV, Carola Wenk, Ovidiu Daescu, Steven Bitner, Yam K. Cheung and Anastasia Kurdia. Visiting a Sequence of Points with a BevelTip Needle 
Abstract: Many
surgical procedures could benefit from guiding a beveltip needle along
circular arcs to multiple treatment points in a patient. At each
treatment point, the needle typically extracts a tissue sample or
injects a radioactive pellet into a cancerous region. Our main result
is an algorithm to steer a beveltip needle through a sequence of
treatment points in the plane while minimizing the number of times that
the needle must be reoriented. This algorithm takes quadratic time when
consecutive points in the sequence are sufficiently separated. When
consecutive points in the sequence are not sufficiently separated,
optimal substructure can fail, and our fixedparameter tractable
algorithm steers a needle by accounting for locally suboptimal paths. 
MohammadHossein Bateni and MohammadTaghi Hajiaghayi. Euclidean Prizecollecting Steiner Forest 
Abstract: In this paper, we consider Steiner forest and its generalizations, prize
collecting Steiner forest and kSteiner forest, when the vertices of the input graph are points in the Euclidean plane and the lengths are
Euclidean distances. First, we present a simpler analysis of the polynomialtime approximation scheme (PTAS) of Borradaile et al. [10]
for the Euclidean Steiner forest problem. This is done by proving a new structural property and modifying the dynamic programming by adding a
new piece of information to each dynamic programming state. Based on our new structural property and algorithm, we develop a PTAS for a
wellmotivated case, i.e., the multiplicative case, of prizecollecting and budgeted Steiner forest. The ideas used in the algorithm may have
applications in design of a broad class of bicriteria PTASs. At the end, we demonstrate why PTASs for these problems can be hard in the
general Euclidean cases (and thus for PTASs we cannot go beyond the multiplicative case). 
Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid and Hanjo Täubig. Time Complexity of Distributed Topological SelfStabilization: The Case of Graph Linearization 
Abstract: Topological selfstabilization is an important concept to build robust open distributed systems (such as peertopeer systems) where nodes can organize themselves into meaningful network topologies. The goal is to devise distributed algorithms that converge quickly to such a desirable topology, independently of the initial network state. This paper proposes a new model to study the parallel convergence time. Our model sheds light on the achievable parallelism by avoiding bottlenecks of existing models that can yield a distorted picture. As a case study, we consider local graph linearizationi.e., how to build a sorted list of the nodes of a connected graph in a distributed and selfstabilizing manner. We propose two variants of a simple algorithm, and provide an extensive formal analysis of their worstcase and bestcase parallel time complexities, as well as their performance under a greedy selection of the actions to be executed. 
Jonathan Backer and Mark Keil. The Mono and Bichromatic Empty Rectangle and Square Problems in All Dimensions 
Abstract: The
maximum empty rectangle problem is as follows: Given a set of red
points in $\mathbb{R}^{d}$ and an axisaligned hyperrectangle $B$, find
an axisaligned hyperrectangle $R$ of greatest volume that is contained
in $B$ and contains no red points. In addition to this problem, we also
consider three natural variants: where we find a hypercube instead of a
hyperrectangle, where we try to contain as many blue points as possible
instead of maximising volume, and where we do both. Combining the
results of this paper with previous results, we now know that all four
of these problems (a) are NPcomplete if $d$ is part of the input, (b)
have polynomialtime sweepplane solutions for any fixed $d\ ge 3$, and
(c) have near linear time solutions in two dimensions. 
Greg Aloupis, Jean Cardinal, Sebastien Collette, Shinji Imahori, Matias Korman, Stefan Langerman, Oded Schwartz, Shakhar Smorodinsky and Perouz Taslakian. Colorful Strips 
Abstract: We study the following geometric hypergraph coloring problem: given a planar point set and an integer $k$, we wish to color the points with $k$ colors so that any axisaligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least $2k{}1$ points, such a coloring can always be found. In dimension $d$, we show that the same holds provided the strip contains at least $k(4\ln k +\ln d)$ points.
We also consider the dual problem of coloring a given set of axisaligned strips so that any sufficiently covered point in the plane is covered by $k$ colors. We show that in dimension $d$ the required coverage is at most $d(k{}1)+1$.
Lower bounds are also given for the two problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations.
From the computational point of view, we show that deciding whether a threedimensional point set can be 2colored so that any strip containing at least three points contains both colors is NPcomplete. This is in contrast with the planar case, for which it is easy to decide. 
Nadja Betzler, Jiong Guo, Christian Komusiewicz and Rolf Niedermeier. Average Parameterization and Partial Kernelization for Computing Medians 
Abstract: We propose an effective polynomialtime preprocessing strategy for intractable median problems. Developing a new methodological framework, we show that if the input instances of generally intractable problems exhibit a sufficiently high degree of similarity between each other on average, then there are efficient exact solving algorithms. In other words, we show that the central median problems Swap Median Permutation, Consensus Clustering, Kemeny Score, and Kemeny Tie Score all are fixedparameter tractable with respect to the parameter ``average distance between input objects''. To this end, we develop the new concept of ``partial kernelization'' and identify interesting polynomialtime solvable special cases for the considered problems. 
Britta Peis, Martin Skutella and Andreas Wiese. Packet Routing on the Grid 
Abstract: The packet routing problem, i.e., the problem to send a given set of unitsize packets through a network on time, belongs to one of the most fundamental routing problems with important practical applications, e.g., in traffic routing, parallel computing, and the design of communication protocols. The problem involves critical routing and scheduling decisions. One has to determine a suitable (short) origindestination path for each packet and resolve occurring conflicts between packets whose paths have an edge in common. The overall aim is to find a path for each packet and a routing schedule with minimum makespan.
A significant topology for practical applications are grid graphs. In this paper, we therefore investigate the packet routing problem under the restriction that the underlying graph is a grid. We establish approximation algorithms and complexity results for the general problem on grids, and under various constraints on the start and destination vertices or on the paths of the packets. 
Andreas Brandstädt, Christian Hundt and Ragnar Nevries. Efficient Edge Domination on Holefree Graphs in Polynomial Time 
Abstract: This paper deals with the Efficient Edge Domination Problem (EED, for short), also known as Dominating Induced Matching Problem. For an undirected graph G=(V,E) EED asks for an induced matching M subset of E that simultaneously dominates all edges of G. Thus, the distance between edges of M is at least two and every edge in E is adjacent to an edge of M. EED is related to parallel resource allocation problems, encoding theory and network routing. The problem is NPcomplete even for restricted classes like planar bipartite and bipartite graphs with maximum degree three. However, the complexity has been open for chordal bipartite graphs.
This paper shows that EED can be solved in polynomial time on holefree graphs. Moreover, it provides even linear time for chordal bipartite graphs.
Finally, we strengthen the NPcompleteness result to planar bipartite graphs of maximum degree three. 
Viliam Geffert and Giovanni Pighizzini. Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata 
Abstract: For
each sufficiently large N, there exists a unary regular language N such
that both L and its complement L^c are accepted by unambiguous
nondeterministic automata with at most N states while the smallest
deterministic automata for these two languages require an exponential
number of states, at least $e^{\Omega(\sqrt[3]{N\cdot\ln^{2}\!N})}$.
Actually, and L^c are accepted by nondeterministic machines
sharing the same transition graph, differing only in the distribution
of their final states. As a consequence, the gap between the sizes of
unary unambiguous selfverifying automata and deterministic automata is also exponential. 
Amalia Duch, Conrado Martinez and Rosa M. Jimenez. Rank Selection in Multidimensional Data 
Abstract: Suppose we have a set of $K$dimensional records stored in a general purpose spatial index like a $K$d tree. The index efficiently supports insertions, ordinary exact searches, orthogonal range searches, nearest neighbor searches, etc. Here we consider whether we can also efficiently support search by rank, that is, to locate the ith smallest element along the jth coordinate. We answer this question in the affirmative by developing a simple algorithm with expected cost $O(n^{\alpha(1/K)}\log n)$, where $n$ is the size of the $K$d tree and $\alpha(1/K)<1$ for any $K\ge 2$. The only requirement to support the search by rank is that each node in the $K$d tree stores the size of the subtree rooted at that node (or some equivalent information). This is not too space demanding. Furthermore, it can be used to randomize the update algorithms to provide guarantees on the expected performance of the various operations on $K$d trees. Although selection in multidimensional data can be solved more efficiently than with our algorithm, those solutions will rely on adhoc data structures
or superlinear space. Our solution adds to an existing data structure
($K$d trees, for instance, but it can be easily adapted to other spatial indexes) the capability of search by rank with very little overhead. The
simplicity of the algorithm makes it easy to implement, practical and
very flexible; however, its correctness and efficiency are far from selfevident. 
Tsunehiko
Kameda, Ichiro Suzuki and John Z. Zhang. Finding the MinimumDistance
Schedule for a Boundary Searcher with a Flashlight 
Abstract: Consider a dark polygonal region in which intruders move freely, trying to avoid detection. A robot, which is equipped with a flashlight, moves along the polygon boundary to illuminate all intruders. We want to minimize the total distance traveled by the robot until all intruders are detected. We present an $O(n\log n)$ time and $O(n)$ space algorithm for optimizing this metric, where $n$ is the number of vertices of the given polygon. This improves upon the best known time and space complexities of $O(n^2)$ and $O(n^2)$, respectively. 
Prosenjit Bose, Karim Douïeb, Vida Dujmović and John Howat. Layered WorkingSet Trees 
Abstract: The
workingset bound [Sleator and Tarjan, J. ACM, 1985] roughly states
that searching for an element is fast if the element was accessed
recently. Binary search trees, such as splay trees, can achieve this
property in the amortized sense, while data structures that are not
binary search trees are known to have this property in the worst case.
We close this gap and present a binary search tree called a layered
workingset tree that guarantees the workingset property in the worst
case. The unified bound [Badoiu et al., TCS, 2007] roughly states that
searching for an element is fast if it is near (in terms of rank
distance) to a recently accessed element. We show how layered
workingset trees can be used to achieve the unified bound to within a
small additive term in the amortized sense while maintaining in the
worst case an access time that is both logarithmic and within a small
multiplicative factor of the workingset bound. 
Andrew Novocin and Mark van Hoeij. Gradual sublattice reduction and a new complexity for factoring polynomials 
Abstract: We
present a lattice algorithm specifically designed for some classical
applications of lattice reduction. The applications are for
lattice bases with a generalized knapsacktype structure, where the
target vectors are boundably short. For such applications,
the complexity of the algorithm improves traditional lattice reduction
by replacing some dependence on the bitlength of the input vectors by
some dependence on the bound for the output vectors. If the
bitlength of the target vectors is unrelated to the bitlength of the
input, then our algorithm is only linear in the bitlength of the input
entries, which is an improvement over the quadratic complexity
floatingpoint LLL algorithms. To illustrate the usefulness
of this algorithm we show that a direct application to factoring
univariate polynomials over the integers leads to the first complexity
bound improvement since 1984. A second application is
algebraic number reconstruction, where a new complexity bound is
obtained as well. 
Sylvain Lombardy and Jacques Sakarovitch. Radix crosssections for length morphisms 
Abstract: We prove that the radix crosssection of a rational set for a length morphism, and more generally for a rational function from a free monoid into N, is rational, a property that does not hold any more if the image of the function is a subset of a free monoid with two or more generators.
The proof is based on several results on finite automata, such as the lexicographic selection of synchronous relations or the iterative decomposition of unary raional series with coefficients in the tropical semiring. It also makes use of a structural construction on weighted transducers that we call the length difference unfolding. 
MohammadTaghi Hajiaghayi and Arefeh Nasri. PrizeCollecting Steiner Networks via Iterative Rounding 
Abstract: In this paper we design an iterative rounding approach for the classic {\em prizecollecting Steiner forest problem} and more generally the {\em prizecollecting survivable Steiner network design} problem. We show as an structural result that in each iteration of our algorithm there is an LP variable in a basic feasible solution which is at least onethirdintegral resulting a 3approximation algorithm for this problem. In addition, we show this factor $3$ in our structural result is indeed tight for prizecollecting Steiner forest and thus prizecollecting survivable Steiner network design. This especially answers negatively the previous belief that one might be able to obtain an approximation factor better than 3 for these problems using a natural iterative rounding approach. Our structural result is extending the celebrated iterative rounding approach of Jain~\cite{Jain01} by using several new ideas some from more complicated linear algebra. The approach of this paper can be also applied to get a constant factor (bicriteria)approximation algorithm for degree constrained prizecollecting network design problems.
We emphasize that though in theory we can prove existence of only an LP variable of at least onethirdintegral, in practice very often in each iteration there exists a variable of integral or almost integral which results in a much better approximation factor than provable factor 3 in this paper (see patent application~\cite{patent}). This is indeed the advantage of our algorithm in this paper over previous approximation algorithms for prizecollecting Steiner forest with the same or slightly better provable approximation factors. 
Brigitte Vallee and Manfred Madritsch. Modelling the LLL algorithm via sandpiles 
Abstract: Lattice
reduction algorithms notably
the LLL algorithm, created by Lenstra, Lenstra and Lovasz in
1982 aim at finding a ``reduced'' basis of a Euclidean lattice of dimension n. The LLL algorithm plays a primary role in many areas of mathematics and computer science,
like cryptology, computer algebra, integer linear programming, and number theory. However, its general behaviour is far from being
well understood. There are already many
experimental observations about the number of iterations or the
geometry of the output, that pose challenging questions that
remain unanswered and lead to natural conjectures which
are yet to be proved. However, until now, there
exist few experimental observations about the precise
execution of the algorithm. Here, we
provide experimental results which precisely
describe an essential parameter of the
execution, namely the ``logarithm of the decreasing
ratio''. These experiments give
arguments towards a ``regularity'' hypothesis. Then, we
propose a simplified model for the LLL algorithm, based
on this
``regularity'' hypothesis, which leads us to
wellknown algorithms, based on
discrete dynamical systems, as sand piles or chip
firing games. Upon the validity of the
regularity hypothesis, it is then
possible to obtain a precise quantification of main
parameters of the LLL algorithm, notably the
number of iterations, and the geometry of the
output. These results well fit with experimental
results performed on general input bases, which indirectly
proves the validity of such a regularity hypothesis and shows the
usefulness of such a simplified model. 
Paolo Ferragina, Travis Gagie and Giovanni Manzini. Lightweight Data Indexing and Compression in External Memory 
Abstract: In this paper we describe algorithms for computing the BWT and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are lightweight in the sense that, for an input of size n, they use only n bits of disk working space while all previous approaches use Theta(n log n) bits of disk working space. Moreover, our algorithms access disk data only via sequential scans, thus they take full advantage of modern disk features that make sequential disk accesses much faster than random accesses.
We also present a scanbased algorithm for inverting the BWT that uses Theta(n) bits of working space, and a lightweight internalmemory algorithm for computing the BWT which is the fastest in the literature when the available working space is o(n) bits.
Finally, we prove lower bounds on the complexity of computing and inverting the BWT via sequential scans in terms of the classic product: (internalmemory space) x (number of passes) over the disk data. 
Bettina Speckmann and Kevin Verbeek. Homotopic Rectilinear Routing with Few Links and Thick Edges 
Abstract: We
study the NPhard problem of finding noncrossing thick minimumlink
rectilinear paths which are homotopic to a set of input paths in an
environment with rectangular obstacles. We present a 2approximation
that runs in $O(n^3 + k_{in} \log n + k_{out})$ time, where $n$ is the
total number of input paths and obstacles and $k_{in}$ and $k_{out}$
are the total complexities of the input and output paths. Our algorithm
not only approximates the minimum number of links, but also
simultaneously minimizes the total length of the paths. We also show
that an approximation factor of 2 is optimal when using smallest paths
as lower bound. 
Yuichi Asahiro, Eiji Miyano and Kazuaki Samizo. Approximating Maximum DiameterBounded Subgraphs 
Abstract: The paper studies the maximum diameterbounded subgraph problem ({¥sc MaxDBS} for short) which is defined as follows: Given an $n$vertex graph $G$ and a fixed integer $d¥geq 1$, the goal is to find its largest subgraph of the diameter $d$. If $d=1$, the problem is identical to the maximum clique problem and thus it is ${¥cal NP}$hard to approximate {¥sc MaxDBS} to within a factor of $n^{1¥varepsilon}$ for any $¥varepsilon > 0$. Also, it is known to be ${¥cal NP}$hard to approximate {¥sc MaxDBS} to within a factor of $n^{1/3¥varepsilon}$ for any $¥varepsilon >0$ and a fixed $d¥geq 2$. In this paper, we first strengthen the hardness result; we prove that, for any $¥varepsilon > 0$ and a fixed $d¥geq 2$, it is ${¥cal NP}$hard to approximate {¥sc MaxDBS} to within a factor of $n^{1/2¥varepsilon}$. Then, we show that a simple polynomialtime algorithm achieves an approximation ratio of $n^{1/2}$ for any even $d¥geq 2$, and an approximation ration of $n^{2/3}$ for any odd $d¥geq 3$. Furthermore, we investigate the (in)tractability and the (in)approximability of {¥sc MaxDBS} on subclasses of graphs, including chordal graphs, split graphs, interval graphs, and $k$partite graphs. 
Alexis Ballier, Emmanuel Jeandel and Bruno Durand. Tilings robust to errors 
Abstract: We
study the error robustness of tilings of the plane. The fundamental
question is the following: given a tileset, what happens if we allow a
small probability of errors? Are the objects we obtain close to an
errorfree tiling of the plane? We prove that tilesets that produce
only periodic tilings are robust to errors; for this proof, we use a
hierarchical construction of islands of errors. We also show that
another class of tilesets, those that admit countably many tilings is
not robust and that there is no computable way to distinguish between
these two classes. 
Eric Angel, Evripidis Bampis and Nicolas Thibault. Randomized truthful algorithms for scheduling selfish tasks on parallel machines 
Abstract: We
study the problem of designing truthful algorithms for scheduling a set
of tasks, each one owned by a selfish agent, to a set of parallel
(identical or unrelated) machines in order to minimize the makespan. We
consider the following process: at first the agents declare the length
of their tasks, then given these bids the protocol schedules the tasks
on the machines. The aim of the protocol is to minimize the makespan,
i.e. the maximal completion time of the tasks, while the objective of
each agent is to minimize the completion time of its task and thus an
agent may lie if by doing so, his task may finish earlier. In this
paper, we show the existence of randomized truthful
(nonpolynomialtime) algorithms with expected approximation ratio
equal to 3/2 for different scheduling settings (identical machines with
and without release dates and unrelated machines) and models of
execution (strong or weak). Our result improves the best previously
known result [1] for the problem with identical machines (P∣∣Cmax) in
the strong model of execution and reaches, asymptotically, the lower
bound of [5]. In addition, this result can be transformed to a
polynomialtime truthful randomized algorithm with expected
approximation ratio 3/2 + epsilon (resp. 11/6 − 1/3m) for Pm∣∣Cmax
(resp. P∣∣Cmax). 
C.R. Subramanian and Kunal Dutta. Largest Induced Acyclic Tournament in Random Digraphs: A 2point concentration 
Abstract: Given a simple directed graph $D = (V,A)$, let the size of the largest induced acyclic tournament be denoted by $mat(D)$.
Let $D \in \mathcal{D}(n,p)$ be a \emph{random} instance, obtained by
choosing each of the ${{n}\choose{2}}$ possible
undirected edges independently with probability $2p$ and then orienting
each chosen edge in one of two possible directions with proabibility $1/2$. We show that for such a random instance, $mat(D)$ is asymptotically almost surely one of only 2 possible values, namely either $b^*$ or $b^*+1$, where $b^* = \lfloor 2(\log_{p^{1}} n)+0.5 \rfloor$. It is then shown that any maximal induced acyclic tournament is of a size which is at least nearly half of any optimal solution. We also analyze a polynomial time heuristic and show that it produces a solution whose size is at least $\log_{p^{1}} n + \Theta(\sqrt{\log_{p^{1}} n})$. Our results also carry over to a related model in which each possible directed arc is chosen independently with probability $p$. An immediate corollary is that minimum feedback vertex set can be approximated within a ratio of $1+o(1)$ for random tournaments. 
Jaroslaw Byrka, Andreas Karrenbauer and Laura Sanita. The interval constrained 3coloring problem 
Abstract: In this paper, we settle the open complexity status of interval constrained coloring with a fixed number of colors. We prove that the problem is already NPcomplete if the number of different colors is 3. Previously, it has only been known that it is NPcomplete, if the number of colors is part of the input and that the problem is solvable in polynomial time, if the number of colors is at most 2. We also show that it is hard to satisfy almost all of the constraints for a feasible instance. 
Vahab Mirrokni, S. Muthukrishnan and Uri Nadav. QuasiProportional Mechanisms: Priorfree Revenue Maximization 
Abstract: Inspired
by Internet ad auction applications, we study the problem of allocating
a single item via an auction when bidders place very different values
on the item. We formulate this as the problem of priorfree auction and
focus on designing a simple mechanism that always allocates the item.
Rather than designing sophisticated pricing methods like prior
literature, we design better allocation methods. In particular, we
propose quasiproportional allocation methods in which the probability
that an item is allocated to a bidder depends (quasiproportionally) on
the bids.
We prove that corresponding games for both allpay
and winnerspay quasiproportional mechanisms admit pure Nash
equilibria and this equilibrium is unique. We also give an algorithm to
compute this equilibrium in polynomial time. Further, we show that the
revenue of the auctioneer is promisingly high compared to the ultimate,
i.e., the highest value of any of the bidders, and show bounds on the
revenue of equilibria both analytically, as well as using experiments
for specific quasiproportional functions. This is the first known
revenue analysis for these natural mechanisms (including the special
case of proportional mechanism which is common in network resource
allocation problems). 
RASENDRAHASINA VONJY and RAVELOMANANA VLADY. Limit theorems for random MAX$2$XORSAT 
Abstract: We consider random instances of the MAX2XORSAT optimization problem. A $2$XOR formula is a conjunction of Boolean equations (or clauses) of the form $x \xor y = 0$ or $x \xor y = 1$. The MAX2XORSAT problem asks for the maximum number of clauses which can be satisfied by any assignment of the variables in a $2$XOR formula. In this work, formula of size $m$ on $n$ Boolean variables are chosen uniformly at random from among all ${n(n1) \choose m}$ possible choices. Denote by $X_{n,m}$ the \textit{minimum} number of clauses that can not be satisfied in a formula with $n$ variables and $m$ clauses. We give precise characterizations of the random variable $X_{n,m}$ around the critical density $\frac{m}{n} \sim \frac{1}{2}$ of random $2$XOR formula. As $\mu$ and $n$ are both large but $\mu=o(n^{1/3})$, we prove that for random formulas with $m= \frac{n}{2}\frac{\mu}{2}n^{2/3}$ clauses $X_{n,m}$ converges in distribution to a Poisson r.v. with mean $\sim \frac{\log{n}}{12} \frac{\log{\mu}}{4}$. If $m = \frac{n}{2} + O(1)n^{2/3}$, $\frac{12 X_{n,m}}{\log{n}} \distrib 1$. If $m = \frac{n}{2} + \frac{\mu}{2}n^{2/3}$ with $1 \ll \mu = o(n^{1/3})$ then $\frac{ 6X_{n,m}}{\mu^3+O(\log{n})} \distrib 1$. For any absolute constant $\varepsilon>0$, if $\mu = \varepsilon n^{1/3}$ then $\frac{8(1+\varepsilon)}{n( \varepsilon^2  \sigma^2)} X_{n,m} \distrib 1$ where $\sigma$ is the solution of $(1+\varepsilon)e^{\varepsilon} = (1\sigma)e^{\sigma}$.
Thus, our findings describe phase transitions in the optimization context similar to those encountered in decision problems. 
Frédérique Bassino, Laura Giambruno and Cyril Nicaud. Complexity of Operations on Cofinite Languages 
Abstract: We study the worst case complexity of regular operations on cofinite languages (i.e. languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata. 
Greg Aloupis, Jean Cardinal, Sebastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy FabilaMonroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara and Perouz Taslakian. Matching Points with Things 
Abstract: Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a noncrossing matching between pointobject pairs. We show that when the objects we match the points to are finite point sets, the problem is NPcomplete in general, and polynomial when the objects are on a line or when their size is at most 2. When the objects are line segments, we show that the problem is NPcomplete in general, and polynomial when the segments form a convex polygon or are all on a line. Finally, for objects that are straight lines, we show that the problem of finding a minmax noncrossing matching is NPcomplete. 
Edyta Szymanska, Marek Karpinski and Andrzej Rucinski. Computational complexity of the Hamiltonian cycle problem in dense hypergraphs 
Abstract: We study the computational complexity of deciding the existence of a Hamiltonian Cycle in some dense classes of kuniform hypergraphs. Those problems turned out to be, along with the hypergraph Perfect Matching problems, exceedingly hard, and there is a renewed algorithmic interest in them. In this paper we design the first polynomial time algorithm for the Hamiltonian Cycle problem for kuniform hypergraphs with density at least $\tfrac12 + \epsilon$, $\eps>0$. In doing so, we depend on a new method of constructing Hamiltonian cycles from (purely) existential statements which could be of independent interest. We establish also a lower bound for intractability of that problem with the density at least $\tfrac1k  \epsilon$. Our results seem to be the first complexity theoretic results for the Diractype dense hypergraph classes. 
Joachim
von zur Gathen, Alfredo Viola and Konstantin Ziegler. Counting
reducible, squareful, and relatively irreducible multivariate
polynomials over finite fields 
Abstract: Among the multivariate polynomials over a finite field, most are irreducible. We present exact counting methods for some classes of special polynomials, namely the reducible ones, those with a square factor, and the “relatively irreducible” ones which are irreducible but factor over an extension field. We also present approximations with relative errors that essentially decrease exponentially in the input size. 
Petra Berenbrink, Robert Elsaesser and Thomas Sauerwald. Randomised Broadcasting: Memory vs. Randomness 
Abstract: In this paper we analyse broadcasting in $d$regular networks with good expansion properties. For the underlying communication, we consider modifications of the so called random phone call model. In the standard version of this model, each node is allowed in every step to open a channel to a randomly chosen neighbour, and the channels can be used for bidirectional communication. Then, broadcasting on the graphs mentioned above can be performed in time $O(\log n)$, where $n$ is the size of the network. However, every broadcast algorithm with runtime $O(\log n)$ needs in average $\Omega(\log n/\log d)$ message transmissions per node. This lower bound even holds for random $d$regular graphs, and implies a high amount of message transmissions especially if $d$ is relatively small.
In this paper we show that it is possible to save significantly on communications if the standard model is modified such that nodes can avoid opening channels to the same neighbours in consecutive steps. We consider the so called \rr model where we assume that every node has a cyclic list of all of its neighbours, ordered in a random way. Then, in step $i$ the node communicates with the $i$th neighbour from that list. We provide an $O(\log n)$ time algorithm which produces in average $O(\sqrt{\log n})$ transmissions per node in networks with good expansion properties. Furthermore, we present a related lower bound of $\Omega(\sqrt{\log n/\log\log n})$ for the average number of message transmissions. These results show that by using memory it is possible to reduce the number of transmissions per node by almost a quadratic factor. 
Gero Greiner and Riko Jacob. The I/O Complexity of Sparse Matrix Dense Matrix Multiplication 
Abstract: We
consider the multiplication of a sparse N x N matrix A with a dense N x
N matrix B in the I/O model. We determine the worstcase nonuniform
complexity of this task up to a constant factor for all
meaningful choices of the parameters N (dimension of the matrices), k
(average number of nonzero entries per column or row in A, i.e., there
are in total kN nonzero entries), M (main memory size), and B (block
size), as long as M > B^2 (tall cache assumption).
For large
and small k, the structure of the algorithm does not need to depend on
the structure of the sparse matrix \A, whereas for intermediate
densities it is possible and necessary to find submatrices that fit in
memory and are slightly denser than on average.
The focus of
this work is asymptotic worstcase complexity, i.e., the existence of
matrices that require a certain number of I/Os and the existence of
algorithms (sometimes depending on the shape of the sparse matrix) that
use only a constant factor more I/Os. 
Rene van Bevern, Hannes Moser and Rolf Niedermeier. Kernelization Through TidyingA Case Study Based on sPlex Cluster Vertex Deletion 
Abstract: We introduce the NPhard graphbased data clustering problem sPlex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are splexes. In an splex, every vertex has an edge to all but at most s1 vertices; cliques are 1plexes. We propose a new method for kernelizing a large class of vertex deletion problems and illustrate it by developing an O(k^2 s^3)vertex problem kernel for sPlex Cluster Vertex Deletion that can be computed in O(k s n^2) time, where n is the number of graph vertices. The corresponding ``kernelization through tidying'' exploits polynomialtime approximation results. 
Janusz Brzozowski, Galina Jiraskova and Baiyu Li. Quotient Complexity of Ideal Languages 
Abstract: We
study the state complexity of regular operations in the class of ideal
languages. A language L which is a subset of A* (the set of all words
over alphabet A) is a right (left) ideal if it satisfies L = LA* (L =
A*L). It is a twosided ideal if L = A*LA*, and an allsided ideal if L
is the shuffle of A* with L. We prefer “quotient complexity” to “state
complexity”, and we use quotient formulas to calculate upper bounds on
quotient complexity, whenever it is convenient. We find tight upper
bounds on the quotient complexity of each type of ideal language in
terms of the complexity of an arbitrary generator and of its minimal
generator, the complexity of the minimal generator, and also on the
operations union, intersection, set difference, symmetric difference,
concatenation, star and reversal of ideal languages. 
Navid Imani and Qianping Gu. Connectivity is Not a Limit for Kernelization: Planar Connected Dominating Set 
Abstract: We prove a small linearsize kernel for the connected dominating set problem in planar graphs through data reduction. Our
set of rules efficiently reduce a planar graph $G$ with $n$ vertices
and connected dominating number $\gamma_c(G)$ to a kernel of size at
most $413\gamma_c(G)$ in $O(n^3)$ answering the question of whether
the connectivity criteria hinders the construction of small kernels,
negatively (in case of the planar connected dominating set). Our result
gives a fixedparameter algorithm of time $(2^{O(\sqrt{\gamma_c(G)})}\cdot \gamma_c(G) + n^3)$ using the standard branchdecomposition based approach. 
Emden Gansner, Yifan Hu, Michael Kaufmann and Stephen Kobourov. Optimal Polygonal Representation of Planar Graphs 
Abstract: In
this paper, we consider the problem of representing graphs by polygons
whose sides touch. We show that at least six sides per polygon are
necessary by constructing a class of planar graphs that cannot be
represented by pentagons. We also show that the lower bound of six
sides is matched by an upper bound of six sides with a linear time
algorithm for representing any planar graph by touching hexagons.
Moreover, our algorithm produces convex polygons with edges with slopes
0, 1, 1. 
Salvatore La Torre, Madhusudan Parthasarathy and Gennaro Parlato. The Language Theory of Bounded ContextSwitching 
Abstract: Concurrent
compositions of recursive programs with finite data are a natural
abstraction model for concurrent programs. Since reachability is
undecidable for this class, a restricted form of reachability has
become popular in the formal verification literature, where the set of
states reached within $k$ contextswitches, for a fixed small constant
$k$, is explored.
In this paper, we consider the language theory of these models. More
precisely, we consider concurrent recursive programs with finite
variable data domains that communicate using shared memory and work
within $k$ roundrobin rounds of contextswitches, and where further
the stack operations are made visible (as in visibly pushdown
automata). We show that the corresponding class of languages, for any
fixed $k$, forms a robust subclass of contextsensitive languages,
closed under all the Boolean operations. Also, surprisingly, the
deterministic and nondeterministic versions of the automatatheoretic
model define the same class of languages.
This class is the
first class we are aware of that includes noncontextfree languages,
and yet has a decidable emptiness problem, is closed under all Boolean operations, and is determinizable. 
Adrian Dumitrescu and Minghui Jiang. Minimumperimeter intersecting polygons 
Abstract: Given a set $\S$ of segments in the plane, a polygon $P$ is an intersecting polygon of $\S$ if every segment in $\S$ intersects the interior or the boundary of $P$. The problem MPIP of computing a minimumperimeter intersecting polygon of a given set of $n$ segments in the plane was first considered by Rappaport in 1995. This problem is not known to be polynomial, nor it is known to be NPhard. Rappaport (1995) gave an exponentialtime exact algorithm for MPIP\@. Hassanzadeh and Rappaport (2009) gave a polynomialtime approximation algorithm with ratio $\frac{\pi}{2} \approx 1.58$. In this paper, we present two improved approximation algorithms for MPIP: a $1.28$approximation algorithm by linear programming, and a polynomialtime approximation scheme by discretization and enumeration. Our algorithms can be generalized for computing an approximate minimumperimeter intersecting polygon of a set of convex polygons in the plane. From the other direction, we show that computing a minimumperimeter intersecting polygon of a set of (not necessarily convex) simple polygons is NPhard. 
Pankaj Agarwal, Jeff Phillips and Bardia Sadri. Lipschitz Unimodal and Isotonic Regression on Paths and Trees 
Abstract: We
describe algorithms for finding the regression of t, a
sequence of values, to the closest sequence s by
mean squared error, so that s is always
increasing (isotonicity) and so the values of two consecutive points do
not increase by too much (Lipschitz). The isotonicity
constraint can be replaced with a unimodular constraint, where there is
exactly one local maximum in s. These algorithm
are generalized from sequences of values to trees of
values. For each scenario we describe nearlinear time
algorithms. 
Hagai Cohen and Ely Porat. Fast Set Intersection and Two Patterns Matching 
Abstract: In this paper we present a new problem, the fast set intersection problem, which is to preprocess a collection of sets in order to efficiently report the intersection of any two sets in the collection. In addition we suggest new solutions for the twodimensional substring indexing problem and the document listing problem for two patterns by reduction to the fast set intersection problem. 
Christine Chung, Katrina Ligett, Kirk Pruhs and Aaron Roth. The Power of Fair Pricing Mechanisms 
Abstract: Abstract.
We explore the revenue capabilities of truthful, monotone (“fair”)
allocation and pricing functions for resourceconstrained auction
mechanisms within a general framework that encompasses unlimited supply
auctions, knapsack auctions, and auctions with general nondecreasing
convex production cost functions. We study and compare the revenue
obtainable in each fair pricing scheme to the profit obtained by the
ideal omniscient multiprice auction. We show (1) for capacitated
knapsack auctions, no constant pricing scheme can achieve any
approximation to the optimal profit, but proportional pricing is as
powerful as general monotone pricing, and (2) for auction settings with
arbitrary bounded nondecreasing convex production cost functions, we
present a proportional pricing mechanism which achieves a
polylogarithmic approximation. Unlike existing approaches,
all of our mechanisms have fair (monotone) prices, and all of our
competitive analysis is with respect to the optimal profit extraction. 
Michael Coury, Pavol Hell, Jan Kratochvil and Tomas Vyskocil. Faithful Representations of Graphs by Islands in the Extended Grid 
Abstract: We investigate embeddings of graphs into the infinite extended grid graph. The problem was motivated by computation on adiabatic quantum computers, but it is related to a number of other well studied grid embedding problems. Such problems typically deal with representing vertices by grid points, and edges by grid paths, while minimizing some objective function such as the area or the maximum length of the grid paths representing the edges. Our particular model, while expressible in this language, is more naturally viewed as one where the vertices are represented by subtrees of the grid (called islands), and the edges are represented by the usual grid edges joining the islands. Somewhat unexpectedly, these graphs turn out to unify such seemingly unrelated graph classes as the string graphs and the induced subgraphs of the extended grid. The connection is established by limiting the size (number of vertices) $k$ of the representing islands. We prove that the problem of representability of $G$ by islands of size at most $k$ is NPcomplete when $k < 3$ or $k > 5$. 
Qi Cheng and YuHsin Li. Finding the smallest gap between sums of square roots 
Abstract: Let $k$ and $n$ be positive integers, $n>k$. Define $r(n,k)$ to be the minimum positive value of $$ \sqrt{a_1} + \cdots + \sqrt{a_k}  \sqrt{b_1}  \cdots \sqrt{b_k}  $$ where $ a_1, a_2, \cdots, a_k, b_1, b_2, \cdots, b_k $ are positive integers no larger than $n$. It is important to find a tight bound for $r(n,k)$, in connectin to the sumofsquareroots problem, a famous open problem in computational geometry. The current best lower bound and upper bound are far apart. In this paper, we present an algorithm to find $r(n,k)$ {\em exactly} in $n^{k+o(k)}$ time and in $ n^{\ceil{k/2}+o(k)} $ space. As an example, we are able to compute $r(100,7)$ exactly in a few hours on one PC. 
Anna Gal and JingTang Jang. The Size and Depth of Layered Boolean Circuits 
Abstract: We
consider the relationship between size and depth for layered Boolean
circuits, synchronous circuits and planar circuits as well as classes
of circuits with small separators. In particular, we show
that every layered Boolean circuit of size $s$ can be simulated by a
layered Boolean circuit of depth $O(\sqrt{s\log s})$. For
planar circuits and synchronous circuits of size $s$, we obtain
simulations of depth $O(\sqrt{s})$. The best known result so
far was by Paterson and Valiant \cite{TCS::PV1976}, and Dymond and
Tompa \cite{JCSS::DT1985}, which holds for general Boolean circuits
and states that $D(f) = O(C(f)/\log C(f))$, where $C(f)$ and $D(f)$ are
the minimum size and depth, respectively, of Boolean circuits computing
$f$. The proof of our main result uses an adaptive strategy
based on the twoperson pebble game introduced by Dymond and Tompa
\cite{JCSS::DT1985}. Improving any of our results by polylog
factors would immediately improve the bounds for general circuits. 
Prosenjit Bose, Paz Carmi, Michiel Smid and Daming Xu. CommunicationEfficient Construction of the Plane Localized Delaunay Graph 
Abstract: Let $V$ be a finite set of points in the plane. We present a $2$local algorithm that constructs a plane $\frac{4 \pi \sqrt{3}}{9}$spanner of the unitdisk graph $\UDG(V)$. Each node can only communicate with nodes that are within unitdistance from it. This algorithm only makes one round of communication and each point of $V$ broadcasts at most $5$ messages. This improves on all previously known messagebounds for this problem. 
Paul Bonsma and Felix Breuer. Counting hexagonal patches and independent sets in circle graphs 
Abstract: A
hexagonal patch is a plane graph in which inner faces have length 6,
inner vertices have degree 3, and boundary vertices have degree 2 or 3.
We consider the following counting problem: given a sequence of
twos and threes, how many hexagonal patches exist with this degree
sequence along the outer face? This problem is motivated by the enumeration of benzenoid hydrocarbons and fullerenes in computational chemistry. We
give the first polynomial time algorithm for this problem. We show that
it can be reduced to counting maximum independent sets in circle
graphs, and give a simple and fast algorithm for this problem. 
Fedor Fomin, Fabrizio Grandoni, Daniel Lokshtanov and Saket Saurabh. Sharp Separation and Applications to Exact and Parameterized Algorithms 
Abstract: Many
divideandconquer algorithms employ the fact that the vertex set of a
graph of bounded treewidth can be separated in two roughly balanced
subsets by removing a small subset of vertices, referred to as a
separator. In this paper we prove a tradeoff between the size of the
separator and the sharpness with which we can fix the size of the two
sides of the partition. Our result appears to be a handy and powerful
tool for the design of exact and parameterized algorithms for NPhard
problems. We illustrate that by presenting two applications.
Our
first application is a parameterized algorithm with running time
O(16^{k+o(k)} + n^{O(1)}) for the Maximum Internal Subtree problem in
directed graphs. This is a significant improvement over the best
previously known parameterized algorithm for the problem by [Cohen et
al.'09], running in time O(49.4^k + n^{O(1)}).
The second
application is a O(2^{n+o(n)}) time algorithm for the Degree
Constrained Spanning Tree problem: find a spanning tree of a graph with
the maximum number of nodes satisfying given degree constraints. This
problem generalizes some wellstudied problems, among them Hamiltonian
Path, Full Degree Spanning Tree, Bounded Degree Spanning
Tree, Maximum Internal Spanning Tree and their edge weighted variants. 
Per Austrin, Siavosh Benabbas and Avner Magen. On Quadratic Threshold CSPs 
Abstract: A predicate P : {1, 1}^k > {0; 1} can be associated with a constraint satisfaction problem MaxCSP(P). P is called "approximation resistant" if Max CSP(P) cannot be approximated better than the approximation obtained by choosing a random assignment, and "approximable" otherwise. This classi cation of predicates has proved to be an important and challenging open problem. Motivated by a recent result of Austrin and Mossel (Computational Complexity, 2009), we consider a natural subclass of predicates de fined by signs of quadratic forms, including the special case of predicates de fined by signs of linear forms, and supply algorithms to approximate them as follows. In the quadratic case we prove that every symmetric predicate is approximable. We introduce a new rounding algorithm for the standard semide nite programming relaxation of Max CSP(P) for any predicate P : {1, 1}^k > {0; 1} and analyze its approximation ratio. Our rounding scheme operates by fi rst manipulating the optimal SDP solution so that all the vectors are nearly perpendicular and then applying a form of hyperplane rounding to obtain an integral solution. The advantage of this method is that we are able to analyze the behaviour of a set of k rounded variables together as opposed to just a pair of rounded variables in most previous methods. In the linear case we prove that a predicate called "Monarchy" is approximable. This predicate is not amenable to our algorithm for the quadratic case, nor to other LP/SDPbased approaches we are aware of. 
Leonor Vázquez and Carles Padró. Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming 
Abstract: Determining
the optimal complexity of secret sharing schemes for every given access
structure is a difficult and longstanding open problem in
cryptology. Lower bounds have been found by a
combinatorial method that uses polymatroids. In this
paper, we point out that the best lower bound that can be obtained by
this method can be determined by using linear programming, and this can
be effectively done for access structures on a small number of
participants. By applying this linear programming
approach, we present better lower bounds on the optimal complexity and
the optimal average complexity of several access
structures. Finally, by adding the Ingleton inequality
to the previous linear programming approach, we find a few examples of
access structures for which there is a gap between the optimal
complexity of linear secret sharing schemes and the combinatorial lower
bound. 
Diego Recalde, Cyriel Rutten, Petra Schuurman and Tjark Vredeveld. Local search performance guarantees for restricted related parallel machine scheduling 
Abstract: We consider the problem of minimizing the makespan on restricted related parallel machines. In restricted machine scheduling each job is only allowed to be scheduled on a subset of machines. We study the worstcase behavior of local search
algorithms. In particular, we analyze the quality of local optima with
respect to the jump, swap, push and lexicographical jump neighborhood. 
Martin Fürer. Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded TreeWidth 
Abstract: An $O(n \log^2 n)$ algorithm is presented to compute all coefficients of the chromatic polynomial of an $n$ vertex graph of bounded treewidth. Previously, it has been known how to evaluate the chromatic polynomial for such graphs in linear time, implying a computation of all coefficients of the chromatic polynomial in quadratic time. 
Daniel Panario, Brett Stevens and Qiang Wang. Ambiguity and Deficiency in Costas Arrays and APN Permutations 
Abstract: We introduce the concepts of weighted ambiguity and deficiency for a mapping between two finite Abelian groups of the same size. Then we study the optimum lower bounds of these measures for a permutation of $\mathbb{Z}_n$ and give a construction of these permutations by modifying some permutation polynomials over finite fields. These permutations are also APN permutations. 
Elizabeth Maltais and Lucia Moura. Finding the best CAFE is NPhard 
Abstract: In
this paper, we look at covering arrays with forbidden edges (CAFEs),
which are used in testing applications (software, networks, circuits,
drug interaction, material mixtures, etc.) where certain combination of
parameter values are forbidden. Covering arrays are classical objects
used in these applications, but the situation of dealing
with forbidden configurations is much less studied. Danziger et. al.
have recently studied this problem and shown some computational
complexity results, but left some important open questions.
Around the same time, Martinez et al. defined and studied error
locating arrays (ELAs), which are very related to CAFEs, leaving
similar computational complexity questions. In particular, these papers
showed polynomial time solvability of the existence of CAFEs and ELAs
for binary alphabets ($g=2$), while their NPhardness for $g\geq 5$.
This not only left open the complexity of determining optimum CAFEs and
ELAs for $g=2,3,4$, but some suspicion that the binary case
might be solved by a polynomial time algorithm. In this paper, we prove
that optimizing CAFEs and ELAs are indeed NPhard even when restricted
to the case of binary alphabets. We also provide a hardness of
approximation result. The proof strategy uses a reduction from edge
clique covers of graphs (ECCs) and cover all cases of $g$. We also
explore important relationships between ECCs and CAFEs and give some
new bounds for uniform ECCs and CAFEs. 