
We study the proportional chore division problem where a protocol wants to
divide an undesirable object, called chore, among $n$ different players. The
goal is to find an allocation such that the cost of the chore assigned to each
player be at most $1/n$ of the total cost. This problem is the dual variant of
the cake cutting problem in which we want to allocate a desirable object.
Edmonds and Pruhs showed that any protocol for the proportional cake cutting
must use at least $\Omega(n \log n)$ queries in the worst case, however,
finding a lower bound for the proportional chore division remained an
interesting open problem. We show that chore division and cake cutting problems
are closely related to each other and provide an $\Omega(n \log n)$ lower bound
for chore division.

The edit distance between two strings is defined as the smallest number of
insertions, deletions, and substitutions that need to be made to transform one
of the strings to another one. Approximating edit distance in subquadratic time
is "one of the biggest unsolved problems in the field of combinatorial pattern
matching". Our main result is a quantum constant approximation algorithm for
computing the edit distance in truly subquadratic time. More precisely, we give
an $O(n^{1.858})$ quantum algorithm that approximates the edit distance within
a factor of $7$. We further extend this result to an $O(n^{1.781})$ quantum
algorithm that approximates the edit distance within a larger constant factor.
Our solutions are based on a framework for approximating edit distance in
parallel settings. This framework requires as black box an algorithm that
computes the distances of several smaller strings all at once. For a quantum
algorithm, we reduce the black box to \textit{metric estimation} and provide
efficient algorithms for approximating it. We further show that this framework
enables us to approximate edit distance in distributed settings. To this end,
we provide a MapReduce algorithm to approximate edit distance within a factor
of $3$, with sublinearly many machines and sublinear memory. Also, our
algorithm runs in a logarithmic number of rounds.

The secretary and the prophet inequality problems are central to the field of
Stopping Theory. Recently, there has been a lot of work in generalizing these
models to multiple items because of their applications in mechanism design. The
most important of these generalizations are to matroids and to combinatorial
auctions (extends bipartite matching). KleinbergWeinberg \cite{KWSTOC12} and
Feldman et al. \cite{feldman2015combinatorial} show that for adversarial
arrival order of random variables the optimal prophet inequalities give a
$1/2$approximation. For many settings, however, it's conceivable that the
arrival order is chosen uniformly at random, akin to the secretary problem. For
such a random arrival model, we improve upon the $1/2$approximation and obtain
$(11/e)$approximation prophet inequalities for both matroids and
combinatorial auctions. This also gives improvements to the results of Yan
\cite{yan2011mechanism} and Esfandiari et al. \cite{esfandiari2015prophet} who
worked in the special cases where we can fully control the arrival order or
when there is only a single item.
Our techniques are threshold based. We convert our discrete problem into a
continuous setting and then give a generic template on how to dynamically
adjust these thresholds to lower bound the expected total welfare.

Graph problems are troublesome when it comes to MapReduce. Typically, to be
able to design algorithms that make use of the advantages of MapReduce,
assumptions beyond what the model imposes, such as the {\em density} of the
input graph, are required.
In a recent shift, a simple and robust model of MapReduce for graph problems,
where the space per machine is set to be $O(V)$ has attracted considerable
attention. We term this model {\em semiMapReduce}, or in short, semiMPC, and
focus on its computational power.
In this short note, we show through a set of simulation methods that semiMPC
is, perhaps surprisingly, almost equivalent to the congested clique model of
distributed computing. However, semiMPC, in addition to round complexity,
incorporates another practically important dimension to optimize: the number of
machines. Furthermore, we show that algorithms in other distributed computing
models, such as CONGEST, can be simulated to run in the same number of rounds
of semiMPC while also using an optimal number of machines. We later show the
implications of these simulation methods by obtaining improved algorithms for
these models using the recent algorithms that have been developed.

