Is there an efficient program for generating a Sidon sequence? I would need a Sidon sequence of about $10^9$ elements.
I found math papers like [1] that explain how to generate Sidon sequences but it seems a lot of pain to write the corresponding program.

Are you aware of any existing program that generates a dense enough and large enough Sidon sequence ?

Extra: my real constraint for the sequence is $a+a′ , a \lt a′ ,~ a,a′ ∈ A$ instead of the true Sidon sequence property $a+a ′ , a ≤ a ′ , a, a ′ ∈ A$.
So a Sidon sequence would do the job but I could hope for a denser sequence by tuning the program.

[1] Javier Cilleruelo, "Infinite Sidon sequences", eprint on arXiv: http://arxiv.org/abs/1209.0326

Consider a prime $p$ and let $g$ be a primitive root mod $p$. The set $ A= \{ (x,g^{x}), x=0,..,p-2\}$ is a Sidon set in $Z_{p-1} \times Z_{p}$. This is an explicit method.

Now, since $Z_{p-1} \times Z_{p}$ is isomorphic to $Z_{p(p-1)}$, then the natural isomorphism $\Phi$ maps $A$ in $\Phi(A)$, which is also a Sidon set in $Z_{p(p-1)}$, which is a Sidon set in $[1,p(p-1)]$.


Lower bounds and impossibility results for distributed transactions I am studying on distributed transactions, mainly on the correctness criteria (e.g., serializability (SR) and snapshot isolation (SI) in replicated settings) and their implementations.

To avoid unnecessary efforts, I would like to know that

  What are the known (or conjectural) impossibility results and lower bounds on the complexity of implementing distributed transactions conforming to some correctness criterion and/or some progress condition?

For example,

  Is it possible to implement SI in a wait-free/lock-free manner in replicated settings?

The arXiv paper "Non-Monotonic Snapshot Isolation" [1] proves several impossibility theorems demonstrating that SI (Snapshot Isolation) and GPR (Genuine Partial Replication) are incompatible.

To this end, it first decomposes SI into four properties:

  Decomposition theorem: $SI = ACA \cap SCONS \cap MON \cap WCF$

where,

$ACA$: avoiding cascading aborts; $SCONS = SCONSa \cap SCONSb$: strictly consistent snapshots; $MON$: snapshot monotonicity; and $WCF$: write-conflict freedom.

Then, it gives the following

  Impossibility theorem: None of SCONSa, SCONSb, and MON  is attainable in some asynchronous failure-free GPR system with obstruction-free updates (OFU) and wait-free queries (WFQ).

[1] Non-Monotonic Snapshot Isolation by Masoud Saeida et al@arXiv'2013


Complexity of Finding Largest Set of Intersecting Convex Polytopes I have a set of $n$ convex polytopes, and I wish to find the largest subset of those polytopes that shares at least one point in common. I think that this problem should be NP-hard, but I am struggling to find a reduction and I can't find any relevant literature on the subject. Can anyone help me with a reduction or point me towards something I can read about? Thanks!

Suppose that the dimension $d$ of the Euclidean space is fixed, and that the input consists of $n$ convex polytopes in $\mathbb{R}^d$ that altogether have $p$ facets.

Let $h_1,\ldots,h_p$ denote the supporting hyperplanes for the $p$ facets of the input polytopes. The arrangement of $h_1,\ldots,h_p$ is the decomposition of $\mathbb{R}^d$ into connected open cells of dimensions $0,1,\ldots,d$.
It is well-known that the arrangement has combinatorial complexity $O(p^d)$ and that it can be computed in time $O(p^d)$; see for instance

  Chapter 28 "Arrangements" by D. Halperin and M. Sharir,
  in Handbook of Discrete and Computational Geometry (edited by J.E. Goodman, J. O'Rourke, and C.D. Tóth)
  https://www.csun.edu/~ctoth/Handbook/chap28.pdf

So you may compute the arrangement in polynomial time $O(p^d)$, and then compute for every cell $C$ in the arrangement the number $x(C)$ of input polytopes that contain $C$.
The maximum of all these numbers $x(C)$ yields the answer to your question.


How to prove $\tilde{\mathbb{E}}PQ=0$ when $\tilde{\mathbb{E}}P^2 = 0$? Let $\tilde{\mathbb{E}}$ be a degree-$r$ pseudo-distribution. If $\tilde{\mathbb{E}}P^2 = 0$, how to prove that $\tilde{\mathbb{E}}PQ=0$ for all polynomials $Q$ such that $\mathrm{deg}(PQ)\le r$?

We can prove the case $\mathrm{deg}(PQ) < r$ by induction, but it fails when $\mathrm{deg}(PQ) = r$.

That implication is not actually true.
Consider $P$, $Q$, and the pseudodistribution given by:

$$P = x, \quad Q = x^3,$$
$$r = 4,$$
$$\mathbb{\tilde E} 1 = 1, \quad \mathbb{\tilde E} x = 0,$$
$$\mathbb{\tilde E} x^2 = 0, \quad \mathbb{\tilde E} x^3 = 0,$$
$$\mathbb{\tilde E} x^4 = 1$$

Then $\mathbb{\tilde E}P^2 = 0$ but $\mathbb{\tilde E} PQ = 1$.

This is a valid degree-4 pseudodistribution since its moment matrix is positive-semidefinite.

$$ \left[\begin{array}{ccc} \mathbb{\tilde E}1 & \mathbb{\tilde E}x & \mathbb{\tilde E}x^2 \\ \mathbb{\tilde E}x & \mathbb{\tilde E}x^2 & \mathbb{\tilde E}x^3 \\ \mathbb{\tilde E}x^2 & \mathbb{\tilde E}x^3 & \mathbb{\tilde E}x^4 \\\end{array}\right] = \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 & 0  \\ 0 & 0 & 1 \\\end{array}\right] $$


Using negative results to prove positive results in computability theory Many results in cryptography depend on impossibility results/conjectures in complexity theory. For example, public-key cryptography using RSA is believed to be possible because of the conjecture about infeasibility of the factoring (and the modular root finding problems).

My question is :

  do we have similar results in computability theory? Are there interesting positive constructions using negative impossibility results?

E.g., does the undecidability of the halting problem allow us to perform tasks that we would not be able to do if the halting problem was decidable?

In some sense, this is what the theory of parametricity is all about.

Data abstraction is how we ensure that no client of a module can access the elements of a module except according to the interface exposed by the module.
We rely on this to ensure that the internal invariants of data structures cannot be broken by the clients of a module -- eg, if you access a balanced tree only via the published interface, then it follows that the tree will always be balanced.

So we use a negative property -- that no possible client can break the abstraction boundary -- to deduce a positive one -- that the data representation invariant always holds.


Good algorithms to solve ATSP What are some good neighborhood-based local search algorithms or strategies to solve the Asymmetric TSP ? I see many 2-OPT and K-opt based algorithms (e.g. Lin-Kernighan implementations), but I think that these algorithms are more time consuming since the evaluation complexity is not constant (assuming my calculations are correct).

What are some good alternative that are less time consuming? are their any technique swapping nodes for example? Could you suggest a good paper about such algorithms?

You can also transform the ATSP to TSP; the process requires doubling number of nodes (adding dummy cities).

http://www.sciencedirect.com/science/article/pii/0167637783900482
http://www.sciencedirect.com/science/article/pii/0167637786900817


Why do we use single tape Turing machines for time complexity? As you know there are many anomolies for the single tape Turing machines when the time is $o(n^2)$: multi-tape TM simulation, simulation of larger tape alphabet with just $\{0,1,b\}$, time constructability, non-tightness of time hierarchy theorem, ...

