Is `sort` typeable on elementary affine logic?

I think sort, as presented there, isn't typeable on EAL. I can't prove that, but it doesn't work on Lamping's Abstract Algorithm without the oracle. Moreover, while the term is somewhat clever and brief, it uses very wacky strategies that are not EAL-friendly.

But behind this question there is a more interesting one: "can a nat-sorting function be implemented in EAL"? That was a very hard question back then, but now it looks pretty trivial. Yes, of course. There are many simpler ways to do it. For an example, one can just fill a Scott-encoded NatSet with Church-encoded Nats, and then convert it to a list. Here is a complete demonstration:

-- sort_example.mel
-- Sorting a list of Church-encoded numbers on the untyped lambda calculus
-- with terms that can be executed by Lamping's Abstract Algorithm without
-- using the Oracle. Test by calling `mel sort_example.mel`, using Caramel,
-- from https://github.com/maiavictor/caramel

-- Constructors for Church-encoded Lists
-- Haskell: `data List = Cons a (List a) | Nil`
Cons head tail = (cons nil -> (cons head (tail cons nil)))
Nil            = (cons nil -> nil)

-- Constructors for Church-encoded Nats
-- Haskell: `data Nat = Succ Nat | Zero`
Succ pred = (succ zero -> (succ (pred succ zero)))
Zero      = (succ zero -> zero)

---- Constructors for Scott-encoded NatMaps
---- Those work like lists, where `Yep` constructors mean
---- there is a number on that index, `Nah` constructors
---- mean there isn't, and `End` ends the list.
---- Haskell: `data NatMap = Yep NatMap | Nah NatMap | End`
Yep natMap = (yep nah end -> (yep natMap))
Nah natMap = (yep nah end -> (nah natMap))
End        = (yep nah end -> end)

---- insert :: Nat (Church) -> NatMap (Scott) -> NatMap (Scott)
---- Inserts a Church-encoded Nat into a Scott-encoded NatMap.
insert nat natMap    = (nat succ zero natMap)
    succ pred natMap = (natMap yep? nah? end?)
        yep? natMap  = (Yep (pred natMap))
        nah? natMap  = (Nah (pred natMap))
        end?         = (Nah (pred natMap))
    zero natMap      = (natMap Yep Yep (Yep End))

---- toList :: NatMap (Scott) -> List Nat (Church)
---- Converts a Scott-Encoded NatMap to a Church-encoded List
toList natMap        = (go go natMap 0)
    go go natMap nat = (natMap yep? nah? end?)
        yep? natMap  = (Cons nat (go go natMap (Succ nat)))
        nah? natMap  = (go go natMap (Succ nat))
        end?         = Nil

---- sort :: List Nat (Church) -> List Nat (Church)
---- Sorts a Church-encoded list of Nats in ascending order.
sort nats = (toList (nats insert End))

-- Test
main = (sort [1,4,5,2,3])

Here is the bruijn-indexed normal form of a slightly altered version of the sort above, which must receive (x -> (x x)) as the first argument in order to work (otherwise it doesn't have a normal form):

λλ(((1 λλλ(((1 λλλ((1 3) (((((5 5) 2) λλ(1 ((5 1) 0))) 1) 0)))
λ(((3 3) 0) λλ(1 ((3 1) 0)))) λλ0)) ((0 λλ(((1 λλ(((0 λλλλ(2 (
5 3))) λλλλ(1 (5 3))) λλλ(1 (4 3)))) λ(((0 λλλλ(2 3)) λλλλ(2 3
)) λλλ(2 λλλ0))) 0)) λλλ0)) λλ0)

Pretty simple in retrospect.


Efficient (non-crypto-grade?) pseudorandom permutations with arbitrary domain size

unbalanced numeric Feistel (page 10)

swap-or-not

FastPRP

Those are all cryptographically strong; I'm not aware of

any way to get better performance by sacrificing that.


Busy Beaver Equivalent for the Untyped Lambda Calculus

Sequence https://oeis.org/A333479 in the On-Line Encyclopedia of Integer Sequences mostly answers your question. The question of shortest term for which lack of a normal form cannot be proven in ZFC remains open, but one candidate is the 213 bit Laver program presented in https://codegolf.stackexchange.com/questions/79620/laver-table-computations-and-an-algorithm-that-is-not-known-to-terminate-in-zfc


Algorithms for factorization using the decision version

All of the following algorithms either find a complete factor or a complete non-trivial factorization:

Trial division.
Pollard rho.
Pollard $p-1$ and its variants, including the elliptic curve method (ECM).
Shanks' SQUFOF.
Quadratic sieve (QS).
Number field sieve (NFS).

As far as I understand this list includes all algorithms actually used to factor integers in real life.

Finding just one bit of a factor sounds very unnatural to me, and I can't imagine an algorithm which can find one bit without finding all bits. (Even the SAT algorithm for factorization will find all bits at once.)


Humanifying computer-generated or computer assisted proofs

You are probably thinking of Gower's work with Ganesalingam, based on the latter's MSc dissertation (1). Gowers blogged about this in (2) and other places, and they've written a paper on the subject (3).

There is other work in that direction, for example from the interactive proof assistant community. The most well-known example here might be the Isar language (4). This is quite an active area of research, see e.g. (5). I know that this is also pursued by more linguistics oriented researchers, but I don't have references handy.

M. Ganesalingam, A Language for Mathematics.
W. T. Gowers, An experiment concerning mathematical writing.
M. Ganesalingam, W. T. Gowers, A fully automatic problem solver with human-style output.
M. Wenzel, Isabelle/Isar - a versatile environment for human-readable formal proof documents.
F. Wiedijk, A Synthesis Of The Procedural And Declarative Styles Of Interactive Theorem Proving.


Intuitively, the situation is you'd like some deterministic extractor $E: \{0,1\}^n \rightarrow \{0,1\}$ that can take in $n$ bits sampled from a weak source and output one bit with probability close to $1/2$, say it outputs 0 with probability $1/2 \pm \epsilon$ and 1 with $1/2\pm\epsilon$.

Here's a weak argument that at the very least, such extractors $E$ can't exist if we don't put any restrictions on the input distribution other than it has 'enough' min-entropy. Suppose $E$ is such a potential extractor. By flipping the output if necessary, we may assume without loss of generality that $|E^{-1}(0)|\ge|E^{-1}(1)|$; that is, $E^{-1}(0)$ is a set of $n$-bit strings of size at least $2^{n}/2$. Thus a random variable that samples uniformly from $E^{-1}(0)$ will have min-entropy at least $n - 1$, but the extractor will never give you any 'random' output other than 0.

Of course, if we tighten the restrictions on the input distribution (say, we assume all $n$ bits are IID) then we do have deterministic extractors that work. But as problem 6.6 in Salil Vadhan's survey of pseudorandomness shows, even weakening the IID assumption a little bit will cause deterministic extractors to fail, by a slight generalization of the same argument as I made above.


Alternatives to Normalization by Evaluation

NbE really has 2 goals:

As an evaluation mechanism for $\lambda$-terms. In this regard there are many many alternatives, basically any interpreter, virtual machine or compiler is a possible approach. NbE is just a way to get the host language to do the compilation for you!

As a proof technique to show the decidability of convertability for typed lambda calculi. E.g. it is decidable to prove $t =_{\beta\eta} u$ if $t$ and $u$ are simply typed terms of the same type. The obvious alternative is: proving that $\beta\eta$-reduction is strongly normalizing and confluent. It's not clear whether you're lumping this in with NbE, because they (usually) both use logical relations at their core. Certainly there are systems for which SN does not hold, but for which we can carry out NbE though.


Impredicativity + large eliminations (with no excluded middle) in Coq

No: strong elimination of large inductive types (SELIT) is itself inconsistent because it breaks the layering of universes by trivially allowing you to smuggle a large value in a Prop box and take it back out unscathed.
In Is Impredicativity Implicitly Implicit? I proposed a restriction on SELIT which is a bit more permissive than Coq's while still enjoying consistency (I still don't have a proof for it, tho I believe I'm almost there ;-)


Reference Request: Application of Block Designs to Software Testing

Suppose you have some software which includes a list of n variables s1,s2,...,sn and suppose each of these variables are able to take on a range of values.  Now suppose you want to test the program for 2-way interactions, that is, you want to test the program runs correctly for every pair of variables si and sj and every possible value that these variables can take.

To do this by a brute-force -- by processing each pair i and j one-by-one, then testing each allowable value of si and sj (while picking the others arbitrarily) -- would require testing a enormous number of cases.

But, we can test for several 2-way interactions in a single test.  For example, if we have three variables s1, s2 and s3, and we test when s1=1, s2=2 and s3=0, then we have tested three possible 2-way interactions simultaneously.

We can design a test-suite for the program based on a covering array -- the columns represent the variables and the rows represent the specific test to be performed (so fewer rows is better).  In a strength 2 covering array, within any two columns i and j, there exists every possible pair of the variables si and sj.  There are higher strength covering arrays which can test for t-way interactions (but usually interactions are a result of only a few components).

Sets of mutually orthogonal Latin squares (and various other block designs) form particularly efficient covering arrays.


Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?

The scaled down version of $\mathsf{PH}$ versus $\mathsf{PP}$ is $\mathsf{AC}^0$ versus $MAJ \circ \mathsf{AC}^0$, and we know that for the latter there is an exponential separation. Of course, this separation doesn't propagate exponentially up, but you could take this as philosophical evidence that $\mathsf{PH}$ is different enough from $\mathsf{PP}$ that perhaps that remains true even if $\mathsf{P} = \mathsf{NP} = \mathsf{PH}$. (In fact, following this line of reasoning, I'd guess you can build an oracle relative to which $\mathsf{P} = \mathsf{NP} \neq \mathsf{PP}$.)


How to sample from a distribution with submodular weights

There is a paper by Gotovos, Hassani, and Krause (NIPS, 2015) titled "Sampling from Probabilistic Submodular Models" which describes a MCMC method based on Gibbs sampling. They show that the mixing time $t_{\text{mix}}(\epsilon)$ is bounded above by
$$ t_{\text{mix}}(\epsilon) \leq 2 n^2 \exp(\zeta_f) \log \left( \frac{1}{\epsilon p_\min} \right) $$
where $p_\min = \min_{S} p(S)$ and the quantity $\zeta_f$ is
$$\zeta_f =  \max_{A, B \subset V} \left| f(A) + f(B) - f(A \cup B) - f(A \cap B) \right| $$
which I don't know of appearing elsewhere in the literature. There is another paper by Rebeschini and Karbasi (JMLR, 2015) titled "Fast Mixing for Discrete Point Processes" which proposes a different Gibbs sampler whose mixing time is bounded using the so-called "discrete hessian" which I also haven't seen used elsewhere in the literature.

It seems that submodularity of $f$ alone isn't enough to get fast mixing times for MCMC methods. Current methods certainly need to consider other quantities of $f$ to ensure fast mixing times.


What class of languages is recognized by finite-state automata with $k$ heads?

This model is one of the standard models in automata theory and it has been examined by some researchers.

The references given in the first comment are very good starting points.

When the head is two-way, the classes of languages recognized by such models are identical to logarithmic-space classes. However, when the head is one-way, then, up to my knowledge, we do not have a similar exact characterization, but, we have certain incomparable results and some hierarchies based on the number of heads.

