Largest common subgraph of two maximal planar graphs Consider the following problem -

Given maximal planar graphs $G_1$ and $G_2$, find the graph $G$ with maximum number of edges such that there is a subgraph (not necessarily induced) in both $G_1$ and $G_2$ that is isomorphic to $G$.

Can this be done in polynomial time? If yes, then how?

It's known that if $G_1$ and $G_2$ are general graphs, then the problem is NP-complete (because $G_1$ could be a clique). It's also known that if $G_1$ and $G_2$ are trees, or bounded degree partial k-trees, then the problem can be solved in polynomial time. So what about the maximal planar case? Does anyone know this? Graph isomorphism on two maximal planar graphs is polynomial. Perhaps this helps somehow?

It's NP-complete, via a modified version of the reduction Wigderson used to prove that Hamiltonicity of maximal planar graphs is NP-complete.

Careful examination of Wigderson's 1982 NP-completeness proof of hardness for Hamiltonian cycles in maximal planar graphs (http://www.math.ias.edu/avi/node/820) shows that the instances produced by his reduction have the property that there exists an edge $e$ such that either there exists a Hamiltonian cycle through $e$ or there does not exist any Hamiltonian cycle at all. For instance, $e$ can be chosen to be one of the edges in one of Wigderson's $M$-gadgets.

Let $G$ be a hard instance constructed  in this way, and embed $G$ so that the edge $e$ belongs to the outer triangle of the embedding. Connect many copies of this embedded graph so that their $e$-edges form a cycle, and make the result maximal planar again by adding two more vertices, one on each side of this cycle, connected to all the exposed vertices of the copies of $G$. Let the number of copies be $c$, and call the resulting graph $H$. Let $n$ be the number of vertices in $G$.

Our hard instance for the largest common subgraph will be the pair $(H,B)$ where $B$ is a bipyramid with the same number of vertices as $H$. Thus, an optimal common subgraph will have to pair all of the vertices. If we make $c$ large enough, the subgraph will necessarily pair the apexes of the bipyramid with the two added vertices in $H$, because their degrees ($c$ and $2c$) will be sufficiently higher than every other vertex in $H$, so that adding these degrees to the solution size will make up for any disruption elsewhere caused by this pairing.

If $G$ is Hamiltonian, then the common subgraph formed by matching the Hamiltonian cycle (minus $e$) in the copies of $G$ to the equator of the bipyramid will have $c(n+2)$ edges, $c(n-1)$ for the equator and $3c$ for the apexes. If $G$ is not Hamiltonian, then (for large enough choices of $c$ that the optimal solution pairs the apexes correctly) any common subgraph will have fewer edges: still $3c$ at the apexes but fewer than $c(n-1)$ elsewhere. So testing whether the common subgraph of $H$ and $B$ has at least $c(n+2)$ edges is NP-complete.


Maximal non-reducible vertex cover of a graph Let $G=(V,E)$ be a graph (i.e. an undirected simple finite graph).
We say that a vertex cover $V'$ of $G$ is non-reducible if any $V''$ with $V''\subsetneq V'$ is not a vertex cover of $G$. We say that a non-reducible vertex cover $V'$ of $G$ is maximal if for all non-reducible vertex cover $V''$ of $G$ we have $|V''|\le |V'|$. Note that the minimum vertex cover is non-reducible, but of course not necessarily maximal.

What is know about the (time)-complexity of finding a maximal non-reducible vertex cover?

Is there anything known for hypergraphs with multiple edges?

What you call a non-reducible vertex cover is commonly known as a minimal vertex cover. So, what you are looking for is a minimal vertex cover of maximum cardinality, i.e a maximum minimal vertex cover.

I'm not aware of any literature on this problem per se, however the equivalent Independent Dominating Set problem is quite well studied. An independent dominating set in a graph $G$ is an independent set $I$ such that every vertex not in $I$ has a neighbor in $I$. In the Independent Dominating Set problem input is a graph $G$ and the task is to find a smallest possible independent dominating set. This problem is known to be NP-complete.

The two problems are equivalent because a set $S$ is a minimal vertex cover if and only if $V(G) \setminus S$ is an independent dominating set.


Termination of the Bellman-Ford algorithm in asynchronous distributed model I'm looking for an algorithm to compute the BFS tree of a graph rooted in the leader processor $r$ in the asynchronous distributed model.

The only requirement is $O(D)$ time complexity, where $D$ denotes the diameter of the graph (message complexity isn't relevant).

Currently, I'm using Bellman-Ford algorithm, but I don't know how to guarantee the global termination of this method in $O(D)$ time. I was trying to use the convergecast technique, but with no success.

Is it possible to guarantee a termination of Bellman-Ford in $O(D)$ time or is there any other algorithm for computing the BFS tree in $O(D)$ time?

I found the answer. The alpha synchronizer will do it.

Here is the full paper: Baruch Awerbuch (1985). Complexity of Network Synchronization


Smallest Boolean circuit to generate a language Consider a non-empty language $L$ of binary strings of length $n$. I can describe $L$ with a Boolean circuit $C$ with $n$ inputs and one output such that $C(w)$ is true iff $w \in L$: this is well-known.

However, I want to represent $L$ with a Boolean circuit $C'$ with $n$ outputs and a certain number of inputs, say $m$, such that the set of the output values of $C'$ for each of the $2^m$ possible inputs is exactly $L$.

  Given $L$, how can I find such a circuit $C'$ of minimal size, and what is the complexity? Is there any relationship between known bounds about the size of circuits of the first kind ($C$) and circuits of this second kind ($C'$), or the complexity of finding them?

(Observe that there is some sort of duality in the following sense: given $C$, I can easily decide if an input word $w$ is in $L$ by evaluating the circuit, but it is NP-hard in general to find some word in $L$ by finding an assignment such that the output is true. Given $C'$ it is likewise NP-hard to decide if some input word $w$ is in $L$ because I have to see if an assignment yields $w$ as output, but it is easy to find some word in $L$ by evaluating the circuit on any arbitrary input.)

I will point out a simple connection to nondeterministic circuits, and comment briefly on cryptographic hardness.

For $S \subseteq \{0, 1\}^n$, define the image complexity, denoted $imc(S)$, as the minimal number of gates in any (fanin-two, AND/OR/NOT) Boolean circuit $C: \{0, 1\}^m \rightarrow \{0, 1\}^n$ whose image is $S$.  The question asks about the complexity of computing $imc(S)$, given a truth-table representation of $S$ (a string of length $2^n$).

Also define the nondeterministic circuit complexity of $S$, which we'll denote $ncc(S)$, as the smallest nondeterministic circuit $C(x, y): \{0, 1\}^{n + m'} \rightarrow \{0, 1\}$ accepting exactly $S$.  That is, we require of $C$ that $x \in S$ iff $\exists y: C(x, y) = 1$.  This is a standard notion, used to define the non-uniform class $NP/poly$: it is the class of all sets $S = \{S_n\}_{n > 0}$, with $S_n \subseteq \{0, 1\}^n$, such that $ncc(S_n) \leq poly(n)$.

What I wanted to point out is that $imc(S) = ncc(S) \pm O(n)$.  Both directions of this inequality are simple to verify.

Let $dcc(S)$ denote the deterministic circuit complexity.  Using Razborov-Rudich, the paper that Dai Le mentions shows (roughly speaking here) that under certain cryptographic assumptions, it is computationally hard to distinguish truth-tables of $S$ with $dcc(S)$ small, from truth-tables of truly random $S$ (with $dcc(S)$ near-maximal).  Random $S$ also have $ncc(S)$ nearly-maximal, and we of course have $ncc(f) \leq dcc(f)$. So your problem is hard under the same assumptions.

Which is harder to compute given a truth-table for $S$, $dcc(S)$ or $ncc(S)$?  Is there a reduction either way?  I don't know.


Complexity of approximating a real function using queries Consider the following computational problem, where $I$ is the real interval $[-1,1]$:

There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of the kind: "Given $x\in I$, what is $f(x)$?". Let $x_0$ be an element of $I$ such that $f(x_0)=0$ (if it exists). Your goal is to find a value $x$ such that $|x-x_0|<\epsilon$. How many queries do you need, as a function of $\epsilon$?

All real numbers have infinite precision, as in the Real RAM model. It is allowed to do arbitrary computaitons on such real numbers - the only costly operations are the queries.
Here, the solution is simple: using binary search, the interval in which $x$ can lie shrinks by 2 after each query, so $\log_2(1/\epsilon)$ queries are sufficient. This is also an upper bound, since an adversary can always answer in such a way that the possible interval for $x$ shrinks by at most 2 after each query.
However, one can think of more complicated problems of this kind, with several different functions and possibly different kinds of queries.
What is a term, and some references, for this kind of computational problems?
Related posts in other sites:

First posted on cs.stackexchange.
This MathOverflow post is related, but there it is required to use a finite number of registers with a finite precision.

Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If $X$ is some set and $f:X\to\{0,1\}$, what is the minimal number of evaluation queries needed to uniquely identify $f$? As already noted in the OP, the question only makes sense if one fixes a function class $F$ of possible candidate functions $f$ to consider.
This is a well-studied problem, where the key notion is the teaching dimension (which is the minimum size of a teaching set), see here:
https://www.cs.umd.edu/sites/default/files/scholarly_papers/NealGupta.pdf
A teaching set $S\subset X$ is such that the values of $f$ on $S$ uniquely identify $f\in F$, for a given fixed function class $F$.
Nothing is stopping you from defining an $\epsilon$-teaching dimension for real-valued functions. You can define an $\epsilon$-teaching set $S\subset X$ to be such that all $f\in F$ that agree on $S$ all lie within an $\epsilon$-tube (i.e., are all within $\epsilon$ in $\ell_\infty$ distance).
As you can see from the discussion in that paper I linked, the teaching dimension is a rather stringent notion, which motivates more "interesting" variants, such as the recursive teaching dimension. Here again, I encourage you to explore its natural real-valued extensions.


Popular average-case complexity assumptions Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?

The assumptions often used in crypto are a form of average-case complexity assumptions, such as hardness of factoring or discrete log in various groups.

Many lattice problems used for strong hardness guarantees for lattice based cryptography are qualitatively somewhat different than the factoring/discrete log based cryptographic assumptions.

The development of indistinguishability obfuscation has also introduced a number of novel average case hardness assumptions.

Often times average case complexity is used in the study of data structures for upper bounds (eg., of hash tables), but there are also some useful lower bounds. For example, the worst case $\Omega(n \log n)$ lower bound on sorting can be generalized to the average case, and to randomized algorithms as well (eg., see these lecture notes)


Families of LDPC codes with constant error fraction corrected I am looking for families of error-correcting LDPC codes with a constant error fraction corrected by a decoding algorithm.

For example, I know that Sipser and Spielman proved that there is an algorithm that can correct a constant fraction of errors for expander codes (in Expander codes, 1996).

But, is there any equivalent theorem for other families of LDPC codes (like regular LDPC or irregular LDPC, for example)? References would be useful.

Thanks!

Here are a few examples:

There are the expander codes of Spielman (not to be confused with Sipser-Spielman):
http://www.cs.yale.edu/homes/spielman/Research/ITsuperc.pdf

