Problems that can be used to show polynomial-time hardness results When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find the polynomial time algorithm. It's not that I know for sure that P != NP, it's just that this is the best that can be done with current knowledge, and indeed the consensus is that P != NP.

Similarly, say I've found a polynomial-time solution for some problem, but the running time is $O(n^2)$. After a lot of effort, I make no progress in improving this. So instead, I might try to prove that it is 3SUM-hard instead. This is usually a satisfactory state of affairs, not because of my supreme belief that 3SUM does indeed require $\Theta(n^2)$ time, but because this is the current state of the art, and a lot of smart people have tried to improve it, and have failed. So it's not my fault that it's the best I can do.

In such cases, the best we can do is a hardness result, in lieu of an actual lower bound, since we don't have any super-linear lower bounds for Turing Machines for problems in NP.

Is there a uniform set of problems that can be used for all polynomial running times? For example, if I want to prove that it is unlikely that some problem has an algorithm better than $O(n^7)$, is there some problem X such that I can show it is X-hard and leave it at that?

Update: This question originally asked for families of problems. Since there aren't that many families of problems, and this question has already received excellent examples of individual hard problems, I'm relaxing the question to any problem that can be used for polynomial-time hardness results. I'm also adding a bounty to this question to encourage more answers.

Yes, the best known algorithm for $k$-SUM runs in $O(n^{\lceil k/2 \rceil})$ time, so it's very possible that you could argue some $n^7$ problem is difficult, because if it's in $n^{6.99}$ then you can solve $14$-SUM faster.

Note the $k$-SUM problem gets "easier" as $k$ increases: given an improved algorithm for $k$-SUM, it's fairly easy to get an improved algorithm for $2k$-SUM: take all $O(n^2)$ pairs of $n$ numbers in your given $2k$-SUM instance, replacing each pair with the sum of the two, and look for a sum of $k$ numbers out of those that equal $0$. Then, an $O(n^{k/2-\varepsilon})$ algorithm for $k$-SUM implies an $O(n^{k-2\varepsilon})$ algorithm for $2k$-SUM. Put another way, a tight lower bound for $2k$-SUM is a stronger assumption than a tight lower bound for $k$-SUM.

Another candidate for a hard problem is $k$-Clique. See my $O(\log n)$-Clique answer for more on that. If you can show (for example) that a better algorithm for your problem implies an $O(n^2)$ algorithm for $3$-clique, then a super-breakthrough would be required to improve on your algorithm. Parameterized complexity gives many examples of other problems like this: $k$-Clique is hard for the class $W\[1\]$, and $k$-SUM is hard for $W\[2\]$.

Let me warn you that although problems like this are very convenient to work with, problems like $3$-SUM are not among the "hardest" in $TIME[n^2]$, e.g., it is very unlikely that every problem in $TIME[n^2]$ can actually be linear-time reduced to $3$-SUM. This is because $3$-SUM can be solved with $O(\log n)$ bits of nondeterminism in linear time, so if everything in quadratic time can be reduced to $3$-SUM, then $P \neq NP$ and other fantastic consequences results. More on this point can be found in the article "How hard are $n^2$-hard problems?" (At some point, "3SUM-hard" was called "$n^2$-hard"; this SIGACT article rightly complained about that name.)


Practical example: how to formally verify "file name" implementation from a spec? Say you have an OS-independent specification for file names. The file names are case sensitive, and let's say can't be more than 200 characters, and can't have : or / in the name.

Now say you want to implement this specification in C on different operating systems (different versions of linux and darwin, not windows for now).

Let's say for argument's sake, it turns out on some operating system (operating system "A"), that you also can't use | in the file name. Well, you didn't capture this in your spec initially.

The question is, how do you figure this out before running into this case? In circuits (from my understanding), you can use "model checking" to automatically explore all possible states of the system, to figure out edge cases your spec doesn't handle. That makes sense for relatively simple state machines like logic circuits. But what about this case with file names?

How would you generate file names, and try to save the file on that operating system, so it can discover these implementation errors, without having to generate every possible string up to 200 characters in length?

How do you verify that the implementation of the spec on operating system "A" is valid? The model checker would have to somehow randomly construct a file name using the | character, and then hit an error. Or maybe I am misunderstanding model checking, and what this really is is automatic testing.

What I'm wondering is, how do you account for these types of cases in advance using formal methods? What are the general techniques or topics to start looking into?

In general, the technique used is known as "fuzzing". Not all errors are equally likely. Let's consider two hypothetical errors:

System A incorrectly rejects a filename if it contains an | anywhere.
System A incorrectly rejects a filename if it contains a prime number of b characters.

Errors of the second type are much, much rarer, but this is not explained by Computer Science. It's a result from how humans construct software. Fuzzing tries to focus on typical human bugs. In this case, we can predict the following types of errors are more likely:

Very short paths and very long paths may have boundary errors.
Errors near the begin or end of the path are more common than errors at the end
Many characters can be organized into classes which are treated identically, such as lowercase characters. All characters in this class are treated equally, so whether a filename is valid does not depend on a substitution within the class.
Some characters are a priori known to be problematic and each should be treated as a class on its own. (Examples: <>/\&:")
Duplicating characters is more likely to cause bugs the closer they're together.

Fuzzing aims to generate a smaller set of strings by omitting irrelevant variations. We obviously generate an initial set of testcases of all possible lengths (1-200). This checks rule 1. We then expand this set by varying a few characters near both ends. We might try varying the 150th character of the 170 character testcase, but we won't bother with all 254 variations. Nor will we add a variation in the 151th character.


Second order logic = PH. Do even higher order logics correspond to anything on complexity side of things? In the context of descriptive complexity PH is the class of languages expressible by statements of second-order logic. What classes of languages do higher order logics correspond to?

As you move to higher-order logics, each new order gives you quantification over exponentially larger objects than before, thus you can simulate exponentially longer computations. Other than that, it works pretty much the same as in the second-order case.

More precisely, define the iterated exponential function $2_d^x$ by
$$\begin{align*}2_0^x&=x,\\2_{d+1}^x&=2^{2_d^x}.\end{align*}$$
Let $\Sigma^d_m$ denote in the usual fashion the class of $(d+1)$th order sentences that consist of $m$ alternating blocks of $(d+1)$th order quantifiers starting from existential, followed by a $d$th order formula. (Note that the superscript is off by one from the order. Don’t blame me for this historical peculiarity.)

Then:

For any $d,m\ge1$, the class of all $\Sigma^d_m$-expressible languages is exactly $\Sigma_m\text-\mathrm{TIME}\bigl(2_{d-1}^{\mathrm{poly}(n)}\bigr)$.
Thus, for any $d\ge1$, the languages expressible in $(d+1)$th order logic are exactly those from the $2_{d-1}^x$-time hierarchy: $\bigcup_m\Sigma_m\text-\mathrm{TIME}\bigl(2_{d-1}^{\mathrm{poly}(n)}\bigr)$. For example, second-order logic corresponds to $\mathrm{PH}$, and third-order logic to $\mathrm{EXPH}$.
Thus, the class of languages expressible in all of finite-order logic is $\mathrm{ELEMENTARY}$.

Reference:

[1] Leszek Kołodziejczyk: Truth definitions in finite models, Journal of Symbolic Logic 69 (2004), no. 1, pp. 183–200, doi: 10.2178/jsl/1080938836.


Pseudorandom increasing sequence I am looking for a way to generate an increasing sequence of integers $(x_i)$ such that the sequence of differences $(x_{i+1}-x_i)$ is pseudorandom (in any common way of defining pseudorandomness). It should be possible to efficiently find the $k$-th element in the sequence for a given $k$.

Nonexamples:

A linear congruential generator is not increasing, but it is possible to generate the $k$-th element, $x_k = A^kX_0+(1+\dotsc+A^{k-1})B \pmod{p}$, using $O(log(k))$ arithmetic operations.
Accumulating the sum of a linear congruential generator gives a sequence with the desired pseudorandomness property, but I don't know how to get the $k$-th element efficiently.

Given that you said it would be enough for the sequence to be unpredictable, here is a very simple solution.  The $i$th value in the sequence is given by

$$x_i = 2^{128} i + y_i$$

where $y_i$ is any pseudorandom sequence where you can efficiently find the $i$th value ($y_i$) and where each $y_i$ is 128 bits wide (i.e., $0 \le y_i < 2^{128}$).  For instance, you could use

$$y_i = F(K,i)$$

where $F$ is any pseudorandom function (e.g., AES) with a 128-bit output, and $K$ is a key (the seed from which the entire sequence is generated).


Is there software for graph product calculation and visualization? I am interested in finding a program which can calculate and preferably also visualize various products of not huge graphs.

More specifically, I work with labeled, directed multigraphs, and would like to be able to calculate and visualize especially the lexicographic product of such graphs.

Further, as it more precisely is a close variant of the lexicographic product I am interested in, it would be preferable if modifying the predefined operation is possible.

Specifically, I am interested in the following: where L(sG) constitute the set of labels on node s in graph G, and pre(tH) is one of two sets of labels for t in H, the product is one such that 1) the set of nodes is (s,t) such that pre(tH) is a subset of L(sG), 2) (s,t) and (s',t') are related in GxH as specified by the lexicographic product, and 3) the labels L(sGxH) are [those from L(sG) plus those from the second set of labels of t in H called post(t,H)] minus [those from L(sG) inconsistent with the new post(t,H)].

I do not assume that the program in question has the specified operation pre-programmed, but it would be very nice if it was implementable with some tampering.

Does any one know of a package that would allow this?

I think that Sage is the right thing for this task.

Example.

sage: G = digraphs.Circuit(40)
sage: G = G.lexicographic_product(G)
sage: G.show()

Other graph products and algorithms are available as well.


Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize? This is a follow up to this question, and is related to this question of Shiva Kinali.

It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use hierarchy theorems. I want to know if the proofs are "pure" diagonalization theorems, or if they use something more that usual diagonalization. So my question is

  is there a reasonable relativization which puts permanent in uniform $\mathsf{TC^0}$?

