Shortest path in DAG with path dependent arc costs I've got the following problem

Consider a DAG $G=(V,E)$ with $V=[v_1,…,v_n]$, and edge-set $E=[e_1,…,e_m]$, with associated costs $c_1,…,c_m$. The problem is to find the shortest paths from an initial vertex $s$ to multiple targets $t_1,…,t_k$, taking into account these costs. A typical shortest path problem.

However, my problem is slightly different:
the costs $c_1,…,c_m$ depend on the previously traversed nodes
Is there an alternative to the brute-force solution: find all the simple paths between $s$ and $t$ and then select the one with the lowest cost?

Path can be compared.
Take as example the following graph:
Red arcs are "checkpoint arcs". All the sub-paths having a red arc as last one can be compared, so a local decision can be taken. Similarly, costs are reset after traversing such arcs: 22->23 has a different cost if the subpath includes the arc 11->22 or not.

EDIT 2:

Costs are related to two sequences: $P$ and $Q$, where $len(P)=N$ and $len(Q)=M$. In the aforementioned case $M=N=4$.
Each element of $P$ and $Q$ is a tuple $(t,p)$. The tuple ($t_i,p_i)$ is the ith tuple of the sequence. Tuples are constrained on $t$: $t_{i+1} > t_i$. There's no constraint on $p$.

Let $s_p$ a set of valid indices for the sequence $P$ and $s_qp$ a set of valid indices for the sequence $Q$. The cost $C(s_p,s_q)= C_t(s_p,s_q)+C_q(s_p,s_q)$ where $C_t = max(max(P[s_p][t]),max(Q[s_q][t])) - min(min(P[s_p][t]),min(Q[s_q][t]))$ and $C_p = max(max(P[s_p][p]),max(Q[s_q][p])) - min(min(P[s_p][p]),min(Q[s_q][p]))$

The cost $C(s_p,s_q)$ represents the "diameter" of the element obtained by merging the $s_p$th elements of $P$ and the $s_q$th elements of $Q$.

Each path in the graph builds different $s_p$ and $s_q$ sets.
For example, the path 00,11,22,33 has a cost $C_{tot} = C(0,0)+ C(1,1)+ C(2,2)+ C(3,3)$, while the path 00 - 01 - 12 - 22 - 33 has a cost $C_{tot} = C(0,[0,1])+ C([1,2],2)+ C(3,3)$

Without further information on how the costs can vary, the problem is NP-complete. For instance, consider the following rule for setting costs:

If an edge would return to a previously-traversed node then its cost is $n$
If an edge reaches $t$ without previously traversing all other nodes then its cost is $n$
In all other cases the cost of an edge is $1$.

For such a rule, a Hamiltonian path has cost $n-1$ and all other paths have cost $n$ or greater. The problem could still be solved more efficiently than a brute-force search (e.g. in time $O(n^22^n)$ by dynamic programming) but not in polynomial time unless $\mathsf{P}=\mathsf{NP}$.

So if you want to find a polynomial time algorithm you will need to be much more specific about what sort of dependence between edge cost and previous path information is allowed.


Is this graph transformation unique up to isomorphism? [Answer:NO] Suppose, transformation T is defined as given in the diagrams below.
Every vertex (v) is replaced by deg(v)-gon. And then graph is reconnected as shown.

Those on the left are Gs and on the right are T(G)s.

It is easy to see that every vertex in  T(G) has degree 3.
This paper claims that graph isomorphism of such graphs can be tested in polynomial time. Also, G can be converted to T(G) in polynomial time.

Statement I: G1 and G2 are isomorphic iff T(G1) and T(G2) are isomorphic.
EDIT:
Specifications for G1,G2:

G1 = (V1,E1) and G2=(V2,E2)
|E1| = |E2| and |V1| = |V2|
Sort[{deg(v)|v in V1}] = Sort[{deg(u)| u in V2}]

If Statement I is True then do we have solution for GI problem?

Note: I am n00b in this field. I invent funny techniques daily.

Along with the already-given answers stating the existence of two graphs G1≠G2 for which T(G1)=T(G2), there is also a different problem: there exist pairs G1=G2 for which T(G1)≠T(G2). This is because the transformation depends not just on the isomorphism class of G, but also on the cyclic ordering of the edges around each vertex of G.

Edited to add an example based on Mark Reitblatt's comment:


Finding a dual of a graph According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles, and below $S_n$ refers to the sphere with exactly $n$ handles), one can define a dual multigraph by treating the faces of the original graph embedding as vertices and adding an edge between two vertices for every side the corresponding faces have in common in the original graph.

Here's my problem. Given a graph $G$, I need to find another graph $G'$ such that there exists a surface $S$ and a cellular embedding of $G$ on $S$ such that $G'$ is the dual of this embedding of $G$. I know that there are many possible graphs $G'$; I just need to find one for every graph $G$.

I have several questions. My current strategy is to (1) determine the genus $n$ of $G$, (2) find an embedding of $G$ on $S_n$, and (3) find the dual of this embedding. All those steps have known algorithms (although (1) is NP-Hard). I wonder if there's a way to find a $G'$ that bypasses the computation of the genus, since that is the bottleneck of this approach, and that's my first question. My second question is: If I know that $G$ is regular, can that ease the computation of the genus? And my third question is a request for any references that can help me solve this problem.

Does your dual have to be of minimum genus? Because it's trivial to find a cellular embedding for any graph: just choose a circular ordering for the edges incident to each vertex, arbitrarily, and then determine the faces of the embedding as the sequences of edges consistent with the chosen orderings.

I like the GEM (graph-encoded map) representation of an embedding from the book Foundations of Topological Graph Theory by Bennington and Little. In this representation, an embedding is represented by a 3-edge-colored 3-regular graph with one vertex for every flag of the embedding (an incident triple of vertex, edge, and face) and one edge for every two flags that differ in only one of the elements of the vertex/edge/face sets that they represent. For instance, the image below from Wikipedia can be interpreted as a GEM of a regular dodecahedron, in which the red cycles represent its faces, the yellow cycles represent its edges, and the blue cycles represent its vertices; the edges may be colored according to the colors of their two incident faces.

Given a circular ordering of the edges of a graph G, its GEM can be found by making a cycle of 2d vertices for each degree-d vertex of G, two for each edge, with the pairs of vertex for each incident edge occurring in the cycle in the chosen circular order, and then for each edge e of G linking the two pairs of GEM edges for the two endpoints of e into a rectangle. If you want an oriented embedding the choice of how to link these four vertices into a rectangle should be consistent with the circular orderings, otherwise it can be arbitrary.

Then, the vertices, edges, and faces of the embedding of G are represented by cycles in the GEM that alternate between two of the three edge colors. The dual of G is represented by a GEM with the same underlying 3-regular graph but with two of its edge colors swapped. And the graph represented by a GEM can be formed by contracting all of its vertex cycles and merging pairs of parallel edges into single edges. So constructing a dual of G (as long as you don't care which dual) can easily be done in linear time.


Applications of HHL's algorithm for solving linear equations In HHL's algorithm for solving a system of linear equations (HHL = Harrow, Hassidim and Lloyd) the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a problems which would classically use the solutions of the linear equations?

If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical solution $x$ to a system $Ax=b$" then the answer is no. As you mention, the final quantum state  in Harrow, Hassidim, Lloyd's algorithm does not immediately give you the classical solution $x$ of the system but a quantum states that encodes $x$ in its amplitudes; it is hard to extract the "explicit information" $x$ from that state.

However there are indeed interesting applications of the HHL linear systems algorithm as a subroutine to solve other problems, using the output of the quantum algorithm in "more quantum" ways.

The HHL algorithm can be readily applied to compute expectation values
$\langle x| M | x \rangle$ of a poly-size Hermitian operator $M$.
Dominic Berry gave a generalized version of hte HHL algorithm to solve linear systems of the differential equations. The HHL algorithm is used as a subroutine there. (Berry's algorithm uses HHL's as a subroutine.) The final solution of Berry's algorithm is also encoded in the amplitudes of a quantum state.
Wiebe, Braun, Lloyd  gave an algorithm based on HHL's that can be used to find the optimal least-square fit to some discrete data. Although the output of that algorithm is again encoded in some quantum amplitudes, the authors also gave a quantum algorithm to asses the quality of an optimal least-square fit in a quantum computer, and there the output is classical. For certain types of fit functions, their quantum algorithm outperforms classical ones.
Recently, HHL's algorithm has been employed in Lloyd-Mohseni-Rebentrost's quantum algorithm for machine learning.

Note that, in all of these algorithms,   quantum manipulations of the output state of the HHL's algorithm are performed, instead of classical ones. This is similar to the case of the quantum Fourier transform (QFT), which can be computed exponentially faster in a quantum computer as a quantum gate than the classical discrete Fourier transform. We cannot use this fact in quantum algorithms to Fourier-transform classical functions faster. However, the QFT has remarkable applications in Shor's factoring algorithm and quantum phase estimation.


Shallow versus Deep Embeddings When encoding a logic into a proof assistant such as Coq or Isabelle, a choice needs to be made between using a shallow and a deep embedding. In a shallow embedding logical formulas are written directly in the logic of the theorem prover, whereas in a deep embedding logical formulas are represented as a datatype.

What are the advantages and
limitations of the various
approaches?
Are there any guidelines available for determining which to use?
Is it possible to switch between the two representations in any systematic fashion?

As motivation, I would like to encode various security related logics into Coq and am wondering what the pros and cons of the different approaches are.

What are the advantages and limitations of the various approaches?

Pros of deep embeddings : You can prove and define things by induction on formulas' structure. Examples of interests are the size of a formula.
Cons of deep embeddings: You have do deal explicitly with binding of variables. That's usually very laborious.

  Are there any guidelines available for determining which to use ?

Shallow embeddings are very useful to import result proved in the object logic. For instance, if you have prove something in a small logic (e.g. separation logic) shallow
embeddings can be a tool of choice to import your result in Coq.

On the other side, deep embedding are almost mandatory when you want to prove
meta-theorems about the object logic (like cut-elimination for instance).

  Is it possible to switch between the two representations in any systematic fashion?

The idea behind the shallow embedding is really to work directly in a model of the object formulas. Usually people will maps an object formula P directly (using notations or by doing the translation by hand) to an inhabitant of Prop. Of course, there are inhabitants of Prop which cannot be obtained by embedding a formula of the object logic. Therefore you lose some kind of completeness.

So it is possible to send every result obtained in a deep embedding setting through an interpretation function.

Here is a little coq example:

Inductive formula : Set :=
    Ftrue : formula
  | Ffalse : formula
  | Fand : formula -> formula -> formula
  | For : formula -> formula -> formula.

Fixpoint interpret (F : formula) : Prop := match F with
    Ftrue => True
  | Ffalse => False
  | Fand a b => (interpret a) /\ (interpret b)
  | For a b => (interpret a) \/ (interpret b)
 end.

Inductive derivable : formula -> Prop :=
    deep_axiom : derivable Ftrue
  | deep_and : forall a b, derivable a -> derivable b -> derivable (Fand a b)
  | deep_or1 : forall a b, derivable a -> derivable (For a b)
  | deep_or2 : forall a b, derivable b -> derivable (For a b).

Inductive sderivable : Prop -> Prop :=
    shallow_axiom : sderivable True
  | shallow_and : forall a b, sderivable a -> sderivable b -> sderivable (a /\ b)
  | shallow_or1 : forall a b, sderivable a -> sderivable (a \/ b)
  | shallow_or2 : forall a b, sderivable b -> sderivable (a \/ b).

(* You can prove the following lemma: *)
Lemma shallow_deep :
   forall F, derivable F -> sderivable (interpret F).

(* You can NOT prove the following lemma :*)
Lemma t :
   forall P, sderivable P -> exists F, interpret F = P.


Does faster exact algorithm for counting independent sets in comparability graphs than general graph exisits? Sorry for not-precise question. :-(

There are several papers concerning exact counting (maximum) independent sets in general graphs. Actually, they concerns counting of solutions of 2SAT. The best of them is $O(1.23^n)$. But the algorithms do not use the specific information of comparability graphs.

So I wonder whether there exists more powerful(faster) exact algorithm for counting independent sets in comparability graphs?

Bipartite graphs are comparability graphs, and it's known (since Provan and Ball) that counting the number of independent sets in bipartite graphs is #P-complete.

J. S. Provan and M. O. Ball. The complexity of Counting Cuts and of Computing the Probability that a Graph is Connected.  SIAM J. Comput. 12 (1983) 777-788.

If I haven't mistaken, this should answer your question.


Dynamic programming algorithm for NP-complete problem Hello everybody here is a problem i have approximated but would like to hear your opinion about. Perhaps someone finds a better solution than me :)

Given a Graph G with undirected edges:

Divide it into the minimal number of sets, so that :

No two nodes in a set are connected to each other
Every node is member of at least one set
for any two distinct nodes x and y, there is a set which contains exactly one of x and y. All nodes appear in a different combination of sets. That means node x and y do not appear only in the same sets together. if you expressed the appearence of the nodes as a bit pattern, the bit pattern would differ at least in one digit.

Put another way, we want to find a 0-1 matrix with $|V|$ rows and a minimum number of columns, such that (1) each column denotes an independent set in the graph $G$, (2) every row has at least one $1$ in it, and (3) every pair of rows differs in at least one bit. Note it is trivial to give an $|V| \times |V|$ matrix of this kind for every $G$: just take the identity matrix. The problem becomes interesting when the number of columns can be made much smaller.

Example: B has no adjacent nodes, D=>A, A=>D

solution:

A B /
/ B D

A : 1 = 10
B : 2 = 11
D : 3 = 01

not a solution:

A D B
/ D B

A : 1 = 10
D : 2 = 11  _ same combination of
B : 3 = 11  / sets

D and B appear in the same combination of sets. D appears in the second and third set, as well as B.

what i need is something of a dynamic programming equation or another kind of solution that gives me an exact solution to this problem. I know that it is NP-hard, so an exponential solution is fine with me. ( i did a reduction onto Clique and Max-Sat)

An optimal solution would give me the composition of the sets, so that the number of sets is minimal, yet all nodes are part of the solution.

thanks for your help.

[Edited ro reflect the intended meaning of the 3rd condition]

I believe you you describe the graph vertex coloration problem with a variation . We allow a vertex to have multiple colours :

No adjacent nodes should be colored with the same color.
Every node should have at least one color.
For every pair of nodes (x,y) with x /neq y , one of these nodes must be colored with a color that the other is not colored with.

I want to present two situations, due to the nature of condition 3.

a) If only 1 and 2 apply. The minimum number of sets will be found if we color each node with only one color. Every other color applied to a node not only does not help solve the problem, but it adds additional constraints. Therefore this problem can be reduced to the single-colored vertex coloring problem.