There are the linear-time codes of Guruswami-Indyk:
https://www.cs.cmu.edu/~venkatg/pubs/papers/lin-zyablov.pdf

There are the expander codes of Zemor:
https://courses.engr.illinois.edu/cs598sgt/zemor.pdf


Is there an array structure that allows for O(1) complexity for reverse, zip, slice etc operations? Many operations on arrays have $O(n)$ complexity.

If we represent arrays as accessors methods, many of them could be done in $O(1)$. For example, the $i$th item in the reverse of an array $A$ of size $n$ is given by $reverse(A).i = A[n-1-i]$. So we can define reverse as:

$$reverse := \lambda A:array \ \lambda i:int. \ A[n-1-i]$$

and similarly for other operations like
slicing, zipping, concatenation, and so on.
This technique allows us to implement these complicated operations in constant time without touching the original memory at all.

What is the formal name of this structure?
What are the negative aspects of using this structure compared to the standard structure?

This is not completely useless, and this sort of thing does indeed see a few niche uses, for instance when we want to access an array backwards it's faster to loop over array[n-i-1] rather than calling reverse(array) followed by a loop over array[i].

The flaw I'm seeing here is that this sort of thing will cause access times to scale with the number of times the data in the list have been fiddled with. After $k$ modifications to the data, you'll naturally take at least $O(k)$ time to access the data. If I want to perform $O(n^2)$ non-lookup list transformations I'm not going to be happy unless you flatten it back down to an array first. Changing the data from a function representation, proposed by you, to an array representation takes one access per element, so $O(nk)$ time.

How frequently should we change the representation back? If we rebuild the array after every $l$ operations on it, we need to spend $O(nl)$ time to rebuild every $l$ operations, so the amortised complexity of each operation becomes $O(n)$. The complexity of a lookup becomes $O(l)$ in the worst case. This is worse than an array representation in general.


Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights? The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in reasonable time is an approximate one (Synopsis diffusion), but increasing its precision is exponential in the number of bits (and I need a lot of bits).

Background: this task is done (several times with different 'weights') as part of the probability calculations in  BBChop (http://github.com/ealdwulf/bbchop) a program for finding intermittent bugs (ie, a bayesian version of 'git bisect'). The DAG in question is therefore a  revision history. That means that the number of edges is unlikely to approach the square of the number of nodes, it's likely to be less than k times the number of nodes for some smallish k.
Unfortunately I haven't found any other useful properties of revision DAGs. For example, I was hoping that the largest triconnected component would grow only as the square-root of the number of nodes, but sadly (at least in the history of the linux kernel) it grows linearly.

We assume that vertex weights can be arbitrary positive integers, or more precisely, they can be positive integers at most 2n.  Then the current task cannot be performed even in a slightly weaker time bound O(n2), unless the transitive closure of an arbitrary directed graph can be computed in O(n2) time, where n denotes the number of vertices.  (Note that an O(n2)-time algorithm for the transitive closure will be a breakthrough.)  This is the contrapositive of the following claim:

Claim.  If the current task can be performed in time O(n2), the transitive closure of an arbitrary directed graph given as its adjacency matrix can be computed in O(n2) time (assuming some reasonable computational model).

Proof.  As a preprocessing, we compute the strongly connected component decomposition of the given directed graph G in time O(n2) to obtain a DAG G′.  Note that if we can compute the transitive closure of G′, we can reconstruct the transitive closure of G.

Now assign the weight 2i to each vertex i of the DAG G′ and use the algorithm for the current problem.  Then the binary representation of the sum assigned to each vertex i describes exactly the set of ancestors of i, in other words, we have computed the transitive closure of G′.  QED.

The converse of the claim also holds: if you can compute the transitive closure of a given DAG, it is easy to compute the required sums by additional work in time O(n2).  Therefore, in theory you can achieve the current task in time O(n2.376) by using the algorithm for the transitive closure based on the Coppersmith-Winograd matrix multiplication algorithm.

Edit: Revision 2 and earlier did not state the assumption about the range of vertex weights explicitly.  Per Vognsen pointed out in a comment that this implicit assumption may not be reasonable (thanks!), and I agree.  Even if arbitrary weights are not needed in applications, I guess that this answer might rule out some approaches by the following line of reasoning: “If this approach worked, it would give an algorithm for the arbitrary weights, which is ruled out unless the transitive closure can be computed in time O(n2).”

Edit: Revision 4 and earlier stated the direction of edges incorrectly.


Incremental Maximum Flow in Dynamic graphs I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/deleted with its corresponding edges to form a graph $G^1$. What is a maximum flow in newly created graph? Is there a way to prevent from recalculating maximum flow?

Any preprocessing which isn't very time/memory consuming is appreciated.

Simplest idea is recalculating the flow.

Another simple idea is as this, save all augmenting paths which used in previous maximum flow calculation, for adding a vertex $v$, we can find simple paths (in updated capacity graph by previous step) which start from source, goes to the $v$ then goes to the destination, but problem is, this path should be simple, I couldn't find better than $O(n\cdot m)$ for this case, for $m=|E|$. (Also note that if it was just one path this could be done in $O(n+m)$ but it's not so.)

Also for removing node above idea doesn't work.

Also I already saw papers such as Incremental approach for edges, but seems they are not good enough in this case, it's more than $O(m)$ for each edge and seems is not suitable extension in this case (we just recalculate a flow). Also currently I'm using Ford-Fulkerson maximum flow algorithm If there is better option for online algorithms, it's good to know it.

The described approach may not be theoretically optimal. It is just a simple practical solution that may work for the author. I can't provide any references because I always thought it is a widely known folklore, but strangely enough nobody posted it in the answer. So I do it.

Assume we have an undirected network $G=(V,E,c)$. Assume it is stored in a data structure which allows easy vertex/arc insertions/deletions. Sometimes we will use residual network $G_f$ (i.e. with updated capacities $c_f = c - f$).

First part is how to process vertex insertions/deletion. It's more or less straightforward for insertions:

Add a new vertex with corresponding edges to the residual network.
Find a maximum flow in the updated residual network using a maxflow algorithm of your choice.

For deletions things became more complicated. Imagine we split the vertex $v$ we are about to delete into 2 halves $v_{in}$ and $v_{out}$ such that all in-arcs points to $v_{in}$, all out-arcs goes from $v_{out}$ and this new vertices are connected by an arc of infinite capacity. Then deletion of $v$ is equivalent to deletion of the arc between $v_{in}$ and $v_{out}$. What will happen in this case? Let's denote by $f^v$ the flow passing through the vertex $v$. Then $v_{in}$ will experience excess of $f^v$ flow units and $v_{out}$ will experience shortage of $f^v$ flow units right after deletion (the flow constraints will be obviously broken). To make the flow constraints be held again we should rearrange flows, but also we want to keep the original flow value as high as possible. Let's see first if we can do rearrangement without decreasing the total flow. To check that find a maxflow $\tilde{f^v}$ from $v_{in}$ to $v_{out}$ in the "cutted" residual network (i.e. without the arc connecting $v_{in}$ and $v_{out}$). We should bound it by $f^v$ obviously. If it happen to be equal to $f^v$ then we are lucky: we have reassigned the flow which was passing through $v$ in such way that the total flow wasn't changed. In the other case the total flow must be decreased by "useless" excess of $\Delta = f^v - \tilde{f^v}$ units. To do that, temporarily connect $s$ and $t$ by an arc of infinite capacity and run maxflow algorithm again from $v_{in}$ to $v_{out}$ (we should bound flow by $\Delta$). That will fix residual network and make flow constraints be held again, automatically decreasing total flow by $\Delta$.

The time complexity of such updates may depend on maxflow algorithm we use. Worst cases may be pretty bad, though, but it's still better than total recalculating.

The second part is which maxflow algorithm to use. As far as I understand the author needs not very complex (but still efficient) algorithm with small hidden constant to run it on a mobile platform. His first choice of Ford-Fulkerson (I expect it to be Edmonds-Karp) looks not very bad from this point of view. But there are some other possibilities. The one I would recommend to try first is $O(|V|^2|E|)$ variant of Dinic's algorithm because it's quite fast in practice and can be implemented in a very simple way. Other options may include capacity scaling Ford-Fulkerson in $O(|E|^2 \log C_{max})$ and, after all, different versions of push-relabel with heuristics. Anyway the performance will depend on a use case so the author should find the best one empirically.


Is it possible to determine if a reduction is correct? Suppose we have an arbitrary term, x, in Lambda Calculus, or in an equivalent turing-complete system. Suppose we ask an oracle what is the normal form of that term, and it answers y. Is it possible to determine, in finite time, if the oracle answer's ir correct?

Secondary question: is there any system (non-turing complete, perhaps) where that would be possible?

I don't know what your "oracle" is, but without further information what you are asking is whether the following language is decidable:

$L:=\{ (t,u)\in\Lambda\times\Lambda \mathrel{|} t \rightarrow^* u, u \textrm{ normal}\}$

(with $\Lambda$ being the set of $\lambda$-terms). This is obviously not the case: for every Turing machine $M$, there is a $\lambda$-term $t_M$ (effectively computable from the description of $M$) such that $t_M$ reduces to a fixed normal form $u$ if $M$ terminates on the empty string and has no normal form otherwise; therefore, if $L$ were decidable, we would be able to decide the halting problem for $M$ on empty input by asking whether $(t_M,u)\in L$.

If your "oracle" gives more information, then of course the situation may very well be different.  For instance, if the oracle also gives an upper bound to the number of reduction steps needed to reach the purported normal form, then it is obviously decidable whether the oracle's answer is correct.

If you are actually asking about proof-carrying code (like D.W. suggests), please modify your question accordingly and I'll be happy to modify/remove my answer.


What evidence is there that $coRP \neq NP$? What evidence is there that $coRP \neq NP$?

$coRP$ is the class of languages for which there exists a probabililistic Turing Machine that runs in polynomial time and always answers Yes on an input belonging to the language and answers No with probability at least one half on an input not belonging to the language.

When considering the power of non-determinism (P vs NP), randomization seems like a 2nd order issue.  In particular when we think about "P=NP?" we are really interested in the question "are all NP problems tractable", where randomization could be allowed, so tractability really means "in BPP".  So "NP contained in BPP" seems essentially as unlikely as "P=NP", and in fact if these were considered different then people would care about the former rather than the latter.  (The peculiar variant "NP in coRP" is formally somewhere in the middle between these two, but conceptually essentially the same).    If good enough pseudo random generators exist then the two questions are formally the same.  Similarly, in "non-uniform settings" randomization is known not to help and thus "NP in BPP" implies that NP has poly-size circuits.


Is this edge orientation optimization problem NP-hard? Is the following optimization problem NP-hard?

Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\times d_{in}(v)$, where $d_{out}$ (resp. $d_{in}$) is the number of out-neighbors (resp. in-neighbors).

Motivation:
Assume the edge orientation does not induce any cycle of length 3, then the following algorithm lists all triangles in the input undirected graph in linear memory and in time $O(\sum_\limits{v\in V} ~d_{out}(v)\times d_{in}(v)+m+n)$ where $m$ is the number of edges and $n$ is the number of nodes.

