When a type is a value? In functional programming and in the theoretical setting of the $\lambda$-calculus it is standard to consider a lambda abstraction $\lambda x.M$ as a value. In my understanding, the intuitive reason is that a function $\lambda x.M$ is an finished piece of data, sharing with other values like $3$ or $\mathtt{true}$ the following ontological status:  something that one can handle independently of a notion of execution. (Indeed, you cannot execute $\lambda x.M$ until you apply it to something. Of course you may reduce a $\beta$-redex in $M$, but then intuitively you are not reducing the whole piece of code $\lambda x.M$.)

Now, when it comes to dependent type theories, or more generally any type system having some vertex of Barendregt's cube as its core, all levels of the syntax - objects, types, kinds and possibly all the infinite higher kinds - have the status of terms. So it makes sense to ask when one of them is a value. Let us ask the question for types, but of course the same applies to all possible superior kinds.

Obviously a functional type $\lambda x: T. T' : \Pi x: T.A $ (for $A: \mathtt{Kind}$ and $T:\mathtt{Type}$) is a value. (Notice that in basic dependent type theory, the one without the higher-dimensional kinds $\omega$, the kind $\Pi x: T.A$
 is actually $T\to A$).

Now, what about the universal type $\Pi x: T.T'$ (where $T,T': \mathtt{Types}$) ? From a mathematical perspective it is a family, hence a function. It corresponds to my definition of ontology of a value above: something that one can handle independently of a notion of execution.
But on the other side $\Pi x: T.T'$  has a relevant difference from $\lambda x: T. T' $: the latter has a destruction operator (the application), whereas the former does not. In light of this, would you consider $\Pi x: T.T'$ as a value?

In a way, I am asking the following (philosophical?) question. Which intuition do you prefer:

a value is something that one can handle independently of a notion of execution
a value is something that one can handle independently of a notion of execution and when it is not ground can be decomposed via an appropriate operator.

In case 2  the "dependent arrow" type $\Pi x: T.T'$ is not a value, only the functional type $\lambda x: T. T'$ and the polymorphic universal type $\forall X.T$ are.

I am personally inclined towards option 2, but I would like to hear from more experienced researchers.

I will offer a semantic perspective. The relationship between values and general computations may be expressed in terms of an adjunction between two categories:
\begin{align*}
F &: \mathcal{V} \to \mathcal{C} \\
U &: \mathcal{C} \to \mathcal{V} \\
F &\vdash U
\end{align*}
Here $\mathcal{V}$ is a category of values, $\mathcal{C}$ is a category of computations. The prototypical example comes from domain theory:

$\mathcal{V}$ is the category of predomains, i.e., $\omega$-chain complete posets which may not have a list element,
$\mathcal{C}$ is the category of domains, i.e., $\omega$-chain complete posets with a least element,
$F$ is the lifting functor
$U$ is the forgetful functor

This view is closely related to Paul Levy's call-by-push-value (CBPV).

The semantic picture suggests that we should not only distinguish values and computations, but also value types and computations types. Thus, instead of saying that there are terms of type $A$, some of which are values and others are computations, we say instead that there are two kinds of types: the elements of value types are always values, while the elements of computation types are always computations.

In CBPV languages the distinction is explicit. For instance $\mathtt{nat}$ is a value type and $42 : \mathtt{nat}$ while $F \mathtt{nat}$ is a computation type inhabited by computations such as $\mathtt{return}\;42$ and $(\lambda n . n \cdot n + 6) \; 6$.

From a theoretical point of view such a typing discipline is desirable, because the value/computation distinction becomes a proper mathematical concept, rather than a syntactic device that drives normalization algorithms. (I warned you that I will offer the semantic perspective.)

We may think about the distinction between values and computations for dependent types and other corners of Barndregt's cube. The semantic picture suggests that we should again distinguish value types from computation types. Thus, we really should replace the judgement $\Gamma \vdash A \ \mathrm{type}$ ($A$ is a type in context $\Gamma$) with two judgements:

$\Gamma \vdash A \ \mathrm{vtype}$
$\Gamma \vdash C \ \mathrm{ctype}$

Of course, the next step requires us to figure out precisely how to extend the above picture to the rather more complicated situation that arises through dependencies. This is a topic of current research, and a great deal of past research.

Now, as to whether something like $(\lambda T .  \mathrm{return}\,T) (\prod_{x : A} B(x))$ itself is a value or a computation can be phrased in terms of universes. There ought to be a universe of value types $\mathcal{U}_V$ and a universe of computations $\mathcal{U}_C$, each reflecting the two kinds of judgements above. We also have to decide whether $\mathcal{U}_V$ and $\mathcal{U}_C$ themselves are value or computation types (probably value types, with corresponding computation types $F \mathcal{U}_V$ and $F \mathcal{U}_C$). The typing rules would place $(\lambda T .  T) (\prod_{x : A} B(x))$ into one or the other universe (presumably in this case the universe of computations).

I do not really want to give a definitive answer here, I just want to place the question into a proper mathematical context that allows us to consider the mathematical possibilities rather than look for an answer based on experience with normalizing algorithms.


Minimize makespan on identical machines when jobs are vectors Given are $n$ $d$-dimensional vectors and $m$ machines where $d$ need not be fixed. The objective is to minimize the makespan i.e., assign the vectors to machines such that the maximum of the component-wise sum is minimized over all machines.

I would like to know is there any constant factor approximation algorithm for this problem and is there a generalization of list scheduling to this problem, if so what is its worst-case ratio?

This is the Vector Scheduling (VS) problem. Unless P = NP, VS admits no constant factor approximation algorithm when $d$ is part of the input:

Chekuri, C., Khanna, S.: On multidimensional packing problems.
SIAM J. Comput., 33(4):837-851, 2004.

The same paper gives a polynomial-time approximation scheme when $d$ is not part of the input, and a polynomial time $O((\log d)^2)$ approximation when $d$ is part of the input. The latter was improved to $O(\log d)$ by Meyerson, Roytman and Tagiku (APPROX 2013). For more references and recent results you can refer to:

Bansal, N., Vredeveld, T., van der Zwaan, R.: Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. Lecture Notes in Computer Science, 8392:47-59, 2014.


In external memory, is grouping equal elements easier than sorting? Sorting an array will put equal elements adjacent to each other. So, in no model of computation can grouping equal elements be harder than sorting. In the RAM model, grouping equal elements is $O(n)$ because you can accomplish it by putting everything into a hashmap that maps keys to lists of equal elements.

The external memory model of computation is one where for an input size $N$ that's stored in "external memory," you can fit $M$ elements inside cache, and can transfer $B$ elements from cache to external memory per one slow I/O operation. All computation has to be done in cache.

The fastest sort in external memory is generally accepted to be an $O(N \log N)$ mergesort, even when the position in the output can be computed directly from the keys without any comparison. A surprising result shown in [1] is that, for practical[2] values of $B$ and $M$, permuting the values in external memory based on indices that are already known is no faster than sorting them! (This is in sharp contrast to permutation in RAM, which is trivially $O(n)$.)

I think grouping equal elements might be easier than permuting, because there are many permutations that would group equal elements. In a sense, if there is one "easy permutation" that groups equal elements, the algorithm could give you that instead of being forced to give you a specific permutation that may be very hard. Is this so? If it is so, what algorithm is known that could do it?

[1] https://pdfs.semanticscholar.org/05f5/c5521c69a87ed2fc32521312d85aeb1da874.pdf

[2] This is actually not true for big (>4KB) elements on solid state drives, but it's commonly repeated and valid for many cases.

Even testing whether $n$ elements are distinct is known to require $\Omega(n \log n)$ time on a model with some pretty reasonable restrictions.  See, for example,
Anna Lubiw, András Rácz:
A Lower Bound for the Integer Element Distinctness Problem. Inf. Comput. 94(1): 83-92 (1991).


correlation in an almost independent set of random variables Suppose I have a set of $n$ binary random variables $X_1, \ldots, X_n$ that sit on a line, and assume that $\Pr(X_i=0)=\delta$ for all $i$. In addition, assume that any two subsets of variables that are separated by at least one site are completely independent. For example:
$P(X_1, X_2, X_4, X_7) = P(X_1,X_2)\cdot P(X_4, X_7) = P(X_1,X_2)\cdot P(X_4)\cdot P(X_7)$.

In other words, whenever we look at a multi-variable dist', we can "break" it into blocks of contiguous variables.

Finally, assume that for any subset of $k<n$ variables, $\{X_{i_1}, \ldots, X_{i_k}\}$, we have $\Pr(X_{i_1}=X_{i_2}=\ldots=X_{i_k}=0) > 0$.

In that case, can I find a lower bound on $P_n\equiv \Pr(X_1=X_2=\ldots=X_n=0)$ ?

In particular, I would like to know, if there is a threshold $\delta_0$, such that for every $\delta>\delta_0)$, it must be that also $P_n>0$, and how this threshold depends on $n$.

A simple use of Lovaz local lemma says that if $\delta>7/8$ then indeed $P_n>0$. But I think that it can be improved. For example, for $n=3$, a direct calculation shows that for $n=3$, it is impossible that $P_3=0$ unless $\delta < (\sqrt{5}-1)/2 \simeq 0.61$.

Can you think of any method to attack this problem?

I think Yury's beautiful example actually answers my question. It shows that $\delta_0$ does not go to 0 as $n\to \infty$. One can probably also use a similar construction to show that the same holds for any $\delta<1/2$.

Thanks Yury!


Sub-exponential algorithm for Hamiltonian cycle problem on cubic planar graphs? There are several graph $NP$-complete problems that have sub-exponential time algorithm on planar graph instances.

What is the fastest algorithm for HC problem on cubic planar graphs? Is there a sub-exponential algorithm for this class of graphs?

Actually, you don't need to exploit the "Catalan structure" in planar graphs to get a $2^{O(\sqrt{n})}$ time bound as Saeed suggests. Cygan et al. show you how to detect a Hamiltonian Cycle in $\operatorname{poly}(n)4^{\operatorname{tw}(G)}$ time even in general graphs, and in the final version of the paper they also describe how this can be improved to $\operatorname{poly}(n)3^{\operatorname{tw}(G)}$ time in cubic graphs.

The above algorithm is randomized. If you insist on a deterministic one, this is also possible with a slightly larger base constant, see Bodlaender et al.


Neighborly properties in a bipartite graph Input: Let $G$ be a connected, bipartite graph with parts $A$ and $B$, each of size $n$. For a set of vertices $S$, let $N(S)$ be its set of neighbors.
Question: Decide whether there exists a subset $S\subseteq A$ with $\emptyset\ne S\ne A$ such that $|S|=|N(S)|$.
My attempts so far: First some observations. If $a \in A$ has $\deg(a) = 1$, then we are done so it suffices to consider the case where $\deg(a)\ge2$ for all $a\in A$. Further, if we can find a proper subset $S\subseteq A$ such that $|S|\ge|N(S)|$ then we are also done (remove a well chosen vertex of $S$ one at a time). The problem is straight-forward to solve if $G$ is a tree.
Various greedy approaches have been tried and have thus far failed e.g. consider the following counter-example for greedy by smallest degree.

