A stronger multiplexing rule for soft linear logic?

Your rule $(\ast)$ is sometimes referred to as "absorption".  I think the first who considered it was Jean-Marc Andreoli in his paper on focusing proofs. Indeed, it makes a lot of sense in proof search: read bottom-up, it says that when you have $?A$ (on the right), you may extract a copy of $A$ and try and do something with it, while keeping $?A$ for future use.

Of course, as you know, absorption plus weakening and promotion (the usual one, i.e., functoriality of $!(-)$ + comonad comultiplication) gives a system equivalent to full linear logic.  You are asking about the system obtained by also taking promotion to be strictly functorial (what Lafont calls "soft promotion").  Let me call it $\mathbf{PL}^-$, for reasons I'll clarify momentarily.

As you rightly observe, $\mathbf{PL}^-$ is much more powerful than $\mathbf{SLL}$.  Indeed, and this is essentially a computational reformulation of your answer, the untyped term calculus underlying $\mathbf{PL}^-$ is Turing-complete, whereas the untyped calculus underying $\mathbf{SLL}$ has exactly the same expressiveness as $\mathbf{SLL}$: its terms strongly normalize in $O(s^d)$ steps, where $s$ is the size and $d$ the exponential depth of the term being normalized (this is the key feature of so-called "light" logics: their normalization does not rely on the logical complexity of formulas.  Types/formulas are there only to ensure that the normal forms are of a prescribed shape: integers, strings, booleans, etc.).

Now I must apologize for invoking my own work, but it is truly relevant to your question: $\mathbf{PL}^-$ is actually the intersection of linear logic and a system I call parsimonious logic ($\mathbf{PL}$), which is a variant of linear logic based on the the fact that the exponential modality obeys the isomorphism

$$!A \cong (A\&1)\,\otimes\,!A$$

and nothing more (except functoriality, of course). With Kazushige Terui, we refer to this iso as Milner's law, because of its similarity with the structural equality $!P\equiv P\mathrel{|}\,!P$ in the $\pi$-calculus (especially if one considers the affine version of parsimonious logic, which is most frequent in applications). Milner's law does not hold in $\mathbf{LL}$, so $\mathbf{PL}$ is not a subsystem of linear logic. On the other hand, the $!(-)$ of linear logic is a comonad and has contraction, which is not the case in $\mathbf{PL}$, so this latter is not a supersystem of $\mathbf{LL}$. Categorically, a model of $\mathbf{PL}$ is just a SMCC with products (in fact, free copointed objects suffice) and with a monoidal endofunctor $!(-)$ satisfying Milner's law (naturally in $A$). Comparatively, models of $\mathbf{LL}$ are much more complex to describe.

As you see, the implication from left to right of Milner's law gives you precisely weakening and absorption (composing with the projections of $\&$, which is the product as usual). So the system you are asking about is $\mathbf{PL}$ with only "half" of Milner's law, and in fact $\mathbf{PL}^-=\mathbf{PL}\cap\mathbf{LL}$.

Not unlike $\mathbf{SLL}$, it turns out that $\mathbf{PL}$ has quite interesting complexity properties. However, quite unlike $\mathbf{SLL}$ and Girard's light linear logic, complexity is not controlled by the structure of the logical rules (they are Turing-complete) but by the types: simply-typed $\mathbf{PL}$ captures $\mathsf L$ (deterministic logspace), whereas $\mathbf{PL}$ with linear polymorphism (i.e., where the $X$ in $\forall X.A$ may only be instantiated with a $!$-free formula) captures $\mathsf P$ (deterministic polytime). I also conjecture that "parsimonious system F" ($\mathbf{PL}$ with full polymorphism) captures primitive recursion. When I say "captures" above I mean that one defines types $\mathsf{Str}$ of binary strings and $\mathsf{Bool}$ of booleans (more or less as usual) and looks at the class of problems decidable by terms of type $\mathsf{Str}\multimap\mathsf{Bool}$ (or instantiations of them when polymorphism is absent/limited).

The side of Milner's law that's missing from $\mathbf{PL}^-$ is necessary for the completeness with respect to logspace and polytime (for instance, without it you cannot type the predecessor with simple types $\mathsf{Nat}\multimap\mathsf{Nat}$). So simply-typed (resp. linear polymorphic) $\mathbf{PL}^-$ does not correspond to any class I know of: you will only be able to solve logspace (resp. polytime) problems in it, but you'll be missing some of those. However, when you have full second order (or when you are untyped), $\mathbf{PL}^-$ seems to be (is) just as expressive as $\mathbf{PL}$. In particular, one may play around with "parsimonious OCaml", which is a (fictional, I haven't implemented it :-) ) variant of OCaml following the type discipline prescribed by $\mathbf{PL}^-$. The funny thing about such a language is that it does not have general fixpoints, only linear fixpoints: when you write

$$\mathtt{letrec}\ \mathtt f\ \mathtt x = \mathtt{code}$$

$\mathtt{code}$ may only contain one occurrence of $\mathtt f$ (in every branch of an $\mathtt{if\ldots then\ldots else}$ statement). Since while loops are exactly linear (tail) recursions, parsimonious Ocaml is Turing-complete. However, there's lots of "natural" OCaml programs you'll have to non-trivially rewrite for them to run in parsimonious OCaml! (Pretty much every structural recursion on binary trees for example).  In a sense that I would like (but don't know how) to make precise, parsimonious logic (and hence the logic you are asking about) is the "logic of while loops". I think that this is the ultimate reason why it behaves so well from the complexity viewpoint.

I'm going to stop here and give you some pointers, in case you are more curious. There is a series of papers (by myself and co-authors) on parsimonious logic and complexity, all available on my web page. However, things are a bit scattered here and there and I think that the most readable account is in Chapter 3 of my habilitation thesis, so I suggest you go there instead.


Problems outside of P that are not P-hard

I think you can construct a set not in $P$ that is not $P$-hard by a Ladner-style argument. Here's a specific example.

In his paper "A Uniform Approach to Obtain Diagonal Sets in Complexity Classes" (Theor. Comp. Sci. 18, 1982), Schöning proves the following:

  Theorem Suppose $A_1 \notin C_1$, $A_2 \notin C_2$, $C_1$ and $C_2$ are recursively presentable complexity classes and are closed under finite variations. Then there's a set $A$ such that $A \notin C_1$, $A \notin C_2$, and if $A_1 \in P$ and $A_2$ is not trivial (empty set or all strings) then $A$ is polytime many-one reducible to $A_2$.

To apply this, set $A_1$ to be the empty set, and $A_2$ to be $EXP$-complete under polytime reductions, set $C_1$ be the set of $P$-hard sets that are in $EXP$, set $C_2 = P$. The empty set cannot be $P$-hard (the definition of $P$-hardness for a language requires that there is at least one instance in the language and one instance not in). $A_2$ is definitely not in $C_2$. The $C_1$ and $C_2$ can be verified to meet the above conditions (similar to how Schoening does it for the $NP$-complete sets; see also this related question). So we get an $A$ that is not a $P$-hard problem in $EXP$, and that $A$ is not in $P$. But because $A_1 \in P$ and $A_2$ is nontrivial, $A$ is many-one reducible to an $EXP$-complete set, so it is in $EXP$. Therefore, in particular, $A$ cannot be $P$-hard either.

In the above argument, the restriction to $P$-hard problems in $EXP$ is necessary to ensure recursive presentability, since the P-hard problems as a whole are not recursively presentable and not even countable.
Now, "natural" examples of this are a different story...


What is the proof of this nonstandard version of Azuma's inequality?

I can't find a reference, so I'll just sketch the proof here.

Theorem. Let $X_1, \cdots, X_n$ be real random variables. Let $a_1, \cdots, a_n, b_1, \cdots, b_n$ be constants. Suppose that, for all $i \in \{1,\cdots,n\}$ and all $(x_1,\cdots,x_{i-1})$ in the support of $(X_1, \cdots, X_{i-1})$, we have

$\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{i-1}] \leq 0$ and
$\mathbb{P}[X_i \in [a_i,b_i]]=1$.

Then, for all $t\geq0$, $$\mathbb{P}\left[\sum_{i=1}^n X_i \geq t\right] \leq \exp\left(\frac{-2t^2}{\sum_{i=1}^n (b_i-a_i)^2}\right).$$

Proof. Define $Y_i = \sum_{j=1}^i X_j$. We claim that $$\forall i \in \{1,\cdots,n\}~\forall \lambda \geq 0 ~~~~~ \mathbb{E}\left[e^{\lambda Y_i}\right] \leq e^{\frac18 \lambda^2 \sum_{j=1}^i (b_j-a_j)^2}.\tag*{(*)}$$ For all $i$ and $\lambda$, we have $$\mathbb{E}\left[e^{\lambda Y_i}\right] = \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot e^{\lambda X_i}\right] = \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot \mathbb{E}\left[e^{\lambda X_i}\middle|Y_{i-1}\right]\right].$$
By assumption, $\mu(y_{i-1}):=\mathbb{E}[X_i|Y_{i-1}=y_{i-1}]\leq 0$ and $\mathbb{P}[X_i \in [a_i,b_i]] =1$ for all $y_{i-1}$ in the support of $Y_{i-1}$. (Note that $Y_{i-1}=X_1+\cdots+X_{i-1}$.) Thus, by Hoeffding's lemma, $$\mathbb{E}\left[e^{\lambda X_i}\middle|Y_{i-1}=y_{i-1}\right] \leq e^{\lambda\mu(y_{i-1})+\frac18 \lambda^2(b_i-a_i)^2}$$ for all $y_{i-1}$ in the support of $Y_{i-1}$ and all $\lambda \in \mathbb{R}$. Since $\mu(y_{i-1})\leq 0$, we have, for all $\lambda \geq 0$, $$\mathbb{E}\left[e^{\lambda Y_i}\right] \leq \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot e^{0+\frac18 \lambda^2(b_i-a_i)^2}\right].$$
Now induction yields the claim (*) above.
Now we apply Markov's inequality to $e^{\lambda Y_n}$ and use our claim (*). For all $t, \lambda > 0$, $$\mathbb{P}\left[\sum_{i=1}^n X_i \geq t\right]=\mathbb{P}[Y_n \geq t] = \mathbb{P}\left[e^{\lambda Y_n} \geq e^{\lambda t}\right] \leq \frac{\mathbb{E}\left[e^{\lambda Y_n}\right]}{e^{\lambda t}} \leq \frac{e^{\frac18 \lambda^2 \sum_{i=1}^n (b_i-a_i)^2}}{e^{\lambda t}}.$$
Finally, set $\lambda=\frac{4t}{\sum_{i=1}^n (b_i-a_i)^2}$ to minimize the right hand expression and obtain the result. $\tag*{$\blacksquare$}$
As I mentioned in my comment, the key difference between this and the "usual" statement of Azuma's inequality is requiring $X_i \in [a_i,b_i]$, rather than $X_i \in [-a,a]$. The former allows more flexibility and this saves a factor of 2 in some cases.
Note that the $Y_i$ random variables in the proof are a supermartingale. You can obtain the usual version of Azuma's inequality by taking a Martingale $Y_1, \cdots, Y_n$, setting $X_i=Y_i-Y_{i-1}$ and $[a_i,b_i]=[-c_i,c_i]$ (where $\mathbb{P}[|Y_i-Y_{i-1}|\leq c_i]=1$), and then applying the above result.