Note that I am not sure how to define oracle access for uniform $\mathsf{TC^0}$, I know that finding the correct definition for small complexity classes is nontrivial. Another possibility is that permanent is not complete for $\mathsf{\#P}$ in the relativized universe, in which case I should use some complete problem for $\mathsf{\#P}$ in the relativized universe in place of it, and I think $\mathsf{\#P}$ should have a complete problem in any reasonable relativized universe.

Any separation of classes closed under "polynomial resources" has an oracle making them equal. (This is provided the oracle mechanism is fair and allows both machine models to make polynomial length queries and no more.)

Let $TC0^{O}$ be "$TC0$ with gates for oracle $O$". Letting $O$ be a $PSPACE$-complete language under $TC0$ reductions, we have $TC0^{O} = PSPACE = PSPACE^{O} = PP^{O}$, where  in the oracle mechanism for $PSPACE$, we count the space usage of the oracle tape along with the rest of the memory. (So only polynomially length queries are asked.) Such an equality holds for many classes "closed under polynomial resources", in the sense that they can ask polynomially length queries to an oracle, but no larger. These classes include stuff like $AC0$, $TC0$, $LOGSPACE$ (under a different oracle mechanism which does not count oracle queries towards the space bound), $P$, $NP$, $PH$, and $PP$. So any separation of classes in this list must necessarily use some kind of "non-relativizing" argument. This also implies (for example) that the natural proofs of things like Parity not in $AC0$ are non-relativizing (but this is even easier: all you need here is an oracle for parity, so you get $AC0[2]$).

In the collection of proofs you cite, I believe most of them (if not all) work by assuming $TC0 = PP$ and deriving a contradiction. These kinds of results are called "indirect diagonalization". So a relativization of their proof would have to say: "if $TC0^{O} = PP^{O}$, then contradiction..." but this assumption is actually true for some oracles $O$.

In the comments, it was pointed out that $LOGSPACE^{O} = PSPACE^{O}$ in the way that I am using it. These are just subtleties with the oracle mechanism. On the LOGSPACE side, the query tape cannot be part of the space bound, since queries are polynomial length. On the PSPACE side, the query tape is taken as part of the space bound. That was to make things "fair". But if you give them exactly the same oracle mechanism then indeed you can separate them again by diagonalization. For instance, if queries do not count towards the space bound, then in PSPACE^{PSPACE} you can ask exponentially long questions to PSPACE, so this in fact contains EXPSPACE. I apologize for not saying this explicitly earlier.

Space-bounded computation is very subtle with respect to oracles. See page 5 of this article by Fortnow for a good summary of why oracle and space-bounded computation don't always mix.


Long-term data encoding, Phoenix Mars DVD While browsing I've stumbled over the Phoenix Mars lander

http://en.wikipedia.org/wiki/Phoenix_(spacecraft)#Phoenix_DVD

and it says that the craft contains a DVD with all kinds of information on it.

Now my question would be: If the disc is made to last centuries or even millenia, how would one make sure that the digital information can be decoded in a future when all knowledge about present-day encoding must be assumed long forgotten?

I'm not even talking about building a working DVD player; if all else fails, take a strong microscope and extract the bits the hard way.

It's about, how would I, as a future scientist, interpret the bits such that the original meaning is restored, and how would I know that I've picked the right decoding? "Digital Memory Loss" has been recognized as a major problem already, and it's only been a few decades since we earnestly started producing (and forgetting!) mass quantities of digital information.

Ordinarily, I'd think this was out of scope. However, there's an interesting series of papers involving Madhu Sudan, Brendan Juba and Oded Goldreich on what they call universal semantic communication (or how to talk with aliens). The papers are here: one, two, three.


Sampling monotone Boolean functions I'm interested in sampling monotone increasing Boolean functions on $n$ input bits uniformly at random. I understand that this is equivalent to approximating the Dedekind numbers ($D_n = $ the number of monotone increasing Boolean functions on $n$ bits), so I don't expect a method to be very efficient, but I'm interested in a nontrivial method: not generating all of them and sampling from them and not rejection sampling.

Antichains are sets of incomparable points in a poset. The approach that seems to make sense to me would be sampling antichains in the Boolean cube: every monotone increasing Boolean function $f$ is defined by its minimal incomparable $1$s, which we will call $\partial f$ in this thread, and every set of incomparable bitstrings correspond to a monotone increasing (and decreasing) Boolean function. I've attempted to sample these, but all of my methods are not uniform, biased towards unbalanced functions.

Any thoughts on this would be appreciated; I am not necessarily expecting a full solution to be found in this thread.

In [1], the paper where Propp & Wilson introduce the "coupling from the past" technique for MCMC sampling, they also outline a "heat bath algorithm" applicable to a certain kind of spin system model (Section 3.1). Then, they further illustrate how to map their spin system model to the problem of uniformly sampling from the order ideals of a poset which, in turn, is equivalent to sampling from the antichains of that poset (Section 3.2).

Propp, James Gary, and David Bruce Wilson. "Exact sampling with coupled Markov chains and applications to statistical mechanics." Random Structures & Algorithms 9.1‐2 (1996): 223-252.


complexity of fitting models to data Suppose $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$ is some some continuous function

$x_1 \ldots x_n$ is a set of real values, and we'd like to compute

$\text{argmin}_a \sum_i f(a,x_i)$ to prescribed accuracy

Are there some results on difficulty of this problem for various f?

For instance, suppose $f(m,x)=(m-x)^2$. The minimum of our problem is now the mean of x's, easy to compute. On other hand, suppose $f(m,x)=\log (1+\exp(-m x))$, there's no closed form solution, so it seems argmin is harder to compute...or is it?

Motivation: this minimization problem comes up when fitting models to data. First example of f is least-squares fit and second f is logistic regression.

Edit: I just saw a related question, and it is in the spirit of what I was asking, for a particular choice of f

You may already be aware of this, but if f is a Bregman divergence, then this arg min always has an easy solution. The specific form depends on the order of the parameters, but if the expression being minimized is

$$ \arg\min_a \sum_i f(x_i, a) $$

where $f$ is a Bregman divergence, then the answer is always the mean of the $x_i$. If the order of parameters is the other way around, then you can use the duality of Bregman divergences. Specifically, if $f$ is generated by a strictly convex function $\phi$, then the solution is the $\phi$-mean $c$ given by $$\nabla \phi(c) = (1/n)\sum_i \nabla \phi(x_i)$$.

Another interesting case is when $f$ is the Euclidean norm (not squared). In that case, the arg min is the well known Fermat-Weber point, and has been extensively studied in operations research. There's a globally optimal iterative scheme to solve it, but no closed form expression.


Finding a set of hubs in a graph Suppose, we are given a graph $G = (V,E,d)$, where $V$ is the set of vertices, $E$ is the set of edges, and $d$ is a distance function $d: E \mapsto \mathbb{R^+}$. Let $S$ be the set of source vertices and $EX$ be the set of exit vertices in $G$. Further, we are given the integers $k, \gamma$ and $\delta$. A $(k, \gamma, \delta)$-hub is a set of vertices $H \subseteq V \setminus (S \cup EX)$ such that:

For any source vertex $s_i \in S$, there exists an exit vertex $t_j \in EX$ and a hub vertex $h_{ij} \in H$ such that $d(s_i,h_{ij}) \le \gamma$ and $d(h_{ij},t_j) \le \delta$,
$|H| \le k$, i.e., there are at most $k$ hub vertices.

Intuitively, a hub is a small set of vertices such that for any source vertex, there is a short path to some exit through an intermediate hub vertex.

An optimization problem is: given $\gamma$ and $\delta$, find the minimum $k$ such that there exists a $(k, \gamma, \delta)$-hub (or show that none exists). This problem is likely to be NP-hard, but I could not find a reduction from an existing NP-hard problem.

Is there any known hardness result or approximation algorithm for this problem?

Reduction

The decision version of your problem (where $k$ is given and we wish to know whether a hub exists for that $k$) is NP-hard by reduction from dominating set.

Let $G = (V, E)$ be the given graph for the dominating set problem and let $k$ be the target number of vertices to be selected for the dominating set problem.

Then construct the instance of your problem (a graph $G'$, a distance function, a set of source vertices $S$, a set of exit vertices $EX$, a target number of hub vertices $k'$, and a pair of values $\gamma$ and $\delta$) as follows:

The new graph $G' = (V', E')$ has vertex set $V'$ and edge set $E'$.
$V' = V \times \{0,1,2\}$.
For all $v \in V$, $((v, 0), (v, 1))$ and $((v, 1), (v, 2))$ are edges in $E'$.
For all $(w, v) \in E$, $((w, 1), (v, 1))$ is an edge in $E'$.
No other edges are present in $E'$.
Every edge has length 1, so that the distance function is the standard undirected graph distance.
$S = V \times \{0\}$.
$EX = V \times \{2\}$.
$k' = k$.
$\gamma = \delta = 2$.

Correctness

The choice of a $(k', \gamma, \delta)$-hub is the choice of $k'$ vertices in $V' \backslash (S \cup EX)$ such that for every $v \in S$ there exists a chosen vertex within distance $\gamma$ of that vertex and a vertex $w \in EX$ within distance $\delta$ of that chosen vertex.

The instance generated by the reduction (when run on graph $G = (V, E)$ and value $k$) asks whether a $(k,2,2)$-hub exists. In that particular case, it is a question of whether there exists a choice of $k$ vertices in $V' \backslash (S \cup EX) = V \times \{1\}$ such that for every $v \in S = V \times \{0\}$ there exists a chosen vertex within distance $2$ of that vertex and a vertex $w \in EX = V \times \{2\}$ within distance $2$ of that chosen vertex.

But notice that any vertex that could be a hub vertex is of the form $(v, 1)$, and therefore has distance one from exit vertex $(v, 2)$. The part of the condition requiring a nearby exit vertex is then automatically satisfied.

Thus the instance is a "yes" instance if and only if there exists a choice of $k$ vertices in $V' \backslash (S \cup EX) = V \times \{1\}$ such that for every $v \in S = V \times \{0\}$ there exists a chosen vertex within distance $2$ of that vertex. This occurs if there exists a choice of $k$ vertices $C \subseteq V$ such that for every $v \in V$ there exists some $c \in C$ with $d((v, 0), (c, 1)) \le 2$.

But $d((v, 0), (c, 1)) \le 2$ if and only if $c$ and $v$ are equal or neighbors in $G$. Thus we can rewrite the condition for the problem instance to be a "yes" instance as follows: there exists a choice of $k$ vertices in $V$ such that every vertex in $V$ is either adjacent to a chosen vertex or is chosen itself. This is exactly the "yes" condition for the dominating set instance, proving this reduction to be answer preserving.

Since the reduction is clearly polynomial time, this concludes the proof that your problem is NP-hard.


Generating interesting combinatorial optimization problems I'm teaching a course on meta-heuristics and need to generate interesting instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$ and bigger. I tried of course to generate a graph with a cost matrix with values taken from a random $U(0,1)$, and found out that (as expected) the histogram for the path cost (drawn by sampling a lot of random paths) has a very narrow normal distribution ($\mu$ is $~100$ but $\sigma$ is around $4$). This means, in my opinion, that the problem is very easy, since most random paths will be below the average, and the minimum cost path is very close to a random path.

So I tried the following approach: After generating the $U(0,1)$-matrix, take a long random walk around the graph, and randomly (Bernoulli with $p=0.5$) double or halve the value of the edge. This tends to lower all values, eventually reaching zero, but if I take just the right number of steps, I can get a distribution with $\mu$ around $2$ and $\sigma$ around $1$.

My question is, first, is this even a good definition for an interesting problem? Ideally I would want an instance that is highly multi-modal (for the most common neighborhood functions), and that has very few paths near the minimum value, so that most random solutions will be very far from the optimum. The second question is, given this description, how can I generate instances with such characteristics?

One general approach to generating harder instances is as follows:

Start with a random problem instance.
Embed a "hidden backdoor": randomly choose a good solution (one that's likely to be much better than any solution that already exists) and modify the problem instance to forcibly embed this solution into the problem instance.

For instance, for TSP, you could do something like the following.  Generate a random problem instance by picking a random $U(0,1)$ cost matrix.  Then, adjust the problem instance to hide a much-better solution in it: randomly select a tour that visits each vertex exactly once, and reduce the edge weights on that tour (e.g., generate it randomly from $U(0,c)$ where $c<1$; reduce the existing weight; or modify the existing edge with some fixed probability).  This adjustment procedure ensures that the optimal solution will, with high probability, be that special tour that you selected.  If you're lucky and you select a reasonable embedding, it will also not be so easy to recognize where you hid the special solution.

This approach is derived from general ideas in cryptography, where we want to create trapdoor one-way problems: where the problem is hard to solve without knowledge of the secret trapdoor, but with knowledge of the secret trapdoor, the problem becomes very easy.  There have been many attempts to embed secret trapdoors into a variety of hard problems (while still preserving the hardness of the problem even after the trapdoor has been added), with mixed degrees of success.  But this general approach seems like it might workable, for your purposes.

The resulting problem instances might be hard, but will they be interesting, from any practical perspective?  I don't know.  Beats me.  They look fairly artificial to me, but what do I know?

If your primary goal is to select problem instances that are practically relevant and representative of real-world applications of TSP, my suggestion would be take a totally different approach.  Instead, start by surveying real-world applications of TSP, then looking for representative instances of those problems, and convert them to their corresponding TSP problem instance -- so you are working with problem instances derived from a real world problem.


Is algorithmic information theory still evolving? I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory.
The field seems very interesting for me, but it seems everything is the field was done before many years.

So my question is:
Is the field “alive” or is it pretty much closed?
Does it have open questions?

Thanks

A modern tweak on algorithmic information theory is algorithmic randomness which was developed intensively in the 2000s (2009-2009) and is still quite active.

The most notorious open problem there may be whether Kolmogorov-Loveland randomness (in which martingales are computable but are allowed to bet on bits out of order) is the same as Martin-Löf randomness (in which martingales are only semicomputable, i.e., the capital function is computably approximable from below). This is known to be almost true, e.g. if $A\oplus B=\{2n:n\in A\}\cup \{2n+1:n\in B\}$ is KL-random then either $A$ or $B$ is ML-random.

An example of a recent paper in this area:

Bienvenu, Laurent, Kolmogorov-Loveland stochasticity and Kolmogorov complexity, Theory Comput. Syst. 46, No. 3, 598-617 (2010). ZBL1204.68110..


Set Cover for Permutation Matrices Given a set S of nxn permutation matrices (which is only a small fraction of the n! possible permutation matrices), how can we find minimal-size subsets T of S such that adding the matrices of T has at least 1 in every position?

I am interested in this problem where S is a small subgroup of S_n. I am wondering whether it is possible to find (and implement!) approximation algorithms that are much quicker than the greedy algorithms (run many times until it got 'lucky', which is a very slow procedure but nonetheless it has given some near optimal bounds in small cases), or whether inapproximability guarantees that I cannot.

A few easy facts about this problem:
A length n cyclic group of permutation matrices solves this problem, of course optimally. (At least n matrices are needed because each permutation matrix has n ones and there are n^2 ones needed.)

The sets S of which I am interested do not have a n-cyclic group in them.

This problem is a very special case of set cover. Indeed, if we let X be the set (1,2, ... n)*(1,2,... n), with n^2 elements, then each permutation matrix corresponds to a size n subset, and I'm looking for the smallest subcollection of these subsets that cover X. Set cover itself is not a good way to look at this problem, because approximation of the general set cover problem.

The only reason why this problem is not much too slow using the greedy approach is because symmetry in the permutation group helps eliminate a lot of redundancy. In particular, if S is a subgroup, and T is a small subset which is a minimal covering set, then the sets sT (multiply T by any element of the group s) are still in S and still are a covering set (of course of the same size, so still minimal.) In case you were wondering, the successful case has n~30 and |S|~1000, with lucky greedy results having |T| ~37. Cases with n~50 have some very poor bounds taking a very long time to get.

To summarize, I am wondering if there are approximation approaches to this problem or if it is still general enough to fit within some inapproximability theorem- like there is for the general set cover problem. What algorithms are used to approximate related problems in practice? It seems like there may be something possible since the subsets are all of the same size and every element appears at the same small frequency 1/n.

-B

Over lunch in Brussels we proved this problem is NP-Hard by a fairly short reduction from 3SAT. Our proof doesn't lead to an inapproximability result (yet). We'll think more about it.

Roughly, you transform a 3-SAT instance (with n variables and c clauses) into a series of permutations structured as follows:

1...n for numbering the n variables
n+1 used by the variable gadget
n+2, n+3 representing the 1st clause
...
n+2j, n+2j+1 representing the jth clause
n+2c+2 used by the garbage collector

variable xi is represented by the permutation
1,...,i-1,n+1,i+1,...,n,i,...
and swapping n+2j+1, n+2j for every clause where j where xi appears;
and  the permutation
1,...,i-1,n+1,i+1,...,n,i,...
and swapping n+2j+1, n+2j for every clause where j where -xi appears.

Then we use the garbage collector to place each number in a position where it could not appear otherwise. To place x in position y, we put y in position n+2c+2 and n+2c+2 in position x. We will have exactly n+2c-1 such garbage collectors for each variable and 2(n+2c-1) for each clause. The 3SAT is satisfiable iff we can choose exactly one of the 2 permutations for each variable, iff the permutation set cover has a solution of size n+(n+2c-1)(n+2c).

There are probably some minor details missing for small instances.

Stefan.


Connectivity of graphs by edge and vertex removal Let us say that a graph $G$ is $(a,b)$-connected if the removal of any $a$ vertices and any $b$ edges from $G$ leaves always a connected graph. For example, a $k$-connected graph, according to the standard definition, is $(k-1,0)$-connected, according to the new definition. Is there a polynomial-time algorithm to decide if $G$ is $(a,b)$-connected? Here I consider that the input is $G$, $a$ and $b$.

This is an edited version of a previous "answer" which incorrectly claimed a polynomial-time algorithm for the problem. What I write below is a connection to an existing problem which suggests that the problem is difficult.

Let $s,t$ be two nodes in $G$ and we want to check if they are $(a,b)$-connected. That is removing any $a$ nodes and any $b$ edges should not disconnect $s$ and $t$. Another way to look at it as follows: what is the minimum number of nodes that we need to remove to reduce the edge-connectivity between $s$ and $t$ to $b$? These type of problems have been studied under the name multi-route cuts and they are dual to multi-route flows. Various approximation results have been shown though many basic problems are not yet resolved. A result of interest is the following. Suppose each edge has a cost $c(e)$ and we wish to remove the minimum-cost set of edges to reduce the edge-connectivity between $s$ and $t$ to $b$; then this problem is NP-Hard when $b$ is part of the input. This result is in the paper by Barman and Chawla: http://arxiv.org/abs/0908.0350

Two papers that will appear in upcoming SODA 2012 are on multi-route cuts which have further results on the topic. The one by Chuzhoy etal has hardness results for some variants.


Finding the minimum number of coordinates to change to get a vector inside a subspace Let $\mathbb F$ be a field (ex. a finite field, or the reals), $A$ a $m\times n$ matrix over $\mathbb F$, and $x\in \mathbb F^n$ a vector. I'm interested in finding the smallest number of coordinates I need to change in $x$ to order to have $Ax=\mathbb 0$.

What would be an algorithm to find this, or alternatively, an intractability result (ex. NP-completeness)?

Note: I am thinking of this in the context of matrix rigidity.

This problem is NP-hard in general.

This is equivalent to finding the sparsest vector $y\in \mathbb F^n$ such that
$$Ay = -Ax$$

As finding a sparsest solution vector for an underdetermined system of linear equations is NP-hard, so is your problem.


Expected values of Kolmogorov complexity in a random sample Kolmogorov complexity of a string is not computable. However, in a random subset of size $M$ of binary strings of length $n$, how many are expected to have complexity less than some integer $n_{0}$ less than $n$ (as a function of $M$, $n$ and $n_{0}$)?

Kolmogorov complexity is only determined up to some additive constant, so it is not possible to give an exact answer. The bound that I describe here is even weaker.

Of course the expected number can be computed easily once we know how many of the $2^n$ strings have complexity less than $n_0$, so let me answer this. It is usually the first statement about Kolmogorov complexity that this number is at most $2^{n_0}-1$ - since there are only these many strings of smaller length. On the other hand, if your program says "of length $n$, take the $x$th number", then you get $2^{n_0-K(n)-C}$ strings of complexity less than $n_0$, where $K(n)$ is the prefix-free version of Kolmogorov complexity of $n$ (so at most $\log n+\log^* n + O(1)$). In more detail, the string first contains the description of the Turing machine that taken input $px$, where p is the description of a prefix-free program that outputs $n$, outputs the $x$th number of length $n$, which is $O(1)$ bits, and then this is followed by $px$.

Probably it is possible to improve these bounds, but I doubt that you could get an exact answer.


Quantum Bell-Type Inequalities I'm curious if someone could recommend some supplementary material for gaining a deeper understanding of the paper : "Some Results and Problems on Quantum Bell-Type Inequalities - Tsirelson".

Specifically something that may elaborate a tad more on the geometric interpretation of Bell-Type inequalities. Perhaps a primer paper or relevant textbook that goes into more detail on these matters. I'd appreciate any/all feedback. Thanks again.

This paper by Barrett et al. gives a fairly intuitive description of non-signalling correlations (what Tsirelson calls non-interacting systems). Sections II.A. and II.B.1. are the most useful and easy to read, the rest is more heavy stuff.


Directed multigraphs as minimal automata Given a regular language $L$ on alphabet $A$, its minimal deterministic automaton can be seen as a directed connected multigraph with constant out-degree $|A|$ and a marked initial state (by forgetting labels of transitions, final states). We keep the initial state because every vertex must be accessible from it.

Is the converse true ? I.e. given a directed connected multigraph $G$ with constant out-degree and initial state such that every vertex is accessible from it, is there always a language $L$ such that $G$ is the underlying graph of the minimal automaton of $L$ ?

For instance if $|A|=1$ it's true, since the graph must be a "lasso" with a prefix of size $i$ and a loop of size $j$, and corresponds to the minimal automaton of $L=\{a^{i+nj}~|~n\in\mathbb N\}$.

The motivation comes from a related problem encountered in a decidability reduction, where the solution is easier : starting from a non-oriented simple graph, and with more operations allowed like adding sinks. But I was wondering if someone had already looked at this more natural question ?

The only things remotely connected I could find in the literature are papers like Complexity of Road Coloring with Prescribed Reset Words, where the goal is to color such a multigraph so that the resulting automaton has a synchronizing word. However minimality does not seem to be considered.

Update: Follow-up question after the answer of Klaus Draeger: what is the complexity of deciding whether a graph is of this shape ? We can guess the labeling and polynomially verify minimality of the automaton, so it is in NP, but can we say more ?

Any absorbing node $n$ will have to be either accepting or not (so that either everything or nothing is accepted once $n$ is entered). If the graph has more than two absorbing nodes, then some of them will end up equivalent for any choice of labeling and accepting set.

More generally, for any strongly connected graph $H$ there is only a finite number $n(H)$ of different possible labelings and accepting subsets; if your graph has more than $n(H)$ terminal strongly connected components equivalent to $H$ (attached at the leaves of a tree, say), it cannot correspond to any minimal automaton.

EDIT, regarding the follow-up question: This sounds tricky. One approach suggested by my argument might look like this:

Partition $G$ into SCCs. This is cheap; $O(|V|+|E|)$ using Tarjan's algorithm.
Sort the SCCs into isomorphism classes. Unfortunately graph isomorphism is not known to be in $P$.
For each terminal isomorphism class, determine the number of permissible corresponding sub-automata, and fail if there are not enough of them. Note that not every combination of accepting subset and edge labeling is permissible: for example, suppose our alphabet is $\{a,b\}$, and a component has two nodes, each with a self-loop and an edge to the other node. Making both nodes accepting and labeling both loops with $a$ (and the other edges with $b$) gives an automaton which is bisimilar to a single absorbing state, violating minimality.
Treat the remaining SCCs in the DAG similarly, taking into account the lower ones; I'm a bit fuzzy on the details of this part.

That is one step whose complexity is famously open, and another one which looks like it may require exponential time (since there may be exponentially many partitions into bisimilarity classes to be excluded when determining permissible automata). Can we do better?


Finding spanning spiders Is there a polynomial-time algorithm to find—if one exists—a spanning spider
of a given graph $G$?  A spider is a tree with at most one node with degree greater than 2:

I know that various degree conditions on $G$ (essentially, sufficiently large node degrees) guarantee the existence of a spanning spider.  But I am wondering if there is an algorithm for arbitrary $G$.  Thanks!

The question has been answered in the comments by Tsuyoshi & Chandra!  I am adding this CW answer so I can accept it to indicate the question is closed.  Thanks, everyone!


Gap in degree of representations of candidate boolean functions Let $x_1,x_2,\dots x_n$ be literals.

Let $P(x_1,x_2,\dots,x_n)$ be one of the following Boolean function:

$0)$ Equality function - $Eq_k^n(x)=1\iff x_1+\dots+x_n= k$

$1)$ Threshold function - $Th_k^n(x)=1\iff x_1+\dots+x_n\ge k$

$2)$ Majority function - $Maj_n(x)=1\iff x_1+\dots+x_n\ge \lceil\frac{n}{2}\rceil$

