It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow problem on an $m$-edge graph can be expressed (via a network simplex formulation) using only $O(m)$ bits of information (which edges are saturated, which are unused, and which form a spanning tree of used but unsaturated edges). Similar arguments apply to minimum-cost flow, etc. So to make a flow problem that has enough information in the solution to recover the sorted order, you need $\Omega(n\log n)$ edges.


Simple and practical deterministic algorithm, complicated running time

The union-find data structure operations seem to meet your criteria:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure


Is generalized pigeonhole search known to be no harder than PPP?

Please see the comments below by Emil Jeřábek, so I am not that sure anymore that the problem is harder.

No, it is not known but it is harder than PPP :)

Here I focus on the $M=2N+1$ case, so $t=3$, that is, we want $3$ inputs that map to the same output. In Papadimitriou's seminal paper "On the Complexity of the Parity Argument" he defined PPA-3 similarly to PPA as the search problems reducible to the argument "If in a bipartite graph a node has degree not a multiple of 3, then there is at least another such node."

Let me define here PPAD-3 in a way similar to PPAD as the search problems reducible to the argument "If in a balanced, directed bipartite graph $(A,B;E)$ there is a node in $A$ whose outdegree is not $2$ or whose indegree is not $1$, then there is at least another such node in $A$ OR there is a node in $B$ whose outdegree is not $1$ or whose indegree is not $2$."

Just like PPAD$\subset$PPP, you can show that PPAD-3 is a subset of the problem you have defined. Unfortunately this is all the evidence I can give you as (as far as I know) PPA-3 has not been investigated much and no oracle separation results are known for it, though I don't think it would be hard to obtain some. Papadimitriou defining it as a separate class should be enough evidence that there is a good chance that they differ.


Is intersection of $k \ge 3$ graphic matroids in P?

I think it is still NP-complete, by a reduction from Hamiltonian paths in bipartite graphs with two degree-one vertices and all other vertices having degree three. (This is just the same as finding Hamiltonian cycles through a specified edge in a cubic bipartite graph — replace the specified edge by two leaves.)

To reduce from Hamiltonian paths to graphic matroid intersection, use one graphic matroid to force the subgraph you choose to be a spanning tree (true of every path) and two more graphic matroids, one on each side of the bipartition, to force the subgraph to have degree two at each degree-three vertex and to have an edge at each degree-one vertex. These are the graphic matroids of a graph with disjoint copies of $K_3$ for each degree-three vertex and $K_2$ for each degree-one vertex.


Huck, as Lance and Robin pointed out, we do have oracles relative to which PH is not in PP.  But that doesn't answer your question, which was what the situation is in the "real" (unrelativized) world!

The short answer is that (as with so much else in complexity theory) we don't know.

But the longer answer is that there are very good reasons to conjecture that indeed PH ⊆ PP.

First, Toda's Theorem implies PH ⊆ BP.PP, where BP.PP is the complexity class that "is to PP as BPP is to P" (in other words, PP where you can use a randomization to decide which MAJORITY computation you want to perform).  Second, under plausible derandomization hypotheses (similar to the ones that are known to imply P=BPP, by Nisan-Wigderson, Impagliazzo-Wigderson, etc.), we would have PP = BP.PP.

Addendum, to address your other questions:

(1) I'd say that we don't have a compelling intuition either way on the question of whether PP = PPP.  We know, from the results of Beigel-Reingold-Spielman and Fortnow-Reingold, that PP is closed under nonadaptive (truth-table) reductions.  In other words, a P machine that can make parallel queries to a PP oracle is no more powerful than PP itself.  But the fact that these results completely break down for adaptive (non-parallel) queries to the PP oracle suggests that maybe the latter are really more powerful.

(2) Likewise, NPPP and coNPPP might be still more powerful than PPP.  And PPPP might be more powerful still, and so on.  The sequence P, PP, PPP, PPPP, PPP^PP, etc. is called the counting hierarchy, and just as people conjecture that PH is infinite, so too one can conjecture (though maybe with less confidence!) that CH is infinite.  This is closely related to the belief that, in constant-depth threshold circuits (i.e., neural networks), adding more layers of threshold gates gives you more computational power.


It will be somewhat easier to replace $\{0,1\}$ with $\{\pm 1\}$, so that the parity function is just $x_1\cdots x_n$. Since this is an affine transformation, it doesn't affect degrees. I'm also assuming that the denominator of a rational function must be non-zero for all $\pm 1$ inputs. Since we only care about $\pm 1$ inputs, we work below over the ideal generated by $\{x_i^2 - 1\}$.

We prove by induction on $n$ that if $P/Q$ represents parity of length $n$ then $PQ = \alpha \prod_{i=1}^n x_i + \cdots$ for some positive $\alpha$, where the dots represent lower degree terms. This implies that $\deg P + \deg Q \geq n$. The claim is clearly true for $n = 0$. Now consider
$$\frac{P}{Q} = \frac{x_nP_1+P_2}{x_nQ_1+Q_2}, $$
where $P_1,P_2,Q_1,Q_2$ are over $x_1,\ldots,x_{n-1}$. Substituting $x_n=\pm1$ and applying the induction hypothesis, we deduce that for some $\alpha,\beta > 0$,
$$
\begin{align*}
(P_1+P_2)(Q_1+Q_2) &= \alpha \prod_{i=1}^{n-1} x_i + \cdots, \\
(P_1-P_2)(Q_1-Q_2) &= -\beta \prod_{i=1}^{n-1} x_i + \cdots. \\
\end{align*}
$$
Subtracting both equations, we get
$$ P_1 Q_2 + P_2 Q_1 = \frac{\alpha+\beta}{2} \prod_{i=1}^{n-1} x_i + \cdots. $$
Therefore
$$ PQ = (x_nP_1+P_2)(x_nQ_1+Q_2) = x_n(P_1Q_2+P_2Q_1) + \cdots = \frac{\alpha+\beta}{2} \prod_{i=1}^n x_i + \cdots. $$


If P = BQP, does this imply that PSPACE (= IP) = AM?

Great question!  Short answer: no implication like
$$
\mathsf{P} = \mathsf{BQP}   \Rightarrow  \mathsf{IP} = \mathsf{AM}
$$
is known; but that doesn't mean it's not worth trying to prove...

I would say, though, that finding such an implication seems unlikely.  I think the message of much quantum complexity theory is that, while quantum computers are not an all-purpose panacea for solving hard problems, they can be much more powerful than classical computers in certain specific circumstances.

For example, in query complexity, quantum algorithms can efficiently solve certain problems classical ones provably cannot, when the input is promised to obey some nice global structure.  E.g., Shor's algorithm is based on an algorithm to quickly find the unknown period of a function promised to be periodic.  On the other hand, quantum query algorithms are not too much stronger than classical ones for solving problems in which there is no special structure assumed on the input.  (See Buhrman and de Wolf's survey on query complexity for this last point.)

Similarly, I think the results $\mathsf{QIP}(3) = \mathsf{QIP} = \mathsf{IP}$ tell us, not that interaction is unexpectedly weak (even if $\mathsf{P} = \mathsf{BQP}$), but that quantum computation is unexpectedly strong, specifically in the context of interaction with computationally-unbounded provers.


Hidden constant in eps-sample size computation

I discovered after this publication that there is older work by
Dvoretzky-Kiefer-Wolfowitz in 1956 that looks specifically at this one-dimensional case for sampling.  There is also follow up by just Kiefer and Wolfowitz a year or two later that handles the (anchored) rectangle case.

For these specific settings, there has been some much more refined work looking at the actual constants.  Here is a reference that might help:

P. Massart, "The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality", 1990.

I don't know off-hand any other work on the constants other than the 1-d or "anchored" rectangle cases

Jeff


Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

Yes, there are such proofs in computability theory (a.k.a. recursion theory).