What is the known complexity of this game? (similar to PushPush-1)

There are no sliding blocks, so the game is in $P$

Informally: from the starting position just mark the cells reachable by the cursor. The level has a solution iif the final position becomes reachable.

The algorithm is similar to the Dijkstra's algorithm for shortest path applied to the graph derived from the level.

For example:

For an $n \times n$ level the complexity is $O(n^4)$.

Let me know if you need further details.


If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

There are 4 possibilities, name them e1-e4:

e1  neither match
e2  a only matches
e3  b only matches
e4  both match

Now I restate what you want to prove: Suppose:

\begin{align*}
  \Pr[e4] &\gt 0.25  & \text{prob of correct guess} \\
  \Pr[e2] + \Pr[e4] &\leq 0.5  & \text{prob guess a correctly} \\
  \Pr[e3] + \Pr[e4] &\leq 0.5  & \text{prob guess b correctly}
\end{align*}

This implies that
\begin{align*}
  \Pr[e2] < 0.25  \\
  \Pr[e3] < 0.25  \\
  \implies \Pr[e2] + \Pr[e3] < 0.5  \\
  \implies \Pr[e1] + \Pr[e4] > 0.5,
\end{align*}
and then we notice that this is the probability that the XOR matches.


Does randomness buy us anything inside P?

Problem: An array $A[1..2n]$ consists of $n$ 1s and $n$ 0s. Find an $i$ such that $A[i]$ is 1.

You are allowed to query 'Which number is present in $A[i]$'? Each query takes constant time.

Solution:
Randomized Algorithm: Pick a random index $i$ and check if $A[i]$ is 1. Expected number of queries is 2, but any deterministic algorithm must make at least $n$ queries. Therefore, the randomized upper bound is strictly better than the deterministic lower bound in this model.

This is an example from query complexity which Tsuyoshi was referring to in the comment.


Normal form for deterministic (sub)sequential transducers with letter-by-letter outputs

I'm not sure what your question is. Tell me if I am mistaken.
From what I understand:
Given a subsequential transducer, you can easily transform it into your canonical form by replacing every transition $(q,a)\to (p,v)$ into a transition reading $a$ and producing nothing followed by a sequence of transitions reading nothing and producing $v$ one letter at a time.

On the other hand, given such a transducer with $\epsilon$ transitions where all loop read some letter, you can compress the finite $\epsilon$-paths to get to a classical sequential transducer.


Why is computing pure Nash equilibria NP-complete?

These are my two comments as an answer:

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

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

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

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

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


Standard notions of reduction used in Descriptive Complexity are first-order reduction and the weaker first-order projection. Definitions of both these notions are found in Immerman's book on Descriptive Complexity.


Path replanning in path finding algorithms

The problem is known as the Canadian Traveler Problem.


Minimize makespan on identical machines when jobs are vectors

This is the Vector Scheduling (VS) problem. Unless P = NP, VS admits no constant factor approximation algorithm when $d$ is part of the input:

Chekuri, C., Khanna, S.: On multidimensional packing problems.
SIAM J. Comput., 33(4):837-851, 2004.

The same paper gives a polynomial-time approximation scheme when $d$ is not part of the input, and a polynomial time $O((\log d)^2)$ approximation when $d$ is part of the input. The latter was improved to $O(\log d)$ by Meyerson, Roytman and Tagiku (APPROX 2013). For more references and recent results you can refer to:

Bansal, N., Vredeveld, T., van der Zwaan, R.: Approximating Vector Scheduling: Almost Matching Upper and Lower Bounds. Lecture Notes in Computer Science, 8392:47-59, 2014.


Books/Lecture Notes on Parametrized Complexity

A good place to start is "Parameterized Complexity Theory" by Jörg Flum and Martin Grohe, published by Springer.


What is the difference between a second preimage attack and a collision attack?

I can motivate the difference for you with attack scenarios.

In a first preimage attack, we ask an adversary, given only $H(m)$, to find $m$ or some $m'$ such that $H(m')$ = $H(m)$. Suppose a website stores $\{username, H(password)\}$ in its databases instead of $\{username, password\}$. The website can still verify the authenticity of the user by accepting their password and comparing $H(input) =? H(password)$  (with probability of $1/2^n$ for some large $n$ for false positives). Now suppose this database is leaked or is otherwise comprimised. A first preimage attack is the situation where an adversary only has access to a message digest and is trying to generate a message that hashes to this value.

In a second preimage attack, we allow the adversary more information. Specifically, not only do we give him $H(m)$ but also give him $m$. Consider the hash function $H(m) = m^d \mod{pq}$ where $p$ and $q$ are large primes and $d$ is a public constant. Obviously for a first preimage attack this becomes the RSA problem and is believed to be hard. However, in the case of the second preimage attack finding a collision becomes easy. If one sets $m' = mpq + m$, $H(mpq + m) = (mpq + m)^d \mod{pq} = m^d \mod{pq}$. And so the adversary has found a collision with little to no computation.

We would like one way hash functions to be resistant to second preimage attacks because of digital signature schemes, in which case $H(document)$ is considered public information and is passed along (through a level of indirection) with every copy of the document. Here an attacker has access to both $document$ and $H(document)$. If the attacker can come up with a variation on the original document (or an entirely new message) $d'$ such that $H(d') = H(document)$ he could publish his document as though he were the original signer.

A collision attack allows the adversary even more opportunity. In this scheme, we ask the adversary (can I call him Bob?) to find any two messages $m_1$ and $m_2$ such that $H(m_1) = H(m_2)$. Due to the pigeonhole principle and the birthday paradox, even 'perfect' hash functions are quadratically weaker to collision attacks than preimage attacks. In other words, given an unpredictable and irreversible message digest function $f(\{0,1\}^*) = \{0,1\}^n$ which takes $O(2^n)$ time to brute force, a collision can always be found in expected time $O(sqrt(2^n)) = O(2^{n/2})$.

Bob can use a collision attack to his advantage in many ways. Here is one of the simpliest: Bob finds a collision between two binaries $b$ and $b'$ ($H(b) = H(b')$) such that b is a valid Microsoft Windows security patch and $b'$ is malware. (Bob works for Windows). Bob sends his security patch up the chain of command, where behind a vault they sign the code and ship the binary to Windows users around the world to fix a flaw. Bob can now contact and infect all Windows computers around the world with $b'$ and the signature that Microsoft computed for $b$. Beyond these sorts of attack scenarios, if a hash function is believed to be collision resistant, that hash function is also more likely to be preimage resistant.


Proving membership in W-hierarchy when problem is not parameterized by its solution size

The answer to your updated Question (1) "When a problem is parameterized by something other than the size of a solution (and as a result, the size of a solution is still unbounded in terms of the parameter), then [is it] W[t]-hard for all t, at least?" is no. Independent Set for example is FPT with respect to the treewidth $\omega$ of the input graph. The solution size $k$ (essentially the size of a largest independent set of the input graph) can be much larger than $\omega$.
In general, a parameter can be anything that is related to the input instance. The standard parameter solution size is just one of many different ways to parameterize a problem.


How do 'tactics' work in proof assistants?

The basic tactics either run an inference rule forwards or backwards (for example, convert hypotheses $A$ and $B$ into $A\wedge B$ or convert goal $A\wedge B$ into two goals $A$ and $B$ with same hypotheses), apply a lemma (~ function application), split up a lemma about some inductive type into a case for each constructor, and so on. Basic tactics may succeed or fail depending upon the context in which they are applied. More advanced tactics are like little functional programs that run the basic tactics, perform pattern matching over the terms in the goal and/or assumptions, make choices based on the success or failure of tactics, and so forth. More advanced tactics deal with arithmetic and other specific kinds of theories. The key paper on Coq's tactic language is the following:

D. Delahaye. A Tactic Language for the System Coq. In Proceedings of Logic for Programming and Automated Reasoning (LPAR), Reunion Island, volume 1955 of Lecture Notes in Computer Science, pages 85–95. Springer-Verlag, November 2000.

The formal rules which form the essence of the basic tactics are defined in the Coq users guide here or in Chapter 4 of the pdf.

A quite instructive paper on implementing tactics and tacticals (essentially tactics that take other tactics as arguments) is:

Amy Felty. Implementing Tactics and Tacticals in a Higher-order Programming Language Journal of Automated Reasoning, 11(1):43-81, August 1993.

Coq's tactic language has the limitation that the proofs written using it hardly resemble proofs one does by hand. Several attempts have been made to enable clearer proofs. These include Isar (for Isabelle/HOL) and Mizar's proof language.

Aside:
Did you also know that the programming language ML was originally designed to implement tactics for the LCF theorem prover? Many ideas developed for ML, such as type inference, have influenced modern programming languages.


Types which correspond to sets of cardinality of continuum

You must be careful here. You are using set-theoretic concepts (cardinal, continuum) outside set theory. There is potential for confusion.

Your question can be understood in several ways.

Maybe you are asking whether there can be uncountably many terms of a given type. The answer is: obviously not since there are only countably many finite strings, and eact term is a string (or a finite tree if we think of abstract syntax). You might be asking this question because you claim that "the elements of types are terms". This, in my opinion, is a very damaging view of types. It is like saying that the elements of $\mathbb{R}$ are only certain expressions which denote real numbers.

Another possibility is that you are asking whether there is a model of type theory in which some of the types are interpreted as uncountable sets. The answer is yes, for example the set-theoretic type model in which types are sets. In this case $\mathtt{nat} \to \mathtt{bool}$ has the power of continuum because it is the sets of all infinite boolean sequences.

You could be asking whether inside type theory we can prove that there are types of the cardinality of continuum. In this case the question does not make sense because the notion "cardinality of continuum" is something that only make sense in set theory. You need to rephrase it so that it makes sense in type theory, but there are complications. Cardinality just does not behave the same way in type theory as it does in set theory. For example, you cannot show that cardinals (whatever you think they are) are linearly ordered. But we can still define special cases. Thus we can define the notion of an uncountable type:

Definition uncountable (A : Type) :=
   forall f : nat -> A, exists x : A, forall n : nat, ~ (f n = x).

In words, $A$ is uncountable if for every sequence $f : \mathbb{N} \to A$ there exists $x : A$ such that $x$ is not in the image of $f$. The Baire space $\mathbb{N}^\mathbb{N}$ is uncountable:

