Approximation algorithms for Metric TSP It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time.
Is anything known about finding approximation solutions in exponential time (for example, less than $2^n$ steps with only polynomial space)?
E.g. in what time and space we can find a tour whose distance is at most $1.1\times OPT$?

I've studied the problem and I found the best known algorithms for TSP.
$n$ is the number of vertices, $M$ is the maximal edge weight.
All bounds are given up to a polynomial factor of the input size ($poly(n, \log M)$).
We denote Asymmetric TSP by ATSP.
1. Exact Algorithms for TSP
1.1. General ATSP
$M2^{n-\Omega(\sqrt{n/\log (Mn)})}$ time and $exp$-space (Björklund).
$2^n$ time and $2^n$ space (Bellman; Held, Karp).
$4^n n^{\log n}$ time and $poly$-space (Gurevich, Shelah; Björklund, Husfeldt).
$2^{2n-t} n^{\log(n-t)}$ time and $2^t$ space for $t=n,n/2,n/4,\ldots$ (Koivisto, Parviainen).
$O^*(T^n)$ time and $O^*(S^n)$ space for any $\sqrt2<S<2$ with $TS<4$ (Koivisto, Parviainen).
$2^n\times M$ time and poly-space (Lokshtanov, Nederlof).
$2^n\times M$ time and space $M$ (Kohn, Gottlieb, Kohn; Karp; Bax, Franklin).
Even for Metric TSP nothing better is known than algorithms above. It is a big challenge to develop $2^n$-time algorithm for TSP with polynomial space (see Open Problem 2.2.b, Woeginger).
1.2. Special Cases of TSP
$1.657^n\times M$ time and exponentially small probability of error(Björklund) for Undirected TSP.
$(2-\epsilon)^n$ and exponential space for TSP in graphs with bounded average degree, $\epsilon$ depends only on degree of graph (Cygan, Pilipczuk; Björklund, Kaski, Koutis).
$(2-\epsilon)^n$ and $poly$-space for TSP in graphs with bounded maximal degree and bounded integer weights, $\epsilon$ depends only on degree of graph (Björklund, Husfeldt, Kaski, Koivisto).
$1.251^n$ and $poly$-space for TSP in cubic graphs (Iwama, Nakashima).
$1.890^n$ and $poly$-space for TSP in graphs of degree $4$ (Eppstein).
$1.733^n$ and exponential space for TSP in graphs of degree $4$ (Gebauer).
$1.657^n$ time and $poly$-space for Undirected Hamiltomian Cycle (Björklund).
$(2-\epsilon)^n$ and exponential space for TSP in graphs with at most $d^n$ Hamiltonian cycles (for any constant $d$) (Björklund, Kaski, Koutis).
2. Approximation Algorithms for TSP
2.1. General TSP
Cannot be approximated within any polynomial time computable function unless P=NP (Sahni, Gonzalez).
2.2. Metric TSP
$3 \over 2$-approximation (Christofides).
Cannot be approximated with a ratio better than $123\over 122$ unless P=NP (Karpinski, Lampis, Schmied).
2.3. Graphic TSP
$7\over5$-approximation (Sebo, Vygen).
2.4. (1,2)-TSP
MAX-SNP hard (Papadimitriou, Yannakakis).
$8 \over 7$-approximation (Berman, Karpinski).
2.5. TSP in Metrics with Bounded Dimension
PTAS for TSP in a fixed-dimensional Euclidean space (Arora; Mitchell).
TSP is APX-hard in a $\log{n}$-dimensional Euclidean space (Trevisan).
PTAS for TSP in metrics with bounded doubling dimension (Bartal, Gottlieb, Krauthgamer).
2.6. ATSP with Directed Triangle Inequality
$O(1)$-approximation (Svensson, Tarnawski, Végh)
Cannot be approximated with a ratio better than $75\over 74$ unless P=NP (Karpinski, Lampis, Schmied).
2.7. TSP in Graphs with Forbidden Minors
Linear time PTAS (Klein) for TSP in Planar Graphs.
PTAS for minor-free graphs (Demaine, Hajiaghayi, Kawarabayashi).
$22\frac{1}{2}$-approximation for ATSP in planar graphs (Gharan, Saberi).
$O(\frac{\log g}{\log\log g})$-approximation for ATSP in genus-$g$ graphs (Erickson, Sidiropoulos).
2.8. MAX-TSP
$7\over9$-approximation for MAX-TSP (Paluch, Mucha, Madry).
$7\over8$-approximation for MAX-Metric-TSP (Kowalik, Mucha).
$3\over4$-approximation for MAX-ATSP (Paluch).
$35\over44$-approximation for MAX-Metric-ATSP (Kowalik, Mucha).
2.9. Exponential-Time Approximations
It is possible to compute $(1+\epsilon)$-approximation for MIN-Metric-TSP in time $2^{(1-\epsilon/2)n}$ with exponential space
for any $\epsilon\le \frac{2}{5}$, or in time $4^{(1-\epsilon/2)n} n^{\log n}$ with polynomial space for any $\epsilon \leq \frac{2}{3}$ (Boria, Bourgeois, Escoffier, Paschos).
I would be grateful for any additions and suggestions.


Why does the log-rank conjecture use rank over the reals? In communication complexity, the log-rank conjecture states that

$$cc(M) = (\log rk(M))^{O(1)}$$

Where $cc(M)$ is the communication complexity of $M(x,y)$ and $rk(M)$ is the rank of $M$ (as a matrix) over the reals.

However, when you are just using the rank-method to lower bound $cc(M)$ you can use $rk$ over any field that is convenient. Why does the log-rank conjecture restrict to rk over the reals? Is the conjecture resolved for $rk$ over fields of non-zero characteristic?  If not, is it of interest or is there something special about $rk$ over $\mathbb{R}$?

The conjecture fails over $\mathbb{F}_2$. Look at $M(x, y) = \langle x, y \rangle \bmod 2$, and $x, y \in \{0, 1\}^n$. The communication complexity is $\Omega(n)$, but the rank of $M$ over $\mathbb{F}_2$ is $n$, by the linearity of inner product.


Have you ever realized you can't solve the homework you assigned? This question is targeted at people who assign problems: teachers, student assistants, tutors, etc.

This has happened to me a handful of times in my 12-year career as a professor: I hurriedly assigned some problem from the text thinking "this looks good."  Then later realized I couldn't solve it.  Few things are more embarrassing.

Here's a recent example: "Give a linear-time algorithm that determines if digraph $G$ has an odd-length cycle."  I assigned this thinking it was trivial, only to later realize my approach wasn't going to work.

My question: what do you think is the "professional" thing to do:

Obsess on the problem until you solve it, then say nothing to your students.
Cancel the problem without explanation and move on with your life.
Ask for help on cstheory.SE (and suffer the response, "is this a homework problem?")

Note: I'm looking for practical and level-headed suggestions that I perhaps haven't thought of.  I realize my question has a strong subjective element since handling this situation involves one's own tastes to a large extent, so I understand if readers would prefer to see it not discussed.

Yes, sadly, I've done this several times, as well as the slightly more forgivable sin of assigning a problem that I can solve, but only later realizing that the solution requires tools that the students haven't seen.  I think the following is the most professional response (at least, it's the response I've settled on after several false starts):

Immediately and publicly admit the mistake.  Explain steps 2 and 3.
Give every student full credit for the problem.  Yes, even if they submit nothing.
Grade all submitted solutions normally, but award the resulting points as extra credit.  In particular, give the usual partial credit for partial solutions.

The first point is both the hardest and the most important.  If you try to cover your ass, you will lose the respect and attention of your students (who are not stupid), which means they won't try as hard, which means they won't learn as well, which means you haven't done your job.  I don't think it's fair to let students twist in the wind with questions I honestly don't think they can answer without some advance warning.  (I regularly include open questions as homework problems in my advanced grad classes, but I warn the students at the start of the semester.)  Educational, sure, but not fair.

It's sometimes useful to give hints or an outline (as @james and @Martin suggest) to make the problem more approachable; otherwise, almost nobody will even try.  Obviously, this is only possible if you figure out the solution first.  On the other hand, sometimes it's appropriate for nobody to even try.  (For example, "Describe a polynomial-time algorithm for X" when X is NP-hard, or if the setting is a timed exam.)

If you still can't solve the problem yourself after sweating buckets over it, relax.  Probably none of the students will solve it either, but if you're lucky, you'll owe someone a LOT of extra credit and a recommendation letter.

And if you later realize the solution is easy after all, well, I guess you screwed up twice.  Go to step 1.


The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem In the movie Inception  Cobb asks a asks Ariadne to design a maze that takes twice as much time to design. This lends itself to a generalized problem where we have an situation where we are resource limited by some amount and whoever will verify that this problem is in the given complexity class that either will take more time and or space to solve. Is this a novel problem?

This situation comes up frequently in crypto, where you want to generate hard problem instances along with their solutions. For example, there is the work of Eric Bach (and later, Adam Kalai) on efficiently generating random integers with their prime factorizations.

One of many interesting observations of Impagliazzo and Wigderson (Randomness vs time: derandomization under a uniform assumption. J. Comput. Syst. Sci., 63:672–688, 2001) is that one can efficiently generate uniform random matrices modulo p along with their permanents. (Think about it... use self-reducibility of permanent....) Moreover, we know that the permanent is random self-reducible. So this is an example of a very hard problem for which we can efficiently generate solved instances.


$k$-wise independent probability spaces I have been having a great deal of difficulty finding a reference that gives simple and straightforward explanation of the following:

Suppose we have $n$ random variables $Y_1, \dots, Y_n$, each of $b$-bits long. (I.e. with values in $\{0, \dots, 2^b-1 \}$). We want a probability space where each $Y_i$ is unbiased (takes on each value with probability exactly $2^{-b}$), and has $k$-independence. That is, for any $i_1 < \dots < i_k$ and any $y_1, \dots, y_k$ we have
$$
P(Y_{i_1} = y_1 \wedge \dots \wedge Y_{i_k} = y_k) = 2^{-k b}
$$

When $b = 1$ you can always get a probability space of size $n^{k}$ and sometimes you can get $n^{k/2}$ -- is there any clear statement about when these are possible?

Can someone point me to references about what happens when $b > 1$?

Thanks

For arbitrary $b$, Alon, Babai and Itai showed a lower bound on the probability space size of $m(n,\lfloor k/2 \rfloor)$ where
$$ m(n,k) = \sum\limits_{i=0}^k \binom{n}{i}$$

which is $\Omega(n^{k/2})$ for constant $k$.

They also gave a construction of size $O(n^{k/2})$ in the case of $b = 1$.

For $b=1$ there is a paper by Karloff and Mansour which shows lower bounds and upper bounds for arbitrary probabilities, i.e., for $p_1,\ldots,p_n$ with $p_i = P(Y_i = 1)$. E.g., there are probabilities $p_1,\ldots,p_n$ such that the probability space size is at least $m(n,k)$. They also say that $m(n,k)$ is also a upper bound for arbitrary probabilities.

