
We study the following computational problem: for which values of $k$, the
majority of $n$ bits $\text{MAJ}_n$ can be computed with a depth two formula
whose each gate computes a majority function of at most $k$ bits? The
corresponding computational model is denoted by $\text{MAJ}_k \circ
\text{MAJ}_k$. We observe that the minimum value of $k$ for which there exists
a $\text{MAJ}_k \circ \text{MAJ}_k$ circuit that has high correlation with the
majority of $n$ bits is equal to $\Theta(n^{1/2})$. We then show that for a
randomized $\text{MAJ}_k \circ \text{MAJ}_k$ circuit computing the majority of
$n$ input bits with high probability for every input, the minimum value of $k$
is equal to $n^{2/3+o(1)}$. We show a worst case lower bound: if a
$\text{MAJ}_k \circ \text{MAJ}_k$ circuit computes the majority of $n$ bits
correctly on all inputs, then $k\geq n^{13/19+o(1)}$. This lower bound exceeds
the optimal value for randomized circuits and thus is unreachable for pure
randomized techniques. For depth $3$ circuits we show that a circuit with $k=
O(n^{2/3})$ can compute $\text{MAJ}_n$ correctly on all inputs.

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if
there is a homomorphism from graph $G$ to graph $H$ cannot be done in time
$V(H)^{o(V(G))}$. We also show an exponentialtime reduction from Graph
Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a
possibility of $V(H)^{o(V(H))}$time algorithm deciding if graph $G$ is a
subgraph of $H$. For both problems our lower bounds asymptotically match the
running time of bruteforce algorithms trying all possible mappings of one
graph into another. Thus, our work closes the gap in the known complexity of
these fundamental problems.
Moreover, as a consequence of our reductions conditional lower bounds follow
for other related problems such as Locally Injective Homomorphism, Graph
Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic
Assignment Problem.

We prove that unless Exponential Time Hypothesis (ETH) fails, deciding if
there is a homomorphism from graph $G$ to graph $H$ cannot be done in time
$V(H)^{o(V(G))}$. Combined with the reduction of Cygan, Pachocki, and
Soca{\l}a, our result rules out (subject to ETH) a possibility of
$V(G)^{o(V(G))}$time algorithm deciding if graph $H$ is a subgraph of $G$.
For both problems our lower bounds asymptotically match the running time of
bruteforce algorithms trying all possible mappings of one graph into another.
Thus, our work closes the gap in the known complexity of these fundamental
problems.

The Secluded Path problem models a situation where a sensitive information
has to be transmitted between a pair of nodes along a path in a network. The
measure of the quality of a selected path is its exposure, which is the total
weight of vertices in its closed neighborhood. In order to minimize the risk of
intercepting the information, we are interested in selecting a secluded path,
i.e. a path with a small exposure. Similarly, the Secluded Steiner Tree problem
is to find a tree in a graph connecting a given set of terminals such that the
exposure of the tree is minimized. The problems were introduced by Chechik et
al. in [ESA 2013]. Among other results, Chechik et al. have shown that Secluded
Path is fixedparameter tractable (FPT) on unweighted graphs being
parameterized by the maximum vertex degree of the graph and that Secluded
Steiner Tree is FPT parameterized by the treewidth of the graph. In this work,
we obtain the following results about parameterized complexity of secluded
connectivity problems.
We give FPTalgorithms deciding if a graph G with a given cost function
contains a secluded path and a secluded Steiner tree of exposure at most k with
the cost at most C.
We initiate the study of "above guarantee" parameterizations for secluded
problems, where the lower bound is given by the size of a Steiner tree.
We investigate Secluded Steiner Tree from kernelization perspective and
provide several lower and upper bounds when parameters are the treewidth, the
size of a vertex cover, maximum vertex degree and the solution size. Finally,
we refine the algorithmic result of Chechik et al. by improving the exponential
dependence from the treewidth of the input graph.

The graph homomorphism problem (HOM) asks whether the vertices of a given
$n$vertex graph $G$ can be mapped to the vertices of a given $h$vertex graph
$H$ such that each edge of $G$ is mapped to an edge of $H$. The problem
generalizes the graph coloring problem and at the same time can be viewed as a
special case of the $2$CSP problem. In this paper, we prove several lower
bound for HOM under the Exponential Time Hypothesis (ETH) assumption. The main
result is a lower bound $2^{\Omega\left( \frac{n \log h}{\log \log h}\right)}$.
This rules out the existence of a singleexponential algorithm and shows that
the trivial upper bound $2^{{\mathcal O}(n\log{h})}$ is almost asymptotically
tight.
We also investigate what properties of graphs $G$ and $H$ make it difficult
to solve HOM$(G,H)$. An easy observation is that an ${\mathcal O}(h^n)$ upper
bound can be improved to ${\mathcal O}(h^{\operatorname{vc}(G)})$ where
$\operatorname{vc}(G)$ is the minimum size of a vertex cover of $G$. The second
lower bound $h^{\Omega(\operatorname{vc}(G))}$ shows that the upper bound is
asymptotically tight. As to the properties of the "righthand side" graph $H$,
it is known that HOM$(G,H)$ can be solved in time $(f(\Delta(H)))^n$ and
$(f(\operatorname{tw}(H)))^n$ where $\Delta(H)$ is the maximum degree of $H$
and $\operatorname{tw}(H)$ is the treewidth of $H$. This gives
singleexponential algorithms for graphs of bounded maximum degree or bounded
treewidth. Since the chromatic number $\chi(H)$ does not exceed
$\operatorname{tw}(H)$ and $\Delta(H)+1$, it is natural to ask whether similar
upper bounds with respect to $\chi(H)$ can be obtained. We provide a negative
answer to this question by establishing a lower bound $(f(\chi(H)))^n$ for any
function $f$. We also observe that similar lower bounds can be obtained for
locally injective homomorphisms.