Theorem baire_uncountable : uncountable (nat -> nat).
Proof.
  intro f.
  exists (fun n => S (f n n)).
  intro n.
  intro E.
  absurd (f n n = S (f n n)).
  - auto.
  - pattern (f n) at 1.
    rewrite E.
    reflexivity.
Qed.

So, classically this would mean that the cardinality of the Baire space is larger than $\aleph_0$, but as I said, cardinalities inside type theory, and in constructive mathematics in general, behave a lot less nicely than in set theory.


Classes of boolean functions where reasonable lower bounds on approximate degree is unknown?

If I understand correctly you are asking about the relationship between the degree necessary for exact representation and the degree necessary for approximate representation.  The seminal paper by Nisan and Szegedy shows that for $\epsilon$ constant these degrees are polynomially related.


Well known classes of boolean formulas that require exponentially long resolution proofs

Hard instances for resolution:

Tseitin's formulas (over expander graphs).
Weak ($ m $ to $ n$) pigeonhole principle (exponential in $n$ lower bounds, for any $ m>n $).
Random 3CNF's with $ n $ variables and $ O(n^{1.5-\epsilon})$ clauses, for $ 0<\epsilon<1/2 $.

Good, relatively up-to-date, technical survey for proof complexity lower bounds, see:

Nathan Segerlind: The Complexity of Propositional Proofs. Bulletin of Symbolic Logic 13(4): 417-481 (2007) available at: http://www.math.ucla.edu/~asl/bsl/1304/1304-001.ps


Church-style CoC with axiom for induction over Church-encoded unit, is it consistent?

Yes, it's consistent. Probably the easiest account is in my 2013 CSL paper with Derek Dreyer, Internalizing Parametricity in the Extensional Calculus of Construction, which is all about adding this style of parametricity axiom to the CoC.


Simulation of every physical quantum system on quantum computer

We will never be able to prove this statement, because we can never be able to know for sure whether we have the exact laws of physics, or just a very good approximation to them. Even if we had a satisfactory theory of everything which we could use to make good predictions about every experimentally measurable physical system, there would be no way to tell whether it was correct or a very good approximation.

Having said that, we are still quite far from even coming close to a proof of this statement. For example, we can't even prove that the Standard Model is simulable by a quantum computer. Jordan, Lee, and Preskill have two papers showing how to use a quantum computer to simulate a quantum field theory which is much simpler than the Standard Model. This turns out to be harder than it might at first appear.


The entropy of a convolution over the hypercube

There is no such $C$. Define $g\colon\mathbb{Z}_2^n\to\mathbb{R}$ by
$$g(x_1,\dots,x_n)=\begin{cases}
2^{2n/3}&\text{ if $x_1=\dots=x_n=0$}\\
1&\text{ otherwise.}\end{cases}$$

Then $g*g$ satisfies
$$(g*g)(x_1,\dots,x_n)=\begin{cases}
2^{4n/3}+2^n-1&\text{ if $x_1=\dots=x_n=0$}\\
2^{2n/3}\cdot 2+2^n-2&\text{ otherwise.}\end{cases}$$

Let $f=g/\|g\|_2$. Then $H(f)=H(g/\|g\|_2)$ is $o(1)$ (in fact it's exponentially small in $n$), while $H(g*g/\|g*g\|_2)$ is about $n$.


Complexity of finding the square root of a perfect square

The square root of an $n$-digit number can be computed in time $O(M(n))$ using e.g. Newton’s iteration, where $M(n)$ is the time needed to multiply two $n$-digit integers. The current best bound on $M(n)$ is $n\log n\,2^{O(\log^*n)}$, provided by Fürer’s algorithm. See http://en.wikipedia.org/wiki/Methods_of_computing_square_roots for more square root algorithms, and http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations for an overview of computational complexity of arithmetical operations.


Best algorithm for calculating lists of neighbours

This is the well-studied problem of Nearest Neighbour Search.  There is not one 'best solution' to the problem---you'll want to choose trade offs based on the input and requirements.

Do you need the creation of the data structure to be parallel?  Or just the queries?  Depending on how many thousands of points you're talking about, if your set of points is static it might not be impractical to do something naive like:

For each point $x$, construct a list of all other points, sorted by distance from $x$.

This can be done in $O(n^2\log n)$ time and $O(n^2)$ space, which is not that bad if you only need to run it once for a set of several thousand points.  It will give you constant or logarithmic query time for pretty much anything you'd want to do.

If you need something smarter that requires less space or less time, I'd recommend reading the Wikipedia article on Nearest Neighbour Search and perhaps refining your question, telling us

how many times you'll need to build the structure from scratch
whether or not it needs to be dynamic
what exactly needs to be parallelized
whether your 'cutoff value' for Euclidean distance is fixed, or will vary from query to query
if possible, a tighter estimate on the number of points.  When somebody says 'thousands' sometimes they mean 3,000 and sometimes they mean 300,000.


Trying to understand a paper on ksvd algorithm (dictionary learning) by Elad, et al

By examples that use the atom $d_k$,i.e. those where $x_T^{k} (i)$ is nonzero, the authors are referring to the nonzero elements of the coefficient matrix $X$ because only nonzero elements play a role in multiplying two matrices. Since we seek to have a sparse representation, we only pay attention to the nonzero elements of $X$ and keep the zero elements intact.


Logic Programming: Transforming B:-A C:-A to B,C:-A

So, this is an instance of the fact that $(A \supset B) \wedge (A \supset C)$ is equivalent to $A \supset (B \wedge C)$. A different type isomorphism, namely that $(B \supset A) \wedge (C \supset A)$ is equivalent to $(B \vee C) \supset A$, looks more like what you wrote down, but that's because in logic programming notation we write B :- A when we mean $A \supset B$. (Note: $\supset$ is "implies," $\wedge$ is "and," and $\vee$ is "or.")

What you're trying to do is related to the binarization transformation, which is discussed in McAllester's "On the complexity analysis of static analyses." There may be a better name for the transformation, but if so, it wasn't known the authors of the paper "A succinct solver for ALFP" (Alternating Least Fixedpoint formulas are a generalization of Horn clauses for bottom-up logic programs such as yours) - in Example 1 on page 4 they discuss a similar transformation and just call it "exploiting the possibility of sharing of pre-conditions."


upper bound on the size of a DFA for A|B given the DFAs for A and B?

The upper bound of $nm$ follows from the usual Cartesian product construction that you will find in just about any book on automata theory.  A lower bound of $nm$ is observed (for the case $\operatorname{gcd}(n,m) = 1$) in this paper:

  Sheng Yu.  State Complexity of Regular Languages.  Journal of Automata, Languages and Combinatorics, 2001.

The lower bound is proved for DFAs that I would consider to exist in the real world -- but if you want an expectation you will have to be more precise about the distribution from which $A$ and $B$ are drawn.

The bound is simple and can surely be extended to three DFAs.


To what extent is anonymity through a Chaum mix compromised by using trusted mixes in the cascade?

I haven't seen a paper that addresses your (first) question specifically. One extreme example of a mix node that you trust is yourself, if you are participating in the network as well as using it. One paper that talks about the trade-offs of using yourself as a node in a mix network is: On the Economics of Anonymity. It sort of addresses your second question.

While Tor is not exactly a mix network, I believe it carefully chooses entry nodes based on individuals the network maintainers trust. In this case, all users have the same "trust network" and so it avoids the problem you are proposing to study. The drawback is you personally must trust the same nodes.

As to your specific question, I haven't seen a paper that specifically addresses what you want but I also do not follow the area closely. Most papers on Mix Networks are catalogued here: http://freehaven.net/anonbib/ and so you could thumb through the titles for something that might be related.

Finally, I'm not sure you'll find the adversary has much power unless if they can observe large portions of the network, in which case there are more effective attacks (especially in Tor-like anonymity networks which don't actually mix or obfuscate packet timing).


"Security Against Covert Adversaries" question

1) $x_0$ is (indeed) a plaintext. (Perhaps to guess at where confusion arose from:) the 'more modern' version of homomorphic encryption is fully homomorphic encryption (FHE) fully supporting both additive and multiplicative homomorphisms, whereas the paper you're reading was published about 2.5 years before Gentry's original FHE scheme came out. (Check out the wikipedia article on homomorphic encryption for more examples..)

This paper uses additive-homomorphic encryption, which allows the computation $Enc(pk, x_0) + Enc(pk, x_1) = Enc(pk, x_0 + x_1)$. Note that additive-homomorphic encryption schemes tend to support (must.. support?) an additional "scalar-multiplication homomorphism." That is, the computation
$$x_0 \cdot Enc(pk, x_1) = Enc(pk, x_0\cdot x_1),$$
where plaintext $x_0$ is public information.

(Note that the above is different than FHE, which supports both the prior additive homomorphism, and simultaneously the "full" multiplicative homomorphism of $Enc(pk, x_0) \cdot Enc(pk, x_1) = Enc(pk, x_0\cdot x_1).$)

2) Read it as a field =)


Looking for Literature Source for Following idea

It seems that this idea is attributed to Levin (It is called optimal search). I believe this fact is well known. A similar algorithm is described in wikipedia for instance, although using the subset sum problem. In this article from scholarpedia you can find several references on the subject, including a pointer to the original algorithm and to some other optimal search algorithms.

Comment 1: Levin's optimal search guarantees that if $\varphi$ is a satisfiable instance then a solution will be found in polynomial time assuming $P=NP$. If
$\varphi$ is not satisfiable the algorithm may not terminate.

Comment 2: As Jaroslaw Blasiok pointed out in another answer, this algorithm does not decide Sat only assuming P=NP.


Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

