Why does most cryptography depend on large prime number pairs, as opposed to other problems?

Boaz Barak addressed this in a blog post

My takeaway from his post (roughly speaking) is that we only know how to design cryptographic primitives using computational problems that have some amount of structure, which we exploit. With no structure, we don't know what to do.  With too much structure, the problem becomes efficiently computable (thus useless for cryptographic purposes). It seems that the amount of structure has to be just right.


Factoring with LLL when the form of the factors is given

Yes, assuming you want both $f_1(x)$ and $f_2(x)$ with integer coefficients.

One of the reasons why LLL is so popular is precisely because it gives a polynomial time algorithm to factor polynomials with integer coefficients.

For an excellent introduction, I recommend C. Yap's "Fundamental Problems in Algorithmic Algebra" (available online, for free), specifically chapter 9 "Lattice Reduction and Applications" (section 9.6).

Following Yap, choose an approximation, $\alpha$, of a (complex) root for $f(x)$.  Setup the lattice reduction with the following basis:

$$ B_k = \begin{bmatrix}
\text{Re}(\alpha^0) & \text{Re}(\alpha^1) & \text{Re}(\alpha^2) & \cdots & \text{Re}(\alpha^k) \\
\text{Im}(\alpha^0) & \text{Im}(\alpha^1) & \text{Im}(\alpha^2) & \cdots & \text{Im}(\alpha^k) \\
c & 0 & 0 & \cdots & 0 \\
0 & c & 0 & \cdots & 0 \\
0 & 0 & c & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & c
 \end{bmatrix}
$$

Choosing $c = 2^{-4t^3}$, with $\alpha$ to have $O(t^3)$ bits for each of the real and complex portions.  Here, $t = \log ||f(x)||_{\infty}$ (that is, the cube of the number of bits of the maximum coefficient of $f(x)$).

Quoted from FPiAA:

  Theorem 9 Given a basis $A \in \mathbb{Q}^{n \times m}$, we can compute a reduced basis $B$ with $\Lambda(A) = \Lambda(B)$ using $O(n^5(s + \log n))$ arithmetic operations, where s is the maximum bit size of entries in $A$

This gives us the (polynomial) run time.  Proof of correctness that for a properly setup lattice will give you the minimal factor of a reducible polynomial is a bit more involved, but please refer to theorem 14 of the same chapter to see the relation between the reduced basis and the minimal polynomial.

By setting up the basis with dimension $n=k$ you can easily see the bound as roughly $O(k^5( \lg^3(||f(x)||_{\infty}) + \log n))$.

Since, by assumption, you know the degree of $f_1(x)$ and $f_2(x)$, the lattice reduction algorithm only needs to be run once to find one of the two factors of $f(x)$.  You can then use the discovered $f_j(x)$ to find the other by standard polynomial division.

The original paper by Lenstra, Lenstra and Lovasz, "Factoring polynomials with rational coefficients", is also quite readable and I found it to be a good compliment to Yap's introduction.


Maximal classes for which largest independent set can be found in polynomial time?

An interesting paper to look at might be:

A. Brandstadt, V. V. Lozin, R. Mosca: Independent Sets of Maximum Weight in Apple-Free Graphs, SIAM Journal on Discrete Mathematics 24 (1) (2010) 239–254. doi:10.1137/090750822

The infinite class of apples is defined as cycles C_k, k>=5, each with a stalk.

You don't mention whether your notion of IS-easiness includes the weighted IS problem. Chair-free graphs (aka fork-free graphs) are known to be IS-easy:

V. E. Alekseev, Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Applied Mathematics 135 (1-3) (2004) 3–16. doi:10.1016/S0166-218X(02)00290-1

The tractability of the weighted case is a non-trivial extension, see:

V. V. Lozin, M. Milanic: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Journal of Discrete Algorithms 6 (4) (2008) 595–604. doi:10.1016/j.jda.2008.04.001

Are there any other (interesting) classes where the weighted IS problem is significantly more difficult/intractable/open than the unweighted case?


question about probability ranking principle

This is a clear definition of the probability ranking principle.

If a reference retrieval system's response to each request is a ranking of the documents in the collection in order of decreasing probability of relevance to the user who submitted the request, where the probabilities are estimated as accurately as possible on the basis of whatever data have been made available to the system for this purpose, the overall effectiveness of the system to its user will be the best that is obtainable on the basis of those data.

As an IR professional (I work on Google Local Search), the principle is definitely wrong in the case that you assume the searcher doesn't examine every result and is just looking for one to satisfy their request.  Imagine you have 10 results that are excellent independently, but are near duplicates of each other.  Then the probability that the user finds something relevant barely increases as you spend results on the duplicate documents.  If you would have shown a diverse set of results with just one of the excellent, non-duplicate results, and others that satisfy the a secondary interpretation of the query, you'd do better to satisfy the user.

On the other hand, if your evaluation metrics for a set of results are just a sum of independent, result level metrics, then the principle is certainly correct.  You want to maximize the relevance of each result, and you can do that by picking the best ones in a vacuum.


The Canadian CS community is seriously under-server and under-organized.  The ACM (in the US) completely overshadows us, and since it (nominally anyways) tries to be international, that leaves little room for Canadians to get organized.  So typical community-driven issues, like aggregating jobs, does not happen.  The community is (now) large enough to be able to sustain such an organization (I know, I belong to the CMS, the Canadian Mathematical Society, and it manages just fine, and the sizes involved are in the same ballpark).

I realize that this answer is a bit of a non-answer.  But the (unfortunate!) answer to your question is 'no'.  So rather than just saying that, I figured I would elaborate.

Ok, so apparently my Google-fu was not good enough.  I just stumbled upon the CACS/AIC, which is the Canadian Association of Computer Science.  But the web site is astonishingly bare bones, with no real sign of the purpose, etc.  So still a 'no', but not quite exactly as I had said.  And CIPS is different, as it really focused on the IT side of things, not so much on the CS.


Why are regular languages called "regular"?

A quick check of the sources reveals that Chomsky called the levels of his hierarchy just “type 0, type 1, type 2, type 3”. He mentions in a footnote that his type 3 corresponds to “regular events” of Kleene. Kleene wrote there: We shall presently describe a class of events which we will call "regular events." (We would welcome any suggestions as to a more descriptive term.)

It would thus appear that the term is a historical accident, and in any case has no bearing on the relation of regular languages to context-free languages.


Assuming $\mathsf{PH}$ does not collapse and that Graph Isomorphism is not in $\mathsf{P}$, then $\# GI$ (the counting version of graph isomorphism) satisfies your conditions. This is because $\# GI \equiv_m^p GI$.


This is a well known open question. You will see in complexity theory many open questions for which you'd wonder how come no one managed to solve them. Part of the reason is that we need new people like you to help us solve them :)

For the latest result in this area, showing that Savitch's algorithm is optimal in some restricted model, see Aaron Potechin's FOCS paper.

Specifically, he starts from the nice observation that because the configuration graph of a deterministic TM has only one outgoing edge (after fixing the input), one can think of it as an undirected graph, and so the question becomes something like the following: given a directed graph $G$ of $n$ vertices with two special vertices $s,t$, if we map it to an $N$ vertex undirected graph $G'$ (also with special vertices $s',t'$) such that the existence of each edge in $G'$ depends on one edge in $G$ and there is a path from $s$ to $t$ in $G$ iff there's a path between $s'$ and $t'$ in $G'$, how much bigger $N$ has to be from $n$.

To show that Savitch's algorithm is optimal, one needs to show that $N$ has to be at least $2^{\Omega(\log^2 n)}  = n^{\Omega(\log n)}$. To show $L\neq NL$, it suffices to show the weaker bound that $N > n^c$ for every constant $c$.  I'm pretty sure that even $N > n^{10}$ is not known, though perhaps something like $N \geq n^2$ is known for some not so interesting reasons.


The case where all gaps have the same parity was solved by Jácint Szabó.

There is a very recent arXiv post by Szymon Dudycz and Katarzyna Paluch. They claimed to have solved the problem.


How should one simulate self-avoiding random walks?

I'm not sure if I'm interpreting your question correctly, but it sounds to me that you're asking not about simulating self-avoiding random walks, but about enumerating self-avoiding random walks.  I say this because you talk about exponentiating an adjacency matrix, which will give you a (weighted) enumeration of random walks.

I'm not sure if there is much literature on enumerating self-avoiding walks in general graphs; I believe that most attention has been focused on self-avoiding walks in lattices in Euclidean space, and that's what my comments below are based on.  I suspect that many of the ideas will carry over to general graphs.

The classic tool for reducing the labor involved in exactly enumerating self-avoiding walks is the lace expansion.  You should be able to locate the relevant literature easily with that keyword.  For highly connected graphs, though, my guess is that the lace-expansion idea won't help too much (but then maybe nothing will help much in that case).

If you're satisfied with approximate enumeration then there are a few options.  See EJJ van Rensburg's 2009 paper on "Approximate enumeration of self-avoiding walks" for a survey.  See also "Self-testing algorithms for self-avoiding walks" by Randall and Sinclair (2000).


For which problems in P is it easier to verify the result than to find it?

it is known that given a graph G and a tree T, it can be verified in linear time that T is a minimum spanning tree of G. But we don't yet have a deterministic linear time algorithm to compute the MST. Of course the gap is tiny (1 vs $\alpha(n)$), but it's still there :))


Which are the best universities for a DPhil/PhD in proof theory and automated reasoning?

I'm aware of at least two perfect places.

Paris and suburbs. You might want to check websites of David Baelde/Gilles Dowek (ENS Paris-Saclay), Delia Kesner (IRIF), Dale Miller (INRIA Saclay).

Vienna. There is a strong group of Agata Ciabatoni and of Roman Kuznets.

You also might check the list of the accepted papers for LICS/CSL/MFCS/FOSSACS/ESOP/JELIA and see the authors of the papers that seem to be related to proof theory.


Problems that are hard w.r.t UGC-hardness of VERTEX COVER

Node-weighted multiway-cut is a problem to which vertex-cover can be reduced to in an approximation preserving way. Thus, a better than $2$-approximation for node-weighted multiway cut is not possible assuming UGC. The reduction was shown by Garg-Vazirani-Yannakakis in their paper which also established a $2$-approximation for node-weighted multiway-cut.


Why is linearizability a safety property and why are safety properties closed sets?

What are the advantages of linearizability as a safety property? Are there some results based on this fact in the literature?

Suppose that you've implemented a shared memory machine $M$ that only satisfies eventual linearization, defined as follows: in every run $\alpha$ of $M$, there exists some point in time $T_\alpha$, such that linearization holds from time $T_\alpha$ on. Note that there is no upper bound on $T$. (*)
 (This is an artificial liveness counterpart of the standard safety property definition of linearizability.)

Such a shared memory implementation wouldn't be very useful to the programmer: Note that if only eventual linearizability holds, there are no guarantees whatsoever on the consistency of read/write operations in any "early" prefix of a run (before the unknown time $T$). Or, in other words, whatever has happened until now, you can still extend the current prefix of a run to one that satisfies eventual linearizability.

(*) If there was such an upper bound, then eventual linearizability would become a safety property.

  How to characterize linearizablity as closed sets topologically? In particular, what is the underlying set and what is the topology?

We can define a metric topology on the set $ASYNC$, which is the set of all possible runs of a distributed algorithms. Note that each run $\alpha \in ASYNC$ corresponds to an infinite sequence of state transitions.
For $\alpha, \beta \in ASYNC$, $\alpha \ne \beta$, we define $$d(\alpha,\beta) := 2^{-N}$$where $N$ is the earliest index where the state transitions in $\alpha$ and $\beta$ differ; otherwise, if $\alpha = \beta$, we define $d(\alpha,\beta) = 0$.

