Proof Complexity and Circuit Lower bound for coNP I have two questions

(1)Circuit lower bound for coNP

TAUT is a set of formulae such that any formula in TAUT is satisfied for all boolean assignments.
UnSAT is the complement problem of SAT.

It is known that if NP$\neq$coNP then P$\neq$ NP, and that solving NP vs coNP problem is harder task than proving circuit lower bound of NP-complete problems.

Is the following statement true?

Proving NP is not equal to coNP by showing a super-poly lower bound of proof size is "harder" task than deriving super-poly circuit lower bounds for a coNP-complete problem such as TAUT or UnSAT.

I think that this is true because NP and coNP has a "symmentric" relation.

(2)Uniform theory of  proof complexity

There are two streams of circuit complexity. First one is concrete complexity lower bounds for Non-uniform models like Sipser's PARITY lower bounds for constant depth circuit. Second one is simulation based lower bounds which is intensively argued in a book of Introduction to Circuit Complexity: A Uniform Approach by Vollmer.

Can we construct a simulation based uniform theory of proof systems and deriving structural separatins beween two classes of proof systems ?

For the first question, it depends on what you mean by "harder". If you mean one logically implies the other then yes.

A lowerbound in a deterministic model of computation (containing negation) works also for the complement of the language because it is deciding the language. Therefore a circuit lowerbound for an $\mathsf{NP}$ problem is also a circuit lowerbound for its complement which is in $\mathsf{coNP}$.

(If you mean finding a proof of one is considerable harder than finding a proof of the other then it is a matter of opinion and arguable.)