I am beginning to suspect that the problem is NP-hard, but I do not have any good reduction sources (Hamilton Cycle comes to mind, but that uses all the vertices of the graph).

There is a polynomial time algorithm for this problem.
First, as pointed out by D.W., by Hall's theorem we can assume that there is a perfect matching between $A$ and $B$.
In particular, if there is no perfect matching then there is a subset $S$ with $|S| > |N(S)|$, and we can remove vertices from $S$ without affecting $N(S)$ until we get an answer.
Now that we have a perfect matching we also have that $|S| \le |N(S)|$ for any set $S$, so we are looking for a set $S$ with $|S| \ge |N(S)|$.
Consider a version of this problem where we have a special vertex $a_0 \in A$ and we are looking for a set $\emptyset \subsetneq S \subseteq A \setminus \{a_0\}$ with $|S| \ge |N(S)|$. The original problem can be reduced to $|A|$ instances of this problem in polynomial time.
We create a linear program that can be seen as a relaxation of this problem, and prove that this linear program has a feasible solution if and only if the problem has a solution.
The linear program has a variable $X_a \ge 0$ for each vertex $a \in A$ and a variable $X_b \ge 0$ for each vertex $b \in B$.
We require that $\sum_{a \in A} X_a = 1$ and $\sum_{b \in B} X_b = 1$. For each edge $(a, b)$ we require that $X_b \ge X_a$. We also set $X_{a_0} = 0$ for the special vertex $a_0$. This linear program has a feasible solution if we have a solution $S$: for each $a \in S$ set $X_a = 1/|S|$ and for each $b \in N(S)$ set $X_b = 1/|N(S)|$.
Let's prove that if there is a feasible solution to the linear program then we have a solution to the problem.
Take $S$ as the set of vertices $a \in A$ with $X_a > 0$. If $|N(S)| \le |S|$ we are done.
Suppose $|N(S)| > |S|$.
There is a matching from $S$ to a subset $N' \subsetneq N(S)$ because the graph has a perfect matching.
Note that $1 = \sum_{a \in S} X_a \le \sum_{b \in N'} X_b$ because the matching matches each vertex $a \in S$ to a vertex $b \in N'$ with $X_b \ge X_a$.
There is a vertex $b \in (N(S) \setminus N')$ with $X_b > 0$, and therefore $\sum_{b \in N(S)} X_b$ must be greater than $1$, which is a contradiction.


A quantum algorithm for GCD Does anyone know of a direct quantum algorithm for computing GCD, - There could be quantum gates for addition subtraction constructed explicitly, using CNOT, etc. - the construction can be done in some poly(n) of input, (this is just a guess), but is there any algorithm, scheme for computing GCD, using quantum algorithms, gauss sums, QFT, quantum approximation, anything(!!) thanks,

A search for "Quantum GCD" yields a 2013 paper by Saeedi and Markov titled "Quantum Circuits for GCD Computation with O(n \log n) Depth and O(n) Ancillae". It's not mentioned in the title, but the size of the circuit used in their algorithm $O(n^2)$.


Is solving the following system of boolean equations NP-hard? I reduced a problem I'm currently working on to the following system of boolean equations:
$$
X_i \iff
\begin{cases}
\bigvee_{B \in A_i} \bigwedge_{k \in B} X_k \\
true \\
false
\end{cases}
$$
Where $|B|>=1$ for all $B \in A_i$ and each $X_i$ has exactly one of these defining equations.
I need to find $X_i$ that satisfies all these equations ($A_i$ are given). I'm wondering if this problem is NP-hard. I couldn't reduce the general boolean satisfiability problem to it yet.
Ideally, I would find an algorithm to solve this problem in polynomial time. If it's NP-hard I guess I have to hope that SAT solvers can solve it reasonably fast.
Thanks!

Here's an example:
$$
X_1 \iff true \\
X_2 \iff false \\
X_3 \iff X_4 \\
X_4 \iff X_1 \vee (X_2 \wedge X_3)
$$

[Now that the question's been clarified I'll post my previous comment as an answer.]
It's in $\mathsf{P}$. Start with unit propagation. Afterwards, what's left on the right-hand sides will be monotone, so will be satisfied by setting all remaining variables to True.
(If you want to count the number of solutions, on the other hand, that might be harder.)


Computational complexity of the 3-partition problem with distinct numbers This question is related to an answer I posted in response to another question.

The 3-partition problem is the following problem:
Instance: Positive integers a1, …, an, where n=3m and the sum of the n integers is equal to mB, such that each ai satisfies B/4 < ai < B/2.
Question: Can the integers a1, …, an be partitioned into m multisets so that the sum of each multiset is equal to B?

It is well-known that the 3-partition problem is NP-complete in the strong sense that it remains NP-complete even if the numbers in the input are given in unary.  See Garey and Johnson for a proof.

Questions: Does the 3-partition problem remain NP-complete if the numbers a1, …, an are all distinct?  Does it remain NP-complete in the strong sense?

(My feeling is that the answers to both questions are probably yes because I do not see any reason why the problem should become easier if all numbers are distinct.)

It does not seem that the proof in Garey and Johnson establishes the NP-completeness of this restricted version.

In the answer to the other question linked above, I gave a proof that the 6-partition problem (defined analogously) with distinct numbers is NP-complete in the strong sense.

It is proved in [1, Corollary 7], that 3-partition is strongly NP-hard when the integers $a_1, \ldots, a_n$ are all distinct. The bounds $B/4 < a_i < B/2$ are not imposed in [1], but this should not make a difference.

[1]: Heather Hulett, Todd G. Will, Gerhard J. Woeginger: Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. Oper. Res. Lett. 36(5): 594-596 (2008). DOI


Context-free Grammar for a Context-free Language Intersecting a Regular Language (get the Maximum Number of Rules) It is well known that the intersection of $L \cap R$ of a context-free Language $L$ and a regular Language $R$ is context-free. Each proof I have seen constructs a automaton (a PDA) that accepts $L$ and one (a DFA) that accepts $R$. Than a further automaton (a PDA) is constructed that accepts $L \cap R$. This automaton can be converted to a context-free language.

Is there some literature that gives a proof without constructing automatons and constructs a context-free grammar that generates $L \cap R$ directly?

What I want to know actually: Given a context-free Language $L$ and a regular Language $R$. How many rules at most does a context-free grammar need to generate $L \cap R$?

Answer to your first question http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf.

A summary of the proof given in the link. First, it is shown that proving $L \cap R$ is CFL reduces to proving that $L \cap R'$ is CFL, where $R'$ is a regular language recognized by a DFA with exactly one final state. Then from the grammar for L (in Chomsky normal form) and DFA for R' a new grammar for $L \cap R'$ is constructed using a few straightforward rules.


Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise? In Feldman-Gopalan-Khot-Ponnuswami 06 the authors show that agnostically learning parities reduces to learning parities with random classification noise. They also remark (among other things) that learning conjunctions in this model is NP-hard.

Though I can't remember the source right now, I also recall that a random projection argument gives a reduction from learning parities with malicious noise to learning parities with uniform random noise.

Is there a reduction from learning conjunctions with malicious noise to learning conjunctions with random noise?

Let me clarify the question a bit first:
Agnostic learning conjunctions is known to be NP-hard only if the learner needs to be proper (output a conjunctions as a hypothesis) and work for any input distribution. The reductions in FGKP06 are for the uniform distribution and to the best of my knowledge there is no similar result for general distributions.
But in either case the answer to your question is "no" (in the sense that such a reduction is not known and unlikely to exist).
Learning conjunctions with random (classification) noise is an easy problem that was solved in a paper of Anguin and Laird "Learning From Noisy Examples" from 1988 that introduced the model of random noise (see also Kearns 1993 paper on Statistical Queries)
Learning conjunctions with malicious noise is at least as hard as agnostic learning of conjunctions which is believed to be a hard problem (even over the uniform distribution it is at least as hard as learning log-n sparse parities with noise)


Complexity to calculate a full set of eigenvectors over a finite field Let a full rank $n\times n$ matrix ${\bf A}$ with elements over $\mathbb{GF}(2)$. What is the worst case complexity to calculate $n$ linearly independent (over $\mathbb{GF}(2)$) vectors, such that each one of them obeys $${\bf A}{\bf x} = {\bf x}$$ again over $\mathbb{GF}(2)$.

There will generally not exist a set of $n$ linearly independent vectors $x$ such that $Ax = x$; this can only happen for $A$ being the identity matrix. On the other extreme, there may be no such vectors at all. For example, the matrix
$$
A = \left(\begin{array}{cc} 0 & 1\\ 1 & 1 \end{array}\right)
$$
has full rank, but there are no nonzero vectors $x$ such that $Ax = x$. This is consistent with the fact that the characteristic polynomial of $A$ is $\lambda^2 + \lambda + 1$, which is irreducible over GF(2).

If you want to find the maximum number $k$ of linearly independent vectors $x$ such that $Ax=x$, compute the nullspace of $A - I$. This can be done using Gaussian elimination in time $O(n^3)$. Several other algorithms for this task also exist, and are described in textbooks on computational linear algebra.


Approximately counting paths and cycles in a graph Counting cycles, and paths in graphs is a hard problem, see questions  here, and related question for cycles for a given length $k$,  here. The question is about the approximability of these graph problems, are they easily approximatable? Or do they have more fundamental implications for $NP$ complete problems, or #$P$ counting problems, hardness or otherwise. Any #$P$ hardness for approximately counting paths and cycles(from uniform distributions, or not) would imply, gaps between actually generating cycles paths(approximately) and enumerating the number of paths, and cycles. Also, what can be said about the  $APX$ hardness implications under reasonable hardness reduction assumptions($L$-hardness, others)?

Approximately counting all paths (or cycles) in polynomial time implies NP=RP. There is a very simple reduction to amplify the weight of the longest path/cycle. See https://doi.org/10.1016/0304-3975(86)90174-X, section 5.


SAT variant with almost disjoint clauses I'm wondering whether the following SAT variant is NP-complete or polynomial.
The formula given in input has n*m variables, and it has two parts.

A part with the n positive clauses:
$$(x_{1,1} \lor \dots \lor x_{1,m}) \land \\\dots\\(x_{n,1} \lor \dots \lor x_{n,m})$$

And a part with negative clauses with two variables:
$$ \neg x_{i,j} \lor \neg x_{k,l} $$ where $x_{i,j}$ and $x_{k,l}$ are part of the n*m variables mentioned above.

Thank you for the help

I don't know the Multicolored Clique Problem suggested by Daniello, however there is a simple reduction from 3SAT:

Given a 3SAT formula $\varphi$ over $n$ variables $x_1,...,x_n$; for each $x_i$ add two variables:

$y_{i}^T$ that represents $x_i = true$, and
$y_{i}^F$ that represents $x_i = false$

and add the clause $(\neg y_{i}^T \lor \neg y_{i}^F)$ that represents the condition that $x_i$ cannot be both true and false.

Finally replace every clause   $C_j = (l_{j1} \lor l_{j2} \lor l_{j3})$ of $\varphi$ with a clause made of three positive literals $(y_{j1}^a \lor y_{j2}^b \lor y_{j3}^c)$ where:

$a = T$ if $l_{j1}= x_{j1}$, $b=F$ if $l_{j1} = \neg x_{j1}$
$b = T$ if $l_{j2}= x_{j2}$, $b=F$ if $l_{j2} = \neg x_{j2}$
$c = T$ if $l_{j3}= x_{j3}$, $b=F$ if $l_{j3} = \neg x_{j3}$

For example $(x_1 \lor \neg x_2 \lor \neg x_3)$ becomes: $(y_1^T \lor y_2^F \lor y_3^F)$

Update:

In order to make every positive literal $y_i$ (that can be $y_i^T$ or $y_i^F$) occur only once in the upper part, you can use the following technique:

Suppose that $y_i$ occurs twice, then you can simply replace the two occurrences with two new positive variables: $y_i'$ and $y_i''$ and add the conditions for: $y_i' \leftrightarrow y_i''$:

$$(\neg y_i' \lor y_i'') \land (\neg y_i'' \lor y_i')$$

At this point repeat the split procedure ($y_i'$ becomes $y_i^{T'}$ and $\neg y_i'$ becomes $y_i^{F'}$):