$3)$ Modular-$s$ function - $MOD_k(s)=s\iff x_1+\dots+x_n\equiv 0\mod k$

If a function 'represents' $P(x_1,x_2,\dots,x_n)$, that means the function and $P(x_1,x_2,\dots,x_n)$ agree on $x_i\in\{0,1\}$.

If a function is rational then its degree is the sum of degrees of numerator and denominator.

What is known about the smallest degree of a:

$A)$ polynomial $p(x_1,x_2,\dots,x_n)\in\mathbb R[x_1,x_2,\dots,x_n]$

$B)$ rational function $r(x_1,x_2,\dots,x_n)\in\mathbb R(x_1,x_2,\dots,x_n)$

that represents $P(x_1,x_2,\dots,x_n)$ in each case of $0,1,2$ and $3$?

In which case the gap is the largest? It seems intuitively that $2,3$ should be the most complex with possibly the largest gap for $3$.

Note that both the polynomial and the numerator and denominator of the rational function can be multilinear since $x_i^t=x_i$ on $\{0,1\}$.

For symmetric functions (as those you suggest), one may make use of the Minsky-Papert symmetrization technique to get an easy $(n+1)/2$ lower bound for all nonconstant functions.

The idea behind the symmetrization technique is to replace a polynomial $p(x)$ of degree at most $d$ by the symmetric polynomial $\sum_{\sigma \in S_n} p(\sigma(x))$. Then we may find a univariate polynomial $P$ also of degree at most $d$ such that $P(\sum_i x_i)  = \sum_{\sigma \in S_n} p(\sigma(x))$.

