Implications of unprovability of $P\neq NP$

Your question might better be phrased, "How would complexity theory be affected by the discovery of a proof that P = NP is formally independent of some strong axiomatic system?"

It's a little hard to answer this question in the abstract, i.e., in the absence of seeing the details of the proof.  As Aaronson mentions in his paper, proving the independence of P = NP would require radically new ideas, not just about complexity theory, but about how to prove independence statements.  How can we predict the consequences of a radical breakthrough whose shape we currently can't even guess at?

Still, there are a couple of observations we can make.  In the wake of the proof of the independence of the continuum hypothesis from ZFC (and later from ZFC + large cardinals), a sizable number of people have come around to the point of view that the continuum hypothesis is neither true nor false.  We could ask whether people will similarly come to the conclusion that P = NP is "neither true nor false" in the wake of an independence proof (for the sake of argument, let's suppose that P = NP is proved independent of ZFC + any large cardinal axiom).  My guess is not.  Aaronson basically says that he wouldn't.  Goedel's 2nd incompleteness theorem hasn't led anyone that I know of to argue that "ZFC is consistent" is neither true nor false.  P = NP is essentially an arithmetical statement, and most people have strong intuitions that arithmetical statements—or at least arithmetical statements as simple as "P = NP" is—must be either true or false.  An independence proof would just be interpreted as saying that we have no way of determining which of P = NP and P $\ne$ NP is the case.

One can also ask whether people would interpret this state of affairs as telling us that there is something "wrong" with our definitions of P and NP.  Perhaps we should then redo the foundations of complexity theory with new definitions that are more tractable to work with?  At this point I think we are in the realm of wild and unfruitful speculation, where we're trying to cross bridges that we haven't gotten to and trying to fix things that ain't broke yet.  Furthermore, it's not even clear that anything would be "broken" in this scenario.  Set theorists are perfectly happy assuming any large cardinal axioms that they find convenient.  Similarly, complexity theorists might also, in this hypothetical future world, be perfectly happy assuming any separation axioms that they believe are true, even though they're provably unprovable.

In short, nothing much follows logically from an independence proof of P = NP.  The face of complexity theory might change radically in the light of such a fantastic breakthrough, but we'll just have to wait and see what the breakthrough looks like.


Bin packing approximation with different bin sizes

I started a project under MIT license to try to solve this problem.  Currently it uses the 'best fit' approach.  Sorts 'items' from largest to smallest and sorts bins from smallest to largest.  Finds first bin that is large enough to use that has ALREADY been used (if possible).  Let's see if we can make it a good enough solution for all.

https://github.com/asharif/packit4.me


Results/concepts that also proved useful outside of their "home areas"

One thing that immediately comes to mind is that graph k-coloring is used in compilers for register allocation. An instance of register allocation for k registers is solved by reducing into an instance of k-coloring. See, for example, section 8.8 of Aho, Lam, Sethi and Ullman (i.e. Dragon Book).


I'll answer the second part of the question.

I. Eigenvalues and Eigenfunctions

Let's first consider the one dimensional case $n=1$. It is easy to check that the operator $R_{p_1,p_2}$ has two eigenfunctions: $1$ and
$$\xi(x) = (p_1+p_2)x - p_1 =
\begin{cases}
-p_1, &\text{ if } x =0,\\
p_2, &\text{ if } x =1.
\end{cases}$$
with eigenvalues $1$ and $1-p_1 - p_2$, respectively.

Now consider the general case. For $S\subset \{1,\dots,n\}$, let $\xi_S(x) = \prod_{i\in S} \xi(x_i)$. Observe that $\xi_S$ is an eigenfunction of $R_{p_1,p_2}$. Indeed since all variables $x_i$ are independent, we have
\begin{align*}
R_{p_1,p_2}(\xi(x)) &= R_{p_1,p_2}\left(\prod_{i\in S} \xi(x_i)\right) = \prod_{i\in S} R_{p_1,p_2}(\xi(x_i)) \\
&= \prod_{i\in S}\left((1-p_1 - p_2)\xi(x_i)\right) = (1-p_1 - p_2)^{|S|} \xi_S(x).
\end{align*}

We get that $\xi_S(x)$ is an eigenfunction of $R_{p_1,p_2}$ with eigenvalue $(1-p_1-p_2)^{|S|}$ for every $S\subset \{1,\dots,n\}$. Since functions $\xi_S(x)$ span the whole space, $R_{p_1,p_2}$ has no other eigenfunctions (that are not linear combinations of $\xi_S(x)$).

II. Multiplicative Property

In general, the “multiplicative property” doesn't hold for $R_{p_1,p_2}$ since the eigenbasis of $R_{p_1,p_2}$ depends on $p_1$ and $p_2$. However, we have
$$R_{p_1,p_2}^2 = R_{p_1',p_2'},$$
where $p_1' = 2p_1- (p_1+p_2)p_1$ and $p_2' = 2p_2- (p_1+p_2)p_2$. To verify that, first note that $R_{p_1,p_2}$ and $R_{p_1',p_2'}$ have the same set of eigenfunctions $\{\xi_S\}$. We have,
$$R_{p_1,p_2}^2(\xi_S) = (1-p_1-p_2)^{2|S|} \xi_S=(1-p_1'-p_2')^{|S|}\xi_S = R_{p_1',p_2'} (\xi_S) $$
since
\begin{align*}
 1-p_1'-p_2' &= 1 - p_1\cdot (2- (p_1+p_2)) - p_2\cdot (2- (p_1+p_2)) \\
&= 1 - (p_1+p+2) (2- (p_1+p_2)) \\
&= 1 - 2(p_1 +p_2) + (p_1 + p_2)^2 = (1-p_1-p_2)^2.
\end{align*}

III. Relation to the Bonami—Beckner operator

Let us think of functions from $\{0,1\}^n$ to ${\mathbb R}$ as polylinear polynomials. Let $\delta = \frac{1}{2}\cdot \frac{p_1-p_2}{p_1+p_2}$. Consider the operator
$$A_{\delta}(f) = f(x_1 + \delta, \dots, x_n + \delta).$$
It maps every multilinear polynomial $f$ to a multilinear polynomial $A[f]$. We have,
$$R_{p_1,p_2}(f) = A_{\delta}^{-1} T_{\varepsilon}A_{\delta}(f),$$
where $\varepsilon = 1 - p_1 - p_2$. Note that parts I and II follow from this formula and properties of the Bonami—Beckner operator.


When is it hard to invert a sparse matrix?

Jacobi or Gauss-Seidel are not really state of the art for solving systems of linear equations. It is more done by preconditioned conjugated gradient (for symmetric positive semi-definite matrices) and preconditioned (F)GMRES (or other Krylov subspace methods) for arbitrary matrices.
The crucial part here is the preconditioner. There was recently (=21th century) huge progress with very efficient preconditioners for Laplacian systems. In Hardness Results for Structured Linear Systems by Rasmus Kyng and Peng Zhang, it is shown

that if the nearly-linear time solvers for Laplacian matrices and their generalizations can be extended to solve just slightly larger families of linear systems, then they can be used to quickly solve all systems of linear equations over the reals.

They go on to say:

This result can be viewed either positively or negatively: either we will develop nearly-linear time algorithms for solving all systems of linear equations over the reals, or progress on the families we can solve in nearly-linear time will soon halt.

But even beyond such deep theory, one can say something about the computational cost of a preconditioner and its efficiency. A matrix is hard to solve, if its condition number is big. The task of the preconditioner is to reduce the condition number, by approximately inverting the matrix. The (asymptotic) computational cost (vs efficiency) can estimated based on separators of the sparse matrix. For example, to separate a N x N x N grid in 3D, you need a separator of size O(N^2). If you would not approximate the system on the separator, you would get a full matrix of size(N^2), i.e. N^4 non-zero entries. So you need to approximate the clique graph on the separator with a sparse (directed) graph, probably an extender graph. One fast preconditioner algorithm for Laplacian systems approximates the clique (among the neighbors of the eliminated node, which has to be added to the graph) in each elimination step by a tree. This is good enough to keep the computational cost under control. The efficiency of this preconditioner in reducing the condition number is also often extremely good in practice, but proving this theoretically would still be a nice achievement.
A recent result on fast solving sparse linear systems replaced the Krylov subspace methods mentioned above by "an efficient, randomized implementation of the block Krylov method": Solving Sparse Linear Systems Faster than Matrix Multiplication by Richard Peng and Santosh Vempala. Even so the paper title says "solving ... faster than matrix multiplication," this does not answer the question asked here, because the paper means dense matrix multiplication, but the question here is about sparse matrix multiplication.


Example of an context-sensitive language with a specific number of words of length $n$

The language
$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor n^\delta\rfloor}0^{n-\lfloor n^\delta\rfloor}$$
is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\lfloor n^\delta\rfloor}$.
The language
$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor(\log n)^c\rfloor}0^{n-\lfloor(\log n)^c\rfloor}$$
is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\lfloor(\log n)^c\rfloor}$.
You can construct any number of examples like this. Basically, if $f\colon\mathbb N\to\mathbb N$ is any function such that given $n$ in binary, $f(n)$ (in binary) is computable in space $O(n)$ (which is exponential space in terms of the length of its input) and $f(n)\le2^n$, then there exist languages $L\in\mathrm{DSPACE}(n)\subseteq\mathrm{CSL}$ such that $s_L(n)=f(n)$, such as
$$L=\bigcup_{n\in\mathbb N}\bigl\{w\in\{0,1\}^n:w<_\mathrm{Lex}\operatorname{bin}(f(n))\bigr\},$$
where $<_\mathrm{Lex}$ denotes lexicographic order, and $\operatorname{bin}(f(n))\in\{0,1\}^n$ is the binary expansion of $f(n)$.


What is the minimum number of bits required to store a sudoku puzzle?

Along the same lines as ratchet freak's answer, if you fill in the non-starred cells in the following matrix, a 3x3 box at a time, always choosing the next box to fill in to be one that shares rows or columns with a box you've already filled in, you get a pattern like the following for the number of choices per step (filling in the top middle box first, the top right box next, etc).

In each 3x3 box after the first, once you've filled in one row or column of the box, three of the remaining six digits are localized to a single row. Choose their locations first, and then fill in the remaining three cells. (So the actual order of which cells to fill in might vary depending on what you already know, but the number of choices is never more than what I've shown.)

After you've filled in these cells the stars are all determined.

* * *    9 8 7    6 5 4
* * *    6 5 4    3 3 2
* * *    3 2 1    3 2 1

6 5 4    * * *    6 3 3
3 3 2    * * *    5 3 2
3 2 1    * * *    4 2 1

6 3 3    6 5 4    * * *
5 3 2    3 3 2    * * *
4 2 1    3 2 1    * * *

If I've calculated correctly, this gives 87 bits. There's some additional savings to be had in the last 3x3 block, per the comment by Peter Shor: every value is localized to one of four cells, and every row contains at least one cell with only four possible values, so certainly the factors in that block should start with 4 not 6, but I don't understand the remaining factors in Shor's answer.


How could one define a language based on the Calculus of Constructions, but with fixed points and EAL-style duplication restrictions?

Dependency is interesting because of equality, and equality is adjoint to contraction. As a result, substructural calculi (which in general omit contraction) do not have an obvious notion of equality.