$$(\neg y_i^{T'} \lor \neg y_i^{F''}) \land (\neg y_i^{T''} \lor \neg y_i^{F'}) \land (y_i^{T'} \lor y_i^{F'}) \land (y_i^{T''} \lor y_i^{F''}) $$

and add a dum clause to the upper part in order to include the $y_i^{F'}$ and  $y_i^{F''}$, for example: $(y_i^{F'} \lor y_i^{F''} \lor z_i)$, where $z_i$ is a new variable that can make the clause true.

If $y_i$ occurs more than twice the procedure is similar.


What is the probability that a random Boolean function has a trivial automorphism group? Given a Boolean function $f$, we have the automorphism group $Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \}$.

Are there any known bounds on $Pr_f(Aut(f) \neq 1)$? Is there anything known for quantities of the form $Pr_f(G  \leq Aut(f))$ for some group $G$?

Yes. To your first question, the probability goes to zero double-exponentially fast. This can be calculated as follows. For each permutation $\pi$, we can bound the probability that $\pi \in Aut(f)$, i.e. that $f(\pi(x)) = f(x)$ for all $x \in \{0,1\}^n$. Consider the orbits of $\pi$ acting on $\{0,1\}^n$. We have that $\pi$ is an automorphism of $f$ iff $f$ is constant on the $\pi$-orbits. If $\pi$ is nontrivial, it has at least one orbit on $[n]$ that is not a singleton, and therefore at least on orbit on $\{0,1\}^n$ that is not a singleton. Suppose that orbit has $k$ elements in it. The probability that $f$ is constant on that orbit is thus precisely $2^{-(k-1)}$. Suppose that $\pi$ acting on $[n]$ has $c_1$ fixed points, $c_2$ cycles of length 2, etc. (in particular $\sum_{i=1}^n i c_i = n$). Then the number of points of $\{0,1\}^n$ fixed by $\pi$ is precisely $2^{\sum_i c_i}$. All the remaining points of $\{0,1\}^n$ are in nontrivial orbits of $\pi$. To upper bound the probability that $\pi \in Aut(f)$, note that the best possibility is if all the non-fixed elements of $\{0,1\}^n$ come in orbits of size 2. So we get that $Pr(\pi \in Aut(f)) \leq (1/2)^{M/2}$ where $M = 2^n - 2^{\sum_i c_i}$. Now, we want a lower bound on $M$, which means we want an upper bound on $\sum_i c_i$. Since $\pi \neq 1$, the largest $\sum c_i$ can be is when $c_1 = n-2$ and $c_2 = 1$, i.e. $\sum c_i = n-1$ and $M = 2^n - 2^{n-1} = 2^{n-1}$, so $M \geq 2^{n-1}$ and $Pr(\pi \in Aut(f)) \leq (1/2)^{2^{n-2}}$. Now apply the union bound: $|S_n| = n!$, so $Pr((\exists \pi \in S_n)[\pi \neq 1 \text{ and } \pi \in Aut(f)]) \leq n! 2^{-2^{n-2}}$, which is basically $2^{n \lg n - 2^{n-2}} \to 0$ as $n \to \infty$, pretty quickly.

For any given $G \leq S_n$ you could use similar reasoning, but the probability will also go to zero very quickly.


SAT in finite model theory without order It is well known in finite model theory that without an order on the input, the expressivity is very limited. For example it is known that $FO(<,\textit{PFP})$ is equal to  PSPACE, and  $FO(\textit{PFP})$ (without any order in the input) is only PSPACE-relational, a notion defined by Abiteboul and Vianu when they proved their theorem:$FO(\textit{IFP},<)=FO(\textit{PFP},<)$ iff $FO(\textit{IFP})=FO(\textit{PFP})$. (Equivalently P = PSPACE iff P-relational = PSÄCE-relational.)

Relational machines are Turing machines with a finite number of relations. As in a database, a relation is a set of tuples of elements from a finite universe. The machine can check if a relation is empty (if a table is empty), perform Boolean operations over the relations (union, intersection, join, projection), and the usual Turing machine operations. Note that the input of relational machines is given in the relations and not on the tape. It is well known that PSPACE-relational ($FO(\textit{PFP})$) can not even compute parity, hence is less expressive than PSPACE.

One can define queries with relational machines, but one can also define functions, the answer of a function being the content of some relations and of the tape at the end of the computation. Such a machine has the property that if there are two elements $a$ and $b$ of the input such that there is an isomorphism $\phi$ sending  $a$ to $b$ and $b$ to $a$, then it is never possible to distinguish $a$ from $b$. In particular in every relation $R$ of the output, if $R(a,\overline x)$ is true, then $R(b,\phi(\overline x))$ is also.

The reason for this is that the allowed operations (union, intersection, projection and join) all respect the isomorphism. Hence the output respects every isomorphism respected by the input.

In $(a\lor b)\land(\neg a\lor\neg b)$, $a$ and $b$ are symmetric, and the function $\phi$ switching $a$ and $b$ is clearly an isomorphism of the input. Suppose there exists a function to compute satisfying assignments for $3-SAT$ instances, and whose output is $P$ (the set of variables assigned to true in a correct assignment).  Then we would either want to have $P=\{a\}$ or $P=\{b\}$. However, the isomorphism means that $P$ contains either both $a$ and $b$, or neither.

Hence we have proved that there is no PSPACE-relational function that can output an assignment to a 3-SAT instance.

My question is: how do you prove that there is no PSPACE-relational (i.e. $FO(\textit{PFP})$) that accepts only the input which has a satisfying assignment? The question is different, since I don't intend to compute the assignment and I do not ask to see $a$ or $b$ in the output, I just want to see "accept" or "reject. And contrary to the usual world of Turing machines, it is not equivalent to know if an answer exists and to find the answer, because there is no way for us to use our relational machine for the question "is there an answer with $a=true$" because we can not differentiate $a$ from $b$.

The standard method for showing inexpressibility results for FO(PFP) (and for FO(LFP), by the way) is by using the fact that FO(PFP) is embedded in the finite-variable infinitary logic $\mathrm{L}^\omega_{\infty\omega}$. Here $\mathrm{L}^\omega_{\infty\omega}$ is the finite-variable fragment of $\mathrm{L}_{\infty\omega}$, where the latter is the class of (infinitary) formulas build from the atoms by means of negations, finitary or infinitary disjunctions and conjunctions of the type $\bigvee_i \phi_i$ and $\bigwedge_i \phi_i$, and existential and universal quantification. The logic $\mathrm{L}^k_{\infty\omega}$ is the collection of all formulas in $\mathrm{L}_{\infty\omega}$ that involve at most $k$ variables (quantified or not), and $\mathrm{L}^\omega_{\infty\omega} = \bigcup_k \mathrm{L}^k_{\infty\omega}$.

It is known that FO(PFP) $\subseteq \mathrm{L}^\omega_{\infty\omega}$ (see Theorem 7.4.2 in Ebbinghaus and Flum book "Finite Model Theory"). Thus, if you prove that something is not expressible in $\mathrm{L}^k_{\infty\omega}$ for any $k$, then you also prove that it is not expressible in FO(PFP).

Now, how does one prove inexpressibility results for $\mathrm{L}^k_{\infty\omega}$? By playing the $k$-pebble games. These are Ehrenfeucht-Fraissé-type of games where the number of rounds is unbounded but each player has at most $k$ pebbles that he can re-use (see Ebbinghaus and Flum book again for details).