Suppose that $f$ is a symmetric non-constant Boolean function. With abuse of notation, write also $f(k) = f(x)$, where $k = \sum_i x_i$.
Let $p$ and $q$ be polynomials such that $p(x)/q(x) = f(x)$ for all $x$ (in particular $q(x)\neq 0$ for all $x$). Then $p(x)=f(x)q(x)$, and hence $\sum_{\sigma \in S_n} p(\sigma(x)) = \sum_{\sigma \in S_n} f(\sigma(x)) q(\sigma(x)) = f(x) \sum_{\sigma \in S_n} q(\sigma(x))$ for all $x$. We may thus find univariate polynomials $P$ and $Q$ such that $P(k) = f(k) Q(k)$ for all $k$. Thus $P(k)/Q(k)=f(k)$. Now we can observe:

The polynomial $P(k)$ must be 0 exactly when $f(k)=0$. This means $\mathrm{deg(p)} \geq \#\{k \mid f(k)=0\}$.
The polynomial $P(k)-Q(k)$ must be 0 exactly when $f(k)=1$ (since q is by assumption never 0). This means $\max(\mathrm{deg}(p),\mathrm{deg(q)}) \geq \#\{k \mid f(k)=1\}$.

It follows that the degree of $p(x)/q(x)$ must always be at least $(n+1)/2$.

For representation by polynomials even better bounds have been proved by von zur Gathen and Roche as well as Cohen and Shpilka. Namely any nonconstant symmetric function must have degree $n$ minus lower order terms.

In any case, the conclusion is, that for symmetric Boolean functions, the largest separation you may hope for is a factor 2.


Is there any time efficient way of achieving the result of FKS hashing lemma? FKS hashing lemma states.

  Given a set of $n-$bit numbers $\{x_1,x_2,\dots,x_k\}$ there exist a
  prime $p$ of $O(\log n + \log k)$-bit such that $x_i$ mod $p \neq $
  $x_j$ mod $p$ if $x_i \neq x_j$.

This follows from prime number theorem. But finding such a prime takes a lot of time. Are there more efficient hashing schemes which achieve the similar results?

DGS prove a hashing lemma that bijectively hashes a sparse set to a set from a smaller universe (without involving a primality test). In particular see Lemma 3 in the paper that maps a set of size at most $(\log n)^{1/3}$ from the universe $[n]$ to a set  of size at most $v < \log{n}$ by using the hash function $((x \bmod{u})\bmod{v})$ where $u < n$.

I guess in your setting the set consists of elements from $n$-bit numbers and you can therefore plug in $2^n$ instead of $n$ in the DGS-lemma.


How expensive may it be to destroy all long s-t paths in a DAG? We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-cut is a set of edges whose removal destroys all $s$-$t$ paths longer than $k$; shorter $s$-$t$ paths as well as long "inner" paths (those not between $s$ and $t$) may survive!

Question:
Is it enough to remove at most about a $1/k$ portion of edges from a DAG
 in order to destroy all $s$-$t$ paths longer than $k$?

That is, if $e(G)$ denotes the total number of edges in $G$, does then every DAG $G$ have
a $k$-cut with at most about $e(G)/k$ edges?  Two examples:

 If all $s$-$t$ paths have length $> k$, then a $k$-cut with $\leq e(G)/k$ edges exists.
 This holds because then
there must be $k$ disjoint $k$-cuts: just layer the nodes of $G$ according to their
distance from the source node $s$.

 If $G=T_n$ is a transitive tournament (a complete DAG), then also a $k$-cut with
$\leq k\binom{n/k}{2} \approx e(G)/k$ edges exists: fix a
topological ordering of nodes, split the nodes into
$k$ consecutive intervals of length $n/k$, and remove all edges joining the nodes of the same interval; this will destroy all $s$-$t$ paths longer than $k$.

Remark 1: A naive attempt to give a positive answer (which I also tried as first) would be to try to show that every DAG
must have about $k$ disjoint $k$-cuts. Unfortunately, Example 2 shows that this attempt can badly fail: via a nice argument, David Eppstein has shown that, for $k$ about $\sqrt{n}$, the graph $T_n$ cannot have more than four disjoint $k$-cuts!

Remark 2: It is important that a $k$-cut needs only to destroy all long $s$-$t$ paths, and not necessarily all long paths. Namely, there exist1 DAGs in which every
"pure" $k$-cut (avoiding edges incident to $s$ or $t$) must contain almost all edges.
 So, my question actually is: can the possibility to remove also edges incident with $s$ or $t$ substantially reduce the size of a $k$-cut? Most probably, the answer is negative, but I could not find
a counterexample as yet.

Motivation: My question is motivated by proving lower bounds for monotone switching-and-rectifier networks. Such a network is just a DAG, some of whose edges are labeled by tests "is $x_i=1$?" (there are no tests $x_i=0$).  The size of a network is the number of labeled edges. An input
vector is accepted, if there is an $s$-$t$ path all whose tests are consistent with this vector. Markov has proved that, if
a monotone boolean function $f$ has no minterms shorter than $l$ and no maxterms shorter than $w$, then size  $l\cdot w$ is necessary.  A positive answer to my question would imply that
networks of size about $k\cdot w_k$ are necessary, if at least $w_k$ variables must be set to $0$ in order to destroy all minterms longer than $k$.

1The construction is given in this paper.
Take a complete binary tree $T$ of depth $\log n$. Remove all edges. For every inner node $v$, draw an edge to $v$ from every leaf of the left subtree of $T_v$, and an edge from $v$ to every leaf of the right subtree of $T_v$. Thus, every two leaves of $T$ are connected by a path of length $2$ in the DAG. The DAG itself has $\sim n$ nodes and $\sim n\log n$ edges, but $\Omega(n\log n)$ edges must be removed in order to destroy all paths longer than $\sqrt{n}$.

[Self answer; this is a shortened version, the old one can be found
here]

