
Dense kernel matrices $\Theta \in \mathbb{R}^{N \times N}$ obtained from
point evaluations of a covariance function $G$ at locations $\{ x_{i} \}_{1
\leq i \leq N}$ arise in statistics, machine learning, and numerical analysis.
For covariance functions that are Green's functions of elliptic boundary value
problems and homogeneouslydistributed sampling points, we show how to identify
a subset $S \subset \{ 1 , \dots , N \}^2$, with $\# S = O ( N \log (N)
\log^{d} ( N /\epsilon ) )$, such that the zero fillin incomplete Cholesky
factorisation of the sparse matrix $\Theta_{ij} 1_{( i, j ) \in S}$ is an
$\epsilon$approximation of $\Theta$. This factorisation can provably be
obtained in complexity $O ( N \log( N ) \log^{d}( N /\epsilon) )$ in space and
$O ( N \log^{2}( N ) \log^{2d}( N /\epsilon) )$ in time; we further present
numerical evidence that $d$ can be taken to be the intrinsic dimension of the
data set rather than that of the ambient space. The algorithm only needs to
know the spatial configuration of the $x_{i}$ and does not require an analytic
representation of $G$. Furthermore, this factorization straightforwardly
provides an approximate sparse PCA with optimal rate of convergence in the
operator norm. Hence, by using only subsampling and the incomplete Cholesky
factorization, we obtain, at nearly linear complexity, the compression,
inversion and approximate PCA of a large class of covariance matrices. By
inverting the order of the Cholesky factorization we also obtain a solver for
elliptic PDE with complexity $O ( N \log^{d}( N /\epsilon) )$ in space and $O (
N \log^{2d}( N /\epsilon) )$ in time.

This paper shows that $\mathbf{P} = \mathbf{NP}$ by means of oneinthree
SAT, also known as exactly1 3SAT, or X3SAT. $\phi = \bigwedge C_k$ denotes an
X3SAT formula, $C_k = (r_i \odot r_j \odot r_u)$ is a clause, and $\phi(r_j) :=
r_j \wedge \phi$ denotes the truth assignment $r_j = \mathbf{T}$, $r_j \in
\{x_j, \overline{x}_j\}$. The assignment initiates reductions via $\odot$ of
$C_k = (r_j \odot \overline{x}_i \odot x_u)$ into $\psi_k = r_j \wedge x_i
\wedge \overline{x}_u$ for all $C_k \ni r_j$, and $C_k = (\overline{r}_j \odot
r_u \odot r_v)$ into $C_{k'} = (r_u \odot r_v)$ for all $C_k \ni
\overline{r}_j$. These reductions transform $r_j \wedge \phi$ into $\psi(r_j)
\wedge \phi'(r_j)$, unless $\psi(r_j)$ involves a contradiction $x_i \wedge
\overline{x}_i$. Then, $\phi'(r_j) = \bigwedge (C_k \wedge C_{k'})$, and
$\psi(r_j) = \bigwedge (\psi_k \wedge C_{k'})$ such that $C_{k'} = r_i$, thus
$\psi(r_j)$ and $\phi'(r_j)$ are disjoint. Also, $\psi(r_j)$ involves $x_i
\wedge \overline{x}_i$ iff $\not\models \psi(r_j)$, which is trivial to verify.
Furthermore, it is redundant to check if $\not\models \phi'(r_j)$, sketched out
as follows. Any $\psi(r_i)$ is true, $\psi(r_i) \models \psi(r_i  r_j)$, hence
$\psi(r_i  r_j)$ is true for all $r_i$ in $\phi'(r_j)$, which becomes
satisfiable when any $r_j$ such that $\not\models \psi(r_j)$ is removed from
$\phi$, hence any $\overline{r}_j$ is in $\psi$. Thus, $\phi$ transforms into
$\psi \wedge \phi'$, where $\psi = \bigwedge r_i$. If $\psi \supseteq \{x_j,
\overline{x}_j\}$, then $\not\models \phi$, or else $\phi(r_i) = \psi(r_i)
\wedge \phi'(r_i)$ reduces to $\psi(r_i)$ and $\psi \wedge \psi(r_{i_0}) \wedge
\psi(r_{i_1}  r_{i_0}) \wedge \cdots \wedge \psi(r_{i_n}  r_{i_m})$ satisfies
$\phi$, and any $\psi(r_j  r_i)$ and $\psi(r_k  r_j)$ are disjoint. The time
complexity is $O(mn^3)$, therefore $\mathbf{P} = \mathbf{NP}$.

