Job scheduling: minimizing number of reads

After a failed polynomial-time quick attempt, here it is an idea to prove that it is NP-complete using a reduction from 3SAT.

Given a 3SAT formula with $x_1,...,x_n$ variables and $C_1,...,C_m$ clauses, first build a variable assignment gadget like in the figure below (thanks to @Jukka for the clarifications, the graph drawing style, and the hint for the gadget with two configurations and same cost!).

Each blue horizontal line corresponds to a different schedule time ($s=1,2,...$).
On the left of the picture there is a complete assignment gadget for three variable ($x1,x2,x3$).
The red nodes correspond to a $true$ assignment ($+x_i$), the blue nodes to a $false$ assignment ($-x_i$). A green node correspond to a variable $x_i$ and can be placed
on the same schedule time of the red or the blue node, without afftecting the total cost of the gadget. The three possible combinations for $x_1$ are showed on the right. The number in the nodes represents the cost (the number of distinct parents). Both $x_1 = true, x_1 = false$ have a cost of 7 ($c=7$). Note that the last combination has a greater cost so it cannot be used.

Now we extend the assignment gadget to "simulate" the clauses of the formula.

First we add a top node, and a mirror chain of $3n+2$ nodes (the chain of nodes on the left of the picture). By construction some of the nodes of the mirror chain must be on the same schedule time of the $true/false$ assignments; we call them $+x'_1, -x'_1, +x'_2, -x'_2,...$ (yellow nodes of the mirror chain in the figure).
Now we add a clause node $C_j$ for each clause and we force it to be at schedule time $s=1$ by adding two directed edges from the bottom of the mirror chain and assignment gadget.

We link the clause node to the three variables it contains (green edges in the figure), and to the corresponding positive/negative literal in the mirror chain (red edges in the figure). Finally we link the clause node to the top node using a chain of 6 clause pegs $P_{j_1},...,P_{j_6}$ (purple nodes in the figure).

How it works

The clause pegs of $C_j$ are linked together so they must be placed at different schedule times. So the cost of $C_j$ is greater than or equal to $6$. We can keep the cost of $C_j$ equal to 6 if and only if the assignment corresponding to the position of the green variables nodes contained in $C_j$ satisfies $C_j$.

First of all note that the bottom peg $P_{j,1}$ must be put at schedule time $s=2$ because $C_j$ is linked to the bottom of the assignment gadget and mirror chain. So only 5 of the pegs are "free" to be assigned to greater schedule times (otherwise the cost of $C_j$ is \geq 7$).

Now, suppose for example that $C_1$ is $(x_1 \lor \bar{x}_2 \lor x_3)$ (like in the figure). We have the green edges: $x_1 \to C_1, x_2 \to C_1, x_3 \to C_1$ and the red edges $+x'_1 \to C_1, -x'_2 \to C_1, +x'_3 \to C_1$.

Suppose that we set $x_1 = true, x_2 = true, x_3=false$ then the green variable $x_1$ will be on the same schedule time of $+x'_1$. But $x_2, -x'_2$ and $x_3, +x'_3$ will be on different schedule times. We can put a peg on the same schedule time of $x_1=true$, and the remaining 4 can be placed on the same schedule times of $x_2=true, -x'_2, +x'_3, x_3=false$ ("mask" them). The total cost of $C_1$ is still 6.

But what happens if we cannot find an assignment that satisfy all clauses? Then, in at least one clause (suppose $C_1$), the green variable nodes $x_1=false,x_2=true,x_3=false$ are all on a different schedule time of the corresponding $+x'_1, -x'_2, +x'_3$. So the 5 free pegs are not enough to "mask" them and the number of distinct parents of $C_1$ increases to $7$, like in the figure below.

Note that without the pegs, the (minimum) total cost $c_t$ of the schedule is fixed, so we can conclude that after adding the pegs, the original formula is satisfiable if and only if the total cost of the graph is less than $c_t + 6*m$.


NP-hardness of minimizing sum of weighted product

The problem is indeed NP-complete - reduce from the 3-partition problem where you are given $3n$ positive integers and asked to group them into $n$ groups such that for all the groups the sum of the elements is the same.

Note (1) that partition is strongly NP-complete - i.e remains NP-complete when the input numbers are polynomial in $n$. Note (2) that if the sum of all the groups is the same then this sum must be equal to $X$, where $X$ is the sum of all the numbers in input, divided by $n$. (3) The problem remains NP-complete even when all numbers are strictly between $X/4$ and $X/2$. In this case, each group forced to be a triple.

For each integer $a$ in the input to $3$-partition, replace it by $n^{10a}$ in the input to your problem. Use $n$ bins. Ask whether you can obtain a value of the objective function at most $3n^{10X+2}$.

For the forward direction, if there is a $3$-partition then putting each group into a bin gives value at most $n \cdot 3n \cdot n^{10X}$ for your objective function.

For the reverse direction, suppose that there is a distribution into bins such that the objective function value is at most $n \cdot 3n \cdot n^{10X}$. Make bins into groups. Note that no group adds to more than $X$, since otherwise the product in that bin would be at least $n^{10X+10}$ which is already more than objective function value. Since the input numbers all have value $X/4 < a < X/2$ it follows that all groups have size exactly $3$.

Note that this proves NP-completeness of your problem, but not strong NP-completeness. I suspect that this problem is also strongly NP-complete.


Upper bounds on the length of longest simple path in non-Hamiltonian graph?

There exist cubic bipartite planar graphs in which the longest path has length only $O(\log^2 n)$:


There's a parallel algorithm for shortest paths from Carla Savage's 1977 Ph.D. thesis that consists of forming a square matrix with 0 on the diagonal entries, the length of the edges on the off-diagonal entries corresponding to edges, and a suitably large number for the remaining off-diagonal entries, and then repeatedly squaring this matrix in the (min,+) algebra.

After $\lceil\log_2 n\rceil$ squaring steps, the numbers in the resulting matrix are the distances between each pair of vertices. Each squaring step is easy to parallelize with logarithmic time and cubic work. So overall this algorithm takes $O(\log^2 n)$ time and $O(n^3\log n)$ work. With a little care (using a slightly more complicated algebra) this can be modified so that it also provides the first step of each shortest path in the same time and work bounds.

However, if you only want single source shortest paths rather than all pairs shortest paths, I don't know of anything that comes close to the total work of the sequential Dijkstra algorithm and that provides much in the way of a parallel speedup.


In terms of complexity reasons (rather than complete problems): The Hartmanis-Immerman-Sewelson Theorem should also work in this context, namely: $\mathsf{EXP} \neq \oplus \mathsf{EXP}$ iff there is a polynomially sparse set in $\oplus \mathsf{P} \backslash \mathsf{P}$. Given how far apart we think $\mathsf{P}$ and $\oplus \mathsf{P}$ are - e.g. Toda showed that $\mathsf{PH} \subseteq \mathsf{BPP}^{\oplus \mathsf{P}}$ - it would be quite surprising if there were no sparse sets in their difference.

More directly, if there were no sparse sets in their difference, it would say that for every $\mathsf{NP}$ verifier, if the number of strings of length $n$ with an odd number of witnesses is bounded by $n^{O(1)}$, then the problem [of telling whether there is an odd number of witnesses] must be in $\mathsf{P}$. This seems like quite a striking and unlikely fact.


Actually for applications to approximation algorithms, hereditary discrepancy is often the right quantity. The central result here is due to Lovasz, Spencer and Vesztergombi:

  LSV Thm. For any $m\times n$ matrix $A$ and any vector $x \in [0,1]^n$, there exists a vector $y \in \{0,1\}^n$ such that $\|Ax - Ay\|_\infty \leq \mathrm{herdisc}(A)$.

(If you don't have access to the paper, you can check Lemma 1.14 in Chazelle's book for a proof.)
This theorem can then be used to round a solution to a linear programming relaxation of a combinatorial problem. A very nice example is the recent work on the bin packing problem: for the basic idea check the paper by Eisenbrand, Palvoelgyi, and Rothvoss, and for the best result to date, check this recent arxiv paper by Hoberg and Rothvoss.

The exact guarantee you mention -- efficiently finding a coloring with discrepancy bounded by the hereditary discrepancy -- fits very nicely into this, because it's exactly the guarantee to make the LSV theorem constructive. I.e. if you have an algorithm that for any matrix $A$ finds in polynomial time a coloring $x \in \{-1, 1\}^n$ such that $\|Ax\|_\infty \leq \alpha \cdot \mathrm{herdisc}(A)$, then we have an efficient LSV theorem in which for any $A$ and $x$ there exists a polynomial time computable $y$ such that $\|Ax - Ay\|_\infty \leq \alpha \cdot \mathrm{herdisc}(A)$.