Computing a generating set of invariants (sometimes called the computational problem of "Noether's Normalization Lemma") for the action of $SL_3$ on an $n$-dimensional vector space $V$. (You can also talk about $SL_m$, but it's just a little cleaner to state the results when $m=3$.)
Went from non-constructive proof of finiteness, to computable, to EXPSPACE, to nearly-polynomial, over the course of over a century.
As discussed in GCT V: Hilbert originally proved that the invariant ring $\mathbb{C}[V]^{SL_3}$ was finitely generated non-constructively. After Gordan's criticism, Hilbert [1893] gave an algorithm, showing (in modern language) that a finite generating set can be computed in finitely many steps (so, the problem became computable). Degree bounds proved nearly a century later by Popov and then Derksen combined with Gröbner basis puts it into $\mathsf{EXPSPACE}$. In GCT V, Mulmuley put this problem into time $n^{O(\log \log n)}$.


Coloring where all colors are present in closed neighborhood of every vertex

I would call this a polychromatic coloring of the closed neighborhood hypergraph.
I don't think this has been studied before for general graphs.
Here is a paper studying the question when edges are colored:
Béla Bollobás, David Pritchard, Thomas Rothvoß, Alex Scott: Cover-Decomposition and Polychromatic Numbers
And here is one that studies the conflict-free coloring problem for your hypergraph:
Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, Rogers Mathew: Conflict-free coloring on closed neighborhoods of bounded degree graphs
If you replace closed neighborhood with geometric range spaces, then you can find a lot more literature, most notably my own amazing papers.


For computable functions LB from {1,2,3,...} to itself, if

1/(LB(1)) + 1/(LB(2)) + 1/(LB(3)) + 1/(LB(4)) + 1/(LB(5)) + ...  computably converges
and
there is a positive integer m such that for all integers i, if  m < i  then  LB(i) ≤ ni

then the density exists and is computable by using m and the convergence to upper-bound the

probability of being divisible by something beyond the cutoff point.  (To verify that that argument works despite density not being countably additive, do that for each {1,2,...,n} separately.)

I only have a vague suggestion for possibly speeding up the finite part:

Perhaps in most cases you can find a good-enough bound on the

sizes of most of the high-order inclusion-exclusion intersections.


Question 1: For a function $f(n)$ lets say that $f$ is sub-polynomial if $\forall \epsilon > 0, f(n) = O(n^\epsilon)$. The Exponential Time Hypothesis (ETH) states that 3-SAT needs $2^{\epsilon n}$ time for some $\epsilon > 0$. Let's postulate a much weaker version, ``Weak Exponential Time Hypothesis'' (WETH): There exists an $\epsilon > 0$ such that $3$-SAT requires $2^{\epsilon n^\epsilon}$ time.

Claim: If $f$-bounded Independent Set is NP-hard for any sub-polynomial function $f$ then the WETH fails.

Proof: Supose $f$-bounded Independent Set is NP-hard under Turing-reductions for some any sub-polynomial function $f$. Then there exists a constant $c$ and an $O(n^c)$ time algorithm for $3$-SAT with $n$-variables that makes at most $O(n^c)$ oracle calls to $f$-bounded Independent Set with at most $O(n^c)$ vertices.

From this algorithm we make an algorithm for $3$-SAT where the oracle calls to $f$-bounded Independent Set are replaced by the $O(|V(G)|^{k+2})$ time brute force algorithm. The running time of this algorithm is upper bounded by
$O((n^c) \cdot (n^c)^{f(n^c)+2}) = 2^{O(\log n \cdot f(n^c))}$. For any $\epsilon > 0$, pick $\delta = \epsilon / 2c$. Since $f$ is sub-polynomial we have that $f(n^c) = O((n^c)^\delta) = O(n^{\epsilon / 2})$. Therefore the running time of the algorithm is upper bounded by $2^{O(\log n \cdot n^{\epsilon / 2})} = 2^{O(n^{\epsilon})}$, contradicting the WETH.

Question 2: Let's say that $f$ computably tends to infinity if there exists a computable function $g : \mathbb{N} \rightarrow \mathbb{N}$ such that for every $c$ and every $n \geq g(c)$, $f(n) \geq c$.

Claim: If $f$-bounded Independent Set is in P for any function $f$ that computably tends to infinity, then FPT = W[1].

Proof: Assuming the existence of a polynomial time algorithm for $f$-bounded Independent Set we will give an FPT algorithm for Independent Set, proving FPT=W[1].

Given as input $G$ and $k$, set $n = |V(G)|$ and compute $g(k)$. Note that computing $g(k)$ takes time that is only a function of $k$. If $g(k) \leq n$ run the polynomial time algorithm for $f$-bounded Independent Set, this will output the correct answer because $k \leq f(n)$. If $g(k) > n$ then run the brute force $n^{k+2}$ algorithm, this takes time $g(k)^{k+2}$. In total the running time is bounded by $O(n^c + h(k))$ for some constant $c$ independent of $k$ and some function $h$.

Remark: Note that nothing here is specific to Independent Set. The first argument works for any problem with a $O(n^{k^c})$ time algorithm for some $c$, while the second argument works for any decidable problem.


Complexity of intersection of regular languages as context-free grammars

This is a great question and it really lies within my interests.  I'm glad that you asked it Max.

Let $n$ DFA's with at most $O(n)$ states each be given.  It would be nice if there existed a PDA with sub-exponentially many states that accepts the intersection of the DFA's languages.  However, I suggest that such a PDA might not always exist.

Consider the copy language.  Now, restrict it to copying strings of length n.

Formally, consider $n$-copy $:=$ $\{ xx \, | \, x \in \{0,1\}^{n}\}$.

We can represent $n$-copy as the intersection of $n$ DFA's of size at most $O(n)$.  However, the smallest DFA that accepts $n$-copy has $2^{\Omega(n)}$ states.

Similarly, if we restrict ourselves to a binary stack alphabet, then I suspect that the smallest PDA that accepts $n$-copy has exponentially many states.

P.S.  Feel free to send me an email if you would like to discuss further.  :)


Why differential approximation ratios are not well-studied comparing to standard ones despite of their claimed benefits?

I am not familiar with the notion of differential approximation, and I do not have any theory why it is not well-studied.  However, I would like to point out that it is not always desirable to describe the performance of an approximation algorithm by a single measure.  In this sense, I find it difficult to agree that some measure is better than another.

For example, as you stated, minimum vertex cover admits a polynomial-time 2-approximation algorithm whereas it is NP-hard to approximate maximum independent set to any constant ratio.  Although I understand that this can be surprising at first sight, it has a legitimate meaning: (1) minimum vertex cover can be approximated well when it is small but (2) it cannot be approximated well when it is large.  When we state that it is NP-hard to approximate minimum vertex cover (and maximum independent set) with any positive constant differential approximation ratio, we are effectively ignoring the property (1).  It is probably good enough for some purposes to ignore the property (1), but certainly it is not always the case.

Note that we do not always use approximation ratio to describe the performance of approximation algorithms.  For example, to state an inapproximability result based on the PCP theorem in its full generality, we need the formulation based on gap problems.  See my answer to another question for details.  In this case, neither using the standard approximation ratio nor using the differential approximation ratio allows us to state the result in the full generality.


No, bitonic sort is not stable.

For this post I will denote numbers as 2;0 where only the part before the ; is used for comparison and the part behind ; to mark the initial position.
Comparison-exchanges are denoted by arrows where the head points at the desired location of the greater value.

As written in the link that @JukkaSuomela posted a stable sorting network needs to avoid swaps of equal values.

When swapping equal values, the bitonic sorter for two values is already unstable:

0;0 ----- 0;1
      |
      v
0;1 ----- 0;0

Of course, this can be fixed when we don't swap equal values:

0;0 ----- 0;0
      |
      v
0;1 ----- 0;1

However, it could happen that the order of two equal elements is swapped without them being compared to each other.

This is exactly the case in this example of a bitonic sorter for 4 values:

1;0 ------ 1;0 ------ 0;2 ------ 0;2
      ^          |          |
      |          |          v
1;1 ------ 1;1 --|--- 1;1 ------ 1;1
                 ||
                 v|
0;2 ------ 0;2 ---|-- 1;0 ------ 1;0
      |           |         |
      v           v         v
2;3 ------ 2;3 ------ 2;3 ------ 2;3

Although we were careful not to swap elements that compared equal (upper left comparison), the merging pass swapped the order of 1;1 and 1;0 which cannot be corrected later on.

This counterexample proves that bitonic sort cannot be stable.


What NP-complete problems are most similar to integer factoring?

The textbook of Computational Complexity: Modern Approach, by Arora and Barak gives such example:

They define the decision problem Integer Factoring on input of three positive integers,

$\text{Integer Factoring} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$.

They state that Alon and Kilian showed that if integer $p$ is not required to be prime number then the problem becomes $NP$-complete.


Problems not known to be PSPACE-complete

Retrograde Chess. It is $PSPACE$-complete if you are allowed to have arbitrarily many kings and none of them can be in check at any time. If no (or only one per player) kings are allowed, it is known that there are positions that require exponential moves, but the problem is only known to be $NP$-hard.

http://arxiv.org/abs/1409.1530

https://mathoverflow.net/questions/27944/do-there-exist-chess-positions-that-require-exponentially-many-moves-to-reach


Approximation algorithms used in exact algorithms

An example from the parameterized complexity is a kernelization for the vertex cover problem using a theorem of Nemhauser and Trotter.

In the minimum vertex cover problem, we are given an undirected graph G, and we need to find a vertex cover of G of minimum size.  A vertex cover of an undirected graph is a vertex subset that touches all edges.

Here is an exact algorithm that uses an approximation at the first phase.

Phase 1: Set up the integer linear programming formulation of the minimum vertex cover problem.  It's known (or easy to show) that a basic optimal solution of the linear programming relaxation is half-integral (i.e., every coordinate is either 0, 1, or 1/2).  Such a basic optimal solution can be found by a usual polynomial-time algorithm for linear programming (or in this special case, we can formulate it as a network flow problem, so we can solve it combinatorially in polynomial time).  Having such a basic optimal solution, we round it up to obtain a feasible solution to the original integer linear programming problem.  Let S be the corresponding vertex subset.  It's good to note that S is a 2-approximation of the given minimum vertex cover instance.

Phase 2: Find a minimum vertex cover in the subgraph induced by S (for example by an exhaustive search).  A theorem by Nemhauser and Trotter states that this subgraph contains an optimal solution of the original input graph.  So, the correctness of this approach follows.

You may consult a book by Niedermeier on fixed-parameter algorithms for this algorithm.


Terminology about computation and Finite algebra

Such algebras are called functionally complete. Also, what you call terms are actually called polynomials. In standard terminology, term operations have a more restricted definition that allows variables and the basic operations $f_i$, but not constants from $E$. Algebras that satisfy the stronger condition that every operation is represented by this kind of a term are called primal. See e.g. Burris&Sankappanavar, A Course in Universal Algebra.


Looking for papers and articles on higher-order sequent systems

Again I'm not exactly sure what you are looking for because there are potentially many "similar" systems, but for recent work that I think is very related you can read Part II ("Mixing Derivability and Admissibility") of Dan Licata's thesis, as well as Constructive provability logic by Rob Simmons and Bernardo Toninho.


Counting reversibly using few FullAdders and little work space

Here is a construction with $3N + O(\lg N)$ adder computations/uncomputations and $2 \lg(N)$ ancilla usage.

Divide the input into $N/\lg N$ groups of size $\lg N$.
Allocate a result register of size $\lg N$.
For each group $g$:

Use the naive strategy to compute $g$'s weight using $\lg N$ adder computations and space.
Add the weight into the result register using $\lg N$ adder computations and uncomputations.
Uncompute $g$'s weight using $\lg N$ adder uncomputations.

The result register now contains the total weight.

The inner loop uses $3 \lg N$ adders, and runs $N / \lg N$ times, for a total of $3N$ adders. Half of the $2 \lg N$ ancilla bits are for the result register, and the other half are for the group weight computations.

Basically, using groups of size $\lg N$ instead of $\sqrt{N}$ gives an exponential improvement in space usage but only a constant factor loss in adders.