The complexity of computing the Fourier transform is a longstanding open
problem. Very recently, Ailon (2013, 2014, 2015) showed in a collection of
papers that, roughly speaking, a speedup of the Fourier transform computation
implies numerical illcondition. The papers also quantify this tradeoff. The
main method for proving these results is via a potential function called
quasientropy, reminiscent of Shannon entropy. The quasientropy method opens
new doors to understanding the computational complexity of the important
Fourier transformation. However, it suffers from various obvious limitations.
This paper, motivated by one such limitation, partly overcomes it, while at the
same time sheds llight on new interesting, and problems on the intersection of
computational complexity and group theory. The paper also explains why this
research direction, if fruitful, has a chance of solving much bigger questions
about the complexity of the Fourier transform.

We present new results on realtime alternating, private alternating, and
quantum alternating automaton models. Firstly, we show that the emptiness
problem for alternating onecounter automata on unary alphabets is undecidable.
Then, we present two equivalent definitions of realtime private alternating
finite automata (PAFAs). We show that the emptiness problem is undecidable for
PAFAs. Furthermore, PAFAs can recognize some nonregular unary languages,
including the unary squares language, which seems to be difficult even for some
classical counter automata with twoway input. Regarding quantum finite
automata (QFAs), we show that the emptiness problem is undecidable both for
universal QFAs on general alphabets, and for alternating QFAs with two
alternations on unary alphabets. On the other hand, the same problem is
decidable for nondeterministic QFAs on general alphabets. We also show that the
unary squares language is recognized by alternating QFAs with two alternations.

Many natural combinatorial problems can be expressed as constraint
satisfaction problems. This class of problems is known to be NPcomplete in
general, but certain restrictions on the form of the constraints can ensure
tractability. The standard way to parameterize interesting subclasses of the
constraint satisfaction problem is via finite constraint languages. The main
problem is to classify those subclasses that are solvable in polynomial time
and those that are NPcomplete. It was conjectured that if a core of a
constraint language has a weak near unanimity polymorphism then the
corresponding constraint satisfaction problem is tractable, otherwise it is
NPcomplete.
In the paper we present an algorithm that solves Constraint Satisfaction
Problem in polynomial time for constraint languages having a weak near
unanimity polymorphism, which proves the remaining part of the conjecture.

We study the detection problem of finding planted solutions in random
instances of flat satisfiability problems, a generalization of boolean
satisfiability formulas. We describe the properties of random instances of flat
satisfiability, as well of the optimal rates of detection of the associated
hypothesis testing problem. We also study the performance of an algorithmically
efficient testing procedure. We introduce a modification of our model, the
light planting of solutions, and show that it is as hard as the problem of
learning parity with noise. This hints strongly at the difficulty of detecting
planted flat satisfiability for a wide class of tests.

Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an
induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is
definable in $k$variable firstorder logic. The recognition problem of $I(F)$,
known as Induced Subgraph Isomorphism (for the pattern graph $F$), is solvable
in time $O(n^{W[F]})$. Motivated by this fact, we are interested in determining
or estimating the value of $W[F]$. Using Olariu's characterization of pawfree
graphs, we show that $I(K_3+e)$ is definable by a firstorder sentence of
quantifier depth 3, where $K_3+e$ denotes the paw graph. This provides an
example of a graph $F$ with $W[F]$ strictly less than the number of vertices in
$F$. On the other hand, we prove that $W[F]=4$ for all $F$ on 4 vertices except
the paw graph and its complement. If $F$ is a graph on $t$ vertices, we prove a
general lower bound $W[F]>(1/2o(1))t$, where the function in the littleo
notation approaches 0 as $t$ inreases. This bound holds true even for a related
parameter $W^*[F]\le W[F]$, which is defined as the minimum $k$ such that
$I(F)$ is definable in the infinitary logic $L^k_{\infty\omega}$. We show that
$W^*[F]$ can be strictly less than $W[F]$. Specifically, $W^*[P_4]=3$ for $P_4$
being the path graph on 4 vertices.
Using the lower bound for $W[F]$, we also obtain a succintness result for
existential monadic secondorder logic: A usage of just one monadic quantifier
sometimes reduces the firstorder quantifier depth at a superrecursive rate.