I don't known any construction with a better upper bound than $O(n^k)$ which is given by the construction (see here) mentioned by Thomas as a comment.


Generate connected induced subgraphs as the satisfying assignments to a SAT instance I want a SAT instance (in CNF) whose set of satisfying assignments are the connected induced subgraphs of a given input graph. A general solution would be helpful, but I really only need this when the input is a subgraph of a 2D grid graph.

Of course, I want the size of the SAT instance to be polynomial in the size of the input graph, so that rules out ideas like encoding every path between each pair of vertices.

Edit: The answer I needed and accepted allows the use of extra variables to formulate a SAT instance.  Interestingly, @DavidEppstein shows that if no new variables are allowed, the required SAT instance cannot, in general, be found.

It's not possible if the variables are restricted to be only the given ones for the graph vertices. Consider a graph $G$ that has $2n+2$ vertices: $x$, $u_i$, $v_i$, and $y$ for $1\le i\le n$, formed by the union of $n$ edge-disjoint paths $x$--$u_i$--$v_i$--$y$. Also consider only the subgraphs that include both $x$ and $y$: if the whole graph has a small CNF formula for connected subgraphs, then so does this subset of subgraphs, obtained by setting the variables for $x$ and $y$ to true and then simplifying the formula.

The connected subgraphs that include both $x$ and $y$ do have a very simple $2$-DNF formula:
$$\bigvee\limits_{i=1}^n(u_i\wedge v_i).$$
However, when you convert this to its (unique) CNF form, it has $2^n$ terms (one for each way of excluding either $u_i$ or $v_i$ from the subgraph, for each $i$). So no polynomial-size CNF formula exists.

$G$ is not a grid graph but the same construction can easily be embedded into a grid by expanding $x$ and $y$ into larger connected subsets of grid points. As above, the whole graph can't have a small CNF formula, because if it did then you'd also have a small CNF formula for the connected subgraphs that include all the grid points representing $x$ and $y$, but we can write down the formula for this subset of the subgraphs and it does not have polynomial size.


Great algorithms, machine learning and no linear algebra I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of the currently most interesting/greatest algorithmic results in machine learning. The potentially tricky constraint is that the students will not have any particular previous knowledge of linear algebra or the other main topics in machine learning.

This is really to excite them about the topic and to let them know that ML is a potentially exciting research area for algorithms experts.