Actually, the problems BBB and BBB-F above are not currently specified as languages or decision problems (the black box is not explicitly given to us as a binary string of some kind, is it?), so these problem cannot be in NP, PP, PSPACE, or even decidable/undecidable. A fundamental property of languages in the computability/complexity sense is that no bit of the initial input is "hidden" from you.

As suggested by M. Alaggan, the problems BBB and BBB-F are probably closest to the "learning with membership queries" framework, where one can only access a target function by querying it at various points and tries to infer the function. Nevertheless, both problems require superpolynomially many queries to the black box in the worst case, so they are both "intractable" in that sense. For BBB and BBB-F, your intuition is correct: it requires $\Omega(2^n)$ queries just to check that $B$ is not the "all-zeroes" function.

Even if you assume that the black box in these problems can be indeed modeled by some polynomial size circuit, it is highly unlikely that this helps. For example, if pseudorandom functions exist (a common cryptographic assumption) then for all $n$ there are polynomial size circuits $C_n$ with $n$ bits of input that cannot be distinguished from a completely random $n$-bit function, by any probabilistic subexponential time algorithm with black-box access to $C_n$. It follows that no subexponential time algorithm can efficiently reconstruct $C_n$ just from queries to $C_n$.


Incremental Maximum Flow in Dynamic graphs

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

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

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

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

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

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

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


Find worst case input for a program solving an NP-hard problem

See Fast Reduction from RSA to SAT for some ways to get hard instances of SAT.  Then, you can use the known reductions to turn these into hard instances for ILP.  You could also use the SAT instances at http://www.satcompetition.org/, too.


Maximizing a convex function with linear constraints

Your problem in revision 3 of the question is NP-hard by a reduction from the vertex cover problem.  Slightly more precisely, even if aip’s are restricted to 0 or 1, it is NP-complete to decide whether the maximum value in the question is equal to N or less than N.  (Note that the maximum value cannot be greater than N if aip’s are 0 or 1.)  The detail is left as an exercise.


Fastest known algorithm for finding simple paths through given set of vertices


Deciding DDH based in partial information

Given the latest formulation of your question, this appears to be impossible. Consider the case where you have (families of) cyclic groups $\mathbb{G}$ and $\mathbb{H}$, where $\mathbb{G} \ne \mathbb{H}$ and we have a bilinear map $e: \mathbb{G} \times \mathbb{H} \to \mathbb{T}$. Under the XDH assumption we can suppose that DDH is hard in $\mathbb{G}$ and discrete log is hard in $\mathbb{H}$.

Let $g$ be a generator of $\mathbb{G}$ and $h$ be a generator of $\mathbb{H}$.
Then define $f : \mathbb{Z}_{|\mathbb{G}|} \to \mathbb{H}$ as $f(a) = h^a$.

Now given $(g, g^a, g^b, g^X, z=f(a)=h^a)$, we can easily determine whether $X = ab$ by checking $e(g^b, z) \overset{?}= e(g^X,h)$. (You can also similarly verify the correctness of $z$ if you like.) Yet, it would seem unlikely that an extractor could extract $a$ or $b$ from such a tuple. Extracting $b$ is obviously equivalent to discrete log; if there is a distortion map from $\mathbb{H}$ to $\mathbb{G}$ (there cannot be one in the other direction) then extracting $a$ is equivalent to discrete log (in $\mathbb{H}$).


List the $k$-faces of an $n$-dimensional simplex

See chapter 3 of Nijenhuis and Wilf, "Combinatorial Algorithms" (the entire book is available free online and despite its age contains many useful algorithms).


Better approximation for special case of 3-hitting set

What you've defined is the vertex cover problem for 3-uniform hypergraphs. Khot and Regev showed that if the unique games conjecture is true, then it is NP-hard to get an approximation of $3-\epsilon$ for this problem.


EDIT (Jan 2019): Lemma 2 as currently stated below is wrong. (Indeed, given any instance, adding a single edge with a single type of very large cost will not change the instance but will yield $N(I)=1$, in which case the lemma claims that the algorithm will give an optimal solution.  The proof is wrong because the function $\Phi$ defined there is not supermodular.)  I do believe that the proof can be fixed, and the algorithm there can be patched, to obtain an $O(\log n)$-approximation algorithm.  I'll correct it  hopefully later this month. -NY