For the second question,
the concept of uniform proof complexity corresponds to theories in bounded arithmetic. You can translate proofs in such theories to propositional proofs using the propositional translation. See Stephen A. Cook and Phuong Nguyen, "Logical Foundations of Proof Complexity", 2010. These theories correspond to the uniform version of propositional proof systems in a similar way that uniform complexity classes like $\mathsf{P}$ are considered to be the uniform version of non-uniform complexity classes like $\mathsf{P/poly}$.
There are other nice relations between the uniform and non-uniform proof systems that add justification to this correspondence.
(Some ideas goes back to Steve'e original paper "Feasibly Constructive Proofs and the Propositional Calculus" from 1975 paper).

One can define other types of uniform proofs between these two, but it is not clear what you are asking (seems more like a post to solicit opinion about an idea than a question). You can find related stuff in Jan Krajicek's and other peoples' lecture notes on proof complexity.


Looking for an online community specializing in the Z specification language, where I can ask questions Where can I find an online community specializing in the Z specification language, where I can ask specific questions about the ISO standard for Z?

There is the comp.specification.z newsgroup, available on Google Groups.
There are some mailing lists:

ZFORUM mailing list
Zed Freelists mailing list

Additionally, there are mailing lists for tools that support the Z notation.  For tools that support ISO Z (or a similar dialect), I doubt anyone would object to a question about the notation itself if the above sources are not useful.  For example:

Community Z Tools (CZT) mailing lists
ProofPower mailing list


Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$ Consider a rational polytope $P$ that is defined by means of a separation oracle. That is, $P$ can be described implicitly as $P = \{x \in R^k: Ax \leq b, A \in Z^{m \times k}, b \in Z^m \}$, but since $m$ is very large, we use an oracle, that given a point $x \in R^k$, either says $x \in P$ or returns a half-space such that $x \notin S$.

My goal is to find a point in $P$ or determine that $P$ is empty. I'm aiming for  a polynomial running time in the representation size of $U$ and $k$, where $U$  is the largest absolute value in $A$. That is, the algorithm should make only polynomial many calls to the separation oracle.

In general, $P$ might be contained in a hyper-plane of lower dimension and thus it is problematic to use the ellipsoid method. So, as in Khachiyan's trick, I alter $P$ (and the separation oracle) to use $P^\epsilon$, where $\epsilon$ is something like $1/U$. Intuitively, the half-spaces that define $P^\epsilon$ are the same as the ones that define $P$ only that they are translated by $\epsilon$. The polytope $P^\epsilon$ has the following properties: $P^\epsilon$ is empty iff $P$ is empty, and if $P$ is not empty, $P^\epsilon$ is full-dimensional.

My question is as follows:
Assume the algorithm finds a point $p \in P^\epsilon$. Is it possible to generate a point in $P$ using $p$?

From any choice of a polytope $P$ in ${\mathbb R}^k$, $\epsilon$, and a point $q$ in ${\mathbb R}^k$ it is possible to find a polytope $\hat P$ in ${\mathbb R}^{k+1}$, together with an embedding of ${\mathbb R}^k$ into ${\mathbb R}^{k+1}$, such that $\hat P$ is within $\epsilon$ Hausdorff distance of (the embedded image of) $P$ and such that (the embedded image of) $q$ belongs to $\hat P^\epsilon$. To do this, simply make the facets of $\hat P$ be nearly parallel to the embedded image of ${\mathbb R}^k$, so that translating them by $\epsilon$ in ${\mathbb R}^{k+1}$ causes their intersection with ${\mathbb R}^k$ to move away from $\hat P$ by a much greater distance.

Because $q$ was arbitrary, the knowledge of $q$ is of no use in finding a point in or near $P$; everything you could do with it you could do without it. But, because $\hat P$ and $P$ are so close, finding a point near $P$ is equivalent to finding a point near $\hat P$. Therefore, the knowledge of $q$ (a point in $\hat P^\epsilon$) is of no use in finding a point near $\hat P$.


Why is computing pure Nash equilibria NP-complete? In this paper, it is claimed that computing pure-strategy Nash equilibria of games in standard normal form is NP-complete.

This confuses me, because I do not understand why it is hard to guess the right strategy profile (the authors call this the "global strategy") for a game.  Surely if the Nash equilibrium of a game is written out in normal form, where every strategy profile is assigned its own cell, then it should take only linear time to run through every possible strategy profile that is a candidate for being a Nash equilibrium.

I do not understand what I am missing; please explain why Nash equilibrium computation is hard for standard normal form games.  Thank you.

These are my two comments as an answer:

Of course you are right that if the strategic form (also called the normal form) is given explicitly then one can just check all pure strategy profiles. In that case, the problem of deciding if there is a pure equilibrium is clearly not likely to be NP-hard.

However, the paper shows in Theorem 3.1 hardness for graphical games (called in the paper, games in graphical normal form (GNF)), which are succinctly represented games. (It might not be the best phrasing in the statement of Theorem 3.1 to say "even for", which is fine as regards constant values of parameters, but not for the representation type itself).

In general, if each of $n$ players has $m$ actions then the the strategic form has $nm^n$ entries, but a graphical game has $O(nm^{d+1})$, where $d$ is the maximum degree in the graph. So for constant $d$, the graphical game representation is exponentially smaller than the strategic form. In their reduction $d$ can be 3 (and $m$ can also be 3, so only $n$ needs to vary).

For the strategic form (standard normal form, SNF, as they call it in the paper) they show that the problem is easy (Theorem 5.1), which is straightforward as you noted.

SNF and GNF are compared on page 6 of the paper.


Type checking, Hypothetical judgments, meaning explanations and computational type theory We say that a system is a computational type theory if it is a type theory defined by not a bunch of inference rules, but some sort of Martin-Löfian meaning explanations (e.g. in the sense of NuPRL). Now according to Martin-Löf's meaning explanations [1], a hypothetical judgment of the form
$$ x_1 : A_1, ..., x_n : A_n \vdash a : A \qquad\qquad\qquad\qquad\qquad\qquad (1)$$
means that
$$ \vdash a[x_1,...,x_n/a_1,...,a_n] : [x_1,...,x_n/a_1,...,a_n]A \qquad (2)$$
for all closed terms $a_1 : A_1, ..., a_n : A_n$ (and also that this judgment should be functional in respect to judgmental equality, but I don't need to tackle this issue here).

This means, among other things, that the judgment
$$ x : \mathsf{empty} \vdash \mathsf{1} : \mathsf{nat} \to \mathsf{nat}  \qquad\qquad\qquad\qquad\qquad\qquad\quad (3)$$
is derivable in the theory, since there are no closed terms of the empty type (for the condition given is vacuously true). But also that less obvious judgments are also vacuously evident:
$$ x : \mathsf{nat} \times (\mathsf{nat} \to \mathsf{empty}) \vdash \mathsf{1} : \mathsf{nat} \to \mathsf{nat} \qquad\qquad\qquad\qquad (4)$$
since any closed term of $\mathsf{nat} \times (\mathsf{nat} \to \mathsf{empty})$ gives us a closed term of $\mathsf{empty}$, which should have none.

My question is:

  What is a nice way to implement a type checker for such a hypothetical judgments?

(I'm aware that the problem is undecidable in general, but in theory this should affect us only in the sense that we are unable to rule out all invalid judgments).

For simplicity, we can suppose that we already have a type checking algorithm for categorical judgments.

IMHO$-$and in the spirit of the universal introduction rule of predicate logic$-$the obvious type checking algorithm for (1) to say that it is valid whenever $$\vdash a[x_1,...,x_n/t_1,...,t_n] : [x_1,...,x_n/t_1,...,t_n]A$$ for a list of arbitraries closed terms $t_1 : A_1 ,..., t_n : A_n $ (since we can't possibly consider each closed term of such types). However, this algorithm is clearly unable to validate sequents such as (3), let alone (4).

There is a quick highly-inelegant fix, which is to add the condition that if you find $x : \mathsf{empty}$ in the context list, halt and automatically recognize the whole sequent as true. But what about not-so-evident vacuously evident judgments such as (4)?

Anyway, how would a correct, elegant and general approach look like?

PS: I'm sorry if the question is not precise enough, but I can't think of a better way to state it.

[1] Martin-Löf, Constructive Mathematics and Computer Programming, 1982.

Part of the problem is we cannot say that we have a checker for categorical judgments, because these often reduce to hypothetical judgments. For instance, the categorical judgment $M\in A\to B$ reduces to a hypothetico-general judgment.

In practice, the way that you implement this kind of type theory is by formalizing rules for hypothetico-general equality & membership as a kind of sequent calculus, and then you can write tactics that automate as much of the work as possible. This is the technique used in Nuprl, JonPRL and RedPRL, which all implement type theories of the kind that you describe in your post.


What is the coproduct: A + A? In the HoTT book, it is said

  The type of booleans 2 : U is intended to have exactly two elements. It is clear that we could construct this type out of coproduct and unit types as 1 + 1.

I don't see how this works, since it seems to me A + A = A, which would imply 1 + 1 = 1, and 1 != 2. What am I missing?  (Sorry for the brevity; I'm only able to work and read using a mobile device for this week).

The coproduct is the disjoint union. Set-theoretically, you can think of forming the coproduct of the sets $A$ and $B$ as:

$$
 A + B \;\;\triangleq\;\; \{ (0, a) \;|\; a \in A \} \cup \{ (1, b) \;|\; b \in B \}
$$

Now it should be obvious that $A + A \not= A$.


Is where an oracle B in EXP that $P^B$ $ \ne$ $NP^B$? According to Baker, Gill, Solovey where is an oracle A in EXP, so $P^A$ = $NP^A$. But is there an oracle B in EXP, what $P^B$ $\ne$ $NP^B$?

Yes, the Baker-Gill-Solovay B oracle is itself in EXP.


Combinatorial discrepancy of the system of all cuts This is a variant of this previous question. In the meantime I have learned that what I am really interested in is the discrepancy of the system of all cuts of the complete graph on $n$ vertices. More precisely, my ground set $X$ is the set of all 2-element subsets of $[n]=\{1,\ldots,n\}$, and I am looking at the set system which consists of the sets $S_U=\{\{i,j\}\in X\ :\ i\in U\text{ and }j\not\in U\}$ for all $U\subseteq[n]$. Is there a function $f:X\to\{1,-1\}$ such that

$$\forall U\subseteq[n]\ \left\lvert\sum_{\{i,j\}\in S_U}f(\{i,j\})\right\rvert=O(n)\,?$$

Choosing $f$ at random gives $O(n^{3/2})$ and I think that is also what follows from Spencer's 6 standard deviations theorem. But maybe one can do better by exploiting the cut structure.

I doubt you can do better than $O(n^{3/2})$. Here is a lower bound, using old arguments by Spencer and Erdos, that shows that the discrepancy is $\Omega(n^{3/2})$ if you expand the set system to cuts of induced subgraphs. See the edit for a lower bound for cuts as well, suggested by Domotor.

Let $V$ be the vertex set of the complete graph, and fix a function $f:{V \choose 2} \to \{-1, 1\}$. Split $V$ into $L$ and $R$, each of equal size. Let $S$ be a random subset of $L$. Then, for any $v \in R$,
$$
\mathbb{P}\left(\Bigl|\sum_{u \in S}{f(u, v)}\Bigr| \geq c\sqrt{n}\right) \ge 1/4,
$$
for a suitable constant $c$. (This can be proved using the Central Limit Theorem or a 4-th moment argument.) Letting $T_0$ be the subset of all $v \in R$ satisfying $\Bigl|\sum_{u \in S}{f(u, v)}\Bigr| \geq c\sqrt{n}$, we have that $\mathbb{E}|T_0| \geq n/8$. So there exists some choice of $S$ such that $T_0$ has size at least $n/8$: fix such an $S$ and pick $T = \{v \in R: \sum_{u \in S}{f(u, v)} \geq c\sqrt{n}\}$ or $T = \{v \in R: \sum_{u \in S}{f(u, v)}\leq -c\sqrt{n}\}$, whichever is larger. Clearly
$$
\Bigl|\sum_{u \in S, v \in T}{f(u,v)}\Bigr| \ge \frac{cn^{3/2}}{16}.
$$

EDIT: As Domotor pointed out in a comment the above suffices for a $\Omega(n^{3/2})$ lower bound on the discrepancy of cuts as well. Let $S$ and $T$ be the sets above, and $U = V \setminus (S \cup T)$. Define $f(X,Y) = \sum_{x \in X, y \in Y}{f(x,y)}$ for any two subsets $X,Y\subseteq V$. Assume without loss of generality that $f(S,T) \ge c'n^{3/2}$ for $c' = c/16$ (the case $f(S,T) \le -c'n^{3/2}$ is analogous). Then at least one of the cases below holds:

$f(S,U) \ge -c'n^{3/2}/2$ and $f(S, T \cup U) \ge c'n^{3/2}/2$;
$f(T,U) \ge -c'n^{3/2}/2$ and $f(S\cup U, T) \ge c'n^{3/2}/2$;
$f(S \cup T, U) = f(S, U) + f(T,U) < -c'n^{3/2}$.

In each case the discrepancy of some cut is $\Omega(n^{3/2})$.


Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...) Edit: I originally defined a regular function as a function computable by a Mealy machine, but Denis pointed out that that was a weaker model than what I was thinking of.

So to be more precise, by a "finite-state transducer" with input alphabet $A$ and output alphabet $B$, I mean a deterministic finite automaton over $(A \cup \{\epsilon\}) \times (B \cup \{\epsilon\})$.

In particular, if both of the following hold for a transducer, then the transducer computes a function:

Every transition $(q, (x,y), q')$ is uniquely determined by $q$ and $x$;
If there is a transition $(q, (\epsilon, x), q')$ for any $x$, then there are no other transitions from state $q$.

Feel free to generalize or restrict as desired.

Definitions:

Let $L$ and $M$ be languages. A regular function $f:L\to M$ is a function computable by a finite-state transducer $A$ such that $(l,m)\in L(A)$ if and only if $l \in L$ and $m=f(L)\in M$. Note that it is decidable whether the relation computed by a given FST is a function.

Define the equalizer $Eq(f,g)$ of two regular functions $f,g:A\to B$ as the set of all strings $x\in A$ such that $f(x)=g(x)=y$ for some $y\in B$.

"Theorem": The equalizer of two regular functions is regular.

"Proof": Since $f$ and $g$ are regular functions, they are also regular relations. In particular, we can take their intersection $h=f\cap g$. By definition, we have $(x,y)\in h$ if and only if $(x,y)\in f$ and $(x,y)\in g$; in function notation this becomes $(x,y)\in h$ iff $f(x)=g(x)=y$. By the closure properties of regular relations, it follows that $h$ is a regular relation; and since $f$ and $g$ are functions, $h$ is also a function.

Since $h$ is a regular relation, it is recognized by some finite state transducer $T$. We can take the input projection $\pi_1 T$, giving us a finite automaton which accepts a string $x$ if and only if $(x,y)\in h$ for some $y$. Let $E$ denote the language of the automaton $\pi_1 T$. By the definitions of $h$, $f$, and $g$, it follows that $x\in E$ if and only if $x\in A$ and $f(x)=g(x)=y$ for some $y\in B$. $\square$

But wait. Suppose $A$ is the set of all nonempty strings $\Sigma^+$ over some alphabet $\Sigma$, and suppose $f$ and $g$ are homomorphisms (every homomorphism is a regular function.) Then we can take the equalizer $P=Eq(f,g)$, which is regular by the above "theorem".

Now $P$ will be nonempty iff there is a string $x\in \Sigma^+$ such that $f(x)=g(x)$. In other words, $P$ encodes the Post correspondence problem (PCP) for $f$ and $g$.

But since $P$ is regular, it is recognized by some finite automaton, and emptiness is decidable for finite automata. Since intersection and projection are computable constructions on transducers, we therefore have a method to solve PCP given the transducers for the homomorphisms $f$ and $g$. But this is impossible since PCP is undecidable. So where am I wrong?

If you use Mealy machines, it forces your functions to be length-preserving, and therefore you cannot encode PCP with them.

Your regularity theorem holds with length-preserving functions.
If you want to allow length-increasing functions (that you need for PCP), you need a more powerful transducer model, for which undecidability quickly kicks in.


Formally proving no algorithm exists Are there standard techniques to show that no algorithms exist for given complexity constraints?

For example, consider the following problem. The input is a list of items with exactly one duplicate, and you wish to find the duplicate item.

How do you formally prove that there cannot be an algorithm that does this in constant space and linear time?

See this lower bound for sorting, for example:
http://planetmath.org/lowerboundforsorting

You typically need to assume something about the algorithm's access to the input data. In this case, the assumption is that the algorithm sorts via pairwise comparisons. Any such algorithm must make at least $\Omega(n\log n)$ such comparisons. This is because the pairwise comparisons effectively induce a binary tree on $n!$ leaves -- one leaf for each possible input ordering. Such a tree must have depth $\Theta(\log(n!))=\Theta(n\log n)$.

Note that in a different data access model, algorithms can achieve linear-time sorting:
https://en.wikipedia.org/wiki/Radix_sort

Obiously, faster than linear time is impossible, since you have to at least read all of the inputs.


Minimum cost cut with discount - what is the complexity? Consider an undirected graph $G=(V,E)$ with non-negative edge costs. Given an integer $k$ with $0\leq k\leq |E|$, let us call an edge set $C\subseteq E$ a $k$-discounted cut, if the following hold:

$C$ is a cut in the usual sense.
The cost of the $k$ most expensive edges in $C$ is changed to 0. (If $k\geq |C|$, then all edge costs in $C$ are changed to 0.) This cost reduction is the "discount." The cost of the $k$-discounted cut is the sum of the edge costs in $C$, after the cost reduction, i.e., the remaining cost after taking the discount.

Task: Given $k$, and the graph with edge costs,  find a  minimum cost $k$-discounted cut.

Question: Is anything known about this problem? Can it be solved in polynomial time?

Note: It is well known that the (conventional) minimum cost cut can be found in polynomial time. It is not clear, however, how the discount influences the complexity.

Consider the connectivity interdiction problem, which can be solved in polynomial time [1].

  (Unweighted) Connectivity interdiction

  Given a graph $G$ and integer $k$. Find a set $R$ of $k$ edges, such that the min-cut in $G-R$ is minimized.

Your problem is the same as this problem because $R$ is the $k$ discounted edges in the minimum $k$-discounted cut.

Zenklusen's paper discusses a more general weighted version of the problem. Each edge has a weight (independent from cost). $R$ is chosen so the weight is at most $k$. That problem admits a PTAS. The special case we care about is when the weights are all $1$, which is the case solvable in polynomial time.

Zenklusen, Rico, Connectivity interdiction,  ZBL06945298..


Is signing a message hash a valid replacement for blind signature? I didn't understand how the blind signature implementations work. But I devised my own way of doing it:

Alice would compose the message
Alice would calculate the hash of the message
Alice would hand the hash to Bob
Bob would sign it with his private key
Alice would hand the message and the signed hash to Carol
Carol would calculate the actual hash using the message
Carol would decode the signed hash with Bob's public key
Carol would compare the actual hash with the decoded hash

Wouldn't this algorithm replace the blind signature implementation as described in Wikipedia in every case?

Wouldn't this algorithm replace the blind signature implementation as described in Wikipedia in every case?

No, because hashing is a deterministic algorithm. Let M be Alice's message, and $H(\cdot)$ be the hash function.

In your algorithm, Alice passes H(M) to Bob, who can store H(M) for later reference. This way, Bob effectively creates a database of message hashes signed by him, as well as the ID of the user who asked for Bob's signature. Let $D = \{\langle H(M_1), ID_1 \rangle, \langle H(M_2), ID_2 \rangle, \ldots \}$ be this database.

On seeing a message-signature pair $(M, \sigma)$, Bob hashes M to H(M), and searches D for H(M). If H(m) is found, Bob can easily recover the ID of the user. Hence, this method does not blind the identity of the user.


Generalization of locally bounded treewidth graphs Is the following graph class known in the literature?

The class of graphs is parameterized by positive integers $d$ and $t$ and contains each graph $G=(V,E)$ such that for each vertex $v\in V$, the subgraph of $G$ induced on all vertices at distance at most $d$ from $v$ in $G$ has treewidth at most $t$.

It generalizes the concept of locally bounded treewidth, and it seems useful when searching for local structures in graphs.

The concept of exploiting properties that a graph possesses locally can be taken even further. Dawar, Grohe and Kreutzer in Locally Excluding a Minor considered classes of graphs that locally exclude a minor and Dvorak, Kral and Thomas in Deciding first-order properties for sparse graphs considered classes of graphs that have (locally) bounded expansion.

Both of those classes are subsumed by classes of nowhere dense graphs, introduced by Nesetril and Ossona de Mendez.

Grohe announced this week at the Highlights conference that Grohe, Kreutzer and Siebertz. have proved that every property of graphs definable in first-order logic can be solved in almost linear time on nowhere dense classes of graphs. This implies many fixed-parameter tractability results on nowhere dense graphs, e.g. for the (connected) dominating set and digraph kernel (both parameterized by the size of the solution), Steiner tree (parameterized by the size of the tree) and circuit satisfiability (parameterized by the depth of the circuit and the Hamming weight of the solution).


LP relaxation of independent set I've tried the following LP relaxation of maximum independent set

$$\max \sum_i x_i$$

$$\text{s.t.}\  x_i+x_j\le 1\  \forall (i,j)\in E$$
$$x_i\ge 0$$

I get $1/2$ for every variable for every cubic non-bipartite graph I tried.

Is true for all connected cubic non-bipartite graphs?
Is there LP relaxation which works better for such graphs?

Update 03/05:

Here's the result of clique-based LP relaxation suggested by Nathan

I've summarized experiments here  Interestingly, there seem to be quite a few non-bipartite graphs for which the simplest LP relaxation is integral.

Non-bipartite connected cubic graphs have the unique optimal solution $x_i = 1/2$; in a bipartite cubic graph you have an integral optimal solution.

Proof: In a cubic graph, if you sum over all $3n/2$ constraints $x_i + x_j \le 1$, you have $\sum_i 3 x_i \le 3n/2$, and hence the optimum is at most $n/2$.

The solution $x_i = 1/2$ for all $i$ is trivially feasible, and hence also optimal.

In a bipartite cubic graph, each part has half of the nodes, and the solution $x_i = 1$ in one part is hence also optimal.

Any optimal solution must be tight, that is, we must have $\sum_i 3 x_i = 3n/2$ and hence $x_i + x_j = 1$ for each edge $\{i,j\}$. Thus if you have an odd cycle, you must choose $x_i = 1/2$ for each node in the cycle. And then if the graph is connected, this choice gets propagated everywhere.


Graph addition chains An addition chain for $n \in \mathbb{N}$ is a sequence of natural numbers
$$1 = a_0,\ldots,a_l =n$$
such that each $a_t$ is the sum of two previous elements in the sequence. The length of minimal addition chains for natural numbers has been studied intensely.

I wonder if "graph addition chains" have been studied, most probably under different names. For a graph $G$, a graph addition chain could be a sequence of graphs
$$G_0,\ldots,G_l =G$$
such that $G_0$ is contained in some set $\mathcal{F}$ of elementary graphs, and each $G_t$ is some sum of two previous elements. Depending on $\mathcal{F}$ and the sum operation, one could ask about the length of minimal graph addition chains (if they exist).

As an example, set $\mathcal{F} = \{K_{k+1}\}$ and let the sum operation be the $k$-sum of graphs. Graph addition chains with these parameters produce partial $k$-trees, and we ask to construct partial $k$-trees using the minimal number of $k$-sums. For $k=1$, graph addition chains for path graphs correspond to addition chains for natural numbers, making this problem already $NP$-hard.

I would be thankful for any references to algorithmic and structural results about this or related concepts.

Sequences of colored graphs under the operations of disjoint union (a form of graph addition), recoloring, and adding edges between all vertices with some color combination form the basis for the definition of clique-width. However, the quantity of interest for measuring the complexity of such a sequence is not the number of operations needed, but the number of colors.


Results about computability power or limitations of shared read/write registers I want to know more results about the computability power or limitations of shared $\texttt{read/write}$ registers/objects in distributed/concurrent computing theory.

Two typical examples are:

[1]. All types of atomic $\texttt{read/write}$ registers are equivalent in terms of computability: we can simulate the most complex one (i.e., multi-writer multi-reader multi-value atomic register) using the simplest ones (i.e., single-writer single-reader binary atomic registers).

[2]. Atomic $\texttt{read/write}$ registers have consensus number $1$. Therefore, from a set of atomic registers, it is impossible to construct a wait-free implementation of stack, queue, test&set, compare&swap, or memory-to-memory swap.

[1] "The Art of Multiprocessor Programming (book abstract)" by Maurice Herlihy and Nir Shavit, 2008.

[2] "Wait-Free Synchronization" by Maurice Herlihy, ACM Transactions on Programming Languages and Systems, 1991.

  Do you know any other results about the computability power or limitations of shared $\texttt{read/write}$ registers in distributed/concurrent computing theory?

Pointers to the literature would be appreciated.

You might want to look at the work of Gadi Taubenfeld. Many of his papers deal with  impacts of different progress conditions such as (generalized) wait-freedom or obstruction-freedom on the computability power of shared objects in distributed systems, which includes registers.


Is MLTT effectively pCiC without Prop? Is Martin-Löf type theory basically the predicative Calculus of inductive Constructions without impredicative $\mathtt{Prop}$?

If they're closely related but with more differences than just $\mathtt{Prop}$, what are those differences?

The short answer is yes, MLTT can reasonably be equated with CIC without impredicative Prop.

The main technical issue is that there are dozens of variants when one talks about Martin-Löf Type Theory and, perhaps more surprisingly, when one talks about CIC. For example, taking the version of CIC defined in Benjamin Werner's thesis, it doesn't even make sense to remove Prop, as one doesn't have either Set or universes of Type.

The main variations one can consider in either of these theories are:

Universes: how many, and how are they defined (Palmgren, On Universes in Type Theory, discusses many inequivalent variations), and whether or not universe polymorphism is admitted.
Which inductive types/families: Agda admits Inductive-Recursive types, but there are many more mundane variations depending on how "large" the types in the constructors and eliminators are allowed, handling parameters vs indices, etc.
Injectivity of type constructors. This leads to a system inconsistent with EM in Agda. Of course Epigram has a more extreme "Observational Type Theory", but this can be considered something different altogether.
Axiom K: this comes for free with certain versions of dependent pattern matching.
Intentional vs Extensional: this is a huge difference, where essentially a new conversion rule is added in the extensional systems
$$ \frac{\Gamma\vdash t:\mathrm{Id}_{\mathrm{Type}}\ A\ B }{\Gamma\vdash A\ =\ B} $$
Which makes type-checking undecidable (but much more powerful!). Martin-Löf himself seems to have considered both types of systems.
The presence of coinductive types and associated elimination principles.

All of the above variations (except OTT) have been considered in the literature and associated with the name "Martin-Löf Type Theory" or "Calculus of Inductive Constructions", mostly because of their association with the Agda and Coq systems, respectively.

So the long answer is that there is no consensus about what the exact definition of either of these systems is.


Finding a set which dominates the Minimum Dominating Set Given an unweighted, undirected graph, a dominating set $S$ is a set of nodes such that every node is in $S$ or adjacent to a node in $S$.

The dominating set problem is NP-hard, but I am considering a new variation.
Given $k$, the size of the minimum dominating set, I need to find a set of nodes $T$ of size at most $k$ such that there exists a minimum dominating set $S$ in the graph which is dominated by $T$. That is, every any node in $S$ should be in $T$ or adjacent to a node in $T$.

My attempt:
The following is an algorithm I came up with that I have not proven or found a counterexample for.
At the start, all nodes are unmarked.

1) Pick an unmarked node $v$ as a center and mark everything within 2 hops of $v$. EDIT: Instead of picking an arbitrary unmarked node in this step, select the node that would cause the least number of nodes to be marked.

2) Repeat step 1 until all nodes are marked. (Note, this will never place more than $k$ centers)

3) If we have picked less than $k$ centers, keep placing centers on undominated nodes until we have placed $k$ centers.

I have proved that the above algorithm finds a set of centers which dominates a minimum dominating set, under the condition that we don't place any centers in step 3. That is, the algorithm works if steps 1 and 2 manage to place exactly $k$ centers.

Any ideas for whether this algorithm works or a counterexample?

The algorithm previously proposed in the post (before the current edit), does not work.

Here are the problem and algorithm proposed in that version of the post:

input: graph $G=(V,E)$ and the minimum size $k$ of any dominating set in $G$

output: a set of $k$ nodes that dominates a dominating set of size $k$

  algorithm$(G,k)$:

  At the start, all nodes are unmarked.

  1) Pick an unmarked node $v$ as a center and mark everything within 2
  hops of $v$.  [This step was edited and differs in the current post.]

  2) Repeat step 1 until all nodes are marked. (Note, this will never
  place more than $k$ centers)

  3) If we have picked less than $k$ centers, keep placing centers on
  undominated nodes until we have placed $k$ centers.

  Lemma. The algorithm above doesn't work.