If you are interested in, I recommend you to check alternating, probabilistic, and quantum versions of multi-head automata, as well. Such models can be quite interesting even when using a single head, as the computation is split in into different paths, and then, in each path, the head may access different part of the inputs.

Some generic references:

Turing Machines with Sublogarithmic Space - https://books.google.lv/books?id=vNPuNOo9BUYC

Alternation

Viliam Geffert - https://dblp.uni-trier.de/pers/hd/g/Geffert:Viliam

Probabilistic computation

Ioan I. Macarie - https://dblp.org/pers/hd/m/Macarie:Ioan_I=

Probabilistic and quantum computation

Rusins Freivalds - https://dblp.uni-trier.de/pers/hd/f/Freivalds:Rusins
Abuzer Yakaryilmaz - https://dblp.uni-trier.de/pers/hd/y/Yakaryilmaz:Abuzer

Related models: multi-counter automata and automata using pebble.


Do there exist x such that K(xx)<K(x), where K is Kolmogorov complextity.

I am no expert on Kolmogorov complexity, but I think that such x can be constructed for every complexity function K as follows.  Since 1, 11, 1111, 11111111, …, 12n, … is an encoding of a natural number n, K(12n) cannot be o(log n).  However, when n=2m, obviously K(12n)=K(122m)=O(log m)=O(log log n).  Therefore the sequence K(1), K(11), K(1111), K(11111111), …, K(12n), … cannot be weakly monotonically increasing, which means that there exists a string x in the form 12n such that K(xx) < K(x).


Minimum communication cost for zero knowledge proofs of three colorability

So here is the right paper for my purposes:

Joe Kilian, "A note on efficient zero-knowledge proofs and arguments." http://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf

To get the strongest result, we need to accept zero knowledge arguments rather than proofs (computationally bounded prover); these are what I am interested in but did not know the terminology.

Assuming sufficient cryptographic assumptions, the paper gives zero knowledge arguments with total communication $O(b \log^c n \log (1/p))$ for $c = O(1)$.

This result is tightened to $O(1)$ rounds by Ishai et al., "On Efficient Zero-Knowledge PCPs", http://www.cs.virginia.edu/~mohammad/files/papers/13%20ZKPCPs.pdf.


Grover's search algorithm for 3 coloring

You don't need to keep track of all $3$ colours for your colouring, because we know how to two colour quickly.

Let the colours be $\{0,1,2\}$. Have an oracle $f: \{0,1\}^{|V|} \rightarrow \{0,1\}$ that you interpret as selection a subset $C_0 \subseteq V$ that you will pretend is $0$-coloured. Your circuit then (1) in polynomial time checks if $V - C_0$ is two-colourable with $\{1,2\}$, and (2) in polynomial time checks if $C_0$ is an independent set. If both are true then it returns $1$, else $0$. Now you are searching over only $2^n$ database entries for a marked element and so have the runtime you wanted.


Yes, cancellations are needed and there are lower bounds for monotone and for non-commutative models where cancellations are impossible.  See discussion in Monotone arithmetic circuits.  A survey of aritmetic circuit complexity can be found in http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf


Major advance for measurement based quantum computing?

A paper which makes strong claims ought to be sufficiently clearly written for readers to  check those claims. I don't find the current (http://arxiv.org/pdf/1211.3405v2.pdf) version of this paper expresses its results clearly enough to make a concrete assessment.

But if it were, I'd want to check:

a) whether the quantum part of the algorithm solely consists of Pauli measurements on a cluster state.

Such a measurement-based quantum computation can be simulated using polytime classical processing (due to the Gottesman-Knill theorem), and hence one would have a solely classical superfast search algorithm.

b) whether the oracle used might be of a different type to the oracle in Grover's algorithm.

The oracle in Grover's algorithm has the property that it must recognise the target string, but, crucially, it does not need to know this string in advance, or be able to calculate that target string in polytime (see Nielsen and Chuang chapter 6 for a discussion of this).

Unless P=NP, an oracle which knows the target string needs to be more powerful than one which merely recognises it (consider a search for a solution of an NP-hard problem). I'd want to check whether the oracle here is of the "recognising" or "knowing" kind. If it is the second, then the extra computational power in the oracle might, on its own, explain any exponential improvement reported.


On succinct $EXP$ and $NEXP$ complete problems?

The description of a succinct problem has very little to do with graphs, per se. Given a language $L \subseteq \Sigma^*$, we can define its succinct version as the set of Boolean circuits $C$ such that, if $C$ has $m$ inputs, then the string $s$ of length $2^m$ which is the concatenation of $C(0^m) C(0^{m-1} 1) C(0^{m-2} 10) \dotsb C(1^m)$ is in $L$.
You can make such a version, though I haven't seen it studied before. The smallest known upper bound on the deterministic time complexity of $\mathsf{NEXP}$ is $\mathsf{EEXP} = \mathsf{DTIME}(2^{2^{n^{O(1)}}})$, so you could conjecture that a standard $\mathsf{NEXP}$-complete problem is not in significantly sub-doubly-exponential time.


Decompose a complete graph into smaller cliques

If you want to decompose a complete graph into triangles then look for "steiner triple system" (STS). You will find some there: http://steinertriples.fr/

If you want to decompose a complete graph into cliques of size p, the generalization of STS that you want are "Balanced Incomplete Block Designs". If you want to know more about that, try to find the book from Douglas Stinson named "Combinatorial designs: construction and analysis".

Finally, if you want to build some BIBD, we've been sweating a lot over combinatorial designs code in Sage recently. It can build a (v,k,1)-BIBD whenever one exists for k<=5, and as for larger values of k, well, it depends.

Either way, if you find a combinatorial design that it cannot build come tell us about it ! :-P

Nathann


Example of pairwise independent random process with expected max load $\sqrt{n}$

Here's how to do it.

First, choose a random $k$ between 1 and $n$ to be the "crowded bin".
Next, choose a random permutation $\pi$ of $1,2,\ldots, n-1$.

Now, for $1 \leq i \leq n-1$,
$$ \mbox{put ball } i \mbox{ into bin }
\begin{cases} k \ \ \ \ \ \ \ \ \ \ \ \ \mbox{with probability }\ \frac{1}{\sqrt{n}}, \\
k + \pi(i) \mbox{ with probability }1 - \frac{1}{\sqrt{n}},
\end{cases}$$
where the sum is taken mod $n$.

Put ball $n$ into a random bin.

Consider balls $i,j$ where $1 \leq i < j \leq n-1$. The bins these two balls fall into are independent. They both go into the crowded bin with probability $\frac{1}{n}$, and the crowded bin is equally likely to be any of the $n$ bins. And if they don't both go into the crowded bin, by symmetry they are equally likely to be in any two different bins. Thus, the bins these two balls are placed into are independent.

Since ball $n$ is placed into a random bin, it is independent of the other balls.

The expected max load here is essentially the expected number of balls in the crowded bin, which is
$$\frac{n-1}{\sqrt{n}}+\frac{1}{n} = \sqrt{n} + o(1).$$


I've studied the problem and I found the best known algorithms for TSP.
$n$ is the number of vertices, $M$ is the maximal edge weight.
All bounds are given up to a polynomial factor of the input size ($poly(n, \log M)$).
We denote Asymmetric TSP by ATSP.
1. Exact Algorithms for TSP
1.1. General ATSP
$M2^{n-\Omega(\sqrt{n/\log (Mn)})}$ time and $exp$-space (Björklund).
$2^n$ time and $2^n$ space (Bellman; Held, Karp).
$4^n n^{\log n}$ time and $poly$-space (Gurevich, Shelah; Björklund, Husfeldt).
$2^{2n-t} n^{\log(n-t)}$ time and $2^t$ space for $t=n,n/2,n/4,\ldots$ (Koivisto, Parviainen).
$O^*(T^n)$ time and $O^*(S^n)$ space for any $\sqrt2<S<2$ with $TS<4$ (Koivisto, Parviainen).
$2^n\times M$ time and poly-space (Lokshtanov, Nederlof).
$2^n\times M$ time and space $M$ (Kohn, Gottlieb, Kohn; Karp; Bax, Franklin).
Even for Metric TSP nothing better is known than algorithms above. It is a big challenge to develop $2^n$-time algorithm for TSP with polynomial space (see Open Problem 2.2.b, Woeginger).
1.2. Special Cases of TSP
$1.657^n\times M$ time and exponentially small probability of error(Björklund) for Undirected TSP.
$(2-\epsilon)^n$ and exponential space for TSP in graphs with bounded average degree, $\epsilon$ depends only on degree of graph (Cygan, Pilipczuk; Björklund, Kaski, Koutis).
$(2-\epsilon)^n$ and $poly$-space for TSP in graphs with bounded maximal degree and bounded integer weights, $\epsilon$ depends only on degree of graph (Björklund, Husfeldt, Kaski, Koivisto).
$1.251^n$ and $poly$-space for TSP in cubic graphs (Iwama, Nakashima).
$1.890^n$ and $poly$-space for TSP in graphs of degree $4$ (Eppstein).
$1.733^n$ and exponential space for TSP in graphs of degree $4$ (Gebauer).
$1.657^n$ time and $poly$-space for Undirected Hamiltomian Cycle (Björklund).
$(2-\epsilon)^n$ and exponential space for TSP in graphs with at most $d^n$ Hamiltonian cycles (for any constant $d$) (Björklund, Kaski, Koutis).
2. Approximation Algorithms for TSP
2.1. General TSP
Cannot be approximated within any polynomial time computable function unless P=NP (Sahni, Gonzalez).
2.2. Metric TSP
$3 \over 2$-approximation (Christofides).
Cannot be approximated with a ratio better than $123\over 122$ unless P=NP (Karpinski, Lampis, Schmied).
2.3. Graphic TSP
$7\over5$-approximation (Sebo, Vygen).
2.4. (1,2)-TSP
MAX-SNP hard (Papadimitriou, Yannakakis).
$8 \over 7$-approximation (Berman, Karpinski).
2.5. TSP in Metrics with Bounded Dimension
PTAS for TSP in a fixed-dimensional Euclidean space (Arora; Mitchell).
TSP is APX-hard in a $\log{n}$-dimensional Euclidean space (Trevisan).
PTAS for TSP in metrics with bounded doubling dimension (Bartal, Gottlieb, Krauthgamer).
2.6. ATSP with Directed Triangle Inequality
$O(1)$-approximation (Svensson, Tarnawski, Végh)
Cannot be approximated with a ratio better than $75\over 74$ unless P=NP (Karpinski, Lampis, Schmied).
2.7. TSP in Graphs with Forbidden Minors
Linear time PTAS (Klein) for TSP in Planar Graphs.
PTAS for minor-free graphs (Demaine, Hajiaghayi, Kawarabayashi).
$22\frac{1}{2}$-approximation for ATSP in planar graphs (Gharan, Saberi).
$O(\frac{\log g}{\log\log g})$-approximation for ATSP in genus-$g$ graphs (Erickson, Sidiropoulos).
2.8. MAX-TSP
$7\over9$-approximation for MAX-TSP (Paluch, Mucha, Madry).
$7\over8$-approximation for MAX-Metric-TSP (Kowalik, Mucha).
$3\over4$-approximation for MAX-ATSP (Paluch).
$35\over44$-approximation for MAX-Metric-ATSP (Kowalik, Mucha).
2.9. Exponential-Time Approximations
It is possible to compute $(1+\epsilon)$-approximation for MIN-Metric-TSP in time $2^{(1-\epsilon/2)n}$ with exponential space
for any $\epsilon\le \frac{2}{5}$, or in time $4^{(1-\epsilon/2)n} n^{\log n}$ with polynomial space for any $\epsilon \leq \frac{2}{3}$ (Boria, Bourgeois, Escoffier, Paschos).
I would be grateful for any additions and suggestions.


