How small can be a layered boolean circuit for a function with circuit complexity $s$? Consider a function $f$ computed by a boolean circuit $C$ with $n$ inputs of size $s(n) = \mathsf{poly}(n)$ over the basis $\{\mathsf{XOR},\mathsf{AND},\mathsf{NOT}\}$ (with indegree 2 for the $\mathsf{XOR},\mathsf{AND}$ gates).

A boolean circuit is layered if it can be arranged into $d$ layers ($d$ being the depth of the circuit) of gates such that any edge between two gates connects adjacent layers.

Given that $f$ has a boolean circuit of size $s$, what can we say about the size of a layered circuit computing $f$? There is a trivial upper bound: by adding dummy nodes to $C$ at each layer crossed by an edge, we get a layered circuit of size at most $O(s^2)$. But can we get better in general (e.g. $O(s\cdot \log s)$, or $O(s)$), or for interesting class of circuits?

Background. This question stems from recent results in cryptography which show how to securely compute layered boolean circuits of size $s$ with communication $o(s)$ (e.g. $s/\log s$ or $s/\log\log s)$; I'm trying to understand how restrictive this restriction to layered boolean circuits can be in practice, either for general circuits or for "natural" circuits. However, I've not found much about layered circuits in the literature; appropriate pointers would also be welcomed.

As far as I know, three classes of layered circuits have been studied. In all of these definitions arcs are allowed only between two adjacent layers.

A circuit is called synchronous (Harper 1977) if all gates are arranged into layers, and inputs must be at the layer 0. (An equivalent definition: for any gate $g$, all paths from the inputs to $g$ have the same length.)
A circuit is locally synchronous (Belaga 1984) if each input occurs exactly once but at an arbitrary layer.
A circuit is layered (Gál, Jang 2010) if gates and inputs are arranged into layers, inputs can occur multiple times at different layers. (An equivalent definition: for any  gate $g$ and output gate $o$, all directed paths from $g$ to $o$ have the same length.)

It is easy to see that the three classes are listed from the weakest to the strongest (and the class of unrestricted circuits is even stronger).

Regarding the size of a layered circuit computing an unrestricted circuit of size $s$ we know the following:

Any circuit of size $s$ can be computed by a synchronous/locally synchronous/layered circuit of size $s^2$ (Wegener 1987, Section 12.1).
It should be hard to find an explicit function which requires a synchronous/locally synchronous/layered circuit of size $\omega(s\log{s})$. Indeed, every circuit of size $s$ and depth $d$ can be computed by a synchronous circuit of size $O(sd)$ (Wegener 1987, Section 12.1). Thus, even if we have an explicit function $f$ which requires synchronous circuits of size $\omega(n\log{n})$ (regardless of its complexity in the class of unrestricted circuits), then $f$ cannot be computed by a circuit of depth $O(\log{n})$ and size $O(n)$, which answers a long-standing open question in circuit complexity (Valiant 1977).
There exist explicit functions

3.1. with $\Omega(n\log{n})$ lower bound for synchronous circuits but $O(n)$ upper bound for locally synchronous circuits (Turán 1989).

3.2. with $\Omega(n\log{n})$ lower bound for locally synchronous circuits but $O(n)$ upper bound for layered circuits (Turán 1989).

It is important to note that these two separation results by Turán are proven for functions with one output. It is often much easier to find a function with $n$ outputs which separates two such classes.

As an example, consider the function $f\colon\{0,1\}^n\to\{0,1\}^n$ where the $i$th output bit is an XOR of all inputs except for the $i$th one. This function can easily be computed by a layered circuit of size $O(n)$: First compute an XOR of all inputs in $\log{n}$ layers of total size $n$, then compute all outputs in one layer of size $n$. On the other hand, $f$ requires synchronous circuits of size $\Omega(n\log{n})$. Indeed, in order to compute a parity of length $n-1$, the circuit depth must be at least $\Omega(\log{n})$. On the other hand, each layer must transmit $n$ bits of information, thus its size must be at least $n$.


How to produce a random graph that does not have a Hamiltonian cycle? Let class A denote all the graphs of size $n$ which have a Hamiltonian cycle. It is easy to produce a random graph from this class--take $n$ isolated nodes, add a random Hamiltonian cycle and then add edges randomly.

Let class B denote all the graphs of size $n$ which do not have a Hamiltonian cycle. How can we pick a random graph from this class? (or do something close to that)