Proof. Consider the counter-example $G=(V,E)$ where

$V=\{a, b, c, d, e, f\}$
$E=\{(a, b), (a, c), (a, d), (b, e), (c, f), (d, f)\}.$

The (unique) minimum dominating set is $\{b, f\}$, with size $k=2$.

The algorithm can place a center on $v=a$ in Step 1 (marking all nodes), then place a center on $e$ in Step 3.  This returns a set $\{a, e\}$ of two centers, neither of which dominates $f$ (which is in the only dominating set of size $2$). $~~~\Box$


Why does Coq have Prop? Coq has a type Prop of proof irrelevant propositions which are discarded during extraction. What are the reason for having this if we use Coq only for proofs. Prop is impredicative, so Prop : Prop, however, Coq automatically infers universe indexes and we can use Type(i) instead everywhere. It seems Prop complicates everything a lot.

I read that there're philosophical reasons for separating Set and Prop in Luo's book, however, I didn't find them in the book. What are they?

$\mathtt{Prop}$ is very useful for program extraction because it allows us to delete parts of code that are useless. For example, to extract a sorting algorithm we would prove the statement "for every list $\ell$ there is a list $k$ such that $k$ is ordered and $k$ is a permutatiom of $\ell$". If we write this down in Coq and extract without using $\mathtt{Prop}$, we will get:

"for all $\ell$ there is $k$" will give us a map sort which takes lists to lists,
"such that $k$ is ordered" will give a funciton verify which runs through $k$ and checks that it is sorted, and
"$k$ is a permutation of $\ell$" will give a permutation pi which takes $\ell$ to $k$. Note that pi is not just a mapping, but also the inverse mapping together with programs verifying that the two maps really are inverses.

While the extra stuff is not totally useless, in many applications we want to get rid of it and keep just sort. This can be accomplished if we use $\mathtt{Prop}$ to state "$k$ is ordered" and "$k$ is a permutation of $\ell$", but not "for all $\ell$ there is $k$".

In general, a common way to extract code is to consider a statement of the form $\forall x : A \,.\, \exists y : B \,.\, \phi(x, y)$ where $x$ is input, $y$ is output, and $\phi(x,y)$ explains what it means for $y$ to be a correct output. (In the above example $A$ and $B$ are the types of lists and $\phi(\ell, k)$ is "$k$ is ordered and $k$ is a permutation of $\ell$.") If $\phi$ is in $\mathtt{Prop}$ then extraction gives a map $f : A \to B$ such that $\phi(x, f(x))$ holds for all $x \in A$. If $\phi$ is in $\mathtt{Set}$ then we also get a function $g$ such that $g(x)$ is the proof that $\phi(x, f(x))$ holds, for all $x \in A$. Often the proof is computationally useless and we prefer to get rid of it, especially when it is nested deeply inside some other statement. $\mathtt{Prop}$ gives us the possibility to do so.

Added 2015-07-29: There is a question whether we could avoid $\mathsf{Prop}$ altogether by automatically optimizing away "useless extracted code". To some extent we can do that, for instance all code extracted from the negative fragment of logic (stuff built from the empty type, unit type, products) is useless as it just shuffles around the unit. But there are genuine design decisions one has to make when using $\mathsf{Prop}$. Here is a simpe example, where $\Sigma$ means that we are in $\mathsf{Type}$ and $\exists$ means we are in $\mathsf{Prop}$. If we extract from
$$\Pi_{n : \mathbb{N}} \Sigma_{b : \{0,1\}} \Sigma_{k : \mathbb{N}} \; n = 2 \cdot k + b$$
we will get a program which decomposes $n$ into its lowest bit $b$ and the remaining bits $k$, i.e., it computes everything. If we extract from
$$\Pi_{n : \mathbb{N}} \Sigma_{b : \{0,1\}} \exists_{k : \mathbb{N}} \; n = 2 \cdot k + b$$
then the program will only compute the lowest bit $b$. The machine cannot tell which is the correct one, the user has to tell it what he wants.