We first argue that $d$ is a metric on $ASYNC$.
By definition, $d$ is nonnegative and $\forall \alpha,\beta \in ASYNC$ we have
$d(\alpha,\beta)=d(\beta,\alpha)$.
For $\alpha,\beta,\gamma \in ASYNC$, the triangle-inequality $d(\alpha,\beta)
\le d(\alpha,\gamma) + d(\gamma,\beta)$ trivially holds if $\gamma=\alpha$ or
$\gamma=\beta$.
Now consider the case that $d(\alpha,\gamma) \ge d(\gamma,\beta) > 0$, i.e.,
$d(\alpha,\gamma)=2^{-n_1}$ and $d(\gamma,\beta)=2^{-n_2}$, for some indices
$n_1\le n_2$.
Since $\gamma$ shares a common prefix of length $n_2-1$ with $\beta$ but only a
prefix of length $n_1-1$ with $\alpha$, it follows that $\alpha$ and
$\beta$ differ at index $n_1$, and thus $d(\alpha,\beta) = d(\alpha,\gamma)$ and
the triangle-inequality follows.
The case where $0<d(\alpha,\gamma) < d(\gamma,\beta)$ follows analogously.

The metric $d$ induces a topology (e.g., page 119 of [1]) where the $\epsilon$-balls  $B_\varepsilon(\alpha) = \{
\beta \in ASYNC \mid d(\alpha,\beta) < \varepsilon \}$ are the basic open sets.
We will now argue why safety properties correspond to
closed sets:
If an execution $\alpha$ does not satisfy a safety property
  $S\subseteq ASYNC$, i.e.\ $\alpha \notin S$, then there is an index
  $N$ where
  all runs $\beta$ that share a prefix longer than $N$ with $\alpha$ are
  not in $S$. This closely matches intuition, since once a
    safety property is violated in a prefix of an execution, it makes no
    difference how this prefix is extended!
Formally speaking, suppose that $\alpha \notin S$.
There exists an $N\geq 0$ such that, if some
$\beta \in ASYNC$ has $d(\alpha,\beta) < {2^{-N}}\text{,}$ i.e., $\alpha$ and
$\beta$ share a prefix of length $\ge N$, then $\beta \notin S$.  Thus, the
set of runs $S$ is closed, since its complement is open.

[1] James Munkres. Topology.


The problem as stated now is solvable in linear time.

To see this, suppose $p\in P$ is such that there are $x\in X$ and $w\in W$ with $p_i=x_iw_i$ for all $i$. This means on the one hand that $1=\sum_{i=1}^np_i=\sum_{i=1}^nx_iw_i$, but on the other hand because of $1 = \sum_{i=1}^nx_i$ and $1 = \sum_{i=1}^nw_i$ we have $1 = \sum_{i=1}^n\sum_{j=1}^nx_iw_j$, so that $x_iw_j$ must be $0$ for all $i\neq j$ (using also that all the $x_i,w_i$ are nonnegative).

This implies that there is some index $k$ with $x_k=w_k=1$ and $x_j=w_j=0$ for all other $j$: indeed, since $1 = \sum_{i=1}^nx_i$, some $x_k$ must be nonzero. Then $x_kw_j=0$ means $w_j=0$ for all $j\neq k$, and because $1 = \sum_{i=1}^nw_i$, we have $w_k=1$. Analogously we get $x_j=0$ for $j\neq k$ and $x_k=1$. As a consequence, $p_k=1$ and $p_j=0$ for $j\neq k$.

The decision problem is whether this is true for all $p\in P$. Since $P$ is convex, this is only possible if $P$ only consists of one of these unit vectors, i.e. for some $k$ we have $a_k=b_k=1$ and $a_j=b_j=0$ for all other $j$; additionally, $X$ must also contain this vector, i.e. we need to have $u_k=1$ and $l_j=0$ for $j\neq k$.

EDIT: What we have are the following results:

If $p,x,w\in[0,1]^n$ with $\sum_ip_i=\sum_ix_i=\sum_iw_i=1$ and $p_i=x_iw_i$ for all $i$, then $p=x=w=e_k$ for some $k$, where $e_k$ is the unit vector given by $(e_k)_k=1$ and $(e_k)_j=0$ for all $j\neq k$.
Adding the constraints $a_i\le p_i\le b_i$ and $l_i\le x_i\le u_i$ further restricts the set of solutions to those $e_k$ which are both in $P$ and in $X$, i.e. such that $b_k=u_k=1$ and $a_j=l_j=0$ for $j\neq k$.
The decision problem given in the question is whether such $x,w$ exist for all $p\in P$; the answer to this is "yes" if and only if $P$ is a singleton set $\{e_k\}$ for some $k$, i.e. $a_k=b_k=1$ and $a_j=b_j=0$ for $j\neq k$, and additionally this $e_k$ is in $X$, i.e. $u_k=1$ and $l_j=0$ for $j\neq k$. This can be checked in linear time.


Jerrum, Valiant and Vazirani showed that if for a "self-reducible" NP-relation, there exists a polynomial time approximate counter which produces a $1 + O(n^{-\beta})$ approximation for some constant $\beta > 0$, then this counter can be bootstrapped to make an an FPRAS for the counting problem.  As far as I know, all known #P-complete problems do correspond to "self-reducible" NP-relations, and hence the claim on Wikipedia.  However the exact claim that an approximate counter which produces a poly($n$) approximation for a self-reducible NP-relation can be bootstrapped to produce an FPRAS for counting was proved by Jerrum and Sinclair.  The citation I can think of the top of my head is Sinclair, 1993.


Testing feasibility of special linear programs

My first observation: we know how to solve your LPs in strongly polynomial time, but this is an open question for general LPs.


Surveys on pseudo-random number generator design?

You might want to check out

Chapters 5 and 6 of Katz and Lindell
Pseudorandomness by S. Vadhan
Parwise Independence and Derandomization by Luby and Wigderson
Pseudorandomness and Combinatorial Constructions by Trevisan
Goldreich's webpage on pseudorandomness, where he has pointers to other sources.


Number of accepting path of a non deterministic automaton

This concept is called the ambiguity of the NFA.
Typically, there are 3 classes of ambiguity in this context: Bounded, polynomially bounded, and exponentially bounded.

Every NFA has at most an exponential number of runs on a given word (this is easy to see).

Interestingly, there is a simple syntactic characterization of polynomially bounded NFAs:

An NFA has a polynomial number of runs on a word $w$ iff for every state $q$, there is at most one cycle from $q$ to itself on every word $x\in \Sigma^*$. See this for details.

Testing for bounded ambiguity is PSPACE-complete. A good starting point is this paper


A theorem regarding statistically-hiding commitment schemes

This certainly follows for $n=1$.

Fix any algorithm $A$ that attempts to distinguish, and let $p_{a,b} = \Pr[A(\langle a, C(b) \rangle)=1]$, where $a,b\in \{0,1\}$.  Now by the assumption that $C$ is statistically hiding, we have $p_{0,0} \approx p_{0,1}$ (for otherwise you could prepend the fixed constant 0 to any commitment and then use $A$ to break the hiding property) and we have $p_{1,0} \approx p_{1,1}$ (for a similar reason).

Expanding out the definitions, we have $\Pr[A(X)=1]=(p_{0,0}+p_{1,1})/2$ and $\Pr[A(Y)=1]=(p_{0,0}+p_{0,1}+p_{1,0}+p_{1,1})/4$ (where $X,Y$ are samples from your distributions ${\cal X},{\cal Y}$).  But from the facts above, we have $2p_{0,0} + 2p_{1,1} \approx p_{0,0} + p_{0,1} + p_{1,1} + p_{1,0}$, i.e., $\Pr[A(X)=1]\approx \Pr[A(Y)=1]$, and thus $X,Y$ are statistically indistinguishable.

I think from this you should be able to see how this generalizes to $n>1$ as well. Basically, you note that

$$\Pr[A(X)=1]=1/2^n\sum_b \Pr[A(\langle b,C(b)\rangle)=1]\approx 1/2^{2n}\sum_{a,b} \Pr[A(\langle a,C(b)\rangle)=1] = \Pr[A(Y)=1],$$