Your problem generalizes Set Cover, and in turn is a special case of the classical problem of minimizing a linear cost function subject to a submodular constraint, a problem for which the greedy Set-Cover algorithm and its logarithmic approximation ratio naturally extend (as observed e.g. by Wolsey in the 1980's).  Consequently, there is a poly-time log-approximation for your problem, and (unless P = NP) that is the best you can do. Here are the details.

Given any instance $I$ of your problem, define $N(I)$ to be the minimum, over all source-to-destination paths $p$, of the sum, over the edges $e$ in $p$, of the number of labels $F_i$ that $e$ has.  Unless P=NP, the best approximation-ratio obtainable for your problem is $\ln N(I)$ (up to lower-order terms). The reasoning is in two steps: a hardness result, then a poly-time $\ln N(I)$-approximation algorithm.

Here's the hardness result, showing that your problem subsumes Set Cover.

Lemma 1. Unless P=NP, the problem has no $((1-\epsilon)\ln N(I))$-approximation algorithm for any $\epsilon>0$.

Proof. We give an approximation-preserving reduction from unweighted Set Cover.  Given an unweighted Set-Cover instance $(S_1, S_2, \ldots, S_m)$ on a universe $U=\{1,2,\ldots,n\}$, construct a multigraph with vertex set $\{1,\ldots,n,n+1\}$ where, for each element $i\in U$, for each set $S_j$ containing $i$, there is an edge $(i, i+1)$ with a single label $F_j$.  Set $C(F_j) = 1$ for each $j$.

(Note: If a multigraph is not allowed, one can simply split each $(i, i+1)$ with label $F_j$ into a path $(i, v(i,j), i+1)$ where $v(i,j)$ is a new vertex, edge $(i, v(i,j))$ has label $F_j$, and edge $(v(i,j), i+1)$ has no label...)

Then for any path $p$ from vertex $1$ to vertex $n+1$ there is a set cover $C(p) = \{S_j : F_j \text{ is the label of some edge on } p\}$ of size equal to the cost of $p$, and vice versa.  Also, $N(I)$ for this instance $I$ equals $n$.

So, if there is a $(1-\epsilon)\ln N(I)$-approximation algorithm for your problem, then there is a $(1-\epsilon)\ln n$-approximation algorithm for Set Cover.  Unless P=NP, there is no such algorithm. $~~~\Box$

EDIT: The remaining part is wrong, see comment at top.

Here's the upper bound, showing that your problem is a special case of minimizing a linear cost function subject to a submodular constraint.

Lemma 2. The problem has an $H_{N(I)}$-approximation algorithm, where $H_i \approx \gamma + \ln i$ is the $i$'th Harmonic number.

Proof. Fix an instance $I$ of the given problem. Assume without loss of generality that each edge in the graph has only one label.  (Otherwise, for any edge having, say, labels $F_{i_1}, F_{i_2},\ldots,F_{i_k}$, replace the edge by a path of $k$ edges, where the $j$th edge has label $F_{i_j}$.  This does not change $N(I)$.)

Given any set $S$ of labels, define $\phi(S)$ to be the minimum, over all paths $p$ from the source to the destination, of the number of edges on $p$ whose label is not in $S$.  Define the cost of $S$ to be the sum of the costs of the labels in $S$. Then

$\phi$ is supermodular,  $\leftarrow$ EDIT: THIS IS NOT NECESSARILY TRUE
$\phi(\emptyset) = N(I)$,
$\phi(S) = 0$ if and only if there is a path from the source to the destination that uses only labels in $S$, and
the cost of $S$ is the cost of the labels in $S$.

Now apply Wolsey's generalization of the greedy-set-cover algorithm (for minimizing a linear function subject to a submodular constraint) to find an approximately minimum-cost set $S$ with $\phi(S) = 0$.  That algorithm is:

$S \leftarrow \emptyset$
while $\phi(S) > 0$:
. . choose label $F_i$ maximizing
$\displaystyle\frac{\phi(S) - \phi(S\cup\{F_i\})}{C(F_i)}.$
. . add $F_i$ to $S$
return $S$

That algorithm is known to compute a solution $S$ of cost at most $H_D$ times the minimum, where $D = \max_{S,F_i} \{ \phi(S)-\phi(S\cup\{F_i\}) \le \phi(\emptyset) = N(I)$.

By inspection the algorithm can be implemented to run in polynomial time.

And, given the set $S$ with $\phi(S)=0$, one can easily compute in poly-time a path $p$ from the source to the destination with cost at most the cost of $S$.  $~~\Box$

Did I miss anything here?

Wolsey's original paper:

[1] L. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385–393, 1982. (See here for a summary.)


Ecology and evolution through the algorithmic lens

Hmmm. As far as evolutionary dynamics/game theory goes, my personal opinion is that the Livnat et al paper you mentioned, while very nice work, doesn't seem to fall "outside" the standard mathematical approach to evolutionary game theory (see work by e.g. Martin Nowak's group, such as the '05 paper "Evolutionary Dynamics on Graphs").

So the two claims I would make are: First, while this is some great work in Evolutionary Dynamics that happens to be done by computer scientists, I would not personally place it inside Theoretical Computer Science or as being all that closely related to TCS, except for the preexisting relationship between evolutionary and algorithmic game theory. Second, if you're inclined to disagree, then you may be surprised how much the field of Evolutionary Dynamics already shares/shared with TCS philosophically (but I'm still not sure the techniques are that similar).

In general, I would be inclined to say that there is not any work along these lines, including the reference you mentioned, that fit what you seem to be looking for, which I think is a deep connection between some core concept/technique in TCS and the study of evolution. (Of course, if anyone has a differing opinion, please say so!)

I do think that evolutionary game theory or evolutionary dynamics could benefit from more algorithic approaches, (such as Livnat et al). For a particular example, I see possible nice extensions for considering evolvable agents with (limited) computional abilities, as modeled by e.g. finite state machines. This would allow us to study the evolution of discrete agents with more complex conditional strategies such as tit-for-tat. I've looked into this a bit and heard of some preliminary work along these lines but don't have any references to cite.

But even this example is a rather straightforward application, so results of this sort probably still wouldn't answer your question.

I have much higher hopes on the other hand for learning theory, which could someday make nice connections to evolutionary dynamics as well. But, I'm not very familiar with those results so I will leave that for others to comment on.

(Edit) One potential connection that should be mentioned is the known relationship of learning (e.g. the "expert's problem") and convergence to equilibria in repeated games. Specifically, for example (see Aaron Roth's comment for details), in a repeated game, if all players are playing no-regret strategies, then the past distribution of actions converges to a coarse correlated equilibrium of the single-round game. There may be something interesting and novel to say about this as viewed through the evolutionary game theory lens; I'm not sure.


Analysis of the synergy of two algorithms in comparison to their simulation in parallel

In Willard's Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time, he references a preliminary version (of the linked paper) entitled "Surprisingly efficient search algorithms for nonuniformly generated files" appearing at the 21st Allerton Conference on Communication Control and Computing in 1983, pp. 656-662. I can't find this paper on the web, but in the later (linked) version above, he says that the older paper shows that the synergy between binary and interpolation search can reduce search time to $o(\log n)$ for certain non-uniform distributions of record keys.

Specifically, call a PDF $\mu$ regular if there are $b_1, b_2, b_3, b_4$ such that $\mu(x) = 0$ for $x < b_1$ or $x > b_2$ and $\mu(x) \geq b_3 > 0$ and $|\mu\prime(x)| < b_4$ for $b_1 \leq x \leq b_2$. For data produced by regular PDFs, interpolation search takes $\Omega(\log n)$ expected time, while binary search takes $\Theta(\log n)$ expected time. Interleaving them, however, takes $O(\sqrt{\log n})$ expected time.

You may also be interested in Willard and Reif's "Parallel processing can be harmful: The unusual behavior of interpolation search", which shows that "parallel processing before the literally last iteration in the search of an unindexed ordered file has nearly no usefulness".


Minimum Spanning tree on a complete "random" graph

Let's consider a general model in which $L_n(\mu)$ is the (random) length of an MST on $K_n$, where the weight of each edge is sampled independently from a probability distribution $\mu$. When $\mu$ is uniform on $[0,1]$, Frieze showed that $\lim_{n \to \infty} \mathbb{E}[L_n(\mu)] = \sum_{k\ge1}{\frac{1}{k^3}} = \zeta(3)$. Steele showed that for a $\mu$ with CDF $F$ which is differentiable from the right at $0$, this same limit is $\zeta(3)/F'(0)$. In particular, for $\mu$ an exponential distribution with parameter $1$, the expectation is once again $\zeta(3)$ in the limit.

It follows from general results that $L_n(\mu)$ is tightly concentrated around the mean. For example, in his survey McDiarmid shows how to use Talagrand's inequality to prove that, in the case of $\mu$ uniform on $[0,1]$, for any $t$ there exists a $\delta(t)$ such that $\Pr[|L_n(\mu) - \zeta(3)| > t] < e^{-\delta(t) n}$. I am fairly certain that the argument extends to the case of an exponential random variable.

Central limit theorems are also available. Janson proved that $\sqrt{n}(L_n(\mu) - \zeta(3))$ converges in distribution to a Gaussian with mean $0$ and constant variance. (The constant was computed exactly by Wastlund.) This is again shown for uniform $\mu$, but I think it should extend to exponential.

BTW, Steele's result is basically a reduction to the uniform case. Say $\mu$ has a continuous CDF $F$. Then, if $X$ is distributed according to $\mu$, $F(X)$ is uniform on $(0,1)$, and, moreover, $F$ is a monotone function. So, if you apply $F$ to the random weights of your graph, you don't change the MST, and you change the weights to be uniform. The other key observation is that all weights in the MST will be fairly small, so you only really care about the behavior of $F$ close to $0$.


Continuation passing transform of binary functions

The closest I've seen to an answer to this question is the first picture in the Gallery of Doctor Melliès,

illustrating the map
$$\neg\neg A \otimes \neg\neg B \longrightarrow \neg\neg(A \otimes B)$$
which exists in any dialogue category (i.e., a monoidal category with closures into a fixed object).  Note that the left-to-right CPS transform of general binary functions reduces to applying this map and then composing with the functorial action of the double-negation monad.

The illustration basically follows the standard conventions of string diagrams (modulo the polarizations of the wires, which are meant to indicate the flow of control).  In particular, the map is constructed in three steps: twice applying the strength ($\kappa\wedge$) of the monad induced from the negation self-adjunction, and then applying the counit of the adjunction ($\epsilon$).  At this level of abstraction, the derivation is generic for any adjunction giving rise to a strong monad, and you could then ask for a more abstract characterization of such adjunctions, which Melliès has also written about.


Approximation algorithms for min vector subset-sum over GF(2)

Dumer, Miccancio and Sudan showed that the minimum distance of a linear code is not approximable to any constant factor in randomized polynomial time, unless $\mathsf{NP} = \mathsf{RP}$. The minimum distance problem is the same as your problem if the $v_i$'s form the columns of the parity check matrix and $y = 0$.


Let $\mathbb K$ be a field of characteristic $0$ or at least $d(d-1)+1$, and $p\in\mathbb K[x_1,\dotsc,x_n]$ be a polynomial of total degree at most $d$. If $d$ is fixed and $n$ is growing, one has the following complexity bounds for the reduction of the factorization of $p$ to the factorization of a degree-$d$ univariate polynomial: (The notation $\tilde{\mathcal O}(\cdot)$ ignores logarithmic factors.)

Deterministic algorithms:

$\tilde{\mathcal O}\left( \binom{n+d}{n}^4 \right)$ field operations, using naive multiplication algorithms;
$\tilde{\mathcal O}\left( \binom{n+2d-2}{n-1} d^\omega \right)$ field operations, if fast multiplication algorithms are availaible, where $2<\omega\le 3$ is an admissible exponent for linear algebra.¹

Probabilistic algorithms:

$\tilde{\mathcal O}\left(\binom{n+d}{n}\right)$ field operations, if fast multiplication algorithms are available.

Then, one has to factorize a univariate degree-$d$ polynomial. The complexity of this step does not depend on $n$ anymore, so the above bounds remain valid for the complete factorization algorithms. The only difference is in positive characteristic: Since no deterministic polynomial-time algorithm is known to factor a univariate polynomial, even the deterministic reduction yield a probabilistic algorithm. Nonetheless, if $d$ is really fixed and small, one can replace the probabilistic polynomial-time algorithm by a deterministic exponential-time one.

Note that the probabilistic bound $\tilde{\mathcal O}\left(\binom{n+d}{n}\right)$ is optimal up to logarithmic factors since $\binom{n+d}{n}$ is the size of the input.

More details can be found in the paper Improved dense multivariate polynomial factorization algorithms of Grégoire Lecerf (link without paywall).

Another reference, especially for fields of small characteristic, is E. L. Kaltofen & G. Lecerf, Factorization of multivariate polynomials (link without paywall), chapter 11.5 of G. L. Mullen and D. Panario, editors, Handbook of finite fields.

¹ The result needs to assume that $\omega>2$.


Is there any language for which a perfect optimization is decidable?

Certainly not for a Turing-complete programming language, following up on D.W. and David's comments. Consider a program in this language that simulates a Turing Machine $M$ (where $M$ is hardcoded into the program) and outputs zero if $M$ halts.

When your optimizer receives such a program where $M$ halts, it must output some least-cost program that always returns zero (because the original program always returns zero). If $M$ doesn't halt, then your optimizer can output any program that runs forever (as the original program always runs forever).

OK, now let's show that your optimizer would allow us to solve the halting problem. Suppose that the statement "return zero" has cost $C$. (Thus, we know that any least-cost program that always returns zero has cost at most $C$.) Given a Turing Machine $M$, construct the program that simulates $M$ and outputs zero if $M$ halts. Feed it to the optimizer. Run the output program for up to total cost (time) $C+1$. If it has output zero, then the original program halts. If not, the original program does not halt.

...I agree with user17410's suggestion to look at the primitive recursive functions as they are likely to be able to cover most problems we want to solve practically.


Why backward symbolic execution is so unpopular?

Forward SE is easier to implement, composes better with other testing methods, and thus is more scalable.

Usually, on industrial-scale workloads, it's not possible to enumerate all paths in the program under test -- there are simply too many paths. So we need some way to deal with this and sample only a subset of paths, while still having a reasonable chance of finding bugs.  With forward SE, there is an easy way to deal with this: if you have a test case, you can run the program concretely for a while, then switch to forward SE partway through execution.  Or, you can run the program concretely until it terminates, recording the path it took, and use SE to generate new inputs that will cause it to go down a similar but not identical path.  The state-of-the-art tools tend to combine fuzzing (random testing) with SE, and this approach is a nice way to enable that sort of composition.

Second, forward SE has implementation benefits.  Inevitably there are some kinds of operations that you can't or don't want to model symbolically (e.g., floating point, system calls, etc.).  With forward SE, that's no problem: you just execute the program concretely and keep only part of the state symbolic, treating the results of those operations as concrete (you concretize by forcing their inputs to match the observed concrete value, and same for the outputs).  It's usually not possible to do that concretization with backwards SE.  So forward SE allows "concolic execution", where some of the state of the program is concrete (a single value) and some is treated as symbolic (represented by some variables that we accumulate constraints on).

Finally, many modern tools are path-based: they consider a single path through the program, and construct a path expression -- a set of constraints that characterize the set of inputs that will cause the program to follow that path.  This is convenient for multiple reasons.  When you take this approach, the differences between forward SE and backwards SE largely disappear, as there is no state merging; you only consider a single path at a time.  So if you're taking this approach, in some sense you don't need to choose between the two, or the choice is inconsequential (both are basically equivalent) -- you can choose whichever you want based on which one you find a more convenient  way to think about it.


What is the current known hardness of Graph Isomorphism?

Graph Isomorphism is hard for DET, the class of problems which are $NC^1$ reducible to the determinant. See "On the Hardness of Graph Isomorphism" by Jacobo Toran. http://epubs.siam.org/sicomp/resource/1/smjcat/v33/i5/p1093_s1?isAuthorized=no

It seems this is the strongest hardness result to date.


How can AIC converge in the limit when even 2 parameter models can have infinite VC dimension?

I tried to find a simple and accessible analysis of AIC. A definitive work seems to be Barron, Birgé, Massart, "Risk bounds for model selection via penalization"
https://link.springer.com/article/10.1007/s004400050210
though I can't vouch for accessibility.

Instead, let's analyze your sinusoids example. Suppose I have a parametric class of densities over $[0,1]$, parametrized by a single parameter $\alpha$, which is the frequency of the sinusoid. I take the positive part of the sinusoid and normalize the function to integrate to $1$ -- now it's a density. I can choose the $\alpha$ via any of the model selection techniques, including maximum likelihood and AIC. For any fixed $\alpha$, I think all of these will converge (maybe even almost surely) to the true $\alpha$. So why doesn't this contradict the fact that this family of functions (when thresholded at $0$) has infinite VC-dimension?

It's all about the order of quantifiers. Finite VC-dimension means that you can specify a sample size $m_0(\epsilon,\delta)$ that will suffice to achieve $\epsilon$-accuracy at $\delta$-confidence -- in advance of seeing any data. In our model selection example above, you will not be able to specify such an $m_0(\epsilon,\delta)$.

There are certainly infinite-VC classes that are learnable in this sense, which is weaker than PAC. For any target concept and distribution on the integers, you will eventually see enough examples to know the true concept to any desired accuracy -- you will just not be able to specify this sample size independently of the distribution and the target concept. (See Ex. 0.2(c) here
https://www.cs.bgu.ac.il/~asml162/wiki.files/hwk0.pdf
).


Optimal upper bound on the number of non-isomorphic graphs with certain parameter

This is just a partial answer mainly answering just $a)$ and $b)$

