Deciding the Most Significant Bit of Binary Multiplication I am interested in determining the complexity of the following decision problem: Given two integers $l_1$ and $l_2$ (each with at most m bits), decide whether the most significant bit of the multiplication $l_1 \cdot l_2$ is 1 (where the result is printed in 2m bits with possibly leading 0's)?

Some background on the problem: Obviously, this problem is a special case of binary multiplication that asks whether the $i$-th bit of the multiplication $l_1 \cdot l_2$ is 1.  In their paper, Uniform constant-depth threshold circuits for division and iterated multiplication, Hesse, Allender and Barrington prove that iterated (and thus binary) multiplication is in $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$. Moreover, it seems to be well-known that binary multiplication is already $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard. However, I was not able to find a particular source proving this hardness result. As a non-expert in circuit complexity, I would also appreciate a pointer to this general hardness result. Finally, assuming that binary multiplication is $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard, my question can also be read as: Does it remain $\mathsf{DLogTime}$-uniform $\mathsf{TC}^0$-hard if we want to decide only the most significant bit of binary multiplication?

UPDATE: Kaveh's answer clarifies why binary multiplication is $\mathsf{TC}^0$-hard (reduction from COUNT). The precise complexity of deciding the most significant bit of binary multiplication remains open (and the bounty is for this question).

Multiplication is complete for $\mathsf{TC}^0$ and
this is a well know result.
The reduction is from Count
(number of 1 bits in a binary number).
Comparison of binary numbers is in $\mathsf{AC^0}$
so $\mathsf{Majority}$ is reducible to $\mathsf{Count}$.

To reduce $\mathsf{Count}$ to $\mathsf{Mult}$ do as follows:
consider input is $a_0a_1\ldots a_n$.
Insert $k$ 0s between $a_i$s and call it $a$.
Multiply it with $b$ which is like $a$ except that
$a_i$s in it are replaced with 1s.
Pick $k>3n$.
The number in the middle section of $ab$ is the answer.
The reduction is in $\mathsf{FO}$ and shows that
$\mathsf{Count} \in \mathsf{FO(Mult)}$.


Finding a prime greater than a given bound Is a deterministic polynomial-time algorithm known for the following problem:

Input: a natural number $n$ (in binary encoding)

Output: a prime number $p > n$.

(According to a list of open problems by Leonard Adleman, the problem was open in 1995.)

The current best unconditional result was given by Odlyzko,  which finds a prime $p >N$ in $O(N^{1/2 + o(1)})$ time. The strong conjecture in Polymath4 project seeks to resolve if this can be done in polynomial time, under reasonable number-theoretic assumptions like the GRH.

http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

Currently the project seeks to answer the following question:

  Given a number $N$ and an interval between $N$ and $2N$, check in time $O(N^{1/2 - c})$ for some $c>0$ if the interval contains a prime.

So far, they have a strategy which determines the parity of the number of primes in the interval.

http://polymathprojects.org/2010/06/29/draft-version-of-polymath4-paper/


Natural, untestable graph properties In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from having the property. (An algorithm can be asked to succeed with 1-sided or 2-sided error.)  A graph is $\epsilon$-far from having a property if no $\epsilon \binom{n}{2}$ edges can be added/subtracted to make it have the property.

A property is said to be testable if it can be tested in the manner specified above in a sub-linear number of queries, or better yet, in a number of queries independent of $n$ (but not $\epsilon$).  The notion of what properties are can also be formalized, but it should be clear.

There are many results characterizing what properties are testable, with many examples of natural testable properties.  However, I am not aware of many natural properties that are known to not be testable (say in a constant number of queries) -- one that I am familiar with is testing for isomorphism to a given graph.

So, my question is: what natural graph properties are known not to be testable?

In the adjacency matrix model, there is a lower bound of $\Omega(n)$ on the query complexity of testing whether an $n$ vertex graph consists of two isomorphic copies of some $n/2$-vertex graph (see Introduction to testing graph properties - Goldreich for a survey).

Also, there are many lower bounds that depend on $n$ for testers with one-sided error, e.g.: testing $\rho$-Clique,$\rho$-Cut, and $\rho$-Bisection (see Property testing and its connection to learning and approximation - Goldreich, Goldwasser, Ron)

Moreover, in the bounded degree graph model, testing 3-Colorability requires $\Omega(n)$ queries, whereas testing 2-Colorability (i.e., Bipartiteness) requires $\Omega(\sqrt n)$ (see Property testing in bounded degree graphs - Goldreich, Ron).


Known properties of a specific class of quantum states Recently, I have been studying a quantum protocol for the "Hidden Matching" problem that makes use of states that can be expressed as

$|\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^n (-1)^{x_i}|i\rangle$,

where $x_i\in \{0,1\}$ and $n$ is a power of 2. Note that instead of an $n$-level system we can consider these as states of $\log_2 n$ qubits. I suspect these states to have appeared in other contexts as they are a straightforward and useful way to map an $n$ bit string into an exponentially smaller amount of qubits. Hence I am wondering: have the properties of these types of states been already extensively studied?

I am particularly interested in how the reduced density matrix of each qubit and the entanglement of the state depend on the bit values $x_i$.

Thank you!

M. G. Parker and V. Rijmen have studied the quantum entanglement of binary and bipolar sequences in arXiv:quant-ph/0107106. I remember reading their paper long ago. They use a lot of terminology from coding theory, so now by just skimming through, I can't understand exactly what their result is, but you can have a deeper look.

Notice also that graph states are a special case of your states. In particular, $\psi$ is a graph state if and only if the sequence $x$ is generated by a quadratic polynomial in GF(2).


Total orders which are the transitive closure of a set in P I am wondering if there is an example of the following form. It seems highly plausible that there should be but I am struggling to come up with one.

Consider $T \subseteq \mathbb{N}^2$, a set representing a total order. That is we have some total order $\preceq$ such that $i \preceq j$ iff $(i, j) \in T$.

Does there exist $T$ and a subset $S \subseteq T$ such that:

The decision problem $(i, j) \in T$ is "probably not in P". e.g. is NP-hard or is provably not in P.
The decision problem $(i, j) \in S$ is in P
$T$ is the transitive closure of $S$ (i.e. the smallest set $M$ containing $S$ such that if $(i, j), (j, k) \in M$ then $(i, k) \in M$)

Note that if e.g. there's some polynomial $p$ such that for all $(i, j) \in S$ there exists some $k \leq p(i, j)$ with $(i, k), (k, j) \in T$ then the decision problem for $S$ is necessarily in NP (because you can provide such a k and verifying that it works is polynomial in $i, j$), but I suspect there are examples which don't satisfy this.

Note that the conditions imply that $T$ is recursive. The construction below shows that apart from that, its complexity can be arbitrarily large.

Let $L\subseteq\mathbb N$ be an arbitrary recursive language, and $f\colon\mathbb N\to\mathbb N$ a function such that $x\in L$ is decidable in time $|f(x)|$, and the subgraph $\{(x,y):y<f(x)\}$ is polynomial-time decidable. (Here $x,y$ are assumed to be written in binary as usual.) Let $(x,y,i)$ be an efficient bijective enumeration of triples where $x,y\in\mathbb N$, and $i=0,1$. Let $S$ consist of the following pairs of these triples:

$((x,y,i),(x',y',i'))$ for $x<x'$.
$((x,y,i),(x,y',i))$ for $y<y'<f(x)$.
$((x,f(x),0),(x,0,1))$ and $((x,f(x),1),(x,f(x)+1,0))$ if $x\in L$.
$((x,f(x),1),(x,0,0))$ and $((x,f(x),0),(x,f(x)+1,0))$ if $x\notin L$.
$((x,y,i),(x,y',i'))$ if $f(x)<y$ and $2y+i<2y'+i'$.

The properties of $f$ ensure that $S$ is polynomial-time decidable, and it is easy to see that its transitive reflexive closure is a total order $T$. However, $T$ is as hard to compute as $L$, since $((x,0,0),(x,0,1))\in T$ iff $x\in L$. (Conversely, $T$ is easily seen to be reducible to $L$.)


Where can I find an elementary small-step structural operational semantics for closures? Lexical closures are an implementation technique in languages with first-class functions.

I'm interested in a simple operational description of function closures. Does anyone know of such a description?

Is chapter 29 of Bob Harper's book what you are looking for?


The number of edges in the ith shortest path in a directed graph $G$ - directed graph,
$n$ - count of nodes

According to Eppstein's Algorithm in this paper, the ith shortest path in a digraph may have $\Omega(ni)$ edges.

Anybody can explain how this estimate is taken?

As Igor said- Consider a directed cycle with n vertices $C=(v_1,v_2,\ldots,v_n,v_1)$.

The shortest path between $v_1$ and $v_n$ is the path $(v_1,v_2,\ldots, v_n)$ and goes through $n-1$ edges.
The second  shortest path between $v_1$ and $v_n$ completes a cycle $C$ once, and then uses the path $(v_1,v_2,\ldots, v_n)$. It uses $2n-1$ edges.

The $i^{th}$ shortest path uses $in-1=\theta(in)$ edges


What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k? I asked this question some weeks ago at mathoverflow, but I got no reply.

Here, by 3D-grid of sidelength $k$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,k\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$, i.e., the nodes are placed at 3-dimensional integer coordinates between 1 and $k$, and a node is connected to the at most 6 other nodes that differ in precisely one coordinate by one.

What is the name of this graph? I'll use 3D grid, but perhaps 3D mesh or 3D lattice are what other people are used to.

  What is the treewidth or pathwidth of
  this graph?  Is this already published
  somewhere?

I know already that $tw(G) = (3/4) k^2 + O(k)$, i.e. it is really smaller than $k^2$.
To me, this suggests that the standard arguments showing that the $k\times k$ 2D-grid has treewidth and pathwidth $k$ will not easily generalize.

To see this, we consider a path decomposition that "sweeps" the grid using mainly node-sets of the form $S_c= \{(x,y,z)\mid x+y+z = c\}$.
Observe $|S_c| \leq (3/4) k^2 + O(k)$, $S_{3/2 k}$ being the largest such set.
The sets between $S_c$ and $S_{c+1}$ are created by sweeping with a line and need $O(k)$ additional nodes to be separators. More precisely, use the sets
$S_{c,d} = \{(x,y,z)\mid (x+y+z = c \wedge x \leq d ) \vee (x+y+z = c \wedge x \geq d ) \}$ as a path decomposition of $G$.

I also have an idea for a proof that shows $tw(G) = \Omega(k^2)$, but that is not finished yet.

The pathwidth of $P^3_k$ can be determined as a corollary to some known results.
FitzGerald [2] showed that the bandwidth of $P^3_k$ is $\lfloor \frac{3}{4} k^{2} + \frac{1}{2} k \rfloor$.
Harper [3] showed a condition such that if a graph satisfies the condition, then its pathwidth and bandwidth are the same.
Moghadam [4,5] and Bollobás and Leader [1] independently showed that any multi-dimensional grid satisfies Harper's condition.
These results imply that the pathwidth of $P^3_k$ is also $\lfloor \frac{3}{4} k^{2} + \frac{1}{2}k \rfloor$.

In our paper mentioned by Hsien-Chih, we generalized FitzGerald's result as Yoshio explained.
I believe the treewidth of $P^3_k$ is not known.

FYI: I've just submitted an English version of our paper to arXiv.

B. Bollobás and I. Leader, Compressions and isoperimetric inequalities, J. Combin. Theory Ser. A 56 (1991) 47-62.
C.H. FitzGerald, Optimal indexing of the vertices of graphs, Math. Comp. 28 (1974), 825-831.
L.H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory 1 (1966) 385-393.
H.S. Moghadam, Compression operators and a solution to the bandwidth problem of the product of $n$ paths, Ph.D. thesis, University of California, Riverside (1983).
H.S. Moghadam, Bandwidth of the product of $n$ paths, Congr. Numer. 173 (2005) 3-15.


On Zero sum perfect matching Fix $c\geq1$.

Input is a $m$ vertex complete graph with edges assigned $a_1,\dots,a_{\frac{m(m-1)}2}\in\Bbb Z$ in some order.

Is it $\mathsf{NP}$-complete to decide if there is a perfect matching of zero-sum for cases:

(A) $|a_i|\leq m^{\frac1c}$

(B) $|a_i|\leq\log^{c}m$?

I looked at the literature for perfect matching and subset sum and could not find this version.

The closest was minimum weight perfect matching which has a polynomial time algorithm as in http://www.math.uwaterloo.ca/~bico/papers/match_ijoc.pdf which however in this case does not work.

It also seems like restricted version of subset sum and so the complexity is not obvious because of size of $|a_i|$.

Update: Including case C.

(C) What if $a_i$ needs roughly $m^\alpha$ bits for some fixed $\alpha>0$?

The problem is in RP in both (A) and (B) by a variation of Lovasz's algorithm:
Fix a finite field $F$ of characteristic $2$ on at least $q=4m\max_i |a_i|$ elements.
Consider the graph's Tutte matrix $T(r)$ where you replace indeterminate $x_{ij}$ by $y_{ij}r^{a_{ij}+q/4}$, where $y_{ij}=y_{ji}$ is a uniformly and independently randomly chosen element in $F$ and $r$ is an indeterminate. Now observe that the determinant equals $\sum_{\mbox{Matching }M} \prod_{ij\in M} y_{ij}^2r^{2a_{ij}}$.
Hence, you can solve for the coefficient of $r^{q/2}$ in the polynomial $\operatorname{det} T(r)$ to see if there is a zero-sum matching. Compute the determinants of the numerical matrices $T_r$ obtained after replacing $r=1,2,\ldots, q$ in $T(r)$, and use interpolation to recover the coefficient. It is non-zero with probability at least $1-m/q$ if and only if the graph had a zero-sum matching.
Update: In (C) the problem is NP-complete.
Consider an instance $b_1,b_2,\ldots, b_n$ and $t$ to Subset Sum, i.e. is there a subset $I\subseteq [n]$ such that $\sum_{i\in I} b_i=t$?
We can embed this in a Zero-sum matching problem as follows. Consider the bipartite graph with biadjacency matrix $\begin{bmatrix}I_n & I_n & 0\\I_n & I_n & 0\\0 & 0 & 1 \end{bmatrix}$, where $I_n$ is a $n\times n$ identity matrix, and weights $\begin{bmatrix}B & 0_n & 0\\0_n & 0_n & 0\\ 0& 0 & -t \end{bmatrix}$
where $0_n$ is a $n\times n$ all-zero matrix and $B=\operatorname{diag}(b_1,b_2,\ldots,b_n)$ is a $n\times n$ diagonal matrix.
Now observe that there is a zero-sum perfect matching if and only if there is a solution to the Subset Sum instance.


How to shuffle colour balls? I have 400 balls, in which 100 are red, 40 are yellow, 50 are green, 60 are blue, 70 are purple, 80 are black. (balls of the same colour are identical)

i need an efficient shuffling algorithm, so that after shuffling, balls are in a list, and

Any consecutive 3 balls are not of the same colour. e.g, i can not have "red, red, red, yellow...."

And, all permutation are "equally" likely to occur. (well, if the trade-off of efficiency vs. unbiasedness is good enough, i don't mind more efficiency than unbiasedness).

i tried to adapt Fisher-Yates-Knuth, but the outcome is not ideal.

Why Fisher-Yates not good enough? As FY adopts Monte Carlo inverse transformation. And the output distribution treats the same colour balls differently, i.e. it would generate biased result for my needs.

And, the Naive thinking would be to filter out / backtracking all bad permutations from the whole space. When the restriction is very strong, say, if we have only 300 balls and 100 of which are red, then there will be too many back tracking/failures before getting an appropriate permutation.

So, ultimately, I would wish to be able to iterate through all good permutations. However, because the number of valid permutations is too large, i can only randomly sample some of them. I wanna the statistical feature of the "some" of them resemble the population as much as possible.

What you need for a Markov chain to converge to an equal distribution over all possible sequences of balls is that it is reversible: the probability of moving from sequence $i$ to sequence $j$ is the same as moving in the opposite direction. I thus propose that you use the following moves (with some fixed probability distribution to choose which type of move to make) to perform a Markov chain on all possible sequences. In the following, a "run" is a maximum-length consecutive subsequence of balls of the same colour. This Markov chain relies on there being at least three colours.

Pick two runs at random. If you can exchange them and still have a legal sequence, do so.
Pick two adjacent runs. If you can exchange them and still have a legal sequence, do so.
Pick two runs of the same colour. Redistribute the balls in them randomly among legal possibilities (so if the maximum number of balls in a single run was 3, and you had 5 balls total in the two chosen runs, the first one is equally likely to get 2 or 3 balls; if there were 3 balls total, the first is equally likely to get 1 or 2; if there were 4 balls total, 1, 2, and 3 are all equally likely).
Pick some colour $C_i$ at random. Consider the sequence $S'$ of balls with all balls of colour $C_i$ removed. Now, pick at random two points in $S'$ where adjacent balls of different colours touch.

a. If there are two runs of colour $C_i$ at these two points in the original sequence $S$, and neither is maximum length, move a ball from one to the other, with each direction chosen with probability ½.

b. If there are two runs of colour $C_i$ at these two points in the original sequence $S$, but one is maximum length and the other is not, move a ball from the maximum length run to the shorter one with probability ½.

c. If there is just one run of colour $C_i$ at one of these two points in $S$, with probability ½ move one ball from the run to the other point.

d. If there is no run of colour $C_i$ at either of these points, or if there are runs of maximum length at both of these points, do nothing.

If my analysis is right, this is a reversible Markov chain that eventually converges to a uniform distribution of legal sequences of coloured balls, so if you run this chain for long enough, you will get very close to this uniform distribution.

How can you tell when this has converged? I would suggest watching the entropy of this sequence, and stop when it stops increasing. How do you compute the entropy? There are two main terms in the entropy calculation: the distribution of run lengths, and the sequence of colors each run has. For the distribution of run lengths, assume that there are $n_{i,k}$ runs of colour $i$ with length $k$. The contribution of these to the entropy is
$$ \sum_i \ \log_2 \ { \sum_k n_{i,k} \choose n_{i,1}\ n_{i,2}\ \ldots \ n_{i,r} }, $$
where $r$ is the maximum permissible length of a run. Now, let us consider the contribution of the colour sequence to the entropy. Suppose there are $m_{i,j}$ places where a run of colour $i$ is immediately followed by one of colour $j$ (so $m_{i,i}=0$). The contribution of this to the entropy is
$$ \sum_i \ \log_2\  { \sum_j m_{i,j} \choose  m_{i,1}\ m_{i,2}\ \ldots \ m_{i,c} }, $$
where $c$ is the number of colours.

(In the interest of accuracy, let me note that we are leaving out a number of contributions to the entropy, including the colour of the first ball, but these are lower order terms which should be safe to neglect.)

UPDATE:

There should be ways of speeding this up. I believe that for steps c and d, you can use analysis to perform both these steps over all runs of one color at once. For steps a and b, this is equivalent to the question of finding a random sequence of colored balls with the constraint that no two balls of the same color touch. There should be some good way of doing the mixing for this problem. Then you just have to alternate a/b steps with c/d steps, where each step mixes over those two moves completely. I think this should converge quite fast, although I don't have any rigorous analysis for this Markov chain.


Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible? In the recent preprint https://arxiv.org/abs/1801.00776, it is claimed that $n$ real numbers can be sorted in time
$$O(n \sqrt{\log n}),
$$
and linear space. The paper seems reasonable, though I am not an expert in sorting algorithms.

If correct, this would be a significant, I believe, at least theoretically.

The presentation of the main argument is somewhat informal and nontraditional, however.

Has anyone noticed/commented on this paper? It seems that the same author, Yijie Han, has published a related result on integer sorting, as discussed in Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm

Based on Sasho Nikolov's very helpful comment, it seems that both papers use similar models of complexity which lead to unreasonable conclusions, such as the implication that any problem in PSPACE or #P can be solved in polynomial time.

I welcome any comments which may lead to a modification of this tentative answer.


Maximizing the number of heads in $N$ tosses by choosing which coin to toss Assume you have two coins $A,B$ with biases $P_A,P_B$ respectively.
We would like to make $N$ coin tosses and get the maximal number of heads possible.
Unfortunately, we know $P_B$, but $P_A$ is unknown at the beginning of the process.

What is the best possible strategy for selecting which coin to toss at each step?

Note: I'm looking for actual optimization of the selection, not heuristic methods. You may assume a reasonable prior distribution on $P_A$ if needed.

EDIT:

Here is a formal definition of the objective.
Let $P_A,P_B\in (0,1)$ and $P=max\{P_A,P_B\}$. The optimal strategy in hindsight will achieve on average $P\cdot N$ head tosses.
Let $a(P_A,P_B)$ be the expected number of times our strategy picked coin $A$ given that the probabilities were $P_A,P_B$.

The Optimization Objective: minimize the expected regret, i.e. $$Regret=P\cdot N - P_A\cdot a(P_A,P_B) - P_B\cdot (N-a(P_A,P_B))$$

The Goal: Devise a selection strategy that guarantees (expected) $Regret\leq r$ for any values of $P_A,P_B$ (for the smallest value of $r$ possible).

Note that if $P_A\approx P_B$ this is not a problem in this definition as it means our regret will be small regardless of which coin we flip.

If $N$ is unknown (i.e. the process may end arbitrarily after an adversarialy chosen number of tosses), the best strategy would be to occasionally explore coin $A$ to get a better $\widehat {P_A}$ estimation, and in the rest of the time toss coin $A$ iff $\widehat {P_A} > P_B$.

In the scenario $N$ is known, it's not hard to argue that the optimal strategy makes a series of tosses of coin $A$ and then either keeps on tossing $A$ for the remaining tosses or starts tossing only coin $B$, but how can we optimize the cutoff (i.e. the switch to tossing coin $B$) to maximize the expectancy of head results?

I agree with D.W. that this should just be a dynamic programming question.
Assume that $P_B$ is known and that we have a prior on $P_A$ and that $N$ is known. (Without a prior on $P_A$ or a known $N$, I do not see how your objective or "optimal" are well-defined.)
Let optimal mean "maximizes expected number of heads" with the expectation over both the coin flips and the draw of $P_A$ from the prior. (This seems to me the only natural definition of (edit: achievable) "optimal" here.)

Let $Val(t,prior)$ be the expected number of heads of the optimal strategy starting at time $t$ with prior $prior$ on $P_A$. Then immediately
 $$ Val(N,prior) = \max\{ P_B, ~ \mathbb{E}P_A \} $$
since at the last step we should just choose the higher chance of flipping heads, and $\mathbb{E}P_A$ with respect to $prior$ is the probability of getting heads from flipping coin $A$. So we know how to choose the coin at the last step for any distribution on $P_A$.

At step $t < N$,
  $$ Val(t,prior) = \max\{ P_B + Val(t+1,prior), ~~ \text{val if flip $A$}\} $$
where
  $$ \text{val if flip $A$} ~~ = \mathbb{E}P_A ~~ + (\mathbb{E}P_A) Val(t+1,posterior(prior,heads)) ~~ + (1-\mathbb{E}P_A) Val(t+1,posterior(prior,tails)) . $$

Explanation: The value for flipping $B$ is $P_B$ for this coin flip, plus the value of the optimal strategy at time $t+1$ with the same prior on $P_A$ as we currently have. The value for flipping $A$ is the expected number of heads for this round, $\mathbb{E}P_A$, plus our expected value over the two possible cases. First, if the coin comes up heads (which happens with probability $\mathbb{E}P_A$), then we will update our prior to a posterior on $P_A$ conditioned on that event, and we will play the optimal strategy at time $t+1$ with that new distribution. Similarly if it comes up tails.

There are at the very most $O(n^3)$ cases to calculate because there are $N$ time steps, and at each time step $t$, we have a distribution on $P_A$ that consists of the original prior updated after observing $j=0,\dots,t$ heads and $k=0,\dots,t-j$ tails. But this should be reduced with your observation that we need only consider strategies that try $A$ for some amount of time, then (optionally) flip $B$ for the rest of the time.

Why this is optimal: Assume that the strategy is optimal at time $t+1$ for the specified prior distribution. But the "correct" prior distribution is always exactly the one we plug in to the formula: After observing a heads, the correct distribution over $P_A$ is precisely $posterior(prior,heads)$, and so on. When I say correct, what I mean is that the posterior gives the exact distribution over $P_A$ given that $P_A$ is drawn from the prior and these outcomes are observed. So we really are maximizing over the "average case" in each given scenario.


P and Descriptive Complexity In the Complexity Zoo, it says [1] that, in descriptive complexity, $P$ can be defined by three different kind of formulae, $FO(LFP)$ which is also $FO(n^{O(1)})$, and also as $SO(HORN)$.

However, there are some exceptions, for example, $Evenness$ can not be expressed by FP(FP has the same expressive power with LFP). $Connectivity$ and
$2-colourability$ are not definable by first-order logic. Some problems cannot even be axiomatized with a finite number of variables such as $Evenness$, $Perfect~Matching$, $Hamiltonicity$.

Immerman proposed that Fixed Point Logic + Counting(FPC) may be a possible logic for capturing P.

However, Cai Furer, Immerman showed that there are polynomial-time graph properties that are not expressible in FPC[2]. The problem of solving linear
equations over the two element field is not definable in infinitary logic with counting[3]. You may refer to [4] for more details.

So, what logic structure can capture P in general? The positive answer is that a class of ordered finite structures is definable in least fixed-point logic if, and only if, it is decidable in P by Immerman[5]and Vardi [6]. How about in the unordered case? Can you show more counterexamples of the statement in the complexity zoo?

Martin Grohe made substantial progress on this question recently. He gives a logic capturing polynomial time on classes of graphs embeddable in a fixed surface: https://dl.acm.org/citation.cfm?doid=2371656.2371662
Edit: the general case seems to be unresolved (but I am by no means an expert on this).


representing code path as graph walks.. a provable graph walk? I am looking into some security analysis of arbitrary code which is represented as a graph

Are there any papers on whcih graphs walks are valid code paths ?
Or a provable graph walk which is shorter than a graph walk itself ?

Can anyone direct to any specific terms or papers i should be looking into ?

This paper matches some of your criteria:

Nenad Dedic, Mariusz H. Jakubowski, Ramarathnam Venkatesan: A Graph Game Model for Software Tamper Protection. Information Hiding 2007: 80-95

It uses random walks on the flow graph of a program to make the program more tamper resistant.


Something-Treewidth Property Let $s$ be a graph parameter (ex. diameter, domination number, etc)

A family $\mathcal{F}$ of graphs has the $s$-treewidth property if there is a function $f$ such that for any graph
$G\in \mathcal{F}$, the treewidth of $G$ is at most $f(s)$.

For instance, let $s = \mathit{diameter}$, and $\mathcal{F}$ be the family of planar graphs. Then it is known that any planar graph of diameter at most $s$ has treewidth at most $O(s)$.
More generally, Eppstein showed that a family of graphs has the diameter-treewidth property if and only if it excludes some apex graph as a minor.
Examples of such families are graphs of constant genus, etc.

As another example, let $s = \mathit{domination{-}number}$. Fomin and Thilikos have proved an analog result to Eppstein's by showing that a family of graphs has the domination-number-treewidth property
if and only if $\mathcal{F}$ has local-treewidth. Note that this happens if and only if $\mathcal{F}$ has the diameter-treewidth property.

Questions:

For which graph parameters $s$ is the $s$-treewidth property known to hold on planar graphs?
For which graph parameters $s$ is the $s$-treewidth property known to hold on graphs of bounded local-treewidth?
Are there any other families of graphs, not comparable to graphs of bounded local-treewidth for which the $s$-treewidth property holds for some suitable parameter $s$?

I have a feeling that these questions have some relation with the theory of bidimensionality. Within this theory,
there are several important parameters. For instance, the sizes of feedback vertex set, vertex cover,
minimum maximal matching, face cover, dominating set, edge dominating set,
R-dominating set, connected dominating set, connected edge dominating set,
connected R-dominating set, etc.

Does any parameter $s$ encountered in bidimensionality theory have the $s$-treewidth property for some suitable family of graphs?

For question $1$: any bidimensional parameter has this property on general graphs. A parameter $s(G)$ is bidimensional if the value of $s(G) \geq s(H)$ for every minor $H$ of $G$, and if $s$ is ``large'' on grids.
In applications to PTASes, sub exponential algorithms and kernels on minor-free classes of graphs, "large" means that there exists a constant $c$, such that the value of $s$ on a $t$ times $t$ grid is at least $ct^2$. This is what you most likely will find if you do a google search for ``bidimensionality''
However, for your question it is sufficient that $s$ grows to infinity on $t$ times $t$ grids as $t$ grows to infinity. This is because any graph with large enough treewidth will contain a large enough grid minor. So, to conclude, if $s$:

is closed under minors
is arbitrarily large on $t$ times $t$ grids for large enough $t$

Then s has the s-treewidth property. See the recent parameterized complexity book ( http://parameterized-algorithms.mimuw.edu.pl ) in the treewidth chapter for more info.


Theoretical Applications for Approximation Algorithms Lately I've started looking into approximation algorithms for NP-hard problems and I was wondering about the theoretical reasons for studying them. (The question is not meant to be inflammatory - I'm merely curious).

Some truly beautiful theory has come out of the study of approximation algorithms - the connection between the PCP theorem and hardness of approximation, the UGC conjecture, the Goeman-Williamson approximation algorithm, etc.

I was wondering though about the point of studying approximation algorithms for problems like Traveling Salesman, Asymmetric Traveling Salesman and other variants, various problems in mechanism design (for instance in combinatorial auctions), etc.
Have such approximation algorithms been useful in other parts of theory in the past or are they studied purely for their own sake?

Note: I'm not asking about any practical applications since as far as I know, in the real world, it's mostly heuristics that are applied rather than approximation algorithms and the heuristics are rarely informed by any insight gained by studying the approximation algorithms for the problem.

I strongly disagree with the last paragraph. Blanket statements like that are not useful. If you look at papers in many systems areas such as networking, databases, AI and so on you will see that plenty of approximation algorithms are used in practice. There are some problems for which one desires very accurate answers; for example say an airline interesting in optimizing its fleet scheduling. In such cases people use various heuristics that take substantial computational time but get better results than a generic approximation algorithm can give.

Now for some theoretical reasons for studying approximation algorithms. First, what explains the fact that knapsack is very easy in practice while graph coloring is quite hard? Both are NP-Hard and poly-time reducible to each other. Second, by studying approximation algorithms for special cases of a problem one can pin-point what classes of instances are likely to be easy or hard. For example we know that many problems admit a PTAS in planar and minor-free graphs while they are much harder in arbitrary general graphs. The idea of approximation pervades modern algorithm design. For example, people use data streaming algorithms and without the approximation lens is hard to understand/design algorithms because even simple problems cannot be solved exactly.


How many samples are needed to reconstruct a path? Consider an input set of vertices $V$ and vertices $s,t\in V$.
The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be multiple shortest paths.

At each iteration, each vertex is randomly colored using $0$ or $1$.
We then get a single bit, that is $1$ with a probability proportional to the number of $1$-vertices along the path.
That is, if $6$ of the vertices along the path were colored with $1$ and $4$ were zero, then the bit will be $1$ w.p. 3/5.

Importantly, we get to know the coloring of every iteration, and the goal path does not change.

  How many samples do we need until we can compute the path with, say, probability 2/3?

A very simplistic approach would be to eliminate all monochromatic paths whose color is different than the given bit (e.g., a $1$-path can be eliminated if we get a $0$-bit). This seems to give a very weak bound.

Here’s a simple idea: try a certain number $s$ of samples, and for each vertex, record how many times its colour agreed with the provided bit.

For vertices outside the path, they agree with probability $1/2$ on each iteration, while for vertices on the path, the probability is $1/2+1/2k$, where $k$ is the number of vertices on the path.

Thus, if $s\approx k^2\log n$, the Chernoff–Hoeffding inequality ensures that with probability at least $2/3$, all vertices outside the path agree for less than $s(1/2+1/4k)$ samples, and all vertices on the path agree for more than $s(1/2+1/4k)$ samples, which lets you pinpoint the path. If you don’t know $k$ in advance, you can just bound it by $n$.


Does NP-completeness/hardness have to be constructive? Is there any $L\in {\bf NP}$ with the following properties:

It is known that $L\in {\bf P}$ implies ${\bf P}={\bf NP}$.
There is no (known) polynomial time Turing reduction of $SAT$ (or some other ${\bf NP}$-complete problem) to $L$.

In other words, if a polynomial time algorithm for $L$ implies the collapse of ${\bf NP}$ into ${\bf P}$, then  is it necessary that this "general hardness" of $L$ for ${\bf NP}$ must be somehow $constructive$, in the sense that, say, $SAT$ must be reducible to $L$ via some specific reduction?

Yes, there are such sets, take any $\mathsf{NP}$-intermediate set (any set that is provably $\mathsf{NP}$-intermediate assuming $\mathsf{P}\neq\mathsf{NP}$), e.g. construct one from SAT using Ladner's theorem.

Note that your $L$ needs to considered an $\mathsf{NP}$-intermediate problem, since it is in $\mathsf{NP}$ but not complete for it. Note also that you are assuming that $\mathsf{P}\neq\mathsf{NP}$ otherwise there is no such $L$ as every non-trivial problem would be complete for $\mathsf{NP}$ if $\mathsf{NP}=\mathsf{P}$. Additionally the conditions that you have given does not imply to completeness so the question in the first part is not the same as the question about constructiveness of completeness.

Regarding the question in the title, i.e. "does $\mathsf{NP}$-hardness have to be constructive?".

The answer depends on what we mean by "constructive". Classically, a decision problem $A$ is defined to be $\mathsf{NP}$-hard iff

$$\forall B\in \mathsf{NP} \ B \leq^\mathsf{P}_m A$$

which means

$$\forall B\in \mathsf{NP} \ \exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in B \leftrightarrow f(x)\in A)$$

And by Cook's theorem this is equivalent to

$$ SAT \leq^\mathsf{P}_m A$$

which means

$$\exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in SAT \leftrightarrow f(x)\in A)$$

How can we make this definition constructive? It is already seems very constructive to me.
I guess what you want to ask is if we can prove this for some $A$ without knowing what is $f$ explicitly. I don't remember seeing any such hardness proof.

Classically even when we don't have a specific function there is a function, saying that it is impossible that no function is a reduction is equivalent to saying that some function is a reduction. To talk about constructiveness we need to be more considerate. For example we can talk about statements which are provable classically but not constructively (e.g. intuitionism where different state of mathematical knowledge makes sense, Google for "ideal mathematician" or check this).

Intuitively it seems plausible to me that we can prove such a statement using a proof by contradiction and without giving any explicit reduction function. But it won't mean that there is no constructive proof of the statement. To be say more that no constructive proof exists we have to be more specific: proofs in which theory/system? what do we mean by a constructive proof?


Order of drawing colored balls from a bag We're looking for an upper bound on (or a method to compute) probabilities of the following type:  Suppose I put 12 yellow balls, 18 red balls, 7 white balls, and 2 green balls in a bag.  Then I start withdrawing random balls one by one. What is the probability that I draw at least one red ball and at least one yellow ball before I draw the first green ball?

More generally, I have a set $A$ of $m$ colors, a set $B \subset A$ of colors, a color $c \in A \setminus B$ and a set of $n$ balls with colors from $A$ where the number of balls of each color is known. Whats the probability that I draw at least one ball of each color in $B$ before I draw a ball of color $c$?

Peter Shor points out that this is related to the coupon collector's problem (thanks!), the main difference being that we want to know the probability of a particular color being last (not the number of steps required to collect every coupon).  The literature we've searched on the coupon collector's problem (in the last few hours) doesn't seem to address this question.  (A minor difference is that we're sampling without replacement, though a solution for sampling with replacement would be welcome too.)  Ideally we'd like a closed-form upper bound (an asymptotic upper bound would probably do), but a polynomial-time algorithm to compute an upper bound would be useful too.

We seek this bound to help us analyze a randomized geometric algorithm.

First observation: the cases with and without replacement have exactly the same answer. (Once you have drawn a red ball, say, you don't care about future draws of red balls: all you care about now is the relative order of future green and yellow balls).

A good way to attack the case with replacement is by embedding in continuous time.

Imagine that the balls arrive according to independent Poisson processes with appropriate rates: rate 12 for yellow balls, rate 18 for red balls, rate 2 for green balls. Then whenever a ball arrives, it has probability 12/32 of being yellow, 18/32 of being red and 2/32 of being green, as desired - I'm ignoring the white balls since they're irrevelant. So the sequence of colours observed is exactly as it would be from a sequence of independent draws with replacement.

Now you want to know the following: does the first event in the green process occur after the first events in the yellow and red processes? This is easy enough to calculate, since the first event in a Poisson process of rate $r$ has exponential distribution with rate $r$, and the three processes are independent.

So, integrating over the time of the first event in the green process, you get the following expression for your probability:

$\int_0^\infty 2e^{-2x} (1-e^{-12x})(1-e^{-18x})dx$

which is straightforward to evaluate and generalises nicely.


Inexact labelled binary tree matching Does anyone recognise the following problems? Do they have names? Are they hard?
If we were looking for an exact match (0 mismatches), these would be solvable in polynomial time (using e.g. standard algorithms for rooted tree isomorphism). But what about the inexact case?
Variant 1
Input:

A rooted perfect full binary tree $T$ with $2^k-1$ nodes; let $V$ be the set of nodes.
Functions $x\colon V\to \{0,1\}$ and $y\colon V\to \{0,1\}$.

Output:

Automorphism $f\colon V \to V$ of tree $T$ that minimises the number of nodes $v \in V$ with $x(v) \ne y(f(v))$ — these are called mismatches.

Put otherwise, the task is to find a labelling $x'$ such that $x'$ is as close to $x$ as possible (minimise the number of elements that differ) and the labelled trees $(T,x')$ and $(T,y)$ are isomorphic.
Variant 2
The same as above, but only leaf nodes can have non-zero labels.

I think that the problem is not hard, because if I understood the problem statement correctly, it can be solved in $O(|V|^2)$ time as follows:

We have two $0$-$1$-labeled rooted perfect full binary trees $(A, x)$ and $(B, y)$ with $2^k-1$ nodes. We compute the minimum number of mismatches in any isomorphism between the trees denoted by $F(A, B)$ recursively by using the $F$-values of the subtrees. We have essentially two options when choosing the isomorphism: either we swap the child subtrees of the root in one of the trees or we do not swap anything. Therefore
$F(X, Y)$ is obtained as a minimum of $F(X_{\text{left}}, Y_{\text{left}}) + F(X_{\text{right}}, Y_{\text{right}})$ and $F(X_{\text{left}}, Y_{\text{right}}) + F(X_{\text{right}}, Y_{\text{left}})$, increased by one if the $x$-label of the root of $X$ and the $y$-label of the root of $Y$ are distinct. If we use dynamic programming to optimize this recursion, we have to compute $F(X, Y)$ only once for every pair of subtrees $X$ and $Y$ of the original tree with equal heights.


SODA '15 Page Limits The SODA '15 submission rules state that "The submission, excluding title page, bibliography and appendix, must not exceed 10 pages."

However, the website does not define "title page." Does "title page" simply mean "the page with the title and abstract," or does it mean some sort of cover page?

I emailed the PC and received the following answer:

  "Title  page" means a page that contains only the title and abstract.


Examples of Universe inconsistency in normal use of dependent types In dependent types, Type : Type results in inconsistency (Girard's or Hurken's paradox).

Are there examples of universe inconsistency (where assuming Type : Type would result something that is false) showing up "accidentally" when not deliberately trying to prove it (when proving unrelated things)?

This is a hard question to answer, in part because it's unclear what it means to get something "by accident". Regularly, though, people run into the Universe Inconsistency error of Coq, as some quick googling will show (e.g. here). This certainly sometimes happens by accident, sometimes in the attempt at showing inconsistencies or testing the limits of the prover.

One of the big sources of universe inconsistencies unsurprisingly comes from trying to formalize category theory in Coq, as is mentioned in this article by Gross, Chlipala and Spivak.

In most cases, it's hard to tell whether the inconsistency comes from an actually inconsistent statement, or just a limitation of the proof checker, which sometimes has counter-intuitive restrictions on universes, particularly in the allowed parameters for inductive types. This is actually a somewhat tricky subject (see the official definition and Chlipala's more accessible discussion).


Resolution vs Extended Resolution Let $R(f)$ and $ER(f)$ be the minimum-size for unsat proofs of $f$ in Resolution and Extended Resolution respectively. What's the best bound we have on $D=\min_f (R(f)-ER(f))$ where $f$ belongs to a worst-case family of boolean formulae? Since no superpolynomial lower bounds are known on Extended Resolution, we don't have a good upper bound on $D$, so I'm interested in lower bounds on $D$.

Edit: Clarified question as per Kaveh's answer below

Your definition of $D$ is not clear, if it is $D = \max_f (R(f) - ER(f))$, then it is exponential.

There are DNFs whose shortest proofs in ER is exponentially shorter than their shortest proofs in R e.g. PHP (pigeon hole principle) has polynomial size ER-proofs but only exponential size R-proofs.

Unsatisfiability of $f$ is the same as $\lnot f$ being a tautology. Let $\lnot f$ be as PHP. Then $R(f)$ is exponential where as $ER(f)$ is polynomial, so the difference is exponential. Also it cannot be more than exponential.

Addendum:

If $D =  \min_f (R(f) - ER(f))$ then it is 0. Take $\lnot f=\top$ and it has one line proof in both. (R is included in ER so it cannot be less than 0.)


How much independence is required for separate chaining? If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In "The Power of Simple Tabulation Hashing", Pătraşcu and Thorup mention that "Chernoff-Hoeffding bounds for applications with limited independence" (mirror) shows that this bound on the population of the heaviest loaded bin also holds if the balls are distributed by an $\Omega(\lg n/\lg \lg n)$-independent hash function.

In "Balls and Bins: Smaller Hash Families and Faster Evaluation", Celis et al. note that it is not known if there is a family of hash functions where

Hash functions can be represented with $O(\lg n)$ bits of space
Hash functions can be evaluated in $O(1)$ time
The maximal load is $O(\lg n / \lg \lg n)$ with high probability.

If there is a constant $k$ such that any $k$-independent family suffices for #3, then it the polynomial construction of $k$-independent families would meet #1 and #2.

What bound do we have for the heaviest loaded bin with $k$-independent hashing?

Using Theorem 4.III of "Chernoff-Hoeffding bounds ..." and the union bound, I think I can get a bound of $O(n^{2/k})$ on the weight of the heaviest loaded bin w.h.p.

Can this be brought down to $O(\lg ^c n)$ using other techniques?

Apparently not. "Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence", by  Mathias Bæk Tejs Knudsen and Morten Stöckel shows "a $k$-independent family of functions that imply [heaviest loaded bin] size $\Omega(n^{1/k})$".


programming language with type-level functions Is there any programming language out there that allows the same set of tools it offers, to be used at the type level as well? I know, Haskell and some other ML family languages allow parametric types but those are usually very limited and have a very adhoc syntax to define a new type.

To clarify, imagine the following pseudo code:

person = { name: 'jon', lastName: 'doe', age: 600 }
assoc = (k, v, obj) =>
   returns { name: 'jon', lastName: 'doe', age: 600, k: v }

assoc('color', 'red', person)
   // evaluates to { name: 'jon', lastName: 'doe', age: 600, color: 'red' }

So this is at the value-level. But I'm looking for a language that allows me to do the same thing at the type level:

type Person = { name: String, lastName: String, age: Int }
type Color = Red | Yellow

assoc = (k, v, type) =>
   returns a new type { name: String, lastName: String, age: Int, k: v }

assoc(color, Color, Person)
   // evaluates to { name: String, lastName: String, age: Int, color: Color }

You get the point, right? Basically, things that the PL allows you to do on values can be done on the types as well. It treats types as values, if you will.

Yes, and this is much, much more common than you may have thought. You can do meaningful (and actually Turing-complete!) type-level computation in C++ (see this post by Matt Might for example). Haskell allows type-level partial functions by way of type families, etc.

Of course, the system that fits your description best is probably dependent typing, which unify types and terms, i.e. there is no differentiation between type-level and value-level computation in a dependently-typed language. There are a myriad dependent type systems (Calculus of Constructions, Martin-Lof type theory, Zhaohui Luo's UTT, etc.), and also plenty of dependently-typed programming languages (Coq, Agda, Idris, you name it).

So, I doubt this question is anywhere near research-level. But the answer to your question is, yes, there are such languages, and a lot, and the theory of such languages is already fairly well-researched. For a reference on dependent types, you might want to consult Chapter 2 of Advanced Topics in Types and Programming Languages (ATTAPL), or Software Foundations by Benjamin Pierce et al., and Type-Driven Development with Idris by Edwin Brady if you're more inclined to work with code.


Cover time and spectral gap for reversible random walks I am looking for a theorem which say something like this: if the cover time of a reversible Markov chain is small, then the spectral gap is large. Here the spectral gap means $1-|\lambda_2|$, that is, we ignore the smallest eigenvalue of the chain.

The only result I was able to find in this direction is from Bounds on the Cover Time, Broder and Karlin, FOCS 88. There it is assumed that the transition matrix of the chain is doubly stochastic (but not necessarily reversible) and aperiodic; roughly speaking, the paper shows that under these assumptions if the cover time is $O(n \log n)$, then $1-\max(|\lambda_2|, |\lambda_n|)$ is at least $n^{-1}$.

Intuitively, it seems very plausible that if you can cover all the vertices of a graph quickly, then mixing time ought to be small. In particular, if you can cover all the vertices of a graph in $n^2$ time, surely you should be able to rule out a spectral gap of, say, $n^{-1000}$?

One possible obstacle that would break the implication between small cover time and large spectral gap is bipartiteness: on a bipartite graph, you can have a small cover time with an eigenvalue of $-1$. By in my question, I am bypassing this issue by ignoring the smallest eigenvalue.

Roughly speaking, the mixing time is the worst-case hitting time of the half the vertices.  Cover time is a stopping time when ALL subsets of vertices are hit.  In other words, it is always larger than the the mixing time.  Thus is your example one cannot have mixing time $n^{1000}$ and cover time $n^2$.

Making this intuition precise requires a bit of care since we need to relate mixing times to eigenvalue gap, take not half the vertices but half the stationary distribution $\pi$, etc.  None of this is difficult.  Start with this paper by Lovasz and Winkler, which gives the above version of the mixing time and relates it to more standard mixing time in total variation.


References on generalization bounds I'm looking for references (books, papers, lecture notes etc) on generalization bounds and their proofs. Specifically, I'm looking to fully understand the technique of defining a hypothesis class (or distribution) and using a concentration inequality to obtain a generalization bound.

What are the standard references for such techniques?

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

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

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

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


Implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model What are implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model to $\mathsf{Turing}$ model and $\mathsf{Valiant's}$ counting complexity model?

In opposite direction what are implications of $\mathsf{P}=\mathsf{NP}$ in $\mathsf{BSS}$ model to $\mathsf{Turing}$ model and $\mathsf{Valiant's}$ counting complexity model?

$\newcommand\Ptime{\mathsf P} \newcommand\NP{\mathsf{NP}} \newcommand\poly{\mathsf{poly}}$
It is known that $\Ptime/\poly \neq \NP/\poly \implies \Ptime_{\mathbb C}\neq \NP_\mathbb{C}$ [1] where the latter two represent the classes $\Ptime$ and $\NP$ in the BSS model over the complex numbers. (You can take the contrapositive to obtain a consequence of $\Ptime_\mathbb C = \NP_\mathbb C$.)
To the best of my knowledge, this is the only known result, though results of the same kind are known for other classes (in particular in Koiran's weak model).

For more on this, look at Chapter 1 (in particular Fig. 1.1) and Chapter 8 of Bürgisser's book [2].

[1] F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther. On real
Turing machines that toss coins. In Proc. 27th ACM STOC, Las Vegas,
pages 335–342, 1995.
[2] Peter Bürgisser. Completeness and reductions in algebraic complexity theory, 1998.


Complexity of the recovery of an adjacency matrix from its square I am interested in the following problem:  Given an $n\times n$ matrix, is there an undirected graph on $n$ vertices whose adjacency matrix squared is that matrix?

Is the computational complexity of this problem known?

Remarks:

Of course this can also be phrased as a search problem, where you are given the matrix $A^2$ for $A$ an adjacency matrix of an undirected graph and the problem is to find any adjacency matrix (of an undirected graph) $B$ such that $B^2 = A^2$.
Motwani and Sudan (Computing roots of graphs is hard, 1994) and
Kutz (The complexity of Boolean matrix root computation, 2004) show similar but distinct problems from this one are NP-hard - they consider only the square of adjacency matrices under Boolean matrix multiplication.

It is known that squares of bipartite graphs can be recognized in polynomial time ( See this). In general, there is a characterization of the complexity of this problem based on the girth of the underlying graph.

Recently there was a optimization variant studied, which gives FPT algorithms for the problem when you want to test whether a graph has a square root with at most (respectively at least) $s$ edges for some given integer $s$.


Do there exists polynomial size CFG that describe this finite language? Do there exists permutations $\pi_1,\pi_2$ and polynomial size (in $|w|=n$) context free grammar that describe the finite language $\{w \pi_1(w) \pi_2(w)\}$ over alphabet $\{0,1\}$?

UPDATE: For one permutation $\pi$ it is possible. $\pi$ is the reversal or relatively minor modification of the reversal.

Chomsky normal form

A CFG is in CNF (Chomsky normal form) if the only productions are of the form $A \rightarrow a$ and $A \rightarrow BC$; a grammar can be brought to CNF with only quadratic blowup.

For a grammar $G$ in CNF, we have the nice Subword Lemma:  If $G$ generates a word $w$, then for each $\ell \leq w$, there is a subword $x$ of $w$ of length $\ell/2 \leq |x| < \ell$ which is generated by some non-terminal of $G$. Proof: Descend the (binary) syntax tree, always going to the child which generates the longer subword. If you started with a subword of size at least $\ell$, you can't have gone below $\ell/2$.

 Solution

Without loss of generality, we can assume that a grammar for $L_n$ (such a language with specific $\pi_1,\pi_2 \in S_n$) is in Chomsky Normal Form. The language $L_n$ consists of the words $w(x) = x\pi_1(x)\pi_2(x)$ for all $x \in \{0,1\}^n$.

Using the Subword Lemma, for each $w(x)$ we can find a substring $s(x)$ of length $$\frac{n}{2} \leq |s(x)| < n$$ generated by some symbol $A(x)$ and occurring at position $p(x)$.

Suppose that $p(x) = p(y)$ and $A(x) = A(y)$. Since $|s(x)|<n$, the subword $s(x)$ cannot intersect both the $x$ part and the $\pi_2(x)$ part of $w(x)$; we can assume it is disjoint from the $x$ part. Thus $w(x)$ is of the form $x \alpha s(x) \beta$. This implies that $A(x)$ generates exactly one string, namely $s(x)$. Therefore $s(x) = s(y)$.

Now $s(y)$ intersects either $\pi_1(y)$ or $\pi_2(y)$ in at least $n/4$ places, and thus determines at least $n/4$ bits of $y$. Therefore at most $2^{3n/4}$ strings $y \in \{0,1\}^n$ can have $p(x) = p(y)$ and $A(x) = A(y)$. Since there are at most $3n$ possibilities for $p(y)$, we get that there are at least $$\frac{2^{n/4}}{3n}$$ different non-terminals in the grammar.

Comment: The same proof works if $\pi_1,\pi_2 \in S_{\{0,1\}^n}$, i.e. are arbitrary permutations on the set of all $n$-bit words. Given $n/4$ bits of $\pi_i(y)$, there are exactly $2^{3n/4}$ preimages $y$.

 More examples

Using the same method, one can prove that the language where each character appears exactly twice requires exponential-size CFG in the size of the alphabet. We can replace "twice" with any subset of $\mathbb{N}$ other than four trivial ones (ignoring $0$, either containing none of $\mathbb{N}_{\geq 1}$ or all of it).

I would appreciate a reference for this proof method.


Complexity of acyclicity of a "nondeterministic" graph By "nondeterministic" I mean the graph is a collection of sets of "candidate" edges sharing a single destination: $E \subseteq 2^V \times V$. The problem is whether it is possible to pick one edge from each candidate set, so that the picked edges form an acyclic graph.
When the candidate sets are all singletons, the graph is then deterministic and the problem is of course linear. The general case seems sufficiently complicated to be NP hard, but I couldn't prove it, nor did I find any related literature.
Does anyone know whether this problem has already been investigated? Is it NP hard?
Thanks!

The strategy I outlined in the comment worked: reading through Bodirsky and Kara's paper, the first solvable case they consider is the case of min-closed languages, and your problem happens to fall into this category.
The algorithm they suggest is quite simple (in hindsight): look for a vertex $v_0$ which is never the target of any edge, and if you find one, force every candidate edge that could begin at the vertex $v_0$ to begin there. If no such $v_0$ exists, then there is no solution.


State of the Art for the Monadic Class? Monadic First Order Logic, also known as the Monadic Class of the Decision Problem, is where all predicates take one argument. It was shown to be decidable by Ackermann, and is NEXPTIME-complete.

However, problems like SAT and SMT have fast algorithms for solving them, despite the theoretical bounds.

I'm wondering, is there research analogous to SAT/SMT for monadic first order logic? What is the "state of the art" in this case, and are there algorithms which are efficient in practice, despite hitting the theoretical limits in the worst case?

I found signs that such a decision procedure was implemented in the (general purpose) theorem prover SPASS.

In particular see the thesis of Ann-Christin Knoll, On Resolution
Decision Procedures
for the Monadic Fragment and Guarded Negation
Fragment. This implements what you want, though I couldn't find the implementation online.


Midpoint solutions to linear programs There is a linear program for which I want not merely a solution but a solution that's as central as possible on the face of the polytope that assumes the minimal value.

A priori, we expect the minimizing face should be high dimensional for various reasons, including that the objective function being minimized is the maximum of many of the constraints :

Minimize $\epsilon$ subject to $f_i(\bar x) \leq \epsilon < 0$ with $f_i$ linear and $x_i > 0$ for all $i$ and $\sum_i x_i = 1$.

We'd never obtain any centrality-like property form the simplex algorithm of course.  Do any of the usual interior point algorithms exhibit such properties though?  Do any even guarantee they'll avoid vertices or lower dimensional faces whenever possible?

In fact, I'm probably content with a easy quadratic program that finds the midpoint of the entire polytope since centrality matters more than minimality, just vaguely curious if other linear programming algorithms offer relevant properties.

Update : I've reduced the underlying problem to a simple constrained minimization problem solvable with Lagrange multipliers, but the question above remains interesting anyways.

First find the optimal solution, then add the linear constraint that the solution must have value equal to the optimal you want, and restate your LP as the one looking for the largest ball inside the feasible region. Solve this modiefied LP, and you have what you want.

Why the second problem can be solved using LP is a stnadard cute problem in Computational Geometry...

==============

More formally, you find the affine subspace spanning the feasible points containing the optimal solution. So, assume that the optimal solution lies on the hyperplane $h \equiv cx = \alpha$ (i.e., $\min c x$ was the original LP target function). If $P$ is the feasible region of the original LP, we are looking for the largest ball in $P \cap h$. To this end, we need to compute the smallest dimensional affine subspace containing this set. Once you found this subspace, change variables so that you consider only this affine subapce. Now, your polytope is full dimenisonal, and you can use the second LP as I described above.

So, let $v$ be the vertex computed by the first LP.
Considering all the neighboring vertices to $v$. Consider the affine subspace of $v$ together with all its neighbors that have the same target value (i.e., $\alpha$). It is not hard to see, that this affine subspace is the desired subspace.

So, to summerize:
(A) solve LP to discover optimal value.
(B) Compute the smallest dimensional subspace containing the feasible solution with the optimal value.
(C) Rewrite the original LP in this affine subpsace (i.e., dropping all the irrelevant dimensions), add a variable, and turn it into an LP for finding the largest ball inside this polytope.


Exercises of polynomial and turing reductions I'm following a graduated course in theoretical computer sicence. A good part the theory we see in this course has to do with polynomial and Turing reductions of NP problem (to prove NP-completeness), mostly including gadgets. However the course has very few exercises to practice ourselves and the teacher is reluctant to give us some more. Is there any resources, web or books, that could fill this gap for me? I'm talking about problems and possibly their solutions and some explanation about the process of finding the reduction.

Thanks.

A good start is Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. Chapter 3.2 discusses techniques and 3.3 has exercises. You can find more in the books about complexity everyone should read.


Squash type vs Propositional truncation type Homotopy type theory has a notion of propositional truncation type. It seems to me that it's strongly related to a notion of squash types. (See https://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ttfp.pdf p. 265). It seems that squash types have serious problems with definitions (see the book), and prop. trunc don't. Why this is so? What are these problems? (The book mentions them, but I can't  understand well what they are, they have an example for subtypes but, AFAIU it doesn't apply to squash types).

Squash types correspond to judgmental truncation, not propositional truncation.  In a type theory without a type for judgmental equality, there's non much of a way to make use of an inhabitant of a squash type; there's no way to write an eliminator into any type except another squash type.  Relatedly, having squash types, as presented in the book you linked, makes typechecking undecidable; having propositional truncation types does not result in this drawback.

Why do squash types result in undecidable typechecking?  Quoting the book you linked:

  The first approach to representing the proposition is to consider the ‘squash’
  type, defined in [C+86a] to be

  $\|A\| ≡_{df} \{ t : \top\ \mid\ A \}$

  which will be inhabited by the object $Triv$ if and only if there is some proof
  object $a : A$.

Now let $A$ be your favorite undecidable problem, and ask your typechecker to decide if $Triv$ has type $\|A\|$.  By construction, it can't decide your problem, and thus can't typecheck $Triv : \|A\|$.

Note that this problem is specific to squash types with canonically named inhabitants.  Agda has a form of judgmental truncation, which goes by the name "irrelevant arguments" or "irrelevant fields", without canonically named inhabitants.  Agda maintains decidable typechecking, though I think it doesn't manage to throw away the proofs, and has to carry them around (perhaps only for technical implementation reasons).  (This would be something to ask about on the Agda mailing list.)  These suffer the drawback, mentioned above, of not being able to eliminate into any non-irrelevant types.


A special case of the boolean multivariate quadratic polynomial problem It's well known that in the general case, the boolean MQ problem:

given $(f_1, \ldots, f_n) \in \mathbb{F}_2[x_1, \ldots, x_m]$ with $\deg(f_i) = 2$, can we find a solution $\vec{y}: f_i(\vec{y}) = 0$,

is NP-hard.  I was wondering if there was an efficient algorithm for the special case in which each $f_i$ is the product of linear functions?

This case is still NP-hard. Suppose we have an instance of 3-SAT:

$F=C_1\wedge\ldots\wedge C_n; C_i=L_{i,1}\vee L_{i,2}\vee L_{i,3}$,

where each literal $L_{i,j}$ is either $V$ or $\neg V$ for some boolean variable $V\in Var$. We can translate this into an equivalent system of equations $f_{i,j}=0$ for $i=1,\dots,n$ and $1\le j\le 4$, where each $f_{i,j}$ is a product of two linear factors, as follows.

Introduce a variable $V'$ for each $V\in Var$, variables $c_i,d_i$ for each clause $C_i$, and an auxiliary variable $z$. For all $i$ and each $1\le j\le 3$, let $t_{i,j}$ be $V'$ if $L_{i,j}=V$, and $(1-V')$ if $L_{i,j}=\neg V$. Then the fact that clause $C_i$ is supposed to be satisfied by a valuation of $Var$ can be split into the conditions:

$(1-c_i)z = (1-c_i)(1-z) = 0$, forcing the value of $c_i$ to be $1$;
$(c_i-d_i)(c_i-t_{i,1}) = 0$, forcing $c_i$ to equal $d_i$ or $t_{i,1}$; and
$(d_i-t_{i,2})(d_i-t_{i,3})=0$, forcing $d_i$ to equal $t_{i,2}$ or $t_{i,3}$.

Together these force at least one of the $t_{i,j}$ to be $1$, corresponding to one of the $L_{i,j}$ being true. Combining these for all $i$ gives a system of equations equivalent to $F$.


Pi-calculus (or session types) - proof for weakening lemma I'm writing a thesis about session types and am currently writing a section concerning type soundness for the system. I started to proof weakening lemma, which states, that
$$
\text{If } \Gamma \vdash P, \text{ then } \Gamma, x:T \vdash P.
$$
That is, names not free in a process can be added to the typing environment. However, I can't understand how to find a derivation for
$$
\Gamma, x:T \vdash (\upsilon x)P
$$
The rule T-RES for restriction is
$$
\frac
{
  \Gamma, x:T \vdash P
}
{
  \Gamma \vdash (\upsilon x)P
}
$$
I tried to find a proof for the lemma (for session types, pi-calculus or other calculi), but all the proofs seemed to be something like "a straightforward induction on the derivation of $\Gamma \vdash P$".
I'm trying to understand, what I'm misunderstanding or missing. The rule T-PAR explicitly states, that $x$ is not in the environment in $\Gamma \vdash (\upsilon x)P$. However, the lemma states, that $\Gamma, x:T \vdash (\upsilon x)P$ is valid.

You should $\alpha$-rename to avoid conflict with the variable names. That is, you should prove weakening of the form: $\Gamma \vdash (\upsilon y) P$ implies $\Gamma, x : T \vdash (\upsilon y) P$.
$\alpha$-equivalence and capture-avoiding substitution is an important concept to understand in type theory: I would recommend studying this concept for the untyped or simply-typed $\lambda$-calculus to begin with, before trying to prove things about a more complicated calculus.


Linear circuit complexity classes The class $\textrm{NC}^i$ is the class functions computable by circuits families of bounded fan-in, $n^{O(1)}$ size and $O(\log^i(n))$ depth.
The $\textrm{NC}$-hierarchy is the union of those classes.

Is there any study of the linear-size variant of this hierarchy? That is circuits families of bounded fan-in, polylog depth and linear size?

I know their exists some work with linear-$\textrm{AC}^0$ but nothing else. Remark that at least linear-$\textrm{NC}^1$ is nontrivial since it contains regular languages (and thus some $\textrm{NC}^1$-complete languages).

It follows from work of Valiant [1, 2] that linear-size $\textrm{NC}^1$ can be simulated by $2^{O(n / \log \log n)}$-size circuits of depth three and unbounded fan-in.

For a nice exposition of this result, see section 3 of the survey by Viola [3].

[1] Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In: Mathematical Foundations of Computer Science 1977. MFCS 1977. Lecture Notes in Computer Science, vol 53. Springer, Berlin, Heidelberg.

[2] Leslie G. Valiant. Exponential lower bounds for restricted monotone circuits. In: Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC '83). ACM, New York, NY, USA, 110-117.

[3] Emanuele Viola. On the power of small-depth computation
. Foundations and Trends in Theoretical Computer Science, vol. 5, num. 1, pp. 1--72, 2009.


Finding appropriate spanning tree of connected bipartite graph I got this as a sub-problem while working on a research problem connected to index coding. Can someone please give me directions as to how to approach this problem?

Problem: We have a connected undirected bipartite graph $G=(U,V,E)$. Let $|U| = m$ and the degree of $i$th node in U be $a_i$. Consider a spanning tree of $G$ and let the degree of $i$th node in $U$ be $b_i$ in the spanning tree (so $b_i \le a_i$). I am interested in finding the spanning tree that minimizes $max_{i=1,2,...,m} (a_i-b_i)$. I am interested in getting directions about how to design an algorithm for it.

Isn't this a special case of matroid intersection,
which is solvable in polynomial time?

Fix your graph $G$ and any integer $d \in \{0,1,\ldots,\max_i a_i\}$.
You want to maximize $d$; you can try all possibilities.
For a given $d$, you want to answer the following question:

  Is there is a spanning tree $T$ such that $\max_i a_i - \mbox{deg}_T(u_i) \le d$?

Since any spanning tree has $n-1$ edges, the following question is equivalent:

  Is there an edge-set $S$ of size at least $|E|-n+1$, with at most $d$ edges incident to each vertex in $U$, whose complement contains a spanning tree?

Thus, your problem reduces to the following problem:

  Find a maximum-size edge-set $S$ having at most $d$ edges incident to each vertex in $U$ and whose complement contains a spanning tree.

The independent sets of edges in $G$ form a matroid.  The bases are the spanning trees.  The dual of this matroid is a matroid $M_t^*$.  The edge-sets in $M_t^*$ are the edge-sets whose complement contains a spanning tree.

The edge-sets in which each vertex $u_i$ in $U$ has degree at most $d$ form yet another matroid $M_d$.

Thus, the following two conditions on edge-set $S$ are equivalent:

$S$ is in the intersection $M_d \cap M_t^*$ of the two matroids;
$S$ has at most $d$ edges incident to each vertex in $U$, and the complement of $S$ contains a spanning tree.

So the following algorithm solves the problem in polynomial time:

  Using matroid intersection, find a maximum-size edge-set $S$ in $M_d \cap M^*_t$.


Why is it so difficult for a computer to prove something? This may be considered a stupid question. I am not a computer science major (and I'm not a mathematics major yet, either), so please excuse me if you think that the following questions display some major erroneous assumptions.

While there are plans to formalize Fermat's Last Theorem (see this presentation), I have never read or heard that a computer can prove even a "simple" theorem like Pythagoras'.

Why not? What is (/are) the main difficulty(/ies) behind establishing a fully autonomous proof by a computer, aided only by some "built-in axioms"?

A second question I would like to ask is the following: Why are we able to formalize many proofs, while it is currently impossible for a computer to prove a theorem on its own? Why is that "harder" ?

While there are plans to formalize Fermat's Last Theorem (see this presentation), I have never read or heard that a computer can prove even a "simple" theorem like Pythagoras'.

In 1949 Tarski proved that almost everything in The Elements lies within a decidable fragment of logic, when he showed the decidability of the first-order theory of real closed fields. So the Pythagorean theorem in particular is not talked about much because it's not especially hard.

In general, the thing that makes theorem proving hard is induction. First-order logic without induction has a very useful property called the subformula property: true formulas $A$ have proofs involving only the subterms of $A$. This means that it's possible to build theorem provers which can decide what to prove next based on an analysis of the theorem they are instructed to prove. (Quantifier instantiation can make the right notion of subformula a bit more subtle, but we have reasonable techniques to cope with this.)

However, the addition of the induction schema to the axioms breaks this property. The only proof of a true formula $A$ may require doing a proof $B$ which is not syntactically a subformula of $A$. When we run into this in a paper proof, we say we have to "strengthen the induction hypothesis". This is quite hard for a computer to do, because the appropriate strengthening can require both significant domain-specific information, and an understanding of why you're proving a particular theorem. Without this information, truly relevant generalizations can get lost in a forest of irrelevant ones.


How do you get a "Physical Intuition" for results in TCS? I'm sorry if this question is a little vague, but I am curious how successful researchers get a "feel" for the results in TCS.

For example, linear algebra can be understood geometrically, or in terms of its physical interpretations (eigenvectors can be thought of as "stable points" in a system), etc. It's also intuitive that there exists an IP protocol for TQBF (as the IP protocol can be visualized as a kind of a "game" between two entities of greatly differing computational power). However, I find that a lot of the results, even extremely basic ones in TCS do not have such simple intuitions (MA $\subseteq$ AM). Worse still, occasionally, unrefined intuitions go awfully wary (2-SAT is in P while 3-SAT is not believed to be in P (in fact, is NP-complete)). Are there any "general principles" for developing an intuition in TCS?

Like many scientific fields, it can take years to build intuition, but it can take only one new idea to tear that intuition down (and hopefully something nice gets rebuilt in its place).

There are some basic exercises you can use to try to build intuition for some paper you're reading and can't seem to penetrate. Here's one that I still do from time to time. Start with a proof that you don't understand but would really like to, which is very long. As you read each paragraph of the proof, try to write a sentence in your own words about what you think the paragraph is saying, in the margins. Hopefully the proof is written well enough that there are well-defined "parts" to the proof ("do X, then define a new function f, then apply X to f, ..."). If not, then from your sentences, separate the proof into your own parts.

Now for each part, try to write a sentence (in your own words) about what each part is doing. At this point, it could be that you find your earlier sentences are not quite accurate or don't fit well together (your intuition was "off"), so you may refine them so they fit logically together. Now you have a few sentences summarizing the whole proof. Then (now this last part is from my advisor, Manuel Blum) try to think of one word or phrase for the whole thing. This phrase would be the key idea that, in your mind, is what gets the whole argument started. (For example, most existence proofs via the probabilistic method can be summed up by: "PICK RANDOM". In the case of $MA \subseteq AM$, I would say something like "MAKE ARTHUR SPEAK MORE". But maybe something else in the proof feels to be the "key" idea to you, which is perfectly fine. It's your intuition!)

I guess my suggestion may be useful for most mathematics, but I found it very useful for TCS, where many proofs really do boil down to 1-2 really new ideas, and the rest is a synthesis of that idea with what was already known.


Is there a survey of the field of quantum automata? I'm looking for a survey paper of the important concepts in the field of Quantum Automata. I've found Quantum Automata Theory -- A Review
 by Hirvensalo, but it sounds too succinct to grasp the topic.
Is there a quite comprehensive survey on the topic of Quantum Automata?

Also, could you point me to the essential literature about the topic?

You can check the recent survey by Ambainis and Yakaryilmaz: Automata and Quantum Computing. It is comprehensive and points the essential literature with some open questions.

Moreover, here is a list of papers published on quantum automata until 2015.


Is this dense version of Kruskal's algorithm well-known? About a year ago, a friend and I thought of a way to implement Kruskal's algorithm for dense graphs in better than the usual $O(m \log m)$ bound (without assuming pre-sorted edges). Specifically, we achieve $\Theta(n^2)$ in all cases, similar to Prim's when implemented using adjacency matrices.

I've posted a bit about the algorithm in my blog, including C++ code and benchmarks, but here's the general idea:

Maintain one representative node for each connected component. Initially, all nodes represent themselves.
Maintain a vector dist[i] such that, for every component i, has the lightest component-crossing edge incident to i.
When finding the lightest edge that crosses partitions, simply find i that minimizes the weight of dist[i], in linear time.
When joining two components $c_i$ and $c_j$, modify the adjacency matrix $A$, such that now $A_{i, k} = \min \{A_{i, k}, A_{j, k}\}$ for all components $k$, and mark $i$ as no longer representative of its connected component (only $j$ will now remain).

The contracting of the lightest edge and the finding of said edge can thus both be done in linear time. We do this $n - 1$ times to find the MST. A little bookkeeping is needed to actually find which edge we want to add to the MST, but does not increase the complexity. Thus the runtime is $\Theta(n^2)$. The implementation is just a couple of for loops.

Is this version of Kruskal well-known in the literature?

I'm not sure about this specific method for achieving $O(n^2)$ time, but two different methods for performing Kruskal in $O(n^2)$ time are given in my paper "Fast hierarchical clustering and other applications of dynamic closest pairs" (SODA 1998, arXiv:cs.DS/9912014, and J. Experimental Algorithms 2000):

Use Prim–Dijkstra–Jarník instead and then sort the edges to get the insertion sequence that Kruskal would give, or
Use the quadtree closest-pair data structure described in the paper, viewing Kruskal as a standard agglomerative clustering procedure where we merge the closest two clusters into a supercluster at each step, with "closest" defined as the length of the shortest edge connecting two clusters.

Solution 2 is similar in spirit to what you describe but the details of how to keep track of the distances between clusters are slightly different. You keep the row-wise minima of the cluster distance matrix, allowing you to scan this list of row-minima in linear time to find the global minimum, while my paper overlays a quadtree on the same matrix and keeps track of the minimum in each quadtree square. Your method is simpler, but less flexible for some other dynamic closest pair problems (it depends on the fact that merging two clusters causes their distances to other clusters to decrease, true for this problem but not necessarily for others).

As I wrote in 2011 in the Wikipedia article on the nearest-neighbor chain algorithm, that algorithm can also be used to perform Kruskal in $O(n^2)$ time. However (unlike some other applications of the nearest-neighbor chain algorithm) you don't get a space savings, so (like the quadtree method and your method) the space is still $O(n^2)$. In contrast Prim+sorting can use only $O(n)$
space beyond that needed to store the input.


Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver? Per the title, other than using a general purpose LP solver, is there an approach for solving systems of inequalities over variables $x_i, \ldots, x_k$ where inequalities have the form $\sum_{i \in I} x_i < \sum_{j \in J} x_j$? What about the special case of inequalities that form a total order over the sums of the members of the power set of $\{x_i, \ldots, x_k\}$?

For your first question, without the total order, the answer to your question is that it's essentially as hard as linear programming. Here's an outline of a proof.

First, let's establish a variable $x_1>0$, which we call $\epsilon$. Now, let's choose another variable $x_i$, which we will call $1$. We want to make sure that $$\epsilon \ll 1\, .$$
To do this, consider the inequalities
$$x_1 < x_2,$$
$$x_1 + x_2 < x_3,$$
$$x_2+x_3 < x_4,$$
and so on. With a long enough chain, this will tell us that $Nx_1 < x_i$, or $\epsilon < 1/N$, for some very large $N$ ($N$ is a Fibonacci number, and so grows exponentially in $i$).

We can now manufacture a linear program with integer coefficients. If we want a coefficient of 3 on $x_t$, we add the inequalities
$$x_t < x_{t'} < x_{t''} < x_t + \epsilon$$ and let $x_t + x_{t'} + x_{t''}$ stand in for 3$x_t$. If you want larger coefficients, you can get them by expressing the coefficients in binary notation, and making inequalities that guarantee that $x_u \approx 2x_t$, $x_v \approx 2x_u$, and so on. To get the right-hand-side, we do the same with the variable $x_i = 1$. This technique will let us use linear programs of the OP's form to approximately check feasibility for arbitrary linear programs with integer coefficients, a task which is essentially as hard as linear programming.

I don't know how to analyze the second question, asking about the case where there's a total order on all subsets.


Connecting cells by line and column permutations in a finite grid I'd like to know whether the following simple problem has been studied before and if any solution is known.

Let G be a finite (MxN) grid, S a subset of G's cells (the "crumbs"). Two crumbs are said to be (locally) connected if their coordinates differ by at most one (i.e., if drawn as squares, they share at least one corner point).

Now, one can try to connect the crumbs (their set as a whole) by permutating the lines and the columns of the grid. In other words, the goal is to come up with a permutation of the lines and a permutation of the columns so that any two crumbs in the resulting grid are connected by a chain of (locally) connected crumbs.

Question: is there always a solution?

I don't quite know how to attack it. For lack of a better idea, I have written a raw program that looks for solutions by brute force (it generates the permutations at random and checks whether the resulting grid has its crumbs connected). The program has so far always found solutions on smallish (10x10 or 7x14) grids, and larger grids are clearly out of reach of its simplistic strategy (it would take too long to stumble at random across a solution).

Here is an example of a grid solved by the program:

Initial grid (crumbs are denoted by X's, empty cells by dots):

   0 1 2 3 4 5 6 7 8 9
 0 X . X X . X . X X .
 1 X . . . . X . . . .
 2 . . X . . . . X . X
 3 . X . . X . X . . X
 4 . . . X . . . . . .
 5 X X . . . X X . X .
 6 . . . X . . . . X .
 7 X . X . . X . . . .
 8 X . . . X . . X X .

Solution:

   6 1 4 7 8 2 9 3 5 0
 1 . . . . . . . . X X
 4 . . . . . . . X . .
 5 X X . . X . . . X X
 8 . . X X X . . . . X
 7 . . . . . X . . X X
 0 . . . X X X . X X X
 3 X X X . . . X . . .
 6 . . . . X . . X . .
 2 . . . X . X X . . .

Naturally, the problem can readily be generalized to any dimension d > 2. I suppose other generalizations could be considered.

Thanks in advance,

Yann David

Let's try a similar counting argument to the one in the earlier version of my answer, more carefully.

Given an input 0-1 matrix with q nonzeros, define a "solution" to be a permutation of the rows, a permutation of the columns, and the connected 0-1 matrix that one gets as output after performing the permutations. The important observation here is that there are at most $n^2 2^{5q}$ different output matrices possible: once we make one of $n^2$ choices for the position of one of the nonzeros, we can encode the rest of the output matrix in $5q$ bits by doing a preorder traversal of a spanning tree of the nonzeros and recording for each edge in the tree whether it goes to a leaf, whether it is the last edge from its parent, and what its direction is. So the number of solutions is in total at most $n^2 2^{5q} (n!)^2$.

Now each solution works only for a single input, because we can reverse the permutations to get the input back from the output matrix. The number of inputs that have exactly $c$ nonzeros per row is $\binom{n}{c}^n$, and for $c$ constant this can be rewritten $\exp(cn\log n-O(n))$. But for $q=cn$ the number of solutions is $\exp(2n\log n+O(cn))$. For $c>2$, the inputs outnumber the solutions, so there is an unsolvable input.


Graph classes for which the diameter can be computed in linear time Recall the diameter of a graph $G$ is the length of a longest shortest path in $G$. Given a graph, an obvious algorithm for computing $\text{diam}(G)$ solves the all-pairs shortest path problem (APSP) and returns the length of the longest path found.

It is known that the APSP problem can be solved in optimal $O(n^2)$ time for several graph classes. For general graphs, there is an algebraic graph theoretic approach running in $O(M(n) \log n)$ time, where $M(n)$ is the bound for matrix multiplication. However, computing the diameter is apparently not critically linked to APSP, as shown by Yuster.

  Are some non-trivial graph classes known for which the diameter can be computed even faster, say in linear time?

I am especially interested in chordal graphs, and any subclasses of chordal graphs such as block graphs. For example, I think the diameter of a chordal graph $G$ can be computed in $O(n+m)$ time, if $G$ is uniquely representable as a clique tree. Such a graph is also known as ur-chordal.

The eccentricity of a vertex $v$ is the length of a longest shortest path starting from $v$.  The diameter is the maximal eccentricity over all vertices.
Any BFS from a vertex will establish its eccentricity.
A key idea for efficient diameter finding is therefore to preprocess the graph to find a small set of vertices, at least one of which achieves maximal eccentricity.

Running a lexicographic breadth-first search, the end-vertex often has high eccentricity.  In particular, it is guaranteed to have eccentricity at most one less than the diameter for chordal graphs.  For some subclasses of chordal graphs such as interval graphs, it is guaranteed to have maximal eccentricity.  This also holds for some non-chordal classes such as $\{\text{AT},\text{claw}\}$-free graphs.

LBFS and BFS are both linear in the size of the graph, but of course if $m = \Omega(n^2)$ (such as $K_n$) then the runtime will not be $o(n^2)$.  Your discussion implies that you probably really want a linear algorithm $O(m+n)$ rather than $o(n^2)$.

So for some subclasses of chordal graphs, a linear algorithm is to run LBFS, take the end-vertex, then run BFS starting at that vertex.  For chordal graphs this will determine the diameter with an error of at most 1.  The graphs for which this is exact seem to be those where the even powers are chordal.  These are precisely those chordal graphs that contain no rising sun or $(\text{rising sun}- K_2)$ subgraph that preserves distances.

(source: graphclasses.org)

Feodor F. Dragan, Falk Nicolai and Andreas Brandstädt, LexBFS-orderings and powers of graphs, WG 1996, LNCS 1197, 166–180.  doi:10.1007/3-540-62559-3_15

I do not know if this can be extended to compute the diameter for all chordal graphs precisely.  Corneil's survey seems to indicate that this was still open in 2004.  I also don't know if an analysis has been done on extending the search from one vertex to a small constant number or $\log n$ starting vertices; this might be interesting to explore.

Derek G. Corneil, Lexicographic Breadth First Search – A Survey, WG 2004, LNCS 3353, 1–19. doi:10.1007/978-3-540-30559-0_1


Number of local maxima in MAX-2-SAT Given an instance of MAX-2-SAT, let us call an assignment of variables a "local maximum" if changing the value of any variable reduces the number of satisfied clauses.  My question is, how many local maxima can an instance of MAX-2-SAT have?  Clearly it must be less than $2^N$, but how large can it be?

To illustrate, suppose instead of considering MAX-2-SAT, we considered MAX-k-CSP with $k=N$ and a single clause.  This means that we can choose any function of $N$ variables as the truth value of the clause.  If we pick, for example, the parity function so that the clause is true if parity is odd, then there are $2^{N-1}$ local maxima (any odd parity configuration is a local maximum as flipping any spin makes it even parity).  On the other hand, I would guess that going from MAX-k-CSP to MAX-2-SAT will significantly reduce the maximum possible number of local maxima.

I would also be interested if anyone knows the answer to the number of local maximum for MAX-k-SAT and MAX-k-CSP for $k>2$ but $k=O(1)$.  I would also be interested in the answer in the case of bounded ratio of number of clauses to number of variables.

One can get a $n \choose n/2$ lower bound by considering the $n$ variable formula that for every pair $x$, $y$, of variables contains the clauses $(x \vee y)$ and $(\neg x \vee \neg y)$. The total number of clauses is $2 \cdot {n \choose 2}$. Every assignment will satisfy one of the two clauses on $x$ and $y$. Both clauses are satisfied exactly when $x$ and $y$ get different values. Hence, if $i$ variables are set to true the total number of satisfied clauses is
$${n \choose 2} + i \cdot (n-i).$$
This is maximized when $i = n/2$. Thus, for even $n$, every assignment that sets exactly $n/2$ variables to true is a local maxima. The total number of such assignments is $n \choose n/2$, which is $\Theta(\frac{2^n}{\sqrt{n}})$.


Equivalence for Constant-width Read-Once Branching Programs with Distinct Orders Let $X={x_1,...,x_n}$ be a set of variables and $\pi:[n]\rightarrow [n]$ be a permutation of the $n$-element set $[n]=\{1,...,n\}$.

A $\pi$-OBDD is an oblivious, read-once branching program where the variables are tested in the order $x_{\pi(1)}x_{\pi(2)}...x_{\pi(n)}$. The width of an OBDD $F$ is the maximum number of nodes in a layer of $F$.

Let $c$ be a constant. Given a $\pi_1$-OBDD $F_1$ and a $\pi_2$-OBDD $F_2$, both of width at most $c$, where $\pi_1$ and $\pi_2$ are possibly distinct permutations, what is the complexity of determining whether $F_1$ and $F_2$ represent the same function?

Obs: If $\pi_1 = \pi_2$ then testing whether $F_1$ and $F_2$ represent the same function can be done in polynomial time via classic automata-theoretic techniques.

In "Branching Programs and Binary Decision Diagrams" by Ingo Wegener [1] (very good, complete reference to check this kind of fact on branching programs), Section 5.7 deals with how you can transform a given $\pi_1$-OBDD $F_1$ into an equivalent $\pi_2$-OBDD $F_2$ by using syntactic rules. If you have a bound $B$ on the representation of $F_1$ by $\pi_2$-OBDD then you can do this in time polynomial in $|F_1|$ and $B$. He uses it to prove Corollary 5.7.11 which answers your question and a bit more: you do not need to assume the width is bounded.

Corollary 5.7.11 (in [1]): Given $F_1$ a $\pi_1$-OBDD and $F_2$ a $\pi_2$-OBDD, one can check if $F_1$ is equivalent to $F_2$ in time $O(|F_1| \cdot |F_2| \cdot \log |F_2|)$.

[1] Wegener, Ingo. Branching programs and binary decision diagrams: theory and applications. Society for Industrial and Applied Mathematics, 2000.


Should experts in TCS charge money to read proofs that P != NP? It's well-known that there are tons of amateurs--myself included--who are interested in the P vs. NP problem.  There are also many amatuers--myself still included--who have made attempts to resolve the problem.

One problem that I think the TCS community suffers from is a relatively high interested-amateur-to-expert ratio; this leads to experts being inundated with proofs that P != NP, and I've read that they are frustrated and overwhelmed, quite understandably, by this situation.  Oded Goldreich has written on this issue, and indicated his own refusal to check proofs.

At the same time, speaking from the point of view of an amateur, I can assert that there are few things more frustrating for non-expert-level TCS enthusiasts of any level of ability than generating a proof that just seems right, but lacking both the ability to find the error in the proof yourself and the ability to talk to anyone who can spot errors in your proof.  Recently, R. J. Lipton wrote on the problem of amateurs who try to get taken seriously.

I have a proposal for resolving this problem, and my question is whether or not others think it reasonable, or if there are problems with it.

I think experts should charge a significant but reasonable sum of money (say, 200 - 300 USD) in exchange for agreeing to read proofs in detail and find specific errors in them.  This would accomplish three things:

Amateurs would have a clear way to get their proofs evaluated and taken seriously.
Experts would be compensated for their time and energy expended.
There would be a significantly high cost imposed on proof-checking that the number of proofs that amateurs submit would go down dramatically.

Again, my question is whether or not this is a reasonable proposal.  Obviously, I have no ability to cause experts to adopt what I suggest; however, I'm hoping that experts will read what I've written and decide that it's reasonable.

I have some "real-world experience" in this nascent industry (and no, I'm not talking about my $200,000 offer to Deolalikar :-) )

In January, a software developer emailed me that he had an attempted proof of P≠NP, and that while he was almost sure there was an error, he couldn't find it.  He asked if I knew any grad students who'd be willing to find the error for him in exchange for a few hundred dollars.

To give you some context: I get a proof of either P≠NP or P=NP in my inbox roughly once per month.  Many of these emails go to a long list of complexity theorists (Cook, Karp, Fortnow, Sipser...); they often include religious or metaphysical ruminations as well as dark hints about academic conspiracies.  (In one case, there were graphic death threats against me, which led to my contacting the police.)  Virtually none of them acknowledge any possibility that the proof might be wrong, or that the author might have misunderstood the question.  And when, back in grad school, I tried to correspond with the authors, I found all of them to be fervent believers in Churchill's maxim "never, never, never, never give up."

So the software developer's request really impressed me!  This was the first time I'd ever seen a P≠NP proof accompanied by this level of self-awareness---both about the imposition being made on people's time and (more importantly) about the likelihood of error.  As it happened, my PhD student Michael Forbes sent the author a beautiful, detailed report explaining the problems with his approach; the author thanked Michael and (I think! :-) ) paid up as promised.

So yes: for amateurs who want someone to examine their P vs. NP proofs (or similar work), I think paying a grad student a few hundred bucks is a great way to go.  (Note that grad students are a much better choice than professors: not only do they have more energy and enthusiasm for such things, they also need the money more.)  I wish more amateurs availed themselves of this option.


Another variant of PARTITION I've got a reduction of the following partition problem to a certain scheduling problem:

Input: A list $a_1\leqslant\cdots\leqslant a_n$ of positive integers in non-decreasing order.

Question: Does there exist a vector $(x_1,\ldots,x_n)\in\{-1,1\}^n$ such that

\[\sum_{i=1}^na_ix_i=0\qquad\text{and}\]
\[\sum_{i=1}^ka_ix_i\geqslant 0\quad\text{for all }k\in\{1,\ldots,n\}\]

Without the second condition it's just PARTITION, hence NP-hard. But the second condition seems to provide a lot of additional information. I'm wondering if there is an efficient way of deciding this variant. Or is it still hard?

Here is a reduction from PARTITION to this problem. Let $(a_1,\dots, a_n)$ be an instance of PARTITION. Assume that $a_1\leq a_2\leq \dots \leq a_n$.

Let $N$ be a “very large number”, e.g. $N = (\sum_{i=1}^n |a_i|) + 1$. Consider the instance
$$\underbrace{N, \dots, N}_{5n \text{ times}}, N + a_1, \dots, N+a_n,\underbrace{4N, \dots, 4N}_{n \text{ times}}$$
of our problem.

If there is a solution $x_1,\dots, x_n$ to PARTITION then
$$\underbrace{1, \dots, 1}_{4n \text{ times}},-x_1,\dots,-x_n,x_1,\dots,x_n,\underbrace{-1,\dots,-1}_{n \text{ times}}$$
is a solution to our problem.
If there is a solution $(x_1,\dots,x_{5n},y_1,\dots, y_n, z_1,\dots,z_n)$ to the instance of our problem (which we reduced an instance of PARTITION to), then $\sum_{i=1}^n a_i y_i \equiv 0 \pmod N$. Thus $$\sum_{i=1}^n a_i y_i = 0. $$
That is, $(y_1,\dots, y_n)$ is a solution to PARTITION.