Binary vector $t$ in $span(S)$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$ $\Rightarrow$ $t$ in $span(S)$ over $\mathbb{Z}$?

The revised conjecture is true, even under relaxed constraints on $S$ and $t$—they may be arbitrary integer vectors (as long as the set $S$ is finite). Notice that if we arrange the vectors from $S$ into a matrix, the question simply asks about the solvability of the linear system
$$Sx=t$$
in the integers, hence I will formulate the problem as such below.

  Proposition: Let $S\in\mathbb Z^{k\times n}$ and $t\in\mathbb Z^k$. Then the linear system $Sx=t$ is solvable in $\mathbb Z$ if and only if it is solvable in $\mathbb Z/q\mathbb Z$ for all prime powers $q$.

This can be proved in at least two ways.

Proof 1:

For any prime $p$, the solvability of the system modulo each $p^m$ implies that it is solvable in the ring of $p$-adic integers $\mathbb Z_p$. (There is a minor problem in that the solutions are not unique, hence given solutions mod $p^m$ and mod $p^{m'}$ need not be compatible. This can be sorted out e.g. using the compactness of $\mathbb Z_p$, or using König’s lemma.)

Consequently, the system is also solvable in the product
$$\hat{\mathbb Z}=\prod_{p\text{ prime}}\mathbb Z_p,$$
i.e., the ring of profinite integers. I claim that this implies its solvability in $\mathbb Z$.

Notice that solvability of the system (i.e., $\exists x\,Sx=t$) is expressible as a (primitive positive) first-order sentence in the language of abelian groups, augmented with a constant $1$ so that we can define $t$. Now, one can check that the complete first-order theory of the structure $(\mathbb Z,+,1)$ can be axiomatized as follows (it’s an order-free version of Presburger’s arithmetic, or rather, of the theory of $\mathbb Z$-groups):

the theory of torsion-free abelian groups,
the axioms $\forall x\,px\ne1$ for each prime $p$,
the axioms $\forall x\,\exists y\,(x=py\lor x=py+1\lor\dots\lor x=py+(p-1))$ for each prime $p$.

However, all these axioms hold in $\hat{\mathbb Z}$ as well. Thus, the structures $(\mathbb Z,+,1)$ and $(\hat{\mathbb Z},+,1)$ are elementarily equivalent, and the solvability of $Sx=t$ in $\hat{\mathbb Z}$ implies its solvability in $\mathbb Z$.

In fact, we do not actually need the full axiomatization of $(\mathbb Z,+,1)$ above: it is enough to observe that $\hat{\mathbb Z}$ satisfies the axioms 2., which means that $\mathbb Z$ is a pure subgroup of $\hat{\mathbb Z}$, and therefore a pure $\mathbb Z$-submodule.

Proof 2:

There exist matrices $M\in\mathrm{GL}(k,\mathbb Z)$ and $N\in\mathrm{GL}(n,\mathbb Z)$ such that the matrix $S'=MSN$ is in the Smith normal form. Put $t'=Mt$. If $x$ is a solution of $Sx=t$, then $x'=N^{-1}x$ is a solution of $S'x'=t'$, and conversely, if $x'$ is a solution of $S'x'=t'$, then $x=Nx'$ is a solution of $Sx=t$. (This equivalence holds over any commutative ring, as $M,M^{-1},N,N^{-1}$ are integer matrices.)

Thus, we may assume without loss of generality that $S$ is a diagonal matrix (meaning that the excess rows or columns are zero if $k\ne n$). Then the system $Sx=t$ is unsolvable in $\mathbb Z$ only if

for some nonzero diagonal entry $s_{ii}$ of $S$, the corresponding entry $t_i$ of $t$ is not divisible by $s_{ii}$, or
for some $i$, the $i$th row of $S$ is zero, but $t_i\ne0$.

Let $q$ be a prime power such that $q\nmid t_i$, and, in the first case, $q\mid s_{ii}$. Then the system $Sx=t$ is not solvable in $\mathbb Z/q\mathbb Z$.


Is the 2016 implementation of Shor's algorithm really scalable?

The main thrust of Cao and Luo's argument is that in the variant of the algorithm that was implemented, the first register—that eventually contains the output—contains only 1 bit. And if you only get 1 bit of output from the algorithm, that's insufficient for factorization. (For one thing, although this isn't their argument, 1 bit clearly does not contain enough information to determine the factors.)

What Cao and Luo seem not to realize is that for the variation of the Fourier transform with only one bit in the first register, the same value of $c$ is output as in the standard factoring algorithm; it's just output one bit at a time.
This change doesn't affect the $O(\log^3 N)$ running time.

To try to be fair to Cao and Luo, they say that they don't think this algorithm works, and if it does work, then it isn't Shor's algorithm because it doesn't exactly match the algorithm described in the original factoring paper. A quote from their paper:

  Finally, we would like to stress that if the implementation is indeed credible then it would be a new quantum factoring algorithm, not the Shor algorithm, because all requirements of the original Shor’s algorithm are not satisfied.

And indeed, it's not the algorithm from my original factoring paper. It uses the phase estimation procedure from Kitaev's factoring algorithm, and a variant on that, discovered by Griffiths and Niu (not by Parker and Plenio, as I said in a previous edit of this answer) that lets the algorithm output the estimate of the phase one bit at a time.


What automorphisms on a Markov Chain imply a uniform limiting distribution?

This is perhaps a nearly trivial observation, but I couldn't think of another general property just of the automorphisms that would ensure the limiting distribution is uniform.

If the automorphism group of the corresponding weighted directed graph is vertex-transitive, then the limiting distribution must be uniform, since then no vertex can be distinguished from any other.


Where do I turn for help with research/publishing?

If your SAT algorithm is meant to be practical, then you should run the SAT competition benchmarks on it.  The SAT solving community is going to take your work much more seriously if you can show that your approach is competitive with existing solvers.  Your solver doesn't have to be faster than every solver, or solve more instances, but it should be a serious competitor.  You don't need a very fast or powerful machine to run the benchmarks; you can simply compare runtime against one of the free SAT solvers like MiniSAT or PicoSAT.  These solvers will also allow you to see what the answers should look like.

If you are working on a practical solver that uses new techniques, and your approach is not yet competitive, I would still suggest trying these benchmarks.  They would help you to understand the kinds of problems that you should be aiming to solve, and the kind of performance you should be aiming for.  You might also want to read some of the key chapters of the Handbook of Satisfiability, or the recent survey

Knot Pipatsrisawat and Adnan Darwiche, On Modern Clause-Learning Satisfiability Solvers, Journal of Automated Reasoning 44 277–301, 2010. (PDF)

to see the kinds of arguments that support the major solvers.  If you have new ideas that are not yet optimized to perform as well as the top solvers, you would need to explain the potential advantages of your approach to someone who knows the long sequence of theoretical reasoning that has led to the current set of "best practice" design decisions.

If your contribution is purely theoretical, then you need to be aware of the many papers in this area, and explain in your paper why your approach is better in at least some way.  Have a look at recent work by for instance Amin Coja-Oghlan or Alan Frieze to get a feel for the state of the art and for useful pointers to important papers.


Complexity of Determining Linear Separability

If you merely want separation, then this is solved using linear programming. If you want to maximize the separation, then you're in the land of linear classification problems and max-margin classification in general.


Given discrete rvs X,Y, find Z s.t. I(Z;X) is high and I(Z;Y) is low. -- known problem?

In one form, your question is actually a clustering question that is addressed by the information bottleneck method.

Roughly, $Y$ represents the rows of a joint distribution and $X$ represents the columns. The random variable $Z$ then represents a distribution over the rows ($Y$) that is highly compressed (because $I(Z;Y)$ is small) but represents the joint distribution well (because $I(Z;X)$ is large).

It's not clear to me that this can be solved using LPs. the underlying problem is not convex. But there's a simple EM-style alternating optimization scheme that can be used to solve it.


I finally managed to dig out a nice survey by Kitaev and Mansour, which gives pointers to the literature related to permutation pattern matching on  "usual"/signed/coloured permutations and words.


Largest common subgraph of two maximal planar graphs

It's NP-complete, via a modified version of the reduction Wigderson used to prove that Hamiltonicity of maximal planar graphs is NP-complete.

Careful examination of Wigderson's 1982 NP-completeness proof of hardness for Hamiltonian cycles in maximal planar graphs (http://www.math.ias.edu/avi/node/820) shows that the instances produced by his reduction have the property that there exists an edge $e$ such that either there exists a Hamiltonian cycle through $e$ or there does not exist any Hamiltonian cycle at all. For instance, $e$ can be chosen to be one of the edges in one of Wigderson's $M$-gadgets.

Let $G$ be a hard instance constructed  in this way, and embed $G$ so that the edge $e$ belongs to the outer triangle of the embedding. Connect many copies of this embedded graph so that their $e$-edges form a cycle, and make the result maximal planar again by adding two more vertices, one on each side of this cycle, connected to all the exposed vertices of the copies of $G$. Let the number of copies be $c$, and call the resulting graph $H$. Let $n$ be the number of vertices in $G$.

Our hard instance for the largest common subgraph will be the pair $(H,B)$ where $B$ is a bipyramid with the same number of vertices as $H$. Thus, an optimal common subgraph will have to pair all of the vertices. If we make $c$ large enough, the subgraph will necessarily pair the apexes of the bipyramid with the two added vertices in $H$, because their degrees ($c$ and $2c$) will be sufficiently higher than every other vertex in $H$, so that adding these degrees to the solution size will make up for any disruption elsewhere caused by this pairing.

If $G$ is Hamiltonian, then the common subgraph formed by matching the Hamiltonian cycle (minus $e$) in the copies of $G$ to the equator of the bipyramid will have $c(n+2)$ edges, $c(n-1)$ for the equator and $3c$ for the apexes. If $G$ is not Hamiltonian, then (for large enough choices of $c$ that the optimal solution pairs the apexes correctly) any common subgraph will have fewer edges: still $3c$ at the apexes but fewer than $c(n-1)$ elsewhere. So testing whether the common subgraph of $H$ and $B$ has at least $c(n+2)$ edges is NP-complete.


An algorithm for calculating the probability of a disease spreading through a graph

Immunity seems to make your problem easier in one sense, as it means that infection can be modelled by a process that terminates after a linear number of infection attempts.  The stipulation that the probability of infection does not depend on the neighbours of a vertex also helps.  However, the model does not seem easy to analyse: the immune vertices in effect are removed from the graph, so a vertex may effectively become unreachable.
The infection, immune, and unreachable probabilities depend on the intermediate graphs created by the infection process.

It might be useful to start with cliques, paths, and cycles with a single initially infected vertex.  Cliques are trivial.  For a path with one infected endpoint the probability that the other endpoint becomes infected at some stage is the product of the probabilities of infection of all the intermediate vertices.  For a cycle, the probability depends on both paths; the longer path becomes relevant if an immune vertex appears on the shorter path.  Trees also have a single path between any two vertices, so can be handled as for the path case.

It might then be feasible to extend the analysis to $k$-connected graphs and regular grids, though this already seems quite tricky.

I am not familiar with literature that deals with this specific problem.  Here are some general comments and pointers.

Some relevant keywords are "contagion" (in the context of network models) and "percolation" (in statistical mechanics).  These models tend to focus on the behaviour of randomized processes that behave like the one you suggest.  However, different models focus on different parameters of interest, so you might have to examine several to find one that best matches the specific one you are interested in.

As an example, a lot of post-2008 work has applied contagion models to financial systems, since it has been argued that these models explain well the gridlock experienced at that time by the global financial system.

The Ising model is one of the simplest and earliest models that involve interacting parties in a graph, and has an extensive literature.

From a purely TCS perspective, computing the partition function of spin systems like the Ising model is equivalent to counting the solutions of a constraint satisfaction problem.  The mixing time is also often of interest.

Andrei Bulatov and Martin Grohe, The complexity of partition functions, TCS 348, 2005, 148–186.  doi:10.1016/j.tcs.2005.09.011 (preprint)
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum, Matrix norms and rapid mixing for spin systems, Annals of Applied Probability, 19, 2009, 71–107.
doi:10.1214/08-AAP532


Can a det. $k$-counter machine ($k \geq 2$) be simulated by a det. $k'$-counter machine using non-$\epsilon$-moves followed by $\epsilon$-moves?

No, that is not possible. There are languages accepted with $\varepsilon$-transitions that cannot be accepted if $\varepsilon$-transitions can only occur at the end (even if you
allow nondeterminism in exchange for restricted $\varepsilon$ usage).

Take, for example, the language $L=\{w\#w \mid w\in\{a,b\}^*\}$.
As a recursively enumerable language, it can be accepted by a
determinisic 2-counter machine. A simple counting argument shows
that this requires interspersed $\varepsilon$-transitions:

If $\varepsilon$-transitions occur only at the end, then
after reading a word $w\#$, the machine can only produce counter
values whose size is linear in $|w|$. In particular, there is
a polynomial $p$ so that after reading a word $w\#$, the machine
can be in at most $p(|w|)$ configurations. Thus, since there
are exponentially many words of a given length, the machine can
be tricked into accepting a word $w\#w'$ with $w'\ne w$.


NP completeness of linear $0-1$ assignment problem

If I understood it well, (1) is also NP-complete, a possible reduction is from SUBSET SUM:

Given a set of $m$ positive integers $A = \{a_1, ..., a_m\}$, and a positive integer $B$, is there a subset of $A' \subseteq A$ a such that $\sum_{a_i \in A'} a_i$

You simply pick $n = (m+1)$ and build your set in this way:

add $ a_1, a_2, , ..., a_m$
add $m$ zeros
add the only negative number $-B$
"fill" the other remaining $n^2 - 2m - 1$ elements with $C = \sum_{a_i} + B +1$

($\Rightarrow$) If the original subset sum has a solution $A'$ then it is sufficient to use this partition $\Pi_1$

a1  C  C  ... C  0  C
 0 a2  C  ... C  C  C
        ....
 C  C     ... 0 am  C
 C  C     ... C  C -B

and for each "row" pick $a_i$ if $a_i \in A'$, $0$ otherwise (and pick the final $-B$)

($\Leftarrow$) If there is a partition $\Pi_1$ with a vanishing 0/1 assignment then note that:

(i)  none of the $C$s can be picked (they are too large);
(ii) at least one row must contain all elements different from $0$ (because there are $m+1$ rows and only $m$ zeros); so at least one nonzero element must be picked;
(iii) in every case the $-B$ element must be picked to vanish the sum

So the elements $a_i$ picked, no matter how the elements are partitioned between the rows, sum exactly to $B$; i.e. they are a valid solution for the original SUBSET SUM problem.

OUCH! I just read Michael's answer about problem (2) and the reduction is almost the same ... so you can also accept his answer!

EDIT: the reduction remains valid for the (1b) case:

The ($\Leftarrow$) direction it uses only the constraints on $\Pi_1$ which are the same of case 1a (exactly 1 "pick" from each row).

The ($\Rightarrow$) direction is also valid; to see it "visually", just build the main diagonal of $\Pi_1$ with the elements of $a_i \in A'$, the element $-B$, while the remaining elements of the diagonal are $0$s.

For example if $m = 5$ and the solution of the subset sum is $A' = \{ a_1, a_2, a_4 \}$, $\Pi_1$ is:

 a1  0  C   C  C   C
  C a2  0   C  C   C
  C  C  0  a3  C   C
  C  C  C  a4  0   C
  C  C  C   C  0  a5
  C  C  C   C  c  -B

In this way you can build $\Pi_2$ setting the element $j$ of row $i$-th equal to element $j$ of column $i$ in $\Pi_1$. The assignment clearly vanishes both $\Pi_1$ and $\Pi_2$ and the constraints are met.


I try to give my intuition why I think this is unlikely to hold. Take your favorite problem in $PPA$, and convert it into a problem in $\sharp P$, e.g., our function $f$ can be the number of Hamiltonian cycles in an input 3-regular graph containing a certain fixed edge. From the parity argument we know that $f$ is always even, so you can define $F:=f/2$ and I see no reason why $F$ would be in $\sharp P$.


If you are asking if the same statement holds true or not in higher dimensions, it does. Just project all the points to a random 2-dimensional plane.
Another natural generalization is to consider hyperplanes instead of lines. Here, you have Beck's "other" theorem:

Theorem: For any $d \geq 2$, there are constants $\beta_d, \gamma_d \in (0,1/2]$ such that for any set $P$ of $n$ points in $\mathbb{R}^d$, at least one of the following holds:

a hyperplane contains at least $\beta_d n$ points of $P$
the $d$-tuples of $P$ span at least $\gamma_d n^d$ distinct hyperplanes.

Here, a hyperplane is a $(d-1)$-dimensional flat. For $d=2$, this is essentially what you stated. The restriction that $\beta_d \leq 1/2$ is from the example of having two skew lines in $\mathbb{R}^3$ containing $n/2$ points each, where the number of spanned planes is $n$. For more, see: http://www.cs.elte.hu/~elekes/Abstracts/elest.ps


Cover a Concave Polygon with a minimum number of rectangles

This is a variant of geometric set cover. Depending on the exact settings, you might be able to do some good approximation. The problem is of course NP-Hard. The natural huersitics are to use greedy algorithm (always pick the rectangle/strip that covers the most area not covered yet. The alternative technique is to use reweighing. There are some interesting theoretical results, but frankly, nothing that should be too useful in practice. One interesting hueristic you might want to try, is to first decompose your polygon into minimal number of convex shapes (using Keil dynamic programming algorithm), and then covering each convex polygon separately...


Computable function $f = \Theta(g)$ with $g$ uncomputable

Sure: just take g(n) = n + halt(n) (where halt(n)=1 if TM number n halts, and 0 ow).


What is a precise definition of "in-place"?

An in-place algorithm assumes its input is given in working memory, and it cannot use any other working memory than what the input initially occupies. We can consider any fixed amount of working memory to be part of the algorithm itself.

For example,

finite automata are in-place;
pushdown automata are not;
linear bounded automata are;
Turing machines are not.

A formalization of the notion can be a random-access machine with limited memory.


Optimal partition according to partition cardinality

This problem is NPC; we can use it to decide whether there exist a $k$-clique.

Each edge $(u,v)$ is transformed into a set $S_{u,v}$, we put $u$ and $v$ into $S_{u,v}$, as well as $U$ globally unique elements. Set $K=\frac{k(k-1)}{2}U+k$ and $U=n^3$. Each share of the partition can contain $\frac{k(k-1)}{2}$ edges, if they form a $k$-clique; otherwise it can contain exactly $\frac{k(k-1)}{2}-1$ edges.

We add dummy edges to make sure the total number of edges has the form $C\cdot (\frac{k(k-1)}{2}-1)+1$. If there is no $k$-clique, we need $C+1$ shares, otherwise we need at most $C$ shares.


Maximize graph with k cut edge operations

I guess this problem is NP-hard.

It is known that finding the minimum k-cut that separates k specified vertices is NP-hard (https://en.wikipedia.org/wiki/Minimum_k-cut). Therefore, given a minimum k-cut instance as well as k specified vertices, we can assign weight-1 to all the k specified vertices, and weight-0 to other vertices. Finally we apply the blackbox algorithm for your XOR problem to binary-search for the minimum k-cut size.


Reference for mixed graph acyclicity testing algorithm?

Finding mixed cycles in a mixed graph is equivalent to finding elementary directed cycles (of length >=3) in the corresponding directed graph. The corresponding directed graph is obtained from the mixed graph by replacing each undirected edge by two directed edges pointing in opposite directions. Proof: (1) Each elementary directed cycle (of length >=3) in the digraph corresponds directly to a mixed cycle in the mixed graph. (2) Each mixed cycle in the mixed graph contains an elementary mixed cycle of length >=3, and each such cycle corresponds directly an elementary directed cycle (of length >=3) in the directed graph. (1) and (2) together prove both directions of the statement, qed. So we are looking for references how to compute (all?) elementary cycles (of length >=3) in a directed graph.

The comments indicate that cs.stackexchange contains some answers to this question, but it is unclear how to organize the results into a concise answer. This blog post seems to nicely summarize the (most?) important references:

  Algorithm by R. Tarjan

  The earliest algorithm that I included was published by R. Tarjan in 1973.

Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

  Algorithm by D. B. Johnson

  The algorithm by D. B. Johnson from 1975 improves on Tarjan's algorithm by its complexity.

Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

  In the worst case, Tarjan's algorithm has a time complexity of O(n⋅e(c+1)) whereas Johnson's algorithm supposedly manages to stay in O((n+e)(c+1)) where n is the number of vertices, e is the number of edges and c is the number of cycles in the graph.

  Algorithm by K. A. Hawick and H. A. James

  The algorithm by K. A. Hawick and H. A. James from 2008 improves further on Johnson's algorithm and does away with its limitations.

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf

  In contrast to Johnson's algorithm, the algorithm by K. A. Hawick and H. A. James is able to handle graphs containing edges that start and end at the same vertex as well as multiple edges connecting the same two vertices.

The acyclicity testing itself seems to be easy: Compute the strongly connected components of the graph. Any (elementary) cycle is completely contained in a strongly connected component. A strongly connected component contains an elementary cycle iff it is not an undirected tree.

David Eppstein's proposed algorithm additionally computes one elementary cycle as evidence, and the above algorithms enumerate all elementary cycles. Any vertex or edge not contained in an elementary cycle could be deleted as a preprocessing step to improve the speed of the above algorithms. David Eppstein's algorithm could be used for that purpose, but even if only used on the strongly connected components, it won't delete every possible vertex or edge that can be deleted. But even if it could be extended to do so (computing the block-cut tree at least allows to delete every possible vertex that can be deleted), it is unclear whether this would really improve the speed of the above algorithms.


This problem is NP-hard.  As proof, the maximal clique problem (or rather the decision variant find-a-K-clique) can be reduced to this problem as follows.

Start with a problem on a graph with N vertices where we wish to find a clique of size K.  The set containing these original vertices we'll call S. Add a clique (we'll call it C) of size (N - K)*K which is joined to every vertex in S.  Additionally, adjoin one more vertex V which is joined only to the vertices in S (not the ones in C).

Now we have an instance of your problem (never mind the edge weights) where we want to divide the resulting graph up into N - K + 1 cliques of size K+1.  I claim that there is a solution to this problem if and only if there is a clique of size K in the original graph.

only-if follows from the fact that V must belong to some clique of size K+1 which is only the case if there are K vertices which form a clique in S.

Furthermore, there will be enough leftover nodes in C that every S-vertex not in the solution clique can be assigned to a separate set of K vertices from C.  So once we've managed to find a clique for V, finding the other N-K (K+1)-cliques is always possible (and indeed trivial).

So taking "efficient" to mean "polynomial time", then the answer to your question is "no", or more precisely, "only if P = NP"


There are two related complexity classes in $\text{NL}$ which are also in $\text{LogDCFL}$, which puts them in $\text{SC}^2$ (by Cook).

The first is $\text{RUL}$, for "Reach-Unambiguous Log-space" which has reachability in mangroves (graphs where every pair of vertices has at most one directed path between them) as a complete problem.  This class has been discussed before.
The second is $\text{ReachFewL}$, which has reachability complete for graphs with at most a polynomial number of paths between any pair of vertices.

Performing depth-first search on these graphs using a stack has a guarantee that it will take polynomial time, so these classes are in $\text{LogDCFL} \subseteq \text{SC}^2$.


Designing a Transport network path suggestion tool

The obvious way of doing this is via time-dependent or time-independent graphs where you run a Dijkstra on it. This is also described in the lectures I mention below.

Also you should have a close look into transfer patterns (used at google) and RAPTOR (used at microsoft). There is a nice introduction into transfer patterns at university freiburg in lectures 9-11. RAPTOR is implemented in OpenTripPlanner and later this year probably also in my GraphHopper project.

  But the complication is that the shortest route may not be the fastest route to the destination.

Of course, but why not just use the time as weight instead of the distance? So 'shortest' and 'fastest' is not really a big difference ...


How does the Multiplicative Weights Update method maximize entropy?

Here's one way to look at it, based on usul's comment.

Let the gains of each expert $i$ at time $t$ be given by $g_i^t$.

Then the expected gains of the algorithm are:

$$\sum_{u=1}^{t-1}\sum_i p_i^t g_i^u$$

We can then define the potential function

$$\Phi=\epsilon \sum_{u=1}^{t-1}\sum_i p_i^t g_i^u + \sum_i p_i^t \ln \left(\frac{1}{p_i^t}\right)$$

Where the right-hand term is the entropy and $\epsilon$ is a learning rate.

This function is maximized for

$$p_i^t = \exp\left(\epsilon \sum_{u=1}^{t-1} g_i^u-1\right)$$

We can find a similar expression that maximizes the function for $t+1$.

Taking the logarithms of these expressions and subtracting gives:

$$p_i^{t+1}=p_i^t \exp (\epsilon g_i^t)$$

Which is the MWU update rule.

Therefore, by applying this update rule we are maximizing a potential function of utility and entropy.


Is there any such thing as a non-nested hierarchy?

I think this question is more about the semantics of the english language than about cs theory. Unless this has a connection to some problem. I think generally speaking, hierarchy of things just means there is a well ordered relation of these things. And nested just means that the things are nested within each other. The relation is defined based on nesting. So the military ranks are a hierarchy, but not a nested one because the groups aren't nested within each other.


In the edge setting, the problem you're referring to is the bisection problem, and the size of such a minimum edge is called the bisection width. There's a ton of research on this problem, and the best known approximation for the problem is $O(\log n)$ by Racke.

A good review of the known work on this problem (which connects to sparsest cut, spreading metrics, and even the unique games conjecture) is in this recent paper on generalizations of bisection width by Krauthgamer, Naor and Schwartz.


Dividing a complete graph into two cliques with maximal sum of edge weights

I'm going to assume you didn't mean to end up two (maximal) cliques, but instead two disconnected complete graphs. Those are not the same, e.g. for $n = 6$ you can end up with extra edges that don't form any other maximal cliques otherwise:

If that assumption is correct, your operation is called a bisection of the graph. You want to maximize the remaining weights, and thus minimize the edge weights of the edges that are cut.

This problem is NP-complete, and you can find a reduction in "Some simplified NP-complete graph problems" by M. R. Garey, D. S. Johnson, and L. Stockmeyer in Theorem 1.3 and the preceding paragraph.


This is the geometric median problem. There is a nearly linear time algorithm based on interior point methods due to Cohen et al.: to find a $(1+\varepsilon)$-approximation their algorithm runs in time $O(nd\log^3(n/\varepsilon))$. Note that some approximation is necessary, because the optimal solution may not be rational and doesn't have to be a simple function of the input. See the paper for references to prior work.


How to go about finding the most "complex" function?

Pick one at random.

If it is random, then there is no way to compress the representation. You have to store the entire truth table.

http://en.wikipedia.org/wiki/Kolmogorov_complexity


Computational Complexity of Computer Vision Problems

Computer vision is not well defined as a theory problem, but machine learning does have a nice theoretical framework called PAC learning in which one can try to address your question.

It is open whether learning is hard, i.e. whether there exists an class that is impossible to efficiently (PAC) learn.

Some results that indicate learning is probably hard:

Some classes (e.g. automata) are cryptographically hard to learn.
Some classes (e.g. k-term DNF) are NP-hard to properly learn.

Perhaps some good news?: we're unlikely to find an NP-Hardness of learning result unless the polynomial hierarchy collapses.


[An alternative answer for $BS(f)$]

There is a paper related to this problem.

Scott Aaronson: Algorithms for Boolean Function Query Properties.
SIAM J. Comput. 32(5): 1140-1157 (2003)

The paper gives an $O(N^{\log_2 5} \log N)$ algorithm for computing $BS(f)$ if $f$ is given by
a truth table of size $N=2^n$. Thus, even if $c$ is not fixed, deciding $BS(f) > c$
is in P.


Policy Adjustment in Markov Decision Process

The set of optimal policies for one MDP may be completely different than for another MDP even if the two MPDs differ only in the rewards and/or transition probabilities.

One thing you might try in order to save resources in some cases when you change the MDP (e.g. when the set of optimal policies does not change too much) is to use policy iteration to find optimal policies and to start it for the new MDP from an optimal policy for the old MDP. Theoretically, you should bear in mind that there are exponential time examples for policy iteration that start and finish at policies that differ in only one action, but these are pathological examples that will almost certainly not arise in practice.

You may find some relevant information if you search for "sensitivity analysis" or "perturbation analysis" for MDPs.


How can you encode natural numbers operations on interaction combinators?

Contrarily to the $\lambda$-calculus, the interaction combinators have no underlying logical system (i.e., there is no Curry-Howard correspondence for them), it is therefore hard to say that a numeral system is more "natural" than another.

(In the $\lambda$-calculus, Church numerals may be claimed to be "natural" because their type is the erasure of the second order definition of natural number, i.e.

$\mathsf{Nat}(x) := \forall X.(X(0)\Rightarrow\forall y.(X(y)\Rightarrow X(Sy))\Rightarrow X(x)).$

If you erase all quantifiers and first-order terms, you get $X\to(X\to X)\to X$, which is exactly the simple type of Church integers, perhaps modulo a permutation, i.e. $(X\to X)\to X\to X$ also works. But even in the $\lambda$-calculus there are lots of other numeral systems which may be preferred to the Church integers in some cases).

Anyhow, there are at least a couple of reasons why no-one bothered to explicitly define a numeral system for the interaction combinators:

the interaction combinators are studied more as an abstract model of computation than an actual programming language in which one wants to explicitly code algorithms; more general interaction net systems, in which one defines the agents and the interaction rules arbitrarily, are much more suitable for explicit programming (as shown for instance in Lafont's very first paper on interaction nets, POPL 1990), just like a functional language with a primitive integer type and fixpoint definitions (a la PCF) is better for real-life programming than the bare $\lambda$-calculus.
if you really want to, it is fairly straightforward to find numeral systems in the interaction combinators.  It is well known (see for instance Barendregt's The Lambda Calculus book, Sect. 6.4) that in a language allowing arbitrary recursive definitions (such as the interaction combinators), Turing-completeness is ensured as soon as one is able to define zero, successor, if-then-else (with test for zero) and predecessor. It doesn't take much to find a numeral system satisfying the above. The quickest solution I came up with in 5 minutes is to mimick Scott numerals (another numeral system in the $\lambda$-calculus). Scott numerals have the advantage of being linear, so they may be encoded in multiplicative proof nets, which in turn are essentially the $\gamma\varepsilon$ fragment of the interaction combinators. This is nice because these numerals will be duplicable without problems (by $\delta$ cells). Here are the definitions:

where $\mathbf M_3$ and $\mathbf M_3^\ast$ are the multiplexor and demultiplexor of rank 3 as defined in Lafont's Interaction Combinators paper (I&C, 1995). They both consist of two $\gamma$ cells and they annihilate with each other generating 3 parallel wires.


The Equivalency of Two Definitions of Completeness & Soundness in Interactive Proof Systems

The prover is "all-powerful and possesses unlimited computational resources" so it has no need of random bits. Thus the only randomness is the randomness of the verifier.

If the prover uses random bits, it should replace them with the random bit string that is most likely to make the verifier accept (this is true for both the honest and any dishonest prover). Furthermore, the prover can determine this optimal bit string because the prover is "all-powerful".


Why is the security of lattice cryptosystems not provable from $P \neq NP$?

To expand somewhat on Sasho Nikolov's comment...

  LWE is at least as hard as finding approximate solutions to SVP, but the approximation factors for which the reduction from SVP to LWE works are larger than the approximation factors for which we know NP-hardness

...the following is a reasonably complete view of things:

This was part of Oded Regev's talk at the Winter School on Lattice-Based Cryptography and Applications, held at Bar-Ilan University, Israel, in 2012.

If you are interested in a good introduction to the very basics of lattice cryptography, I'd happily recommend checking out the full record of this winter school. You can (still-- as of Summer 2017) find a large list of slides and talk videos at:

https://cyber.biu.ac.il/event/the-2nd-biu-winter-school/


Threshold Fully Homomorphic Cryptosystems

A new paper by Steven Myers, Mona Sergi, and Abhi Shelat on eprint, "Threshold Fully Homomorphic Encryption and Secure Computation", claims a threshold fully homomorphic encryption scheme.
From their abstract:

...
Gentry [Gen09a] shows how to combine both ideas with fully homomorphic encryption in order to construct secure multi-party protocol that allows evaluation of a function $f$ using communication that is independent of the circuit description of $f$ and computation that is polynomial in $|f|$. This paper addresses the major drawback's of Gentry's approach: we eliminate the use of non-black box methods that are inherent in Naor and Nissim's compiler.
To do this we show how to modify the fully homomorphic encryption construction of van Dijk et al. [vDGHV10] to be threshold fully homomorphic encryption schemes.
...
Altogether, we construct the first black-box secure multi-party computation protocol that allows evaluation of a function $f$ using communication that is independent of the circuit description of $f$.


finding smallest k elements in array in O(k)

Preprocess the array of $n$ values in time $O(n)$:

$i\leftarrow n$
while $i>2$

Compute the median $m$ of $A[1..i]$ in time $O(i)$
partition $A[1..i]$ into $A[1..i/2-1] \leq m$ and $A[i/2+1..i]\geq m$ in the same time.
$i \leftarrow \lfloor i/2 \rfloor$

The total precomputation time is within $O(1+2+4+...+n)\subseteq O(n)$

Answer a query for the $k$ smallest elements in $A$ in time $O(k)$:

$l\leftarrow \lfloor \log_2 k \rfloor$
select the $(k-2^l)$th element $x$ of $A[2^l..2^{l+1}]$ in time $O(2^l)\subseteq O(k)$
partition $A[2^l..2^{l+1}]$ by $x$ in the same time

$A[1..k]$ contains the $k$ smallest elements.

References:

In 1999, Dor and Zwick gave an algorithm to compute the median of $n$ elements in time within $2.942 n + o(n)$ comparisons, which yields an algorithm to select the $k$th element from $n$ unordered elements in less than $6n$ comparisons.


When you say "undecidable" I assume you mean it is independent of a theory such as ZFC. There will be statements like
$$B(m)>n$$
(for natural numbers $m$, $n$) that are not decided by ZFC, assuming ZFC is consistent. Because otherwise we could compute the function $B$ just by searching for proofs in ZFC of such statements.

Since $B$ is Turing complete there is some Turing machine $\Phi$ with
Con(ZFC)$\iff$ $\Phi$ accepts with oracle $B$ (on input 0, say) and $\neg$Con(ZFC)$\iff$ $\Phi$ rejects.

Now assuming that actually Con(ZFC) is true we know $\Phi$ accepts and there is some collection of facts $B(m_i)=n_i$, $1\le i\le k$ that was used in the computation (we may set it up so that the oracle access works in this way). Then
$$\sum_{i=1}^k (B(m_i)-n_i)^2>0$$
is false, but this fact is not provable in ZFC, else ZFC would prove its own consistency.
Of course this can be rewritten as
$$\sum_{i=1}^k B(m_i)^2+n_i^2>\sum_{i=1}^k 2B(m_i)n_i\tag{*}$$
and so arguably (*) provides a Yes answer to your question.

However, I don't think we can figure out what these numbers $m_i$, $n_i$ are, because the queries are adaptive (what is asked about depends on answers to previous questions, and we don't know those answers).


What's the point of $\eta$-conversion in lambda calculus?

Update [2011-09-20]: I expanded the paragraph about $\eta$-expansion and extensionality. Thanks to Anton Salikhmetov for pointing out a good reference.

$\eta$-conversion $(\lambda x . f x) = f$ is a special case of $\beta$- conversion only in the special case when $f$ is itself an abstraction, e.g., if $f = \lambda y . y y$ then $$(\lambda x . f x) = (\lambda x . (\lambda y . y y) x) =_\beta (\lambda x . x x) =_\alpha f.$$ But what if $f$ is a variable, or an application which does not reduce to an abstraction?

In a way $\eta$-rule is like a special kind of extensionality, but we have to be a bit careful about how that is stated. We can state extensionality as:

for all $\lambda$-terms $M$ and $N$, if $M x = N x$ then $M = N$, or
for all $f, g$ if $\forall x . f x = g x$ then $f = g$.

The first one is a meta-statement about the terms of the $\lambda$-calculus. In it $x$ appears as a formal variable, i.e., it is part of the $\lambda$-calculus. It can be proved from $\beta\eta$-rules, see for example Theorem 2.1.29 in "Lambda Calculus: its Syntax and Semantics" by Barendregt (1985). It can be understood as a statement about all the definable functions, i.e., those which are denotations of $\lambda$-terms.

The second statement is how mathematicians usually understand mathematical statements. The theory of $\lambda$-calculus describes a certain kind of structures, let us call them "$\lambda$-models". A $\lambda$-model might be uncountable, so there is no guarantee that every element of it corresponds to a $\lambda$-term (just like there are more real numbers than there are expressions describing reals). Extensionality then says: if we take any two things $f$ and $g$ in a $\lambda$-model, if $f x = g x$ for all $x$ in the model, then $f = g$. Now even if the model satisfies the $\eta$-rule, it need not satisfy extensionality in this sense. (Reference needed here, and I think we need to be careful how equality is interpreted.)

There are several ways in which we can motivate $\beta$- and $\eta$-conversions. I will randomly pick the category-theoretic one, disguised as $\lambda$-calculus, and someone else can explain other reasons.

Let us consider the typed $\lambda$-calculus (because it is less confusing, but more or less the same reasoning works for the untyped $\lambda$-calculus). One of the basic laws that should holds is the exponential law $$C^{A \times B} \cong (C^B)^A.$$ (I am using notations $A \to B$ and $B^A$ interchangably, picking whichever seems to look better.) What do the isomorphisms $i : C^{A \times B} \to (C^B)^A$ and $j : (C^B)^A \to C^{A \times B}$ look like, written in $\lambda$-calculus? Presumably they would be $$i = \lambda f : C^{A \times B} . \lambda a : A . \lambda b : B . f \langle a, b \rangle$$ and $$j = \lambda g : (C^B)^A . \lambda p : A \times B . g (\pi_1 p) (\pi_2 p).$$
A short calculation with a couple of $\beta$-reductions (including the $\beta$-reductions $\pi_1 \langle a, b \rangle = a$ and $\pi_2 \langle a, b \rangle = b$ for products) tells us that, for every $g : (C^B)^A$ we have $$i (j g) = \lambda a : A . \lambda b : B . g a b.$$
Since $i$ and $j$ are inverses of each other, we expect $i (j g) = g$, but to actually prove this we need to use $\eta$-reduction twice: $$i(j g) = (\lambda a : A . \lambda b : B . g a b) =_\eta (\lambda a : A . g a) =_\eta g.$$
So this is one reason for having $\eta$-reductions. Exercise: which $\eta$-rule is needed to show that $j (i f) = f$?


Data Structure to calculate which interval a point lies in?

Since the intervals are non-overlapping, this can be done by building a 1-D summed area table of the interval values. Building the table takes $O(n)$ time; querying the table consists of two $O(\log n)$ binary searches followed by an $O(1)$ subtraction.

Note that the above solution specifically only works because the operation we want to perform on the interval values (addition) is invertible. It is also possible to design a more general data structure that has the same asymptotic performance and works on values from any monoid, using a trick similar to the parallel prefix sums algorithm.

For the initial construction, in $O(n)$ time we build a balanced binary tree, where each leaf node is labeled with an interval/value pair from the problem input, and each internal node is labeled with the union of its two child intervals and the sum of its two child values. For your example problem, the binary tree might look like this:

       [0,10]=9
      /        \
[0,2]=1        [2,10]=8
              /        \
         [2,4]=3     [4,10]=5

To query the data structure, you perform the following steps:

Use two $O(\log n)$ binary searches in the tree to find the endpoints of the smallest union of input intervals that contains the query interval. (Same as in the first solution.)
Sum the values of all of subtrees whose intervals are between these endpoints in the tree. Since we already have cached values for each subtree, only $O(\log n)$ node values need to be summed together.

For your example queries:

For the interval [0,3], we find the containing interval [0,4], then compute 1 + 3 = 4.
For the interval [0,5], we find the containing interval [0,10], then compute 9 = 9.
For the interval [5,9], we find the containing interval [4,10], then compute 5 = 5.


Boundedness of expected reward Markov chain

It is not bounded sorry for the inconvenience. Here is the proof a friend gave me (thanks a lot to him):

Let consider the set $W_1 = \{w = (s,w_1,\dots)| w_1 \leq n\}$. Then $\mathcal{E}^n_n$ is bigger than $\displaystyle\sum_{w\in W_1}O^n_n(w)*P(w)$.

\begin{align}
\sum_{w\in W_1}O^n_n(w)*P(w) &= \sum_{k=0}^n \sum_{i=0}^k {n\choose i}(1-p)^i p^{n-i}q^{k-i}(1-q) * k \\
&= (1-q) \sum_{i=0}^n \sum_{k=i}^n {n\choose i}(1-p)^i p^{n-i}q^{k-i}*k\\
&= (1-q) \sum_{i=0}^n  {n\choose i}(1-p)^i p^{n-i}\sum_{k=i}^n q^{k-i}*k\\
&\geq (1-q) \sum_{i=1}^n  {n\choose i}(1-p)^i p^{n-i}i \\
&\geq (1-q) \sum_{i=0}^{n-1} {n\choose i+1}(1-p)^{i+1} p^{n-1-i}(i+1) \\
&\geq (1-q) n (1-p) \sum_{i=0}^{n-1} {n-1 \choose i}(1-p)^i p^{n-1-i} \\
&\geq (1-q) n (1-p)
\end{align}


Each SAT clause has 1, 2, 3 or more variables. The 3 variable clause can be copied with no issue

The 1 and 2 variable clauses {a1} and {a1,a2} can be expanded to {a1,a1,a1} and {a1,a2,a1} respectively.

The clause with more than 3 variables  {a1,a2,a3,a4,a5} can be expanded to {a1,a2,s1}{!s1,a3,s2}{!s2,a4,a5} with s1 and s2 new variables whose value will depend on which variable in the original clause is true


Does there exist a data structure for quick list manipulation and order queries?

Keep your integers in skip lists. Normal skip lists are ordered by key, but we will just use them as a representation of sequences. Additionally, maintain an array of pointers of size $n$. Each element of the array should point to a node in a skip list. I believe this supports $next$ in $O(1)$ and all other operations in $O(\lg n)$.

Specifically:

$concat$ing or $split$ting two skip lists takes $O(\lg n)$ time and therefore invalidates at most $O(\lg n)$ pointers.
$next$ just follows the forward pointer at the leaf level, taking $O(1)$ time.
$first$ takes $O(\lg n)$ time: follow up pointers until you get stuck, then follow a left pointer. When you can't follow any more left pointers, you're at the head pointer of your skip list. Follow down pointers to the leaf, then one forward pointer. This is the first element in the list.
$follows$ is somewhat trickier. Proceed as in $first$ for $y$, but record a list of the values where you get stuck (that is, where you can't follow up pointers any more). We'll call this list you record a "trace". Do the same for $x$, but follow right pointers when you get stuck, not left. If $x$ precedes $y$, their traces will intersect. The traces are of size $O(\lg n)$. If each element in the trace is annotated with the stuck level, we can check for an intersection in time $O(\lg n)$.

$next$ is worst-case $O(1)$, all others are $O(\lg n)$ with high probability. They can be made worst-case by using deterministic skip lists.

I think $concat$ can be made $O(\lg \lg n)$ by using leaf-level-linked (2,5) trees and boostrapping the spines. For the bootstrapping trick, see "Purely functional representations of catenable sorted lists" by Kaplan and Tarjan.


$T_\infty$ means you have as many processor as you need (theoretically an infinite number). The strategy to assign each iteration to one processor is base on Divide and Conquer. So, at first, one processor split the number of iterations in two, spawn a new thread with the first half and recursively processes the other half. Then this two processors split each half in two chunks each. And so on until you have one iteration on each chunk, so you can compute it in $iter_\infty (i)$ time. Given that you have an infinite number of processors you can recruit twice the number of processors on each new level of this recursion, so each level can be executed in $O(1)$, but still you need to executed each level after the other. In order to have $n$ iterations (leaf on the recursion tree) you will need $O(\log n)$ levels.


Assuming a practical algorithm is found, the applications will overwhelmingly be in quantum simulation. Basically any research in large quantum systems - chemistry, biochemistry, condensed matter, nuclear systems will be affected. We'd likely see major advances in basic biology, medicine and pharmaceuticals. Moore's law would be restored for a few years and we would finally have working fusion reactors. Physical simulation using the new algorithm might also lead to new physics.


I assume you're talking about maintaining keys, in order, in an $O(N)$-sized array, with $O(\log^2 N)$ amortized worst-case update time.

  At the beginning how many chunks do I have? I suppose one.

At the beginning, you will have one chunk.  Ordered file maintenance doesn't make sense for very small arrays.  Pick a smallish number (like 64 or 1024), and only start this whole chunking method once you grow above this small number.  In the small array do something naive, pushing elements around as necessary.

  When the array is full according to the target density, do I need to grow the array and how? I suppose yes, always by a power of two (number of chunks).

Yes, you can use standard dynamic array methods, like doubling in size when it gets too large.

Some data structures like to avoid this, as a full rebuild is a really large cost.  But this isn't a big deal for us, as this data structure is highly amortized anyway.  In other words, you have to do about $\Theta(\log N)$ rebuilds of the entire data structure every $N$ insertions anyway, just to maintain balance.  This just adds an extra one.

  Is there a possibility that a tree is impossible to rearrange according to the density? I hope not.

No, so long as there aren't too many elements.  This is fairly easy to see---so long as you don't have too many elements, you can distribute the elements in the whole array evenly, meeting the density bound of the top array.  But the arrays have looser requirements as they go down.  So if the top array fits in density (and the elements are distributed evenly), the entire data structure is correctly balanced.

  Is there any source code that I can take a loot at?

Yes, here (this was a class project; beyond that I know almost nothing about that code).  The author of that code has a nice writeup of the data structure as well.  Some more recent academic work on that data structure has experimental results.  You may try looking through those as well (though of course, many are variations on the original concept).

  When $N$ changes do I need to change the chunk size accordingly? I think so.

It depends on what you mean.  Do you mean "when I insert a single element, so $N\gets N+1$, should I update the chunks?" then the answer is no.  On the other hand, if you mean "when I run out of room in the data structure, and double its size, rebuilding the entire data structure, should I update the chunks?" then the answer is yes.


Split find-min data structure that finds several small elements?

Use a forest of 2-4 trees in which the keys are at the leaves. Every internal node contains a copy of the minimum key that descends from it as well as a positive integer indicating the number of values of this key descending from it.

Additionally, maintain a van Emde Boas tree containing as keys each positive integer $i$ where $e_i$ is the left-most element in one of the 2-4 trees. In the vEB tree, each integer $i$ has satellite data: a pointer to the root of the tree the key associated with $e_i$ is in.

$Split$ is the normal split on 2-4 trees, updating the internal node data as it proceeds. This takes logarithmic time in the size of the tree being split, while updating the vEB tree takes time corresponding to the logarithm of the logarithm of the number of trees in the forest.
$FindMin$, which now returns the $l$ smallest keys, does a breadth-first search down the tree containing the element in question. Starting from the root, this takes time linear in $l$. To find the root from the element, access the vEB tree, find the predecessor, then follow the pointer to that root.
$DecreaseKey$ modifies a single 2-4 tree, taking time logarithmic in the size of that tree.

Each $Split$ uses $O(\log \log n)$ time for the vEB operation and $O(\log n)$ key comparisons. Each $FindMin$ uses $O(\log \log n)$ time for the vEB operation and $O(l)$ key comparisons. Each $DecreaseKey$ uses $O(\log n)$ key comparisons.


Does every online algorithm has an offline counterpart?

This statement seems false to be because of the notion of competitive ratio that is used to analyze virtually all online algorithms. Heuristically the competitive ratio measures how well the online algorithm performs on a sequence of inputs versus an adversary that knows the sequence in advance. In particular, the adversary is solving an offline problem.

If you look at any of the online problems that are studied, they all use the competitive ratio as a benchmark. To back up this claim, look at the abstracts of any paper in a well known journal (such as SODA 18: https://archive.siam.org/meetings/da18/da18_abstracts.pdf) and search for abstracts that study online algorithms. They all use some type of competitive ratio in their analysis.


Does Nisan's pseudo-random generator relativize?

It depends on whether in your definition of the Oracle TM, the oracle query tape is also bounded to be of logarithmic size: if it is bounded then the PRG fools also L^A for any A too, if it is not bounded then A can contain the list of "pseudorandom strings" and thus L^A will not be fooled.


Turing Machines and Subroutine Simulation

Martin Davis's book "Computability and Unsolvability" contains a very detailed account of Turing machines. In gory detail. In your particular case Corollary 2.2 on page 37 shows that composition of Turing-computable functions is again Turing-computable. This is just another way of saying that subroutines can be done.


Log Rank Conjecture Collaborative Approach

it seems researchers might be cautious/ unlikely to conjecture/ speculate solution to this problem would likely/ definitely open up other areas (eg one you list of matrix rigidity is provably nearly equivalent to the extremely hard challenge of proving nontrivial lower bounds on eg circuits etc) but it definitely provably touches many areas. here is a nice recent survey (Jan 2015) by Lovett that lists "many connections" sec 6 along with two other refs that show crosscutting connections/ formulations

Recent advances on the log-rank conjecture in
communication complexity / Lovett

6.1 Randomized protocols vs approximate rank
6.2 Quantum protocols for low-rank matrices
6.3 The structure of low-rank sparse matrices, and matrix rigidity

En Route to the log-rank Conjecture:
New Reductions and Equivalent Formulations / Gavinsky, Lovett
On the "log rank"-Conjecture in Communication Complexity / Raz, Spieker


Number of "3-edge" triangles in a planar triangulation

I think only those vertices corresponding to triangles sharing an edge with boundary or holes of the polygon will be of degree less than 3. Now the number of triangles in the triangulation is fixed. So you can always get the exact ratio of the number of degree 3 vertices for a polygon.

If the polygon has $k$ vertices and $l$ holes vertices and the number of triangles in the total triangulation is $N$
then the upper bound should be $(N-K-l)/N$.


What is the fastest known algorithm for finding conjugacy classes?

I believe this can be done on $O(n \log n)$ on a RAM, where $n=|G|$; I don't know a reference so I'll just write it down here (but surely this is not original). Nor do I know if this is the fastest known, but clearly you can't do it faster than $\Omega(n)$, so it's gotta be close.

Let's assume the group elements are denoted in the computer by the integers $1,\dotsc,n$, with $g_i \in G$ being the group element corresponding to the integer $i$. Assume WLOG that $g_1$ is the identity.

1) Find a generating set $\Gamma$ of size $\leq \log_2 n$ in $O(n \log n)$ time:

G = list of group elements
Gamma = []
Gr = new graph with vertex set G and no edges           // O(n) steps
found = new array of length n, initialized to all false // O(n) steps
for i = 2 to n: // never need to add identity to generating set
    if not found[i] then
        Gamma.append(i)
        // Now update the graph Gr by adding new edges
        // Corresponding to the new generator G[i]=g_i
        for each vertex g in Gr:
            Gr.addEdge(g,g*G[i])
        end for
        do BFS on Gr starting from 1, ignoring any vertices already found
        (for any vertex j encountered, this sets found[j]=true)
    end if
end for

2) Build the following sparse graph (that is, in the edge list representation, not the dense adjacency matrix representation): vertices are the elements of $G$, and there is an (undirected) edge $(g,h)$ if $h = \gamma g\gamma^{-1}$ for some generator $\gamma \in \Gamma$. This is a graph with $n$ vertices and maximum degree $O(\log n)$. Its connected components are the conjugacy classes, and finding them can be done by BFS (say) in time $O(v + e) = O(n + n \log n) = O(n \log n)$.


Stephen Hawking's impact on computer science

He didn't have any major impact on computer science.

His writing in computer science are limited to popsci and more recently raising public concerns about AI.


Is it possible to represent a regular expression with bounded captures using a DFA and O(1) additional processing?

I have no direct answer, but some additional remarks regarding on the topicality of my paper from this year's STACS which Raphael  mentioned in his answer. (Due to space reasons, I opted for a new answer, instead of a comment.)

As far as I understand the question, the classes of regular expressions with $\leq k$ captures corresponded to the classes RegEx(k) of extended regular expressions with at most $k$ variables in my paper. Among the results in the paper, the ones that are probably most relevant to the question are that, even with one variable (the class RegEx(1)),

1) there is no effective way of converting expressions from RegEx(1) to "proper" regular expressions, even if the problem is restricted to those expressions that describe regular languages,

2) even if one is able to convert these expressions with one variable to proper regular expressions (or any other description mechanism for the class of regular languages), the resulting blowup in size is not bounded by any computable function,

3) given an expression $\alpha\in RegEx(1)$, universality (the question whether $L(\alpha)=\Sigma^*$) is not decidable.

This does not directly answer the question, but imposes some limits on possible conversion procedures. For example, if the universality problem for the class of resulting DFAs with extra storage is decidable, such a conversion procedure cannot exist. (On the other hand, although the automata model that is described in the question appears to be underspecified regarding the storage and storage operations, I am under the impression that this problem should be undecidable for the resulting class of automata.)

Among the few papers that deal with regular expressions with variables/backreferences/captures, I know of only two other works that consider something in the direction of limiting the number of variables: Aho's chapter on string matching in the Handbook of TCS (Vol. A), which contains a sketch of a proof that extended regular expressions with at most $k$ backreferences can be matched in time $O(n^{2k})$, and the paper by Reidenbach and Schmid from CIAA 2010, which gives a polynomial time matching algorithm for a larger class of extended regular expressions.


Finding all solutions by Grover search(not superposition)

First note that the sum $O\left(\sqrt{\frac{N}{t}}+\sqrt{\frac{N-1}{t-1}}+\dots+\sqrt{\frac{N-t+1}{1}}\right) = O(\sqrt{Nt})$.

The quantum query complexity of this problem is indeed $\Theta(\sqrt{Nt})$.

The lower bound can be shown by reduction from the problem of deciding whether the input has $t$ marked elements or $t+1$ marked elements. This problem is very similar to $t$-threshold, and has a lower bound of $\Omega(\sqrt{Nt})$. This can be shown using the polynomial method or the adversary method.


Interesting real life problem similar to subsetsum /bin packing problem

Your problem is at least as hard as bin-packing.  In particular, optimizing objective (a) basically is the bin-packing problem (in particular, bin packing is the special case where all drums have equal length, so your problem is at least as hard as bin packing), which is known to be NP-complete.  Consequently, your problem is NP-hard, too.  All the usual hardness results about bin packing apply to your problem as well: there is no polynomial-time approximation scheme (unless P=NP); and bin packing is known to be strongly NP-complete, so there is no hope for a pseudo-polynomial time solution, either.

If you want a pragmatic approach to solve this in practice, or at least get as good a solution as possible, I would recommend formulating it as an instance of integer linear programming (ILP) and applying an off-the-shelf ILP solver.  In particular, you can formulate the problem of minimizing objective (a) as an ILP instance, in the same way as for bin-packing.  Then, off-the-shelf ILP solvers might be effective: even if they don't find the optimal solution, they typically have a way to output the best solution found after a certain amount of computation time, and that might be pretty close to optimal.  Of course, it is not a silver bullet; in the worst case it might take exponential time.  There's no way to know in advance whether it will work well enough.  The only way to tell is to try it and see.

Objective (b) amounts to maximizing a sum-of-squares objective function (per your comment).  This can't be expressed using integer linear programming, but it can be expressed as an instance of quadratic integer linear programming.  You could try formulating it as an instance of mixed-integer quadratic programming (MIQP) and then applying an off-the-shelf MIQP solver.  However, MIQP is substantially harder than ILP, so I don't know whether it will work well on problem instances of the size you have.


Dave Clarke's answer basically says it all: this is the standard convention in classical and constructive mathematics.  Nonetheless, your objection is the source of a century-old subdiscipline of philosophical logic called "relevance logic", which can be seen as rejecting the axiom p → (q → p) -- or in terms of natural deduction, rejecting precisely this ability to use a hypothesis zero times, or equivalently in terms of sequent calculus, rejecting the structural rule of weakening. Reconsidering other structural rules/axioms leads more generally to substructural logics, which have found applications in linguistics and theoretical computer science.  (One important example, linear logic, is mentioned in the appendix to Proofs and Types.)


Take an arbitrary element $e \in \Omega$. If $f(e) = f_{\Omega-e}(e)$ then $e$ is not affected by the rest of the elements so we can choose $X_1 = \{e\}$ and $X_2 = \Omega-\{e\}$. Otherwise let $X$ be an inclusion-wise minimal subset of $\Omega-e$ such that $f(e) > f_X(e)$. Then $X \cup \{e\}$ should be in the same partition. If $X \cup \{e\} = \Omega$ we conclude that there is no desired partition, otherwise we shrink this set into a single element and recurse.


Why does not the definition of NP problems care about the complexity of guessing?

According to that, a problem is in NP if one can guess a certificate of polynomial size in polynomial time.

No, there is nothing about guessing in the actual definition. It is required that a certificate exist if the answer is "yes" (and doesn't exist if the answer is "no") and that verification of a proposed certificate takes polynomial time. The definition specifically doesn't require that there is any way to obtain the certificate if one exists, so we sometimes talk about "guessing" it. But it could equally be replaced e.g. by "if an alien gives you a string and claims it's a certificate for an instance, you can verify this in polynomial time". In any case, neither "guessing" nor "being given by an alien" have any complexity we could talk about.

In fact, for any $NP$ problem there are algorithms allowing to find a certificate for any instance (if one exists, i.e. if the answer is positive). But if this algorithm is polynomial, then the problem is actually in $P$, and for $NP$-complete problems only exponential algorithms are known.

  which have infinitely many certificates (even thought still in polynomial sizes) than ones that have only few

For any $n$ and for any polynomial of $n$ there is a finite number of strings of that length. Even if all of them are certificates (such as in the proof that $P$ is a subset of $NP$), you can't have an infinite number of certificates.


What are the consequences of $P \subseteq L/poly$?

One simple consequence is $\mathbf{P}/\text{poly} = \mathbf{L}/\text{poly}$. Proof: For any language $A \in \mathbf{P}/\text{poly}$, there is a language $B \in \mathbf{P}$ and a sequence of polynomial-length advice strings $y_1, y_2, y_3, \dots$ such that $x \in A \iff (x, y_{|x|}) \in B$. By assumption, there is a language $C \in \mathbf{L}$ and a sequence of polynomial-length advice strings $z_1, z_2, z_3, \dots$ such that $(x, y) \in B \iff (x, y, z_{|(x, y)|}) \in C$. This implies $A \in \mathbf{L}/\text{poly}$; the advice string for $x$ is $(y_{|x|}, z_{|(x, y_{|x|})|})$.

(A concise version of the proof: $\mathbf{P} \subseteq \mathbf{L}/\text{poly} \implies \mathbf{P}/\text{poly} \subseteq (\mathbf{L}/\text{poly})/\text{poly} = \mathbf{L}/\text{poly}$.)


The actual field you seem to be talking about is formal methods, and in particular, formal semantics of programming languages. The particular programming language you have (the machine language of the processor) seems to be without recursion and with some global state involved. This kind of effectful semantics has been well investigated in various forms and approaches.

The fields involved have developed so much that a full overview is out of the question. Also, these not only contain results, but tools employed to attack the difficulties inherent in establishing eqivalences. I will try to mentionsome keywords and topics.

One famous approach is that of axiomatic semantics. In this approach one interleaves the program with formulae from a prespecified logic, used to reason about the language. For example, in your case this logic might encode statements about the state of the processor's registers: $\exists n: r_1 =n \wedge r_2 >n^2+n-5$. These combine to form a logic (rigorous reasoning system), where statements have the form $\{\phi\}C\{\psi\}$. $\phi$ is a formula in this logic representing a precondition known about the state of the world prior to the execution of the program phrase $C$. $\psi$ is a formula representing the postcondition, guaranteed to be valid in state of the world (under the assumption that the precondition held).

The semantics is then given axiomatically as a collection of pre/post-conditions and inference rules. For instance, the semantics of register addition may look like this:
$\{r_1 = n \wedge r_2 = m\} {\rm addi\ r3,r1,r2}\{r_3=m+n\}$. The inference rules may include rules for using intermediate formulae to compose smaller phrases into larger ones.

So in your case, you will need to show that for all preconditions and postconditions, the statement $\{\phi\}B_1\{\psi\}$ is valid iff $\{\phi\}B_2\{\psi\}$ is valid. There are several such systems, applied academically and industrially. The keywords are Hoare logic, separation logic, invariants.

Another approach is operational semantics. In this approach the meaning is given by an implementation of the language. It is desirable to give an abstract implementation, so that rigorous reasoning is possible. Nowadays it is also reasonable to expect this semantics to be structural: the operation of the machine is directed by the structure of the languages syntax, and the meaning of a composite program is given by the meaning of its components.

The implementation is commonly given as a transition system, where each state is a configuration containing the current program phrase that awaits execution. Some keywords and tools that are useful for your problem: structural operational semantics, structural induction, small-step and big-step semantics, observational equivalence, contextual equivalence.

A third approach is denotational semantics. In this, the meaning of a program phrase is given by a mathematical function of its components. This semantics tends to give a global understanding of the mathematical  structure of the semantics. As a consequence, their presentation is a lot less elementary, and tend to lag behind the other approaches. On the other hand, this global understanding may give rise to deep insights about the behaviour and structure of the language. Some keywords: domain theory, category theory, monads, call-by-push-value.

The bottom line is that program equivalence has been investigated quite a lot.  It is one of the most fundamental questions in semantics. In your case, determining algorithmically and tractably whether two such computations are equivalent will probably involve tools from model checking.  Indeed, if you have $n$ registers of $k$ bits then the state-space has at least $n2^k$ points. An exhaustive search of this space is then $\Omega(n2^km)$ where $k$ is the length of the program. Of course, it might even be much worse than this.  So I guess you'll need to employ some non-trivial reasoning to establish such equivalences. Some keywords: the state-space explosion, abstract and symbolic interpretation, normalization by evaluation.

Some places to start looking at things. The Handbook of Theoretical Computer Science (Volume B) has some chapters covering various topics in semantics (Chapters 7, 9, 11, 12, 15 and 19). By now these topics are taught to undergraduates in various universities, they usually concentrate on operational and axiomatic semantics (as they are more elementary).  There is a related question about that here at TCS@SE.

I'm sorry for speaking in such broad terms, but the body of knowledge and tools underlying this problem is quite extensive. I hope that I at least given you somewhere to start looking!

It is a pet peeve of mine that the formal semantics community, who explores these  questions inherent to compiler theory, have drifted apart from the compiler community. This is not entirely the semantics' community fault: first, as usual in TCS, a big body of theory needs to be developed before a substantial application is possible. Also, Moore's law and other advances in computer science allowed compiler writers to concentrate on other problems, and dismiss formal semantics as abstract nonsense. Another observation I heard from Paul Levy is that people from outside the community take interest because of the usefulness of the problems, and then become so fascinated with the theory that they join the community.

Finally, i'll mention that the gap is closing. There are researchers around the world from both communities that take interest in each other and in closing the gap. A few local names in the semantics world: Nick Benton, Gordon Plotkin, Peter Sewell.


Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.


For a really thorough listing of various distances, metric or not, that are in use, I recommend Encyclopedia of Distances by Deza and Deza. (It is also available electronically from Springer.) For a really simple example of a family of non-metric distances, you can simply let $p$ be less than 1 for an $L_p$ distance, for example. For a family that is in heavy, actual use, you could look into various forms of weighted edit distance. There's also the cosine measure, Jeffrey divergence, partial Hausdorff distance, dynamic time warping distance, and domain-dependent distances such as the COSIMIR model, all discussed in Skopal's paper on indexing non-metric distances.


Can concurrency models be compared in terms of some metrics?

There are no metrics, but an excellent discussion of many concurrency models, in Tony Garnock-Jones PhD thesis. See the (HTML version of the) chapter "Approaches to coordination". This studies concurrency models with a particular focus, namely how information is exchanged for coordination.


The significance of NP-Hard Problems in Cryptography

Hardness of NP-complete problems is not sufficient for cryptography.  Even if NP-complete problems are hard in the worst-case (P≠NP ), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using the $P \ne NP$ assumption is a major open problem.

An excellent read is the classic by Russell Impagliazzo, A Personal View of Average-Case Complexity, 1995.

An excellent survey is Average-Case Complexity by Bogdanov and Trevisan, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 (2006) 1–106


Here are some references, not a self-contained answer to the question.  For self-contained answers, see other people’s answers and comments.

Assuming that symbol ℕ in the question denotes the set of nonnegative integers, your problem is called the feasibility version of the change-making problem.  Chapter 5 of Martello and Toth [MT90] states that it is NP-complete, attributing the result to Lueker [Lue75].  I have not checked the report [Lue75].

Even if symbol ℕ in the question denotes the set of positive integers, the problem is still NP-complete because the nonnegative version can be easily reduced to the positive version.

References

[Lue75] G. S. Lueker.  Two NP-complete problems in nonnegative integer programming.  Report No. 178, Computer Science Laboratory, Princeton University, 1975.

[MT90] Silvano Martello and Paolo Toth.  Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990.  http://www.or.deis.unibo.it/knapsack.html


Is counting maximal cliques in an incomparability graph #P-complete?

According to this abstract for "The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected" (SIAM J. Comput. 12 (1983), pp. 777-788), counting anti-chains in a partial order is #P-complete. I don't have access to this paper so I can't tell if this result covers maximal anti-chains or not.


High probable polynomial time algorithm for NP-hard problems?

Fernandez de la Vega and Karpinski in their paper 9/8-approximation algorithm for
random max-3sat give, as the title suggests, such an algorithm under the uniform distribution over 3sat clauses. Håstad showed that no deterministic 7/8 approximation algorithms exists for max-3sat (unless ...)

I don't know of any clear-cut decision problems, i.e. ones where the algorithm beats an inapproximability result for an optimization problem.


Known sparse integer programming problems

Probably, this is not an intended answer.  The sparsity constraint can be naturally represented in integer programming.

(1) For the binary integer programming (the variables take only values 0 and 1), an extra constraint that "the sum of variables is at most $k$" leads to a solution with at most $k$ non-zeros.

(2) If your problem is not binary and each variable takes the value in $\{0,\ldots,M\}$, then for each variable $x_i$ we introduce another 0/1 variable $y_i$, and give an extra constraint as $y_i \leq x_i \leq M y_i$. This means that $y_i=0$ if and only if $x_i=0$, so the sparsity can be described by means of $y$. Namely, we introduce the sparsity constraint $\sum y_i \leq k$ as (1) above.

I'm imagining you're to look at an analogue of linear programming (or convex programming) with sparsity constraint to integer programming. However, linear programming with sparsity constraint is no longer linear programming, while integer programming with sparsity constraint is still integer programming (as described above). Their natures are totally different.

Or, if you need some "interesting" examples, I would say "any combinatorial optimization problem with cardinality constraint".  That's almost equivalent to a binary integer programming with the constraint that the sum of variables is at most a certain number.


Is there a better than linear lower bound for factoring and discrete log?

@Suresh: following your advice, here is my "answer". The status of circuit lower bounds is quite depressing. Here are the "current records":

  $4n-4$ for circuits over $\{\land,\lor,\neg\}$, and $7n-7$
for circuits over $\{\land,\neg\}$ and $\{\lor,\neg\}$
  computing $\oplus_n(x)=x_1\oplus x_2\oplus\cdots\oplus x_n$;
Redkin (1973). These bounds are tight.

 $5n-o(n)$ for circuits over the basis with all
  fanin-2 gates, except the parity and its negation; Iwama and
  Morizumi (2002).

  $3n-o(n)$ for general circuits over the basis
  with all fanin-2 gates; Blum (1984). Arist Kojevnikov and Sasha Kulikov from Petersburg have found a simpler proof of a
$(7/3)n-o(1)$ lower bound. The advantage of their proof is its simplicity, not numerical. Later they gave a simple proof of $3n-o(1)$ lower bound for general circuits (all fanin-2 gates are allowed). Albeit for very complicated functions - affine dispersers. Papers are online  here.

 $n^{3-o(1)}$ for formulas over
  $\{\land,\lor,\neg\}$; Hastad (1998).

  $\Omega(n^2/\log n)$ for general fanin-$2$ formulas,
$\Omega(n^2/\log^2 n)$ for deterministic branching programs, and
$\Omega(n^{3/2}/\log n)$ for nondeterministic branching programs;
Nechiporuk~(1966).

So, your question "Specifically do any of these problems have more than a linear complexity lower bound?" remains widely open (in the case of circuits). My appeal to all young researchers: go forward, these "barriers" are not unbreakable! But try to think in a "non-natural way", in the sense of Razborov and Rudich.


R. Impagliazzo ; G. Tardos shown that there exists  an oracle  relative to which
$\textbf{E} = \textbf{NE}$ , yet there is an exponential-type search problem
that requires doubly exponential randomized time.

The similar situation with collapsing of exponential hierarchy.


Reducing redundant edges from a dependency graph

The Transitive Reduction of a Directed Graph
A. V. Aho, M. R. Garey, and J. D. Ullman

According to wikipedia, this algorithm is used by tred which is tool for transitive reduction available in GraphViz package. You can run it on your graph and get reduced graph.

This question is duplicate of this stackoverflow question.

code here graphviz/tools/src/tred.c does use DFS. ;-)


$\mathsf{P}^\mathsf{BPP}$ vs $\mathsf{BPP}$ (Are they known to be equal)

Yes, since BPP is low, but this is not a research level question.


Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$

Here's a step in the right direction...

I'll argue that for $p=1/2$,
you have $1/2 - I_n(1/2) = \Omega(\sqrt{1/2^n})$.

(This is not quite as strong as it should be.
Maybe someone can strengthen the argument to show $\Omega(\sqrt{n/2^n})$.)
Here's a proof sketch.

It suffices to show $1/2 - E_f[\min(\text{Inf}_1[f],\text{Inf}_2[f])] = \Omega(\sqrt{1/2^n})$. We do that.

Note that if $\text{Inf}_1[f]$ and $\text{Inf}_2[f]$ were completely independent, we'd be done because the expectation of the minimum of the two independent sums is $1/2-\Omega(\sqrt{1/2^n})$.  First, we'll argue carefully that the two sums are almost independent.

Consider the universe of points $X=\{-1,1\}^n$.  Call $x$ and $x'$ in $X$ $i$-neighbors if they differ in just the $i$th coordinate.  Say the two neighbors contribute (to $\text{Inf}_i[f]$) if $f(x) \ne f(x')$.  (So $\text{Inf}_i[f]$ is the number of contributing $i$-neighbors, divided by $2^{n-1}$.) Note that, if $x$ and $x'$ are $i$-neighbors, and $y$ and $y'$ are $i$-neighbors, then either $\{x,x'\}=\{y,y'\}$ or $\{x,x'\}\cap\{y,y'\}=\emptyset$.  Hence, the number of contributing $i$-neighbors is the sum of $2^{n-1}$ independent random variables, each with expectation $1/2$.

Partition the universe $X$ into $2^{n-2}$ groups of size four, where $x$ and $x'$ are in the same group iff $x$ and $x'$ agree on all but their first two coordinates. Then for each pair $(x,x')$ of 1-neighbors, and each pair $(x,x')$ of 2-neighbors, $x$ and $x'$ are in the same group.  For a given group $g$ and $i\in\{1,2\}$, let r.v. $c^g_i$ be the number of contributing $i$-neighbors in $g$. Then, for example, the number of contributing 1-neighbors overall is $\sum_g c^g_1$, a sum of $2^{n-2}$ independent random variables, each in $\{0,1,2\}$.

Note that $c^g_1$ and $c^{g'}_2$ are independent if $g\ne g'$. By a case analysis, if $g=g'$, the joint distribution of $c^g_1$ and $c^g_2$ is
$$\begin{array}{c|ccc}
 & 0 & 1 & 2 \\ \hline
0 & 1/8 & 0 & 1/8 \\
1 & 0 & 1/2 & 0 \\
2 & 1/8 & 0 & 1/8 \\
\end{array}$$

Let r.v. $N=\{ g : c^g_1=c^g_2=1\}$ denote the set of neutral groups. (They contribute exactly their expected amount to the 1-influence and the 2-influence.) The number of contributing 1-neighbors is then
$$|N| + \sum_{g\in \overline{N}} c^g_1.$$

Conditioned on $N$, for each $g\in \overline N$ r.v.'s $c^g_1$ and $c^g_2$ are independent (by inspection of their joint distribution above), so (conditioned on $N$) all r.v.'s $\{c^g_i : i\in\{1,2\}, g\in\overline N\}$ are i.i.d. uniformly over $\{0,2\}$ so,
$$\textstyle E\Big[|\overline N|- \min\big(\sum_{g\in \overline N} c^g_1, \sum_{g\in \overline N} c^g_2\big) ~\Big|~ N\Big] \ge \Theta(\sqrt{|\overline N|}).$$

Finally, note that each group is neutral with probability 1/2, so $\Pr[|\overline N| \le 2^{n-2}/3]$ is extremely small, say $\exp(-\Omega(2^n))$ (and even in that case the left-hand-side above is at least $-2^n$). From this the claimed lower bound follows...


How to exploit knowledge of the sampling distribution for better generalization bounds?

For specific distribution over $X$ uniform convergence bounds scale linearly with the logarithm of the size of the (smallest) $\epsilon$-cover of the concept class $C$ (the cover can use any functions over $X$). This is proved in "Learnability with respect to fixed distributions" paper of Benedek and Itai. As a result sample complexity of PAC learning scales linearly with this parameter.


You are exactly right. The relativization operation $B\mapsto B^A$ is not well defined.
P and PA are independently defined objects. The names are suggestive, but you cannot formally define PA from the set P. (You can define P from PA by setting A to be the empty set.)

Think of PA as being some kind of generalization of P, which equals P when A is empty, but otherwise may be different. Now if you only know the set P, it is not clear how to generalize this to get PA. As an analogy, if I asked you to generalize the real numbers, it's not clear what generalization I'm looking for. Am I thinking of fields, rings, vector spaces, etc.? The reason this happens is that while P is merely a set of languages, PA is defined in terms of a machine. This machine has the property that when A is empty it decides exactly the same languages as P. You could come up with some other machine, let's call it QA, which also has the property that when A is empty decides the same languages as P. This does not mean that PA = QA for all A. This would be analogous to asserting that if f(0)=g(0), then f and g are the same function.

Perhaps this post by Terence Tao will be helpful.


What are some good resources for strengthening my theoretical foundation for machine learning?

I suggest
Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal. Probability is at the foundation of machine learning and it's one of the weakest points for many beginners, in my experience.


Effect of protocol ordering on multiparty comm. complexity

Any protocol $\pi$ can be modified into an equivalent protocol $\hat\pi$ that has the special "round-robin" communication pattern. The modification is as follows: Whenever party $i$ generates an output in $\pi$, it holds it in a buffer until party $i-1$ has spoken. After party $i-1$ speaks, party $i$ either releases its buffer or broadcasts a "dummy" (or empty) message if there is nothing in the buffer.

The conversion of $\pi$ into $\hat\pi$ is without loss of generality, with respect to the correctness and security properties of the protocol. Whether it incurs a loss of generality with respect to communication complexity depends on whether the model allows "empty" messages. You should see whether the proof technique in this paper assumes that parties can broadcast only non-empty messages. If empty messages are allowed, then $\hat\pi$ has the same communication complexity as $\pi$.


Dependent C-style types with subtyping rule

I think the best setup here is Liquid Types, but compared to the original Liquid Types paper, you would want a much weaker language of constraints. Also, if you don't need type inference, it's even easier.

You'd still have to solve linear programs, though. Consider this function:

{int | (< 30) /\ (>= 10)} foo({int | (> 20)} bar, {int | (<= 70)} baz) {...}

and you do some arithmetic on bar and baz inside the function. Then, to type check the function, you'd have to make sure that this expression takes a value between 10 and 29, which means you'd still need to solve linear programming (treating all non-constant multiplication as atoms), which is NP-complete. However, it is known that linear programming can be polynomial if you fix the number of variables involved. What implications do this fact have on our system? I don't really know as I'm not an expert in this area.

But I suspect what you really want is some sort of symbolic execution or abstract interpretation. If your language is completely first-order and doesn't have pointers, both should be pretty easy, and would involve far less human work (i.e. type annotations).


The Relation between Babbage and von Neumann

In their 2003 paper Lovelace & Babbage and the Creation of the 1843 ‘Notes', John Fuegi and Jo Francis quote H.J. Gray’s Digital Computer Engineering, Prentice-Hall, 1963, in the annoted bibliography given by B. Randell, ed., The Origins of Digital Computers: Selected Papers, Springer Verlag, 1973, p. 420, as saying:

  “John von Neumann urged that all the machine units be connected ... so
  that the machine could be used as a computer of the Babbage type ...
  This was done and ENIAC was operated in this fashion until it
  retired.”


Computing the DAG of a program given source code or AST

I assume you're looking for ways to compute the Control Flow Graph of a given program.

This graph depends (obviously) on the actual operational semantics of the language you are interested in, and so cannot be computed from the AST alone, in the sense that some knowledge of the language semantics themselves are needed.

For a given language it is possible to build the CFG given the AST of the parsed program, and indeed this is usually a very important step in compilers to perform flow analysis. This can be found in chapter 17 of Appel or in chapter 7 of Muchnick.


What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$

As already pointed out by Emil Jeřábek in the comments, this is Hilbert's Tenth Problem over the rationals, whose computability is a notorious open question.
In this case, note that the Boolean formula $f$ is satisfiable iff $t(f)$ has an integer zero: a satisfying assignment, when treated as 0s and 1s, gives an integer zero, and conversely, given an integer zero $\vec{\alpha}$, taking it mod 2 gives a satisfying Boolean assignment (this follows from the form of the translation $t(\bullet)$). Now, given a rational solution to $t(f)=0$, if all of the denominators involved are odd, then we may still take it mod 2 to get a Boolean solution, so we have

  Boolean solution iff integer solution iff rational solution w/ odd denominators

Therefore, deciding the existence of integer roots or of rational roots with odd denominators for polynomials of the form $t(f)$ is $\mathsf{NP}$-complete.

This leaves us with the question of how hard it is to decide existence of a rational root of $t(f)$ in general (that is, without restriction on the denominators). I do not know anything more about this question than about Hilbert's Tenth Problem over $\mathbb{Q}$ (addressed in Q1).


You are asking about Dinur's proof of the PCP Theorem. The alphabet reduction step does use a PCP, but the PCP has very different parameters from the one you construct, and you don't necessarily have to use recursion to construct it. In particular, in Dinur's proof, because this inner PCP for the alphabet reduction is applied on constant sized input, we don't care if it has huge (say exponential or even more than that) blowup, which makes it comparatively easy to give a direct construction of a good enough PCP.

The entire proof including this stage is described in several places (see answer to this question), and so you may find a different description that you like better. In particular, in my complexity textbook with Sanjeev Arora this is covered in Chapters 11 and 22, we offer there two alternative ways to achieve the alphabet reduction step. One is using Hadamard-based PCP in the main text. But maybe the simplest self contained variant of it is the construction worked out in   Exercise 22.5. We also have a table, in Section 22.2.1, that shows exactly what very step of the proof does to the alphabet size (and other parameters such as soundness error, size and number of queries) and that may allay your concern.


This is publicity of my own work, but crossing number and 1-planarity are trivially solvable in planar graphs but hard for graphs of genus one. See http://arxiv.org/abs/1203.5944


Expected Kolmogorov complexity under Kolmogorov complexity distribution

If $\alpha$ is the answer to the 1st question then $\alpha=\infty$. Namely, for any  $c $  there is an $n $ such that all strings $w $ of length at least $n $ have $K (w) \ge c$. In particular the expectation of $K (w) $ with respect to any distribution on strings of length $n $ is  $\ge c $.

Similarly if $\beta$ is the answer to the 2nd question then $0\le\beta\le 1$, since
$$
(\exists c)(\forall w)(K(w)\le |w|+2\log |w| + c),
$$
but I don't know exactly what $\beta$ is.


Approximation algorithms for the maximum $2$-independence set problem

An $O(\sqrt n)$-approximation greedy algorithm for this problem is presented in the paper "Independent sets with domination constraints" by Magnús M. Halldórsson, Jan Kratochvı́l, Jan Arne Tellec (Discrete Applied Mathematics, Vol. 99, Issues 1–3, Pages 39–54). The algorithm is greedy: it consequently selects to the output solution a vertex with minimum degree, such that the output solution is still $2$-independent. Thus, the lower and the upper bounds for this problem coincide.


Fast deletion / contraction in combinatorial embedding

This question is incomplete without specifying what information about the graph as it changes you want your dynamic graph data structure to output or support queries for. But the following paper is likely relevant, even though it is described in a more general setting of combinatorial embeddings in arbitrary genus rather than just planar. It definitely supports both contractions and deletions, as well as their reverse operations, in logarithmic time per operation.

Dynamic generators of topologically embedded graphs.
D. Eppstein.
arXiv:cs.DS/0207082.
SODA 2003, pp. 599-608.

As for the second question: I don't see how to handle multiple adjacencies in general, but it's easy to get rid of bigons (multiple edges with nothing between them) as they can only come from the two faces that are on either side of a contracted edge or from the face that surrounds a deleted edge. That should be sufficient for many purposes since getting rid of the bigons ensures that the remaining graph has a number of edges proportional to its number of vertices.


The main credit should go to John Fearnley!

Here is a PSPACE-complete problem given in (John Fearnley, Marcin Jurdzinski: Reachability in Two-Clock Timed Automata Is PSPACE-Complete. ICALP (2) 2013: 212-223):

\begin{equation}
 \mathtt{SUBSETSUM\mbox{-}GAME}=\{ S~ \forall(a_1 , b_1) \exists(e_1,f_1) \cdots \forall(a_n , b_n) \exists(e_n,f_n)  \},
\end{equation}
where

$S$ and each $ a_i,b_i,e_i $, and $f_i$ are natural numbers ($1 \leq i \leq n$); and,
for every $ x=(x_1,\ldots,x_n) \in \times_{i=1}^n  \{ a_i,b_i \} $, there exists a $ y=(y_1,\ldots,y_n) \in \times_{i=1}^n  \{ e_i,f_i \} $ such that $ S = \sum_{i=1}^n = x_i+y_i $.

Similarly, we can define some complete problems for each level of polynomial hierarchy (PH). But, of course, in case of being complete at some level of PH, we need to release the condition of having only two natural numbers after each quantifier.