In the Shortest Superstring problem we are given a set of strings $S=\{s_1,
\ldots, s_n\}$ and integer $\ell$ and the question is to decide whether there
is a superstring $s$ of length at most $\ell$ containing all strings of $S$ as
substrings. We obtain several parameterized algorithms and complexity results
for this problem.
In particular, we give an algorithm which in time $2^{O(k)}
\operatorname{poly}(n)$ finds a superstring of length at most $\ell$ containing
at least $k$ strings of $S$. We complement this by the lower bound showing that
such a parameterization does not admit a polynomial kernel up to some
complexity assumption. We also obtain several results about "below guaranteed
values" parameterization of the problem. We show that parameterization by
compression admits a polynomial kernel while parameterization "below matching"
is hard.

We introduce a general approach for solving partition problems where the goal
is to represent a given set as a union (either disjoint or not) of subsets
satisfying certain properties. Many NPhard problems can be naturally stated as
such partition problems. We show that if one can find a large enough system of
socalled families with infants for a given problem, then this problem can be
solved faster than by a straightforward algorithm. We use this approach to
improve known bounds for several NPhard problems as well as to simplify the
proofs of several known results.
For the chromatic number problem we present an algorithm with
$O^*((2\varepsilon(d))^n)$ time and exponential space for graphs of average
degree $d$. This improves the algorithm by Bj\"{o}rklund et al. [Theory Comput.
Syst. 2010] that works for graphs of bounded maximum (as opposed to average)
degree and closes an open problem stated by Cygan and Pilipczuk [ICALP 2013].
For the traveling salesman problem we give an algorithm working in
$O^*((2\varepsilon(d))^n)$ time and polynomial space for graphs of average
degree $d$. The previously known results of this kind is a polyspace algorithm
by Bj\"{o}rklund et al. [ICALP 2008] for graphs of bounded maximum degree and
an exponential space algorithm for bounded average degree by Cygan and
Pilipczuk [ICALP 2013].
For counting perfect matching in graphs of average degree~$d$ we present an
algorithm with running time $O^*((2\varepsilon(d))^{n/2})$ and polynomial
space. Recent algorithms of this kind due to Cygan, Pilipczuk [ICALP 2013] and
Izumi, Wadayama [FOCS 2012] (for bipartite graphs only) use exponential space.

Assume that a group of people is going to an excursion and our task is to
seat them into buses with several constraints each saying that a pair of people
does not want to see each other in the same bus. This is a wellknown coloring
problem and it can be solved in $O^*(2^n)$ time by the inclusionexclusion
principle as shown by Bj\"{o}rklund, Husfeldt, and Koivisto in 2009.Another
approach to solve this problem in $O^*(2^n)$ time is to use the fast Fourier
transform. A graph is $k$colorable if and only if the $k$th power of a
polynomial containing a monomial $\prod_{i=1}^n x_i^{[i \in I]}$ for each
independent set $I \subseteq [n]$ of the graph, contains the monomial
$x_1x_2... x_n$.
Assume now that we have additional constraints: the group of people contains
several infants and these infants should be accompanied by their relatives in a
bus. We show that if the number of infants is linear then the problem can be
solved in $O^*((2\varepsilon)^n)$ time. We use this approach to improve known
bounds for several NPhard problems (the traveling salesman problem, the graph
coloring problem, the problem of counting perfect matchings) on graphs of
bounded average degree, as well as to simplify the proofs of several known
results.

These are the lecture notes for the DIMACS Tutorial "Limits of Approximation
Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building,
Rutgers University on 2021 July, 2009. This tutorial was jointly sponsored by
the DIMACS Special Focus on Hardness of Approximation, the DIMACS Special Focus
on Algorithmic Foundations of the Internet, and the Center for Computational
Intractability with support from the National Security Agency and the National
Science Foundation.
The speakers at the tutorial were Matthew Andrews, Sanjeev Arora, Moses
Charikar, Prahladh Harsha, Subhash Khot, Dana Moshkovitz and Lisa Zhang. The
sribes were Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan,
Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov,
David Pritchard and Gwen Spencer.