This is impossible (unless NP=coNP) since in particular that implies a poly-time function whose range is the non-Hamiltonian graphs (the function goes from the random string to the output graph), which in turn will imply an NP-proof of non-Hamiltonianicity (to prove G doesn't have an Hamiltonian circuit, show x that maps to it.)


"Learning" when test and train distributions don't match We know that the theory of PAC-learning is distribution-free, i.e. assuming that the test and train distributions are the same, we have guarantees on learning the hypothesis.

Question: what if the train/test(evaluation) distributions don't match; is there any result that tells us we can still learn something (say when the training distribution is log-concave and the test distribution is uniform).

In general, the results are pretty strongly negative --- fairly strong assumptions are needed for something like this to work. As an extreme case, suppose that training and testing distributions have disjoint supports, so that the training sample can be nearly uninformative regarding the test performance.

That having been said, there is a body of research on learning (with) changing target concepts/distributions. Here are four fairly representative samples; once you do a follow-up search of who cites them and who they cite, you'll pretty much span the space:

https://link.springer.com/chapter/10.1007/978-3-642-34106-9_13

https://link.springer.com/article/10.1023/A:1007604202679

https://dl.acm.org/citation.cfm?id=269812

https://link.springer.com/article/10.1023/A:1007666507971

Also potentially relevant: Transfer learning
https://en.wikipedia.org/wiki/Transfer_learning


Optimization problems with good characterization, but no polynomial-time algorithm Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the maximum value of $f(x)$ over $n$-bit strings $x$?

Let us say that such a problem has a minimax characterization, if there is another polynomial-time computable function $g$, such that
$$\max_x f(x) = \min_y g(y)$$ holds. Here $x$ runs over all $n$-bit strings, and $y$ runs over all $m$-bit strings; $n$ and $m$ may be different, but they are polynomially related.

Numerous natural and important optimization problems have such minimax characterization. A few examples (the theorems on which the characterizations are based shown in parenthesis):

   Linear Programming  (LP Duality Thm),   Maximum Flow   (Max Flow Min Cut Thm),   Max Bipartite Matching   (Konig-Hall Thm),   Max Non-Bipartite Matching   (Tutte's Thm, Tutte-Berge formula),   Max Disjoint Arborescences in directed graph   (Edmond's Disjoint Branching Thm),   Max Spanning Tree Packing in undirected graph    (Tutte's Tree Packing Thm),    Min Covering by Forests   (Nash-Williams Thm),   Max Directed Cut Packing   (Lucchesi-Younger Thm),   Max 2-Matroid Intersection   (Matroid Intersection Thm),   Max Disjoint Paths   (Menger's Thm),   Max Antichain in Partially Ordered Set   (Dilworth Thm), and many others.

In all these examples, a polynomial-time algorithm is also available to find the optimum. My question:

  Is there any optimization problem with a minimax characterization, for which no polynomial-time algorithm has been found so far?

Note: Linear Programming was in this status for about 30 years!

In some technical sense you are asking whether $P = NP \cap coNP$.  Suppose that $L \in NP \cap coNP$, thus there exists poly-time $F$ and $G$ so that $x \in L$ iff $\exists y: F(x,y)$ and $x \not\in L$ iff $\exists y: G(x,y)$.  This can be recast as a minmax characterization by
$f_x(y) = 1$ if $F(x,y)$ and $f_x(y) = 0$ otherwise; $g_x(y) = 0$ if $G(x,y)$ and $g_x(y) = 1$
otherwise.  Now indeed we have $max_y f_x(y) = min_y g_x(y)$.

So in this sense, any problem known to be in $NP \cap coNP$ but not known to be in $P$ can be turned into an answer to your question.  E.g. Factoring (say, the decision version of whether the $i$'th bit of the largest factor is 1).


Complexity of the halting problem One of the most celebrated results in computer science is that the halting problem is undecidable. However there are still notions of complexity that are applicable. Here are 3 that I have in mind:

$K(n)$ is the Kolomogorov complexity of the string $h_{<2^n}$ of length $2^n$ whose $k$-th bit is 1 iff the $k$-th program halts
$C(n)$ is the minimal size of a Boolean circuit solving the halting problem for programs of size at most $n$
$T(n)$ is the time complexity of the halting problem made solvable by introducing an extra-tape into our Turing machine on which an infinite bit-string is written in the initial state. For example the bit-string can be an infinite look-up table: the $k$-th bit is 1 iff the $k$-th program halts. This allows a simple look-up algorithm to solve the halting problem but the complexity would be $O(2^n)$

$K$ is at most $O(n)$ since we can construct a program which encodes the longest-running program of length $n$ and checks whether the input program halts before that one. $C(n)$ is at most $O(2^n)$ because we can construct a "look-up table" circuit and $T(n)$ is at most $O(2^n)$ as noted above

What other bounds on $K$, $C$, $T$ can be found? In particular, are $C$ and/or $T$ less than exponential?

EDIT: Actually, $K(n) = n + O(1)$. To see this, consider $H_n$ an algorithm solving the halting problem for all inputs of length at most $n$ and $P$ the following program.

$P$ runs $H_n$ on $P$ itself. If result is "halts", it goes into an infinite loop. If result is "doesn't halt", it terminates.

$H_n$ fails to evaluate $P$'s halting correctly therefore the length of $P$ is greater than $n$. On the other hand $P$ is only longer than $H_n$ by a constant so $H_n$ can't be much shorter than $n$.

EDIT: If the halting problem is in $P/poly$ i.e. $C$ is polynomial, then $NP \subset P/poly$ (which implies $PH = \Sigma_2$). To see this consider $S \subset \{0,1\}^*$ a decision problem in $NP$ and $V$ a verifier program for $S$. Deciding whether $x \in S$ is equivalent to solving the halting problem for the following program $Q_x$: "Loop over all $p \in \{0,1\}^*$, halt if $V(x,p) = 1$". The size of $Q_x$ is the same as the size of $x$, up to a constant. Therefore if we can solve the halting problem for $Q_x$ in polynomial time with polynomial advice, we can decide $x \in S$ in polynomial time with polynomial advice

Note that $C$ is polynomial iff $T$ is polynomial. Consider $R_n$ a family of circuits solving the halting problem. Then we can construct an infinite-advice program $H$ for solving the halting problem by encoding $R_n$ as advice. This yields

$$T(n) = O(n \, C(n) \ln C(n))$$

On the other hand if we have $H$ an infinite-advice program solving the halting problem, we can construct a circuit $R_n$ representing the computation process of $H$ on an input of size $n$. The size of this circuit is the product of the spatial complexity by the temporal complexity so

$$C(n) = O(T(n)^2)$$

EDIT: If the halting problem is in $coNP/poly$ then $NP \subset coNP/poly$. This is due to reasoning similar to above i.e. an existential quantifier can be replaced by a universal quantifier at the cost of requiring polynomial advice. I think this also implies some kind of collapse of the polynomial hierarchy

EDIT: It is possible to construct a specific infinite-advice algorithm of optimal complexity, analogous to Levin search for $NP$ problems. As opposed to the case of $NP$, there is no way to verify correctness of solutions, on the other hand it is possible to restrict the dovetailing only to valid programs. This is done by encoding all programs which solve the halting problem together with their respective infinite advice sequences in the infinite advice of our algorithm. The penalty incurred by using this encoding is at most polynomial, hence the resulting algorithm has complexity which is optimal up to a polynomial

Just an extended comment: I'm not an expert, but for what regards 1., something can be said if you interpret: $HALT(k) = 1$ iif $TM_k$ halts on the empty tape.

In this case the string $s$ that lists the first $n$ bits $HALT(k)$, $k = 1,2,...,n$ is highly compressible:

$|s|=n$
let $h$ be the number of halting TMs between $1$ and $n$ ($h \leq n$)

If you know $h$, in order to build $s$ you can simply simulate all TMs between $1$ and $n$ and when $h$ of them stops you have enough information to reconstruct $s$ (you have the positions of the $1$s, the other can be set to $0$s).

So $K(s) = \lceil \log h \rceil + c$

If you interpret $HALT(k) = 1$ iif $TM_k$ halts on all inputs, then:

$K(s) =  min\{n, K(\lceil \log n \rceil, \lceil \log z \rceil )\} + c$

Where $z$ is the minimum number such that for every non halting $TM_k$ in 1..n exists $y \leq z$ such that $TM_k(y)$ doesn't halt. Informally you can simulate the $n$ TMs on inputs $1..z$ being sure that those who halts are the only TMs that always halts on all inputs.

Perhaps the same reasoning can be applied to points 2. and 3.


Algorithm/Complexity for the following SAT Version Given   : A 3 SAT problem.

Known 1 : The SAT problem is satisfiable.

Known 2 : We have a solution that satisfies the given 3 SAT.

Problem Statement: Maximize the solution, i.e. find a solution such that it contains the maximum number of 1's amongst all possible valid solutions to the given problem.

The search problem in the question—let me call it MAX-WEIGHT-3-SAT for now—is $\def\fnwl{\mathrm{FP^{NP[wit,log]}}}\fnwl$-complete.

Recall that $\fnwl$ is defined as the class of search problems solvable by a polynomial-time Turing machine using $O(\log n)$ queries to a witnessing NP oracle: that is, the oracle is required to provide witnesses to all its YES answers.

However, for the present purpose, the following equivalent description is more convenient: a search problem is in $\fnwl$ if it is solvable by a polynomial-time machine using (polynomially many) parallel queries to an (ordinary) NP oracle, followed by a single query to a witnessing NP oracle that always has a positive answer.

To see that MAX-WEIGHT-3-SAT is in $\fnwl$, let $\phi(x_1,\dots,x_n)$ be the input formula. First, using $n+1$ parallel NP queries, check for each $0\le w\le n$ whether $\phi$ is satisfiable by an assignment with $w$ 1s. Let $w_m$ be the maximal $w$ where the answer is positive; make a final witnessing query to get a satisfying assignment with $w_m$ 1s.

In order to show $\fnwl$-completeness, let $S$ be a search problem from $\fnwl$, and fix a poly-time $S$-solver $M$ using $n^c$ parallel NP queries followed by a witnessing query. The predicate $A(x,y,z_1,\dots,z_{n^c})$ defined as “$M$ has a run with input $x$ and output $y$ if $z_i\in\{0,1\}$ is supplied as the answer to the $i$th parallel query, and moreover, whenever $z_i=1$, this answer is indeed correct” is in NP, hence by the proof of the Cook–Levin theorem, there is a poly-time computable sequence of 3-CNF formulas

$$\phi_x(y_1,\dots,y_{n^d},z_1,\dots,z_{n^c},u_1,\dots,u_{n^d})$$

such that if we identify $y$ with its binary representation,

$$A(x,y,z_1,\dots,z_{n^c})\iff\exists u_1,\dots,u_{n^d}\,\phi_x(y,\vec z,\vec u)=1.$$

Now, if we take a satisfying assignment to $\phi_x$ with the maximal number of 1s among the $z_i$’s, then all answers supplied by $\vec z$ for the computation of $M$ are correct, and we can read of the output ($y$) from the assignment. Thus, $S$ is reducible to the following generalization of MAX-WEIGHT-3-SAT:

input: a (satisfiable) 3-CNF formula $\phi(x_1,\dots,x_n,y_1,\dots,y_m)$

output: a satisfying assignment to $\phi$ with the maximal possible number of 1s among the $x_i$’s

But in fact, this problem is reducible to the original MAX-WEIGHT-3-SAT: given $\phi$ as above, consider the formula
$$\phi(\vec x,\vec y)\land\bigwedge_{i=1}^n\bigwedge_{j=1}^m(x_i\leftrightarrow z_{i,j})$$
which behaves just like $\phi$, except that each $x_i$ variable split in $m+1$ variables with the same truth value (under satisfying assignments), overwhelming the count  of the $y_i$ variables.

A related $\fnwl$-complete problem is also given in the answer to Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard? .


What does it mean for CvRDT replicas to transmit their state "infinitely often"? In Shapiro et al.'s SSS '11 paper on Conflict-Free Replicated Data Types for eventual consistency of distributed replicated objects, they describe a system model in which replicas transmit their state to one another "infinitely often".  On the receiving end, a replica can merge the received state with its own local state by executing a method m.

In the case of convergent replicated data types, or CvRDTs, the states a replica can take on are elements of a (join-semi)lattice, and the m operation takes the join of the the received state and the local state with respect to the lattice.  Also, replicas can update their local state (by calling an update method, u), but only in a way that is inflationary with respect to the lattice (that is, the state can only "get bigger").

My questions have to do with the "infinitely often" bit, and are as follows:

Is it just the state transmission that occurs infinitely often, or also the calls to m?  That is, does the process running at some replica have to explicitly call the m method in order to do a merge, or are these merges happening infinitely often "in the background"?  (It seems to me that it must be happening infinitely often in the background, because otherwise, if a process didn't call m at the end of its run, then its replica wouldn't converge with the others, breaking the eventual consistency guarantee that CvRDTs provide.)
But, if merges occur infinitely often, do updates to a CvRDT really have to be inflationary?  In the presence of infinitely-often merges, it seems like if a non-inflationary update ever happened, that update would just be lost -- which would be unfortunate, but wouldn't actually pose a problem for convergence.  When I look at the proof that CvRDTs are eventually consistent, I don't see the place that the inflationary condition on the u method is required.  Why exactly does u have to be inflationary?
Finally, the definition of causal history in the paper seems fishy if merges are really happening "infinitely often", because if so there would be "no room" for any other method execution to occur! The k'th method execution would have to be a merge, for all k, wouldn't it?  Am I taking "infinitely often" too literally?  (Update: Yes, I am taking it too literally!  See below.)

Thanks!

(Update: After a Twitter discussion with Niklas Ekström, I understand the meaning of "infinitely often" better.  If an event occurs "infinitely often", that doesn't mean anything about the frequency of it occurring; it just means that the event occurs an infinite number of times.

So, if event X occurs infinitely often, and some other event Y occurs once (or some finite number of times), then X is guaranteed to occur after Y, because infinitely many occurrences of X cannot all occur before the occurrence(s) of Y.  And here, in particular, there is no way for a replica to update itself and for the neighbors not to find out, because a state transmission will always occur after that update (because there are infinitely many state transmissions, and therefore they can't all occur before that update!).

I'm still not sure if I should be thinking of state transmissions and merges as happening infinitely often, or just state transmissions.  But, even if merges also occur infinitely often, my comment above about there being "no room" for any other event to occur doesn't make sense, considering what "infinitely often" actually means.)

From my understanding of CvRDTs (though I haven't read that exact paper recently)

I believe after receiving new state m is always called, however this should be part of the send/receive machinery, rather than something the application has to deal with. That doesn't prevent the application calling m if it sees the need, but in lots of cases there isn't one.
u has to be inflationary otherwise it will get "lost" by a merge. Given a merge could happen at any time, a non-inflationary update could disappear beneath the CvRDT user as they were performing operations on it. And while non-inflationary updates don't pose a problem for convergence, they do pose a problem for equality: a <merge> b may not be deterministic in the presence of non-inflationary updates.
I don't have an answer for this. Maybe it's worth reading as "unboundedly many times between each update", but that's a guess.


Non-Orthogonal Vectors Problem Consider the following problems:

  Orthogonal Vectors Problem

  Input: A set $S$ of $n$ Boolean vectors each of length $d$.

  Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ such that $v_1 \cdot v_2 = 0$?

  Non-Orthogonal Vectors Problem

  Input: A set $S$ of $n$ Boolean vectors each of length $d$ and a positive
  integer $k$.

  Question: Do there exist distinct vectors $v_1$ and $v_2 \in S$ such that $v_1 \cdot v_2 \geq k$?

What is the relationship between these two problems?

In particular, here are a few more specific questions that I've been wondering about:

(1) Do either of these problems appear to be harder than the other?

(2) I'm not sure what the current state of the art algorithm is for OVP, but for either of these problems, can you get an upper bound better than $O(n^2 \cdot d)$ time?

(3) Does fixing $k$ make any difference for the second problem's complexity?

By $v_1 \cdot v_2$, I mean the inner product of $v_1$ and $v_2$ over $\mathbb{R^d}$.

  Edit: Most of the responses offer really great insights when $d$ is
  small.

  What can be said when $d$ is larger?  Say $d = n$ or $d = \sqrt{n}$
  or at least $d = n^\alpha$ for some $\alpha > 0$.

When $k$ is given as part of the input, the second problem is equivalent to the monochromatic Max-IP problem (given $S \subseteq \{0,1\}^d$, find $\max_{(a,b) \in S, a\ne b} a \cdot b$).

Recently I and Ryan Williams have an (unpublic yet) work showing that when $d = O(\log n)$, OVP and a bichromatic version of Max-IP (given $A,B$, find $\max_{(a,b) \in A \times B} a \cdot b$), is actually equivalent: that is, if one of them has $n^{2-\varepsilon}$ time algorithm, so does the other one. (The reduction from OVP to Max-IP is well-known, the new reduction here is that from Max-IP to OVP).

Since the monochromatic version of Max-IP can be reduced to the bichromatic version, the above result also implies that when $d = O(\log n)$, monochromatic Max-IP can be reduced to OVP.

I believe it is an open question that whether OVP can be reduced to monochromatic Max-IP. This is also closely related to establishing the OV-hardness for the closest pair problem (see e.g. On the Complexity of Closest Pair via Polar-Pair of Point-Sets)

For monochromatic Max-IP, there is an algorithm with running time $n^{2 - 1/\widetilde{O}((d/\log n)^{1/3})}$ time algorithm by Alman, Chan and Williams (also pointed out by Rasmus), for which I believe is the state of the art. While the best algorithm for OVP runs in $n^{2 - 1/O(\log c)}$ time when $d = c \log n$, which is significantly faster.

Also, the approximate version of Max-IP is also studied by this paper On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product, which gives a characterization for the bichromatic case (that is, for which dimensions $d$ and approximate ratio $t$, the problem can be solved in $n^{2-\varepsilon}$ time?). The algorithm in that paper also works for the monochromatic case.


How much bigger does a precomputed lookup table get when salt is added? I am trying to wrap my head around the benefits of salt in cryptography.

http://en.wikipedia.org/wiki/Salt_(cryptography)

I understand that adding salt makes it harder to precompute a table. But exactly how much harder do things get with salt?

It seems to me, like when you add salt, the number of entries in your precomputed table would = number of common passwords to precompute x number of entries in the password table (ie number of different possibile salts).

So if you have a list of 100 common passwords, then without salt, you would have 100 hashed passwords. But if you have 10 users on a system, with 10 different salts, then you would now have 1000 different combinations to check.

So as the numbers of users or the size of common password list increases, the precomputed table gets so big that you can't pre-compute it easily (if at all)

Am I getting this? Do I have it right?

There are a couple of different things going on here, and you need to define your problem more clearly.

For starters, let's just look at a simple case where what is being stored in a database (for each user) is either $H(pw)$ or $s, H(s, pw)$ where $H$ is a hash function, $pw \in \{1, \ldots, N\}$ is a password, and $s \in \{0,1\}^\ell$ is a salt.

To attack a single user without a salt, the attacker can pre-compute $H(pw)$ for all possible values of $pw$ yielding a table of size $N$. Without knowing the salt, however, the attacker has to compute $H(s, pw)$ for all possible salts as well, thus requiring a table of size $N \cdot 2^\ell$. On the other hand, if the attacker does no pre-computation but instead just waits until it compromises the database and then obtains $s^*, H(s^*, pw)$, then we are back to the previous case where the attacker just has to compute $N$ values of $H(s^*, pw)$ to learn the password.

Thus, in the single-user case, the salt increases the attacker's off-line computation but does not increase the on-line computation needed.

Before continuing, let me note also that (in the case without the salt) the attacker can use  to obtain various time-space tradeoffs. Use of salts makes rainbow tables less effective as well.

Salts also help, in a somewhat orthogonal way, in the multi-user setting. To see this, note that if the attacker got the database of hashed passwords in the unsalted case, then using $N$ work he gets the passwords of all users. But in the salted case, assuming each of $M$ users is assigned a different salt, the attacker must do $M \cdot N$ work to recover all passwords.


Non-trivial applications of Bloom filters Does anyone have some nice examples of modifying algorithms that employ a set data structure to instead employ a Bloom filter?  In other words, the damage done by the Bloom filter's false positive rate requires an interesting trick to accommodate.

Michael Mitzenmacher has a nice survey on Bloom filters where he outlines many applications. Maybe some of these might help.


Can you identify the sum of two permutations in polynomial time? There were two questions asked recently on cs.se which were either related to or had a special case equivalent to the following question:

Suppose you have a sequence $a_1, a_2, \ldots a_n$ of $n$ numbers such that $\sum_{i=1}^n a_i = n(n+1).$  Decompose it into the sum of two permutations, $\pi$ and $\sigma$, of $1 \dots n$, so that $a_i = \pi_i + \sigma_i\,$.

There are some necessary conditions: if the $a_i$  are sorted so that $a_1 \leq a_2 \leq \ldots \leq a_n\,$, then we must have

$$\sum_{i=1}^k a_i \geq k(k+1).$$

However, these conditions are not sufficient. From the answer to this math.se question I asked, the sequence 5,5,5,9,9,9 cannot be decomposed as the sum of two permutations (one can see this by using the fact that both 1 or 5 can only be paired with 4).

So my question is: what is the complexity of this problem?

No, you can not identify the sum of two permutations in polynomial time unless P=NP. Your problem is NP-complete since the decision version of your problem is equivalent to the NP-complete problem $2$-Numerical Matching with target sums:

Input: Sequence of $a_1, a_2, \ldots a_n$ of positive integers, $\sum_{i=1}^n a_i = n(n+1)$, $1 \le a_i \le 2n$ for $1 \le i \le n$

Question: Are there two permutations $\psi_1$ and $\psi_2$ such that $\psi_1(i)+\psi_2(i)= a_i$ for $1\le i \le n$?

In the reference, a severely restricted variant of NUMERICAL 3-DIMENSIONAL MATCHING (RN3DM) was proven to be strongly NP-complete.

  RN3DM, Given a multiset $U = \{u_1, . . . , u_n\}$ of integers and an integer $e$ such that $\sum_{j=1}^n  u_j +
n(n + 1) = ne$ , do there exist two permutations $\lambda$ and $\mu$ such that
  $u_j + \lambda( j ) + \mu( j ) = e$, for $j = 1, . . . , n$?

There is an easy reduction from RN3DM to $2$-Numerical Matching with target sums problem:
Given an instance of RN3DM. We construct the corresponding instance by making $a_i= e-u_i$ for $1 \le i \le n$

W. Yu, H. Hoogeveen, and J. K. Lenstra.
Minimizing makespan in a two-machine flow shop with
delays and unit-time operations is NP-hard. Journal of
Scheduling, 7:333–348, 2004

EDIT Oct. 1st: Your problem is called PERMUTATION SUMS. It is listed since 1998 in OPEN PROBLEMS IN COMBINATORIAL OPTIMIZATION by Steve Hedetniemi.


What specific evidence is there for P = RP? RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error.  P is the usual class of problems decidable by a deterministic Turing machine that terminates in polynomial time.

P = RP follows from a relationship in circuit complexity.  Impagliazzo and Wigderson showed that P = BPP follows if some problem that can be decided in deterministic exponential time also requires exponential size circuits (note that P = BPP implies P = RP).  Perhaps due to these results, there seems to be a feeling among some complexity theorists that probabilistic reductions can probably be derandomized.

  What other specific evidence is there that P = RP?

The existence of problems in DTIME(2^O(n)) which require exponential-size circuits to compute (which is the assumption in IW) seems plausible since otherwise we would have non-uniformity giving a speedup on EVERY computational problem -- which goes completely against the current thinking that does not see a "too significant" gap between uniform and non-uniform complexity for "normal" problems.  This thinking comes from the fact that there are very few examples where a "non-uniform" algorithm is known that is significantly better than the known uniform one (again except for derandomization).

Another piece of "evidence" is that relative to a random oracle we do have P=BPP.


1-D set cover optimisation with connected subsets Given a 1-D universe $U$ (e.g. $\mathbb{Z}$) and a set-of-sets $\pmb{S}$, where each element of $\pmb{S}$ is a closed, connected subset of $U$ (e.g. $[a .. b]$ given $ a,b\in\mathbb{Z}$) and $\bigcup\pmb{S}=U$, what is the quickest way to find $\pmb{S}^*\subseteq \pmb{S}$ with the smallest cardinality such that $\bigcup \pmb{S}^* = U$?

In other words, is there a fast 1-D set cover optimisation algorithm given that the sets you're working from are closed-connected?

It seems to me that the naive greedy set cover will in fact be optimal here, but I'm not expert enough to prove it. Can anyone think of a counter-example?

The leftmost point must be covered by some interval. There is no harm in picking the longest interval that covers the leftmost point. Then iterate (after removing the interval and all covered points from the instance).

This is the well-known greedy algorithm for the "Interval Point Cover" problem;
see for instance the course page by Andranik Mirzaian for a full analysis.


The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset Let $V = F_2^n$ be the $n$-dimensional vector space over the field of two elements. The $\epsilon$-noise distribution on $V$, denoted $\mu_\epsilon$, is a probability distribution on $V$ for which sampling a vector $w$ is done by setting each coordinate of $w$ independently, and a particular coordinate is set to $1$ with probability $\epsilon$ and to $0$ with probability $1-\epsilon$.

Let $C \subseteq V$ be a linear subspace, and let $e \in V \setminus C$ be a vector not in $C$. Consider the following pair of events concerning a vector $x$ drawn from $\mu_\epsilon$:

$E_1$ is the event that $x$ is in $C$
$E_2$ is the event that $x$ is in the coset $C + e$

Some experimentation (picking some choices for $C$ at random and also some popular linear codes) suggests that, when $\epsilon < 1/2$, the probability of $E_1$ occurring is at least the probability that $E_2$ occurs, for any $C$. Does anyone have any solid intuition or a proof for why this might be true? Or know of an example where it is false?

The probability that $x \in C + e$ is equal to $2^n \langle T_\rho 1_{0}, 1_{C+e} \rangle$, where $T_\rho$ is the noise operator and $\rho = 1-2\epsilon>0$. Now
$$
2^n \langle T_\rho 1_0, 1_{C+e} \rangle = 2^n \langle T_\rho 1_e, 1_C \rangle = \frac{2^n}{|C|} \langle T_\rho 1_{C+e}, 1_C \rangle.
$$
In terms of the Fourier expansion, this quantity equals
$$
\frac{2^n}{|C|} \sum_S \rho^{|S|} \widehat{1_C}(S) \widehat{1_{C+e}}(S) = \frac{2^n}{|C|} \sum_S \rho^{|S|} \widehat{1_C}(S)^2 \chi_S(e).
$$
Since $\rho > 0$, this is maximized uniquely when $\chi_S(e) = 1$ whenever $\widehat{1_C}(S) \neq 0$. In other words, the quantity is maximized uniquely for $e$ satisfying $C + e = C$.

Note that even when $C$ isn't a code, we have shown that if you start at a random point in $C$, apply the noise, and measure the probability that you reach $C + e$, then this probability is maximized for $e$ satisfying $C + e = C$, and in particular for $e = 0$.


Translating SAT to HornSAT Is it possible to translate a boolean formula B into an equivalent conjunction of Horn clauses? The Wikipedia article about HornSAT seems to imply that it is, but I have not been able to chase down any reference.

Note that I do not mean "in polynomial time", but rather "at all".

No.  Conjunctions of Horn clauses admit least Herbrand models, which disjunctions of positive literals don't.  Cf. Lloyd, 1987, Foundations of Logic Programming.

Least Herbrand models have the property that they are in the intersections of all satisfiers.  The Herbrand models for $(a \lor b)$ are $\{\{a\}, \{b\}, \{a,b\}\}$, which doesn't contain its intersection, so as arnab says, $(a \lor b)$ is an example of a formula which can't be expressed as a conjunction of Horn clauses.

Incorrect answer overwritten


Existence of equilibria in infinite two players zero sum extensive form games with perfect information I am looking for a study that has examined whether and under which conditions (if any), an infinite and of possibly infinite horizon two person zero sum extensive form game with perfect information and finite discrete action space, has a value. I would appreciate very much any tips.

By the Ky Fan minimax theorem, if you can identify the strategy spaces of the two players with convex compact subsets of a locally convex topological vector space, and the payoff function $M(x, y)$ is convex and continuous in $y$ for any $x$, and also concave and continuous in $x$ for any $y$, then the minimax theorem holds.


Proving liveness-like property on an infinite tree (Context: this is a problem from the middle of my dissertation work, abstracted into a more general problem. It's related to showing that some liveness properties hold, so perhaps work from something like CTL could apply.)

Say you have some tree of possibly infinite depth with root node $n_0$. (EDIT: the number of children per node is bounded, in case that helps.) There exists a special set $G$ of "good" nodes in the tree such that for every path from $n_0$ through the tree, that path contains a node in $G$ (although that node can be at any arbitrary depth).

Now, say there is some property $P$ on nodes of the tree such that $P(n)$ holds if and only if:

$n \in G$, or
for every child node $n'$ of $n$, $P(n')$ holds.

To prove: $P(n_0)$ holds

$P$ is practically another way of saying "every path has a node in $G$", so this seems almost trivial. However, I can't seem to formally prove it. An inductive proof seems like the way to go ("I expect my children to all be in P if I'm not in $G$ myself, so $P$ should hold for me"), but what to induct on? Something like "distance until the farthest "good" node" seems natural, but I'm not sure such a bound exists.

I'm reasonably sure this statement can be proved, so how to prove it? Is there indeed a bound on the farthest "good node", and if so, what is the argument that such a bound exists?

See the comments on the question above: both a proof by contradiction and a use of König's lemma appear to suffice.


Lossless Compression Books I am intrigued by compression techniques and I'd like some recommendations about books to study, specifically, on lossless compression algorithms and data structures.

I don't know if there is a comprehensive book (or books) that deals with both compression of general sources (stream of bytes), and known inputs (e.g., integers, strings).

Thanks for your references!

I recommend the following books:

Khalid Sayood "Introduction to DATA COMPRESSION"
Khalid Sayood "Lossless Compression Handbook"
David Salomon "Handbook of Data compression"

And a little more specific, but also good books in this field:

Timothy Bell "Text compression"
Donald Adjeroh, Timothy Bell, Amar Mukherjee "The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern
Matching"


What happens to complexity classes if all $\#P$ problems have polynomial-time algorithms? As title says what happens to other complexity classes if all $\#P$ (Sharp-P) problems have polynomial-time algorithms? What happens to PSPACE?

By definition, $\mathbb{P} = \mathbb{NP}$, since any $\mathbb{NP}$ problem could be solved by answering the question "Is the # of accepting paths non-zero", which by assumption, can be calculated in $\mathbb{P}$. As a consequence, the polynomial hierarchy collapses as well.

You also get other results by using results or their contrapositives.


Is there a name for this property of a term rewriting system? Given TRS let's call it top-reducible or left-reducible if no rule's right hand side is contained in any rule's left hand side non-trivially.

A term A is contained in an other one B trivially if they overlap at their roots e.g. 2(y) is contained in 1(2(x)) non-trivially while 1(y) is contained in 1(2(x)) trivially) (I also don't know if this 'containment' has a name)

E.g.

A TRS with a single rule 1(2(x)) -> 2(x) is not top-reducible.
A TRS with rules 1(2(x)) -> 3(x), 4(3(5(x,y))) -> 1(5(x,y)) is not top-reducible.

I'm not sure there is a name for this specific property, though I would say "All right-hand sides are in head-normal form".

To be honest, this seems like a very strange property to request, especially since an inner reduction may provoke a head reduction, like so:

$$ {\cal R} = \{a \rightarrow b, f(b)\rightarrow f(a)\}$$
(I'm using letters for function symbols instead of numbers, as is traditional). In this case $f(a)$, the right hand side of the second rule, does not match any rule at it's head, but it may match the second rule if you apply the $a\rightarrow b$ reduction inside.


Maximum-clique practical applications The question is: what are examples of clique problem applications? I mean, what problems can be solved by reducing to clique problem (sorry for tautology)?

All I came with is finding social cliques: groups of people who know each other personally.

I understand, that similar ideas may arise in electronics, CS (i.e., compiler design?) and probably other fields, but can't think of other interesting problems.

Would be glad to see some of them.

If you ask questions like that, I feel that the only answers you could get are problems that "reduce to the maximum clique". That would be a mistake. There are many problems in practice where finding a maximum clique is thought of as a subroutine, as it is not the most expensive part of the algorithm.
Finding cliques is known to be NP-Hard, and depending on the instances it is or it is not. NP Hard does not mean anything in practice.
My (reduced) own experience tells me that I would prefer 1000 times to deal with a maximum clique problem that with a TSP, or worse : an integer multiflow.  Max clique is for me one of the "kind" NP-hard problems.
And it means that I sometimes reduce problems to Max Clique because it can be done this way, and because I know that I will get the result fast in practice (and also because I already have all the functions available, so there is nothing new to code).

If you are interested in pratical problems that can be formulated immediately as a max clique problem, I am afraid you will not find many. Practical problems have their own aspect. However, I solved one thousand time "Max Clique" problems, often on optimization problems which would not have required it, because Max Clique is, somehow, an easy problem, and because it is so general of aspect.

I guess the last time I computed a maximum independent set (which is exactly the same) was in order to obtain a decomposition of a graph (a partition of its edges into copies of a given graph).

The graph had hundreds of nodes, and solving the max clique problem on it was very far from being the bottleneck.

Hoping it helped,


Does k-PATH admit a constant approximation? In the $k$-PATH problem, we receive as input a graph $G$ and an integer $k$. The goal is to decide whether there exists a simple path of length $k$ in $G$.

A $\alpha$-approximation for $k$-PATH is an algorithm which given an input $\langle G,k\rangle$ either confirms that a path of length $k/\alpha$ exists in $G$, or denies the existence of a $k$-path. It may act arbitrarily if the longest simple path in $G$ is at least of size $k/\alpha$ and at most of size $k$.

Is there a constant $\alpha>0$ for which $k$-PATH is $\alpha$-approximable in poly time?

Karger, Motwani and Ramkumar (1997) discuss this question.
They show that if any polynomial-time algorithm can approximate the longest path to a ratio of $2^{O(\log^{1−\epsilon} n)}$, for any $\epsilon>0$, then NP has a quasi-polynomial deterministic time simulation; this results even holds for graphs of bounded degree.

  David R. Karger, Rajeev Motwani, G. D. S. Ramkumar:
  On Approximating the Longest Path in a Graph.
  Algorithmica 18(1): 82-98 (1997)


Graph theory: definiton of the crown of a graph I'm currently reading "Invitation to Fixed-Parameter Algorithms" by Rolf Niedermayer. Page 69 gives the following definition of the crown of a graph, which I do not quite understand:

A crown of a graph $G = (V,E)$ consists of $H\subseteq V$ and $I \subseteq V$ with $H \cap I = \varnothing$ s.t. the following three conditions hold:

$H = N(I)$
$I$ forms an independent set
the edges connecting $H$ and $I$ contain a matching in which all elements of $H$ are matched.

$N(I)$ is the neighborhood of vertices $I$, i.e., $N(I) = \{u \mid v \in I \land  (u,v) \in E\}$.

I'm stuck with the third point: I'm interpreting it as "in the bipartite graph $(H, I, F)$ with $F = \{(u,v) \in E \mid u\in I \land v \in H\}$ there is a matching $M\subseteq F$ s.t. $\forall v \in H: \exists (u,v) \in F$, i.e., each vertex in $H$ is covered by an edge in the matching $M$".

But does this not imply that  $|I| \geq |H|$ since there can at most be $|I|$ non-adjacent edges connected to vertices in $I$? This would imply that $I$ is a set of vertices that have degree 1, which surely is not the intention since a crown is intended to be a generalization of 1-connected vertices.

What am I missing?

Yes, it implies that $|I| \geq |H|$ but it does not imply $I$ contains only vertices of degree 1. The edges joining $H$ to $I$ contain an H-covering matching, but there can be many more edges. See, for instance, D. Marx' slides on crown reduction: http://www.cs.bme.hu/~dmarx/papers/marx-agape09-slides-print.pdf


Permutations with forbidden subsequences Let $[n]$ denote the set $\{1,...,n\}$ and C(n,k) denote the set of all $k$-combinations of elements from $[n]$ without repetition.
Let $p= p_1p_2...p_k$ be a $k$-tuple in $C(n,k)$. We say that a permutation
$\pi:[n]\rightarrow [n]$ of the set $[n]$ avoids $p$ if there is no k-tuple
of integers $i_1<i_2<...<i_k$ such that
$$\pi(i_1) = p_1, \;\;\pi(i_2)=p_2,\;\;  ...,\;\;\pi(i_k) = p_k.$$

For instance, if $n=5$ then the permutation $12453$ avoids $134$ as a subsequence, while the permutation $\mathbf{1}2\mathbf{3}5\mathbf{4}$ does not.

Question: Let $k$ be a constant. Given a set $S\subset C(n,k)$ of $k$-tuples, find a permutation
$\pi:[n]\rightarrow [n]$ that avoids each $k$-tuple in $S$.

Is there an algorithm for this problem that is polynomial in $|P|$ and $n$? Here $n$ is given in unary. An algorithm running in time $n^{f(k)}|P|^{g(k)}$ would be fine.
Or is this problem NP-complete?

Any references for this problem, or suggestions of algorithms are welcome. Note that the notion of permutation avoiding subsequence defined above is not the same as the notion of permutation avoiding pattern  where only the relative order of elements is important, and which seems to be well studied in combinatorics.

It's NP-complete for $k=3$ by a reduction from betweenness. In the betweenness problem, one is given $n$ items to be totally ordered, and constraints on some triples of items forcing one item of the triple to be between the other two. In your problem, the same constraint can be forced by forbidding all the subsequences on three elements that do not place the middle element in the middle. But betweenness is known to be NP-complete: see J. Opatrny, Total ordering problem, SIAM J. Comput., 8 (1979), pp. 111–114.


What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$? Following Josh Grochow's suggestion, I am converting my comment from a previous question into a new question.

  What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?

Here $\mathsf{UP}$ is the class of languages recognizable by polynomial time non-deterministic Turing machines that have a unique accepting path on "yes" instances and no accepting path on "no" instances.

Obviously $\mathsf{UP} \subseteq \mathsf{NP}$, but why would we believe that the containment is strict? The evidence I can find is oracle separation: subject to a random oracle, $\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$. Also, the Complexity Zoo suggests that $\mathsf{UP}$ is not believed to have complete problems.

Even, Selman, and Yacobi conjectured that there does not exist a disjoint $NP$-pair $(A, B)$ such that all separators of $(A, B)$ are $ \le_T^p $-hard for $NP$. This conjecture implies that $UP \ne NP$.

S. Even, A. Selman, and J. Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61:159–173, 1984.


A simple programming language? What is a simple toy research programming language that has simple denotational semantics (including numbers or reals) that is used often to demonstrate certain properties of programming languages, or other things?

I am looking to demonstrate an idea on a programming language, and I don't want it to be complex in syntax, and I also want it to have easy to understand denotational semantics.

I don't need a working implementation of the language. Just the syntax and denotational semantics for the syntax.

Thanks.

Joy comes to mind. It's a simple concatenative language that involves manipulations on a stack. It's essentially a reverse Polish notation for combinatory logic with quoting, developed by a professor of logic and programming so presumably it was taught in class. :)

I'm not 100% sure what qualifies as as denotational semantics, but, there is an algebra for it:

http://www.kevinalbrecht.com/code/joy-mirror/j04alg.html


Why is BQPSPACE in PSPACE if it can have doubly exponentially long running times? The standard proof that BQPSPACE is in PSPACE relies on a Savitch game type analysis on path integrals. However, it assumes the time running length for BQPSPACE is at most exponentially long. This is true for PSPACE, but for closed quantum systems with a fixed number of degrees of freedom, it typically takes a doubly exponentially long time before Poincare recurrence due to the exponential nature of the state vector. So, does the proof still run through, or not?

BQPSPACE can only use polynomial qbits, but its computation is driven by a classical machine. This classical machine also only gets a polynomial number of bits. Thus, the classical computer limits the number of steps to simply exponential, regardless of what the quantum computer does.

The limitation of exponential length circuits by polynomial size algorithms is due to the computer creating the circuit getting in an infinite loop, not about the state or details of the circuit itself. Quantum circuits are no different.


Minimal specification of Martin-Löf type theory I'm reading the formal presentation of Martin-Löfs type theory (appendix of the HoTT book). The authors introduce a hierarchy of universes, then $\Pi, \Sigma,+, {\bf 0}, {\bf 1}$ and also $W$-types as well as natural numbers $\mathbb N$ (inductively via $0$ and $succ$). Eventually they add higher inductive types too.

But then I wonder why it's necessary to do $\mathbb N$ in the theory specification. Doesn't ${\bf 1}$ and $+$ and algebraic data types, in the incarnation of having $W$-types, suffice to set it up? E.g. with the initial algebra approach. (Or at least after we pass from MLTT to HoTT have inductive types - after all, the integers $\mathbb Z$ emerge as homotopy group of circle type $\mathbb S$ within the theory.)

Or has it to do with our need to have primitive recursion from the start, which is defined right next to $\mathbb N$ in the presentation? This is an idea which I have because I don't quite know how "definition is defined" in that framework, or how extending the language works, formally. I might add that I recognize that at least an informal notion of numbers and "greater" is used already when the hierarchy of universes is defined.

In case one can spare $\mathbb N$ and the specification is just not minimal, are there other items one could, in principle, drop? E.g. I could imagine $\bf 2$ and then $+$ coming from some combination of $\Pi, \Sigma, {\bf 0}, {\bf 1}$, but I was not able to do it.

The purpose of the system described in the appendix of the HoTT book is to present something that corresponds to what is used by the book. The book is aiming to be educational. Therefore it would be a bad idea to do everything in a minimalist way. For example, we introduce $\mathbb{N}$ separately because it is instructional to see how inductive constructions work in a familiar case.

You are perfectly correct, to jump-start inductive types from general $W$-types you just need $0$ and $2$. You immediately get $1$ as $0 \to 0$, and you get $+$ from $2$ and $\Sigma$. Once you have that, you get all finite sums $1 + 1 + \cdots + 1$. At this point it is easy to do the usual algebraic datatypes.

If you drop $0$, so you start from $\Pi$, $\Sigma$, $1$ and $2$, then you cannot get $0$ back because every type you make will be inhabited.

Suppose you only have $\Pi$, $\Sigma$, $0$ and $1$. Then you cannot make $2$ because you can show that every construction you make gives you back either $0$ or $1$. In fact, you cannot make any interesting dependent families at all. A larger family of types which is closed under $\Pi$, $\Sigma$, $0$ and $1$, but does not contain $2$ is the $(-1)$-types (propositions).


Shor's quantum error correction code with unknown basis $\newcommand{\ket}[1]{\lvert #1 \rangle}$I've met a problem in quantum secret sharing which involves the use of a quantum error-correction code. (let's make it simple to be the 9-qubit Shor code)

In the Shor code, Alice encodes $\ket{0}$ as $(\ket{000}+\ket{111})^3$, and $\ket{1}$ as $(\ket{000}-\ket{111})^3$, so the code can fight against 1-qubit flip or phase error, and recover the original qubit.

However, what I'm wondering is:

What becomes of the 9 qubits after measurement? Do they become the original 1 logical qubit? Or do they stay as 9 entangled qubits?
What would happen if Bob, the one who decodes the code, actually has a slightly different orthogonal basis than the original one due to imperfect knowledge or experimental error, e.g. Bob is measuring with $\ket{0'}=\cos(x)\ket{0}+\sin(x)\ket{1}$ and $\ket{1'}=-\sin(x)\ket{0}+\cos(x)\ket{1}$ but $x$ is small? (Or, let's say he is really unlucky and mistook Alice's $\ket{0}$ and $\ket{1}$ basis entirely, so he uses $\ket{+}$ and $\ket{-}$ basis, then Bell basis for him would become $\ket{+++} + \ket{---}$

When $x$ is small, would he still be able to decode out the original qubit using the "wrong" Bell basis? And would there be some way to calculate the error probability?

Q1 : Fate of the 9 qubits
There is no (or 2) answer to your question, since it is implementation dependent :

If your implementation of the code is ideal, and you have a way to directly measure the syndromes, the 9 qubits are projected on the global 9 entangled qubits state. It is the case, for example, if the code is used in a fault-tolerant implementation of quantum computing.
If the implementation is more realistic, the measurement of the 8 syndromes is performed in 2 steps : 1st you apply a global unitary (through a quantum circuit) on the 9 qubits, then you measure 8 qubits, destroying them in the problem. You have then a single qubit, to which you can apply a unitary(depending on the measurement result) to get the single original qubit.

Q2: Effect of misalignment
The misalignment behaves like an error, whether $x$ is small or $π/4$ (as in your $\lvert±\rangle$ example). What you describe correspond to applying the operator $\cos x I +\sin x XZ$ to each qubit. Measuring the syndrome projects the state to one with a given number of errors, but as long as there is less than 1 X error and 1 Z error, the code is enough to correct it.
This condition happens with probability
$$(\cos^2 x)^9 + 9 (\cos^2 x)^8\sin^2 x=\cos^{16}x(1+8\sin^2x)\simeq 1-64x^4$$
the last approximation being valid for small $x$.
If the rotation is by $\pi/4$, the error rate is 50% and your code will not be able to correct it.


Categories a computer scientist should know about I am a computer scientist with a CS degree from the 80's.
I am learning category theory by myself.
I am looking for advice about learning category theory.
E.g. it is quite helpful in learning category theory
to have examples from a familiar topic like logic or programming languages.
What I know
I have read the answers to this question and the paper
Physics, Topology, Logic and Computation: A Rosetta Stone
which builds up concepts with parallels between category theory,  logic, and theory of computation.
I know about the following categories:
• categories
• monoidal categories
• braided monoidal categories
• closed monoidal categories
• symmetric monoidal categories
• closed braided monoidal categories
• compact monoidal categories
• cartesian categories
• closed symmetric monoidal categories
• compact braided monoidal categories
• cartesian closed categories
• compact symmetric monoidal categories
Questions

Are there any other major categories that a computer scientist should know about?

Were there any that have fallen out of favor?
If yes, why?
Have they been replaced with other categories?

When thinking about categories should I
focus on the arrows first before the objects?

Note that most of the categories you considered are 'abstract', i.e., they require structure or properties of an abstract category. As computer scientists we should also be familiar several concrete categories which turn out to be useful:

Concrete categories

Set
Set$_{\mathcal P}$ (objects are sets, morphisms are relations)
Rel (objects are relations, morphisms are functions preserving these relations)
Pred (objects are predicates (= subsets) morphisms are functions preserving these relations.
Posets
$\omega$-CPOs
Nominal sets
Lawvere theories

Abstract categories

Functor categories
Presheaf categories, in particular, monoid actions, which are equivalent to finite automata iianm
Locally presentable categories
Monads
Enriched categories (in particular, O-categories)
Kleisli and Eilenberg-Moore categories
Embedding-projection categories
Profunctors

Also, sometimes properties don't commute on the nose, and the structure under consideration is of higher-dimensional (i.e., 2-categorical).

As to your question 3: you can define a category without mentioning objects at all (though it's conceptually clearer if we do mention the objects).


Open/unsolved problems in (computational) random matrix theory / matrix completion? I was wondering what some open problems are in random matrix theory (especially those of interest to TCS people/so mainly non-asymptotic things, I imagine). Also, and relatedly, what are remaining/outstanding open problems in matrix completion?

In view of the questions above, I'd also be interested if people can point to research monographs/survey papers/texts that provide some background on the topics (RMT in computer science/matrix completion) above.

Not sure if this is the kind of thing you want but here is something I find fascinating : This particular breakthrough paper's proof technique is in a sense  "random matrix theory", https://arxiv.org/abs/1505.08010
(..I dont know if before this paper anyone had guessed that random matrix is the way of think of this question..)

I feel it is a deeply important question to be able to (a) come up with a version of this which shows this existential result restricted to only simple graphs and (b) come up with a deterministic polynomial time algorithm (or prove that such a thing can't exist!) which makes this existential argument constructive in the case of simple graphs.  This isnt clear for even just bipartite graphs!


A reachability problem Let $P$ be a length-preserving (i.e. $|P(x)|=|x|$)
polynomial-time computable program.

I.
Given two strings $x$ and $y$,
we want to decide if $y$ can be obtained by
repeated applications of $P$ to $x$.
In other words,
is there a $k$ such that $P^k(x)=y$?

II. Given a string $x$,
find the number strings of length $|x|$
which cannot be obtained by repeated applications of $P$ to $x$?

I am looking for PTAS algorithms for these problems.

The first problem is PSpace-complete, see this answer on MO.

With respect to Problem II, it is coNP-hard (under Karp reductions) to tell if the number of unreachable strings is 0 or at least $1 - 2^{-\text{poly}(|x|)}$ fraction of all strings. I suspect there is a way to boost this and show that the gap problem is PSPACE-hard, maybe by using IP as a robust characterization of PSPACE.

Let $L$ be a coNP-complete language. There exists a polynomial time Turing machine $M$ and a polynomial $p$ such that $x \in L$ if and only if for all $w$, $|w| = p(|x|)$, we have $M(x, w) = 0$.

Construct $P$ to be the following program. It takes $z$ where $|z| = p(|x|) + i$ and maps it to

itself if $z = (w, 0^{i})$ and $M(x, w) = 1$
to $z'$, where $z'$ is the successor of $z$ in the lexicographic order, otherwise

Notice that if $x \in L$, then starting from $0^{p(|x|) + i}$ and repeatedly applying $P$ we run through all strings $z$ of size $p(|x|) + i$. Otherwise, there is some $w$ such that $M(x, w) = 1$ and the repeated applications of $P$ reach at most $2^{p(|x|)}$ strings. Taking $i$ to be a large enough polynomial in $|x|$ finishes the proof.


Zero knowledgeness of a simple protocol Say there's a public encryption scheme whose public key is $p_k$ and secret key is $s_k$. Prover $P$ wants to convince verifier $V$ that he knows $s_k$. The protocol is:

$V$ uniformly generates $m$ and sends $c = Enc_{p_k}(m)$ to $P$
$P$, receiving $c$, sends $m' = Dec_{s_k}(c)$ to $V$
$V$ checks whether $m = m'$. If so, accept. Else, reject.

Completeness and soundness are obvious. Intuitively decryption shouldn't leak information about the secret key $s_k$ if this scheme is CCA-secure. But I just haven't come up with a proper simulator to argue this. If $V$ cheats, it's hard to get the correct plaintext without knowledge of $s_k$. If the simulator just guess, the probability is so low that exponentially many rounds are required. So the question is:

Is this protocol really zero knowledge? If so, how to construct the simulator?

First, I think the CCA-security is not enough, and the encryption scheme must be at least IND-CCA2-secure.

Second, I believe the protocol is not zero-knowledge, at least in the auxiliary-input model. The reasoning is as follows: Let z be the auxiliary input to the malicious verifier V*. It's safe to assume that $z = Enc_{p_k}(m)$, where m is unknown to V*. Then, V* can deviate from the original protocol: Instead of choosing a random m and computing c (as prescribed in the protocol), she lets c = z, and sends c to the prover. This way, V* exploits P as a "decryption oracle," and obtains knowledge beyond what she could possibly compute.

One piece of advice: Read the paper Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks, specially section 4. It suggests a protocol similar to yours; one which has never been realized. It also proposes the now-famous "knowledge-of-exponent" assumption (KEA), one which was later used to construct a non-black-box ZK protocol. (The reason why you can't find a simulator, beyond the line of reasoning above, is that you try to imagine a black-box simulator. That's impossible by the result of Goldreich and Krawczyk). For more info on the use of the KEA in constructing non-black-box ZK, see [Hada and Tanaka] and the more recent [Bellare and Palacio].

--Edit-- @cyker: I'm working on a similar issue as (presumably) you're doing: The (right) definition of simulators. A partial result of mine, closely related to the protocol you offered, can be found at http://eprint.iacr.org/2010/150. The latest results are submitted but not published online yet.


Practical applications of the Theory of Equality with Uninterpreted Functions (EUF) In these days I'm reading the book Decision Procedures - An Algorithmic Point of View. Chapters 3 and 4 deal with the Theory of Equality with Uninterpreted Functions (EUF). The authors give 3 toy examples on using EUF to solve real-world problems: proving equivalence of programs, proving equivalence of circuits, validating the translation performed by a compiler. I'm looking for further practical applications of EUF, possibly non-toy examples.

  Question(s)

  Did anyone use EUF to successfully solve real-world problems different than those indicated above?
  Did anyone use EUF to successfully solve the above problems, but in a real world setting rather than a toy setting?
  Did anyone use EUF to model (parts of) big, complex systems? What did you model? What did you manage to prove about such systems? Do you have any success story to tell?

Pointers to papers are greatly appreciated. I've already posted this question on ai.stackexchange.com, without receiving any answer (moreover, unfortunately that site was closed during its beta for insufficient activity).

Most automatic theorem provers handle EUF in some form. In particular, provers based on the Nelson-Oppen architecture do so. For big systems, however, EUF is usually not enough. One needs specialized decision procedures for arithmetic, arrays, bit vectors, and so on to get better performance. Take a look at SMT solvers. If you follow the links to solvers and where they are used you'll find many applications to real world problems. For example, Z3 is used in VCC, which in turn is used to fully verify Microsoft's (baby) hardware simulator Hyper-V.


OR-circuit complexity of a dense linear operator Consider the following simple monotone circuit model: each gate is just a binary OR. What is the complexity of a function $f(x)=Ax$ where $A$ is a Boolean $n \times n$ matrix with $O(n)$ 0's? Can it be computed by linear size OR-circuits?

More formally, $f$ is a function from $n$ to $n$ bits. The $i$-th output of $f$ is $\bigvee_{j=1}^{n}(A_{ij} \land x_j)$ (i.e., an OR of the subset of input bits given by the $i$-th row of $A$).

Note that $O(n)$ 0's split the rows of $A$ into $O(n)$ ranges (subsets consisting of consecutive elements of $[n]$). This makes it possible to employ known range query data structures. E.g., a sparse table data structure can be turned into an OR-circuit of size $O(n\log n)$. Yao's algorithm for range semigroup operator queries can be turned into an almost linear circuit (of size $O(\alpha(n) \cdot n)$ where $\alpha(n)$ is inverse Ackermann)

In particular, I don't even know how to construct a linear size circuit for a special case where each row of $A$ contains exactly two zeros. While the case of exactly one zero in each row is easy. (Each output function can be computed by an OR of a prefix $[1..k-1]$ and a suffix $[k+1..n]$, which can be precomputed by $2n$ OR-gates.)

This is a partial (affirmative) answer in the case when we have an upper bound on the number of zeros in every row or in every column.

A rectangle is a boolean matrix consisting of one all-1 submatrix and having zeros elsewhere.
An OR-rank $rk(A)$ of a boolean matrix is the smallest number $r$ of
rectangles such that $A$ can be written as a (componentwise) OR of these rectangles. That is, every 1-entry of $A$ is a 1-entry in at least one of the rectangles, and every 0-entry of $A$ is a 0-entry in all rectangles. Note that $\log rk(A)$ is exactly the nondeterministic communication complexity of the matrix $A$ (where Alice gets rows, and Bob columns).
 As OP wrote, every boolean $m\times n$ matrix $A=(a_{i,j})$ defines a mapping $y=Ax$, where  $y_i=\bigvee_{j=1}^na_{i,j}x_j$ for $i=1,\ldots,m$. That is, we take a matrix-vector product over the boolean semiring.

The following lemma is due to Pudlák and Rödl; see Proposition 10.1 in this paper
or Lemma 2.5 in this book for a direct construction.

Lemma 1: For every boolean $n\times n$ matrix $A$, the mapping $y=Ax$ can be computed by an unbounded fanin OR-circuit of depth-3 using at most $O(rk(A)\cdot n/\log n)$ wires.

We also have the following upper bound on the OR-rank of dense matrices.
 The argument is a simple variation of that used by Alon in this paper.

Lemma 2: If every column or every row of a boolean matrix $A$ contains at most $d$ zeros, then $rk(A)=O(d\ln|A|)$, where $|A|$ is the number of $1$s in $A$.

Proof:
Construct a random all-$1$ submatrix $R$ by picking each row independently with the same probability $p=1/(d+1)$. Let $I$ be the obtained random subset of rows. Then let $R=I\times J$, where $J$ is the set of all columns of $A$ that have no zeros in the rows in $I$.

A $1$-entry $(i,j)$ of $A$ is covered by $R$ if $i$ was chosen in
  $I$ and none of (at most $d$) rows with a $0$ in the $j$-th column
  was chosen in $I$. Hence, the entry $(i,j)$ is covered with probability at least $p(1-p)^{d}\geq pe^{-pd-p^2d}\geq p/e$.
  If we apply this procedure $r$ times to get $r$ rectangles,
  then the probability that $(i,j)$ is covered by none of these
  rectangles does not exceed $(1-p/e)^r\leq e^{-rp/e}$.  By the union bound, the
  probability that some $1$-entry of $A$ remains uncovered is at most
$|A|\cdot e^{-rp/e}$, which is smaller than $1$ for $r=O(d\ln|A|)$.
$\Box$

Corollary: If every column or every row of a boolean matrix $A$ contains at most $d$ zeros, then the mapping $y=Ax$ can be computed by an unbounded fanin OR-circuit of depth-3 using
$O(dn)$ wires.

I guess that a similar upper bound as in Lemma 2 should also hold when $d$ is the average number of $1$s in a column (or in a row). It would be interesting to show this.

Remark: (added 04.01.2018) An analogue $rk(A)=O(d^2\log n)$ of Lemma 2 also holds when $d$ is the maximum average number of zeros in a submatrix of $A$, where the average number of zeros in an $r\times s$ matrix is the total number of zeros divided by $s+r$.
This follows from  Theorem 2 in N. Eaton and V. Rödl;, Graphs of small dimension, Combinatorica 16(1) (1996) 59-85.
A slightly worse upper bound $rk(A)=O(d^2\ln^2 n)$ can be derived directly from Lemma 2 as follows.

Lemma 3: Let $d\geq 1$. If every spanning subgraph of a bipartite graph $G$ has average degree $\leq d$, then $G$ can be written as a union $G=G_1\cup G_2$, where the maximum left degree of $G_1$ and the maximum right degree of $G_2$ are $\leq d$.

Proof: Induction on the number $n$ of vertices. The base cases $n=1$ and $n=2$ are obvious. For the induction step, we will color the edges in blue and red so that the maximum degree in both blue and red subgraphs are $\leq d$. Take a vertex $u$ of degree $\leq d$; such a vertex must exists because also the average degree of the entire graph must be $\leq d$. If $u$ belongs to the left part, then color all edges incident to $u$ in blue, else color all these edges in red. If we remove the vertex $u$ then the average degree of the resulting graph $G$ is also at most $d$, and we can color the edges of this graph by the induction hypothesis. $\Box$

Lemma 4: Let $d\geq 1$. If the maximum average number of zeros in a boolean $n\times n$ matrix $A=(a_{i,j})$ is at most $d$, then $rk(A)=O(d^2\ln^2 n)$.

Proof: Consider the bipartite $n\times n$ graph $G$ with $(i,j)$ being an edge iff $a_{i,j}=0$. Then the maximum average degree of $G$ is at most $d$. By Lemma 3, we can write $G=G_1\cup G_2$, where
 the maximum degree of the vertices on the left part of $G_1$, and the maximum degree of the vertices on the right part of $G_2$ is $\leq d$.
Let $A_1$ and $A_2$ be the complements of the adjacency matrices of $G_1$ and $G_2$.
Hence, $A= A_1\land A_2$ is a componentwise AND of these matrices.
The maximum number of zeros in every row of $A_1$ and in every column of $A_2$ is at most $d$. Since $rk(A)\leq rk(A_1)\cdot rk(A_2)$, Lemma 2 yields $rk(A)=O(d^2\ln^2 n)$. $\Box$

N.B. The following simple example (pointed by Igor Sergeev) shows that my "guess" at the end of the answer was totally wrong: if we take $d=d(A)$ to be the average number of zeros in the entire matrix $A$ (not the maximum of averages over all submatrices), then Lemma 2 can badly fail.  Let $m=\sqrt{n}$, and put an identity $m\times m$ matrix in, say left upper corner of $A$, and fill the remaining entries by ones. Then $d(A)\leq m^2/2n < 1$ but $rk(A)\geq m$, which is exponentially larger than $\ln|A|$. Note, however, that the OR complexity of this matrix is very small, is $O(n)$. So, direct arguments (not via rank) can yield much better upper bounds on the OR complexity of dense matrices.


Is there a randomized algorithm for set-cover? Is there a well-known randomized algorithm for the set cover problem in the literature - such that it has an approximation ratio of $O(\log n)$ or $f$ - where $f$ is the max frequency of an element. please don't mention the randomized rounding method with LP (or any other method depending on LP) ?

Here's one randomized $O(\log n)$-approximation algorithm (not well known I'm afraid), for unit-cost set cover.

input: collection of sets over $n$ elements, upper bound $U$ on opt

output: w/probability $\ge 1/2$, a set cover of size $O(U \ln n)$.

Let $K=\lceil \ln(2n)U/0.99\rceil$.  Let $T=\ln(100)$.
Create $K$ tokens, each with an associated unit-rate Poisson process.
As time $t$ increases continuously from $0$ to $T$, do the following:
When a Poisson process fires at time $t$,
remove its token from its current set (if any),
then place it on a set $s$ chosen to maximize
$$
\sum_{e\in s}
\Big(
\frac{1-1/U}{1/f(t) - 1/U}
\Big)^{C^{(t)}_e},
$$
where $C^{(t)}_e$ denotes the number of tokens (other than the firing token)
currently covering element $e$, and $f(t) \doteq 1-\exp(-(T-t))$.
Return the sets that have tokens on them.

When a token fires, it moves
to a set whose elements have largest total ``weight''.
Initially, when $t\approx 0$, the weight of element $e$
is about $.99^{C_e} \approx 1$,
so the algorithm essentially moves tokens onto the largest sets.
When $t\approx T-\ln 2$, the weight of an element $e$ is about $.5^{C_e}$.
Thus, each token on a set covering $e$ cuts $e$'s weight by a factor of $1/2$.
Finally, when $t\approx T-\epsilon$, an element $e$ has weight about
$\epsilon^{C_e}$, so only uncovered (or minimally covered) elements contribute significant weight.

If $U$ is unknown,
then binary search can be used
to find the smallest integer $U$
between $1$ and $n$
for which the algorithm works.

Here is the approximation guarantee:

Theorem.
If there exists a fractional set cover of size $U$,
then, with probability at least 1/2,  the algorithm returns
a set cover of size at most $\lceil \ln(2n)U/0.99\rceil$.

For the derivation and proof see https://algnotes.info/on/obliv/greedy/set-cover-grasp/.

One more

Oh, and there is a well-known randomized parallel algorithm for set cover, namely Primal-dual RNC approximation algorithms for set cover and covering integer programs by Rajagopalan and Vazirani.


Exponential Speedup in External Memory Background

The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses).  These running times are generally given in terms of $M$, the size of memory, and $B$, the number of words that can be transferred to memory at one time.  Sometimes $L$ and $Z$ are used for $B$ and $M$ respectively.

For example, sorting requires a cost of $\Theta(N/B\log_{M/B} N/B)$ and naive matrix multiplication requires $\Theta(n^3/B\sqrt{M})$.

This model is used to analyze "cache-oblivious algorithms", which do not have knowledge of $B$ or $M$.  Generally the goal is for the cache-oblivious algorithm to perform optimally in the external memory model; this is not always possible, as in the Permutation problem for example (shown in Brodal, Faderberg 2003).  See this writeup by Erik Demaine for a further explanation of cache-oblivious algorithms, including discussions of sorting and matrix multiplication.

We can see that changing $M$ causes a logarithmic speedup for sorting and a polynomial speedup for matrix multiplication.  (This result is originally from Hong, Kung 1981 and actually predates both cache obliviousness and the formalization of the external memory model).

My question is this:

Is there any case where the speedup is exponential in $M$? The running time would be something like $f(N,B)/2^{O(M)}$. I am particularly interested in a cache-oblivious algorithm or data structure that fits this description but would be happy with a cache-aware algorithm/data structure or even a best-known lower bound.

It is generally assumed in most models that the word size $w = \Omega(\log N)$ if $N$ is the input size and clearly $M > w$.  Then a speedup of $2^M$ gives a polynomial speedup in $N$.  This makes me believe that if the problem I'm looking for exists, it is not polynomial.  (Otherwise we can change the cache size by a constant to obtain a constant number of I/Os, which seems unlikely).

I am not sure I understood the question.  But it seems to me that under the assumption that $PSPACE$ contains problems requiring exponential time, such problems would fulfill your requirements, since if $M$ is $O(\log N)$ you would need an exponential number of I/O operations (since you can't "stay" in the same memory block of size $O( \log N)$ more than a polynomial number of steps without going into a cycle) and if $M=N$ you would only need a linear number of I/O operations. Also, concerning your observation that such a problem cannot belong to $P$, it is correct if the speedup must hold for values of $M$ that are $\Omega(N)$ (since it would mean we have an exponential number of operations). But if the speedup only applies to smaller values of $M$, intuitively I believe this is not true, because I feel it should be possible to design a problem that is in fact the concatenation of smaller problems of size $O(\log N)$ each requiring exponential time in its own size, and an exponential number of I/O operations (that is, $poly (N)$, since $poly(N)$ is exponential in $O(\log N)$). In practice I believe $PSPACE$-complete problems such as $TQBF$ fulfill your condition.


Minimum cost topological ordering We are given a $n$ vertex directed graph $G=(V,E)$ and also given a cost function $c:V\times [n]\to \mathbb{R}$. Consider a topological ordering of the vertices, $v_1,\ldots,v_n$, the cost of the ordering is $\sum_{i=1}^n c(v_i,i)$.

Is finding the minimum cost topological ordering NP-hard?

Your problem is NP-hard. I show this by a reduction from the shuffle problem: given words $w, w_1, \ldots, w_k$ over the alphabet $\{a, b, c\}$, decide whether $w$ can be obtained as an interleaving (aka "shuffle") of $w_1, \ldots, w_n$. This problem is NP-hard: see Warmuth & Haussler, On the complexity of iterated shuffle, JCSS, 1984, Theorem 3.1.

Given an instance $w, w_1, \ldots, w_n$ of this problem, and writing $l_i := |w_i|$ for all $1 \leq i \leq n$, we build the DAG $G$ as a union of path graphs $L_1, \ldots, L_n$, where each $L_i$ for $1 \leq i \leq n$ has $l_i$ vertices written $v^i_1, \ldots, v^i_{l_i}$. Now, we define the cost function $f$ as follows: for each $1 \leq i \leq n$ and $1 \leq j \leq l_i$, for each $1 \leq k \leq |w|$, we set $f(v^i_j, k)$ to be $0$ if the $j$-th character of $w_i$ is the same as the $k$-th character of $w$, and $1$ otherwise.

This reduction is clearly in PTIME, and it is clear that the minimum cost of a topological sort is 0 iff there is an interleaving of the path graphs realizing exactly the word $w$, showing that the reduction is correct.

(Shameless ad: If you're interested in NP-hard variants of topological sorting, you may be interested about a recent preprint of mine which studies the complexity of finding topological sorts that fall into fixed regular languages.)


Treewidth and the NL vs L Problem ST-Connectivity is the problem of determining whether there exists a directed path between two distinguished vertices $s$ and $t$ in a directed graph $G(V,E)$. Whether this problem can be solved in logspace, is a long-standing open problem. This is called the $NL$ vs $L$ problem.

  What is the complexity of ST-Connectivity, when the underlying undirected graph of $G$ has bounded treewidth.

Is it known to be NL-hard ? Is there a $o({\log}^2n)$ upper bound known ?

It appears the problem is in L by [EJT10] and thus L-complete under $\text{NC}^1$ reducibility by [CM87]. See page 2 of [EJT10]:

  Applying Theorem I.3 to the formula $\phi(X)$ expressing that $X$ is a
  simple path from $s$ to $t$ shows that the problem $\{(G,s,t) \text{ }
  | \text{ tw$(G) \leq k$, there is a path from $s$ to $t$ in $G$}\}$
  lies in L

Actually this result applies to all problems on bounded treewidth graphs which can be formulated in monadic second-order logic in L.

[EJT10] Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 143–152, 2010.

[CM87] Stephen A. Cook, Pierre McKenzie: Problems Complete for Deterministic Logarithmic Space. J. Algorithms 8(3): 385-394 (1987)


Do you know this problem of deciding whether a given 0-1 matrix contains k pairwise disjoint “column-paths”? Problem: $X$
  Instance: A $m\times n$ 0-1 Matrix $A$,  $k \in \mathbb{N}$.
  Question: Does $A$ contain $k$ pairwise disjoint "column-paths"?

A column-path starts in the first column, ends in the last one
and traverses only 1-entries.  It may visit any row at most once.
Any 1 may be visited once only, by any path.

Example:

    $ A =
    \begin{pmatrix}
    a_{00} & a_{01} & a_{02} \\
    a_{10} & a_{11} & a_{12} \\
    a_{20} & a_{21} & a_{22} \\
    a_{30} & a_{31} & a_{32} \\
    \end{pmatrix}
     =
     \begin{pmatrix}
    0 & 1 & 0 \\
    1 & 0 & 0 \\
    1 & 0 & 1 \\
    0 & 1 & 1 \\
    \end{pmatrix}
    $

$A$ contains the paths $(a_{10},a_{01},a_{22})$, $(a_{10},a_{01},a_{32})$, $(a_{10},a_{31},a_{22})$
and $(a_{20},a_{01},a_{32})$. Since there are (only) 2 disjoint paths, i.e. the
last 2, $(A,2) \in X$.

It is easy to see, that this problem reduces to set packing. It
does not work so easily the other way around, because the set
packing instance may be too "restrictive".

Any idea what kind of problem this is?

(from comments, per request)

Here is a sketch of a polynomial-time solution.

First, interpret matrix $A$ as a bipartite graph $G=(V \cup U,E)$, with $m$ nodes in part $V$ and $n$ nodes in part $U$, $n \le m$. Then column-paths are $U$-saturating matchings, i.e., matchings of size $n$ (each node of $U$ is incident to precisely one edge in the matching).

The union of $k$ such matchings is a simple $k$-matching of size $kn$ (each node of $U$ is "covered" precisely $k$ times). Conversely, if there is a simple $k$-matching of size $kn$, by Hall's theorem there are also $k$ disjoint $U$-saturating matchings.

Hence to solve the problem it is enough to find a maximum-size simple $k$-matching. This is possible in polynomial time.

Some background:

A simple $k$-matching is a subset $M \subseteq E$ such that each node is incident to at most $k$ edges in $M$. A simple $1$-matching is a matching in the usual sense. For more information on (simple) $k$-matchings and algorithms for finding them, see, for example:

Korte & Vygen (2008): Combinatorial Optimization—Theory and Algorithms, 4th edition, Chapter 12.


Properties of convex polytope of 0-1 matrices Problem setting

Consider a set $ S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$.

Consider a $k\times k$  matrix $M$ s.t  $\;M_{ij} = \big|S_i\cap S_j\big|\big/n'$, size of the intersection of the $i^{th}, j^{th}$ subset divided by $n'$.

Question

Does $M_{ij}$ lie in the polytope of zero-one matrices? Paraphrasing the question - Can we express every $M_{ij}$ as a convex combination of zero-one matrices?

Sasho already gave you a yes/no answer, but here's an actual convex combination for you: If $B_\ell$ is the $k \times k$ matrix which is $1$ when $|S_i \cap S_j| \ge \ell$ and zero otherwise, then $M = \sum_{\ell=1}^{n'} \frac{1}{n'} B_\ell$.


Sampling from the binomial distribution with limited randomness and time This is a basic question that I can't answer (it's not a homework assignment).  A reference would be perfectly acceptable.

Consider a $[0,k]$ valued random variable X distributed binomially so that:

$$\text{Pr}[X=i]=\binom{k}{i}/2^k$$

It's clear that we can sample from $X$ in poly($k$) time using $k$ random bits.  The basic question is if it's possible to do better if I'm only interested in approximate sampling.

For example, if I'm interested in sampling from any $Y$ so that $|X-Y|<\epsilon$ (in statistical distance), can I do this in randomized time poly($1/\epsilon$) (i.e., with $1/\epsilon$ random bits)?

To exactly sample from the binomial distribution on $\{0,1,\cdots,n\}$ requires $n$ random bits. However, we can approximately sample with $O(\log(n/\varepsilon))$ bits, where $\varepsilon$ is the statistical distance from binomial we allow.

Let $$a_0=0, ~~~~a_{k+1}=a_k+{n \choose k} \cdot 2^{-n} ~~~~(k \in \{0,1,\cdots,n\}).$$ We can sample exactly from the binomial distribution by sampling $x \in [0,1)$ uniformly and then picking $k$ such that $x \in [a_k,a_{k+1})$. The probability of picking any given $k$ is thus $$\mathrm{Pr}_x[k]=\mathrm{Pr}_x[x\in[a_k,a_{k+1})] = a_{k+1}-a_k = {n \choose k} \cdot 2^{-n}.$$

We will sample approximately by sampling $\tilde{x} \in \{ 0, 1/m, 2/m, \cdots, (m-1)/m \}$ uniformly and then picking $k$ such that $\tilde{x} \in [a_k,a_{k+1})$. This requires $O(\log m)$ bits of randomness. We have $$\mathrm{Pr}_\tilde{x}[k]=\mathrm{Pr}_\tilde{x}[\tilde{x}\in[a_k,a_{k+1})]=\frac{\lceil m a_{k+1} \rceil - \lceil m a_k \rceil}{m}=a_{k+1}-a_k \pm \frac{1}{m} =\mathrm{Pr}_x[k] \pm \frac{1}{m}.$$
So the difference between the probability of $k$ under exact sampling and under approximate sampling is at most $1/m$. Summing over all $k$, we have that the statistical distance is at most $(n+1)/m$. Setting $m=O(n/\varepsilon)$ ensures that the approximate sampling is $\varepsilon$ statistically close to binomial.


Is there any natural Karp reduction from Independent Set problem to SAT? Is there a natural Karp reduction from Independent Set to SAT ? That is, a reduction that does not rely on the Turing machine (as the case in proof of Cook's theorem) but the combinatorial structure.

Yes, just think how you would use a SAT solver to solve the independent set problem.
If you have one variable per node, it should be clear how to write constraints that guarantee that variables that are true indeed form an independent set. I think the only non-trivial part is counting: how to make sure that your independent set is sufficiently large. For that you can use BDD-based techniques; see e.g. Section 5.3 of this paper.


Classifying reversible gates Post's lattice, described by Emil Post in 1941, is basically a complete inclusion diagram of sets of Boolean functions that are closed under composition: for example, the monotone functions, the linear functions over GF(2), and all functions.  (Post didn't assume that the constants 0 and 1 were available for free, which made his lattice much more complicated than it would be otherwise.)

My question is whether anything analogous has ever been published for classical reversible gates, like the Toffoli and Fredkin gates.  I.e., which classes of reversible transformations on {0,1}n can be generated by some collection of reversible gates?  Here are the rules: you're allowed an unlimited number of ancilla bits, some preset to 0 and others preset to 1, as long as all the ancilla bits are returned to their initial settings once your transformation of {0,1}n is finished.  Also, a SWAP of 2 bits (i.e., a relabeling of their indices) is always available for free.  Under these rules, my student Luke Schaeffer and I were able to identify the following ten sets of transformations:

The empty set
The set generated by the NOT gate
The set generated by NOTNOT (i.e., NOT gates applied to any 2 of the bits)
The set generated by CNOT (i.e., the Controlled-NOT gate)
The set generated by CNOTNOT (i.e., flip the 2nd and 3rd bits iff the 1st bit is 1)
The set generated by CNOTNOT and NOT
The set generated by the Fredkin (i.e., Controlled-SWAP) gate
The set generated by Fredkin and CNOTNOT
The set generated by Fredkin, CNOTNOT, and NOT
The set of all transformations

We'd like to identify any remaining families, and then prove that the classification is complete---but before we spend much time on it, we'd like to know whether anyone has done it before.

$\def\N{\mathbb N}\DeclareMathOperator\sym{Sym}\def\cC{\mathcal C}\def\cD{\mathcal D}\def\cP{\mathcal P}\def\cI{\mathcal W}\def\cMI{\mathcal{MW}}\DeclareMathOperator\pol{Pol}\DeclareMathOperator\inv{Inv}\DeclareMathOperator\minv{MInv}\let\pres\parallel$This is a presentation of one half of a duality for reversible transformations, analogous to the standard clone–coclone duality (such as here). It doesn’t answer the question, but it shows that all closed classes of such functions are determined by preservation of properties of a particular form.

In contrast to the standard case, the main complication is that permutations can count (they preserve cardinality), hence their invariants need to involve a bit of arithmetic to account for this.

Let me start with some tentative terminology. Fix a finite base set $A$. (In the classical case Scott asks about, $A=\{0,1\}$. Parts of the discussion also work for infinite $A$, but not the main characterization.)

A set of permutations (or: reversible transformations) is a subset $\cC\subseteq\cP:=\bigcup_{n\in\N}\sym(A^n)$, where $\sym(X)$ denotes the group of permutations of $X$. A permutation clone is a set of permutations $\cC$ such that

  Each $\cC\cap\sym(A^n)$ is closed under composition.
  For any $\pi\in\sym(\{1,\dots,n\})$, the permutation $\tilde\pi\in\sym(A^n)$ defined by $\tilde\pi(x_1,\dots,x_n)=(x_{\pi(1)},\dots,x_{\pi(n)})$ is in $\cC$.
  If $f\in\cC\cap\sym(A^n)$ and $g\in\cC\cap\sym(A^m)$, the permutation $f\times g\in\sym(A^{n+m})$ defined by $(f\times g)(x,y)=(f(x),g(y))$ is in $\mathcal C$.

Since $A$ is finite, 1 means that $\cC\cap\sym(A^n)$ is a subgroup of $\sym(A^n)$. The OP only demands 2 for transpositions $\pi$, but the version here is clearly equivalent. Condition 3 is equivalent to what I called introduction of dummy variables in the comments above.

A master clone is a permutation clone with allowance of ancillas:

  Let $f\in\sym(A^{n+m})$, $g\in\sym(A^n)$, and $a\in A^m$ be such that $f(x,a)=(g(x),a)$ for all $x\in A^n$. Then $f\in\cC$ implies $g\in\cC$.

We aim to characterize permutation clones and master clones by certain invariants. Let me first motivate the latter by a few examples on $A=\{0,1\}$:

The master clone of permutations preserving Hamming weight (generated by the Fredkin gate). If $w$ denotes the inclusion of $\{0,1\}$ in $\N$, these permutations are characterized by the property
$$y=f(x)\implies\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i),$$
where $f\in\sym(A^n)$, and I write $x=(x_1,\dots,x_n)$.
The master clone of permutations preserving Hamming weight modulo fixed $m$, mentioned in the comments. This is characterized by the same formula as above, if we interpret $w$ as a function from $\{0,1\}$ to the cyclic group $C(m)$, and compute the sum there.
The master clone of affine permutations $f(x)=Mx\oplus b$, $M\in\mathrm{GL}(n,\mathbb F_2)$, $b\in\mathbb F_2^n$ (generated by CNOT). One checks easily (or knows from the Post case) that a single-output function $\mathbb F_2^n\to\mathbb F_2$ is affine iff it preserves the relation $x^1\oplus x^2\oplus x^3\oplus x^4=0$. Thus, if we define $w\colon\{0,1\}\to\{0,1\}$ by
$$w(x^1,x^2,x^3,x^4)=x^1\oplus x^2\oplus x^3\oplus x^4,$$
an $f\in\sym(A^n)$ is in the clone iff
$$y^1=f(x^1)\land\dots\land y^4=f(x^4)\implies\max_{i=1}^nw(x^1_i,\dots,x^4_i)=\max_{i=1}^nw(y^1_i,\dots,y^4_i),$$
so we are dealing with sums in the monoid $(\{0,1\},0,\max)$.

In general, a weight function is a mapping $w\colon A^k\to M$, where $k\in\N$, and $M$ is a commutative monoid. A master weight function is one that maps all the diagonal $k$-tuples $(a,\dots,a)$, $a\in A$, to invertible elements of $M$. Let $\cI$ denote the class of all weight functions, and $\cMI$ the master weight functions.

If $f\in\sym(A^n)$, and $w\colon A^k\to M$ is a weight function, we say that $w$ is an invariant of $f$, or (mindlessly borrowing the terminology) that $f$ is a polymorphism of $w$, and write $f\pres w$, if the following condition holds for all $(x_i^j)_{i=1..n}^{j=1..k},(y_i^j)_{i=1..n}^{j=1..k}\in A^{n\times k}$:

  If $y^1=f(x^1),\dots,y^k=f(x^k)$, then
  $$\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i).$$

Here, $x^j=(x^j_1,\dots,x^j_n)$, $x_i=(x_i^1,\dots,x_i^k)$, and similarly for $y$. In other words, $f\pres w$ if $f$ (or rather its parallel extension to $(A^k)^n$) preserves the sum of $w$-weights of its arguments.

The relation $\pres$ between $\cP$ and $\cI$ (or $\cMI$) induces a Galois connection between sets of permutations $\cC\subseteq\cP$, and classes of weight functions $\cD\subseteq\cI$, in the usual way:
\begin{align*}
\pol(\cD)&=\{f\in\cP:\forall w\in\cD\,(f\pres w)\},\\
\inv^*(\cC)&=\{w\in\cI:\forall f\in\cC\,(f\pres w)\},\\
\minv^*(\cC)&=\cMI\cap\inv^*(\cC),
\end{align*}
and thus a dual isomorphism between the complete lattices of closed sets of permutations, and closed classes of (master) weight functions, respectively. To see that we are on the right track, we observe that closed sets of permutations are indeed clones:

  Lemma: If $\cD\subseteq\cI$, then $\pol(\cD)$ is a permutation clone. If $\cD\subseteq\cMI$, then $\pol(\cD)$ is a master clone.

Proof: The first assertion is more or less obvious. For the second, let  $w\in\cD$, $f,g,a$ be as in condition 4 so that $f\pres w$, and let $(x_i^j),(y_i^j)$ be as in the definition of $g\pres w$. Put $\bar x^j=(x^j,a)$, $\bar y^j=(y^j,a)=f(\bar x^j)$, and $u_i=w(a_i,\dots,a_i)$. Then $f\pres w$ implies
$$\sum_{i=1}^nw(x_i)+\sum_{i=1}^mu_i=\sum_{i=1}^{n+m}w(\bar x_i)=\sum_{i=1}^{n+m}w(\bar y_i)=\sum_{i=1}^nw(y_i)+\sum_{i=1}^mu_i.$$
However, $u_i$ are invertible in $M$ as $w$ is a master weight function, hence
$$\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i).\tag*{QED}$$

Before we proceed further, we need to fix one problem: monoids can be huge, hence invariants of this form can be rightly suspected of being useless abstract nonsense.

First, given a weight function $w\colon A^k\to M$, we can assume that $M$ is generated by $w(A^k)$ (and by additive inverses of images of diagonal elements in the master case), as other elements of $M$ do not enter the picture. In particular, $M$ is finitely generated. Second, by general results from universal algebra, we can write $M$ as a subdirect product
$$M\subseteq\prod_{i\in I}M_i,$$
where each $M_i$ is subdirectly irreducible, and $M_i$ is a quotient of $M$ via the $i$th product projection $\pi_i$; in particular, it is still a finitely generated commutative monoid. By a result of Mal'cev, f.g. subdirectly irreducible commutative monoids (or semigroups) are in fact finite. The mapping $w_i=\pi_i\circ w\colon A^k\to M_i$ is again a weight function, master if $w$ was, and it is easy to see that
$$\pol(w)=\bigcap_{i\in I}\pol(w_i).$$
Thus, we can without loss of generality restrict attention to weight functions $w\colon A^k\to M$, where $M$ is finite and subdirectly irreducible. Let $\mathcal{FW}$ be the class of such weight functions, and put
\begin{align*}
\inv(\cC)&=\mathcal{FW}\cap\inv^*(\cC),\\
\minv(\cC)&=\mathcal{FW}\cap\minv^*(\cC).
\end{align*}
Examples of finite subdirectly irreducible commutative monoids are the cyclic groups $C(p^d)$, and the truncated addition monoids $(\{0,\dots,d\},0,\min\{d,x+y\})$. The general case is more complicated, nevertheless one can say a lot about their structure: one can write each in a certain way as a disjoint union of a $C(p^d)$, and a finite nilsemigroup with some properties. See Grillet for details.

Now we are ready for the main point of this post:

  Theorem: The closed sets of permutations in the Galois connection to finite subdirectly irreducible (master) weight functions are exactly the permutation clones (master clones, resp.).

  That is, if $\cC\subseteq\cP$, then the permutation clone generated by $\cC$ is $\pol(\inv(\cC))$, and the master clone generated by $\cC$ is $\pol(\minv(\cC))$.

Proof: In view of the preceding discussion, it suffices to show that if $\cC$ is a permutation clone, and $f\in\sym(A^n)\smallsetminus\cC$, there is an invariant $w\colon A^k\to M$ of $\cC$ such that $f\nparallel w$, and one can take $w$ to be a master weight function if $\cC$ is a master clone.

Put $k=|A|^n$, and let $F$ be the free monoid generated by $A^k$ (i.e., finite words over alphabet $A^k$). We define a relation $\sim$ on $F$ by
$$x_1\cdots x_m\sim y_1\cdots y_m\iff\hbox{$\exists g\in\cC\cap\sym(A^m)\,\forall j=1,\dots,k\,g(x^j_1,\dots,x^j_m)=(y^j_1,\dots,y^j_m).$}$$
(Words of unequal length are never related by $\sim$.) Since each $\cC\cap\sym(A^m)$ is a group, $\sim$ is an equivalence relation (in fact, its restriction to words of length $m$ is just the orbit equivalence relation of $\cC\cap\sym(A^m)$ acting in the obvious way on $A^{mk}$). Moreover, $\sim$ is a monoid congruence: if $g\in\cC\cap\sym(A^m)$ and $g'\in\sym(A^{m'})$ witness that $x_1\cdots x_m\sim y_1\cdots y_m$ and $x'_1\cdots x'_{m'}\sim y'_1\cdots y'_{m'}$, respectively, then $g\times g'\in\cC\cap\sym(A^{m+m'})$ witnesses $x_1\cdots x_mx'_1\cdots x'_{m'}\sim y_1\cdots y_my'_1\cdots y'_{m'}$.

Thus, we can form the quotient monoid $M=F/{\sim}$. The swap permutation witnesses that $xy\sim yx$ for each $x,y\in A^k$; that is, the generators of $M$ commute, hence $M$ is commutative. Define a weight function $w\colon A^k\to M$ as the natural inclusion of $A^k$ in $F$ composed with the quotient map.

It is easy to see that $\cC\subseteq\pol(w)$: indeed, if $g\in\cC\cap\sym(A^m)$, and $y^1=f(x^1),\dots,y^k=f(x^k)$, then
$$\sum_{i=1}^mw(x_i)=x_1\cdots x_m/{\sim}=y_1\cdots y_m/{\sim}=\sum_{i=1}^mw(y_i)$$
by the definition of $\sim$ (using the notation as in the definition of $\pres$). On the other hand, assume $f\pres w$. Let $\{a^j:j=1,\dots,k\}$ be an enumeration of $A^n$, $b^j=f(a^j)$, and let $a_i,b_i\in A^k$ for $i=1,\dots,n$ be again as in the definition of $\pres$. Then
$$a_1\cdots a_n/{\sim}=\sum_{i=1}^nw(a_i)=\sum_{i=1}^nw(b_i)=b_1\cdots b_n/{\sim},$$
hence by the definition of $\sim$, there exists $g\in\cC\cap\sym(A^n)$ such that $g(a^j)=b^j=f(a^j)$ for each $j$. However, since the $a^j$ exhaust $A^n$, this means $g=f$, i.e., $f\in\cC$, a contradiction. This completes the proof for permutation clones.

Even if $\cC$ is a master clone, $w$ needn’t  be a master weight function, in fact, the diagonal elements are not even necessarily cancellative in $M$, hence we need to fix it. For each $c\in A$, let $c^*=(c,\dots,c)\in A^k$, and define a new equivalence relation $\approx$ on $F$ by
$$x_1\cdots x_m\approx y_1\cdots y_m\iff\exists c_1,\dots,c_r\in A\,x_1\cdots x_mc_1^*\cdots c_r^*\sim y_1\cdots y_mc_1^*\cdots c_r^*.$$
Using the fact that elements of $A^k$ commute modulo $\sim$, it is easy to show that $\approx$ is again a congruence, hence we can form the monoid $M'=F/{\approx}$, and a weight function $w'\colon A^k\to M'$. Since $\approx$ extends $\sim$, $M'$ is commutative, and a quotient of $M$; in particular, $\cC\subseteq\pol(w')$. On the other hand, if $f\pres w'$, then the same argument as above together with the definition of $\approx$ would give a $g\in\cC\cap\sym(A^{n+r})$, and $c_1,\dots,c_r\in A$ such that
$$g(x,c_1,\dots,c_r)=(f(x),c_1,\dots,c_r)$$
for all $x\in A^n$, thus $f\in\cC$ as $\cC$ is a master clone, a contradiction.

The definition of $\approx$ ensures that
$$xc^*\approx yc^*\implies x\approx y$$
for all $x,y\in F$, and $c\in A$. It follows that the elements $c^*/{\approx}=w'(c^*)$ are cancellative in $M'$. It is an easy well-known fact that any commutative monoid can be embedded in another one where all cancellative elements become invertible. The composition of such an embedding with $w'$ is then a master weight function $w''$, and $\pol(w')=\pol(w'')$, hence $w''\in\minv^*(\cC)\setminus\minv^*(f)$.  QED

EDIT: A generalization of the clone–coclone duality above is now written up in

[1] E. Jeřábek, Galois connection for multiple-output operations, preprint, 2016, arXiv:1612.04353 [math.LO].