Can we have more than one Deterministic Finite Automata diagrams for a set of strings?

Can we have more than one Deterministic Finite Automata (DFA) diagrams for a set of strings?

Of course!

There's also an algorithm to minimize a deterministic finite automata into a minimal deterministic finite automata. The existence of such algorithm is a proof that for most, if not all, sets of strings, many DFAs can be defined.


From Papadimitriou's paper "On total functions, existence, theorems and computational complexity":

Nondeterministic multivalued functions with values that
are polynomially verifiable and guranteed to exist form an
interesting class (called $TFNP$) between P and NP ...

.... It is quite interesting, in view of Theorem 2.1,
that in some cases of problems in $TFNP$, if together with the input
we are also given one of the solutions
that are guaranteed to exist, then the problem indeed becomes NP-complete ...

For example the TRICHROMATIC TRIANGLE problem is in $TFNP$, but the SECOND TRICHROMATIC TRIANGLE is $NPC$ (the paper contains a sketch of the proof).


Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard?

The general (non-bernoulli) problem is #P hard, via a reduction from #Knapsack.

#Knapsack is the problem of counting the solutions to an instance of the knapsack problem. This problem is known to be #P complete. An equivalent way to think of the #Knapsack problem is the following: You are given a set of integers $a_1,\ldots,a_n$ and a threshold $t$. Let $x_i$ be a random variable which is either $0$ or $a_i$ with equal probability, and assume those random variables are independent. Compute the probability that $\sum_i x_i \leq t$.

It is not too hard to see that the #Knapsack problem could be equivalently defined as the problem of computing the probability that $\sum_i x_i \geq t$ (simply flip the sign of all the integers and add a large constant). Therefore, had I stated my problem with an arbitrary probability $p$ rather than $0.5$, the problem stated in the question can be interpreted as the decision version of #knapsack. A reduction of #knapsack to its decision version via binary search would then complete the #P hardness proof.

The way I defined the problem, however, fixed a particular threshold 0.5. It's not too hard to see that this doesn't make the problem easier. We can reduce the decision problem with probability $p\leq 0.5$ to the problem with $p=0.5$ by simply adding an additional random variable $x_0$ which is equal to the threshold $t$ with probability $\frac{0.5-p}{1-p}$ and $0$ the rest of the time. For $p > 0.5$, a similar reductions lets $x_0$ be $-M$ for a sufficiently large $M$ with probability $\frac{p-0.5}{p}$ and $0$ otherwise; if you don't like negative numbers, simply shift all random variables and the threshold $t$ up by a suitable constant.


Your question is essentially covered by Cor 9.5 in [1]
which implies that as long as the ratio of self-loops to the original degree is bounded above and below, the mixing time of this modified walk is equivalent (up to constants) to the mixing time of the lazy walk on $G_1$.
[1]
Peres, Yuval, and Perla Sousi. "Mixing times are hitting times of large sets." Journal of Theoretical Probability 28, no. 2 (2015): 488-519.
https://www.dpmms.cam.ac.uk/~ps422/mix-hit.pdf


Choosing random permutations in "strict" polynomial time

I believe the answer is that it is possible in polynomial time as follows:

Each permutation of $N$ can be expressed as a function $f(x)$ which maps an input index to the corresponding output index. Each such function can be expressed as a string $f(1) + f(2) + f(3) + ... + f(N)$, where $+$ is the concatentaion operator. Thus there is a natural lexicographic ordering on the permutations. The idea is to pick the permutations in lexicographic order.

The probability $p_{i,1}$ that permutation $P_i$ will be the first permutation (in lexicographic order) from a set of $M$ permutations of $N$ elements chosen uniformly at random will be $$p_{i,1} = \frac{\binom{N-i}{M-1}}{\binom{N}{M}}.$$

By making a random choice from this probability distribution we determine the first permutation in our set. Let's assume that this permutation is indexed by $x_1$. We now need to choose the permutation which is second lowest in lexicographic order. Clearly, this is the same problem as before, but now we need to choose according to the probability distribution $$p_{i,2} = \frac{\binom{N-x_1-i}{M-2}}{\binom{N-x_1}{M-1}}.$$

For an arbitrary ranking $k$ the probability distribution will be given by $$p_{i,k} = \frac{\binom{N-i-\sum_{j=1}^{k-1} x_j}{M-k}}{\binom{N-\sum_{j=1}^{k-1}x_j}{M-k+1}}.$$

This process is repeated until we have chosen all $M$ permutations. As there is no possibility of collision, the process terminates after exactly $M$ such choices, and hence is an exact polynomial time computation assuming the random choice can be made in time $\mbox{poly}(N)$.

UPDATE: Kaveh points out in the comments below that I have not shown how to find the $i$th permutation in time polynomial in $n$, so here is one way.

We can turn an permutation into an integer by taking $I_P = \sum_{k=0}^{n-1} \frac{n!}{(n-i)!} (y_k-1)$. Here $y_k$ is defined as follows: Let $S_0$ be the set of integers from 1 to $N$, and take $S_k = S_0 / \{f(x)\}_{x=1}^k$. Then $y_k$ is the lexicographic index of $f(k+1)$ in $S_k$. Note that $y_k$ is always an integer between 1 and $n-k$. Thus you obtain a unique integer between 0 and $n!-1$ for every permutation. To reverst this and find the $i$th permutation is trivial, since $y_0 = (I_P \mbox{ mod } n)+1$, $y_1 = ((I_P-y_0)/n \mbox{ mod } n)+1$ etc., and once all $y_k$ have been calculated, $f(x)$ can be calculated by taking $f(1) = y_0$, which allows you to calculate $S_1$, which in turn gives you $f(2)$, etc.

Thus you have a polynomial time algorithm for converting a permutation of $n$ items into a unique integer between $0$ and $n!-1$ and back.

This answer makes an assumption that it is possible to generate probabilities of the necessary form, which is not necessarily granted in the question. See the answer for Peter Shor for why this can be a problem.


Algorithms for creating a directed network with a given 3-node motifs distribution

As I understand, you are interested in an approximate solution. I have two heuristic ideas, maybe they can serve as a starting point.

However, if you want more (e.g. randomness in the Haar-measure sense or fixing other properties (graph diameter, spectrum, number of connected components, ...)) they are not sufficient.

Rewiring

Especially when you want to have distributions of network motifs close to a 'random' one.

Generate a graph with desired distribution of in-degrees and out-degrees.
For each pair of nodes $(x,y)$ calculate the number of each motif $m_i(x,y)$
Now, in each step:

Randomly draw two edges.
Perform rewiring (i.e. $(a\rightarrow b, c \rightarrow d) \mapsto (a\rightarrow d, c \rightarrow b) $) if it is possible and if it results in distribution of motifs closer to the desired one (e.g. in the sense of the Kullback-Leibler divergence or perhaps the Euclidian distance). Modify $4\times13$ affected $m_i(x,y)$.

As variance is of order $\sqrt{n}$, each rewiring takes a fixed time, you need roughly $n^3/\sqrt{n}$ steps, so I guess that it should scale as $O(n^{2.5})$.

Addition

Alternatively, you can try to add edges to an empty graph in such way it produces the desired distribution. Also, one need to hold $m_i(x,y)$.

For each step one randomly draws a pair of nodes and put an edge if it results in a desired distribution at this step (perhaps with some randomness).