We study rewritability of monadic disjunctive Datalog programs, (the
complements of) MMSNP sentences, and ontologymediated queries (OMQs) based on
expressive description logics of the ALC family and on conjunctive queries. We
show that rewritability into FO and into monadic Datalog (MDLog) are decidable,
and that rewritability into Datalog is decidable when the original query
satisfies a certain condition related to equality. We establish
2NExpTimecompleteness for all studied problems except rewritability into MDLog
for which there remains a gap between 2NExpTime and 3ExpTime. We also analyze
the shape of rewritings, which in the MMSNP case correspond to obstructions,
and give a new construction of canonical Datalog programs that is more
elementary than existing ones and also applies to formulas with free variables.

Blind delegation protocols allow a client to delegate a computation to a
server so that the server learns nothing about the input to the computation
apart from its size. For the specific case of quantum computation we know that
blind delegation protocols can achieve informationtheoretic security. In this
paper we prove, provided certain complexitytheoretic conjectures are true,
that the power of informationtheoretically secure blind delegation protocols
for quantum computation (ITSBQC protocols) is in a number of ways constrained.
In the first part of our paper we provide some indication that ITSBQC
protocols for delegating $\sf BQP$ computations in which the client and the
server interact only classically are unlikely to exist. We first show that
having such a protocol with $O(n^d)$ bits of classical communication implies
that $\mathsf{BQP} \subset \mathsf{MA/O(n^d)}$. We conjecture that this
containment is unlikely by providing an oracle relative to which $\mathsf{BQP}
\not\subset \mathsf{MA/O(n^d)}$. We then show that if an ITSBQC protocol
exists with polynomial classical communication and which allows the client to
delegate quantum sampling problems, then there exist nonuniform circuits of
size $2^{n  \mathsf{\Omega}(n/log(n))}$, making polynomiallysized queries to
an $\sf NP^{NP}$ oracle, for computing the permanent of an $n \times n$ matrix.
The second part of our paper concerns ITSBQC protocols in which the client and
the server engage in one round of quantum communication and then exchange
polynomially many classical messages. First, we provide a complexitytheoretic
upper bound on the types of functions that could be delegated in such a
protocol, namely $\mathsf{QCMA/qpoly \cap coQCMA/qpoly}$. Then, we show that
having such a protocol for delegating $\mathsf{NP}$hard functions implies
$\mathsf{coNP^{NP^{NP}}} \subseteq \mathsf{NP^{NP^{PromiseQMA}}}$.

Population protocols have been introduced by Angluin et al. as a model in
which n passively mobile anonymous finitestate agents stably compute a
predicate on the multiset of their inputs via interactions by pairs. The model
has been extended by Guerraoui and Ruppert to yield the community protocol
models where agents have unique identifiers but may only store a finite number
of the identifiers they already heard about. The population protocol models can
only compute semilinear predicates, whereas in the community protocol model
the whole community of agents provides collectively the power of a Turing
machine with a O(n log n) space. We consider variations on the above models and
we obtain a whole landscape that covers and extends already known results: By
considering the case of homonyms, that is to say the case when several agents
may share the same identifier, we provide a hierarchy that goes from the case
of no identifier (i.e. a single one for all, i.e. the population protocol
model) to the case of unique identifiers (i.e. community protocol model). We
obtain in particular that any Turing Machine on space O(logO(1) n) can be
simulated with at least O(logO(1) n) identifiers, a result filling a gap left
open in all previous studies. Our results also extend and revisit in particular
the hierarchy provided by Chatzigiannakis et al. on population protocols
carrying Turing Machines on limited space, solving the problem of the gap left
by this work between peragent space o(log log n) (proved to be equivalent to
population protocols) and O(log n) (proved to be equivalent to Turing
machines).