You can first show that the halting problem (the set $0'$) can be used to compute a set $G\subseteq\mathbb N$ that is 1-generic meaning that in a sense each $\Sigma^0_1$ fact about $G$ is decided by a finite prefix of $G$. Then it is easy to prove that such a set $G$ cannot be computable (i.e., decidable).

We could replace 1-generic here by 1-random, i.e., Martin-Löf random, for the same effect. This uses the Jockusch-Soare Low Basis Theorem.

(Warning: one might consider just showing that $0'$ computes Chaitin's $\Omega$, which is 1-random, but here we have to be careful about whether the proof that $\Omega$ is 1-random relies on the halting problem being undecidable! Therefore it's safer to just use the Low Basis Theorem).


For the statement to hold, f must grow exponentially, even with the unary alphabet.

[Edit: The analysis is improved slightly in revision 2.]

Here is a proof sketch.  Suppose that the statement holds and let f be a function such that every NFA with at most n states that accepts all strings with length at most f(n) accepts all strings whatsoever.  We will prove that for every C>0 and sufficiently large n, we have f(n) > 2C⋅√n.

The prime number theorem implies that for every c < lg e and for sufficiently large k, there are at least c ⋅2k / k primes in the range [2k, 2k+1].  We take c=1.  For such k, let Nk = ⌈2k / k⌉ and define an NFA Mk as follows.  Let p1, …, pNk be distinct primes in the range [2k, 2k+1].  The NFA Mk has Sk=1+p1+…+pNk states.  Apart from the initial state, the states are partitioned into Nk cycles where the ith cycle has length pi.  In each cycle, all but one state are accepted states.  The initial state has Nk outgoing edges, each of which goes to the state immediately after the rejected state in each cycle.  Finally, the initial state is also accepted.

Let Pk be the product p1…pNk.  It is easy to see that Mk accepts all strings of length less than Pk but rejects the string of length Pk.  Therefore, f(Sk)≥Pk.

Note that Sk ≤ 1 + Nk⋅2k+1 = o(22k) and that Pk ≥ (2k)Nk ≥ 22k.  The rest is standard.


Finding maximum weight arborescence in an edge-weighted DAG

The problem is NP-complete by a reduction from the set cover problem.

Set cover
Instance: A finite set U, a family C of subsets of U and k∈ℕ.
Question: Is there a cover D of U in C with at most k sets, that is, a subset D of C with |D|≤k such that the union of D is equal to U?

Given an instance (U, C, k) of the set cover problem, let U={a1, …, an} and C={S1, …, Sm} (n=|U|, m=|C|) and construct a DAG G with four layers of vertices:

The first layer consists of a single source s.
The second layer consists of m vertices x1, …, xm, each of which has an incoming edge from s with weight −1.
The third layer consists of n vertices y1, …, yn.  The vertex yi has an incoming edge from the vertex xj with weight 0 for each pair (i, j) such that ai∈Sj.
The fourth layer consists of n vertices z1, …, zn.  Each vertex zi has an incoming edge from the corresponding vertex yi with weight m.

Then it is easy to see that there is a cover of U in C with at most k sets if and only if the DAG G has an arborescence rooted at s with total weight at least nm−k.


The Flood Fill algorithm is a particular case of the Depth First Seach algorithm, on regular mesh graphs:

Wikipedia indicates that they do not work on the same kind of data:

The Flood Fill algorithm is "an algorithm that determines the area connected to a given node in a multi-dimensional array."
The Depth First Seach algorithm is "an algorithm for traversing or searching tree or graph data structures".

A multi-dimensional array (and the kind of neighborhood considered in the flood fill algorithm) is a particular case of graph, extremely regular.

In any case, the complexity is clearly within $O(n)$ where $n$ is the number of nodes being colored (for both problems).


I'd say no. Consider the following example. Let $(A,\land)$ and $(B,\land)$ be two unrelated semilattices. Let $(S,\land)$ be their direct product, and put $(a,b)\le_1(a',b')$ iff $a\le a'$, $(a,b)\le_2(a',b')$ iff $b\le b'$. Then your conditions are satisfied, even though the two preorders look nothing like each other.


This problem is sometimes called Subset Containment and it is computationally equivalent to: given $n$ sets $S_1,\ldots,S_n \subseteq [d]$, are there $i \neq j$ such that $S_i \cap S_j = \varnothing$? (I believe the reduction is folklore and appears in several places, but one concrete reference is the arxiv paper "Into the Square".) In turn, this disjointness problem is identical to the (gradually becoming infamous) Orthogonal Vectors (OV) problem.

Therefore, algorithms for OV apply directly to this problem. Hence the problem can be solved in $O(2^d \cdot n)$ time, $O(n^{2-1/O(\log(d/\log n))})$ time, and so on (see for example, this SODA'15 paper). Also, there is an $\tilde{O}(n + 2^d)$ time algorithm (I can give it, if you're interested). Furthermore, fine-grained hardness results for OV apply to the problem as well. For example, if it could be solved in $n^{1.999} 2^{o(d)}$ time in the worst case, then the Strong Exponential Time Hypothesis is false -- but don't let that stop you ;)

The "average case" (depending on how you define it) is generally easier and is (as far as we know) unrelated to Strong ETH; partial search data structures (such as Rivest's work on partial search from the 1970s) can be used to solve the average case in subquadratic time.


Funding opportunities for non-european people going to Europe for a PhD in TCS

Never having worked or studied in Spain, I can not really help with local information. However, as I mentioned in the comments, the most obvious source for such funding in European universities (aside from internal university or departmental sources and local research councils) would be funding from the European Research Council. The ERC has many different kinds of grants, including training networks and personal grants, which can often be used to fund overseas students from. Additionally, the European Commission offers funding for postgraduates and postdocs via Marie Curie actions.

Further, there is the China Scholarship Council which also offers support for students wishing to study abroad.

Then there are the industry scholarships: Google, IBM, Microsoft, etc.

If either of the students is female, then there are more options (see Google's Anita Borg scholarship, etc.).

Lastly, many European countries have bilateral agreements with China or Chinese institutions which may be another potential source of funding.


Who introduced nondeterministic computation?

I have always seen the notion of nondeterminism in computation attributed to Michael Rabin and Dana Scott. They defined nondeterministic finite automata in their famous paper Finite Automata and Their Decision Problems, 1959. Rabin's Turing Award citation also suggests that Rabin and Scott introduced nondeterministic machines.


Embedding points in Euclidean space into a box

Solved. The answer is to square the edge lengths and test if the result is L1 embeddable. Details to come at some unspecified future time.


There's been recent work on doing clustering in the MRC model (a formal model for analyzing mapreduce computations). Specifically, you should look at the work by Bahmani et al in VLDB 2012 on k-means$||$ and earlier work by Ene et al in KDD 2011 on the same topic. These papers have some discussion of the general problem of parallelizing $k$-means, which might be a good jumping off point for what you're interested in.


Computing parity of a permutation in a streaming-fashion way

I would like to ask everyone not to upvote this, as this is not an answer, but an extended comment, in which I would like to argue why this question did not receive any answers. My main point is, that a communication complexity lower bound won't work. By this, I mean that no matter how we cut the input into two parts and give it to two players, A and B, A can transfer a single bit to B from which he can compute the parity of the permutation. (This follows simply by considering inversions.)

Proofs that use another bound are hard.
See this comment here by Noam Nisan (for the non-deterministic version): Bounds on the size of the smallest NFA for L_k-distinct,

this related question by myself answered by Hermann Gruber which shows that the communication complexity lower bound can be very far from the truth (again in the non-deterministic version)
Lower bound for NFA accepting 3 letter language.

Also related that to decide whether the permutation is a single cycle, seems to be hard, see this FOCS paper by Ran Raz and Boris Spieker:
http://www.computer.org/csdl/proceedings/focs/1993/4370/00/0366870-abs.html.

So, I am also very interested to learn the answer to this question.


What do you mean by "should have"?

In principle you could train a neural network (a multi-layer perceptron, I assume) to perfectly classify the training set (provided that it doesn't contain conflicting examples), however doing so might require a long time (exponential in the size of the training set) and more importantly will usually impair the neural network ability to generalise to unseen data points.

In practice you usually divide your training examples in a training set proper and a validation set: train on the training set and after each epoch you measure accuracy on the validation set, repeat until the accuracy on the validation doesn't increase for a small number of epochs and keep the network with the best accuracy on the validation set. You might also reiterate the whole training process a few times starting from random weights each time, in order to avoid being trapped in local optima.
Moreover, you can experiment varying parameters such as the number of hidden layers, the number of nodes in each hidden layer, and the learning rate, changing the data encoding, and carefully selecting the input features.

Eventually your neural network will reach a maximum accuracy which depends on the problem difficulty.


As Ricky Demer said in his comment, many search problems can be sped up with sorting or building some other index structure
Lowest common ancestor queries can be answered in constant time with linear preprocessing.
Lots of text problems can be sped up with some preprocessing, e.g. building a suffix array


Refinements of pair approximation for network analysis

The way you formulate your question makes it sound like you care about dynamics, but since what you are looking for seems to be a steady state solution, ground states seem like a much more productive route to go down.

Since you want to go beyond pairwise approximation, the most natural candidate technique seems to be matrix product states, which is a pretty hot topic at the moment for dealing with quantum ground states. The way this approach works is basically by introducing maximally entangled pairs between nodes, and at each node introducing a projector. By adding higher dimensional systems you'll capture more features of the graph. I know your problem probably isn't quantum, but I don't see why this technique still shouldn't work. You should be able to simply replace the entangled states with $\frac{1}{2}(|00\rangle \langle 00| + |11\rangle \langle 11|).$

Also, I'm not sure if this is the kind of thing you are looking for or not, but there are some recent results on realizibility of scale-free networks, showing that they exhibit two phase transitions which seems to have just been accepted to PRL. A preprint entitled "All scale-free networks are sparse" can be found as arXiv:1106:5150.


Questions about computing matrix rigidity

The following additional references on Matrix Rigidity may be helpful:

Complexity Lower Bounds using Linear Algebra, S. V. Lokam,
in Foundations and Trends in Theoretical Computer Science, Volume 4, 1-2, 2009.
http://dx.doi.org/10.1561/0400000011
Using Elimination Theory to construct Rigid Matrices, A. Kumar, S.V. Lokam,. V. Patankar, J. Sarma,
ECCC TR09-106, http://eccc.hpi-web.de/report/2009/106/


Here is a partial answer:

Sometimes $H'$ is almost universal, but not always.

For an example of an $H$ that makes $H'$ almost universal, let $D$ be a field and consider $H_R = \{ h_x(a,b) = a + bx : x \in D\}$. $H_R$ is universal: Consider $(a,b) \neq (c,d)$. If $b \neq d$, then $(\Pr_x h_x(a,b) = h_x(c,d)) = (\Pr_x a + bx = c + dx) = (\Pr_x (b-d)x = c-a) = (\Pr_x x = (c-a)/(b-d)) = |D|^{-1}$. Otherwise, $b=d$, and thus $a \neq c$, and by a similar calculation $h_x(a,b) \neq h_x(c,d)$.

In this case, $\langle f,g \rangle(a,b,c,d)$ is a polynomial of degree $3$, with four terms with different coefficients. If $(a',b',c',d') \neq (a,b,c,d)$, $\langle f,g \rangle(a,b,c,d) - \langle f,g \rangle(a',b',c',d')$ is a polynomial of degree at most $3$ with at least one non-zero coefficient. By Schwartz-Zippel, $H'$ is almost universal.

If $H = \{h_x(a,b) = ax + b : x \in D\}$, then $\langle h_x, h_y \rangle(a,b,c,d) = ax + by + cx + d$, and $(c,b,a,d) \neq (a,b,c,d)$ is guaranteed to have the same hash value. Thus, $H'$ is not almost universal.


Has this bipartite graph problem been studied?

This can be solved in polynomial time: it is a system of linear equations over the integers, so you can solve it in polynomial time by forming the Hermite normal form.  This might not be the most efficient way to solve it...

If you want to express it as a flow, you could try the standard transformation of replacing every vertex $v$ with two vertices $v_\text{in},v_\text{out}$ with an edge $v_\text{in} \to v_\text{out}$; edges directed towards $v$ are replaced with edges to $v_\text{in}$, and edges out of $v$ are replaced with edges out of $v_\text{out}$.  I don't know whether that will help in your situation.


Rademacher complexity for piecewise-linear convex function

Since we're talking about real-valued functions, rather than VC-dimension, you probably want the fat-shattering one. The $\gamma$-fat-shattering of linear functions with $\ell_2$ norm bounded by $B$ is of order $(B/\gamma)^2$. For a $k$-fold maximum of such functions, the bound grows as $O((B/\gamma)^2k\log k)$, as shown here:
https://www.cs.bgu.ac.il/~karyeh/rademacher-max-hyperplane.pdf

This translates immediately into a Rademacher bound, given therein.

The $\log(k)$ factor cannot be removed in this case, as recently shown in
https://arxiv.org/abs/1807.07924

Edit: I had originally neglected to mention that the fat-shattering bound of $(B/\gamma)^2$ implicitly assumes that the instance space is confined to the Euclidean ($\ell_2$) unit ball. More generally, if the linear functions have $\ell_p$ norm at most $B$ and the data is confined to an $\ell_q$ ball of radius at most $R$, the bound becomes $BR/\gamma^2$,
where $1/p+1/q=1$, $p,q\ge1$.
This readily follows from the classic Rademacher analysis of "fat" hyperplanes: in the step where Cauchy-Schwarz is invoked, invoke instead Hölder.


Here are three in shortest paths research:

$1$. Is there a linear time algorithm for single source shortest paths in directed graphs with nonnegative weights, at least in the word-RAM model of computation? Note that a linear time algorithm exists for undirected graphs (see Thorup's paper). Based on that, Hagerup has a runtime of $O(n+m\log w)$ for directed graphs with weights bounded by $2^w$. Is there a faster algorithm?

$2$. Is there an $O(n^\omega$ polylog $n)$ algorithm for all pairs shortest paths in unweighted directed graphs? ($\omega<2.376$ is the exponent of matrix multiplication) The current best runtime is $O(n^{2.575})$ by Zwick, and for undirected graphs the problem can be solved in $O(n^\omega$ polylog $n)$.

(Are the directed problems actually harder?)

$3$. Is there an $O(n^{2.9})$ algorithm for all pairs shortest paths in $n$-node graphs with weights in {$0,\ldots,n$}? Or, is there a reduction from the general all pairs shortest paths problem to this restriction?


Succinct circuit representation of graphs

Your question seems to be asking: how does one represent arbitrary graphs (or even arbitrary path graphs) as a circuit of polynomial size? The answer is, you don't. The number of different path graphs with 2n vertices is (2n)!, far more than the number of different circuits with nc gates (exponential in nc log n). So almost all graphs with this many vertices cannot be represented by a succinct circuit.

Therefore, as you hint, in some sense only graphs that have a high degree of structure can be represented in this way. That's what makes complexity classes like PPAD interesting: despite the structure that we know the input graphs to the EOL problem must have, we don't seem to know how to take advantage of the structure to solve the problem efficiently.

If I'm misunderstanding your question and you're really asking: how does one make a circuit that even meets the input requirements for EOL, for even a very highly structured graph: try the path graph that connects vertex x (considered as a number in binary) to x-1 and x+1, with ends at zero and at 2^n-1. Or if you want something less trivial that seems more difficult to solve EOL for: let E and D be the encryption and decryption functions for a fixed key in your favorite cryptosystem, let the neighbors of x in the graph be E(x) and D(x), and let the ends of the line be 0 and D(0).


Complexity Theory in Finance and journals?

Not sure if such a combo can be useful in practice.

To answer your question, I don't think you have done your homework.

Look at the thread:
Computational complexity in quantitative finance

But if this is a general remark about the journal. The editorial board appears almost impeccable. Sure, it looks a bit suspect that the editor in chief advocated a field that has been dubbed controversial as seen in A New Kind of Finance.
Some critics maintain that the creation of the journal is strongly coupled with Wolfram Research's efforts to tap academics in the finance field. Other hidden agendas ?

Also consult with Wilmott's thread:
http://www.wilmott.com/messageview.cfm?catid=11&threadid=89959

Last, my 3 cents. The inaugural issue is one that usually sets the tone. Papers looked good.

Efficient Greek Estimation in Generic Swap-Rate Market Models.
This is by the great Mark Joshi. It deals with how to compute Greeks using automatic differentiation for a range of swap-rate market models. It's useful to practitioners since they want fast Greeks.

Markets are Efficient if and Only if P = NP. Not an expert in TCS, so refer to thread above computational-complexity-in-quantitative-finance for comments.

Forecasting Prices from Level-I Quotes in the Presence of Hidden Liquidity. Seemed important.

Binomial Options Pricing Has No Closed-Form Solution. Nifty. Nice read.


Suggested approach to cover data structure literature

If you're looking for data structures at a graduate level, my suggestion would be Erik Demaine's online course materials for his class "Advanced Data Structures" (video lectures and notes) available through MIT Open Courseware at https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/

Unfortunately I don't think there is really a good textbook on this material at this level; for this reason, in my own graduate data structures course, I use a collection of Wikipedia readings instead.


Factoring semiprimes whose factors very close to a power of two

If $0 \le k_p < 2^{b/2}$ and $0 \le k_q < 2^{b/2}$, it's easy to factor such numbers.  Consider:

$$N = pq = (2^b-k_p)(2^b-k_q) = 2^{2b} -(k_p+k_q) 2^b + k_p k_q.$$

Under the stated conditions, you can read off the values of $k_p k_q$ and $k_p+k_q$ from the binary representation of $N$, since $0 \le k_p k_q < 2^b$ and $0 \le k_p+k_q < 2^b$.  In particular, $k_p k_q$ can be obtained as $N \bmod 2^b$, and then you can compute $k_p + k_q$ as $(2^{2b} - N + k_p k_q)/2^b$.  Once you know those values, you can solve for $k_p,k_q$ by solving a quadratic equation (you have a system of 2 equations in 2 unknowns; simple algebra can be used to recover the value of the unknowns).  Once $k_p,k_q$ are known, the factorization of $N$ is immediately revealed.


Sum of products with bounded coefficients

An $O(n^2 \log r)$ bound can be obtained by Bézout's lemma:

  Lemma. For every integers $0 < c_i \leq n$, $\gcd(c_1,\ldots,c_r) = \sum_i m_i c_i$ for some integers $m_i$ with $|m_i| \leq n \log r$.

This lemma is obtained by recursively applying Bézout's lemma on two variables and the identity $\gcd(x_1,x_2,x_3) = \gcd(\gcd(x_1,x_2),x_3)$.

Without loss of generality assume that $\gcd(c_1,\ldots,c_r) = 1$ by dividing $\gcd(c_1,\ldots,c_r)$ on both sides of $\sum_i m_i c_i = k$. By Bézout's lemma there exists integers $m_i$ with $|m_i| \leq n \log r$ such that

$$k \cdot \sum_i m_i c_i = \sum_i (k \cdot m_i) c_i = k \cdot 1 \text,$$

by observing $k = O(n)$ we have the desired $m'_i = k \cdot m_i$ with $|m'_i| = O(n^2 \log r)$.

If you are searching for literature, the keyword is inhomogeneous linear Diophantine  equations, that is the equation $\sum_i m_i c_i = k$ when $k = 0$. For the homogeneous one, one can obtain a linear bound on $|m_i'|$, see e.g. this or this paper. As for the inhomogeneous one, I have not yet found such a result; however this paper seems relevant.


Reduction from independent set in hypergraphs to independent set in graphs

From the standard machinery, we can quickly deduce that there is a quasilinear-time reduction from $\textrm{IS-H}$ to $\textrm{IS}$. (But see below if quasilinear isn't good enough for you.)

Recall that $\textrm{3-SAT}$ is hard for $\mathsf{NTIME}[t(n)]$ under reductions that run in time $\tilde{O}(t(n))$, and in particular the resulting 3-CNF formula has size $\tilde{O}(t(n))$.

It's fairly straightforward to check that $\textrm{IS-H}$ can be solved in $\mathsf{NTIME}[\tilde{O}(n)]$ in any reasonable model of computation. (The naive algorithm has some dependence on $n \cdot k$, but this can be reduced with some sorting and binary search.) It follows that there is a reduction from $\textrm{IS-H}$ to $\textrm{3-SAT}$ which has only quasilinear blowup.

Additionally, the usual reduction from $\textrm{3-SAT}$ to $\textrm{IS}$, where 2-cliques are made for each variable and 3-cliques are made for each clause and some edges are added between clause gadgets and the clause's constituent variables' gadgets, has only linear blowup (a 3-CNF on $n$ variables and $m$ clauses gets mapped to an $\textrm{IS}$ instance with $2n+3m$ vertices and $2n+6m$ edges.

Composing these two reductions gives an overall quasilinear-blowup reduction from $\textrm{IS-H}$ to $\textrm{IS}$.

If a quasilinear-blowup reduction isn't good enough for you, we can work a little harder to get a linear-blowup reduction.

The idea is to replace the reduction from $\textrm{IS-H}$ to $\textrm{3-SAT}$ by a more efficient reduction. To do this, we'll reduce $\textrm{IS-H}$ to a version of $\textrm{Circuit-SAT}$ which takes as input circuits in which all gates have fan-in 2. This reduction will have linear blowup. From here, we can use the standard reduction from fan-in 2 $\textrm{Circuit-SAT}$ to $\textrm{3-SAT}$ (using the Tseitin transformation) which has only linear blowup. Composing these with the linear-blowup reduction from $\textrm{3-SAT}$ to $\textrm{IS}$ then completes a linear-blowup reduction from $\textrm{IS-H}$ to $\textrm{IS}$.

The reduction from $\textrm{IS-H}$ to $\textrm{Circuit-SAT}$ proceeds as follows. Let the input hypergraph be $(V,E)$, where we view $E \subseteq 2^V$ which doesn't contain the empty set. Let the input threshold be $k$.

We make variables $x_v$ for every vertex $v \in V$. We think of assignments to the variables as corresponding to subsets $S$ of the variables, where $v \in S$ if and only if $x_v \gets \texttt{True}$ in the assignment.
For each edge $e$, we construct a fan-in 2 formula computing $\bigvee_{v\in e} \overline{x_v}$, to rule out sets $S$ which are not independent sets.
Finally, we just need to translate the constraint $|S| \ge k$. To do this, we just need to give a linear-size, fan-in 2 circuit $\phi$ which takes as input $n$ bits and decides whether the number of bits set to $\texttt{True}$ is at least $k$. This can be done efficiently; see e.g. the answers here, but briefly the idea is just to efficiently compute the binary representation of the number of bits set to $\texttt{True}$, whence any symmetric function can be computed by a circuit of size linear in $n$.

It's easy to check that this is indeed a reduction from $\textrm{IS-H}$ to $\textrm{Circuit-SAT}$ in which the output has fan-in 2 gates and size only linear in the $\textrm{IS-H}$ instance. Moreover, the reduction results in a circuit of size $O(|V| + |E|)$ (where $|E|$ denotes $\sum_{e\in E}|e|$), and so we are done.


Proving the set of powers of 2 over ternary alphabet to be non regular.

Here's an alternative solution (with detailed explanation) using Myhill-Nerode Theorem. I'll use base $3$ and $2$ for readibility, but the proof generalizes for arbitrary bases $r,k$ that are not powers of the same integer.

(1) Show that given any ternary string $x$, there exists another string $y$ such that $xy$ is a power of $2$.

Proof: Given any $x$ (letting $n$ be the number it represents), $\forall k$ and $c\in \{0,\ldots,3^k-1 \}$, there exists $y$ such that $xy$ represents $3^kn + c$. In fact, this characterizes all the numbers $xy$ can represent. Hence, finding the minimal $y$ such that $xy$ is a power of $2$ is depends on finding the smallest integer $k$ such that we have some power of $2$ in the interval $[3^kn,3^k(n+1)-1]$. Taking log base $2$, we need to find $k$ such that we have an integer in the interval $[k\log 3 + \log x, k\log3 + \log(x+1)]$ (dropping the $-1$ here is iffy, but simplifies calculations which do not rely on it). Notice that changing $k$ only affects the $k\log 3$ portion, so we can find a $k$ that gets us arbitrarily close to some integer.

(2) Given some $x$ and the corresponding minimal $y$, show that there exists a string x' such that the corresponding minimal $y'$ has to be larger than $y$. Repeating this gives us infinitely many equivalence classes of strings.

Proof Outline: Since $\log 2^m x = m + \log x$, given an $x$ and its corresponding $y$ and $k$ we can always find some $x' = 2^m x$ where $\log(2^m x + 1) - \log (2^m x)$ is sufficiently tiny such that no integer is contained in $[k\log 3 + m +\log x, k\log3 + \log(2^mx+1)]$. Note that we are implicitly using the fact that $k\log 3 + \log x$ can never be an integer.


The paper you mention is probably one of Paul Vitányi's, possibly Time, Space, and Energy in Reversible Computing.

However, not everyone takes the viewpoint that simulation of irreversible computations is the main point. There is some research into what reversible computing can do in addition to such simulations, the beginnings of which is in Bennett's seminal paper Logical Reversibility of Computation on reversible Turing machines. See this paper for an elaboration of these ideas.

In terms of reversible logic circuits, there has been significant effort from the quantum computing community to build non-trivial circuits for arithmetic, e.g. Quantum networks for elementary arithmetic operations, some of which are purely classical, i.e., reversible. These implement a reversible variant of, say, addition, where one of the operands is conserved, but they do not rely on "irreversible thinking", do not use a history, and display a significant amount of ingenuity in their design.


Can you explain an intuition behind Coherent Spaces?

The intuition behind coherence spaces is that the elements of a coherence space represent observations of some underlying data, and the coherence relation tells you whether two observations could have come from the same piece of data.

Concretely, suppose we have a set of animals

Animals = {cat, duck, fish}

Now, we can have a set of observations:

Observations = {warm-blooded, swims, water-breathing, furry}

Let us say that two observations are compatible if they could both be made of the same animal. Every observation is compatible with itself, and in addition:

warm-blooded $\stackrel{{\large\frown}}{{\small\smile}}$ furry
warm-blooded $\stackrel{{\large\frown}}{{\small\smile}}$ swims
warm-blooded $\stackrel{{\large\frown}}{{\small\smile}}$ furry
swims $\stackrel{{\large\frown}}{{\small\smile}}$ water-breathing

We know that being warm-blooded is compatible with swimming, because ducks are both warm-blooded and swim. But being warm-blooded and water-breathing are not compatible, since we have no animals which are both warm-blooded and water-breathing.

At this point, we have defined a coherence space (Observations, $\stackrel{{\large\frown}}{{\small\smile}}$), where Observations is the web, and $\stackrel{{\large\frown}}{{\small\smile}}$ is the coherence relation.


Finding a cutting plane that splits a polyhedron evenly

I can't remember the analytic way to do this!

But this a classical problem for Genetic Programming! If you are familiar with it you can use a normalized vectors in the center of the polyhedron that describes the cutting plane.

So your population is a set of [x,y,z,...] normalized vectors and as fitting function you use the difference between the 2 split volumes!

So, if the difference tends to zero more "fit" is your vector/plane!


Time complexity for multiplying two lower triangular matrices

With the expert hints of Mr Emil, I could find a reduction of general matrix multiplication to triangular matrix multiplication. If we wish to multiply two $n \times n$ matrices $A$ and $B$, I can embed $A$ as $M_{32}^{th}$ block of a $3n \times 3n$ matrix $M$ with rest of the blocks all zero matrices. Similarly, I can embed $B$ as $N_{21}^{th}$ block of $3n \times 3n$ matrix $N$ with rest of the blocks all zero. Both M and N are lower triangular. An asymptotically faster algorithm for $M.N$ would then yield faster algorithm for $A.B$ too.

$$
\begin{bmatrix}
0 & 0 & 0\\
0 & 0 & 0\\
0 & A & 0
\end{bmatrix}
\begin{bmatrix}
0 & 0 & 0\\
B & 0 & 0\\
0 & 0 & 0
\end{bmatrix}
=
\begin{bmatrix}
0 & 0 & 0\\
0 & 0 & 0\\
AB & 0 & 0
\end{bmatrix}
$$

It's amazing how this argument does not manifest when trying to embed $A$ and $B$ in $2n \times 2n$ matrices!


Complexity of edge coloring in planar graphs

Every bridgeless planar cubic graph can be 3-edge-colored in quadratic time, as this task is equivalent to four-coloring a planar graph, which can be done in quadratic time. (See Robertson, Sanders, Seymour and Thomas: http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps )

EDIT: As Mathieu points out, cubic graphs with bridges are never 3-edge colourable.


For a concise overview the ideas you can read Mendelson's notes on the topic.

For a  bit more check out the outline (and the links in it) by Kontorovich on how the basic and most fundamental bonds where proved.

For a more extended discussinon you can go over lecture notes of statistical learning courses. Here is one for example.

If books are your favorite kind of learning source, any good theoretic statistical learning book will have chapters discussing the basics. Here's links for two relevant books.


Uniform mortality problem for Turing Machines

The mortality problem is undecidable (P.K. Hooper, Th eUndecidability of the Turing Machine Immortality Problem (1966))

The uniform mortality problem undecidability follows from the following:

Theorem: A Turing machine is mortal if and only if it is uniformly mortal

I found the proof in: Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: Undecidable Boundedness Problems for Datalog Programs. J. Log. Program. 25(2): 163-190 (1995)

Proof: Let $\delta_1,...,\delta_n$ be the possible transitions of $M$. We call a sequence $\delta_{i_1},..,\delta_{i_k}$ of transitions consistent if it reflects a computation of $M$, i.e., if there exists a configuration $c = (l,s,r,q)$ ($l$ left tape, $s$ symbol under head, $r$ right tape, $q$ current state) from which $M$ will execute that sequence.

Now arrange all consistent transition sequences in a (possibly infinite) tree, with the empty sequence at the root and each node extending the sequence at its parent by one transition. This tree is of bounded degree. Also (1) $M$ is mortal iff there is non infinite path in the tree, and (2) $M$ is uniformly mortal iff there are no arbitrarily long paths in the tree. By Konig's Lemma (in a tree of bounded degree there is an infinite path if and only if there is a family of paths of unbounded length), these two conditions are equivalent.


The complexity of the permanent of low rank matrices

The paper "Two algorithmic results for the traveling salesman problem" by Barvinok describes an $n^{\mathcal{O}(m)}$ algorithm for computing the permanent of a rank-m matrix. I don't know whether this can be improved to $\mathrm{poly}(n) 2^{\mathcal{O}(m)}$.

(I originally posted this as a comment. I post it as an answer by lack of any other answers.)


Voronoi diagram on surface of polyhedron

You can just use MMP k times, if you have k sites. For every face, you have to compute the additive weighted Voronoi diagram, and the overlay of k such diagrams still have linear complexity (because, it is just a planar additive weighted Voronoi idagram). As such, for a polytope with n faces and k sites, this takes $O(n^2 k \log n)$ time. You can use the latest monstrorisity by Sharir and Schriber and do it in $O(nk log n)$ time - but is not clear how to overlay the diagrams on every face. It is probably a good idea to look at their paper and see if they do something for this case.

As far as approximation, it is not hard to show that one can build a space decomposition of complexity $O(k/\epsilon^{O(1)} )$ such that given a query point, one can report the approximate nearest-neighbor on the polytope in $O( \log (k/\epsilon) )$ time. I think using some newer machinery, one can in fact also return the approximate distance in this time.


I’m not sure this is a research-level question, however solving linear systems over $\mathbb F_p$ is a $\mathrm{Mod}_p\mathrm L$-complete problem, hence in particular it is in $\mathrm{NC}^2$. More generally, linear algebra over $\mathbb F_{p^k}$ (at least for $k$ fixed) can be reduced to the $\mathbb F_p$ case.


Complexity class corresponding to sorting

The sorting problem is actually complete for $\mathsf{TC}^0$ (under $\mathsf{AC}^0$-reduction). A standard source for this is Section 1.4.3 of Vollmer's book.

Note that $\mathsf{TC}^0$ is the class of decision problems, but we usually think of sorting as a function problem, i.e., we want to output the numbers, say, in nondecreasing order. However, we can also define sorting as a decision problem as follows:

  Given a sequence of numbers $a_1,\ldots,a_n$ and two numbers $k,p\in [n]$, we want to decide if $a_k$ is at position $p$ in the sequence we get by sorting $a_1,\ldots,a_n$ in nondecreasing order. Note that to avoid ambiguity, when $a_i=a_j$, we want $a_i$ to precede $a_j$ if $i<j$.


(1) As finding a second satisfying assignment to a 3SAT formula is still $\mathsf{FNP}$-complete (indeed, it is $\mathsf{ASP}$-complete, see Theorem 3.5 of [1]), and we can encode 3SAT as an integer program by a parsimonious reduction, finding a second integer point in an integer program is also $\mathsf{NP}$-hard.

(2) Barvinok [2] showed that in fixed dimension, you can actually count the number of integer points in polynomial time, so the answer to your second question is $\mathsf{P}$.

[1] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003. (freely available author's copy)

[2] FOCS 1993


Obtaining the Axiom of Choice through a modality in HTT

There is a trivial sense in which the answer is yes.  For any proposition $P$, there's a modality $O_P$ called the open modality determined by $P$, defined by $O_P(X) \equiv (P\to X)$.  If you take $P$ to be the statement of the axiom of choice (relative to some universe), then for $M=O_P$ the type you showed is inhabited, since you get to use the axiom of choice in proving the conclusion.

However, this is not as useful as the double-negation modality for LEM.  To see why, notice that there is an even more trivial sense in which the answer is yes, namely when $M$ is the trivial modality, $M_{\rm triv}(X) \equiv \mathbf{1}$.  Obviously that's not very interesting.  The point is that $M_{\rm triv} = O_{\mathbf{0}}$, and  if we don't know whether $P=\mathbf{0}$ (such as when $P=\rm AC$), then we don't know whether $O_P = M_{\rm triv}$.  (And in fact, in models where $\rm AC$ is refutable, we do have $O_{\rm AC} = M_{\rm triv}$.)  The same argument applies to $P=\rm LEM$, of course; but $O_{\rm LEM}$ is not the same as double-negation, and we can prove that double-negation is always nontrivial (e.g. $\neg\neg \mathbf{0} = \mathbf{0}$).  So this "answer" is not really telling us anything.

As Ingo says, it seems unlikely that we can construct any provably-nontrivial modality with this property.  I don't know how to prove that we can't, but I think I can prove that no such lex modality can be constructed in the absence of univalence.  Take a model of ZF that doesn't satisfy AC.  Then its topos of sets is a model of MLTT with function extensionality, propositional extensionality, propositional truncation, and propositional resizing, in which lex modalities correspond to geometric subtoposes; but it has no proper nontrivial geometric subtoposes.

It should be possible to include Univalence as well, but I'm hazy on the necessary details.  Voevodsky's original simplicial model of HoTT has no nontrivial proper lex modalities, but its construction uses AC.  More recent cubical-type models of HoTT are constructive, but many of them do have nontrivial proper lex modalities.  Possibly the recent "equivariant" cartesian cubical model would work: it exists constructively, and classically is Quillen equivalent to the simplicial model and hence has no nontrivial proper lex modalities; but I'm not quite sure whether the latter equivalence uses AC or only LEM.

Relaxing lexness is going to be trickier, since even the classical simplicial model has lots of nontrivial proper non-lex modalities, like the $n$-truncations for all $n$.  I don't know whether there's any classification of all such modalities, or any other way to verify that none of them make AC true.


There are two natural strategies:

Put it on the arxiv, forget about publishing it somewhere else. I have several such writeups - people see them and cite them.

Go to lower venue conferences. Don't give up. I had a paper rejected 5 times before it got accepted, and it was a strong result that later appeared in a good journal. Rejection is just acceptance to the complement, etc.


Algorithms for graph generation given parameters

This question was posted more than 8 years ago, and much progress was done since then. However, many questions remain open, even very natural ones like sampling a random graph with prescribed clustering coefficient. Also, sampling simple graphs (no loop, no multi-edge) with prescribed degree sequence made much progress but remains difficult.
I would like to give a pointer to a quite comprehensive and recent survey on many aspects of these questions, which I think may be of interest to most readers of this post:
Recent Advances in Scalable Network Generation by
Manuel Penschuck, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, Peter Sanders, Christian Schulz, 2020
For the specific problem of graphs with prescribed degree sequence, I recommend:

Configuring Random Graph Models with Fixed Degree Sequences by
Bailey K. Fosdick, Daniel B. Larremore, Joel Nishimura, Johan Ugander, 2016
Fast uniform generation of random graphs with given degree sequences by
Andrii Arman, Pu Gao, Nicholas Wormald, 2020

but this is a very partial list, of course.
The last reference has a dedicated discussion of the regular case.


On $n$ dimensional manifolds and lattices

Here is a measure-free proof which works for affine manifolds over an arbitrary infinite field $\mathbb F$ (the result is false for finite fields).

By induction on $n\ge0$, we will show that an affine manifold $A\subseteq\mathbb F^m$ of dimension $n$ is not a finite union of affine manifolds of dimension less than $n$.

The statement is clear for $n=0$: a point is not a (finite) union of empty sets.

Assume the statement holds for $n$, we will show it for $n+1$. Let $A=\bigcup_{i<k}A_i$, where $\dim(A)=n+1$ and $\dim(A_i)\le n$. Consider an arbitrary affine submanifold $B\subset A$ of dimension $n$. Since $B=\bigcup_i(B\cap A_i)$, the induction hypothesis implies that $\dim(B\cap A_i)=n$ for some $i<k$, i.e., $B=A_i$. Since there are only $k$ sets $A_i$, and $B$ was arbitrary, it follows that $A$ has only finitely many submanifolds of dimension $n$. However, this is a contradiction: if we fix any such submanifold $B_0$ and a vector $v$ parallel to $A$ but not to $B_0$, there are infinitely many affine submanifolds of $A$ of the form $B_0+av$, where $a\in\mathbb F$.


What Is the Complexity of This Two-to-One Matching Problem?

EDIT: changed a few things to make this work with the new constraint, also rewrote the whole proof to add details and clarity.

The following is a reduction of minimum vertex cover to your problem.

Take the graph $(V, E)$ we want to solve minimum vertex cover on. Set $|V_{1}| = |V|^{2} + |V| + |E|$, $|V_{2}| = |E| + |V|$.

To every node $x \in V$ there correspond $|E| + 1$ nodes $a_{x, i}, b_{x}$ in $V_{1}$. To the edge with index $i$ there corresponds node $f_{i}$ in $V_{1}$ and $e_{i}$ in $V_{2}$. Additionally, there are $|V|$ nodes $c_{1}, \dots, c_{|V|}$ in $V_{2}$.

Add the edges $(a_{x, i}, b_{x})$ for all $i, x$ and $(b_{x}, c_{x})$ for all $x$. This way we get $S$ to be one larger if we use no edges starting from some $a_{x, i}$.

For every edge $(x, y) \in E$ with index $i$, add the edges $(a_{x, i}, e_{i}), (a_{y, i}, e_{i})$ and $(f_{i}, e_{i})$. The idea is that the edge $(f_{i}, e_{i})$ is "free".

We'll now show that there exists a vertex cover of size $k$ if and only if there exists an answer $S$ of size $|S| \geq 2|E| + |V| - k$.

Take any solution S to our instance, we'll modify it to create a solution $S'$ with $|S'| \geq |S|$ we can read a vertex cover of size $k \leq 2|E| + |V| - |S'| \leq 2|E| + |V| - |S|$ from.

If some edge $(f_{i}, e_{i})$ is not in $S'$, add it to $S'$, possibly removing one other edge adjacent to $e_{i}$. This can be done in $O(E)$ and doesn't decrease the size of $S'$.

Assume that the degree of $e_{i}$ corresponding to $(x, y)$ is not two, meaning that edge is "not covered". Then $a_{x, i}$ has degree zero, and we can add $(a_{x, i}, e_{i})$ to $S'$, possibly removing $(b_{x}, c_{x})$. This can be done in $O(E)$ and again doesn't decrease the size of $S'$.

Now we build a vertex cover: if we do not have the edge $(b_{x}, c_{x})$, add node $x$ to our vertex cover. Since the degree of $e_{i}$ is two for all $i$, $|S| \leq |S'| = 2|E| + (|V| - k)$ where $k$ is the size of our vertex cover. Hence we find a vertex cover of size $k \leq 2|E| + |V| - |S|$.

Now take any vertex cover of size $k$. Add to $S$ the edges $(f_{i}, e_{i})$ for all $i$. If $x$ is not in the vertex cover, add the edge $(b_{x}, c_{x})$. For every edge $i$ at least one of its endpoints $x$ is in the vertex cover, so $(b_{x}, c_{x})$ is not in our solution, so we can add $(a_{x, i}, e_{i})$ to $S$. Hence $|S| = 2|E| + (|V| - k) \implies k \geq 2|E| + |V| - |S|$.

Hence for maximum size set $S$ and minimum size of a vertex cover $k$ we have $k = 2|E| + |V| - |S|$, so there exists a vertex cover of size $k$ or less if and only if there exists a $S$ with size $2|E| + |V| - k$ or more.


Proof of $LP$ is in $coNP$ without showing it is in $P$?

Note: all vector inequalities in this reply are to be interpreted pointwise.
Given a linear feasibility problem, you can always rewrite it in the following canonical form: given a matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^m$, does there exist an $x \geq \vec{0}$ such that $Ax \leq b$?
Farkas' lemma states that when a system of inequalities such as the above has no solution, then there exists a "witness" vector $y \in \mathbb{R}^{m}$ such that

$y \geq \vec{0}$,
$A^{\intercal}y \geq \vec{0}$, and
$b^{\intercal}y < 0$.

Effectively, $b$ gives you a nonnegative scaling factor for each constraint, such that when you add up all of the scaled constraints, the left-hand side ends up with a sum of a bunch of nonnegative terms, and the right-hand side ends up with a strictly negative value. That is, $y$ provides a direct way to prove that the inequalities are inherently contradictory.
Therefore, the existence of such a $y$ is both a necessary and sufficient condition for any given problem instance to be infeasible, meaning that it can be used as a polynomial-time checkable certificate of infeasibilty. So linear feasibility checking is in co-NP.


Forbidden minors for bounded genus graphs

The disjoint union of $n$ copies of $K_5$ (or $K_{3,3}$) is a minimal forbidden minor for the graphs of genus $n-1$; the same is true for a graph in which some of these copies share a single vertex, so that the blocks of the graph are $K_5$ or $K_{3,3}$. This follows from results in J. Battle, F. Harary, Y. Kodama and J.W.T. Youngs, "Additivity of the genus of a graph", Bull. Amer. Math. Soc. 68 (1962) 565–568, and is already enough to show that there are at least exponentially many forbidden minors.

Bojan Mohar, "An obstruction to embedding graphs in surfaces", Discrete Math. 78 (1989) 135–142, lists the graph formed from $K_8$ by removing a 4-cycle as having genus 2. Since $K_7$ is toroidal, this means that either $K_8\setminus C_4$ or one of its spanning subgraphs is an obstruction to torus embedding, and that graphs that have $n$ copies of this graph as their blocks have genus $2n$.

Mohar also shows that the graph formed from a $(2k+2)$-cycle by connecting vertex 0 to all the even vertices and vertex 1 to all the odd vertices has "relative genus" at least $\lceil k/2\rceil$. The graph is planar, but I think relative genus means that the cycle has to be a face; or you could add another vertex to the graph, connected to all of the cycle vertices, to effectively force it to be a face. Maybe this is closer to the sort of thing you want. But I don't think he shows that these graphs are minimal forbidden minors.


is determining an unknown CFL from intersection of two CFLs decidable?

It's well-known you can present computation history of a Turing machine as an intersection of two CFLs. Take a deterministic Turing machine $M$ and force it to reject everything except possibly the empty word. The set of computation histories is either empty (if $M$ rejects the empty word), or a singleton (if there's an accepting computation for the empty word), and if there was an algorithm for your problem, you could tell those cases apart.


How does one augment AdaBoost with cross-validation?

The question is stated very succinctly; yet I think I can help since I'm familiar with the terminology. I'm gonna use information from Data Mining: Concepts and Techniques, which is a standard textbook.

Chapter 6 discusses different algorithms for classification. Then, in section 6.14, two methods are introduced for increasing the accuracy of a classifier:

Bagging: Creates an ensemble of models (classifiers or predictors) for a learning scheme where each model gives an equally-weighted prediction.
Boosting: Creates an ensemble of classiﬁers. Each one gives a weighted vote.

The two methods incorporate a base classifier, trying to improve its accuracy by sampling the data several times, and training the classifier on the sampled instance.

AdaBoost is a boosting method. (The name stands for "Adaptive Boosting".)

AdaBoost works as follows:

http://img181.imageshack.us/img181/8198/adaboost.png

The equation (6.66) mentioned in the image is as follows:

$error(M_i)=\sum\limits_j^d{w_j \times err(X_j)}$

where:

$error(M_i)$ is the error rate of model $M_i$;
$err(X_j)$ is the misclassiﬁcation error of tuple $X_j$: If the tuple was misclassiﬁed,
then $err(X_j)$ is 1. Otherwise, it is 0.

Now, what is cross-validation?

Quoting a part of section 6.13.2 of the above textbook:

  In k-fold cross-validation, the initial data are randomly partitioned into $k$ mutually
  exclusive subsets or “folds,” $D_1, D_2, \ldots , D_k$, each of approximately equal size. Training and testing is performed $k$ times. In iteration $i$, partition $D_i$ is reserved as the test
  set, and the remaining partitions are collectively used to train the model. That is, in
  the ﬁrst iteration, subsets $D_2, \ldots , D_k$ collectively serve as the training set in order to
  obtain a ﬁrst model, which is tested on $D_1$; the second iteration is trained on subsets
  $D_1, D_3, \ldots , D_k$ and tested on $D_2$; and so on.

Can AdaBoost be Augmented with Cross-Validation?

Yes. In AdaBoost, you need $D$, a set of $d$ class-labeled training tuples. Applying a k-fold cross-validation on this set, you will have 1 test sample (containing $d/k$ tuples) and $k-1$ training samples (containing $d(k-1)/k$ tuples). Using this strategy, and iterating $k$ times, the algorithm will benefit from the best of both worlds.

Note that cross-validation is an accuracy evaluation method, while AdaBoost is an accuracy improvement method. In the method I suggested above, cross-validation is used to retain the best classifier obtained from AdaBoost (in terms of accuracy), and discarding other classifiers.


As far as I can see, the value of each item depends on which bin it is added to. Its full quality if it is added to its primary preference, and a reduced quality (reduced by -0.5 and -1, respectively) for its secondary and tertiary preferences. Do I understand you correctly?

In this case, this problem can be formulated as a min-cost flow problem, which resembles min-cost bipartite matching (but with the added twist of bin capacity). I.e., it is not an NP-hard bin packing problem at all (unless P=NP).

Construct a flow network with a source, a sink, and two "layers" of nodes, corresponding to the items (first layer) and bins (second layer). Add edges from the source to the items (zero cost, capacity 1) and from the bins to the sink (zero cost, capacity equal to the bin capacity, i.e., from 1 to 3). From each item, you add an edge to each of its primary, secondary and tertiary bins, with capacity 1 and a cost of its adjusted quality multiplied by -1 (to go from a positive value to a negative cost).

Now just run a standard min-cost-flow (or min-cost max-flow) algorithm to get your answer.

Of course, not all items will be matched if the total capacity is less than the number of items, but the match will produce the matching that gives the greatest total (adjusted) quality.

If you don't want to muck about with min-cost flow, you could split each bin node into multiple nodes (the number of nodes corresponding to the bin capacity), and duplicate the edges from the items. So if an item has an edge with a given cost to a bin node with a capacity of 3, you'd now have 3 bin nodes, and that item would have an edge to each of them with the given cost. You could then just use an algorithm for min-cost bipartite matching, such as the Hungarian algorithm. (You will now no longer have a source or a sink, of course.)

This latter version is probably more practical to implement, and libraries for the Kuhn-Munkres algorithm are available in multiple languages.


Data structures is nothing but the ways how data of different kinds can be structured in a systematic way. The actual definition may be somewhat lengthy and descriptive which can be found on different sources. But it is all about defining structures of your data that will satisfy your need to solve any particular problem.


Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms

New answer:
The number of pseudo line arrangements is 2^{Theta(n^2)} http://page.math.tu-berlin.de/~felsner/Paper/numarr.pdf . Which is in turn can be used to bound the number order type of n points in the plane. Thus if you want to check some concrete conjecture on point configurations in the plane, you are going to get your desired running time. Examples of algorithms using this approach and use this approach are here: http://www.ist.tugraz.at/aichholzer/research/rp/triangulations/ordertypes/ . If you do not aggressively cut the search space for the specific conjecture you are checking, you would get the running you want.

In a similar direction, checking if a generic property holds for all binary n*n matrices, would take this running time. This in particular, the time it would take to verify a "generic" property over graphs over n vertices. As a "silly" example, think about a Ramsey type conjecture: Every graph over n vertices contains either a clique or an independent set of size $\Theta(\log n)$. Ha! This running time is explicitly mentioned in the Wikipedia page: http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers.

Old answer:
Some variants of Cylindrical algebraic decomposition if my memory serves me right.

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


Are there other computer architectures apart fom the von neumann /turing architectures?

Turing machine is an abstract computational model which has its strengths and weaknesses.
Von Neumann architecture is a way to implement it.
There are several other computational models. You can find a list of many of them here


Is $\mathsf{P} = \mathsf{NP}$ relative to a universal predictor?

I am not familiar with the notion of universal predictor, and I did not follow everything you wrote; in particular, I did not follow your sketch of the proof of existence of a universal predictor in E.  But assuming that there exists a universal open predictor that belongs to E, the answer to your question is positive.  And I am afraid that you will probably be disappointed by the reason.

Edit in revision 2: I changed the construction in response to the added restriction in revision 2 of the question, but the general idea is the same: mix a hard language into a universal open predictor in such a way that the definition of universal open predictor does not notice the difference.

Let T = {0|x|11x: x∈{0,1}*}.  Note that every word in T has an even length.  An important property of T is that no word in T is a proper prefix of another word in T.  This implies that if the symmetric difference between two languages V and W is contained in T, then for every infinite sequence s∈{0,1}ω, there is at most one n such that χV(s<2n)≠χW(s<2n), and in particular V is a universal open predictor if and only if W is a universal open predictor.

It is easy to see that there exists an EXPSPACE-complete language which is a subset of T.  Let L be such a language.  Let V be a universal open predictor that belongs to E, and hence also to EXPSPACE.  Define a language W = L ∪ (V∖T).  Because V is a universal open predictor and the symmetric difference between V and W is contained in T, W is also a universal open predictor.  It is easy to see that W is EXPSPACE-complete, and therefore PW = NPW = EXPSPACE.  This concludes that W satisfies the desired property.


Lower bound of the time complexity of heap building

It is essentially using decision tree model to obtain the lower-bound. There are $n!/H(n)$ leafs in the decision tree, it is a binary tree, therefore the height of the tree is at least $\lg (n!/H(n))$.


First-order multi arity functions in dependent type?

I do not understand what you are asking for, as it seems that you are simply asking for record types. The comments are too terse for a normal discussion, so I will offer a solution here, and you tell us what is wrong with it. I will do it by way of an example.

Suppose we are given the following types:
\begin{align*}
& \vdash A \ \mathsf{type} \\
x : A & \vdash B(x) \ \mathsf{type} \\
x : A, y : B(x) & \vdash C(x,y) \ \mathsf{type}
\end{align*}
We would like the type of "binary" dependent functions whose domain is something like $x : A, y : B(x)$ and the codomain is $C(x, y)$.

Let us write
$$
\{ \ell_1 : A_1, \ell_2 : A_2(\ell_1), \ldots, \ell_n : A_n(\ell_1, \ldots, \ell_{n-1})
\}
$$
for a dependent record type with fields $\ell_i$. Observe that this looks a lot like a chunk of a context. Given a term $p$ of the above type, write $p.\ell_i$ for the $i$-th projection.

Without any pattern matching the type of dependent functions from $x : A, y : B(x)$ to $C(x, y)$ can be written as
$$\Pi (p : \{x : A, y : B(x)\}) \,.\, C(p.x, p.y),$$
which is arguably not so nice. But since patterns for record types are irrefutable (they always match), we can also use pattern-matching to write
$$\Pi (\{x = x_0, y = y_0\}) \,.\, C(x_0, y_0).$$
or, if we dare use the same symbol for a field label and the bound variable (OCaml allows this, for instance),
$$\Pi (\{x, y\}) \,.\, C(x, y),$$
For such pattern matching to make sense we need to know ahead of time that the fields $x$ and $y$ have types $A$ and $B(x)$, respectively. In implementations of proof assistants this is typically not a problem as each record type has to be declared before it can be used. Otherwise, we can still write something like
$$\Pi (\{x : A , y : B(x)\}) \,.\, C(x, y)$$
to indicate the missing type information.

Of course, the same sort of ideas apply to $\lambda$-abstraction. Given
$$x : A, y : B(x) \vdash e(x,y) : C(x,y)$$
the term
$$\lambda \{x : A, y : B(x)\} \,.\, e(x,y)$$
will receive the above product type.

In any case, it seems that we can have pattern matching on the records and get precisely what you are asking for. I kindly ask that, in case this is not what you are asking for, you modify your question and provide some concrete examples of what you are looking for.


[Is there] a formal representation of
  a distributed system on top of a
  turing machine?

Regarding this, the discussion (see link posted by Jukka on comments) is the way to look. The way, I see it, how you would formally represent a distributed system largely depends on how you view them, and that depends on "your favourite system assumptions" (i.e., the assumptions on synchrony (i.e., relative timing of actions in the distributed system), on communication (message passing vs. shared memory), on faults (of processes and/or links, benign or Byzantine, etc). As the community does not agree on this point, there is also no agreement on the basic formalism.

  [Is] it
  possible to extend (make a variant)
  the concept of a turing machine to
  take advantage of distributed
  computing?

I guess it is entirely possible, but no-one (that I know of) has looked into it.
What I know of are these:

Timed IO Automata also used in Lynch's Distributed Computing book
Communicating Sequential Processes
Temporal logic of actions
Pi-Calculus (also already mentioned by Alex)
And more (have been and will be mentioned here)...


Post correspondence problem for finite monoids

Yes, it is decidable.  Build a graph where each vertex is a pair $(r,s)$ of elements from $M$.  Add all edges of the form $(r,s) \to (r m_i, s m'_i)$ for all $r,s,i$.  Then, your question asks whether there exists a path in this graph from the vertex $(1,1)$ to any vertex of the form $(t,t)$.  This can be answered using standard reachability algorithms (e.g., DFS).  The running time is linear in the size of the graph (i.e., $O(|M|^2 n)$), so the problem is decidable.


Can multipebble automata decide all deterministic context-sensitive languages?

No. Counterexample: the halting problem for MPAs is decidable in linear space: if the MPA has N states, we need |k|+2 bits of space to store the pebble locations, log N bits to store the current state and $\log(N(|k|+2))+|k|+2$ bits to store a counter; if the counter cycles, the simulated machine will never halt. This is linear in |k| (ignoring the O(N \log N) space required to describe the machine), as required.

Since this language is decidable in linear space, it is also expressible as a DCSL.


Program transformation using partial functions which preserve partial correctness

I imagine that you can prove this straight from the operational
semantics using the standard operational precongruence (assuming that
you have a sequential language). Some of the relevant techniques
have been collected in Operationally-based theories of program equivalence by
Andy Pitts.

If you have a Hoare logic of partial correctness for the language you are interested
in, you can probably
establish a meta-theorem to the effect that for all programs $M$, all
models $\xi, \xi'$ such that $\xi$ is less defined than $\xi'$, and
all formulae $A, B$, we have
$\xi \models \{A\} M \{B\}$ implies $\xi' \models\{A\} M \{B\}$.  Proving such
a meta-theorem typically boils down to the operational reasoning
mentioned above.

Such questions come up all the time in proving observational and
descriptive completeness of Hoare logics. As Neel points out in
an answer to your other question, domain theory is based upon
related ideas.


Who said: "There is no central arbiter of truth in open distributed systems."

The exact quotation seems to be:

  "Pluralism: There is no central arbiter of truth in the system."

See:

http://archive.org/stream/byte-magazine-1985-04/1985_04_BYTE_10-04_Artificial_Intelligence#page/n237/mode/2up

(p. 239, 2nd bullet point.)


Optimal payoff from sampling from a collection of Bernoulli random variables?

This is called the explore/exploit trade-off in machine learning.  This scenario is precisely captured by the multi-armed bandit problem with i.i.d. payoffs.  Algorithms such as UCB and Exp3 will get you an expected payoff within $\tilde{O}(\sqrt{Kn})$ of the optimal, and you asymptotically cannot do better.


To what extent can an algorithm predict the time complexity an arbitrary input program?

In general you cannot determine complexity, even for halting programs: let $T$ be some arbitrary Turing machine and let $p_T$ be the program (that always returns 0):

input: n
run T for n steps
if T is in halting state, output: 0
otherwise, loop for n^2 steps and output: 0

It is clear that it is undecidable in general whether $p_T$ is linear-time or quadratic-time.

However, much work has been carried out on the effective computation of program complexity. I have particular fondness for Implicit Complexity Theory which aims at creating languages that, using special constructs or type disciplines, allows one to write only programs that inhabit a certain well-defined complexity class. By what I consider to be something of a miracle, these languages are often complete for that class!

One particularly nice example is described in this paper by J.-Y. Marion, which describes a tiny imperative language, with a type discipline inspired from information-flow and security analysis techniques, which allows a characterization of algorithms in P.


Resources for Church's paper "An Unsolvable Problem of Elementary Number Theory"?

The article "The Church-Turing Thesis" of the Standford Encyclopedia of Philosophy might help and/or provide references to texts that might be useful to you. The article by Joachim Breitner Church’s undecidability result might help you as well.


ETH itself precludes this possibility.

In https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf
 we show that any $n^{O(1)} n^{k/\alpha(k)}$ time algorithm for k-SUM, for any monotone nondecreasing unbounded function $\alpha$, would imply ETH is false.


How to prove fooling set problem to be NP-hard

The proof is given in Section 6 the full version of the paper. I bring an excerpt, since there was originally much confusion about what "fooling set" means.

Basically, the notion of fooling set was introduced by Jean-Camille Birget in Intersection and union of regular languages and state complexity.

To prove that fooling set problem (as defined below) is NP-hard, the authors reduced the NP-complete induced matching problem on bipartite graphs to it.

Here's an excerpt of the paper, which defines the problem and proves the theorem.


Here is another approach, based on information theory and heavily inspired by @usul's answer. It shows that $\epsilon_n=O(1)$ with very few calculations, and can be used to prove that $\epsilon_n \rightarrow \log_2 \sqrt{e}$ and to derive good estimates on the rate of convergence with less calculations than @usul's approach. In fact, I find a closed-form expression for $\epsilon_n$ : $$(1)  \; \; \; \; \epsilon_n = n \left( H(Binom(n,1/2)) - H \left( Binom \left( n-1, 1/2 \right) \right) \right) \ .$$

Details:

Let $X$ be a uniform random variable in $\{0,1\}^n$. Let $K$ be a random variable equal to the number of 1's in $X$. The expression $\#$ that @Danny wants to analyze is exactly equal to $n \cdot \mathbb{E}_{k} [H(X_1 | K=k)]$. (Here $X_1$ is the first bit of $X$.) By the basic properties of the entropy operator,
$$(2)  \; \; \; \; \# = n\mathbb{E}_{k} [H(X_1 | K=k)]=nH(X_1|K)=n(H(X_1K)-H(K))=n(H(K|X_1)+H(X_1)-H(K)) = n(1-H(Binom(n,1/2)) + H(Binom(n-1,1/2))) \ .$$
The last equality follows from the fact that $X_1$ is just a uniformly random bit, $K$ is the binomial distribution, and $K|(X_1=x_1)$ is distributed either as $Binom(n-1,1/2)$ or as $Binom(n-1,1/2)+1$, depending on the value of $x_1$, both of which have the same entropy.

This already gave us equation (1). Now we just need to calculate to get the value of $\lim_{n \rightarrow \infty} \epsilon_n$

We use any known estimation for the entropy of a binomial RV, such as here. We see that $$ (3)  \; \; \; \; H(K)=H(Binom(n,1/2))=\frac12 \log_2 ( \pi en / 2) + O(1/n) \ ,$$ and, similarly, that $$H(K|X_1)=H(Binom(n-1,1/2))=\frac12 \log_2 ( \pi e(n-1)/2) + O(1/n) \ .$$ Canceling out terms and substituting into (1), we get $$ (4)  \; \; \; \; \epsilon_n = n \cdot (H(K)-H(K|X_1)) = n \cdot \frac12 (\log_2 (n/(n-1)) + O(1/n)) = \\ \frac12 \log_2 ((n/(n-1))^n) + O(1) \rightarrow \log_2(\sqrt{e}) + O(1) \ . $$

By slightly improving the approximation (3) we should be able to replace the $O(1)$ term in (4) by $O(1/n)$ and therefore get that, indeed, $\lim_{n \rightarrow \infty} \epsilon_n = \log_2 \sqrt{e}$. To get this better estimation it should be enough to check that $H(Binom(n,1/2))=\frac12 \log_2 ( \pi en / 2) + err(n)$ where $err(n)=O(1/n)$ and $err$ is a monotone function.


Complexity of reachability in linear dynamical systems over finite fields

For clarity, I'm going to generalize your question to be over characteristic $p
> 0$ (with base field $\mathbb{F}_q$) instead of the specific case of $p=q=2$.
I'll take $p$ and $q$ as a fixed constants;
I'll leave it to the reader to figure out what the exact dependence on these parameters is,
as there are some tradeoffs that can be made.
The end result here is that your problem is roughly equivalent to the discrete
log problem for finite fields of characteristic $p$.

To be more specific,
let the ordinary discrete log problem over extensions of $\mathbb{F}_q$ be,
given an extension field $\mathbb{F}$ of $\mathbb{F}_q$, and $a,b \in \mathbb{F}$,
find any integer $t$ so that $a = b^t$,
or report that none exists.
Let the strong discrete log problem over extensions of $\mathbb{F}_q$ be,
given $\mathbb{F},a,b$ as before, find integers $z,m$ so that
$a = b^t$ for an integer $t$ iff $t = z \pmod{m}$,
or report that no $t$ exists.
Then the following reductions exist:

There is a deterministic mapping reduction from discrete log over extensions of $\mathbb{F}_q$ to your problem.
There is an efficient, deterministic algorithm which solves your problem
when given access to an oracle computing the strong discrete log problem
over extensions of $\mathbb{F}_q$.

Accordingly, I'd consider it unlikely that somebody will post a proof of
$\mathsf{NP}$-hardness or a proof that your problem is in $\mathsf{P}$ in the
near future.

Remark: The strong discrete log problem over extensions of $\mathbb{F}_q$
can be Turing-reduced to the following ostensibly weaker form
(though still seemingly stronger than the ordinary discrete log problem):
Given an extension field $\mathbb{F}$ of $\mathbb{F}_q$, and $a,b \in \mathbb{F}$,
find the least, non-negative integer $t$ so that $a = b^t$.
This follows from the fact that the order of $b$ is one plus the smallest
non-negative $t$ so that $b^{-1} = b^t$.

First reduction:
The claim is that the ordinary discrete log problem over extensions of $\mathbb{F}_{q}$ mapping-reduces to this problem.
This follows the fact that multiplication in $\mathbb{F}_{q^n}$ is a linear transformation
when we view $\mathbb{F}_{q^n}$ as an $n$-dimensional vector space over $\mathbb{F}_q$.
Hence a question of the form $a = b^t$ over $\mathbb{F}_{q^n}$
becomes $\vec{a} = B^t\vec{e}$ over $\mathbb{F}_q$, where $\vec{a},\vec{e}$ are $n$-dimensional vectors,
and $B$ is an $n\times n$ matrix, all over $\mathbb{F}_q$.
The vector $\vec{a}$ can be easily computed from $a$, $B$ from $b$, and
$\vec{e}$ is just the representation of $1 \in \mathbb{F}_{q^n}$, which can be
written down efficiently.
This appears to still be a hard case of the general discrete log problem,
even with $p=q=2$ (but growing $n$, of course).
In particular, people are still competing to see how far out they can compute it.

Second reduction:
The claim is that your problem reduces to the strong discrete log problem over extensions of $\mathbb{F}_q$.
This reduction has a few pieces to it, so forgive the length.
Let the input be the $n$-dimensional vectors $x,y$ and $n\times n$ matrix $A$, all over $\mathbb{F}_q$;
the goal is to find $t$ so that $y = A^tx$.

The basic idea is to write $A$ in Jordan canonical form (JCF),
from which we can reduce testing $y = A^tx$ to the strong discrete log problem
with some straightforward algebra.

One reason for using a canonical form under similarity of matrices
is that if $A = P^{-1}JP$, then $A^t = P^{-1}J^tP$.
Hence we can transform $y = A^tx$ to $(Py) = J^t(Px)$,
where now $J$ is in a much nicer format than the arbitrary $A$.
The JCF is a particularly simple form, which enables the rest of the algorithm.
So from now on, assume that $A$ is already in JCF,
but also allow that $x,y,$ and $A$ may have entries in an extension field of
$\mathbb{F}_q$.

Remark: There are some subtleties that arise from working with the JCF.
Specifically, I'll assume that we can do field operations within any extension
of $\mathbb{F}_q$ (no matter how large) in one time step,
and that we can compute the JCF efficiently.
a priori, this is unrealistic, because working with the JCF may require
working in an extension field (the splitting field of the characteristic polynomial)
of exponential degree.
However, with some care, and using the fact that we're working over a finite field,
we can circumvent these issues.
In particular,
we will associate with each Jordan block a field $\mathbb{F}'$ of degree at most $n$ over $\mathbb{F}_q$
so that all the entries in the Jordan block and the corresponding elements of $x$,$y$
all live within $\mathbb{F}'$.
The field $\mathbb{F}'$ may differ from block to block,
but using this ``mixed representation'' allows for an efficient description of the JCF,
which moreover can be found efficiently.
The algorithm described in the remainder of this section only needs to work
with one block at a time,
so as long as it does its field operations within the associated field $\mathbb{F}'$,
the algorithm will be efficient.
[end remark]

The use of JCF gives us equations of the following form,
with each equation corresponding to a Jordan block:
$$
\begin{bmatrix}
  y_1 \\
  y_2 \\
  y_3 \\
  \vdots \\
  y_{k-1} \\
  y_{k} \\
\end{bmatrix}
=
\begin{bmatrix}
\lambda & 1       &         &        &         &         \\
    & \lambda & 1       &        &         &         \\
    &         & \lambda & 1      &         &         \\
    &         &         & \ddots &         &         \\
    &         &         &        & \lambda & 1       \\
    &         &         &        &         & \lambda \\
\end{bmatrix}^t
\begin{bmatrix}
  x_1 \\
  x_2 \\
  x_3 \\
  \vdots \\
  x_{k-1} \\
  x_{k} \\
\end{bmatrix}$$

The algorithm will handle each block separately.
In the general case, for each block, we'll have a query for our strong discrete log oracle,
from which the oracle will tell us a modularity condition, $t = z \pmod{m}$.
We'll also get a set $S \subseteq \{0,1,\cdots,p-1\}$ so that
$\bigvee_{s\in S}\left[ t = s \pmod{p} \right]$
must hold.
After processing all the blocks,
we'll need to check that there is a choice of $t$ that satisfies the conjunctions of all these conditions.
This can be done by making sure there is a common element $s$ in all the sets $S$
so that the equations $t = s \pmod p$ and $t = z_j \pmod{m_j}$ are all simultaneously satisfied,
where $j$ ranges over the blocks.

There are also some special cases that arise throughout the procedure.
In these cases,
we'll get conditions of the form $t > \ell$ for some value of $\ell$,
or of the form $t = s$ for some specific integer $s$, from certain blocks,
or we might even find that no $t$ can exist.
These can be incorporated into the logic for the general case without issue.

We now describe the subprocedure for handling each Jordan block.
Fix such a block.

Begin by focusing on just the last coordinate in the block.
The condition $y = A^tx$ requires that $y_k = \lambda^t x_k$.
In other words, it's an instance of the discrete log problem in some field extension of $\mathbb{F}_q$.
We then use an oracle to solve it,
which either results in no solution,
or else gives a modularity condition on $t$.
If "no solution" is returned, we return indicating such.
Otherwise,
we get a condition $t = z \pmod{m}$,
which is equivalent to $y_k = \lambda^t x_k$.

To handle the other coordinates,
we start with the following formula
(see, eg, here):
$$
\begin{bmatrix}
\lambda & 1       &         &        &         &         \\
    & \lambda & 1       &        &         &         \\
    &         & \lambda & 1      &         &         \\
    &         &         & \ddots &         &         \\
    &         &         &        & \lambda & 1       \\
    &         &         &        &         & \lambda \\
\end{bmatrix}^t
=
\begin{bmatrix}
\lambda^t & \binom{t}{1}\lambda^{t-1} & \binom{t}{2}\lambda^{t-2} & \cdots & \cdots & \binom{t}{k-1}\lambda^{t-k+1} \\
 & \lambda^t & \binom{t}{1}\lambda^{t-1} & \cdots & \cdots & \binom{t}{k-2}\lambda^{t-k+2} \\
 &  & \ddots & \ddots & \vdots & \vdots\\
 &  & & \ddots & \ddots & \vdots\\
 &  & &  & \lambda^t & \binom{t}{1}\lambda^{t-1}\\
 &  &  &  &  & \lambda^t
\end{bmatrix}$$
First, let's take care of the case in which $x_k = 0$.
Since we already have the modularity condition which implies $y_k = \lambda^t x_k$,
we can assume that $y_k = 0$ also.
But then we can just reduce to focusing on the first $k-1$ entries of $x$ and $y$,
and the top left $(k-1)\times (k-1)$ submatrix of the Jordan block.
So from now on, assume that $x_k \ne 0$.

Second, we'll handle the case in which $\lambda = 0$.
In this case,
the powers of the Jordan block have a special form,
and force either $t = z$ for some $z \le k$,
or else $t > k$, with no other conditions.
I won't belabor the cases, but suffice it to say that each can be checked for efficiently.
(Alternatively, we could reduce to the case where $A$ is invertible; see my comment on the question.)

Finally, we arrive at the general case.
Since we already have the modularity condition which implies that $y_k = \lambda^t x_k$,
we can assume that condition holds, and use $y_k x_k^{-1}$ as a stand-in for $\lambda^t$.
More generally, we can use $y_kx_k^{-1}\lambda^{-z}$ to represent $\lambda^{t-z}$.
Thus we need to check if the following system holds for some choice of $t$:
$$
\begin{bmatrix}
  y_1 \\
  y_2 \\
  y_3 \\
  \vdots \\
  y_{k-1} \\
  y_{k} \\
\end{bmatrix}
=
\begin{bmatrix}
y_kx_k^{-1} & \binom{t}{1}y_kx_k^{-1}\lambda^{-1} & \binom{t}{2}y_kx_k^{-1}\lambda^{-2} & \cdots & \cdots & \binom{t}{k-1}y_kx_k^{-1}\lambda^{-(k-1)} \\
 & y_kx_k^{-1} & \binom{t}{1}y_kx_k^{-1}\lambda^{-1} & \cdots & \cdots & \binom{t}{k-2}y_kx_k^{-1}\lambda^{-(k-2)} \\
 &  & \ddots & \ddots & \vdots & \vdots\\
 &  & & \ddots & \ddots & \vdots\\
 &  & &  & y_kx_k^{-1} & \binom{t}{1}y_kx_k^{-1}\lambda^{-1}\\
 &  &  &  &  & y_kx_k^{-1}
\end{bmatrix}
\begin{bmatrix}
  x_1 \\
  x_2 \\
  x_3 \\
  \vdots \\
  x_{k-1} \\
  x_{k} \\
\end{bmatrix}
$$
Observe that whether the equation holds depends only on $t \pmod{p}$;
this is because the dependence on $t$ is only polynomial,
$t$ must be an integer,
and the above equations are over a field of characteristic $p$.
Hence we can just try each value of $t \in \{0,1,\ldots,p-1\}$ separately.
The set $S$ we will return is just the choices of $t$ for which the system is
satisfied.

So now, except for some special cases, the per-block subprocedure has found a modularity condition $t = a \pmod{m}$,
and a set $S$ so that one of $t = s \pmod{p}$ must hold for some $s \in S$.
These conditions are equivalent to $y = A^tx$ within this specific Jordan block.
So we return these from the subprocedure.
The special cases either conclude that no $t$ can exist (in which case the subprocedure immediately returns an indication of that),
or else we have a modularity condition $t = a \pmod{m}$ and some special condition like $t = s$ for an integer $s$,
or $t > \ell$ for some integer $\ell$.
In any case, the conditions involved are all equivalent to $y = A^tx$ within this Jordan block.
So, as mentioned above, the subprocedure just returns these conditions.

This concludes the specification of the per-block subprocedure,
and of the algorithm as a whole.
It's correctness and efficiency follow from the preceding discussion.

Subtleties with using JCF in second reduction:
As mentioned in the second reduction, there are some subtleties that arise from
working with the JCF.
There are a few observations for mitigating these problems:

Extensions of finite fields are normal.
This means that if $P$ is a an irreducible polynomial over $\mathbb{F}_q$,
then any extension of $\mathbb{F}_q$ containing a root of $P$
contains all the roots of $P$.
In other words, the splitting field of an irreducible polynomial $P$
of degree $d$ has degree only $d$ over $\mathbb{F}_q$.
There is a generalization of the Jordan canonical form,
called the primary rational canonical form (PRCF),
which does not require field extensions to be written down.
In particular, if $A$ is a matrix with entries in $\mathbb{F}_q$,
then we can write $A = P^{-1}QP$ for some matrices $P,Q$ with entries in $\mathbb{F}_q$,
where moreover $Q$ is in PRCF.
Additionally, if we pretend that the entries $A$ live in a field $\mathbb{F}'$
extending $\mathbb{F}_q$ which contains all the eigenvalues of $A$,
then $Q$ will in fact be in JCF.
Thus we can view computing the JCF of $A$ as a special case of computing the PRCF.
Using the form of the PRCF,
we can factor computing the JCF of $A$ as

computing the PRCF of $A$ over $\mathbb{F}_q$
computing the PRCF of each block $C$ (borrowing the notation from the Wikipedia article) in the PRCF of $A$,
over an extension field $\mathbb{F}'$,
where $\mathbb{F}'$ is chosen to contain all the eigenvalues of $C$

The key advantage with this factorization is that the characteristic
polynomials of the blocks $C$ will all be irreducible,
and hence, by our first observation,
we can choose $\mathbb{F}'$ to have degree the size of $C$ (which is at most $n$) over $\mathbb{F}_q$.
The downside is that now we have to use different extension fields to
represent each block of the JCF, so the representation is atypical and complicated.

Thus, given the ability to compute the PRCF efficiently,
we can compute a suitable encoding of the JCF efficiently,
and this encoding is so that working with any particular block of the JCF can be done within
an extension field of degree at most $n$ over $\mathbb{F}_n$.

As for computing the PRCF efficiently,
the paper
"A Rational Canonical Form Algorithm" (K. R. Matthews, Math. Bohemica 117 (1992) 315-324)
gives an efficient algorithm to compute the PRCF when the factorization of the characteristic
polynomial of $A$ is known.
For fixed characteristic (such as we have),
factoring univariate polynomials over finite fields can be done in deterministic polynomial time
(see eg "On a New Factorization Algorithm for Polynomials over Finite Fields" (H. Niederreitter and R. Gottfert, Math. of Computation 64 (1995) 347-353).),
so the PRCF can be computed efficiently.


So far, the only improvement to Chazelle's juggernaut is the 2001 randomized linear-time algorithm by Amato, Goodrich, and Ramos.  Chazelle's algorithm is still the only deterministic O(n)-time triangulation algorithm known.


Knapsack problem with dependent weight and profits among the items

Hi that sounds quite a lot like the multiobjective Knapsack Problem to me. It has undergone some research for example by the bio-inspired computation community, see for example here:
https://etheses.bham.ac.uk/id/eprint/7532/2/Joshi17PhD.pdf


Measurability of an $\omega$-regular language

An $\omega$-regular language is actually quite low in the Borel hierarchy (inside $\Delta_3$), a result due to

R. McNaughton, Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521-530.

For a proof and more details, you can look at Chapter 3 of the following book

D. Perrin et J.-É. Pin, Infinite words, Pure and Applied Mathematics Vol 141, Elsevier, 2004, ISBN 0-12-532111-2.


Embedding a graph as a collection of interior-disjoint tetrahedra

In Hardness of embedding simplicial complexes in $\mathbb{R}^d$ it is stated that $\mbox{EMBED}_{3\rightarrow3}$ is at least as hard as recognizing a 3-sphere, which is known to be in NP, but not known to be in P. They continue to say that for all we know, the problem may be undecidable.

EDIT: Update. Actually, my answer applies to PL embeddings. For linear embeddings the problem is known to be in PSPACE. I don't know if anything else is known.


Applications of Game theory in computer science?

One of the most famous examples of game theory in computer science is Yao's minimax principle.  Let $X$ be a set of inputs for some problem, and let $A$ be a set of (deterministic) algorithms for that problem.  Yao's principle states that
$$
\max_{x\in X} \operatorname{E}\limits_{a\in A} \left[T(a,x)\right]
\ge
\min_{a\in A} \operatorname{E}\limits_{x\in X} \left[T(a,x)\right] ,
$$
where the expectations on the left and right are taken with respect to any desired probability distribution over algorithms and inputs, respectively.

For example: Any deterministic comparison-based sorting algorithm requires $\Omega(n\log n)$ time on average to sort an array permuted uniformly at random.  (Proof: In any binary tree with $N$ leaves, at least half the leaves have depth at least $(\lg N)/2$. $\square$)  So Yao's principle implies that the worst-case expected running time of any randomized comparison-based sorting algorithm is also $\Omega(n\log n)$.

Yao's minmax principle follow easily from von Neumann's minimax theorem for two-player zero-sum games, where one player provides the input and the other provides the algorithm.


Is there a continuous version of parallel repetition theorem

Does exponential decrease also happen in continuous case?

No.  Feige and Verbitsky [FV02] showed that for every n, there is a game G (with finite sets of questions and answers) such that v(G)≤3/4 and v(Gn)≥1/8.  Because your formulation generalizes games with finite sets of questions and answers of any size, parallel repetition (of any finitely many times) cannot decrease the value of a game from 3/4 to 1/8.

[FV02] Uriel Feige and Oleg Verbitsky.  Error reduction by parallel repetition—A negative result.  Combinatorica, 22(4):461–478, Oct. 2002.  doi:10.1007/s00493-002-0001-0.


What is the complexity of vertex cover on k-partite graphs?

For bipartite graphs, vertex cover is polynomially solvable by routine techniques from matching theory.

For $k$-partite graphs with $k\ge3$, we observe the following:

Vertex cover is NP-complete on cubic graphs
By Brooks' theorem, every cubic graph (except $K_4$) is 3-colorable and hence 3-partite.


Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$?

Yes. This is Theorem 4 in the following paper.

Philip M. Lewis II, Richard Edwin Stearns, Juris Hartmanis:
Memory bounds for recognition of context-free and context-sensitive languages. SWCT (FOCS) 1965: 191-202.

Edit: I am sorry. My answer is not helpful. I missed the "small o". Stupid...
I am not sure what to do. Delete the answer?


FSM transducer sequential composition decidability

The problem seems undecidable: consider a transducer $F$ that parses and "executes" a single step of a Turing machine $M$ with the head $H$ on symbol $a$, in state $S$ and with tape content $x[a]by$ where $a,b \in \Sigma; x,y \in \Sigma^*$:

$$\# x \, a \, H\, S \, b \, y \, \# \, w $$

where $w \in \{0,1\}^+$ and it outputs

$$\# x \, H \, S' \, a'\, b \, y \, \# \, w' $$

if the head moves left, i.e. $\sigma(a,S)\to (a',S',L)$ or it outputs

$$\# x \, a' \, b \, H \, S' \, y \, \# \, w' $$

if the head moves right, i.e. $\sigma(a,S)\to (a',S',R)$.

$w'$ is simply $w +1$ (binary addition with the LSB on the left) and its "role" is to make $x_{i+1} \neq x_j \forall j \leq i$ as required.

If $M$ halts (when $S'$ is a final state), then $F$ adds an extra $\#$ at the end (i.e. it makes the output ascending) and rejects to stop the sequence; otherwise it accepts and the length is unaltered.

If there is not enough space for a right move of the head then $F$ rejects to stop the sequence.

If there is not enough space for writing $w+1$ (carry overflow on the right), it simply replaces the last digit with $\#$ (to make $x_{i+1} \neq x_i$) and rejects to stop the sequence.

Note that:

$F$ needs only a limited look-ahead buffer (4 symbols) to make the rewrite and also to perform the $w+1$ operation;
the internal states of $F$ embeds the internal states of $M$ so it can simulate the transition function $\sigma$;

Now, consider $M$ on an empty tape; we can use an (infinite) regular language:

$L = \{ \# \, H \, S_0\, \, 0^+ \# \, 0^+ \}$

$M$ halts if and only if $F^n(x)$ is not descending for all $n$, for all $x \in L$

Indeed the only length increase occurs when $F$ runs on $\# \, H \, S_0\, 0^s \, \# \, 0^t$ and $s,t$ are such that $M$ halts in less than  $2^t$ steps using at most $s$ space.


Which complexity class does this number theory problem belong to?

Added later: As noted in the comments, the NP upper bound is trivial if a, b, and c are positive, as was asked.

Theorem 1.2 in this paper shows that deciding if a given diophantine equation in two variables has a solution is in NP.


I also have the impression that Descriptive Complexity is a less active area of research nowadays. Nevertheless, there are some topics in which people are still active:

Rank logics:

Rank Logic is Dead, Long Live Rank Logic! by Grädel and Pakusa
Symmetric Circuits for Rank Logic by Dawar and Wilsenach
Separating Rank Logic from Polynomial Time
by Lichter

Choiceless Polynomial Time:

Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time by Lichter and Schweitzer
Choiceless Logarithmic Space by Grädel and Schalthöfer

Dynamic Complexity:

Dynamic Complexity of Parity Exists Queries by Vortmeier and Zeume
Reachability Is in DynFO by Datta, Kulkarni, Mukherjee, Schwentick and Zeume
PHD thesis of Thomas Zeume

Other interesting things:

Descriptive Complexity for Counting Complexity Classes by Arenas Muñoz and Riveros
Descriptive complexity of real computation and probabilistic independence logic by Hannula, Kontinen, Van den Bussche and Virtema
Descriptive Complexity of Deterministic Polylogarithmic Time by Ferrarotti et al
On the Power of Symmetric Linear Programs by Atserias, Dawar and Ochremiak
Traversal-invariant characterizations of logarithmic space by Bhaskar, Lindell and Weinstein

The list is not supposed to be complete. Just giving you a glimpse on what kind of problems are people looking at.


When is hypertree width more useful than generalized hypertree width?

Every XP/FPT algorithm parametrized by htw also gives an XP/FPT algorithm parametrized by ghtw (provided that the decomposition is given in the input)  since there is a linear relation between ghw and hw [1]: $\mathsf{hw} \leq 3\mathsf{ghw}+1$. So basically, you can see hw as a easier to compute constant approximation of ghw.

I am not aware however of problems that are XP when parametrized by hw but not by fhw.

Side note however: if you are only interested in problems when the input is a CSP (with positive encodings) / Database of bounded (f)hw, then an XP algorithm for htw will often give you an XP algorithm for fhw.

Indeed, if the algorithm is XP for hw, then it is polynomial on $\alpha$-acyclic hypergraphs, that is, hypergraphs of hw $1$. Now, if you perform the join of the guards inside each bag of the (fractional / generalized) hw decomposition then you get a new CSP / Databases that is $\alpha$-acyclic. Moreover, each new relation is of XP size in the original DB/CSP. Now if you can rewrite your problem on this new database, this directly give you an XP algorithm for fhw.

[1] I. Adler, G. Gottlob, and M. Grohe.  Hypertree width and related hy-pergraph invariants.European  Journal  of  Combinatorics, 28(8):2167– 2181, 2007.  24


Set data structure for efficient repeated insertions

I think Raman and Rao's "Succinct Dynamic Dictionaries and Trees"  meets the bounds you specify. From the abstract:

  We first give a representation of a set $S \subseteq U =
\{0, \dots , m − 1\}, |S| = n$ that supports membership queries in $O(1)$ worst
  case time and insertions into/deletions from $S$ in $O(1)$ expected amortised time. The representation uses $B + o(B)$ bits, where $B = \lceil lg \binom{m}{n} \rceil$ is the information-theoretic minimum space to represent $S$.