After all this background, now we can show that CNF-SAT is not expressible in $\mathrm{L}^k_{\infty\omega}$ for any $k$. For every fixed $k$, we need to find a satisfiable CNF formula $F_k$ and an unsatisfiable CNF formula $G_k$ such that $F_k \equiv^k_{\infty\omega} G_k$, where $A \equiv^k_{\infty\omega} B$ means that the Duplicator has a winning strategy for winning the $k$-pebble game on the structures $A$ and $B$ (here we need to fix some sensible way of encoding CNF formulas as finite structures: let's say we encode them as their bipartite incidence graph with elements representing clauses on one side, elements representing variables on the other, and 2 types of binary relations indicating which variables appear in which clauses and under what sign). I claim that an explicit choice of $F_k$ and $G_k$ is possible. But instead I will give you an indirect proof.

It is trivial to see that $K_k \equiv^k_{\infty\omega} K_{k+1}$, where $K_a$ denotes the clique-graph on $a$ vertices. In particular EVENNESS is not definable in $\mathrm{L}^\omega_{\infty\omega}$. It is also known that CNF-SAT is NP-complete under first-order reductions (see Theorem 7.16 in Immerman's "Descriptive Complexity" book). Since trivially EVENNESS is in NP, this means that there is a first-order reduction from EVENNESS to CNF-SAT. Since first-order reductions (in pure first-order logic, without built-in linear-order or anything as it is the case in Theorem 7.16 from Immerman's book) preserve expressibility in $\mathrm{L}^\omega_{\infty\omega}$ backwards, the result follows: if CNF-SAT were expressible, EVENNESS would also be; a contradiction.


Estimating VC-Dimension What is known about the following problem?

  Given a collection $C$ of functions $f:\{0,1\}^n\rightarrow\{0,1\}$, find a largest subcollection $S \subseteq C$ subject to the constraint that VC-Dimension$(S) \leq k$ for some integer $k$.

Are there approximation algorithms or hardness results for this problem?

Edit: the original problem is $n^{1-\epsilon}$-hard to approximate when $k=1$ where $n$ denotes the number of sets.

The dual of a hypergraph is obtained by exchanging vertices with edges, and preserving incidences. It is easier to understand the problem when we note that a hypergraph has VC-dimension 1 iff its dual is cross-free (for all $P, Q$ in $A$, at least one of $P \cap Q, P \backslash Q, Q \backslash P, (P \cup Q)^c$ is empty).

By duality the original problem (for $k=1$) is equivalent to, given a hypergraph $(V, \mathcal{S})$, find a max-size $U \subseteq V$ with $(U, \{S \cap U \mid S \in \mathcal{S}\})$ cross-free.

In fact, this (dual) problem is very hard even when all sets in $\mathcal{S}$ have size 2: then it is a graph and we are looking for a max-size vertex size whose induced subgraph which does not contain any two-edge path (it's not hard to see this is the only way a crossing pair can arise, assuming the graph has at least 4 vertices). But this property is hereditary and nontrivial and thus we can use a result of Feige and Kogan to show hardness.

Original reply

The dual problem for $k=1$ (find a maximum-size $S$ such that the dual VC-dimension of $S$ is at most 1) is hard to approximate within $n^{1-\epsilon}$ (in a family with $\Theta(n)$ sets).

The reason for this is that the dual VC-dimension of a family $A$ is 1 iff the following holds: for all $P, Q$ in $A$, at least one of $P \cap Q, P \backslash Q, Q \backslash P, (P \cup Q)^c$ is empty. (I.e. VC-dim=1 is the dual of what is often called crossing-freeness.)

We reduce from independent set to computing the maximum-size cross-free subfamily. Given a graph $G=(V, E)$ construct a hypergraph $H=(X, S)$ where $X = V \uplus E \uplus \{0\}$ for some dummy element $0$. For each vertex $v$ of $G$, we add the following set $T_v$ to $S$: $$\{v\} \cup \{e \mid e \textrm{ is an edge incident to }v\}.$$

It's not hard to show a family $\{T_v\}_{v \in U}$ is crossing-free iff $U$ is independent in $G$.

But for the original (primal) problem, it seems some more thought is required... looks interesting!


What does it mean that there are differing views on how computations are represented on the Turing Machine? For a given algorithm (eg reverse the items in this list) and a given type of Turing machine (eg the 3-state 2-symbol busy beaver reduced to 5-tuples) - is there a single simplest way that this algorithm can be represented?

(This thread on LTU seems to suggest there are differences of opinion about what representing an algorithm on the Turing machine boils down to.)

It is not the algorithms that are represented in different ways, but input and output. Depending on how the input is encoded, a given problem might be hard or easy. To take a trivial example, consider the following encoding of Turing machines:

  A turing machine $T$ is represented by a number of the form $2 n + b$ where $n$ such
  that the binary digit expansion of $n$ gives a description of $T$'s program (encoded in a reasonable way). The number $b$ is $1$ if $T$ halts when run on empty input and $0$ otherwise.

With this encoding of Turing machines the halting problem becomes very easily computable. Given a description of Turing machine, just look at the lowest bit to determine whether the machine stops.

The moral of the story is that encoding of data is meaningless until we also specify what sort of structure we are trying to encode, i.e., which operations on data are supposed to be computable. (In the case of Turing machines it is known that the relevant operations are those of the s-m-n and u-t-m theorems, which fail for the silly encoding above.)

In case we worry about computational complexity we also need to require that the data are suitably "compressed", for example, if the input to an algorithm is a number $n$, it should be written with input of size $O(\log n)$, otherwise we can artificially "boost" the efficiency of the algorithm by writing down input in a very inefficient way.

If we work with the usual Turing machines then all reasonable ways of representing data will be equivalent (even polynomial-time convertible). But with very small Turing machines one might be forced to represent inputs in very strange ways because the machine will lack the power to recode its input in whatever form is needed. Under such circumstances people might disagree what is a reasonable way of encoding input. For example, may the input be repeated twice (suppose the machine lacks the ability to go backwards but it needs to read the input twice to do its job)? May the input be repeated infinitely many times? If we impose no restrictions on how the input is presented to the machine, then the input itself might already contain the answer that the machine is supposedly computing (witness the example of the Halting problem above). Sometimes it is hard to tell whether a given representation is "hiding" extra information. An infamous example of this was the solution to the Wolfram 2,3 Turing machine research prize where the input tape had to contain an infinite repeating pattern in order for the machine to work correctly. I suggest you look at the archives of the Foundations of mathematics mailing list for a detailed discussion about the 2,3 prize and about how even minor changes in input representations can cause big jumps in the computational power of a machine. The relevant threads are:

Wolfram 2,3 Turing Machine Prize
Smallest universal machine
Definition of universal Turing machine
Simple Turing machines, Universality, Encodings, etc.


Bounding the number of edges between star graphs such that graph is planar I have a graph $G$ which consists only of star graphs. A star graph consists of one central node having edges to every other node in it. Let $H_1, H_2, \ldots, H_n$ be different star graphs of different sizes which are present in $G$. We call the set of all nodes which are centres in any star graph $R$.

Now suppose these star graphs are building edges to other star graphs such that no edge is incident between any nodes in $R$. Then, how many edges exist at maximum between the nodes in $R$ and the nodes which are not in $R$, if the graph should remain planar?

I want the upper bound on the number of such edges. One upper bound that I have in mind is: consider them as bipartite planar graph where $R$ is one set of vertices and rest of the vertices form another set $A$. We are interested in edges between these sets ($R$ and $A$). Since it is planar bipartite, the number of such edges is bounded by twice the number of nodes in $G$.

What I feel is that is there a better bound, maybe twice the nodes in $A$ plus the number of nodes in $R$.

In case you can disprove my intuition, then that would also be good. Hopefully some of you can come up with a good bound along with some relevant arguments.

Your statement is a little ambiguous: first you write that "...such that no edge is incident between the nodes in $R$", but the next paragraph implies that there are also no edges between vertices in $A$. I'll also assume that the stars are disjoint, and that you count all edges (including those initially present in the stars). Let's also assume there are at least two stars, and at least one of them has degree $\ge 2$.

In that case, you cannot beat the $2N-4$ bound ($N$ = number of all vertices). Consider a slightly different scenario: start with any set of $N$ vertices, some red some black, at least two of each kind. At each step add arbitrarily an edge between a red and a black vertex, as long as it does not create intersections or duplicate edges. I claim that when you get stuck, all cycles have length $4$.

Your scenario is a special case of this process where you start by first creating stars and then later adding the remaining edges. If all cycles have length $4$, the $2N-4$ bound follows. More generally, it shows that no matter what bipartite graph you start from, you can always complete it to a quadrilaterated (a word I made it up) graph.

Now, let's show the claim. In this process, all paths will have alternating black and red vertices and each cycle will have length at least $4$. If the graph is not connected, you can connect any red vertex on the outer face of one component with a black vertex on the other face of another component. So we can assume the graph is already connected.

Suppose you have a face $F$ of length $6$ or more. $F$ must have at least three black vertices (some possibly equal). If some vertex $x$ is repeated on $F$, take two clockwise consecutive appearances of $x$, say $x-a-...-x-b...$. $F$ must contain a black vertex $z\neq x$, so, depending on the location of $z$, we could connect either $a$ or $b$ to $z$ inside $F$ without duplicating edges. If no vertex is repeated, pick a clockwise section $x-a-y-b-z$ of $F$, where $x,y,z$ are black and $a,b$ are red. If $x$ is connected to $b$ then $a$ cannot be connected to $z$ (by planarity), so we can add one of the edges $(x,b)$, $(a,z)$ inside $F$.


Compressing grammars by introducing ambiguity and left-recursion This is a reference request. What is known about the following questions?

Problem: Given a grammar $G$ (for example context-free) with language $L$ we can introduce a
new grammar $G'$ which also accepts $L$, but may introduce left
recursion and ambiguity.

Which algorithms have been investigated that produce such $G'$ from $G$?
By how    much can $G'$ be more succinct than
$G$ (for any reasonable notion of succinctness)?

Context. There has been a great deal of work on making grammars
parsable in practise. This involved removing ambiguity and (relevant
only for some form of parsing) left-recursion. Many notions of normal
form have been invented form this purpose, with parsers that can
handle these NFs. However, making grammars digestible by parsers also
makes them  less readable by humans. I'm    interested in going the other
way: How to make machine-parsable grammars more readable by giving up
on machine parsability (or at least making parsing harder).

Regarding your second question about succinctness, there is a nonrecursive tradeoff in grammar size when moving from general cfgs to unambiguous cfgs. See here:

Erik Meineche Schmidt, Thomas G. Szymanski:
Succinctness of Descriptions of Unambiguous Context-Free Languages. SIAM J. Comput. 6(3): 547-553 (1977)

EDIT (16/3/2019): answering to the comment, by introducing ambiguity, the resulting grammar will be nondeterministic, i.e. a general CFG. Imposing further restrictions on the given grammar, e.g. that the given CFG is LR(1), is of course not a suitable way to tame the tradeoff. Historically the first nonrecursive tradeoff to be shown was between finite automata and CFGs (Albert R. Meyer and Michael J. Fischer: Economy of Description by Automata, Grammars, and Formal Systems. SWAT 1971: 188-191). Completing the picture, there is also a nonrecursive tradeoff when moving from unambiguous CFGs to LR(1) grammars: Leslie G. Valiant:
A Note on the Succinctness of Descriptions of Deterministic Languages. Information and Control 32(2): 139-145 (1976)

EDIT (24/03/2019): answering to the other comment, if we restrict our attention to unambiguous finite automata, the gain in succinctness by introducing ambiguity will be at most exponential. In fact, a recent paper discusses a novel NFA minimization heuristics which merges equivalent states. A preprocessing step in the algorithm introduces additional transitions to the given automaton, which do not alter the accepted language ("saturation step"). The saturation step makes the automaton bigger, at least with respect to the number of transitions. And this step may introduce ambiguity. But the algorithm then contains a "quotienting step", which can allow for merging more states that are equivalent than without the saturation step. (The heuristics works for automata over infinite words and those over finite words.)

Clemente, Lorenzo and Mayr, Richard: Efficient reduction of nondeterministic automata with application to language inclusion testing. Logical Methods in Computer Science 15(1), 2019.


Does treewidth $k$ imply the existence of a $K_{1,k}$ minor? Let $k$ be fixed, and let $G$ be a (connected) graph. If I'm not mistaken, it follows from the work of Bodlaender [1, Theorem 3.11] that if the treewidth of $G$ is roughly at least $2k^3$, then $G$ contains a star $K_{1,k}$ as a minor.

Can we make the term $2k^3$ smaller? That is, does say treewidth at least $k$ already imply the existence of a $K_{1,k}$-minor? Is there a proof somewhere?

[1] Bodlaender, H. L. (1993). On linear time minor tests with depth-first search. Journal of Algorithms, 14(1), 1-23.

It is indeed true that every graph $G$ with no $K_{1,k}$ minor has treewidth at most $k-1$. We prove this below, first a few definitions:

Let $tw(G)$ be the treewidth of $G$ and $\omega(G)$ be the maximum size of a clique in $G$. A graph $H$ is a triangulation of $G$ if $G$ is a subgraph of $H$ and $H$ is chordal (i.e has no induced cycles on at least $4$ vertices). A triangulation $H$ of $G$ is a minimal triangulation if no proper subgraph of $H$ is also a triangulation of $G$. A subset $X$ of vertices of $G$ is a potential maximal clique if there exists a minimal triangulation $H$ of $G$ such that $X$ is a maximal clique of $H$. It is well known that
$$tw(G) = \min_{H} \omega(H) - 1$$
Here, the minimum is taken over all minimal triangulations $H$ of $G$.

The above formula implies that to prove that $tw(G) \leq k-1$ it is sufficient to prove that all potential maximal cliques of $G$ have size at most $k$. We now prove this. Let $X$ be a potential maximal clique of $G$, and suppose that $|X| \geq k+1$.

We will use the following characterization of potential maximal cliques: a vertex set $X$ is a potential maximal clique in $G$ if, and only if, for every pair $u$, $v$ of non-adjacent (distinct) vertices in $X$ there is a path $P_{u,v}$ from $u$ to $v$ in $G$ with all its internal vertices outside of $X$. This characterization can be found in the paper Treewidth and Minimum Fill-in: Grouping the Minimal Separators by Bouchitte and Todinca.

With this characterization it is easy to derive a $K_{1,k}$ minor from $X$. Let $u \in X$. For every vertex $v \in X \setminus \{u\}$, either $uv$ is an edge of $G$ or there is a path $P_{u,v}$ from $u$ to $v$ with all internal vertices outside $X$. For all $v \in X$ that are non-adjacent to $u$ contract all the internal vertices of $P_{u,v}$ into $u$. We end up with a minor of $G$ in which $u$ is adjacent to all of $X$, and $|X| \geq k+1$. So the degree of $u$ in this minor is at least $k$, completing the proof.


When does "X is NP-complete" imply "#X is #P-complete"? Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version.

Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"?

Of course the existence of a parsimonious reduction is one such condition, but this is obvious and the only such condition of which I am aware.  The ultimate goal would be to show that no condition is needed.

Formally speaking, one should start with the counting problem #$X$ defined by a function $f : \{0,1\}^* \to \mathbb{N}$ and then define the decision problem $X$ on an input string $s$ as $f(s) \ne 0$?

The most recent paper on this question seems to be:

Noam Livne, A note on #P-completeness of NP-witnessing relations,
Information Processing Letters, Volume 109, Issue 5, 15 February 2009, Pages 259–261
http://www.sciencedirect.com/science/article/pii/S0020019008003141

which gives some sufficient conditions.

Interestingly the introduction states "To date, all known NP complete sets have a defining relation which is #P complete", so the answer to Suresh's comment is "no examples are known".


Could any one enumerate some applications of enumerative combinatorics and Ramsey theory in TCS? The combinatorics, needless to say, is very closely related to TCS. But I found it hard to find the applications of enumerative combinatorics or Ramsey theory.

Or rather than being applied to TCS, the enumerative combinatorics or Ramsey theory is related to TCS because we use TCS techs and algorithms to tackle their problems.

I dont know very deep theory works, so please treat it easy.

This book will be helpful:

http://books.google.co.uk/books/about/Extremal_combinatorics.html?id=g6X2VWuB8qIC


partition to min the max number of intersections Given $n$ items and $m$ customers, each of whom is interested in some subset of the items, partition the set of items among $k$ different stores so that the maximum number of customers visiting any store is minimized.

Does anyone recognize this problem? I have the slight feeling that it is some standard set or cut problem in disguise, but I just cannot find the right one.

This is NP-hard, by reduction from 3-partition.

Given $\left[\hspace{.03 in}j_0,j_1,j_2,...,j_{(3\cdot k)-1}\hspace{-0.01 in}\right]$, $\:$ where $\; J = \operatorname{sum}\left(\left[\hspace{.03 in}j_0,j_1,j_2,...,j_{(3\cdot k)-1}\hspace{-0.01 in}\right]\right) \;$, $\;$ if there are

$k$ different stores, $\:J$ items, and $\:(3\cdot k)+(4\cdot J)\:$ customers,

with customer $i$ for $\:i\in [0,1,2,...,(3\cdot k)-1]\:$ interested in the obvious $j_i$ items

and four other customers interested in each one of the items,

then

the maximum can't be less than $\:\frac{4\cdot J}k+3\:$ and the partitions whose maximum is

$\frac{4\cdot J}k+3\:$ are exactly those corresponding to $3$-partitions of $\left[\hspace{.03 in}j_0,j_1,j_2,...,j_{(3\cdot k)-1}\hspace{-0.01 in}\right]$

.


Optimal partition according to partition cardinality Given $N$ sets of integers $S_1, \ldots,S_N$ with $|S_i| \le K$.

We want to partition those sets such that the union of all sets in any given partition doesn't contain more than $K$ elements.

Can the minimum number of partitions be found in polynomial time?
If so, how to know what other partition cost functions admit polynomial algorithms as well?

This problem is NPC; we can use it to decide whether there exist a $k$-clique.

Each edge $(u,v)$ is transformed into a set $S_{u,v}$, we put $u$ and $v$ into $S_{u,v}$, as well as $U$ globally unique elements. Set $K=\frac{k(k-1)}{2}U+k$ and $U=n^3$. Each share of the partition can contain $\frac{k(k-1)}{2}$ edges, if they form a $k$-clique; otherwise it can contain exactly $\frac{k(k-1)}{2}-1$ edges.

We add dummy edges to make sure the total number of edges has the form $C\cdot (\frac{k(k-1)}{2}-1)+1$. If there is no $k$-clique, we need $C+1$ shares, otherwise we need at most $C$ shares.


Abstract machine or algorithm for line solving a Nonogram I am currently working on a little project where I would like to write an efficient solver for three-dimensional Nonograms.

http://en.wikipedia.org/wiki/Nonogram

So I wanted to ask whether anybody of you know a good way on how to solve a line in a normal 2D Nonogram. The problem is NP-complete btw so finding a robust algorithm that always does it will be quite hard ;-)

But does anybody of you have an idea? It doesn't need to solve everything possible but should do basic checks on a line and see if it can fill out something.

Would be  great if anybody could give me tips on how I could achieve this... thanks!

... or if you just want to have fun you can simply grab a lot of useful tips from other (powerful) Nonogram solvers; you can start from here:

http://webpbn.com/pbnsolve.html which will teleport :-) you to:

http://webpbn.com/survey/ and ...

http://www.comp.lancs.ac.uk/~ss/nonogram/ ...

http://www.comp.lancs.ac.uk/~ss/nonogram/list-solvers

You can find detail descriptions of single-line / multi-line solving techniques and descriptions of more complex strategies.

When switching to 3D Nonograms single-line and multi-line strategies are still valid (apply 2D multi-line strategies on each section of your 3D puzzle); but if the 3D puzzle is difficult (or random), an iterated loop with those strategies ends up with many unknown pixels and to proceed you must apply specific 3D strategies.

If your question is more TCS oriented  then there are plenty of references in some public downloadable articles: http://www.google.it/search?as_q=nonogram+np&as_filetype=pdf


Max-Cut Of Minor Closed Family It's well known that planar graphs from a closed-family with forbidden minors $K_{3,3}, K_{5}$, graphs with bounded treewidth also are closed family graphs with no $H_{k}$ as minor.

I assume that graphs with bounded max cut form closed family graphs. Given arbitrarily graph $G$ that doesn't contain $H$ as a minor, how to find max cut approximately.

Thanks!

Addendum:

The relevant topic can be found on On the complexity of the Maximum Cut problem Chapter 6. Graphs with bounded treewidth. The PTAS begins with making modification to the tree decomposition without increasing it's treewidth.

1) $T$ is a binary  tree.