String matching is the problem of deciding whether a given $n$bit string
contains a given $k$bit pattern. We study the complexity of this problem in
three settings.
Communication complexity. For small $k$, we provide nearoptimal upper and
lower bounds on the communication complexity of string matching. For large $k$,
our bounds leave open an exponential gap; we exhibit some evidence for the
existence of a better protocol.
Circuit complexity. We present several upper and lower bounds on the size of
circuits with threshold and DeMorgan gates solving the string matching problem.
Similarly to the above, our bounds are nearoptimal for small $k$.
Learning. We consider the problem of learning a hidden pattern of length at
most $k$ relative to the classifier that assigns 1 to every string that
contains the pattern. We prove optimal bounds on the VC dimension and sample
complexity of this problem.

We present an O(n^6 ) linear programming model for the traveling salesman
(TSP) and quadratic assignment (QAP) problems. The basic model is developed
within the framework of the TSP. It does not involve the citytocity
variablesbased, traditional TSP polytope referred to in the literature as "the
TSP polytope." We do not model explicit Hamiltonian cycles of the cities.
Instead, we use a timedependent abstraction of TSP tours and develop a direct
extended formulation of the linear assignment problem (LAP) polytope. The model
is exact in the sense that it has integral extreme points which are in
onetoone correspondence with TSP tours. It can be solved optimally using any
linear programming (LP) solver, hence offering a new (incidental) proof of the
equality of the computational complexity classes "P" and "NP." The extensions
of the model to the timedependent traveling salesman problem (TDTSP) as well
as the quadratic assignment problem (QAP) are straightforward. The reasons for
the nonapplicability of existing negative extended formulations results for
"the TSP polytope" to the model in this paper as well as our software
implementation and the computational experimentation we conducted are briefly
discussed.

We study the computational complexity of distance games, a class of
combinatorial games played on graphs. A move consists of colouring an
uncoloured vertex subject to it not being at certain distances determined by
two sets, D and S. D is the set of forbidden distances for colouring vertices
in different colors, while S is the set of forbidden distances for the same
colour. The last player to move wins. Wellknown examples of distance games are
NodeKayles, Snort, and Col, whose complexities were shown to be PSPACEhard.
We show that many more distance games are also PSPACEhard.

In this paper, we introduce a general framework for finegrained reductions
of approximate counting problems to their decision versions. (Thus we use an
oracle that decides whether any witness exists to multiplicatively approximate
the number of witnesses with minimal overhead.) This mirrors a foundational
result of Sipser (STOC 1983) and Stockmeyer (SICOMP 1985) in the
polynomialtime setting, and a similar result of M\"uller (IWPEC 2006) in the
FPT setting. Using our framework, we obtain such reductions for some of the
most important problems in finegrained complexity: the Orthogonal Vectors
problem, 3SUM, and the NegativeWeight Triangle problem (which is closely
related to AllPairs Shortest Path).
We also provide a finegrained reduction from approximate #SAT to SAT.
Suppose the Strong Exponential Time Hypothesis (SETH) is false, so that for
some $1<c<2$ and all $k$ there is an $O(c^n)$time algorithm for kSAT. Then we
prove that for all $k$, there is an $O((c+o(1))^n)$time algorithm for
approximate #$k$SAT. In particular, our result implies that the Exponential
Time Hypothesis (ETH) is equivalent to the seeminglyweaker statement that
there is no algorithm to approximate #3SAT to within a factor of $1+\epsilon$
in time $2^{o(n)}/\epsilon^2$ (taking $\epsilon > 0$ as part of the input).

A colouring of a graph $G=(V,E)$ is a function $c: V\rightarrow\{1,2,\ldots
\}$ such that $c(u)\neq c(v)$ for every $uv\in E$. A $k$regular list
assignment of $G$ is a function $L$ with domain $V$ such that for every $u\in
V$, $L(u)$ is a subset of $\{1, 2, \dots\}$ of size $k$. A colouring $c$ of $G$
respects a $k$regular list assignment $L$ of $G$ if $c(u)\in L(u)$ for every
$u\in V$. A graph $G$ is $k$choosable if for every $k$regular list assignment
$L$ of $G$, there exists a colouring of $G$ that respects $L$. We may also ask
if for a given $k$regular list assignment $L$ of a given graph $G$, there
exists a colouring of $G$ that respects $L$. This yields the $k$Regular List
Colouring problem. For $k\in \{3,4\}$ we determine a family of classes ${\cal
G}$ of planar graphs, such that either $k$Regular List Colouring is
NPcomplete for instances $(G,L)$ with $G\in {\cal G}$, or every $G\in {\cal
G}$ is $k$choosable. By using known examples of non$3$choosable and
non$4$choosable graphs, this enables us to classify the complexity of
$k$Regular List Colouring restricted to planar graphs, planar bipartite
graphs, planar trianglefree graphs and to planar graphs with no $4$cycles and
no $5$cycles. We also classify the complexity of $k$Regular List Colouring
and a number of related colouring problems for graphs with bounded maximum
degree.

