As for the first question, that is what a reduction does.  For how to reduce #3SAT to #Monotone-2SAT, see the proof of #P-completeness of #Monotone-2SAT [Val79b], which is based on the #P-completeness of Permanent [Val79a].  To reduce #SAT to #3SAT, Cook’s reduction from any problem in NP to 3SAT is parsimonious and therefore reduces #SAT to #3SAT.

The answer to the second question is no.  The reduction in [Val79a] from #3SAT to Permanent does not preserve the number of solutions.  Moreover, if a reduction from #SAT to #Monotone-2SAT (or Permanent) which preserves the number of solutions were known, the same reduction would reduce the decision version of SAT to the decision version of Monotone-2SAT (or Bipartite Matching), implying P=NP.

References

[Val79a] Leslie G. Valiant.  The complexity of computing the permanent.  Theoretical Computer Science, 8(2):189–201, 1979.  http://dx.doi.org/10.1016/0304-3975(79)90044-6

[Val79b] Leslie G. Valiant.  The complexity of enumeration and reliability problems.  SIAM Journal on Computing, 8(3):410–421, Aug. 1979.  http://dx.doi.org/10.1137/0208032


Figuring EasyVer problems - problems whose witness can be verified in time independent on the instance size

If I get it right, you are interested in those parameterized problems that can be verified by a bounded-time NTM (running in time $f(k)$ for some function of the parameter). Up to fpt-reduction, these are precisely the problems in the class $W[1]$, see "On the parameterized complexity of short computation and factorization" by Cai, Chen, Downey and Fellows.


Adversarial Machine Learning, Learning with (Malicious) noise

In the proof of the positive result in [2] you are referring to, namely Theorem 2, the argument goes as follows. For every possible concept $L_i$ of the hypothesis class $\mathcal{H} = \{L_1,\dots, L_N\}$, let $p_i$ to be the distance (probability of disagreement) with the true concept $L^\ast$. Then, under a classification noise $\eta$, we have that the probability $p_i$ that a labeled example $\langle x,y\rangle$ disagrees with $L^\ast$ is exactly
$$
p_i =  d_i(1-\eta) + (1-d_i)\eta = \eta+d_i(1-2\eta) \tag{$\dagger$}
$$
where $d_i = \Pr[x\in L_i\triangle L^\ast]$ is the probability to hit the region where $L_i$ and $L^\ast$ disagree. In particular, for any "bad" concept $L_i$ which is $\varepsilon$-far from $L^\ast$, we have $p_i \geq \eta+\varepsilon(1-2\eta)$, while for $L_i=L^\ast$ we have $p_i = \eta$. The argument then goes by applying concentration bounds and a union bound over the (at most $N$) bad concepts to see how many examples are enough to ensure that, w.h.p., choosing the concept consistent with the maximum number of examples taken rules out all bad concepts. (In particular, the "gap" on expectation for $m$ examples between a bad concept and the true concept is at least $\varepsilon(1-2\eta)m$ by the above.)

Now, what changes under malicious noise? (Or, even, under the milder assumption that the adversary can, with probability $\eta$, decide to flip or not the label of a sample, instead of flipping it automatically as in the classification noise) Put it simply, $(\dagger)$ is no longer true.

