If I understood well the problem, perhaps this is an idea for a reduction from the Hamiltonian path problem: given $G$ with $|V| = n$, a source and target node $s, t \in V$;  you can extend it adding a $(n-1) \times n$ "full" grid graph having the bottom-left node of the last row connected to $s$ and the bottom right node of the last row connected to $t$.

Then connect each of the $n-2$ remaining nodes of the last row to each of the nodes in $|V| \setminus \{s,t\}$ adding $(n-2)^2$ edges.

The resulting graph $G'$ has a graph minor of size $n \times n$ if and only if there is an Hamiltonian path from $s$ to $t$ in the source graph $G$.

In the following picture a no instance (left) and a yes instance (right) with the corresponding $n \times n$ grid graph minor.


Long Cycle in Bounded Tree-Width Graphs using DFS and Dynamic Programming

There is a nice trick to reduce $\geq k$ cycle to finding a cycle of length exactly $t$, for $t \leq 2k$ (I first heard of this trick from Daniel Marx). The key observasjon is that contracting an edge of $G$ may not increase the length of the longest cycle in G, and may only decrease the length by a factor at most two. Thus we can search for cycles of length exactly $t$ for $k \leq t \leq 2k$. If no cycle is found, contract an edge and repeat.

This shoukd be quite a bit faster than the treewidth based algorithms, I believe, especially if you use the sieving methods for finding t-cycles (paths). There are very efficient implementations for $k$-path by Bjorklund et al:

Fast Witness Extraction Using a Decision Oracle, with Andreas Björklund and Petteri Kaski
Proc. 22th Annual European Symposium on Algorithms (ESA 2014), LNCS 8737, 2014, pp. 149-160.

This should be adaptable to your problem.


Such functions can be typed in dependently typed programming languages (among others).

This is an example in Agda, a dependently typed language that looks similar to Haskell:

more : Nat -> Set
more 0 = Nat
more (S x) = Nat -> more x

sum : \forall {x : Nat} -> Nat -> more x
sum {0}   a = a
sum {S x} a = \lambda m -> sum {x} (m + a)

The function sum takes x natural numbers as arguments and returns with the sum of all arguments. The S in the pattern matches is the "successor" constructor on the natural numbers.

Note: Agda has a much nicer Unicode syntax, but most browsers can't display it correctly.


Polynomial algorithm for correlated equilibrium

The linear program for computing a correlated equilibrium in a game has size that is polynomial in the size of the game matrix: i.e. exponential in the number of players. The scheduling game that you describe is an $n$ player game, so the linear program will not be polynomially sized. However, it is a compactly represented game, so you can in principle use the Ellipsoid approach of Papadimitirou and Roughgarden.

If you are ok with an approximate correlated equilibrium, there are much simpler and easier to implement approaches based on no-regret algorithms. For a textbook exposition, check out Chapter 4 of Algorithmic Game Theory.


In his 1962 paper "The Maximum Connectivity of a Graph", Harary describes a way to construct for integers $p$ and $q$ with $q\ge p-1$ a way to construct a graph with $p$ vertices and $q$ edges  that is $k=\lfloor 2q/p\rfloor$-connected. Roughly, the idea is to give indices from $0$ to $p-1$ to the $p$ vertices and then add edges between vertices whose indices (modulo $p$) differ by at most $k/2$ (the exact construction depends on whether or not $2q/p$ is an integer).

One could start with these graphs and then perturb them by adding and removing edges without changing the connectivity. The graphs will not be bipartite, however.

Another easy way of creating random graphs with a certain edge-connectivity value is to exploit those cases in which edge-connectivity and minimum degree are identical since creating random graphs with a fixed minimum degree is much easier. Such conditions, also for bipartite graphs, are discussed for example in the paper On equality of edge-connectivity and minimum degree of a graph by Plesník and Znám.


Papers on using resource states to implement QFT efficiently

Here is a 2018 paper that uses phase gradient states and adders to optimize the T-count of the approximate QFT: "Approximate Quantum Fourier Transform with O(nlog(n)) T gates" by Nam et al.