We consider two basic algorithmic problems concerning tuples of
(skew)symmetric matrices. The first problem asks to decide, given two tuples
of (skew)symmetric matrices $(B_1, \dots, B_m)$ and $(C_1, \dots, C_m)$,
whether there exists an invertible matrix $A$ such that for every $i\in\{1,
\dots, m\}$, $A^tB_iA=C_i$. We show that this problem can be solved in
randomized polynomial time over finite fields of odd size, the real field, and
the complex field. The second problem asks to decide, given a tuple of square
matrices $(B_1, \dots, B_m)$, whether there exist invertible matrices $A$ and
$D$, such that for every $i\in\{1, \dots, m\}$, $AB_iD$ is (skew)symmetric. We
show that this problem can be solved in deterministic polynomial time over
fields of characteristic not $2$. For both problems we exploit the structure of
the underlying $*$algebras, and utilize results and methods from the module
isomorphism problem.
Applications of our results range from multivariate cryptography, group
isomorphism, to polynomial identity testing. Specifically, these results imply
efficient algorithms for the following problems. (1) Test isomorphism of
quadratic forms with one secret over a finite field of odd size. This problem
belongs to a family of problems that serves as the security basis of certain
authentication schemes proposed by Patarin (Eurocrypto 1996). (2) Test
isomorphism of $p$groups of class 2 and exponent $p$ ($p$ odd) with order
$p^k$ in time polynomial in the group order, when the commutator subgroup is of
order $p^{O(\sqrt{k})}$. (3) Deterministically reveal two families of
singularity witnesses caused by the skewsymmetric structure, which represents
a natural next step for the polynomial identity testing problem following the
direction set up by the recent resolution of the noncommutative rank problem
(Garg et al., FOCS 2016; Ivanyos et al., ITCS 2017).

A tight lower bound for required I/O when computing an ordinary matrixmatrix
multiplication on a processor with two layers of memory is established. Prior
work obtained weaker lower bounds by reasoning about the number of segments
needed to perform $C:=AB$, for distinct matrices $A$, $B$, and $C$, where each
segment is a series of operations involving $M$ reads and writes to and from
fast memory, and $M$ is the size of fast memory. A lower bound on the number of
segments was then determined by obtaining an upper bound on the number of
elementary multiplications performed per segment. This paper follows the same
high level approach, but improves the lower bound by (1) transforming
algorithms for MMM so that they perform all computation via fused multiplyadd
instructions (FMAs) and using this to reason about only the cost associated
with reading the matrices, and (2) decoupling the persegment I/O cost from the
size of fast memory. For $n \times n$ matrices, the lower bound's leadingorder
term is $2n^3/\sqrt{M}$. A theoretical algorithm whose leading terms attains
this is introduced. To what extent the stateoftheart Goto's Algorithm
attains the lower bound is discussed.