The number of non-isomorphic graphs is asymptotically equivalent to $$\frac{2^{n \choose 2}}{n!}$$ Almost all graphs are connected (in fact $k$-connected for any constant $k$) hence this answer your first question.
This is an open problem. If we restrict ourselves to trees then it is well known that almost all trees are cospectral hence that for every tree $T$ there exist another non-isomorphic tree $T'$ with equal adjacency spectrum. I believe there is no other result generalizing this one.  There is plenty of literature on this subject, check on Google for "cospectral graphs".

It is conjectured that almost all graphs are determined by their spectrum but no real evidence for this fact is known. The conjecture is of course motivated by the isomorphism problem.

The number (and proportion) of cospectral graphs on $n=12$ vertices has been computed recently and can be found here.


The log of the partition number is a lower bound on the deterministic communication complexity and the square of the log of the partition number is an upper bound. In other words, if $CC$ is the communication complexity, then we know that $\log_2 p \leq CC \leq (\log_2 p)^2$: this is Theorem 2.11. in the Kushilevitz-Nisan monograph. It is an open problem whether $CC = \Theta(\log p)$, and the biggest known gap is a factor $2$.

So $p < r^{\log^d r}$ for a constant $d$ implies that the communication complexity is at most $\log^{2d+2} r$. In other words there exists such a constant $d$ if and only if the log rank conjecture is true. I believe the best we know is $p < r^{C\sqrt{r}}$ for a constant $C$, by a recent result of Lovett.


In the months since I asked this question, I think I have found a sensible answer.

Often, the type of relations considered do not compose. For instance, if your notion of a relation $R : D \to E$ between $\omega$CPOs is an $\omega$-chain complete subset of $|D|\times |E|$, then the relation $R : \omega + 1 \to \mathbb{N}$ between the ordered naturals plus infinity $\omega+1$ and the flat CPO of naturals $\mathbb{N}$ given by $R(n,n)$ holds and nothing else, then $R$ is admissible, as is its converse, but the composite $R;R^T : \omega+1 \to \omega + 1$ is not chain-complete, since $n R;R^T n$ for every natural, but we don't have $\omega R; R^T \omega$.


I believe that the formula with the quantifier prefix you want to achieve are strictly less expressive than the two-variable logic with counting quantifiers. So there is no hope that you can translate any C2 formuale into such a form.
Similar types of Scott-normal forms were obtained in:

Bartosz Bednarczyk, Witold Charatonik: Modulo Counting on Words and Trees. FSTTCS 2017 [for modulo-counting quantifiers but without binary predicates]
Michael Benedikt, Egor V. Kostylev, Tony Tan:
Two Variable Logic with Ultimately Periodic Counting. ICALP 2020 [for ultimately-periodic counting]