2) If a node $i \in I$ has two children $j_{1}$ and $j_{2}$, then $X_{i}=X_{j1}=X_{j2}$.

3) If a node $i \in I$ has one child $j$, then either $X_{j} \subset X_{i}$ and $|X_{i}-X_{j}|=1$, or $X_{i} \subset X_{j}$ and $|X_{j}-X_{i}|=1$.

In my opinion it's very strong modification, and actually I don't get the idea behind this modification. On the 2th condition if I understood rigth, if there is a node with two neighbors then all of then contain actually the same set of the vertexes, but what for?

MaxCut can be solved in polynomial time in $K_5$-minor-free graphs but is NP-hard in $K_6$-minor-free graphs (in particular, for apex graphs of planar graphs) [Barahona 1983].

See also this WG 2010 paper and slides by Marcin Kamiński.


Can chess simulate a Universal Turing Machine? I am looking to get a definite answer to title question.

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff the program halts?

The rules are the same as ordinary chess minus the 50 move rule, exchanges and castling.

And what is the minimum number of different types of pieces (ie the simplest game) that is needed for a chess-like game to be turing-complete? (Each type of piece having a set of allowed moves that is invariant under translations).

Is there any piece we can add to the game to prove it turing complete?

I also think that a very similar question has been asked before, I think first here: https://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board/63684
Here is my updated and modified opinion.

I think the problem is not solved completely, but the answer is almost surely yes. I do not have a proof for chess, as I lack the ability to design certain configurations but I think they must exist. And even if they don't, for some chess-like game they certainly do which shows that the attempts to prove decidability should be incorrect. Later I realized that there is a very similar argument to mine here: http://www.redhotpawn.com/board/showthread.php?threadid=90513&page=1#post_1708006 but my proof shows that in fact two counters are enough and maybe mine is more detailed.

The reduction relies on the notion of a stack machine. A stack machine with only two stacks using a stack alphabet of only one letter can simulate any Turing-machine. (Some people would call this deterministic finite automaton with two counters.) So our goal would be to simulate any such machine with a chess position. I can see two ways for this.

i, Build two separate configurations, such that both have a starting part and a moving part that can change (to store the state). Also, the moving parts would be connected, eg. by rooks, which could checkmate, if released, so this is why if one states moves 1, the other has to move k, and so on.

ii, Build a single configuration, that depending on its state, moves l horizontally and -k vertically. Also, place a rook at (0,0) that would never move but could guarantee that the configuration can "sense" when it gets back to an empty counter.

So all left to do is to design such configurations, which I guess should be possible with some effort and knowledge of chess. Also, note that in both cases the construction uses a piece whose range is not bounded, I wonder if this is really necessary. As a first step, I proposed to give a position equivalent to the Collatz conjecture:
https://mathoverflow.net/questions/64966/is-there-a-chess-position-equivalent-to-the-collatz-conjecture


What is the smallest result you publish on ArXiv? In essence, the question is:

What is the least publishable unit for the ArXiv?

Of particular interest are fields that use the ArXiv extensively such as quantum computing. But comments on other fields and preprint services (like, ECCC & ePrint) are also welcome.

Detailed question
This is based on the following two questions:

When should you say what you know?
How do you decide when you have enough research results to write a paper and to which journal you submit the paper

In particular, on Jukka Suomela's comment on this answer:

I think ArXiving your results ASAP is a good idea. Please keep in mind that an ArXiv manuscript does not need to constitute a minimum publishable unit. I think it is perfectly ok to submit a 2-page proof to ArXiv, even though it would be obviously too short as a conference or journal paper. Resolving an open problem that other people would like to solve is more than enough.

In my field (quantum computing) it seems that every preprint I see on the ArXiv is a publication-level paper, released early so that we don't have to wait for conference proceedings or journal turnaround. It is intimidating to submit something that is not at publication-level. Is it alright to put up results which are partial or only slight extensions of existing work? Is it alright to put up results that are potentially interesting (i.e. you've given some talks on them and not everybody fell asleep) but you doubt would get into a top-conference or journal? Do you have advice on when to share results on ArXiv or similar preprint-servers? Can sharing results early hurt you?