The fixed parameter tractable (FPT) approach is a powerful tool in tackling
computationally hard problems. In this paper, we link FPT results to classic
artificial intelligence (AI) techniques to show how they complement each other.
Specifically, we consider the workflow satisfiability problem (WSP) which asks
whether there exists an assignment of authorised users to the steps in a
workflow specification, subject to certain constraints on the assignment. It
was shown by Cohen et al. (JAIR 2014) that WSP restricted to the class of
userindependent constraints (UI), covering many practical cases, admits FPT
algorithms, i.e. can be solved in time exponential only in the number of steps
$k$ and polynomial in the number of users $n$. Since usually $k << n$ in WSP,
such FPT algorithms are of great practical interest. We present a new
interpretation of the FPT nature of the WSP with UI constraints giving a
decomposition of the problem into two levels. Exploiting this twolevel split,
we develop a new FPT algorithm that is by many orders of magnitude faster than
the previous stateoftheart WSP algorithm and also has only polynomialspace
complexity. We also introduce new pseudoBoolean (PB) and Constraint
Satisfaction (CSP) formulations of the WSP with UI constraints which
efficiently exploit this new decomposition of the problem and raise the novel
issue of how to use generalpurpose solvers to tackle FPT problems in a fashion
that meets FPT efficiency expectations. In our computational study, we
investigate, for the first time, the phase transition (PT) properties of the
WSP, under a model for generation of random instances. We show how PT studies
can be extended, in a novel fashion, to support empirical evaluation of scaling
of FPT algorithms.

Approximate counting via correlation decay is the core algorithmic technique
used in the sharp delineation of the computational phase transition that arises
in the approximation of the partition function of antiferromagnetic twospin
models.
Previous analyses of correlationdecay algorithms implicitly depended on the
occurrence of strong spatial mixing (SSM). This means that one uses worstcase
analysis of the recursive procedure that creates the subinstances. We develop
a new analysis method that is more refined than the worstcase analysis. We
take the shape of instances in the computation tree into consideration and
amortise against certain "bad" instances that are created as the recursion
proceeds. This enables us to show correlation decay and to obtain an FPTAS even
when SSM fails.
We apply our technique to the problem of approximately counting independent
sets in hypergraphs with degree upperbound Delta and with a lower bound k on
the arity of hyperedges. Liu and Lin gave an FPTAS for k>=2 and Delta<=5 (lack
of SSM was the obstacle preventing this algorithm from being generalised to
Delta=6). Our technique gives a tight result for Delta=6, showing that there is
an FPTAS for k>=3 and Delta<=6. The best previouslyknown approximation scheme
for Delta=6 is the Markovchain simulation based FPRAS of Bordewich, Dyer and
Karpinski, which only works for k>=8.
Our technique also applies for larger values of k, giving an FPTAS for
k>=Delta. This bound is not substantially stronger than existing randomised
results in the literature. Nevertheless, it gives the first deterministic
approximation scheme in this regime. Moreover, unlike existing results, it
leads to an FPTAS for counting dominating sets in regular graphs with
sufficiently large degree.
We further demonstrate that approximately counting independent sets in
hypergraphs is NPhard even within the uniqueness regime.

Mutual information I in infinite sequences (and in their finite prefixes) is
essential in theoretical analysis of many situations. Yet its right definition
has been elusive for a long time. I address it by generalizing Kolmogorov
Complexity theory from measures to SEMImeasures i.e, infimums of sets of
measures. Being concave rather than linear functionals, semimeasures are quite
delicate to handle. Yet, they adequately grasp various theoretical and
practical scenarios. A simple lower bound i$(\alpha:\beta) = \sup_{x\in N}
(K(x)  K(x\alpha)  K(x\beta)) $ for information turns out tight for
MartinLof random $ \alpha,\beta $. For all sequences I$(\alpha:\beta) $ is
minimum of i$(\alpha':\beta') $ over all $ O(1) $random $ \alpha',\beta' $
such that $ U(\alpha')=\alpha, U(\beta')=\beta $.

Arora, Barak, Brunnermeier, and Ge showed that taking computational
complexity into account, a dishonest seller could strategically place lemons in
financial derivatives to make them substantially less valuable to buyers. We
show that if the seller is required to construct derivatives of a certain form,
then this phenomenon disappears. In particular, we define and construct
pseudorandom derivative families, for which lemon placement only slightly
affects the values of the derivatives. Our constructions use expander graphs.
We study our derivatives in a more general setting than Arora et al. In
particular, we analyze arbitrary tranches of the common collateralized debt
obligations (CDOs) when the underlying assets can have significant
dependencies.

Young flattenings, introduced by Landsberg and Ottaviani, give determinantal
equations for secant varieties and their nonvanishing provides lower bounds
for border ranks of tensors and in particular polynomials. We study
monomialoptimal shapes for Young flattenings, which exhibit the limits of the
Young flattening method. In particular, they provide the best possible lower
bound for large classes of monomials including all monomials up to degree 6,
monomials in 3 variables, and any power of the product of variables. On the
other hand, for degree 7 and higher there are monomials for which no Young
flattening can give a lower bound that matches the conjecturally tight upper
bound of Landsberg and Teitler.