In type-theoretic language, equality is characterized by the following inference rule[*] being valid in both directions (top-to-bottom and bottom-to-top):

$$
\begin{array}{l}
\Gamma, x:\tau, y:\tau \;|\; \Theta, x = y : \tau \vdash P \\
\hline
\Gamma, z:\tau \;|\; [z/x,z/y]\Theta : \tau \vdash [z/x,z/y]P \\
\end{array}
$$

This says that if you have two free variables $x$ and $y$, and an assumption they are equal, that lets you derive the same things are replacing them both by a variable $z$. Note that going from top to bottom is a contraction -- the number of uses of $z$ will be the sum of the uses of $x$ and $y$.

As a result, interpreting the meaning of equality in linear calculi is tricky. The obvious thing to do is to restrict your attention to types which are contractible, but it turns out there are multiple incomparable ways of doing so!

One idea, originating in the work on Linear LF by Cervesato and Pfenning, is to only permit dependency on exponential types.

I, with Nick Benton and Pierre Pradic, gave another calculus based on another version of this idea, which exploited Benton and Wadler's characterization of linear logic in terms of an adjunction between a cartesian closed category and a monoidal closed category. Basically, we just made the CCC part dependent, so that linear types could be dependent on intuitionistic types, but not vice-versa. (However, you could be dependent on closed linear terms, since they are duplicable.)

In his PhD thesis, Matthijs Vákár gave a denotational model of Linear LF. His semantics was based on Benton-Wadler adjoint models, so it should also interpret our calculus.

The other main idea is due to Conor McBride, with subsequent refinements by Bob Atkey. His idea is based on resource interpretations of linear logic, with the idea that if you forget the resource usage information on a linear term, you are left with a nonlinear term approximating it. Then, you can depend on that nonlinear term.

[*] This inference rule is for the case of first-order logic. The dependent case is more complicated, but the underlying issues are the same.


Approximating transitive reduction of a transitive closure of a dag

Due to [Aho, Garey, and Ullman, The transitive reduction of a directed graph, 1972]; $G^t = G - GG^+$, where $G^t$ is the transitive reduction of $G$. In this particular case, $G = G^+$. So, we can conclude $G^t = G - G^2$. Although this result does not lead to a linear non-approximate algorithm, I hope such an observation would be helpful in this context.


Almost every algorithm that works in the PAC model (with the exception of parity learning algorithms) can be made to work in the SQ model. See e.g. this paper of Blum et al. in which several popular algorithms are translated into their SQ equivalents (Practical Privacy: the SuLQ framework). The paper is in principle concerned with "privacy", but you can ignore that -- it is really just implementing algorithms with SQ queries.

Agnostic learning, on the other hand, is much harder in the SQ model: computational issues aside (though these are important), the sample complexity required for agnostic learning is roughly the same as that required for exact learning, if you actually have access to the data points. On the other hand, agnostic learning becomes much harder in the SQ model -- you will usually need to make superpolynomially many queries, even for classes as simple as monotone disjunctions. See this paper by Feldman (A complete characterization of statistical query learning with applications to evolvability) or this recent paper by Gupta et al. (Privately Releasing Conjunctions and the Statistical Query Barrier)


Constructing vectors in general position

If you choose $\mathbf{a}$ uniformly at random from the hypercube $[0,1]^n$, the matrix $[\mathbf{A}~ \mathbf{a}]$ will have the desired property with probability $1$.


Parallel sorting: introduction and state of research

Parallel algorithms are very dependent on the computation model, and there are a lot of different parallel models. So, it is difficult to have a representative general introduction.

I teach parallel algorithms following the pattern I first saw in a similar course by my PhD advisor. I spend the first few lectures on sorting networks, covering Batcher's constructions, and AKS very briefly. Then I introduce a specific general-purpose parallel computation model (BSP suits me very well), and cover five or six textbook-type algorithmic problems, first recalling their sequential algorithms, and then discussing with students how to parallelize them efficiently.

