I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle) It is known that Hamiltonian (Ham for short) Cycle is NP-complete and that Planar Ham Cycle is NP-Complete. The proof for Planar Ham Cycle is not from Ham Cycle.

Is there a nice gadget that will, given a graph G, replace all of the crossings
with some planar gadget so that you have a planar graph G' such that

  G has a Ham cycle iff G' has a Ham cycle.

(I'll be happy with variants- like Ham path or directed Ham Cycle or
Directed Ham Path.)

No.  At least, no "nice" gadget for one crossover.

Let $(a, b)$ and $(x,y)$ be a cross we want to replace.

There are many cases for our graph, $G$, but we have to satisfy at least the following four.  Case 1: there is at least one hamiltonian cycle, but none use either of the edges.  Case 2: there is at least one cycle, and all cycles use exactly one of the two edges.  Case 3: there is at least one cycle, and all cycles use both edges.  Case 4: there is no hamiltonian cycle.

If our gadget has two (or more) vertices for each of $a, b, x, y$ adjacent to all the same neighbors (so that $a_0$ and $a_1$ retain $a$'s neighbors) then $G'$ will not necessarily still be planar.  In order to satisfy the first of our cases above, we then cannot have any new vertices in the gadget.

In order to satisfy case 3 above, we must have at least two edges in the gadget.  Neither planar and covering pair, $(a, x), (y, b)$ nor $(a, y), (x, b)$ satisfies case 2, so we need a third edge.  Without loss of generality, let those three be $(a, y), (y, b), (x,b)$.

However, that replacement breaks the fourth case, because $G'$ could contain a hamiltonian cycle when $G$ does not.  Take, for example, $G = (V, E)$ where $V = \{a, b, x, y, p, q, r, s, t\},$ and
$E = \{(a, b), (x, y), (a, r), (a, p), (a, q), (b, s), (b, x), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$.  $G$ is not planar and does not have a hamiltonian cycle.

Then $G' = (V, E')$ where $E' = \{(a, y), (y, b), (x, b)\} \cup$
$\{(x, y), (a, r), (a, p), (a, q), (b, s), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$.  $G'$ is planar, and has a hamiltonian cycle ($a, q, x, t, p, s, b, y, r, a$).

Note that if $(b, y)$ was the edge not added instead of $(a, x)$, then $G'$ would not have a hamiltonian cycle.  It seems that you'd have to have knowledge of the possible cycle to choose the edge correctly, though.

A similar problem exists for having the gadget include one of the diagonal edges, such as: $(a, b), (a, y), (x, b)$.

Since adding three edges breaks case 4, adding more won't help.

Thus, no "nice" gadget exists.  It could be that a gadget exists that pays more attention to the neighbors of each of $a, b, x$ and $y$, but that doesn't seem very "nice".

(Note: please let me know if I made any errors above!)

(Note 2: I had some nice figures, but can't post them.  Posted.)


Does bisimulation or the approximation lemma work for monadic streams? For ordinary streams $S_A := \nu X. A \times X$, there is a bisimulation lemma. It says that two streams are equal if there exists a bisimulation between them. A bisimulation is a relation $\sim$ on streams defined like this:
$s_1 \sim s_2 \iff \operatorname{head} s_1 = \operatorname{head} s_2 \wedge \operatorname{tail} s_1 \sim \operatorname{tail} s_2$.

Now, let $M$ be a monad. We'll define the type of "monadic streams" $S^M_A := \nu X. M (A \times X)$. Intuitively, if $M$ corresponds to a side effect, every time I retrieve the head from the stream I have to perform the side effect. I can define $\operatorname{head}^M: S^M_A \to M A$ and $\operatorname{tail}^M: S^M_A \to M S^M_A$ (using functoriality of $M$).

My question is now: Is there anything similar to bisimulation for monadic streams? Can I prove equality of monadic streams in the same way, using $\operatorname{head}^M$ and $\operatorname{tail}^M$? If not, what are proof methods that work on this coinductive type? Maybe the approximation lemma?

Edit: Maybe there has to be a restriction on the monad, like being completely positive?

Here's a well written piece explaining what the proper definition of a stream monad should be: Proper Definition of the Stream Monad

The resumption and reactive resumption monads are similar to the stream monad:Resumption Monad Transformers


what is easy for minor-excluded graphs? Approximating number of colorings seems to be easy on minor-excluded graphs using algorithm by Jung/Shah. What are other examples of problems that are hard on general graphs but easy on minor-excluded graphs?

Update 10/24
It seems to follow Grohe's results that formula that is FPT to test on bounded-treewidth graphs is FPT to test on minor excluded graphs. Now the question is -- how does it relate to tractability of counting satisfying assignments of such formula?

 The above statement is false. MSOL is FPT on bounded tree-width graphs, however 3-colorability is NP-complete on planar graphs which are minor-excluded.

The most general result known is by Grohe.  A summary was presented in July 2010:

Martin Grohe, Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors, LICS 2010.  (PDF)

In short, any statement that is expressible in fixed-point logic with counting has a polynomial-time algorithm on classes of graphs with at least one excluded minor.  (FP+C is first-order logic augmented with a fixed-point operator and a predicate that gives the cardinality of definable sets of vertices).  The key idea is that excluding a minor allows the graphs in the class to have ordered treelike decompositions that are definable in fixed-point logic (without counting).

So a large class of answers to your question can be obtained by considering properties that are definable in FP+C but that are hard to count.

Edit: I'm not sure this actually answers your question, even less so for your update.  The pointer to and statement of Grohe's result are correct, but I don't think the struck out text is relevant for your question.  (Thanks to Stephan Kreutzer for pointing this out.)  It might be worth clarifying: do you want a counting problem that is difficult in general but easy on minor-excluded classes, or a decision problem?


A property of suffix-free regular languages of maximal state complexity for the reverse operation Let $L$ be a regular suffix-free language whose complete minimal automaton has $n$ states and  that the minimal automaton of $L^R$ has exactly $2^{n-2}+1$ states. Let $p, q$ be two distinct states of the minimal automaton of $L$ which are neither the initial state nor a sink state, then there exists a word $w \in X^*$ such that $\delta(q, w) = \delta(p, w)$ in the minimal automaton for $L$.

That such languages exist is shown in this paper. The above reasoning is used in a paper without any further explanation, and I do not see that it is true. If we denote by $Q = \{0,\ldots, n-1\}$ the states of the minimal automaton of $L$ and by $F$ its final states, where $0$ is the start state and $n-1$ the sink state (which a suffix-free language always has) then it just precedes with constructing a NFA for $L^R$, determinizing by the subset construction and showing that it must contain the $2^{n-2}+1$ sets $\{ \{ 0 \} \}\cup \{ S \subseteq \{1,\ldots, n-2\}\}$ as states. Hence for $p,q \in \{1,\ldots, n-2\}$ we have some $p,q \in S$ such that $\delta_R(F, w) = S$ in the constructed automaton for $L^R$, and then it concludes that $\delta(p, w^R) = r = \delta(q, w^R)$ for some state $r$.

StefanH: You are right, there was this bug in the proof of Theorem 9 in the arxiv version; the argument worked only for $|F|=1$. We fixed this in the revised version for a journal (not published yet) in a similar way you proposed. I have just updated arxiv (https://arxiv.org/abs/1504.05159).


Quadratic relationship between nondeterministic and deterministic space? Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades.

Suppose we approach the problem from the other end.
For simplicity, assume the Boolean alphabet.
The amount of space used by a TM to decide a computable language is often closely related to the logarithm of the number of states used by the automaton simulating the TM for each regular slice of a language.
This motivates the following question.

Let $D_n$ be the number of syntactically distinct DFAs with $n$ states, and let $N_n$ be the number of distinct NFAs with $n$ states.
It is straightforward to show that $\lg N_n$ is close to $(\lg D_n)^2$.

Further, let $D_n'$ be the number of distinct regular languages that can be recognised by a DFA with $n$ states, and let $N_n'$ be the number recognised by an NFA.

  Is it known whether $\lg N_n'$ is close to $(\lg D_n')^2$?

It is not clear to me how $D_n$ and $D_n'$, or $N_n$ and $N_n'$, are related to each other, or how closely.
If all this relates to a well known question in automata theory then a hint or pointer would be appreciated.
The same question is also relevant for two-way automata, due to the same reasoning, and I am especially interested in this version.

In my paper with Domaratzki and Kisman, "On the number of distinct languages accepted by finite automata with n states" published in J. Automata, Languages, and Combinatorics 7 (2002) we proved that if $G_k (n)$ is the number of distinct languages accepted by NFA's with $n$ states over a $k$-letter alphabet, and $g_k (n)$ is similarly the number of distinct languages accepted by DFA's, then for fixed $k \geq 2$

(i) $\log g_k (n)$ is, up to smaller order terms, asymptotically $kn\log n$

(ii) $\log G_k (n)$ is, up to smaller order terms, asymptotically between $(k-1)n^2$ and $kn^2$.


Is the problem of finding operators to satisfy a list of boolean variables NP complete? This is similar to SAT, except that we know the assignment of each variable, but do not know the assignment of any boolean operator. In that case, is finding the assignment of each operator so the expression evaluates to a given boolean value a NPC problem?

Actually, I was wondering if finding assignment of arithmetic operators to satisfy an integer arithmetic expression(e.g., $1$ $op_1$ $3$ $op_2$ $7$ $op_3$ $op_4$ = 10) is NP complete?

With addition and subtraction, I think the Partition problem, which is NP-hard, reduces to your second problem.

Given a set $S = \{s_1, s_2, \ldots, s_n\}$ we create the problem

$s_1$ $op_1$ $s_2$ $op_2$ $s_3$ $op_3$ $\ldots op_{n-1}$ $s_n = 0$.

If a solution exists, we create two sets:

$S_1 = \{s_1\}\cup \{s_i | op_{i-1} = +\}$

$S_2 =  \{s_i | op_{i-1} = -\}$

These two sets have to have the same sum by the setup of our original problem, so the partition problem is solved.  This shows that not only is coming up with the actual solution to this problem hard, it's in fact NP hard to determine if a solution exists (at least for addition and subtraction).

For a set of operations that doesn't allow creation of negative integers, say multiplication and addition, it's not so clear.  Also, this only shows that the problem is weakly NP-hard; there may be a reduction that gives a stronger result than this.


Why are linear bounded automata not as popular as other automata? In my experience, context-sensitive languages and linear bounded automata are frequently skipped or breezed over in computability theory courses, and are even left out of some notable text books, although finite and pushdown automata receive a lot of attention. Surely there must be a good reason for why LBAs are given less focus than their counterparts?

With "appropriate" modifications we can turn these classes into complexity classes; Finite Automata into $NC^1$, CFL into LogCFL, and LBA into PSPACE.

It should now be quite clear why we are interested in the first two more than LBA. The first two naturally fit into the usual definition of feasible computation. But PSPACE does not.


Count the number of spanning trees fast Let $t(G)$ denote the number of spanning trees in a graph $G$ with $n$ vertices.  There is an algorithm that computes $t(G)$ in $O(n^3)$ arithmetic operations. This algorithm is to compute $\frac{1}{n^2} \det(J + Q)$, where $Q$ is the Laplacian of of $G$ and $J$ is the matrix consisting solely of $1$'s. For more information on this algorithm see Biggs - Algebraic graph theory or this Math SE question.

I wonder if there is some way to compute $t(G)$ faster. (Yes, there is faster than $O(n^3)$ algorithms for computing determinant but I am interested in some new approach.)

It's also interested in considering special families of graphs (planar, maybe?).

For example, for circulant graphs, $t(G)$ can be computed in $O(n \lg n)$ arithmetic operations via the identity $t(G) = \frac{1}{n} \lambda_1 \dotsm \lambda_{n-1}$, where $\lambda_i$ are nonzero eigenvalues of Laplacian matrix of $G$, which can be computed quickly for circulant graphs. (Represent the first row as a polynomial and then compute it on $n$-th roots of unity - this step uses the Discrete Fourier transformation and can be done in $O(n \lg n)$ arithmetic operations.)

Thank you very much!

It is known that, for $G$ of bounded treewidth, the Tutte polynomial $T(G;x,y)$ can be evaluated at any $(x,y)$ using $O(n)$ arithmetic operations. If $G$ is connected, then $t(G)=T(G;1,1)$.


Sequential execution in π-Calculus I am just starting into process algebra (π-Calculus) for formally defining the operational semantics of a system. One common statement that I come across that π-Calculus is used for Concurrent and parallel processing systems.

However if two processes share the common link and send some token on the same link, where the later process will not begin until it receives the token then does it represent a sequential execution in π-Calculus ? , is my understanding correct?

So the below shows a sequential execution between process P and Q where: first process P outputs y on channel x and then process Q shares the same channel x and get the token y on it and only then begin?.

Sequential execution is an edge case of concurrent computation.
Robin Milner said this clearly in his  Turing award lecture "Elements of interaction" (CACM, 36(1), 1993):

I reject the idea that there can be a unique conceptual model,
or one preferred formalism, for all aspects of something as large
as concurrent computation, which is in a sense the whole of our
subject – containing sequential computation as a well-behaved
special area.

You can see sequential computation as a form of well-behaved, nice concurrent computation. This niceness comes out when comparing the processes of reasoning about, an implementing sequential vs concurrent computation.

But this insight is much older and forms the essence of the Actor
model. See for example Hewitt's 1976 "Viewing Control Structures as
Patterns of Passing Messages".

There are various ways of enforcing sequential computation in process
calculus. A simple one is only to allow processes that have at most
one active output, i.e. an output that is not under an input
prefix. This can be enforced by typing see e.g. "Strong Normalisation in the $\pi$-Calculus".

Now coming to your question: does interaction on $x$ in  $x(v).P \ |\ \overline{x}y.Q \rightarrow P[y/v] \ |\ Q$ represent sequential behaviour as such? No. The reason is that other processes could be running in parallel with $x(v).P \ |\ \overline{x}y.Q$. All we are seeing here is an exchange of messages, a handshake, where the receiver has to wait until the sender's message arrives.


Problem with a group as complexity parameter? I am currently studying a complexity problem related to symmetries, and am considering a study of the parameterized complexity of the problem.

In theory, any part of the input can be fixed as a parameter, but in practice it seems like parameters are almost always integers.
Some problems use a graph as a parameter, such as the testing whether H is a minor of G (polynomial when H is fixed, hence fixed parameter tractable with H as a parameter).

My question is: do you know any study of the complexity of a problem parameterized by a group?

Candidates could be classical group-related problems, such as coset intersection problem or hidden subgroup problem, but I have not found such parameterized complexity study for them.

Many of the best results around graph isomorphism and permutation group algorithms are parametrized by some structure of a relevant group. For example, let $\mathcal{S}_d$ denote the class of groups all of whose composition factors are isomorphic to subgroups of $S_d$. Then coset intersection for groups in $\mathcal{S}_d$ can be solved in polynomial time for constant d. This is closely related to the polynomial-time isomorphism test for bounded-degree graphs.

I think there are also several other problems that are solvable in polynomial time when certain associated groups are in $\mathcal{S}_d$ for $d=O(1)$, but I don't have references off the top of my head.


Complexity of the $(3,2)_s$ SAT problem? Let define the $(3,2)_s$ SAT problem : Given $F_3$, a satisfiable 3-CNF formula, and $F_2$, a 2-CNF formula ($F_3$ and $F_2$ are defined on the same variables). Is $F_3 \wedge F_2$ satisfiable?

What is the complexity of this problem ? (Has it been studied before ?)

This problem is NP-complete.

Let $\varphi$ be an arbitrary CNF formula (an instance of SAT).  Consider $\varphi \lor y$, where $y$ is a fresh variable; obviously, this formula is satisfiable (you can simply set $y$ to true).  Now convert $\varphi \lor y$ to 3-CNF, using any standard method, and let $\psi$ denote the result.  Note that $\psi$ is a satisfiable 3-CNF formula, so we can let $F_3 = \psi$.  Now, let $F_2 = \neg y$.  Notice that $F_3 \land F_2$ is satisfiable if and only if $\varphi$ is.  Therefore, the $(3,2)_s$ SAT problem is at least as hard as SAT.  Also, it is clearly no harder than SAT.  Therefore, it is exactly as difficult as SAT.


CFGs in a certain normal form Consider Context-Free Grammars with rules of the form $S\to\epsilon$
or $A\to aB | Ba|a$,
meaning that any nonterminal other than $S$ can be replaced by a terminal, or by a pair of letters exactly one of which is nonterminal (and the other one terminal). What class of languages do such grammars generate? Certainly the regular ones, but also $a^n b^n$, via the rules $S\to\epsilon|aB$, $B\to b|Ab$, $A\to a|aB$. Short of a full characterization, I conjecture that these grammars do not generate the full CFL language family, and would be curious to see a proof.

A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.
A linear language is a language generated by some linear grammar.
See also:  https://en.wikipedia.org/wiki/Linear_grammar

It is known that the regular languages form a proper subfamily of the linear languages, and that the linear languages form a proper subfamily of the context-free languages.
The language $\{a^kb^kc^nd^n|k,n\ge1\}$ is known to be context-free but not linear.

The text-book "Introduction to Automata Theory, Languages, and Computation" by John E. Hopcroft and Jeffrey D. Ullman (Addison-Wesley, 1979) states a pumping lemma for linear languages:

  Let $L$ be a linear language.
  Then there exists an integer $n$ such that for any word $p\in L$ with $|p|\ge n$, there exists a factorization $p=uvwxy$ with the following properties:

  $uv^iwx^iy \in L$ for all integers $i\in\mathbb{N}$
  $|vx|>0$
  $|uvxy| \le n$.


Is an NP-hardness proof of an NP-hard problem considered a contribution? I am solving a problem that is claimed to be NP-hard elsewhere, say in the paper [XYZ]. The NP-hardness provided in [XYZ] is complicated and uses advanced techniques. After some research and work, I succeeded to give a simple and clear proof of the NP-hardness. I am wondering if this is considered as a contribution or not? I am trying to motivate my work but I didn't find a similar path.

I don't know if this is the right place to ask or should I go to academia?

There are venues that are interested by elegant proofs of existing results, see for instance the Symposium on Simplicity in Algorithms.

So yes, in some cases an elegant proof can be considered as a contribution, especially if it offers new insights.


Convex polygons inclusion relation I have the following problem which came as a subproblem in some work I was doing and I am completely stuck.
Note that I am interested in it only in terms of worst case time complexity (not heuristics or anything else).

Given is a set $\mathcal{P}$ of $m$ convex polygons with $n$ overall vertices.

PROB: Find the set $Z \subset \mathcal{P}$, such that for any $Q \in Z$, there exists a $P \in \mathcal{P}\setminus \{Q\}$ with $P$ contained in $Q$. (i.e. "Find the polygons which contain at least one polygon")

In the following example, the set Z would consist of the 4 highlighted polygons

Some thoughts I had were:

A first idea was to plane sweep with all vertices as events. Every time an event would come we would check the polygons it belongs to and mark them. When the event would be the end of a polygon we could verify that if this belongs to any polygon or not.
The problem is that a query event could take $O(m)$ as it could be inside $O(m)$ polygons (assuming an interval tree DS where an "all_overlap" operation takes $O(\min\{m,c\cdot \log m\})$ time, where $c$ is the number of overlaps - containing polygons). Moreover, I believe we can create a worst case instance where $O(n)$ events have $O(m)$ overlaps. So, with this approach it seems that we could end up with an $O(mn + n\log n)$ time complexity.
I started having some thoughts for a more elaborate plane sweep to use the pairwise polygon intersections but since this can be $\Theta(m^2)$ in the worst case, I didn't further look on that.
Another thought was to make an algorithm using range search queries for the convex polygons. If we triangulated every polygon, having $O(n)$ triangles, we could check the containment. Unfortunately, taking a "brief look", I didn't find very "positive" results for answering fast range queries with anything different than rectangles, e.g. triangles. Although I didn't yet delve very deep into it.

I would be extremely happy to have an $O((1+|Z|) n\log^2 n)$ time algorithm. I am not positive about that anymore. So, I would be happy with any algorithm or ideas how to further proceed.

Finally, and perhaps as a starting point, one could consider the simplified decision problem.

PROB*: Does there exist $Q \in \mathcal{P}$ such that there exists a $P \in \mathcal{P}\setminus \{Q\}$ with $P$ contained in $Q$.

What would be an efficient algorithm for that?

Here's an argument that you need time quadratic in the number of polygons. More precisely,
you should not be able to find containing pairs among $n$ $k$-sided polygons in time $O(n^{2-\epsilon})$, for any $k=O(n^{\delta})$ and any $\epsilon,\delta>0$ It's a reduction from the orthogonal vectors problem, the problem of finding two disjoint binary vectors among a set of $n$ $k$-dimensional binary vectors, for which the non-existence of an algorithm with time $O(n^{2-\epsilon})$ is a standard conjecture in fine-grained complexity (see e.g.  Abboud et al, "More consequences of falsifying SETH and the orthogonal vectors conjecture"). Here orthogonality is measured in $\mathbb{Z}^k$, i.e. it means that the vectors have disjoint subsets of nonzero coordinates.

Given a set of vectors among which we wish to find an orthogonal pair, consider a regular $k$-gon $P$, whose vertices correspond to the coefficients of our vectors. For each vector $x$ construct a polygon $p(x)$ as the convex hull of the $k$-gon vertices for which $x$ has a nonzero coefficient. To make sure that none of these polygons contains each other, shrink each $k$-gon by a factor $1-\gamma |x|$ for some very small number $\gamma$, so that when one vector is dominated by another its polygon is shrunk more.

Next, form two more regular $k$-gons $Q$ and $R$, concentric with $P$, where $Q$ is slightly smaller than $P$ (so that all its vertices are inside the shrunken copies of vertices of $P$) and $R$ is slightly bigger (both close enough that the construction below produces convex polygons). For each vector $x$, construct a second polygon $q(x)$, a convex $k$-gon that, on each ray from the origin through a vertex of $P$, $Q$, and $R$, chooses either a vertex of $Q$ or $R$: a vertex of $Q$ when the corresponding coefficient of $x$ is nonzero, and a vertex of $R$ when it is zero.
We can make sure that all vectors have at least one zero coefficient in order to ensure that no $q(x)$ is contained inside a $p(y)$, and we can do the same variable-shrinking trick to ensure that no two $q$'s are nested.

With this construction, the only remaining containments of polygons are that a polygon $q(x)$ contains another polygon $p(y)$. This happens if and only if $x$ and $y$ are orthogonal. So if we could solve your polygon question in sub-quadratic time, we could also solve the orthogonal vectors problem in sub-quadratic time, conjectured to be impossible.


Wouldn't the calculus of constructions with linear types be a simple functional core that is consistent and expressive? I have recently asked if there is a simple functional core that is consistent and expressive. In another question, cody pointed out that this is an open problem to have a language that is:

Consistent/Normalizing
Can express all the type families from Coq (or even Agda)
Allows for a simple expression of recursion over these families
Simple or has a small number of core constructions (Π,Σ,μΠ,Σ,μ).

Now, suppose we take the elementary affine logic and extend it with dependent types and fix. It is easy to prove that language is consistent and normalizing as a consequence of EAL. It can, I believe, express all the type families from Coq, with lambda-encodings and since it has fix. A simple expression of recursive algorithms is possible with church-encodings for iteration and scott-encodings for matching. And it is obviously simple, as it only has ∀, ! and let. Moreover, such language would have the very comforting property that it can be reduced optimally using the abstract fragment of Lamping's algorithm.

All things considered, such language looks like a perfect candidate for the role of a small functional core that serves as an universal code-interchange format, as proposed by Gabriel. Is my suspicion correct, or is there any problem with this reasoning?

This is a tough question to answer, since simplicity is in the eye of the beholder.

Certainly $\lambda$-encodings have their drawbacks, there are reasons why Coq decided to move away from them, the most obvious one is the inability to introspect the subterms during recursion. The second is the general awkwardness in defining deeply or mutually recursive functions.

As you note, the "fix-encoding" avoids this but then it is hard to define non-constant functions (which is the point Damiano brings up)! You have to choose: introspection or recursion. Often we want both.

I'm also a bit skeptical of Gabriel's proposal: how does he compute exponentials on "native" ints without recursion?

In addition, the fact that EAL can only express elementary functions seems intuitively like it should restrict "natural" ways of writing recursions. In particular this shouldn't be well-defined:

Fixpoint acker m := match m with
| O => S
| S m => (fix acker' f n := match n with
    | O => f 1
    | S n => f (acker' f n)
    end)
   (acker m)
end.

since it defines a non-elementary function. So what feature of EAL is preventing this definition? If I understand correctly (and I'm not sure I do), the term f (acker' f n) cannot be well-typed, there must be some "stratum" which prevents the final application of f.

So certainly the natural way to write this function is forbidden. What other natural things are forbidden in this framework? It's hard to say without asking a specialist, but my guess is that there will be a fair number of things. Linear type systems can be powerful frameworks, but they aren't very convenient or natural for writing programs.

It's also an important fact (but maybe this is asking for a lot) that $0\neq 1$ is directly provable in Coq, thanks to large elimination. Is adding this feature easy in your proposal?

Finally, there's something I'm always worried about when I hear about type systems with linear logic: how hard is it to write a type checker? Certainly the checker has to figure out which pieces of the context go where when performing checking. Also the user or the front-end has to figure out where to put all the !s, if you want to have any non-linear components (and you usually do!).

To summarize, my answer to the question "is EAL with dependent types simple, consistent and expressive?" is probably not: it is probably consistent, but I'm not sure it's simple, and I don't think it is sufficiently expressive.

However, there is a "simple" way to refute this claim: write down the system definition, ideally prove it consistent, and write down some simple functions using it, probably up to, say, red-black trees or something. If the fully detailed syntax and typing rules is large, then the system is complex, if it is very tough to write down the functions, then it is insufficiently expressive. If it is neither of those, then you've answered a tough open problem in type theory!


Barriers to separating other complexity classes Do Natural Proofs, Relativization and Algebrization also affect separation of other complexity classes like $L\neq NL\neq NP\neq coNP \neq PH\neq PSPACE$ etc?

For instance natural proofs barrier should affect any proof of $NP\neq CoNP$ since it will separate $P\neq NP$. However relation between $NP$ and $CoNP$ does not seem to have much with OWFs as compared to relation between $P$ and $NP$. So do natural proofs affect the stronger separation of $NP\neq CoNP$?

There are (at least) two areas where existing barriers have little to say:

ACC Lower Bounds There is no known barrier to proving that TC0 is not in (non-uniform) ACC -- other than the possibility that the separation may be false. It's unclear whether the Natural Proofs barrier should apply to ACC. The question boils down to: should we expect there to be pseudorandom functions implementable in ACC?

LOGSPACE vs NP As pointed out by Fortnow, the existing oracle mechanisms for space-bounded computation do not seem to present a real barrier to LOGSPACE vs NP. To my knowledge, the known oracle models which yield a collapse of LOGSPACE and NP also collapse ALTERNATING LOGSPACE (i.e., P) and ALTERNATING POLYTIME (i.e., PSPACE), hence these oracles treat alternating computational models inconsistently with reality (since LOGSPACE is not equal to PSPACE).


Flynn's taxonomy, and "task parallelism and data parallelism" Quoted from http://en.wikipedia.org/wiki/Task_parallelism:

  Task parallelism (also known as function parallelism and control
  parallelism) is a form of parallelization of computer code across
  multiple processors in parallel computing environments. Task
  parallelism focuses on distributing execution processes (threads)
  across different parallel computing nodes. It contrasts to data
  parallelism as another form of parallelism.

I was wondering if there is some correspondence between  Flynn's
taxonomy (SISD, SIMD, MISD and MIMD), and "task parallelism and data parallelism"? For example,

does task parallelism mean multiple-instruction in Flynn's taxonomy,
so one can say "task parallelism = MISD+MIMD"?

does data parallelism mean multiple-data in Flynn's taxonomy, so one
can say "data parallelism = SIMD+MIMD"?
If there is no exact correspondence between the two classification
methods, how shall one understand their differences and relations?

Thanks and regards!

Task/Data parallelism is a simple classification that lies at the algorithm-level of a computation.

Flynn's taxonomy describes low-level machine architectures or models.

Trying to draw lines between both completely ignores the vast sea of complexity that lies between those two levels.  Using an example; You can do task, data and pipeline parallelism perfectly on a SISD for example. Stating that you cannot ignores the vast complexity of today's operating systems.


About learning a single Gaussian in total-variation distance I am looking for the proof of this following result which I saw as being claimed as a "folklore" in a paper. It would be helpful if someone can share a reference where this has been shown!

  Let $G$ be an $n-$dimensional Gaussian and let $\delta >0$. Then there
  exists a polynomial time algorithm that given $O(\frac {n^2}{\delta^2})$ independent samples from $G$ returns a probability
  distribution ${\bf P}$ so that with probability at least $\frac 2 3$
  we have, $d_{\text{TV}}(G,{\bf P}) < \delta$

To clarify the notation of "TV" used above :

Given two distributions $\bf P$ and $\bf Q$ with p.d.fs (which we denote by the same symbols) we define the ``Total-Variation" distance between them as,

$ d_{\text{TV}}({\bf P},{\bf Q}) := \frac {1}{2} \int_{\bf x \in \mathbb{R}^n} \vert {\bf P}(\bf x) - {\bf Q}(\bf x) \vert d{\bf x} =: \frac {1}{2} ||{\bf P} - {\bf Q}||_1 $

Essentially, this follows from three facts:

learning a Gaussian in total variation distance $\delta$ is equivalent to learning its two parameters, $\mu,\Sigma$, to (respectively) $\ell_2$ and relative Frobenius norms $O(\delta)$. (Since then the "empirical Gaussian" with the mean and covariance you estimated will be $\delta$-close to the true Gaussian).
learning the mean $\mu$ to $\ell_2$ distance $\delta$ can be done with $O(\frac{n}{\delta^2})$ samples. (This is tight)
learning the covariance to relative Frobenius distance $\delta$ can be done with $O(\frac{n^2}{\delta^2})$ samples. (This is tight)

I suggest you try to prove these yourself. The first one follows from relatively "standard" facts about Gaussians [1], the second two are good exercises.

(If you really want a specific reference, I can try to dig some up.)

[1] Theorem 1.3 in this recent paper is overkill, but will do the job. https://arxiv.org/abs/1810.08693


Reducing threshold questions to finiteness questions It is usually simpler to reason about calculus where the limitation is finiteness of computation rather than a threshold like "computable in polynomial amount of time".

In formal languages theory for example, rather to use the $\exists n. x^{n+1} = x^n$ to characterize aperiodic monoïd, it is easier to use profinite words so that $x^{\omega+1} = x^{\omega}$.

In complexity theory, the only technic I know which is linked to that is the padding trick for example linking the problem of P vs NP to EXPTIME vs NEXPTIME. But the natural infinite equivalent of complexity questions would be computability ones'.

  Are there some results that link complexity to computability questions using some encoding such that the resource threshold of complexity theory becomes a finiteness question of computation in computability theory ?

Sipser proved that no infinite parity can be computed by an (infinite) circuit of any constant depth, which you can view as a warm-up to the result that PARITY is not in $AC^0$.

There are also some results and attempts at proofs of lower bounds in proof complexity using nonstandard models (some results of Ajtai and Krajicek. See esp. Krajiceks' "Forcing with Random Variables and Proof Complexity," available from Cambridge Press, but also a draft available online) . The basic idea is to build a nonstandard model of arithmetic in which a statement is false in the model (rather than "true, but without short proofs"), and then, from the properties of the model, infer that a corresponding sequence of finite statements does not have polynomial-size proofs in some proof system.

I'm not sure, but my impression is that often these results sort of "hide the asymptotics under the hood" so that it's not so much a reduction from threshold to finiteness as it is a new mathematical language in which "false" in the new language corresponds to "without short proofs" in the old language. That's not to say that the new language doesn't provide a useful new viewpoint, but I'm not quite sure if it's what you're looking for.


Practical applications of parity games Are there examples of practical applications of parity games, ie systems, in the real world, that can be represented as parity games ?

Usually related documentation on parity games has almost never a practical example of this application.

Here is a rather different application from what you may have had in mind. Linear programming has many practical applications. There are many algorithms for linear programming and those based on George Dantzig's simplex method are among the most commonly implemented. An important parameter of simplex is called the pivoting rule. Victor Klee and George Minty provides a set of polytopes on which the pivoting rule suggested by Dantzig would require an exponential number of pivoting steps. Since then, examples demonstrating an exponential lower bound have been discovered for nearly every deterministic pivoting rule.

Simplex can however use randomized pivoting rules. Gil Kalai in 1992 introduced a randomized pivoting rule and proved a sub-exponential upper bound for simplex with this rule. Also in 1992, Micha Sharir and Emo Welzl defined LP-type problems which include  standard linear programming and with    Jiří Matoušek also proposed randomized variants of simplex and proved subexponential upper bounds for this variant. Subexponential lower bounds were also discovered on LP-type problems, but till about 2010 there were no concrete examples of linear programs on which these lower bounds could be demonstrated. See these two posts on Gil Kalai's blog for another telling of this story, the connection to the Hirsch conjecture and links to the literature.

What does any of this have to do with parity games? A couple of steps are required to set up a connection. An open problem in parity games research till about 2009 was to determine if certain policy iteration algorithms for solving parity games might have exponential behaviour. See the papers of Marcin Jurdziński for more on this. Oliver Friedmann, starting in 2009, exhibited examples of parity games on which certain policy iteration algorithms required exponential time. By exploiting a connection between parity games and certain LP-type problems he derived sub-exponential lower bounds for various pivoting rules for simplex. (Note however that one of the results, which concerned the Random Facet algorithm was shown by Oliver Friedmann, Thomas Hansen and Uri Zwick to be erroneous.)

I hope you'll agree that's a pretty fascinating and convincing example of an application of parity games.

There is a more direct answer to your question as well. Suppose one wants to design a discrete controller that regulates how some physical system (thermostat, chemical plant, etc.) behaves based on the state of the system and the state of the environment. The question of whether a controller exists to provide the guarantees a designer wants can be reduced to solving parity games. So you can think of a parity game in terms of systems, environments and controllers.

Another setting is program analysis. Suppose you want to automatically determine if a  program satisfies some correctness property in the modal $\mu$-calculus. Model checking is one approach to solving this problem and $\mu$-calculus model checking is deeply connected to parity games.


Primary source for the equivalence of non-deterministic polynomial time and deterministic polynomial time verification Who was the first person to show that a language is in NP if a certificate for the language can be verified in polynomial time?  Do we have a paper that formally proves this?  When did the TCS community start de-emphasizing non-determinism in favor of verifiability? I cannot, for the life of me, find a good reference for this beyond texts like Papadimitriou and Arora and Barak.

[An extended comment] I think that the "roots of verification" are already contained in Karp's milestone paper "Reducibility Among Combinatorial Problems" (1972):

  ...
  Let $P^{(2)}$ denote the class of subsets $\Sigma^* \times \Sigma^*$ which are recognizable in polynomial time. Given $L^{(2)} \in P^{(2)}$ and a polynomial $p$, we define $L$ as follows:

  $L = \{ x \mid $ there exists $y$ s.t. $\langle x,y \rangle \in L^{(2)}$ and $\log(y) \leq p(\log(x)) \}$

(however Karp doesn't call $y$ a "certificate")

  ... We refer to $L$ as the language derived from $L^{(2)}$ by $p$-bounded existential quantification.

  Definition 4. $NP$ is the set of languages derived from elements of $P^{(2)}$ by polynomial-bounded existential quantification.

  There is an alternative characterization of NP in terms of nondeterministic Turing machines ... [definition of computation of a nondeterministic Turing machine] ...

and

  ... Theorem 1: $L \in NP$ if and only if $L$ is accepted by a nondeterministic Turing machine which operates in polynomial time ...


Using game-based proofs in simulation-based proofs Simulation-based security provides more natural and more powerful definition of security than game-based security. I have seen the simulation based approaches use the game-based proofs in-part to prove security of some parts of the protocol. For example, to assess the security of a protocol for round complexity or total messages exchanged during execution of the protocol, a game-baed approach is taken, but the security of the protocol itself regarding the framework (in my study the UC framework) is proven by Ideal/Real paradigm (i.e., simulation based approach).

  Question: Under what circumstances can we use a game-based approach to prove security of a part of the protocol or the whole protocol when the protocol design must conform to a simulation approach? Can we use this approach at any point for any reason as long as it is not relevant to security of the whole protocol regarding the simulation-based framework?

Let me explain it through an example: I am studying a group key exchange protocol over UC framework (simulation-based), but the protocol uses encryption schemes which are CCA-Secure (proven by a game between adversary and some oracles) or CCA2-secure (proven by a game-based approach too), signatures must be existentially unforgeable (game-based approach too) and finally the communication cost of the protocol is calculated and analysis of the protocol security is done through 10 or 11 games between adversary and simulator. Finally proofs are made to show that the protocol conforms to UC regulations.

One paper that deals with the issue is Games and the impossibility of Realizable Ideal Functionality by Datta et al, but it does't seem to address the issue in full generality. I am not aware of any general statement that guarantees simulation-based security of the whole protodol based on specific game-based security properties of its sub-protocols (unless of course the game-based definitions imply simulation based security, in which case the generic composition theorems by Canetti should apply).

However, there do exist specific instances in which one can obtain simulation-based security from game based security. The most telling example in my view is a constant-round zero-knowledge (ZK) argument for NP by Feige and Shamir (see e.g. Feige's PhD), which builds on witness indistinguishabille (WI) and witness-hiding (WH) sub-protocols. Both WI and WH are (arguably) game-based definitions, and yet the entire protocol can be proved to be ZK (which is the mother of all simulation-based definitions, at least for interactive protocols).


Cobham's Result on Efficient Computations In the following paper:

Alan Cobham (1965), "The intrinsic computational difficulty of functions", Proc. Logic, Methodology, and Philosophy of Science II, North Holland.

Cobham defined the class P as the class for efficient computations. He stated that his notion is machine-independent.

Unfortunately, I don't have access to this paper. Can anyone clarify the points he made there? Is it just a thesis, or something proved?

You can try to look at the paper A new recursion-theoretic characterization of the polytime functions by Stephen Bellantoni and Stephen Cook, which has very nice discussion on Cobham's polynomial-time characterization in the introduction section. This paper also has pointers to other related works. You can easily find the paper somewhere on the web in case you are not subscribed to Springer.


Constrained Topological Sorting with bounded number of chains In general, constrained topological sorting is NP-hard.

Now we add another constraint to it, such that take any k+1 nodes and there will be at least one pair (u, v)such that there is a path from u to v -- that is, there can be maximum k number of chains.

I want to know, is it still NP Hard?

Edit: I have my answer. Decision version of this question is in NL which implies it is in PTIME.

The additional constraint amounts to saying that the input DAG has width $\leq k$, i.e., there is no antichain of size $k+1$. In this case, if $k$ is a constant, the decision version of the constrained topological sorting problem is in NL by Prop C.2 of https://arxiv.org/abs/1707.04310, which amounts to a PTIME dynamic programming algorithm. Reconstructing a matching topological sort as part of the dynamic programming algorithm will also be in PTIME


Is deciding whether changing one entry decreases the permanent of a matrix in the polynomial hierarchy? Consider the following problem: given a matrix $M\in\{-m,\dots,0,\dots,m\}^{n\times n}$, indices $i,j\in\{1,\dots,n\}$ and an integer $a$. Replace $M[i,j]$ by $a$ and call new matrix $\hat M$. Is $per(M)>per(\hat M)$?

Is this problem in the polynomial hierarchy?

Your problem is equivalent to testing, given $M$, whether $PER(M) > 0$.

Proof: Assume you are given $M$ and you want to decide whether $PER(M) > 0$. We construct $M'$ as follows:
\begin{bmatrix}
    1 & 0 & \dots & 0 \\
    0 & & & & \\
    \dots & & M & &\\
    0 & & & &
\end{bmatrix}
It is easy to see that $PER(M) = PER(M')$. Now, define $\hat{M'}$ to be $M'$ where we replace the $(0,0)$ entry of $M'$ by $-1$. By multilinearity, it follows that $PER(M) = PER(M') = -PER(\hat{M'})$. Thus $PER(M) > 0$ if and only if $PER(M') > PER(\hat{M'})$.

Now assume you are given $M$, $(i,j)$ and $a$ and define $\hat{M}$ as in your question, that is, by changing $M[i,j]$ to $a$. We have
\begin{align}
PER(M) > & PER(\hat{M}) \text{ iff} \\
\sum_{\sigma} \prod_{k=1}^n M[k,\sigma(k)] > &\sum_{\sigma} \prod_{k=1}^n \hat{M}[k,\sigma(k)] \text{ iff} \\
\sum_{\sigma, \sigma(i)=j} M[i,j] \prod_{k \neq i}^n M[k,\sigma(k)] > &\sum_{\sigma, \sigma(i)=j} a \prod_{k \neq i}^n M[k,\sigma(k)] \text{ iff}\\
(M[i,j]-a) \cdot \sum_{\sigma, \sigma(i)=j} \prod_{k \neq i}^n M[k,\sigma(k)] > & 0 \text{ iff}\\
(M[i,j]-a) \cdot PER(M') > 0
\end{align}

where $M'$ is the $(n-1) \times (n-1)$ matrix obtained from $M$ by removing line $i$ and column $j$. $\square$


Automata model with undecidable (or non-context-sensitive) languages and no $\varepsilon$-transitions. Adding extensions to automata has always been a fruitful domain.  But usually, one wants to add weak capabilities, as undecidability comes quickly into the picture.

Take FSM with added stacks.  It is easily seen that two stacks can simulate a Turing machine's tape, and the state control of the TM is taken care of by the FSM.  Thus, such machines recognize Turing-recognizable languages.

The implicit assumption made here is that the FSM is not only non-deterministic but has $\varepsilon$-transitions, which are used to "wait" for the TM to halt.

My question is thus: what (minimal) capabilities should one add to $\varepsilon$-transition-free automata in order to make them recognize undecidable (or non-context-sensitive) languages.  I'm searching for something else than an oracle for a specific language, of course!

Nota: Requiring no-$\varepsilon$-transition means that a word of length $n$ is read taking $n$ transitions.  This may mean that the added power ought to be undecidable / of large space complexity by nature.

I do not think it is possible at all. Either such automata cannot be recursively defined, or have to make local non-recursive decisions at nodes. The first case is obviously uninteresting, and the latter is equivalent to having undecidable oracles at nodes.


How do I describe this (graph-)problem for a research paper? I have a function f(x, y) which takes two integers and returns a scalar.

My task is to find the set of (x, y) pairs, 0<x<W, 0<y<H where f(x, y)>0, which maximize the sum f(x_i, y_i) with the constraint that no two pairs shall overlap.
Two pairs (x1, y1) and (x2, y2) overlap if (x2 >= x1 and x2 < x1+y1).

I have implemented a practical solution which processes in O(WxH) time with O(W) memory. I'm pretty sure this is optimal. It seems to me that it is a kind of a graph flow algorithm, but I don't know how to formally describe it without pseudo code.

Can anybody tell me what class of problems this problem belongs to?

I attach a screenshot of a solution to one configuration (darker means higher f(x, y)).

Replace any negative value with zero. Then, think of the numbers in the range $1\dots W$ as vertices in a graph, and think of a pair $(x,y)$ as corresponding to an edge from vertex $x$ to vertex $x+y$ (or to $W$ if $x+y>W$), with weight $f(x,y)$. This graph is a DAG, and what you are looking for are the nonzero edges on a longest path from $1$ to $W$ in this DAG. DAG longest path problems can be solved in time linear in the size of the DAG (here, $O(WH)$); see https://en.wikipedia.org/wiki/Longest_path_problem.


Can the Banach-Tarski paradox be "realized" by floating-point round-off? The Banach-Tarski paradox says that
a ball in $\mathbb{R}^3$ can be partitioned into a finite number of pieces, whose rearrangement has a larger volume than the original.
It occurred to me that it might be possible to define the pieces
$P_1,P_2,\ldots,P_n$ by a finite amount of geometric data, such that
the applied rearrangement function $f(P_i)$ actually does increase the volume of $P_i$, because
of floating-point round-off error: $f$ is an isometry but when implemented
in floating-point hardware it is not an exact isometry. So it might be possible that
$$\textrm{Vol}(f(P_1))+\ldots \textrm{Vol}(f(P_n)) > \textrm{Vol}(P_1)+\ldots \textrm{Vol}(P_n) \;.$$
Repeating, this might lead to a type of "realization" of the paradox in terms of floating-point
computations.

Whether you think this would be as interesting as I do is in the eye of the beholder.

This seems to have little to do with Banach-Tarski.
In your setting, f is simply not an isometry due to floating-point errors, and in particular there must be a single piece $i$ such that $\mathrm{Vol}(f(P_i))>\mathrm{Vol}(P_i)$, so no need to cut into several pieces.

Banach-Tarski works because the notion of volume is not well-defined on the pieces. This clashes with your requirement that the pieces are defined by "a finite amount of geometric data", and with your writing of $\mathrm{Vol}(P_1)+\dots+\mathrm{Vol}(P_n)$.


Complexity status of the Edge Deletion problem to bounded degree graphs I'm interested in the complexity status of the following problem.

Input: a graph $G=(V,E)$ and two natural numbers $k$ and $d$.

Output: Yes, if there exists a subset $E' \subseteq E$ of cardinality at most $k$ such that the maximum degree of $G-E' = (V,E \setminus E')$ is at most $d$. No, otherwise.

Equivalently, your problem may be stated as follows: You are looking for a subgraph, in which every vertex degree lies in the interval $[0,d]$ and that contains as many edges as possible.

This problem is well-known to be solvable in polynomial time.
For instance, it is discussed in Chapter 10 (and in particular in Exercise  10.1.4) of the book

  M.D. Plummer and L. Lovász:
  Matching Theory
  Volume 29 of Annals of Discrete Mathematics, Elsevier, 1986.


Is there an easy way to improve this Tree Normal Form for Busy Beaver candidates? In "Attacking the busy beaver 5" by Heiner Marxen and Jürgen Buntrock, an algorithm to create tree normal candidates is explained (it also contains a concise introduction of the relevant terms).

If during simulation an undefined transition is found, the selection of the enumeration values is made as follows:

  Enumerate all meaningful values (see below) for this transition, and
  recursively do step 2 with M set to each of these more completely
  defined machines.

  The set of legal transition values is formed by an arbitrary
  combination of (n+1) target states, 2 symbols to write, and 2
  directions to move. The set of meaningful transitions enumerated in
  step 6 is a subset of all legal ones by the following reduction rules:

  From the set of states M has not yet taken, only the smallest one (according to some arbitrary but fixed order on the states) is used as
  target state (isomorphism).
  When defining the very first transition force a state change (else M never halts), write a one (isomorphism), and move left (symmetry).
  This completely fixes the very first transition.
  When defining the very last transition, consider only the halt state as target state.
  If the target state is the halt state, go left (makes no difference) and write a one (never worse). This completely fixes the
  last transition.
  If there is a state that M has not yet taken, do not consider the halt state as target state.

I'm not sure if I'm missing something, but should there not be a rule that enforces using a new state if we're determining the last open slot of all currently used states? This new rule would replace/extend rule 3 above.

In other words: With $2k-1, k \leq N$ transitions defined, and the maximum index of states used being $\leq k$, the $2k$-th transition must point to a state with index > $k$.

If we don't do this, it would be possible to create closed subsets, or equivalently, unreachable states (described e.g. by Kellett, MA thesis, 2005, p.46), one of whom will be the halting state. Those machines cannot possibly halt obviously.

For instance, given the partially defined 3-state machine 1RB 0RB, 1LA -?-, -?- -?-, the next transition (which in this example happens to be $\delta(B,1)$) must point exactly to state C.

Pointing to H is not allowed because it would quit too early (unused state C).
Pointing to A or B is not allowed because it would lead to a closed state subset with no way to leave.

Your proposed optimization is a special case of the "forward reasoning" nontermination detection that Marxen and Buntrock describe in part 5 of their paper:

  If there is a set S of states such that all transitions from elements of S are defined and their target state is also in S, (and the machine is in one of those states) it will never again leave S and thus not halt (closed state/transition cluster).

If you've implemented this nontermination detection then your optimization is redundant.  You could include it for a possible slight efficiency win.  Your optimization applies whenever we are defining the 2k-th transition and there are currently only k states.  That will not be the case as often as you might think, since Marxen and Buntrock's enumeration algorithm does not assign transitions in order by state index.  Instead, it simulates each Turing machine during enumeration and assigns each transition only as it is reached.

The "forward reasoning" nontermination detection will catch cases that your optimization would not, e.g. in this partially defined 3-state machine:

    0    1
A: 1LB, -?-
B: 1LC, 1LC
C: 1RB, 1RB


Average-case space complexity I am trying to find problems whose average-case space complexity has been analyzed.

More specifically, I am interested to know if there are any  problems with a proven  space complexity lower bound that is  super-linear, and especially if there are any  with an  average-case analysis (e.g., the bound holds even if the algorithm is allowed to err for a small percentage of times etc. )

Thanks in advance

I'm interested in but not familiar with this topic. Searching for "Average case complexity theory", I found a thesis written by Tomoyuki Yamakami:

  Average Case Computational Complexity Theory, Tomoyuki Yamakami, 1997.

Section 3.5.1 seems relevant, a space-analog notion similar to the average-time complexity is defined. Hopefully with a deeper reading we'll find some problems that has been analysed :)

Also in the paper

  On the Theory of Average Case Complexity, Shai Ben-David, Benny Chor, Oded Goldreich and Michael Luby, 1989.

Average log-space complexity is defined in Section 7.


Graph partition optimization with weights on edges and vertices I am interesting in studying the complexity of some graph partition problems, where it is important to take into account the weights on the edges as well as the weight on the vertices. Max-cut only cares about the weights on the edges, while other problems only care about the weights on the vertices. Does anyone know problems in which BOTH weights are important in order to make the optimal partition?

Thank you very much

Here's an example problem:

Input: directed graph with vertex weights $u_i$ and arcs weights $w_{ij}$.

Output: a subset S of V to maximize the sum of the following things:

$\sum_{i, j \in S} w_{ij} + \sum_{i,j \in V - S} w_{ij}$ (arc weights inside each side)
$\sum_{|{i,j} \cap S| = 1} w_{ij}u_j$: the sum over all cut edges of product of  arc weight and the weight of the destination vertex.

(not quite an answer, but too long for a comment)

Given your new cost function, I'm wondering if there's a simpler formulatio. Let $W = \sum_{(i,j) \in E} w_{ij}$. Now your goal is to maximize

\[ W - \sum_{|\{i,j\} \cap S| = 1} w_{ij} + \sum_{|\{i,j\} \cap S| = 1} w_{ij}u_j\]

Collecting terms, your goal is then to minimize

\[ \sum_{|\{i,j\} \cap S| = 1} w_{ij} (u_j - 1)\]

Setting $w'_{ij} = w_{ij}(u_j - 1)$, your problem now becomes a min cut problem with the twist that it's not a typical min cut (you're not counting edges going from one side to the other, but both sides)


Alphabet of single-tape Turing machine Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing machine using an alphabet of size $3$ (say, $0,1,$ and blank)?

(From comments below by the OP)
Note the input is written using $0,1$, but the Turing machine using alphabet of size $k$ can overwrite the input symbols with symbols from the larger alphabet. I don't see how to encode symbols in the larger alphabet in the smaller alphabet without having to shift the input around which would cost time $n^2$.

A partial answer if TM runs in $o( |x| \log |x|)$

If TM4 is a 4-symbols TM (with alphabet $\Sigma_4 = \{\epsilon,0,1,2 \} $ ) that computes $f:\{0,1\}^* \to \{0,1\}$, i.e. decides language $L = \{ x | f(x) = 1 \}$ in $(o( |x| \log |x|))$

One tape deterministic linear-time complexity is $1DLIN = 1DTime(O(n))$

Hennie proved (1) that $REG = 1DLIN$
Kobayashi proved (2) that $REG = 1DTime(o(n \log n))$

So $L$ is regular, and is obviously still regular over alphabet $\Sigma_3 = \{\epsilon,0,1\}$

So there is a DFA that decide L and uses only symbols in $\Sigma_3$. A one-tape, 3-symbols TM3 can be built directly from the DFA and it decides L using the same unpadded input of the original TM4.

... you cannot build it directly from TM4, but TM3 exists.

If TM4 runs in $\Omega(n^2)$ then you can shift the input and make a direct conversion from TM4 to TM3.

As noticed in the comments the difficult case is when TM4 runs in $\Omega(n\log n) \cap o(n^2)$.

(1) Hennie, One-tape, off-line Turing machine computations (1965)

(2) Kobayashi, On the structure of one-tape nondeterministic Turing machine time hierarchy (1985)


Looking for approximation class between NPO and Exp-APX I'm trying to identify the approximation hardness of some maximization problem A. In problem A, finding a solution whose quality is 0 (i.e. such that the value returned by the objetive function is 0) is trivial, although obtaining solutions with any quality higher than 0 is NP-hard.

If I get it right, problem A cannot be in Exp-APX: any polynomial-time algorithm would return solutions with 0 quality, so the performance ratio (i.e. quality of best solution / quality of found solution) of any polynomial-time algorithm would be infinite in the worst case. Thus the performance ratio cannot be exponentially bounded.

On the other hand, finding some bad solution for problem A is trivial, which is not the case of NPO-complete problems such as e.g. MAX {0,1}-LINEAR PROGRAMMING or MAX WEIGHTED 3-SATISFIABILITY, where finding any valid solution is NP-hard. Therefore, problem A cannot be NPO-hard, right? In particular, an AP-reduction couldn't map 0-valued solutions of problem A into some solutions of MAX {0,1}-LINEAR PROGRAMMING, as finding any solution to the latter problem is NP-hard.

So, is there any known approximation class X such that problem A could be X-hard?

Related question 1: What version of TSP is said to be Exp-APX-complete? Is it "all pairs of nodes are connected" + "the minimal distance between nodes is 1"? If finding some hamiltonian cycle weren't easy, or if 0-length round trips could exist, then the problem couldn't be in Exp-APX, could it?

Related question 2: Is there any "Max TSP" variant (i.e. finding longest round trips) that is Exp-APX-complete? Or any other Exp-APX-complete problem (preferably a maximization one) I could use to prove the Exp-APX-hardness of A?

As pointed out by Markus Bläser in the comments section, objective values must be positive integers, so they cannot be 0. Hence my problem A is not formally an NPO problem. Personally I think it makes sense to consider feasible solutions with 0 objective value in that particular problem, but using standard approximation hardness notions requires redefining the problem so that 0-objective solutions are just "not feasible". In fact, under that new definition, problem A turns out to be NPO-complete.


LogDCFL-complete problems LogCFL is the set of all languages that are logspace reducible to a context-free language. Similarly, LogDCFL is the set of all languages that are logspace reducible to a deterministic context-free language. See this wikipedia article for some natural LogCFL-complete problems. There are several other interesting LogCFL-complete problems. I could not find any natural LogDCFL-complete problems. Name any natural LogDCFL-complete problem.

The following language is a slight tweak of the usual LogCFL complete one so that it is LogDCFL complete.  The proof can be found in Sudborough's On the Tape Complexity of Deterministic Context-Free Languages.

Let $\Sigma = \{(_1,(_2,)_1, )_2\}$ and $T = \{[,],|\}$.  The following language over $\Sigma \cup T$ is LogDCFL-complete.  $L$ consists of words $$w_0\left[(_1l_1|(_2r_1\right]\ldots\left[(_1l_n|(_2r_n\right]$$ where $w_0, l_i, r_i \in \Sigma^*$ such that there exists $w_1, \ldots, w_n$ with $w_i = (_1l_i$ or $w_i = (_2r_i$ for all $i \geq 1$ and $w_0w_1\ldots w_n$ is parenthetically correct.


Is NPI contained in P/poly? It is conjectured that $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ since the converse would imply $\mathsf{PH} = \Sigma_2$. Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptyset$. However, the proof doesn't seem to generalize to $\mathsf{P}/\text{poly}$ so the possibility $\mathsf{NPI} \subset \mathsf{P}/\text{poly}$ i.e. $\mathsf{NP} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly}$ seems open.

  Assuming $\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$ (or even that the polynomial hierarchy doesn't collapse on any level), is $\mathsf{NPI} \subset \mathsf{P}/\text{poly}$ known to be true or
  false? What evidence can be put for and against it?

Here is a possible alternative to a padding argument, based on Schöning's generalization of Ladner's theorem. To understand the argument, you need to have access to this paper (which will unfortunately be behind a pay wall for many):

  Uwe Schöning. A uniform approach to obtain diagonal sets in complexity
  classes. Theoretical Computer Science 18(1):95-103, 1982.

We will apply the main theorem from that paper for $A_1$ and $A_2$ being languages and $\mathsf{C}_1$ and $\mathsf{C}_2$ being complexity classes as follows:

$A_1 = \varnothing$ (or any language in $\mathsf{P}$)
$A_2 = \text{SAT}$
$\mathsf{C}_1 = \mathsf{NPC}$
$\mathsf{C}_2 = \mathsf{NP} \cap \mathsf{P/poly}$

For the sake of clarity, the fact we will prove is $\mathsf{NP} \not\subseteq \mathsf{P/poly}$ implies $\mathsf{NPI} \not\subseteq \mathsf{P/poly}$.

Under the assumption that $\mathsf{NP} \not\subseteq \mathsf{P/poly}$ we have $A_1\not\in\mathsf{C}_1$ and $A_2\not\in\mathsf{C}_2$. It is clear that $\mathsf{C}_1$ and $\mathsf{C}_2$ are closed under finite variations. Schöning's paper includes a proof that $\mathsf{C}_1$ is recursively presentable (the precise definition of which can be found in the paper), and the hardest part of the argument is to prove that $\mathsf{C}_2$ is recursively presentable.

Under these assumptions, the theorem implies that there exists a language $A$ that is neither in $\mathsf{C}_1$ nor in $\mathsf{C}_2$; and given that $A_1\in\mathsf{P}$, it holds that $A$ is Karp-reducible to $A_2$, and therefore $A\in\mathsf{NP}$. Given that $A$ is in $\mathsf{NP}$ but is neither $\mathsf{NP}$-complete nor in $\mathsf{NP} \cap \mathsf{P/poly}$, it follows that $\mathsf{NPI} \not\subseteq \mathsf{P/poly}$.

It remains to prove that $\mathsf{NP} \cap \mathsf{P/poly}$ is recursively presentable. Basically this means that there is an explicit description of a sequence of deterministic Turing machines $M_1, M_2, \ldots$ that all halt on all inputs and are such that $\mathsf{NP} \cap \mathsf{P/poly} = \{L(M_k):k=1,2,\ldots\}$. If there is a mistake in my argument it is probably here, and if you really need to use this result you will want to do this carefully. Anyway, by dovetailing over all polynomial-time nondeterministic Turing machines (which can be simulated deterministically because we don't care about the running time of each $M_k$) and all polynomials, representing upper bounds on the size of a Boolean circuit family for a given language, I believe it is not difficult to obtain an enumeration that works. In essence, each $M_k$ can test that its corresponding polynomial-time NTM agrees with some family of polynomial-size circuits up to the length of the input string it is given by searching over all possible Boolean circuits. If there is agreement, $M_k$ outputs as the NTM would, otherwise it rejects (and as a result represents a finite language).

The basic intuition behind the argument (which is hidden inside Schöning's result) is that you can never have two "nice" complexity classes (i.e., ones with recursive presentations) being disjoint and sitting flush against each other. The "topology" of complex classes won't allow it: you can always construct a language properly in between the two classes by somehow alternating between the two for extremely long stretches of input lengths. Ladner's theorem shows this for $\mathsf{P}$ and $\mathsf{NPC}$, and Schöning's generalization lets you do the same for many other classes.


Is infinitary Böhm-reduction wrt. root-active terms for $\lambda$-calculus transitive? I expect the answer to be "obviously yes", but to my inexperienced eye, that's not directly obvious, because the definition of infinite Böhm-reduction does not include a transitivity rule (it wouldn't work), and because I couldn't find a relevant lemma in the papers themselves.

I'm referring in particular to the definition by Czajka [1] of the relation $\rightarrow^\infty_{\beta\bot}$, called infinitary Böhm-reduction. I've looked at [2], which however does not include Böhm-reduction (such that the defined relation isn't confluent IIUC, which is a problem for me).

Rationale: Defining reduction for infinitary $\lambda$-calculus is tricky. In particular, you cannot create an "infinite transitive closure" which allows an infinite number of transitivity steps, but you need to be more careful. In particular, if you define multi-step reduction coinductively, you cannot include a transitive rule, lest your relation becomes total and thus degenerate. So one ends up doing transitivity elimination, which is not always trivial; and given how unintuitive coinduction is, I'm afraid I'd fool myself when attempting a proof.

[1] Łukasz Czajka, 2014. A Coinductive Confluence Proof for Infinitary Lambda-Calculus. Proc. of Rewriting and Typed Lambda Calculi, Springer. http://www.mimuw.edu.pl/~lukaszcz/coind.pdf

[2] Jorg Endrullis and Andrew Polonsky, 2011. Infinitary Rewriting Coinductively. In Proc. of TYPES, volume 19 of LIPIcs, pages 16–27. Schloss Dagstuhl. http://drops.dagstuhl.de/opus/volltexte/2013/3897/

[3] Richard Kennaway, Jan Willem Klop, M. Ronan Sleep, and Fer-Jan de Vries, 1997. Infinitary lambda calculus. Theoretical Computer Science, 175(1):93–125. http://www.sciencedirect.com/science/article/pii/S0304397596001715

I think you'll find that the exact same proof of Lemma 3 in [1] (the proof itself appears in [2]) concerning $\rightarrow^\infty_\beta$ also holds for $\rightarrow^\infty_{\beta\bot}$: indeed, they are defined in the same way from $\rightarrow^*_\beta$ and $\rightarrow^*_{\beta\bot}$ respectively, which are transitive by definition!

The lemma holds for an arbitrary reflexive-transitive congruence relation in place of $\rightarrow^*_{\beta\bot}$, as you can verify in [2] without needing to go into the detail of the coinductive proofs. In particular, the proofs of lemmas 4.1-5 in [2] are unchanged (with extra induction cases in 4.4).


Complexity of hidden polygon puzzle on square grids? Hiroimono

 is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle.

The problem is:

Input: Given a set of points on on a $n$x$n$ square grid and integer $k$

Question: Is there a rectilinear polygon (its sides parallel to the $x$ or $y$-axis) such that the number of points on the polygon's corners is at least $k$?

Every corner of the polygon must be at one of the input points (so bends are only allowed at an input point).

  What is the complexity of this problem? What is the complexity if the solution restricted to convex rectilinear polygons?

EDIT April 13: Alternate formulation: Find a rectilinear polygon with the maximum corners on the given points.

I thought of this weird reduction (chances that it is wrong are high :-). Idea: reduction from Hamiltonian path on grid graphs with degree $\leq 3$; each node of the planar graph can be shifted in such a way that every "row" ($y$ value) and every "column" ($x$ value) contains at most one node. The graph can be scaled and each node can be replaced by a square gadget with many points; horizontal links between the gadgets (the edges of the original graph) are made using pairs of points on distinct rows, vertical links using pair of points on distinct columns. Node traversals are forced using the "many points" of the square gadgets.

The node gadget is represented in the following figure:

It has 3 "interface points" $[W,N,E]$ (on distinct columns/rows), and an inner border of $C \times C$ points. A polyline that traverses the gadget from one interface point to another can have a number of corners that is proportional to $C$ (three traversals of the gadget are shown in the figure), in particular the number of corner points is between $2C$ and $2C+2$ (the total number of points of the gadget is $C \times C - 4 + 6$).
The gadget can be rotated to get other interface point combinations ($[N,E,S]$, $[E,S,W]$, $[S,W,N]$).

Now we can shift the planar grid graph in such a way that for every pair of nodes $(x_1,y_1), (x_2,y_2)$, $x_1 \neq x_2$ and $y1 \neq y_2$. See the following figure of a simple $4 \times 3$ grid. Next, we can scale the graph and replace each node with the gadget above. At this stage each gadget is "isolated": a polyline cannot go from one gadget to another.

Now we can simulate the edges of the original graph using pairs of points on the bottom or on the right, each pair on a separate row or on a separate column; see the following figure for two adjacent nodes linked horizontally (in a new bottom row two points are added one on the same column of interface point $E$ of the first gadget, the other on the same column of interface point $W$ of the second gadget).

On every gadget there can be max $4 + 2C$ corner points (1 generated by the enter interface point, 1 generated by the exit interface point, 2 generated by the extra turn on straight traversals and 2C on the inner zig-zag), the points used for the edges can generate max $2e$ corner points.

Suppose that the original graph has $n$ nodes and $e$ edges, if we pick $C > (4n+2e)$, and $k = 2Cn$ as the number of corner points that must be used, then we force the "hidden" polygon of the puzzle to traverse every gadget; but every gadget can be entered/exited exactly once (through a pair of interface cells); so the problem has a solution if and only if the original grid graph has an Hamiltonian path.


Algorithm for finding smallest set and instanciation for a given constraint system I have a system of constraints described by a set of clauses of the form
$x_1 \neq x_2 \lor \dots \lor x_{i-1} \neq x_i$, for instance:

x1 != x2
x3 != x4 or x5 != x6

and I need to find the smallest set $A$ such that $x_1, \dots x_n \in A$, and of course an instanciation of those variables.

Note that I'm not working with numbers, so I don't have any other sorts of inequalities (like $x_i \leq x_j$, etc.), only $x_i \neq x_j$.

Has this problem a name ? Is there a specific algorithm for this problem ?

I was planning to use a SMT solver for this, replacing $A$ by $\mathbb{N}$ and adding the constraint $\forall i, x_i \leq k$ while minimizing $k$. This works fine but I feel like it's a bit too much.

Thanks for your help!

Your problem is at least as hard as SAT: given a CNF formula $\varphi$ on variables $x_1,\dots,x_n$, add variables $x_{\bot},x_{\top}$ and the clause $x_{\bot} \ne x_{\top}$, and translate each occurrence of the literal $x_i$ in $\varphi$  to $x_i \ne x_\bot$ and each occurrence of the literal $\overline{x_i}$ to $x_i \ne x_\top$.  In this way each clause of $\varphi$ can be translated into a constraint of your form.  Then $\varphi$ is satisfiable iff the resulting set of constraints can be satisfied by a set $A$ of size 2 (i.e., $|A|=2$).  Therefore, if we could solve your problem, we could solve SAT.  So your problem is at least as hard as SAT.

Consequently, solving your problem by bit-blasting to SAT is a reasonable way to solve your problem.  I don't think you should expect a much better algorithm.

This does leave some room for cleverness in how you encode your problem as a SAT instance.  You could encode each $x_i$ either with a one-hot encoding (using $nk$ bits), or in binary (with $n\lceil \lg k \rceil$ bits), or by encoding which pairs of $x$'s are equal (with ${n \choose 2}$ bits, i.e., a boolean variable for each $i,j$ encoding whether $x_i = x_j$, with transitivity constraints enforced).  Which you choose is likely to affect the running time in practice.  I suggest experimenting a bit with different possible ways of encoding your problem as SAT to see what seems to work best for the types of problems you are dealing with.  (I don't particularly expect a SMT solver to do any better than a SAT solver here, but you could try it.)


Algorithms for tree rotation What is the fastest known algorithm(s) for finding a minimal sequence of tree rotations that transform given trees $A$ to $B$ (each with $n$ unlabeled nodes)? Equivalently, how can we find a shortest path between two elements in the Tamari lattice? Since Wikipedia lists the problem of finding the length of such a path as not known to be in polynomial time, presumably the best known algorithm is $O(c^n)$.

As a rough attempt at an upper bound, the Tamari lattice has $C_n$ nodes (Catalan's number), and by its definition each has degree $n-1$ (for the rotations of each of its internal nodes), while the diameter of the graph is at most $2n-2$, so an algorithm of Johnson 1982 for shortest paths yields an $O(C_nn\log\log n)$, or $4^{n-o(n)}$ upper bound.

(I would also be interested to know about polynomial time algorithms that find approximate solutions, for example with length $\le c\ell$ where $\ell$ is the shortest path.)

It's fixed-parameter tractable in the natural parameter, the distance. So if two trees have distance $k$ you can find the distance in time polynomial + $f(k)$ for some function $f$. The proof is a kernelization that produces a kernel of size $O(k)$ so putting that together with the naive method of finding a shortest path in the flip graph gives time singly exponential in $k$. See "Rotation distance is fixed-parameter tractable", Cleary & St. John, Inf. Proc. Lett. 2009, and "An improved kernel size for rotation distance in binary trees", Lucas, Inf. Proc. Lett. 2010. See also "A linear-time approximation for rotation distance", Cleary & St. John, JGAA 2010.


Is predicting (in the limit) computable sequences as hard as a dominating function? Define a "predicting oracle" to be an oracle that does as described in this question.

default (weak) version:

Is it the case that, for every predicting oracle $O$, there exists an

oracle machine $M$ such that when $M$ operates on $O$, the result

computes a function that dominates all (ordinarily) computable functions?

uniform (strong) version:

Does there exist an oracle machine $M$ such that for every predicting oracle $O$, when $M$ operates on $O$, the result computes a function that dominates all (ordinarily) computable functions?

The uniform version is theorem 7 of the paper "Inductive inference and unsolvability" by Adleman and M. Blum. The result is for Gold's model of learnability in the limit (the oracle, instead of predicting the next bit, gives you an index of a program that computes the sequence you are trying to discover). Both models are equivalent.

The idea behind the proof is that, for every total computable function $h$ there is a total computable function $g$ whose running time dominates $h$. So, you use the oracle to, on input x, find the greatest of the running time of all functions inferable from a prefix of length $x$. In order not to run forever, you stop counting the steps of the function predicted by the oracle if you find that it will change its prediction when a finite number of 0s are appended to the prefix (this eventually happens because the oracle has to predict every finite variation of the constantly 0 function). The trick is that for every $h$ and every sufficiently large $z$, the output is at least as big as the number of steps to compute $g(z)$, for the respective $g$.


Question about discarding the second register in the standard approach of hidden subgroup algorithm My questions:

What does discarding the second register mean for the standard approach of hidden subgroup algorithm?
Why does discarding  let the first register end up in a mixed state?

My understanding so far:

I am trying to understand the effect of discarding the second register in the standard approach of hidden subgroup algorithm using this paper as resource. I will be using $S_5$ as my group of interest.

It is said in the paper that,

I assume $f$ maps $g$ to it's irrep. So, if we take the case of $S_5$, assuming an automorphism group of a $5$-node graph is hidden inside $S_5$, $|G| = |S_5| = 120$. Both $|g\rangle$ and $|f(g)\rangle$ are $120$ element column vectors.

So, when it is said that the second register is discarded what it actually means? Let's take the case of trapped ion qubits. When we say we discard the second register, does it mean that we will not do any unitary transformation or measurement on them anymore but they will always be there? In the Wikipedia page of Simon's problem the second register is measured.

I also don't understand why discarding (whatever it means) will let the first register end up in a mixed state. Shouldn't it be in a pure quantum state?

Discarding in this context can be carried out by performing a Partial Trace. The system you're interested in is that of the first register. If you want to know only its state, as opposed to the combined state of the two registers, then you take the density matrix of the whole system and trace out the second register.  The resultant state will, in this case, be mixed.  What you're seeing at work is more or less purification in reverse. The resultant mixed state is the reduced state of some other pure system, namely the system comprised of the two registers.


Data structure for dynamic memory allocation Think of the cell-probe model.  Is there a data structure that can allocate contiguous chunks of memory of any length (like e.g. malloc in C), and free them, while avoiding memory segmentation, and executes every operation in worst-case deterministic O(log n) time where n is the total size of the memory?

By avoiding memory segmentation I mean that if the total number of free cells is F, then I should be able to allocate a contiguous segment of F cells or about F cells.

Even without the time bound, it is impossible to "avoid memory segmentation" unless you can move the allocated objects around, like in a compacting garbage collector. See Robson's "Bounds for Some Functions Concerning Dynamic Storage Allocation", which shows that allocating $m$ bytes in blocks of size between $n$ and $N$ requires $\Omega(m \log (N/n))$ bytes of memory.

Additionally, the buddy system achieves this bound and can be done in logarithmic time.


What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes? I guess it would be called #P-Space but I have found only one article vaguely mentioning it. How about the counting version of EXP-TIME-Complete, NEXP-Complete as well as EXP-SPACE-Complete problems? Is there any previous work that can one cite in regards to this or any type of inclusion or exclusion like Toda's Theorem?

The number of satisfying assignments to a boolean formula equals the number of valid quantifications of the formula.  The inductive proof is quite elegant. So #P = #PSpace.


Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem Question

  Suppose that there exist a deterministic algorithm for solving a #P-complete problem in time $O^*(2^{n / \log(n \log n)})$. What would be the theoretical consequences of such a fact? Would it disprove the ETH (Exponential Time Hypothesis)?

Solving any old $\# P$-complete problem in $2^{O(n/\log n)}$ time would not necessarily have interesting consequences. In fact there are some $\# P$-complete problems, like counting the number of minimum vertex covers in a planar graph, which can already be done in $2^{O(n^{1/2})}$ time where $n$ is the number of vertices. (Recall that for planar graphs, the number of edges is linear in the number of vertices, so this is truly a subexponential algorithm.)

Added after Walter's recent comment: I should say that there are several $\# P$ problems which are believed to require $2^{\Omega(n)}$ time (such as counting the number of satisfying assignments to a 3-CNF formula), and the time complexities of these problems are closely related: a $2^{o(n)}$-time algorithm for one of them would imply $2^{o(n)}$-time algorithms for all of them. Some recent work in this direction can be found here. I am not 100% certain, but an $2^{O(n/\log n)}$-time algorithm for counting vertex covers in 3-regular graphs may have interesting consequences along these lines.


How to find the exact period of Blum-Blum-Shub random number generator? I've read the original paper and some related ones. But the best I can find about the period of BBS is that the period is a factor of $λ(λ(M))$, where $λ$ is Carmichael function and $M$ is the product of two large primes that are congruent to 3 (mod 4).

Is there any way to determine the exact period of BBS?

You can determine the period reasonably easily if you know the factorization of $M$ as $pq$, the factorization of $(p-1)\cdot (q-1)$ and the factorization of $\ell-1$ for any prime $\ell$ that divides $(p-1)\cdot (q-1)$.

This requires two steps, first find the order of $x_0$ modulo $M$. Since this divides $(p-1)\cdot (q-1)$ whose factorization is known, this is standard. Let $L$ denote this order, the period of BBS is the order of $2$ modulo $L$ and you can compute it in the same way as we computed $L$.


Dual/complement of independence system An independence system is a pair $(I,\mathcal{I})$ where $I$ is a (usually finite) ground set and $\mathcal{I}$ is a collection of subsets of $I$ such that:

$\emptyset \in \mathcal{I}$, and
$I_1 \subset I_2 \in \mathcal{I}$ implies $I_1 \in \mathcal{I}$.

I am interested a related, dual notion, where we replace conditions 1 and 2 with:

$I \in \mathcal{I}$, and
$I_1 \supset I_2 \in \mathcal{I}$ implies $I_1 \in \mathcal{I}$.

It is clear that the pair $M=(I,\mathcal{I})$ is an independence system if and only if $\overline{M}=(I,\overline{\mathcal{I}})$ obeys the new conditions, where $\overline{\mathcal{I}} = \{ I\setminus I_0 : I_0 \in \mathcal{I} \}$. However, in my application it is much easier to work with the new conditions. Does this have a name?

The usual terms I know from the theory of posets and lattices are downset and upset (or upper set). Also as the empty set is a subset of every set, I think your first condition is vacuous as long as the system is not empty. Same for the first condition in the second definition.

If a downset is closed under joins (in your case set unions), it is called an ideal. If an upset is closed under meets (in your case set intersections), it is called a filter.


State of the art on approximating quadratic assignment problem I was wondering what is the state of the art on approximating the quadratic assignment problem (QAP). In particular, I am interested in the following instance. Suppose the $A = (a_{ij}) \in \{0,1\}^{n \times n}$ is the adjacency matrix of an undirected graph. Let $B = (b_{\ell k}) \in \mathbb{R}^{K \times K}$ and $\pi : [n] \to [K]$ be a map. (We might put some restriction on $\pi$ too, for example, equal number of nodes being mapped to each element of $[K]$.) We would like to solve
$$
\arg \max_{\pi} \sum_{ij} a_{ij} b_{\pi(i),\pi(j)}
$$
A more specific questions is this: what is known about semi-definite programming relaxations (SDP) of this problem? Are there ones which do not significantly increase the dimension of the problem? Any review papers on recent advancements?

See the following paper. There may have been other developments since then.

Maximum Quadratic Assignment Problem,
Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko,
ICALP 2010

http://www.cs.princeton.edu/~kmakaryc/pdf/maxqap.pdf


Best sources for communication complexity What are some of the best sources (books and papers) to motivate and learn communication complexity on its own and in connection with its relation to computational complexity theory?

Books:

Eyal Kushilevitz and Noam Nisan, "Communication Complexity", 2006.
Stasys Jukna, "Boolean Function Complexity: Advances and Frontiers", 2012. (Part II of the book is dedicated to Communication Complexity.)

Articles:

Alexander Razborov, "Communication Complexity".

Lecture Notes:

Toni Pitassi, "Communication Complexity, Information Complexity and Applications", 2012
Ran Raz, "Circuit Complexity and Communication Complexity".

Also check Sasha's remarks about communication complexity.


Closure of Recognizable Languages under Kleene Star: Algebraic Proof? Let $Rec(\Sigma)$ be the class of languages over $\Sigma^*$ recognizable by finite monoids.

To show that $Rec(\Sigma)$ is closed under Kleene star, one would usually refer to the equivalence of recognizable and regular languages and invoke Kleene's theorem. Can anyone think of a direct algebraic proof of this closure property on the level of monoids?

For a pointer on concatenation-like operations (including Kleene star) and their impact on the algebraic structure, you can look to Schützenberger products (see here [1] for instance).

[1] Pin, Jean-Éric. "Theme and variations on the concatenation product." International Conference on Algebraic Informatics. Springer, Berlin, Heidelberg, 2011, https://www.irif.fr/~jep/PDF/ThemeVariations.pdf


Recovering a rank-one matrix from its eigendecomposition after randomized rounding Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ with probability } A_{ij} \\ 0 & \mbox{ with probability } 1-A_{ij} \end{cases} $$

Is it possible to recover $x$ by looking at the principal eigenvector of $A_{\rm rounded}$? In other words, suppose $v$ is the principal eigenvector of $A$; is it true that, after rescaling $v$ and $x$ to have unit norm, the two vectors are nearly the same? In particular, can one show that $P( || \frac{x}{||x||_2} - \frac{v}{||v||_{2}} ||_{\infty} \geq \epsilon)$ goes to zero for any $\epsilon > 0$ as $n \rightarrow \infty$?

I wrote a quick MATLAB simulation that suggests the answer is yes. Here is my code:

  n=20000; %matrix size

  %generate matrix;

  x = rand(n,1);

  y = rand(n,1);

  A = x*y';

  %generate rounded matrix

  B = zeros(n,n);

  for i=1:n

for j =1:n

    if rand>A(i,j)

        B(i,j)=0;

    else

        B(i,j) =1;

    end

end

  end

  %eigendecomposition of B

  [v,d]=eig(B);

  %figure out the index of the principal eigenvector;

  m = max(abs(d));

  mm = max(m);

  i = find(m==mm);

  %compare principal eigenvector to true answer

  y = v(:,i)/norm(v(:,i)) - x/norm(x);

  norm(y,inf)

Running this code with matrix size of 20,000 took me a few hours and returned $|| v/||v||_2 - x/||x||_2 ||_{\infty} \approx 0.02$, suggesting that the answer is positive. Since the answer is likely yes, is this something that is present in the literature? And is there a simple argument to see that recovery is possible, in this or a related model?

(I previously asked this question on MO without receiving an answer.)

I think that, as the question is currently formulated, the answer is no.

Here is a proposed counterexample. Fix arbitrarily large $n$.  Take $xy^T$ to be the matrix having each coordinate equal to $\delta/n$, for a sufficiently small constant $\delta>0$ (so $x$ is uniform). $A$ is then a random matrix where each entry is $1$ with probability $\delta/n$ and otherwise zero.

Here is a proof that this is indeed a counterexample to the conjecture in the post.

Lemma 1. With probability $\Omega(\delta)$, $A$ has a dominant eigenvector $v'$ such that $$\Big\|\frac{x}{\|x\|_2} - \frac{v'}{\|v'\|_2}\Big\|_\infty = \Big|\frac{1}{\sqrt n} - 1\Big| \approx 1.$$

Proof. Consider the directed graph $G=(V,E)$ with adjacency matrix $A$, that is $V=\{1,\ldots,n\}$ and $E=\{(i,j) : A_{ij} = 1\}$.  So $G$ is a random digraph where each possible edge (including self-loops) is independently present with probability $\delta/n$.

Let $X$ be the event that $G$ has a directed cycle of length 2 or more.  By the naive union bound, the probability that there is such a cycle is less than $\sum_{\ell\ge 2} n^\ell (\delta/n)^\ell = \sum_{\ell\ge 2} \delta^\ell = \delta^2/(1-\delta)$.

Let $Y$ be the event that $G$ has at least one vertex $i$ with a self-loop but no other outgoing edges.  (That is, $A_{ii}=1$ and every other entry in row $i$ is zero.)  By calculation, event $Y$ happens with probability about $1-e^{-\delta/e^\delta} = \Omega(\delta)$.

So the probability that $Y$ happens and $X$ does not is $\Omega(\delta) - O(\delta^2) = \Omega(\delta)$.
Assume that $Y$ happens and $X$ does not.  Because $Y$ happens, there is a row $i$ of $A$ where $A_{ii} =1$ but all other entries are zero.  So $A$ has an eigenvector $v'$ where $v'_{i} = 1$ is the only non-zero entry.  But $x_i/\|x\|_2 = 1/\sqrt n$, so, for this eigenvector,
$$\Big\|\frac{x}{\|x\|_2} - \frac{v'}{\|v'\|_2}\Big\|_\infty = \Big|\frac{1}{\sqrt n} - 1\Big| \approx 1.$$

To finish, we show that $v'$ is a dominant eigenvector, that is, that the largest eigenvalue of $A$ is 1.  Consider any eigenvector $v$.  Let $\lambda$ be the eigenvalue of $v$, so $Av = \lambda v$.  Let $C=\{i : v_i > 0\}$ be the support of $v$.  Consider the subgraph $G_C$ induced by $C$ (as a set of vertices in $G$).  Since $X$ does not happen, $G_C$ has no cycle of length 2 or more, so each strongly connected component of $G_C$ is a single vertex.  Hence, $G_C$ contains a single vertex $i$ having no incoming edges in $G_C$, except possibly a self-loop.  Now, because $v$ is an eigenvector with support $C$, this implies $A_{ii} v_i = \lambda v_i$.  Since $v_i>0$ this implies $\lambda =A_{ii} \in\{0, 1\}$. $~~\Box$

I think that the above argument suggests that $G$ can have multiple dominant eigenvectors (each with eigenvalue 1), and that some of those eigenvectors could have larger support --- size $\Omega(\log n)$, maybe? And such an eigenvector $v$ could have $\max_i v_i/\|v\|_2 = O(1/\log n)$, and so could meet the proposed condition for being "the same" as $x$.  But see Remark 1 below.

Remark 1. The condition currently suggested in the post for $x$ and $v$ to be "the same", namely,
$$\Big\|\frac{x}{\|x\|_2} - \frac{v}{\|v\|_2}\Big\|_\infty \le \epsilon,$$
seems to be too weak. It can only be violated if $x$ or $v$ has at least one very large coordinate.

For example, suppose the first $n/2$ coordinates of $x$ are 1 and the rest are zero, while the first $n/2$ coordinates of $v$ are zero, and the rest are 1.  Then $x$ and $v$ are orthogonal, so arguably not at all "the same".  But $x_i/\|x\|_2 \le \sqrt{2/n}$ and $v_i/\|v\|_2 \le \sqrt{2/n}$, so, assuming $n \ge 2/\epsilon^2$, the suggested condition is satisfied.

Of course, if the condition were strengthened, the counterexample above should still hold...

Remark 2. Tangentially, the behavior of eigenvectors of sparse random graphs (where the edge probability is around $1/n$ or so), seems to be fairly complicated.  Among the references I found, the most relevant to the argument was [1].  It considers the case when $\delta$ is just below 1, and shows that each strongly connected component of $G$ is either a single vertex or a cycle of constant size (possibly with self-loops).

The case when the edge probability is slightly larger, above $\log(n)/n$, say, seems to be more well studied, and in that case I think (although I'm not sure) that the eigenvectors of $G$ are more uniform.  Search Google Scholar for "eigenvectors of sparse random graphs".

[1]  Luczak, T. and Seierstad, T. G.. The critical behavior of random digraphs. Random Structures and Algorithms 35, 271-293 (2009).
http://folk.uio.no/taralgs/artikler/digraph.pdf


Is education for research-based CS at odds with that of industrial CS? I'm an undergraduate strongly interested (well, this is a hunch) in theoretical CS and all things mathematical. While I'd like to devote my time to participating in research opportunities and learning more about academia-related CS, I also want to develop a skillset (in software engineering) that, if I were unsuccessful in entering academia, would give me a fallback.

I suspect that the past an early point, the learning routes for academia-CS and industrial CS diverge, meaning that I can't prepare myself for both. To what extent is this true  -- everybody needs to have experience in a couple of programming languages, for example, but that aside, are there commonalities or differences between preparing for academia and industry that bar or support my plan? Is what I want feasible and, if so, how? Many Thanks.

I struggled with the same question while pursuing my undergrad in CS. I performed a fair amount of research, but currently work as a software engineer. I can tell you that for the most part, you won't do too much theoretical CS in the industry (assuming a typical SE, not something tailored for R&D or the like). You may want to consider looking into R&D positions after graduating, should you decide not to pursue a career in academia.

The learning routes do definitely differ (although this is university-specific), but the principles learned can be used in either setting. Certain classes (Compilers, Automata Theory, etc.) may not seem like they have a place in the typical industry for software engineers, but you'd be surprised just how much they come into play.

The biggest difference that you should be prepped for is the difference in "soft" classes. Software engineers are often expected to interface directly with customers, nontechnical managers, and the like, while researchers/professors generally rub shoulders with their own kind in the workplace. As a SE, you get a lot more face time than many CS people are prepared for.