How to be formal while writing papers? I am just beginning my second year of PhD. While my advisor is largely happy with my progress and work, there seems to be a recurring point in our discussions that I need to be more formal in my writing. Until now, he has been happy to help me formalize my arguments and proofs but this is clearly something I am struggling with.

Any advice on how to be more formal while writing papers? The obvious answer is to read a lot of papers and try to re-create proofs by writing them down. I seem to do that relatively well but the writing itself is a problem for me.

Sure, here's a basic checklist. It would make for a very dry read to actually follow these to the letter, but maybe you should first try to write extremely formally, then see where it's reasonable to relax the writing without risk of misunderstanding or vagueness.

Preface. The high-level goal of formality is to make your proof closer to "machine-checkable". You want to allow people of a variety of different backgrounds, knowledge levels, abilities, and intuitions to be able to read your definitions, claims and proofs, understand what they say, and verify that they are correct.

Just as a computer cannot execute a program that is vague and skip steps, so it is difficult for a human to verify a proof with the same flaws.

However, a caveat is that mathematical formality is not perfectly aligned with conveying understanding. Notice I said "verify" above, not "understand". But even if the goal is to convey understanding, it is important to at least be able to formalize what one writes, since you want to convey to others the ability to formalize it.

Define terminology and notation precisely. For example, this is informal:

  each vertex gets a weight $w_v$ whenever it gets matched, and $W$ is
  the total of all the weights.

This is formal:

  the graph $G$ has a set of vertices $V$. For each vertex $v \in V$, the algorithm is given its weight $w_v$. For an algorithm $A$, let $S_A \subseteq V$ be the vertices matched by $A$. $S_A$ is a random variable depending on the random choices of $A$. Let $W_A = \mathbb{E} \sum_{v \in S_A} w_v$ where the expectation is over the randomness of $A$.

Why bury ourselves in so much notation? For one thing, notice that in the formal rewrite, we realized $W$ wasn't well-defined because it depended on the algorithm (and even its randomness), so we had to introduce and define notation to capture that. We had to introduce notation $S_A$, but it will come in handy later anyway.

Try not to feel frustrated or annoyed if things that sound simple take up a lot of space and require a lot of notation when written formally. Don't think of this as dirty work, think of it as a valuable part of the process to deeply understanding what you're writing.

Do not use a technical term if you have not defined it yet, and do not use nontechnical terms in a technical discussion or proof. For example, do not say "because $G$ is an expander, ..." as part of a step of a proof if a precise definition of expander has not yet appeared. But it's okay to say "intuitively, $G$ is acting like an expander". Do not say as part of a proof, "if the algorithm has made enough matches, then ..." unless you have precisely defined what that means. Better is to define a threshold $R(t)$ at each time $t$, then say "if the number of matches at time $t$ is at least $R(t)$, then...."
State results precisely using a logical sentence. Any proposition / lemma / theorem should really be a logical sentence such as "For all $x$ such that $P(x)$, there exists $y$ such that $Q(x,y)$. For example, "There exists a constant $c$ such that the following holds: For all input graphs on $n$ nodes, there exists $m$ such that Algorithm 4 runs in $m$ steps and $m \leq c n^3$."

First make sure you can write the result you are stating in this form, then see if you're willing to relax it to someting like "Algorithm 4 runs in time $O(n^3)$ on graphs of $n$ vertices". I would avoid something like "Algorithm 4 runs in cubic time" since it's unclear (cubic in what?).
Understand what a "step" of a proof is and use them well. A step in the proof starts with what has already been shown so far and applies a simple, known fact, axiom, or result (properly cited/stated) to get a new statement. For example, if we have already shown that $M \leq (1+x)^n$, then we can apply the fact that $1+x \leq e^x$ for all $x$ to deduce $M \leq e^{nx}$.

Even there I left out a step: $(e^x)^n = e^{nx}$. When in doubt, do not omit any step bigger than that. You can always cut them down later.

Your proof should be a sequence of steps of this kind, where the first step only uses assumptions stated in the claim, each step uses only statements shown in previous steps, and the last step derives the statement in the claim.

You should also split proofs into lemmas and so on, but that's beyond my scope.
In particular, each step should be short and easy to follow. If you are trying to write formally as a beginner, don't skip a bunch of lines of calculation and expect the reader to trust you. (If for some reason you do, at least tell the reader that's what you're doing!) The reader should be able to see immediately why this step is correct.

A big mistake beginning proof-writers make (also experienced ones) is to not bother writing why a seemingly-obvious step is true. This is a big red flag. Sit down and go through the math convincing yourself why that "obvious" step is true, then put that into the proof! Do not ever write "clearly" or "obviously". Give me the fact for why it's clear ("Because probabilities are at most $1$, $\sum p_i \leq n$").
When you proofread, do so extremely slowly, carefully, and pretend you're explaining to someone who has never seen your paper. Read it out loud if you have to. If you proofread in your head fast, you're just reminding yourself of what you intended it to say. A step or definition left out of the paper won't be noticed because it will still be in your head. You want to check that each sentence makes sense given (only) what came before it.


Variants of Cluster-Vertex-Deletion problem The Unweighted Cluster-Vertex-Deletion problem is the following:

Input: An undirected graph G = (V, E) and a nonnegative number k

Output: Is there a subset X ⊆ V with |X| ≤ k such that deleting all vertices in X from G results in a cluster graph (i. e., a graph where every connected component forms a complete graph)?

This problem is NP-Complete.
More information can be found here:
Fixed-Parameter Algorithms for Cluster Vertex Deletion where FPT algorithms are given for a more general problem.
In particular, for a weighted version of d-Cluster-Vertex-Deletion where $d$ is a parameter that limitates the number of cliques to be generated, they developed three algorithms with running times: $O(2^k \cdot k^9 + nm), O(1.40^k \cdot k^{3d} + nm)$ and $O(1.84^{k+d} + nm)$.

I was wondering if it there is some known result for the case where $G \setminus X$ is a disjoint union of exactly 2 cliques, or the case where $G \setminus X$ is a disjoint union of p-defective cliques (cliques that misses at most p edges) in both cases (exactly two p-defective cliques or any number of p-defective cliques). I am specially interested in algorithmic results such as FPT or approximation algorithms developed for any of these variants.

I couldn't found anything but I suspect there is some results on this or maybe can be mapped from some other very well studied problem.

Thanks in advance

Edit:
Adding to the useful answers, here is a paper that I've recently found and show NP-Hardness of the variant separating in exactly two cliques (but for a weighted case).
Approximating clique and biclique problems

It seems to me that the case where G\X is a disjoint union of exactly two cliques has an FPT algorithm with runtime $O^*(3^k)$.

Here's what the algorithm would do.

If $k \leq 0$ then output YES if and only if G is a disjoint union of two cliques.
If the input graph contains an induced path on three vertices ($P_3$), then at least one of these three vertices need to be deleted to turn the graph into a cluster graph. Thus we branch in three ways depending on a choice of vertex, decreasing the parameter by 1 in each branch. Output the OR of the recursive calls.
If the graph is induced $P_3$-free, it is a cluster graph. If there is only 1 clique in this cluster graph: output NO. If there are two cliques in this cluster graph: output YES. If there are more than 2 cliques: sum the number of vertices in all but the two largest cliques. If this number is more than k, then output NO (all those vertices need to be deleted to reduce the number of cliques to 2, but we can't afford this). If the sum is at most k, output YES.

The approach generalizes to obtaining a cluster graph with exactly $\ell$ cliques for any value of $\ell$.


How can I find tight asymptotic bounds for this half-history recurrence relation? The recurrence relation $\forall n\in\mathbb{N}\cup\{0\}$ is $T(n)=\Theta(n^2)+2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}{T(i)}$, with base case of $T(0)=0$.

Fairly simple tree analysis shows that $T(n)\in\Omega(n^3)$ and $T(n)\in O(n^{\log_2{n}})$.

But I want to find $f(n)$ for which $T(n)\in\Theta(f(n))$, or at least tighter lower and upper bounds.

It is $n^{\Theta(\log n)}$, although I'm not sure exactly what the constant in the theta is. For the upper bound (the one you already have), note that, even without the $n^2$ term but with a base case of $1$ rather than $0$, this recurrence is dominated term-by-term by the recurrence
$$U(n)=nU(\frac{n}{2}).$$
For the lower bound, note that it dominates the recurrence
$$L(n)=\frac{n}{2}L(\frac{n}{4}).$$


Are there any schools with researchers interested in cellular automata? I have been working on an independant project focusing on cellular automata and was wondering if this might be something that I could continue on in graduate school somewhere. I've seen some mathematics departments with symbolic dynamics as well as a few CS departments with researchers interested in CA. The list is small though. If anyone knows which departments to look at and/or any specific faculty/programs to look at then I would greatly appreciate it.

Also, my project is sort of taking on a "mathematical" flavor and I was wondering if it would be better to look into mathematics over computer science departments, or is it generally pretty easy to do this type of thing in either.

The AUTOMATA workshop series focuses on cellular automata:

http://www.eng.u-hyogo.ac.jp/eecs/eecs12/automata2014/


FPRAS for Perfect Matching If you have FPRASes for counting number of matchings of size $\leq n$ and size $\leq n-1$,
can you get an FPRAS for counting number of matchings of size $n$ (i.e perfect matchings)?

No. Knowing $x$ and $y$ to within multiplicative error bounds of $1\pm\varepsilon$ does not give you a multiplicative error bound on $x-y$. In particular, if $x=y$, being allowed only multiplicative error means that an FPRAS for $x-y$ would have to return exactly zero with probability at least $\tfrac34$, whereas you could end up returning any value $v$ such that $|v|\leq 2\varepsilon\cdot |x|$.


Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$? There are assumptions that are known to imply that $P = BPP$. For example, if there exists a function in $E = DTIME(2^{O(n)})$ that has circuit complexity $2^{\Omega(n)}$, then $P = BPP$ [1]. Clearly, such a result would also imply that $P = ZPP$.

Is there an assumption that is known to imply $P = ZPP$ but is not known to imply that $P = BPP$? Alternatively, is there a reason to believe that such a result is unlikely to exist?

[1] Impagliazzo, Russell, and Avi Wigderson. "P= BPP if E requires exponential circuits: Derandomizing the XOR lemma." Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. 1997.

I think it is "easy" to come up with an assumption that implies one but not necessarily the other... (just write down a condition that is equivalent to P=ZPP)... however, a "natural" and non-uniform assumption (e.g. some weak form of PRG) seems harder, since (for example) hitting set generators (the non-uniform thing you need for P=RP) imply pseudorandom generators (what you need for P=BPP).

Just to give an idea of how annoying the problem is, here is a "natural" non-uniform condition that implies P=ZPP but (oops) also implies hitting sets, so it also implies P=BPP.