We realized with Georg Schnitger that the answer to my question is strongly negative: there are DAGs
(even of constant degree), where every $k$-cut must have a constant fraction of all edges, not just an about $1/k$ fraction, as in my question. (A slightly weaker result that a $1/\log k$ fraction may be necessary can be obtained by using a much simpler construction mentioned in the footnote above.
A quick write-up is here)

Namely, in the paper
"On depth-reduction and grates", Georg constructed a sequence of directed acyclic
graphs $H_n$ of constant maximum degree $d$ on $n=m2^m$ nodes with the following property:

 For every constant $0\leq \epsilon < 1$ there is a constant $c > 0$ such that, if any subset of at most $cn$ nodes is removed from $H_n$, the remaining graph
contains a  path of length at least $2^{\epsilon m}$.

Take now two new nodes $s$ and $t$, and draw an edge from $s$ to every node of $H_n$, and an edge
from every node of $H_n$ to $t$. The resulting graph $G_n$ still has at most  $2n+dn=O(n)$ edges.

For every constant $0\leq \epsilon < 1$, there is a constant $c ' > 0$ such that, if any subset of at most $c'n$ edges is removed from $G_n$, the remaining graph
contains an $s$-$t$ path with  $2^{\epsilon m}$ or more edges.

Proof:
Call the nodes of $H_n$  inner nodes of $G_n$.
Remove any subset of at most $c'n$ edges from $G_n$, where $c'=c/2$.
After that, remove an inner node if it was incident to a removed edge. Note that
at most $2c'n=cn$ inner nodes are then removed. None of the edges incident to survived nodes
was removed. In particular, each survived inner node is still
connected to both nodes $s$ and $t$. By the above property of $H_n$, there must remain
a path of length $2^{\epsilon m}$ consisting entirely of survived inner nodes.
Since the endpoints of each of these paths survived, each of them
can be extended to an $s$-$t$ path in $G_n$. Q.E.D.

 A consequence is sad:  there does not exist any analogue of Markov's lemma for functions with many short minterms, even though the set of long minterms has some "complicated" structure: no super-linear lower bounds on the network size can be then proved using this "length times width" argument.

P.S. This "length times width" argument (when all $s$-$t$ paths are long enough) was earlier used by Moore and Shannon (1956). The only difference is that they do not allowed rectifies (unlabeled edges). So, this is, in fact, a "Moore-Shannon-Markov argument".


Non-comparable natural numbers The "name the biggest number game" asks two players to write down a number secretly, and the winner is the person who wrote down the larger number. The game commonly allows players to write down functions evaluated at a point, so $2^{2^{2^{2}}}$ would also be an acceptable thing to write down.

The value of the Busy Beaver function, $BB(x)$, cannot be determined (in ZFC, or any reasonable consistent axiomatic system) for large values of $x$. In particular, $BB(10^4)$ cannot be determined as per this paper. However, this doesn't mean that we cannot compare values of the Busy Beaver function. For example, we can prove that $BB(x)$ is strictly monotonic.

Lets suppose that we allow players to write down expressions involving compositions of elementary functions, natural numbers, and the Busy Beaver function. Are there two expressions that the two players can write down such we can prove in ZFC that determining the winner in ZFC is impossible (assuming ZFC is consistent)?

EDIT: Originally this question said “... arbitrary combinations of computable functions, natural numbers, and the Busy Beaver function.”

If we let $f(x)$ take on the value of $3$ if $BB(x) >$ [something ungodly large and inexpressible on this website] and $7$ if it’s not, then $f(10^4)$ and $6$ are incomparable.

This doesn’t satisfy me, largely because $f$ isn’t a reasonable function for someone to use in this game. I don’t see how to phrase my intuition about this though, so I’ve restricted the question to avoid piecewise functions.

When you say "undecidable" I assume you mean it is independent of a theory such as ZFC. There will be statements like
$$B(m)>n$$
(for natural numbers $m$, $n$) that are not decided by ZFC, assuming ZFC is consistent. Because otherwise we could compute the function $B$ just by searching for proofs in ZFC of such statements.

Since $B$ is Turing complete there is some Turing machine $\Phi$ with
Con(ZFC)$\iff$ $\Phi$ accepts with oracle $B$ (on input 0, say) and $\neg$Con(ZFC)$\iff$ $\Phi$ rejects.

Now assuming that actually Con(ZFC) is true we know $\Phi$ accepts and there is some collection of facts $B(m_i)=n_i$, $1\le i\le k$ that was used in the computation (we may set it up so that the oracle access works in this way). Then
$$\sum_{i=1}^k (B(m_i)-n_i)^2>0$$
is false, but this fact is not provable in ZFC, else ZFC would prove its own consistency.
Of course this can be rewritten as
$$\sum_{i=1}^k B(m_i)^2+n_i^2>\sum_{i=1}^k 2B(m_i)n_i\tag{*}$$
and so arguably (*) provides a Yes answer to your question.

However, I don't think we can figure out what these numbers $m_i$, $n_i$ are, because the queries are adaptive (what is asked about depends on answers to previous questions, and we don't know those answers).


SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$? Do we know of instances of $Max-2-Lin(\mathbb{Z}_2)$ which have a integrality gaps w.r.t to high degree (> 4) SOS relaxations?

Or if we specialize to Max-CUT do we know of graphs whose Max-CUT polynomial needs high SOS degree to be solved? (Or if we at least know of integrality gaps for it for high SOS degree)

We don't have integrality gaps even for Max-CUT, even for degree 4. See Barak and Steurer's notes, at the end.

You might be interested in Lee Raghavendra Steurer '14. They seem to be saying there can be no SDP relaxations for exact Max-CUT of size $2^{n^c}$ for some $c < 1$. I think this means there can be no SOS proof of degree $n^c$, and hence there are instances of Max-CUT requiring higher degree. I lack the expertise to be sure I'm interpreting this correctly though.

Other than this, I don't know of any lower bounds for the degree of SOS that can solve Max-CUT exactly.


A variation on discrepancy involving random graphs Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $−1$. Call this a configuration $\sigma \in \{+1,−1\}^n$.  The number of $+1$s that we have to assign is exactly $s$ (hence the number of $−1$s is $n−s$.) Given a configuration $\sigma$, we look at each node $i$ and sum the values assigned to its neighbors, call this $\xi_i(\sigma)$. We then count the number of nodes for which $\xi_i(\sigma)$ is nonnegative:
$$N(\sigma):=\sum_{i=1}^n 1\{\xi_i(\sigma) \ge 0\}.$$
The question is: what is the configuration $\sigma$ that maximizes $N(\sigma)$? More importantly, can we give a bound on $(\max N)/n$ in terms of $s/n$. I am wondering if this problem looks familiar to anyone, or if it can be reduced to some known problem in graph theory. If it helps, the graph can be assumed to be random of Erdős-Renyi type (say, G(n,p) with edge probability $p ~  (\log n)/n$, i.e. average degree growing as $\log n$). The main instrest is in the case where $s/n \in (0,1/2)$.

You could approach this with a "second moment method" calculation, similar to the one I used in A sharp threshold for a random constraint satisfaction problem, Discrete Mathematics 285/1-3 (2004), 301-305.

When the average degree grows like a sufficiently large constant times $\log n$, this approach has often been sufficient to find precisely the threshold of satisfiability.  It could possibly also show the fraction of clauses that can be satisfied in an unsatisfiable instance, although I have not investigated that.

To make your problem look more like my general one, you can view it as a "MAX-AT-LEAST-HALF-SAT" with a special graphical structure underlying the clauses in the CNF formula. I don't think that this special structure will help in a worst-case analysis, however, and since your clause size is non-uniform and your "bad" assignment set is growinyou'll have to go through the calculation and see if it still works.


$\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$ Is $\mathsf{NP^{PP}} = \mathsf{P^{PP}}$? Or, more generally, Is $\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}$?

These are interesting open problems. Your second question effects a Karp-Lipton collapse.

Note that Toda's theorem gives you $NP\subseteq P^{PP}$, but that does not suffice for our purposes. We want to know whether $NP^{PP}\subseteq P^{PP}$, which makes this a funny question in my opninion.