Also results like $\mathsf{DTime}(o(n\lg n)=\mathsf{Reg}$, and very model specific $O(n^2)$ time lowerbounds for simple problems (that don't translate to even superlinear lowerbounds on two tape TMs).

For space complexity, we use a model where we have a separate read only input tape, which is more natural and robust.

A TM model with multiple tapes (or at least 2 working tapes) would be much more robust and will not lead to anomalies like those I listed above. I once asked a prominent complexity theorist who has proven simulation results in the early years of complexity theory if he knows any improvements on one of these old results and the reply was that he doesn't think that "questions about the one tape model are that important".

If we change the standard model for time complexity to a two tape TMs, reasonable results in complexity theory will not change and we avoid these anomalies caused by particular model. So my question is:

  is there any reason why the time complexity is still defined in terms of single tape TMs?
  (other than historical reasons)

I've seen texts define TIME( $f(n)$ ) using multi-tape Turing machines, but Sipser uses a single tape machine.  You've almost surely first encountered this material through Sipser because it's so fabulously well written.

There is a crystal clear pedagogical reason why Sipser does this, namely the course just naturally flows that way because :

You should introduce the single tape machine before the multi-tape machine, otherwise steepens the learning curve.
There is no compelling reason to introduce the multi-tape machine before introducing O($\cdot$) and TIME($\cdot$) for single tape machines.
You should ideally compare the multi-tape machine with the single tape machine the moment you introduce the multi-tape machine, otherwise the prolonged ignorance will lead to additional confusion.
You could omit introducing the analogous TIME classes for multi-tape machines, thus simplifying notation overall.

There is no reason to quibble over conceptual cleanliness when the pedagogy so clearly dictates the easiest path, and every computer science undergrad must take this elementary course, including all those who still don't understand proofs.


What's the intuition behind Rademacher complexity? As stated, what exactly is the intuition behind Rademacher Complexity which is defined:

Rademacher complexity captures the richness of a family of functions by measuring the degree to which a hypothesis set can fit random noise.

The standard "intuition" is that the Rademacher complexity quantifies the ability of the function class $F$ to fit symmetric random noise: a low value (close to 0) means that this ability is limited (and hence the "capacity" of this class is bounded), while a high value (close to 1 for $\{-1,1\}$-valued classes) means that essentially any sequence of random signed bits has a perfect fit (and hence the capacity is unbounded).
To delve a bit deeper, it's always helpful to consider the extreme cases. Let $F$ be a collection of $\{-1,1\}$-valued functions on some large set $\Omega$, $|\Omega|=N\gg1$. What happens when $F$ consists of a single function $f$? What happens when $F=2^\Omega$ consists of all possible functions? You can also consider the cases where $|F|=2,3$ and look up "Massart's finite class lemma", which gives a bound for $|F|<\infty$ and is actually at the heart of more sophisticated (covering-number based) bounds.


Minimum Triangle Covers Given a graph $G$, what is the minimum number of edges of $G$ that we need to delete to make the graph triangle free? To my untrained eye, this appears to be a difficult problem.

Is this problem known to be NP-complete? What about the analogue for oriented graphs (i.e., digraphs with no parallel edges) and directed 3-cycles? References would be greatly appreciated!

EDIT: David has very helpfully answered my question, in the undirected case, below. Any information on the directed/oriented version would be much appreciated.

The undirected version is NP-hard. More specifically, the following problem, known as Partial Feedback Edge Set is NP-complete: given an undirected graph $G$, and positive integers $K$ and $L$, is there a set of at most $K$ edges that contains at least one edge from every cycle of length at most $L$ in $G$.  This is still NP-complete for any fixed $L\geq 3$, and if $G$ is restricted to be bipartite (in which case, $L$ may also be fixed to any value of at least $4$).

For the directed case, Karp's proof that Feedback Arc Set is NP-complete  actually shows that it's NP-complete to determine if you can remove all directed $4$-cycles from an oriented graph by deleting at most $k$ edges. (His reduction from Vertex Cover produces an oriented, triangle-free graph in which deleting all $4$-cycles deletes all cycles.) But that's not what you're asking.

Sources: The undirected version is problem GT9 of Garey and Johnson, Computers and Intractability (Freeman, New York, 1979). The original paper was Yannakakis, Node- and edge-deletion NP-complete problems (Proceedings of STOC 1978) but it doesn't seem to contain a proof. Karp's Feedback Arc Set proof is on page  of the "21 problems" paper: Reducibility among combinatorial problems (Proceedings of symposium on Complexity of Computer Computations, 1972).


The exponential function over algebraic numbers Given an algebraic number $\alpha$,
I am interested in finding an approximation of $\Re(e^\alpha)$
up to a given precision,
where $\Re()$ refers to the real part of the complex number.

Formally, I want to compute a rational number $r$ such that
$$|\Re(e^\alpha)-r|\leq 2^{-n}$$

$\alpha$ is given by a (standard) minimal polynomial.

How fast can we solve this problem?

When $\alpha$ is given as a floating point,
the following reference

R. Brent. Fast multiple-precision evaluation of elementary functions. JACM, 1976.

seems to give an answer.

However,
I am not sure it can be used for the algebraic number $\alpha$.

As written, the problem requires time $2^{\Omega(m)}$, where $m$ is the length of input (you unfortunately used $n$ for something else). Indeed, if e.g. $\alpha$ is a positive integer (given by its minimal polynomial $x-\alpha$) and $n=0$, the size of the output is exponential in the size of the input. This bound is of course optimal, as there are a number of ways how to compute the result in time $2^{O(m)}$.

Let me try to reformulate the question so that it makes a bit more sense. The main issue is how to choose the representation of the input and output, as well as the notion of approximation, so that exponentiation stands a fighting chance of being computable in polynomial time.

One way was mentioned by Kaveh in the comments: restrict the domain to a fixed finite interval. While this works, it is unnecessarily restrictive; in particular, there is no good way how to transform an algebraic number into one that is bounded so that their exponentials have anything to do with each other.

A more flexible approach is to represent the input as a fixed point number, and the output as a floating point number. To be specific, a fixed point representation is a string
$$\pm a_ra_{r-1}\dots a_0.a_{-1}\dots a_{-s}$$
denoting $\pm\sum_ja_j2^j$, where $a_j\in\{0,1\}$, and a floating point representation is
$$\pm2^e\times a_0.a_{-1}\dots a_{-s}$$
with a similar interpretation, where $e$ is a binary integer, and $a_0=1$. (As an exception, we also allow $0$ to represent itself.) An approximation of a real $x$ to $m$ bits of absolute accuracy is a real $x'$ such that $|x-x'|<2^{-m}$, and an approximation to $m$ bits of relative accuracy is $x'$ such that $|1-x'/x|<2^{-m}$. We will use absolute accuracy for fixed point approximations, and relative accuracy for floating point approximations. It follows that in both cases, we may as well assume $s\le m$ (up to loss of one bit of accuracy).

Fixed point and floating point representations of dyadic Gaussian rationals, and approximations of complex numbers, are defined similarly, using a pair of reals. Everywhere below, $n$ denotes the total size of the input.

Now, let (real or complex) exponentiation be the following problem: the input is a fixed point representation of a number $x$ and a unary natural number $m$, and the output is a floating point approximation of $e^x$ to $m$ bits of relative accuracy. Dually, logarithm takes as input a floating point number $x$ and unary $m$, and the output is a fixed point approximation of $\log x$ (say, the principal branch in the complex case) to $m$ bits of absolute accuracy.

As long as we stick to run-time bounds satisfying some mild regularity conditions, and ignore constant multiplicative factors, we have:

The complexity of exponentiation, logarithm, or any similar analytic function, is at least the complexity of integer multiplication: e.g., we can read off $a^2$ from $\exp(a2^{-t})=a2^{-t}+a^22^{-2t-1}+O(a^32^{-3t})$ for sufficiently large $t$, linear in the length of $a$.
Exponentiation and logarithm have the same complexity. The reason is that we can compute the inverse of a nice function by Newton iteration (or more sophisticated methods such as in Brent) using evaluation of the function itself. The iteration typically involse multiplications or divisions, but we can afford these by the previous point.

As for algebraic numbers $\alpha$, they can be represented by their minimal polynomial $f$ (written as a sequence of integer coefficients in binary) together with some means to distinguish between the roots of the same polynomial. A natural way to do that is to require an isolation interval or disk: a pair of fixed point numbers $c,\rho$ such that $|c-\alpha|<\rho$. We need to at least require that $\alpha$ is a unique root of $f$ with this property, but something stronger may be more suitable. More on that later.

Let algebraic number approximation be the following problem: given an algebraic number $\alpha$ in the representation above, and $m$ in unary, compute a (complex) fixed point approximation of $\alpha$ to $m$ bits of absolute accuracy.

$\DeclareMathOperator\re{Re}$The original question asked for $\re e^\alpha$, but let me ignore that for now, and define algebraic number exponentiation as the following problem: given $\alpha$ and $m$ as above, compute a (complex) floating point approximation of $e^\alpha$ to $m$ bits of relative accuracy.

  Fact: Up to linear factors, the complexity of algebraic number exponentiation is the same as the complexity of algebraic number approximation plus the complexity of complex exponentiation.

Proof sketch: On the one hand, we can first compute the fixed point approximation of $\alpha$ and then exponentiate it. Note that $m+O(1)$ bits of absolute accuracy for $\alpha$ determine $e^\alpha$ to $m$ bits of relative accuracy, and vice versa.

On the other hand, if we can do algebraic number exponentiation, we can also do plain exponentiation, as we can readily convert a fixed point number (considered exact) to its representation as an algebraic number. By the comments above, this means we can also compute logarithms in the same time bound. Thus, we can approximate an algebraic number by first approximating $e^\alpha$, and then taking a logarithm. QED

This splits the question to two quite unrelated problems. The best known upper bound on exponentiation is

  Theorem (Brent): If we can multiply $n$-bit integers in time $M(n)$, we can compute complex exponentiation (and logarithm) in time $O(M(n)\log n)$.

The best known lower bound is the $\Omega(M(n))$ mentioned above. The best known upper bound on $M(n)$ is $n\log n\,2^{O(\log^*n)}$ by Fürer’s algorithm.

Figuring out the state of art for algebraic number approximation (that is, root finding) is rather harder, as it is still an area of active research, and the formulations of bounds in the literature are often not as clear as one would want them. Let $\tilde O(f(n))$ denote $O(f(n)\mathrm{polylog}(f(n)))$.

For real root approximation, Pan and Tsigaridas give:

  Theorem: Real algebraic number approximation can be done in time $\tilde O(d^2\tau+dm)$, where $d=\deg(f)$, and $\tau$ is maximum of bit-lengths of the coefficients of $f$.

In the same paper, they mention $\tilde O(d^3+d^2m)$ as the best known bound for complex root approximation. In a slightly more recent paper (http://arxiv.org/abs/1404.4775), they seem to claim the same bounds for the complex case as for the real case, under the assumption that the given isolation disk has isolation ratio (the distance of the disk’s center to the nearest other root of $f$ divided by the radius of the disk) at least $1+1/\log d$ or so, but it’s written in a rather messy way and I may misinterpret it.

Now, the final complication. I defined the problem as approximation of $e^\alpha$, whereas the question asks for $\re e^\alpha$. This actually makes the problem harder: if $\re e^\alpha\ll\operatorname{Im}e^\alpha$, then an approximation $x+iy$ of $e^\alpha$ to $m$ bits of relative accuracy has error $y2^{-m}$, which may well be larger than $x$ itself, and in any case is not guaranteed to be bounded by $x2^{-m}$.

For exponentiation of exact rationals, we can circumvent the problem:

  Proposition: Given $\alpha=x+iy$ and unary $m$, where $x,y$ are binary rationals (or exact fixed point numbers), we can compute a floating point approximation of $\re e^\alpha$ to $m$ bits of relative accuracy within the same time bound as complex exponentiation as defined above, up to linear factor. (I.e., $O(M(n)\log n)$ using Brent’s algorithm.)

Proof sketch: We have $\re e^\alpha=e^x\cos y$. We can approximate $e^x$, and floating point numbers are easily multiplied, the problem is to approximate $\cos y$ with relative error $2^{-m}$. We can compute the integer $k$ nearest to $2y/\pi$, whence $\cos y$ is $\pm\cos y'$ or $\pm\sin y'$, where $y'=y-k\frac\pi2$ satisfies $|y'|\le\pi/4$. The issue arises when we need to compute $\sin y'$ and $y'$ is very small, since in order to have $\sin y'$ to $m$ bits of relative accuracy, we need $m+\log|{y'}^{-1}|$ bits of absolute accuracy. Assume that $y=u/v$, where $u,v$ are integers given as input. If $y'$ is small, we have a good rational approximation of $\pi$:
$$\left|\pi-\frac{2u}{kv}\right|\le\frac{2|y'|}k.$$
Now, $\pi$ is known to have a finite irrationality measure $\nu$ (the current bound is $7{.}6063$ by Salikhov). This implies
$$|y'|\ge\frac1{2k^{\nu-1}v^\nu},$$
which gives a linear upper bound on $\log|{y'}^{-1}|$ in terms of the length of the input. We can thus compute $y'$ to the desired accuracy; evaluating $\sin y'$ is then not a problem (if $y'$ is sufficiently small, we can just take $\sin y'\approx y'$). QED

I do not know whether the same holds for algebraic $\alpha$. In the argument above, one can get a bound on $\log|y'|$ from Baker’s theorem, however, none of its versions that I’ve seen is good enough to make the required accuracy linear in the size of the input: in particular, the bounds involve a (rather nasty) polynomial in $\deg(f)$. This makes the resulting algorithm polynomial in the size of the input, but with a ridiculous exponent.


Document references describing weaknesses for cutting planes and algebraic proof system? Here, Fortnow says (section 4.3):

  Since then complexity theorists have shown similar weaknesses in a number of other proof systems including cutting planes, algebraic proof systems based on polynomials and (...)

I am trying to find references to documents describing weaknesses for cutting planes and algebraic proof system regarding the P vs NP question. Unfortunately, Fortnow's document does not provide any.

For each of these proof systems we know that there are some formulas where the shortest proof needs to have exponential length. Some of the earliest examples are an exponential lower bound for the pigeonhole principle in polynomial calculus (Razborov '98, IPS '99), and an exponential lower bound for the clique-colouring formula in cutting planes (Pudlák '99). Nowadays there are a few more examples to choose from.


Continuation passing transform of binary functions Recall the continuation passing transform (CPS transform) which takes $A$ to $\beta A \mathrel{{:}{=}} R^{R^A}$ (where $R$ is fixed) and $f : A \to B$ to $\beta f : \beta A \to \beta B$ defined by
$$\beta \, f \, \kappa \, r \mathrel{{:}{=}} \kappa (r \circ f).$$
In fact we have the continuation monad with the unit $\eta_A : A \to \beta A$ defined by
$$\eta_A x \mathrel{{:}{=}} \lambda r . r \, x$$
and the multiplication $\mu_A : \beta (\beta A) \to \beta A$ defined by
$$\mu_A \, K \, r \mathrel{{:}{=}} K (\lambda f . f \, r).$$

Now let us think about how we can transform a binary map $f : A \to B \to C$, i.e, we want $\gamma f : \beta A \to \beta B \to \beta C$. One quickly comes up with
$$\gamma \, f \, \kappa \, \nu \, r \mathrel{{:}{=}}
   \kappa (\lambda x . \beta (f x) \nu r).$$
This makes sense from a programming point of view as well.

Here is my question: is there a deeper reason for $\gamma$, other than the fact that it looks right from a programming point of view? For instance, is there a category-theoretic or other "theoretical" reason for thinking that $\gamma$ makes sense? For instance, can we cook up $\gamma$ from the monad in a systematic way?

I am looking for an insight into CPS transforms of $n$-ary functions.

The closest I've seen to an answer to this question is the first picture in the Gallery of Doctor Melliès,

illustrating the map
$$\neg\neg A \otimes \neg\neg B \longrightarrow \neg\neg(A \otimes B)$$
which exists in any dialogue category (i.e., a monoidal category with closures into a fixed object).  Note that the left-to-right CPS transform of general binary functions reduces to applying this map and then composing with the functorial action of the double-negation monad.

The illustration basically follows the standard conventions of string diagrams (modulo the polarizations of the wires, which are meant to indicate the flow of control).  In particular, the map is constructed in three steps: twice applying the strength ($\kappa\wedge$) of the monad induced from the negation self-adjunction, and then applying the counit of the adjunction ($\epsilon$).  At this level of abstraction, the derivation is generic for any adjunction giving rise to a strong monad, and you could then ask for a more abstract characterization of such adjunctions, which Melliès has also written about.


Reference request: Arithmetic circuit complexity I am completely new to this field. I want to read the prelims and unfortunately, I don't see any book written for a beginner in this area. Can anyone give me some basic starting points/references(text/video) for a gentle introduction? I found these two given below.
Determinant versus permanent by Manindra Agarwal https://pdfs.semanticscholar.org/6a05/a4fe63e409ba040b890bbf5da0f3b1ca7085.pdf
Arithmetic circuits by Amir Shpilka
https://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf
Is there any other material which can be more appropriate for a beginner?

This depends on what you want to do. For more structural questions there is a relatively recent survey by Meena Mahajan:

Meena Mahajan: Algebraic Complexity Classes.

There is also the book by Bürgisser:

Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory.

For Geometric Complexity Theory, you might try the theses of Joshua Grochow or Christian Ikenmeyer. I think both of them have introduction into the field, but I must admit that I have read neither of them.


The complexity of finding a Borsuk-Ulam point The Borsuk-Ulam theorem says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x_0$ such that $g(x_0)=0$.

Simmons and Su (2002) describe a method to approximate the point $x_0$ using Tucker's lemma. However, it is not clear what the run-time complexity of their method is.

Suppose we are given an oracle for the function $g$ and an approximation factor $\epsilon>0$. What is the run-time complexity (as a function of $n$) of:

Finding a point $x$ such $|g(x)|<\epsilon$?
Finding a point $x$ such that the $|x-x_0|<\epsilon$, when $x_0$ is a point satisfying $g(x_0)=0$?

Papadimitriou showed that a version of this problem is PPAD-complete in the paper introducing that class, "On the complexity of the parity argument and other inefficient proofs of existence".

His formulation of the problem is:

  Borsuk-Ulam. Given an integer n and a Turing machine computing for each
  point $P=(x_1,\dots,x_d)$ with $-n\leq x_i\leq n$ and $\max_{|x_i|}=n$ (the surface of the $L_1$ sphere), a function $f(p)$ with $f(p) \leq \frac{1}{Kn}$. Find an $x$ with $|f(x) - f( - x)| \leq \frac{1}{n^2}$.

(Sidenote -- many times when you see a fixed-point type of theorem, PPAD is a good guess for the complexity of finding it...)


Normal forms for counting quantifiers? In the paper by [Erich Grädel and Martin Otto], the authors state that any formula in First Order Logic with two variables with counting quantifiers can be reduced to a formula of the form
$$ \forall x \forall y \alpha(x,y)\land \bigwedge_{i=1}^{m} \forall x \exists! y\beta_i(x,y)$$
Another reduction mentioned by [Ian Pratt-Hartmann] as
$$\forall x \forall y (\alpha(x,y) \lor (x \approx y)) \land \bigwedge_{1\leq h \leq m}\forall x \exists_{=c_h}y f_h(x,y) \land (x\not\approx y) $$
I am interested in these normal forms, because the reductions preserve the use of two variables only.
I would like to know whether are there other such reductions.
In particular, are there such reductions that would allow only
quantifiers of the type $\displaystyle\exists^{c}\forall$,
where $c$ is an arbitrary counting condition?

I believe that the formula with the quantifier prefix you want to achieve are strictly less expressive than the two-variable logic with counting quantifiers. So there is no hope that you can translate any C2 formuale into such a form.
Similar types of Scott-normal forms were obtained in:

Bartosz Bednarczyk, Witold Charatonik: Modulo Counting on Words and Trees. FSTTCS 2017 [for modulo-counting quantifiers but without binary predicates]
Michael Benedikt, Egor V. Kostylev, Tony Tan:
Two Variable Logic with Ultimately Periodic Counting. ICALP 2020 [for ultimately-periodic counting]

Moreover, note that the normal form by Ian is somehow more useful than the normal form by Graedel and Otto, since under the binary encoding of numbers in the thresholds it requires an exponential blow-up (while the Ian's version can be obtained in poly-time).
Edit: Extended description of the above paragraph. Consider a formula $\exists^{=c} \varphi$ with a threshold $c$ encoded in binary, i.e. it means that to encode the value 1000 we need approximately $log(1000)$ bits rather than 1000. Hence, the value of $c$ is exponential in $|\varphi|$ rather than polynomial. In Grädel&Otto approach you need to introduce a fresh binary relation for each witness of $\varphi$, which increase the size of the formula exponentially (by c). The translation into Ian's normal form increases the size of the formula only polynomially.
You might be also interested in Gaifman's normal forms for FO extended with various kinds of counting. Here is the most recent paper, but you might check other papers by Dietrich Kuske and his co-authors:
http://eiche.theoinf.tu-ilmenau.de/kuske/Accepted/HeiKS18.pdf


How hard is it to find a "well-distributed" subset of models of a propositional formula? We consider the propositional language $\mathcal{L}_{\mathit{PS}}$ defined over a finite alphabet $\mathit{PS}$ and the usual logical connectives. An interpretation is an assignment $\mathit{PS} \mapsto \{true, false\}$, and a model of a formula $\phi \in \mathcal{L}_{\mathit{PS}}$ is an interpretation $\omega$ which makes $\phi$ true in the usual way. The set of models of a formula $\phi$ is denoted $Mod(\phi)$. The Hamming distance $d_H(\omega, \omega')$ between two interpretations is the number differences between them, i.e., $d_H(\omega, \omega') = |\{x \in \mathit{PS} \mid \omega(x) \neq \omega'(x)\}|$.

I am interested in the computational complexity of the following decision problem. Given a formula $\phi$, an integer $k$ given in unary and a number $\alpha$, does there exist a set $\mathcal{I} \subseteq Mod(\phi)$ such that $|\mathcal{I}| \leq k$ and such that $\forall \omega' \in Mod(\phi)$, $\exists \omega \in \mathcal{I}$, $d_H(\omega, \omega') \leq \alpha$? Intuitively, this problem asks whether there is a subset (of size at most $k$) of models of a given formula such that every model of the formula is "close" enough (wrt the distance threshold $\alpha$) to some model of the subset.

Actually, I am also wondering about the hardness of the above problem when the set $Mod(\phi)$ is given explicitly in input (at least, this one is in $\mathbf{NP}$, but is it $\mathbf{NP}$-hard?)

Update:

The following is the answer for the case where the set $Mod(\phi)$ is explicitely given in input.
The problem is $\mathsf{NP}$-hard by reduction from the vertex cover problem on cubic graph, which is known to be $\mathsf{NP}$-hard.
Let $G = (V, A)$ be a cubic graph with $V = \{v_1, \dots, v_n\}$ and $A = \{a_1, \dots, a_m\}$ and $k$ be a positive integer.
We associate with every edge $a_j \in A$ a propositional variable $f(a_j) = x_j$ and denote $\{x_1, \dots, x_m\} = \mathit{PS}$.
We associate with every vertex $v_i \in V$ an interpretation $g(v_i) = \omega_i$ defined for every $j \in \{1, \dots, m\}$ as $\omega_i(x_j) = 1$ if the edge $a_j \in A$ is incident to the vertex $v_i$, $0$ otherwise. Denote $\{\omega_1, \dots, \omega_n\} = \mathcal{S}$ ($\mathcal{S}$ stands for the set of models $Mod(\phi)$ of some formula $\phi$, but which is here defined explicitely). One can see that for every $\omega_i, \omega_j \in \mathcal{S}$, $d_H(\omega_i, \omega_j) = 4$ if $v_i$ and $v_j$ are adjacent in $G$, otherwise $d_H(\omega_i, \omega_j) = 6$. Therefore, $G$ admits a vertex cover $V'$ such that $|V'| \leq k$ if and only if the set $\mathcal{I} = \{g(v_i) \mid v_i \in V'\}$ satisfies $\forall \omega_j \in \mathcal{S}$, $\exists \omega_i \in \mathcal{I}$, $d_H(\omega_i, \omega_j) \leq 4$.

For the succinct case (i.e., where considering a formula $\phi$ instead of a list of interpretations), then the problem is still open. From the answers of Marzio De Biasi and D.W., it is $\mathsf{coNP}$-hard. Moreover, it is in $\mathsf{NP}^\mathsf{NP} = \Sigma_2^{\rm P}$. Indeed, one can use the following non-deterministic algorithm with $\mathsf{NP}$ oracle: (i) guess a set $\mathcal{I}$ of interpretations such that $|\mathcal{I}| \leq k$; (ii) check in polynomial time that $\forall \omega \in \mathcal{I}$, $\omega \in Mod(\phi)$, and check using one call to the $\mathsf{NP}$-oracle that $\forall \omega' \in Mod(\phi)$, $\exists \omega \in \mathcal{I}$, $d_H(\omega, \omega') \leq \alpha$.

I still need to characterize the exact complexity of the problem. Intuitively, it seems that the problem is $\Sigma_2^{\rm P}$-hard (thus, it would be $\Sigma_2^{\rm P}$-complete in this case). Does anybody know an extension of the vertex cover problem to some $\Sigma_2^{\rm P}$-hard problem? Otherwise, a reduction from the validity problem of a QBF of the form $\exists X \forall Y \psi$ to our problem seems cumbersome.

Well, I don't know what the exact complexity class is, but the problem is hard: a polynomial-time algorithm for this problem would imply P=NP.  Just take $k=0$; then the answer to your problem is yes if and only if $\phi$ is unsatisfiable.  Therefore, any polynomial-time algorithm for your problem would imply P=NP.

If you don't like relying on the special case $k=0$, here's a related construction.  Let $\psi$ be a boolean formula on $n$ variables $x_1,\dots,x_n$.  Introduce $n+1$ new variables $y_0,\dots,y_n$.  Define the formula

$$\phi := (\psi \land y_0 \land \dots \land y_n) \lor (\neg y_0 \land \dots \neg y_n).$$

Set $k=1$ and $\alpha=n$.  If $\psi$ is satisfiable, the answer to your problem is no.  If $\psi$ is not satisfiable, the answer to your problem is yes.


Maximum weight matching and submodular functions Given a bipartite graph $G = (U \cup V, E)$ with positive weights let $f: 2^U \rightarrow \mathbb{R}$ with $f(S)$ equal to the maximum weight matching in the graph $G[S\cup V]$.

Is it true that $f$ is a submodular function?

Definition. For a given finite set $A$, a set function $f:2^A \rightarrow \mathbb{R}$ is submodular if for any $X, Y \subseteq A$ it holds that:
$$
f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y).
$$

Lemma
Given a bipartite graph $G = (A \cup B, E)$ with positive edge weights, let $f: 2^A \rightarrow \mathbb{R}^+$ be the function that maps $S\subseteq A$ to the value of the maximum weight matching in $G[S \cup B]$.  Then $f$ is submodular.

Proof.
Fix two sets $X, Y \subseteq A$ and let $M_\cap$ and $M_\cup$ be two matchings for the graphs $G[(X\cap Y) \cup B]$ and $G[(X \cup Y) \cup B]$ respectively.  To prove the lemma is enough to show that it is possible to partition the edges in $M_\cap$ and $M_\cup$ into two disjoint matchings $M_X$ and $M_Y$ for the graphs $G[X\cup B]$ and $G[Y\cup B]$ respectively.

The edges of $M_\cap$ and $M_\cup$ form a collection of alternating paths and cycles.  Let $\mathcal{C}$ denote this collection and observe that no cycle of $\mathcal{C}$ contains vertices from $X\setminus Y$ or $Y\setminus X$.   This holds because $M_\cap$ does not match those vertices.

Let $\mathcal{P}_X$ be the set of paths in $\mathcal{C}$ with at least one vertex in $X \setminus Y$ and let $\mathcal{P}_Y$ be the set of paths in $\mathcal{C}$ with at least one vertex in $Y \setminus X$.  Two such paths are depicted in the figure below.

Claim 1.
$\mathcal{P}_X \cap \mathcal{P}_Y = \emptyset$.

Assume by contradiction that there exists a path $P \in \mathcal{P}_X \cap \mathcal{P}_Y$.  Let $x$ be a vertex in $X\setminus Y$ on path $P$ and similarly let $y$ be a vertex in $Y \setminus X$ on path $P$.  Observe that since neither $x$ nor $y$ belong to $X \cap Y$ they do not belong to the matching $M_\cap$ by definition, and therefore they are the endpoints of the path $P$.  Moreover, since both $x$ and $y$ are in $A$, the path $P$ has even length and since it is an alternating path, either the first or last edge belongs to $M_\cap$. Therefore $M_\cap$ matches either $x$ or $y$, which contradicts the definition and proves the claim.

Let
$$M_X = (\mathcal{P}_X \cap M_\cup) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cap)$$
and
$$M_Y = (\mathcal{P}_X \cap M_\cap) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cup).$$
It is clear that $M_X \cup M_Y = M_\cap\cup M_\cup$  and $M_X \cap M_Y = M_\cap \cap M_\cup$.  To prove the theorem it remains to show that $M_X$ and $M_Y$ are valid matchings for $G[X\cup B]$ and $G[Y\cup B]$ respectively.
To see that $M_X$ is a valid matchings for $G[X\cup B]$ observe first that that no vertex of $Y \setminus X$ is matched by $M_X$ since $\mathcal{P}_X$ does not intersect $Y \setminus X$ by Claim 1, and $M_\cap$ does not intersect $Y \setminus X$ by definition.  Therefore, $M_X$ only uses vertices of $X \cup B$.  Second observe that every vertex $x\in X$ is matched by at most one edge of $M_X$ since otherwise $x$ belongs to either two edges of $M_\cup$ or two edges of $M_\cap$, contradicting the definition.  This proves that $M_X$ is a valid matching for $G[X\cup B]$;  showing that $M_Y$ is a valid matchings for $G[Y\cup B]$ is similar.


Why do TCS papers have author names in alphabetical order of their surnames? I am currently doing a Ph.D. in Theoretical Computer Science, and any research paper I encountered so far has the author's names in alphabetical order of their surnames.
For example consider the most fundamental book on algorithms: "Introduction to algorithms" by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein.
Also consider the book: "Parameterized Algorithms" by Marek Cygan, Fedor V. Fomin,
Lukasz Kowalik, Daniel Lokshtanov,
Dániel Marx, Marcin Pilipczuk,
Michal Pilipczuk and Saket Saurabh
Basically take any paper in the TCS domain, all follow this pattern. This pattern is not followed in other domains where the authorship is decided based on the individual contribution of the authors. In other words, a person having the most contribution to the paper is given the first authorship. Likewise, a person with less contribution would have his/her name appear later in the list of authors.
I consider this norm, fundamentally flawed. Can somebody provide a good reason as to why such a norm is followed in the TCS domain?

The American Mathematical Society has released a statement (pdf link) about the commonly accepted practice of listing authors in alphabetical order in mathematics. Their reasoning applies, in my opinion, to TCS as well.

This kind of theoretical research is often done in small groups of 2-5 people. In close collaboration it can be difficult to determine who came up with which idea and/or whose ideas are more important for the main results. Using the alphabetical order lets us circumvent arguments about it and default to "everyone contributed equally", which is often (but not always) more or less the case anyway. It's also easy to explain to non-mathematicians by e.g. showing the above statement. When you apply to math/TCS positions, the hiring committee will be aware of this convention and won't hold your last name against you. My impression is that researchers in fields close to math/TCS tend to know about it as well.

In biology and other fields where research is based on experiments, papers are written by large groups whose members have distinct roles. A professor has an idea and obtains funding, one researcher designs the experiments, some lab assistant runs them, someone else analyzes the results, others write the paper. In this context it makes more sense to differentiate the authors by their contribution.


Book for self study of algorithms in group theory I am a math major interested on TCS.

I want to self-study the algorithms, and complexity of them for solving the group theoretical problems like find order of elements, coset enumeration, find generator, test if a given subset generates the group.

What book should I read?

It really makes a difference what the input to the algorithm is: how do you specify a group?

If you want groups given by generators and relators, I would suggest Combinatorial Group Theory, by Magnus, Karrass, and Solitar (but algorithms there are sparse because too many of the important problems are undecidable).

If you want automatic groups (groups whose elements are strings of symbols and whose group operations are performed by finite automata, with applications in low-dimensional topology), I would suggest Word Processing in Groups by Epstein (not me!), Cannon, Holt, Levy, Paterson, and Thurston.

If you want permutation groups (the kind of group-theoretic algorithm that is most relevant e.g. for graph isomorphism) then Seress has a book Permutation Group Algorithms but I don't have a copy so I can't tell you whether it's any good.

There should be a fourth paragraph here about matrix group algorithms but I don't know of a book on that topic. There's a little coverage in Seress's book.


Is the computation of a satisfying variable assignment for a Boolean formula $FP^{NP}$-hard? By the well-known self-reducibility of SAT we can obtain a satisfying variable assignment for a Boolean formula by a polynomial number of calls to an $NP$ oracle (delivering only yes/no answers). Thus, the computation of a satisfying variable assignment for a Boolean formula is in $FP^{NP}$.

On the other hand, it is not possible with only a logarithmic number of $NP$ queries to obtain a satisfying variable assignment of Boolean formula as shown by Gottlob and Fermüller.

Has it already been shown that the computation of a satisfying variable assignment is also $FP^{NP}$-hard?

$\let\mr\mathrm$Let me denote the problem as $S$. Gottlob and Fermüller state that if $S$ is solvable in $\mr{FP}^{\mr{SAT}[\log n]}$, then $\mr{P}=\mr{NP}$. However, the argument actually shows more generally that if $S$ is in $\mr{FP}^{\mr{SAT}[q(n)]}$, then SAT is solvable in time $\mr{poly}(n2^{q(n)})$. In particular, assuming the exponential time hypothesis, $S$ cannot be solved with a sublinear number of $\mr{NP}$ queries.

On the other hand, $S$ shouldn’t be hard for $\mr{FP}^\mr{SAT}$—or even $\mr{FP}^{\mr{SAT}[2]}$—under many-one search-problem reductions. For definiteness, let me assume (following Gottlob and Fermüller) that $S$ is formulated as a total search problem, required to answer “unsatisfiable” for unsatisfiable formulas. Let $L$ be a language whose $\{0,1\}$-valued characteristic function $f_L$ is reducible to $S$, that is, there are poly-time functions $g,h$ such that
$$S(g(x),y)\implies f_L(x)=h(x,y).$$
Then
\begin{align}
x\in L\iff{}&\bigl(g(x)\in\mr{UNSAT}\land h(x,\text{‘unsat’})=1\bigr)\\
&\lor\exists y\,\bigl(y\text{ satisfies }g(x)\land h(x,y)=1\bigr),
\end{align}
and we have a similar expression for $\overline L$ with $0$ in place of $1$, hence
$$L\in\mr{DP}\cap\mr{coDP}.$$
If this were true for all $\mr{DP}$ languages $L$, then the Boolean hierarchy would collapse to $\mr{DP}$, hence the polynomial hierarchy would collapse to something similar one level up. So, assuming no such collapse takes place, there are $\mr{FP}^{\mr{SAT}[2]}$ functions (in fact, characteristic functions of $\mr{DP}$ predicates) not reducible to $S$.

Note that if we instead formulate $S$ so that it is undefined on unsatisfiable inputs, it only becomes easier; it is a (non-total) $\mr{FNP}$ problem. Then it is not hard to see that $f_L$ is reducible to $S$ only if $L\in\mr{NP}\cap\mr{coNP}$. In particular, $S$ is not hard for $\mr{FP}^{\mr{SAT}[1]}$ (or characteristic functions of $\mr{NP}$ languages) unless $\mr{NP}=\mr{coNP}$.


Non-interesting numbers via resource-bounded properties? There is an old joke about the smallest non-interesting number being interesting in itself (I have heard it attributed to Richard Hamming).  This is then used to justify the argument that every number must be interesting.  I have always found this induction unsatisfactory.

Here is an attempt at a more precise argument.  Consider a set of rules, represented as sentences of some logic.  The interesting numbers are then the smallest numbers that are models of some set of sentences.  In first-order logic each natural number can be distinguished from every other one, so the sentences true for any natural number will differ from those true for any other, and every number will be interesting.

Now suppose our rules are given in terms of a bounded model of computation, so that only finite sets of properties can be associated with each number, and so that every property can be checked with a bounded amount of some resource (for instance, time or space).

  Is every number still interesting with resource-bounded properties?

Edit: to clarify, resource bounds is my focus here.  With unbounded resources this devolves into a question about definability and large ordinals, as discussed by Aaron and Kaveh.  The idea is that each interesting number should be definable by a sentence that can be checked given a bounded amount of resources.  (It might also make sense to allow some finite set of sentences as separate building blocks instead of making them into single sentences via conjunction.)

This might be cheating, because I am reinterpreting your notion of "number" as "countable ordinal."  However, there is an extensive theory about exactly what you are asking about in your question -- which ordinals can be defined, with which definition-strengths.  I looked at Wikipedia, and the large countable ordinal page has a lot of information.  In particular, the "smallest number that is interesting because the system can't even prove it's a number" corresponds to the unrecursable ordinals, if we require nothing other than computability as the resource bound.


Algorithms as fractals Recursion utilizes some self similar nature of an object (some representation of the given problem) to produce some quantitative measure (output) on the object through some algorithm (utilizing the self similar nature).

Can one represent algorithms as fractals (such a representation is not possible is not obvious nor how the representation should be if one exists) of some measurable information of the object the algorithm works on?

Has the tools used in the study of fractals provided any illuminating examples for lower or upper bounds for recursive complexity of algorithms?

I am looking for examples and references along the lines of whether algorithms can be treated as fractals and tools about fractals can be used to prove results about algorithms.

just added Would we be compelled to redefine some essential property of Sierpinski triangle if Walsh Transform or Sierpinski triangle transform is shown to be fully linear?
http://en.wikipedia.org/wiki/Walsh_matrix

Blum, Shub, and Smale proved that membership in the Mandelbrot set is undecidable in the Real RAM model of computation (known in some upstart circles as the BSS model).

The high-level argument is one sentence long: Any Real RAM computable set is the countable union of semi-algebraic sets, so its boundary has Hausdorff dimension 1, but the boundary of the Mandelbrot set has Hausdorff dimension 2.  By the same argument, almost every interesting fractal is uncomputable in the real-RAM model.


Analysis of variables of varying numbers I work with amino acid sequences and I want to use a self-made model to tell me something about it, let's call it f(seq). Now I want to know the contribution of every position in the sequence onto the model. E.q. My question is what is the importance/effect of amino acid A occurring at position I in the sequence with respect to the model?

How do I visualize something like that?

I want to use my model also on several sequences of differing lengths. Somehow this throws a monkey wrench into my plans of using a neural net...

My question is simple yet I did not find anything about it. Pointers would be appreciated. Or any comment you might have. This whole idea of mine is pretty unfinished and I don't really know yet what I want. So feel free to criticize, I will update the question accordingly.

"My question is what is the importance/effect of amino acid A occuring at position I in the sequence with respect to the model?"

I suggest Monotony and Surprise by Apostolico for the modeling of importance of words appearing at certain positions, or in certain patterns.  Beyond that, I'm not sure what you're looking for.


Find optimal room from which to visit all other rooms in a rectangular floorplan Suppose we have an orthogonal polygon with holes (all walls are axis-parallel).  All vertices can be on integer coordinates, if that helps.  Partition the polygon into rectangular rooms.  I would like to find the best room to start from, to visit all the rooms (rectangles). There's a limitation on my movement: in any room, I can only leave by two directions, say north and west. (Here best means there would only be one source in the plane dual graph with directed edges showing how to walk from room to room. If more than one source is required, I wish to minimize them.)

I have been looking at art gallery problems, and at VLSI papers on building rectilinear floorplans from network flows, and they are all tantalizingly close but far.  Can anyone provide suggestions so I can focus my search/proof construction?

EDIT to fix problem pointed out by Peter Taylor.  I can choose two directions per room. (probably they need to be adjacent, so NE is ok but NS is not.)  If I enter one room northward, I am automatically choosing South as one of thst new room's directions. (so only two in or out directions per room)  If I choose a  direction, and there are multiple rooms adjacent in that direction, I can enter all of them (and all of them then have the reverse direction assigned as one of their two directions), so the naive greedy approach would be to choose the direction that maximizes the number of rooms I can enter at that stage. I hope this is now complete, and understandable.

(This is joint with Jeff Phillips, who refuses to visit cstheory regularly ;))
I'm working with the problem formulation as stated and evolved in the comments. Namely, the goal is to find a minimum number of "robots" who can traverse a partition of an orthogonal polygon into rectangles, with the constraint that:

A room can be entered and exited only in diametrically opposed directions (so north-south OR east-west)
A robot can only cross room boundaries along one (globally chosen) axis (so no 90 degree turns allowed)
Within a room though, a robot can do whatever it likes, as long it crosses room boundaries as specified.
Robots can backtrack arbitrarily as long as they follow the above rules.

So a solution looks like an assignment of "colors" axes (NS or EW) to each room, and a traversal plan where each robot only traverses rooms having the same "color".
Construct a graph where each rectangle is a vertex and two rectangles are marked as adjacent if they share a boundary. The edge is "colored" NS or EW, depending on the nature of the adjacency.
Claim 1: If we are limited to one axis (NS or EW) then the minimum number of robots is merely the number of components in graph induced by edges of the corresponding color.
Proof: Every edge represents a legal transition in that axis, so placing one robot in each connected component suffices, and you need at least one for each component for coverage.
Now consider the two partitions of the rectangle collection induced by the two colors. Notice that the minimum cardinality partition among these two might be far from optimal if for example your polygon is an L shape with each leg subdivided into n/2 rectangles. The individual graphs each have n/2 components, but the optimal solution is of size 2.
Construct a bipartite graph, in each node is one of the connected components of either of the partitions, and two nodes are connected if their corresponding components intersect. This graph is bipartite because the two sets of components were partitions.
Claim: the size of minimum vertex cover in this graph is the desired optimal soln.
Proof.
Firstly note that in any optimal solution, the set of rectangles covered by any robot must be a subset of one of the components by reachability. Further, it costs nothing for this robot to cover any of the other rectangles in this partition. Hence wlog we can assume that OPT consists of a set of components that together cover all rectangles, i.e a set cover.
Secondly, since the graph is bipartite, we know that any rectangle is represented by exactly one edge between left and right sides. Thus, covering all rectangles actually requires covering all edges in this graph.
QED
VC in bipartite graphs can be solved in polynomial time, so the overall problem can be solved in polynomial time.
Comments ?


What exactly does "semantically observable" side-effect mean? I have question regarding pure functions. According to the Wikipedia page one of the requisites for a pure function is :

  Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.

Now what does this really mean. Or rather how can i make a side effect which is not semantically observable?

A semantics of a program is a model of its behavior which, like any scientific model, ignores aspects that you don't want to study.

An extremely detailed model of the execution of a program would model the physical behavior of the computer that executes it, including the execution time, power consumption, electromagnetic radiation, etc. Such aspects are very rarely taken into account because they are very rarely relevant. Nonetheless they do matter sometimes: a useful model of an airplane autopilot needs to include runtime information, a useful model of a credit card's security needs to include electromagnetic radiation, ...

In typical semantics, side effects such as timing and power consumption are ignored. Even if in a mundane setting where you type an expression at a Haskell interpreter prompt, the printing of the result is a side effect (if you try to print out an infinite object, it matters). If the Haskell interpreter runs out of memory, this is also an observable side effect in a “real-world” model, but not in an idealized model of Haskell that effectively allows unbounded computations.

An observable side effect is one which is modeled in the semantics. In typical models of programming languages, memory consumption is not modeled, so a computation that requires 1TB of storage can be pure, even though if you try to run it on your PC it would observably fail.

Another kind of non-observable side effect is one that is internal to the function. This is, I think, what most semanticists would think of when talking about non-observable side effects. Consider a computation that uses mutable data internally, but does not share this mutable data with any other part of the program. For example, a list sorting function which builds an array with the same elements as the list, sorts the array in place, and returns a list containing the elements as the array in their final order: a semantic model of subexpressions of this function exhibits side effects (modifications of the array), but the function itself has no external side effect, so it is pure.

For a more subtle example, consider a function that writes some data to a temporary file and cleans up after itself. In a semantics where there is always enough room for temporary files and programs do not share temporary files, the function has no side effect; the temporary file acts as extra memory used by the function. In a semantics which takes filesystem full conditions into account, the function has a side effect — it may fail due to external circumstances. In a semantics that allows the machine to crash, the function has a side effect: if there is a crash during the execution of the function, the temporary file may be left behind. In a semantics that allows concurrently executed programs to see and maybe modify the temporary file, the function has a side effect.


What is full-entropy bit-strings? I was going through the description of NIST Randomness Beacon. I would like to know the meaning of the term

  full-entropy bit-strings

used in the third paragraph.

The meaning is a bit string $x$ which is distributed uniformly on $\{0,1\}^{|x|}$.


Uniformity vs. nonuniformity in algebraic complexity theory I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes.  In this sense, nonuniform computational models can be thought of as a secondary device in complexity theory, the main interest being the uniform model.

However, in algebraic complexity, the situation seems to have been the other way around.  Algebraic nonuniform models including algebraic circuits were studied long before the uniform Blum-Shub-Smale machines were introduced.  I am confused about this; since nonuniformity preceded uniformity in the algebraic setting, something about nonuniformity should have been unsatisfactory.  But what was wrong with straight-line programs?

I'd be grateful if you could tell me why uniformity in algebraic complexity theory can be preferable.

EDIT: I realized that uniformity helps if you are discussing computability of algebraic problems.

Blum, Shub and Smale created their model based on known algebraic models of computations, to unify (as much as possible) complexity theory and numerical analysis (cf. [1]). They wanted to give solid theoretical foundations to numerical analysis, and they wanted uniformity since the algorithms used in real life are uniform. Also, their model is a generalization of the Turing Machine, and having uniformity implies that $\mathsf {(N)P}_{\mathbb Z_2}$ in their model equals precisely $\mathsf{(N)P}$ in the classical model.

Uniformity is much less central for lower-bound questions, or as Bürgisser states it [2]:

  Before, uniformity was not studied systematically in algebraic complexity, mainly because it is unknown how to exploit the uniformity condition for lower bound proofs.

Note that non-uniformity in the BSS model can be studied also. This is the viewpoint taken for instance by Poizat [3].

As a final note, BSS model and Valiant's model have different goals, and I am not sure that uniformity is "preferable", neither that non-uniformity is preferable. As a argument for this, both models are used today to study different questions.

References

[1] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. "Complexity and real computation: A manifesto." International Journal of Bifurcation and Chaos 6, no. 01 (1996): 3-26.

[2] Peter Bürgisser. Completeness and reduction in algebraic complexity theory. Vol. 7. Springer, 2000.

[3] Bruno Poizat. Les petits cailloux: une approche modèle-théorique de l'algorithmie. Aléas, 1995.


Sum-of-squares proof system Recently I have seen several articles on arxiv that refer to a proof system called sum-of-squares.

Can someone explain what is a sum-of-squares proof and why such proofs are important/interesting?

How are they related to other algebraic proof systems? Are they some kind of dual to Lassere?

The basic sum-of-squares proof system, introduced under the name of Positivstellensatz refutations by Grigoriev and Vorobjov, is a “static” proof system for showing that a set of polynomial equations and inequations
$$S=\{f_1=0,\dots,f_k=0,h_1\ge0,\dots,h_m\ge0\},$$
where $f_1,\dots,f_k,h_1,\dots,h_m\in\mathbb R[x_1,\dots,x_n]$, has no common solution in $\mathbb R^n$: a refutation of $S$ is given by polynomials $g_i$ and $e_{I,j}$ such that
$$\tag{$*$}-1=\sum_{i=1}^kg_if_i+\sum_{I\subseteq\{1,\dots,m\}}\sum_je_{I,j}^2\prod_{i\in I}h_i.$$
(One could work with any real-closed field in place of $\mathbb R$.) Stengle’s Positivstellensatz guarantees that $S$ has a refutation if and only if it has no solution. The main complexity measure here is the degree of the refutation, which is the maximum of total degrees of the polynomials that appear under the sum signs in $(*)$, that is, $g_if_i$ and $e_{I,j}^2\prod_{i\in I}h_i$.

As usual with algebraic proof systems, one can also consider it as a refutation system for unsatisfiable Boolean formulas $\phi$ by including in $S$ the axioms $x_i^2-x_i$ for each variable $x_i$, and a translation of $\phi$ by polynomial inequalities.

More on the history and development of SOS systems can be found in http://arxiv.org/abs/1211.1958 .


Interactive Proof for HORN-SAT? Is there a way that a prover can convince a verifier that some HORN-SAT expression is satisfiable?

Of course this might seem silly, since there are linear time algorithms for HORN-SAT. On the other hand, HORN-SAT is P-complete, which means it does not have log-space algorithms unless P=L. Accordingly, restrict the computational abilities of the verifier to L. Now the verifier is very feeble, so the problem is no longer silly.

Another twist on this is whether it can be a zero-knowledge proof.

This http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf
survey by Anne Condon contains many facts about space bounded interactive proof systems.

There are several models, and the main differences are whether you allow private coins for the verifier (IP) or public coins only (AM), and whether you also restrict the verification
time to polynomial (not implied by the space bound alone).

Without the time restriction the answer is yes: IP(log-space) contains EXP
and AM(log-space)=P.

Note that IP(log-space) is most likely larger than standard IP. On the other hand
IP(log-space, poly-time)=IP=PSPACE.

AM(log-space, poly-time) = P due to 'Delegating Computation: Interactive Proofs for Muggles' by Goldwasser et al., STOC 2008.

Furthermore the paper 'Zero knowledge with log-space verifiers' by Kilian (FOCS 88)
shows how to get a log-space poly-time zero knowledge proof system for everything in IP (with private coins obviously).


Verifying that a reduction is correct Alice has a function $f: \{0,1\}^* \to \{0,1\}^*$ which can be computed in polynomial time. She claims that $x \in \mathrm{SAT} \iff f(x) \in \mathrm{CLIQUE}$. Alice sends the circuit computing $f$ on the set $\{0,1\}^n$ to Bob. Bob is an algorithm from $\mathbf{P}^{\mathrm{SAT}}$ (or even $\mathbf{P}$). He wants to verify that $f$ is indeed a correct reduction of $\mathrm{SAT}$ to $\mathrm{CLIQUE}$ for all the inputs of length $n$.
If such Bob exists does it imply the collapse of the polynomial hierarchy?

In other words is $\{C \text{ - circuit }\mid \forall x \in \{0,1\}^n\colon x \in \mathrm{SAT} \iff C(x) \in\mathrm{CLIQUE}\}$
(here $n$ is the number of input gates of $C$).
$\Pi_2^P$-complete? $\mathbf{NP}$-hard? Clique and SAT are arbitrary $\mathbf{NP}$-complete languages I've picked.

This is $\Pi_2^p$-complete. Let D be the usual reduction from SAT to CLIQUE. Let w be a string in CLIQUE. Consider a $\Pi_2^p$ language $L$ expressed as the set of $x$ such that for all $y$ there is a $z$ with $(x,y,z)$ in $A$ for some $A$ in P (with polynomial-length bounds on the $y$ and $z$). Let $\phi_{x,y}$ be the formula that will be satisfiable if there exists a $z$ such that $(x,y,z)$ is in $A$.

Define $C_x(\phi)$ as follows: If $\phi=\phi_{x,y}$ for some $y$ then let $C_x(\phi)=w$ otherwise set $C_x(\phi)=D(\phi)$.

Then $x$ is in $L$ if and only if $C_x$ is a reduction from SAT to CLIQUE.


Additive versus multiplicative accuracy I am trying to understand the difference between $\epsilon$-additive and $\epsilon$-multiplicative algorithms. The way I understand this definition is as follows. An $\epsilon$-additive algorithm is one that, for a true solution OPT, returns $OPT' \in [OPT - \epsilon, OPT + \epsilon]$. For an $\epsilon$-multiplicative algorithm, we have $OPT'' \in [OPT(1 - \epsilon), OPT(1+\epsilon)]$. While I can see the differences between these (for instance, if true OPT = 10 and $\epsilon = 0.1$, then in one case, the error is $\pm 0.1$, while in the other, it is $\pm 1$), I would like to know the answers to the following questions:

1) Why is it sometimes easier to achieve $\epsilon$-additive accuracy than $\epsilon$-multiplicative (example, as stated in https://arxiv.org/pdf/0801.1987.pdf)?

2) When is one type of accuracy more important or relevant than the other?