b) 1,2 and 3 apply. For starters, let's 1-colour the graph. That give us a number of sets, let it be S1. For node belonging to different colours, the 3rd condition holds. However, for nodes belonging to the same colour, it doesn't. For every set, the problem of separating the same-set nodes reduces to colouring a full node graph, which we know needs N colours. However, we need not use new colours. We can re-use the already-used colours that of course obey the condition 1.

Therefore, we can create a graph this way: Create a full graph containing all the nodes in the same set. Then, extend it with the nodes that are adjacent to the set colours. Maintain the existing colour for the added nodes (not belonging to the full graph). Also, add a node with the color of the set that is adjacent to every other node in the full graph, so that the original colour cannot be used. Then, try to colour the new graph. Repeat for every set (S1 repeats).

A sketch of the algorithm follows

Multi-colour(graph G) :

Color the graph with 1 color per node. Let S0 be the number of colors used.
For every color ( i from 1 to S0 ) :

a. Create a full graph containing the nodes with THIS color.

b. Add to the graph the nodes adjacent to the nodes colored with THIS color. The adjacent nodes are colored with their colored from step 1.

c. Add a node adjacent to the nodes from step a. Color it with THIS color.

d. Color the graph. Prefer colors that were used in step 1. if none is eligible, use a NEW color.

e. Add every NEW color to the list of "used" colors. Let Si be the number of new colors used. (Si can be zero or positive ). S0 = S0 + Si .
S0 is the number of minimum sets.

Complexity: The number of sets created by step 1 is O(n), where n is the number of vertices. Therefore this problem belongs in the same complexity as the graph coloring problem.

My algorithm is a top-down approach, therefore it is not dynamic programming. I do not know if dynamic programming could be applied to this problem. Does the Principle of Optimality hold for this problem?


Is there a simple argument that shows that  the unique games conjecture implies the PCP theorem how can one show that what is relation between "Unique games conjecture" and "PCP theorem"?
how does one explain "Unique games conjecture" is stronger form of "PCP theorem"?

It depends a bit how you define the PCP Theorem, is it with perfect completeness or not. As we state in our book, an equivalent form of the PCP Theorem is that there is some constraint satisfaction problem for which it's NP-hard to distinguish between the perfect satisfiable case and the case that one can satisfy at most some fraction $s<1$ of the cosntraints. But, we could have state a variant with imperfect completeness, replacing the perfect satisfiable case with being able to satisfy some fraction $c>s$.

The unique games conjecture is an assumption of this latter form (where, making the condition stronger $c$ is close to $1$ and $s$ is close to $0$) and, most importantly, the constraints are of a very special form (permutation constraints on two variables). In that sense it's (essentially) stronger form of the PCP Theorem.

You can ask if there's an easy transformation to convert a PCP with imperfect completeness to one with perfect completeness. I think it probably can be done easier than proving the PCP Theorem, but I'm not aware at the moment of a very simple argument.


Singular Value in Machine Learning I'm reading the paper (http://proceedings.mlr.press/v9/glorot10a/glorot10a.pdf) from Glorot and Bengio. There is something that I don't understand at the abstract section on page 1.

"Training may be more difficult when the singular values of the Jacobian associated with each layer are far from 1"

Why is the singular value of the Jacobian important for training?

Why is the singular value being far from 1 difficult for training?

If the singular values of each layer are smaller than 1, then you can have vanishing gradients.  If the singular values are larger than 1, you can have exploding gradients.  Both cause problems for training.

Why?  As a heuristic, imagine that all the singular values for each layer were 2, and you have $n$ layers.  Then the singular values for the entire network would be $2^n$.  So, if the singular values of the layers are larger than 1, the singular values for the entire network can grow exponentially in the number of layers.  Similarly if they're less than 1, they can vanish exponentially fast.


Reductions from the book. This is along the lines of "Algorithms from the Book". Although reductions are algorithms as well, I thought it doubtful that one would think of a reduction in response to the question about algorithms from the book. Hence a separate query!

Reductions of all kinds are most welcome.

I'll start off with the really simple reduction from vertex cover to multicut on stars. The reduction almost suggests itself once the source problem is identified (before which I would find it hard to believe that the problem would be hard on stars). This reduction involves constructing a star with $n$ leaves, and associating a pair of terminals with every edge in the graph, and it is "easy to see" that it works. I will update this with a link to a reference, once I find one.

Those who are missing the context of the book may want to look at the question about Algorithms from the book.

Update: I realize that I was not entirely clear as to what qualifies as a reduction from the book. I find this issue a little bit tricky, so I confess to half-deliberately dodging the issue by slipping in a reference to the other thread :)

So let me describe what I had in mind, and I suppose it goes without saying - YMMV in this regard. I intend a direct analogy to the original intent of Proofs from the Book. I have seen reductions that are awfully clever, and leave me gaping at how that sequence of thoughts might have occurred to anyone. While such reductions leave me with a definite sense of awe, those are not the examples that I am looking to collect in this context.

What I am looking for are reductions that are described without too much difficulty, and are perhaps mildly surprising, for the reason that they are easy to grasp but aren't easy to come up with. If you estimate that the reduction in question will require a lecture to cover, then likely it doesn't fit the bill, although I am sure there might be exceptions where the high-level idea is elegant and the devil's in the details (for the record, I'm not sure I can think of any).

The example I gave was deliberately simple, and hopefully somewhat - if not perfectly - illustrative of these characteristics. The first time I heard about multi-cut was in a classroom, and our instructor began by saying that not only is it NP-hard in general, it is NP-hard even when restricted to trees... {dramatic pause} of height one. I recall not being able to prove it immediately, although it seems obvious in retrospect.

I suppose obvious in retrospect closely describes what I am looking for. I am not sure if this has anything to do with the complexity of the description - perhaps there are situations where something apparently murky might classify as elegant - feel free to bring up your examples (exceptions?), but I would really appreciate a justification. Given that after some point this is a matter of taste, you should certainly feel free to find what I see as insanely complex, perfectly beautiful. I am looking forward to seeing a variety of examples!

Rabin shows the one-wayness of (x^2 mod N=pq) without the factorization of N by a reduction showing that if you can take square roots module N=pq then you can factor N.


Lower bounds for 3SUM with a free cache Consider the 3SUM problem: given a set $S$ of $n$ numbers identify $x$,$y$,$z$, s.t $x + y = z$. It is believed that the simple $O(n^2)$ algorithm is the best possible; reductions from 3SUM have been used to prove lower bounds for other problems assuming 3SUM is hard [Patrascu 2010].

Is it possible to prove that a small amount $n^\delta$ ($\delta < 1$) of free cache does not help for 3SUM? (An algorithm can store information in the cache and access it for free while accesses to regular RAM cost 1.)

Well, sure, it's possible.  But since we basically don't know how to prove that anything is hard, it doesn't look easy.

In the mid 90s I proved an $\Omega(n^2)$ lower bound for 3SUM in a variant of the linear decision tree model; my proof was later simplified by Ailon and Chazelle.  This model of computation has nothing corresponding to "memory"; the running time of an algorithm is defined simply as the worst-case number of (generalized) comparisons.  So adding a cache won't break these lower bounds; to beat $O(n^2)$ time, you have to do some non-obvious computation with the data in the cache.


KRW Conjecture: separation of NC^1 and P More than a real question this is a recap of something I have been studying. I hope someone will help me getting things straight, so any correction or thought about the following reasoning is more than welcome. I am trying to get a grip on the KRW Conjecture, which is aimed at proving $NC^1 \neq P$.
What I figured out is that the main goal of the whole question is:

Find a boolean function $f$ such that $D(f) = \omega(\log(n))$, where $D(f)$ is the depth complexity of $f$ – the depth of the shallowest circuit computing $f$.

This would imply  $NC^1 \neq P$ since it would prove the existence of a function $f$ which can be computed with a circuit of polynomial size but cannot be computed with a circuit of polylogarithmic depth:

$\exists\ f:\{0,1\}^n \rightarrow \{0,1\}\ |\quad f \in P/\mathrm{poly}$ and $f \notin NC^1$.

So we need tools to prove super-logarithmic lower bounds for boolean functions.
To do so we can relate Circuit Complexity to Communication Complexity via the KW relations. Indeed it has been proved that every boolean function yields a KW relation defined as follows:

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a boolean non-constant function.
Alice receives $x \in f^{-1}(0)$.
Bob receives $y \in f^{-1}(1)$.
Their aim is to find $i$ such that $x_i \neq y_i$.

The reason why we want (and why it is possible) to relate circuits to KW relations is that it was proved what follows:

$D(f) = CC(KW_f)$, where $CC(KW_f)$ is the amount of bits communicated over a protocol solving $KW_f$.