In this paper we present a deterministic polynomial time algorithm for
testing if a symbolic matrix in noncommuting variables over $\mathbb{Q}$ is
invertible or not. The analogous question for commuting variables is the
celebrated polynomial identity testing (PIT) for symbolic determinants. In
contrast to the commutative case, which has an efficient probabilistic
algorithm, the best previous algorithm for the noncommutative setting required
exponential time (whether or not randomization is allowed). The algorithm
efficiently solves the "word problem" for the free skew field, and the identity
testing problem for arithmetic formulae with division over noncommuting
variables, two problems which had only exponentialtime algorithms prior to
this work.
The main contribution of this paper is a complexity analysis of an existing
algorithm due to Gurvits, who proved it was polynomial time for certain classes
of inputs. We prove it always runs in polynomial time. The main component of
our analysis is a simple (given the necessary known tools) lower bound on
central notion of capacity of operators (introduced by Gurvits). We extend the
algorithm to actually approximate capacity to any accuracy in polynomial time,
and use this analysis to give quantitative bounds on the continuity of capacity
(the latter is used in a subsequent paper on BrascampLieb inequalities).
Symbolic matrices in noncommuting variables, and the related structural and
algorithmic questions, have a remarkable number of diverse origins and
motivations. They arise independently in (commutative) invariant theory and
representation theory, linear algebra, optimization, linear system theory,
quantum information theory, approximation of the permanent and naturally in
noncommutative algebra. We provide a detailed account of some of these sources
and their interconnections.

A $\textit{sigma partitioning}$ of a graph $G$ is a partition of the vertices
into sets $P_1, \ldots, P_k$ such that for every two adjacent vertices $u$ and
$v$ there is an index $i$ such that $u$ and $v$ have different numbers of
neighbors in $P_i$. The $\textit{ sigma number}$ of a graph $G$, denoted by
$\sigma(G)$, is the minimum number $k$ such that $ G $ has a sigma partitioning
$P_1, \ldots, P_k$. Also, a $\textit{ lucky labeling}$ of a graph $G$ is a
function $ \ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent
vertices $ v $ and $ u$ of $ G $, $ \sum_{w \sim v}\ell(w)\neq \sum_{w \sim
u}\ell(w) $ ($ x \sim y $ means that $ x $ and $y$ are adjacent). The $\textit{
lucky number}$ of $ G $, denoted by $\eta(G)$, is the minimum number $k $ such
that $ G $ has a lucky labeling $ \ell :V(G) \rightarrow \mathbb{N}_k$. It was
conjectured in [Inform. Process. Lett., 112(4):109112, 2012] that it is $
\mathbf{NP} $complete to decide whether $ \eta(G)=2$ for a given 3regular
graph $G$. In this work, we prove this conjecture. Among other results, we give
an upper bound of five for the sigma number of a uniformly random graph.

In the Planar 3SAT problem, we are given a 3SAT formula together with its
incidence graph, which is planar, and are asked whether this formula is
satisfiable. Since Lichtenstein's proof that this problem is NPcomplete, it
has been used as a starting point for a large number of reductions. In the
course of this research, different restrictions on the incidence graph of the
formula have been devised, for which the problem also remains hard.
In this paper, we investigate the restriction in which we require that the
incidence graph can be augmented by the edges of a Hamiltonian cycle that first
passes through all variables and then through all clauses, in a way that the
resulting graph is still planar. We show that the problem of deciding
satisfiability of a 3SAT formula remains NPcomplete even if the incidence
graph is restricted in that way and the Hamiltonian cycle is given. This
complements previous results demanding cycles only through either the variables
or clauses.
The problem remains hard for monotone formulas, as well as for instances with
exactly three distinct variables per clause. In the course of this
investigation, we show that monotone instances of Planar 3SAT with exactly
three distinct variables per clause are always satisfiable, thus settling the
question by Darmann, D\"ocker, and Dorn on the complexity of this problem
variant in a surprising way.