By the way, hereditary discrepancy turns out to be the right quantity in other applications too: constructing $\epsilon$-samples and differential privacy, for example. Also it can be efficiently approximated up to a factor of $\log^{3/2}m$. The largest hardness of approximation known for hereditary discrepancy is factor 2, so hereditary discrepancy may even be approximable within a fixed constant (although I'd be surprised).

EDIT: Let me say a few more words about the approximation, since you say you want to find upper bounds on $\mathrm{herdisc}$. Although my paper with Kunal is not written this way, what we show in fact is that
$$
\gamma_2(A)/O(\log \min(m,n)) \leq \mathrm{herdisc}(A) \leq O(\sqrt{\log m})\gamma_2(A),
$$
where $\gamma_2(A)$ is a classical factorization norm, equal to the smallest number $t$ such that there exist vectors $u_1, \ldots, u_m$, $v_1, \ldots, v_n$ satisfying

for all $i,j$, $\|u_i\|^2 \leq t$ and $\|v_j\|^2 \leq t$;
for all $i, j$, $a_{i,j} = u_i^T v_j$.

It's not hard to turn this definition into a semidefinite program that computes $\gamma_2(A)$. Besides the approximation, this is very useful because $\gamma_2$ has many nice properties which make it easy to give upper and lower bounds which then translate into upper and lower bounds for hereditary discrepancy. My paper with Matousek has some applications.


The directed versions are much harder. A survey by Nutov available on his web page is
a good starting point.
http://www.openu.ac.il/home/nutov/Survivable-Network.pdf


What is the best approximation for majority vote?

If $p_v > p_i$ for all $i \ne v$, then

$$
\mathrm{Pr}[\mbox{outcome is different from $v$}] \leq \min_T \left(Pr[B(N, p_v) \leq T] + Pr[\forall i \ne v \quad B(N, p_i) \geq T]\right),
$$

where $B(n, p)$ is binomial distribution, and $T$ is an arbitrary threshold. Plugging $T = N (p_v + \max_{i \ne v} p_v) / 2$ and using Chernoff bounds, one can upper-bound this probability as $e^{-\Omega(N)}$.

Of course, if $p_v$ is not maximum, then you get the opposite picture. With overwhelming probability $v$ is not outcome.


Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem

Solving any old $\# P$-complete problem in $2^{O(n/\log n)}$ time would not necessarily have interesting consequences. In fact there are some $\# P$-complete problems, like counting the number of minimum vertex covers in a planar graph, which can already be done in $2^{O(n^{1/2})}$ time where $n$ is the number of vertices. (Recall that for planar graphs, the number of edges is linear in the number of vertices, so this is truly a subexponential algorithm.)

Added after Walter's recent comment: I should say that there are several $\# P$ problems which are believed to require $2^{\Omega(n)}$ time (such as counting the number of satisfying assignments to a 3-CNF formula), and the time complexities of these problems are closely related: a $2^{o(n)}$-time algorithm for one of them would imply $2^{o(n)}$-time algorithms for all of them. Some recent work in this direction can be found here. I am not 100% certain, but an $2^{O(n/\log n)}$-time algorithm for counting vertex covers in 3-regular graphs may have interesting consequences along these lines.


Does distance-2 coloring fit in Telle and Proskurowski 's algorithm for partial-k trees?

distance-2 coloring is coloring in the square (d(x,y) <= 2 implies xy an edge in the square). If a graph has tw k, its square has bounded clique-width (see Gurski-Wanke and Suchan-Todinca). See Oum et al. for algorithms as in Proskurowski-Telle for graphs of bounded clique-width.


Applications and benchmarks for binary quadratic program algorithms

The Biq Mac library provides a collection of instances four your problem.


Can I get all min-cuts after executing Push-Relabel?

I assume that your question is "Do I find all min s-t-cuts this way?"

I believe the answer is no. Note that there may be an exponential number of minimum s-t-cuts (connect vertex s to vertices {1,2,3, ...,n} and then each of these are
connected to vertex t -- then there are 2^n min-s-t-cuts).

The way that I know for sure to enumerate all min-s-t-cuts is to recursively enumerate all directed cuts in the residual graph after the contraction of all
strongly connected components. This algorithm can produce
each cut in linear time per cut. If you need a detailed description of the
enumeration algorithm I can provide to you the pseudocode.


Finding maximum number of disjoint set covers

Yes, this is closely related to the Domatic Partition problem. See the paper below.
http://epubs.siam.org/doi/abs/10.1137/S0097539700380754

One can get the following results. Given a set cover instance let $k$ be the minimum over all elements in $U$, the number of sets that contain that element. Then it is clear that we can have at most $k$ disjoint set covers. The paper above shows that there always exist $\max\{1, k/(c \log n)\}$ disjoint set covers where $c$ is a sufficiently large constant. This immediately gives an $O(\log n)$-approximation. Moreover, it is hard to approximate to within this factor (modulo constants). And there are examples where the number of disjoint set covers is $O(k/\log n)$.


It seems that there is a confusion in the question between oracles resulting in equality vs. oracles resulting in separation. It is easy to find natural oracles resulting in equality. Oracles for separation is a different matter and your question does not contain an example for them.

We don't have that many techniques for separating complexity classes and relativized separations are no different. The examples you get are expected to result from those techniques so it is unlikely that such oracles are known.

As far as I know, diagonalization is the only method we know of that can separate non-small complexity classes, so no surprise the oracles separating $\mathsf{NP}$ from $\mathsf{P}$ are such sets.


Bipartite graph projections, with threshold

My two cents:

The worst case of building $G_\top$ is in $\Omega(n^2)$ time and space: assume $\bot$ contains a single node linked to all nodes in $\top$.
Maybe you are not looking for a worst case complexity? Then, $O(\sum_{u\in\bot}(d_u)^2)$ time to build $G_\top$ by listing all edges $u,v$ such that $u$ and $v$ are neighbors of the same node in $\bot$.
You can use some pruning in the case $k$ is large with the following algorithm. For each node $u\in \top$ such that its degree is $k$ or more: For each neighbor $v$ of $u$: For each neighbor $w$ of $v$ such that $w>u$: List the edge $u,w$. Then postprocess the listed edges to find the ones that appear $k$ times or more. Here is a code that does something like that efficiently.
Some related code here for simple graphs (not bipartite, but can be adapted) where we look for pairs of nodes with Jaccard similarity higher than a threshold. It seems that Jaccard allows to leverage a more aggressive pruning: only a pair of nodes $u,v$ such that $\frac{\min(d_u,d_v)}{\max(d_u,d_v)}>\alpha$ can have a Jaccard similarity higher than $\alpha$.


compleixty of rational checking of eigenvalues

The problem is in P for the following reason.

Eigenvalues are the solutions of a univariate polynomial. Finding a solution of a univariate polynomial over $\mathbb{Q}$  can be done in polynomial time by:

Lenstra, A.K.; Lenstra, H.W.jun.; Lovász, László: Factoring polynomials with rational coefficients. (English) Math. Ann. 261, 515-534 (1982).

The polynomial has only rational roots iff all factors have degree 1.


What is known about learning a maximal independent set in a (very) sparse graph?

Roughly $O(k \log(n/k))$ queries suffice, in the regime you are talking about.

We can equivalently think of this as finding a minimal vertex cover for $G$, given ability to query whether a particular set is a vertex cover or not.  The  algorithm is as follows:

Let $S := V$ (the set of all vertices).
While $S$ is not a minimal vertex cover:

Pick a random subset $T \subseteq S$ of size $|T| = \lceil |S|/k \rceil$.
If $S \setminus T$ is a vertex cover, let $S := S \setminus T$.

Note that the final vertex cover will have size $\le k$.

How many iterations does this take to converge?  Well, for $S \setminus T$ to be a vertex cover, $T$ must avoid all of the vertices in the final minimal vertex cover, so the probability that a $S \setminus T$ is a vertex cover is at least

$$\left(1 - {k \over |S|}\right)^{|T|} \approx \left(1 - {k \over |S|}\right)^{|S|/k} \approx 1/e.$$

In other words, there is a constant probability in each iteration that $S \setminus T$ is a vertex cover.  Thus, the total number of iterations is proportional to the number of times that we succeed in reducing the size of $S$.

Each time that we successfully reduce the size of $S$, we multiply its size by a factor of $1 - 1/k$.  We start with $n$ vertices, and end with about $k$ vertices, so the number of reductions $r$ satisfies

$$n \times \left(1 - {1 \over k}\right)^r = k,$$

or in other words,

$$r = {\log(k/n) \over \log(1 - 1/k)} \approx k \log(k/n).$$

Thus, we do a total of $O(k \log(k/n))$ iterations, i.e., a total of $O(k \log(k/n))$ queries.  When the algorithm terminates, we have found a minimal vertex cover.

What is the cost of testing the termination condition?  The algorithm terminates when we have already tried all possible subsets $T$ of $S$ and none of them can be removed from $S$ ($S \setminus T$ was not a vertex cover for any subset $T$ of size $\lceil |S|/k \rceil$).  Note that we'll end with a vertex cover of size $\le k$, so in the last iterations, $|T|=1$, so it'll only take $O(k \log k)$ iterations before we've tried all possibilities for $T$.  At that point the procedure terminates.  So, this doesn't increase the total asymptotic running time.

You can think of this algorithm as a simple variant of delta debugging.


Some good Theoretical Computer Science Journals

Apart from top conferences mentioned by @usul, I think Journal of the ACM (JACM) is a top journal in computer science, which also includes many excellent theoretical computer science papers. In addition, I read some papers published in Algorithmica. Also, just giving a reference, I find a link to some journals related to Discrete Mathematics (particularly refer to Theoretical Computer Science and Algorithms part), see http://www.math.iit.edu/~kaul/Journals.html.


Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?

Let me clarify the question a bit first:
Agnostic learning conjunctions is known to be NP-hard only if the learner needs to be proper (output a conjunctions as a hypothesis) and work for any input distribution. The reductions in FGKP06 are for the uniform distribution and to the best of my knowledge there is no similar result for general distributions.
But in either case the answer to your question is "no" (in the sense that such a reduction is not known and unlikely to exist).
Learning conjunctions with random (classification) noise is an easy problem that was solved in a paper of Anguin and Laird "Learning From Noisy Examples" from 1988 that introduced the model of random noise (see also Kearns 1993 paper on Statistical Queries)
Learning conjunctions with malicious noise is at least as hard as agnostic learning of conjunctions which is believed to be a hard problem (even over the uniform distribution it is at least as hard as learning log-n sparse parities with noise)


Average-case randomized communication complexity in the small-advantage regime

It is big open problem to prove lower bounds. This would imply lower bounds for BP.PP communication protocols (e.g., Tarui's Theorem in communication complexity), which would then imply lower bounds on matrix rigidity (over the real numbers).
For inner product, there is $O(1)$-bit public coin protocol for $\epsilon=1/n^{O(1)}$. Let me simplify by assuming that all $x_i$ and $y_i$ are IID and get value $1$ with probability $1/\sqrt{2}$ so that $x_i=y_i=1$ with probability $1/2$. This simplifies the calculations (the uniform distribution is similar). Observe that $\langle x,y \rangle \in [0,n]$ is binomially distributed with mean $n/2$. Note that for $c\ll\sqrt{n}$ we have $\langle x,y\rangle \in n/2\pm c$ with probability $\Theta(c/\sqrt{n})$.
For warm up, consider the following protocol: Sample random $i\in[n]$ and accept if $x_i=y_i=1$. Assuming $n$ is odd, $\lfloor n/2\rfloor$ is even and $\lceil n/2\rceil$ is odd, this protocol guesses $IP(x,y)$ right (with advantage $\approx 1/n$) whenever $\langle x,y\rangle \in \{\lfloor n/2\rfloor,\lceil n/2\rceil\}$, which occurs with probability $\Theta(1/\sqrt{n})$ over $(x,y)$.
More generally, using the connection between small-advantage computations (class PP) and low-degree polynomials approximating Xor for inputs of Hamming weight $n/2\pm c$ (e.g, The expressive power of voting polynomials) there are $O(c)$-bit protocols that guess $IP(x,y)$ right (with advantage $1/n^{O(c)}$) when $\langle x,y\rangle \in n/2 \pm c$.
When $\langle x,y\rangle$ is outside middle interval, $\langle x,y\rangle \notin n/2 \pm c$, we expect the protocol to err on roughly half the inputs $(x,y)$. Choosing a large enough constant $c$, the correctness in the middle interval starts dominating: protocol guesses right with probability $1/2+\Theta(c/\sqrt{n})$ over $(x,y)$.


Neural Networks to classify accelerometer double taps

Based on your post I'm assuming you haven't had much experience with this type of work. Here are several things that immediately jump out as being potential problems:

You should probably perform some type of preprocessing so your inputs are in a more acceptable range such as (-1, 1), or (0, 1). When the magnitude of the input values are large, the the hidden units are likely to saturate (i.e. be very close to $\pm$ 1 assuming you're using tanh hidden units). This causes the gradients to be nearly zero which can result in backpropagation performing poorly.
In my experience, you will not get good results when you have very unbalanced classes (50 tap, 3000 no tap) if you just naively apply some machine learning algorithm. For example, a classifier which always outputs -1 will achieve approximately 98% accuracy on your dataset, while being completely useless for your task.
Since you have not mentioned a training/test split of your dataset or cross validation, I'm assuming you're not doing these things. You should be. Neural networks are notorious for overfitting and if you use the same data to train and assess accuracy, you almost surely will.

That being said, I'm surprised this question hasn't been closed or migrated. It is almost certainly a better match for the CS stack exchange or Metaoptimize.


Partitioning a matrix into equal-sized regions: finding the maximum

In the proof of theorem 2 in Improved Approximation Algorithms for Rectangle Tiling and Packing by Berman et al, they proved an upper bound of $\frac{11}{5} \max\{W/p,y\}$, where $W$ is the sum of the weight of all elements, $p$ is the number of rectangles and $y$ is the weight of the largest element.

This implies a upper bound of $\frac{11}{5j}$ for your problem.


Here, "straight-line" is contrasted with "rewinding". A simulator is "straight-line" if it does not "rewind" the party it is doing the simulation for.

For instance, in a zero-knowledge protocol, the simulator usually rewinds the "verifier". In the "straight-line" sense, this rewinding does not happen.

I first saw the term "straight-line simulator" in Rafael Pass's paper (On Deniabililty in the Common Reference String and Random Oracle Models. (CRYPTO'03)) and M.Sc. thesis (Alternative Variants of Zero-Knowledge Proofs).

Edit: I found an earlier paper: Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints by Cynthia Dwork and Amit Sahai, which dates back to 1998. For more pointers, see Alon Rosen's comment below.


A good start would be Katz and Lindell's Introduction to Modern Cryptography.

Alternatively, you might want to take one of the crypto courses on Coursera: I recommend the ones taught by Jonathan Katz and by Dan Boneh (search for "cryptography" on Coursera). They are both free.


You will find lots of links in Steve Wright's plenary talk at the SIAM Optimization 2011 conference: http://pages.cs.wisc.edu/~swright/talks/sjw-siopt11.pdf

At the same conference, Michael Friedlander gave a tutorial with many references and pointers to applications and software: http://www.cs.ubc.ca/~mpf/papers/mpf-tutorial-siopt11.pdf

The video lectures on compressive sensing given by Emmanuel Candes at Cambridge are also a great way to get into the subject: http://www.sms.cam.ac.uk/collection/1117766


Complexity of counting when there is no parsimonious reduction

I don't think that having a non-parsimonious reduction helps in proving that a counting problem is in FP. Eg. if either 1 or 2 instances are mapped to 1, and which of these depends on something NP-hard, then you do not know anything about the complexity of your problem. Of course, you might have a special reduction from which you get some extra information.


Does having unique normal forms imply weak normalization and confluence?

It is a little bit sketchy, but here is my argument: Suppose that there are three terms t, u, v such that t reduces to u, t reduces to v and suppose that each term has a unique normal form. Since you are weakly normalizing as you said, there exists a normal form for v and u. But since the normal form is unique, then v and u are joinable. Hence, the system is confluent.


How to iterate over vectors in order of probability in small space

The following gives an algorithm that uses approximately $2^n$ time and $2^{n/2}$ space.

First, let's look at the problem of sorting the sums of all subsets of $n$ items.

Consider this subproblem: you have two sorted lists of length $m$, and you would like to create a sorted list of the pairwise sums of the numbers in the lists. You would like to do this in roughly $O(m^2)$ time (the output size), but sublinear space. We can achieve $O(m)$ space. We keep a priority queue, and pull the sums out of the priority queue in increasing order.

Let the lists be $a_1 \ldots a_m$ and $b_1 \ldots b_m$, sorted in increasing order. We take the $m$ sums $a_i + b_1$, $i = 1 \ldots m$, and put them in a priority queue.

Now, when we pull the smallest remaining sum $a_i + b_j$ out of the priority queue, if $j < m$ we then put the sum $a_i + b_{j+1}$ into the priority queue. The space is dominated by the priority queue, which always contains at most $m$ sums. And the time is $O(m^2 \log m)$, since we use $O(\log m)$ for each priority queue operation. This shows we can do the subproblem in $O(m^2 \log m)$ time and $O(m)$ space.

Now, to sort the sums of all subsets of $n$ numbers, we just use this subroutine where the list $a_i$ is the set of sums of subsets of the first half of the items, and the list $b_i$ is the set of sums of subsets of the second half of the items. We can find these lists recursively with the same algorithm.

We will now consider the original problem.  Let $S_0$ be the set of coordinates which are $0$, and $S_1$ be the set of coordinates which are $1$. Then
\begin{eqnarray*}\prod_{i \in S_0} p(v_i=0) \prod_{i \in S_1} p(v_i=1) &=& \prod_{1\leq i \leq n} p(v_i=0)   \prod_{i \in S_1} \frac{p(v_i=1)}{p(v_i=0)} \\ &=& \prod_{1\leq i \leq n} p(v_i=0) \exp\,\left(\sum_{i \in S_1} \log \frac{p(v_i=1)}{p(v_i = 0)}\right).\end{eqnarray*}

Sorting these numbers is the same as sorting the numbers $\sum_{i\in S_1}\log p(v_i=1) - \log p(v_i=0)$, so we have reduced the problem to sorting the sums of subsets of $n$ items.


Fast approximation of (vertex) clique cover

You can use a fast (e.g. greedy) max clique algorithm to find cliques one after another. That is, find a maximal clique, remove it from the graph, and repeat until the graph is empty. If fact, I just coded this in C++ for some project that I'm working on now. I can share the code if you'd like it (it accepts DIMACS files).


Can real-time deterministic multicounter automata recognize the marked palindrome language?

I realized that in Fischer, Meyer, and Rosenberg (1968) Theorem 1.3, it is proven that "The language of marked palindrome is not recognizable by any one-way $k-CM$ which operates in time less than $T(n) = 2^{(n/2k)}$."

The same result also appears in Petersen (2009).


A good Library for testing whether a minors exists in a graph?

NAUTY can be used as a library to help you build a hashtable for the entire poset of graph minors for small $n$.  The key would be the cannonial form given by NAUTY and the value would be a concatenation in sorted order of the cannonical forms of it's direct minors.


Sorting points such that the minimal Euclidean distance between consecutive points would be maximized

ETA: Everything below is in the paper "On the maximum scatter TSP", Arkin et al, SODA 1997.

I don't know about exact answers, but here's another approach that's a little different from Suresh's suggestion of Gonzalez clustering:

Assume for simplicity that $n$ is even. For each vertex $p$, find the median of the $n-1$ distances $d(p,q)$. Form an undirected graph in which every vertex $p$ is connected to the other vertices that are at least the median distance away. The minimum degree in this graph is at least $n/2$, so by Dirac's theorem it's possible to find a Hamiltonian cycle in this graph.

On the other hand, there are $n/2 + 1$ vertices in the disk centered at $p$ with radius $d(p,q)$, too many to form an independent set in the cycle, so any Hamiltonian cycle would have to have an edge connecting some two of these vertices, of length at most $2d(p,q)$. Therefore, the Hamiltonian cycle found by this algorithm is at worst a 2-approximation to the bottleneck max cycle.

This will work in any metric space, and gives the optimal approximation ratio among algorithms that work in any metric space. For, if you could approximate better than to within a factor of two then you could solve Hamiltonian cycle problems exactly, by reducing the input graph to the Hamiltonian cycle problem into a metric space with distance 2 for every graph edge and distance 1 for every non-edge.

Probably with some care you can massage this into an approximation algorithm for paths instead of cycles.


How to contribute incrementally to Theoretical CS - similar to github

As mentioned in a comment above, you can contribute to the TCS Wikipedia Project led by Shuchi Chawla:

  Wikipedia is a great resource for people outside of the TCS community to learn about TCS topics, and provides an educational and outreach opportunity for our community. Our community should ensure that important TCS topics get adequate and accurate coverage in Wikipedia through articles written by experts. Unfortunately, writing or editing articles for Wikipedia, and ensuring that the edits are not overwritten, can be a daunting task. It is a task best addressed as a community effort rather than by a few individuals.


Upper and lower bound of binomial summation

Let me denote the sum as $S_{n,p}$. It gives the probability that a random sample from the binomial distribution $B(n,p)$ exceeds its expected value.

For $0<p<1$ constant, the central limit theorem tells you that $B(n,p)$ looks like the normal distribution $N(pn,p(1-p)n)$ for large $n$. Since this is symmetric, $S_{n,p}$ will be approximately $1/2$ as noted in usul’s comment.

This can be quantified using the Berry–Esseen theorem: applying it to $n$ indicator random variables with mean $p$, variance $p(1-p)$, and third moment $(p^2+(1-p)^2)p(1-p)\le p(1-p)$, gives

$$\left|S_{n,p}-\tfrac12\right|\le\frac C{\sqrt{p(1-p)n}}$$

for a certain constant $C<1/2$.


iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation

Yes, it is a lovely observation. At first it might be a little surprising, but it is widely known, in disguise.

If we write the instantaneous description of a Turing machine as $vqw$, where $q$ is the state, $v,w$ are the segments left and right of the head, then the next ID of the TM is obtained by just a local transformation of the string $vqw$ (namely $q$, the letter next to $q$ that the TM is reading, and one or two neighbouring letters). This observation is used when showing that every TM accepted language can be generated by a type-0 grammar. Such a grammar can only transform a local part of the string (and thus this can be simulated by a FST/GSM). Applying consecutive derivation steps then is iterating the transducer.


Complexity class for some group and graph homomorphism problems

(As I mentioned in a comment,) The graph problem is NP-complete, even when H2 is a triangle.

By putting 3 isolated vertices into H1, one gets a modified instance such that if the

original instance had no graph homomorphisms then the modified instance also has no

graph homomorphisms else the modified instance has more than 6 graph homomorphisms.

Taking the group problem literally, it is in DTIME(1), since it's decided by the algorithm ACCEPT.

On the other hand, let ∃NZH be the result of instead interpreting the "0" from the

group problem as "the cardinality of the singleton whose element is the zero morphism".

By Reingold's result, ∃NZH is in  GC$\hspace{-0.02 in}\big(\hspace{-0.04 in}\lceil \hspace{-0.02 in}$log2(|G1|)$\hspace{-0.02 in}\rceil \hspace{-0.06 in}\cdot \hspace{-0.06 in}\lceil \hspace{-0.02 in}$log2(|G2|)$\hspace{-0.02 in}\rceil$,logspace$\hspace{-0.03 in}\big)$ ,  since that class

gives the verifier two-way read access to the alleged proof.  Furthermore (still using Reingold), logspace machines can compute such non-zero homomorphisms given 2-way read access to

such witnesses.  Additionally, by this answer's bound on the number of non-isomorphic groups

(which I don't know how to prove), the negation of ∃NZH is in

GC$\hspace{-0.02 in}\big(\hspace{-0.03 in}\big[\hspace{-0.04 in}\lceil$log2(|G1|)$\hspace{-0.03 in}\rceil^{\hspace{-0.02 in}2}\hspace{-0.05 in}+\hspace{-0.06 in}\lceil$log2(|G2|)$\hspace{-0.03 in}\rceil^{\hspace{-0.02 in}2}$ ordinary bits$\hspace{-0.02 in}\big]\hspace{-0.03 in}$+[1 pointer to the advice string]

,logspace$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}n^{O\left(\hspace{-0.02 in}(\hspace{.02 in}\log(n))^{\hspace{.02 in}2}\hspace{-0.02 in}\right)}$.

(The pointer is to where the advice string gives [an ordered pair of reference groups with no non-zero homomorphisms] such that each input group is isomorphic to the corresponding reference group.)

I'm not aware of any evidence for there being $\big[\hspace{-0.02 in}$a set S of ordered pairs $\langle \hspace{-0.02 in}$m,n$\hspace{-0.02 in}\rangle$

with min(m,n) not bounded above$\hspace{-0.02 in}\big]$ such that the complement of the language

$\: \big\{\hspace{-0.05 in}\langle \hspace{-0.02 in}$m,n,G1,G2$\rangle$  :  $\langle \hspace{-0.02 in}$m,n$\hspace{-0.02 in}\rangle \hspace{-0.03 in}\in$ S  and  and  |G1| < m  and  |G2| < n

     and  G1 and G2 are both 2-groups  and  $\langle \hspace{-0.02 in}$G1,G2$\rangle \hspace{-0.03 in}\in$ ∃NZH $\hspace{-0.08 in}\big\}$

is in  GC$\hspace{-0.03 in}\big(\hspace{-0.03 in}o\hspace{-0.02 in}\big(\hspace{-0.03 in}$(log(m+n))3$\hspace{-0.03 in}\big)\hspace{-0.02 in}$,DTIME$\hspace{-0.03 in}\big(\hspace{-0.03 in}$2o(log(m)$\cdot$log(n))$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}$2^$\big(\hspace{-0.04 in}$(m+n)o(1)$\hspace{-0.02 in}\big)$

or in  NTIME$\hspace{-0.03 in}\big(\hspace{-0.03 in}$2o(log(m)$\cdot$log(n))$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}n^{o\hspace{-0.02 in}\left(\hspace{-0.02 in}(\hspace{.02 in}\log(m+n))^{\hspace{.02 in}2}\hspace{-0.02 in}\right)}$ ,

where all five little-os are as min(m,n) increases without bound.

However, I certainly suspect that the negation of ∃NZH is already in those two classes,

i.e., without needing to bring S into the picture or assume that the groups are 2-groups.


Distributive expansion of CNF and implicants

Theorem 1 is related to Blake canonical form.

The Wikipedia article refers to

Brown, Frank Markham, Boolean Reasoning: The Logic of Boolean Equations,

which in turn references

Canonical expressions in Boolean algebra. Ph.D. dissertation U (1937)).


I think the following paper will help:
Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy

It states that $\mathbf{coNP} \not\subset \mathbf{IP}[\log^{O(1)} n]$ unless the exponential hierarchy collapses. ($\mathbf{IP}[k]$ is the class of languages possessing $k$-move interactive proofs.)

Regarding the natural relation between interactive & probabilistically checkable proofs, I think the above result must help.

I also suggest taking a look at A New Sampling Protocol and Applications to Basing Cryptogaphic Primitives on the Hardness of NP.


Solving multiple instances of 3SUM generated from the same set

It's not linear time, but here at least is an $O(n^{3/2})$ randomized solution to the problem in which you are given a set of $n$ elements together with the sums of $n$ randomly-generated triples of the elements, and you have to find a triple that matches one of the given sums.

Pick randomly two subsets $A$ of $n^{3/4}$ elements and $B$ of $n^{1/2}$ elements. With constant probability at least one of your 3SUMs is in $A+A+B$.
Compute the set $A+A$ and store it in a hash table for fast lookups.
For each pair of a value $x$ in $B$ and a target value $z$ of one of the input 3SUMs, test whether $z-x$ is one of the stored values of $A+A$, and if so whether the resulting triple(s) of numbers $A+A+B$ that sum to $z$ are distinct from each other.

I originally thought this would work equally well for an adversarially-selected set of 3SUMs (instead of the randomly-selected set in your question), but now I'm not sure sure about that part: the expected number of 3SUMs you hit with your choice of $A+A+B$ is always constant, but maybe the adversary could fix things so that you have a high probability of hitting none of them and a small probability of hitting many at once? I'm not sure this is possible but it would take more analysis than I've done so far to be certain.


Degree reduction step in Dinur's proof of the PCP theorem

It is essential to the construction to have an expander between the copies of a vertex (the "cloud" of the vertex).
Otherwise, you won't be able to argue that the adversary assigning values to the vertices is better off assigning those vertices the same value.

In particular, if instead of an expander you have a cycle, the prover can assign one half-cycle one value, and the other half-cycle another value. This way with good probability the verifier won't catch the inconsistency between the vertices, but you can't appeal to the soundness of the original graph to prove soundness for the new graph (it's like allowing the prover in the original graph to use two different assignments for the vertex).


One thing I found useful is to allocate time and designate a space for doing specific research activities.

When I was at Princeton U, I loved sitting at the Engineering library that is well lit, bright and spacious, to read and to think of new ideas. When I verified my 139 pages paper, I used to do it in a room in the biology library at Weizmann that had no computers and no other people, only a desk, chairs and a window to an inner garden. When I go over introductions or notes, I like doing it in coffee shops.

There are several reasons why I found this to be a good practice for me:

(1) Just pondering about a good environment for me for an activity fills me with anticipation for this activity, or at least somewhat prepares me for it.

(2) The fact that I decide to do something specific at this time, and I have the space I need for doing that, induces simplicity, clarity and good order.

(3) Knowing what I like, what I care about, and also what distracts me and what is not good for me, I create environments that make it is easier for me to do what I need to do.


Proof of a unique homomorphism from an initial object

As far as I remember (and my copy of Pierce's Basic Category Theory for Computer Scientists confirms this), the initial object is defined as an object with exactly one arrow to each object in the category.


Semantic distance between excerpts of text.

You are looking for "lexical cohesion". Try searching for this term and you will get tons of literature. After constructing the so-called "lexical chains", well-known graph partitioning and information retrieval algorithms can be used to group them into semantic classes. There is in fact a lot of theory and algorithms behind this "post-processing". Dictionary of synonyms and antonyms is often used to construct these chains. I worked on such extraction algorithms during my undergraduate days, about 10 years back. So this field must be more advanced now.


PCPs are very often used to construct ZKPs, especially for NP-complete languages. The idea is simple: you commit to every bit of PCP separately, and then the prover makes random queries to the PCP. Given the query and committed bit, you prove in ZK that the bits in concrete locations would make the prover to accept. Since the number of queries is small, the proof is relatively efficient.

The main problem tends to be the computational complexity: generating a PCP for an arbitrary NP language is efficient only in theory, and thus people look for more efficient solution.

A recent related paper, that does something in between is by Bitansky and others (TCC 2013) where they study "linear PCPs" and their relation to ZK. Since linear PCPs (see their paper) are less stringent than general PCPs, they can be constructed more efficiently.


Difference between abstract machines and calculi

I essentially agree with Martin's comment, I can elaborate on that to make a tentative answer, knowing that there is no general formal definition of calculus or abstract machine and that what I am going to describe cannot possibly cover the meaning of all instances of these two words found in the literature.

In brief: a calculus usually gives you the abstract spefication of the meaning of programs, whereas an abstract machine usually implements that specification.  Such an implementation is likely to be still high-level (i.e., many low-level details are not specified), hence the adjective "abstract", but it gets closer to what a phyisical machine would do to execute programs (according to the spefication given by the calculus).

More in detail: a calculus usually comes with an operational semantics, which gives you the meaning of programs in terms of the result they denote (if any). For this, one often uses the notation

$t\Downarrow v$,

which means that "the value (i.e., the final result) of the expression $t$ is $v$". Now, such a "big step" operational semantics (as it is sometimes referred to) is usually given in terms of a derivation system (i.e., a system in which you can prove judgments of the form $t\Downarrow v$), which is useful to reason abstractly about programs but is a bit far from describing how the execution of $t$ would look like on a concrete machine.

One may then move to a "small step" operational semantics, which is a set of rewriting rules on expressions (written $t\rightarrow t'$) describing how one can, step by step, compute the value of an expression (if any):

$t\Downarrow v\quad$ iff $\quad t\rightarrow^\ast v$.

Now, even the small-step semantics may be too coarse: typically, some rewriting rules may duplicate arbitrary big sub-expressions, and a chain of duplications may cause an exponential blow-up of the size of expressions in only a linear number of steps, which means that these steps are not so "small" after all...  In particular, one may want to give a more realistic description of the execution of programs, getting even closer to the machine level. This is where abstract machines come into the picture.

It is impossible to give a general description of an abstract machine, since they may differ greatly. However, these usually include low-level components (e.g. a pointer to a "code memory" where the executed program is stored, a stack, a memory for storing the values of variables, etc.) which make them look much more like physical machines executing the programs of the language underlying the original calculus.

About where to "draw the line" between calculi and machines: this is actually a tricky question. There are calculi whose small-step semantics is more or less the same thing as an abstract machine. Lambda-calculi with explicit substitutions are examples of this: in such calculi, expressions contain constructs (the explicit substitutions) which make it possible for the small-step semantics to operate at a lower level, much closer to that of the machine.

About your reasoning on how the levels of expression of an algorithm are "layered", I am not sure I follow it, so I cannot say much. But I hope that at least I gave you some elements of answer to your last two questions.


Proofs techniques related to Curry–Howard correspondence

What you want exists, and is an enormous area of research: it's the entire theory of programming languages.

Loosely speaking, you can view computation in two ways. You can think of machines, or you can think of languages.

A machine is basically some kind of finite control augmented with some (possibly unbounded) memory. This is why introductory TOC classes go from finite automata to pushdown automata to Turing machines --- each class takes a finite control and adds some more memory to it. (Nowadays, the finite control is often  limited even more, as in circuit models.)  The essential thing is that the finite control is given up front, and all at once.

A language is a way of specifying a whole family of controls, in a compositional way. You have primitive forms for basic controls, and operators for building up larger controls from smaller ones. The primordial language, the lambda-calculus, in fact specifies nothing but control -- the only things you can define are function abstractions, applications, and variable references.

You can go back and forth between these two views: the $snm$-theorem is essentially a proof that Turing machines can implement function abstraction and application, and Church encodings demonstrate that the lambda-calculus can encode data. But there's nontrivial content in both of these theorems, and so you should not make the mistake of thinking that the two ways of understanding computation are the same.

Researchers in complexity and algorithms typically take machines as fundamental, because they are interested in costs and in feasibility results. To exaggerate a bit, the basic research question they have is:

  What is the least powerful machine that can solve a certain kind of problem?

Language researchers take languages as fundamental, because we are interested in expressiveness and impossibility results. With a similar exaggeration, our basic research question is:

  What is the most expressive language that rules out a certain kind of bad behavior?

As an aside, note how the two goods each kind of theoretician values are directly in conflict! Good work in algorithms and complexity lets you solve a harder problem, using less resources. Good work in languages lets programmers do more things, while forbidding more bad behaviors. (This conflict is basically why research is hard.)

Now, you might ask why more Theory A types don't use languages, or why more Theory B researchers don't use machines. The reason arises from the shape of the basic research question.

Note that the stylized basic research question in algorithms/complexity is a lower bound question -- you want to know that you have the best solution, and that there is no possible way to do better, no matter how clever you are. A language definition fixes the means of program composition, and so if you prove that a lower bound with a language model, then you might be left with the question of whether it might not somehow be possible to do better if you extended your language with some new feature. A machine model gives you the whole control in one go, and so you know everything the machine can possibly do right from the outset.

But machine specifications are exactly the wrong thing for saying interesting things about blocking bad behavior. A machine gives you a whole control up-front, but knowing that one particular program is okay or bad doesn't help you when you want to extend it or use it as a subroutine -- as Perlis's epigram states, "Every program is a part of some other program and rarely fits." Since language researchers are interested in saying things about whole classes of programs, languages are much better suited for purpose.


Find the cheapest cycle through two points on a rectangular grid

Ok, here's a reduction from Hamiltonian cycles in grid graphs to your problem. It requires the grid graph to have vertices in the two opposite corners but that shouldn't be an obstacle to getting the details to work.


Show that minimal CFG is undecidable via mapping reduction

Here is a solution based on a reduction from Post Correspondence Problem.  The general idea is similar to the ones used in reductions from PCP to the emptiness of intersection and ambiguity in context-free grammars.  I am afraid I am using a Turing reduction for a preliminary claim---which I would consider fair game considering the number of variants of PCP `out there'.

Preliminaries.
A PCP instance is a finite set of pairs $\Pi=(u_i,v_i)_{i<n}$ of finite words over a finite alphabet $\Sigma$.  A solution is a sequence of indices $j_0,\dots,j_m$ with $u_{j_0}\cdots u_{j_m}=v_{j_0}\cdots v_{j_m}$.  The set of indices $I(\Pi)$ of a PCP instance $\Pi$ is the set of indices $i<n$ that appear in some solution; formally $$I(\Pi)=\{ i < n\mid \exists i_0,\dots,i_m <n\mathbin.u_{j_0}\cdots u_{j_m}=v_{j_0}\cdots v_{j_m}\text{ and }\exists 0\leq k\leq m\mathbin.i=j_k\}\;.$$
Then the PCP instance has a solution iff $I(\Pi)\neq\emptyset$.

Claim.  The following decision problem called full PCP is also undecidable:

instance $\Pi$
question $I(\Pi)=\{0,\dots,n-1\}$?

Proof.  By a Turing reduction from PCP.  Assume full PCP is decidable, and consider a PCP instance $\Pi$.  For a subset $J\subseteq\{0,\dots,n-1\}$, let $\Pi_J=(u_i,v_i)_{i\in J}$.  Then $\Pi$ has a solution iff $I(\Pi)\neq\emptyset$ iff there exists $J\subseteq\{0,\dots,n-1\}$ such that $\Pi_J$ is a positive instance of the full PCP.  Thus it suffices to check all the subsets $J$ with the algorithm for the full PCP; if at least one succeeds, the original PCP instance was positive, otherwise it was negative. $\Box$

The first grammar $G_1$ is constructed from a full PCP instance $\Pi$ in order to recognise
$$\begin{aligned}L_1&=\{ \$u_{j_0}\cdots \$u_{j_m}\#(\$v_{j_0}\cdots \$v_{j_m})^R\mid j_0,\dots,j_m < n\}\;,\\L'_1&=L_1\cup\{\#\}\end{aligned}$$
where $\cdot^R$ denotes the reversal operation, and $\$,\#$ are fresh symbols not in $\Sigma$.  Indeed, we can define $G_1=(\{S_1\},\Sigma\uplus\{\$,\#\},P_1,S_1)$ with $$P_1=\{S_1\to \$u_j S_1 v_j^R\$\mid j<n\}\cup\{S_1\to\#\}.$$ Then $L'_1=L(G_1)$.
Without loss of generality, we can assume $(u_i,v_i)\neq(u_j,v_j)$ for all $i\neq j<n$, and the grammar $G_1$ is minimal: the $\$$ symbols are indeed here to ensure minimality (as otherwise there might exist two different sequences of indices yielding the same words).

The second grammar generates `centered non-palindromes'
$$L_2=\{w\#{w'}^R\mid w\neq w'\in\Sigma^*\}.$$  Note that a word $w\#{w'}^R$ in $L_2$ is such that $w$ and $w'$ share a longest common prefix $u$: $w=uv$ and $w'=uv'$ for some $v,v'\in\Sigma^*$ with

either $v=ax$ and $v'=bx'$ for some $a\neq b\in\Sigma$ and $x,x'\in\Sigma^\ast$,
or $v=ax$ and $v'=\varepsilon$ for some $a\in\Sigma$ and $x\in\Sigma^\ast$,
or $v=\varepsilon$ and $v'=ax'$ for some $a\in\Sigma$ and $x'\in\Sigma^\ast$.

Thus $L_2$ is generated by $G_2=(\{S_2,E,A\},\Sigma\uplus\{\#\},P_2,S_2)$ with $$\begin{aligned}P_2&=\{S_2\to aS_2a\mid a\in\Sigma\}\cup\{S_2\to E\}\\&\cup\{E\to aA\#Ab\mid a\neq b\in\Sigma\}\cup\{aA\#\mid a\in\Sigma\}\cup\{\#Aa\mid a\in\Sigma\}\\&\cup\{A\to aA\mid a\in\Sigma\}\cup\{A\to\varepsilon\}\end{aligned}$$
The idea is that $S_2$ generates $u E u^R$ for $u$ the longest common prefix of $w$ and $w'$, after which $E$ applies one of the three cases above.  Thus $L(G_2)=L_2$, and the grammar is minimal.

Relating the two grammars.  Let $h$ be the homomorphism from $(\Sigma\uplus\{\$,\#\})^*$ to $(\Sigma\uplus\{\#\})^*$ defined by $h(a)=a$ for all $a\in\Sigma$, $h(\#)=\#$, and $h(\$)=\varepsilon$; $h$ simply erases $\$$ symbols.  Then $\Pi$ has a solution iff $h(L_1)\not\subseteq L_2$.  We define $L'_2=h^{-1}(L_2)$ and construct the corresponding grammar $G'_2=(N'_2,\Sigma\cup\{\$,\#\},P'_2,S'_2)$ in the obvious way (add a nonterminal $D$ with productions $D\to \$D$ and $D\to\varepsilon$ and introduce $D$ symbols everywhere in the right hand sides of the productions in $P_2$); it is still minimal and $\Pi$ has a solution iff $L_1\not\subseteq L'_2$.

We are however interested in the full PCP on $\Pi$.  Construct $$G=(N_1\uplus N'_2\uplus\{S\},\Sigma\uplus\{\$,\#\},P_1\cup P'_2\cup\{S\to S_1,S\to S'_2\},S) .$$

If $\Pi$ is a positive instance of the full PCP, then it has solutions, which describe words $\$u_{j_0}\cdots \$u_{j_m}\#(\$v_{j_0}\cdots \$v_{j_m})^R\not\in L'_2$ and moreover require every production of $G_1$.  Regarding $G'_2$, it suffices to consider words from $L_2\subseteq L'_2$ with no occurrence of $\$$, which do not belong to $L_1$ and therefore all the productions of $G'_2$ are needed.  Therefore, $G$ is minimal.
Otherwise, there exists $i<n$ such that $i\not\in I(\Pi)$, and the production $S_1\to \$u_i S_1 v_i^R\$$ can be removed, since it cannot be part of a solution of $\Pi$, and therefore any generated word that uses this production is in $L(G'_2)$; thus $G$ is not minimal.  In particular, if $\Pi$ has no solution ($I(\Pi)=\emptyset$), then all the productions in $P_1$ except $S_1\to\#$ can be removed. $\Box$


1) What scholarships exists in my area?

At this phase of your education, you should be talking to your advisers on a regular basis, or at least reading all of the material they send out. Usually advisers will send out all kinds of scholarship information as they receive them. So, your best bet is to talk to your adviser. You can also try scholarship search engines, many scholarships are not location-dependent.

  2) What Universities have open post-doc positions? Beside Princeton/IAS I did not found organized information in other universities.

This one is tricky and I recommend talking to your adviser here also. Many opportunities aren't advertised openly - it isn't always what you know, but who you know. Also consider that there may be opportunities and projects in different departments other than CS that need services a CS student can provide.

If you've already looked but couldn't find anything, then contact the advisers at those schools.

  3) How can I chose the right people to ask recommendation letters from?

Think about all of the people in the institution you have worked with. Advisers, teachers, mentors, ... Now, you want to choose the best people based on :

Choose those who knew you and worked close to you
How high ranked are they, how much relation do they have to your desired postdoc position?
How well do they think of you? Did you do good work for them? Did you get high grades in the class? Were they "wow!"ed by your performance?

  4) Assume that someone wants that I will come to his university to do a post-doc and this will require some effort to hire me(need to find money ...), but my first preference is other university which I still do not know if will want to hire me. What should I do in this case.

It's up to you. I think it's better to be open to everyone that you haven't decided yet so they are more understanding if you take a different route. When an offer does come up, just like a job, I think you can wait about a week before deciding. After that, you are stretching your luck.

Just remember that you don't want to burn any bridges here, be patient and open, and a solid offer has much more weight than a "maybe".


formalizing a statement about the expressive power of programming languages wrt divergence

Let us take a somewhat simplified view of a programming language as a mapping $C$ (the compiler) from finite strings of characters (source code) to descriptions of Turing machines (machine code). A description of a Turing machine is just a finite string of characters of a certain kind. And since finite strings of characters are computably isomorphic to natural numbers (we can computably encode string as numbers and vice versa), we can pretend that both source code and Turing machines are described by numbers.

Under this view a programming language $C$ is a partial map from natural numbers to natural numbers which accepts a number $n$ (the source code) and either diverges or returns a number $C(n)$ (the "compiled" Turing machine). It makes sense to require that $C$ is a computable map, i.e., that there is in fact a Turing machine that calculates it, otherwise magic is required to understand the programming language.

Note that I can enumerate all possible outputs of $C$. I simply try $C$ on every input in parallel by dovetailing, and whenever any parallel copy gives a result, I enumerate it. Let $f : \mathbb{N} \to \mathbb{N}$ be an enumeration of all outputs of $C$.

Let $\phi_k$ be the partial computable map that is computed by the Turing machine described by the number $k$.

We now come to the crux of the matter. Suppose $f$ enumerated precisely the total computable maps, i.e., $\phi_{f(n)}$ is a total computable map for all $n \in \mathbb{N}$, and for every computable map $g$ there is $n$ such that $g = \phi_{f(n)}$. Consider the computable map $d(n) = 1 + \phi_{f(n)}(n)$. This map is total because $\phi_{f(n)}$ is total for every $n$. There is $j$ such that $\phi_{f(j)} = d$, but then $\phi_{f(j)}(j) = d(j) = 1 + \phi_{f(j)}(j)$, contradiction.

The conclusion is that $f$ cannot possibly enumerate precisely the total computable maps. Therefore it either misses out some total maps, or enumerates some partial ones.


parallel algorithms for the determinant of the Hessenberg matrix

Sorry, this is clearly unlikely.
Otherwise, it would be possible to use the algorithm to solve any NL\poly
problem in NC1 via a reduction to evaluating the determinant of a Hessenberg matrix over a sufficiently large field.
The reduction appears as Lemma 3 (and related discussion) in
"Perfect constant-round secure computation via perfect randomizing polynomials".


Simple proof that splay trees have the dynamic finger property?

There has been a lot of further work more broadly on Splay trees and related data structures after the two papers that you mention, for example the 2019 paper of Levy and Tarjan [1].

However, there have been no alternative proofs or simplifications of the dynamic finger result of Cole et al. that you mention. (Any such attempt would be quite interesting to those working on these problems.)

There is, however, a 2016 paper by Iacono and Langerman [2] that proves a generalization of the dynamic finger property for a different data structure called Greedy BST, that matches many (all) known properties of Splay. The proof techniques here are easier and quite different from those in the Splay dynamic finger paper.

[1] https://doi.org/10.1137/1.9781611975482.80

[2] https://arxiv.org/abs/1810.01785


Minimal bandwidth required to synchronize two sets of values

This appears to be known as the "set reconciliation" problem. The key paper appears to be Minsky & Trachtenberg, "Set Reconciliation With Nearly Optimal Communication Complexity", IEEE Transactions on Information Theory (2003). Also, here is some subsequent work on this problem by the same authors: "Practical Set Reconciliation".


Batch membership testing for convex polyhedron specified in vertex representation

Instead of testing each point individually whether it is contained in the convex polyhedron, you should search for a supporting hyperplane of the polyhedron which separates the point from the polyhedron. If a supporting hyperplane does not exists, you know that the point is contained in the polyhedron. Otherwise, the supporting hyperplane helps you to separate additional points from the polyhedron. This is similar to the idea of D.W. but here you only enumerate a smaller number of supporting hyperplanes which is sufficient to separate all outer points.

Here are the details: Let $V$ be a matrix whose columns are the vertices $\mathbf{v}_1,\dots,\mathbf{v}_k$ of the polyhedron $\mathbf{P}$. The test points are denoted by $\mathbf{w}_1,\dots,\mathbf{w}_l$. A hyperplane $\{\mathbf{x}\mid \mathbf{n}^T\mathbf{x} = \lambda\}$ separates $\mathbf{P}$ and some point $\mathbf{w}_j$ if and only if $\mathbf{n}^T\mathbf{v}_i \leq \lambda$ for all $i=1,\dots,k$ and there is some positive $\epsilon>0$ with $\mathbf{n}^T\mathbf{w}_j \geq \lambda+\epsilon$. Assume, such an $\epsilon$ exists, then the conditions above are equivalent to
$\frac{1}{\epsilon}\mathbf{n}^T\mathbf{v}_i - \frac{1}{\epsilon}\lambda \leq 0$ for all $i=1,\dots,k$ and $\frac{1}{\epsilon}\mathbf{n}^T\mathbf{w}_j - \frac{1}{\epsilon}\lambda \geq 1$.
Substituting $\frac{1}{\epsilon}\mathbf{n}$ by $\tilde{\mathbf{n}}$ and $\frac{1}{\epsilon}\lambda$ by $\tilde{\lambda}$ yields the system of linear inequalities
$$V\tilde{\mathbf{n}} - \mathbf{1}\tilde{\lambda} \leq 0,\quad \mathbf{w}_j^T\tilde{\mathbf{n}} - \tilde{\lambda} \geq 1$$
where $\mathbf{1}$ is the vector whose coefficients are all $1$. Hence, the linear program
$$\mbox{minimize } \lambda \mbox{ subject to } V\mathbf{n} - \mathbf{1}\lambda \leq 0,\ \mathbf{w}_j^T\mathbf{n} - \lambda \geq 1$$
is either infeasible and $\mathbf{w}_j$ is contained in $\mathbf{P}$ or its  optimal solution $(\lambda, \mathbf{n})$ provides a separating hyperplane, which is indeed a supporting hyperplane of $\mathbf{P}$. Each remaining point $\mathbf{w}_i$ with $\mathbf{n}^T\mathbf{w}_i > \lambda$ is also not contained in $\mathbf{P}$ and can be removed from the test set.


Why economists should care about computational complexity

I see two separate directions to take your question. One is How has a computer science philosophy and computational thinking impacted the field of economics, and why should economists care about the computer science approach? This is a really cool but really broad question that I'll avoid attempting to address.

The second is more specific: Now that computer scientists know that many problems in game theory are hard, how do we convince economists that these are important issues with or objections to their work? This may not be what you had in mind, but it seems to be an interpretation of what you wrote, so I want to address it because I think it's a bit problematic and I think there are reasons not to write an essay arguing this point (which might explain any lack of answers).

First, micro-economists are often theorists and they may be more interested in understanding the problem in their model than in ours. There is no a priori reason one approach is better than the other. As an analogy, many theoretical computer scientists are happy to design algorithms that work over real numbers even though this may require undecidable operations. Similarly, to an economist, complexity may be a detail that clouds one's understanding of what's important in their model rather than a key consideration. This seems more a matter of preference or philosophy than right or wrong.

Second, it's not clear that computer science is yet in a position to argue convincingly that our models fit the real world better than theirs, until we have experimental data to back this up. (After all, it might be for example that markets often find equilibria quickly in practice, so hardness of computing is irrelevant to real-world applications.) Without data, the disagreement is philosophical and it's hard to claim there is a right or wrong side. I don't know that we have enough data yet to make any specific claims.

Third, I think many economists to whom these issues are relevant have been taking notice. In areas like matching, for example (subject of last year's Nobel!), a computational complexity and algorithmic approach is important as they attempt to implement solutions at large scale. So if an economist claims that complexity isn't relevant to her interests, she might be right; but there are others who do take notice.

So in sum, while it seems like a worthwhile goal to help make economists aware of the results regarding complexity in economics (especially as some do take interest), I am not sure that we are in a position to argue that they should take much notice or change their approach; and I think a strong scientific argument would require more data rather than just philosophy.


Separation between coarse correlated equilibria and correlated equilibria

Fix M>>1>>e and look at the following two player coordination game (both players get the same utility):

M   | 1+e  | 2e   |  e

1+e |  1   |  e   |  0

2e  |  e   |  M   | 1+e

e   |  0   | 1+e  | 1

The second and fourth row and column are strictly dominated so any correlated equilibrium cannot have them in its support, thus it would be on the sub-game:

M  |  2e

2e |  M

for which every correlated equilibrium would give each player more than M/2 utility.

On the other hand, consider the joint probability distribution giving probability 1/2 to each of the 1's, and thus utility 1 to each player.  The claim is that this is a coarse equilibrium.  In a coarse equilibrium the possible deviations of the row player are to one of the pure strategies independently of the outcome of the joint distribution.  Now if it is only known that the column player is mixing evenly between the 2nd and 4th column, then the maximum utility the row player can get is 0.5+e < 1, so deviation is not profitable.


The question seems quite open ended. Or perhaps you wish to have a precise characterization of the time-complexity of any possible symmetric polynomial over finite fields?

In any case, at least to my knowledge, there are several well-known results about the time-complexity of computing symmetric polynomials:

If $f$ is an elementary symmetric polynomial over a finite field then it can be computed by polynomial-size uniform $TC^0$ circuits.
If $f$ is an elementary symmetric polynomial over a characteristic $0$ field, then it can be computed by polynomial-size depth three uniform algebraic circuits (as you already mentioned the Newton polynomial; or by the Lagrange interpolation formula); and so I believe this then translates to polynomial-size uniform Boolean circuits (though perhaps not of constant depth) (but this may depend on the specific field you're working in; for simplicity you might consider the ring of integers; though for the integers I presume $TC^0$ is enough to compute symmetric polynomials in any case.)
If $f$ is a symmetric polynomial over a finite field then there is an exponential lower bound on depth three algebraic circuits for $f$ (by Grigoriev and Razborov (2000) [following Grigoriev and Karpinsky 1998]). But, as mentioned in 1 above, this corresponds only to constant-depth Boolean circuit lower bounds (while there are small uniform Boolean circuits in $TC^0$; meaning also that the polynomials are computable in polynomial-time).

Probably there are more known results about the time-complexity of symmetric polynomial...


Face-walks in rotation systems for graphs

If the sequence $v_0e_1v_1...$ is extended indefinetely without going back to $v_0e_1$, then since the graph is finite, some couple vertex-edge is repeated and hence it is periodic (since the facewalk always continues the same way after meeting this couple vertex-edge), so it looks like $v_0e_1v_1e_2.. v_{i-1}e_{i}v_ie_{i+1}...v_{i+j}e_{i+j+1}v_ie_{i+1}...v_i...v_i$ and so on indefinitely. We can assume that $e_i\neq e_{i+j+1}$ otherwise the loop never starts.
But then we have $e_{i+1}=\pi_{v_i}(e_i)$ and $e_{i+1}=\pi_{v_i}(e_{i+j+1})$, so $e_i=e_{i+j+1}$, yielding a contradiction. (I intentionnaly left out the $\lambda$ for the sake of clarity, but it works the same for non-pure rotation systems by replacing couple (vertex-edge) by triple (vertex-edge-value of $r_i$ when arriving at the vertex)).
For an edge $e$ attached to vertices $v_1$ and $v_2$, $e$ appears in the facewalks starting by $v_1 e$ and $v_2 e$ (possibly the same facewalk !). Moreover, it only appears in facewalks including $v_1 e$ and $v_2 e$ (where would it come from otherwise ?), so that makes exactly two facewalks (or twice the same). Edit : To be more precise, a facewalk is uniquely defined by a triple (vertex-edge-value of $r_i$ when arriving at that edge). But arriving at $v_1 e$ with orientation (value of $r_i$) -1 yields the same facewalk (up to reversing it) as arriving at $v_2 e$ with orientation +1, so there really are only two different facewalks passing through $e$.


Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?

Heller gives a relativized world where $BPP = EXP^{NP}$ which sits far outside of $P^{NP}$. Showing $BPP \neq EXP^{NP}$ unconditionally would in itself be considered a major breakthrough in derandomization.


Application of graph theory in computer science

This is in no way a definitive answer, and I do not intend it as such.

Many problems of interest to computer scientists can be phrased as graph problems, and as a result graph theory shows up quite a lot in complexity theory. The computational effort required to determine where two graphs are isomorphic, for example, is currently a topic of much interest in complexity theory (it is neither known to be NP-complete nor contained in P, BPP or BQP, but is clearly in NP). Graph non-isomorphism, on the other hand, has a very nice zero-knowledge proof (another area of study in complexity theory). Many complexity classes have graph problems which are complete for that class (under some reduction).

However it is not just complexity theory that makes use of graph theory. As you can see from some of the other answers, there is quite an array of problems for which the language of graph theory is most appropriate. There are far to many applications to provide a diffinitive list, so instead I will leave you with an example of how graph theory plays a fundamental role in my own area of research.

Measurement-based quantum computation is a model of computation which does not have a counterpart in the classical world. In this model, the computation is driven by making measurements on a special class of quantum states. These states are known as graph states, because each state can be uniquely identified with an undirected graph with a number of vertices equal to the number of qubits in the graph state. This link with graph theory is more than coincidental, however. We know that an important class of measurements (Pauli-basis measurements in case you are interested) map the underlying graph state to a new graph state on one less qubit, and the rules by which this occurs are well understood. Further, properties of the underlying graph family (it's flow and g-flow) determined fully whether it supports universal computation. Lastly, for any graph G' which can be reached from another graph G by an arbitrary sequence of complementing the edges of the neighbourhood of a vertex can be reached by single-qubit operations alone, and so are equally powerful as a resource for computation. This is interesting because the number of edges, maximum of the vertex degrees, etc. can change drastically.


Does the order of insertion affect the topology of an R-Tree

the R tree algorithms typically create "R"s (rectangles) iteratively/sequentially based on the order of insertion of the data. the "R"s are built directly out of the coordinates of the data seen so far. it does not appear that there are widely studied R-tree variants that build identical trees no matter what the order is, it does not seem to be a generally desired design criteria for the algorithms, which are judged on other criteria such as performance of search, insertion, overflow splitting etc.

except in artificial/contrived/"pathological" cases, the resulting R-trees will be "close" in structure and performance no matter what order the insertion. however it is not inconceivable that such an algorithm could be devised with the property of "resultant tree invariance" based on adjusting the insertion and overflow splitting logic.

on the other hand if you dont require an online algorithm you could just sort your data according to any criteria beforehand and the R tree will end up with the same structure of course.

a close alternative that can be adjusted to have the "order invariant" property you describe is the Quadtree because it is based on partitioning the overall space (assuming its dimensions are known) in a fractal "4-square" pattern that does not depend on ordering of the input or directly use the individual points for bounding coordinates.


Number of distinct nodes in a random walk

A comment:  I recently attended a talk by Bruce Reed with the title Catching a Drunk Miscreant, which was joint work with Natasha Komorov and Peter Winkler.  If you can get a hold of the results from this work, maybe that might help you in some direction.

In general, they prove an upper bound on the number of steps a cop need in a general graph to be able to catch a robber, when we know the robber moves at random along the edges.


Linear Time Maximum Clearance Computation on a Grid Graph?

All the sites are themselves grid points too, right? So I think it should work to compute the Delaunay triangulation of the sites in linear time using the word-model algorithm of Buchin and Mulzer (FOCS 2009), dualize to get the Voronoi diagram, and then fill out the grid neighbors within each Voronoi cell. The Delaunay part should be linear in the number of sites (its bottleneck is integer sorting, but for the magnitude of the integers in your problem sorting is easily done in time linear in the grid size).

To fill out the grid points within a single Voronoi cell, partition the cell along the lines connecting the cell's site to its neighbors and then find the grid points within each of the resulting quadrilaterals. That way it requires only a constant number of comparisons to determine whether any particular grid point belongs to the quadrilateral. Some quadrilaterals may be empty of grid cells but the total number of quadrilaterals formed in this way is linear so there isn't too much wasted work in the empty ones.


Can Lenstra's algorithm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k?

No. The number of feasible solutions cannot be upper bounded by $f(k)n^{O(1)}$.

Consider the integer program
$I_n: 1 \le x\le 2^n$
with the integer variable $x$. So, $k=1$ and the program can be described with $O(n)$ bits. But it has $2^n$ solutions, which is exponential in the instance size.


It sounds like you want an overview of normalization arguments for type systems with positive datatypes. I'd recommend Nax Mendler's PhD dissertation: http://www.nuprl.org/documents/Mendler/InductiveDefinition.html.

As the date suggests, this is pretty classic work. The basic intuition is that an ordinal $\lambda$ can be associated to any element of a positive inductive type, e.g. for the data type

Inductive Ord = Zero : Ord | Suc : Ord -> Ord | Lim : (Nat -> Ord) -> Ord

We would get:

$$ \lambda(t) = 0$$
if $t$ is a normal form which is not a constructor
$$ \lambda(\mathrm{Zero}) = 0$$
$$ \lambda(\mathrm{Suc}(o)) = \lambda(o)+1$$
and
$$ \lambda(\mathrm{Lim}(f)) = \sup_n \lambda(f\ n)$$

where $n$ ranges over terms with normal forms. The caveat is that this interpretation is only defined in the 3rd case when $f\ n$ has a normal form as well, which requires some care in the definitions.

One can then define recursive functions by induction over this ordinal.

Note that these data types can be defined already in classical set theory, as indicated in the excellent Inductive Families paper by Dybjer (http://www.cse.chalmers.se/~peterd/papers/Inductive_Families.pdf). However, because the function spaces are so huge, types like Ord require really large ordinals to interpret.


Size of decision tree for f is polynomial in the DNF size of f and CNF size of f

As pointed out by the OP (user13772), this is false.  Jukna et al. constructed explicit Boolean functions $f$ that require deterministic decision trees of size $2^{\Omega(\log^2 N)}$, where $N$ is the number of monomials in a minimal DNF for $f$ and $\lnot f$.  Note that every Boolean function on $n$ inputs can be expressed as a deterministic decision tree of size $2^{O(\log n \log^2 N)}$.

S. Jukna, A. Razborov, P. Savický, I. Wegener, On P versus NP$\cap$co-NP for decision trees and read-once branching programs, Computational Complexity 8 (1999), 357–370.  doi:10.1007/s000370050005  (preprint)


Semantic definition of strict positivity for a functor

One semantic criterion is preservation of $\omega$-colimits, or $\omega$-cocontinuity. AFAIK, initial algebras of such functors correspond to finitary inductive types in type theory. The construction of initial algebras, given by Adámek's theorem, can be formalized inside type theory as well. It's described in this paper and there's a Coq formalization for it. Probably there is a generalization of this to transfinite colimits, which would give us infinitary inductive types, but for this I don't know any formalization.


How to determine if a labelled digraph contains a cycle with given labels?

The following suggestion may speed up your solution if you need to answer queries for many different words.

Define the set $U_i^w$ to be a set of pairs $(v, A)$ where $A \subseteq V$ and $v$ is reached by some vertex in $A$ after traversing the first $i$ labels of the word $w$.  Then to check if $w$ forms a cycle in the graph, loop through all $(v, A) \in U_{|w|}^w$ and if ever $v \in A$, then a cycle does exist.

Note that if the first $i$ elements of $w$ and $w'$ are the same, then $U_i^w = U_i^{w'}$.  Also, $U_0^w = \{(v, \{v \} ) | v \in V \} $.

As you process queries, dynamically construct a trie such that each node (including the inner nodes) stores $U_i^w$ for some $i$ and $w$.  This way, if $w$ and $w'$ have the same first $k$ elements and $w$ is processed before $w'$, then $U_k^{w'}$ can be quickly retrieved by traversing the first $k$ nodes of the trie.


(I'm not an expert in this subject, but here's my understanding.)

The BCH code of code length $n=2^m-1$ and designed distance $2t+1$ is specified in terms of its generator polynomial.  Fix $\alpha$ to be a primitive element of $GF(2^m)$.  Then, $g$ is the polynomial of smallest degree with coefficients in $GF(2)$ which has its roots $\alpha, \alpha^2,\alpha^3,\dots,\alpha^{2t}$.  (The codewords are then given by all multiples of $g$ of degree at most $n-1$; see the wikipedia page for polynomial codes).  The designed distance is a lower bound on the distance of the code.

The dual BCH code of design distance $2t+1$ is just the dual of the BCH code in the usual sense, the set of vectors orthogonal to the codewords of the BCH code of design distance $2t+1$.  Its generator polynomial is given by $(X^n+1)/g(X)$.  I believe the matrix in the Ailon-Liberty paper has the codewords as its rows.

Here are some notes which describe the BCH code construction: http://www.uotiq.org/dep-eee/lectures/4th/Communication/Information%20theory/2.pdf


Technical lemma about curves used in original proof of PCP theorem

Notation: Let $P(\langle x_1,\dots,x_k\rangle)$ the set of degree $k$ curves that evaluates to $x_1,\dots,x_k\in\mathbb{F}^m$ at the first $k$ field elements in $\mathbb{F}$ and we will use just $P$ as a shorthand for this set.  Let $S$ be any subset of $ \mathbb{F}^m$. Below, we assume
that multiplicity is taken into account when set cardinalities are computed and for any curve $C\in P$, $|C|:=|\{C(i) : k+1<i\leq \mathbb{F} \}|$.

Claim 1: $\mathbb{E}_{C}\big[ \frac{|C\cap S|}{|C|} \big]=\frac{|S|}{|\mathbb{F}|^m}$ where $C$ is a random curve in $P$.

Proof: $\mathbb{E}_{C}\big[ \frac{|C\cap S|}{|C|} \big]=\sum_{C'\in P}\Pr_{C}\big[C=C' \big]\cdot\Pr_{i}\big[C'(i) \in S\big]= \Pr_{C,i} \big[C(i)\in S \big]= \frac{|S|}{|F|^m} $

Here $C$ is a random curve in $P$ and $i$ is randomly sampled from $\{k+1,\dots,\mathbb{F} \}$. The last line holds because sampling a random curve from $P$ and then evaluating the curve at a random $i$ gives a random element from $\mathbb{F}^m$. To see why this is true consider the bipartite graph on $P\cup \mathbb{F}^m$ where for each $i\in \{k+1,\dots,\mathbb{F}\}$, each curve $C\in P$ has a neighbor $C(i)\in \mathbb{F}^m$. Its easy to check that this is a bi-regular graph. Thus, the distribution that samples a random $C$ and outputs a random neighbor $C(i)\in \mathbb{F}^m$ , is same as the distribution that randomly outputs an element from $\mathbb{F}^m$. The claim follows.

Remark 1: Claim 1 implies  that if $|S|/|\mathbb{F}|^m\leq \delta$ then we must have $\Pr_{c}[\Pr_{i}[~c(i)\in \mathcal{S}] >  \sqrt\delta] \leq \sqrt{\delta}$. This I believe is the claim (from the linked thesis) that OP refers to.

Remark 2: What happens if we just sample a random point $i$ from the entire field $\mathbb{F}$ instead of $\{k+1,\dots,\mathbb{F} \}$. Nothing will change much as it will incur a small(if $k\ll |\mathbb{F}|$) additive error of $k/|\mathbb{F}|$. In [1] below this error is there in the argument in page 38.

[1] https://madhu.seas.harvard.edu/papers/1997/arora-journ.pdf


Is it beneficial to regularly read papers outside your field?

Understanding papers outside your field can be surprisingly difficult --- every field develops its own specialized terminology and shared background knowledge. A much better advice I once received from a very productive researcher was: Try to attend research seminars outside your field. These are typically more accessible than "cold" paper reads, and you have the advantage of being able to interactively ask questions. Just talking to people about their research can be extremely useful as well. You'll occasionally hear stories about how someone from field A happened to join a lunch table with people from field B and realized that he has the tools to solve their long-standing open problem (or, conversely, they have a tool to solve his).


If you mean O(1) processors, then no, computation complexity cannot be reduced.

Simply line up the work done by each processor and do it on a single one. If you are worried about synchronization, then one processor can easily emulate that.


Hierarchy theorem for NTIME intersect coNTIME?

(This would've been a comment, but it doesn't render properly when I try that.)

"I don't even see how to separate" $\;\;\;$$\mathbf{U}$$\mathbf{q}$$\mathbf{uasiLIN}$ $\cap \; \mathbf{coUquasiLIN} \;\;\;$ from

$[$the linear-exponent version of QIP[2]$] \;\; \cap \;\; [$the linear-exponent version of coQIP[2]$] \;\;\;\;\;$.


Is there a well-known nontrivial subset of NP for which it is known that it is a proper subset?

[Answering the original motivating issue: "Should I just accept the first statement since NPC is defined with respect to deterministic polytime reductions?"]

First, if $P=NP$ but the Berman-Hartmanis Isomorphism Conjecture fails, then there are infinitely many distinct p-isomorphism classes of languages within $P$. So even though it is true that $P=NP$ implies all sets in $P$ are $NP$-complete with respect to polynomial-time reduction (technical caveat below), that does not mean that we lose all information about $P$. By looking at a finer type of reduction -- but still polynomial-time, namely polynomial-time computable-and-invertible length-increasing one-one reductions -- we can potentially tell a lot about what's going on inside $P$.

In fact, if $P=NP$ but the Isomorphism Conjecture fails, then the partially ordered set of p-isomorphism classes inside $P$ is quite rich: any countable partial order can be embedded in it (see P. Young. Some structural properties of polynomial reducibilities and sets in NP. STOC 1983.).

But more generally, in some cases it does feel wrong to lump all of $P$ together and in other cases it's exactly what you want. This is why, for example, we don't use poly-time reductions when discussing $L$ versus $P$, but we do when discussing $P$ versus $NP$. But there might be another class you want to contrast with $NP$ where it makes sense to use other reductions. The type of reduction you use should be the type you need for the problem at hand; there is no "single right reduction" to define, e.g., $NP$-completeness (though "$NP$-complete" without qualification usually means w.r.t. poly-time many-one reductions, but that is a matter of convention).

Distinctness of complexity classes is not parametrized by reductions; however, there are several potentially distinct classes that could legitimately be called "$NP$-complete," namely for any reducibility $r$, "$NP$-complete with respect to $r$-reductions".

(Caveat: If we use poly-time many-one reductions, then $\emptyset$ and $\Sigma^{*}$ do not become $NP$-complete if $P=NP$. If we use poly-time Turing reductions, or even poly-time 1-tt reductions, they do.)


An infamous example in computational geometry is the incorrect proof of the Zone Theorem for hyperplane arrangements published by Edelsbrunner, O'Rourke, and Seidel [FOCS 1983, SICOMP 1986].  The proof also appears in Edelsbrunner's 1987 computational geometry textbook.

  Zone Theorem: In any arrangement of $n$ hyperplanes in $\mathbb{R}^d$, the total complexity of all cells intersecting any hyperplane is $O(n^{d-1})$.

The Zone Theorem is a key step in the proof that the standard recursive incremental algorithm to build an arrangement of $n$ hyperplanes in $\mathbb{R}^d$ runs in $O(n^d)$ time.

In 1990, Raimund Seidel discovered that the published proof was incorrect, after being challenged on a subtle technical point by a student in his computational geometry class.  Meanwhile, a huge literature on hyperplane/halfspace/simplex/semialgebraic range searching had been developed, all of which relied on the $O(n^d)$ construction time for arrangements, which in turn relied on the Zone Theorem.  (None of those authors noticed the bug.  Raimund had taught the published "proof" in detail for several years before he was challenged.)

Fortunately, Edelsbrunner, Seidel, and Sharir almost immediately found a correct (and much simpler!) proof of the Zone Theorem [New Results and New Trends in CS 1991, SICOMP 1993].


How quickly can we perform base extension in a residue number system?

Check out Lemma 4.4 in HesseAllenderBarrington - it may not be terribly useful for sequential complexity but says essentially that CRR (Chinese Remainder Representation) basis extension can be done in very uniform $\mathsf{TC}^0$. The exact bound is $\mathsf{FOM + POW} = \mathsf{FOM}$ (see also Corollary 6.2 of the same paper).


Does Huffman coding always produce shorter codes than the Shannon code?

This is actually problem 5.12 in Cover and Thomas's information theory textbook; show that the probability distribution ${1/12,1/4,1/3,1/3}$ gives a counterexample.

And if you want a really nice counterexample, consider the many non-isomorphic Huffman trees you can make when you have probabilities proportional to $$1,1,1,2,3,5,8,13,21,34$$ (the Fibonacci series with an extra 1). Figure out what the maximum and minimum depths are for a Huffman tree with this probability distribution. This calculation will lead to a counterexample for your follow-up question.


Minimal information needed for determine some function

A natural condition is to bound the number of states of $T$ --- say, at most $n$. The set
$\mathcal{C}_n$
of all TM's on at most $n$ states is finite --- in fact, of cardinality $2^{O(n)}$. It is well-known that finite classes have a finite teaching dimension,
http://www.cs.columbia.edu/~djhsu/coms6998-f17/student-work/scribe-notes/teaching_dimension.pdf
of size $d_n=O(|\mathcal{C}_n|)$ --- meaning that for each $M\in\mathcal{C}_n$, some set of at most $d_n$ labeled strings uniquely identifies $M$. Taking the union of these "teaching sets" over all $M\in\mathcal{C}_n$ gives you a finite set $S\subset\Sigma^*$, which belongs to $\Sigma^{\le n_0}$ for some $n_0$. Now you required that all of the examples be of the same length, but other than that, this satisfies your criteria.

The bottom line is that for fixed $n$, the resulting $n_0$ will be a constant.


I'm not sure, but I think that the problem here is the fact that we don't have any strong assumptions about pseudorandom monotone function generators (at least none that I know of). The idea of the proof in Razborov-Rudich paper is as follows:

  if there is a natural property of functions (i.e. an efficiently
  decidable property that holds for
  sufficiently large subset of functions
  and implies that the function needs
  big circuits), then it can be used to
  break pseudorandom function generators
  (which breaks also pseudorandom
  generators and one-way functions).

If we were to restate the theorem in terms of monotone functions and monotone circuits, we would like it to say

  if there is a natural property of monotone functions (i.e. an efficiently decidable property that
  holds for sufficiently large subset of
  monotone functions and implies that
  the function needs big monotone
  circuits), then it can be used to
  break pseudorandom function generators
  (which breaks also pseudorandom
  generators and one-way functions),

but now the proof from the paper stops to work, because our pseudorandom generator outputs general functions, not necessarily monotone ones, and we cannot use our natural property to break it, because even a relatively large subset of monotone functions will not be large relative to general functions, for the set of monotone functions itself isn't large relative to the set of all functions ( http://en.wikipedia.org/wiki/Dedekind_number ). We could define some pseudorandom monotone function generator and use the natural property to break it, but we probably would not have the equivalence between this generator and one-way functions, so the theorem would not be so interesting.

Maybe this difficulty can be fixed (but I don't think it follows from the proof in the paper in a straightforward way) and maybe the problem with the monotone functions lies somewhere else. I would really like someone more experienced than me to confirm my answer or to show where I am wrong.