We study the problem of fair allocation for indivisible goods. We use the the
maxmin share paradigm introduced by Budish as a measure for fairness. Procaccia
and Wang (EC'14) were first to investigate this fundamental problem in the
additive setting. In contrast to what realworld experiments suggest, they show
that a maxmin guarantee (1MMS allocation) is not always possible even when the
number of agents is limited to 3. While the existence of an approximation
solution (e.g. a $1/2$MMS allocation) is quite straightforward, improving the
guarantee becomes subtler for larger constants. Procaccia provide a proof for
existence of a $2/3$MMS allocation and leave the question open for better
guarantees.
Our main contribution is an answer to the above question. We improve the
result of [Procaccia and Wang] to a $3/4$ factor in the additive setting. The
main idea for our $3/4$MMS allocation method is clustering the agents. To this
end, we introduce three notions and techniques, namely reducibility, matching
allocation, and cycleenvyfreeness, and prove the approximation guarantee of
our algorithm via nontrivial applications of these techniques. Our analysis
involves coloring and double counting arguments that might be of independent
interest.
One major shortcoming of the current studies on fair allocation is the
additivity assumption on the valuations. We alleviate this by extending our
results to the case of submodular, fractionally subadditive, and subadditive
settings. More precisely, we give constant approximation guarantees for
submodular and XOS agents, and a logarithmic approximation for the case of
subadditive agents. Furthermore, we complement our results by providing close
upper bounds for each class of valuation functions. Finally, we present
algorithms to find such allocations for additive, submodular, and XOS settings
in polynomial time.

An everimportant issue is protecting infrastructure and other valuable
targets from a range of threats from vandalism to theft to piracy to terrorism.
The "defender" can rarely afford the needed resources for a 100% protection.
Thus, the key question is, how to provide the best protection using the limited
available resources. We study a practically important class of security games
that is played out in space and time, with targets and "patrols" moving on a
real line. A central open question here is whether the Nash equilibrium (i.e.,
the minimax strategy of the defender) can be computed in polynomial time. We
resolve this question in the affirmative. Our algorithm runs in time polynomial
in the input size, and only polylogarithmic in the number of possible patrol
locations (M). Further, we provide a continuous extension in which patrol
locations can take arbitrary real values. Prior work obtained polynomialtime
algorithms only under a substantial assumption, e.g., a constant number of
rounds. Further, all these algorithms have running times polynomial in M, which
can be very large.

In this paper, we study a stochastic variant of the celebrated kserver
problem. In the kserver problem, we are required to minimize the total
movement of k servers that are serving an online sequence of t requests in a
metric. In the stochastic setting we are given t independent distributions
<P_1, P_2,..., P_t> in advance, and at every time step i a request is drawn
from Pi. Designing the optimal online algorithm in such setting is NPhard,
therefore the emphasis of our work is on designing an approximately optimal
online algorithm. We first show a structural characterization for a certain
class of nonadaptive online algorithms. We prove that in general metrics, the
best of such algorithms has a cost of no worse than three times that of the
optimal online algorithm. Next, we present an integer program that finds the
optimal algorithm of this class for any arbitrary metric. Finally, by rounding
the solution of the linear relaxation of this program, we present an online
algorithm for the stochastic kserver problem with the approximation factor of
3 in the line and circle metrics and O(log n) in a general metric of size n.
Moreover, we define the Uber problem, in which each demand consists of two
endpoints, a source and a destination. We show that given an aapproximation
algorithm for the kserver problem, we can obtain an (a+2)approximation
algorithm for the Uber problem. Motivated by the fact that demands are usually
highly correlated with the time we study the stochastic Uber problem.
Furthermore, we extend our results to the correlated setting where the
probability of a request arriving at a certain point depends not only on the
time step but also on the previously arrived requests.

Hill and Kertz studied the prophet inequality on iid distributions [The
Annals of Probability 1982]. They proved a theoretical bound of $1\frac{1}{e}$
on the approximation factor of their algorithm. They conjectured that the best
approximation factor for arbitrarily large n is $\frac{1}{1+1/e} \approx
0.731$. This conjecture remained open prior to this paper for over 30 years. In
this paper we present a thresholdbased algorithm for the prophet inequality
with n iid distributions. Using a nontrivial and novel approach we show that
our algorithm is a 0.738approximation algorithm. By beating the bound of
$\frac{1}{1+1/e}$, this refutes the conjecture of Hill and Kertz. Moreover, we
generalize our results to noniid distributions and discuss its applications in
mechanism design.

We design the first online algorithm with polylogarithmic competitive ratio
for the edgeweighted degreebounded Steiner forest(EWDBSF) problem and its
generalized variant. We obtain our result by demonstrating a new generic
approach for solving mixed packing/covering integer programs in the online
paradigm. In EWDBSF we are given an edgeweighted graph with a degree bound
for every vertex. Given a root vertex in advance we receive a sequence of
terminal vertices in an online manner. Upon the arrival of a terminal we need
to augment our solution subgraph to connect the new terminal to the root. The
goal is to minimize the total weight of the solution while respecting the
degree bounds on the vertices. In the offline setting edgeweighted
degreebounded Steiner tree (EWDBST) and its many variations have been
extensively studied since early eighties. Unfortunately the recent advancements
in the online network design problems are inherently difficult to adapt for
degreebounded problems. In contrast in this paper we obtain our result by
using structural properties of the optimal solution, and reducing the EWDBSF
problem to an exponentialsize mixed packing/covering integer program in which
every variable appears only once in covering constraints. We then design a
generic integral algorithm for solving this restricted family of IPs. We
demonstrate a new technique for solving mixed packing/covering integer
programs. Define the covering frequency k of a program as the maximum number of
covering constraints in which a variable can participate. Let m denote the
number of packing constraints. We design an online deterministic integral
algorithm with competitive ratio of O(k log m) for the mixed packing/covering
integer programs. We believe this technique can be used as an interesting
alternative for the standard primaldual techniques in solving online problems.

We initiate the study of degreebounded network design problems in the online
setting. The degreebounded Steiner tree problem { which asks for a subgraph
with minimum degree that connects a given set of vertices { is perhaps one of
the most representative problems in this class. This paper deals with its
wellstudied generalization called the degreebounded Steiner forest problem
where the connectivity demands are represented by vertex pairs that need to be
individually connected. In the classical online model, the input graph is given
online but the demand pairs arrive sequentially in online steps. The selected
subgraph starts off as the empty subgraph, but has to be augmented to satisfy
the new connectivity constraint in each online step. The goal is to be
competitive against an adversary that knows the input in advance. We design a
simple greedylike algorithm that achieves a competitive ratio of O(log n)
where n is the number of vertices. We show that no (randomized) algorithm can
achieve a (multiplicative) competitive ratio o(log n); thus our result is
asymptotically tight. We further show strong hardness results for the group
Steiner tree and the edgeweighted variants of degreebounded connectivity
problems. Fourer and Raghavachari resolved the online variant of degreebounded
Steiner forest in their paper in SODA'92. Since then, the natural family of
degreebounded network design problems has been extensively studied in the
literature resulting in the development of many interesting tools and numerous
papers on the topic. We hope that our approach in this paper, paves the way for
solving the online variants of the classical problems in this family of network
design problems.

We study fair allocation of indivisible goods to agents with unequal
entitlements. Fair allocation has been the subject of many studies in both
divisible and indivisible settings. Our emphasis is on the case where the goods
are indivisible and agents have unequal entitlements. This problem is a
generalization of the work by Procaccia and Wang wherein the agents are assumed
to be symmetric with respect to their entitlements. Although Procaccia and Wang
show an almost fair (constant approximation) allocation exists in their
setting, our main result is in sharp contrast to their observation. We show
that, in some cases with $n$ agents, no allocation can guarantee better than
$1/n$ approximation of a fair allocation when the entitlements are not
necessarily equal. Furthermore, we devise a simple algorithm that ensures a
$1/n$ approximation guarantee. Our second result is for a restricted version of
the problem where the valuation of every agent for each good is bounded by the
total value he wishes to receive in a fair allocation. Although this assumption
might seem w.l.o.g, we show it enables us to find a $1/2$ approximation fair
allocation via a greedy algorithm. Finally, we run some experiments on
realworld data and show that, in practice, a fair allocation is likely to
exist. We also support our experiments by showing positive results for two
stochastic variants of the problem, namely stochastic agents and stochastic
items.

We study the problem of computing Nash equilibria of zerosum games. Many
natural zerosum games have exponentially many strategies, but highly
structured payoffs. For example, in the wellstudied Colonel Blotto game
(introduced by Borel in 1921), players must divide a pool of troops among a set
of battlefields with the goal of winning (i.e., having more troops in) a
majority. The Colonel Blotto game is commonly used for analyzing a wide range
of applications from the U.S presidential election, to innovative technology
competitions, to advertisement, to sports. However, because of the size of the
strategy space, standard methods for computing equilibria of zerosum games
fail to be computationally feasible. Indeed, despite its importance, only a few
solutions for special variants of the problem are known.
In this paper we show how to compute equilibria of Colonel Blotto games.
Moreover, our approach takes the form of a general reduction: to find a Nash
equilibrium of a zerosum game, it suffices to design a separation oracle for
the strategy polytope of any bilinear game that is payoffequivalent. We then
apply this technique to obtain the first polytime algorithms for a variety of
games. In addition to Colonel Blotto, we also show how to compute equilibria in
an infinitestrategy variant called the General Lotto game; this involves
showing how to prune the strategy space to a finite subset before applying our
reduction. We also consider the class of dueling games, first introduced by
Immorlica et al. (2011). We show that our approach provably extends the class
of dueling games for which equilibria can be computed: we introduce a new
dueling game, the matching duel, on which prior methods fail to be
computationally feasible but upon which our reduction can be applied.

In the Colonel Blotto game, which was initially introduced by Borel in 1921,
two colonels simultaneously distribute their troops across different
battlefields. The winner of each battlefield is determined independently by a
winnertakeall rule. The ultimate payoff of each colonel is the number of
battlefields he wins. This game is commonly used for analyzing a wide range of
applications such as the U.S presidential election, innovative technology
competitions, advertisements, etc. There have been persistent efforts for
finding the optimal strategies for the Colonel Blotto game. After almost a
century Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin
provided a polytime algorithm for finding the optimal strategies. They first
model the problem by a Linear Program (LP) and use Ellipsoid method to solve
it. However, despite the theoretical importance of their algorithm, it is
highly impractical. In general, even Simplex method (despite its exponential
runningtime) performs better than Ellipsoid method in practice. In this paper,
we provide the first polynomialsize LP formulation of the optimal strategies
for the Colonel Blotto game. We use linear extension techniques. Roughly
speaking, we project the strategy space polytope to a higher dimensional space,
which results in a lower number of facets for the polytope. We use this
polynomialsize LP to provide a novel, simpler and significantly faster
algorithm for finding the optimal strategies for the Colonel Blotto game. We
further show this representation is asymptotically tight in terms of the number
of constraints. We also extend our approach to multidimensional Colonel Blotto
games, and implement our algorithm to observe interesting properties of Colonel
Blotto; for example, we observe the behavior of players in the discrete model
is very similar to the previously studied continuous model.

We study competition in a general framework introduced by Immorlica et al.
and answer their main open question. Immorlica et al. considered classic
optimization problems in terms of competition and introduced a general class of
games called dueling games. They model this competition as a zerosum game,
where two players are competing for a user's satisfaction. In their main and
most natural game, the ranking duel, a user requests a webpage by submitting a
query and players output an ordering over all possible webpages based on the
submitted query. The user tends to choose the ordering which displays her
requested webpage in a higher rank. The goal of both players is to maximize the
probability that her ordering beats that of her opponent and gets the user's
attention. Immorlica et al. show this game directs both players to provide
suboptimal search results. However, they leave the following as their main open
question: "does competition between algorithms improve or degrade expected
performance?" In this paper, we resolve this question for the ranking duel and
a more general class of dueling games.
More precisely, we study the quality of orderings in a competition between
two players. This game is a zerosum game, and thus any Nash equilibrium of the
game can be described by minimax strategies. Let the value of the user for an
ordering be a function of the position of her requested item in the
corresponding ordering, and the social welfare for an ordering be the expected
value of the corresponding ordering for the user. We propose the price of
competition which is the ratio of the social welfare for the worst minimax
strategy to the social welfare obtained by a social planner. We use this
criterion for analyzing the quality of orderings in the ranking duel. We prove
the quality of minimax results is surprisingly close to that of the optimum
solution.

In this paper we consider two special cases of the "coverbypairs"
optimization problem that arise when we need to place facilities so that each
customer is served by two facilities that reach it by disjoint shortest paths.
These problems arise in a network traffic monitoring scheme proposed by Breslau
et al. and have potential applications to content distribution. The
"setdisjoint" variant applies to networks that use the OSPF routing protocol,
and the "pathdisjoint" variant applies when MPLS routing is enabled, making
better solutions possible at the cost of greater operational expense. Although
we can prove that no polynomialtime algorithm can guarantee good solutions for
either version, we are able to provide heuristics that do very well in practice
on instances with realworld network structure. Fast implementations of the
heuristics, made possible by exploiting mathematical observations about the
relationship between the network instances and the corresponding instances of
the coverbypairs problem, allow us to perform an extensive experimental
evaluation of the heuristics and what the solutions they produce tell us about
the effectiveness of the proposed monitoring scheme. For the setdisjoint
variant, we validate our claim of nearoptimality via a new lowerbounding
integer programming formulation. Although computing this lower bound requires
solving the NPhard Hitting Set problem and can underestimate the optimal value
by a linear factor in the worst case, it can be computed quickly by CPLEX, and
it equals the optimal solution value for all the instances in our extensive
testbed.

We introduce a new technique for designing fixedparameter algorithms for cut
problems, namely randomized contractions. We apply our framework to obtain the
first FPT algorithm for the Unique Label Cover problem and new FPT algorithms
with exponential speed up for the Steiner Cut and Node Multiway CutUncut
problems. More precisely, we show the following:
 We prove that the parameterized version of the Unique Label Cover problem,
which is the base of the Unique Games Conjecture, can be solved in 2^{O(k^2\log
\Sigma)}n^4\log n deterministic time (even in the stronger, vertexdeletion
variant) where k is the number of unsatisfied edges and \Sigma is the size of
the alphabet. As a consequence, we show that one can in polynomial time solve
instances of Unique Games where the number of edges allowed not to be satisfied
is upper bounded by O(\sqrt{\log n}) to optimality, which improves over the
trivial O(1) upper bound.
 We prove that the Steiner Cut problem can be solved in 2^{O(k^2\log
k)}n^4\log n deterministic time and \tilde{O}(2^{O(k^2\log k)}n^2) randomized
time where k is the size of the cutset. This result improves the double
exponential running time of the recent work of Kawarabayashi and Thorup
(FOCS'11).
 We show how to combine considering `cut' and `uncut' constraints at the
same time. More precisely, we define a robust problem Node Multiway CutUncut
that can serve as an abstraction of introducing uncut constraints, and show
that it admits an algorithm running in 2^{O(k^2\log k)}n^4\log n deterministic
time where k is the size of the cutset. To the best of our knowledge, the only
known way of tackling uncut constraints was via the approach of Marx,
O'Sullivan and Razgon (STACS'10), which yields algorithms with double
exponential running time.
An interesting aspect of our technique is that, unlike important separators,
it can handle real weights.

Given an edgeweighted directed graph $G=(V,E)$ on $n$ vertices and a set
$T=\{t_1, t_2, \ldots, t_p\}$ of $p$ terminals, the objective of the \scss
($p$SCSS) problem is to find an edge set $H\subseteq E$ of minimum weight such
that $G[H]$ contains an $t_{i}\rightarrow t_j$ path for each $1\leq i\neq j\leq
p$. In this paper, we investigate the computational complexity of a variant of
$2$SCSS where we have demands for the number of paths between each terminal
pair. Formally, the \sharinggeneral problem is defined as follows: given an
edgeweighted directed graph $G=(V,E)$ with weight function $\omega:
E\rightarrow \mathbb{R}^{\geq 0}$, two terminal vertices $s, t$, and integers
$k_1, k_2$ ; the objective is to find a set of $k_1$ paths $F_1, F_2, \ldots,
F_{k_1}$ from $s\leadsto t$ and $k_2$ paths $B_1, B_2, \ldots, B_{k_2}$ from
$t\leadsto s$ such that $\sum_{e\in E} \omega(e)\cdot \phi(e)$ is minimized,
where $\phi(e)= \max \Big\{\{i\in [k_1] : e\in F_i\}\ ,\ \{j\in [k_2] : e\in
B_j\}\Big\}$. For each $k\geq 1$, we show the following: The \sharing problem
can be solved in $n^{O(k)}$ time. A matching lower bound for our algorithm: the
\sharing problem does not have an $f(k)\cdot n^{o(k)}$ algorithm for any
computable function $f$, unless the Exponential Time Hypothesis (ETH) fails.
Our algorithm for \sharing relies on a structural result regarding an optimal
solution followed by using the idea of a "token game" similar to that of
Feldman and Ruhl. We show with an example that the structural result does not
hold for the \sharinggeneral problem if $\min\{k_1, k_2\}\geq 2$. Therefore
\sharing is the most general problem one can attempt to solve with our
techniques.

Optimal stopping theory is a powerful tool for analyzing scenarios such as
online auctions in which we generally require optimizing an objective function
over the space of stopping rules for an allocation process under uncertainty.
Perhaps the most classic problems of stopping theory are the prophet inequality
problem and the secretary problem. The classical prophet inequality states that
by choosing the same threshold OPT/2 for every step, one can achieve the tight
competitive ratio of 0.5. On the other hand, for the basic secretary problem,
the optimal strategy achieves the tight competitive ratio of 1/e.
In this paper, we introduce Prophet Secretary, a natural combination of the
prophet inequality and the secretary problems. An example motivation for our
problem is as follows. Consider a seller that has an item to sell on the market
to a set of arriving customers. The seller knows the types of customers that
may be interested in the item and he has a price distribution for each type:
the price offered by a customer of a type is anticipated to be drawn from the
corresponding distribution. However, the customers arrive in a random order.
Upon the arrival of a customer, the seller makes an irrevocable decision
whether to sell the item at the offered price. We address the question of
finding a strategy for selling the item at a high price.
We show that by using a uniform threshold one cannot break the 0.5 barrier.
However, we show that i) using n distinct nonadaptive thresholds one can
obtain a competitive ratio that goes to (11/e) as n grows; and ii) no online
algorithm can achieve a competitive ratio better than 0.75. Our results improve
the (asymptotic) approximation guarantee of singleitem sequential posted
pricing mechanisms from 0.5 to (11/e) when the order of agents (customers) is
chosen randomly.

Recently [Bhattacharya et al., STOC 2015] provide the first nontrivial
algorithm for the densest subgraph problem in the streaming model with
additions and deletions to its edges, i.e., for dynamic graph streams. They
present a $(0.5\epsilon)$approximation algorithm using $\tilde{O}(n)$ space,
where factors of $\epsilon$ and $\log(n)$ are suppressed in the $\tilde{O}$
notation. However, the update time of this algorithm is large. To remedy this,
they also provide a $(0.25\epsilon)$approximation algorithm using
$\tilde{O}(n)$ space with update time $\tilde{O}(1)$.
In this paper we improve the algorithms by Bhattacharya et al. by providing a
$(1\epsilon)$approximation algorithm using $\tilde{O}(n)$ space. Our
algorithm is conceptually simple  it samples $\tilde{O}(n)$ edges uniformly at
random, and finds the densest subgraph on the sampled graph. We also show how
to perform this sampling with update time $\tilde{O}(1)$. In addition to this,
we show that given oracle access to the edge set, we can implement our
algorithm in time $\tilde{O}(n)$ on a graph in the standard RAM model. To the
best of our knowledge this is the fastest $(0.5\epsilon)$approximation
algorithm for the densest subgraph problem in the RAM model given such oracle
access.
Further, we extend our results to a general class of graph optimization
problems that we call heavy subgraph problems. This class contains many
interesting problems such as densest subgraph, directed densest subgraph,
densest bipartite subgraph, $d$cut and $d$heavy connected component. Our
result, by characterizing heavy subgraph problems, partially addresses open
problem 13 at the IITK Workshop on Algorithms for Data Streams in 2006
regarding the effects of subsampling in this context.

We study the problem of selling $n$ items to a single buyer with an additive
valuation function. We consider the valuation of the items to be correlated,
i.e., desirabilities of the buyer for the items are not drawn independently.
Ideally, the goal is to design a mechanism to maximize the revenue. However, it
has been shown that a revenue optimal mechanism might be very complicated and
as a result inapplicable to realworld auctions. Therefore, our focus is on
designing a simple mechanism that achieves a constant fraction of the optimal
revenue. Babaioff et al. propose a simple mechanism that achieves a constant
fraction of the optimal revenue for independent setting with a single additive
buyer. However, they leave the following problem as an open question: "Is there
a simple, approximately optimal mechanism for a single additive buyer whose
value for $n$ items is sampled from a common basevalue distribution?"
Babaioff et al. show a constant approximation factor of the optimal revenue
can be achieved by either selling the items separately or as a whole bundle in
the independent setting. We show a similar result for the correlated setting
when the desirabilities of the buyer are drawn from a common basevalue
distribution. It is worth mentioning that the core decomposition lemma which is
mainly the heart of the proofs for efficiency of the mechanisms does not hold
for correlated settings. Therefore we propose a modified version of this lemma
which is applicable to the correlated settings as well. Although we apply this
technique to show the proposed mechanism can guarantee a constant fraction of
the optimal revenue in a very weak correlation, this method alone can not
directly show the efficiency of the mechanism in stronger correlations.

An instance of the Connected Maximum Cut problem consists of an undirected
graph G = (V, E) and the goal is to find a subset of vertices S $\subseteq$ V
that maximizes the number of edges in the cut \delta(S) such that the induced
graph G[S] is connected. We present the first nontrivial \Omega(1/log n)
approximation algorithm for the connected maximum cut problem in general graphs
using novel techniques. We then extend our algorithm to an edge weighted case
and obtain a polylogarithmic approximation algorithm. Interestingly, in stark
contrast to the classical maxcut problem, we show that the connected maximum
cut problem remains NPhard even on unweighted, planar graphs. On the positive
side, we obtain a polynomial time approximation scheme for the connected
maximum cut problem on planar graphs and more generally on graphs with bounded
genus.

Online advertising is the main source of revenue for many Internet firms. A
central component of online advertising is the underlying mechanism that
selects and prices the winning ads for a given ad slot. In this paper we study
designing a mechanism for the Combinatorial Auction with Identical Items (CAII)
in which we are interested in selling $k$ identical items to a group of bidders
each demanding a certain number of items between $1$ and $k$. CAII generalizes
important online advertising scenarios such as imagetext and videopod
auctions [GK14]. In imagetext auction we want to fill an advertising slot on a
publisher's web page with either $k$ textads or a single imagead and in
videopod auction we want to fill an advertising break of $k$ seconds with
videoads of possibly different durations.
Our goal is to design truthful mechanisms that satisfy Revenue Monotonicity
(RM). RM is a natural constraint which states that the revenue of a mechanism
should not decrease if the number of participants increases or if a participant
increases her bid.
[GK14] showed that no deterministic RM mechanism can attain PoRM of less than
$\ln(k)$ for CAII, i.e., no deterministic mechanism can attain more than
$\frac{1}{\ln(k)}$ fraction of the maximum social welfare. [GK14] also design a
mechanism with PoRM of $O(\ln^2(k))$ for CAII.
In this paper, we seek to overcome the impossibility result of [GK14] for
deterministic mechanisms by using the power of randomization. We show that by
using randomization, one can attain a constant PoRM. In particular, we design a
randomized RM mechanism with PoRM of $3$ for CAII.

In this paper we present a simple but powerful subgraph sampling primitive
that is applicable in a variety of computational models including dynamic graph
streams (where the input graph is defined by a sequence of edge/hyperedge
insertions and deletions) and distributed systems such as MapReduce. In the
case of dynamic graph streams, we use this primitive to prove the following
results:
 Matching: First, there exists an $\tilde{O}(k^2)$ space algorithm that
returns an exact maximum matching on the assumption the cardinality is at most
$k$. The best previous algorithm used $\tilde{O}(kn)$ space where $n$ is the
number of vertices in the graph and we prove our result is optimal up to
logarithmic factors. Our algorithm has $\tilde{O}(1)$ update time. Second,
there exists an $\tilde{O}(n^2/\alpha^3)$ space algorithm that returns an
$\alpha$approximation for matchings of arbitrary size. (Assadi et al. (2015)
showed that this was optimal and independently and concurrently established the
same upper bound.) We generalize both results for weighted matching. Third,
there exists an $\tilde{O}(n^{4/5})$ space algorithm that returns a constant
approximation in graphs with bounded arboricity.
 Vertex Cover and Hitting Set: There exists an $\tilde{O}(k^d)$ space
algorithm that solves the minimum hitting set problem where $d$ is the
cardinality of the input sets and $k$ is an upper bound on the size of the
minimum hitting set. We prove this is optimal up to logarithmic factors. Our
algorithm has $\tilde{O}(1)$ update time. The case $d=2$ corresponds to minimum
vertex cover.
Finally, we consider a larger family of parameterized problems (including
$b$matching, disjoint paths, vertex coloring among others) for which our
subgraph sampling primitive yields fast, smallspace dynamic graph stream
algorithms. We then show lower bounds for natural problems outside this family.

Given a graph $G$ and an integer $k$, the Feedback Vertex Set (FVS) problem
asks if there is a vertex set $T$ of size at most $k$ that hits all cycles in
the graph. The fixedparameter tractability status of FVS in directed graphs
was a longstanding open problem until Chen et al. (STOC '08) showed that it is
FPT by giving a $4^{k}k!n^{O(1)}$ time algorithm. In the subset versions of
this problems, we are given an additional subset $S$ of vertices (resp., edges)
and we want to hit all cycles passing through a vertex of $S$ (resp. an edge of
$S$). Recently, the Subset Feedback Vertex Set in undirected graphs was shown
to be FPT by Cygan et al. (ICALP '11) and independently by Kakimura et al.
(SODA '12). We generalize the result of Chen et al. (STOC '08) by showing that
Subset Feedback Vertex Set in directed graphs can be solved in time
$2^{O(k^3)}n^{O(1)}$. By our result, we complete the picture for feedback
vertex set problems and their subset versions in undirected and directed
graphs. Besides proving the fixedparameter tractability of Directed Subset
Feedback Vertex Set, we reformulate the random sampling of important separators
technique in an abstract way that can be used for a general family of
transversal problems. Moreover, we modify the probability distribution used in
the technique to achieve better running time; in particular, this gives an
improvement from $2^{2^{O(k)}}$ to $2^{O(k^2)}$ in the parameter dependence of
the Directed Multiway Cut algorithm of Chitnis et al. (SODA '12).

Cournot competition is a fundamental economic model that represents firms
competing in a single market of a homogeneous good. Each firm tries to maximize
its utilitya function of the production cost as well as market price of the
productby deciding on the amount of production. In today's dynamic and
diverse economy, many firms often compete in more than one market
simultaneously, i.e., each market might be shared among a subset of these
firms. In this situation, a bipartite graph models the access restriction where
firms are on one side, markets are on the other side, and edges demonstrate
whether a firm has access to a market or not. We call this game \emph{Network
Cournot Competition} (NCC). In this paper, we propose algorithms for finding
pure Nash equilibria of NCC games in different situations. First, we carefully
design a potential function for NCC, when the price functions for markets are
linear functions of the production in that market. However, for nonlinear price
functions, this approach is not feasible. We model the problem as a nonlinear
complementarity problem in this case, and design a polynomialtime algorithm
that finds an equilibrium of the game for strongly convex cost functions and
strongly monotone revenue functions. We also explore the class of price
functions that ensures strong monotonicity of the revenue function, and show it
consists of a broad class of functions. Moreover, we discuss the uniqueness of
equilibria in both of these cases which means our algorithms find the unique
equilibria of the games. Last but not least, when the cost of production in one
market is independent from the cost of production in other markets for all
firms, the problem can be separated into several independent classical
\emph{Cournot Oligopoly} problems. We give the first combinatorial algorithm
for this widely studied problem.