Some specific background
Just to make the question more personal, I'll include a further motivation. However, I am hoping to receive answers that give more general guidelines that I (and others) could follow in the future.
I did some work on unitary t-designs in which I extended an existing theorem (in a way that is kind of useful, but the proof of the original just needs to be modified slightly -- so no new idea; i.e. when I talked to the author of the earlier paper his comment was along the lines of "oh cool, didn't think about that", and for the proof I had to say about a sentence and then he was like "okay, I see how you would prove that"), proved some easy results, and provided an alternative proof of a lower bound.
I wrote up a pretty verbose paper that I keep on my website, but unfortunately I am not well read enough in the field to really understand how it fits in the bigger picture (and I think that is the biggest weak-point, that I doubt I could overcome easily). I keep the text around mostly as a sort of "I worked on this" note and since I give talks on the topic sometimes. It has also come in useful once to a friend since I make a pretty gentle intro and so he used it as a basic starting point to relate some of his work to designs (although he didn't use any of the results in the paper, just like a lecture note on definitions).
Would this be an example of something that I should put up on the ArXiv? or is the appropriate measure to keep it in on my website?

ArXiv papers still need to be recognizable as papers. I'd only put something on the arXiv if I'd feel comfortable publishing it as a letter in a journal (like, say, Information Processing Letters). For stuff that's even smaller than that, but that I still want to put on some sort of public record, I'll just make a blog post.

But in your case, if you've written it up as a preprint anyway, and you clearly state in it how much or how little is new, then why not? ArXiv papers don't actually have to have any new research content — survey papers are also welcome — so a paper that's mostly a survey but that extends the problem a small step in some direction doesn't sound problematic to me.


Can we count in depth $\frac{\lg n}{\lg \lg n}$? Can we compute an $n$-bit threshold gate by polynomial size (unbounded fan-in) circuits of depth $\frac{\lg n}{\lg \lg n}$? Alternatively, can we count the number of 1s in the input bits using these circuits?
Is $\mathsf{TC^0} \subseteq \mathsf{AltTime}(O(\frac{\lg n}{\lg  \lg n}), O(\lg n))$?

Note that $\mathsf{TC^0} \subseteq \mathsf{NC^1} = \mathsf{ALogTime} = \mathsf{AltTime}(O(\lg n), O(\lg n))$. So the question is essentially asking if we can save a $\lg \lg n$ factor in the depth of circuits when computing threshold gates.

Edit:
As Kristoffer wrote in his answer we can save a $\lg \lg n$ factor. But can we save a little bit more? Can we replace $O(\frac{\lg n}{\lg \lg n})$ with $o(\frac{\lg n}{\lg \lg n})$?
It seems to me that the layered brute-force trick doesn't work for saving even $2 \lg \lg n$ (more generally any function in $\lg \lg n + \omega(1)$).

Consider a fanin 2 circuit of $C$ depth $O(\log n)$. Divide the layers of $C$ into $O(\log n/\log\log n)$ blocks each of $\log\log n$ consecutive layers. We now wish to replace each block by a depth 2 circuit. Namely, each gate in the last layer of a block depends on at most $2^{\log\log n} = \log n$ gates of the last layer in the block below. We can thus replace each gate in the last layer by a DNF of polynomial size with inputs being the gates in the last layer of the block below. Doing this for all gates in the last layers for all blocks and connecting these should yield the desired circuit.

Let me note this is essentially the best one can obtain: the switching lemma allows for lower bounds all the way to depth $\log n/ \log\log n$.


Intuition behind nested positivity and counterexamples I'm looking at the nested positivity conditions for inductive types stated in the Coq manual. First off, are there any other references (not necessarily for Coq, but in dependent type theories generally) for the nested positivity conditions and how they come about? I've found older papers like Dybjer's Inductive Families and Coquand and Paulin's Inductively Defined Types, but I believe these only mention the strict positivity condition, and newer papers like the pCuIC one and A Comprehensible Guide to CIC don't mention nested positivity either.
Now, I'm trying to gain an intuitive understanding of why nested positivity is required. In essence, nested positivity states that when defining a constructor C for some inductive type $D$, if the type of an argument to $C$ is something like $I ~ \vec{p} ~ \vec{t}$, then $D$ can only appear strictly positively in $\vec{p}$, and only if $I \neq D$. I understand that allowing $D$ in negative positions of $\vec{p}$ basically allows for proofs of $(D \to \bot) \to \bot$, and allowing $D$ in other positive positions essentially allows for double negation elimination (and some inconsistency stuff with impredicative Prop). What I don't understand are these:

Why can't $D$ appear strictly positively in $\vec{p}$ if $I = D$ (either as constructor argument or return type)? For instance, for a constructor $C$ of an inductive type $D ~ (A: \textrm{Type}): \textrm{Type}$ (with $A$ as the sole parameter), why is $C: D ~ (D ~ A) \to D ~ A$ disallowed?
EDIT: Not only is this accepted in Agda 2.6.1.2, $C: D ~ (D ~ A \to \bot) \to D ~ A$ is also accepted, which seems suspicious to me.

Why can $D$ otherwise appear strictly positively in the parameters $\vec{p}$, but not in the indices $\vec{t}$? Consider for instance the (rather silly) constructor $C: (D =_{\textrm{Type}} D) \to D$ for the inductive type $D: \textrm{Type}$, where $=$ is the usual equality type.
EDIT: It turns out this doesn't type check in Agda for unrelated universe level reasons, so consider instead the following which Agda rejects for positivity reasons:
data Box : (A : Set) → Set where
  box : (A : Set) → Box A

data D : Set where
  C : Box D → D

This is accepted by Agda if A is instead a parameter, as expected from the nested positivity rules.

I'm particularly interested in finding examples where violating nested positivity conditions (specifically these two I've listed) causes inconsistencies and proofs of $\bot$, which personally would be easier to understand than arguments about monotonicity.

Here is an example exploiting positivity of an index to prove false:
module Whatever where

open import Level using (Level)
open import Relation.Binary.PropositionalEquality
open import Data.Empty

variable
  ℓ : Level
  A B : Set ℓ

data _≅_ (A : Set ℓ) : Set ℓ → Set ℓ where
  trefl : A ≅ A

Subst : (P : Set ℓ → Set ℓ) → A ≅ B → P A → P B
Subst P trefl PA = PA

data U : Set where
  d : U

El : U → Set
data D : Set

El d = D