1: Note that $NP^{PP}=NP^{\#P}$ and $P^{PP}=P^{\#P}$, so your first question has already been asked and answered here. Your are asking whether the polynomial hierarchy collapses relative to a $PP$ oracle (or equivalently relative to a $\#P$ oracle). According to this answer, that is an open question. If $P^{PP}=NP^{PP}$ then clearly the hierarchy does collapse relative to that oracle.

2: I think it is an open problem, and would be answered if we know whether the polynomial hierarchy collapses relative to a $PP$ oracle. Because, note that you get a Karp-Lipton collapse:

$$NP^{PP}\subset P^{PP}_{/poly} \text{ implies }{\Sigma_2^P}^{PP}={\Pi_2^P}^{PP}$$
Here I have only used the fact that the Karp-Lipton theorem relativizes. Whether you see this as evidence against the conjecture depends on whether you think the polynomial hierarchy collapses relative to $PP$, because if you think it collapses all the way down to $P$ relative to this oracle, then yes, $NP^{PP}=P^{PP}\subset P^{PP}_{/poly}$.

Going further, keep in mind that $$PP\subseteq P^{PP}\subseteq NP^{PP}\subseteq PP^{PP}=C_2^P,$$ and we do not have an oracle which separates $PP\subsetneq PP^{PP}$, so an oracle separation towards your first question, $P^{PP}\subsetneq NP^{PP}$, is more ambitious than that, and would be a nice result in its own right. Currently we do not even have an oracle relative to which $P^{PP}\subsetneq PSPACE$.

Personally I'd love to see the flipside: is $PP\subseteq NP_{/poly}$? We already know $PP$ is not contained in $P_{/n^k}$ for any fixed $k$. Can we show the same for $NP_{/n^k}$?


Is a turing machine with random number generator more powerful? Let's extend the Turing machine so that it can read from a stream of random number generators (in addition to an infinite tape to read and write). Certainly the TM with randomness can do whatever a classical TM do, but what about the converse?

One can argue that the classical TM will always generate the same result given the same input,  while the TM with randomness can behave randomly, it can do more. But, then random-valued functions are not really what we call computable. I am aware of randomized algorithms and BPP and what not, but is there an extension of computability that deals with these kind of questions?


What is the recognition complexity of k-uniform k-partite hypergraphs? We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied.
It's also in P, right? What about larger $k$?

The problem is NP-hard for $k=3$ already.

Indeed, testing if a graph is tripartite (i.e., there exists a partition $V_1 \sqcup V_2 \sqcup V_3$ of its vertex set $V$ such that each edge is between two different subsets) is cleary NP-hard, as it is exactly equivalent to $3$-coloring.

Now, I reduce the problem of the question to that problem. Given a graph $G$, construct the 3-uniform hypergraph $H$ by adding to each edge $e = \{v_1, v_2\}$ a fresh vertex $v_e$. I claim that $H$ is tripartite iff $G$ is. Indeed, a tripartition of $H$ clearly gives a tripartition of $G$. Conversely, given a tripartition of $G$, we can construct a tripartition of $H$ by assigning each fresh vertex $v_e$ to the one available class of the partition. The reduction is obviously PTIME.


When do coherence spaces have pullbacks and pushouts? $\newcommand{\symp}{\Bumpeq}$

A coherence relation $\symp_X$ on a set $X$ is a reflexive and symmetric relation. A coherence space is a pair $(X, \symp_X)$, and a morphism $f : X \to Y$ between coherence spaces is a relation $f \subseteq X \times Y$ such that for all $(x,y) \in f$ and $(x',y') \in f$,

if $x \symp_X x'$ then $y \symp_Y y'$, and
if $x \symp_X x'$ and $y = y'$ then $x = x'$.

The category of coherence spaces is both Cartesian and monoidal closed. I would like to know when pullbacks or pushouts exist for this category, and when some monoidal analogue of pullbacks or pushout exists (and how to define it, in case this notion makes sense).

I now see how to define equalizers for coherence spaces, which means pullbacks always exist (since products do). I don't know how to do this, actually....

Recall that composition is the usual relational composition, so if $f : A \to B$ and $g : B \to C$, then:

$f ; g = \{(a,c) \in A \times C \;|\; \exists b \in B.\; (a,b) \in f \land (b,c) \in g\}$

(In this definition, the existential actually implies unique existence. Suppose that we have $b' \in B$ such that $(a,b') \in f$ and $(b', c) \in g$. Since we know that $a \Bumpeq_A a$, this means that $b \Bumpeq_B b'$. Then this means that we have $b \Bumpeq_B b'$ and $(b,c) \in g$ and $(b',c) \in g$, so consequently $b = b'$.)

We now construct equalizers. Suppose we have coherence spaces $A$ and $B$, and morphisms $f, g : A \to B$. Now define the equalizer $(E, e : E \to A)$ as follows.

For the web, take
$$E = \left\{
\begin{array}{l|c}
& \forall b.\; (a,b) \in f \implies \exists a' \Bumpeq_A a.\; (a',b) \in g \\
a \in A & \land \\
& \forall b.\; (a,b) \in g \implies \exists a' \Bumpeq_A a.\; (a',b) \in f \\
\end{array}
\right\}
$$
This picks out the subset of tokens of $A$ on which either $f$ and $g$ agree (up to coherence -- I had this wrong in my first version), or are both undefined.
Define the coherence relation on $\Bumpeq_E = \{ (a,a') \in \Bumpeq_A \;|\; a \in E \land a' \in E\}$. This is just the restriction of the coherence relation on $A$ to the subset $E$. This will be reflexive and symmetric since $\Bumpeq_A$ is.
The equalizer map $e$ is just the diagonal $e : E \to A = \{(a, a)\;|\;a \in E\}$.

Since I messed up my first version of the proof, I'll give the universality property explicitly. Suppose we have any other object $X$ and morphism $m : X \to A$ such that $m;f = m;g$.

Now define $h : X \to E$ as $\{(x,a) \;|\; a \in E\}$. Obviously $h;i \subseteq m$, but to show the equality we need to show the converse $m \subseteq h;i$.

So assume $(x,a) \in m$. We now need to show that $\forall b.\; (a,b) \in f \implies \exists a' \Bumpeq_A a.\; (a',b) \in g$ and $\forall b.\; (a,b) \in g \implies \exists a' \Bumpeq_A a.\; (a',b) \in f$.

First, assume $b \in B$ and $(a,b) \in f$. So we know that $(x,a) \in m$ and $(a,b) \in f$, so $(x,b) \in m;f$. Therefore $(x,b) \in m;g$, and so there is an $a' \in A$ such that $(x,a') \in m$ and $(a',b) \in g$. Since $x \Bumpeq x$, we know $a \Bumpeq a'$, and so there is an $a' \Bumpeq a$ such that $(a',b) \in g$.

Symmetrically, assume $b \in B$ and $(a,b) \in g$. So we know that $(x,a) \in m$ and $(a,b) \in g$, so $(x,b) \in m;g$. Therefore $(x,b) \in m;f$, and so there is an $a' \in A$ such that $(x,a') \in m$ and $(a',b) \in f$. Since $x \Bumpeq x$, we know $a \Bumpeq a'$, and so there is an $a' \Bumpeq a$ such that $(a',b) \in f$.


Equivalence of feasibility checking and optimization for linear systems One way to show that checking the feasibility of a linear system of inequalities is as hard as linear programming is via the reduction given by the ellipsoid method. An even easier way is to guess the optimal solution and introduce it as a constraint via binary search.

Both of these reductions are polynomial, but not strongly polynomial (i.e they depend on the number of bits in the coefficients of the inequalities).

  Is there a strongly polynomial reduction from LP optimization to LP
  feasibility ?

The answer is yes, and in fact one can even reduce to the decision problem of linear inequalities feasibility!

We are as input given a LP instance P:
$\max c^Tx\ \text{s.t.}\ Ax \leq b\ ;\ x\geq 0$.

We furthermore have access to an oracle that given a system of inequalities $S=\{Bz \leq d\}$ returns yes/no, whether the system is feasible.

The reduction now proceeds as follows:

Test if $S_1=\{Ax \leq b\ ;\ x \geq 0\}$ is feasible. If not, we can report that P is INFEASIBLE.
Form the dual program D: $\min b^Ty\ \text{s.t.}\ A^Ty \geq c\ ;\ y \geq 0$.
Test if $S_2=\{Ax \leq b\ ;\ x\geq 0\ ;\ A^Ty\geq c\ ;\ y\geq0 \ ;\ b^Ty \leq c^Tx\}$ is feasible. If not, we can report that P is UNBOUNDED.
Iterate over the inequalities of $S_1$ and try to add them one-by-one as equalities (i.e. add the reverse inequality) to the system $S_2$. If the system remains feasible we keep the constraint in $S_2$, and otherwise remove it again. Let $S_3$ be the system of constraints (linear equalities) that gets added in this way. The system $S_3$  will now completely determine an optimal basic solution to P.
Using Gaussian Elimination on the system $S_3$ compute an optimal solution $x$ to P.


What are "unranked trees"? Recently I have some dispute with my colleagues and would like to clarify the following question.

It is clear what are "ranked" trees. They are those, which produced by tree grammars, where each symbol in their finite alphabets (terminals and non-terminals resp.) has an arity or "rank", which specifies number of possible children. So for terminals it is always "0", while for non-terminals it is always $\geq 1$.

But what should we consider by "unranked" trees?

