Lower bound on the number of "short" paths in a rooted tree with polynomial size

The lower bound is $\Omega(\log n)$ paths with $O(\log n)$ branching nodes, if you have at least $\Omega(\log n)$ branching nodes in the tree.

This can be achieved: use a tree which has one long path (length $n$) all of whose nodes are branching nodes, with no other branching nodes in the tree.

Here is a sketch of the lower bound.

First, compactify the tree by contracting any interior node that isn't a branching node. If the original size of the tree was $< n^c$, the new tree must still be $< n^c$, since you've only reduced the number of nodes. Now, the depth of a leaf is the number of branching nodes on the original path to that leaf, and we have a complete binary tree (every node has either degree 2 or 0).

If there are no leaves of depth $\Omega(\log n)$, then the number of paths is one more than the number of branching nodes, which is $\Omega(\log n)$, so we can assume that at least one leaf has depth $\Omega(\log n)$.

Next, recall Kraft's inequality. If the depth of a leaf in a complete binary tree is $d(v)$, then $\Sigma_{v \mathrm{\ leaf}} 2^{-d(v)} = 1$.

Now, we have fewer than $n^c$ leaves. We want to show that we have a lot of them at depth $O(\log n)$. Suppose we eliminate from consideration the ones that are depth at least $\log_2(n^{c+1}) = (c+1) \log_2 n$. This removes at most weight $1/n$ from the sum in Kraft's inequality, so for those leaves $v$ at depth at most $d(v)\leq (c+1) \log_2 n$, we have $\sum_{v\mathrm{\ low \ depth \ leaf}} 2^{-d(v)} > 1-\frac{1}{n}$.  We also have $\sum_{v\mathrm{\ low\ depth\ leaf}} 2^{-d(v)} < 1$ (since at least one leaf has depth too large to be included in this sum).

It's fairly easy to show that to get a sum of numbers $2^{-k}$ strictly between $1$ and $1-\frac{1}{n}$, we need at least $\log_2 n$ of them. This shows that there are $\Omega(\log n)$ paths with $O(\log n)$ branching nodes.


Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?

The framework of parametric search allows you to do this in many cases. While it was first developed by Meggido for parallel implementation, the idea is more general. Roughly speaking, you start with an oracle $g(x)$ that tells you, given a point $x$, to which side (left or right) the optimum-achieving $x^*$ lies. The idea is to "pretend" to simulate the cost function on the optimal solution. At some point, you're stuck because you don't know which path of a branch to take (since you don't know $x^*$). You identify the breakpoints of this branch, and then using $g$ decide which ones to explore further.

I'm handwaving a lot, because parametric search is quite complicated. This survey talks about ways of making it practical, and also has a decent explanation of the basic idea. This older survey gives a number of examples of parametric search.


Is there a linear time algorithm for integer multiplication verification?

There is a linear time randomized algorithm, that is of complexity $O(\log n)$: Cf M. Kaminski, A note on probabilistically verifying integer and polynomial products, J. ACM 36(1), pp. 142–149, Jan. 1989.
The basic idea: Instead of checking $n = ab$ modulo $p$ for some random prime number $p$, check it modulo $2^i-1$ for some integer $i$. The reduction modulo $2^i-1$ is fast (faster than modulo a prime $p$) since only additions are required. And if you take $i = O(\log^{1-\epsilon} n)$, the computation of $(a\bmod 2^i-1)(b\bmod 2^i-1)$ can be done in (sub)linear time. Kaminski proves that if $n\neq ab$, $n\not\equiv ab\bmod 2^i-1$ with high probability.


Transitivity check vs. Transitive Closure

Below I'll show the following: if you have an O($n^{3-\varepsilon}$) time algorithm for checking if a graph is transitive for any $\varepsilon>0$, then you have an O($n^{3-\varepsilon}$) time algorithm for detecting a triangle in an $n$ node graph, and hence (by a paper from FOCS'10) you'd have an O($n^{3-\varepsilon/3}$) time algorithm for multiplying two boolean $n\times n$ matrices, and hence by a result of Fischer and Meyer from the 70s, this also implies an O($n^{3-\varepsilon/3}$) time algorithm for transitive closure.

Suppose that you want to detect a triangle in an $n$ node $G$. We can now create the following graph $H$. $H$ is tripartite with partitions $I,J,K$ on $n$ nodes each. Here each node $x$ of $G$ has copies $x_I,x_J,x_K$ in the parts $I,J,K$. For each edge $(u,v)$ of $G$ add directed edges $(u_I,v_J)$ and $(u_J,v_K)$. For each nonedge $(u,v)$ of $G$ add the directed edge $(u_I,v_K)$.

First, if $G$ contains a triangle $u,v,w$, then $H$ is not transitive. This is since the edges $(u_I,v_J),(v_J,w_K)$ are in $H$ but $(u_I,w_K)$ is not. Second, if $H$ is not transitive, then there must exist some directed path from some node $s$ to some node $t$ in $H$ such that $(s,t)$ is not a directed edge in $H$. However, the longest paths in $H$ have $2$ edges, and so any such path must be of the form $(u_I,v_J),(v_J,w_K)$ and $(u_I,w_K)$ is not in $H$, hence $u,v,w$ form a triangle in $G$.


Implications of faster randomized $CIRCUIT SAT$ algorithm

The gist of the proof of the proposition you're talking about is to simply cite that $EXP\subset P/poly$ implies $EXP=\Sigma_2^p$ (there is a short proof of this in the Arora and Barak book in the chapter on circuit complexity), and then you can show using this time $2^{n^{o(1)}}poly(m)$ Circuit SAT algorithm that $\Sigma_2^p\subseteq DTIME[2^{n^{o(1)}}]$, which contradicts the time hierarchy theorem (I can edit in a hint for this if this is desirable).

If we replaced the assumption, we would no longer get anything we know to be a contradiction in the above argument. As one of the comments mentioned, it is currently open whether $ZPP=EXP$, and even a substantially weaker version of the proposition with a randomized algorithm would give us this separation (note, as the comment says, $BPP$ and $ZPP$ are contained in $P/poly$).
It is known that if $P = NP$ (so in the flavor of the above, if Circuit SAT has a $poly(n+m)$ time algorithm), we get exponential size lower bounds against $E$. This follows as we know $E^{\Sigma_2^p}$ has exponential size lower bounds, and if $P=NP$, then $E=E^{\Sigma_2^p}$. I'm not sure who this argument first came from, but the idea is that using a $\Sigma_2^p$ oracle, on an input $x$ of length $n$, we can find the lexicographically first truth table of an $n$-bit boolean function with the maximum circuit complexity over $n$-bit boolean functions in time $2^{O(n)}$. After doing this, we can simply look up the value of $x$ in this truth table and output accordingly. In doing this, not only are we computing a function which requires exponential sized circuits, but we are actually showing, as Ricky pointed out in the comments, that $E^{\Sigma_2^p}$ has a language of maximum circuit complexity.  Also, to clarify a point mentioned in the post, to get $P=BPP$, you actually need that $E$ does not even infinitely often have circuits of size $2^{\delta n}$. This does follow from $P=NP$, but it is a stronger hypothesis than $E\not\subset SIZE[2^{\delta n}]$.
The argument above works for any runtime that falls into $2^{n^{o(1)}}$, so this includes $2^{n^{1/\log\log(n)}}$.


This problem is known to be NP-complete (since the 1970s).
Dyer and Frieze established its NP-hardness even for the highly restricted special case where the graph $G$ is planar and bipartite:

  Martin E. Dyer, Alan M. Frieze:
  On the complexity of partitioning graphs into connected subgraphs.
  Discrete Applied Mathematics 10(2): 139-153 (1985)


The first part of your question is answered by Trakhtenbrot's Theorem.
The second part is quite a large question indeed.  Depending on the relational structure you're working on, multiple solutions can be given.  For instance, if you're interested in formal languages, MSO over word structures corresponds to regular languages, and the matching logic (see this) corresponds to CFL, and thus have their satisfiability problem decidable.

You should have a look at Chapter 14 of Libkin, where nice segments of FO are proven to have a decidable satisfiability problem, according to the amount of quantifier alternations allowed.


This http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf
survey by Anne Condon contains many facts about space bounded interactive proof systems.

There are several models, and the main differences are whether you allow private coins for the verifier (IP) or public coins only (AM), and whether you also restrict the verification
time to polynomial (not implied by the space bound alone).

Without the time restriction the answer is yes: IP(log-space) contains EXP
and AM(log-space)=P.

Note that IP(log-space) is most likely larger than standard IP. On the other hand
IP(log-space, poly-time)=IP=PSPACE.

AM(log-space, poly-time) = P due to 'Delegating Computation: Interactive Proofs for Muggles' by Goldwasser et al., STOC 2008.

Furthermore the paper 'Zero knowledge with log-space verifiers' by Kilian (FOCS 88)
shows how to get a log-space poly-time zero knowledge proof system for everything in IP (with private coins obviously).


Using $n$ calls to the halting oracle and time $O(n^2)$, you can compute the first $n$ bits of the Chaitin's constant.  Using the $n$ bits of the Chaitin's constant and unbounded time, all queries to the halting oracle of length approximately $≤n$ (depending on the representation) can be eliminated.  Finally, the result can be obtained in bounded time by querying the halting oracle.

Additional Details: In the relativization of $\mathrm{PSPACE}$ here, the oracle tape counts against space usage, so a $\mathrm{PSPACE}^\mathrm{Halt}$ machine can only use queries of length $n^{O(1)}$ (though the number of the queries can be exponential).  The digits of the Chaitin's constant can be used to get the number of machines of length $≤n$ that halt, and by simulating all these machines until the right number halts, we can find out exactly which of the (roughly $2^n$) machines halt.  The digits of the Chaitin's constant, or just the number of the halting machines, can be computed in $n^{O(1)}$ queries by bisection.


How to simulate sequential registers from causal ones?

Answer my own question: The answer is (probably; please let me know if I am wrong) negative: it is impossible to simulate sequential registers from causal registers.

Note: the following proof is indirect. And I am still interested in a direct proof.

  Theorem: It is impossible to simulate sequential registers from causal registers.

Proof: In the thesis [1], Kawash shows that causal consistency memory (with only $\texttt{read/write}$ operations) cannot solve mutual exclusion. However, Lamport's bakery algorithm (wiki), when run on sequential consistency memories, solves mutual exclusion.

[1] Limitations and Capabilities of Weak Memory Consistency Systems by Jalal Y. Kawash, PhD Thesis, 2000.


Complexity of counting graph endomorphisms