Then the time cost is $O(n^2)$ (or rather $O(\#\text{edges})$ ), so better by $\sqrt{n}$ than the rewiring.

The tricky part is to calculate the desired distribution at each step (or rather - at each edge count). For example, even if one wants to have only $(\bullet\leftrightarrows \bullet\quad \bullet)$ and $(\bullet\quad \bullet\quad \bullet)$ 3-motifs, then when starting one needs to create mostly $(\bullet\rightarrow \bullet\quad \bullet)$ 3-motifs.

I would guess that the desired distribution at a given edge count $E$ is the one resulting from the final motif distribution with removed edges with the probability $1-\frac{E}{E_{final}}$.


For all $a≥0$ and $ε>0$, $\mathrm{DTIME}(O(n \log^{a} n))$ is strictly contained in $\mathrm{DTIME}(O(n \log^{a+ε} n))$; see my answer here.

To recap, the logarithmic overhead comes from tape reduction (and is not needed if the number of tapes is fixed and is at least two).  There is a nonconstructive argument that converts the logarithmic overhead into time hierarchy at $\log^{ε} \mathrm{time}$ multiplicative precision for well-behaved (time-constructible and in a certain sense continuous) time bounds.

A constructive proof of the strict inclusion of $\mathrm{DTIME}(O(n))$ in $\mathrm{DTIME}(O(n \log n))$ remains (to my knowledge) an open problem.


What's the complexity to check whether a matrix is Diagonalizable?

You can do this in uniform NC, see:

G. Villard. Fast parallel algorithms for matrix reduction to canonical forms. AAECC 8:511-537, 1997. http://link.springer.com/article/10.1007%2Fs002000050089


http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/15-amortize.pdf specifically for amortization, and http://theory.cs.uiuc.edu/~jeffe/teaching/algorithms/ generally


Is the proceedings of WG 2015 published?

I am an author of a paper that is to appear in the WG 2015 proceedings. As far as I know, they have not appeared yet, which is indeed quite strange.

Early February I emailed the chair (Ernst Mayr) to ask for the page numbers of my paper; they were not yet known at that time. The chair informed me that he encountered a big technical problem when producing the files for the proceedings, but that the problems were cleared up and that he was in almost done compiling. If you want up to date info, I suggest emailing Ernst Mayr.

PS: The LNCS volume number will be LNCS 9224.


One can get a $n \choose n/2$ lower bound by considering the $n$ variable formula that for every pair $x$, $y$, of variables contains the clauses $(x \vee y)$ and $(\neg x \vee \neg y)$. The total number of clauses is $2 \cdot {n \choose 2}$. Every assignment will satisfy one of the two clauses on $x$ and $y$. Both clauses are satisfied exactly when $x$ and $y$ get different values. Hence, if $i$ variables are set to true the total number of satisfied clauses is
$${n \choose 2} + i \cdot (n-i).$$
This is maximized when $i = n/2$. Thus, for even $n$, every assignment that sets exactly $n/2$ variables to true is a local maxima. The total number of such assignments is $n \choose n/2$, which is $\Theta(\frac{2^n}{\sqrt{n}})$.


It sounds like this class would be exactly MA.  The witness could be the results of pre-processing (which is of polynomial size).  The probabilistic verification procedure would then be to simulate the protocol, including the multiple provers (who are polynomial-time given the results of pre-processing).

Russell Impagliazzo


New algorithm for Discrete log and its implications for Quantum computing

Well, one crucial observation is that the new algorithm apparently only works for groups of the form $Z_{p^k}$ where $p$ is small --- it doesn't give a speedup for groups of the form $Z_p$.  The latter is the much more common setting that people talk about, both for cryptography and for Shor's algorithm, and the new algorithm doesn't threaten the quantum speedup there.  On the other hand, yes, unless I'm mistaken it does make the speedup much smaller in the $Z_{p^k}$ case.


Why do we need formal semantics for predicate logic?

A minor comment, and a more serious answer.

First, it doesn't make sense to declare a natural deduction system complete by fiat. Natural deduction is interesting precisely because it has a natural internal notion of consistency and/or completeness -- namely, cut-elimination. This is a fantastic theorem, and IMO fully justifies attempts to give purely proof-theoretic semantics (and by the CH correspondence, it likewise justifies the use of operational methods in programming language semantics). But this is interesting precisely because it offers a more refined notion of getting the logic right than consistency. Taking the proof theoretic road means you'll have to do more work, but in exchange you get stronger results.

However, it happens that sometimes the logic per se takes a secondary role. We may begin with a (family of) models, and then look for ways of talking syntactically about them, using a logic. The soundness and completeness of a logic with respect to a family of models indicates that the logic really does capture everything both interesting and true you can say about the class of models. A concrete example of when models are more interesting than the logical theories occurs in program analysis and model checking. There, the usual thing to do is to take your model to be the execution of a program, and the logic to be some fragment of temporal logic. The propositions you can say in these languages are (deliberately) not terribly exciting -- e.g., null pointer dereferences never occur -- but it's the fact that it applies to actual program runs that gives it interest.


It is not even known whether NC = P, but P-complete problems seem to be inherently hard to parallelize.  These include Linear Programming and Horn-SAT.  (In contrast, problems in NC seem reasonably easy to parallelize.)

See question Problems between NC and P: How many have been resolved from this list? for reference material (including links to a classic textbook that is now available for free download), and further discussion about problems that are in P but not known to be parallelizable.

See question Generalized Ladner's Theorem for the structure of the complexity classes between NC and P.  Briefly, if they differ then there are infinitely many complexity classes strictly between NC and P.

See question NC = P consequences? for a nice demonstration by Ryan Williams that it is possible to amplify collapses in the hierarchy of complexity classes within P into perhaps more unlikely collapses like PSPACE = EXP.

It is worth pointing out that one consequence of Horn-SAT being P-complete, and the links above, is that it does not seem possible to parallelize general SQL queries in databases, unless we can also rewrite any large-scale computation to use only a reasonable amount of storage.  This is a puzzling discrepancy -- I think it is quite uncontroversial to state there are limits on compression, but I often see articles which seem built on the assumption that it is possible to parallelize any database query.


Programming languages for efficient computation

One language attempting to express only polynomial time computations is the soft lambda calculus. It's type system is rooted in linear logic. A recent thesis addresses polynomial time calculi, and provides a good summary of recent developments based on this approach. Martin Hofmann has been working on the topic for quite some time. An older list of relevant papers can be found here; Many of his papers's continue in this direction.

Other work takes the approach of verifying that the program uses a certain amount of resources, using Dependent Types or Typed Assembly Language.

Yet other approaches are based on resource bounded formal calculi, such as variants of the ambient calculus.

These approaches have the property that well-typed programs satisfy some pre-specified resource bounds. The resource bound could be time or space, and generally can depend upon the size of the inputs.

Early work in this area is on strongly normalising calculi, meaning that all well-typed programs halt. System F, aka the polymorphic lambda calculus, is strongly normalising.  It has no fixed point operator, but is nonetheless quite expressive, though I don't think it is known what complexity class it corresponds to. By definition, any strongly normalising calculus expresses some class of terminating computations.

The programming language Charity is a quite expressive functional language that halts on all inputs. I don't know what complexity class it can expression, but the Ackermann function can be written in Charity.


So the question is pretty brief but very interesting. I suppose that the input is $n$ in unary, and $x$ and $y$ in binary (or we have problems, as pointed out by Kai's answer).

First of all, if you are interested in knowing $K(x,y)$ approximately, then you can just generate a few random DFA's and this will give you (whp) a good approximation. (I wonder if this complexity class has a name.)

Then knowing $K(x,y)$ precisely seems like a tough problem. As pointed out in the comments by a3_nm and Kaveh, the question is equivalent to determining the number of automata for which $x$ and $y$ go to the same state. I will denote the probability that they go to the same state by $p$.

Update: Some of the things I wrote here were not true, now I fixed them.

It is easy to see that $p \ge 1/n$. We have equality, if $x$ is all 0's and $y$ is all zero except for its last bit, which is a 1. Are there other cases? I don't know. If for example $x$ is the empty string and $y=00$, then $p= \frac{n+1}{(n-1)n}$.

To simplify the problem, I even started to think about what happens if $x$ and $y$ are unary. If both are at least $n$ and their difference is divisible by $n!$, then $p=1$. Is there a simple formula for the unary version?


Fast Finding Main Diagonal of Matrix Multiplication

Not unless $\omega = 2$. Take $B = \operatorname{id}$, $A = \begin{bmatrix}X & Y\end{bmatrix}$. You can extract $XY$ from $A^TBA$.

UPDATE: I missed the main diagonal part of the question. Even computing the main diagonal is as hard as matrix multiplication: denote $f(A, B) = \operatorname{tr}(A^TBA) = \sum_{i,j,k} a_{ij} b_{ik} a_{kj}$. The derivatives $\frac{\partial f(A, B)}{\partial a_{ij}}$ form the matrix $BA + A^TB$, and we can apply the Baur-Strassen theorem.


If you had an approximation algorithm for an APX-hard problem which for any $\epsilon, \delta >0$ runs in polynomial time and approximates the problem within a factor of $1+\epsilon$ with probability $1-\delta$, then $\mathsf{NP} \subseteq \mathsf{BPP}$.

The reasoning is very similar to Chandra's answer to another question. APX-hardness for a problem $P$ implies that there is a PTAS reduction from instances of MaxSAT to instances of $P$: for every $\epsilon$, approximating Max3SAT to within a factor of $1+\epsilon$ is polynomial-time reducible to approximating $P$ to within a factor of $1 + c(\epsilon)$. By the PCP theorem, there is a constant $\epsilon_0$ such that the promise problem of distinguishing between satisfiable 3SAT instances and instances where at most a $1-\epsilon_0$ fraction of the constraints can be satisfied is NP-hard (in fact $\epsilon_0$ can be taken arbitrarily close to $1/8$, which is tight). Call this NP-hard promise problem $\text{Gap3SAT}(1, 1-\epsilon_0)$. The PTAS reduction from Max3SAT to $P$ with small enough $\epsilon$ (i.e. $\epsilon < \frac{\epsilon_0}{1-\epsilon_0}$), together with the algorithm with "PAC guarantees", give a BPP algorithm for $\text{Gap3SAT}(1, 1-\epsilon_0)$, which implies a BPP algorithm for any problem in NP.


Efficient algorithm for computing equally distributed points in polytope?

This is an answer just to record a solution to the problem.

Given the polytope, I triangulate it without introducing new vertices. Then I generate for each simplex in the resulting simplicial complex many points in the interior with my second approach. Every coefficient vector will give distinct points because the vertices of the simplices are affinely independent. To implement this solution one can use Sage together with TOPCOM, for example.

Depending on the chosen triangulation, the dimension and and number of vertices this solution can actually be quite inefficient.


Base extension in residue number systems with low space

By a result of Chiu, Davida, and Litow [1], improved by Hesse, Allender, and Barrington [2], Chinese remainder representation base extension is computable in logarithmic space, and in fact in DLOGTIME-uniform $\mathrm{TC}^0$, when all the $p_i$ are “small” (i.e., given in unary). Since the effective size of the input is here $p^*+\sum_ip_i\le p^*+m\max_ip_i\le p^*+(\max_ip_i)^2$ (using the fact that the $p_i$ are distinct), this means it is computable in space
$$O\bigl(\max\{\log p^*,\log p_i:i=1,\dots,m\}\bigr).$$

References:

[1] A. Chiu, G. Davida, B. Litow, Division in logspace-uniform $\mathit{NC}^1$, RAIRO – Theoretical Informatics and Applications 35 (2001), no. 3, pp. 259–275.

[2] W. Hesse, E. Allender, D. Mix Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication, Journal of Computer and System Sciences 65 (2002), no. 4, pp. 695–716.


You can treat this as a directed graph problem, where the weights of all edges coming into a node are equal to that node's weight.

If the edges are weighted too, add the node's weight and the edge's weight together to find the incoming edge's weight in the directed graph.


Placing points far away from each other in simple polygon

This does not answer your (interesting) question, but it may be worth mentioning that
this variant (which does not use geodesic distance) has been studied:

Thomas Shermer, "Hiding people in polygons,"
Computing,
Volume 42, Numbers 2-3 (1989), 109-131 (Springer link):

  A hidden set is a set of points such that no two points in the set are visible to each other. A hidden guard set is a hidden set which is also a guard set. In this paper we consider the problem for finding hidden sets and hidden guard sets in and around polygons. In particular, we establish bounds on the maximum size of hidden sets, and show that the problem of finding a maximum hidden set is NP-hard.

To more directly address your question, perhaps this is the most natural interpretation for $m=1$:

Pollack, Sharir, Rote, "Computing the Geodesic Center of a Simple Polygon,"
Discrete Comput. Geom. 4:611-626 (1989):

  The geodesic center of a simple polygon is a point inside the polygon which minimizes the maximum internal distance to any point in the polygon. We present an algorithm which calculates the geodesic center of a simple polygon with $n$ vertices in time $O(n \log n)$.


Lower bounds on the size of CFGs for specific finite languages

A kind reviewer sent me a paper which proves exactly the same lower bound I do, in exactly the same way. The paper is

  K. Ellul, B. Krawetz, J. Shallit, M.-w. Wang, Regular expressions: new results and open problems, J. Autom. Lang. Comb. 10 (2005), 407–432.

The result is Theorem 30 in the paper.


What relations and differences are between formal semantics for linguistics and for programming languages?

This question is very open-ended and therefore difficult to answer, but I think the short answer is "yes", there is much common ground, the two areas have in fact benefited from interaction in the past, and they have much to gain from further interaction.
Two classical examples of this (respectively from the 1950s and '70s) are Lambek grammar and Montague grammar, which model different aspects of natural language using sequent calculus and lambda calculus (which have become cornerstones of programming language theory, with connections to category theory and type theory).
In relatively more recent history, personally I found Ken Shan's dissertation Linguistic side effects (2005) an inspiring exploration of the thesis that natural languages and programming languages have more common ground than differences.  To quote a bit from the introduction:

This dissertation is about computational linguistics, in two senses. First,we apply insights from computer science, especially programming-language semantics, to the science of natural languages. Second, we apply insights from linguistics, especially natural-language semantics, to the engineering of programming languages. The phrase “computational linguistics” has a popular third sense, which is natural-language processing: teaching computers to listen to, speak, read, and write natural language. That is not our aim, even though the research described here indirectly helps it—by enhancing our understanding of natural and programming languages.

Chris Barker has also written extensively about the concept of continuation from programming languages semantics and how it may be used to illuminate the nature of quantification in natural language, and the two have recently collaborated on a book which explores this topic further.


Zero knowledge proof for value of a hash function

In the rump session of Crypto 98, Hal Finney provided a talk which might be of your interest. The title is "A zero-knowledge proof of possession of a pre-image of a SHA-1 hash." I have not found any transcripts., but the video is available on both YouTube and Google Videos. (the videos are no longer available; see the comments below.) The video is now available from my Google Drive.


There are various examples in which a semidefinite programming relaxation allows an approximation that is superior to known integrality gaps for linear programming relaxations.

For example, the standard linear programming relaxation of max cut has an integrality gap of 1/2, and this is true even for much more sophisticated linear programming relaxations (c.f. de la Vega-Kenyon and Schoenebeck-Trevisan-Tulsiani), but the Goemans-Williamson SDP algorithm has approximation .878...

The Leighton-Rao linear programming relaxation of sparsest cut has an integrality gap $\Omega(\log n)$, but the Arora-Rao-Vazirani SDP algorithm has approximation $O(\sqrt{\log n})$.

Perhaps less well known, Karloff and Zwick shows that using SDP one can approximate Max 3SAT, in the version in which clauses can have 1, 2 or 3 literals, within 7/8, while Goemans and Williamson had studied a linear programming relaxation that they used to prove a 3/4 approximation (Yannakakis had given 3/4 approximation earlier by other methods), and the Goemans-Williamson LP relaxation of Max 3SAT is easily seen to have integrality gap 3/4.


Is there a pair of different lambda terms in the normal form that behave identically when applied to any input?

The result you are looking for is Böhm's theorem. The equivalence described by "behaves the same way on all inputs" is the same as the equivalence given by normal forms, but only if you treat eta-equivalent normal forms (λx.Ix and I) as equivalent. You could disallow the former as a normal forms (eta-short) and then you'd have the syntactic condition you want by Böhm's theorem, if I'm not mistaken.


How would you define a set of 'fundamental operations' over an object?

There is no standard notion of "fundamentalness".  It's not clear that what you are looking for is meaningful or makes any sense.  What is "fundamental" is a matter of perspective; I don't see any reason to privilege insert as more fundamental than splice, or vice versa.

So, if you need a concept of "fundamental" for some reason, you'll need to define for yourself what you mean by "fundamental".  If you're going to head that path, I would suggest that you start by asking yourself, "Why do you care?"

Personally, I suspect an XY problem.  I suspect you're asking the wrong question, and you should go back and ask yourself why you want to know and what you will do with the answer -- and that might help you identify a more sensible question or a more pragmatic path to achieving your real goals.


Semiring examples from formal language theory

There are plenty of semirings related to language theory. First of all, the Boolean semiring. Next any class of languages closed under finite union and (concatenation) product is a subsemiring of the semiring of all languages. For instance the rational (= regular) languages form a semiring. See also the related notion of Kleene algebra.

The $k \times k$ matrices over a semiring do form a semiring. In particular, matrices over the Boolean semiring encode nondeterministic finite automata and matrices over the slightly larger semiring $\{-\infty, 0, 1\}$ encode transitions of a Büchi automaton. Matrices over a semiring are used to characterize rational series.

The tropical semirings, in particular $(\mathbb{N} \cup \{+\infty\}, \min, +)$ and $(\mathbb{N} \cup \{-\infty\}, \max, +)$ play a proeminent role in automata theory. They also led to a new branch of mathematics, the tropical geometry.


Measuring the randomness of CNF formulas

I suggest to borrow physics intuition that "less random" structures are more symmetric. Symmetry for CNF is any transformation of the variables, that keeps the function invariant. By that criteria, functions of 3 variables such as

$\displaystyle x_{1} \vee x_{2} \vee x_{3} .$

or, say,

$\displaystyle(x_{1} \vee x_{2} \vee \neg x_{3}) \wedge (x_{1} \vee \neg x_{2} \vee x_{3}) \wedge (\neg x_{1} \vee x_{2} \vee x_{3}) \wedge (\neg x_{1} \vee \neg x_{2} \vee \neg x_{3}).$

are less random than, say

$\displaystyle(x_{1} \vee x_{2} \vee \neg x_{3}) \wedge (x_{1} \vee \neg x_{2} \vee x_{3}) \wedge (\neg x_{1} \vee \neg x_{2} \vee x_{3}) .$

In general, defining a concept of "random" on finite structures is challenging. Historically, it was tried on binary sequences, which arguably are the simplest finite structures. For example, intuitively, a sequence 01010101 is "less random" than, say, 01001110. However, it was quickly realized that there is no consistent formal definition of finite random sequence! Therefore, one have to be skeptical of any naive attempts to define a measure of randomness for any finite structure.


Finding a Hamiltonian cycle from perfect matching of a bipartite graph

If $G$ has a disjoint vertex cycle cover then I agree that $H$ must have a perfect matching, but I don't see the other direction (or I have misunderstood how you define $H$ exactly). I think the construction you were thinking of is the one described in this answer: https://cstheory.stackexchange.com/a/8570/38111.

As for your question (assuming that $H$ is now the bipartite graph constructed in the answer I linked), I think it depends on what you are asking exactly:

if you are asking "if there is a Hamiltonian cycle in $G$, then is there a perfect matching in $H$ that 'corresponds' to this cycle" then yes, since, as David Eppstein points out in his answer, the perfect matchings of $H$ correspond 1-for-1 with cycle covers of $G$, and a Hamiltonian cycle is in particular a vertex disjoint cycle cover.
if you are asking "can we use the same kind of trick to efficiently find such a Hamiltonian cycle", then probably no, since finding a Hamiltonian cycle is NP-hard.


Algorithmic distinctions between random and pseudorandom.

If you just consider consecutive samples then, for most kinds of PRNGs the answer is that you can't distinguish them from true RNGs.

If you consider large input samples, then, in principle (if you don't take complexity issues into account), you can always distinguish a PRNG from true randomness:

For each PRNG $r$, seed length $L$ and starting point $x$ there exist a sample sequence length $k$ such that $f([r(seed, x),\ r(seed, x+1),\ \dots,\  r(seed, x+k-1)])\ =\ 1$ with certainty, and $f(\dots)\ =\ 0$ for any other sequence,
where $r(seed, n)$ is the n-th sample generated by the PRNG initialized with $seed$.

If the PRNG has finitely many states, as it is the case with all the PRNGs commonly in use, then the sample sequence length $k$ is independent of the seed length and starting point.

The distinguishing algorithm $f(\cdot,\ \cdot)$ can be just a brute-force search that tries in order all possible initial states to check whether they produce the sample sequence. Of course, for large state spaces, this is unpractical.
Moreover, the output sequence of a finite-state PRNG is periodic or eventually becomes periodic, although the period can be very large.

The design goal of cryptographically-secure PRNGs is to ensure that no method substantially faster than brute-force search can be used to distinguish them from true RNGs. Currently, various PRNGs are believed to be cryptographically-secure, though no mathematical proof exists.

Cryptographically-insecure PRNGs like the Mersenne Twister can be easily distinguished from true RNGs by observing a relatively short sample sequence.


P vs. NP and Pseudorandom Bit Generators

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

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

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


Reconstruction of a sequence generated by a Markov chain - reference request

If the number of gaps is small, you can do the following brute force approach. Try every possible way of filling those gaps (there will be exponentially many possibilities, in the number of the gaps). For every "guess", fill in the gaps accordingly and train a maximum-likelihood Markov chain on the full sequence. You can even guarantee something about the convergence of the MLE estimator for MC's:
http://proceedings.mlr.press/v98/wolfer19a.html

Having computed the maximum likelihood model -- together with its likelihood score -- pick the highest-scoring possibility of filling the gaps.

I don't know if there's an efficient (say, dynamic-programming-based) algorithm for doing this when the number of gaps is large.


On complexity of linear programming with quadratic equality/inequality constraints?

A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints.  In particular, they prove:

  Let $G$ be a graph with vertices $1,\ldots,n$ and edge set $E$.
  Then $G$ contains a $k$-clique,
  if and only if there exist real numbers $x_1,\ldots,x_n$
  that satisfy the quadratic constraint
  $$\sum_{(i,j)\in E}x_ix_j \ge \frac12\left(1-\frac1k\right)$$
  together with the linear constraints $\sum_{i=1}^nx_i=1$
  and $x_1,\ldots,x_n\ge0$.

Since the $k$-clique problem is NP-hard, this implies that feasibility testing for a linear program plus a single quadratic inequality constraint is NP-hard.
If the graph $G$ contains a $k$-clique $C$, then for $i\in C$ we may set $x_i=1/k$ and for $i\notin C$ we may set $x_i=0$.
Note that the resulting point $x$ satisfies all constraints in the feasibility problem with equality.
This yields that also feasibility testing for a linear program plus a single quadratic equality constraint is NP-hard.

Reference:
T.S. Motzkin and E.G. Straus (1965), "Maxima for graphs and a new proof of a theorem of Turán." Canadian Journal of Mathematics 17, pp 533–540.


How fine-grained can the time hierarchy theorem be in a reasonable model?

The three ingredients of a diagonalization based proof of the time hierarchy theorem are universal simulation, timing, and reversal.  By choosing (or defining) a computational model where these operations are efficient, we get a sharp hierarchy theorem.  In particular, by using a model with a timed virtualization primitive satisfying certain conditions, we get a time hierarchy in the requested form.  However, unlike the sharp space hierarchy, the precise time usage and hierarchy is on a per-model basis (and thus somewhat arbitrary).

If we set up things appropriately, the following algorithm can be implemented in time $f(n)+O(g(n))$ but not in time i.o.-$(f(n)+O(1))$ where $g(n)≥\log(n+f(n))$ and $f$ is $g$-time computable (i.o. means infinitely often):
* Determine the input length $n$, and compute $f(n)$.
* Read a small portion of the input to get a code $M$.
* Run TimedVirtualize($M$, $f(n) + \lg(n)$)  # check whether $M$ accepts the input in $f(n) + \lg(n)$ steps; TimedVirtualize must be fast enough.
* If $M$ accepts, then Reject, and otherwise Accept.

For the time hierarchy, the simplest model is to have a special tape to write the parameters, and an instruction to call TimedVirtualize with a mapping: {Accept, Reject,Timeout}→{Accept,Reject,Timeout} (with no further instructions after TimedVirtualize finishes; TimedVirtualize runs in real time).

However, it is more natural to be able to use virtualization repeatedly, and the rest of the answer gives a partial specification of a class of timed virtualization models, and how such a model can be implemented efficiently.

Timed Virtualization

A computational model defines how a program is interpreted and how much time it takes.  A problem is solvable in time $f$ iff some program solves in time $f(n)$ for all valid inputs where $n$ is the input length.  We assume that input length can be determined in logarithmic time.

One approach to timed virtualization is to use code, data, and privileged data 'tapes'.  The code tape need not be directly accessible.  The data and privileged data tapes are accessible, except that at a given time, a portion of the privileged data tape may be invisible and undetectable. In addition to ordinary instructions, the models have a virtualization function
TimedVirtualize(Code, Time) such that:

The machine executes Code for up to Time steps (Code and Time are obtained from the privileged data tape).  The code is executed and each step is counted as if we initially set the code to Code (and the data tape to its current state.)  All instructions (including TimedVirtualize) are permitted.  The code sees the privileged data tape as initially empty.  The previous privileged data remains unchanged (but the hierarchy theorems would also hold if it were erased instead).
TimedVirtualize returns a value coding Timeout/Accept/Reject depending on whether the code timed out or called an Accept/Reject instruction (that would otherwise Accept/Reject the input).
(optional extension) an optional space bound can be set.
Full-speed condition:  The number of steps TimedVirtualize(Code, Time) takes equals the number of steps Code took (which is ≤Time), plus Time-independent overhead, plus $O(\log(\mathrm{Time}))$.
A number of features can be added to TimedVirtualize, but they are not needed for the hierarchy theorems.  For example, we might want to set initial privileged data, get the time spent by Code, allow unbounded time, or (optionally) do nonvirtualized execution that replaces the code and (visible) privileged data (thus saving space).

Under basic assumptions about the code and timings, every model of this type satisfies the sharp time hierarchy theorem.  The computation of $f(n)$ must erase the worktape at the end (except for the input data if do not use a read-only input tape); we can either define time-constructibility to include the erasure, or use a model where the erasure can be done in linear time.

Efficient Example and Implementation

For every $k$, there is such a model that can simulate in linear time $k$-tape Turing machines (time depends on the machine simulated), and in turn can be simulated in linear time by a $k+2$-tape Turing machine, which suggests that the full-speed condition is computationally reasonable.  (Since a model defines timings, an implementation is an important evidence of reasonableness.) I am not sure if the two tape gap can be reduced to 0.

To get such a model, we fix an interpretation and timings of the code such that an efficient universal Turing machine can simulate the code in linear time, with the constant factor independent of the code size.  For example, we can interpret the code as a Turing machine, but with the state transition specifying the relative offset $d$ (in bits) and taking $k(d+1)$ time, and with a convention and timings for TimedVirtualize (also, note that without random access tapes, head/cursor position is important).  In addition to the tapes in the model, the machine uses a tape storing the timers (and if implemented, space bounds).  While at time $t$, we might have $O(t / \log t)$ timers, we only need the antimonotonic case (timers that are set later trigger sooner), so we can use a counter for the innermost timer, and efficiently use subtraction to update the previous timer when TimedVirtualize finishes.

TimeSpace Hierarchy

If we define space usage in a reasonable way (and allow space bounds in virtualization), we can even get models with a sharp TimeSpace hierarchy theorem:   $\mathrm{TimeSpace}(T+O(1), S+O(1)) ⊊ \mathrm{TimeSpace}(T+O(g), S+h+O(\log T))$ for $\mathrm{TimeSpace}(g,h)$-constructible $(T,S)$ with $g(n)≥\log(n)$ and $T(n)≥n$.  The need for precise timings makes the space hierarchy less sharp here (at least to the extent we can currently prove the hierarchy).


Defining inductive types in intensional type theory purely in terms of type-theoretic data

It turns out that $W$ types plus identity types (eq/= in Coq) allow you to construct pretty much all the general inductive types you want, with the expected computation rules, and even canonicity. This is a very recent result of mine, you can read a preprint at Why not W?, which has been accepted for publication in the TYPES 2020 post-proceedings.
The idea is that even though the standard construction of say the natural numbers from W types does not work, as is well known, a refined, slightly more complicated construction can be made to work. The way my refinement works is to use identity types to pick out the elements of the standard construction which are in canonical form.
This puts general inductive types on an internal, finitary footing, which is a large simplification of the theory. However, there remain some practical problems to be looked at around efficiency and usability.
Other, prior work on simplifying the theory of inductive types includes The Gentle Art of Levitation, by James Chapman, Pierre-Evariste Dagand, Conor McBride, and Peter Morris.


Worst-case asymptotic-complexity of the Set-cover problem?

I don't see how you can say that SCP or any other problem has "worst-case asymptotic complexity", but surely an algorithm solving it can have. However, the problem is NP-complete, and the optimization version is NP-hard.

For an exact algorithm, this is clearly a "theoretical limit". For an exact algorithm, see for example E. Balas and M. C. Carrera, A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering, Operations Research 44, 875-890, 1996. According to A. Caprara et al., Algorithms for the Set Covering Problem, 2000, this algorithm of Balas and Carrera is the fastest known exact algorithm. The result is a bit old already, so I'm not sure if there are newer and faster exact algorithms.

There is a simple greedy polynomial time approximation algorithm with an approximation ratio of $H_n$, where $H_n$ is the $n$th harmonic number. Under reasonable assumptions, this is the best one can do, since if there exists a $c \ln n$-approximation algorithm for the (unweighted) set cover problem for some constant $c < 1$, then there is an $O(n^{O(\log \log n)})$-time deterministic algorithm for each NP-complete problem. I think the Wikipedia page gives the essential references.


Increasing the capacity to maximize the min cut

Theorem. The problem in the post is NP-hard.

By "the problem in the post", I mean, given a graph $G=(V,E)$ and integer $k$, to choose $k$ edges to raise the capacities of so as to maximize the min cut in the modified graph.

The idea is to reduce from Max Cut.  Roughly, a given graph $G=(V,E)$ has max cut size $s$ if and only if you can increase the capacities of $n-2$ edges so that the resulting graph has min cut size $s$.  The idea is that $n-2$ edges are just enough to force the resulting graph to have only one finite-capacity cut, and that can be any cut you choose.

This idea doesn't quite work because to get a given cut $(C, V\setminus C)$, you need the subgraphs induced by $C$ and $V\setminus C$ each to be connected.  But you can work around this with an appropriate gadget.

Proof.
Given a connected graph $G=(V,E)$, define a connected cut to be a cut $(C,V\setminus C)$ such that the subgraphs induced by $C$ and by $V\setminus C$ are each connected.  Define Max Connected Cut to be the problem of finding a connected cut (in a given connected graph) maximizing the number of edges crossing the cut.

We show that Max Connected Cut reduces to the problem in the post. Then we show that unweighted Max Cut reduces to Max Connected Cut.

Lemma 1.  Max Connected Cut reduces in poly time to the problem defined in the post.

Proof.  Given a Max-Connected-Cut instance $G=(V,E)$, let $k=|V|-2$.  To prove the lemma, we prove the following:

Claim 1: For any $s>0$, there is a connected cut $(C,V\setminus C)$ in $G$ of capacity at least $s$, IFF it is possible to raise $k$ edge capacities in $G$ to infinity so that the resulting graph has min cut capacity at least $s$.

ONLY IF: Suppose there is a connected cut $(C,V\setminus C)$ of capacity at least $s$. Let $T_1$ and $T_2$ be subtrees spanning, respectively, $C$ and $V\setminus C$, then raise the capacities of edges in $T_1$ and $T_2$.  (Note that $|T_1|+|T_2|=|C|-1 + |V\setminus C|-1 = |V|-2 = k$.)  The only finite-capacity cut remaining in the graph is then $(C, V\setminus C)$, of capacity at least $s$, so the resulting graph has min cut capacity at least $s$.

IF: Suppose it is possible to raise $k$ edge capacities in $G$ so that the resulting graph has min cut capacity at least $s$. Consider the subgraph formed by the $k$ raised edges.  Without loss of generality, assume this subgraph is acyclic.  (Otherwise, "unraise" one edge from a cycle of raised edges and instead raise some unraised edge that joins two connected components from the subgraph.  This only increases the min cut in the resulting graph.) By the choice of $k=n-2$, the subgraph of raised edges has two connected components, say $C$ and $V\setminus C$, so the only finite-capacity cut in the resulting graph is $(C,V\setminus C)$.  And this cut has capacity at least $s$, as it did in the original graph.

This proves the claim (and the lemma). (QED)

For completeness, we show that Max Connected Cut is NP-complete, by reduction from unweighted Max Cut.

Lemma 2. Unweighted Max Cut reduces in poly time to Max Connected Cut.

Proof. For any integer $N\ge 1$, define graph $P(N)$ to consist of two paths $A$ and $B$, each of length $N$, with edges from each vertex in $A$ to each vertex in $B$.  We leave it as an exercise to the reader to verify that the max cut in $P(N)$ ($A$ on one side, $B$ on the other) has size $N^2$, and no other cut has size larger than, say, $N^2-N/100$.

Here is the reduction.
Given any unweighted Max Cut instance $G=(V,E)$, construct a  graph $G'=(V',E')$ as follows.  Let $n=|V|$.  Let $N = 100(n^2 + 2n)$.  Add to $G$ the graph $P(N)$ defined above (with its two paths $A$ and $B$).  From each vertex $v\in V$ add an edge to one vertex in $A$ and another edge to one vertex in $B$.  This defines the reduction.  To finish, we prove it is correct:

Claim 2: For any $s\ge 0$, there is a cut $(C,V\setminus C)$ in $G$ of capacity at least $s$, IFF there is a connected cut in $G'$ of size at least $s+N^2+n$.

ONLY IF:  Given any cut $(C,V\setminus C)$ in $G$ of capacity at least $s$, consider the connected cut $(A\cup C, B\cup V\setminus C)$ in $G'$.  This connected cut in $G'$ cuts at least $s$ edges from $C$ to $V\setminus C$, plus $N^2$ edges from $A$ to $B$, plus $n$ of the $2n$ edges from $V$ to $A\cup B$.

IF: Suppose there is a connected cut in $G'$ of size at least $s+N^2+n$. $A$ and $B$ are on opposite sides of the cut.  (Otherwise, since the second largest cut in $P(N)$ cuts at most $N^2-N/100$ edges in $P(N)$, the total number of edges cut is at most $N^2-N/100 + |E| + 2|V| \le N^2 - N/100 + n^2 + 2n = N^2$.) Let $C$ denote the vertices in $V$ on the side of the cut with $A$.  Then there are $N^2$ edges in the cut from $A$ to $B$, and $n$ from $V$ to $A\cup B$, so there must be at least $s$ from $C$ to $V\setminus C$.

This proves the claim and Lemma 2.  (QED)

By Lemmas 1 and 2, since unweighted Max Cut is NP-hard, the problem in the post is also NP-hard.


Why is label pruning possible with hub labeling?

I have emailed the authors and they kindly supplied me with the following example:

Let the nodes be contracted in alphabetical order then the red edge will be added during contraction.

Now look at the upward search from A (i.e. we can only visit nodes that have been contracted later). A will settle B with distance 1 and D with distance 2. Since we are not allowed to visit C via D (as this is not upward) we must settle C via B with distance 6. However, as can clearly be seen from the non-contracted graph, the A-C distance is 5 (via D).

This means that we now have an incorrect distance label for C at A.


Algorithm to find all intersections in set of simplices

Yes. You can do better than the trivial $O(n^2)$ time bound, but you are not going to enjoy it....

You can reduce the problem of deciding if there are intersecting pairs of triangles to $O(n)$ ray shooting queries among triangles, and using some heavy machinery (i.e., range searching techniques) you would get something. See Theorem 7.1 in the paper below.

You should also get something as far as detecting all $k$ intersecting pairs, but the bound is going to be useful only if $k$ is truly small (say, between $n$ and $n^{5/4}$).

In practice, some quadtree based heuristic should work reasonably well, but I am just speculating.

https://www.cs.duke.edu/~pankaj/publications/papers/semi-range.pdf


What is the difference between unification and anti-unification?

The following category theory inspired analysis (adapted from Plotkin's A Note on Inductive Generalization) explains a sense in which unification and anti-unification are dual concepts. As notation, let's write
$$t \underset{\sigma}{\Longrightarrow} u$$
for two terms $t$ and $u$ and a substitution $\sigma$ whenever $t\sigma = u$.  The existence of such a subsitution $\sigma$ implies that $t$ is a generalization of $u$, and that $u$ is a specialization of $t$.

Suppose given two terms $t_1,t_2$.  A unifier of $t_1$ and $t_2$ is a term $u$ together with a pair of substitutions $\sigma_1$ and $\sigma_2$ such that
$$
t_1 \underset{\sigma_1}{\Longrightarrow} u \underset{\sigma_2}{\Longleftarrow} t_2
$$
It is a most general unifier if it is a generalization of any other unifier, that is, if for any other unifier
$$
t_1 \underset{\sigma_1'}{\Longrightarrow} u' \underset{\sigma_2'}{\Longleftarrow} t_2
$$
there is some $\sigma'$ such that
$$
u \underset{\sigma'}{\Longrightarrow} u'
$$
In other words, a most general unifier is precisely a coproduct in the category $\mathcal{C}$ whose objects are terms and where there is a morphism $t \to u$ just in case $t \underset{\sigma}{\Longrightarrow} u$ for some $\sigma$.

To define anti-unification we just reverse all the arrows!  Which is to say that...

An anti-unifier of $t_1$ and $t_2$ is a term $u$ together with a pair of substitutions $\sigma_1$ and $\sigma_2$ such that
$$
t_1 \underset{\sigma_1}{\Longleftarrow} u \underset{\sigma_2}{\Longrightarrow} t_2
$$
It is a least general anti-unifier if it is a specialization of any other anti-unifier, that is, if for any other anti-unifier
$$
t_1 \underset{\sigma_1'}{\Longleftarrow} u' \underset{\sigma_2'}{\Longrightarrow} t_2
$$
there is some $\sigma'$ such that
$$
u' \underset{\sigma'}{\Longrightarrow} u
$$
This means that a least general anti-unifier is precisely a product in the category $\mathcal{C}$ defined above.

Update: fixed the accidentally dualized terminology in the original description (thanks Yann Hamdaoui!).


What is the complexity of counting parse trees?

Because you are asking the question in general, the answer will be: uncertain number of trees.

Consider a degenerate case, when you have such a CFG:

$S\rightarrow aA$

$A\rightarrow B$

$B\rightarrow A$

$A\rightarrow aS$

$S\rightarrow a$

This is a valid grammar, right? Though not normalized.
Obviously you can "run" between $A$ and $B$ for any number of times for any given string $s$ generated by this grammar. Each transition between $A$ and $B$ gives you new node in a parse tree, thus we have uncertain number of them.

So, I would rather ask about normalised CFG. For a normalised CFG I guess it should be only one parse tree per the given string $s$.


About some possible optimality properties of Ramanujan graphs

At least among regular bi-partite graphs, Ramanujan graphs provide the optimal approximation of the complete bipartite graph. Let's say that a graph $H$ $C$-approximates a graph $G$ if $tL_H \preceq CL_G$ for $t$ the smallest real number such that $L_G \preceq tL_H$. (I.e. $t := \|L_H^{-1/2} L_G L_H^{-1/2}\|$ where the norm is the operator norm and inverses are taken w.r.t. to the space orthogonal to the all-ones vector). The eigenvalues of $L_{K_{n,n}}$ are $\lambda_1 = 0, \lambda_2 = \ldots \lambda_{2n-1} = n, \lambda_{2n} = 2n$. For any $d$-regular bipartite $H$, the eigenvalues $0=\mu_1 \le \ldots \le \mu_{2n} = 2d$  of $L_H$ come in pairs $d \pm x$. By Alon-Boppana, $\mu_2 \le d-2\sqrt{d-1}$, and, therefore, $\mu_{2d-1} \geq d + 2\sqrt{d-1}$ (ignoring lower-order terms). This implies $C \geq \frac{d + 2\sqrt{d-1}}{d - 2\sqrt{d-1}}$, which is achived by a $d$-regular Ramanujan graph.


I think that the problem is not hard, because if I understood the problem statement correctly, it can be solved in $O(|V|^2)$ time as follows:

We have two $0$-$1$-labeled rooted perfect full binary trees $(A, x)$ and $(B, y)$ with $2^k-1$ nodes. We compute the minimum number of mismatches in any isomorphism between the trees denoted by $F(A, B)$ recursively by using the $F$-values of the subtrees. We have essentially two options when choosing the isomorphism: either we swap the child subtrees of the root in one of the trees or we do not swap anything. Therefore
$F(X, Y)$ is obtained as a minimum of $F(X_{\text{left}}, Y_{\text{left}}) + F(X_{\text{right}}, Y_{\text{right}})$ and $F(X_{\text{left}}, Y_{\text{right}}) + F(X_{\text{right}}, Y_{\text{left}})$, increased by one if the $x$-label of the root of $X$ and the $y$-label of the root of $Y$ are distinct. If we use dynamic programming to optimize this recursion, we have to compute $F(X, Y)$ only once for every pair of subtrees $X$ and $Y$ of the original tree with equal heights.


Equivalence problem for one-counter automata

I have no time to check the references in detail, but Ibarra states in http://dx.doi.org/10.1007/BF01744294 that, according to
Greibachand Baker and Book, the universe problem (is the language $\Sigma^*$?) for non-deterministic one-counter machines with at most one counter reversal is undecidable.

In addition to this, Ibarra considers even more restricted classes for which this problem is undecidable.

Hence, even a subproblem of equivalence is undecidable for a subclass of non-deterministic one-counter machines.


Generation of unlabeled acyclic digraphs

If you are looking for an implementation, Sage knows how to generate general digraphs up to isomorphism

sage: len(list(digraphs(4)))
218

You can then plug in a "test" method if you just want the acyclic ones :

sage: len(list(digraphs(4, property = lambda g:g.is_directed_acyclic())))
31

It returns 302 digraphs on 5 vertices, and 5984 on 6 vertices. But I am a bit scared to try larger values :-)

By the way, giving those values to the OEIS returns the expected sequence :

http://oeis.org/search?q=1,2,6,31,302,5984&language=english&go=Search

Which also happens to contain several references that may suit your taste :-)

Nathann


Let $\mathsf{coIP}$ denote the problem of returning the negation of the inner product. It has roughly the same complexity as $\mathsf{IP}$ since we can add to both players an extra $1$ bit. It is known that the deterministic communication complexity of a decision problem is upper bounded by the product of the non-deterministic complexities of the problem and its complement. Since $\mathsf{IP}$ has deterministic complexity $\Omega(n)$, it follows that the non-deterministic complexity of $\mathsf{IP}$ and $\mathsf{coIP}$ is $\Omega(\sqrt{n})$, and in particular $\mathsf{IP} \notin \mathsf{NP}^{cc} \cup \mathsf{coNP}^{cc}$.

Sun, Wang and Yu showed that the non-deterministic communication complexity of $\mathsf{IP}$ is in fact $\Omega(n)$, even under the promise that the answer is either $0$ or $1$ (as an integer value).

In the related $\mathsf{MA}$ model, in which we demand perfect completeness but only constant soundness, there is an $O(\sqrt{n}\log n)$ protocol due to Aaronson and Wigderson almost matching Klauck's $\Omega(\sqrt{n})$ lower bound; see for example Pitassi's lecture notes.


Bitcoin and preventing double spending in decentralized digital currencies

There has been a lot of work done in this area. A good survey is the first chapter of "Handbook of Financial Cryptography and Security" (for the crypto) and the seventh chapter (for a survey of technologies).

The first scheme to prevent double spending and not require a public global transcript is, to my knowledge, by Chaum, Fiat and Naor [Crypto 88]. In their model, users obtain digital cash that is unlinkable to their identity but if they double spend the coin, then with high probability it will reveal their identity when the coins are eventually returned to the bank. CFN is very inefficient and there has been much work on improving it.


Log-space reduction from Parity-L to CNOT circuits?

Let us start with the $\oplus L$-complete problem of counting mod $2$ the number of paths of length $n$ from vertex $s$ to vertex $t$ in a directed graph $G=(V,E)$. We apply a couple of logspace reductions as follows.

Let $G'=(V',E')$ be the graph such that $V'=V\times\{0,\dots,n\}$ and $E'=\{((u,i),(v,i+1):i<n,(u,v)\in E\}\cup\{(w,w):w\in V'\}$ (i.e., we take $n+1$ copies of $G$’s vertices, make edges go from the $i$th copy to the $(i+1)$th copy according to $G$’s edges, and add all self-loops). Then the original problem is equivalent to counting paths of length $n$ from $s'=(s,0)$ to $t'=(t,n)$ in $G'$.

Moreover, $G'$ is acyclic, and we can explicitly define an enumeration $V'=\{w_k:k\le m\}$ such that all edges in $G'$ apart from the self-loops go from $w_k$ to $w_l$ for some $k<l$. Without loss of generality, $w_0=s'$ and $w_m=t'$. Let $M$ be the adjacency matrix of $G'$ wrt the given enumeration. Then $M$ is an upper triangular integer matrix with $1$ on the diagonal, and the number of paths of length $n$ from $s'$ to $t'$ equals the top right element of $M^n$.

It is easy to see that
$$M=\prod_{j=m}^1\prod_{i=0}^{j-1}E_{i,j}(M_{i,j}),$$
where $E_{i,j}(a)$ is the elementary matrix whose only nondiagonal entry is $a$ in row $i$ and column $j$. In this way, we reduced the original problem to computing the top right element of a product of elementary matrices. In the $\oplus L$ case, the computation is modulo $2$, i.e., we consider the matrices over $\mathbb F_2$. (In this case, the elementary matrices can be only $E_{i,j}(0)=I$, which we can ignore, and $E_{i,j}(1)$, which can be simulated by a single CNOT gate, as mentioned in the question.) If we consider them as integer matrices, we get a $\#L$-complete problem, and if we consider them modulo $k$, we get a $\mathrm{Mod}_kL$-complete problem.


Riemann Hypothesis and Complexity Theory

Valiant's classes are defined over some field. They can use arbitrary constants from that field. To draw some conclusion about Boolean complexity classes, one needs to replace these arbitrary constants by small discrete constants. Here GRH comes into play, since it ensures the existence of enough primes with certain properties.


vertex in a degeneracy ordering of a undirected graph

See http://en.wikipedia.org/wiki/Degeneracy_(graph_theory)

Essentially, a degeneracy ordering is an ordering on the vertices that you get from repeatedly removing a vertex of minimum degree in the remaining subgraph. The degeneracy of the graph is the smallest number d such that every vertex has at most d neighbors that are later than it in the ordering. Among all possible orderings, the degeneracy orderings minimize this number.


Is there any research on approximation of reals with computable numbers

It's funny you should ask, because computability and diophantine approximation has actually been a popular topic in recent years. In particular Becher and Slaman and coauthors have many results and papers. See for instance

Becher, Verónica; Reimann, Jan; Slaman, Theodore A., Irrationality exponent, Hausdorff dimension and effectivization,  ZBL06837203.


One-way functions with respect to various resource bounds

Regarding log-space:  Several candidate one-way functions are computable in log-space or below (and are supposedly secure even against poly-time adversaries).  You can find several pointers for example in the Cryptography in NC$^0$ paper.

Two specific examples include:

Integer multiplication (there are some subtleties for standard OWF, but if you only care about worst-case this is enough)

The Impagliazzo-Naor candidate based on subset-sum:
$f(a_1,...,a_n,S) := (a_1,..., a_n, \sum_{i \in S} a_i \mod 2^n)$.


For a specific unbounded Turing machine, is its Halting problem undecidable?

It depends in which sense you mean "undecidable".

If you evaluate $M$ on the empty input, and want only to find a yes/no answer, then the algorithmic problem is trivially decidable, as answered by Gamow, since either the algorithm outputting "Yes", or the one outputting "No" is correct. you don't have to know which one is correct to prove decidability: there exists an algorithm solving the problem.

If your Halting problem on a specific $M$ still accepts the input $x$ of the machine as input of the problem, then it is in general undecidable. This is because it is equivalent to the general Halting problem by using a universal Turing machine $M_{univ}$, and giving as input the encoding of the Turing machine you want to test.
For simpler machines, of course, this problem can become decidable.

But coming back to the first version with no input, interestingly, there are Turing Machines for which the answer is actually mathematically undecidable. This means that the machine does not halt, but you cannot prove it using your usual mathematical theory (say ZFC for instance). To see this, consider a machine looking for a proof of contradiction in ZFC, and halting when it finds one. If ZFC is not contradicatory, the machine won't halt. But by Gödel's second incompleteness theorem, you cannot prove that this machine won't halt, since this would amount to prove there is no proof of contradiction in ZFC.

Remark that if the machine halts, then it is always possible to prove it, by exhibiting the full run of the machine.

So in my opinion, the answer to your question is: "the Halting problem can be undecidable for a specific Turing machine, even with no input", but we have to be precise about the meaning of "undecidable" here: it is in the sense of mathematical undecidability, i.e. independent of the axioms.


Is there known any complexity class containing online counterparts of optimization problems?

One tricky aspect of defining complexity classes for online problems is that there's in principle no limit on what kinds of computations I can do once I've read the input. In other words, online problems are hard even if I have (for example) an NP oracle processing the input once it arrives.

It's conceivable that with a more limited processor, even simpler prediction tasks become harder to perform, but in general the difficulty of designing online algorithms comes from the ability of the adversary to change the input after you've built a prediction model.


The complementary version given by Wikipedia is correct.

coNP consists of the complements of the problems in NP. In this case, the universe of discourse (i.e., the encoded instances) is the set of (properly encoded) graphs. The Hamiltonian cycle decision problem contains those graphs which are Hamiltonian; its complement is exactly the set of graphs which are not Hamiltonian.

You are correct; the two problems do look almost the same. This is a vital realization concerning coNP (or any co-class in fact). The key difference is that, for some problem classes, being able to efficiently check whether a solution is correct (NP) does not necessarily mean you can also efficiently verify all answers are incorrect (coNP) and vice-versa.


What are the most known database disk storage layout algorithms?

The Fractal Trees I have seen overviewed in Tokutek talks are Cache-Oblivious Lookahead Arrays (COLAs), which are at the intersection of two motivating storage layout ideas. If you're looking for similar layouts, you might be interested in them:

Decreasing insertion time at the cost of increased search time. See Buffered Repository Trees and $B^{\epsilon}$ trees.
Cache-oblivious data structures.

The COLAs paper discusses another data structure at this intersection, as does a more recent improvement.

Implementation-wise, I only know of one other DBMS that uses cache-oblivious data structures: EaseDB, which is in-memory and appears to no longer be under active development.


Set Cover with bounded intersection size

If I'm not missing something, you can use a reduction from SINGLE OVERLAP RESTRICTED EXACT COVER BY 3 SETS (SINGLE OVERLAP RX3C) which I proved to be NPC in this cstheory question.

EXACT COVER BY THREE SETS (X3C):

Instance: Set $X=\{x_1,x_2,...,x_{3q}\}$ and a collection $C=\{C_1,...,C_m\}$ of 3-element subsets of $X$.
Question: Does C contain an exact cover for $X$, i.e. a subcollection $C′\subseteq C$ such that every element of $X$ occurs in exactly one member of $C′$?

X3C is NP-complete (see G&J), and as shown in [1] it remains NP-complete even if every element $x_i$ is contained in exactly 3 subsets of $C$ (RESTRICTED EXACT COVER BY THREE SETS, RX3C).

I proved that it remains NP-complete even if every pair of subsets in $C$  share at most one element; i.e. for all $i\neq j$, $|C_i \cap C_j|\leq 1$ (I called this restricted version SINGLE OVERLAP RX3C).

The SET COVER WITH BOUNDED INTERSECTION SIZE 1 (its decision version)  is simply a generalization of SINGLE OVERLAP RX3C, indeed you can pick the same universe $X$  and the same collection of subsets $C_1,...C_m$ of the SINGLE OVERLAP RX3C and ask for a cover with $q$ subsets or less.

Obviously a cover with $< q$ subsets cannot exist because every subset contains three elements and there are $3q$ elements in $X$. A cover with $q$ subsets must be exact: if two subsets contain a shared element then there are less than $3q$ elements covered.

[1] Teofilo F. Gonzalez: Clustering to Minimize the Maximum Intercluster Distance. Theor. Comput. Sci. 38: 293-306 (1985).


Minimal Number of Symbols in Context-Free Grammar for a Special One-Letter Language

This is essentially the problem of "addition chains", discussed in great detail in many papers and in Knuth's The Art of Computer Programming.  In brief:  the problem as you have stated it is not known to be NP-hard, but nobody knows an efficient algorithm to find the absolutely minimum.  However, there are good algorithms that come reasonably close to the minimum.


What does research in theoretical computer science involve?

Regarding topics

There are different type of issues that may be considered
theoretical computer science. The important word here is
"theoretical" (as we all have some idea of what computer science
deals with). Understanding the word theoretical is not so obvious.
For a long time I took it to mean mathematical, as opposed for example
to "hacking". I learned better from people in linguistics:
theoretical for them clearly does not meant mathematical, but based
on a theory which may be somewhat informal (though it may be also
mathematical), and is an organized body of knowledge and concepts that
structure understanding of observable phenomena and hopefully allow
some deductive and predictive use of the acquired knowledge. It also
reduces the amount to learn and to teach by reducing the number of
primitive concepts from which the rest can be deduced.

Theoretical can be opposed to practical, which is how this knowledge
is used to actually run computing engines, to build systems, etc. I
can also be opposed to applied which is the use of this knowledge to
address problems in other fields of science and human activities.

But I doubt there are clear-cut boundaries.

This said, theoretical computers science covers diverse domains, and I
will try to give some, while I am sure I forget others, and also that
other people may disagree with this organization.

one domain is computability, which studies what can be computed,
and how in a rather abstract sense: largely what is described in
Suresh Venkat's answer.
another is algorithmics, that finds effective means to compute
answers to specific problems, with specific
constraints. Computability is a theoretical context for algorithmics.
semantics (for want of a better name), analyzes the conceptual
organization of computational problems, and of algorithms, into
higher level concepts, so as to factorize techniques that have
proved useful and are often reused, such as the concept of
subprogram,data-structures, modules, information hiding. It
includes the development of mathematical tools that formalize
adequately these concepts to allow high-level reasonning (Scott
semantics for example). It also touches on the way this is
expressed, thus on the separation and relation between syntax and
semantics. Programming languages concepts are part of it (though
language design is probably the pratical application of that
knowledge). It can also include the relation between proof theory
and computation theory, and the modern role of type systems.
another topic, which could develop more than it has so far, is the
relation between computation and fundamental physics. For
example. is there a relation between the limits on computation and
the properties of the physical world, such as physical information
density or the laws of thermodynamics. Quantum computing may
improve a bit our computational prowess; could we hope for more?
Some may dispute that this is still TCS, though there are TCS
studies on hypercomputation.

Regarding specific activities

I am skipping the obvious activities required by academic life. or scientific life in industry:
teaching, publishing, reviewing papers, writing grant applications,
taking academic responsibilities, managing people, advising students
or policy makers. But even then, there is no simple answer to your
question. Here I am just sketching a few aspects that come to mind,
but I am sure there is a lot more to be said. And I am not sure I am
answering you. Some of the best scientists have written books about their work, and that may give you hints about scientific activities.

Researching in theory may involve a variety of things, depending on
your skills and interests that vary a lot from scientist to
scientist. It is somewhat hard to talk of it, since each person
perceives more her own activity and interests than that of others. Most reasearch
requires a wide knowledge, since interesting and really original
results often comes from putting things in relation, or transferring a
technique from one (sub)field to another, or getting different
technical views of the same problem. So learning as much as you
can in breadth as much as in depth is important. Remember that while
you have the time and ability for it as a student, or as a junior
faculty/scientist, both will be reduced later, because of responsibilities
and life in general. Teaching what you do not specialize in may be a
way to keep learning. On SE you can probably learn more by answering than
by asking.

The kind of work people do can vary a lot, because people are
fortunately very different, with a great variety of interests and
technical abilities, thus complementing each other.  Some people are problem solvers. They look at
theoretical or practical questions raised by other people, or by
themselves, and try to solve them, or get closer to a complete or
partial solution.  Other people will be better at structuring existing
knowledge, and putting thing in relation, and then finding new
questions to ask. Both are essential.

Finding simpler proofs of technical results, or simpler presentations
of theories, or merging concepts is important. It generalizes results,
reduces the numbers of things to learn, emphasizes the essential
ideas and possibly brings new understanding. Since our learning time
is limited, progress is possible only when we condense knowledge.

A simple example is the study of abstract families of formal
languages. When language theory first developped, closure properties
under various operation were proved again and again for each family of
languages (regular, context-free, RE, ...), with ad hoc techniques
depending on the family. Then it occurred that these closure
properties had intrinsic relations independently of the concerned
families, and they were studied as such. Today, we only have to check
a few of the simpler closure properties for a given family, and we
get "for free" a whole set of other properties.

Another important point is that there is not such a clear-cut distinction
between theoretical, practical, or experimental work. A good theory
may lead to the implementation of systems that can mechanize the
resolution of problems. And it will take a good theoretician to
implement such a system, with a mix of theoretical and practical work,
including system implementation, or language design. Many examples
come to mind, such as proof and/or program synthesis systems,
specialized language for synchronous parallel systems, a restricted
algorithmic language for which computational complexity can be
systematically derived. Not only is it important to be able to produce
such pratical systems, which make theoretical results more widely
available and usable, but it is often very important for theoretician
either to use proficiently these systems, if only to unload the now less creative parts of his work, or to contribute to the development and
extension of these system.

Another aspect is to be able to compare theoretical approaches by
pratical experimentation. Here, the issue is to compare different
techniques to accomplish the same goal. Comparing
implementations is often meaningless as their efficiency often depend
on the programming language, or the programming skills of the
implementor. But if they can be expressed all in a common theoretical
framework, then it is sometimes possible to compare them experimentaly
within that framework. Here, theory and practice support each other,
as they often do in science. Pure theoretical analysis is not always
easy to achieve. Furthermore, experimental analysis, when well
conducted, can exhibit unexpected behavior that may motivate better
theoretical analysis.

The world is not simple or clear-cut. That is why it can be fun, with
room for all kinds of skills. Questionning your own knowledge, and
answering questions of others, by whatever means.

Two things often forgotten: ethics of science, and explaining it to
people.  Both are essential, and hard.