In my understanding, as some papers state (I don't have references right now), an unranked tree is produced by a tree grammar where there are no restrictions on the rank for non-terminals. I.e. alphabets are not ranked anymore. And that's all (I don't want to go deeper into the formal details and definitions).

Basically in my understanding, each XML document is generally an unranked tree.

So what my colleague states, is that the "unrankness" necessary implies a kind of "unboundness" of children inside each node. In other words, if a tree grammar specifies a certain finite set of "ranks" for each non-terminal, then trees produced by such a grammar are not unranked.

The difference between my understanding and my opponent's one, is that my definition seems to be more soft and general. So I can say that any XML document is an example of an unranked tree. My colleague's definition restricts it, so not each XML document will be unranked, but only that satisfying an XSD schema which contains some unbounded lists.

So, who is right?

You are Right if the Computing Power for XSD schema is free or freely available (Soft). Otherwise, it will be Hard.


What are the general classes of measured systems Imagine there is a class of system such that a measurement can be performed on an exemplar of this class, each measurement producing 1 bit of information. There are no limitation on how many times the experiment can invoke new instance of a class, and there are no limitations on how many times measurement can be performed. However there are only N types of measurements that can be done.

To clarify, here are some examples:

The measured systems are fixed 4-bit strings, all equal to “0100”; N = 4 and corresponds to measurements of each one of these bits
The measured system is 4 independent random bits. N = 4 and correspond to measurements of these random bits.
Measured system is a pair of entangled photons. N = 4 (there are 2 ways of measuring polarization of the first photon, and 2 ways of measurement the polarization of the second photon).

It’s clear that system as a black box looks the same, and whatever its inner workings, it can be judged by results obtained from the string of 0s and 1s obtained by the measurements. For example, in 1'st case 3 of 4 types of measurements would produce 0s for every instance of the system. In 2nd case all measurements would produce independent random bits. In the 3rd case there would also be random bits, however their distribution will violate Bell's inequality.

My question is – what are the most general classes of systems that can be described by this definition and discriminated by a limited pre-set amount of kinds of measurements?

I don't think there will be any result of the form you want.  There's no single "most general system" that has this property.

(Instead, it'd be better to choose some specific pair of classes of systems you're interested in and ask specifically how to distinguish those two; that's more likely to yield an answerable question.)

To learn about work in the computer science literature that might be applicable to your situation, here are some subjects you should probably take a look at:

Total variation distance measures the "probability" with which we can distinguish two distributions, given a single sample from each, and assuming we have unlimited computational power.  (There are also other metrics.)
Computational indistinguishability, as studied in the cryptographic literature, measures the "probability" with which we can distinguish two distributions, assuming that the distinguishing algorithm is limited to some feasible amount of computation (e.g., no more than one billion CPU-years).

Your situation amounts to the following: we have a family of distributions $D_1(\theta_1)$ parameterized by $\theta_1$ (corresponding to systems of class A, where $\theta_1$ indicates which specific system instance we are working with) and a family of distributions $D_2(\theta_2)$ parameterized by $\theta_2$ (corresponding to systems of class B, where $\theta_2$ indicates the specific instance).  The observer doesn't know $\theta_1,\theta_2$ but gets to observe either a single value sampled from distribution $D_1(\theta_1)$ or a single value $D_2(\theta_2)$, and wants to try to distinguish which of those two types of values he has been given.
You want to know whether, for all $\theta_1,\theta_2$, it's always possible to distinguish with good probability (say, better than guessing).

The special case of this is: given two distributions $D_1,D_2$, if the observe gets to observe either a single value sampled from $D_1$ or a single value sampled from $D_2$, can the observe distinguish which of those two types of values he has been given?  That's been studied carefully.  If there are no limits on the computational power of the algorithm used by the observer, the answer is characterized by the total variation distance.  If the observer is limited to use a computationally-feasible algorithm, the answer is characterized by computational distinguishability.

For the case of a family of distributions, the answer will be characterized by

$$\min \{d(D_1(\theta),D_2(\theta_2) : \theta_1,\theta_2\}$$

where $d(\cdot,\cdot)$ is some appropriate distance measure (total variation distance, computational distinguishability).

There's also a corresponding theory about what happens if the observer gets to see $n$ samples drawn independently from the chosen distribution.


Complexity of intersection of regular languages as context-free grammars Given regular expressions $R_1, \dots, R_n$, are there any non-trivial bounds on the size of the smallest context-free grammar for $R_1 \cap \cdots \cap R_n$?

This is a great question and it really lies within my interests.  I'm glad that you asked it Max.

Let $n$ DFA's with at most $O(n)$ states each be given.  It would be nice if there existed a PDA with sub-exponentially many states that accepts the intersection of the DFA's languages.  However, I suggest that such a PDA might not always exist.

Consider the copy language.  Now, restrict it to copying strings of length n.

Formally, consider $n$-copy $:=$ $\{ xx \, | \, x \in \{0,1\}^{n}\}$.

We can represent $n$-copy as the intersection of $n$ DFA's of size at most $O(n)$.  However, the smallest DFA that accepts $n$-copy has $2^{\Omega(n)}$ states.

Similarly, if we restrict ourselves to a binary stack alphabet, then I suspect that the smallest PDA that accepts $n$-copy has exponentially many states.

P.S.  Feel free to send me an email if you would like to discuss further.  :)


Are there canonical non-relativizing techniques? In a lot of domains, there are canonical techniques which everybody working in the field should master. For example, for logspace reductions, the "bit trick" for composition consisting of not constructing the full output of the composed function, but always asking to recompute the result for every bit of output, permitting to keep logspace constraints.

My question is about non-relativizing techniques. Do theoricians have outlined some fundamental non-relativizing operations, or is there a different trick for each known non-relativizing proof ?

There's really only one "flagship" non-relativizing technique: namely, arithmetization (the technique used in the proofs of IP=PSPACE, MIP=NEXP, PP⊄SIZE(nk), MAEXP⊄P/poly, and several other results).

However, the proof that all NP languages have computational zero-knowledge proofs (assuming one-way functions exist), due to Goldreich, Micali, and Wigderson, used a different non-relativizing technique (namely, the symmetries of the 3-COLORING problem).

Arora, Impagliazzo, and Vazirani argued that even "local checkability," the property of NP-complete problems used in the proof of the original Cook-Levin Theorem (as well as the PCP Theorem), should count as a non-relativizing technique (though Lance Fortnow wrote a paper arguing the opposite).  The sticking point is whether it makes sense to relativize the complexity class of "locally checkable problems."

The pebbling arguments used in results from the 1970s such as TIME(n)≠NTIME(n) have been put forward as another example of a non-relativizing technique.

For more, you might want to check out my algebrization paper with Wigderson, and especially the references therein.  We had to pretty much catalogue the existing non-relativizing techniques in order to figure out which ones were and weren't encompassed by the algebrization barrier.

Addendum: I just realized that I forgot to mention measurement-based quantum computing (MBQC), which was recently used to great effect by Broadbent, Fitzsimons, and Kashefi to obtain quantum complexity theorems (such as QMIP = MIP*, and BQP = MIP with entangled BQP provers and BPP verifier) that most likely fail to relativize.


Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard? Given:

A bipartite graph G=(U,V,E)
Integers n and k.

Decision Problem:

Is there a subset of U of size k that has at most
n neighbours?

I am trying to figure out whether this problem is NP-hard (I suspect so), but couldn't find any reduction so far. The only well-known NP-hard problems for bipartite graphs seem to be finding bipartite subgraphs in graphs [1], and railway schedule optimization. It seems somewhat like an inverse of set cover, but is also different from set packing (which appears called as inverse of set cover).

Does anyone have ideas which problems could be related?

[1]: Computers and Intractability: A Guide to the Theory of NP-Completeness

It's NP-complete by a reduction from cliques in graphs. Given an arbitrary graph $G$, construct a bipartite graph from its incidence matrix, by making one side $U$ of the bipartition correspond to the edges of $G$ and the other side correspond to the vertices of $G$. Then $G$ has a clique of size $\omega$ if and only if the constructed bipartite graph has a set of $\binom{\omega}{2}$ vertices in $U$ that has at most $\omega$ neighbors on the other side of the bipartition.


Pop desired elements on stacks of bounded capacity Consider there are $k$ stacks containing a total of $n$ elements. Each element is either red or blue. We have complete knowledge of each element's location and color.
Only push and pop are allowed on the stacks.

We are interested in removing all the red elements from the stacks while maintaining the blue elements. That is, if we pop a blue element, we have to immediately push it into another stack before any other operation. Each stack has an upper bound capacity $b$, so it cannot hold more than $b$ elements.

We are interested in the minimum number of pop operations to remove all red elements from the stack (or respond it is infeasible).

One can devise a polynomial time algorithm when $k$ is a constant. Is there a polynomial time algorithm with respect to $n$ and $k$?

If we replace stacks with queues, then the problem is trivial.

Here's a simple algorithm:

We repeatedly pick a stack with a red element and execute a subroutine (to be described below) that tries to pop the topmost red element out of the stack. Either we will end up popping every red element or at some point every stack with a red element will have the subroutine failing. In the former case, it is clearly possible to pop all the red elements. In the later case, every topmost red element can't be popped, so in fact no more red elements can be popped, and so popping all the red elements is impossible.

The subroutine:

Simply pop elements out of the stack in question (pushing blue elements into other stacks) until either a red element is popped (success) or until the blue elements being popped cannot fit into the other stacks (failure).

Runtime

The subroutine requires at most $n$ operations, and the subroutine must be executed at most $k$ times in order to either conclude that a solution is impossible or to pop one red element. Since there are at most $n$ red elements. The overall runtime is $O(kn^2)$, which is polynomial in $n$ and $k$.

Correctness

Certainly if this procedure pops all the red elements then popping all the red elements is possible.

Now suppose the subroutine fails on a stack. Define the "blocking" elements in a stack to be all blue elements above the topmost red element. Subroutine failure can only happen if all the blocking elements in the stack and all the elements in all other stacks cannot fit in the other stacks. Thus, this topmost red element cannot be removed until the count of blocking elements plus elements in other stacks decreases. In other words, the topmost red element cannot be the next red element popped.

If the subroutine fails for every stack with a red element, then no red element can be the next red element popped. In other words, no remaining red element can be popped at all.

Since every operation is either reversible (moving a blue element between stacks) or purely beneficial (popping a red element), reaching a state where the subroutine fails for every stack implies that all along the problem could not be solved.


A relaxed Steiner Tree Problem Given a weighted graph $G(V,E,w)$ where $w$ is the weight function on edges and a subset of vertices $S\subseteq Q$ called terminals, a Steiner Tree is a connected subgraph which connects all vertices in $S$. Finding minimum weight Steiner Tree is called Minimum Steiner Tree Problem. This problem and many of its variants are known to be NP-Complete.

I thought about this variant where we dont need to connect all vertices in $S$. That is, along with the input, we are also given a natural number $k$, such that $k<|S|$. Now, find a minimum weight connected subgraph which connects at least $|S|-k$ vertices in $S$.

Notice that when $k$=0, this is the usual Steiner Tree Problem and when $k=|S|-2$, it is Shortest path problem. Is this problem NP-Complete for any arbitrary $k$?

I do not know whether this question already exists (quite possible considering the number of variants of Steiner Tree Problem). I did a brief search and I couldnt find anything related to this problem.

Some observations:

First, let's take a different parameter called c. The problem is to find a minimum weight connected subgraph which connects at least c vertices in S. Now c=2 is the easy problem you refer to, and c=|S| is the Steiner tree problem.

I think for c=$|S|^\epsilon$, the problem is still NP-hard. The reduction would basically add lots of useless terminals connected to the rest of the graph with very high edge weights, so that these vertices will never be picked in the min weight tree, and the min weight tree will only have the vertices we wanted. For example, an algorithm to solve this problem for c=|S|/2 can be used to solve the Steiner tree problem by just taking the instance of Steiner tree, and doubling the number of terminals and connecting them to the rest of the graph with large edge weights.

As you mentioned, the c=2 case is in P. Similarly, for any constant c', the c=c' case is easy by a brute force search.


Can an oracle allowing errors be non-relativizing? I am experimenting with k-SAT.  I'm using an oracle that returns the total number of satisfiable truth assignments, which is in #P.  The interest here is that this total is returned modulo a natural number, say N.  There is therefore a 1/N probability that the oracle mistakes a satisfiable problem for one with zero satisfiable truth assignments.  I'm wondering if this oracle could be non-relativizing.  I'm also wondering if there has been research concerning oracles with similar types of "errors".

When considering variations of a computation model, let alone one that is not natural and might confuse our intuition, definitions are of the essense. Your oracle might be in #P but that doesn't mean that is representative of that class. Since you have changed the definition of the function the oracle computes, you will have to either prove the new problem #P-complete or find another appropriate class for which the problem is complete.

Fooling around the complexity zoo, it seems that such a class has already been defined: http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modp and http://qwiki.stanford.edu/index.php/Complexity_Zoo:M#modkp , depending on how you choose N.


How to use a -coin so a TM can decide an undecidable language in polynomial time? In "Computational complexity- A modern approach" book (page 117) for the lemma 7.12 (following) the author mentioned that if the ρ is efficiently computable ρ-coin cannot give probabilistic algorithm a new power. Then he  states: "The exercises show that if ρ is not efficiently computable, then a ρ-coin can indeed provide additional power."

Lemma 7.12: A coin with Pr[Heads] = ρ can be simulated by a PTM in expected time O(1) provided the ith bit of ρ is computable in poly(i) time.

The exercise that supposed to show, if ρ is not efficiently computable, then a ρ-coin can indeed provide additional power is the following:

Exercise: Describe a real number ρ such that given a random coin that comes up “Heads” with probability ρ, a Turing machine can decide an undecidable language in polynomial time.

Now, how can we show that if ρ is not efficiently computable, then a ρ-coin can indeed provide an additional power for a probabilistic algorithm to decide some undeniable language in polynomial time?

*I removed the hint because it made me more confused but you can find it at the end of the book.

I strongly believe that this is a research level problem and proper to be discussed in theoretical computer science society because this is a high level question about computational complexity and this question has not been discussed anywhere else.

I'll take as given the existence of Chaitin's constant $\Omega\in[0,1]$, and that knowing its first $k$ bits is equivalent to be able to decide the halting problem for all Turning machines of size up to $k$:
https://en.wikipedia.org/wiki/Chaitin%27s_constant

Given access to an $\Omega$-biased coin, one can use Chernoff bounds to compute $\hat\Omega_k$, which agrees with $\Omega$ up to $k$ bits (i.e., $|\Omega-\hat\Omega_k|<1/2^{k+1}$), by sampling the coin $O(2^{2k})$ times. Now this is exponential in $k$ and is actually tight, so how does this square with the problem statement:
"Describe a real number $\rho$ such that given a random coin that comes up “Heads” with probability $\rho$, a Turing machine can decide an undecidable language in polynomial time" ?

The trick is to use a very inefficient encoding for the undecidable language.
Fix a universal encoding (the same one used to define $\Omega$) and consider the language $L$, which consists of all Turing machine descriptions $<M>$, such that $M$ halts on all inputs. Clearly, $L$ is undecidable. Now order $L$ in lexicographic order where $<M_i>$ is the $i$th word, and define $L'$ to consist of the words $<M_i'>$, where $M_i'$ is a TM equivalent to $M_i$ (the two halt on and accept the same set of inputs), but $M_i'$ contains an additional $2^i$ dummy states.

Thus, to determine whether a word $x$ belongs to the undecidable language $L'$, one only needs to know $O(\log|x|)$ bits of $\Omega$, which is feasible in expected poly$(|x|)$ time via the argument above.


Locally monotone Boolean function I am unable to understand the definition of locally monotone Boolean function which is defined in Gotsman and Linial, "Spectral Properties of Threshold Functions", 1994, p. 40:

  A function $f$ is called locally monotone if it is increasing or decreasing in each variable.

Can somebody explain the definition with two examples (a function which is locally monotone and a function which is not)?

An example of a locally monotone function is $g(x,y) = x \cdot (1-y)$. In this example $g$ is monotone increasing in $x$ and monotone decreasing in $y$.

An example of a function that is not locally monotone is $h(x,y) = x \oplus y$.
Let's see why it is not locally monotone. Look at the $x$ variable. (1) It is neither monotone increasing in $x$ since $h(0,1) > h(1,1)$, (2) nor is it monotone decreasing in $x$ since $h(0,0) < h(1,0)$.

Locally monotone functions are called also unate functions.


Inferring an LP cost vector from its solution Say I have the following linear programming formulation in standard form:

\begin{equation*}
\begin{array}{rl}
    \mathbf{x}^* = \underset{\mathbf{x}}{\text{arg}\;\text{min}}        & \mathbf{c}^T\mathbf{x} \\
    \mbox{s.t.} & \mathbf{A}\mathbf{x} = \mathbf{b} \\
                & \mathbf{x} \ge 0,
    \end{array}
\end{equation*}

with $\mathbf{x}^*$, $\mathbf{A}$ and $\mathbf{b}$ known, but $\mathbf{c}$ unknown.

Are there any known methods for computing $\mathbf{c}$ ?

I guess that you want the set of optimal solutions of the LP as small as possible.  (Otherwise, c=0 certainly makes x* one of the optimal solutions but probably that is not what you want.)

One way to obtain such c is as follows.  If x*i=0, then let ci be any strictly negative number.  If x*i>0, then let ci=0.

If you want to know all the vectors c with the required property, you can add any linear combination of rows of matrix A to cT.  It is not hard to prove that no other vectors c satisfy the condition.

Edit: Entirely rewritten in revision 2 to make it simpler.


Minimal encoding of a set (unordered collection of elements)? Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$.

If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are needed.

I'd like to be able to have a "Set" data structure, which take advantage of the fact that the set is unordered to save memory.

It seems that theoretically (information bound), we could only use $k\log \frac{|\mathcal{U}|}{k}$ bits for encoding the set, but I was wondering if such result is known.

I considered looking into implementations of current set structures in popular programming languages, but assumed they'll be more optimized for runtime rather than memory, so my questions are:

Is there a known data structure that allows storing $k$ elements set using $k\log \frac{|\mathcal{U}|}{k} + O(1)$ bits (supporting adding and deleting items of course)?
What is the best runtime of such structure?

I'm well aware we could probably save some memory by hashing (if $k << \mathcal{U}$), but I'm looking for a deterministic structure.

What you're looking for is called a "succinct" or "implicit" dictionary. The best solution I know of is Backyard cuckoo hashing, by Arbitman et al from FOCS 2010, which "guarantees constant-time [insert, delete, lookup] operations in the worst case with high probability" while using $B + o(B)$ bits, where $B$ is the lower bound you mention.

If you need updates, I don't know if you'll be able to beat $O\left(\sqrt{B}\right)$ redundancy, given the lower bounds in Brodnik et al.'s "Resizable Arrays in Optimal Time and Space".


Quantum algorithms for QED computations related to the fine structure constants My question is about quantum algorithms for QED (quantum electrodynamics) computations related to the fine structure constants. Such computations (as explained to me) amounts to computing Taylor-like series $$\sum c_k\alpha^k,$$ where $\alpha$ is the fine structure constant (around 1/137) and $c_k$ is the contribution of Feynman diagrams with $k$-loops.
This question was motivated by Peter Shor's comment (about QED and the fine structure constant) in a discussion regarding quantum computers on my blog. For some background here is a relevant Wikipedea article.
It is known that a) The first few terms of this computation gives very accurate estimations for relations between experimental outcomes which are with excellent agreement with experiments. b) The computations are very heavy and computing more terms is beyond our computational powers. c) At some points the computation will explode - in other words, the radius of convergence of this power series is zero.
My question is very simple: Can these computations be carried out efficiently on a quantum computer.
Question 1