using the fact that $\Pr[A(\langle a,C(b))\rangle)=1] \approx \Pr[A(\langle a,C(b')\rangle)=1]$ for all fixed $a,b,b'$ (otherwise you could distinguish $C(b)$ from $C(b')$ by simply prepending $a$ and then running $A$).


What is the asymptotic time complexity of the number of steps of "Half Or Triple Plus One" ( HOTPO)?

By request, two facts that are known and seem somewhat related to your question.

As a lower bound: infinitely many integers $n$ take time $\Omega(\log n)$. Applegate and Lagarias.
As a sort of an upper bound: $\Omega(N^c)$ positive integers bounded by $N$ reach $1$ in finite time, where $c \approx 0.84$. Krasikov and Lagarias.

Hopefully you have read Lagarias's survey before asking the question.


Succinct Representation and Communication complexity

The circuit computed by Alice gets $\log(n)$ bits representing $i \in [n]$, and outputs $1$ iff $i \in A$. Note that if $A$ does not have a particularly nice structure, the size of this circuit will be exponential in the length of the input, that is $2^{\log(n)}$.


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

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


How is it proven that Key Exchange implies OWFs?

Your question suggests the following tentative reduction to obtain a OWF from a secure KE: Given an input, interpret it as the private random coins of two simulated parties to the KE protocol. Based on their private randomness, there will be some sequence of public messages between them, and at some point they will stop and agree on a private shared key (with some high probability). Then the public transcript of their communications is the output of the OWF.

You are right to be worried about this approach in the case when Alice and Bob may not agree with probability 1. In fact, this construction is NOT necessarily a OWF in that case. Rather, it is a weaker primitive known as a "distributionally one-way function," which is, informally, a function for which it is hard to generate a uniformly random preimage of $f(x)$, when $x$ is selected at random. It is known (but non-obvious) that one can construct a true one-way function using a distributionally one-way function. See e.g. Exercise 17 on page 96 of Goldreich "Foundations of Cryptography: Basic Tools," which is available for limited viewing on Google preview.

To directly see why the above reduction does not suffice, we can use the common "make a stupid modification" technique. Namely, suppose there exists a secure KE protocol where Alice and Bob agree with probability $1 - \epsilon$. Consider a stupidly-modified KE protocol that works as follows: Alice and Bob first each flip 100 coins. For each of Alice, Bob individually: If all 100 coins are zero, their remaining randomness is interpreted as encoding a sequence of messages which they send to the other party, ignoring whatever the other one says; then they just output a random "shared key." (Otherwise they follow the original protocol.) Given any public transcript, it is possible (with negligible probability) that it was generated by an Alice and Bob who BOTH flipped 100 zeroes and happened to have their remaining randomness specify that exact sequence of messages.

This is still a secure KE protocol, where Alice and Bob will agree with probability at least $1 - \epsilon - 2^{-100}$. On the other hand, it utterly fails to be a OWF in the hoped-for manner, since an attacker who sees some public transcript can always trivially invert by choosing 100-zeroes randomness for each of Alice and Bob.


How is the MA version of SETH proven to be false?

You can find a preprint by following this link http://eccc.hpi-web.de/report/2016/002/

EDIT (1/24) By request, here is a quick summary, taken from the paper itself, but glossing over many things. Suppose Merlin can prove to Arthur that for a $k$-variable arithmetic circuit $C$, its value on all points in $\{0,1\}^k$ is a certain table of $2^k$ field elements, in time about $(s + 2^k) \cdot d$, where $s$ is the size of $C$ and $d$ is the degree of the polynomial computed by $C$. (We call this a "short non-interactive proof of batch evaluation" --- evaluating $C$ on many assignments.)

Then Merlin can solve $\#$SAT for Arthur as follows. Given a CNF $F$ on $n$ variables and $m$ clauses, Merlin and Arthur first construct an arithmetic circuit $C$ on $n/2$ variables of degree at most $mn$, size about $mn \cdot 2^{n/2}$, which takes a sum over all assignments to the first $n/2$ variables of the CNF $F$ (adding a $1$ to the sum when $F$ is true, and $0$ when it's false). Using the batch evaluation protocol, Merlin can then prove that $C$ takes on $2^{n/2}$ particular values on all its $2^{n/2}$ Boolean assignments, in about $2^{n/2} poly(n,m)$ time. Summing up all those values, we get the count of the SAT assignments to $F$.

Now we say at a high level how to do the batch evaluation protocol. We want the proof to be a succinct representation of the circuit $C$ that is both easy to evaluate on all of the $2^k$ given inputs, and also easy to verify with randomness. We set the proof to be a univariate polynomial $Q(x)$ defined over a sufficiently large extension field of the base field $K$ (of characteristic at least $2^n$ for our application), where $Q(x)$ has degree about $2^k \cdot d$, and $Q$ ``sketches'' the evaluation of the degree-$d$ arithmetic circuit $C$ over all $2^k$ assignments. The polynomial $Q$ satisfies two conflicting conditions:

The verifier can use the sketch $Q$ to efficiently produce the truth table of $C$. In particular, for some explicitly known $\alpha_i$ from the extension of $K$, we want $(Q(\alpha_0), Q(\alpha_1),\ldots,Q(\alpha_K)) = (C(a_1),\ldots,C(a_{2^K}))$, where $a_i$ is the $i$th Boolean assignment to the $k$ variables of $C$ (under some ordering on assignments).
The verifier can check that $Q$ is a faithful representation of $C$'s behavior on all $2^k$ Boolean assignments, in about $2^k + s$ time, with randomness. This basically becomes a univariate polynomial identity test.

The construction of $Q$ uses an interpolation trick originating from the holographic proofs, where multivariate expressions can be efficiently ``expressed'' as univariate ones. Both of the two items utilize fast algorithms for manipulating univariate polynomials.


How to build comparison operator (comparator) in an arithmetic circuit

I believe this is generally done in MPC by converting the sharing of the field element to some sharing more amenable to comparison. See this (section 6.3), or chapter 9 in Secure Multiparty Computation and Secret Sharing by Cramer et al.

Generically, comparisons are dependent on how you represent values in $\mathbb{F}_p$. For example, in $\mathbb{F}_3$ you might want to say that $1 \leq 2$, but since $-1$ is in the same equivalence class as $1$ any polynomial that computes this (for $\mathbb{F}_3\cong \{0,1,2\}$) would also compute $1 \leq -1$ (for $\mathbb{F}_3\cong\{-1,0,1\}$). You could of course use Lagrange Interpolation to get any polynomial to have arbitrary values, but it'd be difficult to call that polynomial "the comparison polynomial", and your model of arithmetic circuits would have to be with respect to a specific representation of field elements (which sounds non-standard, but I'm no expert).

The book by Cramer et al has some commentary on how comparisons using solely $\mathbb{F}_p$ arithmetic leads to large circuits, so maybe there is actually some "comparison polynomial" (and m preceding paragraph is wrong), but it appears the standard thing to do still is to convert to an easier representation to do comparisons on for efficiency.


The best quantum algorithm for QBF on n variable formulas of size s runs in about $2^{n/2}poly(s)$ steps, regardless of quantifier alternations. This is due to a series of advances on quantum algorithms for game tree search in the early 2000s.
Here is the first reference I found from googling; there are more: https://arxiv.org/abs/0907.1623


Reference request: Shortest homotopic curve via vertex releases

This is morally equivalent to a slower variant of the Hershberger-Snoeyink funnel algorithm.

I'm not aware of any exposition of your simple algorithm in the literature.  This is actually a little surprising, given how many times the basic funnel algorithm has been rediscovered [Tompa, STOC 1980; Chazelle, FOCS 1982; Lee and Preparata, Networks 1984; Leiserson and Maley, STOC 1985].

Both your algorithm and the Hershberger-Snoeyink algorithm are examples of a folklore technique called curve shortening.  At a high level: If the curve can be shortened by a continuous motion, shorten the curve by a continuous motion.  The details are surprisingly irrelevant; you can shorten either by local discrete moves (like your algorithm) or by a global continuous deformation (as if the path were made of elastic).  In any space where curvature is nowhere positive, there is a unique shortest path in every homotopy class [Gromov].  Thus, assuming your shortening process actually converges, it necessarily converges to the unique shortest path homotopic to the given path.

This is exactly why the Hershberger-Snoeyink funnel algorithm works.  Each step in reducing the crossing sequence is shortening a subpath of the path to a line segment, and each step in the funnel algorithm is equivalent to shortening the path inside the next triangle of the sleeve.  (See my notes linked by OP for definitions.)

In particular, the sides of the funnel play exactly the same role as your convex hulls.  Moreover, the standard algorithm for extending the funnel through one triangle is identical to one iteration of the Graham scan convex hull algorithm, or Andrews' equivalent sort-and-repair algorithm, or the equivalent plane-sweep algorithm.

So while I agree that your algorithm is more elementary than Hershberger-Snoeyink, I'm not convinced that it's actually easier to implement.

(One thing that may not be clear in my notes is that the Hershberger-Snoeyink algorithm doesn't actually need to construct the sleeve; the funnel can be guided directly by the reduced crossing sequence.  The only point of the sleeve is to help visualize the algorithm.)

One advantage of the Hershberger-Snoeyink algorithm is that it has a single $O(n\log n)$-time preprocessing phase to compute a global triangulation, after which the running time is proportional the number of crossings, so the overall worst-case running time is $O(n\log n + kn)$, where $k$ is the complexity of the input path.  The analysis is straightforward.

I strongly suspect that the vertex-release algorithm can be polished to have the same running time, with the right combination of preprocessing, data structures, and choice of which unstable vertex to release at each iteration, but it's certainly not straightforward.  Naively, your algorithm needs to compute the convex hull of a subset of the points for each vertex release, which takes $O(n \log n)$ time, and the number of vertex releases could be as high as $\Omega(kn)$.  Suppose we want to simplify the black path in the following example:

For simplicity, suppose we repeatedly release the first unstable vertex on the black path.  The first release creates $\Omega(n)$ new path vertices; the next $\Omega(n)$ releases delete those vertices; and these releases remove one "tooth" from the black path.  (Yes, you can reduce the number of releases by choosing them more intelligently, but that complicates the algorithm.)

So assuming this $\Omega(kn)$ lower bound is tight, a naive implementation of this algorithm runs in $O(kn^2\log n)$ time.  You can remove a $O(\log n)$ factor by pre-sorting the points; then each step can be performed in $O(n)$ time via Graham's scan.

You might try speeding up the algorithm by releasing the vertex that makes "the most progress", but this is uncomfortably close to 2d simplex range searching, so this "improvement" could easily make the algorithm slower, not faster.  For example, deciding whether there is a "trivial" vertex release, which decreases the complexity of the path, is at least as hard as Hopcroft's point-line incidence problem, and therefore is unlikely to be solvable in $o(n^{4/3})$ time.  See [Cabello et al. 2004] and [Bespanyatnikh 2003] for similar hardness results and matching theoretical improvements to Hershberger-Snoeyink.

tl;dr: I would cite "folklore", at least for correctness.


Grid $k$-coloring without monochromatic rectangles

Some of you are probably aware of this, but the 17 x 17 coloring problem has been solved by Bernd Steinbach and Christian Posthoff.  See Gasarch's blog post here.


Name of this graph partitioning problem? (related to coloring)

(Copied from a comment:)
If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as "maximum k-cut" and also "maximum k-colorable subgraph".


Here is a tweet thread by Prof. Vijay about research for undergraduate students.
Also, you can apply for a summer research internship in Europe.

INRIA France, contact individual groups if they have an intern opening.
Max-Planck Institute, Germany, Offering remote internship also, This year's deadline 31st Dec/31st Jan
IST, Austria
EPFL, Switzerland

Edit 1: Just now I got this link.


Hardness of geometric area minimization problem

Never mind. I misremembered the definition of 3-partition.

I'll leave what I wrote here here, but since division into 3 subsets with equal sums is not strongly NP-complete, this doesn't work.

By 3-subset sum, I mean a: given a set of integers, find a partition into 3 subsets whose sums are all equal.

The problem is roughly equivalent to: let $\{p_i\}$ be the multiset of prime factors of $C$; find the best way of partitioning the multiset $\{r_i\}$ into three parts with equal sums, where $r_i = \log p_i$, for $p_i$.

Here's the wrong argument I had before.

=========================

Find a bunch of primes $p_1$, $p_2$, $\ldots$, $p_{\alpha(n)}$ so that $\log p_i \approx M\ i$ for some real $M$.  Now, take a 3-subset sum problem on integers $1 \ldots \alpha(n)$, and replace the integer $i$ with prime $p_i$. Let $C$  be the product of all the primes $p_i$ corresponding to the integers $i$ in the 3-subset sum problem. Then, any $x$, $y$, $z$ with $x \approx y \approx z$ and $xyz = C$ gives a good partition of the integers in the 3-subset sum problem. Let $p_x$, $p_y$, and $p_z$ be the multisets of primes making up the prime factorization of $x$, $y$, and $z$, respectively. If $x$, $y$, and $z$ are close, $\log x \approx \log y \approx \log z$ means $ \sum_{p_i \in p_x} \log p_i \approx \sum_{p_i \in p_y} \log p_i \approx \sum_{p_i \in p_z} \log p_i$, and so you have a good solution to the 3-subset sum problem (and if you've chosen the primes right, you can tell from the optimal $x$, $y$ and $z$ whether or not the original 3-subset-sum problem is solvable). Since you know what the primes you used were, factoring $x$, $y$ and $z$ can be done by trial division to recover the partition.


Use of Lagrangian dual information to prove optimalitiy of a solution : Any example?

Lagrangian duality generalizes standard linear programming duality to the minimization of arbitrary functions (although it's often most effective for convex programs). The rough idea (and Convex Optimization by Boyd and Vandenberghe does a fantastic job of explaining this) is this:

take a a constrained optimization problem,
replace it by an unconstrained optimization problem in which the constraints are folded into the objective linearly by multiplying them by variables (the Lagrange multipliers)
minimize this unconstrained optimization over the original variables
what you end up with is a convex function of the Lagrange variables, the so-called Lagrange dual
and minimizing this (easy, because it's convex regardless of the original function) provides a bound on the original optimization.

If the original problem was convex to begin with, and assuming some technnical conditions, this bound is tight and you have strong duality. Since NP-complete problems are nonconvex in general, you can't use Lagrange duals to prove optimality. However, you can use it to get guaranteed approximations. One of the more well known uses of Lagrange duality is in the approximation algorithm for facility location and the $k$-median problem by Jain and Vazirani.


How to measure programming language succinctness?

The ideas the question expresses are interesting but maybe insufficiently
fleshed out.  I can see a couple of points that deserve further
refinement.

It is difficult to "code the exact same functionality". In part that
is because what counts as "the exact same functionality" depends on
the chosen notion of program equivalence. For terminating programs
in sequential programming languages there's a canonical definition,
but when you move to concurrent, non-terminating programs,
canonicity vanishes, and you are left with multiple, reasonable
choices that are mutually incompatible. Secondly, but related to the
first point, different programming languages are fundamentally
different: things you can do in a low-level language can often not
be done in a high-level language. A typical example is to do with
speed.  Certain tasks can be solved intrinsically faster in assembly language
than in e.g. Prolog or Javascript (assuming conventional
compilation).
The KQuotient is subjective, in the sense that for any
given task, programmers A and B will likely have different length
base and test language implementations.
Moreover, the KQuotient is also task dependent, meaning that, given
a pair of languages, the KQuotient for Task A will in general be
different from the KQuotient of Task B.

Finally, even though I find the idea of measuring maintainability via
query numbers to reach consensus intriguing, I suggest to be more
clear about what kind of queries are relevant here (syntax?
semantics?), and how the concept of programmer consensus can be made
precise.


Complexity of counting all connected subgraphs

Welsh states that the problem #P-complete even in the most restricted case (counting the number of connected subgraphs of a planar bipartite graph). See the bottom of page 305 in Welsh, Dominic (1997), "Approximate Counting", Surveys in Combinatorics, Bailey, R. A., ed., Cambridge University Press, pp. 287–324.

In context, though, I wonder whether he really means connected spanning subgraphs. And that leads me to wonder which version of the problem you want: connected spanning subgraphs, connected subgraphs that need not be spanning, or connected induced subgraphs?


In a cryptosystem, why does the message space need to be finite?

One reason for this is that one can first define a cryptosystem having a small finite message space, and then on top of that, construct another cryptosystem that can handle longer message spaces. This is a very reasonable modular design methodology.

A couple of examples:

given a block cipher with a finite message space, one can use a
block cipher mode (like CBC or CTR) to extend the message space
to be essentially infinite.
given the Paillier public-key cryptosystem, one can institute a
specific length-parameter (as done by Damgård and Jurik) and allow
to efficiency encrypt messages of arbitrary length.

One caveat though is that if messages are of arbitrary length, then also the time to encrypt increases accordingly. If we want to be the cryptosystem to be secure against adversaries working in some time $t$, it is better to restrict the message length so that encrypting any messages of that length takes considerably less time than breaking the cryptosystem (with a small message length).

Remark: one can obviously try to define security in a way that breaking small messages can be easier than breaking long messages, but this does not make sense in practice.


From Lasserre maps to pseudo-distributions

The answer to your first question is yes by some linear algebra. Write down the equations for $L(m) = \sum_{x\in\pm 1} D(x)m(x)$ where $m$ is a monomial of degree at most $d$ (with no squared variables in it). You can write this as $L = MD$ where $M$ is a matrix with rows indexed by the monomials $m$ and columns indexed by the points $x \in \{\pm 1\}$, with values $m(x)$, and $D$ is a vector indexed by the points in $\{\pm 1\}$. $M$ has full rank, so you can find $D$ with $MD = L$ for any $L$. That any such $D$ satisfies the pseudodistribution properties follows from the fact that $L$ satisfies the corresponding properties.

As for your second question, formally, it can be done for prime fields by just using equations like $x^p = 1$ in place of $x^2 = 1$. (I'm not sure what to do for general prime powers.) It might be helpful in characteristics greater than two to generalize the rest of the SOS theory to work over $\mathbb{C}$, since you're working with complex roots of unity. This can be done essentially by replacing "sum of squares" by "sum of products-of-conjugates" and making appropriate adaptations elsewhere.

However, I'm doubtful that it's useful to think of $\{\pm 1\}$ as being "like" $\mathbb{F}_2$ in the context of SOS. Embedding finite fields as roots of unity doesn't jive well with sum of squares: addition in the finite field turns into multiplication over $\mathbb{R}$, and hence SOS requires high degree to reason about sums (in the finite field) of many unknowns, because they translate to products (over the reals) of many variables. An essentially canonical demonstration of this is the lower bound for solving linear equations over $\mathbb{F}_2$ (see section 3.1 here). In particular, you can trick low-degree SOS into believing that a certain system of linear equations over $\mathbb{F}_2$ is completely satisfiable, when in reality at most a $\frac{1}{2}+\epsilon$ fraction of equations can be satisfied by any true assignment.


Streaming Algorithms: Motivations for estimating frequency moments

$F_0$ counting (or estimating distinct elements, or "cardinality estimation") is very useful.

Example: when you're doing profiling at the router level, you often want to estimate functions of distinct IP addresses, and since you can't just maintain counters for each possible address, $F_0$ counting turns out to be quite useful.

$F_1$ counting, or frequency estimation is also very useful:

Example: There's work on building statistical language models that involve counting frequencies of pairs of words, triples of words, and so on. You can't maintain counts for all such triples, so you often want "frequent" ones, or "heavy hitters".


"Almost all objects have property P" vs. "It is easy to test whether an object has property P"

They are separate (assuming $P \ne NP$).  Consider the following property $P(x)$: $x$ is a $2n$-bit string, where either the first $n$ bits are not all zeros, or the last $n$ bits are a yes-instance of 3SAT.  It's clear that testing whether $x$ satisfies $P$ is NP-hard, yet almost all strings satisfy it: the density $\to 1$ as $n \to \infty$.


Concurrent data structures vs. Distributed data structures

What are the big challenges of designing distributed data structures (even harder than those of concurrent data structures)?

Some important challenges that practically all distributed data structures face, are handling dynamic changes, implementing a scalable design, and being fault-tolerant.

This includes finding answers to questions such as:

How can we maintain/repair the properties of the data structure in the presence of churn? That is, new nodes join and old nodes leave the network over time.
Can we design the data structure  such that it is robust against faults?
How can we deal with the congestion on the communication links caused by many parallel requests?
Do the connections required per node and the necessary length of messages scale (at most) logarithmically with the system size?
Is it possible to design a system that is "spam resistant" in the sense that it can withstand attacks by adversarial nodes?

There are also locality issues since, in a distributed system, each node runs its own instance of a distributed algorithm and has only a local view of the network due to being directly connected to only a small number of other nodes. (Typically you would want a node degree of $O(\log n)$ to make the system scalable.) These issues come into play when maintaining global state such as counting the number of data items, finding the maximum, etc.

  Did I miss other distributed data structures in the literature?

DHTs: To give you some pointers, you might want to look at distributed hash tables (DHT) such as Chord, CAN, Tapestry, and Pastry.

Skip Graphs: Since you mentioned skip lists, you might be interested in skip graphs, which is a data structure providing range-queries and $O(\log n)$-time operations for lookups, inserts, etc.
The advantage of a skip graph (vs a skip list) is that a skip graph contains an expander as a subgraph with high probability.
This implies that routing can be done efficiently (i.e. link congestion is low) and that the skip graph remains connected even if a lot of nodes fail.


Is feedback vertex set problem is solvable in polynomial time for some special graph

Surely the problem is polytime for graphs of bounded treewidth via dynamic programming.


Gap-Hamming with different "threshold" (i.e., not $n/2$)

As it turns out, the one-sided error case (public coin) was addressed in [KK16], which shows the communication complexity is then $\tilde{\Theta}\!\left(\frac{(t-g)^2}{t+g}\right)$ (the upper and lower bound are off only by a $\log(t-g)$ factor).

(so, for $\mathsf{GHD}_{n,2\sqrt{n},\sqrt{n}}$, the one-sided public-coin communication complexity is $\tilde{\Theta}\!\left(\sqrt{n}\right)$.)

[KK16] One-sided error communication complexity of Gap Hamming Distance, Egor Klenin and Alexander Kozachinsky. ECCC TR16-173, 2016.


No, as far as I know, there are no models that use string theory.

Given that quantum field theories seem to be simulatable in polynomial time by a quantum computer (Jordan, Lee, and Preskill, 2012), the only possible more powerful physical system would be quantum gravity. This is because physicists generally believe that quantum field theory gives an excellent approximate description of the universe if gravity is neglected; however, general relativity seems incompatible with quantum mechanics. Thus, to get a full description of the universe, we need a theory of quantum gravity.  Many physicists believe this theory is given by string theory; however, physicists currently don't understand string theory well enough to use it as a basis for a model of computation.


Complexity of listing all minimal cut sets / connected 2-partitions of a graph

dear all. There is no contradiction here. The problem of listing or enumerating all cutsets is a counting problem which is #P-hard. The class #P consists of all the problems that can be solved by a non-deterministic counting Turing machine in polynomial time. Therefore, the class #P is useful for classifying counting problems. On the other hand, the class NP is suitable for classifying  decision problems. A decision version of your problem would be, for instance: Is there a cutset with cardinality less than $k$? Obviously, if you can enumerate all the cutsets in polynomial time, then you can also say in polynomial time if there exists a cutset with cardinality less than $k$. In other words, the counting version is at least as hard as the decision version.  Therefore, if a counting problem is #P-hard, then it is NP-hard (I am talking about the same counting problem, not its decision version). However, the converse is an open question. In other words, for the time being, saying that this problem is #P-hard is a stronger statement than saying that it is NP-hard.


Indistinguishability complexity of a subset

I assume $S'$ is parametrized by $n$, i.e.~it is not defined only for a single $n$ but for infinitely many $n$ (otherwise statements like "polynomial time" do not make sense). If so, you are merely defining the fundamental problem of the complexity of deciding membership in a language (i.e. the problem of complexity theory). I am not sure what you mean by "uniform": if you mean that there could be a different algorithm for different $n$, then this is the usual non-uniform complexity.


Minimal polynomial reduction of dominating set to max clique

There are good reasons to expect that there is no polynomial time reduction that takes as input a graph $G$ and outputs a graph $\hat{G}$ such that $\omega(\hat{G})$ depends only on $\gamma(G)$. In particular the Clique problem is complete for $W[1]$ while Dominating Set is complete for $W[2]$, see the Wikipedia page for Parameterized Complexity. A reduction from Dominating Set to Clique where the size of the clique only depends on the size of the dominating set would imply that $W[2] = W[1]$, which is considered unlikely.

On the other hand it is not too hard to make a reduction where $\omega(\hat{G})$  depends only on $\gamma(G)$ and $|V(G)|$. For every edge $uv \in G$ make two vertices $[u,v]$ and $[v,u]$ in $\hat{G}$. For two vertices $[u_1,v_1]$ and $[u_2,v_2]$ of $\hat{G}$ we put an edge between them if $u_1 \neq u_2$, $u_1 \neq v_2$ and $u_2 \neq v_1$. We claim that $\omega(\hat{G}) = |V(G)| - \gamma(G)$.

The intuition is that the vertex $[u,v]$ is interpreted as ``$u$ is dominated by $v$''. Then each vertex of $G$ not in the dominating set should choose exactly one vertex in the dominating set to dominate it. Someone who has chosen to be dominated may then not be a dominator.

Consider a dominating set $S$ in $G$. We make a set $\hat{S}$ as follows: for each vertex $u \notin S$, pick an arbitrary neighbor $v \in S$ of $u$ and add $[u,v]$ to $\hat{S}$. Clearly $\hat{S}$ is a clique of size $|V(G)| - |S|$.

On the other hand consider a clique $\hat{S}$ in $\hat{G}$. Let $S$ be the set of vertices $u$ in $V(G)$ such that there does not exist a $v \in V(G)$ such that $[u,v] \in \hat{S}$. Observe now that $|S| \geq |V(G)| - |\hat{S}|$, since each element of $\hat{S}$ rules out at most one vertex of $G$. Consider a vertex $u \notin S$. There must be some vertex $v \in V(G)$ such that $[u,v] \in \hat{S}$. We know that $uv \in E(G)$, it remains to show that $v \in S$. Suppose not, then there must be some $v' \in V(G)$ such that $[v,v'] \in \hat{S}$. But $[u,v]$ and $[v,v']$ are non-adjacent in $\hat{G}$, contradicting that $\hat{S}$ is a clique. So $S$ is a dominating set.


largest language class for which inclusion is decidable

Converted from comment: language inclusion is decidable for very simple deterministic pushdown automata ("On the Inclusion Problem for Very Simple Deterministic Pushdown Automata (1999)" by E. Makinen, 1999)
and a restricted version of timed finite state machine ("On the Language Inclusion Problem for Timed Automata: Closing a Decidability Gap" by J. Ouaknine and J. Worrell, 2004).


You might consider as a first approximation:

$\sum_i((A[i,i])^2) \over \epsilon + \sum_{i \ne j}((A[i,j])^2)$

(The epsilon value is there to avoid divide-by-zero errors).

Having said that, you might also consider the question of whether the matrices are tri-diagonal. A matrix is often converted to tri-diagonal form before computing its eigenvalues.

Another measure of "diagonalness" could be the sum of the absolute value of the differences between the eigenvalues (arranged in sorted order) and the diagonals (arranged in order of largest diagonal-entry first). This is great if you already know the eigenvalues. In fact, it is probably a better measure. However, in terms of efficiency, I would probably prefer the sum of squares ratios.


Complexity of isotopy of embedded graphs

Since you only care about embeddings in the plane, and every oriented homeomorphism of the plane is isotopic to the identity (Alexander's trick), testing whether two embedded graphs are isotopic is equivalent to testing whether they are congruent by an oriented homeomorphism. And this is a purely combinatorial notion: for example it is equivalent to the two graphs having the same (extended) combinatorial maps (Lemma 5 in our paper with Eric that you cited in your answer).

Testing whether two embedded graphs have the same combinatorial map is solvable in linear time according to this paper but I have never found the full version, and for planar maps it is actually quite simple.

If you already have the isomorphism between the graphs, this is easily doable in linear time (just check that the combinatorics agree everywhere). If you don't, you need to find it. Luckily, planar graph isomorphism is easy and doable in linear time (Hopcrof-Wong).

Now that does not solve your problem exactly, because maybe this could find a graph isomorphism that is not a map isomorphism, while another graph isomorphism would be. But this is not a real issue: the disconnected components are arranged in a tree-like fashion due to the nesting, and thus can be encoded with a tree. Similarly, bi-connected components are arranged in a tree (the block-cut tree), and so are tri-connected components (the SPQR tree). And tri-connected components have a unique embedding, and thus are map-isomorphic if and only if they are graph-isomorphic. (some care needs to be taken (e.g. ordering and/or labeling) so that these trees precisely encode the map you are looking at).

So mixing the Hopcroft-Wong algorithm with some tree isomorphism algorithm should solve your problem in linear time. (this is actually similar to the planar graph isomorphism algorithm, see for example Hopcroft-Tarjan)


Max Sum Product Multi-objective Shortest path problem

It seems NP-complete even with weights in $\{0,1\}$.
I reduce from the MINSAT problem: given a SAT instance, find an assignment that minimizes the number of satisfied clauses.
More precisely, an instance is a CNF formula, and an integer $k$, and you have to say whether there is an assignment satisfying at most $k$ clauses.
It is shown to be NP-complete in this paper.

Start from a MINSAT instance with variables $x_1\dots x_n$ and clauses $C_1\dots C_m$, we build an instance of your problem.
The weight vector has $m$ coordinates (the number of clauses).
The first edge of the graph puts every coordinate to $1$.
Then we traverse $n$ nodes where you have to choose the truth value of the variables $x_1\dots x_n$. For instance if you set $x_i$ to true, the corresponding edge vector contains a $0$ for each clause $C_j$ where $x_i$ appears positively and $1$ elsewhere.
The idea is that a clause is set to $0$ if the assignment makes it true. Since you use the product to evaluate a path, $0$ is absorbing and corresponding to the wanted disjunction.
Finally, you have a path from the source to the target with weight at least $m-k$ if and only if there is an instanciation of variables satisfying at most $k$ clauses.

Reference: The Minimum Satisfiability Problem, Kohli, Krishnamurti, Mirchandani in Journal SIAM Journal on Discrete Mathematics 1994


Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

The answer for (1) is "unlikely".

It is simple to show (reduce from $Partition$) there exists no $\alpha$-approximation for Bin Packing, for any $\alpha<\frac{3}{2}$, unless $P=NP$.

That said, Crescenzi et al. have shown that unless the polynomial hierarchy collapses, Bin Packing is not APX-Hard.

As for (2), perhaps you could phrase it as "Does not admit $PTAS$ unless $P=NP$".


Solution/Hardness of the following (integer) budgeted problem?

Solving this exactly this ends up being $\mathsf{NP}$-hard.

The reduction I have doesn't pay much attention to the representation of the $f_i$'s. That said, the values of $f_i$ I end up giving can be computed efficiently, so this reduction works for any "black box" use of the $f_i$'s.

I'll give the reduction in two parts. Composing the two pieces gives the whole argument.

Firstly I claim that condition (iii) doesn't help very much, even when combined with condition (i). In particular, there is a reduction from the problem with (iii) ignored to the original version of the problem: Suppose there is an instance with $f_i$'s that are non-decreasing but otherwise arbitrary. Then we can make a new instance (whose data is denoted with primes (')) which has

$f_i'(0) \gets 0$,
for $x \ge 1$, $f_i'(x) \gets f_i(x-1) + A$ for an unspecified large constant $A$, and
$C_i' \gets C_i + 1$ and $C' \gets C + N$.

Note that if a given $f_i$ is initially non-decreasing, then so is the new $f_i'$, while the rest of condition (i) holds for $f_i'$.

To satisfy condition (iii), it suffices to make $A$ large enough. This follows from thinking geometrically about what condition (iii) imposes on the $f_i$s. In particular, for any particular $x$, let $\ell$ be the line through the origin and $(x,f_i(x))$. The condition (iii) says that every point $x' \ge x$ must have $(x',f_i(x'))$ below $\ell$, and every point $x' \le x$ must have $(x',f_i(x'))$ above $\ell$. Thinking of increasing $A$ as pulling the origin down while fixing the rest of $f_i$, it's clear that this condition limits toward the empty constraint as $A$ increases, since the lines $\ell$ become arbitrarily steep.

We also need to ensure this reduction is actually a reduction. We can accomplish this also by making $A$ large enough. In particular, it's easy to see that if $A$ is sufficiently large, then any optimal solution of the new instance must invest at least one unit into each startup (ie $x_i' \ge 1$ for any $x'$ optimal in the new instance). Once we have this, identifying each solution $x$ to the original instance with the solution $x'$ of the new instance defined by $x'_i \gets x_i + 1$ gives a correspondence between optimal solutions.
Now, if we ignore condition (iii), we can easily reduce from knapsack by making each $C_i$ the weight of item $i$, $C$ the capacity of the knapsack, and each $f_i$ "all-or-nothing" ($f_i(C_i) = C_i$ and $f_i(x) = 0$ otherwise). Then maximizing $\sum_i f_i(x_i)$ boils down to picking items that go into the knapsack. This is (in my opinion) easy to check and not the interesting part of this answer, so I won't belabor the details.


Communication lower bounds for partial boolean functions

(1) The way I like to think about partial functions is by defining a total function with three outputs e.g, $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1, *\}$.  The $*$ values are where your partial function is undefined.

(2)  You can still define a "monochromatic" rectangle in this case.  But here, you allow $*$'s to be in the rectangle.

A rectangle $R$ is monochromatic if $f(R) \subseteq \{0,*\}$ or $f(R) \subseteq \{1,*\}$.

From this, you can still use many of the standard lower bounds techniques such as fooling sets.

(3) As Marc mentions, you can always define trivial partial functions where the communication complexity is much less than the original.  For example, say the partial function TEQ is the EQ function, restricted to $(x,y)$ pairs such that $x \neq y$.

A partial function that people might care about is the Gap-Hamming-Distance function.
$GHD_{n,g}$ is takes two $n$ bit strings $x,y$ and returns $1$ if their Hamming distance is more than $n/2 + g$ and returns $0$ if their Hamming distance is less than $n/2 - g$.  (The Hamming distance $\Delta(x,y)$ is the number of $i$ where $x_i \neq y_i$.)

People are really particularly interested in the randomized communication complexity of $GHD$.  It's not hard to show that the gapless version (Alice/Bob want to tell if $\Delta(x,y)$ is greater than $n/2$ or not) requires $\Omega(n)$ bits of communication.

It turns out that when $g = O(\sqrt{n})$, you still need a linear amount of communication.  However, when $g = \omega(\sqrt{n})$, you can get away with only $O((n/g)^2)$ bits.  When $g = \Omega(n)$, you get a partial function with $O(1)$ communication complexity.

The $g = \Theta(\sqrt{n})$ case seems to be the "important case".  Indyk and Woodruff introduced this problem, gave a lower bound for one-way randomized protocols, and used it to get lower bounds for streaming algorithms that estimate frequency moments.  The state of the art lower bound is $\Omega(n)$ bits for any randomized protocol and is due to Chakrabarti and Regev.

Piotr Indyk and David Woodruff.  Tight Lower Bounds for the Distinct Elements Problem. FOCS 2003.

Amit Chakrabarti and Oded Regev.  An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. http://arxiv.org/pdf/1009.3460.


A promise problem to decide whether two given pure quantum states are close or far apart

A standard tool is the swap test, which receives two unentangled pure states |φ1⟩ and |φ2⟩ and answers “equal” with probability (1+|⟨φ1|φ2⟩|2)/2 and “not equal” with probability (1−|⟨φ1|φ2⟩|2)/2.  See [BCWW01] (Figure 1 shows the circuit).

[BCWW01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.  Quantum fingerprinting.  Physical Review Letters, 87, article 167902, Sept. 2001.  DOI: 10.1103/PhysRevLett.87.167902.  A preprint version: arXiv:quant-ph/0102001v1.


Non-uniform version for the whole polynomial hierarchy

Well, sure, we know things. I think this is a pretty standard nomenclature for it. This hierarchy collapses if and only if $\mathsf{PH}$ does, exercise:

For one direction, modify the proof of Karp-Lipton to show that if $\mathsf{NP} \subseteq \mathsf{coNP}/poly$ then $\mathsf{PH}$ collapses, and observe that this result relativizes
For the other direction, see the comments by Kaveh below.


The following language is a slight tweak of the usual LogCFL complete one so that it is LogDCFL complete.  The proof can be found in Sudborough's On the Tape Complexity of Deterministic Context-Free Languages.

Let $\Sigma = \{(_1,(_2,)_1, )_2\}$ and $T = \{[,],|\}$.  The following language over $\Sigma \cup T$ is LogDCFL-complete.  $L$ consists of words $$w_0\left[(_1l_1|(_2r_1\right]\ldots\left[(_1l_n|(_2r_n\right]$$ where $w_0, l_i, r_i \in \Sigma^*$ such that there exists $w_1, \ldots, w_n$ with $w_i = (_1l_i$ or $w_i = (_2r_i$ for all $i \geq 1$ and $w_0w_1\ldots w_n$ is parenthetically correct.


Complexity class separation in the presence of relativization barriers

H. Buhrman, L. Fortnow, and T. Thierauf. Nonrelativizing separations. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 8-12. IEEE, New York, 1998. (also from Lance's homepage).  They show unconditionally that $MA_{EXP} \not\subseteq P/poly$, and also build an oracle relative to which $MA_{EXP} \subseteq P/poly$.


Maximum number of internally vertex-disjoint odd length s-t paths

(It's not an answer, but I can't comment yet) I think the above answer doesn't work, because it doesn't guarantee that the paths would be vertex disjoint. One path could use u', and the other u" in G'; in G they would use the same vertex u.


automorphism in Cai-Furer-Immerman gadgets

You're missing the emptyset $\emptyset$ which is connected to all $b$'s. To get an  automorphism, you select a subset $T\subseteq \{1,...,k\}$ of even cardinality and then swaps $a_i$ with $b_i$ for each $i\in T$ and then adjusts the sets in the middle. In your example the graph is $$(a_1,\{12\}),(a_2,\{12\}),(b_1,\emptyset),(b_2,\emptyset).$$

Still in your example if $T=\emptyset$ you don't need to do anything and if
$T=\{1,2\}$ the automorphism is given by swapping $a_1$ with $b_1$, $a_2$ with $b_2$ and $\{1,2\}$ with $\emptyset$.

Now for the general case, we need to show that there is always a way of adjusting the middle vertices. We know that $T$ has even cardinality. So let $|T|=2r$. We just need to show that such an
automorphism exists if $|T|=2$ since otherwise we can apply the composition of $r$ automorphisms corresponding to partitioning $T$ into $r$ subsets of size $2$. Thus assume $T=\{i,j\}$.  Then the automorphism swaps $a_i$ with $b_i$,
$a_j$ with $b_j$, each middle vertex $S$ such that $S\cap\{i,j\}=\emptyset$ with the middle vertex $S\cup \{i,j\}$ (this can be seen in your example), and each subset $S$ such that $S\cap \{i,j\}=\{i\}$ with the subset such that $S\cap \{i,j\}= \{j\}$ (This you can see for $k=3$). Notice that this swapping process is an automorphism since for an index $p\neq \{i,j\}$ the edge relation between $a_p$, $b_p$ and these swapped vertices is completely preserved, and clearly the edge relation between $a_i,a_j,b_i,b_j$ is properly adjusted.

Finally to see that these are the only possible automorphisms, notice that each $a_i,b_i$ is colored with its own color. So they cannot be mapped to another pair $a_j,b_j$. Also notice that it is not possible to have an automorphism that maps an middle vertex to a middle vertex without swapping some $a_i$ with some $b_j$. $\square$


True Bit Complexity of matrix multiplication is $O(n^{4})$

No, the bit complexity of matrix multiplication on $M$-bit entries is $n^{\omega} (\log n)^{O(1)} \cdot M (\log M)^{O(1)}$, where $\omega < 2.4$ is the best known matrix multiplication exponent. Multiplication and addition of $M$-bit numbers can be done in $M (\log M)^2$ time. Multiplying two $M$-bit numbers yields a number which has no more than $2M$ bits. Adding $n$ numbers of $M$ bits each, yields a number which has no more than $M+\log n+O(1)$ bits. (Think about it: the sum is at most $n 2^M$, so the bit representation takes no more than $\log (n 2^M)+O(1)$ bits.)

References to fast integer multiplication algorithms can be found with a web search or wikipedia.


Long-Standing Conjectures later trivially proved by an implication

Erdös and Pósa proved that for any integer $k$ and any graph $G$ either $G$ has $k$ disjoint cycles or there is a set of size at most $f(k)$ vertices $S\in G$ such that $G\setminus S$ is a forest. (in their proof $f(k) \in O(k \cdot \log k)$).

The Erdös and Pósa property of a fixed graph $H$ known as the following (not a formal definition):

The class of graphs $\mathcal{C}$ admits the Erdös-Pósa property if there is a function $f$ such that for every graph $H\in \mathcal{C}$ and for any $k \in \mathbb{Z}$ and for any graph $G$ either there are $k$ disjoint isomorphic copy (w.r.t minor or subdivision) of $H$ in $G$ or there is a set of vertices $S\in G$, such that $|S|\le f(k)$ and $G\setminus S$ has no isomorphic copy of $H$.

After Erdös and Pósa's result for a class of cycles which are admitting this property, it was an open question to find a proper class $\mathcal{C}$. In graph minor V proved that every planar graph either has a bounded tree width or contains a big grid as a minor, by having the grid theorem in hand they showed that Erdös and Pósa property holds (for minor) if and only if $\mathcal{C}$ is a class of planar graphs. The problem still is open for subdivision, though. But the proof of theorem w.r.t minor is somehow simple and as best of my knowledge there is no proof without using the grid theorem.

Recent results for digraphs, provides answers for long standing open questions in the similar area for digraphs. e.g one very basic question was that is there a function $f$ such that for any graph $G$ and integers $k,l$, we either can find a set $S\subseteq V(G)$ of at most $f(k+l)$ vertices such that $G-S$ has no cycle of length at least $l$ or there are $k$ disjoint cycles of length at least $l$ in $G$. This is only a special case but for $l=2$ it was known as a Younger's conjecture. Before that Younger's conjecture was proven by Reed et al with quite a complicated approach.

It's worth to mention that still there are some quite non-trivial cases in digraphs. e.g Theorem 5.6 in the above paper is just a positive extension of younger's conjecture to a small class of weakly connected digraphs, but with the knowledge and mathematical tools that we have it's not trivial (or maybe we don't know a simple argument for that). Perhaps by providing a better characterisation for those graphs, there will be an easier way to prove it.


Importance of irrational numbers in computer science

The question displays a fundamental misunderstanding about the nature of what can be done with computers.  To correct this misunderstanding, I suggest getting a copy of the computer algebra software Maple and trying the commands

expand((1+sqrt(2))^5);
sin(Pi/4);

If computers can only deal with rational numbers, how do you explain the results?


Shortest distance problem with length as functions of time

This is known as the "time-dependent shortest path" problem.  Indeed research has been done for this problem; see for example the classical paper by Orda and Rom, and this recent SODA paper which proves that when the weight function of each edge is polynomial-size piecewise-linear, then the shortest path between two fixed points changes $n^{\Theta(\log n)}$ times.

Dijkstra's algorithm can indeed be used for this problem, when the waiting policy is imposed, that is, wait at a node if that reduces the final arriving time.  Without the waiting policy the situation is much wilder: the shortest path may not be simple, subpath of a shortest path might not be the shortest between the two endpoints of the subpath, paths traversing through infinite number of edges may have finite arriving time, etc.  See again the paper by Orda and Rom for more discussion.


Is the the spectral norm of a Boolean function bounded by the degree of its Fourier expansion?

It is a standard fact that if $f:\{-,1,1\}^n \to \{-1,1\}$ is a function of Fourier degree $d$, then its Fourier coefficients are multiples of $2^{-d+1}$. In particular, every non-zero coefficient must be at least $2^{-d+1}$ in absolute value. Therefore, by Parseval, there are at most $2^{2(d-1)}$ non-zero coefficients, and so the spectral norm of $f$ is at most
$$\sum_{S}|\hat{f}(S)| \leq \sqrt{2^{2(d-1)}}\sqrt{\sum_{S}\hat{f}(S)^2} = 2^{d-1}$$.

This bound is tight. For example the complete binary decision tree of depth $d$ has spectral norm $2^{d-1}$. This can be shown, e.g., by induction on $d$.
The address function has also maximal possible spectral norm.


Help in understanding Symbolic Execution

Don't worry too much about understanding everything in one source. Try reading several different articles and from their summaries and technical details, you may build up your own understanding.

Symbolic Execution for Software Testing: Three Decades Later, Cristian Cadar and Koushik Sen, 2013.
All You Ever Wanted to Know about Dynamic Taint Analysis and Forward Symbolic Execution (but Might Have Been Afraid to Ask), Edward J. Schwartz, Thanassis Avgerinos, David Brumley, 2010.
Symbolic Execution for Software Testing in Practice – Preliminary Assessment, Cristian Cadar, Patrice Godefroid, Sarfraz Khurshid, Corina S. Pasareanu, Koushik Sen, Nikolai Tillmann, Willem Visser, 2011
From Program to Logic: An Introduction, Patrice Godefroid and Shuvendu Lahiri, 2012
Talk on concolic testing, Koushik Sen
Summary of DART, Koushik Sen
Summary of CUTE, Koushik Sen
Automated Whitebox Fuzz Testing with SAGE, Patrice Godefroid
A Lab exercise, Koushik Sen

If you are looking to develop your understanding by starting from a security context, I recommend this excellent summary of pointers to program analysis material from the Reverse Engineering reddit.


How do minimally violated k-mod cuts work (intuitive explanation)?

Suppose you have an integer linear program, and it contains the following constraints:

x1 + x2 + x3 >= 1,
x1 + x2 + x4 >= 1,
x1 + x3 + x4 >= 1,
x2 + x3 + x4 >= 1.

If we set x1, ..., x4 to 1/3, we satisfy all of the constraints, but we don't have integer values.

Now multiply each constraint by 1/3 and sum them together. You obtain:

x1 + x2 + x3 + x4 >= 4/3.

Since the variables are integer-constrained, we can round up the right-hand side to obtain:

x1 + x2 + x3 + x4 >= 2.

This "cuts off" the above-mentioned fractional solution, so it is called a "cutting plane".

Since we multiplied the constraints by 1/3, the given cutting plane is a "mod-3" cut. Moreover, the fractional solution violates the cutting plane by 2/3, which is best possible. So the mod-3 cut is "maximally violated".

More generally, to obtain a mod-k cut, you multiply each constraint by a multiple of 1/k, before summing and rounding. Such a cut is "maximally violated" by a given fractional solution if it is violated by (k-1)/k.


What is a minimum vertex separator as in this definition?

It seems that $Sep(u, v)$ is a vertex separator extended to graphs where $u$ and $v$ are adjacent, by ignoring their common edge.

I assume the correct definition is

  ... vertex separator in $G$ if $\{u,v\} \notin E$ or in $G′=(V,E \setminus \{\{u,v\}\})$ otherwise.

As given, the definition makes no sense. There is no point in removing $\{u, v\}$ from $E$ if $\{u, v\} \notin E$ and, of course, $\{u, v\} \not\subset E$.

In this case, $Sep(u, v)$ can be $\emptyset$ if $\{u, v\}$ is the only edge connecting two components, or if the graph had two components to begin with.


Starting point for cache-oblivious algorithms?

I still find one of the original articles (I could also find it in Google Scholar) quite interesting and clear... in this case it is not extremely "scientific-y":

M. Frigo, C.E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS 99), p.285-297. 1999.

Also, here are Erik Demaine's video lectures on c-o algos, which are also very good.


Recent publications on NP ?= coNP question

NP is equal to coNP if and only if there are efficiently verifiable proofs of unsatisfiability. I.e., if and only if there exists a polynomial time turing machine $M$, which given any SAT formula $\phi$ and a string $\pi$ outputs $M(\phi, \pi) = 1$ if and only if $\phi$ is unsatisfiable. Most theorists believe there are no such efficient proofs, but proving that they don't exist would resolve the P vs NP question. However, there has been progress in showing that proofs of a restricted type must necessarily be superpolynomial in size. This is the subject of proof complexity: see the foundational paper by Cook and Reckhow, the  survey by Krajicek, or these lecture notes by Razborov.


EDITS: Added Lemmas 2 and 3.

Here's a partial answer:  You can reach position $N$

in $N$ moves using space $N^{O(\epsilon(N))}$, where $\epsilon(N) = 1/\sqrt{\log N}$.  (Lemma 1)
in $N^{1+\delta}$ moves using space $O(\log N)$ (for any constant $\delta>0$) (Lemma 2).

Also, we sketch a lower bound (Lemma 3): for a certain class of so-called well-behaved solutions, Lemma 1 is tight (up to constant factors in the exponent), and no such solution using poly-log space can reach position $N$ in time $O(N\,\text{polylog}\, N)$.

Lemma 1. For all $n$, it is possible to reach position $n$ in $n$ moves using space $$\exp(O(\sqrt{\log n}))~=~n^{O(1/\sqrt{\log n})}$$

Proof. The scheme is recursive, as shown in the figure below. We use the following notation:

$k$ is the number of levels in the recursion
$P(k)$ is the solution formed (with $k$ levels of recursion).
$N(k)$ is the maximum position reached by $P(k)$ (at time $N(k)$).
$S(k)$ is the space used by $P(k)$.
$L(k)$ is the number of layers used by $P(k)$, as illustrated below:

In the picture, time proceeds from top to bottom. The solution $P(k)$ does not stop at time $N(k)$, instead (for use in the recursion) it continues until time $2\,N(k)$, exactly reversing its moves, so as to return to a single pebble at time $2\,N(k)$.

The solid vertical lines partition the $L(k)$ layers of $P(k)$.  In the picture, $L(k)$ is five, so $P(k)$ consists of 5 layers.   Each of the $L(k)$ layers of $P(k)$ (except the rightmost) has two sub-problems, one at the top of the layer and one at the bottom, connected by a solid vertical line (representing a pebble that exists for that duration).  In the picture, there are five layers, so there are nine subproblems.  Generally, $P(k)$ is composed of $2\,L(k)-1$ subproblems. Each subproblem of $P(k)$ has solution $P(k-1)$.

The crucial observation for bounding the space is that, at any time, only two layers have "active" subproblems.  The rest contribute just one pebble each thus we have

$S(k) \le L(k) + 2\,S(k-1)$, and
$N(k) = L(k) \cdot N(k-1)$

Now, we choose $L(k)$ to fully determine $P(k)$.  I'm not sure if this choice is optimal, but it seems close: take $L(k) = 2^k$. Then the above recurrences give

$S(k) \le k\cdot 2^k$, and
$N(k) = 2^{k(k+1)/2}$

So, solving for $n=N(k)$,
we have $k \approx \sqrt {2 \log n}$
and $S(k) \approx \sqrt {2 \log n}\, 2^{\sqrt {2 \log n}} = \exp(O(\sqrt{\log n}))$.

This takes care of all positions $n$ in the set $\{N(k) : k\in\{1,2,\ldots\}\}$.  For arbitrary $n$, trim the bottom of the solution $P(k)$ for the smallest $k$ with $N(k)\ge n$.  The desired bound holds because $S(k) / S(k-1) = O(1)$.  QED

Lemma 2. For any $\delta>0$, for all $n$, it is possible to reach position $n$ in $n^{1+\delta}$ moves using space $O(\delta 2^{1/\delta}\log n).$

Proof. Modify the construction from the proof of Lemma 1 to delay starting each subproblem until the previous subproblem has finished, as shown below:

Let $T(k)$ denote the time for the modified solution $P(k)$ to finish. Now at each time step, only one layer has a subproblem that contributes more than one pebble, so

$S(k) \le L(k) + S(k-1)$,
$N(k) = L(k) \cdot N(k-1)$,
$T(k) = (2\,L(k)-1)\cdot T(k-1) \le 2\,L(k)\cdot T(k-1) \le 2^k N(k)$.

Choosing $L(k) = 2^{1/\delta}$, we get

$S(k) \le k 2^{1/\delta}$,
$N(k) = 2^{k/\delta}$,
$T(k) \le 2^k N(k)$.

Solving for $S = S(k)$ and $T=T(k)$ in terms of $n=N(k)$, we have $k=\delta \log n$, and

$S \le \delta 2^{1/\delta} \log n$, and
$T \le n^{1+\delta}$.

This takes care of all positions $n$ in the set $\{N(k) : k\in\{1,2,\ldots\}\}$.  For arbitrary $n$, trim the bottom of the solution $P(k)$ for the smallest $k$ with $N(k)\ge n$.  The desired bound holds because $S(k) / S(k-1) = O(1)$.  QED

The solutions in the proofs of Lemmas 1 and 2 are well-behaved, in that, for sufficiently large $n$, for each solution $P(n)$ that reaches position $n$ there is a position $k\le n/2$ such that only one pebble is ever placed at position $k$, and the solution decomposes into a (well-behaved) solution $P(N-k)$ for positions $k+1,k+2,\ldots,n$ and two (well-behaved) solutions $P(k)$, each for positions $1,2,\ldots,k$, connected by the pebble at position $k$.  With an appropriate definition of well-behaved, let $V(n)$ denote the minimum pebble volume (the sum over time of the number of pebbles at each time) for any well-behaved solution. The definition implies that for sufficiently large $n$, for $\delta=1>0$,
$$V(n) \ge \min_{k<n} V(n-k) + \max(n/2, (1+\delta) V(k)).$$

I conjecture that for every sufficiently large $n$ there is a well-behaved solution that minimizes pebble volume.  Maybe somebody can prove it?  (Or just that some near-optimal solution satisfies the recurrence...)

Recall that $\epsilon(n) = 1/\sqrt{\log n}$.

Lemma 3. For any constant $\delta>0$, the above recurrence implies $V(n) \ge  n^{1+\Omega(\epsilon(n))}$.

Before we sketch the proof of the lemma, note that it implies that any well-behaved solution that reaches position $n$ in $t$ steps has to take space at least $n^{1+\Omega(\epsilon(n))}/t$ at some step.  This yields corollaries such as:

Lemma 1 is tight up to constant factors in the exponent (for well-behaved solutions).
No well-behaved solution can reach position $n$ in $n\,\text{polylog}\, n$ time steps using space $\text{polylog}\, n$.  (Using here that $n^{\Omega(\epsilon(n))} = \exp(\Omega(\sqrt{\log n})) \not\subseteq \,\text{polylog}\, n$.)

Proof sketch.  We show $2 V(n) \ge f(n)$ where $f(n) = n^{1+c\epsilon(n)}$ for some sufficiently small constant $c.$  We assume WLOG that $n$ is arbitrarily large, because by taking $c>0$ small enough, we can ensure $2 V(n) \ge f(n)$ for any finite set of $n$ (using here that $V(n)\ge n$, say).

The lemma will follow inductively from the recurrence as long as, for all sufficiently large $n$, we have $f(n) \le \min_{k<n} f(n-k) + \max(n, 2 f(k))$, that is, $f(n) - f(n-k) \le \max(n, (1+\delta) f(k))$ for $k<n.$

Since $f$ is convex, we have $f(n) - f(n-k) \le k f'(n)$.  So it suffices if $k f'(n) \le \max(n, (1+\delta) f(k)).$

By a short calculation (using $f(n)/n = e^{c\sqrt{\log n}}$ and $f'(n)=(f(n)/n)(1+c/(2\sqrt{\log n})),$ and using a change of variables $x = \sqrt{\log k}$ and $y=\sqrt{\log n}$), this inequality is equivalent to the following:
for all sufficiently large $y$ and $x\le y$, $e^{cy}(1+c/(2y)) \le \max(e^{y^2 - x^2}, (1+\delta) e^{cx})$.  Since $1+z\le e^z$, and $e^z\le 1+2z$ for $z\le 1$, it suffices to show
$e^{cy + c/(2y)} \le \max(e^{y^2 - x^2}, e^{2\delta+cx}),$ that is,
$$cy + c/(2y) \le \max(y^2 - x^2, 2\delta+cx).$$

If $y \le x + 0.1\delta/c$, then $cy+c/(2y) \le cx + 0.2\delta$ (for large $y$) and we are done, so assume $y\ge x + 0.1\delta/c$.  Then $y^2-x^2 \ge 0.1y\delta/c$ (for large $y$), so it suffices to show
$$cy + c/(2y) \le 0.1 y\delta/c.$$
This holds for sufficiently small $c$ and large $y.$  QED


A Boolean function that is not constant on affine subspaces of large enough dimension

The objects you are searching for are called seedless affine dispersers with one output bit.  More generally, a seedless disperser with one output bit for a family $\mathcal{F}$ of subsets of $\{0,1\}^n$ is a function $f : \{0,1\}^n \to \{0,1\}$ such that on any subset $S \in \mathcal{F}$, the function $f$ is not constant.  Here, you are interested in $\mathcal{F}$ being the family of affine subspaces

Ben-Sasson and Kopparty in "Affine Dispersers from Subspace Polynomials" explicitly construct seedless affine dispersers for subspaces of dimension at least $6n^{4/5}$.  The full details of the disperser are a bit too complicated to describe here.

A simpler case also discussed in the paper is when we want an affine disperser for subspaces of dimension $2n/5+10$.  Then, their construction views ${\mathbb{F}}_2^n$ as ${\mathbb{F}}_{2^n}$ and specifies the disperser to be $f(x) = Tr(x^7)$, where $Tr: {\mathbb{F}}_{2^n} \to {\mathbb{F}}_2$ denotes the trace map: $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$.  A key property of the trace map is that $Tr(x+y) = Tr(x) + Tr(y)$.


Las Vegas vs Monte Carlo randomized decision tree complexity

As far as I know, this is still open. A very recent paper that mentions these quantities and some bounds is Aaronson et al: Weak parity (see http://arxiv.org/abs/1312.0036). You can also see chapter 14 of Jukna: Boolean funcions and the 1999 (still beats 1998!) survey by Buhrman and de Wolf. Another very recent paper about randomized decision tree complexity is Magniez et al: http://arxiv.org/abs/1309.7565

Finally, a short summary I made for myself last month (without defs):

R2<=R0<=D<=n

D<=N0*N1<=C^2<=R0^2

s<=bs<=C<=s*bs<=bs^2 (new: [Gilmer-Saks-Srinivasan]: there is f s.t. bs^2(f)=O(C(f)))

D<=N1*bs<=bs^3<=(3R2)^3

deg<=D<=bs*deg<=deg^3 (new: [Tal]: bs<=deg^2)

D<=N1*deg

C<=bs*deg^2<=deg^4

Sensitivity conjecture is that s is also polynomially related to other parameters.


Min weight perfect matching with even number of red edges

I think your problem is solvable in randomized polynomial time, if the weights are bounded polynomially in the size of the graph. You can use an approach based on the algebraic matching algorithm by Mulmuley, Vazirani, and Vazirani. It has been useful for similar applications in the past, see for example Proposition 9 and the preceding discussion in Daniel Marx's paper https://doi.org/10.1016/j.ipl.2003.09.016 .

In randomized polynomial time, you can determine whether there is a perfect matching whose weight is exactly a prescribed value, in an integer-weighted graph with weights bounded polynomially in the graph size. Now, say your graph has $n$ vertices and the maximum weight is $W$. Re-weight the red edges of the graph as follows: if the original weight was x, the new weight becomes $(nW+1) + x$. (I also assume all weights are nonnegative, which can easily be done by adding the same constant value to all of them.) Then observe the following: any perfect matching in the re-weighted graph whose total weight is in the interval $[0 ... nW]$, is a perfect matching with 0 red edges. If its total weight is in the interval $[2(nW+1) ... 2(nW+1) + nW]$, then it is a perfect matching with exactly 2 red edges. In general, from the weight range you can infer the number of red edges.

Hence to find a minimum-weight matching with an even number of red edges, it suffices to go over all the weight ranges corresponding to matchings with an even number of red edges, testing for each weight in that range whether there is a perfect matching of that weight, and scaling the weight of each re-weighted matching back based on the number of red edges contained in it, to figure out which of these corresponds to the minimum-weight even-red perfect matching in your original graph. By standard self-reduction techniques, you can then also extract the matching itself rather than just the value, but you might have to boost the success probability by doing multiple trials to get an overall good success probability when doing self-reduction.


Answer to questions 1 and 2: No. This is also the answer to 3 if $M$ is required to always halt (isn't this implied by the definition of a learner, or do you mean the program produced by $M$ must always halt?). Here's a proof for 1 (2 and 3 work pretty much the same way)

Suppose there's an algorithm $A$ which takes the description of a learner $N$ and outputs a learner $M$ which behaves differently. Let $N$ be a learner which runs $A$ on its own description, then runs the output $A(N) = M$ on the input text to produce a program that enumerates some set. By definition of $A$, $N$ and $M$ behave differently, but by construction they behave identically, contradicting the existence of $A$.

This same argument can be pretty easily modified to show that 2 is impossible. It can also be used to show that 3 is impossible if $M$ must always halt.

Not a real answer for question 4, but you might find this helpful: A prudent learner cannot converge on both every text for a finite set and on every text for the set of all natural numbers. Let $N$ be a learner that converges on every text for a finite set. Now, consider the following text for the set of all natural numbers. It contains all numbers in order, separated by differing numbers of 1s. After $i$, it contains enough 1s that $N$ will return a program which enumerates the set $1,\ldots,i$. $N$ will do this because it converges on every finite set. Because it will return a program enumerating a finite set after every prefix of this text, it does not converge on this text.

So if you let $M_1$ be the learner which converges on all finite sets and $M_2$ be the learner which converges on all texts for the set of all natural numbers, at least one of $M_1,M_2$ satisfies the criteria in question 4. You can extend this to a countably infinite set of learners in which at least all but one learner satisfies the criteria in question 4 by producing a machine $M_i$ for each natural number $i$ which converges on all finite sets which don't contain powers of the $i$th prime and also converges on the set of all powers of the $i$th prime. By similar logic as above, $N$ can't converge on all sets that any two of these converge on.

You can use this set of learners to find an $M$ satisfying 4 with arbitrarily high probability.


TQBF (True Quantified Boolean Formulas) is in E and won't be in NP unless NP = PSPACE.

A language in NP-E is trickier. Such a language would also be in NP-NTIME(n) and we don't have great examples of those. You could use a succinct representation like

$ L = \{ C \ |\ $Circuit $C$ describes a graph $G$ on $|C|^5$ nodes where $G$ is 3-colorable$\}$.

$L$ is in NP, unlikely to be in $E$ but not that natural.


Generalizing the "median trick" to higher dimensions?

What you're looking for is almost the same a robust central tendency: a way of reducing a cloud of data points to a single point, such that if many of the data points are close to some "ground truth" but the rest of them are arbitrarily far away, then your output will also be close to the ground truth. The "breakdown point" of such a method is the fraction of arbitrarily-bad outliers it can tolerate. The difference is that in your case you want to replace "close to" by "within the convex hull of".

One way to capture this is with the notion of Tukey depth. A point has Tukey depth $p$ (with respect to a given set of $n$ data points) if every halfspace containing the given point also contains at least $pn$ data points. If there is a good convex subspace that you want to be inside, then a point with Tukey depth $p$ will be inside it as long as there are at least $(1-p)n$ of the data points inside it. So the breakdown point of this method is the largest value of $p$ that you can attain.

Unfortunately this breakdown point is $1/(d+1)$, not close to 1/2, both for Tukey depth and for your problem. Here's why: if your data are clustered near the $d+1$ vertices of a simplex, then as long as fewer than $1/(d+1)$ fraction of them are outliers (but you don't know which ones) then any point in the simplex is safe to pick as it will always be within the convex hull of the non-outliers. But if more than $1/(d+1)$ of the points can be outliers, there is nowhere that is safe to pick: whichever point in the simplex you choose, the outliers could be all of the points from the nearest simplex vertex, and you'd be outside the hull of the non-outliers.

If you're willing to tolerate a worse breakdown point, more like $O(1/d^2)$, there's a randomized method for finding a deep point that's polynomial in both $n$ and $d$: see my paper

Approximating center points with iterated Radon points,
K. Clarkson, D. Eppstein, G.L. Miller, C. Sturtivant, and S.-H. Teng,
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 91–98,
Int. J. Comp. Geom. & Appl. 6 (3): 357–377, 1996,
http://kenclarkson.org/center/p.pdf


$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$

As proved in [1], Boolean languages computable in $\mathrm P_\mathbb C$ are in $\mathrm{BPP}$. (They state it for $\mathrm P_\mathbb R$ without inequality tests, which amounts to the same thing.) On the other hand, Boolean NP-languages are computable in $\mathrm{NP}_\mathbb C$, hence

$$\mathrm{NP}_\mathbb C=\mathrm P_\mathbb C\implies\mathrm{NP}\subseteq\mathrm{BPP},$$

which is another way to state Smale’s claim. While it is not directly relevant to the question, note that also

$$\mathrm{NP}\subseteq\mathrm{BPP}\iff\mathrm{NP}=\mathrm{RP}.$$

[1] F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther: On real Turing machines that toss coins. Proceedings of ACM STOC’95, pp. 335–342, 1995. doi:10.1145/225058.225155; preprint


Lambda: The Ultimate Imperative - who is Jensen?

Jensen's device was developed by Jørn Jensen, who worked on one of the earliest ALGOL 60 compilers (this answer is based on comment by Kristoffer Arnsfelt Hansen).


Compute lowest dimensional polytope from a given set of sign vectors

This is equivalent to computing the sign rank of a matrix, which is NP-hard as shown in this paper. So you cannot expect too efficient of an algorithm.


How about Welzl's randomized algorithm for minimal enclosing ellipsoids? It has recursion depth O(d) where d is the dimension of the space.

I know next to nothing about derandomization, so this might not be what you're looking for. If my example doesn't qualify (maybe by your definition it only makes inessential use of recursion?), perhaps you could clarify why that is. That would increase the chances of higher quality, more pertinent answers from others.


Graph planarity testing via adjacency matrix

Ignoring trivial responses like, recreate the graph from the matrix and apply any standard planarity algorithm, the closest I know of to a matrix-based planarity test is Whitney's planarity criterion. But it uses the incidence matrix, not the adjacency matrix, and is a mathematical criterion rather than a polynomial time algorithm.

It states that a graph is planar if and only if its matroid (the independence matroid of the columns of the signed incidence matrix) has a dual (the matroid for the dual space of the column space) which is also a graphic matroid.


equivalent way(s) of expressing P=?NP problem in linear programming?

This answer is for your "somewhat related question":

In the following recent paper, Klee-Minty cubes were used explicitly to show that  there exists a pivoting rule for the simplex method (not one of the standard ones, like Dantzig's pivoting rule analysed by Disser and Skutella) for which it is PSPACE-complete to decide whether a variable enters the basis for the simplex method with this pivoting rule. It was left open (Conjecture 3 in the paper) whether the same result holds for Dantzig's pivot rule.

I. Adler, C. Papadimitriou, and A. Rubinstein (2014).
On Simplex Pivoting Rules and Complexity Theory.
In Proc. of IPCO, pp. 13-24.

In the following paper we prove that conjecture and strengthen Disser and Skutella's result to show two PSPACE-completeness results for the simplex method with Dantzig's pivoting rule (one for whether a variable enters the basis "along the way" and another for whether a variable is in the final solution found by Dantzig's pivot rule).

J. Fearnley and R. Savani (2015).
The Complexity of the Simplex Method. In Proc. of STOC, pp. 201-208.
http://arxiv.org/abs/1404.0605

We use the known connection between linear programs and Markov decision processes (MDPs). A central part of our construction are the exponential-time examples due to Condon and Melekopoglou for single-switch policy iteration for MDPs. Those examples use a reflected binary Gray code, as used for Klee-Minty cubes. We use a modification of those examples as a clock to drive iterated circuit evaluation in our construction.


Is there a Time Hierarchy theorem for PH?

Yes. For example, the usual proofs of the time hierarchy theorem (by directly simulating arbitrary machines) can be used to show that for every $c \geq 1$, $\Sigma_c TIME[n^k]$ is not a subset of $\Pi_c TIME[n^{k-1}]$. The reason for switching from $\Sigma$ to $\Pi$ is that, in this diagonalization argument, we have to do the "opposite" of the machine we're simulating, so we have to run in universal mode when the simulating machine is in existential mode, and vice-versa.

You can also get a result like this without switching from $\Sigma$ to $\Pi$: for every $c \geq 1$, $\Sigma_c TIME[n^k]$ is not a subset of $\Sigma_c TIME[n^{k-1}]$. This can be done using the proof of the time hierarchy due to Zak (reference: "A Turing machine time hierarchy", Theoretical Computer Science 26(3):327--333, 1983). For an explicit reference to this version of the time hierarchy theorem, see Dieter van Melkebeek's "A Survey of Lower Bounds for Satisfiability and Related Problems" (available on his home page).


Impossibility in Computability and Complexity: always ultimately due to diagonal arguments?

The standard comparison-model lower bound for sorting, and most cell probe model lower bounds for data structures, are unconditional (for computing within the model but you could say the same about Turing machine lower bounds) and depend on information theory rather than diagonalization.


Does this paper imply graph isomorphism is polynomial for cubic and $4$-regular graphs?

Their paper doesn't say anything about general regular graphs. Note that the $b$ is constant. Actually all of their excluded subgraphs are constant. Their polynomial time algorithm is consist of considering all possible $K_{2b+1}$'s in that case. This causes to running time $\Omega(n^{2b+1})$. Means if we want to use their algorithm for $r$-regular graph then we should use running time $\Omega(n^{2r+1})$, means when $r$ is not fix their algorithm is not polynomial time in the size of input. Actually we can say that they proved the problem in that case belongs to XP when the problem parametrized by $b$. Don't mix parametrized complexity with usual polynomial time algorithms.


Compression algorithms for low-complexity strings?

No, at least not in the TM model, i.e., for Kolmogorov complexity. Given $g(x) \leq f(x) \leq |x|$ for all $x$ where $g$ is monotonic and unbounded and $f$ is recursive, it is not possible to enumerate an infinite subset of $\{ x : K(x) > f(x)\}$.

Suppose for the sake of contradiction there exists a recursive function $h$, the low-complexity compression algorithm, which on input $x$ outputs a TM that reproduces $x$ and has the following additional property: Let $A:\mathbb{N} \rightarrow \mathbb{N}$ and $B:\mathbb{N} \rightarrow \mathbb{N}$ be given such that both are recursive, $A(|x|) \leq B(|x|) \leq |x|$ for all $x$, and $A$ is unbounded. Then $\forall x, K(x) \leq A(|x|) \implies |h(x)| \leq B(|x|)$.

Now choose $f(x) = A(|x|)$. We wish to enumerate an infinite subset of $\{x: K(x) > A(|x|)\}$. Note that there are infinite $x$ such that $K(x) > B(|x|)$ because $B(|x|) \leq |x|$. For any such $x$, $|h(x)| \geq K(x)$ by the definition of $K$ so $|h(x)| > B(|x|)$. Then for a generic string $x$, $|h(x)| > B(|x|) \implies K(x) > A(|x|)$ and we can enumerate an infinite subset of $\{x: K(x) > A(|x|)\}$, a contradiction.


Functions and Counting Problems in Streaming Computation

I don't know if there's a list of canonical hard problems, but there is a list of open problems in streaming as maintained by Andrew McGregor. This is not limited to the specific models you're referring to  though.