Say a circuit pair $(C,C')$ is good for length $n$ if $C$ and $C'$ have the same number of inputs, and for every input $x$ of length $n$,

$(Pr_y[C(x,y)=1]>2/3 \wedge Pr_y[C'(x,y)=0]=1)$ XOR $(Pr_y[C'(x,y)=1]>2/3 \wedge Pr_y[C(x,y)=0]=1)$.

Intuitively, these pairs can model any $RP \cap coRP = ZPP$ function.

To prove $P=ZPP$, it would suffice to have for all $\epsilon > 0$, a polynomial time function which given $1^n$, prints a set $S$ of $poly(n)$ strings of length up to $n$ such that for all circuit pairs $(C,C')$ with size $n$ that are good for length $m=n^{\epsilon}$, and all $x$ of length $m$, $(\exists y \in S)[C(x,y)=1 \vee C'(x,y)=1]$. (This should suffice, since by definition of "good", for all $x$, it cannot be that both $C$ and $C'$ have some input $y$ making them accept. I set $m=n^{\epsilon}$ to keep the condition from being too strong for other reasons.)

The main point is that the hitting set $S$ above "only" has to work for good circuit pairs. Nevertheless, this constraint isn't enough to keep from getting a full hitting set. Consider any circuit $C$ with $\Pr_x[C(x)=1]>2/3$. Write the inputs of $C$ over "$y$-variables" instead of $x$-variables. Look at the circuit pair $(0,C)$, where $0$ is the circuit which outputs zero on all inputs $(x,y)$. This pair trivially satisfies the goodness condition ($C$ and $0$ have the same behavior on all inputs $x$, because they do not depend on $x$ at all). And if there is always an $a \in S$ such that $[C(x,a)=1 \vee 0(x,a) = 1]$ is true, then $S$ is just a hitting set.

You could try to require some "non-trivialness" condition on top of that (say that each circuit in the pair can't be trivial), but the patches I can think of could also be circumvented.

It would be interesting if there is a more general way to formalize this problem, so that one could convincingly show that any hitting set for anything resembling "ZPP circuits" is just a hitting set.


Minimum weight subforest of given cardinality This question was motivated by a question asked on stackoverflow.

Suppose you are given a rooted tree $T$ (i.e. there is a root and nodes have children etc) on $n$ nodes (labelled $1, 2, \dots, n$).

Each vertex $i$ has a non-negative integer weight associated: $w_i$.

Additionally, you are given an integer $k$, such that $1 \le k \le n$.

The weight $W(S)$ of a set of nodes $S \subseteq \{1,2,\dots, n\}$ is the sum of weights of the nodes: $\sum_{s \in S} w_s$.

  Given input $T$, $w_i$ and $k$,

  The task is to find a minimum weight
  sub-forest* $S$, of $T$, such that $S$
  has exactly $k$ nodes (i.e. $|S| =
> k$).

  In other words, for any subforest $S'$ of $T$, such that $|S'| = k$, we must have $W(S) \leq W(S')$.

If the number of children of each node were bounded (for instance binary trees), then there is a polynomial time algorithm using dynamic programming.

I have a feeling that this is NP-Hard for general trees, but I haven't been able to find any references/proof. I even looked here, but could not find something which might help. I have feeling that this will remain NP-Hard even if you restrict $w_i \in \{0,1\}$ (and this might be easier to prove).

This seems like it should be a well studied problem.

  Does anyone know if this is an NP-Hard problem/there is a known P time algorithm?

*A sub-forest of $T$ is a subset $S$ of nodes of the tree $T$, such that if $x \in S$, then all the children of $x$ are in $S$ too. (i.e. it is a disjoint union of rooted sub-trees of $T$).

PS: Please pardon me if it turns out that I missed something obvious and the question is really off-topic.

Similar to the solution for a binary tree, you can solve it in polynomial time on a tree without degree restriction:
First, generalize the problem such that every node also has a "count" $c_i\in\{0,1\}$, and the problem is to find a subforest $S$ of count $k=\sum_{i\in S} c_i$.
Generalize the dynamic programming approach to this version (it still works with a table, given a fixed count $C$, what is the minimal weight subforest in the subtree having count precisely $C$)

Keep the original tree with nodes of count 1.  Every node $v$ with degree greater than 2 is split into a binary tree with deg$(v)$ leaves (the shape does not matter).  The new nodes have count and weight 0. Solve the problem on the new tree. When reading out the solution ignore any new node; this will still be a subforest of the same weight.  Because any original subforest translates into a new subforest of the same weight, the found subforest is optimal.


Universal Approximation - Are ReLUs discriminatory? In Cybenko's elegant proof of the Universal Approximation Theorem (UAT) he proves that single hidden layer neural networks (with linear output layer) are universal approximators whenever their activation functions are (what he calls) discriminatory. He then shows that bounded measureable sigmoidal functions are discriminatory, completing the proof. In particular, continuous sigmoidal functions work as well.

Later Leshno et al. proves that locally bounded piecewise continuous (l.b.p.c.) activation functions yield the UAT if and only if they are nonpolynomial.

My Question(s):

What kinds of functions are discriminatory? Polynomials certainly aren't (Leshno et al.) and continuous sigmoids are (Cybenko).  Are ReLUs discriminatory?

Together, the above results imply that for l.b.p.c. functions, that discriminatory implies non-polynomial. Is the converse true?

Yes, ReLUs are discriminatory. See for example the nice, simple proof in Lemma 3.15 of these notes by Leonardo Ferreira Guilhoto:
http://math.uchicago.edu/~may/REU2018/REUPapers/Guilhoto.pdf

Regarding whether an unbounded function like a ReLU can be discriminatory, note that you can construct a bounded, continuous function as the difference of two ReLUs:

$f(x) = ReLU(W x + b_1) - ReLU(W x + b_2)$

and an appropriate choice of $b_1, b_2$ makes this difference f a sigmoidal function, as defined in Cybenko, so function f is discriminatory.

By definition a function is discriminatory if the zero measure is the only signed Borel measure $\mu$ such that:

$\int f(W x + b) d \mu (x) = 0$
for all W, b

Applying this to the difference of ReLUs above shows that both integrals over each ReLU must have measure zero if integral of f has measure zero.


Cheap online selection with weighted comparisons Suppose we want to find the smallest element of a set $S$, whose elements are indexed from $1$ to $n$.  We do not have access to the values of these elements, but we can compare any two elements of $S$ to see which one is smaller.  For any indices $i$ and $j$, there is an associated cost $C_{i,j}$ to compare the $i$th and $j$th elements of $S$.  The complete cost matrix $C_{i,j}$ is given to us in advance.

It is well known that $n-1$ comparisons are necessary and sufficient to find the smallest element of $S$.  However, since each comparison may have a different cost, we also want to keep the total cost of the comparisons as small as possible.

Is there an online algorithm that finds a sequence of comparisons of small total cost that finds the smallest element of $S$?  There is no online algorithm that finds the set of comparisons with minimum total cost, even when $n=3$, but perhaps there is an online algorithm with small competitive ratio.

In particular, does allowing the online algorithm to perform more than $n-1$ comparisons help?  Is it better to make several "extra" cheap comparisons instead of a few expensive comparisons?

I am especially interested in the case $C_{i,j} = 4^{d(i,j)}$, where $d$ is a discrete metric over the set $S$, and $0 \le d(i,j) \le k$, for all $i,j$.  An optimal online algorithm is still impossible in this setting.

Any references to similar problems are appreciated. I'm not searching for someone to solve my problem (although some ideas may help and are appreciated).  I just want to know if this problem is known. (I couldn't find anything.)

Brute-force case analysis reveals that the optimal competitive ratio for the special case  $n=3$, with no other restrictions on the cost matrix, is the golden ratio $\phi = (\sqrt{5}+1)/2$.  Thus, no online algorithm can achieve a competitive ratio better than $\phi$.

Suppose $C_{1,2}=0$, $C_{1,3}=1$, and $C_{2,3}=\phi$.

Without loss of generality, the algorithm starts by comparing $S_1$ to $S_2$, at cost zero.
The adversary declares $S_1 > S_2$.
If the algorithm compares $S_1$ to $S_3$:

The adversary declares $S_1 > S_3$.
The algorithm must compare $S_2$ and $S_3$.
The adversary declares $S_2 < S_3$, so $S_2$ is the minimum.
The total cost of the algorithm's comparisons is $1+\phi$.
The adversary reveals the total order $S_2 < S_3 < S_1$.
The total cost of the optimal comparisons ($S_1>S_2$ and $S_2<S_3$) is $\phi$.

If the algorithm compares $S_2$ to $S_3$:

The adversary declares $S_3 > S_2$, so $S_2$ is the minimum.
The total cost of the algorithm's comparisons is $\phi$.
The adversary reveals the total order $S_2 < S_1 < S_3$.
The total cost of the optimal comparisons ($S_1>S_2$ and $S_1<S_3$) is $1$.

In either case, the algorithm's comparisons cost a factor of $\frac{1+\phi}{\phi} = \frac{\phi}{1} = \phi$ more than the optimal set of comparisons for the revealed total order.

More generally, the competitive ratio is $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$, where $a\le b\le c$ are the three comparison costs.  (There are more cases to consider here, because there are optimal algorithms that do not perform the cheapest comparison first, but the case analysis is still elementary.)  Tedious calculations imply that the expression $\min\{\frac{a+c}{a+b} , \frac{a+b+c}{a+c}\}$ is maximized when $a=0$, $b=1$, and $c=\phi$.

In particular, if $\frac{a+c}{a+b} > \frac{a+b+c}{a+c}$, the best possible algorithm can be forced to perform all three comparisons.


Reduction graph to planar bounded treewidth and bounded diameter graph We got reduction graph to planar bounded treewidth graph,
but this is unlikely to be true.

Let $H$, the planarizing gadget, be planar graph with four
distinguished vertices $u,u',v,v'$ on the outer faces.

Take graph $G$ drawn on the plane. Add new vertex $S$,
adjacent to all vertices of $G$. So far the diameter is
at most two.

Replace each pair of crossing edges $(u,u'),(v,v')$ by
new copy of the gadget $H$.

The resulting graph $G'$ is planar with diameter $D = 2\max(d(u,u'),d(v,v'))$
where $d$ is the distance in $H$.

The treewidth of $G'$ is $O(D)$, which is constant for fixed $H$,
for reference see here.

Similar reduction with specially chosen $H$ is used to show
NP-hardness of problems for planar graphs.

  What is wrong with this reduction?

Correctness of the reduction is unlikely, because for
bounded treewidth graphs a lot of graph invariants are
computable in polynomial time and choosing suitable
gadget $H$ might give relation between invariants
of $G$ and $G'$, implying $P=NP$.

Another reference claims
"bounded genus graphs of bounded diameter have bounded treewidth".

The diameter of $G'$ will not be bounded. Replacing edge crossings with gadgets can effectively cut each edge $O(n)$ times, so the diameter can blow up by a factor of $O(n)$.


What is mathematical difference between "random" and "unique"? Once in a while when a question like "how I get good random numbers" is asked the suggested approach is to just generate an UUID. UUID looks like a random number and it is designed in such way that UUIDs likely never repeat - it is unique.

What is mathematical difference between "unique" and "random"? Why exactly should UUID not be used as a random number - for example as a cryptographic key?

When you say random numbers you want to have a series of numbers such that given any sequence of $i-1$ numbers, the probability of the $i$th number having a certain value is independent from all its predecessors (I (over)simplify here), i.e.

$\begin{equation*}Pr[n_i = k \mid n_0, \dots, n_{i-1}] = Pr[n_i = k]\end{equation*}$

Unique numbers can be generated without having to guarantee that (e.g. just counting upwards yields unique numbers). These kinds of unique numbers can be guessed, which make them bad random numbers.

In fact, most things that are called random-number generators in practice are pseudo-random-number generators. That means that they have a perfectly deterministic and predictable algorithm of constructing the next number but they start with a secret seed that changes from application to application. Without knowing that seed the generated series have many properties of true random sequences. That can be checked by certain statistical methods.

In most practical, every-day scenarios you want to have unguessable sequences, e.g. for password creation. Pseudo-random-number generators are fine for that provided you choose a proper seed; many people use the system timestamp when the request comes in, assuming this is pretty hard to predict up to the millisecond. If you really need the statistical properties of random sequences, for example for Monte Carlo simulations, you should be more wary.

Edit: To clarify: Random sequences (R) and unique sequences (U) are not opposing concepts; you can have all combinations of both:

R, !U: roll die (or observe other allegedly random event, see random.org)
R, U: roll a die with lots of sides and reject duplicates ( or roll many dice)
!R, U: use any bijective enumeration scheme, e.g. $f(n) = n$
!R, !U: $1,1,1,\dots$ (also: PRNG)


Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines? Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

Background: I recently stumbled upon the dissertation "Computational complexity of multitape Turning machines and Random Access Machines" by Takumi Kasai (see here: https://repository.kulib.kyoto-u.ac.jp/dspace/handle/2433/86527).
As far as I can tell, the author shows that there exists a function $g$ such that $g$ can be computed in $O(n)$ time by RAM machines, but cannot be computed in $O(n^{2-\varepsilon})$ time by Multitape Turing machines for all $\varepsilon > 0$.
Can this result be extended to deciding languages (instead of computing functions)?  In other words, can we prove that there is a language decidable in $O(n)$ time by RAM machines that cannot be decided in $O(n^{2-\varepsilon})$ time by Multitape Turing machines for all $\varepsilon > 0$?

It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a longstanding open problem.
The reason is that there is a very efficient reduction from linear time on RAMs to SAT (in general, nondeterministic quasi linear time on RAMs is the same as nondeterministic quasi linear time on multitape TMs.)
I have never seen the above reference before, and I would be skeptical if it never appeared in a journal or conference, but it could be worth checking to see if it implies a SAT lower bound as well. Interesting find!

UPDATE: I looked at the paper at your link above briefly this morning. The claimed hard function is a complicated partial match query problem. Essentially there is a notion of a "string pattern" and one is given a bunch of binary strings and asked to determine which strings fit the pattern (and which don't). Let me write out the definition of the function, as I understand it. I will use different symbols and terminology to try to make the definition easier to understand.
The set of "string templates" (the author's $U$, Definition 5.1) is a set of strings over $\{0,1,end,branch\}$, defined recursively:

$end \in U$
$\alpha \in U$ implies $0\alpha, 1\alpha \in U$
$\alpha, \beta \in U$ implies $branch~ \alpha \beta \in U$.
Note that every string ends in an $end$ symbol. The $branch$ is used to denote a possible choice in the match: either $\alpha$ can be matched as a partial string, or $\beta$, and $end$ is used at the end of $\alpha$ to signal where $\alpha$ ends and $\beta$ begins.

We say that a binary string $x$ "matches" a string template $\alpha \in U$ (the author's Definition 5.2) if $x$ is in the set $\phi(\alpha)$, recursively defined as:

$\phi(end) = \epsilon$ ($end$ symbols are removed)
$\phi(b\alpha) = b \phi(\alpha)$ for $b \in \{0,1\}$ (normal string matching)
$\phi(branch~ \alpha \beta) = 0\phi(\alpha) \cup 1 \phi(\beta)$, for $\alpha,\beta \in U$.
The third condition is the main one here: the author intends for us to find the $end$ symbol that "matches up" with the first $branch$ symbol, and partition $\alpha$ and $\beta$ according to that. Then, depending on whether the next symbol of $x$ is $0$ or $1$, the next piece of $x$ should either partial-match to $\alpha$ or partial-match to $\beta$.

It should be analogous to think of an $\alpha$ as an encoding of a (rooted) binary tree (each node has at most two children), where we label each edge of the tree by $0$ or $1$, and we say that a string $x$ matches the tree if there's some root-to-leaf path whose concatenated symbols are exactly $x$.
Anyway, the final presumed hard function $g$ (Definition 5.2) is:
Given a string template $\alpha \in U$ and given binary strings $x_1,\ldots,x_k$ (where each string is separated by a new symbol) output $k$ bits indicating which $x_i$'s match the template $\alpha$.
If this was a "normal" partial match query problem (e.g. with strings over $\{0,1,\star\}$, then it would be easily computed in $O(n)$ time on a multitape Turing machine, even one that just reads its input in one direction. I don't see  why computing multiple queries on a binary search tree should take super-linear time for a multitape Turing machine. (I don't see why following $K$ paths down a binary tree of description size $N$ should take more than $(N+K) \cdot poly(\log(KN))$ time.) And the fact that it didn't appear in a major conference or a major journal makes me very suspicious. (It does appear in a journal: https://www.ems-ph.org/journals/show_pdf.php?issn=0034-5318&vol=13&iss=2&rank=5) But I didn't spend more than an hour looking at this!

FINAL UPDATE: Brynmor Chapman looked at this paper more closely, and observed the proof only gives a lower bound for the "on line" version of the function, where the query for each binary string $x_i$ (as described above) must be answered (the TM must output a bit) before the TM is allowed to read the next binary string $x_{i+1}$. This a data structure lower bound for TMs, which is much easier to prove given the 1-dimensional nature of TM tapes. That is, the lower bound proved is much weaker than what is claimed: that there is a function $g$ computable in linear time on RAMs which requires nearly quadratic time on a multi-tape Turing machine. As far as I know, that claim remains open.


Class of languages recognizable by single-tape 3-state TMs I have for a while been curious about Turing Machines with exactly one tape and exactly 3 states (namely the start state $q_0$, the accept state $q_{accept}$, and the reject state $q_{reject}$). Note that I allow arbitrary (finite) tape alphabets (i.e., the tape alphabet is not restricted to equal the input alphabet).

For convenience, call the class of languages recognizable by such TMs $C_3$. I have several questions about this class:

Has $C_3$ previously been studied?
Is $C_3$ known to equal any other complexity/computability classes of interest?
Is the class $C_3$ robust to changes in model. For example, if the TMs used are allowed to stay in place during a single transition (as opposed to always moving either left or right) or if the tape is made to be infinite in both directions instead of just to the right, does the class of languages recognizable by 3-state 1-tape TMs change?
How does $C_3$ relate to the class of regular languages, $Regular$? (In particular, is every regular language in $C_3$?)

A (rather cursory) search brought up only this cs.stackexchange post which is relevant but doesn't answer my questions and this paper, which I haven't read in enough detail to be sure that it concerns exactly the class $C_3$ rather than a similar but different class (the paper claims to prove that (1) every language in $C_3$ is decidable and (2) that $C_3$ and $Regular$ are distinct classes with non-empty intersection). As pointed out in the comments of the cs.stackexchange post, these kinds of TMs can be thought of as very particular cellular automata, so maybe someone who knows the literature on cellular automaton theory could help.

The beast is extremely powerful, for example we can build a TM $M$ that  accepts every string of the form

$L_Y = \{ r\; 0^n \; 1^m\;A \mid m \leq n \}$

and rejects every string of the form

$L_N = \{ r\; 0^n \; 1^m\;A \mid m > n \}$

The idea is to transform the first $r$ into $R$ and then let the head reach the middle of the string then do a "stateless"  zig-zag; if it reaches $A$ before $R$ then it accepts.

Informal description:

on $r$ write $R$ and move right (prepare for rejecting)
on $0$ write $c$ and move right (moving toward the center)
on $1$ write $>$ and move left (mark a $1$, prepare for next left-to-right crossing, and go left)
on $c$ write $<$ and move right (mark a $0$, prepare for the next right-to-left crossing, and go right)
on $<$ write $>$ and go left (left-to-right crossing, prepare for next  right-to-left)
on $>$ write $<$ and go right (right-to-left crossing, prepare for next  left-to-right)
on $A$ accept, on $R$ reject
on blank $b$ reject

Example:

  :r 0 0 0 1 1 A
   R:0 0 0 1 1 A
   R c:0 0 1 1 A
   R c c:0 1 1 A
   R c c c:1 1 A
   R c c:c > 1 A
   R c c <:> 1 A
   R c c < <:1 A
   R c c <:< > A
   R c c:< > > A
   R c:c > > > A
   R c <:> > > A
   ...
   R c < < < <:A ACCEPT

This zig-zag technique is used in the smallest 2-states Universal Turing machine (it has 18 symbols) constructed by Rogozhin (Rogozhin 1996. TCS, 168(2):215–240)).

Some attention should be paid in order to prove that $M$ halts on all inputs (just note that it rejects on blank input and all non-halting symbols "converge" to  $<$ or $>$ which cannot lead to an infinite loop).

As commented by DavidG, the language $L(M)$ recognized by $M$ is a superset of $L_Y$ (i.e. $L_Y \subset L(M)$) but it doesn't contain any string from $L_N$ (i.e. $L(M) \cap L_N = \emptyset$) and - as commented by MikhailRudoy - this is enough to prove that $L(M)$ is not regular.

Indeed if $L(M)$ is regular then also $L(M) \cap \{ r0^*1^*A \} = L_Y = \{ r0^n 1^mA \mid m \leq n \}$ would be regular (which is not by a simple application of the pumping lemma); leading to a contradiction.

So $L(M)$ is not regular.

... But like all superheroes $C_3$ has an Achille's heel: it cannot even recognize the regular:

$L = \{ 1^{2n} \}$

Informally it can use only the leftmost $b 1 ...$ ($b$ is the blank symbol) or the rightmist $1b...$ as a hook and "expand" in the other direction; but the final Accept or Reject cannot be on the blank symbol of the opposite side, so it can be done only on the inner part of the $1$s and starting from a long enough input it can be "faked" stretching it by one.

Finally - after reading the paper - I can confirm that the one-state TM described in it matches your $C_3$ class ... (so nothing new here :-) ...and the langauge used by the author to prove that it contains non-regular languages is very similar to mine.


computing maximal bit density over a FSM let $L$ be a regular language defined by a FSM over binary symbols $\{0,1\}$. consider a function $f(x)$ on words/ strings that computes "bit density", defined as the number of $1$'s in a word ("Hamming weight") divided by the word length.

  what is an algorithm to compute $\max_{x \in L} f(x)$?

there is a simple randomized/ estimation algorithm that computes $f(x)$ over random words; am looking for a deterministic one. note that $f(x)$ evaluated on the shortest word in $L$ is not necessarily the same as the global minimum. am also interested in other generalizations of $f(x)$ that are based on similar "simple word metrics".

bkg: this question arose in studying & idea in attacking an old open number theoretic problem.

First, you mean "sup" rather than "max", because it is easy to construct examples of regular languages, such as 00(011)*00  where there is no max.  (The sup may not be attained.)

Second, by "FSM" I assume you mean finite automaton.

Then I claim that either the maximum bit density is achieved by a word of length < n, the number of states, or it is given by the maximum bit density over a loop of size at most n.
This means there are only finitely many cases to check, for each DFA.  Probably with a bit more work, one can get a polynomial-time algorithm out of it.

To see the claim, first note that if we compute the bit density of the sequence of words
$(u v^i w)_{i \geq 0}$ then this sequence is either (a) strictly increasing, (b) strictly decreasing, or (c) constant.  If the maximum bit density is attained and occurs at a shortest word x of length $>= n$, by the pumping lemma we can write $x = uvw$ where $|uv| \leq n$.  In each case we get a contradiction.  In (a) there are words with higher bit density, like $uv^2w$; in (b) there is a word with higher bit density, namely $uw$, and in (c) there is a shorter word with the same bit density.

The remaining case is that the maximum density is not attained.  A slightly more complicated argument, almost exactly the same as in my paper with Schaeffer, then proves the claim about the loops.

The Critical Exponent is Computable for Automatic Sequences.
Luke Schaeffer, Jeffrey Shallit
Int. J. Found. Comput. Sci. Vol. 23 No. 8 Pg. 1611-1626
Year: 2012


Is the knapsack variant with small profit and unlimited repetition of items NP-hard? Consider the unbounded Knapsack problem where we are given $n$ items of integral weights $w_i$, integral profits $p_i$, and a max weight $W$. The goal is to maximize the total profit $\sum_i x_ip_i$ subject to the total weight $\sum_i w_i x_i$ being at most $W$.  Here (in the unbounded variant) each item $i$ can be taken any number of times, so each $x_i$ can take any value in $\mathbb N_0$.
In general, this problem is NP-hard, but I am wondering about the restriction to instances with small profits --- where every item profit $p_i$ is $O(n)$.  With this restriction, is the unbounded Knapsack problem NP-hard, or is there a poly-time algorithm for it?
For comparison, consider the standard Knapsack problem, where each item can be taken at most once, so each $x_i$ is either 0 or 1.  This version is NP-hard by reduction from Subset Sum. (That reduction creates profits that are the same as the weights, and both are exponential.)  But for instances where each item profit is $O(n)$, the maximum achievable profit $P$ is $O(n^2)$, and there is a standard dynamic-programming algorithm that runs in time polynomial in $n$ and $P$, so the run-time in the case of small profits is polynomial in $n$. In contrast, for the unbounded problem, even with small profits, the maximum achievable profit is not in general polynomial in $n$, so the same approach does not yield a polynomial-time algorithm.

The problem (unbounded Knapsack with small profits) has a polynomial-time algorithm.
Theorem 1. For unbounded Knapsack with integer profits $(p_1,\ldots,p_n)$, there is an algorithm running in time polynomial in $n$ and $\max_i p_i$.
Proof. We first observe that the problem reduces in polynomial time to  the "flipped" variant, where the profits are given a threshold, rather than the weights:
input: weights $w=(w_1,\ldots,w_n)$, positive integer profits $p=(p_1,\ldots, p_n)$, and desired profit $P$
output: the minimum sufficient weight $W^* = \min\big\{ w\cdot x : p\cdot x \ge P,\, x\in\mathbb N_0^n\big\}$.
Throughout "$\cdot$" denotes the dot product, $a\cdot b = \sum_{i=1}^n a_i b_i$.
Lemma 1. Knapsack with integer profits reduces in time polynomial in $n$ and $\log(\max_i p_i)$ to the "flipped" problem defined above.
The proof of Lemma 1 is straightforward.  I've appended it at the end.
Next we observe that the flipped problem has an algorithm whose run-time is polynomial in $n$ and the profit threshold $P$.
Lemma 2. There is an algorithm for the flipped problem that runs in time polynomial in $n$ and $P$.
The proof of Lemma 2 is a standard exercise in dynamic programming.  I've appended it at the end.
The theorem doesn't follow directly, because the desired profit $P$ is not, in general, polynomial in the maximum item profit $\max_i p_i$.
Next we develop an algorithm that runs in time polynomial in $n$ and $\max_i p_i$.
Fix any instance $(p, w, P)$ of the flipped variant.
Let $i^*=\arg\max_i p_i/w_i$ be the item with highest profit-to-weight ratio.
The key observation is the following:
Lemma 3. There is an optimal solution $x$ with $x_i < p_{i^*}$ for all $i\ne i^*$.
Proof. Consider any optimal solution $x$.  Suppose $x_i \ge p_{i^*}$ for some $i\ne i^*$.  Then replace $p_{i^*}$ copies of item $i$ with $p_i$ copies of item $i^*$.  This preserves the total profit, and cannot increase the weight.  Repeat as necessary with other items to obtain the claimed solution. $~~\Box$
In the optimal solution $x$ from Lemma 3, the total profit from items
other than $i^*$ is at most $\sum_{i\ne i^*} p_{i^*} p_i \le n(\max_i p_i)^2$.  That is, the total profit from items other than $i^*$ is polynomial in $n$ and $\max_i p_i$.  Intuitively, this means that we can greedily commit to taking most of the profit from $i^*$, and once we do, for the remaining problem (allocating the rest of the profit), the desired profit will be polynomial in $n$ and $\max_i p_i$. So we can solve that remaining problem using the algorithm from Lemma 2.  Here are the details.
Let optW$(p, w, P)$ denote the minimum weight needed to make profit $P$.
Lemma 4. Let $\delta = \max(0,\lceil P/p_{i^*} - \sum_{i\ne i^*} p_i \rceil)$ and $P'= P - \delta p_{i^*}$.  Then
$$\text{optW}(p, w, P) = \delta w_{i^*} + \text{optW}(p, w, P').$$
Proof. The optimal solution $x$ from Lemma 3 has $x_i < p_i$ for $i\ne i^*$. Since $\sum_i x_i p_i \ge P$, it follows that
$x_{i^*}p_{i^*} \ge P - \sum_{i\ne i^*} p_i p_{i^*}$,
i.e.,
$x_{i^*} \ge \lceil P/p_{i^*} - \sum_{i\ne i^*} p_i \rceil = \delta$.
So this optimal $x$ must consist of an optimal solution to $(p, w, P')$, plus $\delta$ units added to $x_{i^*}$. $~~~\Box$
(A technical remark to avoid confusion: the solution to $(p, w, P')$ in the proof above can still use item $i^*$.  However many copies of $i^*$ it takes, the optimal $x$ will take $\delta$ more.)
Lemma 4 gives the desired algorithm:

calculate $\delta$, and $P'$ as defined in Lemma 4:
$\delta = \max(0,\lceil P/p_{i^*} - \sum_{i\ne i^*} p_i \rceil)$ where     $i^* = \arg\max_i p_i/w_i$
$P'= P - \delta p_{i^*}$

return optW$(p, w, P') + \delta w_{i^*}$,
where optW$(p, w, P')$ is computed using the algorithm from Lemma 2

Correctness of the algorithm follows from Lemma 4. By inspection and Lemma 2 the run time is polynomial in $n$ and $P'$, with
$$\textstyle P' = P-\delta p_{i^*} \le P - (P - \sum_{i\ne i^*} p_i p_{i^*})
= \sum_{i\ne i^*} p_i p_{i^*} \le n(\max_i p_i)^2.$$
So the time is polynomial in $n$ and $\max_i p_i$. $~~~\Box$
Proof of Lemma 1 (reduction to flipped problem). Fix an instance $(p, w, W)$ of Knapsack with integer profits. The optimal solution has profit $P^*$ at most $\lambda^* = p_{i^*} W/w_{i^*}$, because no item has a profit per weight ratio larger than $p_{i^*}/w_{i^*}$.  On the other hand, using just item $i^*$, as many items as possible, yields a solution of profit $\lfloor W/w_{i^*}\rfloor p_{i^*} > \lambda^* - p_{i^*}$. So $\lambda^* - p_{i^*} \le P^* \le \lambda^*.$  Use binary search for $P$ in the range $\lambda^* - p_{i^*}$ to $\lambda^*$ (solving the flipped problem $(p, w, P)$ in each iteration) to find the maximum profit $P^*$ such that the minimum required weight to achieve profit $P^*$ is at most $W$.  This $P^*$ will be the maximum profit achievable with weight-budget of $W$.  The time for this reduction is polynomial in $n$ and $\log(\max_i p_i)$. $~~\Box$
Proof of Lemma 2 (standard dynamic-programming-algorithm for the flipped problem). Fix an input $(p, w, P)$.  For $i\in\{0,1,\ldots,n\}$ and $Q\in \{0,1,\ldots, P\}$, define $W(i, Q)$ to be the minimum sufficient weight for the subproblem formed by the first $i$ items and desired profit $Q$.
Then
$$W(i, Q) = \begin{cases}
0 & \text{if } Q = 0 \\
\infty & \text{if } Q>0, i=0 \\
\min\big\{ x_i w_i + W(i-1, Q-x_i p_i) : x_i\in\mathbb N_0,\, x_i p_i \le Q\big\} & \text{otherwise.}
\end{cases}$$
There are $O(n P)$ subproblems, and for each the right-hand side of the recurrence can be evaluated in time $O(P)$, so the dynamic-programming algorithm takes time $O(n P^2)$. $~~~\Box$
EDIT: Looking briefly over the literature, the same idea (but for weights instead of profits) has been used for unbounded Knapsack with small weights.  See e.g. Section 8.2.1 of https://doi.org/10.1007/978-3-540-24777-7_8 or Section 10.4 of  https://doi.org/10.1007/978-3-540-76796-1_10. I don't know whether it has also been used before for profits.


Is there an oracle that separates two complexity classes known to be equal? We know that there exist two oracles $A$ and $B$ such that $P^A=NP^A$ and $P^B\neq NP^B$, this implies the obstacle of proving $P\neq NP$ using diagonalization.  I just wonder if there exist two complexity classes, say $A$ and $B$ and oracle $O$ such that $A=B$ but $A^O\neq B^O$?

I am not sure if it is a research-level problem. So don't hesitate to close it if not.

Thanks.

We have IP = PSPACE = PPSPACE, where PPSPACE is the "probabilistic polynomial space," as defined by Papadimitriou's Games Against Nature.

However, relative to a random oracle O, we have IPO ≠ PSPACEO = PPSPACEO with probability 1. (See The Random Oracle Hypothesis is False.)

Another example: let the assumption be false; that is, if A=B the AO = BO for any oracle O and all complexity classes A and B. The contrapositive will say: If AO ≠ BO, then A ≠ B. Specially, since there exists an oracle O such that PO ≠ NPO, then P ≠ N, and a long-standing problem is solved!!!

Obviously, this reasoning has no basis, and I believe it can be refuted as such.

PS: When we use the "=" sign with respect to sets, we mean that every element of one set is also a member of the other set, and vice versa. However, the sets might have totally different definitions. In the axiomatic set theory, this is called the axiom of extensionality. The reason of "IP = PSPACE but IPO ≠ PSPACEO with probability 1 for a random oracle O" is exactly this: While IP and PSPACE are externally identical, their internal structure is quite different.


Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$? The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices.  A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ is adjacent to $c$, and $c$ is adjacent to $a$.
It is known that Triangle Finding is closely related to Boolean matrix multiplication and that Triangle Finding is deterministically solvable in $O(n^{\omega})$ time where $\omega$ is the matrix multiplication exponent.  Also, it is known that $\omega < 2.373$.
My Question: Is the complement of Triangle Finding solvable more efficiently with nondeterminism?  In particular, is Triangle Finding in $coNTIME(\tilde{O}(n^2))$?  If this is not known, would there be any interesting implications if it was true?

Update: Sadly, it seems that my initial idea (see below) was incorrect, but it led to some fruitful discussion in the comments.  As a result, the question is still open.
Please let me know if you have any ideas.  :)

Initial Idea: One way to solve Triangle Finding is to find all pairs of vertices that are connected by a path of length 2.  Then, you check if there is an edge between any of these pairs.
A standard way to compute all pairs of vertices that are connected by a path of length 2 is to square the adjacency matrix of the graph.  We can perform Boolean matrix multiplication for the squaring.  All of the 1's in the result will represent pairs of vertices that are connected by a path of length 2.
With nondeterminism, we can compute Boolean matrix multiplication of two n by n matrices in $\tilde{O}(n^2)$ time by guessing the witness for Boolean matrix multiplication (the concept of witness for Boolean matrix multiplication has been discussed in [1] https://doi.org/10.1007/s00453-012-9742-3 and [2] https://doi.org/10.1109/SFCS.1992.267748).  Finally, we check in $O(n^2)$ time if all of the pairs of vertices do not form edges.  <- This paragraph doesn't quite work.


Counting solutions of Monotone-2CNF formulas A Monotone-2CNF formula is a CNF formula where each clause is composed by exactly 2 positive literals.

Now, I have a Monotone-2CNF formula $F$. Let $S$ be the set of $F$'s satisfying assignments. I also have an oracle $O$ which is able to give the following information:

The cardinality of the set $S$ (i.e. the number of solutions of $F$).

Given a variable $x$:

The number of solutions in $S$ containing the positive literal $x$.
The number of solutions in $S$ containing the negative literal $\lnot x$.

Given 2 variables $x_1$ and $x_2$:

The number of solutions in $S$ containing $x_1 \land x_2$.
The number of solutions in $S$ containing $x_1 \land \lnot x_2$.
The number of solutions in $S$ containing $\lnot x_1 \land x_2$.
The number of solutions in $S$ containing $\lnot x_1 \land \lnot x_2$.

Note that the oracle $O$ is "limited": it works only on $F$, it can't be used on a formula $F' \neq F$.

  Question:

  Given 3 variables $x_1$, $x_2$, $x_3$
  is it possible to determine the number
  of solutions in $S$ containing $\lnot
  x_1 \land \lnot x_2 \land \lnot x_3$ in
  polynomial time, using $F$ and
  the information provided by $O$?

  Note:

  You can replace $\lnot
  x_1 \land \lnot x_2 \land \lnot x_3$ in the
  question with whatever else of the 8 possible
  combinations of $x_1$, $x_2$, $x_3$. The problem
  would remain the same.

  Empirical fact:

  I came across the following empirical fact one
  week ago. Let $S_{\lnot x_1 \land \lnot x_2} \subset S$
  be the set of those solutions containing $\lnot x_1 \land \lnot x_2$,
  and let $S_{\lnot x_1 \land \lnot x_2 \land x_3} \subset S$ be the set
  of those solutions containing $\lnot x_1 \land \lnot x_2 \land x_3$. Now, it
  seems to be the case that, if condition $C$ holds, this relationship also holds:
  $\frac{|S_{\lnot x_1 \land \lnot x_2}|}{|S_{\lnot x_1 \land \lnot x_2 \land x_3}|} \simeq \phi$
  where $\phi = 1.618033...$ is the golden ratio. Condition $C$ seems to be the following: "$x_1$, $x_2$, $x_3$ are mentioned in $F$ almost the same number of times".

Some observations, not an answer.

Further to the note to the question, any combination of 3 literals can be expressed in terms of any other combination of literals on the same variables, together with a small number of terms that the oracle can provide.  This follows from looking at the Venn diagram of 3 intersecting sets, and expressing each of the 8 regions in terms of the other regions.  Note that this does not require the formula to be either monotone or 2CNF.

It is also clear that the number of solutions satisfying any 3-literal conjunct can be expressed as the sum of $2^{n-3}$ terms, each of which is either 0 or 1, expressing a particular assignment to all variables.  Each of these can be evaluated in linear time, but there are exponentially many terms to evaluate, so this doesn't satisfy the requirements.

Hence the question is really about whether it is possible to exploit the property of being monotone 2CNF to compress this exponential-size expression to polynomial size.

I tried to look at a simpler question, restricting the oracle to just an advice string with the number of solutions, when the counts for single or pairwise literal combinations are not available.  I cannot see any way to exploit knowledge of the number of solutions to obtain a quick calculation of the number of solutions with respect to any single literal.

Is there something about monotone 2CNF that would allow the number of solutions in $S$ containing $x_1$ to be obtained quickly, if one knew $|S|$?


efficient diff algorithm for trees and Levenshtein distance I've recently read this summary of the issues involved with doing diff between trees and it got me interested in learning what is the state of the art for this problem.

Also, suppose that between your allowed edit operations are the traditional add/delete node, edit content you add the extended operations of copy/move subtree, does this makes the problem (of finding an optimal diff) easier or harder?

The following paper describes a slightly more efficient algorithm than Zhang-Shasha for computing tree edit distance, along with a proof that their algorithm is optimal (within a certain broad class of algorithms):

Erik Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann.  An Optimal Decomposition Algorithm for Tree Edit Distance.  ACM Transactions on Algorithms, 6(1), 2009.


Are string palindrome questions practically interesting? I've been reading Don Gusfield's "Algorithms on Strings, Trees, and Sequences", and quite a some chunk of the textbook concentrates on palindromic-related ideas.

I'm unsure as to whether this is because the question is purely theoretically interesting (in terms of finding good lower bounds), or there are practical use cases for this (in terms of genetics, or even other use cases I don't know of).

So, what do studying palindromes offer us? Do they offer theoretical insight into other string problems --- the way matrix multiplication and matrix inversion offer insights into each other? Are they practically useful? Or is it "just fun"?

I had a use for palindromes as follows:

A string of length $n$ and its reversal have the same complexity. Thus, when studying complexity of strings you can identify a string with its reversal.

Now after identifying you may ask how many equivalence classes have certain properties. And then the number of equivalence classes is directly related to the number of palindromes. If there  are $p_n$ palindromes then there are
$$p_n+(2^n-p_n)/2$$
equivalence classes of binary strings.


Reverse contraposition While it is trivial to prove contraposition

∀ A B: Prop, (A → B) → (~B → ~A)

using Coq, is it equally trivial to prove the reversed form:

∀ A B: Prop, (~A → ~B) → (B → A)

? In particular, is it doable without using any additional axioms, e.g. from classical logic?

It is not provable without additional axioms. In fact, it implies double negation elimination (take $B=\top$), which in turn is equivalent to the excluded middle.


A simple decision problem whose decidability is not known I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability.  I want to give an example of a problem that we do not currently know to be decidable or undecidable.  There are many such problems, but none seem to stand out as nice examples so far.

What is a simple-to-describe decision problem whose decidability is open?

The Matrix Mortality Problem for 2x2 matrices.  I.e., given a finite list of 2x2 integer matrices M1,...,Mk, can the Mi's be multiplied in any order (with arbitrarily many repetitions) to produce the all-0 matrix?

(The 3x3 case is known to be undecidable.  The 1x1 case, of course, is decidable.)


Computing input length on a one-tape Turing machine In connection with this question it occurred to me to wonder: what is the time complexity
for a single-tape single-head Turing machine to compute the length of its input? To be specific, let's say that the tape alphabet is $\{0,1,b\}$, the input is a string in $(0+1)^*$ surrounded by blanks, the machine starts at the leftmost input symbol, and it must terminate at the leftmost symbol of a string in $(0+1)^*$ (again surrounded by blanks) that gives the binary representation of the input length. This can also be thought of as the problem of converting a number from unary to binary.

It's easy to solve this on a two-tape machine or two-head machine in linear time (just scan the input with one head while using the other head to repeatedly increment a counter; incrementing is a constant amortized time operation). But the single-head solutions I can come up with are only $O(n\log n)$ (e.g. repeatedly increment a counter and then shift it by one position along the tape). Is there a matching lower bound?

I tried some searches but phrases like "one head" and "input length" are so common as to make it difficult to search the literature for known results on this problem.

It cannot be computed in time $o(n\lg n)$.

Let $M$ be a machine which
given an input string $x$
halts with the size of $x$
written in binary on the tape.

We can add a simple (zero-space linear-time) DFA to $M$
to check if the size of the input is a power of two:
just check that the first bit is 1 and the rest is zero.

Let's assume that $M$ runs time $o(n \lg n)$.
Then we can decide in time $o(n \lg n)$ that
the size of input is a power of two.
In other words, the following language is
decidable in $\mathsf{DTime}(n \lg n)$.
$$L = \{ 0^i \mid \exists k \ i = 2^k\}$$
It follows from $\mathsf{DTime}(o(n \lg n)) = \mathsf{Reg}$
that $L$ should be regular.
But it is easy to check that the language is not regular.
So $M$ cannot run in time $o(n \lg n)$.


Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem What is the difference between Multiple Knapsack problem and Multidimensional Knapsack Problem? (http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints) According to the literature, Multiple Knapsack problem has integrality gap of 2, what is the integrality gap for Multidimensional Knapsack Problem ?

In a multiple knapsack problem you pack a set of items into several (one-dimensional) knapsacks, whereas in the multidimentional knapsack problem you pack d-dimensional items into one d-dimensional knapsack. The multiple knapsack problem $\max\{\sum_i p_i x_i \mid \sum_i w_{ij}x_i \leq d_j, j=1,2,\ldots,m\}$ is a general 0-1 integer program restricted to positive coefficients. Its integrality gap is unbounded, since it includes the maximum independent set problem whose formulation $\max\{\sum_{v\in V} x_v\mid x_u+x_v\leq 1, \{u,v\}\in E\}$ on an undirected graph $G=(V,E)$ has integrality gap $|V|/2$.

You can find more information on these problems in chapters 9 and 10 of  Kellerer, Pferschy, and Pisinger, "Knapsack problems".


Bounding Rademacher Averages, with and without chaining One can bound the Rademacher average $R_n(A)$ of a finite set of vectors $A\subseteq\{0,1\}^n$ using Massart's Finite Lemma:
$$
R_n(A)\le \max_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n}
$$
where $\|\cdot\|$ is the Euclidean norm.

Then, using Sauer's Lemma, one can obtain
$$
R_n(A)\le C\max_{a\in A}\|a\|\sqrt{\frac{V\ln\frac{n}{V}}{n}},$$
where $V$ is the (empirical) VC-dimension.

Using chaining and a bound on covering numbers, one can get rid of the logarithmic factor and obtain
$$
R_n(A)\le C'\sqrt{\frac{V}{n}}.
$$

Looking at the proof that uses chaining, I can't seem to find a way to have $\max_{a\in A}\|a\|$ in the second bound. Is it even possible?

It may not change much in theory, but it does in practice, and (in my opinion), it intuitively makes sense that the bound should depend on it.

Converting the comment to an answer: See the notes here:
cs.cornell.edu/~sridharan/dudley.pdf
with the dependence on $\sup_f \hat E[f^2]$


Is it possible to prove that, for a given problem, no optimal greedy algorithms exist? Greedy is a non-formal term, but it could be (not sure, that's why I'm asking) that for certain problems, greediness can be mathematically formulated and thus be proven that no optimal greedy algorithm exist. Is this possible?

Yes, there is such work. Allan Borodin with coauthors developed a theory where they formalize the notion of greediness and obtain results which approximation ratios can be reached with them. They introduce a class of priority algorithms, which generalizes greedy algorithms. Their first work on this topic is
the paper "(Incremental) Priority Algorithms".

P.S. The previous paragraph answers on a different question: Is it possible to prove that, for a given problem, no greedy algorithms exist with approximation ratio less than some $1+\epsilon$? What concerns the question I suppose it is assumed there that optimal means exact so the question relates to problems in P (I assume greedy algorithms have polynomial complexity though I guess this is not necessary) which are known to have solution by other methods than greedy ones. And I don't know the answer on this question.

To ivotron: if you didn't mean my first interpretation I will delete this answer.