1):  Can we actually efficiently compute (or well-approximate) with a quantum computers the coefficients $c_k$.
2) (Weaker) Is it  at least feasible to compute the estimates given by QED computation in the regime before  these coefficients explode?
3) (Even weaker) Is it  at least feasible to compute the estimates given by these QED computation as long as they are relevant. (Namely for those terms in the series that gives good approximation to the physics.)

A similar question applies to QCD computations for computing properties of the proton or neutron. (Aram Harrow made a related comment on my blog on QCD computations, and the comments by Alexander Vlasov are also relevant.)  I would be happy to learn the situation for QCD computations as well.
Following Peter Shor's comment:
Question 2

Can quantum computation give the answer more accurately than is possible classically because the coefficients explode?

In other words

Will quantum computers allow to model the situation and to give
efficiently approximate answer to the actual physical quantities.

Another way to ask it:

Can we compute using quantum computers more and more digits of the
fine structure constant, just like we can compute with a digital
computer more and more digits of e and $\pi$?

(Ohh, I wish I was a believer  :) )
more background
The hope that computations in quantum field theory can be carried our efficiently with quantum computers was (perhaps) one of Feynman’s motivation for QC.  Important progress towards quantum algorithms for computations in quantum field theories was achieved in this paper: Stephen Jordan, Keith Lee, and John Preskill  Quantum Algorithms for Quantum Field Theories. I don't know if the work by Jordan, Lee, and Preskill (or some subsequent work) implies an affirmative answer to my question (at least in its weaker forms).
A related question on the physics side
I am curious also if there are  estimations for how many terms in the expansion before we witness explosion. (To put it on more formal ground: Are there estimates for the minimum k for  which $\alpha c_k/c_{k+1} > 1/5$ (say).) And what is the quality of the approximation we can expect when we use these terms. In other words, how much better results can we expect from this QED computations with an unlimited computation power.
Here are two related questions on the physics sister site. QED and QCD with unlimited computational power - how precise they are going to be?; The fine structure constant - can it genuinely be a random variable?

The general belief seems to be that the expansion in $\alpha$ is an asymptotic series but not a convergent series. The handwaving estimate is that in $\sum_k c_k \alpha^k$, the scaling for the coefficients is roughly $c_k \sim k!$. So, since $\alpha \simeq 1/137$ the terms will start to get bigger rather than smaller for $k$ larger than around 137. (I assume there is serious literature on this topic, but I'm not too familiar with it. The above is what high energy physicists have told me in casual conversation.)

The fine structure constant itself is not something for which anyone knows a purely theoretical formula. So getting more digits of $\alpha$ is a fundamentally different problem from getting more digits of $\pi$. That being said, the challenges are both experimental and computational. Various experiments in particle accelerators and atomic physics laboratories are dedicated to making progressively more precise measurements of fundamental constants such as $\alpha$. Often, the high-precision theoretical calculation of the factors relating the experimentally observed quantities (such as scattering probabilities or spectral lines) to fundamental constants of interest such as $\alpha$ is very difficult and computationally heavy. The computational side can be just as much a limiting factor as the experimental side in these precision metrology problems. (Some of my coworkers at NIST specialize in this sort of thing.)

In the quantum algorithm that Keith and John and I developed, we do not use a perturbative expansion in powers of the coupling constant. The simulation algorithm is much more directly analogous to an actual experiment. However, one advantage over experiment is that in a simulation we are free to change $\alpha$ to whatever value we want. So, by computing scattering amplitudes at varying $\alpha$ it might be easier to determine the individual coefficients $c_k$ than it is in the real world. However, the study of quantum algorithms for simulating quantum field theories is in its infancy. The extraction of such coefficients is one of the numerous interesting questions that have not really been explored yet! Also, our algorithms don't yet tackle QED but rather some simplified models.

Today, we primarily have two classical algorithms for QFT: Feynman diagrams and lattice simulations. Feynman diagrams break down at strong coupling or high precision, as discussed above. Lattice calculations are mostly only good for computing static quantities such as binding energies (e.g. the mass of the proton), rather than dynamic quantities such as scattering amplitudes. This is because the lattice calculations use imaginary time. (Also, for certain condensed matter systems that are highly frustrated, even finding static quantities such as ground state energies is exponentially hard. It is not clear to me to what extent this phenomenon is relevant to high energy physics.) There is also a current research program on speeding up the computation of scattering amplitudes in supersymmetric quantum field theories. You may have heard about the "amplituhedron", which is part of this. This seems kind of exciting, but it's recent stuff and I don't know too much about it.

So, there is room for exponential speedup by quantum computation in the case that you wish to compute dynamical quantities such as scattering amplitudes with high precision or in a strongly coupled quantum field theory. My papers with Keith and John work out polynomial-time quantum algorithms for computing scattering amplitudes in simple quantum field theories which can be strongly coupled. We would like to extend our algorithms to simulate more complete models such as QED and QCD but we are not there yet. Doing so involves nontrivial challenges, but my feeling is that quantum computers should be able to compute scattering amplitudes in quantum field theories in polynomial time quite generally.

So, that's the perspective based on known classical and quantum algorithms. There is also a perspective from complexity theory. For many classes of physical systems, the problem of computing transition amplitudes to polynomial precision is BQP-complete, and the problem of computing ground energies is QMA-complete. So, for worst case instances we expect quantum computers to compute transition amplitudes in polynomial time, whereas classical computers require exponential time. We expect both quantum and classical computers (as well as nature itself) to require exponential time to find ground states in the worst case. The question is whether the worst case instances of the computational problems look like any real physics. In the context of condensed matter physics, the answer is basically yes, I would say. In the context of high energy physics, one can construct BQP-hard instances of the scattering amplitude problem that correspond at least loosely to something a physicist might need to calculate. (We are currently working on a paper about this.) Whether one can construct QMA-hard instances of the problem of computing a vacuum state for a quantum field theory is something that I have not really thought about. However, I think this could be done if one is willing to allow non-translationally-invariant external fields.