For each node u:
  For each out-neighbor v of node u:
    For each out-neighbor w of node v:
      If u,w is an edge of the input undirected graph:
        output triangle u,v,w

Implementation details: the graph should be stored in a CSR-like format and, in addition, the edges of the input undirected graph should be put in a hashtable.
Finding the edge orientation that minimizes the quantity should lead to a faster algorithm. I think that the constraint "no induced cycle of length 3" is too complicated and, as a stepping stone, I've decided to formulate the above problem.
The question is related to that one where the edge orientation has to induce a DAG.
Another formulation: The problem can be written as the following Integer Quadratic Programming.
\begin{align}
 \text{Minimize} &\qquad \sum_{v\in V} y_v\times (d_v-y_v) &\qquad  (IQP)\\
 \text{s.t.} &\qquad \forall v \in V, \forall u \in N_v, x_{u,v}  \in \{0,1\}  \\
 &\qquad \forall (u,v) \in E, x_{u,v}+x_{v,u}=1\\
 &\qquad \forall v \in V, y_v=\sum_{u \in N_v} x_{u,v}\\
\end{align}
with $N_v$ the set of neighbors of node $v$ in the input undirected graph and $d_v=|N_v|$.
Is (IQP) NP-hard?

I believe that this problem is NP-hard, here is a sketch proof (don't hesitate to ask for more details if needed).
The idea is based on a reduction from the Not-all-equal 3-SAT. For $\varphi$ a 3-SAT formula with $m$ clauses, we will build $G(\varphi)$ a graph that has minimum objective value of $2\times m$ iif $\varphi$ has a solution. Before diving into the  building of $G(\varphi)$ let us show the gadgets that we will use.
Fixed node gadget:
The idea here is pretty simple. To fix a node $n$ in $G(\varphi)$ we make sure that $n$ has at least $2\times m+2$ neighbors in $G(\varphi)$ by adding nodes only linked to $n$. Once a node $n$ is fixed then any orientation with objective value less or equal $2\times m$ is such that $d_{in}(n)=0$ or $d_{out}(n)=0$.
Litteral gadget: For each variable $x_i$, we will create two fixed nodes $x_i$ and $\lnot x_i$ that will be linked together with an edge. Because the two nodes are fixed and linked, in any orientation of the graph with value less than $2m$, we will have either $d_{in}(x_i)=0 \land d_{out}(\lnot x_i)=0$ or $d_{out}(x_i)=0 \land d_{in}(\lnot x_i)=0$.
Clause gadget: The idea here is slightly more intricate. For each clause $C_j = l_1 \lor l_2 \lor l_3$ we will create three nodes $C_j^1$, $C_j^2$ and $C_j^3$ which are the red nodes in the graph drawn below. In this graph the three blue nodes will correspond to the three literals $l_1$, $l_2$ and $l_3$. Since the literals will be fixed nodes, we know the orientation for the blue-red edges (i.e. the dashed edges) and we want to compute the orientation of the red-red edges (i.e. the filled edges) that minimizes the objective value.

We can easily show that either all the dashed edges are in the same direction (i.e. all blue to red or all red to blue) in which case the minimum objective value is 4 or they are in diverse directions in which case the minimum objective value is 2.
Putting everything together:
If there is a solution to the not-all-equal problem we can orient the edges outward for true literals and inward for false literals and each clause triangle can be oriented in a way to have an error of $2$, therefore the overall error is $2\times m$. On the converse, if there is an orientation with error less or equal to $2\times m$ then we can retrieve a solution to the not-all-equal problem. Indeed, the fixed nodes have an in or out degree of 0 therefore we can say that literals with in degree equal to zero are true and the other are false. Since each literal is connected to its negation their value are coherent and it is a solution to the not-all-equal problem $\varphi$ because since each triangle clause has error at least 2 and the overall error is $2\times m$ it means that all triangle clauses are connected to a positive and a negative literal.


Problems that are hard to prove in $\mathcal{P}$ What is the famous "hard" problems that were shown to be in $\mathcal{P}$ after?

I want to know a list of problems that are difficult to prove in the class of "easy" problems?

Maybe like matching, linear programming. Any list or references would be appreciated.

The famous primality testing problem, shown to be in P in the 2000 paper PRIMES is in P.


Matrix rigidity and uses of matrices with low rigidity Roughly a matrix of rank $n$ is said to be rigid, if to bring its rank down to $\frac{n}{2}$, one has to change at least $n^{1+\epsilon}$ of its entries, for some $\epsilon > 0$.

If an $n \times n$ matrix $A$ is rigid, then the smallest straight line program computing $Ax$  ($x$ is a vector of size $n$) is either super-linear size, or has super logarithmic depth.

Is there a converse to the above statement?

In other words are there uses to non-trivial and non-obvious low rigidity matrices of full rank in TCS?

Is there a notion of rigidity for matrices with lower ranks (say $\frac{n}{c}$ for some constant $c$)?

lacking further clarification of the question, heres a try/sketch of an answer. matrix rigidity has deep connections to fundamental questions in TCS/complexity theory including circuit lower bounds,[1] and thereby complexity class separations, and coding theory[2] as well as other areas. [5] is a nice slide survey.

the terms "low" and "high" in reference to rigidty of matrices are used informally and not in a precisely defined technical sense. [although Friedman did define "strong" rigidity. [6]] random matrices are known to have high rigidity but basically, its ~a 3.5 decades old open problem in this area to explicitly construct any matrix with "significantly high" rigidity.

the question doesnt further define/clarify the subjective terms "nontrivial" or "nonobvious" & will take some freedom there.

in this area there is a line of research looking at the rigidity of Hadamard matrices which have misc uses/applications in coding theory & elsewhere.

it seems fair to say a provably high rigidity result would surpass the threshhold of leading at least to "new nontrivial corollaries in complexity theory" but the best known bounds on Hadamard matrices do not suffice.[3] but neither does this conclusively prove they have limited "low" rigidity. its basically the same story with Vandermonde matrices [also applications in coding theory] considered by Lokam.[4]

so to summarize about all that can be said is that "weak lower rigidity bounds" have been proven on some matrices including Hadamard/Vandermonde matrices.

there also do not appear to be any published numerical experiments, estimates, or algorithms in the area.

[1] Boolean Function Complexity by Stasys Jukna, 2011, sec 12.8 "rigid matrices require large circuits"

[2] On matrix rigidity and locally self-correctable codes Zeev Dvir

[3] Improved lower bounds on the ridigity of Hadamard matrices Kashin/Razborov

[4] On the Rigidity of Vandermonde Matrices Lokam

[5] Mahdi Cheraghchi matrix rigidity talk

[6] J. Friedman. A note on matrix rigidity. Combinatorica, 13(2);235-239, 1993


P vs. NP and Pseudorandom Bit Generators According to an article on pseudorandom number generators (PRNG) by Jeff Lagarias, he states that trying to prove that a PRNG is unpredictable (secure) is just "as hard" as trying to prove that P!=NP. If it is considered impossible to prove mathematically that some bit sequence is random then it should be mathematically impossible to prove P!=NP, right? Are these two problems really equivalent? If they are then why all the hoopla over P vs NP, you can never prove it either way according to these definitions.

There is a bit of an issue with your question. You are using the words unpredictable and secure interchangeably, which would seem to imply that you mean "unpredictable to a polynomial-time bounded  adversary". This is not at all the same thing as being truly unpredictable, since clearly there is a function (in this case the PRNG) which generates them. So this is not related to any issue with proving that the sequence is 'truly' random in some sense. Rather, what you really need is that given the prior output of the PRNG it is computationally hard to predict the next number.

This formulation is clearly related to P vs NP since clearly calculating a sequence of $m$ pseudo-random numbers using the generator is in FP (the functional version of P) when the key $k$ to the PRNG is known. However given a set of $m$ sequential pseudo-random numbers outputted by the device, the problem of finding $k$ is clearly in FNP (the functional version of NP).

Thus proving that it is computationally easy to generate the pseudo random numbers but computationally hard to infer the key from a sample of the output of the PRNG would imply that $FP \neq FNP$ (and hence $P\neq NP$).


Is there any work on purely functional approximation algorithms? It seems to me that approximating a solution to an NP-hard problem would be especially hard for the functional programmer.  For example, graph problems are commonly NP-hard.  But graphs are notoriously awkward to work with functionally.  This makes me think that problems that can be easily solved in a purely functional sense are somehow easier than those that require state.  This distinction in turn might shed some light on what makes hard problems hard.

So, is there any work on purely functional approximation algorithms?  My general impression is that both communities ignore each other.

I'm consolidating my comments into an answer.

First, it is hard to make being "awkward to implement" precise, so an empirical study of program length or development time for a number of approximation algorithms is in order to answer that question.

From a more theoretical viewpoint, every algorithm that can be implemented on a RAM with runtime $f(n)$ can be implemented in a purely functional language with runtime at most $O(\log n * f(n))$. This is because functional languages are turing complete and the simulation of mutable, random access memory via search trees causes logarithmic slowdown. Chris Okasaki's Purely Functional Data Structures shows how to implement search trees in a functional language.

Nowadays many approximation algorithms are designed for huge datasets and are written in the language of MapReduce or Pregel. This type of algorithm is very easy to translate to functional languages, as these distributed computing paradigms generally avoid stateful computations.

As a comment below notes, this question on Stack Overflow is closely related. In particular Edward Kmett gives references that show that under strict evaluation (i.e. not like the lazy evaluation you see in Haskell) there are examples where the logarithmic slowdown is necessary. It seems to be open whether this is also true in lazy settings.


Non-uniform lower bounds from uniform It is well known that lower bounds on circuits implies lower bounds on time complexity, just because circuits can efficiently simulate algorithms.

By the continuous work started by Ryan Williams, we know that upper bounds on the algorithms can imply circuit lower bounds [1].

Another connection between uniform and non-uniform complexities is that there exist algorithms that uses efficient circuits to gain a speed up. For example, first subquadratic algorithm for 3-sum [2] uses efficient decision trees.

I'm looking for results in the direction I haven't discussed yet: can lower bounds for time complexity imply lower bounds for circuit complexity. It is worth mentioning that algorithms that uses efficient circuits are taking advantage of the actual constructions rather then pure existence.

[1] Improving exhaustive search implies superpolynomial lower bounds. Ryan Williams.

[2]Threesomes, Degenerates, and Love Triangles. Allan Grønlund, Seth Pettie

MA $\subseteq$ PSPACE $\subseteq$ EXP $\subseteq$ NEXP  and  P/poly has undecidable unary languages, so

NEXP $\subseteq$ P/poly  $\implies$  NEXP $\subset$ P/poly  $\implies$  NEXP $\subseteq$ EXP .

As something like a generalization of that  (showing that EXP-complete languages are

in CHECK is difficult) ,  for all languages L in CHECK with a checker whose queries all have

length at most  nd ,  for all non-decreasing functions  S : {0,1,2,3,4,...} $\to$ {0,1,2,3,4,...} :

If L's circuit-size in bits is at most S then

L  $\in$  DSPACE$\left(\hspace{-0.04 in}\left(\hspace{-0.02 in}n^d\hspace{-0.05 in}\cdot \hspace{-0.03 in}S\hspace{-0.05 in}\left(\hspace{-0.03 in}n^d\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.04 in}+\hspace{-0.03 in}poly\hspace{.02 in}(n)\hspace{-0.03 in}\right)$  $\subseteq$  DTIME$\hspace{-0.02 in}\left(\hspace{-0.05 in}2^{\left(n^{\hspace{.02 in}d} \hspace{-0.02 in}\cdot S\left(\hspace{-0.02 in}n^{\hspace{.02 in}d}\hspace{-0.03 in}\right)\hspace{-0.03 in}\right)+\hspace{.02 in}poly\hspace{.02 in}(n)}\hspace{-0.04 in}\right)$   ,

so by contrapositive, if    L  $\not\in$  DTIME$\hspace{-0.02 in}\left(\hspace{-0.05 in}2^{\left(n^{\hspace{.02 in}d} \hspace{-0.02 in}\cdot S\left(\hspace{-0.02 in}n^{\hspace{.02 in}d}\hspace{-0.03 in}\right)\hspace{-0.03 in}\right)+\hspace{.02 in}poly\hspace{.02 in}(n)}\hspace{-0.04 in}\right)$

then L's circuit-size in bits exceeds S infinitely-often.

("in bits" as as opposed to "in gates".)

Similarly, for all functions T and $\ell$ and $S$ from {0,1,2,3,...} to {1,2,3,4,5,...},

for all search problems R in  FNTIME(T)  whose output-lengths are bounded above by $\ell$:

If R's circuit-size in bits is at most S then R is solvable by  FDTIME$\left(\hspace{-0.02 in}2^{S(n)} \hspace{-0.04 in}\cdot \hspace{-0.04 in}poly\hspace{.02 in}(S(n))\hspace{-0.04 in}\cdot \hspace{-0.04 in}T(n)\hspace{-0.03 in}\right)$ ,

so by contrapositive, if R is not solvable by  FDTIME$\left(\hspace{-0.02 in}2^{S(n)} \hspace{-0.03 in}\cdot \hspace{-0.03 in}\left(\left(\hspace{.05 in}poly\hspace{.02 in}(S(n)) \cdot \ell(n)\right)+ T(n)\right)\hspace{-0.03 in}\right)$

then R's circuit-size in bits exceeds S infinitely-often.


Algorithms for Interval Coloring with Capacities and Demands We are given a graph $G = (V,E)$, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $I_i = [s_i,t_i]$ associated with it, where $s_i$ is the source and $t_i$ is the destination vertex. A set of requests $\mathcal{R}$ is called feasible, if the total demand of all requests in $\mathcal{R}$ passing through any edge $e$ does not exceed it's capacity, i.e., $\sum_{i:e \in R_i} d_i \le c_e$ for all $e \in E$. The goal is to partition the requests $R_1,\ldots,R_k$ into a number of sets such that each set is feasible and the total number of sets is minimized. This problem is called Interval Coloring with Capacities and Demands. This is because we can think of this as coloring the requests in such a manner so that requests in each color class are feasible and we want to minimize the number of colors. This can also be thought of as routing the requests in a feasible manner in a number of rounds. We consider the special case where $G$ is a path $(v_1,e_1,v_2,e_2,\ldots,e_{n-1},v_n)$.

What is the best approximation algorithm and hardness result known for this problem?

If the demands satisfy the no-bottleneck assumption, that is $\max_i d_i \leq \min_e c(e)$ then a constant factor approximation is known even for trees. See http://dl.acm.org/citation.cfm?id=1273343 which gives a 48-approx for trees. For paths a better bound can be obtained and may have been shown but I am not sure where or whether it was published. For the general case it is not quite clear what the best known result is. One can get an easy $O(\log n)$-approximation as follows. Consider the problem of maximizing the number of requests that can be feasibly routed; there is a constant factor approximation for this problem, see http://arxiv.org/abs/1102.3643. Using this as a black box one can do a greedy set-cover like algorithm to repeatedly pack as many requests as possible to get the desired $O(\log n)$-approximation. A paper by Chalermsook on coloring rectangles may have some implications including giving an $O(\log \log n)$-approximation; the paper is available at http://sites.google.com/site/chalermsook/academic/coloring_full.pdf?attredirects=0. However it may require figuring out several technical details. One suspects that there is a constant factor approximation for the coloring problem.


Partitioning a segmented stick Problem :

We are given a stick partitioned into n - equal parts. Each of these parts has a weight, let's say x. Number of times x appears as weight of some part is guaranteed to be even.

For example consider the following stick with 6 parts -

1 2 2 1 3 3

So the stick has n parts, with weight of first part being 1, of second being 2, and likewise. Note that each weight appears even number of times.

Now, we need to cut the stick across these n partitions, and divide the parts into two users, and those two should have same weight in the end.

We divide the parts as follows -

Let's say I made first cut at y1, then from starting till y1 - this part goes to user1. Now, we make another cut at y2. Then from y1 to y2 goes to user 2. And so on alternatively.

So we need to find the minimum number of cuts in which we can do this fair division.

I couldn't find a polynomial time algorithm. And, problem appears to be NP - Hard. So, any good approximation algorithm for this problem ?

I'm not sure if I understand the problem specification correctly, but the problem looks a special case of the paint shop problem.  In that context, there is an NP-hardness result.

The main reference is: P. Bonsma, Th. Epping, and W. W. Hochstättler, Complexity results on restricted instances of a paint shop problem for words.  Discrete Applied Mathematics 154 (2006) 1335-1343.  http://dx.doi.org/10.1016/j.dam.2005.05.033

The abstract says as follows.

  We study the following problem: an instance is a word with every letter occurring twice. A solution is a 2-coloring of its letters such that the two occurrences of every letter are colored with different colors. The goal is to minimize the number of color changes between adjacent letters.

  This is a special case of the paint shop problem for words, which was previously shown to be NP-complete. We show that this special case is also NP-complete and even APX-hard. Furthermore, derive lower bounds for this problem and discuss a transformation into matroid theory enabling us to solve some specific instances within polynomial time.


NP-Complete Static Square Puzzles In order to empirically test some CSP algorithms, I would like to compile a list of NP-Complete static board games. By static, I mean that a solution of the puzzle is simply an assignment of values to each entry of the board, in such a way that the rules of the games are satisfied.

For instance, slitherlink,numberlink, sudoku, filomino, kakuro etc, are the types of puzzles I'm looking for.

Preferentially, the puzzles should satisfy the following conditions:

Scalability: The puzzle can be defined for $n\times n$ boards for each
$n$. Or if this is not possible, for each $f(n)$ where $f:{\bf N}\rightarrow {\bf N}$ is some
easy looking function.
An online library of instances for the puzzle should be available.

What would be online databases for such puzzles? For instance, the section Games and Puzzles of this wikipedia page has many square games satisfying condition 1. So what I'm really looking for is a of puzzles that also satisfy condition 2.

Please feel free to suggest more than one puzzle in one answer.

Two such puzzles that I know about are:

Unruly. This website has an online library of puzzles and solutions and a generator for puzzles of arbitrary size.
Masyu. This website has a library of puzzles and solutions. It also links to several variants of the puzzle.

Actually, the page where the Unruly puzzle is found lists more such puzzles, some of which satisfy your conditions, while others don't.


Survey on algorithms/complexity of linear algebra I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with emphasis on parallel ($NC$ hierarchy) and polytime algorithms. I could not find a recent one.

Do you know a good recent survey or book on complexity of linear algebra?

Two references you might find to be helpful:

  D. Bini and V. Pan.  Polynomial and matrix computations, Volume 1: Fundamental Algorithms.  Progress in Theoretical Computer Science, Birkhauser, 1994.

  J. von zur Gathen. Parallel linear algebra. In J. Reif, editor, Synthesis of Parallel Algorithms, chapter 13. Morgan Kaufmann Publishers, Inc., 1993.

They aren't necessarily recent, but they're a good starting point.


Intuition behind the Charikar's LP formulation for densest subgraph problem I understand why the LP gives the optimal solution for the densest subgraph problem. But don't understand the intuition behind the LP in this paper.
Just mentioning the LP for maximum density of a subgraph of G(V,E)

$$ \max{\sum_{(i,j) \in E} {x_{ij}}}$$
$$\text{s.t.}$$
$$\forall (i,j)\in E \quad x_{ij} \leq y_i$$
$$\forall (i,j)\in E \quad x_{ij} \leq y_j$$
$$\sum_{i \in V}y_i \leq 1$$
$$\forall (i,j)\in E, i \in V \quad x_{ij}, y_i \geq 0$$

Depending on how people interpret "research-level", this might need to be moved to cs.stackexchange.com.

The intuition becomes more apparent if you first write down an alternate similar looking but not necessarily linear mathematical program

$$\begin{eqnarray}
\textrm{maximize}\,\,&\tfrac{\sum_{(i,j) \in E} x_{ij}}{\sum_{i \in V} y_i}& \\
\textrm{subject to}\,\,& x_{ij} \leq y_i& \forall {(i,j) \in E}\\
& x_{ij} \leq y_j& \forall {(i,j) \in E} \\
& 0 \leq x_{ij} \leq 1 &\forall {(i,j) \in E} \\
& 0 \leq y_i \leq 1 &\forall {i \in V} \\
\end{eqnarray}$$

Integer solutions to this program have a simple interpretation, with $y_i = 1$ iff vertex $i$ is in a chosen subgraph, $x_{ij} = 1$ only if $(i,j)$ is an edge in the subgraph induced by the selected vertices, and the objective function coming directly from the definition of the densest subgraph. Unfortunately, the objective function as written is not valid for an LP.

The key observation is that the objective function is scale-free, in that dividing all $x_{ij}s$ and $y_i$s of a feasible solution by the same constant value $k \geq 1$ does not affect either feasibility of a solution or its corresponding objective function value. Hence, we can without loss of generality restrict our attention to the case that $\sum_{i \in V} y_i = 1$ (otherwise, we can divide all LP variables by exactly $k=\sum_{i \in V} y_i$ to ensure this). We make this restriction explicit by adding in the constraint $\sum_{i \in V} y_i = 1$. But, with this constraint in hand, the denominator of the objective function for the above program is exactly $1$. Hence, we can remove it from the objective, leaving us with something that is linear, and in particular with the LP in the original post.


On sparse complete sets and P vs L Mahaney's Theorem tells us that if there is a sparse $NP$-complete set under polynomial-time many-one reductions, then $P = NP$.  (See "Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis")

Are there known consequences of the existence of sparse complete sets for other complexity classes?  In particular, if there is a sparse $P$-complete set under logspace many-one reductions, does that imply $P = L$?

Yes, exactly what you suggested is true: if there is a sparse $\mathbf{P}$-complete set under log-space many-one reductions, then $\mathbf{P} = \mathbf{L}$. This was conjectured by Hartmanis in 1978 and proven by Cai and Sivakumar in 1995. See this paper.

Hartmanis also conjectured that if there is a sparse $\mathbf{NL}$-complete set under log-space many-one reductions, then $\mathbf{NL} = \mathbf{L}$. This was also proven by Cai and Sivakumar in 1997; see this other paper.


Is there any work relating type systems and Cook-Reckhow proof systems? An important subfield of computational complexity is proof complexity, mostly due to Cook and Reckhow. E.g. one notable result is that a proof system that has efficient proofs (i.e., in length polynomial to the formula being proven) for all tautologies could be constructed iff $coNP$ = $NP$. Other results deal with specific propositional calculus proof systems, showing that they all have superpolynomial proof lower-bounds. Is there any work relating type systems and type inference rules to the proof systems as defined in this theory?

In general, a cursory examination reveals that most discussions of type systems discuss computability (decidability/undecidability) with little discussion of finer complexity bounds (which may well exist in many finite models). Is there a reason why this is so (if indeed it is so)?

Cook-Reckhow propositional proof systems are nonunifrom.
E.g. the computational complexity counterpart to
the class of polynomial-size $\mathsf{Extended Frege}$ proofs is
the nonuniform complexity class $\mathsf{P/poly}$.
We have to look at their uniform counterparts:
E.g. the proof complexity counterpart for $\mathsf{P}$ are
bounded arithmetic theories like
Cook's theory $\mathsf{PV}$ (standing for polynomial-time verifiable),
Buss's theory $\mathsf{S}^1_2$, ...

Cook and Urquhart used Cook's theory $\mathsf{PV}$
to define a theory of higher-types polynomial-time computable functions $\mathsf{PV}^\omega$ in the following paper:

Stephen A. Cook and Alasdair Urquhart, "Functional interpretations of feasibly constructive arithmetic", 1993. doi: 10.1016/0168-0072(93)90044-E

There has been some follow up work which you can find by looking at articles citing this paper.

Implicit complexity theory that Martin mentions is also influenced by this work. Check out Simone Martini's survey slides and Ugo Dal Lago's survey article to get a picture of what is implicit complexity theory and its history.


Are there NP-complete problems with polynomial expected time solutions? Are there any NP-complete problems for which an algorithm is known that the expected running time is polynomial (for some sensible distribution over the instances)?

If not, are there problems for which the existence of such an algorithm has been established?

Or does the existence of such an algorithm imply the existence of a deterministic polynomial time algorithm?

There is a polynomial time algorithm for finding Hamiltonian cycles on random graphs, that succeeds asymptotically with the same probability that a Hamiltonian cycle exists. Of course, this problem is NP-hard in the worst case.

They also show that a dynamic programming algorithm which is always guaranteed to find a Hamiltonian cycle, if it exists, has polynomial expected running time, if the input distribution is uniformly random over the set of all $n$ vertex graphs.

Reference: "An algorithm for finding Hamilton cycles in random graphs"

Bollobas, Fenner, Frieze

http://portal.acm.org/citation.cfm?id=22145.22193


Smoothly leaking information over time Say I have a one bit random variable $X \in \{0,1\}$, and let $n$ be a natural number.  I want a sequence of random variables $0 = X_0, X_1, \ldots, X_n = X$ s.t.

$$H\left(X~|~\{X_0,\ldots,X_k\}\right) = 1-\frac{k}{n}$$

That is, each additional $X_k$ provides $1/n$ of the information of $X$, until everything is revealed by $X_n = X$.  Is there a nice construction for this sequence?

Via Michael Kass: let $Y(t)$ be a Wiener process starting at $Y(0) = X$, and define

$$f(t) = H(X~|~Y(t))$$

Then $f(0) = 0$, $f(\infty)=1$, and $f(t)$ is smoothly strictly increasing in between.  Thus, for any $k$ we can find $0 \le t \le \infty$ s.t. $X_k = Y(t)$ has the desired conditional entropy ($t$ will be a decreasing function of $k$).


Hidden Constants in Complexity of Algorithms For many problems, the algorithm with the best asymptotic complexity has a very large constant factor that is hidden by big O notation. This occurs in matrix multiplication, integer multiplication (specifically, the recent O(n log n) integer multiplication algorithm of Harvey and van der Hoeven), low-depth sorting networks and finding graph minors, to make a few. Such algorithms are sometimes called Galactic algorithms.

Note that for other algorithms, such as general sorting and integer addition, algorithms are known with optimal asymptotic complexity and small constant factors.

What research has been done in separating the former algorithms from the latter algorithms, from a theoretical perspective?

I am aware that hidden constants are often omitted to hide the distinction between different models of computation. However, I am confident that under a wide variety of different models, these Galactic algorithms will be slower than asymptotically worse algorithms for inputs of size one billion, for instance. The distinction is not subtle, in some cases. Has it been made rigorous?

For instance, one could invent a very simple model of computation, such as a von Neumann machine with a very simple ISA, and then implement the algorithms and bound their running times with explicit constants. Has this been done for a variety of algorithms?

One place where this is approached in an interesting way for a certain class of algorithms and combinatorial problems is in analytic combinatorics. The main approach described is similar to what you suggest: you start with some concrete implementation of an algorithm and identify some repeated operation (typically the heaviest one) that you'll use to associate an explicitly countable complexity for the execution of input of a given size $N$ in the form of the number $C_N$ that the chosen operation is performed.

The methodology does not require to fix any specific model of computation, although that could be useful of course. Also note that you could either try to compute the worst case behavior or the expected behavior, or still something else.

The most important ingredient in this methodology is the analysis of the generating functions of these values. You can sometimes obtain very precise asymptotic approximations using methods from complex analysis.

A simple example that is treated in the book is quicksort. This has a quadratic worst case running time, but in practice outperforms most $\mathcal O(n\log n)$ algorithms. When making a precise analysis of the expected cost of quicksort and you compare it to mergesort, you see that it is expected to outperform the latter from a size of around 10, if I remember correctly. To be able to compute this kind of things you cannot disregard the hidden constants of course.

In fact, in quicksort you sort a list by recursively sorting sublists, so that you would get an improvement for all sizes if you use mergesort on lists smaller than size 10. An interesting note in the book mentions that in some open sourced Microsoft library, the generic sort algorithm is implemented as quicksort until you get down to a size of 10, after which mergesort is used. In the code comments it is mentioned that performance tests showed this value to be optimal.


Parameterized complexity of Hitting Set in finite VC-dimension I'm interested in the parameterized complexity of what I'll call the d-Dimensional Hitting Set problem: given a range space (i.e. a set system / hypergraph) S = (X,R) having VC-dimension at most d and a positive integer k, does X contain a subset of size k that hits every range in R?  The parameterized version of the problem is parameterized by k.

For what values of d is the d-Dimensional Hitting Set problem

in FPT?
in W[1]?
W[1]-hard?
W[2]-hard?

What I know can be summarized as follows:

1-Dimensional Hitting Set is in P and is therefore in FPT.  If S has dimension 1 then it is not difficult to show that either there is a hitting set of size 2 or the incidence matrix of S is totally balanced.  In either case we can find a minimum hitting set in polynomial time.
4-Dimensional Hitting Set is W[1]-hard.  Dom, Fellows, and Rosamond [PDF] proved W[1]-hardness for the problem of stabbing axis-parallel rectangles in R^2 with axis-parallel lines.  This can be formulated as Hitting Set in a range space of VC-dimension 4.
If no restriction is placed on d then we have the standard Hitting Set problem which is W[2]-complete and NP-complete.
Langerman and Morin [citeseer link] give FPT algorithms for Set Cover in restricted dimension, though their bounded dimensionality model is not the same as the model defined by bounded VC-dimension. Their model does not seem to include, for example, the problem of hitting halfspaces with points, though the prototype problem for their model is equivalent to hitting hyperplanes with points.

I think this problem is too hard. We do not know the answer to much easier problems in this family. For example, given a set of n points in the plane, and a set of (say n) unit disks, decide if there is a cover of the points by k of the unit disks. There is an easy n^O(k) time algorithm for this, and I would not be surprised if using known insights one can do n^O(sqrt{k}) (but even that is not obvious), but doing f(k)*n^{O(1)} is open, and in fact would be quite interesting. A (1+eps) approximation follows from the work of Mustafa and Ray http://portal.acm.org/citation.cfm?id=1542362.1542367.

BTW, for the continuous version where any unit disk is allowed, one can solve the problem in n^{O(k)} time. A PTAS in this case is also pretty easy using shifted grids.


Type for "ways values can be different" I am looking for a concept in type theory that I am sure has probably been explored, but do not know the name behind.

Let's consider a ML-like language with product and sum types and a Hindley-Milner like type system. I'll use OCaml syntax.

I'm wondering about ways two different values can be different.

Use

My use case is writing "clearer" error messages in a xUnit-like library: if two values are different when they were expected to be equal, this can help build a clearer better message:

Before:

  Values differ: expected {x = [1;2;3;4], y = "a long string"}, got {x = [1;2;3;3], y = "a long string"}

After:

  Values differ: at position .x[3], expected 4, got 3.

(there might be a relation with functional lenses since we're ultimately constructing a lens to a smaller value which differs).

Product types

For example:

type p =
  { x : int
  ; y : string
  }

Equality can be defined as:

let equal a b =
  equal_int a.x b.x && equal_string a.y b.y

But it's also possible to reify the differences:

type delta_p =
  | Equal
  | Diff_x of int * int
  | Diff_y of string * string

let diff_p a b =
  if not (equal_int a.x b.x) then
    Diff_x (a.x, b.x)
  else if not (equal_string a.y b.y) then
    Diff_y (a.y, b.y)
  else
    Equal

(it might make sense to define a delta_int type as int * int to show that it is recursive)

Sum types

For a sum type there are more ways to differ: having a different constructor, or a different value

type s = X of int | Y of string

type ctor_s =
  | Ctor_X
  | Ctor_Y

type delta_s =
  | Equal
  | Diff_ctor of ctor_s * ctor_s
  | Diff_X of int * int
  | Diff_Y of string * string

let diff_s a b = match (a, b) with
  | X xa, X xb ->
    if equal_int xa xb then
      Equal
    else
      Diff_X (xa, xb)
  | (* Y case similar *)
  | X _, Y _ -> Diff_ctor (Ctor_X, Ctor_Y)
  | Y _, X _ -> Diff_ctor (Ctor_Y, Ctor_X)

What's the name of this concept? Where can I learn more about this?

Thanks!

I think you are looking for a typed variant of anti-unification. Anti-unification can be described as follows. First, suppose that we have a grammar of terms as follows:

t ::= () | (t, t) | C t | X

Here, () and (t, t) denote units and pairs, C t is a term with a leading constructor, and X is a term variable, which could be substituted for any term.

The anti-unification problem says, if you give two terms t1 and t2, what is the least general term t such that there are substitutions s1 and s2 such that s1(t) = t1 and s2(t) = t2.

As a concrete example, given two terms

t1 = Cons(3, Cons(2, Cons(1, Nil)))
t2 = Cons(1, Cons(2, Cons(3, Nil)))

the anti-unification algorithm would return the anti-unifier

t = Cons(X, Cons(2, Cons(Y, Nil)))

because the substitutions s1 = [X:3, Y:1] and s2 = [X:1, Y:3] applied to t would give you t1 and t2 back. As an aside, we needed to  specify "least general" because otherwise:

t' = Z

with the substitutions s1 = [Z:t1] and s2 = [Z:t2] would do the trick.

Anti-unification was invented by Gordon Plotkin, and is a delightfully simple algorithm. Assume you have an injective name-generation function gen $: \mathrm{Term} \times \mathrm{Term} \to \mathrm{Var}$. Then we can find an antiunifier as follows

antiunify ()       ()         = ()
antiunify (t1, t2) (t1', t2') = (antiunify t1 t1', antiunify t2 t2')
antiunify (C t)    (C t')     = C (antiunify t t')
antiunify t        t'         = gen(t, t') -- default: t and t' dissimilar

Augmenting this algorithm to return the two substitutions s1 and s2 I leave as an exercise.


Clique graph of bipartite graphs The clique graph $C$ of a given graph $G$ has the maximal cliques of $G$ as vertices and their is an edge between two vertices in $C$ iff the corresponding cliques share some vertices.

Now for chordal graphs, this clique graph is a tree and for proper interval graphs it is a path. Incidentally for both these graphs the max-clique recognition algorithm runs in polynomial time.

My question is are there other class of graphs who has characterization in terms of its clique graph. ? I am specially looking for such characterisations for bipartite graphs.

Any link to paper/journal is welcome.

I recommend you taking a look at this book chapter:

J. L. Szwarcfiter, A Survey on Clique Graphs, Recent Advances in Algorithms and Combinatorics,
CMS Books in Mathematics 2003, pp 109-136.

In there, many characterizations of clique graphs of specific classes are given. For example, it is mentioned that the clique graphs of chordal graphs are the dually chordal graphs and clique graphs of proper interval graphs are also proper interval graphs, and not trees and paths as you supposed.


What are semantic classes that have a syntactic equivalent? This question is related to Benefits for syntactic and semantic classes.
As mentioned there, $\mathsf{PSPACE} = \mathsf{IP}$, which can be interpreted as the semantic class $\mathsf{IP}$ obtaining a syntactic definition.
What are other non-trivial examples for "syntacticizing" a class?

FWIW, the ostensibly semantic class APP defined in [1] was shown to be syntactic in [2].

[1] Valentine Kabanets, Charles Rackoff, Stephen A. Cook, Efficiently
  approximable real-valued functions, ECCC Report TR00-034, 2000.

[2] Emil Jeřábek, Approximate counting in bounded arithmetic, Journal of Symbolic Logic 72 (2007), no. 3, pp. 959–993. doi, preprint


NP-Hardness of a special case of orthogonal packing problem Let $V$ be a set of $D$-dimensional rectangular shapes. For $d \in \{1,...,D\}$ and $v \in V$, $w_d(v) \in \mathbb{Q}^{+}$ describes the length of $v$ in the dimension $d$. The same notation is used for the container $C$.
The $D$-dimensional orthogonal packing problem (OPP-$D$) is to decide if $V$ fits into the container $C$ without overlapping. Formally speaking, the problem is to find out whether $\forall d \in \{1,...,D\}$ there exists a function $f_d:V\rightarrow \mathbb{Q}^{+}$, such that $\forall v \in V, f_d(v)+w_d(v) \leq w_d(C)$ and $\forall v_1,v_2 \in V$, $(v_1 \neq v_2)$, $[f_d(v_1),f_d(v_1)+w_d(v_1)) \cap [f_d(v_2),f_d(v_2)+w_d(v_2)) = \emptyset$.

The problem is NP-complete (see Fekete SP, Schepers J. "On higher-dimensional packing I: Modeling". Technical Report 97–288, University at zu Köln, 1997). The problem is NP-complete even for $D=2$. I am wondering, whether the orthogonal packing problem for a bounded number of types (i.e. sizes in each dimension) of items is still NP-complete or not. Till now I found a result in some paper about NP-completeness of packing squares into a square (see JOSEPH Y-T. LEUNG, TOMMY W . TAM, AND C. S. WONG, "Packing squares into a square", Journal of Parallel and Distributed Computing, Volume 10 Issue 3, Nov. 1990) which is already a restriction but I still don't know what happens when the number of types of items is bounded.

Thank you for your answer,

I think that the paper by Klaus Jansen and Roberto Solis-Oba "An OPT + 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths" has a partial answer to your question. They consider a special case of your problem known as Cutting Stock problem when the number of diﬀerent object types is constant and defined as follows:

  In the cutting stock problem we are given a set $T = \{T_1,T_2,\dots,T_d\}$ of object types, where objects of type $T_i$ have positive integer length $p_i$. Given an inﬁnite set of bins, each of integer capacity $\beta$, the problem is to pack a set $\mathcal{O}$ of $n$ objects into the minimum possible number of bins in such a way that the capacity of the bins is not exceeded; in set $\mathcal{O}$ there are $n_i$ objects of type $T_i$, for all $i =1,\dots,d$.

The authors claim that

  it is not known whether the cutting stock problem can be solved in polynomial time for every ﬁxed value $d$.

And they propose $OPT+1$ approximation polynomial-time algorithm when $d$ is fixed.

Since it's not proved that this special case is in $P$, this is the evidence that your problem is $NP$-hard.

Addendum: it's known that the case with two object types ($d=2$) is polynomially solvable, but for $d=3$ there is known only $OPT+1$-approximation.


Cohomological approach to boolean complexity A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this line of thought brought any new insights into boolean complexity, or does it remains rather a mathematical curiosity?

I corresponded with Joel Friedman about 3 years ago on this topic.  At the time he said that his approach had not led to any significant new insights into complexity theory, though he still thought it was a promising tack.

Basically, Friedman tries to rephrase the problems of circuit complexity in the language of sheaves on a Grothendieck topology.  The hope is that this process will allow geometric intuition to be applied to the problem of finding circuit lower bounds.  While it's certainly worth checking to see if this path leads anywhere, there are heuristic reasons to be skeptical.  Geometric intuition works best in the context of smooth varieties, or things that are sufficiently similar to smooth varieties that the intuition doesn't totally break down.  In other words, you need some structure in order for geometric intuition to gain a foothold.  But circuit lower bounds by their very nature must confront arbitrary computations, which are difficult to analyze precisely because they seem to be so structureless.  Friedman admits right up front that the Grothendieck topologies he considers are highly combinatorial, and far removed from the usual objects of study in algebraic geometry.

As a side comment, I'd say that it's important not to get too excited about an idea just because it uses unfamiliar, high-powered machinery.  The machinery might be very effective at solving the problems that it was designed for, but for it to be useful for attacking a known hard problem in another domain, there needs to be some compelling argument why the foreign machinery is well adapted to address the fundamental obstacle in the problem of interest.


Measures of "correlation" between two orderings An easy question perhaps?

Taking a (fictional) concrete example, let's say I have two ranking methods for HTML documents: PageRank and HITS. I derive an ordered list over the same set of documents according to their rank values (there can be ties) for both ranking methods.

Now, I want to quantify how much the two orderings correlate. I'm not interested in the absolute values of the ranking measures, but I'm looking for measures of correlation between the orderings.

I can think of some intuitive correlation measures one could apply like "average distance" or such:

${\displaystyle\frac{\sum_{doc_i\in Docs}\mathrm{abs}(pos_{rank1}(doc_i) - pos_{rank2}(doc_i))}{|Docs|^2}}$

but I'm wondering if anyone knows of any standard techniques I could check out?

In particular, I would prefer a symmetric measure which is easy to intuit and whose results are tangible/"portable". I've a number of different orderings which I'll be comparing pair-wise, but the set of $Docs$ remains the same.

Many thanks in advance!

(having difficulty tagging... please feel free to edit tags)

The standard approach to computing the correlation between two total orders is Kendall's $\tau$, defined as the difference between the number of agreeing pairs and disagreeing pairs (in rank) divided by $\binom{n}{2}$.

If you only have partial orders, then things get a little trickier.


$\mathsf{NC^1}$ circuit evaluation Is it known if $\mathsf{NC^1}$ circuit evaluation problem is in $\mathsf{NC^1}$?
  How about $\mathsf{ALogTime}$ (uniform  $\mathsf{NC^1}$)?

We know that circuits of depth $k$ can be evaluated with circuits of depth $k+c$
where $c$ is a universal constant.
This means circuits of depth $k\lg n + o(\lg n)$ can be evaluated by
a circuit of depth $O(\lg n)$.
However $O(\lg n)$ doesn't contain a function that eventually dominates all functions in $O(\lg n)$.

We know that formula evaluation problem is in $\mathsf{ALogTime}$. Every $\mathsf{NC^1}$ circuit is equivalent to a Boolean formula. Can't we compute the extended connection representation of an equivalent Boolean formula from that of a given $\mathsf{NC^1}$ circuit in $\mathsf{ALogTime}$?

The extended connection representation of a circuit includes

the number of gates in the circuit,
the type of each gate, and
for every gate $g$ and every path $\pi$ in the DAG of the circuit the gate reached from $g$ following path $\pi$.

A path is given by a 0/1 sequence where 0 represents moving to the left parent and 1 represents moving to the right parent. Note that the number of paths is polynomial: the length of the paths is bounded by the depth of the circuit.

As far as I know, $\mathsf{NC^1}$ evaluation is not known to be in $\mathsf{NC^1}$, and is conjectured to be outside $\mathsf{NC^1}$. See

Emil Jerabek, "On theories of bounded arithmetic for $\mathsf{NC^1}$",  Ann. Pure Appl. Logic 2011


Are finite state automata with one register storage equivalent to push down automata? This is a very simple question, but I couldn't find a reference and I just wanted to check my facts. I was looking for a state machine similar to pushdown automata but where the stack is restricted to one element (i.e. a register).

It occurred to me that if the register has an infinite alphabet (of possible values) it will basically be equivalent to a PDA. Every configuration of the stack could be represented by a single element of the register's alphabet. (E.g. let's say that the register's alphabet is the set of natural numbers). Is this correct?

Furthermore, a DFSM is equivalent in strength to a NFSM. However, I assume that (DFSM + 1 register) would not be equivalent to a (NFSM + 1 register) since DPDA and NPDA are not equivalent?

As pointed out in the comments, the power of such devices depends on the operations that they are allowed to perform on the ''register''. Here is a classic example of a class that captures all regular, but not all context-free languages.

If you restrict a PDA so that there is only one stack symbol, apart from the bottom-of-the-stack, the device is called a one-counter automaton.
I'm unsure what a standard reference is, but you can have a look, for instance, at this paper by Valiant and Paterson in LNCS, vol. 2 (1973).

For such a device, the set of all possible stack configurations is infinite (non-negative integers), but when it comes to operations on the stack, you can only increment and decrement the value by $1$ and test for $0$. This class of automata is strictly less powerful than the class of all pushdown automata; restricting it further with determinism results in an even weaker class. Also note that if you go for two counters instead of one, then even with deterministic machines you reach undecidability (even for the word problem, i.e., given a word, decide whether it is accepted).

Some proofs and additional information can be found here and here.


Distinguishing a biased coin with a small set of tests Say we have a "coin" $f : [n] \to \{\pm 1\}$ so that either $f$ is balanced, or $f$ is $\epsilon$-far from being balanced.

It's a classic result that sampling $O(1/\epsilon^2)$ random points of $f$ are enough to determine if $f$ is biased. That is, if $\mathcal{F} = \binom{[n]}{O(1/\epsilon^2)}$ is the collection of all subsets of size $O(1/\epsilon^2)$, then with probability at least $2/3$ over a random choice of a set $S$ from $\mathcal{F}$, the bias of $S$ will be within $\epsilon/2$ of the true bias of $f$ (correctly determining if $f$ is balanced/unbalanced).

Are there smaller families $\mathcal{F}$ that have the same property? For example, is it possible to find a collection of poly($n, 1/\epsilon)$ sets where 2/3 of the sets have bias close to the bias of $f$, for any $f$ either balanced or $\epsilon$-far from balanced?

Yes. Such families are called "averaging samplers", and there are plenty of constructions for them. You can find a more information about them (and about the more general notion of sampler) in this survey.

The notion of averaging samplers was introduced in this paper, which also showed that they are equivalent to randomness extractors. There are many constructions of extractors, and you can use any of them to construct samplers.

Here are a few relatively simple ways to construct such families:

Take a random family, as pointed out by Emil Jerabek in the comments.
Construct a family using a $k$-wise independent hash function, as pointed out in the comments by D.W.
Construct a family by considering an expander graph over the vertex set [n] and taking the neighborhood of radius $r$ around every vertex (for some sufficiently large values of $r$) - see for example this lecture. Alternatively, take the family obtained from the set of random walks of length $r$ on the graph. -- see for example this lecture  .


Promise Variant of Set-Packing An instance of the SET-PACKING problem is given by a list of sets $\mathcal{S} = \{S_1,\dots,S_m\} \subseteq 2^U$. It is a ``yes'' instance iff there exists some subset $\mathcal S'$ of $\mathcal S$ of size $\ge k$ such that for every $S,T \in \mathcal S'$, $S\cap T = \emptyset$.

Now, I propose the "promise variant" of this problem: I am telling you that your instance is a yes instance; that is, there exists some $\mathcal T'\subseteq \mathcal S$ such that all elements of $\mathcal T'$ are disjoint and it is of size $\ge k$. Can you find some $\mathcal S'$ that is of size $\ge k$ with all disjoint elements?

This seems to be an obviously NP-hard problem, but one needs to be slightly careful in the proof: intuitively, simply taking an instance of SET-PACKING and appending k arbitrary disjoint sets will work (informally, if finding them is in P, then SET-PACKING is also in P).

This relates to a similar question that appeared in cs.stackexchange. I am aware that promise variants of NP hard problems are generally hard (that is, given an NP hard problem X, define promise-X to be the problem X when a yes instance is guaranteed).

Suppose that there was a polynomial time algorithm $A$ for your promise problem, say with time complexity bounded by $const*|U|^a*m^b$.

Take an arbitrary instance of SET-PACKING (the original variant, not the priomise variant) and run algorithm $A$ on it for $2*const*|U|^a*m^b$ steps.
If $A$ does not terminate within this time bound, the answer must be NO.
If $A$ does terminate, verify whether the output produced by $A$ indeed is a feasible solution.

This would allow you to solve the original SET-PACKING problem in polynomial time.


It is known that $L \subsetneq PH$? Is it known whether $Logspace$ is strictly contained in the polynomial time hierarchy ?
Are there oracles relative to which these classes are equal / distinct ?

This is equivalent to $LOGSPACE≠NP$ (which is obviously open). The proof of that equivalence relativizes (at least under the usual oracle models).
And there are oracles making $LOGSPACE = NP$ (the PSPACE-complete TQBF works) and making them not equal (the oracle separating P from NP works).


Assignment problem with multiple workers for each job I am wondering if there are any results on the following version of the assignment problem.  We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given the expertise of the worker for the job $\omega(w,j)$.  The goal is to select a subset of jobs $S\subseteq J$ and assign exactly two workers to each job $j \in S$ while maximizing the total expertise.

That is, if $x_{w, j} = 1$ indicates that the worker $w$ has been assigned to job $j$, solve the following program:

$$
maximize \sum_{j \in S}  x_{w, j} \cdot \omega(w, j)
$$
s.t.
$$
\sum_{j\in S} x_{w, j} \leq 1,  \forall w\in W
$$
$$
\sum_{w\in W} x_{w, j} = 2, \forall j \in S
$$
$$
x_{w, j} \in \{0, 1\}
$$

Edit:

It seems like my explanation is not very clear so I am adding a simple example.  Consider the following graph where dotted edges have weight 0 and solid edges have weight 1.  Worker $i$ has expertise $1$ in job $i$ and expertise $0$ in the other job.

The two possible solutions both have value 1: either assign both workers to job 1, or assign both workers to job 2.  Observe that assigning worker 1 to job 1 and worker 2 to job 2 would result in a solution of value 2, but it is not a valid solution since a job must be assigned exactly 2 workers.

This problem is a special case of the b-matching problem, and hence can be solved in polynomial time. Extensive information on b-matchings can be found for instance in the book:

László Lovász and Michael D. Plummer:
Matching Theory
ISBN-10: 0-8218-4759-7
ISBN-13: 978-0-8218-4759-6


Standard reference for basic model theory definitions I am trying to give a formal presentation of the model-theoretical semantics of a language and I am a bit lost in the terminology. In particular, could somebody clarify the exact definitions of model-structures or pre-interpretations, interpretations and interpretation functions ? It would be great if you could point me to a standard reference.

The way I see it, a "pre-intepretation structure" is defined for the signature of a particular language/logic as regrouping a domain and a mapping ("interpretation function" ?) of constants and predicates to that domain.  Next, one has to assign particular truth values to each of the constructs of the language, according to a specific "interpretation" and valuation. Is this the standard terminology ? Thank you !

Here is one possibility, but other people might use different words. I will use first-order logic as a running example.

Language

The language is a collection of expressions, which are syntactic entities, i.e., finite configurations without any a priori meaning. A language is described by the grammar, which determines which finite configurations are valid expressions.

A language may have several kinds of expressions, for instance terms and formulas, each obeying their own grammar.

The expressions of a language may be represented in different ways. When they are written as strings of characters that is called concrete syntax. When the expressions are represented as abstract mathematical configurations (usually trees of some sort) that is called abstract syntax. The process of passing from the concrete to the abstract syntax is parsing.

When we manipulate the language in a mathematical way it is best to use the abstract syntax so we do not have to deal with silly things like parentheses and spaces.

It may happen in certain situations that the language is so complicated that simple grammatical rules do not suffice to describe the valid expressions. For example, in type theory you may have to prove that a certain expression is valid, and the proof can be arbitrarily complex. In such situations people may speak of "pre-expressions" or "pre-terms" described by the grammar.

First-order logic: there are two kinds of expressions, the terms and the formulas. In each particular situation we also have a list of chosen constant symbols, function symbols, and relation symbols. For instance, the first-order language of an ordered fields has (in addition to the usual logical connectives, $=$, and variables) the constant symbols $0$ and $1$, the function symbols $+$, $\times$, $-$, and the relation symbol $<$.

Structure

It is our intention to give the language a mathematical meaning. For this purpose we first need to describe the mathematical objects that parts of the language map to. Such a mathematical object, or collection of objects, or a category, is called a structure. The structures have to be sufficiently rich to support the interpretation of all the parts of the language.

First-order structure: is a carrier set $S$ together with a list of constants (elements of $S$), functions (mapping from $S^n \to S$) and relations (subsets of $S^n$).

Interpretation

An interpretation is the mapping of the language into the structure. It may be called the "interpretation function".

In complicated situations one might provide an interpretation in several layers, in which case you could the first layer pre-interpretation, etc.

First-order interpretation: The terms are mapped to the elements of the carrier set $S$, the formulas are mapped to propositional functions (mapping from $S^n$ to truth values). A formula is valid in a given interpretation if it is mapped to the propositional function which always gives the value "true".

Formal system

A formal system consists of a language and rules for deriving judgements.

First-order logic: In first-order logic there is just one kind of judgement, $$\phi_1, \ldots, \phi_n \vdash \phi$$ whose intuitive meaning is "$\phi$ is proved from hypotheses $\phi_1, \ldots, \phi_n$".

Just to give you another kind of judgement: in programming languages a typical judgement might be $e \Downarrow v$ with the intuitive meaning "program $e$ computes to value $v$".

Theory

The notion of a theory is somewhat specific to logic (it makes less sense when we speak about programming languages or type theory) where we have a notion of a logical formula.

Given a specific language, say that a set $T$ of logical formulas is deductively closed if any formula that can be derived from formulas in $T$ is again an element of $T$.

Every set of formulas $T_0$ has the deductive closure, which is the least set $T$ that contains $T_0$ and is deductively closed. We get $T$ from $T_0$ by adding to $T_0$ all of its consequences, and consequences of consequences, and so on.

A theory is a deductively closed set of formulas. It is usually (but not necessarily) gives as the deductive closure of a chosen set of formulas called the axioms.

Model

Given a theory $T$ and a structure $S$, a model is an interpretation of the language of $T$ into $S$ such that every formula in $T$ is valid in $S$.


What would signify hierarchy collapse to first level? We know that
$$\mathsf{NP\subseteq P/Poly \iff coNP\subseteq P/Poly\implies PH=\Sigma_2^P}=\mathsf{\Pi_2^P}$$
$$\mathsf{NP\subseteq P/Log\iff coNP\subseteq P/Log\implies PH=\Sigma_0^P=\Pi_0^P}$$

  Is there any circuit result that could imply
  $$\mathsf{PH=\Sigma_1^P=\Pi_1^P}$$ but still $$\mathsf{PH\neq\Sigma_0^P=\Pi_0^P}$$ is a possibility?

  Is there a possible similar collapse result from non-circuit containment?

Conjecture:

  Such result does not exist.

It is perhaps reasonable to think that circuits that people would come up with would come along with easily verifiable proofs of their correctness. (This was indirectly inspired by Dietrich & Wilson's notion of "groups of black box type", and is in the spirit of Hartmanis's "provable complexity.") Towards this end, we consider:

Definition: "Certified $\mathsf{P/poly}$" or "$\mathsf{Cert}$-$\mathsf{P/poly}$" consists of those languages $L$ such that $L$ is in $\mathsf{P/poly}$ and there is a poly-bounded certification of this fact. More precisely, $L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$ if there exists a poly-time $V$, and for all $n$, there exists $C_n, \pi_n$ with $\max\{|C_n|,|\pi_n|\} \leq poly(n)$ such that

$V$ is a Cook-Reckhow proof system for the language $\{C : C \text{ correctly computes } L \text{ at length } \ell=\text{# inputs to C}\}$, that is (a) If $C(x) = L(x)$ for all $x \in \Sigma^\ell$, where $\ell$ is the number of inputs to $C$, then there exists a $\pi$ such that $V(C,\pi)=1$ and (b) If there is $x \in \Sigma^\ell$ such that $C(x) \neq L(x)$, then there is no $\pi$ such that $V(C,\pi)=1$.

For all $n$, $C_n$ has $n$ inputs and $V(C_n,\pi_n)=1$.

Then $\mathsf{Cert}\text{-}\mathsf{P/poly}$ contains $\mathsf{NPSV}_t$-uniform $\mathsf{P/poly}$, so it is probably not just $\mathsf{P}$. And we have the desired statement:

Proposition: $\mathsf{NP} \subseteq \mathsf{Cert}\text{-}\mathsf{P/poly} \Longleftrightarrow \mathsf{coNP} \subseteq \mathsf{Cert}\text{-}\mathsf{P/poly} \Longrightarrow \mathsf{PH} = \mathsf{\Sigma_1 P} = \mathsf{\Pi_1 P}$.

Proof: First we show that $\mathsf{Cert}\text{-}\mathsf{P/poly} \subseteq \mathsf{NP}$, giving the final "$\Longrightarrow$" in the statement. Suppose $L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$ with verifier $V$ and $V$-verified circuit family $\{(C_n,\pi_n)\}_{n=1,2,3,...}$. The following is a nondeterministic poly-time algorithm for $L$: on input $x$ of length $n$, guess $C_n,\pi_n$, and run $V(C_n,\pi_n)$; if it accepts, then output $C_n(x)$.
Next, we show that Certified $\mathsf{P/poly}$ is closed under complement, giving the first "$\Longleftrightarrow$" in the statement. Suppose $L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$, with verifier $V$ as in the above definition. Since $L \in \mathsf{NP}$ by the preceding paragraph, there is some $c$ such that $L \in \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(2^{n^c})$. Let $V'(C',\pi)$ compute as follows: if $C'$ has a negation gate as its output gate, then write $C' = \neg C$, and define $V'(C',\pi) = V(C,\pi)$. Otherwise, $V'(C',\pi)$ checks whether $|\pi|=2^{\ell + \ell^c}$ (where $\ell$ is the number of inputs to $C'$); if not, then $V'$ rejects, and if so, then $V'$ simply enumerates all strings $y$ of length $\ell$, and checks whether $C'(y)=L(y)$, using the $2^{\ell^c}$ deterministic algorithm for $L$, which takes time $poly(|\pi|)$. (This latter yoga was needed to make sure that $V'$ satisfies property 1 in the definition.) If $\{(C_n,\pi_n)\}$ is a certified family of circuits for $L$ with verifier $V$, then $\{(\neg C_n, \pi_n)\}$ is a certified family of circuits for $L^c$ with verifier $V'$. QED


How can an inherited attribute be simulated using a synthesized attribute? Is it possible to simulate an inherited attribute using a synthesized attribute? For example, can the inherited attribute SYMTAB used in normal code generation modules be simulated using a synthesized attribute? If yes, what are the changes proposed to the existing attribute grammar? If not, why not?

How can inherited attributes be simulated with synthesized ones: an example.

The way of doing it is to postpone the evaluation of any attribute
that uses directly or indirectly an inherited attribute, by
abstracting it into a function that takes the inherited attribute as
argument. There may be several such arguments.

Here is a fragment of a simple example, on the grammar rule $T\rightarrow T\; v$
 for a term in an expression, which is to be type-checked.

Right hand side symbols are subscripted to identify occurrences, so we actually write $T\rightarrow T_1\; v_1$
We use the following attributes:

for $T$ the inherited attribute $symtab$ and the synthesized
attribute $type$;
for $v$, which is a terminal, the synthesized attribute $name$ which is actually produced by the lexer.

The semantic rule  for type checking is:  $type(T)\gets
 if\; type(T_1)=symtab[name(v_1).type]\; then\; type(T_1)\; else\; typefail$

meaning that the type of the subterm $T_1$ and the type associated with the symtab entry of the $name$ of the variable $v_1$
must be the same, and that the name of this common type or $typefail$ is the value for the
synthesized attribute $type$ for $T$.

You replace that semantic rule by the following one:
$type(T)\gets \lambda\; symtab.\;      if\; type(T_1)(symtab)=symtab[name(v_1).type]\;$ $\qquad\qquad\qquad\qquad\;\;\;\;\;\;then \;type(T_1)\; else\; typefail$

The synthesized attribute $type$ is now a function rather than a type
name.  When called, it takes a symtab as argument and checks whether
the expression $T$ is well typed with respect to this symtab, calling
recusively other such functional values of the attribute to actually
do the type checking for subexpressions.

You no longer need to know the symbtab where you do the type checking, so you do not need the inherited attribute $symtab$.
When higher up in the tree you get a synthesized attribute that is the
actual symtab, you simply apply the type attribute with that symtab as
argument to get the type checking done.  Well, it is a bit more
complicated with scope rules.

This can be completely formalized, but I do not have the right papers
handy, and I have no courage or time to redo the complete formal presentation. But I am sure there are books and papers on this

It is a kind of continuation passing style for processing the inherited attributes.

A proof that inherited attributes are not necessary

Hypotheses:

attributes can carry values of any type, though functional types
are not really a requirement (see the proof) despite the example
above.
any type of computation on the attributes is permitted.

We assume a CF grammar $G$ with an attribute system, such that
evaluation of attributes on a parse tree $T$ will produce a result
$E(T)$ for a distinguished attribute $\rho$ of the initial symbol
$S$ labeling the root: $\rho(root_T)=E(T)$. Our purpose is to exhibit an attribute system that produces the
same result using only synthesized attributes. Without loss of
generality, we assume that the initial symbol S of the grammar is
never used used in a right-hand side of a rule.

Intuition: we make a copy of the tree as a purely synthesized attribute of the root node.

In the formalization below $A_i$ denotes an occurence of a symbol in a rule, and
we note $\sigma A_i$ the actual symbol in that occurence.

We have a single synthesized attribute $\theta$ for all terminals and
non-terminals. For terminals, this attribute is initialized to a tree
degenerated to its root node labeled by the terminal. In addition,
there is the attribute $\rho$ for the initial symbol
$S$.

To each grammar rule  $\qquad \sigma A_0 \to \sigma A_1 \dots \sigma A_n$

we associate the following attribute calculation

$\theta(A_0) \leftarrow tree(\sigma A_0, [\theta(A_1), \dots \theta(A_1)])$

where $\theta(s,tt)$ is a function that takes two arguments, a
non-terminal $s$ and a list of trees $tt$, and returns a new tree with
a root labeled with $s$ and all the trees in $tt$ as daughters of the
root, in the same order.

It is easily shown by structural induction that attribute evaluation
of a tree $T$ will thus assign to the attribute $\theta(S)$ a value
that is precisely equal to $T$ (i.e., a copy of $T$ if that is more
intuitive). Since we know from the initial attribute system that there
is an effective procedure to compute the result $E(T)$, we only have
to add one extra attribute rule to be associated with the initial
symbol $S$:
$\rho(S)\leftarrow E(\theta(S))$

Thus, our new attribute system has only synthesized attributes and
computes exactly the same result as the initial system.

Some readers may find the proof a bit unsettling, but it is not a
circular (tautological) proof. We do not have to use the initial
attribute system to actually compute $E(\theta(S))$. The only thing
that matters is that it is computable.

Actually it is very close to the technique used in the example above,
using functional attributes, but it delays computation by passing
syntactic information bottom up, rather than doing it more
semantically by passing a continuation. One could use that functional attribute technique to do the proof, but I suspect it would be technically much more complex.

It shows that what matters to make sure than an evaluation policy can
be used is to check that this evaluation policy is able to duplicate
all the data, in this case the parse tree.

From that perspective, it is easily seen that using only inherited
attributes will not in general be adequate, because the tree cannot be
duplicated with only inherited attributes.

The reason is quite simple: when you are going top-down exclusively
you cannot pass information sideways in the tree. Take the rule
$  A \to B C$. If you are on the $B$ node of an instance of that
rule in the tree and want to compute the inherited attributes, all you see is $A$ above. There is no way you can relate to the $C$ side of the tree. And $A$ cannot look at it since information goes top down only, and $C$ is below $A$. The information on the current node depends only on the path from the root to that node, not on the whole tree.


smallest circuit size using XOR gates Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables.
The goal is to compute the minimum number of XOR operations you need to perform to compute all these y_1...y_m functions.

Note that the result of an XOR operation,
say x_1 XOR x_2 might be used in computation of multiple y_j's but is counted as one. Also, note that it might be useful to compute XOR of a much larger collection of x_i's (larger than any y_i function, e.g. computing XOR of all x_i's) in order to compute y_i's more efficiently,

Equivalently, suppose we have a binary matrix A, and a vector X and the goal is to compute vector Y such that A.X=Y where all operations done in GF(2) using minimum number of operations.

Even when each row of A has exactly k one's (say k=3) is interesting.
Does anybody know about the complexity (hardness of approximation) for this question?

Mohammad Salavatiopur

This is NP-hard. See:
Joan Boyar, Philip Matthews, René Peralta. Logic Minimization Techniques with Applications to Cryptology. http://link.springer.com/article/10.1007/s00145-012-9124-7

The reduction is from Vertex Cover and is very nice.

Given a graph $(\{1,\ldots,n\},E)$ with $m=|E|$, define an $m \times (n+1)$ matrix $A$ as: $A[i,j] = 1$ if $j < n+1$ and $(i,j) \in E$, and $A[i,n+1] = 1$. In other words, given $n+1$ variables $x_1,\ldots,x_{n+1}$ we want to compute the $m$ linear forms $x_i+x_j+x_{n+1}$ for all $(i,j) \in E$.

A little thought shows that there is an XOR circuit for $A$ with gates of fan-in two computing the linear transformation $A$ with only $m+k$ gates, where $k$ is the optimal vertex cover for the graph. (First compute $x_{i'} + x_{n+1}$ for all $i'$ in the vertex cover, using $k$ operations. The linear forms are then all computable in $m$ more operations.) It turns out that this is also a minimum size circuit!

The proof that the reduction is correct is not so nice. I would love to see a short proof that this reduction is correct.


Writing universal recursive function Is there a short explicit construction of an universal recursive function? All definitions I have seen involve numbering of Turing machines in some way, which is possible yet seems hard and unmanageable to write in a higher-level programming language (like Python, Haskell etc.)

Sure.  Write routines that compute each of Godel's primitive recursive functions, and write a routine for an unbounded search operator.  The set of functions you can compute this way is equivalent to the set of functions Turing machines can compute.  More information here.

The downside is that any input to your universal program would need to be framed in terms of those simple operations.  Of course, that is what compilers are for.


Remove edges from bipartite graph subject to degree restrictions I have a bipartite graph $G$ with two sets of vertices $X$ and $Y$, where the degree of each vertex in $X$ is exactly $M$.

I now must remove some of the edges to ensure that, after removal, no vertex in $Y$ will have a degree larger than $1$.  I want to choose a way to remove the edges so that as many vertices in $X$ have degree at least $N$ (where $N$ is given to me, $N \le M$).

How can I find the maximum number of vertices in $X$ whose degree will be at least $N$ after removal, subject to the restriction that after removal no vertex in $Y$ should have degree larger than $1$?

This problem is NP-hard as 3DM (3-dimensional matching problem) reduces to it. Just pick M=N=3, Y to be the points of the underlying base set, and X to be the triples on them.