Sorting is one of these problems. Its BSP solution is very elegant: parallel sorting by regular sampling (presented in the original paper by Shi and Schaeffer, and also Quinn's book "Parallel Computing"). It does realise the relevant lower bounds in computation, communication and, surprisingly, also synchronisation - by synchronising the whole computation only a constant number of times (whereas looking at mergesort and AKS, one would expect to have to synchronize O(log n) times). The optimality proof is non-trivial, yet simple enough to be presented in an undergraduate class in 20 minutes - so for me, it is indeed a very good and handy example to teach.

Another good example is Leighton's columnsort - I am not teaching it, but would be if I had a bit more time.


Approximation for counting the number of simple $s$-$t$ paths in a general graph

This problem should be NP-hard by reducing from the maximum length of s-t paths.

The reduction simply replace every edge by, say, $k$ parallel edges. (If you are uncomfortable with a multi-graph, replace each edge by a path of length 2.) The effect of this is that the number $C_{\ell}$ of paths of length $\ell$ becomes $k^\ell C_{\ell}$. Thus, if $k$ is suitably large, the term corresponding to the longest paths in the original graph will dominate everything else (even if $C_{\ell_{max}}=1$). From there you can easily recover the length of the longest s-t path.


What are the major research issues in distributed transactions?

There are many research areas both in the theory and practice of distributed databases.

One of the main practical challenges is that of implementing efficient concurrency control mechanisms for distributed and geo-replicated databases. In order to execute
transactions efficiently, such mechanisms can provide weaker guarantees than serialisability, which requires that transactions appear to be executed sequentially. An alternative to serialisability is that of settling for Snapshot Isolation [1], but this has been proved to scale poorly to geo-replicated and distributed systems.
At the current state of the art, two different variants of Snapshot Isolation (SI) have been defined to deal with concurrency control in geo-replicated systems:
Parallel Snapshot Isolation (PSI) [2], and Non Monotonic Snapshot Isolation (NMSI) [3,4].
As for what it concerns distributed databases (i.e. where data are sharded among different sites), a variant of snapshot isolation
for distributed system has been proposed very recently [5].

Having different notions of isolation levels which provide weaker guarantees than serialisability, another important question is that of writing programs in a way so that executions still appear to be serialisable. A sound criterion for Snapshot Isolation has been devised in [1]. Some people in my group are currently working on devising a reasonable criterion for PSI.

Another relevant question, both from a theoretical and practical point of view, is that of transaction chopping. Basically chopping is a static analysis techniques in which  coarse-grained transactions are broken down into smaller, fine grained transactions. For serialisability, this question has been tackled in [6], and the resulting theory has been applied to give a practical implementation in [7].

From the point of view of theoretical foundations of distributed databases, there has been some proposal to use techniques from the weak memory models community [8] to define formally the behaviour of transactions. In [9] the authors give a formal notion of behaviour for transactions; the same approach have been used in [10] to specify the behaviour of replicated data types.

Recently, I and some colleagues of mine (Alexey Gotsman and  Hongseok Yang) built, starting from the techniques developed in [8,9,10], a theoretical framework for specifying the observable behaviour of consistency levels for geo-replicated databases. We successfully employed the framework to give an axiomatisation of
SI, PSI and NMSI, each of which we have proved to be correct with respect to a simple implementation. We also exploited the resulting theory to devise a
chopping criterion for PSI. These results will hopefully we published in the foreseeable future.

Please do not hesitate to write me if you have other questions.
Hope this helps,

Andrea Cerone.

References:

[1] Fekete et al, Making Snapshot Isolation Serializable (2005)

[2] Sovran et al, Transactional Storage for Geo-replicated Systems (2011)

[3] Arkedani et al, Non-Monotonic Snapshot Isolation: scalable and strong consistency for geo-replicated transactional systems (2013)

[4] Arkedani et al, On the Scalability of Snapshot Isolation (2013)

[5] Binnig et al, Distributed snapshot isolation: global transactions pay globally, local transactions pay locally

[6] Shasha et al, Transaction chopping: algorithms and performance studies (1995)

[7] Zhang et al, Transaction chains: achieving serializability with low latency
in geo-distributed storage systems (2013)

[8] Alglave, A formal hierarchy of weak memory models (2012)

[9] Buckhardt et al, Understanding Eventual Consistency (2013)

[10] Buckhardt et al, Replicated Data Types: Specification, Verification, Optimality (2014)


If $DTIME(f(n))$ is defined as the class of all languages decidable in $O(f(n))$ time by a two tape Turing machine, then I suspect that the answer is no.  In other words, I think that there does not always exist a strictly intermediate time complexity class.

Note: This answer might not be exactly what you are looking for because I'm considering non-computable functions and I don't include every detail of the argument.  But, I felt that it is a good start.  Please feel free to ask any questions.  Maybe I can fill in these details further at some point or maybe this will lead to a better answer from an interested reader.

Consider functions of the form $f : \mathbb{N} \rightarrow \mathbb{N}$.  We refer to these functions as natural number functions.

  Claim 1: I claim that we can construct a very slow growing non-decreasing natural number (non-computable) function
  $\varepsilon(n)$ such that:

  (1) $\varepsilon(n)$ is non-decreasing

  (2) $\varepsilon(n) = \omega(1)$

  (3) For all unbounded computable $f: \mathbb{N} \rightarrow \mathbb{N}$, the set
  $\{ n \; \vert \; \varepsilon(n) \leq f(n) \}$ is infinite.

We construct $\varepsilon(n)$ as a slow growing non-decreasing step function. Let us enumerate all unbounded computable functions $\{ f_i \}_{i \in \mathbb{N}}$. We want to construct $\varepsilon(n)$ in such a way that for every $i$ and every $j \leq i$, $min\{ k \; \vert \; \varepsilon(k) \geq i\} \geq min\{ k \; \vert \; f_{j}(k) \geq i \}$. In other words, we wait to map $\varepsilon(n)$ to $i$ until the first $i$ functions in the enumeration have mapped to a value greater than or equal to $i$ at least once.  Then, $\varepsilon(n)$ continues to map to $i$ until the first $i+1$ functions in the enumeration have mapped to a value greater than or equal to $i+1$ at least once and at this point it starts mapping to $i+1$. If we continue this iterative process for constructing $\varepsilon(n)$, then for any given unbounded computable function, although $\varepsilon(n)$ might not always be smaller, it will infinitely often be at least as small.

Note: I just provided some intuition behind claim 1, I did not provide a detailed proof.  Please feel free to join in on discussion below.

Because $\varepsilon(n)$ is such a slow growing function, we have the following:

  Claim 2: For all computable natural number functions $f(n)$ and $h(n)$, if $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ and $h(n) = O(f(n))$, then $h(n) = \Theta(f(n))$.

For claim 2, if there existed a computable function $h(n)$ between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ such that $h(n) \neq \Theta(f(n))$, then we would be able to compute an unbounded natural number function that grows more slowely than $\varepsilon(n)$ which isn't possible.

Let me explain some relevant details.  Suppose for sake of contradiction that such a function $h(n)$ existed.  Then, $\lfloor \frac{f(n)}{h(n)} \rfloor$ is unbounded.

Note: The preceding function is computable because $f(n)$ and $h(n)$ are computable.

Since $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$, we have $\lfloor \frac{f(n)}{h(n)} \rfloor = O(\varepsilon(n))$.  It follows that there is some constant $\alpha$ such that for all $n$ sufficiently large, $\lfloor \alpha \frac{f(n)}{h(n)} \rfloor < \varepsilon(n)$.  Since this function is unbounded and computable we may apply Claim 1 to get that $\varepsilon(n) \leq \lfloor \alpha \frac{f(n)}{h(n)} \rfloor$ infinitely often which contradicts the previous statement.

  Claim 3: For a time constructible function $f(n)$, we have that $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$, yet there does not exist $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(h(n)) \subsetneq DTIME(f(n))$.

In order to just show that, $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$ we need to use a stronger time hierarchy theorem and this is where we use the assumption that the number of tapes is fixed (we said two tapes above).  See "The tight deterministic time hierarchy" by Martin Furer.

Since there are no computable natural number functions between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ other than those that are $\Theta(f(n))$, we have that for every function $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $h(n) \neq \Theta(f(n))$, $DTIME(\frac{f(n)}{\varepsilon(n)}) = DTIME(h(n))$.


Reference for Levin's optimal factoring algorithm  ?

Manuel Blum is talking about applying Levin's universal search algorithm to the Integer Factorization problem. The idea of Levin's Universal search algorithm is equally applicable to any problem in $NP$.

Here is a quote from lectures notes given by Blum on SECURITY and CRYPTOGRAPHY:

  Leonid LEVIN's OPTIMAL NUMBER-SPLITTING (FACTORING) ALGORITHM.
  Let SPLIT denote any algorithm that computes
  INPUT:  a positive composite (i.e. not prime) integer n.
  OUTPUT: a nontrivial factor of n.

  THEOREM: There exists an "optimal" number-splitting algorithm, which we
  call OPTIMAL-SPLIT. This algorithm is OPTIMAL in the sense that:
   for every number-splitting Algorithm SPLIT
   there is a (quite large but fixed) constant C such that
   for every positive composite integer input n,
  the "running time" of OPTIMAL-SPLIT on input n is at most C times the
  running time of SPLIT on input n.

Here is Levin's optimal factoring algorithm:

  The OPTIMAL-SPLIT ALGORITHM:
  BEGIN
   Enumerate all algorithms in order of size, lexicographically within each size.
   Run all algorithms so that at any moment in time, t, the ith algorithm
  gets  [1/(2^i)] fraction of the time to execute.
   Wnenever an algorithm halts with some output integer m in the range 1 < m
  < n, check if m divides n (i.e. if n mod m = 0).
  If so, return m.
  END


Minimum cost cut with discount - what is the complexity?

Consider the connectivity interdiction problem, which can be solved in polynomial time [1].

  (Unweighted) Connectivity interdiction

  Given a graph $G$ and integer $k$. Find a set $R$ of $k$ edges, such that the min-cut in $G-R$ is minimized.

Your problem is the same as this problem because $R$ is the $k$ discounted edges in the minimum $k$-discounted cut.

Zenklusen's paper discusses a more general weighted version of the problem. Each edge has a weight (independent from cost). $R$ is chosen so the weight is at most $k$. That problem admits a PTAS. The special case we care about is when the weights are all $1$, which is the case solvable in polynomial time.

Zenklusen, Rico, Connectivity interdiction,  ZBL06945298..


Trying understand a move in Cohen's proof of the independence of the continuum hypothesis

Our goal is to prove that $\aleph_1 < 2^{\aleph_0}$ in the model $M[G]$, and therefore the Continuum Hypothesis is not true in $M[G]$. This is equivalent to saying that $\aleph_2 \leq 2^{\aleph_0}$. So we need to construct a model $M[G]$ such that there is an injective map $f$ from $\aleph_2$ to $2^{\aleph_0}$ in $M[G]$. Note that each element of  $2^{\aleph_0}$ is a function from $\aleph_0$ to $\{0,1\}$ (by definition). Thus $f(x)$ (the value of $f$ at point $x$) is actually a function that maps a natural number to $\{0,1\}$. In the proof, we treat $f$ as a function of two parameters
$$h(x,y) = f(x)(y)$$
where $x\in \aleph_2$ and $y\in \aleph_0$. This is the reason why we want to prove that there exist a function $h$ from $\aleph_2 \times \aleph_0$ to $\{0,1\}$ satisfying certain properties.

The choice of $\aleph_2$ here is not arbitrary. Say, if we wanted to prove that $2^{\aleph_0} > \aleph_{19}$, we would consider functions from $\aleph_{20} \times \aleph_0$ to $\{0,1\}$.

BTW, $\aleph_2^M$ is always an element of $M$ and $M[G]$ (for any generic set $G$); on the other hand $\aleph_2$ is usually neither an element of $M$ nor $M[G]$, since $M$ is a countable transitive model of ZFC (or more precisely is a countable model of a large finite fragment of ZFC). So I'm not sure what you mean in the last paragraph.


Is state splitting the LR equivalent of LL nonterminal replication

It is indeed well-known that LR($k$) languages for $k>0$ coincide with SLR($1$) languages, see e.g. M. Dennis Mickunas, Ronald L. Lancaster, and Victor B. Schneider, Transforming LR($k$) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars, J. ACM 23(3):511--533, 1976, doi: 10.1145/321958.321972; it's not clear to me what EBNF syntax has to do with it: could you be more specific?

Edit: in answer to the more specific question regarding nullable nonterminals and LR($k$) vs. SLR($k$), the grammar with rules
$$S\to aAa\mid bAb\mid aBb\mid bBa, A\to a, B\to a$$
is LR(1) but neither SLR(1) nor LALR(1) and does not have any nullable nonterminal.

Another issue is that there is no "perfect" definition of LR($k$) for EBNF syntax---unless you convert to BNF in some specific way and ask the resulting grammar to be LR($k$); see Heilbrunner, Definition of ELR($k$) and ELL($k$) Grammars, Acta Inf. 11(2):169--176, 1979, doi: 10.1007/BF00264023.  The issue is with the reduction operation: how much of the stack should be reduced when reducing, say, $A\to a^\ast$?  Answering this question might require inspecting the stack contents, or adding special stack markers, or $\dots$, and is likely to restrict the class of accepted grammars below ELR($k$).

Finally, I do not know about SLR($k$) techniques for EBNF grammars; a survey on the subject of parsing for EBNF was recently written by Hemerik, Towards a Taxonomy for ECFG and RRPG Parsing, LATA'09, LNCS 5457:410--421, 2009, doi: 10.1007/978-3-642-00982-2_35.


Is scope extrusion necessary in the Pi-calculus?

If we separate the notion of channel names from variables, we can make the ν-binder a true binder where the variable following ν is a normal bound variable and we only need to add a reduction rule for it, which is just like the reference cell allocation in ML:

(νx)P ⟶ P[c/x]

  where c is a globally fresh channel name. Then, everything made sense to me.

You are basically correct.

The reason most people don't do this is that to model your side condition "where $c$ is a globally fresh channel name", you need to give an operational semantics for the $\pi$-calculus which tracks the set of names $\Sigma$ allocated so far. I.e., the rule above would become:

\begin{array}{lcll}
  \langle\Sigma; \nu x.P\rangle & \to & \langle\Sigma \uplus \{c\}; P[c/x]\rangle & \mbox{where } c \notin \Sigma
\end{array}

Then you'd also need a condition that a configuration is well-formed if the set of names $\Sigma$ is bigger than the free names in $P$, and you'd also need to prove some equivariance/permutation lemmas that configurations and reduction sequences are stable under finite permutations of names.

You get this all for free from the $\alpha$-equivalence of $\pi$-calculus terms, at the price of introducing the (admittedly somewhat ugly) scope extrusion rule.
However, if you don't like it, you're in good company. Bob Harper does things the way you suggest in his book Practical Foundations for Programming Languages.


Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm

Alper Ungor did some nice work related to this issues of how do Delaunay refinement with alternative points. See his paper:

A. Ungor. Off-centers: A new type of Steiner points for computing size-optimal guaranteed-quality Delaunay triangulations. Computational
Geometry: Theory and Applications (CGTA), 42(2): 109--118, 2009.


Generating points uniformly distributed over the SURFACE of a standard simplex

I created an algorithm for that. for detail see
    http://www.sciencedirect.com/science/article/pii/0098300493900457

briefly speaking, you can use following recursive formula to generate:

x_1=1-R_1^{1/n-1}
x_k=(1-\sum_{i=1}^{k} x_i)(1-R_k^{1/n-k}),    k=2,…,n-1
x_n=1-\sum_{i=1}^{n-1} x_i

Best wishes


Add the edge $(u,v)$. Your property holds if and only if $G$ is no longer $k$-colorable.


Complexity of propositional LTL with past operators and freeze quantifier?

The answer was buried in a small section of the same paper that I was citing. Adding past operators to TPTL, in contrast of what happens with LTL, causes a huge increase in complexity as the satisfiability problem becomes non-elementary.

The fact is proven in the paper by showing how a mixture of future and past operators, combined with the freeze quantifier, can emulate an arbitrary first-order existential quantifier.


Does the problem "partition a vertex-weighted graph into $k$ balanced connected parts" have a standard name?

The paper [Chlebikova, Approximating the maximally balanced connected partition problem in graphs, 1996] studies a related problem: They have $k=2$, and they maximize $\min(|V_1|,|V_2|)$. It should be a good place to start searching for related results, by following the citation graph.


Stronger Lower Bounds on Nondeterministic Multiparty Communication

There is a tight (within an additive log n) lower bound method for nondeterministic multiparty communication complexity:

Put a hard distribution on the 1-inputs, and measure the size of the largest 1-monochromatic cylinder intersection. To see that it's tight take the relevant section in Kushilevitz and Nisan, and replace the word 'rectangle' with 'cylinder intersection'.

The corruption bound, or rather the one-sided version of it (where you prove that all large rectangles contain a constant fraction of 0-inputs) is harder to use and yields stronger results, for instance allows you to prove MA-communication complexity lower bounds.


The problem can be solved in $O(n^2)$:

Denote $A=\{a_1,\ldots,a_n\}, B=\{b_1,\ldots,b_n\}$.
We will build a graph in which every node $(i,j,x)$ will denote which $a$'s and $b$'s we have already executed and $x$ is a bit representing if the last task was $a$.

Construct the product graph $$G_p=(V_p, E_p)$$
$$V_p = A\times B\times \{0,1\}$$
$$E_p = \{((a_i,b_j,x),(a_{i+1},b_j,0))\mid x\in\{0,1\},j\leq i\in[n-1]\}$$
$$ \cup \{((a_i,b_j,x),(a_i,b_{j+1},1)\mid  x\in\{0,1\},j\leq i+1\in[n]\}$$
Assign weights:
$$w(((a_i,b_j,0),(a_{i+1},b_j,0)))=E(a_i,a_{i+1})$$
$$w(((a_i,b_j,1),(a_{i+1},b_j,0)))=E(b_j,a_{i+1})$$
$$w(((a_i,b_j,0),(a_i,b_{j+1},1))) = E(a_i,b_{j+1})$$
$$w(((a_i,b_j,1),(a_i,b_{j+1},1))) = E(b_j,b_{j+1})$$

And now simply find the shortest path with an algorithm of your choice (run time is linear in $|G_p|$, since it is a DAG).


This is a very interesting question. At a high level, you are asking whether one can preprocess a graph such that shortest path queries become independent of the density of the graph, without using much extra space -- interesting, but as you say, unresolved.

If you are happy with approximate distances, here is a way to get a $2$-approximation. Let $G$ be a weighted undirected graph with $n$ nodes and $m$ edges. It is shown in the following paper that for approximate distance queries, designing data structures for graphs with $m$ edges is no harder than graphs in which each node has degree bounded by $m/n$:

R. Agarwal, P. B. Godfrey, S. Har-Peled, Approximate distance queries and compact routing in sparse graphs, INFOCOM 2011

So, assume that $G$ is a $m/n$-degree bounded graph. Sample $\alpha = O(m/n)$ nodes uniform randomly; call these landmark nodes. During the preprocessing phase, store the distance from each landmark node to each other node in the graph; this requires $O(m)$ space. For each node $u$, store its closest landmark node $\ell(u)$. Also, store the graph within the data structure, say as an adjacency list.

When queried for distance between $u$ and $v$, grow balls around both nodes -- ball of node $w$ is defined as the set of nodes that are strictly closer to $w$ than to its closest landmark node, say $\ell(w)$. It can be shown that the size of each ball is $O(n^2/m)$, in expectation. Let $\Gamma(u) = B(u) \cup N(B(u))$, where $B(u)$ is the ball of node $u$ and $N(B(u))$ is the set of neighbors of nodes in $B(u)$. It can be shown that the size of $\Gamma(u)$ is $O(n)$, in expectation.

Answering the query: if $\Gamma(u) \cap \Gamma(v) \neq \emptyset$, return $\min_{x \in \Gamma(u) \cap \Gamma(v)} \{d(u, x) + d(v, x)\}$; else if $d(u, \ell(u)) \leq d(v, \ell(v))$, return $d(u, \ell(u)) + d(\ell(u), v)$; else return $d(v, \ell(v)) + d(\ell(v), u)$. It is easy to show that this is a $2$-approximation.

In terms of query time, note that growing balls takes $O(n)$ time for a $m/n$-degree bounded graph; constructing $\Gamma(u)$ and $\Gamma(v)$ given respective balls takes $O(n)$ time (since neighbors are stored within the data structure); and checking whether $\Gamma(u) \cap \Gamma(v)$ is empty or not also takes $O(n)$ time.

The above bounds are in expectation; I think it is easy to derandomize the construction. Unfortunately, this technique does not seem to allow getting approximation better than $2$. Its a very interesting question though ....


Here are a few additional references. More can be found by looking at the papers that cite these.

Duris and Galil (1984) give a language in $P$ which requires $T^2 S \geq \Omega(n^3)$ on one-tape Turing machines with any constant number of read-write heads. Karchmer (1986) showed that the same lower bound holds for the element distinctness problem.

Babai, Nisan, and Szegedy (1989) give a very natural language (generalized inner product) that is solvable in $O(n)$ time and $O(1)$ space on a $k+1$-head one-tape Turing machine, that requires $T S \geq \Omega(n^2)$ on any $k$-head one-tape Turing machine.

Ajtai (1999) shows time-space tradeoffs for deterministic random access machines computing element distinctness. In particular if $S \leq o(n)$, then $T \geq \omega(n)$. Subsequent work by Beame, Saks, Sun, and Vee (2000) proves time-space tradeoffs for randomized computations.

Santhanam (2001) showed that $TS \geq \Omega(n^2)$ holds for multitape Turing machines solving SAT, building on Cobham's analogous lower bound for PALINDROMES.


Minimal specification of Martin-Löf type theory

The purpose of the system described in the appendix of the HoTT book is to present something that corresponds to what is used by the book. The book is aiming to be educational. Therefore it would be a bad idea to do everything in a minimalist way. For example, we introduce $\mathbb{N}$ separately because it is instructional to see how inductive constructions work in a familiar case.

You are perfectly correct, to jump-start inductive types from general $W$-types you just need $0$ and $2$. You immediately get $1$ as $0 \to 0$, and you get $+$ from $2$ and $\Sigma$. Once you have that, you get all finite sums $1 + 1 + \cdots + 1$. At this point it is easy to do the usual algebraic datatypes.

If you drop $0$, so you start from $\Pi$, $\Sigma$, $1$ and $2$, then you cannot get $0$ back because every type you make will be inhabited.

Suppose you only have $\Pi$, $\Sigma$, $0$ and $1$. Then you cannot make $2$ because you can show that every construction you make gives you back either $0$ or $1$. In fact, you cannot make any interesting dependent families at all. A larger family of types which is closed under $\Pi$, $\Sigma$, $0$ and $1$, but does not contain $2$ is the $(-1)$-types (propositions).


If we knew a specific computable language $L$ such that we could prove $L\in\mathrm P\iff\mathrm P\ne\mathrm{NP}$, this would make $\mathrm P\ne\mathrm{NP}$ equivalent to a $\Sigma^0_2$ sentence. While $\mathrm P\ne\mathrm{NP}$ is $\Pi^0_2$, it is not known to be $\Sigma^0_2$, and this is outright false in the relativized world (see https://cstheory.stackexchange.com/a/16644).


Reference: Cancellability of the Dyck congruence

Your assertion is wrong, the congruence $\equiv$ is not cancellable from the right: for instance $\bar a a \bar a \equiv \bar a$, but $\bar a a \not\equiv 1$.

By the way the quotient $\Sigma^*/{\equiv}$ is not a group, but a monoid, called the polycyclic monoid, first introduced in [1].

[1] M. Nivat and J-F. Perrot, Une généralisation du monoïde bicyclique, Comptes Rendus de l'Academie des Sciences de Paris 271 (1970), 824-827.


PTAS Algorithm for K-Clustering when Distance Computation is Costly

Have you seen this paper by Piotr Indyk ? It's old, but it's a good one. It solves a number of problems including k-median while making only sublinear number of calls to the distance oracle. It's not exactly the model you're looking for, but it does try to reduce the number of distance invocations.


Is there a name for "physical things out of which one can build a Turing machine"?

Physics models reality with theories that define a concept of time-dependent state associated to a system and a time-evolution operator that describes how this state evolves. As soon as you find a physical system that (after some state-space discretization) implements the state space of your Turing machine, and that features interaction terms that implement (maybe after some time discretization) the time evolution according to the state transition table of your Turing machine on its state space, you have found a Turing-complete physical model of your system. Thus you can arguable say, your system "is" Turing-complete.

When looking at quantum computing, you will find discussions of implications physical theories have on the Turing model of computation. For example, physical theories have to be reversible. A property, which is not shared by ordinary Turing machines. Yet there is no loss in generality, as any Turing machine can be simulated by a reversible one, with some overhead that can trade-off time vs. space, etc.


From http://slkpg.com/llkparse.html

Definition:  A grammar G = ( N, T, P, S ) is said to be strong
LL(k) for some fixed natural number k if for all
nonterminals A, and for any two distinct A-productions in the grammar

$A \rightarrow \alpha$

$A \rightarrow \beta$

$FIRST_k ( \alpha \,\, FOLLOW_k (A) ) \cap  FIRST_k ( \beta \,\, FOLLOW_k (A) ) = \emptyset$

That is, each parsing decision is based only on the next k tokens of the
input for the current nonterminal that is being expanded.


What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?

If $\mathrm{P\subseteq CSL}$, then $\mathrm{P\subseteq DSPACE}(n^2)$. By a padding argument, this implies
$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}\bigl(t(n)^\epsilon\bigr)$$
for every superpolynomial well-behaved function $t(n)$ and every $\epsilon>0$. I believe such a strong advantage of space over time is not expected to be true. The best currently known result in this direction is
$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}(t(n)/\log t(n)),$$
due to Hopcroft, Paul, and Valiant.


I imagine there are lots of possible approaches to this problem (many of which I'm sure you considered) -- here are a few ideas/references.

You could play this as $N$ independent parallel single-arm bandit games, deciding to pull or not pull each arm independently.  This should work especially well if the rewards are independently distributed.
Allow each set of arms to be a new arm and run an Exp3-type algorithm.  This gives a $O(2^{N/2} T^{1/2})$ regret - not so great.
In an upcoming NIPS 2010 paper, Saten Kale, Rob Schapire, and I consider the case where one plays a slate of arms at once.  In our work, however, the size of the slate is fixed.  This paper also considers a similar problem.  Another similar work appeared in ALT 2010.  Perhaps some of the ideas transfer.
If you treat it as an experts problem (each expert recommends a different one of $2^N$ subsets), by following one expert, you can get estimate the performance of other experts who have non-empty intersections in their choice of arms to pull by using importance weighting.  An Exp4 type analysis might get you $O(N\sqrt{T})$ regret but $O(2^N T)$ running time.

EDIT below:

It seems to me that the budget constraint (not going below $0$) makes the problem intractable.  Imagine you have a budget of $1$.  The adversary can make one of the  arms always pay off and the rest never pay off.  So w.p. $(n-1)/n$ you go bust in the first round while the optimal strategy gets $T$ dollars after $T$ rounds.  So your expected regret is at least $(n-1)T/n$ and you can't hope for a high probability bound at all.

It also seems that this can work for any initial budget.  Say you start with $B$ dollars.  Then the adversary can set all but one arms to pay $0$ and one arm to pay something like $2B$ w.p. $1/B$.  I guess if you have a limit on the possible payout amount and a high enough initial budget, then this might leave room for an interesting problem.


The answer is no.  If you consider a graph with satisfying assignments as vertices where two assignments are joined by an edge if the Hamming distance is 1, the graph is always connected because every satisfying assignment can be eventually transformed to the all-1 assignment by changing the value of one variable from 0 to 1.


Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?

I think this is really a question about the API features. Access to an older version, in Driscoll et al.'s sense, requires a pointer to that version, not just a predicate used to traverse a version tree to locate the version.

For a similar API/modelling question, you can look at the question of how long delete takes in a priority queue. Plenty of papers advertise that they offer $O(1)$ delete, but this assumes one already has a pointer to the item to be deleted.


Is there any work relating type systems and Cook-Reckhow proof systems?

Cook-Reckhow propositional proof systems are nonunifrom.
E.g. the computational complexity counterpart to
the class of polynomial-size $\mathsf{Extended Frege}$ proofs is
the nonuniform complexity class $\mathsf{P/poly}$.
We have to look at their uniform counterparts:
E.g. the proof complexity counterpart for $\mathsf{P}$ are
bounded arithmetic theories like
Cook's theory $\mathsf{PV}$ (standing for polynomial-time verifiable),
Buss's theory $\mathsf{S}^1_2$, ...

Cook and Urquhart used Cook's theory $\mathsf{PV}$
to define a theory of higher-types polynomial-time computable functions $\mathsf{PV}^\omega$ in the following paper:

Stephen A. Cook and Alasdair Urquhart, "Functional interpretations of feasibly constructive arithmetic", 1993. doi: 10.1016/0168-0072(93)90044-E

There has been some follow up work which you can find by looking at articles citing this paper.

Implicit complexity theory that Martin mentions is also influenced by this work. Check out Simone Martini's survey slides and Ugo Dal Lago's survey article to get a picture of what is implicit complexity theory and its history.


Multiple independent random number streams

Do not use a single stream of random numbers generated in one thread (or process) and consumed in other threads (or processes). In general, you must instead use several random number streams for your calculations, one for each thread/process. It is extremely important for these streams to be uncorrelated, in order for the pseudorandom numbers to be effective at the desired variance reduction, which is, of course, the point of large Monte Carlo calculations.

You may want to take advantage of the Scalable Parallel Random Number Generators Library (SPRNG), which is a parallel library (but you may also use it sequentially as well) providing these and other additional properties; it is particularly well suited for parallel Monte Carlo simulations.


Explanation of definition of normalizing: 9.1.12 in Terese "Term Rewriting Systems"?

I think you have misunderstood the definitions:

TERESE (9.1.1):

A strategy $S$ for an ARS $\rightarrow$ is a sub-ARS $\rightarrow_S$ of $\rightarrow$ having the same objects and normal forms.

This means that

If $a\rightarrow_S b$, then $a\rightarrow b$ (sub-ARS condition)
If there exists $b$ such that $a\rightarrow b$, then there exists $b'$ such that $a\rightarrow_S b'$ (same normal forms).

The second condition can be read as: if $a$ is not a normal form, then there is some rewrite step from $a$ which conforms to strategy $S$.

TERESE (9.1.12):

If $A$ is a superset of the set of normal forms for $\rightarrow$, a strategy $S$ is $A$-normalizing if the restriction of $S$ to terms not in $A$ is normalizing.

This means that a strategy is $A$-normalizing if every reduction sequence for $\rightarrow_S$ either

Ends on a normal form
Ends in $A$.

Clearly if $A=NF$ then only case 1. is relevant. However if $A$ is taken to be terms in head-normal form, then case 2. may occur independently of case 1.


Speedup from algorithmic advances vs. hardware

this is an unintentionally complex question. this idea that software gains have outpaced hardware gains is apparently rooted in a real govt report but (as your question indicates) possibly approaching minor urban legend status due to being misunderstood or misinterpreted. the summary/sound-bite headlines do not really match the actual point being made in the report.

see [1] or [2] which states

  A report by an independent group of science and technology advisers to the White House, published last December, cited research showing that performance gains in doing computing tasks that result from improvements in software algorithms often far outpace the gains attributable to faster processors.
  ...
  But the White House advisory report cited research, including a study of progress over a 15-year span on a benchmark production-planning task. Over that time, the speed of completing the calculations improved by a factor of 43 million. Of the total, a factor of roughly 1,000 was attributable to faster processor speeds, according to the research by Martin Grotschel, a German scientist and mathematician. Yet a factor of 43,000 was due to improvements in the efficiency of software algorithms.

but the issue of software vs hardware is very far from this one dimensional simplification, much more complex, and Lohrs blog has it more accurate— software and hardware form a sort of yin-yang symbiotic fusion and both have advanced very significantly, even staggeringly over the decades.

caveat/fine print: one cannot take individual gains in particular software algorithms, which in some cases have been very substantial, and generalize that across all algorithms.

the actual quote from the report is on page 71:

  Even more remarkable – and even less widely understood – is that in many areas,
  performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed. The algorithms that we use today for speech recognition, for natural language translation, for chess playing, for logistics planning, have evolved remarkably in the past decade. It’s difficult to quantify the improvement, though, because it is as much in the realm of quality as of execution time.

so this government report is highly researched and polished, the basic claim of massive gains due to theoretical software advances in some areas is correct, and is promoting (theoretical/algorithmic) research partly on that basis.

however there are several other new/recent fundamental/massive phenomena/trends/shifts in recent years or what Intels Grove calls "inflection points" that are occuring in hardware vs software design. aka "gamechangers":

the rise of "Exascale" supercomputing may not be as readily achieved as "Petascale" due to hardware scaling constraints
clock speeds, a main drive of prior speed gains, have plateaued (partly due to heat/cooling constraints)
hardware is undergoing a massive shift toward less compute intensive, more energy efficient devices eg mobile, datacenters/virtualization/cloud etc
improving parallelism in software and hardware (eg "multicore") is therefore becoming more critical for performance improvements (where theory has a lot to say about how to parallelize algorithms)

[1] skeptic.se, does progress in algorithms beat progress in hardware

[2] Software progress beats Moores law NYT blog by Lohr

[3] REPORT TO THE PRESIDENT
AND CONGRESS
DESIGNING A DIGITAL FUTURE:
FEDERALLY FUNDED RESEARCH
AND DEVELOPMENT IN
NETWORKING AND INFORMATION
TECHNOLOGY Dec 2010


Take a look at this question for some pointers to SAT solvers. Specially, there's a link to SAT Competition, in which you can find parallel SAT solvers (like ManySAT or gNovelty2+).


Complexity of counting the number of edge covers of a graph

I don't know where this was first proved, but since EdgeCover has an expression as a Boolean domain Holant problem, it is included in many Holant dichotomy theorems.

EdgeCover is included in the dichotomy theorem in (1).  Theorem 6.2 (in the journal version or Theorem 6.1 in the preprint) shows that EdgeCover is #P-hard over planar 3-regular graphs.  To see this, the expression for EdgeCover as a Holant problem over 3-regular graphs is $\operatorname{Holant}([0,1,1,1])$ (or replace $[0,1,1,1]$ with $[0,1,\dotsc,1]$ containing $k$ 1's for the same problem over $k$-regular graphs).  This $[0,1,1,1]$ notation lists the output of a symmetric function in order of input Hamming weight.  For some subset of the set edges (which we think of as being assigned 1 and the complement set being assigned 0), the constraint at each vertex is that at least one edge is assigned 1, which is exactly what the function $[0,1,1,1]$.  For a fixed subset of edges, its weight is the product of the outputs of $[0,1,1,1]$ at each vertex.  If any vertex is not covered, it contributes a factor of $0$.  If all vertices are covered, then all vertices contribute a factor of $1$, so the weight is also $1$.  Then the Holant is to sum over every possible subset of edges and add the weight corresponding to each subset.  This Holant value is exactly the same if we subdivide every edge and impose the constraint that both incident edges to these new vertices must be equal.  Using the symmetric function notation, this binary equality function is $[1,0,1]$.  This graph is bipartite.  The vertices in one part have the $[0,1,1,1]$ constraint while the vertices in the other part have the $[1,0,1]$ constraint.  The expression for this as a Holant problem is $\operatorname{Holant}([0,1,1,1]|[1,0,1])$.  Then you can check for yourself that row "$[0,1,1,1]$" and column "$[1,0,1]$" of the table near the theorem cited above contains "H", which means the problem is #P-hard even the input graph must be planar.

Side note: Note that Pinyan Lu is an author of both this paper and the first paper you cite.  I am guessing that when their paper says "counting edge covers is
a #P-complete problem even when we restrict the input to 3 regular graphs", they were implicitly citing (1).  They probably didn't mention that the hardness also holds when further restricted to planar graphs since their FPTAS does not need this restriction.

Later Holant dichotomy theorems, such as those in (2,3)---conference and journal versions of the same work---proved more.  Theorem 1 (in both versions) says that EdgeCover is #P-hard over planar $k$-regular graphs for $k \ge 3$.  To see this, we need to apply a holographic transformation.  As described above, the expression for EdgeCover as a Holant problem over $k$-regular graphs is $\operatorname{Holant}([0,1,\dotsc,1])$, where $[0,1,\dotsc,1]$ contains $k$ 1's.  And furthermore, this is equivalent to $\operatorname{Holant}([1,0,1]|[0,1,\dotsc,1])$.  Now we apply a Holographic transformation by $T = \begin{bmatrix} 1 & e^{\pi i / k} \\ 1 & 0 \end{bmatrix}$ (or its inverse, depending on your perspective).  By Valiant's Holant Theorem (4,5), this does not change the complexity of the problem (in fact, both problems are actually the same problem because they agree on the output of every input...only the expression of the problem has changed).  The alternate expression for this problem is

$$
\operatorname{Holant}([1,0,1] T^{\otimes 2}|(T^{-1})^{\otimes k} [0,1,\dotsc,1])
= \operatorname{Holant}([2, e^{\pi i / k}, e^{2 \pi i / k}]|=_k),
$$
where $=_k$ is the equality function on $k$ inputs. To apply Theorem 1, we have to normalize $[2, e^{\pi i / k}, e^{2 \pi i / k}]$ to $[2 e^{-\pi i / k}, 1, e^{\pi i / k}]$ by dividing the original function by $e^{\pi i / k}$, which doesn't change the complexity of the problem since this value is nonzero.  Then the values $X$ and $Y$ in the statement of the theorem are $X = 2$ and $Y = -2^k - 1$.  For $k \ge 3$, one can check that this problem, so thus EdgeCover as well, is #P-hard over planar $k$-regular graphs for $k \ge 3$.

Side note: One can also see this theorem and proof in Michael Kowalczyk's thesis.

I will continue my literature search to see EdgeCover was shown to be #P-hard before (1).

(1) Holographic Reduction, Interpolation and Hardness by Jin-Yi Cai, Pinyan Lu, and Mingji Xia (journal, preprint).

(2) A Dichotomy for $k$-Regular Graphs with $\{0,1\}$-Vertex Assignments and Real Edge Functions by Jin-Yi Cai and Michael Kowalczyk.

(3) Partition functions on $k$-Regular Graphs with $\{0,1\}$-Vertex Assignments and Real Edge Functions by Jin-Yi Cai and Michael Kowalczyk.

(4) Holographic Algorithms by Leslie G. Valiant

(5) Valiant’s Holant Theorem and matchgate tensors by Jin-Yi Cai and Vinay Choudhary


Consequences of sub-exponential proofs/algorithms for SAT

If SAT had a subexponential-time algorithm, the you would disprove the exponential time hypothesis.

For fun consequences: if you showed that circuit SAT over AND,OR,NOT with $n$ variables and $poly(n)$ circuit gates can be solved faster than the trivial $2^n poly(n)$ approach, then by Ryan Williams' paper you show that $NEXP \not\subseteq P/poly$.


Finding witness in minkowski sum of integers

Ok, I've been holding off since really Sariel should get credit for an answer, but I'm tired of waiting, so here is my cut at a near-linear randomized algorithm.

By choosing samples of $n(1-\epsilon)^i$ points, $i=0,1,\dots$, you can get a logarithmic number of subproblems such that each sum from the original problem has constant probability of being represented uniquely in one of the subproblems (the one where the sampling cuts down the expected number of representations to near 1).
By repeating the sampling process a logarithmic number of times you can get all sums to have unique representations with high probability.
If you have a partition of $A$ and $B$ into two subsets, then by multiplying the numbers by four, adding 2 to the numbers in one of the subsets in $A$, and adding 1 to the numbers in one of the subsets in $B$, you can read off from the mod-4 values of the achievable sums which of the two subsets their summands come from.
By repeating the partition process a logarithmic number of times, using each bit position of the binary representations of the values or indices in the subproblems to select the partitions in each step, you can uniquely identify the summands of every uniquely-represented sum.

This blows up the running time by three logarithmic factors; probably that can be reduced.


When does (or should) Theoretical CS care about intuitionistic proofs?

It is is worth thinking about WHY intuistionistic logic is the natural logic for computation, since all too often people get lost in the technical details and fail to grasp the essence of the issue.

Very simply, classical logic is a logic of perfect information: all statements within the system are assumed to be known or knowable as unambiguously true or false.

Intuistionistic logic, on the other hand, has room for statements with unknown and unknowable truth values.  This is essential for computation, since, thanks to the undecidability of termination in the general case, it will not always be certain what the truth value of some statements will be, or even whether or not a truth value can ever be assigned to certain statements.

Beyond this, it turns out that even in strongly normalizing environments, where termination is always guaranteed, classical logic is still problematic, since double negation elimination $\neg\neg P \implies P$ ultimately boils down to being able to pull a value "out of thin air" rather than directly computing it.

In my opinion, these "semantic" reasons are a much more important motivation for the use of  intuistionistic logic for computation than any other technical reasons one could marshal.


Polynomial speedups with algorithms based on semidefinite programming

I'm not familiar with details of the ellipsoid method specifically for semi-definite programs, but even for linear programs, analysis of the ellipsoid method is pretty subtle.

First, one needs to bound the number of iterations of the ideal ellipsoid algorithm.  Let $E_i$ be the ellispoid used in the $i$th iteration of the ellipsoid algorithm, and let $c_i$ be its centroid.  In the ideal algorithm, a separation/membership oracle gives you a halfspace $h_i$ that contains the optimum point $x^*$ but not the centroid $c_i$.  The next ellipsoid $E_{i+1}$ is the smallest ellipsoid containing $E_i\cap h_i$.  For each $i$, we have $vol(E_{i+1}) < (1-\frac{1}{n})\cdot vol(E_i)$, where $n$ is the dimension.  Thus, given a reasonable starting ellipsoid, the number of iterations is polynomial in $n$ and $\log(1/\varepsilon)$.  Computing $E_{i+1}$ from $E_i$ and $h_i$ requires (crudely) $O(n^2)$ arithmetic operations.  So the number of arithmetic operations is also polynomial in $n$ and $\log(1/\varepsilon)$.
However, some of those arithmetic operations are square roots!  It follows that the coefficients of the ideal ellipsoid $E_i$ are irrational numbers of degree $2^i$, and so there's no hope of actually computing $E_{i+1}$ exactly in any reasonable time.  So instead, one computes a close outer approximation $\tilde{E}_i \supset E_i$ at each iteration using finite precision arithmetic.  Grötschel, Lovasz, and Schrijver prove that if one uses (say) $10i$ bits of precision in the $i$th iteration, we still have $vol(\tilde E_{i+1}) < O(1-\frac{1}{n})\cdot vol(\tilde E_i)$, so the number of iterations increases by at most a constant factor.  But now each arithmetic operation during the $i$th iteration (including the operations performed by the separation oracle) requires $O(i~\text{polylog}~i)$ time.

Altogether, the total running time of the ellipsoid method is very roughly the square of the number of arithmetic operations.  Since the number of arithmetic operations is polynomial in $n$ and $\log(1/\varepsilon)$, so is the running time.


For a language to be programmable, is it mandatory that it be based on a context free grammar

Two times no.

First, most HPLs are not context free. While they usually have syntax based on a CFG, they also have what people call static semantics (which is also often included in the term syntax). This can include names and types which have to check out for a correct program. For instance,

class A {
  String a = "a";
  int b = a + d;
}

is a syntactically correct Java program but will not compile because d is not defined and a does not have a fitting type.

Secondly, you can parse languages that are not context-free (as obviously proven by the existence of compilers). It is only that CFGs can be parsed efficiently, while CSGs can not, in general. However, you can add certain non-context-free features while remaining efficient.

Compilers often run in phases: first tokenization (regular), then context-free parsing, then name and type analysis (context-sensitive, sometimes even harder). You can observe that behaviour by the kind of error messages you get.


multi-party Communication complexity of "Set Partition problem"

A linear lower bound on deterministic CC follows by fixing one of the sets to be empty.

For a randomized logarithmic upper bound, first note that this problem can be reduced to the problem asking whether the sum of three $3n$-bit numbers is exactly $2^{3n}-1$.  This one can be solved in $O(\log n)$ randomized communication by the players operating mod a random $O(\log n)$-bit prime.


You asked why

  [[forall a. [forall b. a -> b]]] has a weight of 1

It doesn't. It has a polymorphic weight of 1. The polymorphic weight strips the binder before it looks at the weight. For the $\rho$ you chose:

$[\![\forall \overline{\alpha} . \rho]\!] = wt(\rho) = 1 \neq 2 = wt(\forall \overline{\alpha} . \rho)$


Graph classes for which the diameter can be computed in linear time

The eccentricity of a vertex $v$ is the length of a longest shortest path starting from $v$.  The diameter is the maximal eccentricity over all vertices.
Any BFS from a vertex will establish its eccentricity.
A key idea for efficient diameter finding is therefore to preprocess the graph to find a small set of vertices, at least one of which achieves maximal eccentricity.

Running a lexicographic breadth-first search, the end-vertex often has high eccentricity.  In particular, it is guaranteed to have eccentricity at most one less than the diameter for chordal graphs.  For some subclasses of chordal graphs such as interval graphs, it is guaranteed to have maximal eccentricity.  This also holds for some non-chordal classes such as $\{\text{AT},\text{claw}\}$-free graphs.

LBFS and BFS are both linear in the size of the graph, but of course if $m = \Omega(n^2)$ (such as $K_n$) then the runtime will not be $o(n^2)$.  Your discussion implies that you probably really want a linear algorithm $O(m+n)$ rather than $o(n^2)$.

So for some subclasses of chordal graphs, a linear algorithm is to run LBFS, take the end-vertex, then run BFS starting at that vertex.  For chordal graphs this will determine the diameter with an error of at most 1.  The graphs for which this is exact seem to be those where the even powers are chordal.  These are precisely those chordal graphs that contain no rising sun or $(\text{rising sun}- K_2)$ subgraph that preserves distances.

(source: graphclasses.org)

Feodor F. Dragan, Falk Nicolai and Andreas Brandstädt, LexBFS-orderings and powers of graphs, WG 1996, LNCS 1197, 166–180.  doi:10.1007/3-540-62559-3_15

I do not know if this can be extended to compute the diameter for all chordal graphs precisely.  Corneil's survey seems to indicate that this was still open in 2004.  I also don't know if an analysis has been done on extending the search from one vertex to a small constant number or $\log n$ starting vertices; this might be interesting to explore.

Derek G. Corneil, Lexicographic Breadth First Search – A Survey, WG 2004, LNCS 3353, 1–19. doi:10.1007/978-3-540-30559-0_1


Size of Formulas with no negative sign for Matrix Permanent

Snir has proved a tight lower bound on the size of monotone formulas representing the permanent of an $n\times n$ matrix. The lower bound is $2^{2n - 0.25\log^2 n}$, and he notes that a formula of size $2^{2n - 0.25\log^2 n + O(\log n)}$ exists (Theorem 3.1. and comment after the proof).

The survey by Shpilka, and Yehudayoff is a good resource. Also, a lower bound of $2^{\Omega(n)}$ on the size of monotone circuits for the permanent is known as well (proved by Jerrum and Snir)


You are Right if the Computing Power for XSD schema is free or freely available (Soft). Otherwise, it will be Hard.


Generalized Secretary Optimization Problem

Let's assume the first strategy is the best until someone comes up with a better one, ok?

So we set a threshold for value (between 0 and v). If the value of the candidate is higher than the threshold, try to hire that candidate. Otherwise, interview the next candidate. If we interview several candidates in a row whose value is below the threshold, decrease the threshold until future candidates are likely to have a higher value. If d is low and the candidates decline offers, lower the threshold further.

A few points to determine: the first threshold for value. It's probably ok to wait a few days and just interview candidates so we can see what kind of values they have. Then set a threshold so that 50% (or 20% or 80% or whatever%) of the candidates have higher values.

Another point to determine: when we fail to hire a secretary, how frequently and how much should we lower the threshold.

If v is unknown, we obviously have to observe a few values before making good guesses for a good threshold.

If d is unknown, we'll have to try to hire a few candidates before tuning the algorithm.

What was not mentioned in the question:

How long does it take for the candidate to accept or decline the job offer?
Is the game over when the first candidate accepts the offer?
Can you play the game n times?

If you can't choose the candidates for the interview it seems like winning this game is a matter of coincidence but I might be wrong.


P/poly vs NP separation based on circuit trees instead of DAGs

The class of functions computable by formulas of polynomial size is equivalent to the (nonuniform) class $\mathsf{NC}^1$ of functions computable by (bounded fanin/fanout) circuits of logarithmic depth. Proving the two implications is a nice exercise. In one direction, you can recursively "untangle" each level of a circuit by creating copies of gates. This increases the size by a constant factor for each of the $O(\log n)$ levels of the circuit. The other direction is proven by balancing the tree of the formula.

Also, $\mathsf{NC}^1$ is equivalent, by Barrington's theorem, to width 5 polynomial size branching programs.

We know  that the uniform version of $\mathsf{NC}^1$ is contained in $\mathsf{L} \subseteq \mathsf{P}$ ($\mathsf{L}$ stands for deterministic logspace). It is not known whether any of these containments is proper AFAIK. Also it is not known whether the non-uniform $\mathsf{NC}^1$ is a proper subset of $\mathsf{P/\text{poly}}$.


Automata learning without counterexamples

Consider password automata: for each $w\in\{0,1\}^n$, the DFA $M_w$ accepts the language $\{w\}$. In this case, a membership query is the same as an equivalence query --- and clearly, you'll need exponentially many of these to find the "needle in the haystack". (This is even if the learner knows in advance that the target automaton is of this form.) For a formal proof, a teacher could simply respond to the first $2^{n}-1$ membership/equivalence queries with NO, adaptively choosing the target automaton as the unique remaining possibility.

Update. I neglected to mention that the password automaton has $n+1$ states and is learnable using a single standard Angluin equivalence query (namely, with candidate $M$ as the empty automaton).


How to homomorphically and "efficiently" evaluate $$(a_1 + b_1) \cdot c_1 + (a_2 + b_2) \cdot c_2 + \ldots + (a_n + b_n) \cdot c_n$$

The original question seems to assume that the BGN scheme is the state-of-the-art for problems like this (correct me if I'm wrong :)), so for what it's worth:

The BGN scheme scheme is a prototypical version of a somewhat homomorphic encryption scheme -- the bilinear map gives you a single multiplication on any ciphertext still in the source group $\mathbb{G}$, and (of course) unbounded additions.

It's worth noting that the additively homomorphic property (ie, the unbounded additions) comes from the algebraic representation of the ciphertexts. For similar reasons, El Gamal has multiplicatively homomorphic ciphertexts (unbounded multiplications, no additions), and Paillier has additively homomorphic ciphertexts (no multiplications, unbounded additions).

I think around a year after BGN, Craig Gentry came out with the first fully homomorphic encryption scheme (unbounded multiplications, unbounded additions).

The current state-of-the-art for FHE schemes is some combination of:

((Below are PDF links to ePrint.))

Fully Homomorphic Encryption without Modulus Switching
from Classical GapSVP
Fully Homomorphic Encryption with Polylog Overhead
Somewhat Practical Fully Homomorphic
Encryption

Another Thought:

In case the word "efficiently" in the title was intended to be interpreted as "not FHE," here's an independent observation of mine that might be useful for situations like you ran into just now -- i.e. "I think I need more multiplications than the bilinear map in BGN allows, but I don't want to take the huge hit of FHE..."

If you implement a BGN-like scheme, but substitute a multilinear map for the bilinear map..

See: Candidate Multilinear Maps from Ideal Lattices

..then you should be allowed up to $\kappa$ multiplications, for multilinearity parameter $\kappa$.

The complexity of the GGH multilinear map depends on $\kappa$, but so long as $\kappa=O(1)$, I have a feeling there wouldn't be much difference between the resulting scheme and the BGN scheme in terms of concrete efficiency. (In fact, it's an interesting question on its own!)

In any case, suppose you ran into a situation where you needed.... THREE multiplications per plaintext... Think about using a multilinear map.

A few more details for intuition about what multilinear maps are, if they're new to you:

BGN uses groups $(\mathbb{G}, \mathbb{G}_T)$ and a map $e: \mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_T$.

IIRC, the GGH multilinear map with, say, $\kappa = 2$ can be seen as reducing (in the simplest case) to groups $(\mathbb{G}_0, \mathbb{G}_1, \mathbb{G}_2)$ and a set of bilinear maps, written generally as $e = \{e_i\}_{i\in [0,...,\kappa-1]}$ where for all $i$, $e_i : \mathbb{G}_i\times\mathbb{G}_i\rightarrow\mathbb{G}_{i+1}$.


Does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$?

Recall PCP theorem, $PCP(log(n), 1)$ is NP already and actually $PCP(poly(n),1)$ is $NEXP$.

The problem of your proof is that you cannot simulate a coRP algorithm on a string with length only $2^q$. Though it will only access q bits, the bits it accesses to depend on the random coins. You should not think of a specific coin outcome but all of them on a input. That is basically why your proof doesn't work.


It is an interesting problem to figure out what bothers the OP. First of all, it is not at all the case that the equation put forward by the OP says "different computations have the same value". For instance, the computations

do _ <- putStr "foo"
   return 42

and

do _ <- putStr "bar"
   return 42

both "have" value 42 but are different, since one prints out foo and the other bar.

The problem really arises elsewhere, namely in the idea that "a computation has a value". Consider the following monads:

The Maybe monad: a computation may have a value (Just v), or have no value at all (Nothing).
The non-determinism monad: a computation results in a set of (possible) values. What does it mean that it "has" a value? Has all of them? One of them?
The probability monad: a computation results in a probability distribution of values. Again, in what sense does such a computation "have a value"?
The continuation monad: a computation results in a continuation. What does it mean for a continuation to "have a value"?

It is best to just forget the idea that in general a computation gives back a value, two values, possible values, or anything like that.

There may be particular monads for which it does make sense to speak about "computations having values", but not for all monads.

The OP also suggests that intensional features of computations (one computation takes a different number of steps than another) should be expressible with monads. This is true, but whatever intensional features you want to capture with the monad (memory usage, time), you have to expose them explicitly in the monad. For instance, we could do this:

data Timed a = Timing (a, Integer)

instance Monad Timed where
    return x = Timing (x, 0)
    (>>=) (Timing (x, n)) f = (let Timing (y, m) = f x in Timing (y, n + m + 1))

x :: Timed Integer
x = do u <- return 14
       v <- return 3
       return (u * v)

y :: Timed Integer
y = do u <- return 14
       v' <- return 1
       v'' <- return 2
       v <- return (v' + v'')
       return (u * v)

Here x and y both "have" value 42, but the timing is different since y takes four steps to compute and x takes just two.


Is there a reasonable automated proof system for TCS theorems?

Here is an Isabelle/HOL library containing Rice's theorem, which states undecidability of a wide range of problems. Since this library models computability via recursive functions, you have to encode a universal Turing machine as a recursive function in order to use this theorem for proving undecidability of the halting problem of Turing machines.  However, the essential parts of the undecidability proof is already done.

http://afp.sourceforge.net/browser_info/current/HOL/Recursion-Theory-I/index.html


In the realm of constructive solid geometry, questions like the one you asked can probably be answered. Here, solids are constructed by unions and differences of basic shapes (for example, a sphere with a tunnel can be described as Ball - Cylinder. Shapes are then built up as trees of operations on basic shapes (at the leaves), and the differencing problem can then be thought of as a labelled tree-diff problem (which has been examined among other things in the context of comparing XML documents).

I'm not claiming that these questions are already being studied, but CSG is definitely one place where the geometric questions you're asking might be addressed.


Diameter Constrained Minimum Spanning Graph

Minimum Diameter Spanning Subgraph is what you should be looking for. It is NP-Hard to compute even in the case of planar graphs. This paper gives a nice overview.


Circuity complexity: monotone circuit of Majority function

Time complexity is often defined as the "number of operations in the worst case for a Turing machine." The monotone circuit model of computation is not the Turing time model. Thus it is not meaningful to say what the time complexity of such a circuit is.

On the other hand, if we view the monotone circuit model as a model of actual circuits, then one "time cost" of computation is the depth of such a circuit. Thus in that sense the time complexity of the circuit you mention is 5.3log(n).

Of course, in real circuits there are other factors besides "depth" that contribute to "how long it takes to do the computation." For example, the longest wire in a circuit often is bottleneck in actual VLSI computation as its larger capacitance takes longer to charge.


Order of drawing colored balls from a bag

First observation: the cases with and without replacement have exactly the same answer. (Once you have drawn a red ball, say, you don't care about future draws of red balls: all you care about now is the relative order of future green and yellow balls).

A good way to attack the case with replacement is by embedding in continuous time.

Imagine that the balls arrive according to independent Poisson processes with appropriate rates: rate 12 for yellow balls, rate 18 for red balls, rate 2 for green balls. Then whenever a ball arrives, it has probability 12/32 of being yellow, 18/32 of being red and 2/32 of being green, as desired - I'm ignoring the white balls since they're irrevelant. So the sequence of colours observed is exactly as it would be from a sequence of independent draws with replacement.

Now you want to know the following: does the first event in the green process occur after the first events in the yellow and red processes? This is easy enough to calculate, since the first event in a Poisson process of rate $r$ has exponential distribution with rate $r$, and the three processes are independent.

So, integrating over the time of the first event in the green process, you get the following expression for your probability:

$\int_0^\infty 2e^{-2x} (1-e^{-12x})(1-e^{-18x})dx$

which is straightforward to evaluate and generalises nicely.


[Revised.] I think that there has been a little confusion about what I was referring to in my original answer. I am revising it in order to better describe the result.

Note that your representation will only be capable of representing transitively-closed DAGs, i.e. partial orders; and this representation is a previously-studied one for partial orders. For instance, a paper by Mihalis Yannakakis shows that determining whether a partial order (equivalently, a transitively-closed digraph) has such a representation is NP-complete for n ≥ 3, but feasible if n ≤ 2.

Also, because the representation describes transitively closed DAGs, the body of research on the Transitive Closure problem is a reasonable place to look for related representations. My original response described a representation which, as it turned out, was strictly less general than the representation in terms of vectors. However, your representation has some similarities to the tree-cover representation of transitively closed DAGs (see Efficient management of transitive relationships in large data and knowledge bases: also described briefly in this article).

Without loss of generality, if the DAG has more than one 'source' (vertex with in-degree 0), add a virtual 'root' which can reach all of the sources. The entire DAG then has a spanning tree.
For each vertex, define an interval [ av , bv ] to each vertex v, in such a way that the interval at each node contains the intervals of all its descendants. (For instance, the upper bound bv for each v can be taken to be the post-fix order of the vertex in the tree; the lower bound av is the minimum of these post-fix values for the sub-tree.)
To represent directed edges which are not in the tree, each node keeps a list of the intervals of the different nodes which are reachable from it. (For any given sub-tree which is reachable from a given node, it suffices to record the interval belonging to the root of that sub-tree.)

Thus, the in-bound edges of each vertex is represented by the single interval [ av , bv ] , and its outbound edges are represented by a union of disjoint intervals which strictly contain the intervals of vertices that it can reach.

Some observations:

The vector representation is related to the interval nesting condition by using higher dimensional "intervals". Without loss of generality, the length n of the array xv at each vertex is even (by buffering with a final dummy co-ordinate if needed). Let m = n/2. Partition the coefficients as
$$ \mathbf x^v \;=\; [ \;a^v_1 \;,\; \ldots \;,\; a^v_m \;;\; c^v_1 \;,\; \ldots \;,\; c^v_m \;] $$
For each 1 ≤ j ≤ m , let $$ U_j = \left( \max_v \;\; a^v_j \right) + \left( \max_v \;\; c^v_j \right). $$ Then, we may define for each node an m-fold cartesian product of intervals,
$$ I^v \;=\; [\;a^v_1\;,\; U_1-c^v_1 \;] \times \cdots \times [\;a^v_m\;,\; U_m-c^v_m \;]. $$
Two such "$m$-dimensional intervals" nest if and only if the corresponding vectors have the appropriate ordering relations. It is trivial to verify that the intervals nest only if the corresponding vectors are ordered; for the converse, we depend on none of the coefficients in the graph being larger than the corresponding bounds Uj .
It is not clear to me whether the representation by vectors and by tree-covers are efficiently interconvertible; however it is easy to show that the case n = 2 corresponds exactly to the representation of directed trees in terms of tree-covers (i.e. the two representations are efficiently and reversibly inter-convertible, essentially by the technique I described above). Thus, the dimension may in some sense correspond to how tree-like the digraph is.


Diagonalization arguments for QMA type proof systems

Yes, diagonalization arguments can still be used. For the oracle separation $\mathcal{QMA}^\mathcal{O}\subsetneq \mathcal{PP}^\mathcal{O}$, design an oracle $\mathcal{O}$ such that the following language separates the classes:

$$L = \{1^n\ |\ \left| \mathcal{O}\cap\{0,1\}^n\right|>\tfrac{1}{2}2^n \}$$

This language is clearly in $\mathcal{PP}^\mathcal{O}$ for any choice of oracle $\mathcal{O}$. However, it is not always in $\mathcal{QMA}^{\mathcal{O}}$, "because" it is difficult for a quantum machine to estimate whether a state $a|0\rangle |\phi\rangle+b|1\rangle |\psi\rangle$ has $|a|>|b|$ when the difference $|a|-|b|=\mathcal{O}(2^{-n})$ is exponentially small. This is true even in the presence of a prover, because even if the prover supplies the correct answer, it is not possible to verify whether the answer is correct. In your terminology: There is no needle to give; rather, the task is to count the number of needles, and then a single needle doesn't help much.

I hope somebody can supply useful literature references.


How powerful is $ACC^0$ circuit class in average case?

There seem to be typos in what you wrote; I take it you're asking: is there a function $f \in NEXP$ such that for all polynomials $p$ and infinitely many $n$, no ACC0 circuit of $p(n)$ size can compute $f_n$ on more than $1-1/p(n)$ inputs of length $n$?

As far as I know, this is open. But here is a possible path to doing it. We know that every $NEXP$-complete function $f$ does not have ACC0 circuits of polynomial size. Perhaps an arithmetization of some $f$ (representing $f$ naturally as a family of multilinear polynomials) over a large field of finite characteristic (e.g. characteristic two) would work. (Arithmetizations can typically give you average-case hardness "for free" ... but one would have to carry out the finite field arithmetic in ACC0, presumably.) Cite me if you figure it out. ;)


Complexity class of a subset problem similar to subset sum

With some basic arithmetic, we can reduce this to a question about a two-variable Diophantine equation.

Based upon your comments, it sounds like $d$ was intended to be given as input.  Now the question is just: can we choose $x_1 \ge 1$ and $n$ such that $x_1 + (n-1)d < K$ and such that the arithmetic sequence $x_1,x_1+d,x_1+2d,\dots,x_1+(n-1)d$ sums to $K$.

It is easy to compute the sum of this arithmetic sequence.  By the Gauss formula, it sums to

$$n x_1 + dn(n-1)/2.$$

So, given $K,d$, we want to find a solution to the equation

$$n x_1 + dn(n-1)/2 = K$$

where $x_1,n$ are positive integers and where $x_1+ (n-1)d < K$.

You can view this as a diophantine equation in two variables $x,y$ of the form

$$2xy + \alpha x^2 + \beta x + \gamma = 0,$$

where $\alpha,\beta,\gamma$ are integer constants given in advance and there is an additional linear inequality on $x,y$.  (Here I made the replacement $x=x_1$, $y=n$.)  I don't know if this problem has a nice solution.

One thing we can say is that $n$ must be a divisor of $2K$, since we know

$$2nx_1 + dn(n-1) = 2K,$$

and the left-hand side is divisible by $n$.  Therefore, if you know the factorization of $2K$, and if it doesn't have too many different prime divisors, you could try enumerating all divisors of $2K$ as the candidate values of $n$, and then for each candidate value of $n$, solve for $x_1$  and see if it yields an integral solution.  However, in general this will not be efficient: it gives an algorithm that is efficient in the average case but runs in exponential time in the worst case.


Are there incompressible strings $S$ such that $K(SS) \lt K(S)$?

A rough argument that there should be infinitely many such strings is as follows.

Consider a machine $M$ that first left-pads its input with zeroes out to some known length $2f(|T|)$ (we will specify $f$ below), then repeatedly performs some length-preserving and random-looking operation on it, halting only when it has produced (essentially by accident) a string consisting of two copies of the same string.  It is not required to halt for every input.  When it does, the output it produces from input $T$ will have complexity satisfying $K(SS) \approx K(T) + K_M$ for some $K_M$, as long as $f(|T|)$ is large enough, and $S$ will have length $f(|T|)$.  The string $S$, moreover, will have complexity $K(S) \approx K(SS) + K_C$ for some $K_C$.  The key final step is to choose the right $f(|T|)$.  It must be large enough to ensure that $SS$ is best described as "the output of $M$ applied to $T$", but small enough to ensure that the description of $S$ as "half the output of $M$ applied to $T$" is not less than $|S| = f(|T|)$.  Taking $f(|T|)=|T|+K_M+K_C-1$ should work.  We conclude that arbitrarily long incompressible inputs $T$, if they halt, will typically produce outputs $SS$ such that $K(SS) < K(S)$ and such that $S$ is incompressible.  The machine $M$ could do any number of things; for instance, the machine $M$ that squares its input and then discards every other bit of the result would probably work.


This seems to be addressed in the following paper by Joseph P. Romano, Section 3  [1] (specifically, Example 1):

Example 1 (Finite versus not finite mean). Let $X$ be $X_1, \dots, X_n$, $n$ i.i.d. observations on the real line. As remarked by Bahadur & Savage (1956), "it would be interesting to know whether, in comparable non-parametric situations, tests of the existence of $\mu$ are equally unsuccessful"; here, $\mu$ refers to the mean of an observation. So, let $P_0$ be the family of distributions on the real line with a finite mean, and let $P_1$ be the distributions without a finite mean. Condition B readily holds. [...] Hence, the conclusion of theorem 1 holds, and so it is impossible to construct a test with power greater than the size of the test.

[1] Romano, Joseph P. “On Non-Parametric Testing, the Uniform Behaviour of the t-Test, and Related Problems.” Scandinavian Journal of Statistics, vol. 31, no. 4, 2004, pp. 567–584. JSTOR, www.jstor.org/stable/4616851. Accessed 15 Sept. 2020.


Monotone arithmetic circuit complexity of elementary symmetric polynomials?

One challenge is that if you remove the "monotone" restriction, we do know how to compute such things efficiently.  You can compute the value of all $S_0^n,\dots,S_n^n$ (evaluate all $n+1$ elementary symmetric polynomials) in $O(n \log^2 n)$ time, using FFT-based polynomial multiplication.  So, proving a $\Omega(nk)$ lower bound in the monotone circuit model would require proving a $\Omega(n^2)$ lower bound on polynomial multiplication.

Here's how.  Introduce a formal unknown $y$, and consider the polynomial

$$P(y) = \prod_{i=1}^n (1 + x_i y).$$

Note that since the $x_i$'s are known constants, this is a univariate polynomial with unknown $y$ and with degree $n$.  Now you can note that the coefficient of $y^k$ in $P(y)$ is exactly $S_k^n$, so to evaluate all the $S_0^n,\dots,S_n^n$, it suffices to compute $P(y)$.

This makes it possible to compute $P(y)$ in $O(n \lg^2 n)$ time: build a balanced binary tree of polynomials with the $(1+x_i y)$'s at the leaves, and multiply the polynomials.  Multiplying two polynomials of degree $d$ takes $O(d \lg d)$ time using FFT techniques, so we get the recurrence $T(n) = 2 T(n/2) + O(n \lg n)$, which solves to $T(n) = O(n \lg^2 n)$.  For convenience, I am ignoring $\text{poly}(\lg \lg n)$ factors.

If you care about the case where $k$ is very small, you can compute $S_0^n,\dots,S_k^n$ in $O(n \lg^2 k)$ time using similar tricks, keeping in mind that you only care about $P(x) \bmod y^{k+1}$ (i.e., throwing away all terms of $y^{k+1}$ or higher powers of $y$).

Of course, the FFT uses subtraction, so naively it's not expressible in a monotone circuit.  I don't know whether there's some other way to multiply polynomials efficiently with monotone arithmetic circuits, but any efficient monotone method for polynomial multiplication immediately leads to an algorithm for your problem as well.  So, lower bounds on your problem require/imply lower bounds for polynomial multiplication.


How do I choose a functional dictionary data structure?

I can't really answer #2 without getting lost (there are too many dimensions along which you can compare these structures), but for #3 the answer is pretty simple.

Use an imperative data structure if: (a) there is absolutely no aliasing, or (b) you really need to use aliasing for efficient broadcast.

If there is no aliasing of your data structure at all, then you are not taking advantage of the fact that functional data structures are persistent. So there is no reason to pay for their cost. There are two caveats to this advice. First, you may prefer the simplicity of implementation of a functional data structure: implementing deletion for a functional red-black tree will make you curse, but implementing deletion in an imperative red-black tree with parent pointers will leave you contemplating suicide. Second, assignment can be more expensive than you expect in a gc'd language, since writes can get data structures moved out of the young generation. We really don't have a good theory of cache effects and gc, so you have no choice but to do benchmarking.

Second, if you need a broadcast channel, then a shared data structure is an excellent way to do it. With a constant-time update, you can tell arbitrarily many other people that a value has changed. (This is why union-find is such a great data structure.) With a purely functional setup, either you need to modify all those other people, or give them abstract pointers into a state you code up manually (which is a kind of obtuse thing to do).

If you either don't want to reason about aliasing and object ownership, or if you need multiple versions of the same data structure (you need both a new and an old version, say), then just use a functional data structure.

The place where I find following this advice the hardest is with graph algorithms. There are lots of really elegant imperative graph algorithms, but it's often the case (say, when writing compilers) that you also want persistence. People typically try to split the difference and use the cool imperative algorithm but try to bolt versioning onto the side to get persistence. This is generally pretty horrible, full of bugs, and prone to losing the performance advantage of the imperative algorithm.


Is Buchberger's algorithm or Wu's method valuable theoretically when we have the Tarski–Seidenberg theorem?

For Buchberger, it depends what you want it for, but generally speaking the answer is no. First, as pointed out on the Wikipedia article, the complexity upper bound given by Tarski-Seidenberg is horrendous, whereas Buchberger's algorithm is exponential space, which is optimal (since ideal membership is EXPSPACE-complete).

Second, Tarski-Seidenberg is for semi-algebraic sets over the reals (that is, allowing $\leq, <, =, \neq$), whereas Buchberger's algorithm works not only for the reals, but for polynomials over any field, or even over other rings (such as $\mathbb{Z}$). With minor modifications, Buchberger's algorithm even works in various noncommutative analogues of polynomial rings.

Third, Grobner bases (and hence, Buchberger's algorithm) can be used for many more things besides quantifier elimination. For example, intersecting ideals, quotienting ideals, computing syzygy modules of ideals, proof systems (hence algorithms) for Tautologies, coding theory, group cohomology, applying toric geometry to algebraic geometry (where we think of the initial ideal as a way of deforming an arbitrary variety into a toric variety, and thereby learn things about the original variety that are easier to deduce for the toric one), the list goes on...

(I am less familiar with Wu's method.)


A language $L$ is said to be commutative if the following property holds:

  for every  word $a_1 \dotsm a_n \in L$ and any permutation $\sigma$ on
  $\{1, \ldots, n\}$, the word $a_{\sigma(1)} \dotsm a_{\sigma(n)}$ is
  also in $L$.

Now, my understanding of your question is the following:

  given a finite deterministic automaton $\mathcal{A}= (Q, A, \cdot)$, decide whether
  the language accepted by $\mathcal{A}$ is a commutative language.

There is a polynomial algorithm to answer this question.
Indeed a language is commutative if and only if its syntactic monoid is commutative. But the syntactic monoid $M(L)$ of $L$ is equal to the transition monoid of its minimal automaton. It follows that, $L$ is commutative if and only if the generators of $M(L)$ commute. In terms of automata, this is equivalent to check, for every pair of letters $(a, b)$, whether $q \cdot ab = q \cdot ba$ for all $q \in Q$.

Now, given $\mathcal{A}$, you can compute the minimal automaton of $L$ in $O(|Q|\log |Q|)$ and then check commutativity in $O(|Q||A|^2)$.


The length of non perfect binary 1 error correcting codes

Here is a table of the best known (linear and non-linear) binary codes for distance 3, for $n \leq 512\,$. Distance 3 is equivalent to being able to correct one error. The table only gives you the number of codewords, but the references given in the table will tell you how to construct the codes themselves.

The best known codes for $n$ not in this table can be found by taking the code for the next larger $n$ in the table, repeatedly choosing a coordinate, and retaining only those codewords which have $0$'s (or $1$'s) in that position. You can delete $\ell$ coordinates and retain a $2^{-\ell}$ fraction of the codewords.


For a given algorithm with expected runtime M, does there exist (in theory) an algorithm with equivalent guaranteed runtime?

No. See Chapter 2 of the book Randomized Algorithms by Motwani and Raghavan. They discuss a tree-evaluation problem for which:

any deterministic algorithm takes linear time;
there is a Las Vegas randomized algorithm with sublinear expected running time.