{-# NO_POSITIVITY_CHECK #-}
data D where
  neg : ∀(c : U) → El c ≅ D → (El c → ⊥) → D

¬D : D → ⊥
¬D v@(neg c eq f) = Subst (λ D → D → ⊥) eq f v

spin : ⊥
spin = ¬D (neg d trefl ¬D)

Technically it also makes use of the fact that induction-recursion can create small universes, and that type equality can be smaller than general equality applied to the universe, but those are otherwise not really problematic to my knowledge (Coq has impredicative equality anyway, I believe). It's possible the simultaneous definition could be eliminated, too, but it's not straight forward, at least.

Edit: I asked around about your first bullet point. It was pointed out to me that there is essentially nothing special about a nested type that is nested in itself. This article shows how to use a non-native translation of nested types into indexed types of equivalent size. When you do that, as long as nesting is strictly positive, it's not difficult to apply the translation to a strictly positive indexed type.
Or for instance, the example translation I was shown uses a nested $ℕ$ parameter instead of self-nesting:
data D' (A : Set) (n : ℕ) : Set where
  c : D' A (suc n) → D' A n
  t : (case n of λ where
         zero → A
         (suc m) → D' A m
      ) → D' A n

Where I added the t constructor to make something actually use A, and D A is meant to be equivalent to D' A 0. I think another way to write this would be:
data D' (A : Set) : ℕ → Set where
  c : D' A (suc n) → D' A n
  t : D' A n → D' A (suc n)
  t' : A → D' A zero

Essentially, the $ℕ$ is a tree tracking how much nesting we need to unfold.


Separations between testing and tolerant testing for (natural) classes of functions? Note: I am considering here property testing in the query model, with regard to Hamming distance. (So, for instance, of Boolean functions—I'm phrasing it that way below.) I am in particular not interested in separations in distribution testing.

The property testing model (for Boolean functions) asks for algorithms that, for a fixed property $\mathcal{P}\subseteq 2^{2^n}$, are provided with a proximity parameter $\varepsilon \in (0,1)$ and query access to an arbitrary function $f\colon \{0,1\}^n \to \{0,1\}$, return either $\textsf{accept}$ or $\textsf{reject}$, such that:

if $f\in \mathcal{P}$, then the algorithm returns $\textsf{accept}$ with probability at least $2/3$;
if $d(f,\mathcal{P}) > \varepsilon$, then the algorithm returns $\textsf{reject}$ with probability at least $2/3$;

where $d(f,\mathcal{P}) \stackrel{\rm def}{=} \inf_{g\in \mathcal{P}} d_H(f,g)$ is the minimum (Hamming) distance between $f$ and a function satisfying the property.

Tolerant testing (as introduced by Parnas, Ron, and Rubinfeld) relaxes the first (completeness) guarantee from $d(f,\mathcal{P}) = 0$ to $d(f,\mathcal{P})\leq \varepsilon'$, where $0\leq \epsilon' < \varepsilon$ is another input to the algorithm. In particular, tolerant testing is at least as hard as testing, by choosing $\varepsilon' = 0$.

However, I am aware of only very few separations between testing and tolerant testing which show the latter to be actually harder, for "natural" properties of functions $\mathcal{P}$. (Of course, here the word "natural" is fuzzily defined; I guess we recognize what it means when we see it.)

An example (for contrived properties) was given by Fischer and Fortnow [1], where they provide a property with $O_{\varepsilon,\varepsilon'}(1)$-query testers, while every tolerant tester requires $n^{\Omega(1)}$ queries. This is the extent of my knowledge regarding published or available results.

  Is there any such separation known for an (arguably) natural property of Boolean functions? If not, of functions $f\colon \{0,1\}^n \to \mathbb{R}$, or $f\colon [n]^d \to \mathbb{R}$?

[1] Tolerant Versus Intolerant Testing for Boolean Properties, Eldar Fischer and Lance Fortnow. Theory of Computing, 2006. http://theoryofcomputing.org/articles/v002a009/

The recent preprint of A. Levi and E. Waingarten [1] establishes such a separation* for two "(arguably) natural" properties of functions: unateness and junta-ness.

*(for junta-ness, such a separation is shown only for non-adaptive testers.)

  Theorem 1. ([1]) Non-adaptive tolerant testing of $k$-junta-ness has query complexity $\tilde{\Omega}(k^2)$.

On the other hand, Blais [2] showed that non-adaptive testing of $k$-juntas had query complexity $\tilde{O}(k^{3/2})$, hence the separation.

  Theorem 2. ([1]) Non-adaptive tolerant testing of unateness has query complexity $\tilde{\Omega}(n^{3/2})$.

On the other hand, Baleshzar et al. [3] showed that non-adaptive testing of unateness had query complexity $\tilde{O}(n)$, hence the separation.

  Theorem 3. ([1]) Tolerant testing of unateness has query complexity $\tilde{\Omega}(n)$.

On the other hand, Chen, Waingarten, and Xie [4] showed that non-adaptive testing of unateness had query complexity $\tilde{O}(n^{3/4})$, hence the separation.

[1] Erik Waingarten and Amit Levi. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs, 2018. arXiv:1805.01074

[2] Eric Blais. Improved Bounds for Testing Juntas. APPROX-RANDOM, 2008.

[3] Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri. Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. ICALP, 2017.

[4] Xi Chen, Erik Waingarten, Jinyu Xie. Boolean Unateness Testing with $\tilde{O}(n^{3/4})$ Adaptive Queries. FOCS, 2017.


Are There Highly Symmetric NP- or P-complete Languages? Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on sets $L_n = \{ l \in L \mid |l| = n  \}$ such that there are few orbits, i.e such that $|L_n / G_n| < n^c$ for big enough $n$ and some $c$, and such that $G_n$ can be generated given $n$ efficiently?

The point here is that if one finds a language/group such as this, and if one can find normal forms under polynomial time group actions in $\mathrm{FP}$, then one can reduce $L$ by a $\mathrm{PTIME}$ reduction  to a sparse language by computing the normal form for any given $N$, implying that $\mathrm{P = NP}$ or $\mathrm{L = P}$, depending on whether you chose an NP- or P-complete language initially, respectively. So it seems that either there are no such groups with sparse orbits or that computing normal forms is hard for all such groups or one of these results will hold which I think most of us don't believe. Also it would seem that if one can compute the equivalence relation over the orbits instead of the normal forms, one could still do this nonuniformly, in $\mathrm{P/poly}$. Hoping some other people have thoughts on this.

For NP, this seems hard to construct. In particular, if you can also sample (nearly) uniform elements from your group - which is true for many natural ways of constructing groups - then if an NP-complete language has a poly-time group action with few orbits, PH collapses. For, with this additional assumption about sampleability, the standard $\mathsf{coAM}$ protocol for Graph Isomorphism also works for testing whether two strings are in the same $G_n$-orbit. We then would have $\mathsf{NP} \subseteq \mathsf{coAM/poly} = \mathsf{coNP/poly}$, so PH collapses to $\mathsf{ZPP}^{\mathsf{NP}}$. So, to avoid collapsing PH, any such construction for NP would need the groups to not have an efficient nearly-uniform sampler.


Example of $MSO_2$ definable NP-hard problem on bounded clique-width graphs All $MSO_1$ and $MSO_2$ definable graph problems can be solved in linear time on bounded tree-width graphs by Courcelle's theorem. But it seems this theorem doesn't work for $MSO_2$ definable graph problems on bounded clique-width graphs.

Can some provide me an example of $MSO_2$ definable NP-hard problem on bounded clique-width graphs.

One example is the vertex disjoint paths problem, which is linear time solvable in graphs of bounded tree width but NPC in graphs of clique width at most $6$.


Split find-min data structure that finds several small elements? The split find-min data structure is initialized with a sequence of elements $e_1,\ldots,e_n$, each associated with a key. The data structure supports three operations:

(1) $Split(e_i)$ that splits the sequence at position $e_i$.

(2) $FindMin(e_i)$ that returns the minimum in the interval that contains $e_i$.

(3) $DecreaseKey(e_i,k)$ that decreases the key of $e_i$ by $k$.

For instance, you may have started with $[5,2,1,4]$, where the min is $1$, then split at $2$ to get $[5][2,1,4]$, so the min of the first interval is $5$ and the min of the second interval is $1$.

Seth Pettie gave an implementation of this data structure that makes at most $O(m\log\alpha(m,n))$ comparisons when $m$ is the number of $DecreaseKey$ operations and $n$ is the number of elements ($\alpha$ is the inverse Ackermann function).
For more details see the paper:

Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
http://arxiv.org/abs/1407.1910

My question is: Suppose that you want to support queries not about which is the min element in each interval, but about which are the $l$ smallest elements in each interval, for a parameter $l\gg 1$ (note that you don't need to know the order among the $l$ smallest elements, only what they are). How many comparisons do you need for that?

Use a forest of 2-4 trees in which the keys are at the leaves. Every internal node contains a copy of the minimum key that descends from it as well as a positive integer indicating the number of values of this key descending from it.

Additionally, maintain a van Emde Boas tree containing as keys each positive integer $i$ where $e_i$ is the left-most element in one of the 2-4 trees. In the vEB tree, each integer $i$ has satellite data: a pointer to the root of the tree the key associated with $e_i$ is in.

$Split$ is the normal split on 2-4 trees, updating the internal node data as it proceeds. This takes logarithmic time in the size of the tree being split, while updating the vEB tree takes time corresponding to the logarithm of the logarithm of the number of trees in the forest.
$FindMin$, which now returns the $l$ smallest keys, does a breadth-first search down the tree containing the element in question. Starting from the root, this takes time linear in $l$. To find the root from the element, access the vEB tree, find the predecessor, then follow the pointer to that root.
$DecreaseKey$ modifies a single 2-4 tree, taking time logarithmic in the size of that tree.

Each $Split$ uses $O(\log \log n)$ time for the vEB operation and $O(\log n)$ key comparisons. Each $FindMin$ uses $O(\log \log n)$ time for the vEB operation and $O(l)$ key comparisons. Each $DecreaseKey$ uses $O(\log n)$ key comparisons.


Is there a normalizing (or perpetual) reduction strategy for untyped combinators? Inspired by this question, I was curious whether there was a reduction strategy for untyped SKI combinators that was known to be either normalizing or perpetual.

As described here (Twelfed here), the nondeterminstic rules of the combinator calculus are these:

$Ix \rightarrow x$

$Kxy \rightarrow x$

$Sxyz \rightarrow xz(yz)$

$xy \rightarrow x'y$ if $x \rightarrow x'$

$xy \rightarrow xy'$ if $y \rightarrow y'$

SKI combinators were used as the implementation technique for Miranda, a lazy functional language developed by David Turner. The reduction strategy you are after is
simply to perform the reductions left to right (aka normal order or call-by-name reduction). This is called SKI combinator reduction, and it's naturally lazy. If a normalising reduction sequence exists, then this reduction strategy will find it.

One problem with SKI combinators is that they have the unfortunate property of resulting in an exponential blowout in code size during reduction.

See:

D.A. Turner. A new implementation technique for applicative languages. Soft. Pract. and Exper., 9, pp. 31-49, 1979.
Lambda-Calculus and Combinators: An Introduction, Second Edition by J. R. Hindley and J. P. Seldin


Sorted dictionary structure supporting efficient merges? Many balanced tree structures (red/black trees, splay trees, etc.) and some other sorted dictionary structures (skiplists) support a join operation that takes in two dictionaries where all keys in the first structure are less than all keys in the second, then combines the two dictionaries into a single sorted dictionary in time $O(\log n)$, where $n$ is the total number of keys. However, this only works if there is no overlap in the ranges of keys stored in those trees.

Similarly, many priority queues (binomial heaps, Fibonacci heaps, etc.) support $O(\log n)$-time merges. These merges work regardless of what keys are stored, but given that the data structures are priority queues we can't do lookups for random elements in the resulting structure.

Is there a sorted dictionary structure that supports merges of arbitrary dictionaries in time $O(\log n)$ while simultaneously supporting normal sorted dictionary operations (insertions, deletions, lookups, successor/predecessor queries, etc.) in time $O(\log n)$, or a lower-bound proof that such structures can't exist?

If you have a balanced binary search tree data structure with the finger search tree property (a search for an item $d$ positions away takes time $O(\log d)$), such as for instance a splay tree, then if you insert a sorted sequence of $k$ items into it the total time for the insertion will be $O(k\log(n/k))$.

Now, suppose that you want to support insertions, destructive merges, and searches. For the insertions and searches, just use the existing search tree operations. For a merge, always merge the smaller tree into the larger one, and use an inorder traversal of the smaller tree to get its sorted order in linear time. Then, insert the elements of the smaller tree one at a time into the larger tree in this sorted order.

If an element $x$ is inserted then merged into a sequence of larger trees with sizes $n_1, n_2,\dots$ then the amount of time for the insertion and merges (counting only $x$'s fraction of the total merge time) will be $O(\log n_1)$, $O(\log(n_2/n_1))$, $\dots$, which add in a telescoping sequence to $O(\log n)$. So if one uses an amortization scheme in which this logarithmic total time for a potential sequence of merges is charged to the insertion operation for $x$, then we still get $O(\log n)$ amortized time per insertion or search, and only $O(1)$ amortized time per merge.

Deletions complicate this analysis, but not much. One way to handle them would be to do a semi-lazy deletion, where a deleted item is removed from its tree but not removed from the count of items in this tree, so that when we decide which of two trees is smaller or larger we count all the items that were ever in the tree. Then, the $n$ in the $O(\log n)$ time per operation should be the total number of items ever inserted or deleted rather than the number currently present. If these two numbers ever grow too far apart you can make an update that re-adjusts all the counts to their actual numbers, resetting the data structure to a state with no lazy-deleted items; the amortized time for this update can be charged against the deletion operations you had to perform to get the numbers so far apart. Or possibly you can make the merge amortization work directly with non-lazy deletions, but I haven't worked out the details of that part.


Implications of proving NP=RP on complexity theory Edit: As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, have benefited from them. It would probably be unfair to accept just one one answer in this case.
I apologise if this is off topic. In the paper just uploaded today (Edit: the paper is now withdrawn due to a flaw, see the comments below)
https://arxiv.org/abs/2008.00601
A. Farago claims to prove that NP=RP. From the abstract:
We (claim to) prove the extremely surprising fact that NP=RP. It is achieved by creating a Fully Polynomial-Time Randomized Approximation Scheme (FPRAS) for approximately counting the number of independent sets in bounded degree graphs, with any fixed degree bound, which is known to imply NP=RP. While our method is rooted in the well known Markov Chain Monte Carlo (MCMC) approach, we overcome the notorious problem of slow mixing by a new idea for generating a random sample from among the independent sets.
I am not an expert in the complexity hierarchies, why is this thought to be so surprising?
And what are the implications, if the claim is correct?

Prelude: the below is just one consequence of $\mathsf{RP}=\mathsf{NP}$ and probably not the most important, e.g. compared to collapse of the polynomial hierarchy. There was a great and more comprehensive answer than this, but its author removed it for some reason. Hopefully the question can continue to get more answers.
$\mathsf{P}/\mathsf{poly}$ is the set of decision problems solvable by polynomial-size circuits. We know $\mathsf{RP} \subseteq \mathsf{BPP}$ and, by Adleman's theorem, $\mathsf{BPP} \subseteq \mathsf{P}/\mathsf{poly}$. So among the only mildly shocking implications of $\mathsf{RP}=\mathsf{NP}$ would be $\mathsf{NP} \subseteq \mathsf{P}/\mathsf{poly}$.
Another way to put it is that instead of each "yes" instance of an $\mathsf{NP}$ problem having its own witness, there would exist for each $n$ a single witness string that can be used to verify, in polynomial time, membership of any instance of size $n$.


Information theory and convex optimization I'm taking a graduate level course in information theory and I'm constantly struck by how much convex optimization there is in this subject. However, the proofs seem to shy away from using the full machinery of relaxation theory, duality, etc. This is understandable since you don't want to require a full semester of convex optimization in order to teach this stuff. But as someone fairly well-versed in optimization, I feel like I'm missing out on a lot of elegance and intuition when these links aren't explored more. I often notice proofs that would be way shorter if you had utilized convex analysis as well.

Are there books that cover information theory more from this perspective? We're mostly using lecture notes from Stefan Moser, Y. Polyanskiy and Y. Wu, as well as Network Information Theory by El Gamal.

The books below may be more to your liking, but in general, the texts/lecture notes are written for the use of (mainly) postgraduate students in engineering and cannot presume deep knowledge of convex analysis.

Csizsar, I., and Korner, J., Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd Ed, Cambridge.
Berger, T., Rate Distortion Theory, quite old probably late 70's or early 80s, can't remember the publisher maybe Wiley.
Yeung, R.W., A First Course in Information Theory, Springer.

The research articles on Shannon theory and related fields in, say, IEEE Transactions on Information Theory, may fit the bill better, though not always.

An older text which may also be of interest is

Wolfowitz, J., Coding Theorems of Information Theory, Springer, 1960's.


decision tree complexity and query complexity I want good sources for starting with decision tree complexity and query complexity , what papers to start with ? what book chapters to read ? I already seen arora and barak book and I begin to read it ... so any other suggestions will be welcomed ...

Chapters-3,4 in book Analysis of Boolean Functions by Ryan O'Donnell might be a good starting point.


Any computable transcendental number that is computable in P time but not $O(n)$ Is there any known computable transcendental number such that its $n$th digit is computable in polynomial time, but not in $O(n)$?

Here is the construction of such a number.  You can argue whether this means such a number is "known".

Take any function $f$ from $\mathbb{N}$ to $\{ 1, 2, \ldots, 8 \}$ where the $n$'th digit is not computable in $O(n)$ time.  Such a function exists, for example, by the usual diagonalization technique.   Interpret $f(n)$ as the $n$'th decimal digit of some real number $\alpha$.   Now, for each $n$ of the form $2^{2^k}$, $k \geq 1$, change the digits of $\alpha$ in positions $n, n+1, \ldots, 3n$ to $0$'s.   The resulting number $\beta$ evidently retains the property that the $n$'th digit is not computable in $O(n)$ time, but has infinitely many very good approximations by rationals, say to order $O(q^{-3})$, of the form $p/q$.  Then by Roth's theorem $\beta$ cannot be algebraic.  (It is not rational because it has arbitrarily long blocks of $0$'s set off by nonzeros on both sides.)


What are the most effective algorithms to find random number? I was reading the Ramsey's Theory stating "complete disorder is impossible". Is there any algorithm to generate random numbers for a long period of time without there being any relation from one set of random numbers to any other set?

As other answers mentioned, any deterministic process (such as Turing/Register Machines) can not produce 'philosophical' or 'true' random numbers. Allow me to answer a slightly rephrased question: "What are the most effective algorithms for finding pseudorandom numbers?"

There are arguably four important properties to consider in pseudorandom number algorithms:

Security/Hardness of prediction (under varying contexts, i.e. given different amounts of information about the internal state of the algorithm as it runs or bits generated from its output)
Cycle length, the amount of time it takes for the algorithm to enter into a cycle / repeat its output (and also how this cycle length is distributed according to its input; whether there are some inputs that cause very short cycles)
Distribution of output values (usually this distribution can be 'flattened' into the uniform distribution using various tricks, but this introduces additional overhead)
Speed of the algorithm

There is an old engineering joke involving steam engines. An engineer that specialized in trains confronts his investor, telling him that steam engines have three properties: speed, safety, and cheapness; and that due to some fundamental laws of physics, steam engines can only be designed with two of the three properties.

This story relates well to the current state of pseudorandom number generators. Many algorithms are believed to have several of these properties, but no algorithm (as far as I know) is known to have all of these properties.

And so you must choose the algorithm most appropriate for your application. For example, in Computer Graphics algorithms often use Monte Carlo techniques to find an approximate solution to raytracing problems. Obviously for these applications a long cycle of non-redundant, uniformally distributed outputs are required. The faster this algorithm works, the better. Because the application does not need to keep its bits safe from an adversarial entity, rendering algorithms are free to use non-secure PRGNs that simply pass statistical randomness tests. Monte Carlo applications like this are popular and can be encounterd in statistical physics, primality testing (another) and other probabilistic algorithms, Computer Go, and many more places.

For these types of applications, Lagged Fibonacci Generators have been popular. The Mersenne Twister has in recent years been adopted more and more frequently (despite some criticism). The Mersenne Twister is generally easy to predict and should not be used for applications where hardness is a requirement (caveat: some research has been done in developing variants that are thought to be secure in this manner).

There are some applications that need security garuntees. For example, in Interactive Proof Systems, verifiers need to challenge provers with random decisions. If the prover is capable of predicting the verifier's decisions, the protocol breaks down and we get can get no garuntees on the validity of the proof. For this application, a low speed on the algorithm is an acceptable loss for a hardness garuntee (the prover does almost all of the processing in these schemes). Similarly, when choosing bits of prime numbers to generate an RSA key, it is acceptable to absorb the one-time cost of a slow algorithm that has some garuntee of unpredictability.

There are a number of cryptographically secure pseudorandom number generators. However, the level of security varies greatly between these algorithms. One can use symmetric encryption algorithms and hash functions as PRNGs, although this is generally not suggested in the literature. Fortuna and Yarrow (both by Bruce Schneier) are considered cryptographically secure. However, these are examples of algorithms whose security proofs are derived from the statement "all known methods for breaking PRNGs fail on this algorithm" which is considered a weaker security proof than that of explicitly showing an intractibility proof from reasonable complexity assumptions. Blum Blum Shub is an algorithm noted for its unusually strong security proof.


Grid minor in digraphs Thor Johnson, et al, in their paper: Directed Tree Width, introduced a definition for directed grid $J_k$, and they conjectured:

  $(5.1)$ For every integer $k$ there exists an integer $N$ such that every
  digraph with tree-width $N$ or more has a minor isomorphic to $J_k$.

And they continued by saying:

  We have convinced ourselves that $(5.1)$ holds for planar digraphs,
  but the general case is open.

And I'm looking for this unpublished paper (how they proved the conjecture for di-planar graphs), or related stuff in this case, actually how to use such a grid (I mean $J_k$).

There is a new preprint by Stephan Kreutzer and Ken-ichi Kawarabayashi, in which they apparently show that the statement (5.1) is true for all digraphs.

Stephan Kreutzer and Ken-ichi Kawarabayashi: The directed grid theorem.    arXiv:1411.5681 [cs.DM]

EDIT (June 16, 2015):

A short version of their paper appears here:

Ken-ichi Kawarabayashi, Stephan Kreutzer. The Directed Grid Theorem. In: Rocco A. Servedio, Ronitt Rubinfeld (eds.), Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing 2015. pp. 655-664


Faithful functors vs forgetful functors: exact category-theoretic defs? In category theory, a functor between two categories $C,D$ is a map $F$ that assigns to each object (resp. morphism) $x$ of $C$ a corresponding object (resp. morphism) $F(x)$ of $D$ by respecting the incidence relations.

For each pair of objects $x,y$ of $C$, we may then define a map $F_{x,y}$ that takes any morphism $m : x \rightarrow y$ to a morphism $F(m) : F(x) \rightarrow F(y)$. I understand that $F$ is called faithful if every such mapping $F_{x,y}$ is injective, which means intuitively that the relational structure of the category is preserved, although the objects may not be.

There is a related notion of forgetful functor for which I couldn't find a precise definition, so is there anyone willing to help? I mean, is it just the opposite of faithful or is it the combination of unfaithfulness with some other implicit property?

you should have a look at http://ncatlab.org/nlab/show/forgetful+functor. As the nLab article says, in its common usage there is no precise definition of forgetful functor, though there are some typical examples (such as a functor $U : Alg \to Set$ forgetting some kind of algebraic structure, which will typically have a left adjoint $F : Set \to Alg$ corresponding to the construction of free algebras). And in another (useful) sense, every functor may be regarded as a forgetful functor, and classified according to how much it forgets.  There is no requirement that a functor be unfaithful for it to be called "forgetful", and many common examples of forgetful functors are faithful (such as the forgetful functor $Grp \to Set$ from groups to their underlying sets), while others are not (such as in general the functor $cod : C^\to \to C$ from the arrow category of $C$, forgetting everything about an arrow except its codomain).


Quantum Hardness of Approximating Lattice Problems A common claim in lattice-based cryptography is that cryptosystems based on the Learning with Errors ($\mathsf{LWE}$) problem are hard to break (for a per-system definition of "break") for quantum attackers.

For instance, the standard paper on $\mathsf{LWE}$, Regev2005, makes multiple references to the security of $\mathsf{LWE}$-type systems based on the quantum hardness of solving, say, $\mathsf{GapSVP}_\alpha$ for polynomial approximation ratios $\alpha$. But, as far as I see, there is no mention here as to why a critic might be convinced that such quantum hardness holds.

Across the host of lattice-based cryptography, the reference is generally made back to Regev's first paper, with no more explanation. And this association is quite important to the broader theory community, because likely tens of millions (or more) dollars are handed out in cryptography grant money based (in part) on this high-level claim.

Searching the CSTheory site also turns up no answer to this question. Perhaps there is a simple place to look up this information online.. in which case, consider this question the "CSTheory catalogue" of where to find this information!

$\underline{\rm Question}:$ What is the proper, "standard" justification for why it is believed hard for efficient, quantum algorithms to approximate $\mathsf{GapSVP}_\alpha$ to within polynomial approximation factors $\alpha$?

$\underline{\rm Question\; Clarification\, /\, What\; I'm\; Looking\; For:}$

What structural property of factoring allows Shor's algorithm to run
quickly, but appears to be missing from worst-case lattice (approximation) problems?
In particular: How is this gap related to our current understanding of the Abelian Hidden Subgroup Problem (HSP) vs non-Abelian variants of the HSP?

The answer to your question is the same as with many other such assumptions in cryptography: despite a lot of effort no one has found any substantially faster quantum algorithms for lattice problems. Why do we assume that RSA is secure? We don't have any particular justification for its classical hardness other than the fact that no one has found any fast algorithms for it, and we know that it is vulnerable to quantum attacks. Despite this we trust it to protect billions of dollars of e-commerce.

On the other hand, the situation is not really the same. There is much better justification for LWE-based systems being secure. What makes LWE appealing is that it's based on the worst-case (quantum) hardness of lattice problems. As you probably know, a holy grail of crypto is to derive average-case-hard primitives like one-way functions from worst-case hardness assumptions like $P \neq NP$. Regev's reduction is a big step in this research program, and as far as I know there are no non-lattice based schemes whose security is based on worst-case hardness assumptions.

Finally, it's worth noting that LWE may still be secure against classical attacks even if there are efficient quantum algorithms for lattice problems. A major open problem in lattice-based cryptography is to prove classical hardness of LWE with parameters that match the quantum reduction. A paper by Peikert in 2009 and a follow-up paper by Brakerski et al. in 2013 made progress towards this goal by showing classical hardness of LWE under some weaker parameter settings.