EDIT: This is a final year undergraduate course (as we don't have graduate courses in the UK in the main).  They will have done at least one basic algorithms course beforehand and presumably done well in it to have chosen the advanced follow up course. The current syllabus of the advanced course has topics such as perfect hashing, Bloom filters, van Emde Boas trees, linear prog., approx. algorithms for NP-hard problems etc.  I don't intend to spend more than one lecture exclusively on ML but if something is really relevant to both an algorithms course and an ML one then of course it could also be included.

You can cover boosting.  It's very clever, easy to implement, is widely used in practice, and doesn't require much prerequisite knowledge to understand.


Does approximation degree of AND depend on error? Denote $\underline{x}\triangleq x_1,\dots,x_n$.

Given a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, let $p_\epsilon(\underline{x})\in\Bbb R[\underline{x}]$ be minimum multilinear multivariate polynomial such that $|p_\epsilon(\underline{x})-f(\underline{x})|\leq\epsilon$ at every $\underline{x}\in\{0,1\}^n$.

Can following strict inequality hold for any boolean function $f$

$$deg(p_\epsilon)<deg(p_{\tilde\epsilon})$$ when $0<\tilde\epsilon<\epsilon<\frac{1}2$?

For example if you consider $AND(x_1,\dots,x_{1000})$, can you actually prove that there is a different approximation degree to approximate $AND(x_1,\dots,x_{1000})$ within error $\frac{1}3$ compared to error $\frac{1}{1000^{1000^{1000^{1000}}}}$?

Firstly it is well-known that the approximate degree of $\mathrm{AND}$ is $O(\sqrt{n})$:

Theorem 1. For all $n$ and $\varepsilon>0$, there exists a multilinear polynomial $p : \{\pm 1\}^n \to \mathbb{R}$ of degree $O(\sqrt{n}\log(1/\varepsilon))$ such that $|p(x)-\mathrm{AND}(x)|\leq \varepsilon$ for all $x \in \{\pm 1\}^n$.

Proof. We use the Chebyshev polynomials:

Fact. For all $\ell$ and $d$ there exists $p_{\ell,d} : [-1,1] \to \mathbb{R}$ of degree at most $d$ such that $|p_{\ell,d}(z)-z^\ell| \leq 2e^{-d^2/2\ell}$ for all $z \in [-1,1]$.
See Sachdeva-Vishnoi Theorem 3.3 for a proof.

We also have $$\left|\mathrm{AND}(x) - \left(\sum_{i=1}^n \frac{1-x_i}{2n}\right)^\ell\right| \leq \left(1-\frac{1}{n}\right)^\ell \leq e^{-\ell/n}$$ for all $x \in \{\pm 1\}^n$. Thus $$\left|\mathrm{AND}(x) - p_{\ell,d}\left(\sum_{i=1}^n \frac{1-x_i}{2n}\right)\right| \leq 2e^{-d^2/2\ell} + e^{-\ell/n}$$ for all $x \in \{\pm 1\}^n$.

Setting $\ell = n \log(3/\varepsilon)$, $d=\sqrt{2\ell \log(3/\varepsilon)}$, and $p(x) = p_{\ell,d}\left(\sum_{i=1}^n \frac{1-x_i}{2n}\right)$ proves the theorem. Q.E.D.

Now we show that the approximate degree of $\mathrm{AND}$ becomes the exact degree of $\mathrm{AND}$ (which is maximal) for some value of $\varepsilon>0$:

Theorem 2. For all $n$, there exists $\tilde\varepsilon>0$ such that no multilinear polynomial $p : \{\pm 1\}^n \to \mathbb{R}$ of degree strictly less than $n$ satisfies $|p(x) - \mathrm{AND}(x)|\leq \tilde\varepsilon$ for all $x \in \{\pm 1\}^n$.

Proof.
Let $\mathcal{P} \subset \mathbb{R}^{\{\pm 1\}^n}$ be the space of functions from $\{\pm 1\}^n$ to $\mathbb{R}$ that have degree strictly less than $n$.

Claim. $\mathcal{P}$ is closed with respect to the $\ell_\infty$ norm.
This follows from the fact that $\mathcal{P}$ is a linear subspace of $\mathbb{R}^{\{\pm 1\}^n}$. It is spanned by the multilinear monomials of degree strictly less than $n$.

Claim. $\mathrm{AND} \notin \mathcal{P}$.
The Fourier transform uniquely expresses $\mathrm{AND}$ in the multilinear monomial basis. We see that the degree is $n$:
$$\mathrm{AND}(x) = \prod_{i=1}^n \frac{1-x_i}{2} = \sum_{s \subset [n]} \frac{(-1)^{|s|}}{2^n} \prod_{i \in s} x_i.$$

Claim. $\exists \tilde\varepsilon>0~\forall p \in \mathcal{P}~\|\mathrm{AND}-p\|_\infty>\tilde\varepsilon$.
Since $\mathcal{P}$ is closed, its complement is open. $\mathrm{AND}$ is in the complement of $\mathcal{P}$ which means there exists a closed ball of positive radius $\tilde\varepsilon>0$ centered at $\mathrm{AND}$ that does not intersect $\mathcal{P}$.

The final claim is exactly the theorem.
Q.E.D.

Thus we have shown that there exists $\tilde\varepsilon>0$ such that $\mathrm{deg}_{\tilde\varepsilon}(\mathrm{AND})>\mathrm{deg}_{1/3}(\mathrm{AND})$.


compleixty of rational checking of eigenvalues Given a matrix $A$ with rational entries, how to check whether all the eigenvalues of $A$ are  rational?

What's the complexity of this problem? It seems that this can be done in polynomial time, but is there a tighter upper bound?

The problem is in P for the following reason.

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

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

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


Are shift-chains two-colorable? For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$.

For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$.

A $k$-uniform hypergraph ${\mathcal H}\subset [n]$ is called a shift-chain if for any hyperedges, $A, B \in {\mathcal H}$, we have $A\le B$ or $B\le A$. (So a shift-chain has at most $k(n-k)+1$ hyperedges.)

We say that a hypergraph  ${\mathcal H}$ is two-colorable (or that it has Property B) if we can color its vertices with two colors such that no hyperedge is monochromatic.

Is it true that shift-chains are two-colorable if $k$ is large enough?

Remarks. I first posted this problem on mathoverflow, but nobody commented on it.

The problem was investigated on the 1st Emlektabla Workshop for some partial results, see the booklet.

The question is motivated by decomposition of multiple coverings of the plane by translates of convex shapes, there are many open questions in this area. (For more, see my PhD thesis.)

For $k=2$ there is a trivial counterexample: (12),(13),(23).

A very magical counterexample was given for $k=3$ by Radoslav Fulek with a computer program:

(123),(124),(125),(135),(145),(245),(345),(346),(347),(357),

(367),(467),(567),(568),(569),(579),(589),(689),(789).

If we allow the hypergraph to be the union of two shift-chains (with the same order), then there is a counterexample for any $k$.

Update. I have recently managed to show that more restricted version of shift-chains are two-colorable in this preprint.

Permanent bounty! I'm happy to award a 500 bounty for a solution anytime!

This is not an answer.  What follows is a simple proof that the construction for k=3 is indeed a counterexample.  I think that the asker knows this proof, but I will post it anyway because the proof is nice and this might be useful when people consider the case of larger k.

It is easy to verify that it is a shift-chain.  Let’s show that it does not have Property B.

In fact, the subhypergraph {(123), (145), (245), (345), (346), (347), (357), (367), (467), (567), (568), (569), (789)} already fails to satisfy Property B.  To see this, suppose that this hypergraph has a 2-coloring and let ci be the color of the vertex i.  Look at three hyperedges (145), (245), (345).  If c4=c5, then all of 1, 2 and 3 must be the opposite color to c4, but this would give a monochromatic hyperedge (123).  Therefore, it must be the case that c4≠c5.  Similarly,

c3≠c4 by comparing the three hyperedges (345), (346), (347) and noticing a hyperedge (567).
c6≠c7 by comparing the three hyperedges (367), (467), (567) and noticing a hyperedge (345).
c5≠c6 by comparing the three hyperedges (567), (568), (569) and noticing a hyperedge (789).

Therefore, we have c3≠c4≠c5≠c6≠c7.  But this implies c3=c5=c7, making the hyperedge (357) monochromatic.  This contradicts the assumption of the 2-coloring.


Does XOR automata (NXA) for finite languages benefit from cycles? A non-deterministic Xor automata (NXA) is syntactically an NFA, but a word is said to be accepted by NXA if it has an odd number of accepting paths (instead of at least one accepting path in the NFA case).

It is easy to see that for a finite regular language $L$, there exists a minimal NFA which doesn't contain any cycles (if a cycle was both reachable from the initial state and you get from it to an accepting state - your language is not finite).

This is not necessarily the case for NXAs.

Denote by $xsc(L)$ the xor-state complexity of a language $L$,

and by $axsc(L)$ the acyclic xor state complexity of $L$ (i.e. the size of a smallest acyclic NXA which accepts $L$).

  Is it true that for every finite language $L$: $$axsc(L)=xsc(L)\ ?$$

I think that the answer is the affirmative.  Maybe there is a simpler proof, but here is a sketch of a proof which uses linear algebra.

Like domotorp, we will view a configuration of an n-state XOR automaton as a vector in V=GF(2)n.

Let L be a finite language over an alphabet Σ={1, …, k}, and consider an XOR automaton for L with the minimum number of states.  Let n be the number of states.  We assume that the states are labeled 1, …, n, and state 1 is the initial state.

First we set up the notation.  Let v0 = (1, 0, …, 0)T ∈ V be the elementary vector corresponding to the initial state, and let s be the row vector whose ith entry is 1 if and only if state i is an accepting state.  The subspace R = {v: sv=0} of V corresponds to the configuration vectors that are rejected.

For each a∈Σ, let Aa be the n×n matrix over GF(2) which represents the transition caused by letter a.  For example, the configuration vector after reading the input string ab is AbAav0.  For a string σ=a1…at, we denote the product Aat…Aa1 by M(σ).  Let S = {A1, …, Ak}.

A subspace W of V is said to be S-invariant when AW ⊆ W for every A∈S.  In our context, this means that once the configuration vector goes in W, there is no way out of W by reading more letters.

Because this XOR automaton has the minimum number of states, we have the following properties.

The only S-invariant subspace of V that contains v0 is V itself.  This is because if W is a proper S-invariant subspace containing v0, then we can use W in place of V, contradicting the minimality.
The only S-invariant subspace contained in R is {0}.  This is because if W is a nontrivial S-invariant subspace contained in R, then we can use the quotient vector space V/W in place of V, again contradicting the minimality.

Because L is finite, let m be an integer larger than the length of any string in L.

Lemma 1.  For any string σ of length at least m, we have that M(σ)=0.

Proof.  First we prove that for any string σ of length at least m, we have that M(σ)v0=0.  Let W be the subspace of V spanned by {M(σ)v0: σ is a string of length at least m}.  By definition, W is S-invariant.  Because the XOR automaton in question rejects these strings σ, W is contained in R.  Therefore W={0}, which means that M(σ)v0=0 for all such strings σ.

Now consider any vector v∈V.  Because the only S-invariant subspace of V that contains v0 is V itself, v can be written as a linear combination of vectors of the form M(τ)v0 for some strings τ.  Because M(σ)M(τ)v0 = M(τσ)v0 = 0 (the latter equality follows from the previous paragraph because the length of τσ is at least m), it holds that M(σ)v=0.  ■

We need one more fact from linear algebra.

Lemma 2.  Let A1, …, Ak be n×n matrices over a field, and define M(σ) as above.  If there is m≥0 such that M(σ)=0 for every string σ of length at least m, then the matrices A1, …, Ak are simultaneously similar to strictly lower triangular matrices (that is, there exists an n×n nonsingular matrix P such that the matrices P−1A1P, …, P−1AkP are strictly lower triangular).

The case of k=1 is a well-known characterization of nilpotent matrices, and Lemma 2 can be proved in the same way.

Now consider the n-state XOR automaton in which the transition matrix corresponding to symbol a∈Σ is given by P−1AaP, the initial configuration vector is given by P−1v0, and the characteristic (row) vector of the accepting states is given by sP.  By construction, this XOR automaton accepts the same language L.  Because the transition matrices are strictly lower triangular, every transition edge in this XOR automaton goes from a state with a smaller index to a state with a larger index, and therefore this XOR automaton is acyclic.  Although the initial configuration vector may have more than one 1s, it is easy to convert this XOR automaton to a usual XOR automaton with a single initial state for the same language without increasing the number of states or ruining the acyclicity.


Amortized time and worst case (non-amortized) separation Assume a reasonable computation model (thinking about pointer machine or RAM model), is there a problem where there is a clear separation between amortized and worst case complexity? Say, if amortization is not allowed and only worst case for each operation is considered, the time complexity will be (provably) higher. Notice that this is different from random self-reducibility.

Heapify is one example:
https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/
Another simpler example (Min / Max queue):
https://www.geeksforgeeks.org/design-a-queue-data-structure-to-get-minimum-or-maximum-in-o1-time/  . This is also discussed here (see Szymon's answer): https://stackoverflow.com/questions/12054415/get-min-max-in-o1-time-from-a-queue
And there are many more...


Why can Lambda Calculus not represent some combinators? This paper suggests that there are combinators (representing symbolic computations) that can not be represented by the Lambda calculus (if I understand things correctly):

There are several things that one may want to do in practice and that cannot be directly expressed in the lambda calculus.

The SF calculus is an example. Its expressive power is not news; the interesting part of the paper (not shown in the slides) is the category theory behind it. The SF calculus is analogous to a lisp implementation where you allow functions to inspect the representation of their argument — so you can write things like (print (lambda (x) (+ x 2))) ⟹ "(lambda (x) (+ x 2))".

Another important example is Plotkin's parallel or. Intuitively speaking, there's a general result that states that lambda calculus is sequential: a function that takes two arguments must pick one to evaluate first. It's impossible to write a lambda term or such that (or ⊤ ⊥) ⟹ ⊤, (or ⊥ ⊤) ⟹ ⊤ and or ⊥ ⊥ ⟹ ⊥ (where ⊥ is a non-terminating term and ⊤ is a terminating term). This is known as “parallel or” because a parallel implementation could make one step of each reduction and stop whenever one of the argument terminates.

Yet another thing you can't do in the lambda calculus is input/output. You'd have to add extra primitives for it.

Of course, all these examples can be represented in the lambda calculus by adding one level of indirection, essentially representing lambda terms as data. But then the model becomes less interesting — you lose the relationship between functions in the modeled language and lambda abstractions.


What is the run-time of the bin packing approximation algorithm? The best approximation algorithm that I found for the bin packing problem is by Hoberg and Rothvoss (SODA, 2017). In their Theorem 1.2, they mention that their algorithm finds a solution with at most $OPT + \log(OPT)$ bins,  and its expected run-time is polynomial in the total number of items. However, I could not understand from the paper, what is the exact polynomial? That is:  if there are $n$ items with different sizes, what is a number $k$ such that the run-time is in $O(n^k)$?

According to the definition of polynomial (from Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.):

An algorithm is said to be of polynomial time if its running time is
upper bounded by a polynomial expression in the size of the input for
the algorithm, i.e., T(n) = O(n^k) for some positive constant k.

In their Theorem 1.2 they say "The algorithm is randomized and the expected running time is polynomial". So their are meaning that the algorithm proposed is randomized (non deterministic), but its running time is polynomial, since is within a sum over the bins.


A balanced generalization of Hall’s theorem Let $X$ and $Y$ be sets, and $\mathcal{B}$ be a partition of $X \times Y$. I would like to prove that there exists a distribution $\mathcal{D}$ over $X \times Y$ whose marginal is uniform over $X$, and such that the distribution over $\mathcal{B}$ induced by $\mathcal{D}$ has large entropy(the latter distribution is defined by assigning each $B∈\mathcal{B}$ the total probability mass of the elements of $B$ under $\mathcal{D}$). We can use the following condition:

Consider the bipartite graph $G$ whose sides are $X$ and $\mathcal{B}$, such that for each $(x,y) \in B$ there is an edge $(x,B)$ in $G$ (multiple edges possible). Then, every set of $x$'s of size at least $\frac{3}{4}|X|$ has at least $\frac{1}{100}|B|$ neighbors in G.

I would appreciate it if someone could refer me to a relevant theorem. This question can be viewed in a sense as a generalization of Hall's theorem, where the above condition is a relaxation Hall's condition, and where instead of getting a perfect matching, we get a set of edges whose corresponding subgraph is roughly regular.

Background: The motivation for this questions comes from communication complexity. In the setting of communication complexity, two players, Alice and Bob, get inputs $x$ and $y$ respectively, and interact in order to compute some function $f(x,y)$. Here, each set $B \in \mathcal{B}$ consists of pairs $(x,y)$ that yield the same transcript of communication between Alice and Bob, and I would like to prove that under some condition, one can find a distribution over $X \times Y$ such that Alice gets a uniformly distributed input, and such that the entropy of the transcript under the distribution is large.

You might look into the concept of $f$-factors and specially Tutte's theorem on the existence  of $f$-factors. You might find Proposition 2 of this paper relevant.


Shortest simple path with minimum edge cost minus node reward I have a directed graph which has cycles.
Each edge has a nonnegative weight and each vertex has a nonnegative reward.

Given two vertices s and t, I need to find a simple path (a path with no repeated vertices) from s to t which minimizes

(sum of edge weights on the path) - (sum of vertex rewards covered by the path).

One can surely absorb node reward into edge weight like this post, but then the edge weight can become negative and negative cycles can emerge.  As a result, the shortest simple path, if posed in such a general setting, is NP-hard (eg this post).

However, some hints from submodular analysis suggest this problem is not NP-hard. Can we find an efficient algorithm?

Many thanks in advance.

Follow-up:

Please see this post for a "proof" which gave me the (wrong) hint.

As we discussed earlier, this can be solved by transforming your weighted edges-and-nodes graph to a normal weighted-edges graph: simply make the edge-weights in the new graph equal to the edge-weights in the old graph minus the reward of the node they point to.  This may lead to a graph with negative-cycles; and finding a simple path on such a graph is NP-Hard.

Unfortunately, the two problems are equivalent.  The transformation in the other direction is easy - given a directed weighted graph with negative cycles, you can turn it into a directed weighted-edges-and-nodes graph with no negative edges simply by setting the "reward" of each node to the lowest incoming edge, and subtracting that amount from all incoming edges.

Thus, your problem NP-Hard in the general case.  However, the sub-cases where the transformation in the first paragraph would generate a graph with no negative edge-cycles (ex. if, for instance, the node's reward is <= the least weight of an incoming edge) are in P.


PCP characterization of NP The PCP theorem (NP= PCP(log n, O(1)) )is a major result in complexity theory with many applications such as proving hardness of approximate results. However, it seems to me that it does not offer any insight that leads to separating P from NP or NP from coNP. My intuition is that P=NP would imply that coNP = PCP( log n, O(1)). That means Tautology instance has a proof that can be verified by an efficient probabilistic verifier using logarithmic random bits and reading only constant number of bits from a proposed proof. It seems that PCP theorem can not shed a light on why Tautology can not have such proof system.

  Why is the PCP characterization of NP not helpful in separating NP from coNP ( or from P)? Is there any known barrier?

** EDIT**: Provided context and motivation.

The PCP Theorem is a theorem about checking proofs, i.e. that there exist locally checkable proof systems, ones that don't "turn from non-accepting to accepting by changes that would be insignificant by any reasonable metric" (quote, top of page 2 here).

Simply stated, it's not directly related to "efficient computation" at all -- more of "efficient checking," for an appropriate definition of efficient.

I suppose it might be possible to use the machinery and terminology of PCPs to attack P vs NP, but it seems likely that such an argument would have a simpler statement under a different model and mode of thought to me. If nothing else -- I haven't seen any attempts in that direction.


What is the big version of NC? $\mathsf{NC}$ captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time $O(\log^c n)$ using $O(n^k)$ parallel processors for some constants $c$, $k$. My question is if there is an analogous complexity class where time is $n^c$ and number of processors is $2^{n^k}$. As a fill-in-the-blank question:

  $\mathsf{NC}$ is to $\mathsf{P}$ as __ is to $\mathsf{EXP}$

In particular, I am interested in a model where we have an exponential number of computers arranged in a network with polynomially bounded degree (lets say the network is independent of the input/problem or atleast somehow easy to construct, or any other reasonable uniformity assumption). At each time step:

Every computer reads the polynomial number of polynomial sized messages it received in the previous time step.
Every computer runs some polytime computation that can depend on these messages.
Every computer passes a message (of polylength) to each of its neighbours.

What is the name of a complexity class corresponding to these sort of models? What is a good place to read about such complexity classes? Are there any complete-problems for such a class?

I believe the class you are looking for is $PSPACE$. Suppose you have $exp(n^k) = 2^{O(n^k)}$ processors fitting the requirements:

  Every computer reads the polynomial number of polynomial sized messages it received in  the previous time step.
  Every computer runs some polytime computation that can depend on these messages.
  Every computer passes a message (of polylength) to each of its neighbours.

This can be modeled by having a circuit with $poly(n)$ layers, where each layer has $exp(n^k)$ "gates", and each "gate" does a polynomial time computation (satisfying part 2) with polynomial fan-in (satisfying part 1), and has polynomial fan-out (satisfying part 3).

Since each gate computes a polynomial time function, they each can be replaced by a polynomial size circuit (with AND/OR/NOT) in the usual way. Note the polynomial fan-ins and fan-outs can be made to be 2, by only increasing the depth by a $O(\log n)$ factor. What remains is a $poly(n)$ depth uniform circuit with $exp(n^k)$ AND/OR/NOT gates. This is precisely alternating polynomial time, which is precisely $PSPACE$.


Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols? Preamble.

The complexity class AM are those problems which can be solved by a two-round interactive proof system between a prover "Merlin" and a verifier "Arthur". A problem — which tests some property of an object X — is in AM if:

For YES instances, for a random "challenge" message (of polynomial length) Arthur generates, with high probability Merlin can formulate a (polynomial length) reply which Arthur can use as evidence that X has the property;
For NO instances, for a random challenge message Arthur generates, with high probability Merlin cannot formulate any reply which can be used as evidence for the property being tested for on X.

— The class described doesn't change if we require Merlin to give a useful answer not just with high probability, but for any challenge that Arthur may issue; we might say in this case that we require Merlin's answer always to be valid for YES instances, and what Arthur tests is the validity of the answer. So if Merlin ever produces an invalid response, Arthur knows that the problem instance is a NO instance. This is the setting I'd prefer to consider.

An example is Graph Non-Isomorphism: given graphs G and H with the same set of vertex labels, Arthur can randomly select one of the graphs and produce a "scrambled" version F by permuting its vertex labels, sending a presentation of it to Merlin. If the two graphs are non-isomorphic, Merlin can identify which of G or H Arthur chose by determining whether F ≅ G or F ≅ H, and can respond by identifying which of the two F is isomorphic to. If the two graphs G and H are isomorphic, however, Merlin cannot distinguish which graph F came from, and any answer he gives can only be correct by chance. Thus, for YES instances Merlin can always send a valid response to any challenge; for NO instances any  response which Merlin might send will be with high probability invalid.

In the above problem, not only does there exist a valid response that Merlin can issue to Arthur for each challenge, but in fact there is a unique valid response: i.e. indicate which of G or H Arthur chose, given that this can be determined by identifying which is isomorphic to F.

Question.

Does imposing a constraint along these lines — that for YES instances, for any challenge Arthur might send, there is exactly one valid response for Merlin — yield a more restrictive class, in the sense of yielding a class which is not known to equal AM?

Koiran's paper Hilbert's Nullstellensatz is in the Polynomial Hierarchy provides a public-coin Arthur-Merlin protocol for establishing that a system of $m$ equations on $n$ unknowns has a solution in $\mathbb{C}^n$, contingent on the Generalized Riemann Hypothesis.  Here Merlin finds a prime $p$ with $H(p)=0$ for some random hash $H$, along with a solution $(a_0,a_1,\cdots, a_n)$ to each of the $m$ equations $\bmod p$.

If the system of equations has no solution $\bmod p$, then there will only be a finite number of $p$ modulo which a solution exists.  If the system does have a solution $\bmod p$, then unconditionally there will be an positive density of $p$ with a solution, and the GRH allows that the $p$ with a solution are "equidistributed" in some sense, such that Merlin gets a win.

Although Koiran gives an example of a solvable system where the density of $p$ is exponentially small, Koiran suggests that if the system is solvable in $\mathbb{C}^n$, then in most cases there will be a large number of $p$ (and a large number of $a$); indeed about $1-1/e$ primes should have a solution IIRCC.

Thus, in the above problem, not only does there exist a valid response that Merlin can issue to Arthur for each challenge, but in fact there could be a large number of valid responses.

Distinguishing the easy systems of equations with solutions modulo many $p$ from the hard systems of equations with a few or only one $p$ seems to require determining properties of a Galois group of the system of equations.


Is prime-counting function #P-complete? Recall $\pi(n)$ the number of primes $\le n$ is the prime-counting function.  By "PRIMES in P", computing $\pi(n)$ is in #P.  Is the problem #P-complete?  Or, perhaps, there is a complexity reason to believe that this problem is not #P-complete?

P.S.  I realize this is a bit naive since somebody must have studied the problem and proved/disproved/conjectured this, but I can't seem to find the answer in the literature.  See here if you are curious why I care.

Some heuristic evidence: to the best of our knowledge  $\pi(n)$ looks like a simple function corrected by random fluctuations.  Thus I’d expect a poly-time machine with a $\pi(n)$ oracle to be no stronger than such a machine with a random oracle, and w.r.t. a random oracle $X$ adding a separate random oracle $Y$ to $\mathsf{P}$ gives $\#\mathsf{P}^X \not\subset \mathsf{P}^{XY}$ with probability 1 (here $Y$ corresponds to $\pi(n)$ and $X$ is an independent random oracle).


Online/approximate weighted and capacitated bipartite matching I wish to take a look at online/approximate weighted and capacitated bipartite matching problem.

Consider $G=\{L\cup R, E\}$, $|L|=n_1$, $|R|=n_2$, $|E|=m$ and $E\subseteq L\times R$. For each $r_i\in R$, it has capacity $c_i$ which means that at most $c_i$ nodes from $L$ can be matched to $r_i$. The objective function to maximize is $\sum_{i=1}^{n_2}x_iw_i$ where $x_i$ is the number of nodes in $L$ matched to $r_i$ and $w_i>0$ is the weight. The constraints are (1) $x_i\in\{0,...,c_i\}$, (2) any node in $L$ can be matched at most once and (3) any node $l_j$ is allowed to be matched to $r_i$ if $(l_j, r_i)$  $\in E$.

Is there any paper that solved the exact problem as I described above (provides either approximate or online algorithm)? To be clear, I am asking for references, and methods are not necessary.

I think there is no paper solving that exact problem, but "Online Vertex-Weighted Matching" by Aggarwal, Goel, Karande, and Mehta (2011) is very close. If I understood correctly, they solve your problem only with all capacities equal to one.

My best guess is that you will have to do some work to extend their guarantees and algorithm to your setting. On the other hand, a greedy algorithm probably should guarantee 0.5 of optimal by a standard argument: Consider the opt matching; for every "slot" in OPT left unmatched by greedy, there was some other match made that was more valuable (since the slot was available, its partner must have gone elsewhere). I hope you will forgive this discussion of methods contrary to your request.

(edit: I want to mention that this argument wouldn't work if the weights are on the arriving vertices; it's good to think about why.)


Kolmogorov complexity of D and D+d I'm looking into using of the shelf compression algorithm to approximate the Kolmogorov complexity of a document corpus D and the complexity of D+d, where d is an extra document. I've got a strange result where size(compress(D)) > size(compress(D+d)). Is this possible if compress actually calculated (the uncomputable) Kolmogorov complexity of D and D+d?

I'm no expert on Kolmogorov complexity, but I think it could happen; here is some intuition. The $D$ and $D + d$ are represented by two strings $S(D)$ and $S(D + d)$, and $S(D)$ is a prefix of $S(D + d)$. So you're asking whether a prefix of a string can have higher Kolmogorov complexity than the string itself. I think this is the case:

Let $P$ be some randomly generated string of high complexity. Now let $X$ be the result of repeating $P$ a number of times, say 10 times. Let $Y$ a prefix of $X$ that is some characters shorter. Then a program to output $X$ would just say "repeat string $P$ 10 times", whereas the program to output $Y$ would have to say: "repeat string $P$ 10 times, and then subtract a couple of characters from the end". If $P$ is sufficiently complex then the intuition is that indeed the shortest way to generate $Y$ would be in this way, hence the program that generates $X$ is shorter than the one which generates $Y$, and the Kolmogorov complexity of $X$ would be lower than of its prefix $Y$.


Necessary and sufficient conditions for the existence of a combinatorial algorithm for a given problem. Last semester, I took a combinatorial optimization course where the reference book was Combinatorial Optimization by William J. Cook et al. It was very interesting for me to see the relationship between some great algorithms (like disjktra's shortest path algorithm, edmonds' maximum matching algorithm ...) and LP duality.

My question is about a general framework on constructing combinatorial algorithms based on LP duality.

For a given problem what are the necessary and sufficient conditions for the existence of such algorithms. I think duality gap should be the first necessary condition and to have a totally unimodal matrix could be sufficient.

Maybe the answer is written in that book and I should read it again carefully.

Some people in combinatorial optimization use the word "combinatorial algorithm" to mean "algorithm without using ellipsoid method (or interior-point methods)."  For example, Schrijver's Fulkerson-prize-winning paper has a title "A combinatorial algorithm minimizing submodular functions in strongly polynomial time."  The co-winners (Iwata, Fleischer, and Fujishige) also have "A combinatorial strongly polynomial algorithm for minimizing submodular function."

As far as I see the field of combinatorial optimization, people there actually try to give an answer to the posed question, and still struggle.  Cunningham's survey "Matching, matroids, and extensions" (Mathematical Programming B91 (2002) 515-542) is a bit old by now, but you can see how generalizations of Edmonds' blossom algorithm and concepts on matroid lead to combinatorial polynomial-time algorithms for other problems.  Please note that the field has been advanced since the survey, and good sources are probably some papers from IPCO (Integer Programming and Combinatorial Optimization).

I would like to point out that an big open problem is to find a combinatorial algorithm for the maximum independent set problem for perfect graphs running in strongly polynomial time.


White elephant gift exchanges: mechanisms for fair division A popular game at holiday parties in North America is the white elephant gift exchange. In brief (ignoring variations) it works as follows:
There are $n$ people and $n$ wrapped gifts. Players are ordered arbitrarily. In the $i^{\text{th}}$ round, player $i$ either

chooses a wrapped gift and unwraps it as their present
"steals" one of the already opened gifts (from some player $k < i$).

If a player's gift is stolen, they now have the opportunity to do the same thing. A round is complete when a player chooses a wrapped gift.
While there are many variations in the system, one point to note is that the player going last has an unfair advantage because they alone are guaranteed the ability to choose any unwrapped gift.
THis falls under the class of fair-division methods pertaining to indivisible goods (unlike cake cutting).
My questions is:

Are there mechanisms for disbursing the gifts that are fair (in that
each player has the same opportunity to choose a high value gift under
their valuation) ?

Note that some flexibility will be needed in the definition of fair since the goods are indivisible and we are not introducing monetary compensation for players.

This isn't a complete answer, but it's an incomplete one.

Some background and related lit for those who aren't familiar --

A nice property would be envy-freeness, in which no player would like to trade with another after the mechanism is complete. Unfortunately, for indivisible goods and no money we can see that this is impossible (there might be one good that two people both think is best). The other common property is proportionality, where everyone gets what they consider to be a value of more than $1/n$; this is also clearly impossible to always obtain (there may be an item that nobody wants, but someone must end up with it).

[1] focuses on computing the minimum-envy allocation in an indivisible-goods scenario. They show that a minimum-envy mechanism cannot be truthful. However, we might still be able to design a game with a good price of stability (even though players aren't truthful).

[2] apply the criterion of "max-min fairness". The idea is to consider each player's valuation function over subsets of the items, normalizing it to one on the whole set, and to find the allocation which maximizes the minimum utility of any agent. Again, though, they don't consider our setting here with unit demand. Others study approximation algorithms for this problem, but I don't know if anyone has considered this restriction.

--

It's worth noting that usually notions of fairness are extremely worst-case: A mechanism is usually (perhaps not always?) considered envy-free if every player has a strategy that guarantees she will not envy any other's allocation. If she is playing to maximize her expected utility, she may or may not end up envious. Same goes for proportionality.

Because of this, it's tricky to try to relax these notions in a way that's natural when taken with this philosophical approach to fair division. It might be tempting to define a criterion like "ex-ante envy-freeness" where we hope to be envy-free in expectation (whatever that means). However, I think this would really be setting off on a whole new track from the current philosophy. If one were to do that, I think we should throw out notions of envy-freeness or proportionality altogether and start thinking about how expected-utility-maximizers would play these fair-division games in the first place.

Instead, we might try to extend the traditional approach in a more consistent way. One question would be how often (over the randomness of the mechanism) a player can guarantee herself a constant fraction of optimal utility. However, consider the case where only one of the $n$ items has any value; then any fair mechanism gives each player a constant-approximation to utility only $\frac{1}{n}$ of the time.

To get around this, I think we must consider ordinal criteria instead. I propose the following as a "natural" relaxation:

  A mechanism in our setting is $(\varepsilon,\delta)$-envy-free if with probability $1-\varepsilon$ an agent can guarantee herself one of her favorite $\delta n$ items.

Considering the case where everyone values each item the same amount, we see that no mechanism can possibly do better than $(\varepsilon,\varepsilon)$-envy-freeness here. (For any $\varepsilon$ -- Because only $\varepsilon n$ agents will get one of their $\varepsilon n$ favorite items.)

On the other hand, it is easy to see that your mechanism, if we order the players uniformly at random, is $(\varepsilon,\varepsilon)$-envy-free for all $\varepsilon$.[3]

I don't pretend that this captures nearly all the interesting questions about this setting or the white elephant mechanism. For example, the $(\varepsilon,\varepsilon)$-envy-free strategy for the second player is to take the first player's gift unless it is the worst of all the gifts. However, I think that this shows that our worst-case solution concepts simply don't capture a lot of what's interesting about these scenarios, so we should maybe think about something else like utility maximization instead.

--

[1] Lipton, Markakis, Mossel, Saberi. "On Approximately Fair Allocations of Indivisible Goods." EC 2004.

[2] Bezakova, Dani. "Allocating Indivisible Goods." SIGECOM 2005.

[3] Well, so is random serial dictator, but random serial dictator often has nice properties in theory. I'm also assuming that each item can only be stolen once per round.


Edge labeling in $K_{m,n}$ Background: I have been working on the following problem and was curious if this has come up before, what is it called in the literature, and what are previously tried methods? The motivation for working on this is involved with a certain sequence assembly problem I am working with in bioinformatics.

Problem:
Given a complete bipartite graph $G = (A, B, E)$ and positive integer weights, label edges (with non-negative integers) such that,

$\sum_j w_{ij} = w_i$

That is, for each vertex $i$, label incident edges such that their sum is equivalent to $w_i$.

Does a given instance have a solution?
(Sketch) Split each vertex $i$ with weight $w_i$ into $w_i$ copies of weight 1. So long as a perfect matching exists, we can solve the above equation.

How to solve?
Since the rank of bipartite graphs is $n - 1$ we can see that there exists a solution with at most $n - 1$ edges that will receive non-negative labels.

A simple greedy algorithm can produce a solution by simply matching the maximum vertices, labeling the edge as the min of the two, reducing the counts, and continuing on the remaining vertices.

But these solutions assume that the sums of the weights in $A$ and $B$ are equivalent. So how can we generalize when the weights are uneven? And furthermore, what if we want to maximize the number of 0 labelings?

Generalized Approach:
If we set weights in $A$ to positive values and weights in $B$ to negative values we may solve with a dynamic programming solution to minimize the absolute value of the sum of each connected component.

$\text{MinForest}(S, v) =
\begin{cases}
    \infty \text{ if } v \text{ is not valid in } S \\
    w(v) + min_{S’ = \text{ partitions of S with respect to r}} \text{MinForest}(S’ - \{r\}, i) \forall i \in S & \text{ otherwise}
\end{cases}$

where a vertex $v$ is valid iff $w(v) + \sum_{u \in \text{children}} w(u)$ is between 0 and $w(v)$. Any unlabeled edge will be assigned a value of 0.

Alternatives?
Now it appears similar to edge-graceful labelings, but without the modulo requirement. Are there other edge labeling problems similar to this? Additionally, do these current approaches seem sound?

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

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

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


How to shoot down your proofs What are general guidelines for checking your proofs? I believe this is important for graduate students like me. I already know what we need to do to prove something, but you always have to check everything before you send it out. Even to your own advisor.

I've developed myself some strategies by trial and error, and got a lot of advice from my advisor. But this is always a very tedious work. Normally, when you finish with something, you just want to go on to the next problem, but you still have to stick to the current problem until everything is perfect. Here I present an example of my own list of tricks:

Fill in the details. A lot of mistakes are in places were you write "it is clear that...", "without loss of generality...", etc.
Try some numbers. Try extreme cases, like "what happens when I set $n=1$ or $n=1000$".
Keep a clean notebook. Write every day on it, and compare it with your rough notes. I try to write also in latex, I've found many mistakes this way.

What are the general strategies that you apply for checking your proofs?

The objective of this question is to make it a community-wiki.

Software engineers have a notion they call "code smells".  These are symptoms in the code that may indicate a deeper problem.  Software engineers collect mental lists of smells to be aware of (i.e. excessively long methods or too many parameters).  It does not necessarily mean there is a problem, but simply indicate that the writer might want to double check.

I propose that we ought to also consider "proof smells".  This will not give you an algorithm for checking your proofs but it gives a language and a metaphor for recognizing possible problems in proofs.  Some examples of proofs smells:

The adverbs "Clearly", "Obviously", etc.
Reference to the proof of a previous result instead of a reference to the result itself.
Flippant use of a result with many technical preconditions.

There are also more subtle smells.  For example, if a proof uses the binomial theorem to expand an expression and then later uses the binomial theorem to return to a closed form, then maybe there is a direct manipulation on the closed form that gives the same result.

My suggestion is to collect a (mental or written) list of such smells and check for them as you read through your work.  The nice side effect of this approach is that it will also make you a better reader.

Note: My hope in this answer was to give intuitive side to the rigorous answer supplied by Lamport's How to Write a Proof referenced in M. Alaggan's answer.


Advantages of ANN classifiers over the AdaBoost So what are the advantages of ANN classifiers over the AdaBoost or Boosting algorithm?

from comments, by request:

In terms of running time, performance, something else? In terms of error rates, these two methods are hard to compare theoretically. AdaBoost's performance depends on the choice of a base learner and whether the weak learning assumption is satisfied in the particular instance. ANN will work for some problems/distributions but not others. I think this question would be better answered in a different forum.


Planar Graphs and Skew Binary Subspaces Let $G$ be a planar triangulation on $3m$ edges and $m+2$ vertices. Let $A$ be the binary matrix obtained from the incidence matrix of $G$ by deleting a row (equivalently the rows of $A$ form a basis of the cocycle space of $G$ over $GF(2)$).

My question is: What additional criteria must be assumed (if any) to guarantee there is an $(m-1)$-dimensional subspace of $GF(2)^{m+1}$ which does not contain any column of $A$?

Any relevant references would be much appreciated.

The question has been resolved by Chris Godsil on Maths Overflow. I repost it here for completeness:

What follows is all quite standard, iirc it's in Aigner's book "Combinatorics" but my copy's out on loan....

Let $B$ be the vertex-edge incidence matrix of the graph. (Nothing's gained by deleting a row.) We want a subspace of codimension two in $GF(2)^{m+2}$ containing no column of B. If a and b are distinct non-zero vectors indexed by the vertices of $G$ and $x$ is a column of $B$, we have a map $\rho _{a,b}$ that sends $x$ to $(a^Tx,b^Tx)$ and $a^⊥∩b^⊥$ is a subspace of codimension two that does not contain a column if and only if $0$ is not in the image of $ρ_{a,b}$.

If we identify $V(G)$ with the standard basis for $GF(2)^{m+2}$ then the map that assigns the vector $ρ_{a,b}(ei)$ to the vertex $i$ is a proper 4-colouring of the vertices of $G$, as you can easily check. Hence a necessary condition is that $G$ be 4-colourable.

On the other hand, if $G$ is 4-colourable then we can colour it with the four elements of $GF(2)^2$. Let $a$ be the vector such that $a_i$ is the first coordinate of the colouring of the vertex $i$ and let $b$ be the vector such that $b_i$ is the second coordinate. The $ρ_{a,b}(e_i+e_j)≠0$ if $ij∈E(G)$ and so the kernel of $ρ_{a,b}$ is a subspace of codimension two that does not contain a column of $B$. (If $a=b$ we have a 2-colouring, which is impossible.)

So your question is equivalent to the 4-color theorem.


Reconstruction of a sequence generated by a Markov chain - reference request Let S be a finite sequence of symbols from a finite alphabet, with gaps - that is on some known locations an unknown number of symbols are missing. Assuming that the sequence , including the symbols in the "gaps", is generated by a Markov chain on the alphabet's symbols with an unknown transition matrix, the problem is to design an efficient algorithm that will fill (almost) correctly the gaps , with high probability . More formally , the output sequence must be close (in edit distance , for example) to one of the most  probable sequences, given S and the model. The algorithm receive only the sequence S and must output a new sequence S' generated by filling the gaps in S .

Was this problem or a close variation of it solved ?

This seems to be an important and solvable problem, but I was not able to find any reference . I have some ideas on how to proceed , but I don't want to waste my time on some known result.

I'm imagining the problem can have occurred in bioinformatics or communication theory.

If the number of gaps is small, you can do the following brute force approach. Try every possible way of filling those gaps (there will be exponentially many possibilities, in the number of the gaps). For every "guess", fill in the gaps accordingly and train a maximum-likelihood Markov chain on the full sequence. You can even guarantee something about the convergence of the MLE estimator for MC's:
http://proceedings.mlr.press/v98/wolfer19a.html

Having computed the maximum likelihood model -- together with its likelihood score -- pick the highest-scoring possibility of filling the gaps.

I don't know if there's an efficient (say, dynamic-programming-based) algorithm for doing this when the number of gaps is large.


How hard is it to count the number of factors of an integer? Given an integer $N$ of length $n$ bits, how hard is it to output the number of prime factors (or alternatively number of factors) of $N$?

If we knew the prime factorization of $N$, then this would be easy. However, if we knew the number of prime factors, or the number of general factors, it is not clear how we'd find the actual prime factorization.

Is this problem studied? Are there known algorithms that solve this question without finding the prime factorization?

This question is motivated by curiosity and partially by a math.SE question.

This isn't my answer, but Terrence Tao gave a beautiful answer to this question on MathOverflow.

Here are the first few lines of his answer. To read the complete answer, follow the link.

  There is a folklore observation that if one was able to quickly count the number of prime factors of an integer n, then one would likely be able to quickly factor n completely. So the counting-prime-factors problem is believed to have comparable difficulty to factoring itself.

(I wasn't sure whether this should be an answer or a comment. But it is really an answer, although it isn't written by me. I've made the answer Community Wiki so that it may be upvoted or accepted without unnecessarily giving me reputation.)


Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$) In a read-twice opposite CNF formula each variable appears twice, once positive and once negative.

I'm interested in the $\oplus\text{Rtw-Opp-CNF}$ problem, which consists in computing the parity of the number of satisfying assignments of a read-twice opposite CNF formula.

I was unable to find any reference about the complexity of such problem. The closest I was able to find is that the counting version $\#\text{Rtw-Opp-CNF}$ is $\#\text{P}$-complete (see section 6.3 in this paper).

Thanks in advance for your help.

Update 10th April 2016

In this paper, the $\oplus\text{Rtw-Opp-SAT}$ problem is shown to be $\oplus\text{P}$-complete, however the formula produced by reduction from $3\text{SAT}$ is not in CNF, and as soon as you try to convert it back into CNF you get a read-thrice formula.
The monotone version $\oplus\text{Rtw-Mon-CNF}$ is shown to be $\oplus\text{P}$-complete in this paper. In such paper, $\oplus\text{Rtw-Opp-CNF}$ is quickly mentioned at the end of section 4: Valiant says it is degenerate. It is not clear to me what being degenerate exactly means, nor what does it imply in terms of hardness.

Update 12th April 2016

It would be also very interesting to know if anyone has ever studied the complexity of the $\Delta\text{Rtw-Opp-CNF}$ problem. Given a read-twice opposite CNF formula, such problem asks to compute the difference between the number of satisfying assignments having an odd number of variables set to true and the number of satisfying assignments having an even number of variables set to true. I've not found any literature about it.

Update 29th May 2016

As pointed out by Emil Jeřábek in his comment, it is not true that Valiant said that the problem $\oplus\text{Rtw-Opp-CNF}$ is degenerate. He only said that a more restricted version of such problem, $\oplus\text{Pl-Rtw-Opp-3CNF}$, is degenerate. In the meanwhile, I continue to not know what degenerate exactly means, but at least now it seems clear that it is a synonym of lack of expressive power.

It turns out that every opposite-read-twice formula has an even number of satisfying assignments. Here's a nice proof of it, though one could probably eliminate the graph-theoretic terminology.

Let $\phi$ be an opposite-read-twice CNF formula. Without loss of generality, no clause contains both a variable and its negation.

Consider the graph $G$ whose vertex set is the clauses of $\phi$, and for each variable $x$, we add an (undirected) edge that is incident on the two clauses containing $x$. Our WLOG assumption in $\phi$ says this graph has no self-loops. Moreover, think of labeling each edge by the variable defining it; this way we can distinguish between parallel edges.

An orientation of $G$ is a directed graph whose edges are formed by assigning a direction to each edge in $G$. Call an orientation of $G$ admissible if every vertex of $G$ has an outgoing edge. It's easy to see that satisfying assignments to $\phi$ are in bijective correspondence with admissible orientations of $G$.

Now I claim that the number of admissible orientations of $G$ is even. The argument is "by involution": I construct a map $\Phi$ with the following properties:

$\Phi$ is totally defined (every admissible orientation is mapped somewhere)
$\Phi$ sends admissible orientations to admissible orientations
$\Phi$ is an involution ($\Phi \circ \Phi$ is the identity)
$\Phi$ has no fixed points

Once these are established, we can observe that the orbits of $\Phi$ have size 2 and partition the admissible orientations of $G$. It follows that the number of admissible orientations is even.

To define $\Phi$, let $\vec{G}$ be an admissible orientation, and consider breaking $\vec{G}$ into it's strongly connected components. $\Phi$ then sends $\vec{G}$ to the orientation formed by reversing all the edges within the strongly connected components. The properties are then straightforwardly checked:

Every directed graph can be partitioned into strongly connected components.
Consider the "DAG of strongly connected components" in $\vec G$; call it the quotient graph. Note that $\Phi(\vec G)$ will have the same quotient structure, since $\Phi$ doesn't affect the edges between SCCs, and strongly connected graphs remain strongly connected when reversing all their edges. Additionally, if a SCC has more than one vertex, then all its constituent vertices have an incoming edge. If an SCC has just a single vertex and isn't a source in the quotient, then all its constituent vertices have an incoming edge. So to show $\Phi(\vec G)$ is admissible, it suffices to show that the SCCs which are sources in the quotient have multiple vertices. But this follows by the fact that every vertex in the component has an incoming edge, which must come from another vertex in the component since $G$ has no self-loops and the component is a source in the quotient.
This follows from the fact that the quotient structure of $\Phi(\vec G)$ coincides with the quotient structure of $\vec G$.
By admissibility, $\vec G$ has a cycle, and hence some SCC with an edge inside it.


Greedy vs LP Approximation I wanted to know whether Greedy approximation algorithms can outperform LP relaxation and rounding based algorithms. Specifically, can it beat the integrality gap of a 'reasonable' LP relaxation, (e.g. the natural relaxation of the ILP by relaxing variables $x_i\in\{1,0\}$ to $x\geq 0$).

For an example, if we consider the Setcover problem with universe set $U$ s.t. $|U|=n$ with max frequency of an element $f$, the greedy algorithm gives an $O(\mathrm{log}~n)$ approximation. Whereas LP relaxation can give an $f$ approximation with deterministic rounding. But we know that the integrality gap is $\Omega(\mathrm{log}~n)$ for the general LP formulation. Indeed through a randomized rounding technique we can achieve a $O(\mathrm{log}~n)$ approximation w.h.p. So the greedy is almost as good as the LP relaxation.

Does anyone know of an instance of NP Hard problem having approximations using greedy algorithm which is better than the integrality gap? Please point out the references if known. It will be great if the problem is well studied.

Well, there are cases where LP gives you no useful information. Consider a graph $G$ with $n$ vertices, and the problem of finding a maximum independent set in $G$. The LP gives you a solution of value at least $n/2$ (give every vertex a value of $1/2$). But the optimal independent set might be of size between $1$ and $n$.

On the other hand, the greedy algorithm does give useful results in some cases. For example, if the number of edges is $m \ll n^2$, then the greedy algorithm would give you an independent set of size $\Omega(n^2/m)$ (always pick the vertex that has the smallest numbeer of neighbors).


A good exposition of the random restriction method I'm wondering if there are good references that describe the random restriction method as a lower bound technique ? I'm aware that it's linked to the switching lemma and shows up in many different proofs, but I'm looking for a more or less self-contained explanation of the idea.

A relatively simple setting to illustrate the method of random restrictions is Subbotovskaya's original application of the method to prove an $\Omega(n^{1.5})$ lower bound on the formula size of the parity function, where formulas use arity-2 AND and OR operations. Section 6.3. of Jukna's Boolean Function Complexity has a nice exposition. Also, see these lecture notes from Swastik Kopparty's class in Rutgers.


Are there any open problems concerning decidability? I am learning computability theory. I am just interested to know some famous problems (Formally languages) whose decidability is in question.

Given a finite automaton A over the alphabet {0,1}, does A accept the base-2 representation of at least one prime number?   This is currently not known to be either decidable or undecidable.

(By contrast, the same problem with "prime" replaced by "composite" is decidable.)


Can the halting problem be solved probabilistically? Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random source.
$
\def\pp{\mathbb{P}}
$
Can a probabilistic program solve the halting problem with probability more than $1/2$ for each input? That is, is there a probabilistic program $G$ such that $\pp( \ G(P,X) = H(P,X) \ ) > 1/2$ for every $P,X$? (Note that this in particular requires $G$ to halt with probability more than $1/2$.)
If $G$ always halts, and the random source is a fair coin, then this is impossible, because $G$ can only access the random source a certain number of times that is determined by the inputs (by weak Konig lemma), and so we can translate $G$ to an ordinary (non-probabilistic program) that solves the halting problem.
But my question is about the case where $G$ is not required to always halt, and the above argument fails. Also, in this case we can assume that the random source is a fair coin, since any other random source whose $k$-th output is a string drawn from a distribution computable from its previous outputs can be simulated using a fair coin with halting probability $1$.
Note that the strict bound of "$> 1/2$" is necessary, otherwise there is the obvious trivial solution. And note that I do not require the probability of success to be bounded away from $1/2$. The cases in this post do not cover my question, and I am unable to find any answer on the internet.

It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $>1/2$, the algorithm outputs the correct answer (and therefore halts), but we allow the existence of infinite runs where the algorithm uses infinitely many random bits.
Indeed, by $\sigma$-additivity of the probabilistic measure, for any input $x$, there exists $n$ such that with probability $>1/2$, the algorithm computes the right answer within $n$ steps. Thus, we can find the answer deterministically as follows: for $n=1,2,3,\dots$, we simulate the algorithm for $n$ steps using all possible sequences of random bits (necessarily of length $\le n$) to count the probability that it halts with any particular answer; sooner or later, we find an $n$ and an answer that’s output with probability $>1/2$ within $n$ steps, and then we declare the winner.


Intersection graphs of squares and rectangles Is it known if the class of intersection graphs of rectangles is equal to the class of intersection graphs of squares (not necessarily unit)?

See "Squarability of rectangle arrangements", Konečný, Kučera, Opler, Sosnovec, Šimsa, and Töpfer, CCCG 2016. In particular their Theorem 6 proves for all $d$ the existence of graphs with boxicity 2 and cubicity $d$.


Forbidden minors for bounded treewidth graphs This question is similar to one of my previous questions. It is known that $K_{t+2}$ is a forbidden minor for graphs of treewidth at most $t$.

  Is there a nicely-constructed, parameterized, infinite family of graphs (other than complete graphs and grid graphs) that are minimal forbidden minors for graphs of every treewidth. In other words, is there an explicit graph $G_r$ on $r$ vertices (which is not a complete graph) such that $G_r$ is a forbidden minor for graphs of treewidth at most $r$, where $r$ is a function of $t$ ?

The complete sets of forbidden minors are known for graphs of treewidth at most three. See this Wikipedia article for more details.

  Is the complete set of forbidden minors of graphs of treewidth at most four known ?

In Sparse obstructions and exact treewidth determination, Lucena states that in the PhD thesis of Sanders, "75 or so minimal forbidden minors for treewidth $\leq 4$ are given, and it is believed though not proven that this may constitute the entire obstruction set."


Universal Turing Machines in "Computational Complexity" by Papadimitriou The first part of this question has been solved (see comments).

In the book "computational complexity" by Papadimitriou, a Universal Turing Machine is given. But this machine is not concrete, in the sense that it contains variable parameters. For example, the states of the input Turing Machine are represented as binary strings of fixed length. Hence, no matter how long we let this length be, there will always be Turing Machines with so many states that they cannot be represented. Can this machine then really be called a UTM, or at least a template for a UTM?

I also read that a 2-state, 3-symbol UTM has been discovered. This would mean that the action table contains only 6 entries. Am I right in my conjecture that such a machine must have a very complex encoding of the input TM?

In response to your second question, you are correct -- a 2-state, 3-symbol state TM was shown to be universal by then-undergraduate Alex Smith in 2007 by reduction to a universal cyclic tag system, which makes for a complex encoding.  Here's the original proof, which uses Wolfram's nonstandard notation for representing Turing Machines.

It's easy to intuit why simpler universal Turing Machines require more complicated encodings -- after all, the information involved in the computation needs to go somewhere.  For example, in the encoding scheme implicit in Smith's proof, we would first need to first encode the Turing Machine under simulation within a cyclic tag system, then use Smith's scheme to represent the cyclic tag system within the 2-3 Turing Machine.


Max Sum Product Multi-objective Shortest path problem Is anything known about the following problem:

I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1.
A path is first assigned a vector, which is the component-wise product of the weights of the edges along the path.
The path is then assigned a value, which is the sum of the entries of this vector.
I am interested in the maximum path.

More specifically, I consider the following decision problem: given a graph, a source, a target and a threshold c in (0,1), does there exist a path from the source to the target whose value beats the threshold c?

Is this problem in PTIME or NP-complete?

It seems NP-complete even with weights in $\{0,1\}$.
I reduce from the MINSAT problem: given a SAT instance, find an assignment that minimizes the number of satisfied clauses.
More precisely, an instance is a CNF formula, and an integer $k$, and you have to say whether there is an assignment satisfying at most $k$ clauses.
It is shown to be NP-complete in this paper.

Start from a MINSAT instance with variables $x_1\dots x_n$ and clauses $C_1\dots C_m$, we build an instance of your problem.
The weight vector has $m$ coordinates (the number of clauses).
The first edge of the graph puts every coordinate to $1$.
Then we traverse $n$ nodes where you have to choose the truth value of the variables $x_1\dots x_n$. For instance if you set $x_i$ to true, the corresponding edge vector contains a $0$ for each clause $C_j$ where $x_i$ appears positively and $1$ elsewhere.
The idea is that a clause is set to $0$ if the assignment makes it true. Since you use the product to evaluate a path, $0$ is absorbing and corresponding to the wanted disjunction.
Finally, you have a path from the source to the target with weight at least $m-k$ if and only if there is an instanciation of variables satisfying at most $k$ clauses.

Reference: The Minimum Satisfiability Problem, Kohli, Krishnamurti, Mirchandani in Journal SIAM Journal on Discrete Mathematics 1994


What languages have been successfully cryptographically trapdoored? An observation associated with asymmetric cryptography is that some functions are (believed to be) easy to perform in one direction but difficult to invert. Furthermore, if there exists some 'trapdoor' information that allows the inverse operation to be computed quickly then the problem becomes a candidate for a public key cryptography scheme.

Classic trapdoor problems, made famous by RSA, include the factoring problem and the discrete log problem. Around the same time that RSA was published, Rabin invented a public key cryptosystem grounded on finding discrete square roots (this was later proved to be at least as difficult as factoring).

Other candidates have cropped up over the years. KNAPSACK (soon after RSA), Elliptic Curve "Logarithms" with specific parameters, and Lattice Shortest Basis Problems are examples of problems whose trapdoor problems used in other published schemes. It is also easy to see that such problems must reside somewhere in NP.

This exhausts my knowledge of trapdoor functions. It also seems to exhaust the list on Wikipedia as well.

I am hoping that we can get a community wiki list of languages that admit trapdoors and relevant literature. The list will be useful. Evolving demands of cryptography also change which trapdoor functions can be the basis of cryptosystems. The explosion of storage on computers makes schemes with large keysizes possible. The perpetual-looming spectre of Quantum Computing invalidates schemes that can be broken with an oracle for finding hidden abelian subgroups. Gentry's Fully Homomorphic Cryptosystem works only because we've discovered trapdoor functions that respect homomorphisms.

I am especially interested in problems that are not NP-Complete.

It is important to distinguish between trapdoor functions and public-key encryption. While trapdoor functions do yield public-key encryption schemes, some of the candidates you mentioned are only known to imply public-key encryption and do not necessarily give you trapdoor functions. In fact, Gertner, Malkin and Reingold show that there is no black-box construction of a trapdoor function from a "trapdoor predicate" (which can be thought of as a one-bit public-key encryption scheme).

Classical examples of trapdoor functions are the RSA and Rabin functions. A classical example of a trapdoor predicate is deciding Quadratic Residuosity modulo a composite, due to Goldwasser and Micali. The discrete-log and lattice based constructions that you mention yield public-key encryption directly, without going through trapdoor functions.

Below is a (non comprehensive) list of constructions of public-key encryption schemes, most of which are not known to go through trapdoor functions.

El Gamal public-key cryptosystem (including elliptic curve variants). Security is based on the Decisional Diffie Hellman assumption. Doesn't go throuhg trapdoor functions (but see the Peikert-Waters item below for a trapdoor function whose security is based on the semantic security of El Gamal).

[Taher El Gamal: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. CRYPTO 1984: 10-18]
Ajtai-Dwork, Regev. Security is based on unique SVP in lattices. Not known to imply trapdoor functions.

[Miklós Ajtai, Cynthia Dwork: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. STOC 1997: 284-293]

[Oded Regev: New lattice based cryptographic constructions. STOC 2003: 407-416]
Regev, Peikert. Security is based on hardness of learning with errors (this includes a reduction from SVP). Not known to imply trapdoor functions.

[Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. STOC 2005: 84-93]

[Chris Peikert: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. STOC 2009: 333-342]
Peikert, Waters. Security is based on decisional Diffie Hellman and on lattice problems. Known to imply trapdoor functions (through lossy trapdoor functions).

[Chris Peikert, Brent Waters: Lossy trapdoor functions and their applications. STOC 2008: 187-196]
Lyubashevsky, Palacio, Segev. Security is based on Subset-Sum. Not known to imply trapdoor functions.

[Vadim Lyubashevsky, Adriana Palacio, Gil Segev: Public-Key Cryptographic Primitives Provably as Secure as Subset Sum. TCC 2010: 382-400]
Stehlé, Steinfeld, Tanaka, Xagawa, and Lyubashevsky, Peikert, Regev. Security is based on hardness of ring LWE. The advantage of these over previous proposals is their smaller key size. Not known to imply trapdoor functions.

[Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa: Efficient Public Key Encryption Based on Ideal Lattices. ASIACRYPT 2009: 617-635]

[Vadim Lyubashevsky, Chris Peikert, Oded Regev: On Ideal Lattices and Learning with Errors over Rings. EUROCRYPT 2010: 1-23]


Characterising invisible equivalences by confluent rewrite rules In response to another question, Extensions of beta theory of lambda calculus, Evgenij offered the answer:

beta + the rule {s = t | s and t are closed unsolvable terms}

where a term M is solvable if we can find a sequence of terms such that M's application to them is equal to I.

Evgenij's answer gives an equational theory over the lambda calculus, but not one characterised by a reduction system, i.e., a confluent, recursive set of rewrite rules.

Let's call an invisible equivalence over a theory of the lambda calculus, a reduction system that equates some nontrivial set of closed unsolvable lambda terms, but doesn't add any new equations involving solvable terms.

Are there any invisible equivalences over the beta theory of the lambda calculus?

Postscript An example that characterises an invisible equivalence, but is not confluent.  Let M=(λx.x x) and N=(λx.x x x), two unsolvable terms.  Adding the rule rewriting N N to M M induces an invisible equivalence containing M M = N N, but has the bad critical pair where N N reduces to both M M and M M N, each of which has one rewrite available, which rewrites to itself.

Yes.  With M=(λx.x x) per the question, consider the rewrite ζ that takes M M p to M M.

It is confluent, and so characterises a reduction system over the lambda calculus.  Argument sketch for confluence: since M M is closed, we only need to consider critical pairs of the form M M N1 ... Nk.  These can be resolved.

It is an invisible equivalence, because terms of the form M M I ... I (with zero or more I s) are closed unsolvable terms that reduce only to themselves in the base lambda calculus, thus are distinct, and so the infinite set of these terms is nontrivial, and is obviously equated by ζ.

I don't like accepting my answer to my question, so I'll accept an answer from someone who provides a less absurdly incomplete confluence argument.


Calculating the instantaneous period of a wave I have a set of data which represents slightly imperfect waves of varying amplitudes and periods. I wish to calculate the instantaneous period of the wave around any point within this data set - simply finding the local minima and maxima representing each individual wave and calculating the frequency of these is not precise enough for my needs.

Is there a known algorithm that can achieve this? Even better, an existing implementation of this algorithm? I am currently programming in R, but am willing to switch if needed.

n.b. if this is the wrong StackExchange site for this question, please direct me to a better one.

The instantaneous frequency of a wave is defined as $f(t) = \frac{1}{2\pi}\frac{d\phi}{dt}$ where $\phi$ is the instantaneous phase. See the Wikipedia page on Instantaneous Frequency.

Presumably you have discrete data, in which case you need to estimate $\phi$ and its derivative numerically.

This isn't an entirely meaningful measure, since it doesn't make very much sense to ascribe a frequency to a non-periodic function, but nonetheless there does seem to be a convention for it.

Let me close by saying that I don't consider this a TCS problem. It is firmly in signal processing territory, and so I wouldn't consider here the ideal venue for such questions.


Universal Boolean Formulas Fix $n\in\mathbb{N}$. Consider a rooted binary tree $T$ in which every non-leaf node contains either AND-gate or OR-gate. Let me say that $T$ is an universal formula if for every $f\colon\{0,1\}^n\to\{0, 1\}$ we can assign literals to the leafs of $T$ in such a way that the resulting formula computes $f$.

  What is the minimal size of universal formula?

There is an obvious lower bound $\Omega\left(\frac{2^n}{\log(n)}\right)$ as a tree of size $L$ can compute at most $(2n)^L = 2^{L \cdot \log_2(2n)}$ different Boolean functions. On the other hand, as far as I can see, there is an upper bound $O(2^n)$. Namely, one can take $(n+2)$-bit communication protocol for the universal relation from [1] and transform it into an universal formula via Karchmer-Wigderson correspondence [2].

One more related work is [3], where a different notion of universality is considered. Instead of fixing gates we fix literals and we want that for any $f$ it is possible to assign gates to non-leaf nodes in such a way that the resulting formula computes $f$. There is an obvious lower bound $\Omega(2^n)$ (as there are now 2 choices for every node) and [3] constructs a matching $O(2^n)$ upper bound.

In [1] it is also stated that their protocol improves and simplifies the result of [3]. I don't see why. An explanation would be greatly appreciated.

References

[1] G. Tardos, U. Zwick. The communication complexity of universal relation. Proc. 12th Computational Complexity Conference, pp. 247-259 (1997).

[2] M. Karchmer, A. Wigderson. Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2), pp. 255-265 (1990).

[3] W.F. McColl, M.S. Paterson. The depth of all Boolean functions. SIAM Journal on Computing, 6(2), pp. 373-380 (1977).

Update

Some clarifications: actually in [3] all possible bivariate gates are allowed, not only AND, OR gates. Then it becomes clear why [1] implies [3]. Moreover, it seems that [1] gives a stronger object. Namely, one can get from it a DeMorgan formula $F$ of size $O(2^n)$ such that for any $f\colon\{0, 1\}^n \to \{0, 1\}$ we can change in some leafs of $F$ the corresonding literals to opposite ones so that the resulting $F^\prime$ computes $f$.

A $O(2^n/\log n)$-size depth-3 universal Boolean formula was constructed in

  O.B. Lupanov. Complexity of the universal parallel-series network of
  depth 3. Trudy Matem. Inst. Steklov, 133:127-131, 1973 (In Russian)

In this paper Lupanov uses language of parallel-series networks, which is equivalent to De Morgan formulas with unbounded fan-in AND, OR gates (parallel connection of two networks corresponds to disjunction and series connection corresponds to conjuction).


Complexity class separation in the presence of relativization barriers Give an example of complexity classes $M$ and $N$ and oracles $A$ and $B$ such that
 1. $M^A=N^A$ and
 2. $M^B\neq N^B$ and
 3. $M \neq N$.

H. Buhrman, L. Fortnow, and T. Thierauf. Nonrelativizing separations. In Proceedings of the 13th IEEE Conference on Computational Complexity, pages 8-12. IEEE, New York, 1998. (also from Lance's homepage).  They show unconditionally that $MA_{EXP} \not\subseteq P/poly$, and also build an oracle relative to which $MA_{EXP} \subseteq P/poly$.


Existence of zero-knowledge proof for location N items have been placed at specific points on a map. A prize is awarded to the first person who turns in a list with the location of all N items. The location of each item must fall with a distance error of E.

Player 1 has J locations where $$J < N$$

Player 2 has K locations where $$K < N$$

And for this problem we assume $$(J + K) > N$$

Players 1 and 2 agree to pool their locations to win the prize, but not before they each determine that they have the location of all N items. i.e. $$ J \bigcup K = N $$

Each player wants proof that the other player has some number of locations which they themselves do not have.

Is it possible for a player to prove to the other that they have a location that the other player does not have without disclosing that location?

I call my best guess the triangle game (or sub-game if your prefer)
Here is one round of Player 1 trying to prove a location to player 2.

Player 1 picks a point on the map x1,y1
Player 2 picks a point on the map x2,y2 and a condition 'player 1's point will be in the triangle formed by x1,y1 x2,y2 and x3,y3'
Player 1 picks a point on the map x3,y3 for which at least one his points falls inside the triangle

The condition in step 2 may also be 'player 1's point will not be in the triangle formed by x1,y1 x2,y2 and x3,y3'.

Player 2 will try to pick a point and a condition such that he can confirm that Player 1's point is not one of his K points.

The players may have to play this triangle game many rounds in order to verify a point.

This problem is based on the DARPA Network Challenge

N items=10 red balloons
map=the continental United States
prize=$40,000
distance error of E < 1.0 mile

I think part of the problem you are having finding a solution is that you are using the wrong name for this concept. While it is indeed closely related to the idea of a zero knowledge proof, this type of protocol, accepting input from multiple parties, is known as either Secure Function Evaluation or Secure Multi-Party Computation.

Let's first simplify the game and assume it is played on a lattice, so that the points are discrete. It seems to me that you simply wish to compute $|J \cup K|$. Trivially, this is equal to $|J \cup K| = |J| + |K| - |J \cap K|$. Now, I assume you do not mind each party learning the number of locations the other party holds. In this case, $|J|$ and $|K|$ are public. In this case all that is required to determine $|J \cup K|$ is $|J \cap K|$. Now, if we think of the inputs of Player 1 (henceforth Alice) and Player 2 (henceforth Bob) as being a vector of length equal to the total number of locations possible, with zeros everywhere except for the location that player holds (which is set to 1). In this case $|J \cap K|$ is simply the inner product of their two vectors. Fortunately there are SFE protocols for exactly this inner product computation (see here for example). So Alice and Bob simply calculate $|J \cup K|$.

Now, what about the case you give, where the locations are not discrete, but are rather parameterised by a pair of real numbers which have some range associated with them? In this case it is not sufficient to determine whether two points exactly coincide, but we need to also determine which points are close enough to one another to overlap in the area covered. This can be done fairly easily: The first step is to discretize the set of possible locations, hence imposing some fixed resolution on the problem (in practice you only need the range covered by each location to extend a few pixels in each direction). Once you have done this, the protocol would proceed as follows: Bob prepares a register equal in size to the total number of possible discretized locations. Everywhere is zero, unless that location is within distance $D=2E$ of one of his locations in which case it is set to 1. Alice prepares her vector as before, with a 1 at only her discretized locations. Then Alice and Bob run the secure dot product protocol. The number returned by this is simply the number of locations held by Alice such that the area covered by that point overlaps with the area covered by some location held by Bob. (Adjusting the $D$ parameter can be done to set some minimum overlap if desired). In this way, Alice and Bob can count the number of points where the overlap exceeds some threshold, and the total number of distinct locations they would hold between them.


Polytopes convex hull Assume $P_1$, $P_2$ and $Q$ are axis-parallel polytopes in $\mathbb{R}^d$. Is it true to say that checking $CH(P_1\cup P_2)\neq Q$ is NP-hard? There is a similar result for the general polytopes but I need the same for polytopes that their facets are parallel to the coordinate axises.

Assuming your polytopes are closed, I don't think this is true. Each of your polytopes $P_1,P_2,Q$ is a product of (possibly unbounded) intervals $I_i^1$, $I_i^2$, or $I_i^Q$, respectively, for $i=1,\dots,d$. Then $CH(P_1\cup P_2)$ is axis-parallel iff there are no $i,j$ with $i\neq j$ such that one of the following holds:

$I_i^1\not\subseteq I_i^2$, $I_j^1$ has a lower bound $a_j^1$, and $I_j^2$ has a lower bound $a_j^2<a_j^1$,
$I_i^1\not\subseteq I_i^2$, $I_j^1$ has an upper bound $b_j^1$, and $I_j^2$ has an upper bound $b_j^2>b_j^1$,
$I_j^2\not\subseteq I_j^1$, $I_i^1$ has a lower bound $a_i^1$, and $I_i^2$ has a lower bound $a_i^2<a_i^1$,
$I_j^2\not\subseteq I_j^1$, $I_i^1$ has an upper bound $b_i^1$, and $I_i^2$ has an upper bound $b_i^2>b_i^1$.

These are the cases in which $P_1\cup P_2$ (and therefore the convex hull) contains points $x,y$ with $x_i\neq y_i, x_j\neq y_j$, but at least one of the points obtained by replacing e.g. $x_i$ with $y_i$ in $x$ is not in the convex hull. This can be checked in polynomial time.

If the convex hull is axis-parallel, then it equals $Q$ iff $I_i^Q=I_i^1\cup I_i^2$ for all $i$, which also can be checked in polynomial time.


Is qsort linear when sorting only two values? This CodeGolf answer suggests that quick sorting an array whose elements can take only two values is linear. Can this assumption be proved?

There is a large body of research on Quicksort for sorting multisets.
The talk Quicksort is optimal by Sedgewick gives a nice overview of this.
Basically with 3-way partitioning you get within a constant of the information theoretic minimum. The information theoretic minimum is: Suppose we are to sort $n$ keys, where there is only $m$ distinct keys, and the $i$th key occurs $n_i$ times. Then we need
$n \lg(n) - \sum_{i=1}^m n_i\lg n_i -n \lg e +O(\lg n)$ three way comparisons on the average. (See "Sorting multisets and vectors in-place", by Munro and Raman).