Counting endomorphisms or fixed-point-free endomorphisms is complete for $\mathsf{FP}^{\mathsf{\# P}}$: given a connected graph $G$, consider the graph $G'$ which is the disjoint union of $G$ and a triangle. Then $|\text{End}(G')| = (|\text{End}(G)| + \# 3COL(G))(\#\{\text{triangles in } G\} + 3^3)$, so $\# 3COL$ can be computed using two endomorphism counts (and by a general result, even just one suffices) and some poly-time post-processing. Note that the number of triangles can be counted in cubic (or even matrix multiplication) time. The same equation holds for fixed-point free endomorphisms, since the 3-colorings and triangles are fixed-point-free endomorphisms of $G'$.

If you would like $G'$ to be connected, you can do as follows. First note that counting vertex-colored graph endomorphisms (where vertices of color $c$ can only be mapped to other vertices of color $c$) is equivalent to counting graph endomorphisms, as follows. Let the colors be $\{1,...,C\}$. For each vertex $v$ of color $c$, add in a new disjoint odd cycle $C_v$ of size at least $n + 2c$ ($n=|V(G)|$), and connect one vertex of $C_v$ to $v$. Every endomorphism of $G$ corresponds to $2^n$ endomorphisms of the new graph (for each cycle, you have two choices of how to map it). Note that no vertices of $G$ can map to vertices of any $C_v$, since the cycles are too large (you'd have to be able to fit one cycle inside another, which you can't for odd cycles).

Now, to make a version of $G'$ that is connected, we start with a colored version, and then apply the above transformation. Start as before, by adding to $G$ a disjoint triangle $\Delta$. Now add a single new vertex $v_0$ that is connected to every vertex in $G \cup \Delta$. Color $v_0$ red and all other vertices blue.


For some NP-complete problems, there's a SUCCINCT variant that's NEXP-complete.

An example is SUCCINCT HAMILTON PATH:

A Boolean circuit with 2n inputs and one output represents a graph on 2n vertices. To determine if there is an edge between vertices i and j, encode i and j in n bits each, and feed their concatenation to the circuit: there is an edge between these vertices iff the output of the circuit is true. Given such a circuit, is there a Hamilton path in the graph represented by the circuit?

Similarly, there's SUCCINCT 3SAT, SUCCINCT KNAPSACK, etc.

Reference

Hana Galperin, and Avi Wigderson (1983), "Succinct representations of graphs", Information and Control 56:3, pp. 183–198.


One way I have often found theory problems to work on is by reading about an area and trying to figure out exactly what the state of the art is on a problem.  Invariably, some basic questions end up being left unanswered, and that’s where I will start my research. Such questions are sometimes left unanswered not because they are too difficult, but because nobody formalized things properly, and this is something that can come naturally to a theorist who is just trying to understand what’s known and what’s not. And the ability to formalize problems is a key aspect of doing successful theory.

Another natural way to do successful theory is by trying to solve known open problems, for example those found in the discussion sections of recent papers.  There, the key is having a good enough understanding of your own strengths and interests that you choose problems where you might make progress.  This takes some experience and also some self-awareness, which you can actively think about and cultivate as you go through your PhD.

And as you do your PhD, you’ll develop these skills and more, including the ability to grasp proofs in papers quicker, and if things go well, you’ll be coming up with your own directions naturally by the end.


Computing the convex hull of lattice points

The time is essentially the same as that for sorting numbers in the range $1,\dots M$.

Graham scan (in the version where the points are sorted by their x-coordinates (with ties broken by y coordinates) rather than the one the textbooks unaccountably use in which they are sorted radially) can find convex hulls in linear time after the sorting step. So for your problem in which the coordinates are small integers, all the standard bounds of integer sorting apply. In particular, radix sort can achieve time $O(n(1+\frac{\log M}{\log n}))$ (e.g. linear time whenever $M$ is at most polynomial in $n$), and a randomized sorting algorithm of Han & Thorup 2002 can achieve time $O(n\sqrt{\log\log n})$. These are in models of computation in which machine words hold integers of some word length that is big enough to store the numbers $n$ and $M$ and in which one can do arithmetic and table lookups in constant time.

Conversely, you could use a convex hull algorithm to sort a set of numbers $x_i$, by finding the hull of the points $(x_i,x_i^2)$. So if you could do convex hulls any faster than this, you could also improve the times for integer sorting. (The range $M$ of $y$-coordinates of these points would be the square of the range of the numbers, but since all the time bounds involve logarithms of this range, squaring $M$ makes no difference in terms of the eventual $O$-notation.)


Is the Mendler-encoding in System-F adequate?

$\newcommand{\Alg}{\mathsf{Alg}\ }$
$\newcommand{\NatF}{\mathsf{NatF}\ }$
$\newcommand{\Nat}{\mathsf{Nat}}$
$\newcommand{\map}{\mathrm{map}\ }$
$\newcommand{\Z}{\mathrm{Z}}$
$\newcommand{\S}{\mathrm{S}}$
I don't think this is an actual counter-example.
Parametricity implies:
$$∀(α : \Alg \NatF t) (g : r → t)(x : \NatF r). \\
α\ [r]\ g\ x = α\ [t]\ (λx.x)\ (\map g\ x)
$$
(a special case of the free theorem), where
$$\map g\ x = Λt. λz\ s. x\ [t]\ z\ (s \circ h)$$
let:
$$h : (∀s. s → s) → t \\
h\ \_ = α\ [t]\ (λy. y)\ (Λt. λz\ s. z)$$
which is your first argument to $α$. Then in your example:
$$α\ [∀s. s→s]\ h\ x \\
= α\ [t]\ (λx.x)\ (\map h\ x) \\
= α\ [t]\ (λx.x)\ (Λt. λ\_\ s. s (α\ [t]\ (λx. x)\ (Λt. λz\ \_. z)))$$
Now observe the following from $\Z$ and $\S$
$$
α\ [\Nat]\ (λy. y\ [t]\ α)\ (Λt. λz\ \_. z)  \\
  = α\ [t]\ (λx.x)\ (\map (λy. y\ [t]\ α) (Λt. λz\ \_. z)) \\
  = α\ [t]\ (λx.x)\ (Λt. λz\ \_. z)
$$
$$
α\ [\Nat]\ (λy. y\ [t]\ α)\ (Λt. λ\_\ s. s\ n) \\
 = α\ [t]\ (λx.x)\ (map (λy. y\ [t]\ α) (Λt. λ\_\ s. s n)) \\
 = α\ [t]\ (λx.x)\ (Λt. λ\_\ s. s (n\ [t]\ α))
$$
Then, if we go back to the calculation from your example:
$$
α\ [t]\ (λx.x)\ (Λt. λ\_ s. s (α\ [t]\ (λx.x)\ (Λt. λz\ \_. z))) \\
  = α\ [t]\ (λx.x)\ (Λt. λ\_\ s. s (\Z\ [t]\ α)) \\
  = \S\ \Z\ [t]\ α
$$
So your example is extensionally equal to $1$, assuming my calculations are correct.


Efficient algorithm for existence of permutation with differences sequence?

This is a sketch of a possible reduction to prove that it is NP-hard:

1) $a_i$ subsequences made of 1s (e.g. $...11111...$) (I call them 1SEQ) force a subsequence of increasing or decreasing numbers in the permutation;

2) if a value of $2$ is put in a long 1SEQ,  it forces a hole (a missing number) and doesn't change the direction of the 1SEQ. For example: $1112112111$ forces two holes:

 a_i seq.:     1 1 1  2  1 1  2   1  1  1  forces
 permutation: 1 2 3 4 _ 6 7 8 _ 10 11 12 13 (or its decreasing equivalent)
 (from 4 you cannot go back to 2,
 from 8 you cannot go back to 6)

The holes must be filled in the rest of the permutation.

3) using a large enough 1SEQ, followed by a 1SEQ with some holes, followed by another large 1SEQ you can build a forced line;

4) putting together many forced lines you can build a permutation grid graph in which the nodes correspond to the missing numbers in the underlying forced permutation.

For example the sequence 1111111112111111111112111111111, forces the following 5x7 permutation grid graph:

29 30 31 32 33 34 35
22 23 24    26 27 28
15 16 17 18 19 20 21
 8  9 10    12 13 14
 1  2  3  4  5  6  7

(or its symmetric version). Note that if the grid has size $w \times w$ and $a,b$ are two missing numbers in the same vertical column then $|a-b|=kw$.

5) the Hamiltonian cycle on grid graphs problem is NP-complete; so given a grid graph $G$ (with holes) you can build the equivalent permutation grid graph;

6) from the last number of the permutation you can "jump" to a number corresponding to a hole (a node in $G$), and with a fixed sequence of moves you can simulate the traversal of $G$; this requires a rather complex gadget - the "selection gadget" - that must be created in another part of the permutation grid graph;

7) you can fill all the holes (i.e. complete the permutation) if and only if the original grid graph has an Hamiltonian cycle

EDIT: July, 27 2013

I tried to formally prove the NP completeness of the problem: I introduced a new problem (Crazy Frog problem) which is NPC.
The Permutation Reconstruction from Differences problem is equivalent to the "1-D Crazy Frog problem without blocked cells" (which is also NPC).

