Let G be a directed graph with n vertices and non-negative weights in its
directed edges, embedded on a surface of genus g, and let F be an arbitrary
face of G. We describe an algorithm to preprocess the graph in O(gn log n)
time, so that the shortest-path distance from any vertex on the boundary of F
to any other vertex in G can be retrieved in O(log n) time. Our result directly
generalizes the O(n log n)-time algorithm of Klein [SODA 2005] for
multiple-source shortest paths in planar graphs.

Given a graph G and integers b and w. The black-and-white coloring problem
asks if there exist disjoint sets of vertices B and W with |B|=b and |W|=w such
that no vertex in B is adjacent to any vertex in W. In this paper we show that
the problem is polynomial when restricted to permutation graphs.

This paper studies the problem of finding a (1+eps)-approximation to positive
semidefinite programs. These are semidefinite programs in which all matrices in
the constraints and objective are positive semidefinite and all scalars are
non-negative. Previous work (Jain and Yao, FOCS'11) gave an NC algorithm that
requires at least Omega((1/eps)^13\log^{13}n) iterations. The algorithm
performs at least Omega(n^\omega) work per iteration, where n is the dimension
of the matrices involved, since each iteration involves computing spectral
decomposition.

In this paper, first we give a sequential linear-time algorithm for the
longest path problem in meshes. This algorithm can be considered as an
improvement of [13]. Then based on this sequential algorithm, we present a
constant-time parallel algorithm for the problem which can be run on every
parallel machine.

We consider the problem of computing the k-sparse approximation to the
discrete Fourier transform of an n-dimensional signal. We show:

* An O(k log n)-time algorithm for the case where the input signal has at
most k non-zero Fourier coefficients, and

* An O(k log n log(n/k))-time algorithm for general input signals.

We apply our new hitting set enumeration algorithm to solve the sudoku
minimum number of clues problem, which is the following question: What is the
smallest number of clues (givens) that a sudoku puzzle may have? It was
conjectured that the answer is 17. We have performed an exhaustive search for a
16-clue sudoku puzzle, and we did not find one, thereby proving that the answer
is indeed 17. This article describes our method and the actual search.

We study the problem of determining strongly connected components (SCCs) of
directed hypergraphs. The main contribution is an algorithm computing the
terminal strongly connected components (ie SCCs which do not reach any other
components than themselves). The time complexity of the algorithm is almost
linear, which is a significant improvement over the known methods which are
quadratic time. This also proves that the problems of testing strong
connectivity, and determining the existence of a sink, can be both solved in
almost linear time in directed hypergraphs.

Motivated by the problems of computing sample covariance matrices, and of
transforming a collection of vectors to a basis where they are sparse, we
present a simple algorithm that computes an approximation of the product of two
n-by-n real matrices A and B. Let ||AB||_F denote the Frobenius norm of AB, and
b be a parameter determining the time/accuracy trade-off.

Tries are popular data structures for storing a set of strings, where common
prefixes are represented by common root-to-node paths. Over fifty years of
usage have produced many variants and implementations to overcome some of their
limitations. We explore new succinct representations of path-decomposed tries
and experimentally evaluate the corresponding reduction in space usage and
memory latency, comparing with the state of the art.

We present new and improved data structures that answer exact node-to-node
distance queries in planar graphs. Such data structures are also known as
distance oracles. For any directed planar graph on n nodes with non-negative
lengths we obtain the following:

* Given a desired space allocation $S\in[n\lg\lg n,n^2]$, we show how to
construct in $\tilde O(S)$ time a data structure of size $O(S)$ that answers
distance queries in $\tilde O(n/\sqrt S)$ time per query.

We present the design and analysis of a near linear-work parallel algorithm
for solving symmetric diagonally dominant (SDD) linear systems. On input of a
SDD $n$-by-$n$ matrix $A$ with $m$ non-zero entries and a vector $b$, our
algorithm computes a vector $\tilde{x}$ such that $\norm[A]{\tilde{x} - A^+b}
\leq \vareps \cdot \norm[A]{A^+b}$ in $O(m\log^{O(1)}{n}\log{\frac1\epsilon})$
work and $O(m^{1/3+\theta}\log \frac1\epsilon)$ depth for any fixed $\theta >
0$.

Advances in DNA sequencing technology will soon result in databases of
thousands of genomes. Within a species, individuals' genomes are almost exact
copies of each other; e.g., any two human genomes are 99.9% the same. Relative
Lempel-Ziv (RLZ) compression takes advantage of this property: it stores the
first genome uncompressed or as an FM-index, then compresses the other genomes
with a variant of LZ77 that copies phrases only from the first genome.

Balanced allocation of online balls-and-bins has long been an active area of
research for efficient load balancing and hashing applications. There exists a
large number of results in this domain with different settings, such as
parallel allocations [1], multi-dimensional allocations [5], weighted balls [4]
etc. For sequential multi-choice allocation where m balls are thrown into n
bins with each ball choosing d (constant) bins independently uniformly at
random, the maximum load of a bin is O(log log n)+m/n with high probability
[3]. This offers the current best known allocation scheme.

Allocation of balls into bins is a well studied abstraction for load
balancing problems.The literature hosts numerous results for sequential(single
dimensional) allocation case when m balls are thrown into n bins. In this paper
we study the symmetric multiple choice process for both unweighted and weighted
balls as well as for both multidimensional and scalar models.Additionally,we
present the results on bounds on gap for (1+beta) choice process with
multidimensional balls and bins.

The problem central to sparse recovery and compressive sensing is that of
stable sparse recovery: we want a distribution of matrices A in R^{m\times n}
such that, for any x \in R^n and with probability at least 2/3 over A, there is
an algorithm to recover x* from Ax with

Recently, Mahoney and Orecchia demonstrated that popular diffusion-based
procedures to compute a quick \emph{approximation} to the first nontrivial
eigenvector of a data graph Laplacian \emph{exactly} solve certain regularized
Semi-Definite Programs (SDPs). In this paper, we extend that result by
providing a statistical interpretation of their approximation procedure.

We consider a nonlinear extension of the generalized network flow model, with
the flow leaving an arc being an increasing concave function of the flow
entering it, as proposed by Truemper and Shigeno. We give the first polynomial
time combinatorial algorithm for solving corresponding optimization problems,
finding a epsilon-approximate solution in O(m(m+\log n)\log(MUm/epsilon))
arithmetic operations and value oracle queries, where M and U are upper bounds
on simple parameters.

Motivated by the imminent growth of massive, highly redundant genomic
databases, we study the problem of compressing a string database while
simultaneously supporting fast random access, substring extraction and pattern
matching to the underlying string(s). Bille et al. (2011) recently showed how,
given a straight-line program with $r$ rules for a string $s$ of length $n$, we
can build an $\Oh{r}$-word data structure that allows us to extract any
substring (s [i..j]) in $\Oh{\log n + j - i}$ time.

Submodular function minimization is a key problem in a wide variety of
applications in machine learning, economics, game theory, computer vision and
many others. The general solver has a complexity of $O(n^6+n^5L)$ where $L$ is
the time required to evaluate the function and $n$ is the number of variables
\cite{orlin09}.

In this paper we demonstrate that, ignoring computational constraints, it is
possible to privately release synthetic databases that are useful for large
classes of queries -- much larger in size than the database itself.
Specifically, we give a mechanism that privately releases synthetic data for a
class of queries over a discrete domain with error that grows as a function of
the size of the smallest net approximately representing the answers to that
class of queries.

In order to evaluate, compare, and tune graph algorithms, experiments on well
designed benchmark sets have to be performed. Together with the goal of
reproducibility of experimental results, this creates a demand for a public
archive to gather and store graph instances. Such an archive would ideally
allow annotation of instances or sets of graphs with additional information
like graph properties and references to the respective experiments and results.
Here we examine the requirements, and introduce a new community project with
the aim of producing an easily accessible library of graphs.

We revisit various string indexing problems with range reporting features,
namely, position-restricted substring searching, indexing substrings with gaps,
and indexing substrings with intervals. We obtain the following main results.
{itemize} We give efficient reductions for each of the above problems to a new
problem, which we call \emph{substring range reporting}. Hence, we unify the
previous work by showing that we may restrict our attention to a single problem
rather than studying each of the above problems individually.

We introduce the problem of Weak Dominance Drawing for general directed
acyclic graphs and we show the connection with the linear extension diameter of
a partial order P. We present complexity results and bounds.

Given a set of wireless links, a fundamental problem is to find the largest
subset that can transmit simultaneously, within the SINR model of interference.
Significant progress on this problem has been made in recent years. In this
note, we study the problem in the setting where we are given a fixed set of
arbitrary powers each sender must use, and an arbitrary gain matrix defining
how signals fade. This variation of the problem appears immune to most
algorithmic approaches studied in the literature.

A dictionary (or map) is a key-value store that requires all keys be unique,
and a multimap is a key-value store that allows for multiple values to be
associated with the same key. We design hashing-based indexing schemes for
dictionaries and multimaps that achieve worst-case optimal performance for
lookups and updates, with a small or negligible probability the data structure
will require a rehash operation, depending on whether we are working in the the
external-memory (I/O) model or one of the well-known versions of the Random
Access Machine (RAM) model.

Until recently, techniques for obtaining lower bounds for kernelization were
one of the most sought after tools in the field of parameterized complexity.
Now, after a strong influx of techniques, we are in the fortunate situation of
having tools available that are even stronger than what has been required in
their applications so far. Based on a result of Fortnow and Santhanam (JCSS
2011), Bodlaender et al.

Sundararajan and Chakraborty (2007) introduced a new version of Quick sort
removing the interchanges. Khreisat (2007) found this algorithm to be competing
well with some other versions of Quick sort. However, it uses an auxiliary
array thereby increasing the space complexity. Here, we provide a second
version of our new sort where we have removed the auxiliary array. This second
improved version of the algorithm, which we call K-sort, is found to sort
elements faster than Heap sort for an appreciably large array size (n <=
70,00,000) for uniform U[0, 1] inputs.

We consider a basic problem in unsupervised learning: learning an unknown
\emph{Poisson Binomial Distribution} over $\{0,1,...,n\}$. A Poisson Binomial
Distribution (PBD) is a sum $X = X_1 + ... + X_n$ of $n$ independent Bernoulli
random variables which may have arbitrary expectations. We work in a framework
where the learner is given access to independent draws from the distribution
and must (with high probability) output a hypothesis distribution which has
total variation distance at most $\eps$ from the unknown target PBD.

In the context of designing a scalable overlay network to support
decentralized topic-based pub/sub communication, the Minimum Topic-Connected
Overlay problem (Min-TCO in short) has been investigated: Given a set of t
topics and a collection of n users together with the lists of topics they are
interested in, the aim is to connect these users to a network by a minimum
number of edges such that every graph induced by users interested in a common
topic is connected. It is known that Min-TCO is NP-hard and approximable within
O(log t) in polynomial time.

In this paper we consider two above lower bound parameterizations of the Node
Multiway Cut problem - above the maximum separating cut and above a natural
LP-relaxation - and prove them to be fixed-parameter tractable. Our results
imply O*(4^k) algorithms for Vertex Cover above Maximum Matching and Almost
2-SAT as well as an O*(2^k) algorithm for Node Multiway Cut with a standard
parameterization by the solution size, improving previous bounds for these
problems.

We study the Travelling Salesman Problem (TSP) on the metric completion of
cubic and subcubic graphs, which is known to be NP-hard. The problem is of
interest because of its relation to the famous 4/3 conjecture for metric TSP,
which says that the integrality gap, i.e., the worst case ratio between the
optimal values of the TSP and its linear programming relaxation (the subtour
elimination relaxation), is 4/3. We present the first algorithm for cubic
graphs with approximation ratio 4/3. The proof uses polyhedral techniques in a
surprising way, which is of independent interest.

Partitioning oracles were introduced by Hassidim et al. (FOCS 2009) as a
generic tool for constant-time algorithms. For any epsilon > 0, a partitioning
oracle provides query access to a fixed partition of the input bounded-degree
minor-free graph, in which every component has size poly(1/epsilon), and the
number of edges removed is at most epsilon*n, where n is the number of vertices
in the graph.

A simple algorithm with quasi-linear time complexity and linear space
complexity for the evaluation of the hypergeometric series with rational
coefficients is constructed. It is shown that this algorithm is suitable in
practical informatics for constructive analogues of often used constants of
analysis.

The Multiple Hypothesis Tracking (MHT) algorithm is known to produce good
results in difficult multi-target tracking situations. However, its
implementation is not trivial, and is associated with a significant programming
effort, code size and long implementation time. We propose a library which
addresses these problems by providing a domain independent implementation of
the most complex MHT operations. We also address the problem of applying
clustering in domain independent manner.

I give an introduction to algorithmic uses of the principle of
inclusion-exclusion. The presentation is intended to be be concrete and
accessible, at the expense of generality and comprehensiveness.

We present a (5/3 - epsilon)-approximation algorithm for some constant
epsilon>0 for the traveling salesman path problem under the unit-weight
graphical metric, and prove an upper bound on the integrality gap of the
path-variant Held-Karp relaxation both under this metric and the general
metric. Given a complete graph with the metric cost and two designated
endpoints in the graph, the traveling salesman path problem is to find a
minimum Hamiltonian path between these two endpoints. The best previously known
performance guarantee for this problem was 5/3 and was due to Hoogeveen.

We study the Minimum Submodular-Cost Allocation problem (MSCA). In this
problem we are given a finite ground set $V$ and $k$ non-negative submodular
set functions $f_1 ,..., f_k$ on $V$. The objective is to partition $V$ into
$k$ (possibly empty) sets $A_1 ,..., A_k$ such that the sum $\sum_{i=1}^k
f_i(A_i)$ is minimized. Several well-studied problems such as the non-metric
facility location problem, multiway-cut in graphs and hypergraphs, and uniform
metric labeling and its generalizations can be shown to be special cases of
MSCA.

We comment on two randomized algorithms for constructing low-rank matrix
decompositions. Both algorithms employ the Subsampled Randomized Hadamard
Transform [14]. The first algorithm appeared recently in [9]; here, we provide
a novel analysis that significantly improves the approximation bound obtained
in [9]. A preliminary version of the second algorithm appeared in [7]; here, we
present a mild modification of this algorithm that achieves the same
approximation bound but significantly improves the corresponding running time.

We solve the dynamic Predecessor Problem with high probability (whp) in
constant time, using only $n^{1+\delta}$ bits of memory, for any constant
$\delta > 0$. The input keys are random wrt a wider class of the well studied
and practically important class of $(f_1, f_2)$-smooth distributions introduced
in \cite{and:mat}. It achieves O(1) whp amortized time. Its worst-case time is
$O(\sqrt{\frac{\log n}{\log \log n}})$. Also, we prove whp $O(\log \log \log
n)$ time using only $n^{1+ \frac{1}{\log \log n}}= n^{1+o(1)}$ bits. Finally,
we show whp $O(\log \log n)$ time using O(n) space.

Courcelle's Theorem states that every problem definable in Monadic
Second-Order logic can be solved in linear time on structures of bounded
treewidth, for example, by constructing a tree automaton that recognizes or
rejects a tree decomposition of the structure. Existing, optimized software
like the MONA tool can be used to build the corresponding tree automata, which
for bounded treewidth are of constant size. Unfortunately, the constants
involved can become extremely large - every quantifier alternation requires a
power set construction for the automaton.

We introduce a variant of modal logic, dubbed EXISTENTIAL COUNTING MODAL
LOGIC (ECML), which captures a vast majority of problems known to be tractable
in single exponential time when parameterized by treewidth. It appears that all
these results can be subsumed by the theorem that model checking of ECML admits
an algorithm with such complexity. We extend ECML by adding connectivity
requirements and, using the Cut&Count technique introduced by Cygan et al.

We give an efficient algorithm which can obtain a relative error
approximation to the spectral norm of a matrix, combining the power iteration
method with some techniques from matrix reconstruction which use random
sampling.

A flaw in the greedy approximation algorithm proposed by Zhang et al. for
minimum connected set cover problem is corrected, and a stronger result on the
approximation ratio of the modified greedy algorithm is established. The
results are now consistent with the existing results on connected dominating
set problem which is a special case of the minimum connected set cover problem.

An \emph{acyclic coloring} of a graph is a proper vertex coloring such that
the union of any two color classes induces a disjoint collection of trees. The
more restricted notion of \emph{star coloring} requires that the union of any
two color classes induces a disjoint collection of stars. We prove that every
acyclic coloring of a cograph is also a star coloring and give a linear-time
algorithm for finding an optimal acyclic and star coloring of a cograph. If the
graph is given in the form of a cotree, the algorithm runs in O(n) time.

A classic versioned data structure in storage and computer science is the
copy-on-write (CoW) B-tree -- it underlies many of today's file systems and
databases, including WAFL, ZFS, Btrfs and more. Unfortunately, it doesn't
inherit the B-tree's optimality properties; it has poor space utilization,
cannot offer fast updates, and relies on random IO to scale. Yet, nothing
better has been developed since. We describe the `stratified B-tree', which
beats the CoW B-tree in every way.

We present an incremental, scalable and efficient dimension reduction
technique for tensors that is based on sparse random linear coding. Data is
stored in a compactified representation with fixed size, which makes memory
requirements low and predictable. Component encoding and decoding are performed
on-line without computationally expensive re-analysis of the data set. The
range of tensor indices can be extended dynamically without modifying the
component representation.

In this paper we are interested in indexing texts for susbstring matching
with one edit error. That is given a text T of n characters over an alphabet of
size sigma, we are asked to build a data structure that answers to the
following query: find all the occ substrings of the text which are at edit
distance at most 1 from a string p of length m. In this paper we show two new
results for this problem. The first result suitable for arbitrary alphabet size
sigma uses O(n(log^epsilon n+ log sigma)) words of space and answers to queries
in time O(m+occ).

A biclique is a set of vertices that induce a bipartite complete graph. A
graph G is biclique-Helly when its family of maximal bicliques satisfies the
Helly property. If every induced subgraph of G is also biclique-Helly, then G
is hereditary biclique-Helly. A graph is C_4-dominated when every cycle of
length 4 contains a vertex that is dominated by the vertex of the cycle that is
not adjacent to it.

We study a location-routing problem in the context of capacitated vehicle
routing. The input is a set of demand locations in a metric space and a fleet
of k vehicles each of capacity Q. The objective is to locate k depots, one for
each vehicle, and compute routes for the vehicles so that all demands are
satisfied and the total cost is minimized. Our main result is a constant-factor
approximation algorithm for this problem. To achieve this result, we reduce to
the k-median-forest problem, which generalizes both k-median and minimum
spanning tree, and which might be of independent interest.

We implement a new algorithm for listing all maximal cliques in sparse graphs
due to Eppstein, L\"offler, and Strash (ISAAC 2010) and analyze its performance
on a large corpus of real-world graphs. Our analysis shows that this algorithm
is the first to offer a practical solution to listing all maximal cliques in
large sparse graphs. All other theoretically-fast algorithms for sparse graphs
have been shown to be significantly slower than the algorithm of Tomita et al.
(Theoretical Computer Science, 2006) in practice. However, the algorithm of
Tomita et al.

Orthogonal Matching Pursuit (OMP) has long been considered a powerful
heuristic for attacking compressive sensing problems; however, its theoretical
development is, unfortunately, somewhat lacking. This paper presents an
improved Restricted Isometry Property (RIP) based performance guarantee for
T-sparse signal reconstruction that asymptotically approaches the conjectured
lower bound given in Davenport et al. We also further extend the
state-of-the-art by deriving reconstruction error bounds for the case of
general non-sparse signals subjected to measurement noise.

We study algorithmic problems in multi-stage open shop processing systems
that are centered around reachability and deadlock detection questions. We
characterize safe and unsafe system states. We show that it is easy to
recognize system states that can be reached from the initial state (where the
system is empty), but that in general it is hard to decide whether one given
system state is reachable from another given system state.

This paper addresses combinatorial optimization scheme for solving the
multicriteria Steiner tree problem for communication network topology design
(e.g., wireless mesh network). The solving scheme is based on several models:
multicriteria ranking, clustering, minimum spanning tree, and minimum Steiner
tree problem. An illustrative numerical example corresponds to designing a
covering long-distance Wi-Fi network (static Ad-Hoc network). The set of
criteria (i.e., objective functions) involves the following: total cost, total
edge length, overall throughput (capacity), and estimate of QoS.

We give the first analysis of the computational complexity of {\it coalition
structure generation over graphs}. Given an undirected graph $G=(N,E)$ and a
valuation function $v:2^N\rightarrow\RR$ over the subsets of nodes, the problem
is to find a partition of $N$ into connected subsets, that maximises the sum of
the components' values.

The paper addresses a new class of combinatorial problems which consist in
restructuring of solutions (as structures) in combinatorial optimization. Two
main features of the restructuring process are examined: (i) a cost of the
restructuring, (ii) a closeness to a goal solution. This problem corresponds to
redesign (improvement, upgrade) of modular systems or solutions. The
restructuring approach is described and illustrated for the following
combinatorial optimization problems: knapsack problem, multiple choice problem,
assignment problem, spanning tree problems.

A natural requirement of many distributed structures is fault-tolerance:
after some failures, whatever remains from the structure should still be
effective for whatever remains from the network. In this paper we examine
spanners of general graphs that are tolerant to vertex failures, and
significantly improve their dependence on the number of faults $r$, for all
stretch bounds.

In this paper we consider methods for dynamically storing a set of different
objects ("modules") in a physical array. Each module requires one free
contiguous subinterval in order to be placed. Items are inserted or removed,
resulting in a fragmented layout that makes it harder to insert further
modules. It is possible to relocate modules, one at a time, to another free
subinterval that is contiguous and does not overlap with the current location
of the module. These constraints clearly distinguish our problem from classical
memory allocation.

We introduce the first self-index based on the Lempel-Ziv 1977 compression
format (LZ77). It is particularly competitive for highly repetitive text
collections such as sequence databases of genomes of related species, software
repositories, versioned document collections, and temporal text databases. Such
collections are extremely compressible but classical self-indexes fail to
capture that source of compressibility.

We study the problem of efficiently clustering protein sequences in a limited
information setting. We assume that we do not know the distances between the
sequences in advance, and must query them during the execution of the
algorithm. Our goal is to find an accurate clustering while keeping the number
of queries small. We model the problem as a point set S with an unknown metric
d on S, and assume that we have access to one versus all distance queries that
given a point s in S return the distances between s and all other points.

Submodular maximization generalizes many fundamental problems in discrete
optimization, including Max-Cut in directed/undirected graphs, maximum
coverage, maximum facility location and marketing over social networks.

We empirically analyze two versions of the well-known "randomized rumor
spreading" protocol to disseminate a piece of information in networks. In the
classical model, in each round each informed node informs a random neighbor. In
the recently proposed quasirandom variant, each node has a (cyclic) list of its
neighbors. Once informed, it starts at a random position of the list, but from
then on informs its neighbors in the order of the list.

The visualization of any graph plays important role in various aspects, such
as graph drawing software. Complex systems (like large databases or networks)
that have a graph structure should be properly visualized in order to avoid
obfuscation. One way to provide an aesthetic improvement to a graph
visualization is to apply a force-directed drawing algorithm to it. This
method, that emerged in the 60's views graphs as spring systems that exert
forces (repulsive or attractive) to the nodes.

In this note we present the worst-character rule, an efficient variation of
the bad-character heuristic for the exact string matching problem, firstly
introduced in the well-known Boyer-Moore algorithm. Our proposed rule selects a
position relative to the current shift which yields the largest average
advancement, according to the characters distribution in the text. Experimental
results show that the worst-character rule achieves very good results
especially in the case of long patterns or small alphabets in random texts and
in the case of texts in natural languages.

It is well-known as an existence result that every 3-connected graph G=(V,E)
on more than 4 vertices admits a sequence of contractions and a sequence of
removal operations to K_4 such that every intermediate graph is 3-connected. We
show that both sequences can be computed in optimal time, improving the
previously best known running times of O(|V|^2) to O(|V|+|E|). This settles
also the open question of finding a linear time 3-connectivity test that is
certifying and extends to a certifying 3-edge-connectivity test in the same
time.

Given a directed graph G and an integer k >= 1, a
k-transitive-closure-spanner (k-TCspanner) of G is a directed graph H that has
(1) the same transitive-closure as G and (2) diameter at most k. In some
applications, the shortcut paths added to the graph in order to obtain small
diameter can use Steiner vertices, that is, vertices not in the original graph
G. The resulting spanner is called a Steiner transitive-closure spanner
(Steiner TC-spanner).

In a ground-breaking paper, Indyk and Woodruff (STOC 05) showed how to
compute $F_k$ (for $k>2$) in space complexity $O(\mbox{\em poly-log}(n,m)\cdot
n^{1-\frac2k})$, which is optimal up to (large) poly-logarithmic factors in $n$
and $m$, where $m$ is the length of the stream and $n$ is the upper bound on
the number of distinct elements in a stream. The best known lower bound for
large moments is $\Omega(\log(n)n^{1-\frac2k})$.

We consider the capacity problem (or, the single slot scheduling problem) in
wireless networks. Our goal is to maximize the number of successful connections
in arbitrary wireless networks where a transmission is successful only if the
signal-to-interference-plus-noise ratio at the receiver is greater than some
threshold. We study a game theoretic approach towards capacity maximization
introduced by Andrews and Dinitz (INFOCOM 2009) and Dinitz (INFOCOM 2010). We
prove vastly improved bounds for the game theoretic algorithm.

Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) show that
if a graph is {\epsilon}-far from bipartite, then the subgraph induced by a
random subset of O(1/{\epsilon}) vertices is bipartite with high probability.
We conjecture that the induced subgraph is {\Omega}~({\epsilon})-far from
bipartite with high probability. Gonen and Ron (RANDOM 2007) proved this
conjecture in the case when the degrees of all vertices are at most
O({\epsilon}n). We give a more general proof that works for any d-regular (or
almost d-regular) graph for arbitrary degree d.

We study the problem of Minimum Feedback Arc-Set in Tournaments (MFAST) in a
setting where each edge from the input graph is given for a cost, and
computations are done for free. We show that a recent PTAS by Kenyon and Schudy
from 2007 in a standard computation model (input for free, computation costs)
can be converted into a algorithm that requires observing only a sample of the
input, with a similar approximation guarantee.

The CUR decomposition provides an approximation of a matrix $X$ that has low
reconstruction error and that is sparse in the sense that the resulting
approximation lies in the span of only a few columns of $X$. In this regard, it
appears to be similar to many sparse PCA methods. However, CUR takes a
randomized algorithmic approach, whereas most sparse PCA methods are framed as
convex optimization problems. In this paper, we try to understand CUR from a
sparse optimization viewpoint.

Given a directed acyclic graph with labeled vertices, we consider the problem
of finding the most common label sequences ("traces") among all paths in the
graph (of some maximum length m). Since the number of paths can be huge, we
propose novel algorithms whose time complexity depends only on the size of the
graph, and on the frequency epsilon of the most frequent traces. In addition,
we apply techniques from streaming algorithms to achieve space usage that
depends only on epsilon, and not on the number of distinct traces.

We introduce a new combinatorial structure: the superselector. We show that
superselectors subsume several important combinatorial structures used in the
past few years to solve problems in group testing, compressed sensing,
multi-channel conflict resolution and data security. We prove close upper and
lower bounds on the size of superselectors and we provide efficient algorithms
for their constructions.

Kernelization algorithms, usually a preprocessing step before other more
traditional algorithms, are very special in the sense that they return
(reduced) instances, instead of final results. This characteristic excludes the
freedom of applying a kernelization algorithm for the weighted version of a
problem to its unweighted instances. Thus with only very few special cases,
kernelization algorithms have to be studied separately for weigthed and
unweighted versions of a single problem.

For almost two decades the question of whether tabu search (TS) or simulated
annealing (SA) performs better for the quadratic assignment problem has been
unresolved. To answer this question satisfactorily, we compare performance at
various values of targeted solution quality, running each heuristic at its
optimal number of iterations for each target. We find that for a number of
varied problem instances, SA performs better for higher quality targets while
TS performs better for lower quality targets.

We propose a framework for the exact probabilistic analysis of window-based
pattern matching algorithms, such as Boyer-Moore, Horspool, Backward DAWG
Matching, Backward Oracle Matching, and more. In particular, we show how to
efficiently obtain the distribution of such an algorithm's running time cost
for any given pattern in a random text model, which can be quite general, from
simple uniform models to higher-order Markov models or hidden Markov models
(HMMs).

Relative worst order analysis is a supplement or alternative to competitive
analysis which has been shown to give results more in accordance with observed
behavior of online algorithms for a range of different online problems. The
contribution of this paper is twofold. First, it adds the static list accessing
problem to the collection of online problems where relative worst order
analysis gives better results. Second, and maybe more interesting, it adds the
non-trivial supplementary proof technique of list factoring to the theoretical
toolbox for relative worst order analysis.

Given samples from two distributions over an $n$-element set, we wish to test
whether these distributions are statistically close. We present an algorithm
which uses sublinear in $n$, specifically, $O(n^{2/3}\epsilon^{-8/3}\log n)$,
independent samples from each distribution, runs in time linear in the sample
size, makes no assumptions about the structure of the distributions, and
distinguishes the cases when the distance between the distributions is small
(less than $\max\{\epsilon^{4/3}n^{-1/3}/32, \epsilon n^{-1/2}/4\}$) or large
(more than $\epsilon$) in $\ell_1$ distance.

Two planar graphs G1 and G2 sharing some vertices and edges are
`simultaneously planar' if they have planar drawings such that a shared vertex
[edge] is represented by the same point [curve] in both drawings. It is an open
problem whether simultaneous planarity can be tested efficiently. We give a
linear-time algorithm to test simultaneous planarity when the two graphs share
a 2-connected subgraph. Our algorithm extends to the case of k planar graphs
where each vertex [edge] is either common to all graphs or belongs to exactly
one of them.

We consider an extension of the {\em popular matching} problem in this paper.
The input to the popular matching problem is a bipartite graph G = (A U B,E),
where A is a set of people, B is a set of items, and each person a belonging to
A ranks a subset of items in an order of preference, with ties allowed. The
popular matching problem seeks to compute a matching M* between people and
items such that there is no matching M where more people are happier with M
than with M*. Such a matching M* is called a popular matching.

In this paper we present novel algorithms for several multidimensional data
processing problems. We consider problems related to the computation of
restricted clusters and of the diameter of a set of points using a new distance
function. We also consider two string (1D data) processing problems, regarding
an optimal encoding method and the computation of the number of occurrences of
a substring within a string generated by a grammar. The algorithms have been
thoroughly analyzed from a theoretical point of view and some of them have also
been evaluated experimentally.

Given strings $P$ and $Q$ the (exact) string matching problem is to find all
positions of substrings in $Q$ matching $P$. The classical Knuth-Morris-Pratt
algorithm [SIAM J. Comput., 1977] solves the string matching problem in linear
time which is optimal if we can only read one character at the time. However,
most strings are stored in a computer in a packed representation with several
characters in a single word, giving us the opportunity to read multiple
characters simultaneously.

The pathwidth of a graph is a measure of how path-like the graph is. Given a
graph G and an integer k, the problem of finding whether there exist at most k
vertices in G whose deletion results in a graph of pathwidth at most one is NP-
complete. We initiate the study of the parameterized complexity of this
problem, parameterized by k.

We consider the following general scheduling problem: The input consists of n
jobs, each with an arbitrary release time, size, and a monotone function
specifying the cost incurred when the job is completed at a particular time.
The objective is to find a preemptive schedule of minimum aggregate cost. This
problem formulation is general enough to include many natural scheduling
objectives, such as weighted flow, weighted tardiness, and sum of flow squared.
Our main result is a randomized polynomial-time algorithm with an approximation
ratio O(log log nP), where P is the maximum job size.

Let C be a finite set of $N elements and R = {R_1,R_2, ..,R_m} a family of M
subsets of C. The family R verifies the consecutive ones property if there
exists a permutation P of C such that each R_i in R is an interval of P. There
already exist several algorithms to test this property in sum_{i=1}^m |R_i|
time, all being involved. We present a simpler algorithm, based on a new
partitioning scheme.

Consider a sequence of bits where we are trying to predict the next bit from
the previous bits. Assume we are allowed to say `predict 0' or `predict 1' or
'no prediction'. We will say that for a sequence of bits the loss of a strategy
is the number of wrong predictions minus the number of right predictions. In
this paper we are interested in strategies that never have a (expected) loss
over any string -- for example the strategy that always makes no prediction can
never have a loss however it also never has a gain.

We give a deterministic, polynomial-time algorithm for approximately counting
the number of {0,1}-solutions to any instance of the knapsack problem. On an
instance of length n with total weight W and accuracy parameter eps, our
algorithm produces a (1 + eps)-multiplicative approximation in time poly(n,log
W,1/eps).

We survey recent results on combinatorial optimization problems in which the
objective function is the entropy of a discrete distribution. These include the
minimum entropy set cover, minimum entropy orientation, and minimum entropy
coloring problems.

Sorting algorithms are the deciding factor for the performance of common
operations such as removal of duplicates or database sort-merge joins. This
work focuses on 32-bit integer keys, optionally paired with a 32-bit value. We
present a fast radix sorting algorithm that builds upon a
microarchitecture-aware variant of counting sort. Taking advantage of virtual
memory and making use of write-combining yields a per-pass throughput
corresponding to at least 88 % of the system's peak memory bandwidth. Our
implementation outperforms Intel's recently published radix sort by a factor of
1.5.

Given n elements with nonnegative integer weights w1,..., wn and an integer
capacity C, we consider the counting version of the classic knapsack problem:
find the number of distinct subsets whose weights add up to at most the given
capacity. We give a deterministic algorithm that estimates the number of
solutions to within relative error 1+-eps in time polynomial in n and 1/eps
(fully polynomial approximation scheme). More precisely, our algorithm takes
time O(n^3 (1/eps) log (n/eps)).

We study combinatorial auctions for the secondary spectrum market. In this
market, short-term licenses shall be given to wireless nodes for communication
in their local neighborhood. In contrast to the primary market, channels can be
assigned to multiple bidders, provided that the corresponding devices are well
separated such that the interference is sufficiently low.

We present sublinear-time (randomized) algorithms for finding simple cycles
of length at least $k\geq 3$ and tree-minors in bounded-degree graphs. The
complexity of these algorithms is related to the distance of the graph from
being $C_k$-minor-free (resp., free from having the corresponding tree-minor).
In particular, if the graph is far (i.e., $\Omega(1)$-far) {from} being
cycle-free, i.e.

In this paper we initiate the study of minimizing power consumption in the
broadcast scheduling model. In this setting there is a wireless transmitter.
Over time requests arrive at the transmitter for pages of information. Multiple
requests may be for the same page. When a page is transmitted, all requests for
that page receive the transmission simulteneously. The speed the transmitter
sends data at can be dynamically scaled to conserve energy.

In this paper, we consider lower bounds on the query complexity for testing
CSPs in the bounded-degree model.

We study the problem of ranking with submodular valuations. An instance of
this problem consists of a ground set $[m]$, and a collection of $n$ monotone
submodular set functions $f^1, \ldots, f^n$, where each $f^i: 2^{[m]} \to R_+$.
An additional ingredient of the input is a weight vector $w \in R_+^n$. The
objective is to find a linear ordering of the ground set elements that
minimizes the weighted cover time of the functions.

The replacement paths problem for directed graphs is to find for given nodes
s and t and every edge e on the shortest path between them, the shortest path
between s and t which avoids e. For unweighted directed graphs on n vertices,
the best known algorithm runtime was \tilde{O}(n^{2.5}) by Roditty and Zwick.
For graphs with integer weights in {-M,...,M}, Weimann and Yuster recently
showed that one can use fast matrix multiplication and solve the problem in
O(Mn^{2.584}) time, a runtime which would be O(Mn^{2.33}) if the exponent
\omega of matrix multiplication is 2.

In the Matroid Secretary Problem, introduced by Babaioff et al. [SODA 2007],
the elements of a given matroid are presented to an online algorithm in random
order. When an element is revealed, the algorithm learns its weight and decides
whether or not to select it under the restriction that the selected elements
form an independent set in the matroid. The objective is to maximize the total
weight of the chosen elements. In the most studied version of this problem, the
algorithm has no information about the weights beforehand. We refer to this as
the zero information model.

The usefulness of parameterized algorithmics has often depended on what
Niedermeier has called, "the art of problem parameterization". In this paper we
introduce and explore a novel but general form of parameterization: the number
of numbers. Several classic numerical problems, such as Subset Sum, Partition,
3-Partition, Numerical 3-Dimensional Matching, and Numerical Matching with
Target Sums, have multisets of integers as input.

We show that the three-dimensional layers-of-maxima problem can be solved in
$o(n\log n)$ time in the word RAM model. Our algorithm runs in $O(n(\log \log
n)^3)$ time and uses $O(n)$ space. We also describe an algorithm that uses
optimal $O(n)$ space and solves the three-dimensional layers-of-maxima problem
in $O(n\log n)$ time in the pointer machine model.

A quantum search algorithm based on the partial adiabatic
evolution\cite{Tulsi2009} is provided. We calculate its time complexity by
studying the Hamiltonian in a two-dimensional Hilbert space. It is found that
the algorithm improves the time complexity, which is $O(\sqrt{N/M})$, of the
local adiabatic search algorithm\cite{Roland2002}, to $O(\sqrt{N}/M)$.

We study the following vertex-weighted online bipartite matching problem:
$G(U, V, E)$ is a bipartite graph. The vertices in $U$ have weights and are
known ahead of time, while the vertices in $V$ arrive online in an arbitrary
order and have to be matched upon arrival. The goal is to maximize the sum of
weights of the matched vertices in $U$. When all the weights are equal, this
reduces to the classic \emph{online bipartite matching} problem for which Karp,
Vazirani and Vazirani gave an optimal $\left(1-\frac{1}{e}\right)$-competitive
algorithm in their seminal work~\cite{KVV90}.

We present an efficient algorithm for performing cuckoo hashing in the
MapReduce parallel model of computation and we show how this result in turn
leads to improved methods for performing data-oblivious RAM simulations.

The Traveling Tournament Problem (TTP) is a challenging combinatorial
optimization problem that has attracted the interest of researchers around the
world. This paper proposes an improved search neighbourhood for the TTP that
has been tested in a simulated annealing context. The neighbourhood encompasses
both feasible and infeasible schedules, and can be generated efficiently.

Given a capacitated graph $G = (V,E)$ and a set of terminals $K \sse V$, how
should we produce a graph $H$ only on the terminals $K$ so that every
(multicommodity) flow between the terminals in $G$ could be supported in $H$
with low congestion, and vice versa? (Such a graph $H$ is called a
$flow-sparsifier$ for $G$.) What if we want $H$ to be a "simple" graph? What if
we allow $H$ to be a convex combination of simple graphs?

Sequence assembly from short reads is an important problem in biology. It is
known that solving the sequence assembly problem exactly on a bi-directed de
Bruijn graph or a string graph is intractable. However finding a Shortest
Double stranded DNA string (SDDNA) containing all the k-long words in the reads
seems to be a good heuristic to get close to the original genome. This problem
is equivalent to finding a cyclic Chinese Postman (CP) walk on the underlying
un-weighted bi-directed de Bruijn graph built from the reads.

In this paper, we reduce Prize-Collecting Steiner TSP (PCTSP),
Prize-Collecting Stroll (PCS), Prize-Collecting Steiner Tree (PCST),
Prize-Collecting Steiner Forest (PCSF) and more generally Submodular
Prize-Collecting Steiner Forest (SPCSF) on planar graphs (and more generally
bounded-genus graphs) to the same problems on graphs of bounded treewidth.

We consider the problem of doing fast and reliable estimation of the number
of non-zero entries in a sparse boolean matrix product. This problem has
applications in databases and computer algebra. Let n denote the total number
of non-zero entries in the input matrices. We show how to compute a 1 +-
epsilon approximation (with small probability of error) in expected time O(n)
for any epsilon > 4/\sqrt[4]{n}. The previously best estimation algorithm, due
to Cohen (JCSS 1997), uses time O(n/epsilon^2).

Deciding whether a graph can be embedded in a grid using only unit-length
edges is NP-complete, even when restricted to binary trees. However, it is not
difficult to devise a number of graph classes for which the problem is
polynomial, even trivial. A natural step, outstanding thus far, was to provide
a broad classification of graphs that make for polynomial or NP-complete
instances. We provide such a classification based on the set of allowed vertex
degrees in the input graphs, yielding a full dichotomy on the complexity of the
problem.

In a balancing network each processor has an initial collection of unit-size
jobs (tokens) and in each round, pairs of processors connected by balancers
split their load as evenly as possible. An excess token (if any) is placed
according to some predefined rule. As it turns out, this rule crucially affects
the performance of the network. In this work we propose a model that studies
this effect. We suggest a model bridging the uniformly-random assignment rule,
and the arbitrary one (in the spirit of smoothed-analysis).

We analyse some QR decomposition algorithms, and show that the I/O complexity
of the tile based algorithm is asymptotically the same as that of matrix
multiplication. This algorithm, we show, performs the best when the tile size
is chosen so that exactly one tile fits in the main memory. We propose a
constant factor improvement, as well as a new recursive cache oblivious
algorithm with the same asymptotic I/O complexity.

Analysing Web graphs has applications in determining page ranks, fighting Web
spam, detecting communities and mirror sites, and more. This study is however
hampered by the necessity of storing a major part of huge graphs in the
external memory, which prevents efficient random access to edge (hyperlink)
lists.

Information diffusion and virus propagation are fundamental processes talking
place in networks. While it is often possible to directly observe when nodes
become infected, observing individual transmissions (i.e., who infects whom or
who influences whom) is typically very difficult. Furthermore, in many
applications, the underlying network over which the diffusions and propagations
spread is actually unobserved. We tackle these challenges by developing a
method for tracing paths of diffusion and influence through networks and
inferring the networks over which contagions propagate.

The problems of random projections and sparse reconstruction have much in
common and individually received much attention. Surprisingly, until now they
progressed in parallel and remained mostly separate. Here, we employ new tools
from probability in Banach spaces that were successfully used in the context of
sparse reconstruction to advance on an open problem in random pojection. In
particular, we generalize and use an intricate result by Rudelson and Vershynin
for sparse reconstruction which uses Dudley's theorem for bounding Gaussian
processes.

The rank and select operations over a string of length n from an alphabet of
size $\sigma$ have been used widely in the design of succinct data structures.
In many applications, the string itself need be maintained dynamically,
allowing characters of the string to be inserted and deleted. Under the word
RAM model with word size $w=\Omega(\lg n)$, we design a succinct representation
of dynamic strings using $nH_0 + o(n)\lg\sigma + O(w)$ bits to support rank,
select, insert and delete in $O(\frac{\lg n}{\lg\lg n}(\frac{\lg \sigma}{\lg\lg
n}+1))$ time. When the alphabet size is small, i.e.

In this paper we develop algorithms for approximating matrix multiplication
with respect to the spectral norm. Let A\in{\RR^{n\times m}} and B\in{\RR^{n
\times p}} be two matrices and \eps>0. We approximate the product A^\top B
using two down-sampled sketches, \tilde{A}\in{\RR^{t\times m}} and
\tilde{B}\in{\RR^{t\times p}}, such that \norm{\tilde{A}^\top \tilde{B} -
A^\top B} \leq \eps \norm{A}\norm{B} with constant probability. We use two
different sampling procedures for constructing \tilde{A} and \tilde{B}; one of
them is done by i.i.d.