(The careful reader may notice that the question precedes the paper by two years! That's because the question actually led to the paper, though indirectly. I mentioned the phase gradient operation as an application of efficient adders in this paper, Nam et al saw that, independently realized it would useful for the approximate QFT, and here we are full circle. Oh, and of course Kitaev scooped everyone by over ten years. He mentions the adding-into-phase-gradient technique in a textbook from 2002 [page 133].)


Independent set size in triangle-free graphs

If you don't care about the constants, then the answer is 'yes' by an easy reduction:

Take a triangle-free graph $G$ with average degree $d_{avg}$. Create a new graph $G'$ which is obtained from $G$ by deleting all vertices with degree $\ge 2d_{avg}$. Obviously, any independent set in $G'$ is an independent set in $G$, and $G'$ is triangle-free. Also, the number of vertices in $G'$ is at least $n(G)/2$. Now we can apply the Alon--Spencer proof.


Do we know a specific $L_{ZFC}$ such that $K(s) \ge L_{ZFC}$ is unprovable in ZFC for all strings $s$?

(Note: This answer works for most any consistient theory, not just $ZFC$.)

We will define a machine $p$ based on the universal algorithm. $p$ does a search, looking for a string that represents a proof of a statement of the form "not ($p$ halts and outputs $n$)" (note that this requires quining, since it is self-referential), for some numeral $n$, such that the proof is valid in ZFC. When it finds such a proof, it outputs $n$.

Lemma: For any numeral $n$, if ZFC is consistient, ZFC does not prove the statement "not ($p$ halts and outputs $n$)".

Assume to the contrary that for some $n$, ZFC proves "not ($p$ halts and outputs $n$)". Then $p$ will find this proof, output $n$, and halt. Moreover, since $p$ must halt in a finite amount of time, we can construct a step by step proof of this in ZFC. That is, we can prove "$p$ halts and outputs $n$" in ZFC. This is a contradiction in ZFC, but ZFC is consistient by assumption. Therefore ZFC does not prove the statement "not ($p$ halts and outputs $n$)" for any numeral $n$.

Now, formalize $p$ into a program $\rho$. Let $$L_\text{ZFC} = |\rho|+1$$ Suppose that $ZFC$ proves for some $s$ that $K(s) \ge L_\text{ZFC} \gt |\rho|$. This implies that the machine that $\rho$ encodes, $p$, does not output $s$. But by the lemma, ZFC can not prove this! Therefore, there is no $s$ such that ZFC proves $$K(s) \ge L_\text{ZFC}$$

Now all that needs to be done is to actually create $\rho$ in some programming language, but we will leave that as an exercise to the programmer.


Detecting infeasibility of System of Linear Inequalities

(1) Farkas' Lemma should show the equivalence of the infeasibility problem and LP in strongly polynomial time.

(2) Solving a linear programming problem (as a computational problem) usually means "detect the problem is either infeasible, unbounded, or having an optimal solution, and if the problem has an optimal solution, find one".  In this sense, they are equivalent.


Circuit lower bounds and kolmogorov complexity

There is nothing wrong with your argument, but there is no contradiction. You prove that from some large enough $N$ the Kolmogorov complexity of the spectrum of $f_n$ is always at least $T$. But this statement is trivially true! Although we cannot prove that the Kolmogorov complexity of one string is large, if we have a sequence, then from some point it must contain only strings of large complexity. So what is this $N$ that you got? It must satisfy $N>g^{-1}(c \cdot BB(T))$, what is a number that we cannot compute (because of $BB$), so there is no problem at all.


I don't know whether this problem has been studied but I think its #P-hardness should follow directly from the #CSP dichotomy established by Bulatov (Bulatov JACM'13), later  simplified by Dyer and Richerby (Dyer and Richerby SICOMP'13). In particular, your problem is equivalent to a CSP with a constraint language on the domain D := {1,2,3} with a single binary relation R in the language defined by R := D^2 \ {(1,2),(2,1)}; i.e., all tuples but (1,2) and (2,1) are allowed. A necessary (but not sufficient) condition for tractability is admitting a Mal'tsev polymorphism, which is a ternary operation f:D^3 -> D satisfying, for all a,b in D, f(a,b,b)=f(b,b,a)=a and preserving membership in R. If you take tuples (1,3), (3,3), and (3,2), they all belong to R but any Mal'tsev polymorphism would have to return (1,2) as 1=f(1,3,3) and 2=f(3,3,2) [applying f on the columns if viewing the tuples as rows of a 3x2 matrix]. However, (1,2) is not in R, which is a contradiction.

If I remember correctly, the required result (the necessity of a Mal'tserv polymorphism for tractability of #CSP) is probably established already in Bulatov and Dalmau IC'07 but you may find the other two papers also useful.


Why is it difficult to develop a subexponential functoral approach to discrete log

The reason that sub exponential algorithms for the discrete log in $\mathbb{Z}/p\mathbb{Z}$ do not carry over to groups based on elliptic curves is because $\mathbb{Z}/p\mathbb{Z}$ has extra structure that doesn't seem to be present in elliptic curve groups.

In particular, $\mathbb{Z}/p\mathbb{Z}$ has both addition and multiplication, whereas the elliptic curve groups have only one operation.  The sub exponential algorithms for the discrete log in $\mathbb{Z}/p\mathbb{Z}$ make essential use of this: the extra structure allows us to define the notion of a smooth integer.  A smooth integer is an integer that factors into small primes; here the notion of "small" makes use of this additional structure (namely, the addition operation).  This notion of smoothness is critical to the effectiveness of the sub exponential algorithms for $\mathbb{Z}/p\mathbb{Z}$.

Any discrete log algorithm that relies upon "smoothness" (or this additional structure) is therefore not going to be "functoral".  A consequence is that the best existing techniques we know of for computing the discrete log in $\mathbb{Z}/p\mathbb{Z}$ are not functoral and do not carry over to elliptic curve groups.

Why is it hard to develop an efficient functoral algorithm for the discrete log in $\mathbb{Z}/p\mathbb{Z}$?  Because if you want it to be functoral, you're disallowing use of smoothness, which is essential to all known techniques.

See, e.g., http://en.wikipedia.org/wiki/Index_calculus_algorithm and http://en.wikipedia.org/wiki/Number_field_sieve.

Here is a second hurdle to functoral algorithms.  There are known lower bounds on the discrete log problem in "black box" groups.

A black box group is one where we do not have an explicit representation of group elements.  Instead, all we have are a few black boxes: a black box that, given two group elements, returns their product; a black box that, given a group element, returns its inverse; a black box that returns a random element of the group; and so on.  In particular, in a black box group, you cannot do something like "look at the third bit of the representation of the group element and branch based upon whether it is 1 or 0".  You also can't access any additional structure (since you're only given a black box for the group operation; it's a black box group, not a black box ring).

In this setting, it is known that, if the group is of order $p$ where $p$ is a prime, there is no generic algorithm for the discrete log whose running time is better than $\Theta(\sqrt{p})$.  I'm not 100% clear on how you plan to define "functoral", but it looks to me like this implies you cannot expect a functoral algorithm whose running time is sub exponential.

See, e.g., the following paper:

Lower Bounds for Discrete Logarithms and Related Problems.  Victor Shoup.  EUROCRYPT '97.


Computationally bounded version of Nash equilibrium?

I can't think of any way there could be an easy, completely elegant/satisfying answer to this question, particularly because the ending payoff is so hard to compute; however, my thoughts are too lengthy to post as a comment.

The best idea I have is this:  In the case of chess, try approximating the probability that White will win based on White's material advantage (i.e., extra pawns, knights, etc.) for a given position by randomly selecting positions with that exact amount-of-material configuration.  Perhaps in the case of "all-rooks chess," we could say, "How likely is White to win with 8 rooks to Black's 17 rooks?"  Perhaps this probability is 4%; to calculate it, we would have to examine (say) 1000 different randomly generated chess positions that have 8 white rooks and 17 black rooks, and then look ahead (say) 10 moves deep in every case, and see what the new material configuration is.  Then, take the expected odds based on the material configuration at the end, and force each side to select the path that involves each side taking the best possible option at every turn, given the expected odds at the end.

Of course, it would be necessary to find the material configuration for every relevant possibility (M,N) of M white rooks to N black rooks...presumably starting at the lowest ordered pair (M=1,N=1) and working up from there.

For the original position, don't just go with the statistic you get (i.e., if the original position has (M=6,N=7) rooks, don't just assume that White has a 25% chance of winning because that's the expected odds of victory for (6,7)); instead, because you can be more precise, look 10 moves deep as usual with just this one position and find every possible ending position.  Then, find the right path (that involves optimal play by both sides) to a 10-moves-deep-configuration, and select this path's expected odds as the expected odds of the original position.

I think this process can be done in polynomial time.  Looking k moves deep for fixed k in chess is polynomial in the size of the board, and the total number of white and black rooks is expressed in unary (in a sense) because that number must be smaller than the size of the board.

If this sounds complicated and hard to explain, that's because it is.  A more succinct summary of what I'm describing is:  Use recursion and basic statistics to calculate the odds of victory for white given M white rooks and N black rooks on the board.  Then use these values to look k moves deep and ascertain the odds that White will win in the original position.

Final comment:  I think this problem is also interesting for non-EXPTIME-complete games, such as tic-tac-toe, which according to Wikipedia is PSPACE-complete.  Further, I believe a process like the one I described above could also be useful there too, although obviously it would be impossible to have a "material" advantage in tic-tac-toe; there would have to be some other basis for judging the superiority of X's or O's position.


One example of what you might call non-linear clustering is kernel-based clustering, where the similarity function is described by a (non-linear) kernel function. This is a weak form of non-linearity, since there's a lifting map that makes everything linear (albeit in a Hilbert space)


Maximum shortest word accepted by pushdown automata

The precise answer depends on your model of PDA (models differ among different authors; compare Sipser to Hopcroft &Ullman).  And number of states alone is not a good measure for PDA's, because there is a well-known tradeoff between states and stack symbols.  For example, a classic construction turns a grammar like

$S \rightarrow X_1 X_1$

$X_1  \rightarrow X_2 X_2$

$X_2 \rightarrow X_3 X_3$

...

$X_{n-1} \rightarrow X_n X_n$

$X_n \rightarrow a$

into a 3-state machine accepting the language $\{\,a^{2^n}\,\}$ by final state, no matter how many variables there are, or into a 1-state machine accepting by empty stack.  This gives a classic example of how the shortest string can be exponential in the description size of the PDA.


Easy decision problem, hard search problem

Given an integer, does it have a non-trivial factor? -> Non-trivially in P.

Given an integer, find a non-trivial factor, if there is one -> Not known to be in FP.


I think that this definition is nowadays known under the term space-constructible function. There are functions in sublogarithmic space that are space constructible, while others are not.

http://dl2.acm.org/citation.cfm?id=31171 Andrzej Szepietowski: There are no fully space constructible functions between log log n and log n. Information Processing Letters 24(6),361-362.


Sparse subgraph preserving rooted edge connectivity up to $k$

Let $d^+_G(x)$ be the in-degree of $x$ in graph $G$.

Theorem (Lovász 1973):
For a directed graph $G$ and a specified vertex $r$, there exist a subgraph $G'$ with the property that $d^+_{G'}(x) = \lambda(r,x,G') = \lambda(r,x,G)$.

The desired sparse graph exists, as we can keep removing edges to reach a minimal graph with the desired connectivity property.


Complexity of type-checking in relation to complexity of normalization

The relationship that you're looking for is indeed well-defined, but IMO it's not quite the right thing to look at. For example:

Type checking for terms in the simply-typed lambda calculus is linear time, but normalizing terms in the STLC exceeds any fixed tower of exponentials (i.e., $O(2^{2^{2^{\ldots n}}})$.
Type checking for System F is linear time, but normalization takes as long as any function definable in second-order arithmetic.
For $F^\omega$, typechecking exceeds any tower of exponentials (since you have to normalize simply-typed lambda-terms to do typechecking), but normalization is complete for higher-order arithmetic.
Type inference for rank-1 types (basically, ML-style types) is EXPTIME-complete, but normalization time is somewhere in between the STLC and System
F.
Type inference for intersection types is undecidable (because they characterize halting).

What's going on here is that once you add enough type annotations, typechecking gets easy. If you have to do inference, then the problem gets much harder. This hints that there's a connection between program analysis and evaluation, and the ability of intersection type disciplines to characterize normalization further hints that the key place to look is linear logic.

A good place to get an intuition is from David Van Horn and Harry Mairson's papers Flow Analysis, Linearity, and PTIME and Relating complexity and precision in control flow analysis.

These papers show that for a linear calculus, program analysis and evaluation coincide, because linearity makes the approximation of flow analysis exact.
So by taking a linear calculus and then carefully controlling how much contraction you have via intersection types, you can gain a rather fine control over the complexity of normalization. As you might expect, there is an awful lot of work in this space from the intersection types community.

So rather than trying to summarize it all and missing important references, I'll pick out one line of work I particularly like  (and thereby miss important references on purpose :). This is the work of Damiano Mazza on redoing classical complexity theory in a higher-order implicit complexity framework. Here are three papers I particularly like:

Church meets Cook and Levin. This re-does the famous Cook-Levin proof (that SAT is NP-complete) in an implicit complexity style. The key idea is that you can use affine lambda terms as a kind of "higher-order circuit", and then approximate regular lambda-terms using them.
This idea is explored further in Non-linearity as the Metric Completion of Linearity, which focuses just on this idea (apparently implicit in Girard).
Most recently at POPL this year, Mazza (with Luc Pellissier and Pierre Vial) showed how most linear intersection type systems arise from a general framework for refinement types introduced by Noam Zeilberger and Paul-André Melliès, in their paper Polyadic Approximations, Fibrations and Intersection Types.

I want to emphasize that this is not comprehensive -- chase the references in these papers!


L. Fortnow. Counting complexity. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 81-107. Springer, 1997

This gives more of the structural complexity point of view (complexity classes, oracles, etc.), and discusses other classes related to #P. Although it's from almost 15 years ago, it's really not that out of date in terms of results.


Chromatic number of G+v where G is a cograph

I think Artem is on the right track with perfection:

As cographs are $P_4$-free, cograph+v is $C_5$-free (and $C_{2k+1}$-free and $\overline{C}_{2k+1}$-free, $k>1$) and so they are perfect graphs.

This means the only thing that is pushing the chromatic number up is clique size. So if $\chi(G+v) = \chi(G) + 1$, it is because v has increased the maximum clique size, which means that $N(v)$ must have had a clique of size $\chi(G)$ and so $\langle N(v)\rangle_G$ had the same chromatic number as $G$.

So it seems the statement in question 1 is true.

But even without it, since cograph+v can't have any large induced cycles, it is contained in the set of weakly chordal graphs. A graph $G$ is a weakly chordal graph if for every cycle of length at least 5 in $G$ and $\overline{G}$, there is a chord. Weakly chordal graphs are a subset of perfect graphs and there are various efficient algorithms for a number of optimization problems on weakly chordal graphs, such as colouring.


Does zero integrality gap imply zero duality gap for certain problems?

Here is an instance that could be close to a counterexample to the
claim.

Consider the LP $P = \max \{ 1^T x \,|\, Ax \leq 1, x \leq 1, x \geq
0\}$ and its dual $P' = \min \{1^Ty + 1^Tz ~|~ A^Ty + z \geq 1, ~y
\geq 0, z \geq 0 \}$ for the $12 \times 6$ matrix

$ A =
\begin{bmatrix}
 1 & 0 & 0 & 0 & 0 & 1\\
 0 & 1 & 0 & 0 & 1 & 0\\
 1 & 1 & 0 & 0 & 0 & 0\\
 0 & 0 & 1 & 0 & 1 & 1\\
 0 & 1 & 0 & 0 & 0 & 0\\
 1 & 0 & 0 & 0 & 1 & 0\\
 0 & 0 & 0 & 0 & 0 & 1\\
 0 & 0 & 1 & 0 & 0 & 0\\
 1 & 0 & 0 & 0 & 1 & 0\\
 0 & 0 & 0 & 1 & 0 & 0\\
 0 & 1 & 1 & 0 & 0 & 1\\
 0 & 0 & 1 & 1 & 0 & 0
\end{bmatrix}\,.
$

An optimal solution of $P'$ is given by $y_1=y_2=y_{12}=1$ (all other
variables are zero), with the objective function value of $3$. The
Optimal solution of $P$ is given by the vector $x =
[0.5~0.5~0~1~0.5~0.5]^T$. If you solve $P$ as an integer program, the
optimal objective function value is only $2$, and $x = [1~0~0~1~0~0]$
is an optimal solution.

In summary, the LP $P'$ has an integral optimal solution, but its
dual, $P$ does not have an integral optimal solution. The primal-dual
roles are reversed from the set up that Ankur wanted. But given the
nature of LP duality, this instance could still be considered a
counterexample to the general statement of the original claim.


Based on a fairly cursory inspection of their paper, IBM is clearly aware of the spatial locality. They seem to in fact have taken spatial locality into account when designing their simulation. They use spatial locality to put the states of local systems into primary memory, and record the whole state in secondary memory. If you can't contain the whole state of the quantum machine in your computer, you will have to keep recomputing pieces of the state, which is going to take much more time.

You have to trust both IBM and Google to have thought about the best way to do the simulation, and give accurate answers for how long a simulation would take. The researchers working at both these places are not stupid, and although it's quite possible that people will come up with better simulation methods eventually, they have indeed taken spatial locality into account.

Consider the paragraphs below taken from their paper, where it's clear that IBM uses spatial locality to make their simulation as fast as it is. Their simulation method is based on reference [14], which is turn is an extension of a simulation method discussed in [9]:

  The simulation method in [9] can be seen as a tensor slicing approach. Qubits (and the corresponding
  tensor indices) are divided into “global” qubits, which are sliced and used to address across processing
  nodes, and “local” qubits, corresponding to tensor indices used to address tensor slices stored on each
  processing node. In [9], circuits are partitioned so that all gates within a subcircuit can be applied to the
  local slice of the quantum state, without communicating quantum state information among processing
  nodes. Such zero-communication updates of a local quantum state are possible when all non-diagonal
  gates in a subcircuit are applied to local qubits only. ...

  The in-memory method that we presented in [14] considers circuit partitionings in which the resulting tensors either fit in available aggregate primary memory in their entirety, or their slices can be
  computed using available primary memory (using other tensors already computed and stored in primary memory). With this approach, the resulting tensors and/or their slices will generally be larger than the
  primary memories of individual processing nodes; this represents a difference between [14] and [9].

  As discussed in [14], we combine the zero-communication strategies of [9] with our own tensor
  partitioning strategy to leverage secondary storage when quantum states are too large to fit in aggregate primary memory.

  [9] T. Haner and D. S. Steiger. 0.5 petabyte simulation of a 45-qubit quantum circuit. In ¨ Proceedings of
  the International Conference for High Performance Computing, Networking, Storage and Analysis,
  SC ’17, pages 33:1–33:10, New York, NY, USA, 2017. ACM.

  [14] E. Pednault, J. A. Gunnels, G. Nannicini, L. Horesh, T. Magerlein, E. Solomonik, and R. Wisnieff. Breaking the 49-qubit barrier in the simulation of quantum circuits. arXiv preprint
  arXiv:1710.05867, 2017.

Of course, it's quite possible that you could design a better simulation by using more information about Google's Sycamore architecture. But you may need to use more sophisticated information about it than just locality.


What's the strict definition of random coins in streaming algorithm?

If you want something more formal, you can think of a streaming algorithm as a Turing machine with read-once random bits tape and working tapes whose total size is polylogarithmically bounded. So, you can store and reuse random bits, as long as you don't exceed your polylog memory bound.

From algorithms design perspective, designing and even understanding a streaming algorithm is usually a two-step process. First think of the streaming algorithm as a RAM that can magically reuse random bits, i.e. has access to a random oracle. Actually there are some papers that do propose algorithms in this random oracle model. But usually, the next step is to try to make the algorithm work with hash families with bounded independence rather than a true random oracle. The seed for such families is logarithmic in size, so you can afford to store it. For some fine examples of this, just check out the classical paper of Alon, Matias and Szegedy. Another, heavier hammer to use is Nisan's pseudorandom number generator, which also allows reducing the number of random bits needed to be stored down to polylogarithmic (but larger than you usually get from bounded independence). For an example of using Nisan's generator, look at Indyk's use of the Cauchy distribution to approximate the $\ell_1$-norm of a stream. Both papers are classic and good read.

Refs:
AMS: www.tau.ac.il/~nogaa/PDFS/amsz4.pdf

Indyk: people.csail.mit.edu/indyk/stream.ps


Not sure if I understand your problem correctly, but how about considering it as a flow network problem:

Consider all edges between $A$ and $B$ to be directed edges from $A$ to $B$, the capacity of such edges will be infinity.
Add a source $s$ from which an edge goes out to each of the vertices in A. The capacity of an edge $(s, a_i)$ where $a_i \in A$ is $w(a_i)$.
Add sink $t$, and from every $b_j \in B$ an edge $(b_j,t)$ with capacity $w(b_j)$.

A maximum flow algorithm will assign weights to the edges between A and B, and you're done (the common algorithms also guarantee that the weights are integers).


Has there been any research on $k$-SAT above the satisfiability threshold?

Yes, there has been. Moshe Vardi recently gave a survey talk at BIRS Theoretical Foundations of Applied SAT Solving workshop:

Moshe Vardi, Phase transitions and computational complexity, 2014.

(Moshe presents the graph of their experiment a bit after minute 14:30 in his talk linked above.)

Let $\rho$ denote the clause ratio.
As the value of $\rho$ increases beyond the threshold
the problem becomes easier for existing SAT solvers,
but not as easy as it was before reaching the threshold.
There is a very steep increase in difficulty as we approach the threshold from below.
After the threshold the problem becomes easier compared to the threshold but
the decrease in difficulty is much less steep.

Let $T_\rho(n)$ denote the difficulty of the problem w.r.t. to $n$
(in their experiment $T_\rho(n)$ is the median running-time of GRASP on random 3SAT instances with the clause ratio $\rho$).
Moshe suggests that $T_\rho(n)$ changes as follows:

$\rho \ll$ the threshold: $T_\rho(n)$ is polynomial in $n$,
$\rho$ is near the threshold: $T_\rho(n)$ is exponential in $n$,
$\rho \gg$ the threshold: $T_\rho(n)$ remains exponential in $n$ but
the exponent decreases as $\rho$ increases.


Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm

The question seems somewhat under-specified in the sense that it did not specify the desired error probability of the procedure. Assuming one means constant error probability, then the above is indeed the best I know. For a detailed discussion see Sec 2.5.2.4 in my book "The Foundations of Cryptography - Volume 1" available at http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html

THE ABOVE IS WRONG. SEE CORRECTED ANSWER BELOW.

Prop 2.5.6 in the aforementioned section proves a much better bound:
The algorithm runs in expected time $O(n \log^3(1/\epsilon))$
times the running time of the guessing procedure
(see improvement from $n^2$ to $n$ in the comment right after the proof)
and is correct w.p. $\Omega(\epsilon^2)$. Hence, correctness w.p. $2/3$
is obtained in time (factor) ${\tilde O}(n/\epsilon^2)$, which is optimal in some sense
(see Exer 30).


Examples of hard instances for Goemans and Williamson algorithm

I guess this reference is about what you ask:

  N. Alon, B. Sudakov, and U. Zwick. Constructing worst case instances for semidefinite programming based approximation algorithms. SIAM Journalon Discrete Mathematics, 15:58–72, 2002.

This is an excerpt from it (p.60):

  ... we present the construction of the
  graphs that show that the local analysis of the MAX CUT algorithms of [GW95]
  and [Zwi99] are tight.


Is this vertex ordering optimization NP-Hard?

Consider your problem restricted to 3-regular graphs. Consider some ordering of the vertices. Define a split vertex to be a vertex $v$ such that both $succ(v)$ and $pred(v)$ are non-empty and define a non-split vertex to be any other vertex. Notice that in a 3-regular graph, the value of $|succ(v)| \times |pred(v)|$ is $0$ if $v$ is a non-split vertex and is $2$ otherwise.

Thus, $\sum\limits_{v\in V}|succ(v)|\times|pred(v)| = 2n_{\text{split}}$ where $n_{\text{split}}$ is the number of split vertices.

Therefore, in 3-regular graphs, solving your problem (minimizing the summation) is equivalent to choosing an ordering so as to minimize the number of split vertices.

The following theorem tells us that solving your problem in 3-regular graph $G$ is equivalent to solving Max Cut in $G$. Therefore, since Max Cut in 3-regular graphs is NP-hard, so is your problem.

Theorem If $G = (V, E)$ is a 3-regular graph with $n$ vertices then there exists an ordering of the vertices such that the number of split vertices is at most $k$ if and only if $G$ has a cut of size at least $\frac{3}{2}n - k$.

First direction

First, suppose there exists on ordering of the vertices such that the number of split vertices is at most $k$. Then we partition $V$ into two sets $A$ and $B$ as follows:

Place all non-split vertices (under the ordering) into $A$ and $B$ by putting the vertices with 3 successors into $A$ and the vertices with 3 predecessors into $B$.
Tentatively add all split vertices (under the ordering) into $A$.
Repeat steps 4 and 5 until step 4 fails:
Identify a split vertex $v$ that has more neighbors in its current set ($A$ or $B$) than in the other
Move $v$ to the other set

The partition of $V$ into $A$ and $B$ is a cut, and each occurrence of steps 4 and 5 increases the size of that cut, so this procedure will terminate. Below we compute the size of the resulting cut.

Notice also that each split-vertex $v$ in $A$ (or $B$) has at most one neighbor in $A$ (or $B$) because otherwise this vertex would have been identified in step 4 at the final iteration of the loop. Thus, the number of edges incident on split vertices that are within $A$ or within $B$ is bounded above by the number of split vertices (which we know is at most $k$).

Next consider any edge $(u, v)$ that is not incident on a split vertex. This edge must then be between two non-split vertices. Suppose wlog that $u$ is earlier than $v$ in the ordering. Then since $u$ is a non-split vertex with a successor, it must be the case that $u$ actually has 3 successors, and similarly $v$ must have 3 predecessors. We can conclude from this that $u$ is placed in $A$ and $v$ is placed in $B$, and therefore that $(u, v)$ is not an edge within $A$ or within $B$.

Thus, we conclude that the overall number of edges within $A$ or within $B$ is at most $k$. Then the size of the cut (i.e., the number of edges not within $A$ and not within $B$) is at least $|E| - k = \frac{3}{2}n - k$.

Second direction

Now suppose there exists a cut of size at least $\frac{3}{2}n - k$. Suppose this cut partitions $V$ into sets $A$ and $B$. Then we construct an ordering of the vertices in $V$ by putting the vertices in $A$ first and the vertices in $B$ later. We claim that the number of split vertices under this ordering is at most $k$.

Consider any edge incident on a vertex in $A$. If this edge is $(u, v)$ with $u \in A$ and $v \in B$ then $v$ is a successor of $u$ since all vertices in $B$ are after all vertices in $A$. Thus, edges between $A$ and $B$ do not contribute any predecessors to any vertices in $A$. The only other possible edge incident on a vertex in $A$ is an edge within $A$. Such an edge contributes a predecessor to exactly one of its endpoints. Thus, the total over all $v \in A$ of the number of predecessors of $v$ is at most the number of edges within $A$, and so the number of vertices in $A$ with a predecessor is at most the number of edges within $A$. Since every split-vertex in $A$ is a vertex in $A$ with a predecessor, the number of split-vertices in $A$ is at most the number of edges within $A$.

Analogous logic can be used to show that the number of split-vertices in $B$ is at most the number of edges within $B$. Then the total number of split vertices under this ordering is at most the number of edges within $A$ or within $B$. Since the cut has at least $\frac{3}{2}n - k = |E| - k$ edges between $A$ and $B$, it must have at most $k$ edges within $A$ or within $B$. We conclude that the number of split vertices under the constructed ordering is at most $k$.


Why do Agda and Coq disagree on strict positivity?

The issue seems to be confusion resulting from a confluence of two factors:

I was using a stale version of Agda (2.3.0.1).  It appears that prior to 2.3.2, Agda simply wasn't checking strict positivity of the indices of constructor results (see the bug I linked elsewhere in the thread).
A closer reading of Dybjer's Inductive Families paper suggests that he may have intended that the inductive type being defined not be bound when typing the indices of a constructor result.  Section 3.2.1 gives the scheme for inductive constructors in prose, and apparently I misread the language describing the binding environments of each portion of the scheme.

This closer reading is of course consistent with the check that Coq and (recent versions of) Agda perform, that prohibit any appearance of T in its own indices.


Is there a way to solve or approximate the concave program with separable objective?

I special cases of this problem are a convex optimization problem. If x_i>0, then the objective is a posynomial. If the polytope can be described using posynomials, then the problem becomes a convex optimization problem.

See the tutorial at http://www.stanford.edu/~boyd/papers/pdf/gp_tutorial.pdf which discusses geometric programming and search for posynomial.

--clarification--

See page 73 of the above link.

If your polytope can be described by a posynomial, then you can solve the polytope as a convex programming problem, by converting the problem into an equivalent form.

    Given:
      Minimize f0(x)
      s.t.
      fi(x)<=0 for all i
      fj(x)=0 for all j

Where f0(x) is your original objective and fi(x) is your polytope.

Let x_k an element in x be equal to exp(y_k).
Now, an equivalent problem is cast as:

      Minimize log(f0(exp(y))
      s.t.
      log(fi(exp(y))<=0 for all i
      log(fj(exp(y))=0 for all j

The restriction here is that the only a subset of all polytopes will work in this formulation. However if you can find a reasonable approximation where the polytope is approximated by a set of posynomial constraints, then you will have a computationally fast solution.

--- additional comments ----

The only other approach which might be faster than solving the primal problem is to use KKT conditions to as implied by Ashwinkumar. You can try solving the dual formed from the KKT conditions. Depending on the structure of the polytope, you might be able to find the answer faster.

See http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions.


Compressing grammars by introducing ambiguity and left-recursion

Regarding your second question about succinctness, there is a nonrecursive tradeoff in grammar size when moving from general cfgs to unambiguous cfgs. See here:

Erik Meineche Schmidt, Thomas G. Szymanski:
Succinctness of Descriptions of Unambiguous Context-Free Languages. SIAM J. Comput. 6(3): 547-553 (1977)

EDIT (16/3/2019): answering to the comment, by introducing ambiguity, the resulting grammar will be nondeterministic, i.e. a general CFG. Imposing further restrictions on the given grammar, e.g. that the given CFG is LR(1), is of course not a suitable way to tame the tradeoff. Historically the first nonrecursive tradeoff to be shown was between finite automata and CFGs (Albert R. Meyer and Michael J. Fischer: Economy of Description by Automata, Grammars, and Formal Systems. SWAT 1971: 188-191). Completing the picture, there is also a nonrecursive tradeoff when moving from unambiguous CFGs to LR(1) grammars: Leslie G. Valiant:
A Note on the Succinctness of Descriptions of Deterministic Languages. Information and Control 32(2): 139-145 (1976)

EDIT (24/03/2019): answering to the other comment, if we restrict our attention to unambiguous finite automata, the gain in succinctness by introducing ambiguity will be at most exponential. In fact, a recent paper discusses a novel NFA minimization heuristics which merges equivalent states. A preprocessing step in the algorithm introduces additional transitions to the given automaton, which do not alter the accepted language ("saturation step"). The saturation step makes the automaton bigger, at least with respect to the number of transitions. And this step may introduce ambiguity. But the algorithm then contains a "quotienting step", which can allow for merging more states that are equivalent than without the saturation step. (The heuristics works for automata over infinite words and those over finite words.)

Clemente, Lorenzo and Mayr, Richard: Efficient reduction of nondeterministic automata with application to language inclusion testing. Logical Methods in Computer Science 15(1), 2019.


this is a pretty good discussion in this ref p123: Google's PageRank and Beyond:
The Science of Search Engine Rankings
Amy N. Langville & Carl D. Meyer, Princeton University Press.

  A final disadvantage of HITS is the problem of topic drift. In building the neighborhood graph $N$ for a query it is possible that a very authoritative yet off-topic page be linked to a page containing the query terms. This very authoritative page can carry so much weight that it and its neighboring documents dominate the relevant ranked list returned to the user, skewing the results toward off topic documents. Henzinger and Bharat suggest a solution to the problem of topic drift, weighting the authority and hub scores of the nodes in $N$ by a measure of the relevancy of a query [26].

ref [26] is apparently:

Improved Algorithms for Topic Distillation in a Hyperlinked
Environment Bharat, Henzinger, 21st ACM SIGIR Conference on Research and Development in Information Retrieval 1998

on p.2 they have another description/example of topic drift:

  We often find that the neighborhood graph contains documents not relevant
  to the query topic. If these nodes are well connected, the topic drift problem arises: the most highly ranked authorities and hubs tend not to
  be about the original topic. For example, when
  running the algorithm on the query jaguar and
  car the computation drifted to the general topic
  car and returned the home pages of different car
  manufacturers as top authorities, and lists of car
  manufacturers as the best hubs.


Edit: In the end I did find a reference for the reduction I remembered. It is given in Edge intersection graphs of single bend paths on a grid by Golumbic, Lipshteyn, and Stern. So, to sum up, the class of graphs obtained as intersections of paths on a grid contains all graphs. Therefore, path coloring on grids is as hard to approximate as graph coloring ($n^{1-\epsilon}$-hard).

Original answer:
Path Coloring can be reduced to graph coloring in the obvious way (make a vertex for each path, add an edge if two paths intersect). If the underlying graph in path coloring is allowed to be a grid there is also a reduction in the opposite direction, which means that in this case the problems are equivalent. The reduction does not change the number of colors, so all hardness of approximation results for graph coloring carry over to this case of path coloring, and therefore also when the underlying graph can be any graph.

I heard this reduction in a talk a while ago, but I can't seem to be able to find a reference, so I'll sketch it here.

We start with a graph $G(V,E)$ on $n$ vertices and the question is if it can be colored with $k$ colors. Construct a graph $H$ which is a $n\times ({n\choose 2}+1)$ grid (we index the rows by the vertices of $G$ and the columns by pairs of vertices of $G$). We will add one path in this graph for each vertex of $G$. Initially, each of these paths is simply a row of the grid, so no two of them intersect and they all have length $n\choose 2$. The idea here is that we will use the $n\choose 2$ edges between columns of the grid to simulate the edges of the original graph. For example, if vertex $i$ is connected to vertex $j$ in $G$, with $i<j$, take the path that runs through row $i$ and re-route it as follows: the path now goes from vertex $(i,(i,j))$ to $(j,(i,j))$, then it uses the next edge on the $j$-th row and then it goes back to row $i$. This creates an intersection between paths $i$ and $j$, but no other edge intersections. By adding the rest of the edges of $G$ this way, the resulting instance is $k$-colorable iff $G$ is.


Unfortunately, the best known depth reductions for Boolean circuits only work for very restricted classes of circuits. Valiant (Valiant; Viola) proved that a circuit of size $O(n)$ and depth $O(\log{n})$ can be computed by a depth-3 circuit of size $2^{O(n/\log\log{n})}$. Also, Valiant showed a similar depth reduction for linear size series-parallel circuits (a natural subclass of circuits), see Calabro.

Note that the number of gates in a depth-3 circuit computing a random function is $\Theta(2^{n/2})$ (Dančík; Sergeev), while the best lower bound we can prove is only $2^{\Omega(\sqrt{n})}$ (Håstad; Håstad, Jukna, Pudlák; Paturi, Pudlák, Zane; Boppana; Paturi, Pudlák, Saks, Zane; Meir, Wigderson).


Relation between computational complexity and information

There are enough connections between information theory and computational complexity to merit a graduate course, e.g. this one: http://www.cs.princeton.edu/courses/archive/fall11/cos597D/


What relations has different bounds for NP?

NP-complete problems can be polynomial-time reduced to each other via Karp/Cook/Levin reductions. Since polynomials are closed under composition, if there's a polynomial bound $f(\cdot)$ on the running time of an algorithm to solve NP-complete problem $A$, then for every NP-complete problem $B$ which reduces to $A$ in polynomial-time $g(\cdot)$, there will be an algorithm which solves  $B$ in time bounded by $f(g(\cdot))$ which is a polynomial.

This does not hold for bounds other than polynomial. For instance, if there's a $2^n$ bound on solving $A$, there can be a $2^{n^{10}}$ bound on solving $B$. See this topic for more info.


List of papers on Runtime and Statistical Tradeoffs on Machine Learning

We explored the Runtime-Accuracy tradeoff in the context of nearest neighbors in a 2010 COLT paper [journal version]:
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6867374

Roughly speaking, your dataset has margin $\gamma$ if every pair of opposite-labaled points is at least $\gamma$ apart in distance. You can also impose a desired margin by counting the violating pairs as sample error (this is analogous to the SVM setting where it may be advantageous to impose a margin that's bigger than the data margin, at the expense of some violations). Unlike SVM, the metric margin very much affects the algorithmic runtimes. We also have margin-based generalization bounds. Thus, one can answer questions such as: if my runtime is on a certain budget, what sort of accuracy can I expect?

We continued this line of research in last year's NIPS paper:
http://papers.nips.cc/paper/5528-near-optimal-sample-compression-for-nearest-neighbors.pdf

where we showed that the margin also allows for the sample to be compressed (in fact, nearly optimally).


I know more about purely-functional data structures than external-memory data structures, but I'll give this a go.

A B-tree can be written in a purely-functional way by path copying. The path will be short ($O(\log_B n)$), but copying each block takes $O(B)$ writes in $O(1)$ blocks.

If you're willing to let the structure be just fully persistent, rather than purely functional, I think you can reduce the number of writes in a node copy to $O(\lg w)$ expected amortized, where $w$ is the word width, using the fully persistent arrays in "Confluently Persistent Tries for Efficient Version Control"

You might want to watch this presentation about RethinkDB, which uses purely-functional data structures because of the cost of writes in SSDs.


Does every NO instance of this promise problem have a local refutation?

So if I understood well, your problem in the language of graph theory would be as follows:

  Is there a $k$ such that if for a $3$-uniform hypergraph for any $k$ of its edges we can select a $1$-shallow hitting set (a set of vertices that meets each of the $k$ edges in exactly one vertex), then the hypergraph is $2$-colorable?

The answer to this question is no because for any $g$ and $r$ there are $r$-uniform hypergraphs of girth $g$ with arbitrarily high chromatic number [Kostochka-Nesetril].
The girth $g$ of an $r$-uniform hypergraph is the smallest $g$ for which there are $g-1$ edges whose union has size at most $g(k-1)$.
Thus, if a hypergraph has girth $g$, then any $g-1$ edges have a $1$-shallow hitting set by induction because their union looks like a tree.
This means that locally it satisfies your 1-in-3 satisfiability condition, but it is not $2$-colorable, so there is no NAE-satisfying assignment for the whole hypergraph.


Correspondence between complexity classes and logic

Neil Immerman produced a beautiful diagram that provides at-a-glance correspondences between complexity classes and logics interpreted by finite models.  It's on the cover of his book, and also at the bottom of his web page here: http://www.cs.umass.edu/~immerman/


Can addition be carried out in less than depth 5?

According to Theorem 3.1 in Alexis Maciel and Denis Therien Threshold Circuits of Small Majority-Depth there is indeed a depth-3 circuit for computing the addition of two numbers.

The precise bound is $\Delta_2 \cdot \mathsf{NC}^0_1$ where $\Delta_2 = \Sigma_2 \cap \Pi_2$ are problems which have depth-2 $\mathsf{AC}^0$ circuits with both $\vee,\wedge$ gates at top and $\mathsf{NC}^0_1$ circuits are $\mathsf{NC}^0$ circuits of depth one (see the paper for a detailed explanation of the notation).

The main proof ideas are:

First, express the Carry-lookahead circuit as $\mathsf{NC}^0\cdot\Delta_2\cdot\mathsf{NC}^0$
Next, invoke closure properties of $\Delta_2$ to write this as $\Delta_2\cdot\mathsf{NC}^0$
Finally, use the fact (also proved in the paper) that $\mathsf{NC}^0 \subset \Delta_1\cdot\mathsf{NC}^0_1$


References on implementing universe levels over MLTT?

IMHO universe hierarchy is particularly complicated to implement while the benefit is very small. It complicates programming in the language and the implementation of the language. The only benefit is to ensure the logical consistency. I guess that's why everybody is not writing about it.
Here are some answers to your questions. I don't know much type theory -- I can't answer everything, sorry.

Why not simply reuse the natural numbers for universe levels?

Nat has an eliminator. You shouldn't be able to pattern match on a level. In fact, introducing Level as a type (not to mention an inductive type) already causes problem. Imagine the following function:
Ty : (ell : Level) -> Set (lsuc ell)
Ty l = Set l

What is the universe level of the type of Ty? Also, what's the universe level of the type of Level? If we don't have a type for levels (but instead built it into the syntax, to eliminate these cases) we could avoid these problems (but then you become less flexible ofc).

How does one type-check and perform normalization-by-evaluation on universe levels?

I guess just like Nat. The relevant operations are strict subset of Nat.

What are the subtleties one should be aware of when implementing universes?

Level is actually not a type. I personally don't like Agda's approach (but prefer Lean's, Arend's approach, where Level is not a type).
You need to compare levels for equality and less than relation. So, your compiler should know max(x, y) >= x, max(x, y, z) >= max(x, y), etc.
There are many styles of universe hierarchy. You can peek cumulativity, impredicativity (be careful, it may lead to inconsistency), typical ambiguity, etc.
You may want to implement a solver for level equations (if you have implicit inference mechanism), but that's very complicated.

How should I test that my universe hierarchy implementation is correct?

Try to refute the construction of the Girard paradox. It's everywhere on the internet. Also, there is another example which I believe that it won't work with universe levels.
I'm also implementing universe polymorphism on a little programming language, but the code is kinda messy.


Existing benchmarks for scheduling problems?

Mainly, there exist 3 benchmarks to test shop scheduling problems.
Namely they are Taillard, Structured and ORLib benchmarks. These benchmarks have different
goals. The Taillard benchmark is the most
used benchmark in the literature. The benchmark targets permutation flowshop, flowshop, open shop and job shop scheduling problems. For details and download of the benchmark refer to http://www.lifl.fr/~liefooga/benchmarks/benchmarks/

The second benchmark shop scheduling problems is the structured benchmark. As
the name suggests, the goal of the benchmark is to have test instances having a structure
additional to the test instances with random instances. It contains all the instances from
the Taillard benchmark. Further details and the benchmark can be found at http://www.cs.colostate.edu/sched/generator/

The third benchmark focuses on collecting test cases found difficult to solve in
industry. We refer to this benchmark as ORLib benchmark. Contains instances from
Taillard + some instances from industry. More details and benchmarks can be found at http://people.brunel.ac.uk/~mastjjb/jeb/orlib/flowshopinfo.html


Algorithms to classify the geometrical relationship of two 3D-geometries

I'm assuming you mean

volume A is inside volume B
volume A is disjoint of volume B

Then it's really simple. Pick the volume you expect to be a superset, or $A$. Each polygon defines a plane. Use these points to solve for $ax+by+cz+d=0$, for every polygon of $A$.
Then it would help if you had a point that you know is inside a volume.
find the closest polygon to your inner point, and check whether that point is greater or less than the plane. let that number be $k_{P_n}$ (either 1 or -1).
take a polygon that is next to your initial polygon. find the folding edge of the two.
take a point of the new polygon that is not on the folding edge ($l$).
extend a point from the folding edge orthogonal to the initial plane above the initial plane ($a$). second point on the initial plane, but outside of the line of intersection ($c$). (above with respect to your k of the initial plane)
if $l$ is on the initial plane, then adjust your new k so that $a$ is above the new plane.
if $l$ is above (with respect to the the initial k) the initial plane, then adjust your new k so that $c$ is below the new plane.
if $l$ is below (with respect to the the initial k) the initial plane, then adjust your new k so that $c$ is above the new plane.
keep doing that until you have your complete shell mapped for k. if you have more than one shell (like a hollow object) you need to track all unmapped polygons and do the same thing for them.
then you can compare your volumes.
take any point from B, and find the closest polygon from A, and check whether your B point is above the plane of the A polygon. do this for every point in B.
you also need to check whether any A point is in B, for the special case in which a sharp spike from one volume penetrates the other.
If all points of $B$ are inside $A$, and no points of $A$ are inside $B$, then $B$ is inside $A$
If some but not all points of $B$ are inside $A$, then $A$ and $B$ intersect.
If no points of $B$ are inside $A$, and no points of $A$ are inside $B$, then $A$ and $B$ are disjoint.
Further reading:
Look at computing volume of convex polytopes. Alternatively to the above, you can look at the union volume to draw your conclusions. if $V_U=V_A$, then $A\subset B$. if $V_U<V_A \wedge V_U<V_B \wedge V_U \neq 0 $ then $A$ intersects $B$. If $A_U=0$ then they don't intersect.


Are there [good/optimal] parallel comparison sorts?

(answering my own question)

1. $\:$ Yes

2. $\:$ No

Reference:

Tight Comparison Bounds On The Complexity Of Parallel Sorting

by Yossi Azar , Uzi Vishkin (1987)

publisher: Courant Institute of Mathematical Sciences, New York University

retrieved from http://archive.org/details/tightcomparisonb00azar (June 17, 2012)


This is just a long comment (too many words to fit in a comment box).
Gérard Huet is, among other things, an expert in $\lambda$-calculus who worked worked a lot on the computational processing of Sanskrit, including its phonological aspects.  I remember him once giving a talk in Marseilles entitled Des Lambdas et des Aums ("Lambdas and Oms") but unfortunately I do not recall whether he made any explicit connection between the two (it was a very informal talk in honor of Per Martin-Löf, who was to receive a doctorate honoris causa from the University of Aix-Marseille 2 a few days later.  All this was nearly 16 years ago).
I browsed a bit his web page (linked above), there's a lot of material on the computational analysis of Sanskrit (including phonetics) but none of it seems to mention the $\lambda$-calculus (there's some OCaml programming at best).  Since, as I said, Huet knows the $\lambda$-calculus extremely well, my guess is that had he seen any connection between the latter and Sanskrit phonology, he would have stressed it.  But certainly the best is just to ask him directly!  I'm sure he'll be glad to tell you.
PS: perhaps a little bit of motivation/background to your question wouldn't hurt.  Why do you think there should be any relationship between $\lambda$-calculus and phonology?  I guess I can vaguely understand the motivation behind a computational approach to phonology, but why the $\lambda$-calculus?


[Comment space was too short]

I think it depends on what you mean by behaviour. Probabilistic automata follow in the tradition of finite automata, so their behaviour is defined in terms of their language or traces. Labelled Markov Processes follow in the tradition of process algebra, where it is known that processes can be compared using a variety of preorders typically starting with bisimulation. You do have notions of bisimulation defined for LMPs and in that paper. Bisimulation is stronger than trace equivalence, as you may know, so the behaviour you are interested in is the tree unfolding rooted at a given state. Definition 3.1 of the paper you have linked gives approximations of this tree.


Is every countable, finite-branching LTS bisimilar to a tree?

Q1: Yes, every LTS is bisimilar to its unfolding, which is a tree.
Q2: No, by a cardinality argument. For instance take infinite binary trees with $L=\{a,b\}$. Each tree has countable set of states and is finitely-branching, but you have uncountably many such trees, even up to bisimilarity. However you have only countably many $\mu$-calculus formulas, so some bisimilarity classes are not captured by formulas.
Actually in this setting, a bisimilarity class can be exactly captured by a $L_\mu$ formula if and only if it is the bisimilarity class of a finite structure. The unfolding of a finite structure is called a regular tree. Any formula accepting a non-regular tree must also accept a regular tree, which is not bisimilar to it. See for instance [1] for more details.
[1] The mu-calculus and model checking.
J Bradfield, I Walukiewicz.
Handbook of Model Checking, 871-919


Complement problems are not in the same class in parametrized complexity hierarchy? If not in $P$

The complement problems Minimum (Edge) Bipartization and MaxCut are both in FPT, so the conjecture is false.


Find optimal room from which to visit all other rooms in a rectangular floorplan

(This is joint with Jeff Phillips, who refuses to visit cstheory regularly ;))
I'm working with the problem formulation as stated and evolved in the comments. Namely, the goal is to find a minimum number of "robots" who can traverse a partition of an orthogonal polygon into rectangles, with the constraint that:

A room can be entered and exited only in diametrically opposed directions (so north-south OR east-west)
A robot can only cross room boundaries along one (globally chosen) axis (so no 90 degree turns allowed)
Within a room though, a robot can do whatever it likes, as long it crosses room boundaries as specified.
Robots can backtrack arbitrarily as long as they follow the above rules.

So a solution looks like an assignment of "colors" axes (NS or EW) to each room, and a traversal plan where each robot only traverses rooms having the same "color".
Construct a graph where each rectangle is a vertex and two rectangles are marked as adjacent if they share a boundary. The edge is "colored" NS or EW, depending on the nature of the adjacency.
Claim 1: If we are limited to one axis (NS or EW) then the minimum number of robots is merely the number of components in graph induced by edges of the corresponding color.
Proof: Every edge represents a legal transition in that axis, so placing one robot in each connected component suffices, and you need at least one for each component for coverage.
Now consider the two partitions of the rectangle collection induced by the two colors. Notice that the minimum cardinality partition among these two might be far from optimal if for example your polygon is an L shape with each leg subdivided into n/2 rectangles. The individual graphs each have n/2 components, but the optimal solution is of size 2.
Construct a bipartite graph, in each node is one of the connected components of either of the partitions, and two nodes are connected if their corresponding components intersect. This graph is bipartite because the two sets of components were partitions.
Claim: the size of minimum vertex cover in this graph is the desired optimal soln.
Proof.
Firstly note that in any optimal solution, the set of rectangles covered by any robot must be a subset of one of the components by reachability. Further, it costs nothing for this robot to cover any of the other rectangles in this partition. Hence wlog we can assume that OPT consists of a set of components that together cover all rectangles, i.e a set cover.
Secondly, since the graph is bipartite, we know that any rectangle is represented by exactly one edge between left and right sides. Thus, covering all rectangles actually requires covering all edges in this graph.
QED
VC in bipartite graphs can be solved in polynomial time, so the overall problem can be solved in polynomial time.
Comments ?


Sufficient conditions for the regularity of a context-free language

Every unary context-free language is regular.
(e.g. a direct consequence of Parikh's theorem)
If every iterative/pumping pair of a context-free language L is
degenerated, then L is regular, i.e. L is regular if, for all words x,u,y,v,z it satisfies:
$$xu^nyv^nz \in L, \text{for all } n \geq 0 \implies xu^iyv^jz \in L, \text{ for all }i,j \geq 0.$$This was proved by Ehrenfeucht, Rozenberg, "Strong iterative pairs and the regularity of context-free languages", 1983. See
"Context-free languages" by Berstel and Boasson for an exposition.
If a context-free language is commutative and linear, then it is regular.
(Ehrenfeucht, Haussler, Rozenberg, "On regularity of Context-free Languages",  1983)


Can we construct a k-wise independent permutation on [n] using only constant time and space?

If you are willing to use cryptographic techniques and rely upon cryptographic assumptions and to accept a computational notion of $k$-wise independence, it's posible that format-preserving encryption (FPE) might be helpful.  Let me sketch a few different constructions of this sort.

(By "computational notion of $k$-wise independence", I mean that no adversary with a reasonable running time can distinguish $\sigma$ from a $k$-wise independent permutation, except with negligible advantage.  These schemes won't be information-theoretically $k$-wise independent, but they'll be "essentially as good as $k$-wise independent", assuming all of the computation in sight is computationally bounded.)

A practical scheme, for smaller $n$

In particular, use a FPE construction to build a block cipher (pseudorandom permutation, PRP) with the signature $\sigma_k : [n] \to [n]$.  For values of $n$ that are smaller than $2^{128}$, probably the best scheme is to use a Feistel construction with a fixed number of rounds (say, 10) and a round function that is a PRF derived from AES.   The running time to evaluate $\sigma_k(i)$ for a single value of $i$ will be $O(1)$ AES invocations.  Each AES invocation runs in constant time.

Finally, note that any pseudorandom permutation is automatically $k$-wise independent.  In particular, the Luby-Rackoff theorem guarantees that with at least 3 rounds, you get (approximate) $k$-wise independence if $k \ll n^{1/4}$, assuming AES is secure.  With more rounds, it's likely that there will be a stronger result, but the theorems are harder to prove and become more technical, though it's widely believed that a constant number of rounds should suffice to get extremely high security (and thus essentially perfect $k$-wise independence for all reasonable values of $k$).

Generalizing this to larger $n$

When $n$ is larger, things get weirder, because the unit-cost RAM model implicitly allows up to $O(\lg n)$ parallelism for free.  It's not clear to me what the cost of PRPs should be in this model (constant? increasing with $n$? I don't know).

A third possible construction

Let $m$ be a RSA modulus that is a bit larger than $2n$.  Define $G$ to be the subgroup of $(\mathbb{Z}/m\mathbb{Z})^*$ containing the elements whose Jacobi symbol is $+1$.  Define $\pi : G \to G$ by

$$\pi(x) = x^3 \bmod m.$$

Next, define $\sigma$ by

$$\sigma(i) = g(\pi(f(i)),$$

where $f,g$ are random bijective 2-independent hash functions.

I suspect this construction has a chance of being (approximately) $k$-wise independent, under a RSA-like assumption.  I have no proof, just an intuition.  The main known regularity of $\pi$ is that it is multiplicatively homomorphic: $\pi(xy) = \pi(x) \pi(y)$.  I do not know of any other relevant regularities, even $k$-wise dependence.  Applying a 2-independent hash before and after $\pi$ provably eliminates this regularity: if $\pi$ is $k$-wise independence except for multiplicative homomorphicity, then the 2-wise independent hashes seem like they should provide full $k$-wise independence.  But this is super-sketchy and light-years from a proof of $k$-wise independence.

Note that you'll need to use format-preserving encryption techniques (e.g., the cycling technique) to ensure that $f,g$ work on $G$ rather than on $(\mathbb{Z}/m\mathbb{Z})$.  This scheme should have $O(1)$ (expected) running time to evaluate $\sigma(i)$ at a given input $i$, with suitable choice of $f,g$.

Also, in some sense this candidate construction is abusing the unit-cost RAM model by relying upon the ability to operate on $\lg n$-bit numbers in $O(1)$ time, for large values of $n$, which isn't really reasonable in practice.  (This last construction won't be secure for small values of $n$, so this last approach fundamentally relies upon the large-$n$ regime for it to have a chance of working... exactly the regime where the unit-cost RAM model is most dubious.)

I freely admit that this one is quite a stretch, but I mention it in case it triggers some inspiration for a better solution.

For instance, it might be possible to replace $G$ by a suitable elliptic curve group, so that we have $\pi(x) = e x$ over $G$ (recall that elliptic curve groups usually use additive notation rather than multiplicative notation).  The good thing about this is that it is not totally unreasonable to conjecture that, if the elliptic curve group $G$ is chosen right, $G$ will behave like a "black-box group", which I think might effectively imply that $\pi$ will be $k$-wise independent "except for effects implied by multiplicative homomorphism".  I don't have a complete construction ready to propose (the missing piece is how to choose $G$ and how to construct $f,g$ and how to prove $k$-wise independence from this), but it might be possible to put the pieces together somehow.


Constructing subfields of a finite field

This problem is in BPP.

All finite fields of order $p^n$ are identical, and there is a generator element $g$ whose multiplicative order is $p^n-1$, so every non-zero field element is expressible as $g^r$ for some $r$.

Now, there is a subfield of order $p^j$ iff $j$ divides $n$, and this subfield has a generator element $h$ whose multiplicative order is $p^j-1$.

This means that we can take $h = g^{(p^n-1)/(p^j-1)}$.

What this means, in effect, is that once we have an algorithm for finding a generator of the finite field, everything else is straightforward.

The easy way to find a generator is to pick a field element at random, and test whether it is a generator. The expected number of elements you need to test is indeed polynomial. Doing this test efficiently might require knowing the prime factors of $n$. (But if you can write down all the coefficients of $f(x)$ without using sparse polynomial notation, then $n$ is small and this is easy.)

But you asked for a deterministic algorithm and not a randomized one.
A quick search shows that there is no known efficient deterministic algorithm for finding a generator. See this question on math.SE.

So the question is: can you find a deterministic algorithm for finding the subfields which doesn't actually compute a generator for the subfields? (Because that's probably as hard as finding a generator for the field itself, and so is an open problem.)

Much of this is explained in Wikipedia.


Circuit lower bounds over arbitrary sets of gates

(Moved from comments as Suresh suggested.  Note some errors in the comment are fixed here.)

Thanks to Scott for a great question.

Scott seems to suggest that the reason for the difficulty of lower bounds may be the restricted language of operations in the Boolean case.  Shannon's counting argument that shows most circuits must be large relies on the gap between countable expressive power and uncountably many circuits.  This gap seems to go away when the alphabet has at least 3 symbols.

For alphabet size 2 (the Boolean case), the lattice of clones is countably infinite, and is called Post's lattice.

Post's lattice also makes clear why there are only a few interesting bases of operations for the Boolean case.

For alphabet size 3 or greater the lattice of clones is uncountable.  Further, the lattice does not satisfy any nontrivial lattice identity, so it seems impossible to provide a complete description of the lattice.  For alphabet size 4 or greater the lattice of clones actually contains every finite lattice as a sublattice.  So there are infinitely many possibly interesting bases of operations to consider when the alphabet has 3 or more symbols.

Bulatov, Andrei A.,
Conditions satisfied by clone lattices,
Algebra Universalis
46
237–241,
2001.
doi: 10.1007/PL00000340

Scott asked further: does the lattice of clones remain uncountable if we assume constants are available for free?

The answer is that it does, see for instance

Gradimir Vojvodić,
Jovanka Pantović, and
Ratko Tošić,
The number of clones containing an unary function,
NSJOM
27
83–87,
1997.
(PDF)
J. Pantović, R. Tošić, and G. Vojvodić,
The cardinality of functionally complete algebras on a three element set,
Algebra Universalis
38
136–140,
1997.
doi: 10.1007/s000120050042

although apparently this was published earlier:

Ágoston, I., Demetrovics, J., and Hannák, L.
On the number of clones containing all constants,
Coll. Math. Soc. János Bolyai
43
21–25,
1983.

A nice specific statement is from:

A. Bulatov, A. Krokhin, K. Safin, and E. Sukhanov,
On the structure of clone lattices,
In: "General Algebra and Discrete Mathematics",
editors: K. Denecke and O. Lueders,
27–34.
Heldermann Verlag, Berlin,
1995.
(PS)

  Corollary 3 (attributed to Ágoston et al. as above): Let $k \ge 3$.  Then the number of clones in $\mathcal{L}_k$ containing all constants is $2^{\aleph_0}$.

To wrap up, I am not aware of any work on using non-Boolean clones for circuit lower bounds.  This seems worth investigating in more depth.  Given the relatively little that is known about the lattice of clones, there may be interesting bases of operations waiting to be discovered.

More links between clone theory and computer science would probably also be of great interest to mathematicians working in universal algebra.  A previous example of this kind of interaction came about when Peter Jeavons showed that algebras could be associated with constraint languages, in a way that allows tractability results to be translated into properties of the algebra.  Andrei Bulatov used this to prove the dichotomy for CSPs with domain size 3.  Going the other way, there has been a revival in interest in tame congruence theory as a result of the computer science application.  I wonder what would follow from a link between clone theory and non-Boolean circuit complexity.


Complexity of a variant of the max word problem. NP-complete?

If you allow the repetition of matrices, i.e. there exists $ 1 \leq i < j \leq n $ s.t. $ A_i =A_j $, then your problem is actually undecidable.

Let $ EMPTY_{PFA} $ be the emptiness problem for probabilistic finite automaton (PFA).

A PFA is a 4 tuple: $ P=(\Sigma,\{A_{\sigma \in \Sigma}\},x,y) $, where $\Sigma = \{\sigma_1,\ldots,\sigma_k\}$ is the input alphabet, each $ A_{\sigma} $ is a stochastic matrix, $x$ is a stochastic row vector (initial distribution), and $ y $ is a zero-one column vector. Each word, say $w \in \Sigma^*$, corresponds to a sequence of the matrices from $ \{A_{\sigma \in \Sigma}\} $ by allowing repetition, and vice versa. The accepting probability of $w$ by $P$ is as follows:

$$f_P(w) = x \cdot A_{w_1} \cdot A_{w_2} \cdots A_{w_{|w|}} \cdot y, $$

where $w_i$ is the $i^{th}$ symbol of $w$ and $|w|$ is the length of $w$.

$ EMPTY_{PFA} $ is the problem of, for a given PFA $ P $ and a threshold $ \lambda \in (0,1) $, whether there exists a word accepted with a probability at least $ \lambda $. $ EMPTY_{PFA} $ was shown to be undecidable. It is an old result and you can start digging from this article: http://arxiv.org/abs/quant-ph/0304082

$ EMPTY_{PFA} $ can be reduced to your problem. So, if your problem is decidable, then $ EMPTY_{PFA} $ is also decidable. But this is a contradiction. So, your problem is undecidable, too.


Problems equivalent to the existence of secure cryptosystems?

One-way functions are implied by all of these things, and known to imply symmetric encryption and digital signatures. These equivalences are indeed found in (theoretically-focused) text books.

The situation for key exchange and asymmetric (i.e., public-key) encryption is a less clear. Asymmetric encryption implies key exchange.

Implications in the other direction (from OWF to KE or KE to AE) are not known--in fact, there is evidence that there are no black box reductions of this type. This line of work started with the seminal paper of Impagliazzo and Rudich, and is nicely summarized (as of circa 2000) here: groups.csail.mit.edu/cis/pubs/malkin/GKMRV.ps

I think that the simplest generic assumption known to imply asymmetric encryption is the existence of trapdoor injective one-way functions. However, not think all known PKE schemes imply the existence of trapdoor injective OWF (lattice-based schemes imply something messier). So again, there is no simple answer.

Much of this latter material is not covered in standard text books; you have to read papers to find it. (I hope my own answer is up to date!)


One-way randomized communication complexity of Greater-Than

If you look at the MNSW proof carefully, the base case can be taken to be the trivial fact that a $0$-round protocol for $\textrm{GT}_n$ with $n = 1$ requires one bit of communication.
If the goal is simply to convince oneself from first principles that $\textrm{R}^\to(\textrm{GT}_n) = \Omega(n)$, this is immediate by reduction from the AUGMENTED-INDEX problem. An $\Omega(n)$ one-way lower bound for AUG-INDEX boils down to the chain rule for mutual information. For a discussion of AUG-INDEX, see, e.g., Section 3.4 of Jelani Nelson's PhD thesis (https://people.eecs.berkeley.edu/~minilek/publications/papers/phd_thesis.pdf).


References to learn more about graph laplacian.

Suggest these free available resources. Most textbooks on graph theory only glance at "free probability theory".

Lectures on the Combinatorics of Free Probability (London Mathematical Society Lecture Note Series):
http://www.amazon.com/Lectures-Combinatorics-Probability-Mathematical-Society/dp/0521858526

Speicher lectures: http://www.mast.queensu.ca/~speicher/papers/lectures-IHP.pdf


Simple k-nearest-neighbor algorithm for euclidean data with highly variable density?

I'd recommend using a kd-tree or an R-tree. These structures automatically partition the data.

A kd-tree (k-dimensional tree) is a binary tree in which every node is a point. Every non-leaf node splits the space in half along one of the axes. Points on one side of the split form the left subtree, points on another side form the right subtree. A kd-tree has guaranteed space complexity O(n) and average search, insertion and deletion complexity of O(log n). The cost of building the tree is O(n log n) when using an advanced linear median-finding algorithm. The k-nearest-neighbors search boils down to moving down the tree, checking distances to the elements in final subtree and unwinding the recursion up the tree if more elements are needed. kd-trees are easy to implement in memory, but non-trivial to implement on disk. They may need to be rebuilt when changing data.

R-trees (rectangle trees) group nearby objects in minimum bounding rectangles, group the rectangles in larger rectangles, and so on. This means that they can store not only points, but also polygons. The complexity of search is between O(log n) and O(n), depending on the amount of overlap between rectangles. There are various optimization strategies and algorithms for splitting overflowing nodes and bulk-loading. While more complicated, R-trees have advantages over kd-trees. They are more disk-oriented, making them useful for real databases. Unlike non-bulk-loaded kd-trees, they are balanced, and therefore preferred for changing data.

In conclusion, if the data will change after building the tree or you want the data to be stored on disk, I'd use an R-tree, otherwise kd-tree.


Time complexity of finding chain decomposition of partially ordered set

You may find the following recent reference useful:
M. Caceres, M. Cairo, B. Mumey, R.  Rizzi, and A. Tomescu. On the parameterized complexity of the Minimum Path Cover problem in DAGs.
arXiv preprint arXiv:2007.07575


To complete the search process for an element $x$ that is not in the tree, you have to go all the way to a leaf node to confirm that $x$ is not in the tree.  If you repeatedly search for such an element $x$, you have to splay on an unsuccessful search, otherwise the query time for $x$ could indefinitely remain as bad as $\Theta(n)$, even in an amortized sense.


Taxonomy of notable regular expression automata

Watson (Tech. Rep. Univ. Eindhoven 1995) has written a taxonomy of finite automata construction algorithms; a few more recent developments are found below.

For NFAs with epsilon-transitions, the parsing theory book by Sippu/Soisalon-Soininen (Springer, 1998) contains a variant of Thompson's construction. Ilie and Yu (I&C 2003) and Gulan and Fernau (FSTTCS 2008) give refined versions of the classical construction. The minimum required size of epsilon-NFAs corresponding to regular expressions is further studied by Gruber and Gulan (LATA 2010). The structure of the underlying digraphs resulting from Thompson's construction is studied by Giammarresi, Ponty, Wood & Ziadi (Discr. Appl. Math 2004) and by Gulan (Tech. Rep. Univ. Trier, 2010).

Regarding epsilon-free NFAs, I want to mention the earlier work by Berry & Sethi (TCS 1986) and by Brüggemann-Klein (TCS 1993), but that is probably covered by Watson's taxonomy.

Hagenah and Muscholl (RAIRO 2000) give a fast parallel version of Hromkovic, Seibert & Wilke's (HSW) algorithm. The initial lower bound on size (number of transitions) of epsilon-free NFAs by HSW is improved by Lifshits (IPL 2003). Geffert (JCSS 2003) improves the upper bound in the case of binary alphabets; Later Schnitger (STACS 2006) improves the lower bound on the size of epsilon-free NFAs (for largely growing alphabet sizes, the algorithm by HSW produces asymptotically optimal NFAs), and shows that size $n\cdot 2^{O(\log^*n)}$ suffices for binary alphabets.

Also note: Regarding fast algorithms for regular expression matching, I am aware of recent work by Bille and Thorup (ICALP 2009, SODA 2010). They use the classical Thompson construction (plus of course many tricks for getting speed).


Find two sequences of integers that have sum N but that don't have sub-sequences starting at the head of equal sum

You can solve this with dynamic programming as well.

To see this, first realize you can see this problem as splitting the numbers between $0$ and $N$ into two subsets $X$ and $Y$ (the cumulative sums) that cannot overlap except at $0$ and $N$ (and must overlap there), and where the difference between consecutive elements of a subset is at most 3.

Reformulating the problem this way, you can have the state of your dynamic programming be:

"The number of ways of splitting the numbers between $0$ and $i-1$ into two sequences in the fashion described in the second paragraph, where the the numbers in positions (i, i-1, i-2) have assignments (j,k,h)", with $3 \leq i \leq N-1$, and $(j,k,h) \in \{X,Y,None\}$.

Using the states for $i=k$ to compute the states for $i=k+1$, it does take $\Theta(N)$ time to compute this. Let me know if more details are required.

Edit: I had missed in the previous answer the fact that $T$ and $U$ are fixed. You can take care of this by adding in your state how many positions so far have assignment to $X$, and how many have assignments to $Y$. Sadly, this brings the complexity up to $\Theta(T*U*N)$. Also, note that the solution generalizes to a larger number of sequences, and their values being in a larger range $\{1, \ldots, k \}$.


Base-k representations of the co-domain of a polynomial - is it context-free?

Of course $k \geq 2$ here.

There once was a manuscript by Horváth that claimed to solve the problem, but it was unclear in several places and to my knowledge was never published.

As far as I know, the problem is still open.  One direction of the implication is easy, of course.


Categorical semantics for non-monotonic logics?

Non-monotonic logic is kind of a wide area -- do you have any particular logics in mind? Anyway, defeasibly assuming :) that

you are interested in any logic in which the principle of monotony fails, and
you want a categorical semantics in the sense of categorical proof theory (rather than, say, a hyperdoctrine semantics), then

one answer is that you can give a reasonable categorical semantics to any logic for which a sequent calculus with cut-elimination is known. Basically, the types are objects, normal forms of the sequent calculus are morphisms, and cut-elimination tells you how to implement composition. This gives you the initial category in whatever category of models you end up using to prove soundness and completeness.

This recipe is independent of monotonicity, and so it can work well even for non-monotonic logics. For example, one of the more important successes in categorical logic is its treatment of linear logic. This is a logic where, intuitively, propositions refer to resources, so that the linear implication $A \multimap B$ can be read as "$A$ can be consumed to produce $B$". The consequence relation of linear logic is non-monotonic (since the fact that $A$ can be consumed to produce $B$ does not mean that $A$ and $X$ can both be consumed to produce $B$). However, it has an excellent proof theory, and its categorical models are closely tied to the theory of monoidal categories.


The dependence of learning generalization bounds on the dimension of the instance space

I think the VC-dimension term pretty much takes care of it. You can think of three cases:

The hypothesis space $H$ is far more "complex" than the input space $X$
$H$ and $X$ are matched up well to each other
$H$ is much "simpler" than $X$

We are usually only motivated by the second and third cases, so the VC-dimension term in your bound captures what we care about.

For example in $X=\mathbb{R}^d$, you probably want to choose a hypothesis class that depends on $d$, for instance halfspaces in $\mathbb{R}^d$, and so $d$ shows up in the VC-dimension term (in the case of halfspaces, this is $d+1$).

There are also some examples of classes with finite VC-dimension that are still interesting. Here even if $X$ is "large" or complex, we can get a small bound.


Noisy Parity (LWE) lower bounds/hardness results

The LPN problem is indeed believed to be hard, but like most problems we believe are hard, the main reason for it is that many smart people have tried to find an efficient algorithm and failed.

The best "evidence" for LPN's hardness comes from the high statistical query dimension of the parity problem.  Statistical queries capture most known learning algorithms, except for gaussian elimination (which fails whenever noise is introduced), hashing, and techniques similar to these two.  It is hard to design non statistical-query algorithms, and this is the main bottleneck.  Other evidence of LPN's hardness is its relationship to other hard problems (like LWE, SVP as you've pointed out).

For the SQ-hardness, here is the link to Kearns's ('98) paper.

For progress on the upper bounds on this problem, there are several results:

Probably the most famous is the Blum-Kalai-Wasserman ('00) result which beats the $2^N$ SQ barrier by a little, giving an algorithm that runs in time $2^{n / \log n}$. (link)
Lyubashevsky ('05) found an algorithm with worse running time $O(2^{n / \log\log n})$ but better sample complexity of $O(n^{1 + \epsilon})$. (link)
In the sparse case, where we know the parity is on $k$ variables, Grigorescu-Reyzin-Vempala ('11) gave a $\approx O(n^{0.5 k})$ algorithm, beating the $O(n^k)$ brute-force.  However, this bound decays toward $O(n^k)$ as the noise rate $\eta$ approaches $1/2$. (link)
Valiant ('12) recently gave a $\approx O(n^{0.8 k})$ algorithm for the sparse case.  This bound is stronger because it does not decay in the exponent with the noise rate (unlike the GRV result). (link)


Is there a useful notion of being “approximately computable”

If the family function $f(x,n)=f_n(x)$ is computable then these are exactly the $\Delta^0_2$ functions, or equivalently, the functions that are Turing reducible to the halting set $0'$, which are very well studied within computability-theory.

There are also other, not equivalent, notions of almost computable that go by names such as generically computable and coarsely computable, see e.g.
Jockusch et al.: Asymptotic Density and the Theory of Computability: A partial survey.


Is 0-1 programming with constant number of constraints polynomially solvable?

I'm assuming that by "0-1 programming with a constant number of constraints" you mean the following problem:

Maximize some linear function of (x_1, x_2, ..., x_n) subject to the constraints that each x_i is in {0,1} and a constant number of additional linear constraints.

This problem is NP-complete even with 1 additional constraint since 0-1 knapsack can be written in this form.


Do "outer-bounded-genus" graphs have constant treewidth?

Yes.

Add a vertex in the middle of the outer face, connected to all the vertices in the outer face; this does not change the genus, and does not decrease the treewidth. Now the graph has a very shallow breadth-first search tree rooted at the new vertex (everything is adjacent to it).

Form a spanning tree of the dual graph whose dual edges are disjoint from the edges of the breadth first search tree. Then there is a set of O(genus) edges that do not belong to either tree. Each of these edges induces a short cycle (a triangle) together with a path in the breadth first search tree, and cutting the surface along these cycles produces a planar surface (see my paper "Dynamic generators of topologically embedded graphs"). That is, if G' is the subgraph of the input graph induced by the vertices that are not endpoints of the O(genus) cut edges, then G' is planar, and its vertices can be covered by O(genus) faces of its planar embedding (the faces that the cut cycles cut the original outer face into).

But in a planar graph in which all vertices belong to k faces, one can remove another O(k) edges (a spanning tree of the faces) to get an outerplanar graph. So the treewidth of G' is O(genus). If one forms a tree-decomposition of G' with this width, and then adds to each bag the vertices that are endpoints of the cut cycle edges, the result is a tree-decomposition of the original input graph with treewidth O(genus).

It seems likely that this must be in the literature already somewhere, but I don't know where and some quick searches haven't succeeded in finding an explicit statement of this precise result. However, a more general statement is in a different paper of mine: in "Diameter and treewidth in minor-closed graph families" I prove among other things that bounded genus graphs of bounded diameter have bounded treewidth. In this case (by adding that extra vertex within the outer face) the diameter can be taken to be at most two.


What is the complexity of checking equivalence of two boolean formulae without NOT symbol?

Note that formulas using $\land$ and $\lor$ gates (and possibly the constants $0$ and $1$) are known as monotone.

The complexity of monotone formula equivalence depends on how complex formulas are allowed. Let me start with the related problem of implication (entailment) between two formulas $\phi\vdash\psi$, which is easier to classify. Note that $\phi$ and $\psi$ are equivalent iff $\phi\vdash\psi$ and $\psi\vdash\phi$.

Given monotone formulas $\phi$ and $\psi$, the problem of determining whether $\phi\vdash\psi$ is

in P for $\psi$ a CNF (even non-monotone). Indeed, we have $\phi\vdash\bigwedge_i\psi_i$ iff $\forall i\,(\phi\vdash\psi_i)$, and if $\psi_i$ is a clause, and $e_i$ the corresponding assignment that falsifies $\psi_i$ and makes all variables outside $\psi_i$ true, then
$$\phi\vdash\psi_i\iff e_i(\phi)=0.$$
For the right-to-left direction: if $e_i(\phi)=0$, and $e$ is any assignment such that $e(\psi_i)=0$, then $e\le e_i$, hence $e(\phi)=0$ using the monotonicity of $\phi$.
in P for $\phi$ a DNF (possibly non-monotone), by a dual argument.
coNP-complete for $\phi$ a 2-CNF and $\psi$ a 3-DNF (or dually: $\phi$ a 3-CNF and $\psi$ a 2-DNF), and a fortiori for any larger classes of formulas. Indeed, it is coNP-hard to check if a given 3-DNF is valid; we can write (in polynomial time) any 3-DNF in the form $\psi(\vec x,\neg\vec x)$ where $\psi$ is a monotone 3-DNF, and then
$$\vdash\psi(\vec x,\neg\vec x)\iff\bigwedge_i(x_i\lor y_i)\vdash\psi(\vec x,\vec y).$$
As above, the left-to-right direction follows from the monotonicity of $\psi$.

Now, back to equivalence. On the one hand, we have
$$\phi\equiv\psi\iff\phi\vdash\psi\text{ and }\psi\vdash\phi;$$
on the other hand,
$$\phi\vdash\psi\iff \phi\equiv(\phi\land\psi)\iff\psi\equiv(\phi\lor\psi).$$
Thus, we see that for monotone $\phi$ and $\psi$, the problem of determining if $\phi\equiv\psi$ is

in P for $\phi$ and $\psi$ CNF.
in P for $\phi$ and $\psi$ DNF.
coNP-complete for general monotone $\phi$ and $\psi$. It is enough to take $\phi$ a CNF, and $\psi$ a conjunction of a CNF and a DNF (which means $\psi$ can be written as a depth-3 formula with either $\bigwedge$ or $\bigvee$ as the top connective). Dually, it is enough to take $\phi$ a DNF, and $\psi$ a disjunction of a CNF and a DNF (whence again a depth-3 formula with either $\bigwedge$ or $\bigvee$ on top).

The only case left is the complexity of equivalence of a monotone CNF to a monotone DNF. This problem is interesting. As I learned in [4], it was proved to be solvable in quasipolynomial time $O(n^{\log n})$ by [3], and in coNP with only $O((\log n)^2)$ nondeterministic bits by [2,5]. Furthermore, when one of the formulas has bounded width, the problem is in P by [1,6], and even in L by [4].

References:

[1] T. Eiter, G. Gottlob: Identifying the minimal transversals of a hypergraph and related problems, SIAM Journal on Computing 24 (1995), no. 6, pp. 1278–1304, doi: 10.1137/S0097539793250299.

[2] T. Eiter, G. Gottlob, K. Makino: New results on monotone dualization and generating hypergraph transversals, SIAM Journal on Computing 32 (2003), no. 2, pp. 514–537, doi: 10.1137/S009753970240639X.

[3] M. L. Fredman, L. Khachiyan: On the complexity of dualization of monotone disjunctive normal forms, Journal of Algorithms 21 (1996), no. 3, pp. 618–628, doi: 10.1006/jagm.1996.0062.

[4] J. Goldsmith, M. Hagen, M. Mundhenk: Complexity of DNF minimization and isomorphism testing for monotone formulas, Information and Computation
206 (2008), no. 6, pp. 760–775, doi: 10.1016/j.ic.2008.03.002.

[5] D. J. Kavvadias, E. C. Stavropoulos: Monotone Boolean dualization is in $\mathrm{coNP}[\log^2n]$, Information Processing Letters 85 (2003), no. 1, pp. 1–6, doi: doi.org/10.1016/S0020-0190(02)00346-0.

[6] N. Mishra, L. Pitt: Generating all maximal independent sets of bounded-degree hypergraphs. In: Proceedings of the Tenth Annual Conference on Computational Learning Theory (COLT 1997), 1997, pp. 211–217, doi: 10.1145/267460.267500.


On Boolean functions with a certain number of zeros

One relevant result is that if $\deg f = d$ then $2^d\hat{f}(S)$ is an integer for all $S$ (see for example exercise 12(b) here). In particular, $2^d\hat{f}(\emptyset) = 2^{d-n}|f^{-1}(1)|$ is an integer, and so $|f^{-1}(0)|$ is a multiple of $2^{n-d}$. This gives a lower bound on $d$ given $|f^{-1}(0)|$, which is tight for an AND of $d$ variables.

In terms of corresponding upper bounds you can't expect much, since there are balanced functions of maximal degree (parity for example). Moreover, there are functions with $|f^{-1}(0)| = 2^{n-k}$ of maximal degree for all $1 \leq k \leq n$, for example parity on $n-k+1$ variables ORed with $k-1$ variables; you can probably be a bit more cunning and construct a function of maximal degree for any given $0 < |f^{-1}(0)| < 2^n$. However, if $|f^{-1}(0)| \in \{0,2^n\}$ then the function is constant.


There's a trivial protocol whose expected value is the correct mean: everybody announces their preference, and one is chosen at random. No player (acting alone) can do better than to announce their true preference. I haven't yet looked at the collusion-resistance of this protocol (I would guess it depends on the exact payoff functions).


Is parameterized complexity going to be the future of complexity theory?

Predicting the future is nigh impossible, especially so for cutting-edge research. I don't think anyone predicted how much impact deep learning is now having or that cryptography would be taken over by indistinguishability obfuscation.

That said, I will say this much: I don't see any particular reason to expect parameterized complexity to take over. It's a mature field that has been active for something like 20 years. It doesn't really strike me as an up-and-coming area. To be clear, I think it's a successful area that will continue to thrive.

If you look on google trends, search interest in parameterized complexity has been declining. (Stick in some other terms for a comparison if you're interested.) If you look up the combined citations for the Downey-Fellows textbook Parameterized Complexity and their updated textbook, you see that they are pretty stable:

(Source: Google scholar. I added both books to my own profile, merged them, took a screenshot of the combined citations, and then deleted them from my profile.)

This is a healthy number of citations, but it is not the exponential growth that would make you think parameterized complexity is going to take over. Of course, this data is very flawed, but it's the best indication I can find of the global popularity of parameterized complexity.

Note that things can be very popular locally even if they aren't popular globally.
When I was an undergrad, I thought that I needed to learn about category theory because everyone around me was talking about it; I even bought a book. Then I moved on to grad school and never heard about it again; the book remains unread to this day.
Perhaps you are in a similar situation -- you are in a department where there is a lot of parameterized complexity going on, but, if you move somewhere else, the story will be completely different.


Proof techniques for showing that dependent type checking is decidable

There is indeed a subtlety here, though things work out nicely in the case of type checking. I'll write down the issue here, since it seems to come up in many related threads, and try to explain why things work out all right when type-checking in a "standard" dependent type theory (I'll be deliberately vague, since these issues tend to crop up regardless):
Fact 1: If ${\cal D}$ is a derivation of $\Gamma\vdash t:A$, then there is a derivation ${\cal D}'$ of $\Gamma \vdash A:s$ for some kind $s$, and for every subterm $u\leq t$, there is some type $B$, a context $\Delta$ and a derivation $\cal D''$ of $\Delta\vdash u:B$.
This nice fact is somewhat hard to prove, and offset by a pretty nasty counter-fact:
Fact 2: In general, $\cal D'$ and $\cal D''$ are not sub-derivations of $\cal D$!
This depends a bit on the precise formulation of your type system, but most "operational" systems implemented in practice do satisfy Fact 2.
This means that you cannot "pass to sub-terms" when reasoning by induction on derivations, or conclude that the inductive statement is true about the type of the term you're trying to prove something about.
This fact bites you quite harshly when trying to prove seemingly innocent statements, e.g. that systems with typed conversion are equivalent to those with untyped conversion.
However, in the case of type inference, you can give a simultaneous type and sort (the type of the type) inference algorithm by induction on the structure of the term, which may involve a type-directed algorithm as Andrej suggests. For a given term $t$ (and context $\Gamma$, you either fail or find $A, s$ such that $\Gamma\vdash t:A$ and $\Gamma\vdash A : s$. You do not need to use the inductive hypothesis to find the latter derivation, and so in particular you avoid the problem explained above.
The crucial case (and the only case which really requires conversion) is application:
infer(t u):
   type_t, sort_t <- infer(t)
   type_t' <- normalize(type_t)
   type_u, sort_u <- infer(u)
   type_u' <- normalize(type_u)
   if (type_t' = Pi(A, B) and type_u' = A' and alpha_equal(A, A') then
      return B, sort_t (or the appropriate sort)
   else fail

Every call to normalize was done on well-typed terms, as this is the invariant for infer's success.

By the way, as it is implemented, Coq does not have decidable type checking, as it normalizes the body of fix statements before attempting to type check them.
At any rate, the bounds on the normal forms of well-typed terms are so astronomical, that the decidability theorem is mostly academic at this point anyways. In practice, you run the type checking algorithm for as long as you have patience for, and try a different route if it hasn't finished by then.