For the details of the reduction see my question/answer  on cstheory
"Two Hamiltonian path variants" or download a draft of the proof "When a frog meets a permutation" :)) (I'm still checking/completing it)


Subset Sum Problem and hard looking instances that are not really hard

In my opinion, this is an utter triviality, so unimportant that no one would remark on it.   Furthermore, the chance that $t$ numbers chosen at random would have gcd > 1 is vanishingly small once $t$ is large.  (There is an explicit formula, which says that t integers chosen at random from the interval [1..n] will have gcd 1 with probability tending to $1/\zeta(t)$ as $n$ gets large.)


An algorithm to efficiently draw a extremely large graph in real time

a billion node graphs have probably not been visualized much and are right on the edge of feasibility and an active area of research. the approach would generally have to depend on the unique data characteristics to reveal the features that are relevant/key for that dataset. assuming you mean in 3d. there are at least two roughly independent hard parts of your request

realtime visualization of large dataset
visualizing a very large graph (not nec realtime)

for realtime visualization of a very large graph one could use different approaches. you mention panning and zooming. you do not mention if you want to visualize only local regions. if you want global visualization, either some kind of aggregation method or high performance backend would be required (ie large distributed system).

a reasonable approach would be developing some method of aggregating mass "nearby/related" nodes into representative groups and then visualizing the connectivity of this "super graph" instead. here are some references

[1] Drawing Large Graphs by Low-Rank Stress Majorization Khoury, Hu et al

[2] Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs Gansner, Hu et al

[3] Algorithms for Visualizing Large Networks by Hu

[4] Efficient and High Quality Force Directed Graph Drawing by Hu

[5] Interactive Visualization of Large Graphs and Networks by Munzer

[6] ZAME: Interactive Large-Scale Graph Visualization Elmqvist et al

here is a recent successful example/application/breakthrough discovery that primate brain connectivity (with about 10^10 neurons) follows a grid pattern, by Wedeen et al, based on enhanced MRI mapping/visualization

[7] NIH brain wiring study by Wedeen et al

[8] Spectacular brain images reveal surprisingly simple structure


A sorting algorithm that uses the minimum comparasions possible

Using simple methods, it can be shown that any comparison-based algorithm must perform at least $n\log{n}-o(nlogn)$ comparisons. This bound is obtained (up to lower terms) by the binary insertion sort algorithm (see e.g. [1] for a good introduction on the topic). There are also many other algorithms which obtain this bound asymptotically up to a constant factor, e.g quicksort (in expectation) and heapsort.
That said, for practical purposes I suggest you use the sorting algorithm already implemented in your prefered programming language, as it is most likely been highly optimized, and would work faster than if you implement it yourself, unless you have a very specially structured input.
[1] https://epubs.siam.org/doi/pdf/10.1137/1.9781611975482.79


SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?

We don't have integrality gaps even for Max-CUT, even for degree 4. See Barak and Steurer's notes, at the end.

You might be interested in Lee Raghavendra Steurer '14. They seem to be saying there can be no SDP relaxations for exact Max-CUT of size $2^{n^c}$ for some $c < 1$. I think this means there can be no SOS proof of degree $n^c$, and hence there are instances of Max-CUT requiring higher degree. I lack the expertise to be sure I'm interpreting this correctly though.

Other than this, I don't know of any lower bounds for the degree of SOS that can solve Max-CUT exactly.


parallelizable fast matrix in-place transposition

Sorry, no pseudocode, but a recent paper with a fast parallel algorithm, to appear in ACM Transactions on Mathematical Software:

@Article{Gustavson:2011:PCE,
  author =       "Fred Gustavson and Lars Karlsson and Bo K{\aa}gstr{\"o}m",
  title =        "Parallel and Cache-Efficient In-Place Matrix Storage Format
                  Conversion",
  journal =      "{ACM} Transactions on Mathematical Software",
  accepted =     "8 July 2010",
  upcoming =     "true",
  abstract =     "
                  Techniques and algorithms for efficient in-place
                  conversion to and from standard and blocked matrix
                  storage formats are described. Such functionality is
                  required by numerical libraries that use different
                  data layouts internally. Parallel algorithms and a
                  software package for in-place matrix storage format
                  conversion based on in-place matrix transposition are
                  presented and evaluated. A new algorithm for in-place
                  transposition which efficiently determines the structure
                  of the transposition permutation a priori is one of the
                  key ingredients. It enables effective load balancing in
                  a parallel environment.",
}

Here is the journal page, and here is a pdf version of the paper.
I hope this can be useful.


Separation between existence of crypto primitives

There are several techniques which prove the nonexistence of black-box reductions. They are all inspired by the seminal work of Impagliazzo & Rudich. Let me describe the Impagliazzo-Rudich (IR) technique at a high level.

In crypto, it is well-known how to construct a secure secret-key exchange protocol from trapdoor one-way permutations. However, all attempts to construct such protocols from general one-way permutations were failed. So, it was an open problem whether such constructions were possible at all.

The hard part of refuting those constructions is as follows: It is believed that both one-way permutations and secure secret-key exchange protocols exist; so how can we refute the latter if we merely assume the former? In IR words:

  The implication, "if one-way permutations exist, then secure secret-key agreement is possible," is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model.

While they were not succeeded to refute the existence of such black-box reductions, they were able to provide strong evidence that the implication is not provable by standard techniques. To this end, IR came up with the following model:

Assume that all parties (including the adversary) have access to a random-permutation oracle (RPO), i.e. a function chosen uniformly from all n-bit to n-bit permutations (where 1n is the security parameter). RPO models the black-box access to some one-way permutation. Now, IR prove that in this model, secure secret-key agreement is possible if and only if P ≠ NP. Since standard techniques cannot resolve the P vs. NP problem, it follows that proving (or disproving) the implication "if one-way permutations exist, then secure secret-key agreement is possible" is as hard as proving (or disproving) P ≠ NP.

Other excellent resources on this topic:

Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions: rules out black-box constructions of collision-resistant hash functions from one-way functions (as pointed out in the question). Excerpt:

  We prove the existence of an oracle relative to which there exist several well-known cryptographic primitives, including one-way permutations, but excluding (for a suitably strong definition) collision-intractable hash functions. Thus any proof that such functions can be derived from these weaker primitives is necessarily non-relativizing; in particular, no provable construction of a collision-intractable hash function can exist based solely on a "black box" one-way permutation.
  Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins.
  Notions of Reducibility between Cryptographic Primitives.

The papers are inspired by the work of IR, and extend their techniques.

5 recent papers on the topic can be found in the proceedings of TCC 2011 (see chapters Black-Box Constructions and Separations and Black-Box Separations, pages 541--629).
They have surveys of previous results, which are certainly useful.

An important technique: Black-box reductions are by definition relativizing. So, if relative to some oracle, one primitive exists but the other does not, the existence of the latter cannot be deduced in a black-box manner from the existence of the former.


Reference Request: Submodular Minimization and Monotone Boolean Functions

As far as I understand, the submodular minimization case captures all there is to be said about the monotone Boolean case, and binary submodular Boolean functions can express all submodular Boolean functions.  However, if the domain is non-Boolean, then binary submodular functions are not enough to express all submodular functions, even if hidden variables may be introduced.  (Apologies if I have missed a subtlety in your precise problem phrasing.)

The state of the art is discussed in this nice paper which has lots of links to related work, and that also makes the links to computer vision quite explicit:

Stanislav Živný, David A. Cohen, Peter G. Jeavons, The expressive power of binary submodular functions, DAM 157 3347–3358, 2009.  doi: 10.1016/j.dam.2009.07.001 (preprint)

In case your next question is about approximation, this recent paper looks at the approximation version:

Dorit S. Hochbaum, Submodular problems - approximations and algorithms, arXiv: 1010.1945

Edit: fixed link.


What's "pseudo time" when used in comparison with semaphores

I believe he may be referring to this paper: NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM.


The precoloring extension problem is the following:

Input: a number $k$ and a graph $G$ some of whose edges are labeled with labels in $\{1, 2, \ldots, k\}$.

Decision: is it possible to color the edges of $G$ with colors $1, 2, \ldots, k$ such that no adjacent edges share a color and such that each initially labeled edge is colored with the color it is labeled with.

In other words, given a partially colored graph, can you finish coloring it using only $k$ colors?

A specific case of this problem was proven NP-hard in the paper "NP‐completeness of list coloring and precoloring extension on the edges of planar graphs" by Daniel Marx. In particular, the author showed that precoloring extension is NP-hard even when $k = 3$ and $G$ is a planar 3-regular bipartite graph.

As it turns out, this means your problem is NP-hard too. Here's a simple reduction:

Given an instance of the precoloring extension problem consisting of partially colored planar 3-regular bipartite graph $G$ and $k = 3$, we build an instance of your problem:

We set the degree bound/number of colors (which you called $k$) to be $3$
We set $G_1$ to be $G$ with all initially non-colored edges removed
We set $c_1$ to be the partial coloring of $G$ (and since $G_1$ consists of the edges of $G$ that are colored, $c_1$ is a coloring of $G_1$)
We set $G_2$ to be $G$

Notice that $G_1$ and $G_2$ are both bipartite graphs with vertex-degrees at most $3$.

It is possible to color $G_2$ with a coloring $c_2$ that matches $c_1$ everywhere if and only if it is possible to extend the partial coloring $c_1$ on $G_1$ to a full coloring of $G_2 = G$. In other words, finding a coloring for $c_2$ which differs from $c_1$ as little as possible is equivalent to extending the partial coloring of $G$ into a full coloring.

Thus, your problem is NP-hard.

If you need to solve instances efficiently despite the fact that your problem is NP-hard, I recommend using an ILP solver: for each edge-color pair in $G_2$, make a variable that is 1 if the edge has that color and zero otherwise; then use inequality constraints to enforce that the number of colors of each edge is exactly 1 and that the number of edges at each vertex of each color is at most 1; finally, set the objective that the solver tries to maximize to the sum of the variables corresponding with edge-color pairs present in $G_1$.


Is there any natural Karp reduction from Independent Set problem to SAT?

Yes, just think how you would use a SAT solver to solve the independent set problem.
If you have one variable per node, it should be clear how to write constraints that guarantee that variables that are true indeed form an independent set. I think the only non-trivial part is counting: how to make sure that your independent set is sufficiently large. For that you can use BDD-based techniques; see e.g. Section 5.3 of this paper.


Enumerating topological sorts of a vertex-labeled DAG

One of the simplest way to compute topological ordering is performing a Depth First Search on the given DAG. Different topological orderings can be generated by exploiting the flexibility of choosing the next vertex $v$ to be traversed from the unvisited neighbours of the current vertex $u$.
Since, it is a recursive procedure enumerating all possible traversals (and hence topological orders) would be simple, by choosing different orders in which unvisited neighbours of $u$ are traversed.

Now, in order to limit repeating the same traversal because of similar labels, one can compare the unvisited neighbours $v_1,v_2,...,v_k$ of $u$ having similar labels. Consider two vertices $v_i$ and $v_j$ that have the same unvisited neighbours when the traversal reaches $u$. Surely choosing either of them first would generate the same DFS tree and hence any one of them can be avoided.

Now, comparing the neighbours of all $v_1,...,v_k$ would lead to an overhead of $O(n^2)$ on the total time, but can be performed more efficiently in $\tilde{O}(n)$ by using appropriate data structures.


As you mentioned that "My main goal is to solve different kinds of games on these graphs, but I'm curious about other problems too", you can have a look at the thesis by Morgan Chopin -- "Optimization problems with propagation in graphs: Parameterized complexity and approximation" (https://tel.archives-ouvertes.fr/tel-00933769).
Here, author shows some results with "bandwidth" for "Firefighter" problem and "Target Set Selection" problem which can be thought of as a discretized version of "Influence Maximization".


Pseudo-Random Function families whose instances have full domain

Here is a proof sketch of the security of your construction.

Let $G: \{0,1\}^k \to \{0,1\}^{3k}$ be the PRG and let $G_0, G_1, G_2$ denote the first, middle, and last third of the output of $G$.

Define the function $F_{x,m}$ as follows:

$\qquad
F_{x,m}(y) =
  \begin{cases}
    rand & \mbox{ if } y<x \mbox{ in lex order} \\
    G_m( rand ) & \mbox{ if } y=\epsilon \\
    G_m( F_{x,b}(y') ) & \mbox{ if } y=y'b \\
\end{cases}$

Here $rand$ denotes a value chosen at random for each $(y,m)$, independent of everything else.

Now $F_{\epsilon,2}$ is your GGM construction instantiated with a random seed. Suppose we picture the GGM construction as a labeling of the edges and vertices of a binary tree. Each vertex is associated with a finite binary string. Each vertex labels its two outgoing edges $G_0(\ell), G_1(\ell)$  and labels itself $G_2(\ell)$, where $\ell$ is the value assigned to its incoming edge. Then $F_{x,2}$ is the result of having vertices $y < x$ assign their relevant labels totally randomly.

Fix an adversary $A$ with running time $p(\cdot)$, to which we give oracle access to a function of this form. We'll consider the sequence of hybrids $F_{\epsilon,2}, F_{0,2}, F_{1,2}, F_{00,2}, \ldots, F_{\omega,2}$, where $|\omega| > p(k)$.  From $A$'s point of view, $F_{\omega,2}$ has output distributed identically to a totally random function.

If $x$ is the successor of $x'$ in lex order, then $F_{x,2}$ and $F_{x',2}$ differ only in one application of the PRG. Thus, successive hybrids are indistinguishable. However, we've proposed an exponential number of hybrids, so we are not yet done! Intuitively $A$ can only "notice" the changes in a polynomial-sized portion of the tree. We formalize this as follows:

Conditioned on the event that $A$ never queries its oracle on a string beginning with $x$, then $F_{x,2}$ and $F_{x',2}$ give identical output distribution. Let $q_x$ denote the probability that $A$ queries its oracle on such a string, and let $\delta(\cdot)$ denote the negligible security error of the PRG. Then we have:

$\qquad\Big|\Pr[A^{F_{x,2}}(1^k) = 1] - \Pr[A^{F_{x',2}}(1^k) = 1] \Big| \le q_x \delta(k)$

Then by a hybrid argument, we have:

$\qquad\Big|\Pr[A^{F_{\epsilon,2}}(1^k) = 1] - \Pr[A^{F_{\omega,2}}(1^k) = 1] \Big| \le \delta(k)\sum_x q_x$

The first expression involves $A$ with oracle access to the GGM function, and the second expression involves $A$ with oracle access to a random function. Now we bound the sum $\sum_x q_x \le p(k)^2$. Since $\delta(k) p(k)^2$ is negligible, the construction is a PRF.


Computing a transitive completion / path existence oracle

Compact reachability oracles exist for planar graphs,

Mikkel Thorup: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6): 993-1024 (2004)

but are "hard" for general graphs (even sparse graphs)

Mihai Patrascu: Unifying the Landscape of Cell-Probe Lower Bounds. SIAM J. Comput. 40(3): 827-847 (2011)

Nevertheless, there is an algorithm that can compute a close-to-optimal reachability labeling

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick: Reachability and Distance Queries via 2-Hop Labels. SIAM J. Comput. 32(5): 1338-1355 (2003)

Maxim A. Babenko, Andrew V. Goldberg, Anupam Gupta, Viswanath Nagarajan: Algorithms for Hub Label Optimization. ICALP 2013: 69-80

Building on the work of Cohen et al. and others, there is quite a bit of applied research (database community) see e.g.

Ruoming Jin, Guan Wang: Simple, Fast, and Scalable Reachability Oracle. PVLDB 6(14): 1978-1989 (2013)

Yosuke Yano, Takuya Akiba, Yoichi Iwata, Yuichi Yoshida: Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. CIKM 2013: 1601-1606


Examples of learning via exactly integrable gradient flows

How about the simple squared loss function used in linear regression? That is, let $\ell(w(t), z) = \frac{1}{2n} \sum_{i=1}^n (z_i^\top w(t) - y_i)^2$ for data vectors $z_i \in \mathbb{R}^d$ and $y\in \mathbb{R}^n$?
For the sake of this answer, I'll use the shorthand notation $Z \in \mathbb{R}^{d\times n}$, where each column of $Z$ is the vector $z_i \in \mathbb{R}^d$.
If you use this as the loss function, then the given differential equation is $$\frac{dw(t)}{dt} = -\eta (ZZ^\top) w(t) + Z y.$$ I think this can be solved to get the solution you seek, and I explain below.
Suppose $Z$ is rank-$n$, and let $Z = \sum_{i = 1}^n s_i u_i v_i^\top$ be its singular value decomposition. Pre-multiplying the given ODE with any of the $u_i$ vectors yields the ODE $$ \frac{d}{dt} (u_i^\top w(t)) = - \frac{1}{n} s_i^2 u_i^\top w(t) + \frac{1}{n} s_i v_i^\top y.$$ This is a standard first-order constant coefficient ODE and can be solved  by, for instance, the method of integrating factors. Applying this technique gives $$ u_i^\top w(t) = \frac{1}{s_i} v_i^\top y + c_i (\frac{s_i}{n} v_i^\top y) e^{-\frac{s_i^2 t}{n}}, $$ where $c_i$ is a constant of integration. If you are given an initial condition, you can use it to obtain $c_i$. Suppose you have $w_0 = 0$. Then, this initial condition results in the rule $$u_i^\top w(t) = \frac{1}{s_i} (v_i^\top y) (1 - e^{-s_i^2 t/ n}), $$ for all $i \in [n]$. Therefore, as $t\rightarrow \infty$, we have for all $i \in [n]$ that $u_i^\top w(t) \rightarrow \frac{1}{s_i} v_i^\top y$. This means the loss $\ell(w_t, z) \rightarrow 0$, as you require.


Here is the sketch of a proof I know.
Let us draw $s = \max\left(\frac{4M}{\varepsilon},\frac{c}{\varepsilon} \log\frac{1}{\delta}\right)$ samples from the unkown distribution (where $c$ isconstant), and feed them as input for the mistake-bounded algorithm. We can assume the learning algorithm is conservative, i.e., only changes its working hypothesis after an incorrect prediction has been made.

Look at the sequence of $k \le M$ hypothesis produced by the learner; we claim that, with probability $1-\frac\delta2$, at least one of them has error $< \frac\varepsilon2$. Assume the contrary and observe that any hypothesis with error $\ge \frac\varepsilon 2$ will be found to be wrong within the next $\frac{2}\varepsilon \le \frac{s}{2M}$ random examples on average. Therefore the expected number of samples before the last hypothesis is produced is bounded by $s / 2$. By using a Chernoff-like bound for the sum of geometric random variables, we can bound the probability that a hypothesis with error $< \frac \varepsilon 2$ is not found within $s$ samples by $\delta / 2$ (for a suitable value of $c$).

The rest is easy: we know that one of the hypothesis is good, so we just draw $O\left(\frac{1}{\varepsilon} \log{\frac{M}{\delta}}\right)$ additional samples, test each of them against this new sample set, and select the best one. By Chernoff bounds, it holds that with probability $1-\frac\delta 2$, the good one has empirical error $< \frac{3}{4} \varepsilon$ on this set, while any wrong hypothesis with error $> \varepsilon$ will have empirical error $> \frac{3}{4} \varepsilon$. All in all, a hypothesis with error less than $\varepsilon$ will be selected with probability $1-\delta$.

My guess is that the bound is optimal, but I haven't found a reference for this.


Using lambda calculus to derive time complexity?

There are quantitative results concerning $\lambda $-calculus, in the form of measuring the length of reductions in (typed-)lambda calculus. But this is of course far from saying anything about the complexity of algorithms (especially that the bounds obtained are fast-growing). See for example:  Arnold Beckmann, Exact bounds for lengths of reductions in typed $\lambda $-calculus, Journal of Symbolic Logic 2001, 66(3): 1277-1285.

For something closer to your question, there is a current project that develops and studies a type-system (a functional programing language) which by static-analysis can determine (polynomial) run-time bounds of programs (as well as other resources used by programs). So in some sense, this might hint that there might be some advantage in using functional-programing for analyzing  run-time complexity. The project homepage is here.

A possibly representative paper of this project is:
Jan Hoffmann, Martin Hofmann. Amortized Resource Analysis with Polynomial Potential - A Static Inference of Polynomial Bounds for Functional Programs.  In Proceedings of the 19th European Symposium on Programming (ESOP'10).link


Why does this cut elimination procedure terminate (contraction case)?

I extend what I wrote as a comment. As there is a great number of cases in the proof, I only give an idea of why this transformation terminates. The short answer is:

In the case promotion vs contraction, after the transformation, the number of contractions in the part of the proof containing cuts has decreased by one.

To go a bit more into details, I would say that you were mistaken because you thought that either the number of cuts or the size of the proof should decrease in order to ensure termination. However, termination can be proven by looking at other parameters of the proof.

If you want to prove termination, you only have to show that each rule will be applied a finite number of time. You can prove that the transformation rule promotion vs contraction will be applied at most m times, where m is the number of contractions in your initial proof. To prove this, you just have to observe that no rule introduces a new contraction in proof tree. And this one decreases the number of contraction by one. You can do this trick for any other rules "promotion vs sthg" to prove that this one will be applied only a finite number of time.


Induction over a transitive relation in Coq

It is not clear to me how induction helps with the lemma you are trying to prove, so I'll take an alternative approach.

Firstly, I prove two helper lemmas that break apart and put back together ==>  with --> at the tail, rather than at the start. Based on these lemmas, I can manipulate the result using your definition of eval to get the desired result. My impression is that the core lemma relies too heavily on the somewhat odd definition of eval, which possibly allowed me to side-step any inductive argument you had in mind.

So, although the lemma you are interested in does not require induction over the transitive relation, the two helper lemmas do.

Note: proofs have not been optimised or beautified.

The first lemma inverts instances of t ==> ti so that the single step reduction occurs at the end, rather than at the beginning. The proof relies on induction and was undemanding.

Lemma end_inversion :
  forall (t ti : State),
    t ==> ti ->
    t = ti \/
      exists t', t ==> t' /\ t' --> ti.
Proof.
  intros.
  induction H.

  left; auto.

  destruct IHeval_trans; right.

  exists t.
  subst.
  split; [apply refl | auto].

  destruct H1 as [x [H1 H2]].
  exists x.
  split; auto.
  apply trans with (ti := ti); auto.
Qed.

The second lemma plugs a single step reduction onto the end of a transitive reduction to again get a transitive reduction. The proof is by straightforward induction.

Lemma end_eval :
  forall (t ti t' : State),
    t ==> t' ->
    t' --> ti ->
    t ==> ti.
Proof.
  intros.
  induction H.
  apply trans with (ti := ti); [auto | apply refl].
  apply trans with (ti := ti0); auto.
Qed.

And now your lemma. The proof relies on end_inversion to break up ==>, does some manipulation of the result, and puts things back together using end_eval. No induction is required.

Lemma some_lemma :
  forall (a a' : Address) (m m' : Memory),
    (a, m) ==> (a', m') ->
    (a, m) ==> (S a', m').
Proof.
  intros a a' m m' H.
  apply end_inversion in H.
  destruct H.
  inversion H; subst.
  apply end_eval with (t' := (a', m')).
    apply refl.
    apply eval_step; auto.
  destruct H as [x [H0 H1]].
  apply end_eval with (t := (a, m)) (t' := x); auto.
  inversion H1; subst.
  apply eval_step; auto.
Qed.


Max-Cut algorithm that shouldn't work, unclear why

My earlier claim of $\frac{2}{c+6}$ did not take into account the cut of size $n^2/4$ already present in the graph. The following construction appears to result (emperically - I have created a question at math.stackexchange.com for a rigorous proof) in a $O\left(\frac{1}{\log c}\right)$ fraction.

The algorithm performs badly on unions of several disconnected, differently sized complete graphs. We denote the complete graph on $n$ vertices as $K_n$. Consider the behavior of the algorithm on $K_n$: it repeatedly adds an arbitrary vertex not yet in $S$ to $S$ - all such vertices are identical and so the order does not matter. Setting the number of vertices not yet added to $S$ by the algorithm $|\bar{S}| = k$, the size of the cut at that moment is $k (n-k)$.

Consider what happens if we run the algorithm on several disconnected $K_{x_i n}$ graphs with $x_i$ constants between 0 and 1. If $k_i$ is the number of elements not yet in $S$ in the $i$th complete graph, then the algorithm will repeatedly add a vertex to $S$ from the complete graph with highest $k_i$, breaking ties arbitrarily. This will induce `round' based additions of vertices to $S$: the algorithm adds a vertex from all complete graphs with the highest $k = k_i$, then from all complete graphs with $k_i=k-1$ (with $k_i$ updated after the previous round), and so on. Once a complete graph has a vertex added to $S$ in a round, it will do so for every round from then on.

Let $c$ be the number of complete graphs. Let $0 < x_i \leq 1$ with $0 \leq i \leq c - 1$ be the size modifier for the $i$-th complete graph. We order these size modifiers from large to small and set $x_0 = 1$. We now have that if there are $c'$ graphs with exactly $k$ elements not yet added to $S$, then the size of the cut at that time is $\sum_{i=0}^{c'-1} k (x_i n - k) = k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$. The total number of edges is $|E| = \sum_{i=0}^{c-1} \frac{x_i n (x_i n - 1)}{2} \approx \frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2$.

Note that $k n \sum_{i=0}^{c'-1} x_i - c' k^2$ is a quadratic function in $k$ and hence has a maximum. We will therefore have several locally maximal cuts. For example, if $c=1$ our maximal cut is at $k=\frac{n}{2}$ of size $\frac{n^2}{4}$. We are going to pick $x_1$ so that $x_1 = 1/2 - \varepsilon$, which means the second complete graph will not change the size of this locally maximal cut at $k=\frac{n}{2}$. We then get a new locally maximal cut at $k=3/8 n - \varepsilon'$ and so we pick $x_2 = 3/8 n - \varepsilon''$ (with $\varepsilon, \varepsilon', \varepsilon''$ small constants). We will ignore the $\varepsilon$s for the moment and just assume we can pick $x_1 = 1/2$ - we should ensure $x_1 n = \frac{n}{2} - 1$, but this will not affect the final results if $n$ is large enough.

We wish to find the local maxima of our cuts. We differentiate $k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$ to $k$, yielding $n \sum_{i=0}^{c'-1} (x_i) - 2 c' k$. Equating to $0$ gives $k = \frac{n}{2c'} \sum_{i=0}^{c'-1} x_i$, which gives a cut of size $\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$.

Let $k_i$ be the $k$ determined in the previous paragraph if $c'=i$. We will ensure that the formula holds by demanding that $x_i n < k_i$ - all complete graphs $i'$ with $i'>i$ are then smaller than the $k_i$ of this locally maximal cut and hence do not increase the size of the cut. This means we have $c$ cuts at these $k_i$ that are larger than all other cuts found by the algorithm.

Filling in $x_i n < k_i$, we get the recurrence $x_i = \frac{1}{2c'} \sum_{i=0}^{c'-1} x_i$ (plus some small $\varepsilon$) with $x_0 = 1$. Solving this yields $x_i = \frac{\binom{2i}{i}}{4^i}$: see my question on math.stackexchange.com for the derivation by @Daniel Fisher. Plugging this into $\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$ and using our insight into the recurrence gives us cuts of size $\frac{n^2}{4c'} \left(2c' \frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = n^2 c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2$. Using properties of this central binomial coefficient, we have $\lim_{c' \to \infty} c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = \frac{1}{\pi}$ (also see my question on math.stackexchange.com).

The number of edges is approximately $\frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2 = \frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{\binom{2i}{i}}{4^i}\right)^2$. By known properties we have $\frac{1}{\sqrt{4i}} \leq \frac{\binom{2i}{i}}{4^i}$. Filing in gives at least $\frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{1}{\sqrt{4i}}\right)^2 = \frac{n^2}{8} \sum_{i=0}^{c-1} \frac{1}{i}$ which is asymptotically $\frac{n^2}{8} \log c$ as $c$ goes to infinity.

We therefore have $\frac{\delta(S, \bar{S})}{|E|}$ is asymptotically equal to $\frac{8}{\pi \log c}$ as $c$ goes to infinity, showing that the algorithm can return cuts that are arbitrarily low fractions of $|E|$.


network flow using minimum number of nodes

The problem is NP-hard on layered graphs. This can be seen by reduction from Exact Cover by 3-sets (X3C). Let $A_1,\ldots,A_m$ be subsets of $\{1,2,\ldots,3n\}$ with $\vert A_i\rvert=3$ for every $i$, the problem asks if there exists a set $I\subseteq\{1,2,\ldots,m\}$ of $\lvert I\rvert=n$ indices such that $\bigcup_{i\in I}A_i=\{1,2,\ldots,3n\}$. This can be reduced to the following instance of your problem. The node set is
$$V=\{s,t\}\cup\{v_i\ :\ i=1,2,\ldots,m\}\cup\{w_j\ :\ j=1,2,\ldots,3n\}.$$
There are the following arcs:

an arc $(s,v_i)$ with capacity 3 for every $i\in\{1,2,\ldots,m\}$,
an arc $(v_i,w_j)$ with capacity 1 for every pair $(i,j)$ with $j\in A_i$
an arc $(w_j,t)$ with capacity 1 for every $j\in\{1,2,\dots,3n\}$.

A flow of value $3n$ can be achieved using $4n$ nodes (not counting $s$ and $t$) if and only if the X3C-instance is a YES-instance.


The complexity of counting simple paths in a directed graph

The #P-completeness proof of counting simple s-t paths in both undirected and directed graphs can be found in:

Leslie G. Valiant: The Complexity of Enumeration and Reliability Problems. SIAM J. Comput. 8(3): 410-421 (1979)

From the paper:

...
4. Some #P-complete problems
...
14. S-T PATHS (i.e. SELF AVOIDING WALKS) (directed or undirected)
Input: $G; s,t \in V$
Output: Number of (directed) paths from $s$ to $t$ that visit every node at most once.
...


Queueing Theory: How to estimate steady-state queue length for single queue, N servers?

You need to apply Little's law:

  The long-term average number of customers in a stable queue L is equal to the long-term average arrival rate, λ, multiplied by the long-term average time a customer spends in the queue, W; or expressed algebraically: L = λW.

The beauty of this law is that it does not depend on the distribution of arrivals or the service time (whether it is Markovian or not, etc.). More technically, and in Kendall's notation, it is true for the general GI/G/m queues.

We now assume that service time follows an exponential distribution (with parameter μ), and the arrivals follow a Poisson distribution (with parameter λ). In addition, we assume there's only one server. That is, our queue is modeled as M/M/1.

Using Little's Law, it can be shown (see formula (6.15) on page 247 of this book) that:

$W = \frac{\lambda/\mu^2}{1-\lambda/\mu}$

Note that the book uses different notations than here. It also states the formula holds for M/G/1-PS and M/G/1-LCFS queues.

Using Little's Law, we have $L = {\lambda^2 \over \mu^2-\lambda\mu}$.

In your case, λ = 1/(KT), and μ = 1/T. Hence L = 1/K(K-1).

PS: Little's Law has 3 variants. It can be applied to the whole system, to the queue itself, or to the service center. See pages 259-260 of this book for more info.

Edit: The case for M/M/c queues is much trickier. Here, you need to apply Erlang C formula.

To derive the following formulas, you can take a look at Section 5.2.3 of this book.

Let $a := \lambda/\mu$ and $\rho := a/c$, where c denote the number of servers. Then Erlang C formula, $C[c,a]$ is obtained by:

$C[c,a] = \frac{a^c}{c!} / ((1-\rho)\sum\limits_{n=0}^{c-1}\frac{a^n}{n!}+\frac{a^c}{c!})$

Now we have: $L = \rho C[c,a] / (1- \rho)$.

As a sanity check, note that for $c=1$ we derive the previous answer: $L = {\lambda^2 \over \mu^2-\lambda\mu}$.


What is the best lower bound for the fault-tolerance threshold in quantum computing?

The highest threshold lower bound for for independent stochastic noise of which I am aware is $1.04 \times 10^{-3}$ by Aliferis, Gottesman and Preskill (quant-ph/0703264).  They analyze Knill's teleportation-based scheme with postselection.

If you are willing to consider independent depolarizing noise, then I know of two slightly higher lower bounds: $1.25\times 10^{-3}$ by Aliferis and Preskill (arXiv:0809.5063) and $1.32 \times 10^{-3}$ by myself and Ben Reichardt (arXiv:1106.2190).


What Lecture Notes Should Everyone Read?

Probability Theory And Randomized Algorithms

Lecture notes from Ryan O'Donnell's course Probability and Computing is pretty neat.

Lecture notes from Amit Chakrabarti's course Data Stream Algorithms


What are interesting algorithmic questions for groups in table representation?

First, is it a group at all?  A fundamental problem is checking whether a given operation (in table form) is associative.  The obvious approach is cubic time, Rajagopalan and Schulman do it in near-quadratic time.


Efficiently computing the exact union of 'N' intersecting circles on a plane

See this earlier MathOverflow question: the union of circles can be constructed (as its set of boundary arcs) in $O(n\log n)$ time. Once you have that, it's straightforward to use Green's theorem to calculate the area.


What are the relationships between those hypotheses in Fine-Grained Complexity Theory?

This is a recent paper introducing Nondeterministic Strong Exponential Time Hypothesis (NSETH), which is an extension of SETH.

NSETH: For every $\epsilon >0$, there is a $k$ such that $k$-DNF-TAUT cannot be solved in nondeterministic time $2^{(1-\epsilon)n}$.

NSETH implies SETH. If NSETH is true, then some problems do not have SETH lower bounds (because they have nondeterministic algorithms faster than deterministic algorithms).

This paper also introduced Non-uniform Nondeterministic Strong Exponential Time Hypothesis (NUNSETH), a hypothesis stronger than NSETH and SETH.

NUNSETH: For every $\epsilon >0$, there is a $k$ such that $k$-DNF-TAUT cannot be recognized by nondeterministic circuit families of size $2^{(1-\epsilon)n}$.


Exact complexity of a problem in $\cap_{m \geq 2}\mathsf{AC}^0[m]$

I do not think this is in AC0 and I can show a lower bound for the related promise problem of distinguishing between $\sum x_i = 0$ and $\sum x_i = 2$, when $x \in \{-1, 1\}^n$. Similar Fourier techniques should apply to your problem, but I have not verified that. Or maybe there is a simple reduction.

Suppose there is a size $s$ depth $d$ circuit that computes a function $f: \{-1, 1\}^n \rightarrow \{0, 1\}$ such that  $f(x) = \sum_i x_i$ whenever $\sum_i x_i \in \{0,2\}$. Because for a random $x$, the probability that $\sum_i x_i = 0$ is $2^{-n} {n \choose n/2} \approx n^{-1/2}$, and for each such $x$ there are $n/2$ coordinates that change the value of $f$, the total influence of $f$ is $\Omega(n^{1/2})$, which is roughly the same as majority (because you included most of majority's sensitive inputs). By a theorem of Hastad (see Colorraly 2.5 in Ryan O'Donnel's notes), this implies that

$$
s \geq 2^{\Omega(n^{1/(2d-2)})}.
$$


Rate of convergence for the Perron–Frobenius theorem

See the power method for computing eigenvectors:
http://en.wikipedia.org/wiki/Power_iteration

Convergence is exponential (geometric in the ratio of the top two eigenvalues).


'Uniqueing' an unsorted list of integers

In practice you can solve this problem easily in linear expected time with a hash table: just hash everything and eliminate the duplicates when they collide with each other. See, e.g. this Python recipe which primarily uses hashing but falls back on other strategies for objects that can't be hashed.

Whether you accept this as an acceptable theoretical answer depends somewhat on your model of computation.


Removing all but a few cycles in a graph

I think I have such a reduction for the case when we aren't allowed to break the given cycles. Let $C$ be the set of the vertices belonging to the selected cycles (wlog assume that $G[C]$ is connected), and let $D = V\setminus C$. We cannot remove any vertex from $C$. Let's collapse all the vertices from $C$ into one vertex $c_1$ (of course delete the created loops, but keep the double edges), and create $k$ copies of $c$, with the same neighborhood (so now we have a graph on $\{c_1, \dots, c_{k+1}\} \cup D$). We now search for a feedback vertex set. If I'm not mistaken, instance of feedback vertex set thus created has a solution of size $k$ iff our graph had a solution of size $k$ to our problem.

edit: Answer to Prabu's doubt from the comment

The vertices $v_1$ and $v_4$ would indeed collapse to a vertex $v$ (with all other vertices of the forbidden cycles), but the reduction creates $k+1$ copies of $v$ (let's call them $w_1, ..., w_{k+1}$). So the cycle $P$ is transformed into two families of cycles: $F_1 = \{(w_i, v_2, v_3, w_i): i \in [k+1]\}$ and $F_2 = \{(w_i, v_5, v_6, w_i): i \in [k+1]\}$. To break all the cycles from $F_1$, we would have to delete either all the vertices $w_i$ (but we can't, there's too many of them), or one of the vertices $\{v_2, v_3\}$. Same goes for $F_2$ - so altogether we delete exactly 2 vertices.

Let's now look at our original graph. We have two cycles here, one is $P$, and the other: $(v_1, v_2, v_3, v_4, c_1, c_2, ..., c_l, v_1)$, where $v_4, c_1, ..., c_l, v_1$ is some path from $v_4$ to $v_1$ using only the vertices from the forbidden cycles, which we cannot delete (we assumed that $G[C]$ is connected, if we want to get rid of this assumption, we would have to consider connected components of $C$ and collapse vertices from these components separately). To destroy both of this cycles we would also have to delete one vertex from $\{v_2, v_3\}$ and one from $\{v_5, v_6\}$ (you can easily see this when you draw this graph).

So the reduction did exactly what we wanted in this case.


Let $f\colon \{0,1\}^n \to \{0,1\}$ be a boolean function. If it has a polynomial representation $P$ then it has a multilinear polynomial representation $Q$ of degree $\deg Q \leq \deg P$: just replace any power $x_i^k$, where $k \geq 2$, by $x_i$. So we can restrict our attention to multilinear polynomials.

Claim: The polynomials $\{ \prod_{i \in S} x_i : S \subseteq [n] \}$, as functions $\{0,1\}^n \to \mathbb{R}$ form a basis of for the space of all functions $\{0,1\}^n \to \mathbb{R}$.

Proof: We first show that the polynomials are linearly independent. Suppose that $f = \sum_S c_S \prod_{i \in S} x_i = 0$ for all $(x_1,\ldots,x_n) \in \{0,1\}^n$. We prove by (strong) induction on $|S|$ that $c_S = 0$. Suppose that $c_T = 0$ for all $|T| < k$, and let us be given a set $S$ of cardinality $k$. For all $T \subset S$ we know by induction that $c_T = 0$, and so $0 = f(1_S) = c_S$, where $1_S$ is the input which is $1$ on the coordinates of $S$. $~\qquad\square$

The claim shows that the multilinear representation of a function $f\colon \{0,1\}^n \to \{0,1\}$ is unique (indeed, $f$ doesn't even have to be $0/1$-valued). The unique multilinear representation of OR is $1-\prod_i(1-x_i)$, which has degree $n$.


Ramification of An Impredicative Type Theory

I'm going to elaborate my comments into an answer. The origins of predicative type theory are almost as old as type theory itself, since one of Russel's motivations was to ban "circular" definitions which were identified as part of the source of the XIXth century inconsistencies and paradoxes. Thierry Coquand gives an enlightened overview here. In this theory, predicates over a "level" or type, belong to the types of the "next" level, where there is an infinite (countable) number of levels.

While Russel's predicative hierarchy was (apparently) sufficient to dismiss the known paradoxes, it turned out to be very difficult to use as a foundational system. In particular, defining even something as simple as the real number system was extremely difficult, and so Russel postulated an axiom, the Axiom of Reducibility which postulated that all levels were "reduced" to one. Needless to say, this was not a satisfactory development.

However, contrary to the "harmful" impredicative statements (like unrestricted comprehension), this axiom did not seem to introduce any inconsistencies. The subsequent formulations of foundational theories (simple type theory, Zermelo's theory of sets) accepted them wholesale, making families of predicates (quantifying over possibly the whole universe of sets), predicates at the same level.

Circa 1971, Martin-Löf introduced dependent type theory in which both this principle and the further axiom Type : Type hold. This system turned out to be inconsistent for subtle reasons: the naive Russel paradox can not be played out (in a straightforward manner), but a clever encoding nevertheless allows a contradiction to be found. This prompted a crisis of faith similar to that of Russel, resulting in the predicative type theory with universes we know and love.

There is a way to repair the theory to allow "innocent" impredicativity a la Zermelo set theory, resulting in type theories like the Calculus of Constructions, but the damage was done, and the "Swedish school" of type theory tends to reject impredicativity.

Several points:

What does this have to do with intuitionistic mathematics? The answer is not much. At the turn of the XXth century, mathematicians tended to conflate the use of circular/impredicative principles with non-constructive reasoning (the intuition being that impredicative reasoning seems to assume a pre-existing mathematical universe, as does uses of the excluded middle). However, there are perfectly intuitionistic impredicative theories (like IZF). People interested in intuitionism still tend to be interested in predicativism for some reason (I'm guilty of this, of course).
What can you do in predicative mathematics? As Martin points out in his answer, Hermann Weyl (not to be confused with Andre Weil) started a program which tried to explore the expressive power of predicative systems, taking as starting point that predicative systems were of expressive strength between Peano Arithmetic and Second Order Arithmetic, which is pretty much agreed to be impredicative by most standards (and is comparable to System F on the type theory side). The program was later dubbed "reverse mathematics" as it tried to classify the strength of known mathematical theorems in terms of the axioms required to prove them (the reverse of the usual approach). The wikipedia page give a good overview; the program was quite successful, in that most of XIXth century mathematics can easily be accommodated in very weak systems. It is still an open question whether this program can scale to more recent results in, say, higher category theory (the suspicion is that the answer is "yes, with great effort").


What is the optimal data structure for a tree of maps.

First of all, I think what you mean by "map" is a "dictionary" in TCS lingo. Second, I don't understand the phrase "ideally the lookup would still be $O(\log N)$", since in a dictionary the lookup takes O(1) time with various hash tables. Thirdly, you haven't stated whether the problem is static or dynamic; I'm assuming static.

The optimal complexity to this problem is $\Theta($predecessor search), e.g. $O(\lg\lg N)$ using van Emde Boas. This is optimal if you word size is $\Theta(\lg n)$; see http://people.csail.mit.edu/mip/papers/pred/pred.pdf for the optimal predecessor bounds.

The proper way to attack the problem is to build one global hash table and deal with the hierarchy separately for each key in the table. For one key $x$, we know the nodes where it appears. Consider an in-order traversal of the tree. The nodes where $x$ appears define intervals in this order. To determine whether $x$ is in the hash table of some node $v$, you have to ask whether $v$ stabs any segment as defined above. This is easily done by predecessor search, where we build a predecessor table for all interval end points.

For a lower bound, note that even one stabbing question is as hard as predecessor (see the reductions from colored predecessor search). Since the paper references above shows optimal direct-sum behavior for predecessor search, it means the algorithm described above is optimal for any ration between the number of nodes and the total number of keys.


Is the following optimization problem (a variant to a previous problem) NP-hard?

This is easy to solve in polynomial time.

To see this, it may be easiest to interpret $S$ as a preorder $\le$ on $N$:

$i \le j$ iff $(i,j) \in S$ or $i = j$.

Then we define the equivalence relation $\sim$:

$i \sim j$ iff $i \le j$ and $j \le i$.

Now let $W$ consist of all equivalence classes of $\sim$; for each $i \in N$ let $[i] \in W$ be its equivalence class. Put otherwise, $[i]$ consists of all $j \in N$ such that $(j,i) \in S$ and $(i,j) \in S$. Now we can define the natural partial order $\le'$ on $W$:

$[i] \le' [j]$ iff $i \le j$ for each $i,j \in N$.

We say that $[i] \in W$ is maximal if $[i] \le' [j]$ implies $[i] = [j]$. We have the following property that is easy to verify:

If $[i]$ is maximal, we cannot get the benefit $c(j)$ for all $j \in [i]$.

Hence in any solution, for every maximal class $[i]$, we have to choose at least one node $j \in [i]$ such that we do not get the benefit of $c(j)$.

We now construct a solution as follows: For each maximal class $[i]$, choose a node $j \in [i]$ that minimises $c(j)$; we say that $j$ is a sink node. Now assume that $k \in N$ is not a sink node. There are too cases:

$k \in [i]$, where $[i]$ is maximal. Now we can simply choose the edge $(k,j) \in S$, where $j \in [i]$ is a sink node, and collect the benefit of $c(k)$.
$k \in [i]$, where $[i]$ is not maximal. Then there is a maximal set $[\ell]$ with $[i] \le [\ell]$. Let $j \in [\ell]$ be the sink node, choose the edge $(k,j) \in S$, and collect the benefit of $c(k)$.

That is, we can get the benefit of $c(k)$ for all nodes $k \in N$ that are not sink nodes; the solution is optimal.


A first order logic extended with binding terms like the familiar set descriptors $\{x:\varphi\}$

I would recommend looking at higher-order logics (HOL), for instance Lambek and Scott's Introduction to Higher-Order Categorical Logic. Such a logic will set up binding of bound variables and treat variable contexts properly (single-sorted first-order logic tends to have a somewhat simplistic view of those).

Note that your suggestion to always bind just a single variable does not cover operators that require simulatneous binding of several variables. They are uncommon, but do appear occasionally.

To get what you're asking for, we can cut down on the order. In HOL there is a single sort of types, including a type of propositions $\Omega$, which are closed under formation of function spaces, so that higher-order predicates are formed as $\Omega$, $A \to \Omega$, $(A \to \Omega) \to \Omega$. To prevent these, we can stratify the types into several sorts:

the sort of primitive types $A$, $B$, $C$, ... (in first-order logic you often have just a single one, which is not mentioned at all)
the sort of propositions $\Omega$
the sort of first-order functions $(A_1, \ldots, A_n) \to B$, where $A_i$ and $B$ are primitive types
the sort of (first-order) propositional functions $(A_1, \ldots, A_n) \to \Omega$, where $A_i$ are primitive types.

Variables always range over primitive types. A context $\Gamma$ is a list of variables with their (primitive) types, $\Gamma \equiv x_1 : A_1, \ldots, x_n : A_n$. We never speak of an expression without specifying its context, so that we can keep track of which variables are allowed to appear.

If $S$ is a sort, we write $\Gamma \vdash e : S$ when $e$ is an expression of sort $S$ in context $\Gamma$. For example,
$$x : \mathbb{R}, y : \mathbb{R} \vdash (\exists z : \mathbb{R} . x + z = y) : \Omega$$
is the assertion that $\exists z : \mathbb{R} . x + z = y$ is a proposition (in the given context). It is not the assertion that $\exists z : \mathbb{R} . x + z = y$ holds! For that we postulate a new judgement of the form
$$\Gamma \mid \theta_1, \ldots, \theta_n \vdash \psi \ \mathsf{true}
\tag{1}$$
which states, intuitively, that propositions $\theta_1, \ldots, \theta_n$ jointly entail the proposition $\psi$. If we also have equations (at all types), (1) can be replaced with
$$\Gamma \mid (\theta_1 \land \cdots \land \theta_n) \land \psi =_\Omega \theta_1 \land \cdots \land \theta_n.$$
This is the approach taken by Lambek and Scott. Its main advantage is that the formal system is more like algebra, since it is just a bunch of (fancy) operations and equations.

Another example (where I am using the notation $\langle x_1 : A_1, \ldots, x_n : A_n \rangle . e$ to express the fact that the variables $x_1, \ldots, x_n$ are bound in $e$):
$$x : \mathbb{R} \vdash (\langle y : \mathbb{R}, z : \mathbb{R} \rangle . y^2 + x \cdot z) : (\mathbb{R}, \mathbb{R}) \to \mathbb{R}.$$
This says that there is a function taking $(y, z)$ to $y^2 + x \cdot z$.

We can now introduce first-order binders as operations that map first-order (propositional) functions to primitive sorts and propositions, for instance:

$\forall$ is an operation which takes a propositional function $(A) \to \Omega$ to a proposition. The formation rule would read as follows:
$$\frac{\Gamma \vdash p : (A) \to \Omega}{\Gamma \vdash \forall p : \Omega}$$
En example of such an expression would be $\forall (\langle x : \mathbb{R} \rangle . x^4 - 5 x^2 + 7 > 0)$.
Assuming there is a primitive type $\mathsf{Set}$ of sets and a relation symbol $\in$ of sort $(\mathsf{Set}, \mathsf{Set}) \to \Omega$, subset formation $\sigma$ is an operation which takes $s : \mathsf{Set}$ and $p : (\mathsf{Set}) \to \Omega$ and yields $\sigma(s, p) : \mathsf{Set}$. We also need some rules regarding these, e.g.,
$$
\Gamma \mid \vec{\theta}, e \in s, p(s) \vdash e \in \sigma(s, p) \ \mathsf{true}.
$$
We can also do unrestricted comprehension $\sigma'$, the kind that leads to Russell's paradox. It takes $p : (\mathsf{Set}) \to \Omega$ to $\sigma' p : \mathsf{Set}$. Assuming there is also $\epsilon : (\mathsf{Set}, \mathsf{Set}) \to \Omega$ and negation, we can define Russell's paradoxical $R$ as $\sigma' (\langle x : \mathsf{Set} \rangle . \lnot (x \in x))$.
For a "non-logical" example, let us introduce the $\lambda$-notation from $\lambda$-calculus. Suppose for every primitive types $A$ and $B$ there is a primitive type $A \Rightarrow B$ (normally written as $A \to B$ but I am using a different arrow to avoid confusion). For all primitive types $A$ and $B$, we can introduce an operator $\lambda_{A, B}$ which takes $f : (A) \to B$ to an expression $\lambda_{A,B} f : A \Rightarrow B$. The identity map on $A$ is thus written as $\lambda_{A,A} (\langle x : A \rangle . x)$. This is an example of a higher-order calculus of types with first-order logic layered on top of it (as opposed to HOL, where $\Omega$ is mixed with $\Rightarrow$ freely).

I do not know of any texts that would carefully developed this sort of calculus. I do not know why that is. Traditional logic textbooks usually simplify matters by considering a single-sorted first-order language, whereas the newer computer-sciency texts dive for fancier stuff with unrestricted order. You're asking for a bastard child of higher-order logic, I suppose.


I tried to write a formal proof of the NP-completeness of Problem 1 (Crazy Frog Problem, CFP).

It remains NP-complete even if restricetd to a one dimensional board (1-D Crazy Frog Problem, 1-D CFP) or to a one dimensional board without blocked cells, and there is an immediate reduction from the 1-D CFP without blocked cells to the Permutation Reconstruction from Differences sequence problem.

The reduction is from Hamiltonian path on grid graphs (a grid graph is a node-induced finite subgraph of the infinite grid: if two nodes are adjacent (distance 1 in the grid) then there is an edge between them; a grid graph can have holes, i.e. some nodes may be missing;  see "Hamilton Paths in Grid Graphs" by Alon Itai, Christos H. Papadimitriou, Jayme L. Szwarcfiter). Given a grid graph $G$ that fits in a $w \times w$ square, with nodes $u_i$ at coordinates $(x_{u_i},y_{u_i})$
and source, target nodes $s,t$; build a filled board of size $4n\times4n$ with all blocked cells except cells $(4x_{u_i},4y_{u_i})$ and target cell $(4x_t+1,4y_t)$. The initial frog position is $(4x_s,4y_s)$. This part of the board is called graph area. The first "logical" sequence of moves is the following sequence repeated $|V| - 1$ times:

(suppose that frog is in position $(x,y)$)

$(0,J_i)$: vertically jump to an empty part of the board (edge gadget)
$(-2,2)$: make a backward diagonal jump of length 2
$(0,p)$: vertically jump to another empty part of the board (on the same gadget)
$(2,2)$: make a forward diagonal jump of length 2
$(0,J_i+p)$: return to graph area in one of the cells $(x+4,y),(x-4,y),(x,y-4),(x,y+4)$

This forces the frog to make $n-1$ steps on the empty cells corresponding to the nodes of the original graph.

The sequence is followed by one horizontal step $(1,0)$ (that forces the last cell to be the one associated with the target node $t$) and a forced step that leads to a cleanup gadget. The sequence of jumps of the cleanup gadget allows it to visit all unvisited cells of the edge gadgets and completely fill the board.

This is a simple graphical outline of the gadgets used in the reduction:

Figure: Outline of a CFP instance (for better readability blocked cells are not shown, the cleanup gadget is not complete and space is compacted ). Black jumps represent the graph area traversal, green jumps represent the edge gadgets traversals, red jumps represent the vertical selection gadget traversal, blue jumps represent the horizontal hole gadget traversal.

The details can be found in the draft paper "The Crazy Frog Problem and Permutation Reconstruction from Differences" that can be download here.

The reduction is complex so perhaps it is wrong (or can be simplified), but I think that the results (if new?) are interesting ...


Data structure that allows moving groups of elements into buckets

I don't quite know if this is what you were looking for since it is not a single data structure that has a name - but what you are asking for is easily implementable using just a linked list and a binary search tree:

Keep a single linked list where all the elements of bucket $i$ come before the elements of bucket $i+1$. On every link you can have a boolean flag - is this the same bucket or next bucket. Now doing the shift corresponds to setting the flag to "same bucket" from "next bucket".

Of course you probably also want to maintain some way to see the first element of each bucket. A way to do this is to store the pointers to the first element of each bucket in a balanced binary search tree, such that the key of the pointer to bucket $i$ is $i$. The search tree should be able to: (a) given $i$, output the entry with the $i$'th lowest key and (b) delete entries from the search tree.

Merging bucket $i$ and $i+1$ now reduces to finding the entry in the search tree with the $i+1$'st lowest key, deleting this entry from the search tree, going to where it points in the list, and setting the flag of the arc pointing into this node in the list to "same bucket". Thus all operations take $O(\log n)$ time.

Note that after some "shift" operations are performed the key of the $i$'th bucket is no longer $i$, but it is the $i$'th lowest key stored in the search tree.


You can construct artificial examples by padding. For example, take an NP-hard language $L$ and pad it by zeroes to $L'=\{x0^{|x|^2}|x\in L\}$. Then the original instances form only a $2^{-n^2}$ fraction, and the answer to the fraction $1-2^{-n^2}$ of the instances is trivially "no" (no certificate is needed at all), yet the language remains NP-hard.

If you look specifically at SAT and the uniform distribution, you need to specify a particular encoding of formulas into bit strings (it will change the effective distribution on formulas). See, for example, the paper by Frieze, Goerdt, and Krivelevich on easy random SAT instances and short proofs of unsatisfiability.


Construction of a Global Isomorphism(permutation) for Graph Isomorphism using Local Isomorphism

The computational complexity of of finding $P$ is polynomial in $\beta$.

We construct the generating set of automorphism group of $H$ using  $\beta_k$, for all $k$. As we know, constructing  generating set of automorphism group of  $H$ is a  GI complete problem [1]. So, we try to construct the generating set of $Aut(H)$ . The technique used in the paper [2]  by E. Luks can used here.

Notation:

From now on, $G, H$ are adjacency matrices of graphs $G, H$ respectively. $H_k, G_k$ are blocks or sub-matrices of matrix $H, G$ respectively. The adjacency matrix of graph $H_k \cup  H_e$ is $M_{(k,e)}$ where   $M_{(k,e)} =\left( \begin{array}{ccc} H_e & R_{k,e} \\ R_{k,e}^{T} & H_k\\ \end{array} \right) $,  where, $R_{k,e}$ is the non symmetric sub-matrix of adjacency matrix $H$.  Here, $R_{k,e}$ represents  edges  between $H_k,  H_e$.  Similarly,  $S_{k,e}$ represents  edges  between $G_k, G_e$.
$$H = \begin{bmatrix}
H_{(x)} & R_{(x, x-1)} & R_{(x,x-2)} & \dots & \dots & R_{(x,1)} \\
R_{(x,x-1)} & H_{(x-1)} & R_{(x-1,x-2)} & \dots & \dots & R_{(x-1,1)} \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\
R_{(x,1)} & R_{(x-1,1)} & R_{(x-2,1)} & \dots & \dots &H_{1} \end{bmatrix}$$

For simplicity, we assume $\beta \leq n^{3}$.

The outline of the algorithm to construct generating set:

At $1^{st}$ iteration -

Step 1. Construct all possible  direct product  $(\pi_1 \times  \pi_2)$ where $\pi_1 \in \beta_1$ and $ \pi_2 \in \beta_2$.

There are $| \beta_1 | \times | \beta_2|  <  n^{9}$ direct products (permutations).  All these permutations (direct products) form set $\gamma_1$. Each element of $\gamma_1$ is a permutation that acts on graph $H_1 \cup  H_2$.

Step 2. Construct/find -

$\alpha_1 =\{ \pi \in \gamma_1 |  (M_{(1,2)}^{\pi}= M_{(1,2)}) \land ( R_{1,2}^{\pi} = S_{1,2}) \land  (H_1^{\pi} = G_1) \land  (H_2^{\pi} = G_2) \}$

$\alpha_1$ is the set of automorphisms of matrix $M_{(1,2)}$.        $|\alpha_1| < n^{9}$.There are two possible cases-

Case 1:  If $|\alpha_1| =1$, then  for each $\pi_1 \in \beta_1$,  there is only one permutation
$\pi_2 \in \beta_2$. So, there could be maximum $n^{2}$ permutations in $\gamma_1$ but only one permutation could be included in $\alpha_1$.

Case 2: If $|\alpha_1| >1$,  we would be able to construct a generating set $\mathcal{S}_1$ of an automorphism group of $Aut(M_{(1,2)})$ Note, that if $\exists \pi_a \in Aut(H)$ such that it acts on   vertices of $H_1 \cup H_2$, then  $  \pi_a \in \langle \mathcal{S}_1 \rangle =Aut(M_{(1,2)})$. So, when we construct direct product of  $\mathcal{S}_1$ and another set,   $\pi_a$ can be found in the resulting generating set. See Theorem 7, on page 31 of [3].The theorem showed how to obtain the automorphism group of an arbitrary graph from the intersection of a specific  permutation group with a direct product of symmetric groups.

Step 3. Now, we construct the generating set  $\mathcal{S}_1$  from $\alpha_1$. This construction of generating set can be done in polynomial time (see [3], page 40, theorem 9). From  [4], we find that $|\mathcal{S}_1| \leq log(n!)$ .
 $\mathcal{S}_1$ is the  generating set  of automorphism of  $H_1 \cup H_2$ .

Step 4. We start $2^{nd}$ iteration, for $\beta_3, \mathcal{S}_1$ (instead of $\beta_2$), $ M_{(2,3)}$  where $M_{(2,3)} =\left( \begin{array}{ccc} H_3 & R_{2,3} \\ R_{2,3}^{T} & H_2 \\ \end{array} \right) $.  We find $\gamma_2, \alpha_2$ repeating  steps $1,2$ and construct $\mathcal{S}_2$ (repeating  step $3$)  which  is the  generating set  of automorphism of  graph $H_1 \cup H_2 \cup H_3$. Note that,                    $|\mathcal{S}_2|  \leq log(n!)$ .

Step  5. We keep repeating above  four   processes, until we find the set $\mathcal{S}_{(x-1)} $  which  is the  generating set  of automorphism of graph $H_1 \cup H_2 \cup H_3 \dots \cup H_x=H $. Note that, $|\mathcal{S}_{(x-1)}|\leq  log(n!)$, since $ \langle \mathcal{S}_{(x-1)} \rangle= Aut(H) \leq S_n$.

Detecting Isomorphism:  We repeat the process of construction of $\mathcal{S}_{(x-1)}$ for graph $G$ and obtain set $\mathcal{R}_{(x-1)}$. I assumed, that  the oracle that gave $\beta_k$, would provide permutation sets for $G$ also.

Once we generate  generating sets of $G, H$, we can decide isomorphism betwen them [1].

References:

[1]Mathon, Rudolf. ,A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), no. 3, 131–132.

[2] Luks , Eugene M. , Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences, Volume 25, Issue 1, (1982), Pages 42-65.

[3]Hoffmann, Christoph M. ,Group-Theoretic Algorithms and Graph Isomorphism.

[4] Miller, Gary L.  ,On the $n^{\log_2(n)}$ Isomorphism Technique.

Feel free to down-vote, but please leave a comment if you have anything  technical to say, Thanks for your patience.


Topology/Space of Recursive Algebraic Datatypes

It is possible to construct recursive datatypes (algebraic datatypes are a special case) in a suitable category of complete metric spaces, see for instance P. America and J. Rutten's Solving Reflexive Domain Equations in a Category of Complete Metric Spaces, Journal of Computer and System Sciences 39, 343-375 (1989).

As for making vector spaces out of algebraic datatypes, I do not really know, but if you explain what you want them for, we might be able to suggest something.


I agree with @usul. I've also never seen the term empirical mutual information mentioned, but I've seen the term empirical entropy quite a lot, especially in the compression community. The definition of empirical information is $-\Sigma p_i \log p_i$, where $p_i$ are the empirical probabilities, i.e. the fraction of the time that each value appears in your samples.

To compute empirical mutual information given samples $(x_1,y_1),\ldots,(x_n,y_n)$, I'd just compute the empirical entropy of the $x$'s separately, and of the $y$'s separately, and of the pairs together, and then I'd use the standard equation $I(X:Y)=H(X)+H(Y)-H(XY)$, where all quantities on the right hand side are replaced by their empirical analogue.

I don't know if this is equivalent to the equation that @usul gave, and I don't know if this is the quantity referenced in the articles you're reading, but this seems like the natural interpretation to me.


How to start studying topics Hardness of approximation and PCP's

I recommend Lectures on Proof Verification and Approximation Algorithms,  E.W.Mayr and H.J.Prömel and A.Steger (Eds.), Lecture Notes in Computer Science, vol. 1367, Springer Verlag 1998. These lectures are very suitable for studying these topics from the basic.


Maximum difference between two shortest paths

There exists an optimal solution $p,q,c$ such that $c_e = l_e$ for all edges $e$ in the path $q$ and $c_e = u_e$ otherwise.
For the optimal solution from point 1 exists a vertex $x$ at which the paths $p$ and $q$ split. The subpath $p^x$ of $p$ from $x$ to $v$ is a shortest path from $x$ to $v$ for the edge weights $u$ (the upper bound).

To solve the problem consider the following procedure:

For all $x \in V$:

Compute the length of the shortest path from any vertex $y \in V$ to $w$ for the edge weights $u$. The lengths are stored in $d \in \mathbb{N}^V$.
Define the node potentials $\pi_y = d_x - d_y$.
Compute the shortest path from $x$ to $v$ that respects the node potentials $\pi$, i.e. choose the edge weights such that the shortest path to $v$ with respect to $c$ is greater or equal to $\pi_y$ for all $y \in V$. This can be done by a modified Dijkstra algorithm. The Dijkstra algorithm normally takes fixed edge weights $c$. We choose the edge weights as follows: $\min\{ c \in [l_e,u_e] \mid \pi_w \leq d(u) + c \}$. Furthermore, make sure to take the shortest path that only uses edges with edge weights at their lower bound if possible.
If the above procedure finds a shortest path from $x$ to $v$ that only uses edges with edge weights at their lower bound, then $x$ might be a splitting point from point 2. Remember that $x$ as well as the resulting edge costs $c^x$

For all the remembered pairs of vertices $x$ and corresponding edge costs $c^x$, compute the shortest path to $x$, simillar to the shortest path from $x$ to $v$. Now change $c_e^x$ to $l_e$ for all edges in that shortest path. The solution to problem is now given by
$$ \max_{x}\{c_p^x - c_q^x \mid p \text{ is a shortest } s,w \text{-path}, q \text{ is a shortest } s,v \text{-path} \}. ~~~~~~~ (1)$$

Illustration of correctness:

Let $\mathcal{D}$ be the domain of the original problem and $p,q,c^x$ the solution of (1), then we have $(p,q,c^x) \in \mathcal{D}$. Hence, the solution of (1) is smaller or equal to the solution of the original problem.

Now let $(p,q,c)$ be the solution of the original problem and let $x$ be the splitting point of the two paths $p$ and $q$. The described procedure considers $x$ and computes the shortest path to $v$, which is exactly $p(x \rightarrow v)$, such that the shortest path $\rho$ to $w$ is the shortest path with respect to the edge weights at their upper bound $u$. We therefore get:
$$ c_p - c_q = c_{p(s \rightarrow x)}  + c_{p(x \rightarrow w)} -  c_{q(s \rightarrow x)}  + c_{q(x \rightarrow v)} \\
= c_{p(x \rightarrow w)} - c_{q(x \rightarrow v)} \leq c_{p(x \rightarrow w)} - c_{\gamma}. $$
Hence, the solution of (1) is greater or equal to the solution of the original problem.

To prove the correctness of the modified Dijkstra algorithm, one can modify the original proof.


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$.


The maximum number of induced cycles in a simple directed graph

I don't know what's already known but the obvious bounds are that it is at most $\binom{n}{n/2}$ (Sperner's theorem) and at least $3^{n/3}$ (for $n$ a multiple of three that is at least 9: form a cycle of three-vertex sets and add all edges between vertices in consecutive triples). These bounds hold both for the directed and undirected cases.

The $3^{n/3}$ bound turns out to be the right one, to within a polynomial factor at least, for both the directed and undirected cases. To see this, choose a starting vertex in one of $n$ ways (or a starting edge in the undirected case), and then greedily choose the remaining vertices of the cycle one by one. At each step where you have $k$ choices (the remaining neighbors of the most recently chosen vertex), each choice eliminates all those $k$ vertices from the remaining subproblem, because they can no longer be part of any induced cycle extending what you've already chosen. So, if you define $C(i)$ to be the maximum number of extensions that you could still make, given that you have $i$ remaining vertices, then this number obeys the recurrence $C(i)\le\max_{k\le i} kC(i-k)$. The maximum value of $k$ in this recurrence is given for $k=3$, giving $C(i)\le 3^{i/3}$.


Given a type system T, and a type $A$ in that type system, is there an (effective) surjection from $\mathbb{N}$ onto the set of terms of that type?

One could ask the same of set theory: isn't the set of terms that can be written down countable? Why isn't there a surjection from $\aleph_0$ to any set?

The answer, of course, is in the difference between internal truth and external truth.

Externally, the set of well typed terms of type $A$ (say in the empty context) is recursively enumerable in any reasonable type theory (like MLTT), so there is an effective surjection from $\mathbb{N}$ to that set iff it is non-empty, by a classical result in recursion theory.

Internally however, it is generally not possible to prove that such a surjection exists. In particular, a bijection between say, $\mathbb{N}$ and $\mathbb{N}\rightarrow\mathbb{N}$ implies a contradiction by a simple diagonalization argument (see, e.g., here).

In fact the proof works even if we only require a retract instead of a bijection. However this doesn't preclude a surjection from $\mathbb{N}$ to $\mathbb{N}\rightarrow\mathbb{N}$! It's only necessary that this surjection does not have a right inverse (in set theory, these right inverses always exist, but the proof of that requires the axiom of choice).

It is in fact consistent, but not provable, to assume that such a surjection exists.


A Mealy machine consists of a state set $S$, an initial state $s \in S$, and a transition function $A \times S \to B \times S$ (which takes as input a letter from the alphabet $A$ and a current state $S$, and produces an output letter drawn from $B$ and an updated state from $S$).

We can write this as a type declaration in Ocaml like so:

type ('a,'b) mealy = M : 's * ('a * 's -> 'b * 's) -> ('a,'b) mealy

Then the compose operation in looks like this:

let compose : type a b c. (a,b) mealy -> (b,c) mealy -> (a,c) mealy =
  fun (M(s, f)) (M(t, g)) ->
    let state = (s,t) in
    let trans (a, (s, t)) =
      let (b, s') = f(a, s) in
      let (c, t') = g(b, t) in
      (c, (s',t'))
    in
    M(state, trans)

So the state of the composite machine are the products of the two state sets, and the new initial state is the pairing of the two initial states, and the composite transition function feeds the input to the first transition function and uses its output as the input to the second transition function.


What is a totally ordered sort of sets of a partial order called?

In the context of geometric dominance orders, the standard term is "layers of maxima" (in your case, minima). Obviously, the same term can be used for any partial order.

http://dx.doi.org/10.1007/11785293_34

http://dx.doi.org/10.1007/s00453-004-1082-5


This problem can be transformed into the assignment problem, also known as maximum weighted bipartite matching problem.

Note first that the edit distance equals the number of elements which need to change from one set to another.  This equals the total number of elements minus the number of elements which do not need to change.  So finding the minimum number of elements which do not change is equivalent to finding the maximum number of vertices that do not change.

Let $A = \{ A_1, A_2, ..., A_k \}$ and $B = \{ B_1, B_2, ..., B_l \}$ be partitions of $[1, 2, ..., n]$.  Also, without loss of generality, let $k \ge l$ (allowed because $edit(A, B) = edit(B, A)$).  Then let $B_{l+1}$, $B_{l+2}$, ..., $B_k$ all be the empty set.  Then the maximum number of vertices that do not change is:

$\max_f \sum_{i=1}^k |A_i \cap B_{f(i)} |$

where $f$ is a permutation of $[1, 2, ..., k]$.

This is exactly the assignment problem where the vertices are $A_1$, ..., $A_k$, $B_1$, ..., $B_k$ and the edges are pairs $(A_i, B_j)$ with weight $|A_i \cap B_j|$.  This can be solved in $O(|V|^2 \log |V| + |V||E|)$ time.


How fast can we find and disconnect roots in a forest?

The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations [1], thus overcoming the lower bound for generic version of the problem. Their solution is based on Euler tour of the tree with union-split-find structure (and fast LCA for trees with unbounded degree).

The same paper states that it is an open problem whether this bound is tight.

[1] D. Breslauer and G. F. Italiano. Near real-time suffix tree construction via the fringe marked ancestor problem. Selected papers from the 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011) https://www.sciencedirect.com/science/article/pii/S1570866712001062#br0230


Proof of undecidability not by reduction from the halting problem

One can show fairly directly that Kolmogorov complexity is not computable, see e.g. Sipser, 3rd edition, problem  6.23.


Check the following links for graph instances

DIMACS Graphs: Benchmark Instances and Best Upper Bounds
foo

Graph Coloring Instances

CLIQUE Benchmark Instances


understanding programming monads through diagrams

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.


$\mathcal{MA}$ in terms of $\mathcal{PCP}$

If you want to restate the definition of MA in terms of PCP, you need another parameter for PCP, namely the proof length.  MA is clearly the same as PCP with polynomial randomness, polynomial queries, and polynomial-length proofs.  Usually the proof length in PCP is not restricted (that is, it is bounded only implicitly by randomness and queries), but this is insufficient to restate the definition of MA.

If you are looking for some characterization of the form MA = PCP(q(n), r(n)), which is not just the restatement of the definition of MA, then I do not think that any such characterization is known.


Substitutions form a monoid and they act on terms. We have a choice of writing them as either left or right actions. Sometime in the previous millenium someone decided they act on the right (page 5). A right action should satisfy $a [s \circ t] = (a[s])[t]$, so it makes sense to define the operation $\circ$ that conforms to action on the right. That's all.

You could do entirely the same thing with functions and write them as $x \mathbin{//} f$ (as Mathematica does) in which case you would be seriously tempted to define $x \mathbin{//} (f \circ g) = (x \mathbin{//} f) \mathbin{//} g$. In essence you'd move from the category of sets to its opposite.


Applications of topology to computer science

Personally, I think the most interesting application of topology was the work done by Herlihy and Shavit. They used algebraic topology to characterize asynchronous distributed computation and gave new proofs of important known results and knocked out a number of long-standing open problems. They won the 2004 Godel prize for that work.

"The Topological Structure of Asynchronous Computation"
by Maurice Herlihy and Nir Shavit,
Journal of the ACM, Vol. 46 (1999), 858-923,