Moreover, note that the normal form by Ian is somehow more useful than the normal form by Graedel and Otto, since under the binary encoding of numbers in the thresholds it requires an exponential blow-up (while the Ian's version can be obtained in poly-time).
Edit: Extended description of the above paragraph. Consider a formula $\exists^{=c} \varphi$ with a threshold $c$ encoded in binary, i.e. it means that to encode the value 1000 we need approximately $log(1000)$ bits rather than 1000. Hence, the value of $c$ is exponential in $|\varphi|$ rather than polynomial. In Grädel&Otto approach you need to introduce a fresh binary relation for each witness of $\varphi$, which increase the size of the formula exponentially (by c). The translation into Ian's normal form increases the size of the formula only polynomially.
You might be also interested in Gaifman's normal forms for FO extended with various kinds of counting. Here is the most recent paper, but you might check other papers by Dietrich Kuske and his co-authors:
http://eiche.theoinf.tu-ilmenau.de/kuske/Accepted/HeiKS18.pdf


Is the isomorphism problem between posets represented by DAGs GI-complete?

Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI.

The problem for partial orders is also GI-complete: We can reduce bipartite graph isomorphism (which is GI-complete) to 2 instances of DAG isomorphism where the DAG equals its transitive closure by considering two canonical ways to turn a bipartite graph into a DAG, that is, either directing all edges from partition 1 to partition 2 or directing all edges from partition 2 to partition 1.


Major open problems on polynomial kernel (non) existence

Currently, I would say the 3 major open cases are:

Directed feedback vertex set (make a given digraph acyclic by deleting at most k vertices) parameterized by the size of the solution
Planar Vertex Deletion (make a graph planar by deleting at most k vertices)
Edge Multiway cut (given an undirected graph and a list of terminals, delete at most k edges to ensure all the terminals end up in a different connected component)

For all of these, the relevant parameter is the size of the solution. You can have a look at the open problem list from the 2013 Workshop on Kernelization ( http://worker2013.mimuw.edu.pl/slides/worker-opl.pdf ) for others. Pointers to other (but older) open problem lists in parameterized complexity can be found here: http://fpt.wikidot.com/open-problems .


What is the counting complexity of random 2-SAT?

Perhaps this paper can help you:

New Worst-Case Upper Bound for #2-SAT and #3-SAT with the Number of Clauses as the Parameter by J. Zhou, M. Yin, C. Zhou (2010).

And this one that studies the structure of the set of solutions of a random 2-SAT instance: Satisfying Assignments of Random Boolean Constraint Satisfaction Problems: Clusters and Overlaps by G. Istrate (2007)


What are good references to understanding the proof of the PCP theorem?

Both Goldreich's complexity textbook and Arora and Barak's complexity textbook have chapters devoted to explaining the proof of the PCP theorem (with pictures!).

Also, Dinur's paper is worthwhile to read, if you haven't tried to tackle it yet. It's at least more approachable (in my opinion) than the original proof, and you can get a good intuition for how the proof works by skimming just the first 12 pages (and delve into the technical proofs contained in the latter chunk of the paper later, if you prefer).


Effect of different graph operations at algebraic connectivity of graph laplacian?

Intuitively operations that preserve connectivity will not decrease the eigenvalues. For example, adding edges to the graph does not decrease the connectivity.

In general, if H is a subgraph of a graph G, by interlacing we know that the i-th largest Laplacian eigenvalue of H is no larger than the i-th largest Laplacian eigenvalue of G. A proof can be found in Proposition 3.2.1 of the book "Spectra of graphs" by Brouwer and Haemers. Note that the definition of Laplacian used in the book is not normalized; it has node degrees on the diagonal and -1 (or 0 if there is no edge) in the off-diagonal entries.


Where can I find a copy of Guy Jacobson's thesis "Succinct Static Data Structures"?

You could try writing CMU to ask for a copy of the technical report version; Jacobson's thesis is technical report number CMU-CS-89-112.  No idea if this would actually work though.

It's also possible, but unlikely, that Jacobson's advisor has an electronic copy.

As a last resort, you (or your advisor, or your university library) can order a copy from ProQuest, the entity formerly known as University Microfilms. [Sorry, there's no way to link directly; just search for "Guy Jacobson".]  A PDF copy costs \$37; a softbound paper copy costs \$59.


The distribution of the multiplication of independent Gaussians is not close to a Gaussian.

There are various ways to convince yourself in this. E.g., compute the expectation and the variance of the product from the expectation and the variance of the individual variables.
This gives you a candidate Gaussian if there were a Gaussian approximation.
Now, think of some simple properties of the product (e.g., the probability it is 0) and see if your candidate is good enough as an approximation.


$\mathsf{FP}^{\mathsf{NP}[\log n]}$ versus $\mathsf{FP}^{\mathsf{NP}||}$

This is an open problem, it implies $\mathsf{NP} = \mathsf{RP}$ among other things.
See the following paper:

Alan Selman. A Taxonomy of Complexity Classes of Functions. Journal of Computer and Systems Sciences 48 (1992), pp. 357-381.

You can get it here:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.7438&rep=rep1&type=pdf


Example of R and G when $R \subseteq L(G)$ is undecidable

Given an $R$ and a $G$, one can easily construct a TM which outputs whether $R \subseteq L(G)$.

(Consider two TMs, one that just rejects and one that just accepts. If not the first, then the second TM would definitely be correct.)

What is not possible is this: Give a TM that takes as input any $R$ and any $G$ and accepts iff $R \subseteq L(G)$ and rejects otherwise.

Note that the same is true for the halting problem. Given a TM $M$, it is decidable whether $M$ halts or not. (The same two TMs mentioned above would do.) What's undecidable is the general problem of being able to decide whether a TM given as input halts or not. (A single machine that can take any TM as input and be correct on all of them.)


Recovering a rank-one matrix from its eigendecomposition after randomized rounding

I think that, as the question is currently formulated, the answer is no.

Here is a proposed counterexample. Fix arbitrarily large $n$.  Take $xy^T$ to be the matrix having each coordinate equal to $\delta/n$, for a sufficiently small constant $\delta>0$ (so $x$ is uniform). $A$ is then a random matrix where each entry is $1$ with probability $\delta/n$ and otherwise zero.

Here is a proof that this is indeed a counterexample to the conjecture in the post.

Lemma 1. With probability $\Omega(\delta)$, $A$ has a dominant eigenvector $v'$ such that $$\Big\|\frac{x}{\|x\|_2} - \frac{v'}{\|v'\|_2}\Big\|_\infty = \Big|\frac{1}{\sqrt n} - 1\Big| \approx 1.$$

Proof. Consider the directed graph $G=(V,E)$ with adjacency matrix $A$, that is $V=\{1,\ldots,n\}$ and $E=\{(i,j) : A_{ij} = 1\}$.  So $G$ is a random digraph where each possible edge (including self-loops) is independently present with probability $\delta/n$.

Let $X$ be the event that $G$ has a directed cycle of length 2 or more.  By the naive union bound, the probability that there is such a cycle is less than $\sum_{\ell\ge 2} n^\ell (\delta/n)^\ell = \sum_{\ell\ge 2} \delta^\ell = \delta^2/(1-\delta)$.

Let $Y$ be the event that $G$ has at least one vertex $i$ with a self-loop but no other outgoing edges.  (That is, $A_{ii}=1$ and every other entry in row $i$ is zero.)  By calculation, event $Y$ happens with probability about $1-e^{-\delta/e^\delta} = \Omega(\delta)$.

So the probability that $Y$ happens and $X$ does not is $\Omega(\delta) - O(\delta^2) = \Omega(\delta)$.
Assume that $Y$ happens and $X$ does not.  Because $Y$ happens, there is a row $i$ of $A$ where $A_{ii} =1$ but all other entries are zero.  So $A$ has an eigenvector $v'$ where $v'_{i} = 1$ is the only non-zero entry.  But $x_i/\|x\|_2 = 1/\sqrt n$, so, for this eigenvector,
$$\Big\|\frac{x}{\|x\|_2} - \frac{v'}{\|v'\|_2}\Big\|_\infty = \Big|\frac{1}{\sqrt n} - 1\Big| \approx 1.$$

To finish, we show that $v'$ is a dominant eigenvector, that is, that the largest eigenvalue of $A$ is 1.  Consider any eigenvector $v$.  Let $\lambda$ be the eigenvalue of $v$, so $Av = \lambda v$.  Let $C=\{i : v_i > 0\}$ be the support of $v$.  Consider the subgraph $G_C$ induced by $C$ (as a set of vertices in $G$).  Since $X$ does not happen, $G_C$ has no cycle of length 2 or more, so each strongly connected component of $G_C$ is a single vertex.  Hence, $G_C$ contains a single vertex $i$ having no incoming edges in $G_C$, except possibly a self-loop.  Now, because $v$ is an eigenvector with support $C$, this implies $A_{ii} v_i = \lambda v_i$.  Since $v_i>0$ this implies $\lambda =A_{ii} \in\{0, 1\}$. $~~\Box$

I think that the above argument suggests that $G$ can have multiple dominant eigenvectors (each with eigenvalue 1), and that some of those eigenvectors could have larger support --- size $\Omega(\log n)$, maybe? And such an eigenvector $v$ could have $\max_i v_i/\|v\|_2 = O(1/\log n)$, and so could meet the proposed condition for being "the same" as $x$.  But see Remark 1 below.

Remark 1. The condition currently suggested in the post for $x$ and $v$ to be "the same", namely,
$$\Big\|\frac{x}{\|x\|_2} - \frac{v}{\|v\|_2}\Big\|_\infty \le \epsilon,$$
seems to be too weak. It can only be violated if $x$ or $v$ has at least one very large coordinate.

For example, suppose the first $n/2$ coordinates of $x$ are 1 and the rest are zero, while the first $n/2$ coordinates of $v$ are zero, and the rest are 1.  Then $x$ and $v$ are orthogonal, so arguably not at all "the same".  But $x_i/\|x\|_2 \le \sqrt{2/n}$ and $v_i/\|v\|_2 \le \sqrt{2/n}$, so, assuming $n \ge 2/\epsilon^2$, the suggested condition is satisfied.

Of course, if the condition were strengthened, the counterexample above should still hold...

Remark 2. Tangentially, the behavior of eigenvectors of sparse random graphs (where the edge probability is around $1/n$ or so), seems to be fairly complicated.  Among the references I found, the most relevant to the argument was [1].  It considers the case when $\delta$ is just below 1, and shows that each strongly connected component of $G$ is either a single vertex or a cycle of constant size (possibly with self-loops).

The case when the edge probability is slightly larger, above $\log(n)/n$, say, seems to be more well studied, and in that case I think (although I'm not sure) that the eigenvectors of $G$ are more uniform.  Search Google Scholar for "eigenvectors of sparse random graphs".

[1]  Luczak, T. and Seierstad, T. G.. The critical behavior of random digraphs. Random Structures and Algorithms 35, 271-293 (2009).
http://folk.uio.no/taralgs/artikler/digraph.pdf


Hardness of approximating acyclic chromatic number

It is not a gap-preserving reduction, but an approximation factor preserving reduction. The comment by Manuel Lafond is very close to an answer (but I cannot concur with the opinion that having same optimal values suffices; that is why I am writing this as an answer)

Quoting from Vazirani (the notation $s_1,s_2$ is mine):

  Let $\Pi_1$ and $\Pi_2$ be two minimization problems. An approximation factor preserving reduction from $\Pi_1$ to $\Pi_2$ consists of two polynomial time algorithms, $f$ and $g$, such that

  for any instance $I_1$ of $\Pi_1$, $I_2 = f(I_1)$ is an instance of $\Pi_2$ such that
  OPT$_{\Pi_2}(I_2) \leq$ OPT$_{\Pi_1}(I_1)$, and
  for any solution $s_2$ of $I_2$, $s_1= g(I_1 ,s_2)$ is a solution of $I_1$ such that
  obj$_{\Pi_1}(I_1,s_1) \leq$ obj$_{\Pi_2}(I_2,s_2)$.

Note: obj$_{\Pi_1}(I_1,s_1)$ simply means the value of the objective function for instance $I_1$ for solution $s_1$. Here, for example it is the number of colours used by a colouring($s_1$) of a graph($I_1$).

The whole point of this reduction is that $\chi(G)=\chi_a(H)$. For $3\leq p\leq \Delta$, it is proved that $\chi(G)\leq p\iff \chi_a(H)\leq p$. Also, $\chi(G)\leq \Delta+1$ and $\chi_a(H)\leq \Delta+1$ (I wonder why they didn't mention the latter non-trivial fact in the proof). The choice of exactly $\Delta$ multilpe edges in the construction of $H$ plays a big role here.

I am told in person by someone working in the area that OPT$_{\Pi_1}(I_1)=$ OPT$_{\Pi_2}(I_2)$ suffices. But, I think this is not the case. If this were true, the definition of approximation factor preserving reduction can be simplified to the simple condition OPT$_{\Pi_1}(I_1)=$ OPT$_{\Pi_2}(I_2)$. Note that the 2nd condition implies that OPT$_{\Pi_1}(I_1) \leq$ OPT$_{\Pi_2}(I_2)$. I guess there must be a reason why they used a stronger condition in the definition. (As an evidence, many other approximation related reductions also demand mapping between objective value of solutions.)


The relationship I remember is that the Delaunay tessalation is the "visual complement" of Voronoi cells.

I just found this paper on Google which has a nice figure as to why finding the convex hull in d+a dimensions is equivalent to finding the Delaunay tessalation:

http://www.cs.mtu.edu/~shene/PUBLICATIONS/2004/Hull2VD.pdf

What's also interesting from a theoretical cs perspective is that the knn problem can be mapped to the Voronoi cell problem, and by extension to the Delaunay tesselation and the convex hull problem. Known algorithms in d-dimensions typically have an exponential dependency on dimension.


Index the WHT rows by an integer x, for $0 \le x \lt d$.  So x has log d bits.  Similarly, index the columns.  The (x,y) position is $(-1)^{\langle x,y \rangle}$ where the exponent is the dot product of length log d.  Assume r is a power of 2, rounding up if necessary.  Break the dxr matrix into rxr blocks by letting the first log r bits vary and fixing the other log(d/r) bits in each of the d/r ways. This rxr block is a smaller WHT matrix of size r, except there may be some columns missing, repeated, or negated.  In any case, preprocess the vector easily then do an rxr WHT in time r log r, then repeat d/r times for total time d log r.

Example:

d = 4.

WHT H is

++++
+-+-
++--
+--+

Arbitrary set of columns is 00 and 10 (leftmost and two over from that):

++
++
+-
+-

Row blocks are

++
++

and

--
--

In each block, there are repeated columns, missing columns and, in the second block, negated columns.  Preprocess a vector $(a,b)^T$ into $(a+b,0)^T$ and multiply by 2x2 WHT:

++
+-

Then preprocess $(a,b)^T$ into $(-a-b,0)^T$ and multiply by 2x2 WHT:

++
+-


Complexity of finite-state partial information games

NOTE: my purported algorithm was incorrect; I deleted it.

One thing to realize is that it doesn't matter whether the game is deterministic or not. To randomize, the referee can ask each of the players to contribute a random number mod $p$, and then add them. It's easy to show that if the players use their optimal strategy, the sum is a random number mod $p$, which the referee can then use to randomize his strategy. This doesn't greatly increase the number of states in the game.

For a lower bound on the complexity, the question of approximating the value of a simple stochastic game is not known to be in P. Using the randomization trick I gave above, it is easy to write a simple stochastic game as a refereed game with a polynomial-size lookup table.


Confusion about reduction counting vertex covers to counting cycle covers

Looks like the misunderstanding is this:

In the final reduction to (0,1)-permanent they are using modular
arithmetic, which breaks my argument.

Let $A$ be the original matrix and $B$ the (0,1) matrix.

Working modulo $n$, it might happen $perm(A)=0$ and perm $perm(B)=mn$.

Though equality holds modulo $n$, $B$ have cycle covers.

Haven't found the flaw in the question about maximum weighted
cycle cover, which doesn't appear to be affected by the above.


Properties of Random Directed Graphs with Fixed Out-Degree

In the undirected case random $d$-regular graphs are expanders with high probability (not for $d=2$, but I think $d \ge 3$ suffices), which implies that the mixing time of random walks is $O(\log n)$.  I don't remember enough about these proofs to know whether everything goes through in the directed case (certainly some properties are different: the uniform distribution is no longer stationary), but it may be worth looking into.  Good references for expander graphs are Expander Graphs and their Applications by Hoory, Linial, and Wigderson and Pseudorandomness by Vadhan.


What are some career options for someone with a computer scientist master degree?

Assuming you do not get intimidated when reading theory papers due to your training in your master's degree, which I assume is in a theoretical aspect of CS since you are asking on this site, I think it would be a great idea to try being a research programmer (usually inside some research organization, like an industrial lab or under the umbrella of a larger grant).

Why? It's not easy to implement an algorithm correctly, even if the authors sincerely meant to spell it out completely, and yet sometimes the need to run an algorithm does arise! Additionally, if you enjoy programming and measurements, later on you may even be able to further your study into a PhD in the area of algorithmic engineering, which I think is a very exciting area and wish to see more of it happening. (Check out the ALENEX conference and the DIMACS implementation challenges.)


Decision version of matrix multiplication problem

Let $H$ be some complex hash function (almost any function will do), mapping long bit strings down to a single bit. Then to decide whether $H( A \times B ) = 0$, you will basically need to multiply $A \times B$ and compute $H$ on the resulting product. Unless $H$ has very special properties, there won't be any short cut to this.


Other kinds of running time analysis besides worst-case, average-case, etc?

I have two more for the list, which are somewhat similar.

Parameterized Analysis expresses the running time as a function of two values instead of one, using some additional information about the input measured in what's called the ``parameter''. As an example take the Independent Set problem. The best running time for the general case is of the form $O(c^n n^{O(1)})$ for some constant $1 < c < 2$. If we now take as parameter the treewidth of the graph and represent it by the parameter $k$, an Independent Set can be computed in $O(2^k n^{O(1)})$ time. Hence if the treewidth $k$ is small compared to the total size of the graph $n$, then this parameterized algorithm is much faster.
Output-sensitive analysis is a technique which is applied to construction problems, and also takes the size of the output into account in the run-time expression. A good example is the problem of determining the intersection points of a set of line segments in the plane. If I'm not mistaken you can compute the intersections in $O(n \log n + k)$ time where $k$ is the number of intersections.