Being communication problems, it is possible to prove lower bounds for KW relations using the Communication Complexity framework.
The aim of Communication Complexity is to study the amount of communication, in terms of bits transmitted, required to solve a communication problem using a communication protocol, which is basically an algorithm stating the rules of the conversation.
For what it has been said until now we can establish a deep connection between circuits and protocols: Communication Complexity supplies a different point of view on the $NC^1 \neq P$ problem.
The first and most basic tool that comes from Communication Complexity are combinatorial rectangles:

A set $R \subseteq X \times Y$ is a (combinatorial) rectangle if $R = A \times B$ for $A \subseteq X$ and $B \subseteq Y$.
Furthermore, given a function $f: X \times Y\rightarrow Z$ and a rectangle $R \subseteq X \times Y$, $R$ is monochromatic in relation to $f$ if $f$ is constant over $R$.

Using rectangles it is possible to partition the space of input of any given function. Given a function $f$, the (base 2) logarithm of the amount of rectangles needed to cover the input space of $f$ gives a lower bound on the communication complexity of any protocol computing such $f$.
Here comes my first real question: given a function $f:X \times Y \rightarrow Z$, does proving that it is not possible to cover $X \times Y$ using at most n rectangles imply that $CC(f) = \omega(\log(n))$?
Now let’s talk about a practical example. The Equality Function is defined as follows:
$$EQ(X,Y) =\begin{cases}
1&\text{if $X = Y$,}\\
0&\text{otherwise.}
\end{cases}$$
Since it can be proved using rectangles that $CC(EQ) = n + 1$, wouldn’t that mean that $D(EQ) = \omega(\log(n))$?
There’s something slipping my grasp, thanks in advance to everyone who will spend some of their time to reply.

There are a few points to consider here:

If we wish to show that $CC(f) = \omega(\log n)$, we should show that it is not possible to cover the domain of $f$ using $\mathrm{poly}(n)$ monochromatic rectangles (rather than $n$ rectangles). Showing it for $n$ rectangles would only establish that $CC(f) > \log n$.

If we wish to prove a lower bound on $D(EQ)$, then we should prove a lower bound on $CC(\mathit{KW}_{EQ})$ rather than on $CC(EQ)$. Therefore, the lower bound on $CC(EQ)$ does not imply a lower bound on $D(EQ)$.

In particular, in order to use the Karchmer-Wigderson approach to prove lower bounds on depth complexity, we need to prove lower bounds on the communication complexity of relations rather than functions. This is considerably trickier. For example, in the context of relations, one needs to change the definition of a monochromatic rectangle. Now, it no longer makes sense to require that "the function is constant over $f$" since a relation may allow multiple valid solutions for every input, so it is not clear what being "constant" means. Instead, one should use the following more complicated definition: a rectangle $R \subseteq X \times Y$is said to be monochromatic with respect to a relation $S \subseteq X \times Y \times Z$ if there exists an output $z\in Z$ that is a valid solution for every input in $R$ (i.e., $(x,y,z) \in S$ for every $(x,y) \in R$).

Alas, it is not possible to use rectangle covers to prove meaningful lower bounds on KW relations. The reason is that every KW relations can be covered by $2n$ rectangles. Those rectangles are constructed as follows: for every index $i \in [n]$ and bit $b \in \{0,1\}$ we have the rectangle $$R_{i,b} = \{ x\in f^{-1}(0) \mid x_i = b \} \times \{ y\in f^{-1}(1) \mid y_i = \neg b \}. $$ It is not hard to see that those rectangles are indeed monochromatic rectangles for any KW relation $\mathit{KW}_f$, and that they cover the whole domain of the KW relation.


Lower bounds on the Threshold function In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric boolean (partial and total) functions in terms of a quantity denoted $\Gamma$:

  Theorem (Paturi): Let $f$ be any non-constant symmetric function, and denote $f_k=f(x)$ when $|x|=k$ (i.e. the hamming weight of $x$ is $k$). The approximate degree of $f$, denoted $\widetilde{deg}(f)$, is $\Theta(\sqrt{n(n-\Gamma(f))})$, where $\Gamma(f)=\min\{|2k-n+1|:f_k\neq f_{k+1}\text{ and } 0\leq k\leq n-1\}$

Now let $Thr_t(x)$ be the threshold function, i.e. $Thr_t(x)=1$ if $x\geq t$. In this paper (cf. section 8, page 15) says that $\widetilde{deg}(f)=\sqrt{(t+1)(N-t+1)}$.

Observe that for the threshold function we have $\Gamma(Thr_t)=|2(t-1)-n+1|$, because when $|x|=t-1$ the function changes from 0 to 1. Am I right?

If I apply directly Paturi's theorem to this value of $\Gamma$, I don't get the lower bound on the threshold function reported in other papers. Is the value of $\Gamma(Thr_t)$ above correct? What am I missing?

Edit: I also tried computing the quantum adversary lower bound for threshold. First, let's review the theorem.

  Theorem (Unweighted Quantum Adversary): Let $f$ be a partial boolean function, and let $A\subseteq f^{-1}(0)$ and $B\subseteq f^{-1}(1)$ be subset of (hard) inputs. Let $R\subseteq A\times B$ be a relation, and set $R_i=\{(x,y)\in R : x_i\neq y_i\}$ for each $1\leq i \leq n$. Let $m,m'$ denote the minimal number of 1s in any row and any column in relation $R$ respectively, and let $\ell,\ell'$ denote the maximal number of ones in any row and column in any of the relations $R_i$ respectively. Then $Q_2(f)=\Omega(\sqrt{\frac{m m'}{\ell \ell'}})$.

If I define $B$ as the set of all inputs with the number of 1s greater than or equal to $t$, and $A$ all the inputs with 1s strictly less than $t$, I get (after some algebra) that $\frac{mm'}{\ell\ell'}=n^2 \ln(\frac{n}{t}) \ln(\frac{n}{n-t})$.

So still I'm not getting the same lower bounds reported in other papers. Now, let's compare these bounds. The figure below shows for $n=200$ and without the square roots, a comparison between Paturi's theorem bound (blue), adversary bound (red), and the reported bound from other papers (green).

My questions are:

1- How do I get the bound reported in other papers?

2- You can see from the figure, that the reported lower bound (green) also lower bounds Paturi's bound and the adversary bound. Isn't that weakening the "real" lower bound? For example, if Paturi says that for all symmetric functions we have this bound, then how can you get a matching upper bound for quantum counting ($\sqrt{(t+1)(n-t+1)}$)? Isn't that upper bound violating Paturi's theorem?

I don't know how you can get or see the bound of $\sqrt{(t+1)(n-t+1)}$ from the original bound $\sqrt{n(n-\vert (2(t-1) -n+1 \vert )}$ but here is the proof that this bounds are asymptotically equal up to a constant factor:

First see that (I exclude $t = 0$ because the threshold function is always $1$)
$$ n(n-\vert (2(t-1) -n+1 \vert) = \left\lbrace
\begin{array}{ll}
n(2t-1) & 1 \leq t \leq n/2+1/2\\
n(2n-2t+1) & n/2+1/2 \leq t \leq n-1
\end{array} \right. $$

Define $f_1(t) = n(2t-1)$, $f_2(t) = n(2n-2t+1)$ and $g(t) = (t+1)(n-t+1)$.

Now you have to calculate the maximal value (according to $t$ within the defined intervalls) of the fractions $f_1(t)/g(t)$, $f_2(t)/g(t)$, $g(t)/f_1(t)$ and $g(t)/f_2(t)$. You can do this with differential calculus or approximation with the help of the graph (with $n$ large enough):

$f_1(t)/g(t) \leq f_1(n/2+1/2)/g(n/2+1/2) \leq \dfrac{n^2}{n^2/4} = 4$

$f_2(t)/g(t) \leq f_2(n/2+1/2)/g(n/2+1/2) \leq \dfrac{n^2}{n^2/4} = 4$

$g(t)/f_1(t) \leq g(1)/f_1(1) = \dfrac{2n}{n} = 2$

$g(t)/f_2(t) \leq g(n-1)/f_2(n-1) = \dfrac{n/2}{n/3} \leq 3/2$

This gives you
$$n(n-\vert 2(t-1)-n-1\vert) = \Theta((t+1)(n-t+1))$$
and also the wanted result
$$\sqrt{n(n-\vert 2(t-1)-n-1 \vert)} = \Theta(\sqrt{(t+1)(n-t+1)}).$$

Is there an easier way to see/get this result?


Determining if a word of specific length exists that is not accepted by a NFA It is known that the problem of determining if an NFA accepts every word is PSPACE-COMPLETE, meaning it is also NP-Hard, but is this weaker version of the problem still NP-hard?

Given an NFA and a natural number $n$, determine if there exists a word of length $n$ that is rejected by the NFA.

At first I thought that it is possible to prove this is NP-Hard by reducing the problem of checking if every word is accepted by an NFA to it, by checking every word length until hitting an upper bound. but according to Yuval Filmus in this question, the upper bound is exponential in the number of states of the NFA, so this reduction does not work.

Is there a valid reduction from a NP-Hard problem, or is this problem solvable in polynomial time?

Your problem is NP-hard, by reduction from 3SAT.

Let $\varphi$ be a 3SAT formula with $m$ clauses and on the $n$ variables $x_1,\dots,x_n$.  Construct a NFA over the alphabet $\Sigma=\{0,1\}$ as follows.  The $n$-bit input to the NFA is treated as an assignment to $x_1,\dots,x_n$.  The NFA first nondeterministically selects one of the $m$ clauses.  Then, it checks whether the input satisfies that clause, and if so, rejects; otherwise accepts.  Note that if the input $x$ satisfies $\varphi$, then the NFA rejects; otherwise, the NFA accepts.

Now there exists an input to the NFA of length $n$ that causes the NFA to reject, if and only if there is a satisfying assignment for $\varphi$.  That means that your problem is at least as hard as 3SAT.


compressing rarely used space So an idea I've had bouncing around for a while goes like this: suppose we have some TM that runs in possibly exponential time, and thus can use possibly exponential space.  But let's say that it doesn't use its available space very often: say, it's oblivious and makes a constant number of passes back and forth across the input.

It seems to me that such a machine can have its space usage improved, but I'm not sure of any relevant results.  Can we simulate such a machine in some smaller space bound (ideally polynomial or close to it...), if we allow the simulator to use that smaller amount of space however it wants?  Anyone know of such a result?

I think it can be compressed to linear space.

I assume the machine $M$ has one tape. Initially the first $n$ cells contain the input, which is followed by $2^O(n)$ zeroes. $M$ is oblivious and always makes $k$ passes through the tape (from left end to right and back), and then accepts or rejects. Let $p_i$ denote the state the machine enters after reading the $n$-th cell on $i$-th pass during the left-right phase, and let $q_i$ denote the state the machine enters after reading the $n+1$-th cell on $i$-th pass during the right-left phase. Note that $q_1$ is a function of $p_1$ alone, and generally $q_i$ depends only on the sequence $p_1, p_2, \dots, p_i$ (this sequence has length at most $k$, which is fixed). Therefore we can always compute the state $q_i$ without actually continuing the pass through the extra scratch space - the transitions can be hardcoded into the description of the machine.


Hardness of noisy Boolean functions Let $f$ be a Boolean function  of $n$ Boolean variables. Let $g(x)=T_\epsilon (f) (x)$ be the expected value of $f(y)$ when $y$ is obtained from $x$ by flipping each coordinate with probability $\epsilon/2$.

I am interested in cases where it is computationally hard to approximate $g$. Let me fixed a notion of "approximation" (but there may be others): A Boolean function $h$ approximates $g$ if $h(x)=1$ when $g(x)\ge 0.9$ and $h(x)=0 $ when $g(x)\le 0.1$.A counting argument (based on the existence of positive rate error correcting codes) seem to give that there are Boolean functions for which any such approximation requires an exponential size circuit. But the question is what happens when $f$ to start with is in NP or in its neighborhood.

Q1: Is there an example of $f$ described by NP circuit (or P-space) so that every $h$ is NP hard, or hard in some weaker sense.

To see that $h$ might not always be easy (I thank Johan Hastad for useful discussion about it) we can consider the property of graphs of having a clique of size $n^{1/4}$, for random input, it is conceivable that it is hard to detect if there is a large clique but this is manifested by having more than expected cliques of size log n in the noisy graph. In this case any $h$ will be likely-hard (but not provably, and not terribly hard as quasi-polynomial circuits will be telling).

Q2: What is the situation if $f$ to start with is low complexity. ($AC^0$, monotone $TC^0$, $ACC$ etc.)

Q3: What is the situation for some basic examples of Boolean functions. (The question can be extended also to real-valued function.)

Q4: Can the above question be asked formally for the uniform (Turing-machine) model of computation?

Update: In view of Andy's answer (Hi there, Andy) I think that the most interesting question is to understand the situation for various specific functions.

Update Another question Q5 [Q1 for monotone functions] (also in view of Andy's answer). What is the situation if $f$ is monotone? Can we still encode robustly an NP complete questions>

for Question 1, the answer is Yes, and can be shown as follows.  (I will also be implicitly sketching an affirmative answer to Q4, since the argument is uniform and will treat all input lengths at once.)

Fix any NP-complete language $L$, and a family of good binary error-correcting codes (with rate 1/4 and correcting from a .1 fraction of errors, say).  Let $Enc_n: \{0, 1\}^n \rightarrow \{0, 1\}^{4n}$ be the encoding function for length $n$; we use some such code where $Enc = \{Enc_n\}$ is computable by a uniform polynomial-time algorithm.

Define $L'$ as the set of strings $z$ that are within distance at most $.05 |z|$ from a codeword $y \in Enc(L)$ encoding some element of $L$.  Note that $L'$ is in NP, as you can guess and check the nearby codeword, the decoded word, and the NP certificate for the decoded word's membership in $L$.

Then the claim is that any "approximation" of $L'$ in your sense is NP-hard for $\varepsilon = .01$.  For if we consider a valid codeword $y = Enc(x)$ of some length $4n$, then with probability $1 - o(1)$ over a random $\varepsilon$-perturbed version $y'$ of $y$, it will disagree with $y$ in at most a .05 fraction of coordinates, and will therefore disagree with any other codeword of $Enc_n$ in a more than $.05$ fraction of coords.  For such $y'$ we have $y' \in L'$ iff $x \in L$.  So if $h$ is any approximation to the $\varepsilon$-smoothed version of $L'$ in your sense, then we must have $h(y) = L(x)$.  As $Enc$ is efficiently computable, this gives us a way to efficiently reduce membership questions for $L$ to ones for $h$.  So $h$ is NP-hard.

Two notes:

(1) error-correcting encodings of NP instances have been used before in several papers, notably
D. Sivakumar: On Membership Comparable Sets. J. Comput. Syst. Sci. 59(2): 270-280 (1999).

(2) the argument above of course says nothing about the average-case complexity of any NP problem, since error-correction is being applied on an instance-by-instance basis.


Complexity of a satisfiability problem I would like the know the complexity of a specific satisfiability problem. I have a feeling it could be solved in polynomial time, but I am not sure about it. The problem is described below.
Given $n$ boolean variables $v_1, v_2, \dots, v_n$ and two types of clauses.

At most $n$ clauses of the form $v_a \to \neg v_i \land \neg v_j \land \dots$ where $v_a$ cannot be on both sides of the implication.
At most $n$ clauses of the form $v_a \lor v_b \lor \dots$ where any combination of variables is possible (but no negations!).

The goal is to satisfy all the clauses. I have a feeling this can be done using limited backtracking just like with 2SAT as described on Wikipedia https://en.wikipedia.org/wiki/2-satisfiability#Limited_backtracking.

This is NP-hard.
Here is a reduction from SAT.  Suppose you have a CNF formula $\varphi$ with variables $x_1,\dots,x_n$.  Add variables $x'_1,\dots,x'_n$ and clauses of the form $x_i \to \neg x'_i$ and $x_i \lor x'_i$.  For each clause in $\varphi$, we add a corresponding $\cdots \lor \cdots$ clause: e.g., if $x_i \lor \neg x_j \lor x_k$ is a clause in $\varphi$, then we add the clause $x_i \lor x'_j \lor x_k$.  Once you've added all these clauses, add up the total number of clauses; say you have at most $m$ of the first type of clause and at most $m$ of the second type of clause.  Now add unused variables $x_{n+1},\dots,x_m$.  The result is an instance of your problem with $m$ variables and at most $m$ clauses of each type.  Now $\varphi$ is satisfiable iff this instance is satisfiable.


$\mathsf{UPH}$, $\Pi_2^{\mathsf{P}}$ and $\mathsf{PP}$ In literature, the biggest class I have seen proven to be in $PP$ is $NP$ (and $coNP$ of course as $PP$ is closed under complementation).

However, if we use the following results :

$PP^{RP} = PP$  (in fact $PP^{BQP} = PP$)
There exists a RP-reduction from $SAT$ to $USAT$

Where $USAT$ is the promise class of boolean formulae such that

if $F \in USAT$ then $F$ has a unique solution.
if $F \not \in USAT$ then $F$ is not satisfiable.

It seems quite straightforward to prove that $\Pi_2^P \subseteq PP$ (hence $\Sigma_2^P \subseteq PP$).

  Construction:
  Let $\mathcal{M}\ $ be the following $PP^{RP}$  Turing Machine :

  Input: $\forall x_1, \dots, x_m, \exists y_1, \dots y_n, F$
  Computation:

  Choose uniformely $x_1, \dots, x_m$.
  We obtain then an existential formula.
  Use the Valiant-Vazirani theorem to obtain an USAT formula $\exists! z_1, \cdots z_o G$.
  We choose uniformly $z_1, \dots, z_o$, and if $G$ is satisfied, accept, otherwise, reject with probability $\frac{1}{2}$.

  Modify the previous TM by adding $2^n-1$ rejecting paths. (I know I'm going a bit fast, but we can manage that by adjusting rejecting probabilities after having tested G)

  Validity:

  if $\forall \dots \exists \dots F$ is true, then $\mathcal{M}\ $ has $2^n$ accepting paths + $2^{n-1}$ rejecting paths + an equal number of accepting and rejecting paths, and then $\mathcal{M}\ $ accepts.
  if $\forall \dots \exists \dots F$ is false, then $\mathcal{M}\ $ has less than $2^n$ accepting paths + $2^n-1$ rejecting maths + more rejecting paths than accepting paths. then $\mathcal{M}\ $ rejects.

Moreover, if we extend Valiant-Vazirani theorem to $RP$-reduce $PH$ to $UPH$ (alternation of forall and unique existentials), then by modifying a bit previous construction we would prove that $PH \subseteq PP$.

  Is the previous construction correct ?

  Is there any known litterature around $UPH$ ? (It may not be called $UPH$)

Your proof must be wrong. All your techniques (including VV) relativize and Beigel has an oracle where $P^{NP}$ is not contained in $PP$. I'm guessing you aren't using VV properly.

Also UPH=PH because you can make an existential unique by requiring the lexicographical least witness (using an extra universal quantifier to eliminate the others).


3-coloring planar graphs in $O\left(3^{n^.5}\right)$? I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from planar separator results, yet in wikipedia, it only mentions independent sets, Steiner trees, Hamiltonian cycles, and TSP. Below I include some reasoning which I think almost does achieve this bound.

With a zero reduced decision diagram, (ZDD), I believe you can get $O\left(c^{O(log_2(n)\sqrt{n})}\right)$, and I was curious how I could do better. What I came up with is rather rudimentary. Note: throughout, the ZDD I describe is ternary, but I don’t think that greatly matters. For the ZDD, given an ordering, $L = \{v_1 \dots v_n\}$, of vertices to color, the number of nodes at step $i$ will be exponential in respect to the size the frontier, $F_i = \{v_k | k < i \land v_k~v_j, j \geq i \}$.

To create your ordering $L$, you may create an optimal branch-decomposition tree, $b$, in polynomial time, which has width at most $\sqrt{n}$. Then, select a random leaf $v’$ of $b$ to be your root. With a BFS, weight each edge $e$ by the number of leaves not connected to $v’$ if you were to remove $e$ from $b$. Then, do a DFS to finally create $L$, always going down the edge furtherest from $v’$, choosing the one with least weight if there is a tie, and choosing arbitrarily if there is still a tie. When we reach a leaf, $(u,v)$ add $u$/$v$ to $L$ if either is not in $L$. Let $c_i$ be the component induced in $b$ by the vertices visited when we added $v_i$ to $L$. Then, $F_i$ is bounded by the branch width times the number of edges $x_i$ needs to be removed from $b$ to get the component $c_i$. $x$ is bounded roughly by $log_2$ of the vertices in $b$, which is linear to $n$ since we’re dealing with planar graphs.

With that, you check all three colors for each node for each of the $n$ frontiers and you’re done.

I recommend reading Sections 7 and 14 in the excellent book  by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh.

In short, Gu and Tamaki give a quadratic time algorithm which finds a branch-decomposition of a planar graph of width at most $3\sqrt{n}$. Then Robertson and Seymour in (5.1) give a tree-decomposition of width less than $\frac{9\sqrt{n}}{2}$. Then the classical dynamic programming algorithm (see, e.g., Marx) solves $3$-Coloring in time $3^{\frac{9\sqrt{n}}{2}}\textrm{poly}(n)<141^{\sqrt{n}}$.

On the other hand, it is known (Lichtenstein) that under the Exponential Time Hypothesis (ETH), the Planar $3$-SAT problem is $2^{\Omega(\sqrt{n})}$-hard. And a reduction from Planar $3$-SAT to Planar $3$-Coloring implies that under ETH there is no algorithm solving Planar $3$-Coloring in time $2^{o(\sqrt{n})}$.


Is there an algorithm to generate proof in Coq? I try to imagine using Coq to implement large and complicated software with specifications and proof. However, the manual work of writing proof is daunting. As a Coq newbie,  to specify an insertion sort algorithm costs me a week and nearly one thousand lines accounting for specifications and proof.

Is there possibly to relieve the developer's burden and make computer prove arbitrary theorem, which is much stronger than 'auto' tactic? If not, what is the unsolved question in it?

I guess the resource you are looking for is Adam Chlipala's Certified Programming with Dependent Types in which he builds up powerful tactics.


Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$ Let $G=(V,E)$ be a graph.
Let $m(G)=|E|$ and $n(G)=|V|$.
There are two different density definitions for $G$:
$$d_1(G)=\frac{m(G)}{n(G)}$$
and
$$d_2(G)=\frac{m(G)}{n(G)-1}.$$
Let $H^* \subseteq G$ be a subgraph of $G$ such that
$$d_1 (H^*)\geq d_1 (H)$$
for any subgraph $H\subseteq G$.
My question is:
Is it true that for any subgraph $H\subseteq G$ we still have
$$d_2 (H^*)\geq d_2 (H)?$$
Any comment is welcome!
Update 1:
J.G showed that the statement is NOT TRUE by providing a counterexample.

Consider two disjoint triangles connected by a single edge. Without checking too formally, $^*$ is the full graph with value $7/6$ under the first definition, but either of the triangles has value $3/2$ under the second definition while the full graph only has value $7/5$.

Update 2:
I found that a maximum density subgraph (with the definition $d_1(G)=\frac{m(G)}{n(G)}$) can be found efficiently by using algorithms provided in references:

A. V. Goldberg. Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, University of California at Berkeley, 1984.
G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A Fast Parametric Maximum Flow Algorithm and Applications. SIAM Journal on Computing, 18(1):30–55, 1989.

However, I didn't find any reference for computing a maximum density subgraph (with the definition $d_2 (G)=\frac{m(G)}{n(G)-1}$).
As pointed by J.G, a maximum $d_1$-density subgraph may not be a maximum $d_2$-density subgraph.
My new question is:
Is there any efficient algorithm for computing a maximum density subgraph (with the definition $d_2 (G)=\frac{m(G)}{n(G)-1}$)?

Here is a very slow algorithm, but it handles more general cases, like when density is defined as $d_\beta(G) = \frac{m(G)}{n(G)-\beta}$.
Let $f$ be a submodular function, $g$ be a modular function strictly larger than $0$. The min ratio problem $\min_S f(S)/g(S)$ can be solved in polynomial time. Indeed, use the standard to convert min ratio problem to parametric search problem with linear terms.
Consider we have input graph $G=(V,E)$.
For $d_\beta$ density, fix a set $T$ of size $k = \lfloor \beta \rfloor + 1$, and define $f_T:2^{V-T} \to \mathbb{R}$ as $f_T(S) = -m(G[T\cup S])$, and define $g_T:2^{V-T} \to \mathbb{R}_{>0}$ as $g_T(S) = |S|+|T|$. You can check $f$ is submodular through a counting argument.
Consider the optimum $T$ and $S$ for $$\min_{T:|T|=k, T\subset V} \min_{S:S\subset V\setminus T} f_T(S)/g_T(S).$$ Let $T$ and $S$ be the optimum of the problem. The densest subgraph is $G[T\cup S]$.
Running time is $O(n^k)$ calls to the min ratio oracle. Maybe faster algorithm exists, be nice to avoid that $k$ in the exponent.


Complexity of summing up integral powers Let $x$ be a rational number, and $S_n(x)= \sum_{1\leq i\leq n} i^x$. What is the complexity of computing $S_n(x)$ correct to $d$ decimal places? Is this a Hard problem?

It is clear from Faulhaber's formula that the problem takes $O(x)$ steps to solve for natural $x$. But I'm not very clear about rational $x$.

Check out The generalization of Faulhaber's formula to sums of non-integral powers. Specifically, on the last page, it gives a formula indicating an error bound of $O(N^{\sigma - m})$, where $\sigma$ is $x$ (in this paper, it's generalized to complex numbers), and $m = \lfloor \sigma + 1 \rfloor$. $N$ in this case refers to the depth of a summation you have to calculate. So this implies that for rational numbers slightly greater than an integer, it would be a lot faster than for rational numbers slightly less than an integer. Of course, this is a result on real numbers, and there may be a better result for rationals.


Consequences of OWFs for Complexity It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question is: What are the complexity-theoretic consequences of the existence of one-way functions? For example, OWFs imply that $\mathsf{NP}\ne\mathsf{P}$, $\mathsf{BPP}=\mathsf{P}$, and $\mathsf{CZK}=\mathsf{IP}$. Are there other known consequences? In particular, do OWFs imply that the polynomial hierarchy is infinite?

I'm hoping to better understand the relationship between worst-case and average-case hardness. I'm also interested in results going the other way (i.e. complexity-theoretic results that would imply OWFs).

This is a late response.

First, to correct what you wrote:
Cryptographic pseudorandomness (the one obtained from OWFs) doesn't have enough stretch to derandomize "naturally defined" computational complexity classes. In an old paper (beginning of 80s) Andrew Yao shows some subexponential time derandomization for RP etc using these objects (btw, this is immediate), but no stronger derandomization is known. Note, that in terms of fooling power cryptographic PRGs are stronger than what you need for derandomization but at the same time in terms of their stretch are weaker than their typical complexity-theoretic analogues (this follows by the order of quantification in the definition of the PRGs).

As Sasho Nikolov mentioned there are plenty of examples in PAC learning. Have a look at a very early paper by Kearns and Valiant on the impossibility of learning formulas and automata (follow in google scholar the references from there). Also, there are consequences in proof complexity through interpolation -- have a look in the also early works by Jan Krajicek and Pavel Pudlak. However, I am not sure if you consider these to be complexity-theoretic implications (but I do).

-- Periklis


Complexity class of efficient streaming algorithms Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words:

$L \in \mathsf{StreamL}$ if there exists a Turing machine $M$ which decides $L$, where:

There are two tapes, the read-only input tape and the working tape

$M$ moves only to the left on the input tape, and uses at most $O(\log n)$ space on the working tape.

Has this class been studied?

My assumption is that the answer is yes, but I'm not yet aware of a definition of the class in the literature.
Most literature on streaming algorithms that I am aware of considers the complexity of solving specific algorithmic problems, and does not tackle structural complexity i.e. defining classes such as the above and determining their relationships.
There is also a large body of work on communication complexity classes. In this domain there is a relevant class called $\mathsf{P}^{cc}$ (see Babai, Frankl, and Simon 1986: Complexity classes in communication
complexity theory), which contains functions of two variables $f(x,y)$ where they can be solved using a small amount of communication between $x$ and $y$. This is related to $\mathsf{StreamL}$ above (for functions of two variables, $\mathsf{StreamL}$ is contained in $\mathsf{P}^{cc}$), but the class above is not limited to functions of two variables and enforces a stricter computational requirement.
The obvious inclusions are $\mathsf{REG} \subseteq \mathsf{StreamL} \subseteq \mathsf{L}$, and no apparent inclusion either way between $\mathsf{StreamL}$ and $\mathsf{NC}^1$.

Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it.

Search for "one-way logspace" and you will find plenty of references. (Typically, past work treats it as a reducibility concept.) The papers that those papers reference should cover what you need.


A Question on Convex Conjugate Duality for KL Divergence The convex conjugate of a function, say, $f:X\mapsto \mathbb{R}$ is a function $f^*:X^*\mapsto \mathbb{R}$ defined as
$$f^*(x^*):=\sup_{x\in X} ~\langle  x, x^*\rangle-f(x),$$ where $X^*$ is the topological dual of $X$ and $\langle\cdot, \cdot\rangle$ is dual pairing between $X$ and $X^*$.

The relative entropy (aka Kullback-Leibler divergence) $D(\cdot||Q):\mathcal{P}(X)\mapsto \mathbb{R}^+$, is defined for two probability measures $P$ and $Q$ (P<< Q)  as
$$D(P||Q)=\int_XdP \log\frac{dP}{dQ}.$$

I have been trying to calculate the convex conjugate of map $P\mapsto D(P||Q)$ but I have failed. I know that the answer is $\log \mathbb{E}_{Q}[e^{f}]$ where $\mathbb{E}_Q[\cdot]$ is the expectation operator with respect to probability measure $Q$.

To make it easier let's assume $X$ is finite, of size $n$ and associate the density of $Q$  with an $n$-dimensional vector $q$. Assume also that $q$ is everywhere positive - otherwise replace $X$ with the support of $q$. Then the conjugate is
$$
f^*_q(x) = \sup_p\  \langle x, p \rangle - \sum_{i = 1}^n{p_i\log(p_i/q_i)}.
$$
where the supremum is over the probability simplex $\{p\geq 0: \sum_i p_i = 1\}$. Since the simplex is compact and the function inside the supremum is continuous, the supremum is achieved at some $p$. Using Lagrange multipliers you get that for some real value $\lambda$ an optimal $p$ must satisfy $x_i - 1 - \log(p_i/q_i) = - \lambda$ for all $i$, which gives $p_i = q_ie^{x_i + \lambda-1  }$. Since $1 = \sum_i p_i$, we have $\lambda - 1 = -\log\left(\sum_i{q_i e^{x_i}}\right)$. Substituting, we get
$$
\begin{align}
f^*_q(x) &= \sum_i{q_i e^{x_i + \lambda- 1 }x_i} - \sum_i{q_i e^{x_i+ \lambda-1 }(x_i+ \lambda-1)}  \\
&= -(\lambda-1)\sum_i{q_ie^{x_i+ \lambda-1 }}  \\
&= -(\lambda-1)\sum_i{p_i}\\
&= -(\lambda-1) = \log\left(\sum_i{q_i e^{x_i}}\right),
\end{align}
$$
which is exactly the logarithm of the expectation of $e^{x_i}$ under $q$.


understanding programming monads through diagrams I am trying to understand better how the category definition of monad is related to the computer science definition.  nlab has a rather terse definition of Monad in terms of a bicategory.

an object $a$
an endomorphism $t: a \to a$
$2$-cells $\mu, \eta$ (multiplication and unit).

For the case of programming languages, what are the objects (0-cells), morphisms (1-cells) and 2-morphisms (2-cells)? I am guessing the object is a type and multiplication is the >>= operator (some way of putting commands in succession).  I won' t know what the endomorphism $t$ could be.

I was told that list is a monad, so is maybe and IO but I don't see the category or endomorphisms there.

Alternatively they have another definition that kind of makes sense:

  Indeed, one can define a monad on an object a of a bicategory K as just a monoid in the endomorphism category K(a,a).

Are the endomorphism the lines of code preserving the type a?

nLab goes on to say, that monads can be represented as string diagrams.  Here are

The axioms for a monad - could be represented in terms of the >>= operator in a language like Haskell - are represented in terms of string diagrams.

Then, can a computer program be represented in terms of these diagrams?

This is a sequel to a previous question:  https://cs.stackexchange.com/questions/30757/how-is-io-a-monad and can be migrated at the discretion of the admins.

I think the nLab definition is too abstract and is confusing you more than anything. Perhaps you should start from Wikipedia?  Anyway, here are some comments.

  For the case of programming languages, what are the objects (0-cells), morphisms (1-cells) and 2-morphisms (2-cells)?

In the case of programming languages (and in most usual cases) the bicategory in question is $\mathbf{Cat}$, the 2-category whose 0-cells are categories, 1-cells functors and 2-cells natural transformations.

Spelling out the nLab definition, the object is a category, the endomorphism is an endofunctor and multiplication and unit are natural transformations.

A typed functional programming language usually induces a category as follows: the objects of the category are types; a morphism $A\rightarrow B$ is an expression (i.e., a program) of type B containing a parameter of typa A, modulo evaluation.  I am not overly familiar with Haskell but I believe that people call the induced category $\mathbf{Hask}$, so a Haskell monad is nothing but an endofunctor (with suitable natural transformations) of $\mathbf{Hask}$.  If I am not mistaken, in that context the unit is called "return", whereas multiplication is called "bind", i.e., the >>= operator (the category-theorist's definition of multiplication $\mu$ may be easily recovered from >>=, and vice versa).

  Are the endomorphism the lines of code preserving the type a?

No.  As I said above, the endomorphisms are endofunctors. For Haskell, the object a is not a type but the category $\mathbf{Hask}$.

  Then, can a computer program be represented in terms of these diagrams?

The answer is actually yes, but not through the connection you are describing. In fact, the string diagrams you mentioned live in the 2-category $\mathbf{Cat}$, whereas programs live in the category induced by the programming language.  A little more on this topic may be found in the answers to this cstheory.SE question.


What's the complexity of Median-SAT? Let $\varphi$ be a CNF formula with $n$ variables and $m$ clauses. Let $t \in \{ 0,1 \}^n$  represent a variable assignment and $f_{\varphi}(t) \in \{ 0, \ldots , m \}$ count the number of clauses satisfied by a variable assignment to $\varphi$. Then define Median-SAT as the problem of computing the median value of $f_{\varphi}(t)$ over all $t \in \{ 0,1 \}^n$.  For example, if $\varphi$ is a tautology then the solution to Median-SAT will be $m$ since regardless of assignment every clause will be satisfied. However in the case of $\overline{SAT}$ the solution to Median-SAT could be anywhere between $0$ and $m-1$.

This question arose when I was pondering two natural extensions of SAT, MAX-SAT and #SAT, and what the difficulty of the resulting problem would be if they were put together. For MAX-SAT we have to find a particular variable assignment to maximize the number of variables satisfied by $\varphi$. For #SAT we have to count how many assignments satisfy all $m$ clauses of $\varphi$. This variant winds up mainly as an extension of #SAT (and in fact of #WSAT), but retains some of the flavor of MAX-SAT in that we count the number of satisfied clauses rather than just deciding whether they're all satisfied or not.

This problem seems harder than #SAT or #WSAT. For each variable assignment #SAT decides the Boolean problem of whether that assignment satisfies $\varphi$ or not whereas Median-SAT determines "to what extent" $\varphi$ is satisfied in terms of the number of clauses that an assignment satisfies.

I realize that this problem is somewhat arbitrary; computing the average or mode number of clauses satisfied by each variable assignment seems to capture the same quality. Probably many other problems do too.

Has this problem been studied, perhaps under a different guise? How hard is it compared to #SAT? It's not clear to me a priori that Median-SAT is even contained in FPSPACE, although it does seem to be contained in FEXPTIME.

Given an instance of SAT, an integer $k$, and a variable assignment, we can decide in polynomial time whether exactly $k$ clauses are satisfied, simply by counting the number of clauses that are satisfied and testing whether that number equals $k$. Hence we can calculate the total number of variable assigments satisfying exactly $k$ clauses using a #P oracle.

So like Max-SAT, Median-SAT can be computed in polynomial time using a $\#P$ oracle. This shows that the problem is in $FP^{\#P} \subseteq FPSPACE$.


Average Regret Bounds for Linear Stochastic Bandits I am reading this paper on linear stochastic bandits :

http://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf

All the results are stated in a high-probability setting, that is $\delta$ is a parameter to the algorithm , the regret at time $T$ is such that ,

\begin{align*}
\mathbb{P}(R_T > f(T) ) \geq 1 - \delta
\end{align*}

Is there any resource where the bounds are obtained in the form $\mathbb{E}[R_T] \leq f(T) $ ?

Trivially replacing $\delta = \frac{1}{T}$, does not give an anytime algorithm, that is the bounds don't hold for all $t > 0$.

Using the "doubling trick," you can turn your favorite high probability algorithm (e.g. LinUCB) to be an anytime algorithm with expected regret as a function of $T$, usually giving a $\tilde{O}(\sqrt{T})$ dependence without knowing $T$ in advance.

This turns out to be tight, i.e. in Chu et al. (2011), we give lower bounds on expected regret of $\Theta(\sqrt{dT})$ for the $d$-dimensional linear stochastic bandit problem.  Hence, the expected regret, in the worst case, will indeed still be a function of $T$.


Theoretically, can everyday computing tasks be broken down into ones solvable by a neural network? MIT Review recently published this article about a chip from IBM, which is more or less a Artificial neural network. Why IBM’s New Brainlike Chip May Be “Historic” | MIT Technology Review

The article suggests that the chip might have borrowed a page from the future. It might be the beginning of an era of new and evolved computation power. And also talks about programming for the chip.

  One downside is that IBM’s chip requires an entirely new approach to
  programming. Although the company announced a suite of tools geared
  toward writing code for its forthcoming chip last year (see “IBM
  Scientists Show Blueprints for Brainlike Computing”), even the best
  programmers find learning to work with the chip bruising, says Modha:
  “It’s almost always a frustrating experience.” His team is working to
  create a library of ready-made blocks of code to make the process
  easier.

Which brings me to the question, can everyday computing tasks be broken down into ones solvable by a neural network (theoretically and/or practically)?

Neural networks can arbitrarily approximate any computable function; see
http://en.wikipedia.org/wiki/Artificial_neural_network
or
http://en.wikipedia.org/wiki/Cybenko_theorem

Constructing a NN for a given function -- or worse yet, learning it from examples -- is a hard problem.


What is the relationship between intuitionistic logic, combinatory logic and lambda calculus? I've been reading Lectures on the Curry-Howard Isomorphism and it talks about intuitionistic/constructive logic (IL) , combinatory logic (CL) and lambda calculus ($\lambda$c) before moving on to the Curry-Howard correspondence.

In fact, almost every text I've come across when trying to understand the "history and theory of functional programming", I've almost found these 3 topics interlinked. However, I'm unable to grasp how exactly are they connected?

From what I understand, IL predates CL which predates $\lambda$c.I believe $\lambda$c incorporates the principles of IL and CL in some form but I can't seem to put a finger on it. It seems this some form has something to do with Curry-Howard Isomorphism (CHI), but I'm unable to find a "non-abstract" example that relates everything together. Most texts have proofs with letters A, B, C and the like and it takes a while to figure out exactly what's going on.

So, how are they related? If its CHI, then what's a good example to hit the point home, intuitively speaking? Perhaps a constructive example for the proof of CHI could be helpful.

I don't understand exactly what you are looking for, I'll try to explain the Curry-Howard correspondence in a nutshell, you'll let me know if it helps.

The Curry-Howard correspondence (or isomorphism, if you wish) definitely links the three objects you mention: it actually tells that two of them, IL and $\lambda$c, are the same thing.  The term is used today in a broad sense and often without referring to a specific technical statement, but it can be formulated precisely in at least two frameworks:

Hilbert-style deduction for intuitionistic logic and SK combinators;
Gentzen's natural deduction and the $\lambda$-calculus.

The first is actually the "original" correspondence, dating back to the late 50s when Curry observed that the types you would give to the SK combinators
$$
\begin{align*}
S &:(A\rightarrow B\rightarrow C)\rightarrow(A\rightarrow B)\rightarrow A\rightarrow C \\
K &:A\rightarrow B\rightarrow A
\end{align*}
$$
are exactly the axioms of implicational propositional intuitionistic logic in Hilbert-style deduction.  Note that this latter has only modus ponens as a rule for building proofs; accordingly, terms in combinatory logic are built using only application.

That's it for the combinatory logic side.  It took another decade before Howard fully formulated the correspondence in the second guise, which I think looks best:

on the logical side, you have $\mathbf{NJ}^{\Rightarrow,\land}$, Gentzen's natural deduction system for the negative fragment of propositional intuitionistic logic. You have propositional formulas defined by $A,B::=\alpha\mathrel{|} A\Rightarrow B\mathrel{|} A\land B$ (atom, implication and conjunction), proofs built from introduction and elimination rules for each connective, and you have proof normalization, which consists in 2 rewriting rules replacing what Prawitz calls "detours" (an introduction of a connective immediately followed by its elimination) with more explicit pieces of proof. This rewriting procedure closely corresponds to cut-elimination in sequent calculus, also introduced by Gentzen.
On the computational side, you have the simply-typed $\lambda$-calculus $\Lambda^{\rightarrow,\times}$, with types defined by $T,U::=o\mathrel{|}T\rightarrow U\mathrel{|} T\times U$ (base, function space and pairs), terms built from constructors ($\lambda$ for $\rightarrow$ and pairing for $\times$) and destructors (application for $\rightarrow$ and projections for $\times$), and $\beta$-reduction, which consists of 2 rewriting rules: the usual one and one for handling projections acting on a pair.

The Curry-Howard correspondence, which is the subject of the book you are reading, has three levels:

formulas = types: just change the notation swapping $\alpha/o$, $\Rightarrow/\rightarrow$ and $\land/\times$;
proofs = terms: more precisely, introduction rule=constructor, elimination rule=destructor;
normalization = reduction: this is harder to write inline, but it's obvious once you write the rewriting rules of the two systems side by side. The correspondence is one-to-one, i.e., one step in $\mathbf{NJ}^{\Rightarrow,\land}$ corresponds to exactly one step in $\Lambda^{\rightarrow,\times}$ and vice versa.

At this level, I hesitate to call this an "isomorphism" because it is not entirely clear what structures are being preserved.  Here's where category theory may be of help: if you formulate $\mathbf{NJ}^{\Rightarrow,\land}$ and $\Lambda^{\rightarrow,\times}$ as categories (without being too precise: formulas/types as objects and normal proofs/normal terms as morphisms), then they are isomorphic as Cartesian-closed categories (CCC). Indeed, as I defined them, they both are the free CCC on one object ($\alpha$ if you are a logician or $o$ if you are a computer scientist).  So, there you go, you now have a third object into the picture and you get what Robert Harper calls the Holy Trinity (logic, programming languages and categories).

Actually, the above categorical view hides a bit what I think is the most important aspect of the Curry-Howard correspondence, which is normalization = reduction.  Somewhat annoyingly, this is left out in current alternative terminologies for the correspondence: people say "proofs as programs" or "formulae as types", nobody says "cut-elimination as computation".  To properly accommodate the third level, you'd have to climb a bit up on the higher-dimensional ladder and make $\mathbf{NJ}^{\Rightarrow,\land}$ and $\Lambda^{\rightarrow,\times}$ into 2-categories, or even more (things make sense up to dimension 3 at least).

If you're looking for concrete examples, the above framework isn't very rich but already gives you an idea.  Take the second-order definition of natural number: $$\mathsf{Nat}(x):=\forall\alpha.(\forall y.\alpha(y)\Rightarrow\alpha(\mathsf{s}y))\Rightarrow\alpha(0)\Rightarrow\alpha(x)$$
($x$ is an integer if it satisfies every property $\alpha$ which is true for $0$ and is true for $y+1$ as soon as it is true for $y$). Now, erase all first-order information and second-order quantification.  You get
$$(\alpha\Rightarrow\alpha)\Rightarrow\alpha\Rightarrow\alpha$$
Translated in types, this is
$$\mathsf{N}:=(o\rightarrow o)\rightarrow o\rightarrow o.$$
Guess who are the normal forms of type $\mathsf N$?  Exactly the (typed version of the) Church numerals.  So every term $\mathsf{N}\rightarrow\mathsf{N}$ is a function on integers.  If you keep the first and second order information, you get much more.  For instance, the proof in second-order Peano arithmetic that addition is total, i.e., that
$$\vdash\forall x.\forall y.\mathsf{Nat}(x)\land\mathsf{Nat}(y)\Rightarrow\mathsf{Nat}(x+y)$$
gives you a $\lambda$-term of type $\mathsf{N}\times\mathsf{N}\rightarrow\mathsf{N}$. Guess what functions it computes? Well, addition, of course (see Krivine's book "Lambda-calculus: Types and Models"). Cool, isn't it?

Another classical source to learn about Curry-Howard is Girard, Lafont and Taylor's book "Proofs and Types" (but you may already know that, it's in the bibliography of the book you are reading).


Explicit type system with infinite non-cumulative universe hierarchy Is there an open-source proof assistant or at least an explicit set of rules written down somewhere for a type system with an infinite non-cumulative universe hierarchy and unique typing?
I want to see the rules for the universe lifting function spelled out.

Ali Asaf worked out a hierachy of universes with explicit coercions (lifting) in A calculus of constructions with explicit subtyping and established a relationship with cummulative universes.


Combinatorial algorithm for optimization over semimetric polytope This question is motivated by the Leighton-Rao relaxation for SPARSEST-CUT.

Suppose one wants to find a non-trivial semimetric over an $n$-point space that minimizes a certain linear functional. More formally:

minimize $\sum_{ij = 1}^n c_{ij} d_{ij}$
where $d$ is a semimetric over $\{1, 2, \ldots, n\}$
and $\sum_{ij = 1}^n d_{ij} = 1$

Of course it is a linear program that can be solved in polynomial time using ellipsoid method. But what I would like to know is if there are any combinatorial algorithms for this optimization problem. I suspect that the answer is 'no' since the problem looks pretty general to be solved combinatorially, but who knows...

Yes: the dual is a multicommodity flow problem which can be solved using the Garg-Koenemann algorithm http://dx.doi.org/10.1137/S0097539704446232.


Are there Petri net models with "checking" rather than "taking" transitions? Is there a studied model of Petri nets where each transition only has one normal in-edge (which removes a marker from a place), but can also have "checking" edges, which only check whether there is a marker in a place?

Alternatively, each transition has at least one out-edge to each of its input places, except for one.

Such a net would model a random-permitting context grammar, but a Google Scholar search for "random permitting context" and "petri net" doesn't yield any likely candidates.

EDIT: it seems my question is not very clear, but I'm unsure exactly of how to improve it.

I'm looking for a restricted class of Petri nets: these nets can indeed be simulated by ordinary Petri nets, so I'm definitely not looking for a generalisation of Petri nets.

Unless I'm more-than-usually confused, there are Petri nets which cannot be simulated by these nets.

Perhaps my motivation and what I mean by my definition can be clarified by a further restriction: we keep the restriction of each transition having only one normal in-edge, but further disallow checking edges.
In this case, we get a model (the Parikh vectors of) the context-free languages: each transition represents a production and places represent symbols, with a production deleting one symbol and adding any number of others.

Marek and Češka have shown that Petri nets can simulate any random-context language; the random-permitting context languages are a strictly smaller class (even when we ignore the order of symbols). For example $\{a^{2^n} : n \in \mathbb{N}\}$ is a random-context language but is not random-permitting context language (these languages satisfy a pumping lemma).

The Petri nets here correspond to these languages: the production $A \rightarrow XYZ$ with permitting set $\{C,D\}$ corresponds to a transition with an in-edge from $A$, out-edges to $X$, $Y$ and $Z$, and checking edges from $C$ and $D$.

What you are looking for with "checking edges" are known as Petri nets with read arcs.  In your question you also mention nets with a single read edge, those are called communication-free.  It would be difficult (for me) to point to the original author(s) for these notions, but they are fairly standard.  Relationships between communication-free Petri nets and Parikh images of context-free languages are investigated for instance by Javier Esparza, Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes, FCT 1995, LNCS 965, pp. 221--232, and Fundamenta Informatica 31(1):13--25, 1997.


How large a treewidth can a tree plus half the edges have? Let G be a tree on 2n vertices. The treewidth of G, tw(G) = 1. Now suppose we add n edges to G to get a graph H. An easy upper bound on tw(H) is n + 1. Is this essentially the best possible?

It seems somehow that tw(H) should be O(sqrt(n)) , but this is just a vague hunch. Do we know better upper bounds than O(n) for the treewidth of a graph obtained by adding n edges to a tree on 2n vertices?

Your model is not really any less general than asking about arbitrary 3-regular graphs, and 3-regular expander graphs have linear treewidth. So I don't know about constant factors, but Θ(n) is best possible, yes.


Positivstellensatz and sum of squares method This question comes from many online resources that introduce Sum-of-Squares method, such as the survey of Barak and Steurer (http://arxiv.org/abs/1404.5236). Let me focus on Theorem 2.1 of this survey and the paragraph just before that.

Starting point is "Positivstellensatz" which says that any non-negative polynomial over reals can be written as a sum of squares of rational functions. Corollary of this is the following statement, which is central to sum of squares proofs:

Given multivariate polynomials $P_1,P_2\ldots P_m$ over reals, the system of equations $\{P_1=0,P_2=0\ldots P_m=0\}$ has no solution over reals if and only if there exist polynomials $Q_1,Q_2\ldots Q_m$ and a sum of squares of polynomials $S$ such that $-1=S+\sum_i P_iQ_i$.

My question is how does this Corollary follow from "Positivstellensatz". This important implication constantly appears in various lecture notes/videos, but as far as I have noticed, the proof is always skipped.

As already noted in the comments, the question is based on a misunderstanding; the actual Positivstellensatz is a stronger statement than Artin’s theorem on nonnegative polynomials, and the real Nullstellensatz as stated in the question is indeed its special case.

Other comments asked for lecture notes with a proof of the Positivstellensatz, and as I do not know of any, I can as well write it myself.

The overall strategy of the proof below is similar to the model-theoretic proof of Hilbert’s Nullstellensatz; I will use the facts that each ordered field embeds in a real-closed field, and the theory of real-closed fields has quantifier elimination.

First, some notation. Let $F$ be an ordered field, and $f_1,\dots,f_n\in F[x_1,\dots,x_m]$ polynomials.

$I(f_1,\dots,f_n)$ denotes the ideal generated by $f_1,\dots,f_n$, i.e., polynomials of the form $f_1g_1+\dots+f_ng_n$ for some $g_1,\dots,g_n\in F[x_1,\dots,x_m]$.
$\Sigma$ denotes the set of polynomials of the form $\sum_{i=1}^na_ig_i^2$, where $n\ge0$, $g_i\in F[x_1,\dots,x_m]$, and $a_i\in F^+$. (If every positive element is a sum of squares, such as for $F=\mathbb R$, then $\Sigma$ just consists of sums of squares of polynomials.)
$C(f_1,\dots,f_n)$ is the set of polynomials of the form

$$\sum_{I\subseteq[n]}s_I\prod_{i\in I}f_i,$$

where $s_I\in\Sigma$. That is, $C(f_1,\dots,f_n)$ is the least set of polynomials that contains the $f_i$’s, squares, and positive constants, and is closed under $+$ and $\cdot$.

  Theorem (Positivstellensatz): Let $F$ be an ordered field, $R\supseteq F$ a real-closed field, and $f_1,\dots,f_r,g_1,\dots,g_s,h_1,\dots,h_t\in
F[x_1,\dots,x_m]$. The following are equivalent.

  The system $\{f_i(\vec x)\ge0,g_j(\vec x)=0,h_k(\vec x)\ne0:i\in[r],j\in[s],k\in[t]\}$ has no solution $\vec a\in R^m$.
  $-(h_1\cdots h_t)^{2n}\in C(f_1,\dots,f_r)+I(g_1,\dots,g_s)$ for some $n\in\omega$.

We could also accommodate strict inequalities $p_i(\vec x)>0$ by including $p_i$ among both the $f_i$’s and the $h_i$’s.

We will need

  Lemma: Let $S$ be a commutative ring, $u\in S$, and $P\subseteq S$ be such that

  $P$ is closed under $+$, $\cdot$, and contains all squares;
  $S=P-P$;
  $-u^{2n}\notin P$ for all $n\in\omega$.

  Then there is a homomorphism $\phi\colon S\to K$ to an ordered field $K$ such that $\phi(p)\ge0$ for all $p\in P$, and $\phi(u)\ne0$.

Proof of the Positivstellensatz:

$2\to1$: If $f_i(\vec a)\ge 0$ for $i=1,\dots,r$, then also $f(\vec a)\ge0$ for all $f\in C(f_1,\dots,f_r)$. Likewise, $g(\vec a)=0$ for all $g\in I(g_1,\dots,g_s)$. Thus, if $h=h_1\cdots h_t$ satisfies $-h^{2n}\in C(\vec f)+I(\vec g)$, then $0\le-h^{2n}(\vec a)\le0$, thus $h(\vec a)=0$, thus $h_i(\vec a)=0$ for some $i=1,\dots,t$.

$1\to2$: Assume 2 is false. Let $S=F[x_1,\dots,x_m]$, and $P=C(\vec f)+I(\vec g)\subseteq S$. Notice that every $s\in S$ is a difference of two squares, e.g., $s=\bigl(\tfrac12(s+1)\bigr)^2-\bigl(\tfrac12(s-1)\bigr)^2$. Since $-h^{2n}\notin P$ for all $n$, Lemma 1 gives a homomorphism $\phi\colon F\to K$, where $K$ is an ordered field, $\phi(P)\ge0$, and $\phi(h)\ne0$. We may assume $K$ is real closed. Since $P$ includes $F^+$, $\phi$ restricts to an ordered field embedding of $F$ in $K$; we may simply assume $F\subseteq K$. Then, putting $a_i=\phi(x_i)$, we have $f_i(\vec a)\ge0$, $g_i(\vec a)=0$, and $h_i(\vec a)\ne0$ in $K$. The existence of $\vec a$ with these properties can be expressed as a first-order formula with parameters from $F$; since this formula is true in $K$, quantifier elimination for real-closed fields implies it is also true in $R$.

Proof of the lemma:

Using Zorn’s lemma, let $Q\supseteq P$ be a maximal subset of $S$ closed under $+$ and $\cdot$ such that $-u^{2n}\notin Q$ for any $n\in\omega$.

Put $I=Q\cap(-Q)$. Since $Q$ is closed under $+$ and $\cdot$, $I$ is closed under $+$ and $-$, and we have $IQ\subseteq I$. Since $S=Q-Q$, this means $I$ is an ideal of $S$.

I claim that $S=Q\cup(-Q)$. Assume for contradiction that $a,-a\notin Q$ for some $a\in S$. As $a\notin Q$, $Q+aQ$ is a proper extension of $Q$ closed under $+$ and $\cdot$, thus by maximality of $Q$, we have $-u^{2n}=q+ar$ for some $n\in\omega$ and $q,r\in Q$. Likewise, $-a\notin Q$ gives $-u^{2m}=s-at$ for some $m$ and $s,t\in Q$. We have $-u^{2m}r\in-Q$, and $-u^{2m}r=sr-atr=sr+qt+u^{2n}t\in Q$, thus $u^{2m}r\in I$. It follows that $-u^{2(n+m)}=qu^{2m}+aru^{2m}\in Q+I\subseteq Q$, a contradiction.

I also claim that the ideal $I$ is prime. Assume for contradiction $ab\in I$, but $a,b\notin I$. Without loss of generality, $a,b\notin Q$. Thus, $-b\in Q$, and $-u^{2n}\in Q+aQ$ for some $n$, which implies $u^{2n}b\in-bQ-abQ\subseteq Q+I\subseteq Q$. Likewise, $-u^{2m}\in Q+bQ$ for some $m$, thus $-u^{2(n+m)}\in u^{2n}Q+u^{2n}bQ\subseteq Q$, a contradiction.

Thus, $S/I$ is an integral domain, and it is a (totally) ordered ring by making $Q/I$ its positive cone. Its fraction field $K$ is an ordered field, and the quotient map $\phi\colon S\to S/I\subseteq K$ has the required properties.


Joining lists with some common elements in average case What are some ways of commutatively combining a pair of lists to produce a list comprised of elements from the pair of inputs, with no duplicates, with time complexity better than $O(n \log(n))$? Suppose we have the following inputs

$a = [5, 1, 6, 8]$

$b = [8, 4, 5, 2, 10]$

We would like to commutatively combine $a$ and $b$ to produce a list with no duplicate elements (i.e. if F denotes a function that satisfies the aforementioned criteria, then $\forall x, y \quad F(x, y) = F(y, x)$). One possible valid output is $c = [1, 2, 4, 5, 6, 8, 10]$ - since the output doesn't have to be sorted, any permutation of $c$ is just as valid (although consistency would be nice). The most obvious naïve algorithm concatenates the two lists, then removes duplicates, then sorts the result in $O(n \log(n))$ time.

Is there a commonly used name for this kind of problem, and where can I find literature about it?

Yes and no.

Set interaction is one of the problems specifically studied in Ben-Or's seminal paper on lower bounds for algebraic decision and computation trees.  The problem is formally defined as follows: Given two sets of n numbers, is their intersection empty? Equivelently, does their union have exactly 2n elements?  Ben-or proves a lower bound of Ω(n log n) for this problem.  If the sets have diffent sizes n>m, the lower bound becomes Ω(n log m), but this only beats the naive O(n log n) bound if m is subpolynomial in n.

On the other hand, if your list elements are integers, you can solve the problem in o(n log n) time using fast integer-RAM sorting algorithms.  For reasonable word sizes, I believe the fastest integer sorting algorithm runs in $O(n \sqrt{\log \log n})$ expected time [Han and Thorup, FOCS 2002].


Complexity of existence of simple polygonalization with prescribed area? This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization  is a closed chain of straight line segments that does not cross itself).

I am interested in the complexity of this problem:

Input: Set $S$ of $N$ points on integer 2D grid and a rational number $A$

Question: Is there a polygonalization that has enclosed area $A$?

  Is this problem still NP-complete?

The area $A$ is given as an integer (represented in unary)

Fekete, Sándor P. "On simple polygonalizations with optimal area." Discrete & Computational Geometry 23.1 (2000): 73-110

The answer to your question is already contained in Fekete's paper. In Section 3, Fekete shows that the following problem GRID-EMPTY is NP-complete:

  Problem: GRID-EMPTY
  Instance: a set $S$ of $n$ grid points in the plane
  Question: Is there a simple polygon on this vertex set $S$ that does not contain any other grid points on its boundary or in its interior?

By Pick's theorem, every simple polygon with grid vertices that has $b$ grid points on its boundary and $i$ grid points in its interior has area $(b+2i-2)/2$.

For the scenario in GRID-EMPTY, the smallest possible area is $(n-2)/2$, and this area can be reached if and only if the answer to the GRID-EMPTY instance is YES.
Hence, you simple have to set $A:=(n-2)/2$ in Fekete's reduction and get NP-completeness of your question.


3-Clique Partition for graphs of fixed diameter The 3-Clique Partition problem is the problem of determining whether the vertices of a graph, say $G$, can be partitioned into 3 cliques. This problem is NP-hard by a simple reduction from the 3-colorability problem. It is not hard to see that the answer to this problem is easy when $\textrm{diam}(G) = 1$ or $\textrm{diam}(G) > 5$. The problem remains NP-hard when $\textrm{diam}(G) = 2$ by a simple reduction from itself (given a graph $G$, add a vertex and connect it to all other vertices).

What is the complexity of this problem for graphs with $\textrm{diam}(G) = p$ for $3\le p \le 5$?

The problem seems to be in $P$.

Take two vertices $u$, $v$ with distance exactly 3 (such a pair must exist when $p\ge 3$). They must have different colors (I will use R, G, B to denote 3 colors and the vertices in the same clique are colored the same color). Wlog assume $u$ is colored Red and $v$ is colored Green.

Now the rest of the vertices are partitioned into 3 sets: $\Gamma(u)$ (neighbors of $u$), $\Gamma(v)$ and $V-\Gamma(u)-\Gamma(v)$. The third set must be colored Blue because they are  adjacent to neither $u$ nor $v$. Neighbors of $u$ must be colored either Red or Blue because they are not adjacent to $v$, similarly neighbors of $v$ must be colored either Green or Blue. Each vertex now has at most two choices, therefore the problem becomes a 2-SAT instance that we can solve in polynomial time.


Circuit complexity of Majority function Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i > n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I mean not relying on the probabilistic method like Valiant 84 did or on sorting networks; preferably providing an explicit, straightforward construction of the circuit):

$f$ can be computed by a family of circuits of $O(\log(n))$ depth, poly(n) size, where the gates consists of NOT gates, 2-input OR gates, and 2-input AND gates.

Computing restricted threshold gate ($\sum_i x_i \geq k$) is essentially sorting input bits.

If you can sort the bits then it is easy to compare the result to $k$ and
compute restricted threshold.

On the other hand, assume that we have an circuits to compute restricted threshold.
We can do a parallel search to find the number of ones in the input and
output the sorted list.

These preserve circuit depth. So if you come up with a new $\mathsf{NC^1}$ circuit to compute the restricted threshold then it will give a depth $O(\lg n)$ sorting circuit.
So if we come up with a simple argument for showing majority is in $\mathsf{NC^1}$
you have found a simple depth-$O(\lg n)$ sorting circuit
(other than the one based on AKS sorting network).

Note that it is easy to implement the restricted threshold using majority by adding new 1 and 0 inputs to the majority gate.

Previously this answer claimed that it can be done using divide and conquer and the fact that binary addition is in $\mathsf{AC^0}$. That only shows that majority is in $\mathsf{AC^1}$ and $\mathsf{NC^2}$ since we have unbounded fan-in gates in the binary addition if we do it directly. However it can be done with a bit more work.

We have to use the trick called three-for-two to remain in depth $O(\lg n)$.

  three-for-two binary addition:
  given three binary numbers $a,b,c$ we can compute two binary numbers $x,y$ such that
  $a+b+c = x+y$.

Another method is to use signed digit representation of integers where addition can be done in depth $O(1)$ and fan-in 2. (The idea is to use the flexibility that a number can be represented in more than one way to make sure that carries do not propagate).

See section 4 and exercise 4 in

David Mix Barrington and Alexis Maciel, "Advanced Course on Computational Complexity", lecture 6, IAS/PCMI, 2000.


Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm What is the best known query complexity of Goldreich-Levin learning algorithm?
Lecture notes from Luca Trevisan's blog, Lemma 3, states it as $O(1/\epsilon^4 n \log n)$.
Is this the best known in terms of dependence on $n$? I will be particularly grateful for a reference to a citable source!

Related question: what is the best known query complexity of Kushilevitz-Mansour learning algorithm?

The question seems somewhat under-specified in the sense that it did not specify the desired error probability of the procedure. Assuming one means constant error probability, then the above is indeed the best I know. For a detailed discussion see Sec 2.5.2.4 in my book "The Foundations of Cryptography - Volume 1" available at http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html

THE ABOVE IS WRONG. SEE CORRECTED ANSWER BELOW.

Prop 2.5.6 in the aforementioned section proves a much better bound:
The algorithm runs in expected time $O(n \log^3(1/\epsilon))$
times the running time of the guessing procedure
(see improvement from $n^2$ to $n$ in the comment right after the proof)
and is correct w.p. $\Omega(\epsilon^2)$. Hence, correctness w.p. $2/3$
is obtained in time (factor) ${\tilde O}(n/\epsilon^2)$, which is optimal in some sense
(see Exer 30).


DFA intersection in subquadratic space? The intersection of two (minimal) DFAs with n states can be computed using O(n2) time and space. This is optimal in general, since the resulting (minimal) DFA may have n2 states. However, if the resulting minimal DFA has z states, where z=O(n), can it be computed in space n2-eps, for some constant eps>0? I would be interested in such a result even for the special case where the input DFAs are acyclic.

The answer is yes without any requirement on the size of the automaton. It can be computed in $O(\log^2 n)$ space even for $k$ DFAs where $k$ is a constant.

Let $A_i = (Q_i, \Sigma_i, \delta_i, z_i, F_i)$  ($i \in [k])$ be $k$ DFAs. We show that, given $\langle A_1, \ldots, A_k \rangle$, computing the minimal DFA recognizing $\text{L}(A_1) \cap \cdots \cap\text{L}(A_k)$ can be done in $O(\log^2 n)$ space. We first prove some technical results.

Definition 1: Let $q, r$ be two states then $q \equiv r$ iff $\forall w \in \Sigma^*$, $q . w \in F \Leftrightarrow r . w \in F$

We now consider the automaton $A$ given by the classical cartesian product construction. Let $q = (q_1, \ldots, q_k)$ and $r = (r_1, \ldots, r_k)$ be states of $A$.

Lemma 1: Deciding whether $q \equiv r$ is in NL.

Proof (sketch): We show that testing inequivalence is in NL and use NL = coNL. Guess a word $w \in \Sigma^*$ (one letter at the time) such that $q . w$ is a final state and $r . w$ isn't. This can be achieved by computing $q_i . w, r_i . w$ in log-space for $i \in [k]$ and using the fact that $q$ is final iff $q_i \in F_i \, \forall i \in [k]$. It can be shown that $q \not\equiv r$ implies the existence of a $w$ of poly-size.

Lemma 2: Deciding whether $q$ is (in)accessible is in NL.

Proof (sketch): Guess (poly-size) paths from $z_i$ to $q_i$ ($i \in [k]$).

Definition 2: Consider the states of $A$ in lexicographical order. Define $s(1)$ as being the first accessible state and $s(i)$ the first accessible state following $s(i-1)$ which isn't equivalent to any previous state. We define $c(q)$ as the unique $i$ such that $q \equiv s(i)$.

Lemma 3: $s(i)$ can be computed in $O(\log^2 n)$ space.

Proof (sketch): Definition 2 yields an algorithm. We use $k$ counters to iterate over the states. Let $j \leftarrow 0$ and $q$ be the current state. At each state, we use lemma 2 to verify if $q$ is accessible. If it is, we loop on every previous states and we verify if any of them is equivalent to $q$. If there isn't any, we increment $j$ and output $q$ if $j = i$. Otherwise, we store $q$ as being $s(j)$ and we continue. Since we only store a constant number of counters and our tests can be carried out in $\text{NL} \subseteq \text{DSPACE}(\log^2 n)$, this completes the proof.

Corollary 1: $c(q)$ can be computed in $O(\log^2 n)$ space.

Theorem: Minimizing $A$ can be done in $O(\log^2 n)$ space.

Proof (sketch): Let $1 \leq m \leq |Q_0| \cdots |Q_1|$ be the largest $i$ such that $s(i)$ is defined (ie. the number of classes of $\equiv$). We give an algorithm outputting an automaton $A' = (Q', \Sigma, \delta', z', F')$ where

$Q' = \lbrace s(i) : i \in [m] \rbrace$;
$F' = \lbrace q \in Q' : q_i \in F_i \, \forall i \in [k] \rbrace$;
$z' = s(c(q))$ where $q = (z_0, \ldots, z_k)$.

We now show how to compute $\delta'$. For every $i \in [m], a \in \Sigma$, compute $q \leftarrow s(i) . a$ and output the transition $\left(s(i), a, s(c(q))\right)$. By lemma 3 and corollary 1, this algorithm runs in $O(\log^2 n)$ space. It can be checked that $A'$ is minimal and $\text{L}(A') = \text{L}(A)$.


How to compute ROOK Polynomials for NxM Matrices How to compute ROOK Polynomials for NxM Matrices for k objects ?

See the answers of this question.

Your case is a lot easier, just choose $k$ of the $m$ columns and then you have
$n (n-1)\ldots (n-k+1)$ ways to put the $k$ rooks. So the coefficient of $x^k$ is

$\displaystyle r_k = \binom{m}{k} n (n-1)\ldots (n-k+1) = \binom{m}{k}\binom{n}{k}k!$.

The provided link also gives a dynamic programming approach to compute $r_k$.


Ternary (and beyond) computation and quantum computing? Binary math is at the heart of most computing, in large part because of the ease with which two energy states can be achieved.  I have always thought that having more states could improve computing power (e.g. using a trit instead of a bit), but there is a seeming lack of attention being paid to the problem.

Some work has been done in the quantum computing area using qubits to achieve more than the normal two energy levels (see, for example, the recent effort at UCSB).

What advances have been made toward having ternary (or greater) computers, and what are the primary the implications of the extra states?

Actually the usual RAM model is just this approach taken into extreme: each "storage unit" has as many as $\textrm{poly}(n)$ possible states (instead of just 2 states). We assume that each memory word can store $O(\log n)$ bits and word-operations have unit cost.

Cf. this question.