For instance, the adversary could focus on a specific bad ($\varepsilon$-far) hypothesis, say $L_{i^\ast}$, and decide to only flip the label of a given example $x$ if that example falls into the region of disagreement $L_{i^\ast}\triangle L^\ast$ (and not if it doesn't). In that case, one gets
$$
p_{i^\ast} = d_{i^\ast}(1-\eta) + (1-d_i)\cdot 0 = d_{i^\ast}(1-\eta) \geq \varepsilon(1-\eta)
$$
instead of the previous expression. That is a huge drag for the analysis, and essentially kills it: now, in this possible scenario (which may not happen, but is a valid scenario) to have any hope of separating $L^\ast$ from this bad concept $L_{i^\ast}$ by looking at the disagreements, we need to separate the expected $\eta m$ (for $L^\ast$) from the expected $\varepsilon(1-\eta) m$ (for the bad concept $L_{i^\ast}$)... and to have any hope of doing so, we need
$$
\varepsilon(1-\eta) > \eta
$$
or equivalently $\eta < \frac{\varepsilon}{1+\varepsilon}$.

Note that this is by no means a formal proof of the negative result of [1], more a hand-wavy way to see that things are consistent.


Does the simply typed lambda calculus have general iteration?

Assuming the given type and standard definition of Church numerals this indeed seems possible if we assume the existence of computable bijective mapping between instances of given types.

Note that the main issue is the type mismatch of $\mathsf{it}_\sigma$ and $\mathsf{N}$, otherwise $\mathsf{it}_\sigma$ could be equal to the identity function. One way of solving this issue is to have a way of uniquely converting between the types $\sigma$ and $0$. More specifically, if we have a way of encoding instances of type $\sigma$ into $0$ (which should encode natural numbers, thus have infinitely countable number of instances), we could encode the argument before applying it to $f$ and then decoding back the result. That is, if $e: \sigma \rightarrow 0$ and $d: 0 \rightarrow \sigma$ (which are inverses, thus define a bijection), we can define:

$$\mathsf{it}_\sigma \; n \; f \; x = n \; (\lambda y. e \; (f \; (d \; y)) \; x$$

Of course, this assumes the existence of $f$ and $g$, which might be easily realizable if, for examples, we had ways to enumerate instances of corresponding types. (E.g. for Church numerals, zero and increment should suffice.)

Note that bounded iteration is not as expressive as general iteration. In addition, note that Church numerals are definable by typeable terms in simply typed lambda calculus, together with operations like addition, but not predecessor (for which stronger mechanisms, like polymorphism in System F, are needed). (Short writeup about this can be found here.)


Complete problems or alternative definitions of the complexity class NP^GI?

[Summarizing the answers in the comments by Ricky Demer and Josh Grochow.]

$\mathsf{NP}^{\mathsf{GI}} = \mathsf{NP}^{GraphIso}$, since these are nondeterministic poly-time Turing reductions, which can be simulated by the oracle machine (as detailed e.g. here).

The bounded-time halting problem for non-deterministic machines with a GraphIso oracle is complete for this class, by the usual proof.

Under standard derandomization assumptions (in particular, any that imply $\mathsf{AM} = \mathsf{NP}$), $\mathsf{NP}^{\mathsf{GI}} = \mathsf{NP}$, since under such assumption we have $\mathsf{GI} \subseteq \mathsf{NP} \cap \mathsf{coNP}$, and the latter is low for $\mathsf{NP}$.


The powerful formalism you are looking for cannot exist, for otherwise we could solve the halting problem. Here is the sketch of an argument why.

Consider Hoare triples $\{A\} P \{B\}$ for partial correctness. If  we had a (computable) upper bound that related program length to the lengths of correctness proofs, then we could apply it to the  assertion

$$\{\mathsf{True}\} P \{\mathsf{False}\}.$$

This assertion is true exactly when $P$ loops. Since we have assumed a (computable) upper bound for proof length, we can find such a proof, were it to exist, in finite time by brute force search, giving an algorithms for deciding the halting problem. Contradiction. The argument can be adapted for other formal methods.

That means, regardless of the specifics, there will always be short programs with long proofs.  One way to find such programs is to look at difficult or open number theoretic questions like Fermat's last theorem or the twin prime conjecture: you can write short programs that diagonialise over the natural numbers, looking for counterexamples. Proving that such programs  do or do not terminate is likely to be highly involved.

All that being said, the last decade has seen an explosion of work on formal verification and a great deal of progress.


What is "distributed computing" as a field of computer science?

This is a TCS site, not a general computer science site, so I will only give the TCS answer.

In TCS, the following things are more or less equal:

"distributed computing"
"distributed algorithms"
the study of computational aspects of distributed systems (computability, computational complexity, algorithm design and analysis, etc.)
topics of conferences such as PODC and DISC
topics covered in textbooks such as Lynch (1996): Distributed Algorithms
topics covered in courses such as this.

(Outside TCS, "distributed computing" can mean anything: SETI@home, grids, clusters, clouds, HPC, Internet, web services, P2P, IPC, you name it.)


What does one mean by heuristic statistical physics arguments?

The second paragraph of RJK's response deserves more detail.

Let $\phi$ be a formula in conjunctive normal form, with m clauses, n variables, and at most k variables per clause. Suppose we want to determine if $\phi$ has a satisfying assignment.  Formula $\phi$ is an instance of the k-SAT decision problem.

When there are few clauses (so m is quite small compared to n), then it is almost always possible to find a solution.  A simple algorithm will find a solution in roughly linear time in the size of the formula.

When there are many clauses (so m is quite large compared to n), then it is almost always the case that there is no solution.  This can be shown by a counting argument.  However, during search it is almost always possible to prune large parts of the search space by means of consistency techniques, because the many clauses interact so extensively.  Establishing unsatisfiability can then usually be done efficiently.

V. Chvátal and B. Reed. Mick gets some (the odds are on his side), FOCS 1992. doi: 10.1109/SFCS.1992.267789

In 1986 Fu and Anderson conjectured a relationship between optimisation problems and statistical physics, based on spin glass systems.  Although they used sentences like

  Intuitively, the system must be sufficiently large, but it is difficult to be more specific.

they do actually give specific predictions.

Y Fu and P W Anderson. Application of statistical mechanics to NP-complete problems in combinatorial optimisation, J. Phys. A. 19 1605, 1986. doi: 10.1088/0305-4470/19/9/033

Based on arguments from statistical physics, Zecchina and collaborators conjectured that k-SAT should become hard when $\alpha = m/n$ is near a critical value.  The precise critical value depends on k, but is in the region of 3.5 to 4.5 for 3-SAT.

Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky.  Determining computational complexity from characteristic `phase transitions', Nature 400 133–137, 1999.  (doi: 10.1038/22055 , free version)

Friedgut provided a rigorous proof of these heuristic arguments.  For every fixed value of k, there are two thresholds $\alpha_1 < \alpha_2$.  For $\alpha$ below $\alpha_1$, there is a satisfying assignment with high probability.  For a value of $\alpha$ above $\alpha_2$, formula $\phi$ is unsatisfiable with high probability.

Ehud Friedgut (with an appendix by Jean Bourgain), Sharp thresholds of graph properties, and the $k$-sat problem, J. Amer. Math. Soc. 12 1017–1054, 1999. (PDF)

Dimitris Achlioptas worked on many of the remaining issues, and showed that the above argument holds for constraint satisfaction problems, too.  These are allowed to use more than just two values for each variable.  One key paper shows rigorously why the Survey Propagation algorithm works so well to solve random k-SAT instances.

A. Braunstein, M. Mézard, R. Zecchina, Survey propagation: An algorithm for satisfiability, Random Structures & Algorithms 27 201–226, 2005. doi: 10.1002/rsa.20057
D. Achlioptas and F. Ricci-Tersenghi, On the Solution-Space Geometry of Random Constraint Satisfaction Problems,
STOC 2006, 130–139. (preprint)


What's the nature of hypercomputing and relativity?

There are actually sort-of-researchy things one can say about rotating black holes. Namely it is known that sufficiently quick rotation produces time-like simple closed curves, leading to interesting questions about how to model time-travel paradoxes in complexity theory; see Aaronson and Watrous, "Closed Timelike Curves Make Quantum and Classical Computing Equivalent", arXiv:0808.2669

I have no particular opinion about combining hypercomputers with time travel that does not generalize to my opinion about hypercomputers in general, so probably it's best if I just point you to the one paper I could find that both cites Aaronson and Watrous and discusses hypercomputers:

Hajnal Andréka, István Németi, and Gergely Székely, "Closed Timelike Curves in Relativistic Computation", Parallel Processing Letters, 2012 and arXiv:1105.0047


Descriptive model theory classification of Counting hierarchy

This is only a partial answer (to the $PSPACE$ characterization), but I don't have the reputation to comment.

$PSPACE$ has the following (equivalent) descriptive characterizations:

$FO[2^{n^{O(1)}}]$, first-order logic with exponentially iterated quantifier blocks.
$SO[n^{O(1)}]$, second-order logic with polynomially iterated quantifier blocks.
$SO[TC]$, second-order logic with a transitive closure operator.
$FO[PFP]$, first-order logic with a partial fixed point operator.
$CRAM$-$PROC[2^{n^{O(1)}}, n^{O(1)}]$, concurrent-read concurrent-write random access machine with exponential time and polynomial hardware.
$CRAM$-$PROC[n^{O(1)}, 2^{n^{O(1)}}]$, concurrent-read concurrent-write with polynomial time and exponential hardware.

These are all mentioned in Immerman's book Descriptive Complexity.

I can't find a reference on a descriptive characterization for the counting hierarchy, but here are some observations:

$PP$ naturally corresponds to existential second-order logic with a second-order majority quantifier.
$TC^0$ is equal to $FO$ with a majority quantifier. Padding arguments give us a relationship between $TC^0$ and $CH$. This relationship makes $SO$ with a majority quantifier (on relations) a natural candidate for a descriptive characterization of $CH$.


I think(?) I [Joe O'Rourke] was the first to introduce monotone mountains, but perhaps I copied
that class from someone else.  It is a subclass of monotone polygons, with one of the
two chains that constitutes a monotone polygon a single segment.
I used it in the paper,
"Vertex pi-lights for monotone mountains,"
9th Canad. Conf. Comput. Geom., Aug. 1997, pp. 1-5.

Joe Mitchell subsequently used this class of polygons in his abstract,
"Triangulating Monotone Mountains,"
AMS 345/CSE 355 (PDF link).


I'm sure you know the following paper, but I put a link to it because other readers may be interested: Interpolation by Games

This paper is an attempt to use the communication complexity framework to show lower bounds for cutting planes.  The protocol is used to produce an interpolant circuit for unsatisfiable CNF:
$$
A(x,y)\lor B(x,z).
$$

Player $A$ gets input $a$ and $y^a$, player $B$ gets $b$ and $z^b$.  If there is a shallow tree-like proof in cutting planes then the two players have a communication protocol such that

any communication is mediated by the referee, which helps in evaluating the inequalities in the proof;
the amount of communication is small (the tree is shallow);
the two players either decide which of $A$ or $B$ is falsified;
they find a position $i$ in which $a_i \not= b_i$.

The referee is turned into a probabilistic protocol for inequalities.  In this way it is possible to turn lower bound for tree-like probabilistic protocols in the communication complexity framework into lower bound for tree-like cutting planes proofs.

If we had lower bound for communication protocol of the form of a PLS, then we would get lower bound for dag-like cutting planes proofs.

Notice that this technique does not depend on the actual inference rules of cutting planes. If we assume the inference rules to be (1) positive combination (2) integer division with floor we can build the monotone interpolant circuit using Pavel Pudlák argument.


Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$

Consider $p=2q$, $q\ge 1$.

Asymptotically, the quantity you are after is $2^{4q-2}$.

First, let's prove a lemma of general interest.

Lemma $(2^{2q}/\sqrt{\pi q})/1.136 < \binom{2q}{q} < 2^{2q}/\sqrt{\pi q}$.

Proof: Recall the Robbins bounds
$$
n! = \sqrt{2\pi}n^{n+1/2}e^{-n}e^{r_n},
$$
where $1/(12n+1) < r_n < 1/(12n)$.
This gives
$$
\binom{2q}{q} = 2^{2q}e^{r_{2q}}/\sqrt{\pi q}e^{2r_q} >
\left(2^{2q}/\sqrt{\pi q}\right)/c
$$
where $c = e^{(18q + 1)/(6q(24q+1))} < e^{19/150} < 1.136$.
Further,
$$
\binom{2q}{q} < \left(2^{2q}/\sqrt{\pi q}\right)/d
$$
where $d = e^{(36q - 1)/(24q(12q+1))} > 1$.$\qquad\qquad\Box$

Corollary $\binom{2q}{q} = \Theta(2^{2q-(\log_2 q)/2})$.

A first pass upper bound is $\left(2^{2q-1}\right)^2 = 2^{4q-2}$, since $U$ and $V$ cannot overlap.

For a lower bound.  By the symmetry of the binomial expansion one can achieve
$$
\left(\sum_{i=0}^{q−1}\binom{p}{i}\right)^2
= \left(\left(2^{2q} - \binom{2q}{q}\right)/2\right)^2
= 2^{4q-2}\left(1-1/\left(\alpha\sqrt{\pi q}\right)\right)^2
$$
where $1 < \alpha < 1.136$ by the lemma.
This expression can be obtained by taking $U$ to be the set of $p$-bit Boolean vectors within Hamming distance $q−1$ from $0\dots 0$, and $V$ to be the vectors within distance $q−1$ from $1\dots 1$.
These sets both have the same size.
(Note that the number of $p$-bit Boolean vectors which have Hamming distance exactly $i$ from the all-zero vector is $\binom{p}{i}$.)

Now note that $\alpha\sqrt{\pi q}$ is smallest when $q = 1$, taking a value that exceeds $\sqrt{\pi}$.  Hence $\left(1 - 1/(\alpha\sqrt{\pi q})\right)^2 > 0.1899$.
It follows that the quantity you are interested in is $\beta 2^{4q-2}$, where $0.1899 < \beta < 1$.

The case for $p$ odd seems a bit more involved, but the same idea might apply.  The "buffer zone" between $U$ and $V$ is now going to consist of vectors of two different Hamming weights instead of just one, so it has roughly double the impact.  This probably calls for a more careful analysis of the error, and the lower bound might leave a bit of slack.

Disclaimer: I wrote the above fairly quickly, so there may be some errors in the derivation.  Please check the details if you plan to use this elsewhere.  Such a natural question has probably also been studied in the coding theory literature.

Reference:

Herbert Robbins, A remark on Stirling's formula, The American Mathematical Monthly 62(1), 1955, 26–29.  doi:10.2307/2308012


When was co-NP introduced for the first time?

Albert R. Meyer and Larry J. Stockmeyer introduced the polynomial hierarchy in 1972 with their paper "the equivalence problem for regular expressions with squaring requires exponential space". The class $\Pi_1^P$ in there is of course coNP. Stockmeyer wrote a full paper on the polynomial hierarchy (TCS 1977) which also uses the notation coNP.


Inequality for p-norm of probability distributions

(Comment --> answer)

The inequality unfortunately fails to hold, a counterexample is
 $$p = (1,0,\dots,0)$$
and
 $$q = \left(\frac{1}{2},\frac{1}{2n},\dots,\frac{1}{2n}\right),$$
where the support size is $n+1$ and $x=2$.

Then $\sum p_i^r = 1$, but $x^{r-1}\sum q_i^r \approx \frac{1}{2}$:
\begin{align}
 \sum q_i^r &= \frac{1}{2^r} + n\left(\frac{1}{2n}\right)^r  \\
  &= \frac{1}{2^r}\left(1 + \frac{1}{n^{r-1}}\right)  \\
  &\to \frac{1}{2^r}
\end{align}
as $n \to \infty$, so $x^{r-1}\sum q_i^r \to \frac{2^{r-1}}{2^r} = \frac{1}{2}$.


The average number of annual publications for CS postdocs

The main motive behind this question is to understand where am I standing with my own performance and productivity.

Then you're asking the wrong question.  The right metric to examine isn't the number of publication, but rather your visibility and reputation (and ultimately impact) within the research community.  If the intellectual leaders of your target subcommunity are eager to write you good recommendation letters, it doesn't matter whether you publish one paper a year or ten.  Similarly, if the intellectual leaders in your target subcommunity are not eager to write you good recommendation letters, it doesn't matter whether you publish one paper a year or ten.


Complexity of Finding Optimal Synergistic Set Packings

This is an instance of the standard network flow problem called "Project Selection", and hence can be solved efficiently (even in practice). See (what's currently) Section 24.6 of Jeff Erickson's lecture notes for a nice explanation. It's covered in most introductions to network flow in good undergraduate algorithms courses, so if you don't like Jeff E's notes, I'm sure you can find plenty of alternatives.

The general idea of project selection is that you have a collection of projects, each with a cost/benefit (positive or negative) and a collection of dependencies, and the goal is to find the set of projects that (1) satisfies dependencies, and (2) maximizes the benefit of all the selected projects.

For your case, you would have one project for each set $S_i$, and also one project for each $e_j$. Each $e_j$ project has no dependencies, and each $S_i$ will depend on the $e_j$ in $S_i$. The benefit of $S_i$ is its payoff, and the 'benefit' of each $e_j$ is the negative of its cost. You can see that reasonable ways of selecting projects correspond to all the ways of picking solutions to your problem, and the objective values are the same on either side of the correspondence.

I'll just add that you're really only using a special case of project selection, where there are "good" projects that only depend on "bad" projects that have no further dependencies. Project selection doesn't assume this structure, and can be solved on an arbitrary dependency graph. You might find this useful in your application where you've got multiple phases of computation.


Is it NP-Complete to determine if a quadratic program (QP) has multiple solutions?

[Since I could not edit my comment, I repost it here as an answer]

To determine if a quadratic program (QP) has multiple solutions (so you have to answer "Yes" if the QP has more than one solutions, and "No" if it has one or no solution) can be shown to be NP-complete by modifying the proof on NP-completeness of QP here http://link.springer.com/article/10.1007%2FBF00120662.

The proof uses a reduction from k-clique to a QP. Now, add a free variable to the QP, so that it has one solution iff it have multiple ones. Thus, the answer to the problem if QP has multiple solutions or not gives the answer to the question if a graph has a clique of size k or not.


checking isomorphism between K regular graph

If $p$ is fixed, graph isomorphism can be tested in polynomial time, see [E. Luks. Isomorphism of graphs of bounded valance can be tested in polynomial time. Journal of Computer and System Sciences, 25:42–65, 1982].


Can Polar Codes (or any other efficient codes) reach the second order capacity?

As far as I know, people conjecture that for Polar codes and any fixed DMBSC (discrete memoryless binary symmetric channel), $\log M \leq nC - O(n^{1-c})$ for some absolute constant $c > 0$ and vanishing error probability should be possible (or in other words, in order to be $\epsilon$ close to capacity, only a polynomially large $n$ in $1/\epsilon$ would suffice. However, there is no rigorous published proof available at this point. There are rumors about an upcoming proof, but that's not official yet.


What category are Tagless Final Algebras final In?

Final Algebra semantics was introduced by Mitch Wand in his paper "Final Algebra Semantics and Data Type Extensions", see this freely available tech report: https://www.cs.indiana.edu/ftp/techreports/TR65.pdf .

It does not mean final coalgebra semantics, which is a very different idea. The wrinkle is that the algebra is not final in the same category that the initial algebra is initial, because then the final algebra would just be given by the unit type/terminal object as carrier. Instead, Wand defines a category of adequate extensions of an algebra, which basically say you want the algebras in question to not equate basic values. An example of this is that the signature may contain numbers and you only want to consider algebras where the interpretations of distinct integers are unequal. This rules out the trivial terminal object as carrier because it would equate all numbers. I wrote a blog post about this a while ago in an attempt to understand the same question: http://prl.ccs.neu.edu/blog/2017/09/27/final-algebra-semantics-is-observational-equivalence/ .


Correct me if I'm wrong, but given this is possible with O(n) time, then you can build the sorted array in O(n) time, too:

for(i=0; i<n; i++) {
 C[P[i]] = A[i];
}

If so, there's no way this can be done in O(n), since sorting is O(n.log(n)) at least.
When you take that into account, there are many O(n.log(n)) sorting algorithms, that can be easily fitted for your purpose and you can implement it this way:

B = array(1..n);
sort(B, cmp_func);

where cmp_func(int a, int b) compares A[a] and A[b] instead of a and b.

Sorry for my lame pseudocode, but I think it's understandable.


Largest set allowing one-step unstructured quantum search

Perhaps a more appropriate for your question: Dong Pyo Chi and Jinsoo Kim showed that for any "Grover-like" algorithm, in which we may change the phase of the diffusion operator and the oracle gate from $-1$ to possibly independent and arbitrary complex phases, a marked element can be found with a single query if and only if there are at least $N/4$ marked items. Here is a link to their article.

Note that the case $t=N/4$ was discovered earlier by Brassard, Boyer, Hoyer and Tapp.


Freivalds matrix multiplication with non binary random vector

The answer to both questions is yes. The matrix $A B - C$ gives rise to a linear application over your field $\mathbb F$, which is a multivariate polynomial of total degree $d=1$. By the Schwartz-Zippel lemma, when $x$ is drawn from $S^n$ (where $S \subseteq {\mathbb F}$), the probability that $(A B - C) x = 0$ is at most $d/|S| = 1/|S|$, provided that $A B \neq C$.
As you observe, this can also be proved directly using the standard argument for Freivald's algorithm.


Number of edge induced subgraphs with given vertex parity

For simplicity, let's restrict ourselves to $k$-regular graphs.

The first part of your update is correct.  Changing notation slightly from what you have introduced, let me define $n_e$ (resp. $n_o$) to be the number even (resp. odd) edge-induced subgraphs of a given graph $G$.  For the (arity $k$) signature $f = [1, -1, -1, \dotsc, -1]$, the Holant problem Holant($f$) does indeed correspond to the problem "Given a graph, compute $n_e - n_o$."  To see this, fix a subset of edges $E'$ (i.e. the subset of edges assigned 1) and consider a vertex $v$.  If none of the incident edges of $v$ are in $E'$, then $v$ is not in the edge-induced subgraph defined by $E'$ and the constraint at $v$ contributes a factor of 1 to the weight of $E'$.  Otherwise, some incident edge of $v$ is in $E'$, then $v$ is in the edge-induced subgraph defined by $E'$ and the constraint at $v$ contributes a $-1$ to the weight of $E'$.  Summing over the weights of all subsets of the edges gives $n_e - n_o$.  Since $n_e + n_o = 2^{|E(G)|}$, we could solve for $n_e$ and $n_o$ if we could knew $n_e - n_o$.

The second part of your update is incorrect.  The $k$-ary signature $f = [1, -1, -1, \dotsc, -1]$ is not affine for $k \ge 3$.  For a (rather explicit) list of the affine signatures, see page 7 of this paper.  For $k \ge 3$, this signature defines a #P-hard Holant problem. To determine the complexity of this problem, notice that $f$ has the tensor rank 2 decomposition $f = 2 [1, 0]^{\otimes k} - [1,1]^{\otimes k}$. Let $\omega_{2k}$ be a $2k$th primitive root of unity. Then $f = [\sqrt[k]{2}, 0]^{\otimes k} + [\omega_{2k},\omega_{2k}]^{\otimes k}$.  Under a holographic transformation by the inverse of $M = \begin{bmatrix} \sqrt[k]{2} & \omega_{2k} \\ 0 & \omega_{2k} \end{bmatrix}$, we have the bipartite Holant problem $\operatorname{Holant}([\sqrt[k]{4}, \omega_{2k} \sqrt[k]{2}, 2 \omega_{2k}^2] | =_k)$.  This problem is #P-hard by Theorem 22 in this paper, even when also restricting to planar graphs.

For $k \le 2$, $f$ is actually affine, so the problem is tractable, but it is also tractable for a much simpler reason as well.  Any Holant problem using only constraints of arity at most 2 is tractable using matrix product and trace.


Does assigning missing literals after unit propagation keep a Boolean formula satisfiable?

If "independent" means "not inferred by unit propagation", then the answer is "no". Eg.
$$
\lnot a \lor b, x\lor \lnot b,\lnot x\lor \lnot b
$$.


How can I show a Gap-P problem is outside #P

I'd suggest looking at properties of #P functions that are different than Gap-P functions. For example, determining if a #P function is zero is in co-NP. If you could show determining whether the Kronecker coefficients is zero is UP-hard then you would have "Kronecker coefficients in #P implies UP in co-NP", an unlikely conclusion.


Software engineers have a notion they call "code smells".  These are symptoms in the code that may indicate a deeper problem.  Software engineers collect mental lists of smells to be aware of (i.e. excessively long methods or too many parameters).  It does not necessarily mean there is a problem, but simply indicate that the writer might want to double check.

I propose that we ought to also consider "proof smells".  This will not give you an algorithm for checking your proofs but it gives a language and a metaphor for recognizing possible problems in proofs.  Some examples of proofs smells:

The adverbs "Clearly", "Obviously", etc.
Reference to the proof of a previous result instead of a reference to the result itself.
Flippant use of a result with many technical preconditions.

There are also more subtle smells.  For example, if a proof uses the binomial theorem to expand an expression and then later uses the binomial theorem to return to a closed form, then maybe there is a direct manipulation on the closed form that gives the same result.

My suggestion is to collect a (mental or written) list of such smells and check for them as you read through your work.  The nice side effect of this approach is that it will also make you a better reader.

Note: My hope in this answer was to give intuitive side to the rigorous answer supplied by Lamport's How to Write a Proof referenced in M. Alaggan's answer.


Proper PAC learning of 2-DNF under uniform distribution

I don't know if you'll consider the following a non-trivial bound, but here I go.

First, to be clear so that we're not confusing $c$-DNF with $k$-term DNF (which I often do), an $c$-DNF formula over variables $x_1, \ldots, x_n$ is of the form $\vee_{i=1}^{k}(\ell_{i,1} \wedge \ell_{i,2} ... \ell_{i,c})$ where $\forall 1 \le i \le k$ and $1 \le j \le c$, $\ell_{i,j} \in \{x_1, \ldots, x_n, \bar{x}_1, \ldots, \bar{x}_n \}$.

We can first ask how many distinct terms can exist in an $c$-DNF.  Each term will have $c$ of the $n$ variables, each either negated or not -- making for $2^c\binom{n}{c}$ different possible terms.  In a 2-DNF instance, each term will either appear or not, making for $|\mathcal{H}| = 2^{2^c\binom{n}{c}}$ possible "targets," where $\mathcal{H}$ is the hypothesis space.

Imagine an algorithm that takes $m$ samples and then tries all of the $|\mathcal{H}|$ hypotheses until it finds one that predicts perfectly on the samples.  Occam's Razor theorem says that you only need to take about $m = O(\frac{1}{\epsilon}|(\mathcal{H}|+\frac{1}{\delta})$ samples for this algorithm to find a target with error $\le \epsilon$ with probability $\ge 1-\delta$.

In our case, for $c=2$, $\lg|\mathcal{H}| = O(n^2)$, which means you'll need about $n^2$ samples to do the (proper) learning.

But the whole game in learning is not really sample complexity (though that's part of the game, especially in attribute-efficient learning), but rather in trying to design polynomial-time algorithms.  If you don't care about efficiency, then $n^2$ is the simplest answer for PAC sample complexity.

UPDATE (given the changed question):

Because you explicitly stated that you only cared about sample complexity, I presented the brute-force Occam Algorithm, which is the probably the simplest argument.  However, my answer was a bit coy.  $2$-DNF are actually learnable in polynomial time!  This is a result from Valiant's original paper, "A Theory of the Learnable."  In fact $c$-DNF are learnable for any $c = O(1)$.

The argument goes as follows.  You can view a $c$-DNF as a disjunction of $\approx n^c$
"meta-variables" and try to learn the disjunction by eliminating the meta-variables inconsistent with the examples.  Such a solution can be easily translated back to a "proper" solution, and takes $O(n^c)$ time.  As a side-note, it is still open whether there is polynomial-time algorithm for $c = \omega(1)$.

As to whether the $n^2$ sample complexity is also a lower bound, the answer is pretty much yes.  This paper by Ehrenfeucht et al. shows that the Occam bound is almost tight.


How can I prove formally semantic equivalence of programming languages?

Comparing two programming languages is difficult  is a difficult
problem, and far from being solved. The key issue is that there are many different ways languages can be compared, and none of them is compelling.

The most widely used approach, coming from logic, is to
consider translations between the languages to be compared.
The general
idea is as follows:  if we
have a translation into from $L_1$ into $L_2$, say, then
$L_2$ is at least as expressive as $L_1$.

Unfortunately, things are not quite that easy.
By the Church-Turing thesis you know that you can
always find such translations
(for Turing-complete languages). So the very existence of
translations is not discreminating enough to distinguish
programming languages. And yet, everybody who has programmed in
different languages (e.g. Assembler vs Scala) knows that some
languages are easier to program than others.

This conundrum is
usually approached by putting restrictions on what counts as a
translation functions. The idea here is  that the translation functions
'measure' how much 'rearrangement' is necessary when translating
from one language to the other: the more 'rearrangement'
required, the less expressive the target language. Restrictions
on translations control what kind of 'rearrangement' we consider.
If we can show that
no translation exists that satisfies a bunch of restrictions, then
the languages are substantially different in expressivity.

In this sense e.g. the $\pi$-calculus is very expressive because
we can often find translations meeting various restrictions when
translating from a language $L$ into the $\pi$-calculus. Conversely,
purely functional languages are not so expressive, because when we
translate $L$ into a purely functional language, the translation functions
often violate various constraints.

Here is a far from exhausting list of popular restrictions
for this purpose:

The translation should preserve termination.
The translation should preserve the structure of
programs (mathematically: translation should be a
homomorphism): $$trans(f(P_1, ..., P_n)) = trans(f)(trans(P_1),
  ..., trans(P_n)).$$ This constraint is usually referred to as
compositionality of the translation.
While compositionality can often not be achieved when we try to
compare very different languages $L_1$ and $L_2$, A weaker form
almost always holds: (simplifying a bit) there is a fixed
program $Q$ for each constructor $f$ such that $$trans(f(P_1, ..., P_n)) = trans(f)(Q,
  trans(P_1), ..., trans(P_n)).$$ I like to call this
compositionality-up-to-OS, because the fixed program $Q$ acts
like an operating system.
The translation should preserve the (asymptotic space or time)
complexity of programs. (The Slot and van Emde Boas thesis says
that polynomial-time translations are always possible, so we
might need finer distinctions than preservation of run-time up
to a polynomial factor.) The theory of NP-completeness can be
seen in this light.
The translation should exhibit operational correspondence: We
say an encoding $trans(.)$ is operationally corresponding if it is
Whenever $P →^* Q$ then $trans(P) →^*≈ trans(Q)$. Moreover, whenever $trans(P) →^* Q$ then there is $P'$ such that $P
  →^* P'$ and $Q →^*≈ trans(P')$. Here ≈ is the chosen notion of program
equality in the target language.
Divergence reflection: this means that whenever $trans(P)$ diverges, then so does $P$.
Success sensitiveness: Given a criterion of program
success (e.g. the ability of output a chosen value) on both
source and target, an encoding $trans(.)$ is success sensitive if $P$
is successful if and only iff $trans(P)$ is successful.
Full abstraction, we want $P \simeq_1 Q$ iff $trans(P) \simeq_2 trans(Q)$,
where $\simeq_1$ is the chosen notion of program equality in the source language
of the translation and $\simeq_2$ does that job in the target.
Preservation of program size:  the translation should not lead to substantial
increases in program size.
Name invariance: each program has a finite number of
'interaction points' that the outside can use to interact with
the program, e.g. free variables.  We can require that
encodings commut with injective renamings of 'interaction
points'.

The relationships between those criteria, like the whole field
of programming language expressiveness, is ill-understood.

A pioneering paper in the study of programming language expressiveness is

M. Felleisen, On the Expressive Power of Programming Languages.

where key concepts from logic, such as conservative extension of
theories are generalised to programming languages.


Do combinatorial discrepancy upper bounds lead to smaller $\epsilon$-nets (as with $\epsilon$-samples)?

First, and more obviously, an $\epsilon$-sample is an $\epsilon$-net.

Of course, the above observation gives usually very loose bounds for $\epsilon$-nets. The bound you mention at the end of our post relies not just on small discrepancy but also on VC-dimension itself, so the relationship is not so clear. Let me elaborate.

Let $s(\epsilon)$ be the size of the minimum $\epsilon$-sample for your system. As you mention this can be bounded in terms of discrepancy.

We call a restriction of $\mathcal{S}$ to $Y$ the set system $\mathcal{S}|_Y = \{S \cap Y: S \in \mathcal{S}\}$. Finally, the shatter function $\pi(s)$ is equal to the maximum number of distinct sets in any restriction $\mathcal{S}|_Y$ to a set $Y$  of size at most $|Y| \leq s$.

We can show that there exist $\epsilon$-nets of size at most $O(\frac{1}{\epsilon} \log \pi(s(\epsilon/2)))$. This goes as follows.

any set system of $m$ sets has an $\epsilon$-net of size $O(\frac{1}{\epsilon} \log m)$;
an $\epsilon/2$ net of an $\epsilon/2$-sample for $\mathcal{S}$ is an $\epsilon$-net for $\mathcal{S}$;

Let us instantiate this for $\mathcal{S}$ of constant VC-dimension. For such $\mathcal{S}$, $s(\epsilon) \leq \epsilon^{-2}\log \epsilon^{-1}$. Also, by the Sauer-Shelah lemma, for constant VC dimension $\mathcal{S}$, $\pi(s) = s^{O(1)}$. Plugging this into the bound we got above gives $O(\frac{1}{\epsilon}\log \frac{1}{\epsilon})$ for the size of an $\epsilon$-net.

As you see, the bound on the size of $\epsilon$-nets depends on $\pi$ and not just on the discrepancy. I am not sure if there are any tighter connections. There is a bound on $\pi$ in terms of discrepancy, but the bound is exponential in the discrepancy, so it's not terribly useful.

Finally a note: for $\mathcal{S}$ with VC-dimension $d$ we can show there exist $\epsilon$-samples of size $O(\epsilon^{-\frac{2d}{d+1}})$. This is because the discrepancy of such set system is bounded by $n^{\frac12 - \frac1{2d}}$. The reason why most older references state the loose bound of $\sqrt{n\log n}$ is that until the very recent work of Nikhil Bansal, there were no known polynomial time algorithms for constructing such low discrepancy colorings. Even now, the algorithm giving the loose bound is just a random coloring, so it's very simple and very efficient, and the loose bound makes practically no difference if your end goal is an $\epsilon$-net.


Short answer: the naturals are the first limit ordinals. Hence they play a central role in axiomatic set theory (eg, the axiom of infinity is the assertion they exist) and logic, and PL theorists tend to share foundational preoccupations with logicians. We want to have access to the principle of induction to prove total correctness, termination, and similar properties, and the naturals are an (er) natural choice of well-order.

I don't want to imply that finite-width binary integers are any less cool objects, though. They are representations of the p-adics, and permit us to use power series methods in number theory and combinatorics. This means that their significance becomes more visible in algorithmics than PL, since this is when we start caring more about complexity rather than termination.


Does a given regular language contain an infinite prefix-free subset?

Your problem can be solved in polynomial time.

To begin, convert the given NFA to an equivalent NFA with the following additional properties:

There are no epsilon transitions
All states are reachable from the start state

Helpful subroutine

Suppose we have an NFA $N$, a state $q$, and a nonempty string $s$. The following subroutine will let us evaluate the truth value of the following statement: "every path in $N$ from state $q$ to an accept state corresponds to a string that is a prefix of string $s^n$ for some $n$." Furthermore, this subroutine will run in polynomial time.

First, construct the NFA $S$ with $|s| + 1$ states which accepts all strings that are not prefixes of $s^n$ for any $n$ ($|s|$ non-accept states in a loop to keep track of where in the "pattern" of $sssss\ldots$ we are so far, and one accept state for if we have already deviated from that pattern). Next, construct the NFA $N'$ which is exactly like $N$ but has $q$ as its start state. Finally, construct a final NFA $N''$ whose language $L(N'')$ is $L(S) \cap L(N')$ using the standard NFA intersection construction. Note that all of these constructions are polynomial in the size of the input.

Then simply test whether the language of $N''$ is empty (which can be done in polynomial time with a simple graph search). $L(N'') = \emptyset$ if and only if $L(S) \cap L(N') = \emptyset$, or in other words every string in $L(N')$ is not in $L(S)$. In other words, the language of $N''$ is empty if and only if $N'$ accepts only strings that are prefixes of $s^n$ for some $n$. This can be rephrased as exactly the statement we were trying to evaluate: "every path in $N$ from state $q$ to an accept state corresponds to a string that is a prefix of string $s^n$ for some $n$."

Main algorithm

Consider the set of states in the NFA that are in some loop. For each such state, $q$, do the following:

Let $P_2$ be any simple loop containing $q$. Let $s$ be the string corresponding to loop $P_2$. Since the NFA has no epsilon transitions, $s$ is not empty. Then apply the subroutine to the NFA, state $q$, and string $s$. If the subroutine tells us that every path starting at $q$ in the NFA and ending at an accept state corresponds to a prefix of $s^n$ for some $n$ then continue to the next state $q$. Otherwise, output that the given NFA's language contains an infinite prefex-free subset.

If we try every state $q$ that is in a loop and the algorithm never outputs, then output that the given NFA's language does not contain an infinite prefex-free subset.

Correctness (first half)

First, suppose that the above algorithm asserts that the given NFA's language contains an infinite prefex-free subset. Let's say that this output was selected while considering some loop $P_2$ and some state $q$. As before, $s$ is the string corresponding to $P_2$. Then we know according to the subroutine that not every path starting at $q$ in the NFA and ending at an accept state corresponds to a prefix of $s^n$ for some $n$ (as this is the only output of the subroutine that would lead to the main algorithm outputting at that $q$).

Let $P_3$ be a path whose existence is asserted by the subroutine: a path from $q$ to an accept state such that the corresponding string $t$ is not a prefix of $s^n$ for any $n$.

Let $P_2'$ consist of $m$ copies of $P_2$ where $m$ is sufficiently large that $m|s| > |t|$. Since $P_2$ is a loop through $q$, $P_2'$ can be treated as a path from $q$ to $q$. The string corresponding to $P_2'$ is $s^m$

Let $P_1$ be a path from the start state to $q$ (which exists since every state is reachable from the start) and let $r$ be the string corresponding to this path.

Then the path consisting of $P_1$, $x$ copies of $P_2'$, and $P_3$ is an accepting computation path. The string corresponding to this path is $r(s^m)^xt$. Thus, the NFA accepts every string of the form $r(s^m)^xt$. This is an infinite set of strings accepted by the NFA, and I claim that this set of strings is prefix-free. In particular, suppose $r(s^m)^xt$ is a prefix of $r(s^m)^yt$ with $y > x$. In other words, $t$ is a prefix of $(s^m)^{y-x}t$. Since $(s^m)^{y-x}$ has length $m(y-x)|s| \ge m|s| > |t|$, this implies that $t$ is a prefix of $(s^m)^{y-x} = s^{m(y-x)}$. But we know by the output of the subroutine that $t$ is not a prefix of $s^n$ for any $n$. Thus, $r(s^m)^xt$ cannot be a prefix of $r(s^m)^yt$, and as desired the set of strings is prefix-free.

Thus, I have shown that if the main algorithm outputs that the given NFA's language contains an infinite prefex-free subset then this is in fact the case.

Correctness (second half)

Next, I will show the other half: if the given NFA's language contains an infinite prefex-free subset then the main algorithm will output this fact.

Suppose the given NFA's language contains an infinite prefix-free subset. Let $A$ be the set of (accepting) computation paths corresponding to these strings. Notice that $A$ is an infinite set of accepting computation paths whose corresponding strings are never prefixes of each other.

Say that a state is "looping" in the NFA if there exists a loop in the NFA through that state and "non-looping" otherwise. Consider all paths from the start state to any looping state which pass through only non-looping states (except for the one looping state where they end up). Let $P$ be the set of these paths. Each path $p \in P$ cannot have a loop as then the states in that loop would be looping states and so $p$ would pass through a looping state. Thus, the lengths of paths in $P$ are bounded above by the number of states in the NFA and so $P$ is finite (for example, if the start state is a looping state then the only such path is the empty path).

We can partition $A$ into $|P|+1$ subsets based on how that computation paths in $A$ starts. In particular, for $p \in P$, let $A_p$ be the set of all computation paths in $A$ that start with path $p$ and let $B$ be the set of all other paths in $A$. Clearly, all $A_p$s and $B$ are disjoint and their union is the entire set $A$. Furthermore, $B$ contains only paths that never pass through a looping state, and therefore never loop; thus $B$ is finite. We can conclude then that some $A_p$ must be infinite (otherwise $A$ would be a union of finitely many finite sets).

Since $A_p$ is infinite, there are infinitely many computation paths, none of whose strings are prefixes of each other, that are accepting paths starting with $p$. Let $q$ be the state reached at the end of path $p$. We can conclude that there are infinitely many accepting paths, call this set $A'$, starting at $q$ all of which correspond to strings that are not prefixes of each other.

During the main algorithm, we run the subroutine on state $q$ and some string $s$. This subroutine tells us whether every accepting path starting at $q$ corresponds to a string that is a prefix of $s^n$ for some $n$. If this were the case, then all the infinitely many accepting paths in $A'$ would be prefixes of $s^n$ for various $n$, which would imply that they are all prefixes of each other. This is not the case, so we conclude that when the main algorithm runs the subroutine on state $q$, the result is the other possible outcome. This, however, leads the main algorithm to output that the NFA's language contains an infinite prefix-free subset.

This concludes the proof of correctness.


Problems in BQP but conjectured to be outside P

To have a list of such problems, you can look at the list of superpolynomial speed improvement at the quantum algorithm zoo (QAZ). The list below is based on  this (see QAZ for precise definitions and references. This is another way to say I don’t even pretend to understand many of the problems of this list!)
Algebraic and Number Theoretic Problems
If I’m not mistaken, all problems listed before the Abelian hidden subgroup problem are special cases of it.

Factorization
Discrete logarithm
Pell’s Equation. Factoring reduces to Pell’s equation.
Principal Ideal Ideal problem. Pell’s equation reduces to this problem, which therefore at least as hard as factoring.
Unit Group problem
Class Group problem
Gauß Sums estimation
Matrix Elements of Group Representations
Group Order and Membership
The Abelian hidden subgroup problem
Some (but not all) non-Abelian hidden subgroup problems
Some (but not all) problems phrased as special cases of the hidden shift problem
Some (but not all) Hidden Nonlinear Structures problems
Exploring some graphs (Welded trees)
Group Isomorphism, for Abelian and some non-Abelian groups
Find some properties of Finite Rings and Ideals

Approximation and Simulation

Quantum simulation. Obviously $BQP$-complete
Computing some knot-invariants, including HOMFLY polynomial, of which the Jones polynomial is a special case. Some of them are $BQP$-complete
Computing some Three-manifold Invariants. Some of them are $BQP$-complete.
Estimating the thermodynamic partition function of some classical systems
Computing Zeta Functions over finite fields
A string rewriting problem is  $\mathit{PromiseBQP}$-complete
approximating matrix elements of powers of exponentially large sparse matrices.

Algorithm I don’t really  get.
These are mainly algorithms where QAZ claims a superpolynomial increase, but I don’t get why the original problem is supposed to be out of $P$. That said, I’ll bet lots of my money on QAZ being right and myself being wrong on that.

Pattern matching for large enough ($>\log(n)$) patterns
Some linear system problems, in $P$ but having a $\mathrm{polylog}$ quantum algorithm if the linear system is given as an oracle.
Computing the Electrical Resistance of a graph,has a $\mathrm{polylog}$ quantum algorithm if the electric circuit is given as an oracle
Weight Enumerators problem. Something related to code and partition functions, but I don’t understand what it is about.

$P$ problems 1st proved to be in $BQP$ and then in $P$
Here are some problems where an efficient quantum algorithm has been published before a classical one. In other words, they were once conjectured to be in $BQP$ but not in $P$, but this conjecture is now invalidated.

Satisfying more than $(\tfrac12-\tfrac{\text{constant}}{D})N$ (but less than $\left(\tfrac12-\tfrac{1}{22D^{3/4}}\right)N$) constraints of the  Max E3LIN2 problem. As pointed by Juan Berego Vega in the comments : there is now a classical algorithm for $(\tfrac12-\tfrac{\text{constant}}{\sqrt{D}})N$, which was motivated by the quantum result. (Blog post on this result, paper 1, paper2)
Recommendation systems (see Scott Aaronson’s blog post  for a more detailed explanation). Recommendation system — à la Netflix/Amazon/etc.— can be seen as completing a sparse $m×n$ matrix of low rank $k$ with very incomplete data. Known classical algorithm where polynomial in $m$, $n$ ad $k$. If the matrix is given as an oracle, Iordanis Kerenidis an Anupam Prakash found a $\mathrm{poly}(k)\mathrm{polylog}(mn)$ quantum algorithm finding samples of the unknown elements of the matrix in 2016 (paper). In 2018, while trying to prove this scaling is impossible to reach with a classical machine, Ewin Tang actually found a classical algorithm achieving the same performance under the same conditions (paper available here and here).


Finding small sets of integers in which every element is a sum of two others

I suppose a linear time algorithm should be possible for Question #1) (and if you are willing to deal with a different representation, an O(1) time algorithm)

Given any N >= 23, we construct a strongly self supporting set which contains 1 and N.

We can do that easily if we construct the same for N-1, and then add N to the resulting set.

For the base case of 23, we can start with your example set.

To bring the size down, we should be able to use a similar approach:

Construct sets which contain 1, N and N-1.

We use these constrained sets and do this construction recursively to bring the size down to O(logN) as follows:

If N is even, to construct a set containing 1,N and N-1, recursively construct a set containing 1, N/2 and N/2-1 (i.e. set corresponding to N/2) and add N and N-1 to resulting set. Since N-1 = N/2 + N/2-1 and N = 1 + N-1, this is a valid set.
If N is odd construct a set for N-1 and N to resulting set.

For the base cases, we can start with {−22, −20, −18, −16, −14, −12, −10, −2, 1, 3, 7, 8, 15, 23,24} for N=24. For 24 < N <= 47, we can use the above linear time algorithm and build upon the set for N=24. For N>=48 we switch to reducing by half.

In fact, for composite N, we can bring the size further down to the size required for one of the small primes which divides N: Find a set for the small prime, and just multiply all numbers by a suitable factor.

It might be interesting to prove some lower bounds in the case N is prime.


Searching for the original definition of online algorithms

Thanks.

With Garmow's comment I was able to find the first two references which also called on-line algorithms as on-line:

Johnson, David S. "Fast algorithms for bin packing." Journal of Computer and System Sciences 8.3 (1974): 272-314.

and

Johnson, David S. Near-optimal bin packing algorithms. Diss. Massachusetts Institute of Technology, 1973.


Solving "all-marginals" problem for independent sets on grid

Here's a dynamic-programming algorithm that is fast enough to solve a given 18 x 18 grid in about 20 minutes.  The algorithm is a modification of the algorithm from this paper for counting independent sets in a given $m\times n$ grid.

Fix the input: the grid dimension $n \times n$ and the values $\lambda_{ij}$ for $i,j\in\{1,\ldots,n\}$.  Represent each independent set in the grid by its 0/1 incidence matrix $M$ where $M_{ij}$ is 1 if the grid vertex $(i,j)$ is in the independent set, and 0 otherwise.
Let $S_n$ denote the set of 0/1 vectors of dimension $n$ with no two consecutive 1's.  (I think the size of $S_n$ is the $n+2$nd Fibonacci number, so $|S_{18}|=6765$.)

An $n\times n$ 0/1 matrix $M$ represents an independent set if and only if the following two conditions hold:

Each row $M_i$ of $M$ is in $S_n$.
Every two consecutive rows $M_i$ and $M_{i+1}$ are compatible, meaning that there is no $j$ such that $M_{ij}$ and $M_{i+1,j}$ are both 1.

Construct directed acyclic graph $G=(V,E)$ where $V$ and $E$ are defined as follows.  The vertex set $V$ contains source and sink vertices $s$ and $t$, and, for each row $i\in\{1,\ldots,n\}$ and $x\in S_n$, a vertex $v(i, x)$.  The edge set $E$ contains the following edges: for each $x\in S_n$, an edge from $s$ to $v(1, x)$ and an edge from $v(n, x)$ to $t$; for each $i\in\{1,\ldots,n-1\}$, and each $x\in S_n$, edges from $v(i, x)$ to $v(i+1, y)$ for every $y\in S_n$ that is compatible with $x$.

The $s$-$t$ paths in $G$ correspond bijectively to the independent sets in the grid.  Each $s$-$t$ path is of the form $(s, v(1, x_1), v(2, x_2), \ldots, v(n, x_n), t)$, corresponding to the independent set whose incidence matrix $M$ has $M_i = x_i$ (that is, the $i$th row of $M$ is $x_i$).

Assign weights to the vertices of $G$ as follows.  Give $s$ and $t$ weight $w(s)=w(t)=1$.  Give each vertex $v(i, x)$ weight $w(v(i,x)) = \prod_{j:x_j=1} \lambda_j$.  Then, for any $s$-$t$ path in $G$, the product of the weights of the vertices on that path is the product of the $\lambda_{ij}$'s of the vertices in the corresponding independent set in the grid.

Now, for every vertex $v$ in $G$, define $P(v)$ to be the sum, over all paths from $s$ to $v$, of the product of the weights of the vertices on the path.  Define $P'(v)$ to be the sum, over all paths from $v$ to $t$, of the product of the weights of the vertices on the path except for $v$.  Compute these two quantities for every vertex in $G$.  This can be done in time linear in the size of $G$ (assuming constant-time exact arithmetic) using a standard dynamic-programming approach.  E.g. use $P(s) = 1$ and, for $v\ne s$,
$$P(v) = w(v)\sum_{u: (u, v)\in E} P(u).$$

For each vertex $v$ in $G$, define $Q(v) = P(v)P'(v)$.  This is the sum, over all $s$-$t$ paths in $G$ that go through $v$, of the product of the weights of the edges on the path.  Then $Q(s)$ is the sum, over all independent sets in the grid, of the product of the $\lambda$'s for the vertices in the independent set. For each vertex $v(i, x)$, then, $Q(v(i,x))$ is the sum, over all independent sets $M$ in the grid whose $i$th row $M_i$ is $x$, of the product of the $\lambda$'s for the vertices in the independent set.

Finally, for each vertex $g=(i,j)$ in the grid graph, compute $p_g$ as the sum, over all $x\in S_n$ such that $x_j = 1$, of $Q(v(i, x))$, divided by $Q(s)-1$.  (Subtract 1 as the problem specification doesn't count the empty set in the denominator.)

For the instance with $n=18$ and each $\lambda_{ij}=1$, this Python script computed the answer in about 17 minutes.  (The graph $G$ had about 122K vertices and 159M edges.)  For non-uniform lambdas, in the probability calculations, you'll need to take some care regarding arithmetic precision.  (If you want exact answers, you'll need to use rational arithmetic.  You could compute close approximations using floating-point arithmetic, but then you'll probably have to be careful about the order in which the sums are performed.)

Here's the output of the script for the instance with $n=7$ and each $\lambda_{ij}=1$. Each entry of the 7 x 7 matrix below is the probability for the corresponding vertex of the grid, times the denominator (which for $\lambda_{ij}=1$ is the number of non-empty independent sets in the grid).

N = 7

denominator = 1280128949

402968942 298303063 333041917 316303258 333041917 298303063 402968942
298303063 296843520 279776968 292351405 279776968 296843520 298303063
333041917 279776968 296033698 285917681 296033698 279776968 333041917
316303258 292351405 285917681 293815906 285917681 292351405 316303258
333041917 279776968 296033698 285917681 296033698 279776968 333041917
298303063 296843520 279776968 292351405 279776968 296843520 298303063
402968942 298303063 333041917 316303258 333041917 298303063 402968942


Suppose you had such a randomized procedure that takes a value in $\{-1,1\}$ and outputs a real number. Let $P$ and $Q$ be the output distribution on input $+1$ and $-1$ respectively.
Consider the extreme case of $\mu = +1$. In this case $Y = +1$ for sure, and you are outputting a sample from $P$, which means that $P$ should be an $\mathcal{N}(\nu, 1)$ distribution for some $\nu$ with $|\nu|$ being $\Omega(1)$. Similarly, the other extreme of $\mu=-1$ tells us that $Q$ is a $\mathcal{N}(\nu', 1)$ distribution for some $\nu'$ with $|\nu'|$ being $\Omega(1)$.
But now, for $\mu=0$, you are outputting the uniform mixture of two normals, which cannot be a normal distribution unless $\nu=\nu'$. In the latter case, you get $\mathcal{N}(\nu, 1)$ for some $\nu$ bounded away from zero.
Thus you cannot satisfy this requirement simultaneously for $\mu\in \{-1, 0, 1\}$.


Implicit Complexity has taught us that (some) complexity classes can be classified by type systems, in the sense that there are type systems that only accept polynomial programs, for example. One more practical-minded offshoot of this research is RAML (Resource Aware ML), a functional programming language with a type system that will give you precise information of the running times of its programs. It is more precise, in fact, than big-O complexity, are constant factors are also included, parametrized by a cost model for the base operations.

You may think that this is cheating: surely some algorithms have a complexity that is very hard to compute precisely, so how could this language easily determine the complexity of its programs? The trick is that there are many ways to express a given algorithm, some which the type-system will reject (it rejects some fine programs), and some, maybe, that it accept. So the user doesn't get the world for free: he or she doesn't have to compute cost estimations anymore, but need to figure how to express code in a way that is accepted by the system.

(It is always the same trick, as with programming languages with only terminating computations, or provable security properties, etc.)


Here is a simple Turing machine segment that reads a binary word $w$ starting at a position immediately to the right of the delimeter symbol # and replaces it with $w$'s successor in the lexicographic ordering. Here, L,R,S indicate moving the read/write head Left, Right, or Stay.

This simple and powerful (standard) trick avoids a brute-force enumeration by using the results of previous computations to produce future ones. If you're allowed multiple tapes, it's now quite easy to accomplish the task you defined. Otherwise, there are standard $k$-tape to $1$-tape conversions.


Algebraic construction of $\varepsilon$-biased sets

recall that
$$\langle s(x,y,z),\tau\rangle=\cdots=f_z\Big(\sum_{i,j}x^iy^j\tau_{i,j}\Big)$$

if we define $p_\tau(x,y)=\sum\limits_{i,j}x^iy^j\tau_{i,j}$, we have

$$\langle s(x,y,z),\tau\rangle=f_{p_\tau(x,y)}(z)$$

So, observe that whenever $p_\tau(x,y)\neq 0$ we win as $z$ is uniform and the expected value of $f_{p_\tau(x,y)}(z)$ is also $1/2$ which means that the contribution to the bias of these $x,y$ is zero.

Again from Schwartz-Zippel we have only $O(\sqrt{n}/2^\ell)$ many zeros of $p_\tau$ on them we lose the entire bias. So, the total bias is at most $O(\sqrt{n}/2^\ell)\stackrel{?}{\leq}\varepsilon$. Choosing $\ell=\Omega(\log(\sqrt{n}/\varepsilon))$ finishes the construction.


Observational Equivalence of open terms in PCF

Got the answer, thanks to jonsterling on reddit for the insight.

The error is that both M and N written as full judgements, must be weakened to have the same environment, and one that fits C[-]. So the question becomes whether  ⟦M⟧ = ⟦x,y ⊢ x⟧ and ⟦N⟧ = ⟦x,y ⊢ y⟧ are observationally equivalent.  And the contradiction above disappears.


Counting the number of vertex covers: when is it hard?

The #VC problem of computing the number of vertex covers of a given graph remains #P-hard for 3-regular graphs; see for example [Greenhill, 2000].

To show that the #VC problem remains #P-hard for graphs with at most $c\cdot n$ edges, where $n$ is the number of vertices and $0<c<3/2$, reduce from the 3-regular case by adding a large enough independent set (of linear size). The number of vertex covers remains the same if you add an independent set.

Similarly, to show that the #VC problem remains #P-hard for graphs with at least $c\cdot n^2$ edges, where $n$ is the number of vertices and $0<c<1/2$, reduce from #VC by adding a large enough clique component (of linear size). The number of vertex covers is multiplied by $p+1$ if you add a clique of size $p$ to a graph.

Catherine S. Greenhill: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Computational Complexity 9(1): 52-72 (2000)


Reducing a minimum cost edge-cover problem to minimum cost weighted bipartie perfect matching

If all edge weights are non-negative, then the minimum weight set of edges that covers all the nodes automatically has the property that it has no three-edge paths, because the middle edge of any such path would be redundant. If we assign each vertex to an edge that covers it, some edges will cover both of their endpoints (forming a matching $M$) and others will cover only one of their endpoints (and must be the minimum weight edge adjacent to the covered endpoint). If we let $c_v$ be the cost of the minimum weight edge incident to vertex $v$, and $w_e$ be the weight of $e$, then the cost of a solution is $\sum_{v\in G} c_v + \sum_{(u,v)\in M} (w_{(u,v)}-c_u-c_v)$. The first sum doesn't depend on the choice of the cover, so the problem becomes one of finding a matching that maximizes the total weight, for edge weights $c_u+c_v-w_{(u,v)}$. If you really want this to be a minimum weight perfect matching problem, then instead use weights $w_{(u,v)}-c_u-c_v$ and add enough dummy edges with weight zero to guarantee that any matching with the real edges can be extended to a perfect matching by adding dummy edges.

If the input graph can have negative edge weights, then the three-edge-path constraint becomes meaningful. In this case it's not obvious to me that there is a polynomial time solution.


Geometric picture behind quantum expanders

[This answer was copied from my answer on the now-defunct theoreticalphysics stackexchange site.]
For classical expanders, the spectral definition can be expressed in terms of the second-smallest eigenvalue of the graph Laplacian, which can be thought of as the minimum of a quadratic form over all unit vectors orthogonal to the all-ones vector.  If we restrict this minimization to vectors of the form (a,a,...,a, b,b, ..b), then this yields the edge expansion of the graph.  here is a discussion.  The rough equivalence of these two definitions is known as Cheeger's inequality.

This suggests that for the quantum case we should consider the action of the channel (formed by applying a random unitary from the expander) on projectors.  A result analogous to Cheeger's inequality is derived in Appendix A of arXiv:0706.0556.

On the other hand, while this is mathematically analogous, we do still know of many fewer applications of quantum expanders than are known for classical expanders.


Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion

This isn't a trivial question at all. One of the problems you'll have finding algorithms for this is the disconnectedness (pun intended) of the work on dynamic graphs. Thorup et al.'s work (the one you mention) is probably the best start for the kind of thing you're looking for.

You could also try Bhadra & Ferreira, they're probably getting a bit off-topic for what you want, but they do have references to other material that could be useful.


Implementation that solves minimum set cover

sometimes with various CS optimization problems, the best available or most evolved implementations can be found in EE applications. in this case, consider Espresso, a logic minimizer. its open source and mainly written in C. it has a built in [exact] and also heuristic set cover as a subroutine after generating prime implicants for SAT. the exact covering is chosen with a command line switch.

ie it implements the Quine-McCluskey method where set cover is part of the final optimization. there is some research on an improved exact set cover (also called the "minimum canonical cover") by McGeer et al called Espresso Signature which was implemented but may be more difficult to obtain source code.

note the set cover algorithms are apparently decoupled in the code but possibly not decoupled in the interface. ie it might require a little bit of "wrapper" coding to provide a direct interface to the set cover subroutines. another possibility is using monotone formula inputs in which there are no "derived" prime implicants other than those supplied as input in which the entire logic minimization reduces to set cover only.


Church-Rosser equivalent for concatenative languages?

SK combinators are Church-Rosser.

However, the usual  $\lambda$-calculus method of proving local confluence and then appealing to Newman's lemma doesn't work. You need a slightly fancier argument, and the SEP entry on combinatory logic gives a sketch of a proof that does work.


Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone

Arnaud is correct.  The critical piece I was missing is that for any $z$, $z^\top x > 0 \iff z^\top x / \|x\| > 0.$

So pick $z \in S$. Let $x_0 = \text{arg inf } \{ z^\top x \mid x \in \text{cl}(K) \cap \{0\}, \|x\|=1 \}$
and let $c_{x_0} = z^\top x_0 > 0$.  We know $x_0$ exists because the set $\text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ is closed and bounded.

Now let $\varepsilon = c_{x_0} / 2$ so that for any $z' = z + \gamma u$ where  $\|u\|=1$ and  $\gamma \in (0,\varepsilon)$, we have

$~~~~ z'^\top x_0 \ge c_{x_0} - \gamma > c_{x_0} / 2 > 0.$

Furthermore, for any other $x \in \text{cl}(K)\cap \{x \mid \|x\| = 1 \}$ we know

$~~~~ z'^\top x \ge z'^\top x_0 > 0.$

Therefore, for any $x \in \text{cl}(K) \backslash \{0\}$ we have

$~~~~ z'^\top x / \|x\| > 0$

which proves $z'^\top x > 0$ whenever $z' \in D(z,\varepsilon)$.


What is the computational complexity of "solving" chess?

As @Joe points out, chess is trivial to solve in $O(1)$ time using a lookup table.  (An actual implementation of this algorithm would require a universe significantly larger than the one we live in, but this is a site for theoretical computer science.  The size of the constant is irrelevant.)

There is obviously no canonical $n\times n$ generalization of chess, but several variants have been considered; their complexity depends on how the rules about moves without captures and repeating positions are generalized.

If a draw is declared after a polynomial number of capture-free moves, or after any position repeats a polynomial number of times, then any $n\times n$ chess game ends after a polynomial number of moves, so the problem is clearly in PSPACE.  Storer proved that this variant is PSPACE-hard.

For the variant with no limits on repeated positions or capture-free moves, the number of legal $n\times n$ chess positions is exponential in $n$, so the problem is clearly in EXPTIME.  Fraenkel and Lichtenstein proved that this variant is EXPTIME-hard.


Matching problems that are easy for bipartite graphs but hard for general graphs

The stable marriage problem with ties (a matching problem for bipartite graphs) is (trivially) solvable in polynomial time, whereas the stable roommate problem with ties (a matching problem for general graphs) is known to be NP-hard.  See Eytan Ronn:
NP-Complete Stable Matching Problems. J. Algorithms 11(2): 285-304 (1990) for details.


As you might have realized by now, this problem is closely related to Matrix Multiplication.

Particularly: Task B asks to preprocess an m by n matrix S, such that given as a query a n by matrix X, we need to compute the m by m boolean product SX. For particularly structured matrices S, this can be solved by something like FFT. But I suspect that for a non-structured S (say random S) the best you could do is used fast matrix multiplication.

If the matrices S and X are sparse (i.e. the input sets are of cardinality << n) then there are some algorithms for sparse matrix multiplication that can give some good results.

About the first task, it's of course even harder-looking, and I suspect that, unless the input S is of one of those special structures, the best approach is the naive one that takes O(n) time per query.


Proof that Entanglement Cannot Increase the Capacity of a Noiseless Classical Channel

It follows directly from our formula for entanglement-assisted capacity. An alternate proof uses the classical reverse Shannon theorem and the fact that entanglement does not increase the capacity of a noiseless classical channel. This last fact can be proved by showing that if it did, you could use entanglement to transmit information with no communication. I don't remember whether the alternate proof is in the linked reference or not.


Does the space hierarchy theorem generalize to non-uniform computation?

One non-uniform "space hierarchy" that we can prove is a size hierarchy for branching programs. For a Boolean function $f: \{0, 1\}^n \to \{0, 1\}$, let $B(f)$ denote the smallest size of a branching program computing $f$. By an argument analogous to this hierarchy argument for circuit size, one can show that there are constants $\epsilon, c$ so for every value $b \leq \epsilon \cdot 2^n / n$, there is a function $f: \{0, 1\}^n \to \{0, 1\}$ such that $b - cn \leq B(f) \leq b$.

I think separating $\mathbf{PSPACE}/\text{poly}$ from $\mathbf{L}/\text{poly}$ would be difficult. It's equivalent to proving that some language in $\mathbf{PSPACE}$ has super-polynomial branching program complexity. A simple argument shows that $\mathbf{PSPACE}$ does not have fixed-polynomial-size branching programs:

Proposition. For every constant $k$, there is a language $L \in \mathbf{PSPACE}$ so that for all sufficiently large $n$, $B(L_n) > n^k$. (Here $L_n$ is the indicator function for $L \cap \{0, 1\}^n$.)

Proof. By the hierarchy we proved, there is a branching program $P$ of size $n^{k + 1}$ that computes a function $f$ with $B(f) > n^k$. In polynomial space, we can iterate over all branching programs of size $n^{k + 1}$, all branching programs of size $n^k$, and all inputs of length $n$ to find such a branching program $P$. Then we can simulate $P$ to compute $f$.


Factoring assuming smoothness of some numbers

See my paper with Eric Bach, "Factoring with cyclotomic polynomials", where we show that if the cyclotomic polynomial $\Phi_k(p)$ is $B$-smooth for any $p$ dividing $N$, then we can factor $N$ in time polynomial in $\log N$ and $k$ and $B$.  In particular this gives a $(p+1)$-method (see the earlier work of Williams) and $(p^2+1)$ method.

http://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989-0947467-1/S0025-5718-1989-0947467-1.pdf


Minimizing a submodular function given noisy oracle access

A FOCS'15 paper by Lee, Sidford, and Wong [LSW15] can be leveraged to obtain such minimization guarantees -- cf. Section 5 (specifically, Corollary 5.4) in our recent paper ([BCELR16]).

  Corollary 5.4. Let $g\colon 2^{[m]} \to \mathbb{R}$ be a submodular function. There exists an algorithm that, when given access to an approximate oracle $\mathcal{O}^{\pm}_g$ for $g$, and for input  parameters $\xi, \delta\in(0,1)$,  returns with probability at least $9/10-2\delta$ a value $\nu \in \mathbb{R}$ such that $\nu\leq \min_{S \subseteq [m]} \{g(S)\} + \xi$.

  The algorithm performs $m\log\left(\frac{mM}{\xi}\right)$ calls to $\mathcal{O}^{\pm}_g$ with parameters $\frac{\xi^2}{128m^5M^2}$ and $\frac{\delta}{Cm^2\log\left(\frac{mM}{\xi} \right)}$, where $M\stackrel{\rm def}{=} \max\left\{{2}\max_{S \subseteq [m]}\{\lvert{g(S)}\rvert\},\xi/2 \right\}$ and $C>0$ is an absolute constant.

  The running time of the algorithm is
  $$
O\!\left( m^2\cdot \Phi_g\left( \frac{\xi^2}{128m^{5}M^2}, \frac{\delta}{Cm^2\log\frac{mM}{\xi}} \right)\log{\frac{mM}{\xi}}  + m^3 \log^{O(1)}\frac{mM}{\xi}\right) \;,
$$
  where $\Phi_g$ is the running time of $\mathcal{O}^{\pm}_g$.

[LSW15] A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong. FOCS'15. http://arxiv.org/abs/1508.04874

[BCELR16] Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron. arXiv, 2016. https://arxiv.org/abs/1607.03938


One Generalization of Graph Isomorphism Problem

I wasn't able to figure out whether $\mathrm{GI}(1/2)\in\mathsf P$, but here is a weaker result: The languages $\mathrm{GI}(1/2)$ and $\mathrm{GI}$ are not $\mathsf P$-inseparable.

Proof: It suffices to show the first reverse inclusion in
$$\mathrm{GI}(1/2)\supseteq\{(G,H): |V_G|=|V_H|, |E_G|=|E_H|\} \supseteq \mathrm{GI}(1)=\mathrm{GI}.$$
Let $p$ be the probability that $(a,b)\in E_G$ for uniformly random $a$, $b$.

Let $\Psi:V_G\to V_H$ be a uniformly random function and also let $a$ and $b$ be selected randomly, with $\Psi$, $a$, $b$ mutually independent.
Then the two events
$$\mathscr U = \{(a,b)\in E_G\}\text{,}\quad \mathscr V=\{(\Psi(a),\Psi(b))\in E_H\}$$
are independent. Therefore
$$\Pr_{\Psi,a,b}(\mathscr U\leftrightarrow\mathscr V)=p^2+(1-p)^2\ge 1/2.$$

So by Fubini's Theorem there is some $\psi$ such that
$\Pr_{a,b}(\mathscr U\leftrightarrow\mathscr V\mid \Psi=\psi)\ge 1/2.\qquad\Box$


Diving straight into "research" versus studying broadly as an undergrad (soft question)

[This is really a comment, but too long to fit in a comment field.]

You seem to be exceptionally well prepared compared to most students at the end of your freshman year.  And I'm not sure what you mean by "research" or "publication".  But, by the common meaning of the words in theoretical CS, I would say that the goal of a PhD is to learn to do independent research leading to publication, and that, as a rule, achieving that goal requires a lot of hard work, time, and usually help from an advisor, spread over more than four years of graduate study.  This is why a typical REU (research experience for undergrads) does not have this goal, but instead will allow you to work as a team member in a larger group, or perhaps with an advisor on a smaller project, with the more limited goal of gaining some initial exposure to the process.  (Even MS students rarely do original, published research.)  Can you find any summer REU opportunities to apply for?  They could be at another school.

I'm not sure what to say about "depth" vs "breadth".  I would guess that, at your stage, your fastest way to develop is to complete your undergraduate TCS courses, and take some graduate-level TCS courses if you can.  You may be able to work through some of the undergraduate material on your own in the summer (maybe that's your "studying broadly").  Meanwhile, if there is some degree of TCS community in your school, or nearby, you could try to connect with it.  Find students (including grad students) and a few faculty to cultivate relationships with, and find out what kind of research projects are going on nearby.  A big part of learning to do research is becoming part of the TCS community, learning its norms, and what is currently of interest.  Over the years I've known a small number of students who had an idea they wanted to pursue, and tried to start research on their own, and while I'm sure some have enjoyed the experience, the usual outcome (by an academic / professional standard) is to fall short, for all kinds of reasons.


The computational complexity of spectral norm of a matrix

The answer to your question is the contents of section 1.3.2, titled "[w]hen $\mathcal{P}_{p,r}$ is known to be difficult". (Here $\mathcal{P}_{p,r}$ is the problem of computing the norm $\|A\|_{p,r} = \sup_{\|x\|_p=1} \|Ax\|_r$.) According to that section, the only cases which are known to be difficult are $\mathcal{P}_{\infty,1},\mathcal{P}_{\infty,2},\mathcal{P}_{2,1}$. For example, $\mathcal{P}_{\infty,1}$ (even restricted to positive semidefinite matrices) is a generalization of MAX CUT. Since $\|B'B\|_{\infty,1} = \|B\|_{\infty,2}^2$, $\mathcal{P}_{\infty,2}$ is also hard. Finally, $\mathcal{P}_{2,1}$ is as hard as $\mathcal{P}_{\infty,2}$ as part of the more general observation (proved in section 1.3.1) that $\mathcal{P}_{p,r}$ is as hard as $\mathcal{P}_{1/(1-1/r), 1/(1-1/p)}$.

The thesis goes on to prove that $\mathcal{P}_{p,r}$ is hard whenever $p > r$ - this is the chapter you were reading (chapter 2).

Section 1.3.1 described some easy cases: $\mathcal{P}_{1,\ast}$, the symmetric $\mathcal{P}_{\ast,\infty}$, and the case that MCH mentioned, $\mathcal{P}_{2,2}$. Section 1.3.3 covers some approximability results, several novel of which are described in section 1.4 and the remaining chapters.

The title of section 1.3.2 appears in the table of contents (page iii) - just a hint for next time.


reference request- property of subset of rows in a matrix

Your problem can be solved in polynomial time, by reduction to bipartite matching.  In other words, there is a polynomial-time algorithm to find the largest subset $S$ of rows with your desired property.

Construct an undirected bipartite graph with $m$ left-vertices (one per row) and $n$ right-vertices (one per columN).  Add an edge $(i,j)$ whenever $M_{i,j} \ne z_j$.  Now each subset of rows with your property corresponds to a matching in this bipartite graph: take $S$ to be the set of left-vertices covered by the matching.  In particular, the maximum matching in this graph corresponds to the largest subset of rows that satisfies your property.  You can compute the maximum matching in polynomial time.


What type system fits the subclass of λ-terms that can be reduced optimally?

I think that the type system you want is elementary affine logic with fixpoints.

A distinctive feature (actually, the distinctive feature) of light logics, including elementary linear/affine logic, is that types do not ensure termination: unlike usual logical system, cut-elimination follows from a structural property of proofs (namely, stratification), the logical complexity of formulas does not play any role.  Types in EAL only give you well-formedness properties (like progress, i.e., normalization doesn't get stuck; or the fact that the normal form will have a certain shape).

The fact that cut-elimination holds regardless of types means that you can add arbitrary type fixpoints to EAL and you still get normalization with the same complexity bounds (elementary), because you still have stratification.  With type fixpoints, Scott numerals get the following type:

$$\mu \beta.\forall \alpha.(\beta\multimap\alpha)\multimap\alpha\multimap\alpha$$

A paper that uses EAL+type fixpoints explicitly is

Patrick Baillot. On the expressivity of elementary linear logic: Characterizing Ptime and an exponential time hierarchy.
Information and Computation 241: 3-31, 2015.

You will find formal definitions there.  However, I am afraid that no implementation exists.


This is one of the problems (very briefly) discussed by Valiant, "The Complexity of Enumeration and Reliability Problems", SIAM J. Comput. 1979, doi:10.1137/0208032. See the mention of "elementary cycles" near the top of p. 417. Valiant gives a Turing reduction from the number of Hamiltonian cycles.


Partitioning a set of 2d polygons into intersection-connected subsets

What you want is to find the connected components of the intersection graph of the polygons, right? It would help to be more clear about what counts as an intersection: do the boundaries have to cross or does one polygon entirely inside another count as an intersection? And can the polygons have holes?

Regardless, a natural lower bound for running times for the problem is $\Omega(n^{4/3})$ where $n$ is the total number of segments in the input. Any faster and we could also improve the known time bounds for Hopcroft's problem of detecting an intersection between $n$ given points and $n$ given lines: expand each point into a small polygon (not so large that it intersects any line it didn't before) and test whether any of these expanded points belongs to a nontrivial connected component. This lower bound is mentioned briefly in my paper "Testing Bipartiteness of Geometric Intersection Graphs" which uses it to argue that bipartiteness of intersection graphs is strictly easier than connectivity; it in turn cites Jeff Erickson's paper "New lower bounds for Hopcroft’s problem", which proves an $\Omega(n^{4/3})$ lower bound in a reasonable but limited model of computation.


Ed. Witten's new paper and the simulation of a quantum field theory

To complement what Joe wrote, and maybe explain this question a bit more (without answering it!):

The computational complexity of simulating "realistic" quantum field theories has been considered an open problem for a long time.  One of the main problems, as I understand it, is that (3+1)-dimensional QFTs aren't sufficiently well-defined mathematically for it to be clear what model of computation should correspond to them.

But the situation is different for the (2+1)-dimensional QFTs called topological quantum field theories (TQFTs).  For those, there is a rigorous mathematical description based on the Jones polynomial, due to Witten from the 1980s.  It's that description that led to the deep and celebrated result of Freedman, Kitaev, Larsen, and Wang, which showed that simulating TQFTs is indeed BQP-complete, as one would hope and expect (see Aharonov, Jones, and Landau for a more computer-scientist-friendly version).  This remains essentially the only rigorous result we have about the computational complexity of quantum field theory.

Now, the questioner is asking whether some new work by Witten could give a handle on the computational complexity of (3+1)-dimensional QFTs.  I don't know the answer to that, but it seems obvious that whatever it is, it would involve a significant research effort, and probably not fit within the margins of CS Theory StackExchange. :-)

Addendum (Oct. 12, 2013): I just saw this answer again, and I thought I should add a note that, shortly after I posted it, Jordan, Lee, and Preskill released an important paper showing how to simulate "φ4 theory" (a simple interacting quantum field theory) in quantum polynomial time, in any number of spacetime dimensions.  This doesn't directly address the OP's question, but it does render obsolete my comment about Freedman-Kitaev-Larsen-Wang remaining "essentially the only rigorous result we have about the computational complexity of quantum field theory."


According to this answer, "the space complexity of the algorithm" is polynomial when  2.5 < c .

That answer does not indicate the polynomial's exponent.


The notes from Salil Vadhan's class, "Pseudorandomness", are excellent for this purpose.  He is writing a textbook based on these.  The draft version of the book is available online.


Here are a few theoretical consequences of the equality FP=#P, although they have nothing to do with artificial intelligence.  The assumption FP=#P is equivalent to P=PP, so let me use the latter notation.

If P=PP, then we have P=BQP: quantum polynomial-time computation can be simulated by classical, deterministic polynomial-time computation.  This is a direct consequence of BQP⊆PP [ADH97, FR98] (and of an earlier result BQP⊆PPP [BV97]).  On top of my knowledge, P=BQP is not known to follow from the assumption P=NP.  This situation is different from the case of randomized computation (BPP): since BPP⊆NPNP [Lau83], the equality P=BPP follows from P=NP.

Another consequence of P=PP is that the Blum-Shub-Smale model of computation over the reals with rational constants is equvalent to Turing machines in a certain sense.  More precisely, P=PP implies P=BP(Pℝ0); that is, if a language L⊆{0,1}* is decidable by a constant-free program over the reals in polynomial time, then L is decidable by a polynomial-time Turing machine.  (Here “BP” stands for “Boolean part” and has nothing to do with BPP.)  This follows from BP(Pℝ0)⊆CH [ABKM09].  See the paper for definitions.  An important problem in BP(Pℝ0) is the square-root sum problem and friends (e.g. “Given an integer k and a finite set of integer-coordinate points on the plane, is there a spanning tree of total length at most k?”) [Tiw92].

Similarly to the second argument, the problem of computing a specific bit in xy when positive integers x and y are given in binary will be in P if P=PP.

References

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen.  On the complexity of numerical analysis.  SIAM Journal on Computing, 38(5):1987–2006, Jan. 2009.  http://dx.doi.org/10.1137/070697926

[ADH97] Leonard M. Adleman, Jonathan DeMarrais and Ming-Deh A. Huang.  Quantum computability.  SIAM Journal on Computing, 26(5):1524–1540, Oct. 1997.  http://dx.doi.org/10.1137/S0097539795293639

[BV97] Ethan Bernstein and Umesh Vazirani.  Quantum complexity theory.  SIAM Journal on Computing, 26(5):1411–1473, Oct. 1997.  http://dx.doi.org/10.1137/S0097539796300921

[FR98] Lance Fortnow and John Rogers.  Complexity limitations on quantum computation.  Journal of Computer and System Sciences, 59(2):240–252, Oct. 1999.  http://dx.doi.org/10.1006/jcss.1999.1651

[Lau83] Clemens Lautemann.  BPP and the polynomial time hierarchy.  Information Processing Letters, 17(4):215–217, Nov. 1983.  http://dx.doi.org/10.1016/0020-0190(83)90044-3

[Tiw92] Prasoon Tiwari.  A problem that is easier to solve on the unit-cost algebraic RAM.  Journal of Complexity, 8(4):393–397, Dec. 1992.  http://dx.doi.org/10.1016/0885-064X(92)90003-T


Criteria to determine if a complement of a graph has odd-holes

There is a structural result for odd-hole-free graphs by Michele Conforti, Gérard Cornuéjols, and Kristina Vušković:

  Decomposition of odd-hole-free graphs by double star cutsets and 2-joins, Discrete Applied Mathematics, 2004.

Basically what it says is either the odd-hole-free graph belongs to a kind of basic class, or we can decompose the graph into smaller pieces using two kinds of decompositions.  The proof of the strong perfect graph theorem follows the same spirit, and similar results are also known for various classes, e.g. even-hole-free graphs.

The interesting thing is that although the structural theorem of even-hole-free graphs leads to polynomial-time recognition algorithms (1, 2), the corresponding implication is not known for odd-hole-free graphs.  However if we add the restriction that the clique number is bounded then we do have such a result.

$^1$ The first decomposition-based algorithm.
$^2$ The fastest algorithm currently known.


What is the fastest known simulation of BPP using Las Vegas algorithms?

First, observe that if $\mathsf{BPP} \subseteq \mathsf{ZPTIME}[2^{n^{c}}]$ for some constant $c$, then $\mathsf{BPP} \neq \mathsf{NEXP}$. (Proof by nondeterministic time hierarchy.) So proving such an inclusion would be significant, not just because it's an improved simulation but also would yield the first progress on randomized time lower bounds in decades.

Next, consider the class $\mathsf{PromiseBPP}$, for which the following problem is "$\mathsf{PromiseBPP}$-hard":

  Circuit Approximation Probability Problem (CAPP):  Given a circuit $C$, output the acceptance probability of $C$ to within a $1/6$ additive factor.

Results of Impagliazzo, Kabanets, and Wigderson 2002 imply that a $2^{n^{\varepsilon}}$ time zero-error algorithm for CAPP (where $n$ is the size of $C$) would imply $\mathsf{NEXP} \not\subset \mathsf{P/poly}$. In STOC'10, I extended this to show: supposing for every $C$ with $k$ input bits and $n$ size, one can compute CAPP nondeterministically (so, zero-error suffices) in $2^{k-\omega(\log k)}\mathrm{poly}(n)$ time, then $\mathsf{NEXP} \not\subset \mathsf{P/poly}$. That is, there are certainly problems computable with two-sided-error randomness, for which zero-error algorithms that even mildly beat exhaustive search would imply circuit lower bounds. I believe this should be interpreted as a possible method for proving lower bounds; your mileage may vary.

Notice that even proving $\mathsf{RP} \subseteq \mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ is also open, and proving that would also imply lower bounds: by Kabanets and Impagliazzo 2004, if polynomial identity testing (a $\mathsf{coRP}$ problem) is in $\mathsf{ZPTIME}[2^{n^{\varepsilon}}]$ for all $\varepsilon > 0$, then we have lower bounds for either the Permanent or $\mathsf{NEXP}$. Recently (upcoming in STOC'13), I proved unconditionally that either $\mathsf{BPP} \subseteq \mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^{\varepsilon}$ or $\mathsf{RTIME}[2^n]$ has $n^c$ size circuits, building on the "easy witness" method of Kabanets. This implies two things:

There is a $c$ such that for all $\varepsilon > 0$, $\mathsf{RP}$ is unconditionally in $\mathsf{ioZPTIME}[2^{n^{\varepsilon}}]/n^c$ -- this is about the best unconditional derandomization of $\mathsf{RP/BPP}$ in $\mathsf{ZPP}$ that we know so far.
To start getting interesting subexponential simulations of $\mathsf{BPP}$, you "only" have to assume $\mathsf{RTIME}[2^n]$ doesn't have fixed-polynomial-size circuits.


A few questions about Object-Oriented Languages in general

The answers to these questions vary with the specific OO language. Here are some fairly generic answers.

Can methods contain free variables?
In general yes.

Are free variables statically-scoped?
It's complicated. As a general rule (with many exceptions), most variables are lexically-scoped, except that the self reference (e.g., this in Java) is  an implicit, dynamically-scoped variable. Many OO languages further rewrite function calls m() to a method invocation this.m() if m is known to be a method of the type of this.

Do method names live in a different name space than variables?
Yes. Method names are not variables: they may not be freely $\alpha$-renamed, since the actual text of the name constitutes part of the interface of an object. They are much more closely related to record labels or module component names. However, method names can interact with binding structure since many OO languages treat method invocations a bit specially (e.g., my answer to #2).


Head variables of terms after application

Here's a counterexample to your conjecture.

$$
\begin{array}{lcl}
M & : & ((0 \to 0 \to 0) \to 0 \to 0 \to 0) \to 0 \to 0 \to 0 \\
M & = & \lambda\,f\,x\,y.\;f\;(\lambda\,a\,b.\;f\;(\lambda\,u\,v.\;u)\;a\;b)\;x\;y
\end{array}$$

This beta-normal, eta-long with index 1. Now, consider the two following terms, both also of index 1:

$$
\begin{array}{lcl}
N & = & \lambda\,p\,x\,y.\;p\;x\;y \\
N' & = & \lambda\,p\,x\,y.\;p\;y\;x \\
\end{array}
$$

Now, $M\;N$ reduces to $\lambda\,x\,y.\;x$ (index 1) and $M\;N'$ reduces to $\lambda\,x\,y.\;y$ (index 2).


Canonical representation of Binary Decision Tree in Ptime?

I think that assuming that $\mathsf{NP} \not \subseteq \mathsf{SUBEXP}$, such a canonical representation does not exist. Proof: Suppose such a canonical representation does exist. Then the function $A \mapsto g(f(A))$ can be computed in polynomial time, so in particular, $|g(f(A))|$ is $\text{poly}(|A|)$. But if we take $B$ to be a minimal BDT equivalent to $A$, then $g(f(A)) = g(f(B))$, so $|g(f(A))|$ is $\text{poly}(|B|)$. Such an approximation algorithm implies that $\mathsf{NP} \subseteq \mathsf{SUBEXP}$, according to an answer on another post, if I understand correctly.


What is the relationship between $\mathsf{PLS}$ and $\mathsf{APX}$?

If one wants to approximate the potential function, then yes, there even exists a fully polynomial-time approximation scheme (FPTAS). See

James B. Orlin, Abraham P. Punnen, Andreas S. Schulz: Approximate Local Search in Combinatorial Optimization. SIAM J. Comput. 33(5): 1201-1214 (2004).

For some settings though, this is not interesting. For example, for congestion games, where pure equilibria exist and their computation is PLS-complete, strategy profiles that approximate the potential function well may be very poor approximate equilibria. For some settings, constant-factor approximate equilibria can be computed in polynomial-time even when computing an exact equilibrium is PLS-hard, for other settings it is PLS-hard to compute an approximate equilibrium for any polynomial-time computable non-trivial approximation factor, as explained by the following announcement paper.

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik: Computing approximate pure Nash equilibria in congestion games. SIGecom Exchanges 11(1): 26-29 (2012).

Note PLS might be much easier than FNP.


Finding a hamiltonian cycle in $G'$ given a hamiltonian cycle in $G$

I believe the answer is no and here is why.

Assume that I can efficiently find a hamiltonian cycle of minimum weight in $G'$ given a hamiltonian cycle of minimum weight in $G$. I can use this procedure to find a hamiltonian cycle in any graph, say $A$.

The procedure would work like this. Take $A$ and add vertices and edges (with weight $0$) such that a hamiltonian cycle of weight $0$ is easy to find. The cycle, for example, could alternate between new vertices and the original vertices of $A$. Since all new edges have weight $0$, the cycle weight would be $0$. If we call the new graph $A_1$, we know a simple hamiltonian cycle in $A_1$. Remove one of the newly added vertices from $A_1$ to create $A_2$ then run our procedure to efficiently find a hamiltonian cycle in $A_2$. Then repeat the procedure.

Eventually we will arrive at a graph, say $A_k$, which only has one extra vertex when compared to $A$. We will know a hamiltonian cycle in $A_k$ from the procedure above. So we can use this information to efficiently find a hamiltonian cycle in $A$ (using the same procedure as above).

Therefore, finding a hamiltonian cycle in $G'$ given one in $G$ must be at least as hard as finding a hamiltonian cycle in general.


To meet condition 1, $n$ must be even, so let's assume that it is. Then we can automatically achieve both conditions 1 and 2 by making an $n/2\times n/2$ matrix whose entries are $2\times 2$ submatrices in one of the two patterns
$$ \left( \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right),\quad \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right), $$
as these prevent any three consecutive digits (in either direction) from being equal.

Now all you need to do is to choose which of these two $2\times 2$ matrices to use in which position of the $n/2\times n/2$ matrix. You must now avoid both equal rows and columns, and complementary rows and columns, but that's still very easy, for instance by putting the 1-0-0-1 matrices down the main diagonal and the 0-1-1-0 matrices everywhere else.


Where to find info on (polytime) approximability of various discrete optimization problems?

The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: http://www.csc.kth.se/~viggo/problemlist/