3) How can one one translate between the two? For instance, if you tell me an algorithm solves a problem to $\epsilon$-additive accuracy in time $T$, is it possible to say how fast it will be for $\epsilon$-multiplicative accuracy? (and vice versa)?

Why is it sometimes easier to achieve $\epsilon$-additive accuracy than $\epsilon$-multiplicative?

Consider a problem where the objective value OPT is guaranteed to lie in a constant non-negative real interval such as $[0, c]$. For example, the paper you mention is about computing approximation solutions to two-player zero-sum matrix games in which the payoffs (and hence the value, OPT) is in the $[0,1]$ interval, as originally considered by Grigoriadis and Khachiyan.

In this type of setting, any $(1+\epsilon/c)$-approximate solution has value $v$ satisfying $$v \le (1+\epsilon/c)OPT = OPT + \epsilon OPT/c \le OPT + \epsilon.$$
So, to compute an additive-$\epsilon$ approximate solution, it suffices to compute any multiplicative $(1+\epsilon/c)$-approximate solution.  So, computing an additive $O(\epsilon)$-approximation is no harder than computing a multiplicative $(1+\epsilon)$-approximation.

The converse is not generally true, because when OPT is near zero, an additive error of $\epsilon$ is relatively large (e.g., consider the case when OPT$ < \epsilon$.  (On the other hand, if, say OPT is guaranteed to be in some range $[c_1, c_2]$ with constant $c_1 > 0$, then the two notions of approximation are equivalent up to constant factors.)
When is one type of accuracy more important or relevant than the other?

Historically most (?) optimization problems studied in theoretical computer science are (informally speaking) "scale-free".  For example, consider the Minimum Spanning Tree problem (or any other problem where the objective is a sum of given weights).  Doubling the edge weights gives an equivalent instance.  In this setting, if you could give an $\epsilon$-additive approximation algorithm, the algorithm would also have to be a $\epsilon/2$-additive approximation algorithm (double the weights of the given instance, then compute an additive $\epsilon$-approximate solution for the modified instance --- it has to give an $\epsilon/2$-approximate solution to the original instance).  So generally speaking additive-$\epsilon$ approximation is awkward in this setting.  You might see it occasionally, but with an additive error term that depends on, say, the maximum edge weight.  In contrast, multiplicative approximation is natural in this setting.

Note that unweighted problems can also be "scale-free".  For example, consider unweighted Set Cover.  Given any instance, you could construct a new instance with two independent copies of the original instance.  This has essentially the same effect as doubling the weights.

Of course there are also problems that aren't naturally scale free, such as Minimum-Degree Spanning Tree.  In this setting, additive approximation can make more sense (such as the additive-1 approximation algorithm for Min-Degree Spanning Tree).

In the other extreme, consider finding a spanning tree that minimizes the product of the edge weights.  Here neither notion of approximation fits well.
How can one one translate between the two? For instance, if you tell me an algorithm solves a problem to $\epsilon$-additive accuracy in time $T$, is it possible to say how fast it will be for $\epsilon$-multiplicative accuracy? (and vice versa)?

See the answer to Question 1.  If $OPT$ is in $[0,1]$, any multiplicative $(1+\epsilon)$-approximate solution will be an additive $\epsilon\,OPT \le \epsilon$-approximation.  Conversely, any additive-$(\epsilon\,OPT)$ solution will be a multiplicative $(1+\epsilon)$-approximate solution, so the running time to compute the multiplicative solution (using an additive-error algorithm with additive error $\epsilon'=\epsilon OPT$) will grow with $1/(\epsilon\,OPT)$ (note $OPT\le 1$).

FWIW, I've noticed that, historically, Chernoff bounds tended to be stated in terms of additive error (where "error" = deviation from the mean).  Perhaps that's because Chernoff bounds generally concern sums of $[0,1]$ random variables.  But when used in TCS they tend to be stated multiplicatively, probably for the reasons outlined above.


Do there exist x such that K(xx)<K(x), where K is Kolmogorov complextity. Let $K(x)$ denote the Kolmogorov complexity of a string $x$. Do there exist a string such that $K(xx)<K(x)$. (Here $xx$ is the concatenation of $x$ with itself). A similar but different question was asked here, but the counterexample given in the answer to that question doesn't work for this one.

I am no expert on Kolmogorov complexity, but I think that such x can be constructed for every complexity function K as follows.  Since 1, 11, 1111, 11111111, …, 12n, … is an encoding of a natural number n, K(12n) cannot be o(log n).  However, when n=2m, obviously K(12n)=K(122m)=O(log m)=O(log log n).  Therefore the sequence K(1), K(11), K(1111), K(11111111), …, K(12n), … cannot be weakly monotonically increasing, which means that there exists a string x in the form 12n such that K(xx) < K(x).


Is tensor rank is in VNP? Is it known if tensor rank of three dimensional tensors lies in VNP (non deterministic valiant class)? If yes, what is known about high dimensional tensor rank?

In fact I am interested in much more simple problem. I would like  to know if one can construct class non-zero polynomials $f_n$ which lies in VNP, in $n^3$ variables such that $f_i(T)=0$ if tensor rank of $T$ less than $n^{1.9}$.
For simplicity let us assume that we are working over $\mathbb{C}$.

I would like to mention that it is O.K. if $f_i(T)=0$ for $T$ of high rank only what I need is that $f_i(T)=0$ for all small rank tensors.

The collection of tensors of a given rank, or even of tensors with rank at most $k$ is not a (Zariski-)closed set, so it cannot be described as the vanishing locus of any set of polynomials, regardless of their complexity. (However, over finite fields tensor-rank is $NP$-complete and over $\mathbb{Q}$ it is $NP$-hard but not known to be in $NP$. But these are the usual Boolean classes, not the Valiant analogues.)

The closure of the the set of tensors of rank at most $k$ is the set of tensors of border-rank at most $k$. Call a set of polynomials whose vanishing locus is the set of tensors of border-rank at most $k$ a system of (set-theoretic) defining equations for border rank at most $k$. Such defining equations are known for small $k$, but for most $k$ finding such defining equations is a long-standing open problem, related the border-rank and multiplicative complexity of matrix multiplication.

See Landsberg's Bulletin article Geometry and the complexity of matrix multiplication for an introduction and some references, and see Landsberg's recent book Tensors: Geometry and Applications (freely available introduction) for all that is known about defining equations for border-rank.


Complexity class for quantum computer with commutative gates BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. In quantum computer allowed operations can be represented by unitary matrices. In general, unitary matrices do not commute with each other.

My question is what would be BQP analog for a quantum computer where only unitary matrices that commute with each other are allowed?

There isn't a one word answer to your question, but you can have a look at

Xiaotong Ni's master thesis,

where commuting circuits with several restrictions are considered and compared to classical classes.
There you can also find the definition of the class IQP, which is a subclass of polynomial size commuting Pauli circuits.


Function with space-depending computation time Does a function exist which is easily computable for one space capacity and is hard to compute for another? I am looking for a function which can be computed in polytime when available space is at least $n^2$ (where $n$ is the length of the input) and is NP-hard when there is only linear space.

If there is such a function, please show one.

By the Space Hierarchy Theorem, for every space-constructible space bound $s>\log(n)$, there is a problem $L \in \mathsf{SPACE}(s)\setminus \mathsf{SPACE}(o(s))$.

In other words, $L$ can be solved in space $s$, and thus in time $c^{s(n)}$, but not in space $o(s)$, regardless of how much extra time you allow.


MaxCut instance with smallest max cut Let us look at all 4-regular undirected graphs with $n$ nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of edges in its optimal solution. How would you construct that?

Take a clique of size 5 and consider a graph on $n = 5k$ nodes consisting of $k$ copies of this clique. The size of a maximal cut in this graph is $6k = 6n/5$. Indeed, from each copy we can maximally have 6 edges in a cut.
By the following lemma the size of a maximal cut can not be much smaller.

Lemma. In any undirected 4-regular with $n$ nodes there exists a cut with at least $\lceil 6n/5 \rceil$ edges.

More precisely, for $n$ divisible by 5 the answer to your question is exactly $6n/5$. For other $n$ it can be a bit bigger, but only by a $O(1)$ term. Indeed, we can again consider a graph where all but $O(1)$ nodes are paritioned into  copies of a 4-regular clique.
Proof. Let $G = (V, E)$ be a 4-regular graph with $n$ nodes and let $(S, T)$ be a maximal cut. For a node $a\in V$ let cut-degree of $a$ be the number of edges containing $a$ and belonging to the cut $(S, T)$. We rely on the following two easily verifiable observations:

Observation 1: any node has cut-degree at least 2. Indeed, assume that $a\in V$ has cut degree at most $1$. WLOG, $a\in S$. Then removing $a$ from $S$ and putting it to $T$ would result in a larger cut, contradiction.
Observation 2: no edge of the cut connects two nodes with cut-degree 2. Indeed, assume that nodes $a\in S$ and $b\in T$ are adjacent and both have cut-degree 2. Then swapping $a$ and $b$ (putting $a$ to $T$ and $b$ to $S$) would result in a larger cut, contradiction.

Assume that $|S| = s, |T| = t$. Let $x$ be the number of nodes from $S$ with cut-degree 2. Similarly, let $y$ be the number of nodes from $T$ with cut-degree 2.
Let $C$ be the size of the cut $(S, T)$. Note that $C$ equals the sum of cut-degrees over the nodes from $S$. Exactly $x$ nodes from $S$ have cut-degree $2$. By observation 1 all the other nodes from $S$ have cut-degree at least $3$. Hence
$$C \ge 2x + 3(s - x) = 3s - x.$$
Applying a similar argument to the set $T$ we obtain:
$$C \ge 2y + 3(t - y) = 3t - y.$$
Now, let us sum up the cut-degree over all nodes of $G$ with cut-degree 2. By observation 2 we never count an edge of the cut twice. Hence
$$C \ge 2x + 2y.$$
By summing up these 3 inequalities with appropriate weights we obtain:
$$5C \ge 2(3s - x) + 2(3t - y) + 2x + 2y = 6(s + t) = 6n.$$
This gives us $C \ge \lceil 6n/5\rceil$. Proof of the Lemma is finished.


How can I find the second cheapest spanning tree? The classic Mininum Spanning Tree (MST) algorithms can be modified to find the Maximum Spanning Tree instead.

Can an algorithm such as Kruskal's be modified to return a spanning tree that is strictly more costly than an MST, but is the second cheapest? For example, if you switch one of the edges in this spanning tree, you end up with an MST and vice versa.

My question, though, is simply: How can I find the second cheapest spanning tree, given a graph $G$ with an MST?

The second-smallest spanning tree differs from the minimum spanning tree by a single edge swap. That is, to get the second-smallest tree, you need to add one edge that's not already in the minimum spanning tree, and then remove the heaviest edge on the cycle that the added edge forms.

If you already have the minimum spanning tree, this can all be done in linear time. See e.g. V. King, "A simpler minimum spanning tree verification algorithm", Algorithmica 1997, doi:10.1007/BF02526037.


finding constantness of a term Let $S$ be a multisorted algebraic signature with function symbols $f_0, f_1, \ldots$. For every $i$, I partially know “constantness” of $f_i$. (I have no precise definition of constantness yet.) Examples:

Let $\cdot$ denote multiplication of numbers. If $x_0=0$, then $x_0\cdot x_1$ is constant.
Conditional operation. If $x_0=0$ and $x_2$ is constant, then  $\operatorname{if}x_0\operatorname{then}x_1\operatorname{else}x_2$ is constant.

I need to find a strongest constantness judgement for any term over $S$ given constantness of its variables. Is there an established way of reasoning about constantness?

A purpose is that every term in $S$ defines a function from program states to a pixel on a screen. Variables of the term are components of a state, i.e. the set of states is a Cartesian product. For every pixel $p$, if its term is found to be non-constant then I need to redraw $p$.

You might want to take a look at the compiler literature for some ideas.  What you're describing is akin to a well-known compiler optimization (virtually any modern compiler worth its salt will do it) called constant folding.  Of course, constant folding goes further in not just identifying constant expressions, but replacing them by their value.

In particular, compilers use a dataflow analysis to identify such constant expressions.  Any good compiler textbook will discuss this.


Any Hypothesis Classes Other than Parity in Noisy PAC but not in SQ? Angluin and Laird ('88) formalized learning with randomly corrupted data in the model "PAC with random classification noise" (or noisy PAC). This model is similar to PAC learning, except for the labels of the examples given to the learner are corrupted (flipped), independently at random, with probability $\eta < 1/2$.

To help characterize what is learnable in the noisy PAC model, Kearns ('93) introduced the Statistical Query model (SQ) for learning.  In this model, a learner can query a statistical oracle for properties of the target distribution, and he showed that any class that is SQ learnable is learnable in noisy PAC.  Kearns also proved that parities on $n$ variables cannot be learned in time faster than $2^{n/c}$ for some constant $c$.

Then Blum et al. ('00) separated noisy PAC from SQ by showing that parities on the first $(\log(n) \log\log(n))$ are polynomial-time learnable in the noisy PAC model but not in the SQ model.

My question is this:

  Parities (on the first $(\log(n) \log\log(n))$ variables) are learnable in the noisy PAC model but not in the SQ model.  Are there any other specific classes, sufficiently different from parity, that are known to be learnable in noisy PAC but not in SQ?

I think that the answer is "no", although I'm not certain and would also be interested in other examples. One thing that is known is that agnostic learning is significantly harder from an information theoretic perspective in the SQ model. Agnostically learning monotone disjunctions to error epsilon requires only $d/\epsilon^2$ examples in the PAC setting (though the task of learning might then be computationally hard...). In the SQ model, there is no agnostic learning algorithm for monotone disjunctions that has a polynomial dependence on $1/\epsilon$ in terms of the number of queries it makes, even ignoring computational considerations.


Handbook of advanced algorithms I am looking for resources (preferably a handbook) on advanced topics in algorithms (topics beyond what is covered in algorithms textbooks like CLRS and DPV).

The type of material that can be used for teaching a topics in algorithms course like
Erik Demaine and David Karger's Advanced Algorithms course.

Resources that would give an overview of the field (like a handbook) are preferable,
but more focused resources like Vijay Vazirani's "Approximation Algorithms" book are also fine.

The Design of Approximation Algorithms by Williamson & Shmoys (http://www.designofapproxalgs.com/) is a great book for many approximation methods such as greedy algorithms, semidefinite programming, etc. Also, it covers some topics within complexity that are closely related to approximation algorithms (inapproximability, Unique Games-based hardness of MAX-CUT).


Is the running time of Boyer-Moore linear? With pattern length $M$, text length $N$, and alphabet $\Sigma$,
is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$
(even when $M$ grows larger than $|\Sigma|$)?

Are there any sublinear expected-time string matching algorithms (on all alphabet sizes)?

Here is a true sublinear string matching algorithm, on all alphabet sizes, which answers the question Kaveh posted. My question was: Is Boyer-Moore actually linear on small alphabets?

The log base below is $|\Sigma|$, and (ceiling of) $logM$ (often just one) is implied.

Preprocess the Pattern into a lookup table, with $M-logM+1$ keys, each key having size $logM$, and with associated key positions in the Pattern. Converting sequences of $logM$ letters into array indices is the only tricky part. The table size is $|\Sigma|$ raised to ceiling of $logM$, for easy indexing.  Each bucket is a short, possibly empty, list of key positions.  Run time: $O( MlogM )$.

Main: Skip through Text positions $k$ by $(M - logM + 1)$, constructing a $logM$ sized search key at Text positions $k$ thru $k + logM -1$. Look up the search key in the table. If found, naively attempt to match the Pattern at Text[$k$ - key position].  The naive attempt almost certainly fails in $logM$ comparisons. The only tricky part is that a key may occur in multiple Pattern positions.  The expected number of test positions is $O(1)$.  Expected run time: $O( (N/M)logM )$.

Post: Garbage collect the preprocessing space, $O(MlogM)$.

A proof that Main is optimal for $N>M^2$, on all alphabet sizes, is needed.


Testing whether letters can be scheduled to achieve a word in a regular language I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each letter (i.e., a minimal and maximal position), and my goal is to place each letter in its interval such that no two letters are mapped to the same position and so that the resulting $n$-letter word is in $L$. Formally:

Input: $n$ triples $(a_i, l_i, r_i)$ where $a_i \in \Sigma$ and $1 \leq l_i \leq r_i \leq n$ are integers
Output: is there a bijection $f: \{1, \ldots, n\} \to \{1, \ldots, n\}$ such that $l_i \leq f(i) \leq r_i$ for all $i$, and $a_{f^{-1}(1)} \cdots a_{f^{-1}(n)} \in L$.

Obviously this problem is in NP, by guessing a bijection $f$ and checking membership to $L$ in PTIME. My question: Is there a regular language $L$ such that the letter scheduling problem for $L$ is NP-hard?

Some initial observations:

It seems that similar problems have been studied in scheduling: we could see the problem as scheduling unit-cost tasks on a single machine while respecting starting and finishing dates. However, this latter problem is obviously in PTIME with a greedy approach, and I don't see anything in the scheduling literature for the case where tasks are labeled and we would want to achieve a word in a target regular language.
One other way to see the problem is as a special case of a bipartite maximum matching problem (between letters and positions), but again it's hard to express the constraint that we must fall in $L$.
In the specific case where $L$ is a language of the form $u^*$ for some fixed word $u$ (e.g., $(ab)^*$), then the letter scheduling problem for $L$ is in PTIME with an easy greedy algorithm: build the word from left to right, and put at each position one of the available letters which is correct relative to $L$ and has the smallest time $r_i$. (If there are no available letters which are correct, fail.) However, this does not generalize to arbitrary regular languages $L$ because for such languages we may have the choice of which kind of letter to use.
It looks like a dynamic algorithm should work, but in fact it's not so simple: it seems that you would need to memorize which set of letters that you have taken so far. Indeed, when building a word from left to right, when you have reached a position $i$, your state depends on which letters you have consumed so far. You cannot memorize the entire set because then there would be exponentially many states. But it's not so easy to "summarize" it (e.g., by how many copies of each letter were used), because to know which copies you used, it seems that you need to remember when you have consumed them (the later you have consumed them, the more letters were available). Even with a language like $(ab|ba)^*$, there may already be complicated constraints about when you should choose to take $ab$ and when you should choose to take $ba$ depending on which letters you will need later and when the letters become available.
However, as the regular language $L$ is fixed and cannot memorize so much information, I'm having a hard time finding an NP-hard problem from which I could reduce.

The problem is NP-hard for $L = A^*$ where $A$ is the finite language containing the following words:

$x111$, $x000$,
$y100$, $y010$, $y001$,
$00c11$, $01c10$, $10c01$, and $11c00$

The reduction is from the problem Graph Orientation, which is known to be NP-hard (see https://link.springer.com/article/10.1007/s00454-017-9884-9). In this problem, we are given a 3-regular undirected graph in which every vertex is labeled either "$\{1\}$" or "$\{0,3\}$". The goal is to direct the edges of the graph so that the outdegree of every vertex is in the set labeling that vertex.

The reduction needs to take as input a Graph Orientation instance and produce a list of triples as output. In this reduction, the triples we output will always satisfy certain constraints. These constraints are listed below, and we will refer to a list of triples as valid if and only if they satisfy these constraints:

The characters $x$, $y$, and $c$ are only given intervals containing exactly one index. In other words, whenever these characters are placed, they are placed in specific locations.
For every triple $(i, l, r)$ present in the instance with $i \in \{0,1\}$, the triple $(1-i, l, r)$ is also present.
If $(\alpha, l, r)$ and $(\alpha',l',r')$ are both triples present in the instance then either $l < l' \le r' < r$, or $l' < l \le r < r'$, or $\{\alpha,\alpha'\} = \{0,1\}$ with $l = l' < r = r'$.
If $(\alpha, l, r)$ is a triple then the number of triples $(\alpha', l', r')$ with $l \le l' \le r' \le r$ is exactly $r-l+1$.

Note the following lemma, proved at the end of this post.

Lemma: for a valid list of triples, the characters $x$, $y$, and $c$ must be placed exactly as indicated by the triples, and for any pair of triples $(0, l, r)$ and $(1, l, r)$, the two characters for that triple must be placed at indices $l$ and $r$.

Then the idea of the reduction is the following.

We use pairs of triples $(0, l, r)$, and $(1, l, r)$ to represent edges. The edge goes between endpoints at index $l$ and at index $r$. Assuming we produce a valid list of triples, the characters from these two triples must be placed at $l$ and $r$, so we can treat the order in which they are placed as indicating the direction of the edge. Here $1$ is the "head" of the edge and $0$ is the "tail". In other words, if the $1$ is placed at $r$ then the edge points from $l$ to $r$ and if the $1$ is placed at $l$ then the edge points from $r$ to $l$.

To represent vertices, we place an $x$ or $y$ character at an index and use the next three characters as the endpoints of the three edges which touch the vertex. Note that if we place an $x$, all three edges at the vertex must point in the same direction (all into the vertex or all out of the vertex) simply due to the strings that are in finite language $A$. Such vertices have outdegree $0$ or $3$, so we place an $x$ exactly for the vertices labeled $\{0,3\}$. If we place a $y$, exactly one of the three edges at the vertex must point in the same direction due to the strings in $A$. Such vertices have outdegree $1$, so we place a $y$ exactly for the vertices labeled $\{1\}$.

In some sense, we are done. In particular, the correspondence between solving this instance and solving the Graph Orientation instance should be clear. Unfortunately, the list of triples we produce may not be valid, and so the "edges" described may not work as intended. In particular, the list of triples might not be valid because the condition that the intervals from the triples must always contain each other might not hold: the intervals from two edges may overlap without one containing the other.

To combat this, we add some more infrastructure. In particular, we add "crossover vertices". A crossover vertex is a vertex of degree $4$ whose edges are paired such that within each pair one edge must point into the crossover vertex and one out. In other words, a crossover vertex will behave the same as just two "crossing" edges. We represent a crossover vertex by placing the character $c$ at some index $i$. Then note that the language $A$ constrains the characters at $i-1$ and $i+2$ to be opposite (one $0$ and one $1$) and the characters at $i-2$ and $i+1$ to be opposite. Thus, if we use these indices as the endpoints for the four edges at the crossover vertex, the behavior is exactly as described: the four edges are in pairs and among every pair one points in and one points out.

How do we actually place these crossovers? Well suppose we have two intervals $(l, r)$ and $(l', r')$ which overlap. WLOG, $l < l' < r < r'$. We add the crossover character into the middle (between $l'$ and $r$). (Let's say that all along we spaced everything out so far that there's always enough space, and at the end we will remove any unused space.) Let the index of the crossover character be $i$. Then we replace the four triples $(0, l, r)$, $(1, l, r)$, $(0, l', r')$, and $(1, l', r')$ with eight triples with two each (one with character $0$ and one with character $1$) for the following four intervals $(l, i-1)$, $(i+2, r)$, $(l', i-2)$, $(i+1, r')$. Notice that the intervals don't overlap in the bad way anymore! (After this change, if two intervals overlap, one is strictly inside the other.) Furthermore, the edge from $l$ to $r$ is replaced by an edge from $l$ to the crossover vertex followed by the edge from there to $r$; these two edges are paired at the crossover vertex in such a way that one is pointed in and one is pointed out; in other words, the two edges together behave just like the one edge they are replacing.

In some sense, putting in this crossover vertex "uncrossed" two edges (whose intervals were overlapping). It is easy to see that adding the crossover vertex can't cause any additional edges to become crossed. Thus, we can uncross every pair of crossing edges by inserting enough crossover vertices. The end result still corresponds to the Graph Orientation instance, but now the list of triples is valid (the properties are all easy to verify now that we have "uncrossed" any crossing edges), so the lemma applies, the edges must behave as described, and the correspondence is actually an equivalence. In other words, this reduction is correct.

proof of lemma

Lemma: for a valid list of triples, the characters $x$, $y$, and $c$ must be placed exactly as indicated by the triples, and for any pair of triples $(0, l, r)$ and $(1, l, r)$, the two characters for that triple must be placed at indices $l$ and $r$.

proof:

We proceed by induction on the triples by interval length. In particular, our statement is the following: for any $k$ if some triple has interval length $k$ then the character in that triple must be placed as described in the lemma.

Base case: for $k = 0$, the triple must be placing a character $x$, $y$, or $c$ at the single index inside the interval. This is exactly as described in the lemma.

Inductive case: assume the statement holds for any $k$ less than some $k'$. Now consider some triple with interval length $k'$. Then that triple must be of the form $(i, l, r)$ with $r = l+k'-1$ and $i \in \{0,1\}$. The triple $(1-i, l, r)$ must also be present. The number of triples $(\alpha',l',r')$ with $l \le l'\le r' \le r$ is exactly $r-l+1 = k'$. These triples include triples $(0, l, r)$ and $(1, l, r)$ but also $k'-2$ other triples of the form $(\alpha',l',r')$ with $l < l' \le r' < r$. These other triples all have interval length smaller than $k'$, so they all must place their characters as specified in the lemma. The only way for this to occur is if these triples place characters in every index starting at index $l+1$ and ending at index $r+1$. Thus, our two triples $(0, l, r)$ and $(1, l, r)$ must place their characters at indices $l$ and $r$, as described in the lemma, concluding the inductive case.

By induction, the lemma is correct.


Is bounded-width SAT decidable in logspace? Elberfeld, Jakoby, and Tantau 2010 (ECCC TR10-062) proved a space-efficient version of Bodlaender's theorem.
They showed that for graphs with treewidth at most $k$, a tree decomposition of width $k$ can be found using logarithmic space.
The constant factor in the space bound depends on $k$.
(Bodlaender's theorem shows a linear time bound, with an exponential dependence on $k$ in the constant factor.)

SAT becomes easy when the set of clauses has low width.
Specifically, Fischer, Makowsky, and Ravve 2008 showed that satisfiability of CNF formulas with treewidth of the incidence graph bounded by $k$ can be decided with at most $2^{O(k)} n$ arithmetic operations when the tree decomposition is given.
By Bodlaender's theorem, computing the tree decomposition of the incidence graph for fixed $k$ can be done in linear time, and therefore SAT can be decided for bounded treewidth formulas in time that is a low-degree polynomial in the number of variables $n$.

One might then expect that SAT should actually be decidable using logarithmic space, for formulas with bounded treewidth of the incidence graph.
It is not clear how to modify the Fischer et al. approach for deciding SAT into something space-efficient.
The algorithm works by computing an expression for the number of solutions, via inclusion-exclusion, and recursively evaluating the number of solutions of smaller formulas.
Although the bounded treewidth does help, the subformulas seem to be too large to compute in logarithmic space.

This leads me to ask:

  Is SAT for bounded treewidth formulas known to be in $\mathsf{L}$ or $\mathsf{NL}$?

Indeed, using the resultss in Elberfeld-Jakoby-Tantau-2010 one can
show that SAT can be decided in logspace on formulas whose incidence graph has bounded treewidth. Here is a sketch of how the main steps of the proof of this claim go.

The notions of tree-decomposition and treewidth can be generalized to arbitrary relational structures. See for instance sections 2 and 3 of
this paper by Dalmau, Kolaitis and Vardi.
Courcelle's theorem states that MSO logic can be decided in linear time on relational structures of constant treewidth.
A theorem of Bodlaender implies that if a relational structure has treewidth $t$, then a tree-decomposition of such structure can be found in time $f(t)\cdot n$. In other words, such a decomposition can be found in linear time on graphs of constant treewidth.
One can define suitable relational structure $\tau$ which can be used to encode a formula $F$ together with its incidence graph $I$. The treewidth of $\tau$ is at most a constant plus the treewidth of $I$.
The set of relational structures $\tau$ which encode satisfiable formulas + their incidence graphs is MSO definable.
Therefore, by Bodlander+Courcelle's theorem, one can decide whether a formula of constant treewidth is satisfiable in linear time.
Elberfeld-Jakoby-Tantau-2010 show that "linear time" can be replaced by "logarithmic space" on both Bodlaender and Courcelle's theorem.
Therefore, for each MSO formula $\varphi$, and each relational structure $\tau$, one can determine in logarithmic space whether $\tau$ satisfied $\varphi$.
In particular, SAT can be determined in logspace on graphs of constant treewidth.