What kind of language is needed to recognize an ordered list? [multihead automata, apparently] I'm considering the problem of recognizing a language (over alphabet 0-9 and space) containing strings like "1 2 3 4 5 6" and "14 15 16 17" but not "1 3".

This came up while working on a common parsing task where elements needed to be in an ordered list.  It struck me that while parsing the rest of that language was regular, this part was clearly irregular -- it can recognize, for example, the language A1A2 where A is an arbitrary string 0-9.  In fact it seems to be content-sensitive (and not context-free by the pumping lemma).

My first question: is there a (reasonably well-known, i.e. not defined just for this problem) class of languages between context-sensitive and context-free that describes its expressive power better?  I've read about Aho's indexed languages, but it's not obvious (to me!) that these are even in that class, powerful though it is.

My second question is informal.  It seems that this language is easy to parse, and yet it is very high on the hierarchy. Is it common to come across similar examples and is there a standard way of dealing with them?  Is there an alternate grouping of classes of languages that is incompatible with inclusion on the 'usual' ones?

My reason for thinking this is easy: the language can be parsed deterministically, by reading until you get to the end of the first number, checking if the next number follows, and so forth. In particular it can be parsed in O(n) time with O(n) space; the space can be reduced to $O(\sqrt n)$ without too much trouble, I think.  But it's hard enough to get that kind of performance with regular languages, let alone context-free.

It sounds like what you are looking for are multihead automata (in your case, 1-way 2-head deterministic finite automata should suffice). I'm not really an expert on these, but google turns up some interesting surveys on this language hierarchy, such as

Marek Chrobak: Hierarchies of one-way multihead automata, http://www.sciencedirect.com/science/article/pii/0304397586900939

This also gives one answer to your second question: The hierarchy of n-head automata lies "across" the Chomsky hierarchy.


A 3-CNF formula that requires resolution width $5$ Recall that the width of a resolution refutation $R$ of a CNF formula $F$ is the maximal number of literals in any clause occurring  in $R$. For every $w$, there are unsatisfiable formulas $F$ in 3-CNF s.t. every resolution refutation of $F$ requires width at least $w$.

I need a concrete example of an unsatisfiable formula in 3-CNF (as small and simple as possible) that has no resolution refutation of width 4.

The following example comes from the paper which gives a combinatorial characterization of resolution width by Atserias and Dalmau (Journal, ECCC, author's copy).

Theorem 2 of the paper states that, given a CNF formula $F$, resolution refutations of width at most $k$ for $F$ are equivalent to winning strategies for Spoiler in the existential $(k+1)$-pebble game.
Recall that the existential pebble game is played between two competing players, called Spoiler and Duplicator, and the positions of the game are partial assignments of domain size at most $k+1$ to variables of $F$.
In the $(k+1)$-pebble game, starting from the empty assignment, Spoiler wants to falsify a clause from $F$ while remembering at most $k+1$ boolean values at a time, and Duplicator wants to prevent Spoiler from doing so.

The example is based on (the negation of) the pigeonhole principle.

  For every $i \in \{1, \dotsc, n+1 \}$ and $j \in \{1, \dotsc, n \}$, let $p_{i,j}$ be a propositional variable meaning that pigeon $i$ sits in hole $j$.
  For every $i \in \{1, \dotsc, n+1 \}$ and $j \in \{0, \dotsc, n \}$, let $y_{i,j}$ be a new propositional variable.
  The following $3$-CNF formula ${EP}_i$ expresses that pigeon $i$ sits in some hole:
  $$ {EP}_i \equiv \neg y_{i,0} \wedge \bigwedge_{j=1}^n (y_{i,j-1} \vee p_{i,j} \vee \neg y_{i,j} ) \wedge y_{i,n}. $$
  Finally, the $3$-CNF formula ${EPHP}_n^{n+1}$ expressing the negation of the pigeonhole principle is the conjunction of all ${EP}_i$ and all clauses $H_k^{i,j} \equiv \neg p_{i,k} \vee \neg p_{j,k}$ for $i,j \in \{1, \dotsc, n+1 \}, i \ne j$ and $k \in \{1, \dotsc, n \}$.

Lemma 6 of the paper gives a fairly short and intuitive proof that Spoiler cannot win the $n$-pebble game on ${EPHP}_n^{n+1}$, hence ${EPHP}_n^{n+1}$ has no resolution refutation of width at most $n-1$.

The paper has another example in Lemma 9, based on the dense linear order principle.

Given that computing the minimum width for resolution refutations is EXPTIME-complete, and moreover it takes $\Omega(n^{(k-3)/12})$ time to certify that the minimum width is at least $k+1$ (see Berkholz's paper in FOCS or arXiv), perhaps it is hard to come up with examples which provably need wide resolution refutations?


What are some "must-read" papers for someone getting into Quantum Cryptography? I'm a graduate student that just finished a first course on quantum computation. I've also done a graduate-level course in (classical) cryptography.
I'm interested in Quantum Cryptography and would like to know what people would consider the most important papers for me to read if I want to get an intro to QC, for someone of my background. Any help would be much appreciated.

For an interesting starting paper, that nearly was never a paper see Stephen Wisener's paper on Conjugate Coding. This paper started off things like the BB 84. The paper is paywalled though, and a typewritten copy (with typos too,), as it was written sometime in the  60s or 70s is an interesting read, to start, or to get a historical perspective.


Pathfinding search over a space with known changing costs I'm working on a research project which involves iterative pathfinding over a space whose cells have danger values that change over time.

More specifically, the danger values represent bad weather, and the program uses ten days of weather predictions to find the best route across a section of the earth.

Formalized:
We're given a graph where, for each edge $e$, the cost on that edge when starting at time t is $c_e(t)$. Each edge takes one unit of time to traverse. Find the min-cost route from $u$ to $v$.

Up until now we've been using a modified A* search, however it is extremely inefficient and has become almost exhaustive.

Is there a better algorithm already out there for such a problem?

I've started to take a look at D* lite, but I don't believe it's the best solution, because we already know what the cost at time t.

Any advice is much appreciated.

Cheers,

Arek Sredzki

In general, finding least-cost paths with arbitrary time-dependent edge costs is NP-hard, assuming that either (a) waiting at nodes is forbidden and your costs are not FIFO-preserving (e.g., see here for brief discussion on this complexity, as well as others: https://www.cs.ucsb.edu/~suri/psdir/soda11.pdf) or (b) the cost you are trying to optimize is not simply pure travel time itself (e.g., see http://algo2.iti.kit.edu/download/gen_obj_func_tch.pdf).

As an illustrative example of this latter situation (which seems most similar to yours) and continuing with your suggested notation, it is shown in the second paper above that it is NP-hard for the case in which the time-dependent edge cost is defined in the form $c_e(t) = f_e(t) + d_e$, where $f_e$ is the (typical) time-dependent travel-time function that returns the travel time along the edge for a particular time of day $t$ and $d_e$ is some arbitrary time-neutral cost function. It is not hard to show that similar hardness results for other such cases as well, where, e.g., the function uses a multiplier instead of addition (i.e., $c_e(t) = f_e(t) \cdot d_e$), and so on.

Regardless, one can derive pseudo-polynomial time bounds on such cases if, e.g., you are representing your time instants as integer values and assuming there are only a finite number of possible time instants bounded by $T$. In this way, you only need to maintain a single least-cost path per time instant $t$ for any given node in the graph, which would give you the running time of $O(T(m + nlogn))$, assuming non-negative cost functions. Taking this idea a step further, since your particular use case assumes that "each edge takes one unit of time to traverse", then this automatically gives you a strongly-polynomial-time algorithm since, in your case, $T \in O(n)$ (because each such path contains $\leq n-1$ edges).


Lovasz theta function and regular graphs (odd cycles in particular) - connections to spectral theory The post is related to:
https://mathoverflow.net/questions/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles

How far away is the Lovasz bound from the zero-error capacity of regular graphs? Are there any examples where the Lovasz bound is known to be not equal to the zero-error capacity of a regular graph? (This was answered below by Oleksandr Bondarenko.)

In particular is any strict inequality known for odd cycles of sides greater than or equal to $7$?

Update
What improvement is needed in spectral theory to improve the Lovasz theta function so that the gap between Shannon capacity and Lovasz Theta for the cases for which a gap exists could be lowered? (Note I am concerned only from spectral perspective)

In fact there is known a regular graph $G$ for which zero-error capacity  $\Theta(G)$ is less than the Lov$\acute{a}$sz bound $\vartheta(G)$. W. Haemers in $[1]$ has proved that for the complement of Schl$\ddot{a}$fli graph $G$ the following holds: $\Theta(G)\leqslant7<\vartheta(G)=9$.

In $[2]$ it is noted that "The best known upper bounds on $\Theta(C_m)$ and $\Theta(\overline{C}_m)$ for $m$ odd and greater than $5$ are given by the Lovasz theta function ...". From this I conclude that that the answer to your last question is no (since then I don't know any results improving on this.).

Finding Shannon capacity even for $C_7$ would be a major breakthrough for this hard problem. Additionally, it can be noticed that

  "it is not known if the problem of deciding whether the Shannon capacity of a given input graph exceeds a given value is decidable".

W. Haemers, “On some problems of Lov$\acute{a}$sz concerning the Shannon capacity of a graph,” IEEE Trans. on Information Theory, vol. 25, no. 2, pp. 231–232, Mar. 1979.
T. Bohman, "A limit theorem for the Shannon capacities of odd cycles. II," Proceedings of the American Mathematical Society, 2005.
N. Alon, "Combinatorial Reasoning in Information Theory".


Testing whether a set of n points in the plane form a convex n polygon in o(nlogn) time Assume that you are given a set of n points in the plane and you want to check whether they form a convex n polygon, i.e., if they all lie on the convex hull. I was wondering if anyone knows how to do this in o(nlogn) time, i.e., without computing the CH.

Thats seems unlikely, at least in the comparison/algebraic tree models. Definition first:

A point set $P$ is in convex position if no point of $P$ can be written as a convex combination of the remaining points of $P$.

Now, deciding if a set of $n$ numbers are all distinct takes $\Omega(n \log n)$ time (this is known as UNIQUENESS). Given such a set of $n$ numbers $X$, map them to the set of points
$$
P = \{ (x, x^2) | x \in X\}.
$$
If there is no repeated number, then the points are in convex position.

If there is a repeated number, then this repeated number corresponds to a point that can be written as a convex combination of the remaining points. Namely, the points are not in convex position.

Namely, deciding if a point set is in convex position is as hard as UNIQUENESS.


Monotonicity and Threshold function I have a question about a answer of a question which is proposed in this stack exchange.

The Past Question

One of the most basic result in circuit complexity is the constnat depth cirdcuit lower bound computing PARITY function using the switching lemma.

Another popular function MAJORITY has also lower bound $exp (\Omega (n^{1/(d-1)}))$ and matching upper bound $exp (O (n^{2/(d-1)}))$.

My question is about upper bound of Threshold function which is a natural generalization of majority function.

The formal definition of the threshold function is the following one.

DEFINITION:

$THR(x_{1},...,x_{n})=
  \begin{cases}
    1 & a_{1}x_{1}+\cdots +a_{n}x_{n} \geq t \\
    0 & otherwise
  \end{cases}
$

We assume that each weight $a_{i} \in \mathbb{Z}$ is at most $2^{O(n)}$

QUESTION1:
The depth $d$ circuit with unbounded fanin AND OR NOT gates to compute the above function has size $2^{n^{\epsilon}}$ ?

Where $\epsilon $ can depend on $d$ like $2^{n^{1/100d}}$ .

Answer

Kristoffer Arnsfelt Hansen said that:

1.$General$ $weight$ $threshold$ $gates$ can be computed by polynomial size depth 2 circuits built from $majority$ $gates$. An efficient construction of this is e.g. given by Amano and Maruoka. Then you can just compute each of these by constant depth circuits built from AND and OR gates.

My Question

$majority$ $gates$ is a monotone gate which is computes a monotone function. A monotone functin does not decreace its function value by increasing the number of "1"s in the input 0-1 bit string. However, $General$ $weight$ $threshold$ $gates$  is NOT a monotone function. For example, we can check the function which output 1 if and only if $2x_{1} -5x_{2} + 3x_{3} \geq 3.5$ is not a monotone function because increasing the value of  $x_{2}$ brokes the monotone property.

My question is :

For a givern arbitrary threshold function $THR:\{0,1\}^{n}\rightarrow \{0,1\}$ with arbitrary real number weights and with no monotonicity, can we construct a constant depth circuit with $poly(n)$ threshold gates such that for any gate, any weight of the gate is integer number and is at most $poly(\Delta) $, where $\Delta$ is fan-in of the gate?

If I understand your question correctly the answer is yes. In the paper

"Majority Gates Vs. General Weighted Threshold Gates" (http://www.nada.kth.se/~johanh/majorityvsthreshold.pdf) by Goldman, Håstad, and Razborov

They show that anything that can be computed by a depth $d$ threshold circuit can be computed by a depth $d+1$ unweighted threshold circuit of poly size.

Your question seems to be a special case of this for $d=1$.


How to Quantify Entropy in a Data Set I'm currently creating a program in Java to analysis the pathological cases of Quicksort. Namely, the transition of complexity from O(n^2) to O(nlogn) as a data set gets less ordered. Since Quicksort is a value-based algorithm, the choice of pivot determines its efficiency. We usually (Quicksort 3, and choosing a random element aside) select the first or last element as the pivot in an array. Therefore, since a good pivot is one that splits the array in half symmetrically, a more disordered array will make selecting a good pivot easier; or at least reduce the likely hood of running into the pathological case.

My program gradually randomises this array by swapping some elements each time. When I started to plot the graph of this using gnuplot I notice the trend I expected; a exponential distribution, branching off to a uniform distribution.

My question is, how do I quantify a level of disorder in a array? Is their a better way to gradually make an array of values more disordered?

Inversions are one way to measure "disorder" in a list:

  Let $A[1..n]$ be an array of $n$ distinct numbers.  If $i < j$ and $A[i] < A[j]$ then the pair $(i,j)$ is an inversion of $A$.

However, it's not the only such measure. In general, this concept is formalized in the notion of presortedness - roughly:

  An integer function on a permutation $\sigma$ of a totally ordered set that reflects how much $\sigma$ differs from the total order.

The survey papers by Mannila [1] and Estivill-Castro & Wood [2] might be good places to start.

The question How to measure "sortedness" is related.

[1] Heikki Mannila. "Measures of Presortedness and Optimal Sorting Algorithms." IEEE Transactions on Computers 34.4 (1985): 318-325.

[2] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.


What is known about the relationship between PR and NEXP? For the longest time I was under the impression that PR contains NEXP.  Try as I might, I am unable to recall where I picked up this notion.  I've looked recently, but I have not been able to find anything about what is known about their relationship.

All that I can currently conclude about them is that it's almost certainly not the case that PR = NEXP, as there are known NEXP-complete problems, while the notion of completeness for PR is problematic.

  What is known about the relationship between PR and NEXP?

Transforming the comments above into an answer:

NEXP is strictly contained in PR. Indeed define the class ELEMENTARY as
$$\mathsf{ELEMENTARY}=\text{DTIME}(2^n)\cup \text{DTIME}(2^{2^n}) \cup \text{DTIME}(2^{2^{2n}}) \cup ...$$

It can be shown that ELEMENTARY is strictly contained in PR. Since $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$ we have that $\mathsf{NEXP}$ is strictly contained in $PR$.

As pointed out by Huck Bennett above, the fact that $\mathsf{NEXP}\subseteq \mathsf{ELEMENTARY}$
is a consequence from the fact that

$$\mathsf{NEXP} = \text{NTIME}(2^{\text{poly}(n)}) \subseteq \text{DTIME}(2^{2^{2^n}}) \subsetneq \mathsf{ELEMENTARY}$$


Find a function that combines a set of integers and outputs an integer. This output can be used to deduce the absence of any integer in the set. Lets say that I have 50 events that generate some unique number (you are free to choose the number, but they should all fit in a 32 bit variable). I want to combine those numbers into a single number(32 bit), which can be used to find the absence of an event (i.e. a number).

If it was just ~10 events, I could have just used prime numbers and multiplied them, but multiplying first 50 primes results in 1.9x10^91 (which will not fit in a 32 bit variable).

Can anyone think of a better way to do this?

Well, is it only one missing event you want to detect? It you need to be able to detect the presence or absence of all 50 events, this means distinguishing between $2^{50}$ possibilities which obviously cannot be done with 32 bits. However if you wish to just detect a single missing event, here is a way that will work. Assume you have m events.

Assign each event a sequential number starting at 2.
Calculate $c = (m+1)! \mbox{mod}~p$, where p is some prime number greater than m+1 but less than $2^{32}$.
When registering the events, simply multiply the numbers corresponding to the events sequentially modulo p. Call this result r.
To determine if an event is missing, calculate $x = (c \times r^{-1}) \mbox{mod}~p$. If $x=1$ then no events are missing, otherwise $x$ is the label for the missing event.

UPDATE

A simpler solution (coming from Jukka's comment) is simply to do the following:

Assign each event a sequential number starting at 1.
Calculate $c = \sum_{j=1}^m j~ \mbox{mod}~2^{32} = \frac{j(j+1)}{2} \mbox{mod}~2^{32}$.
When registering the events, simply add the numbers corresponding to the events sequentially modulo $2^{32}$. Call this result r.
To determine if an event is missing, calculate $x = (c - r) \mbox{mod}~2^{32}$. If $x=0$ then no events are missing, otherwise $x$ is the label for the missing event.


Problems equivalent to the existence of secure cryptosystems? What are some necessary and sufficient conditions for the existence of following?

Symmetric encryption (defined here as satisfying $\text{IND-CPA}$ and $\text{INT_CTXT}$)
Asymmetric encryption
Digital signatures
Key exchange

Ignore quantum computing for the moment.

One-way functions are implied by all of these things, and known to imply symmetric encryption and digital signatures. These equivalences are indeed found in (theoretically-focused) text books.

The situation for key exchange and asymmetric (i.e., public-key) encryption is a less clear. Asymmetric encryption implies key exchange.

Implications in the other direction (from OWF to KE or KE to AE) are not known--in fact, there is evidence that there are no black box reductions of this type. This line of work started with the seminal paper of Impagliazzo and Rudich, and is nicely summarized (as of circa 2000) here: groups.csail.mit.edu/cis/pubs/malkin/GKMRV.ps

I think that the simplest generic assumption known to imply asymmetric encryption is the existence of trapdoor injective one-way functions. However, not think all known PKE schemes imply the existence of trapdoor injective OWF (lattice-based schemes imply something messier). So again, there is no simple answer.

Much of this latter material is not covered in standard text books; you have to read papers to find it. (I hope my own answer is up to date!)


Data structure to determine if sets are disjoint in o(n) time My initial question was exactly the title of this post, but after feedback from commenters I have formulated a more precise version of the question that attempts to capture its essence.

Does there exist an encoding of length-$n$ bit strings with the following properties?

The encoding can be computed in $o(n^2)$ time and space, i.e., the encoding $e\colon \{0,1\}^n\to \{0,1\}^{o(n^2)}$ factors as a composition of $o(n^2)$ elementary bitwise operations.
There exists an algorithm computing the disjoint set function with respect to this encoding in $o(n)$ time, i.e., the disjoint set function $e\bigl(\{0,1\}^n\bigr)^2\to \{0,1\}$ factors as a composition of $o(n)$ elementary bitwise operations.

Note: this is inspired by a comment on this unsolved question https://cs.stackexchange.com/questions/96222/find-common-min-in-logarithmic-time

The communication complexity of the set disjointness problem is $\Omega(n)$.  The communication complexity is a lower bound on the time complexity of testing whether the two instances are disjoint.  Imagine Alice stores the data structure for the first set, and Bob stores the data structure for the second set; since they'll have to communicate $\Omega(n)$ bits to determine whether their sets are disjoint, any algorithm that works on these two data structures will also necessarily involve doing at least that much computation.  It follows that testing disjointness of these two sets must take $\Omega(n)$ time, no matter what data structure you use, as long as each data structure is initialized separately.

Consequently, no such data structure exists.

Details: I'll elaborate on the proof more carefully, by sketching the reduction.

Suppose there was such a data structure, together with an algorithm $A$ that lets you test disjointness in $o(n)$ time.  Since it runs in $o(n)$ time, it must involve examining at most $o(n)$ bits of data, and in particular, at most $o(n)$ bits of the data structure for the first set and at most $o(n)$ bits of the data structure of the second set.

So, here is a communication protocol for set disjointness.  Initially, Alice initializes an instance of the data structure with her set, and Bob does the same with his set.  Start running algorithm $A$, with both of them executing the algorithm in lockstep.  Any time that algorithm $A$ examines a bit of the first data structure, Alice sends that bit to Bob.  Any time that the algorithm examines a bit of the second data structure sends that bit to Bob.  Now both Alice and Bob can execute the algorithm to completion.  At the end of the algorithm, both Alice and Bob know whether their sets are disjoint are not.  Also, the computation has taken $o(n)$ time, and they have sent only $o(n)$ bits of data (since it runs in $o(n)$ time, it can't send more than that), so we have a protocol for set disjointness with communication complexity $o(n)$.  This is impossible, so our original assumption that such an algorithm $A$ exists must also have been impossible as well.

If algorithm $A$ is randomized, then it's easy enough to send the random bits to both parties.  This doesn't affect the asymptotic complexity.

If the algorithm is in the RAM model, it can access $O(\log n)$ bits in a single operation, so we need to modify the above reduction slightly: if there is an algorithm $A$ for set disjointness that runs in $o(n/\log n)$ time, we obtain a communication protocol that sends $o(n)$ bits.  It follows that any algorithm $A$ for set disjointness must take at least $\Omega(n/\log n)$ time in the RAM model.  Since the RAM model is a standard assumption, perhaps it would be more reasonable to summarize this result as implying that disjointness queries must take at least $\Omega(n / \log n)$ time, in the worst case, no matter what data structure you use, as long as each instance of the data structure is initialized separately.


Bloom filter for storage I am reading about the Bloom filter, and I must say I am fascinated by the idea. I would like to know if it is possible to use it for storage.

The problem with the Bloom filter is that, even if we accept that there will be false positives, the set of elements that we need to scan to see which ones are present may be very large (assuming that such set is finite). I would like to know if there is a smart way to reduce the complexity of such problems, namely, the complexity associated to the task of finding which elements are currently stored in the Bloom filter (of course with error due to false positives, if any).

Is there any techniques in the literature that I can look at to reduce the complexity of such task?

There is a data structure called an "invertible Bloom filter" due to Goodrich and myself that can be used for storage: you can add and remove keys and, whenever the current number of keys is below the capacity of the structure, determine what they are with high probability (regardless of whether it was ever above capacity in the past). Goodrich and Mitzenmacher have generalized this to allow values to be associated with the keys as well.

However, one drawback to these structures is that they use quite a bit more space than a normal Bloom filter: basically, a logarithmic number of bits per key rather than a constant number of bits per key.

See

Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters.
D. Eppstein, and M. T. Goodrich.
arXiv:0704.3313.
IEEE Trans. Knowledge and Data Engineering 23(2): 297-306, 2011.

and

Invertible Bloom Lookup Tables
Michael T. Goodrich, Michael Mitzenmacher
arXiv:1101.2245


What class of languages is recognized by finite-state automata with $k$ heads? A DFA or NFA reads through an input string with a single head, moving left-to-right. It seems natural to wonder about finite-state machines that have multiple heads, each of which moves through the input from left-to-right, but not necessarily at the same place in the input as the others.
Let us define a finite state machine with $k$ heads as follows:

A k-head NFA is a tuple $(Q, \Sigma, \Delta, q_0, F)$, where:

As usual, $Q$ is a finite set of states, $\Sigma$ is a finite alphabet, $q_0$ is an initial state, and $F$ is a set of accepting states. Let $\Sigma_\varepsilon := \Sigma \cup \{\varepsilon\}$ denote the set of characters including the empty string.

$\Delta \subseteq Q \times (\Sigma_\varepsilon)^k \times Q$ is the transition relation: a transition $(p, (\sigma_1, \sigma_2, \ldots, \sigma_k), q)$ means that, if the machine is in state $p$, it may read in $(\sigma_1, \sigma_2, \ldots, \sigma_k)$ such that $\sigma_i$ is the next character for head $i$ (or $\varepsilon$ if that head does not move), and then move to state $q$.

A run of this kind of machine (any path starting from the start state and ending in an accepting state) results in not one string, but $k$ different strings (formed by concatenating the characters along the run). Then we say that the run is valid if the $k$ strings are identical.
The language of the machine is the set of strings $w$ such that there exists a valid run of the machine where the $k$ strings produced along that run are all equal to $w$.

Question: What is the class of languages recognized by such machines? Has it been studied?

A first observation is that such machines produce a class larger than the regular languages. For example, the language
$$
\{a^n b^n \mid n \in \mathbb{N}\}
$$
is recognized by the following $2$-head NFA with $3$ states:

(Here, an edge labeled with $\sigma_1 / \sigma_2$ denotes a transition of the form $(p, (\sigma_1, \sigma_2), q)$.)
However, a second observation is that not all context-free languages are recognized; for example, it seems that the Dyck language cannot be recognized by these $k$-head machines.

This model is one of the standard models in automata theory and it has been examined by some researchers.

The references given in the first comment are very good starting points.

When the head is two-way, the classes of languages recognized by such models are identical to logarithmic-space classes. However, when the head is one-way, then, up to my knowledge, we do not have a similar exact characterization, but, we have certain incomparable results and some hierarchies based on the number of heads.

If you are interested in, I recommend you to check alternating, probabilistic, and quantum versions of multi-head automata, as well. Such models can be quite interesting even when using a single head, as the computation is split in into different paths, and then, in each path, the head may access different part of the inputs.

Some generic references:

Turing Machines with Sublogarithmic Space - https://books.google.lv/books?id=vNPuNOo9BUYC

Alternation

Viliam Geffert - https://dblp.uni-trier.de/pers/hd/g/Geffert:Viliam

Probabilistic computation

Ioan I. Macarie - https://dblp.org/pers/hd/m/Macarie:Ioan_I=

Probabilistic and quantum computation

Rusins Freivalds - https://dblp.uni-trier.de/pers/hd/f/Freivalds:Rusins
Abuzer Yakaryilmaz - https://dblp.uni-trier.de/pers/hd/y/Yakaryilmaz:Abuzer

Related models: multi-counter automata and automata using pebble.


Log space algorithms for modular decomposition tree Can we have log space algorithms for modular decomposition tree (see definition) for any graph?

If not, can we have log space algorithms for modular decomposition tree for any particular graph class?
If yes, then I would appreciate a pointer to the graph class or a reference.

Finally, can we have parallel algorithms for modular decomposition tree?

There is a logarithmic-space algorithm for the modular decomposition of any graph.

The result is part of the paper "Capturing Polynomial Time using Modular Decomposition", which will appear at LICS 2017 (http://lics.rwth-aachen.de/lics17/).
It is also part of the PhD thesis of the author. A preliminary version can be found here:
https://www2.informatik.hu-berlin.de/~grussien/grussien-pre-phd-thesis.pdf.

The algorithm uses the connection between modules and transitive orientation that was first shown by Gallai in 1967 and combines this with Reingold's logspace algorithm for undirected reachability. Given two vertices u and v, it can compute the minimal module containing both vertices. (A naive implementation of this closure would need some form of directed reachability.)
Every module of the modular decomposition tree is equal to the union of certain modules that are minimal containing two vertices.


A conjecture related to the Cerny conjecture - counterexample/reference request The Cerny conjecture is the statement that any synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. The best current upper bound for the length of a synchronizing word is $O(n^3)$. Let's say that two states are merged by a word if that word takes the two states to the same state. A pumping lemma type argument shows that in a synchronizing automaton, any two states can be merged by a word of length at most $n^2$. Suppose that the following conjecture is true.

Conjecture. Any subset of $k$ states contains two states that can be merged by a word of length (say) at most $n^2/k$. Or more generally, any large set of states contains two that can be merged by a word of length $o(n^2)$.

Then we can consider the following strategy for constructing a synchronizing word. We start with all $n$ states. By the conjecture above, there is a short word merging two states, and we make this the beginning of our synchronizing word. We can run the DFA with this word starting from all states, and we get a set of at most $n-1$ final states. We repeat this with these final states as our new start states. After repeating this a sufficient number of times, we only end up with one final state. Clearly, given the above conjecture, we would have a better bound than $O(n^3)$ for the length of the shortest synchronizing word.

The above motivates the following questions:

Are there any known counterexamples to this conjecture? Cerny's original construction (see page 18) satisfies the statement of the conjecture.
Could you provide a reference where similar ideas are investigated?

I found a partial answer to question 2. The same idea is discussed in the last 10 minutes of this lecture.


Clustering formalizations other than K-means for separable data Real world data sometimes has a natural number of clusters (trying to cluster it into a number of cluster lesser than some magic k will cause a dramatic increase the clustering cost). Today I attended a lecture by Dr. Adam Meyerson and he referred to that type of data as "separable data".

What are some clustering formalizations, other than K-means, that could be amenable to clustering algorithms (approximations or heuristics) that would exploit natural separability in data?

One recent model trying to capture such a notion is by Balcan, Blum, and Gupta '09.  They give algorithms for various clustering objectives when the data satisfies a certain assumption: namely that if the data is such that any $c$-approximation for the clustering objective is $\epsilon$-close to the optimal clustering, then they can give efficient algorithms for finding an almost-optimal clustering, even for values of $c$ for which finding the $c$-approximation is NP-Hard.  This is an assumption about the data being somehow "nice" or "separable."  Lipton has a nice blog post on this.

Another similar type of condition about data given in a paper by Bilu and Linial '10 is perturbation-stability.  Basically, they show that if the data is such that the optimal clustering doesn't change when the data is perturbed (by some parameter $\alpha$) for large enough values of $\alpha$, one can efficiently find the optimal clustering for the original data, even when the problem is NP-Hard in general.  This is another notion of stability or separability of the data.

I'm sure there is earlier work and earlier relevant notions, but these are some recent theoretical results related to your question.


Petri net termination Termination is the following problem.
Input: a Petri Net with initial marking
Output: "yes" iff there exists an infinite firing sequence. The naive algorithm in the case of bounded nets for example consists in running the net until either all configurations have been reached or a repeating one is found. Is there any clever way to solve the problem? What is the lower bound complexity?

Testing whether a Petri net $\mathcal{N} = (P, T, F)$ does not terminate from a marking $M_0$ can be decided by testing whether there exist a firing sequence $\sigma$ and markings $M, M'$ such that $M_0 \rightarrow^* M \rightarrow^\sigma M'$, $|\sigma| > 0$ and $M' \geq M$. By [Rac78], if such a firing sequence exists, then there is one of length doubly exponential. Thus, it can be guessed non deterministically, which shows that the problem is in EXPSPACE. By [Lip76], the problem is EXPSPACE-hard and hence EXPSPACE-complete. See, e.g., Section 3.2.4 of these lecture notes for a presentation of Lipton's reduction.

[Rac78] Charles Rackoff. The covering and boundedness problems for vector addition systems. Theoretical Computer Science, 6:223–231, 1978.

[Lip76] Richard J. Lipton. The reachability problem requires exponential space. Technical report 63, Department of Computer Science, Yale University, 1976.


Resolution vs Nondeterministic Search Problems It is well known that each resolution refutation $\Pi$ for an unsatisfiable CNF formula $F = C_1\wedge C_2 \wedge ... \wedge C_m$ over variables $X$ can  be translated in polynomial time (in the size of $\Pi$) into a deterministic branching program $P$ solving the following search problem:

1) $P$ has one source node and one sink node for each clause $C_i$.

2) For each assingment $\alpha:X\rightarrow  \{0,1\}$ there is a consistent path in $P$ from the
source node to some sink node associated with a clause that is falsified  by $\alpha$.

Question:
Is there a proof system strictly stronger than resolution where each proof $\Pi$ can be translated in polynomial time (in the size of $\Pi$) into a not necessarily deterministic branching program $P$ solving the search problem above?

If I understood correctly the question, the so-called Buss-Pudlak game provides a simple transformation from a proof system to such a decision tree (see Buss-Pudlak '94 http://math.cas.cz/%7Epudlak/howtolie.ps). The queries are formulas (not just variables). The tree is also completely deterministic.

Other decision trees that correspond to different propositional proof systems exist: e.g., Linear Decision Trees correspond to Res(lin) refutations (cf., http://www.csc.kth.se/~sokolovd/files/papers/splitting.pdf and http://cs.rhul.ac.uk/home/tzameret/Res-Lin-Two.pdf). But there are many other examples (cf., Tonian Pitassi's work on CP-like proof systems).


Another edge partitioning problem on cubic graphs This question was motivated by a closely related problem
An edge partitioning problem on cubic graphs

Input: at most cubic graph ( maximum node degree is 3) $G=(V,E)$, a natural number $k$

Question: Is there a partition of $E$ into subgraphs isomorphic to $K_{1,2}$ and $K_{1,1}$  such that the sum of the orders of the corresponding subgraphs is exactly $k$ ?

  Is this problem polynomial time solvable or is it $NP$-complete?

Edit: Changed input graph to at most cubic graphs to avoid triviality.

Perhaps I don't understand the question, but the way I interpret it, Colin's answer seems correct. It is enough to find the minimum possible k for which such partition exists, say k_0. (This is a partition with maximum number of K_21's.) There is a partition for any k between k_0 and 3n/2, because splitting K_21 into two K_11's increases the sum of cardinalities by 1. The K_21's in your partition induce a matching in the line graph of G, so this k_0 corresponds to the maximum matching in the line graph, and this matching can be found in polynomial time.


Abstract definition of universal computation There are many universal computation systems. Turing machines, tag systems, rewrite systems, cellular automata to name just a few. The universality of a system is proved via reduction from a known universal (Turing-complete) model.

I am wondering if it is possible to define abstract conditions, that make each of the systems universal. For example, in definitions of algebraic structures, there are conditions (like: Closure, Associativity, etc.) that can be examined in a structure to determine if it is e.g. a group. There is no reduction from other structure, that is already known to be group.

Is it possible to define in similar way the universality? Are there any related works on the topic?

Have a look at the work of Alex Heller and Robert di Paola on dominical categories. There should be further references there to older work.


Application of methods from dynamical system to the study of k-SAT and similar problems I am looking for literature (survey and non-survey papers) about
transforming the k-SAT problem (or similar problems) into
a system of Ordinary Differential Equations (ODEs) and
study the solution of the k-SAT using methods from dynamical systems theory,
such as computing stable/unstable manifolds,
dynamics on strange attractors,
fixed point theory and so on.

Motivation:
I am not a computer scientist. I am a researcher working in the areas of applied dynamical systems, with focus on applying geometrical and topological methods to study chaotic phenomena. I am always looking for application of the nonlinear dynamical systems theory and I happened to come across the following paper today:
Optimization hardness as transient chaos in an analog approach to constraint satisfaction by Ercesy-Ravasz and Toroczkai, Nature Physics 2011
This paper is very interesting to me, and most of the dynamical systems theory used in it is pretty standard fare these days in my community.
I am looking for CS references that will help me understand the CS-part of this, mainly about solving problems like k-SAT using dynamical systems.

in my opinion after looking into this to some degree, you will probably not do any better than the paper you've cited for background and references which are extensive. the authors specifically indicate that they have devised a novel approach that does not seem to have any direct precedent in the literature, and this seems correct. in other words, as they state themselves:

  Here we present a novel continuous-time dynamical system for k-SAT, with a dynamics that
  is rather different from previous approaches.

so their formulation (in the introduction, eg eqs.1,2) can be seen/regarded as a seminal new "bridge theorem" between two previously mainly different fields of dynamical systems theory and the theory of NP completeness.

this has happened many times in the past with NP completeness, and an early notice of this came in 1988 by Papadimitriou, in NP Completeness, a retrospective, which can be seen as a kind of TCS sequel/analog to the famous essay Unreasonable effectiveness of mathematics in the physical sciences, Wigner.

they cite the following as nearest references to their work:

  Although the theoretical possibility of efﬁcient computation via chaotic dynamical systems has been shown previously [15], nonlinear dynamical systems theory has not been
  exploited for NP-complete problems in spite of the fact that, as shown by Gu et al.[19], Nagamatu
  et al. [20] and Wah et al. [21], k-SAT can be formulated as a continuous global optimization
  problem[19], and even cast as an analog dynamical system [20, 21].

in SAT literature Mezard was a pioneer in introducing statistical physics analogies which have some strong connections to their new framework, but again they cite him.

here are two other sideways angles outside the paper references. Linear programming algorithms have a concept of continous variables, iteration and convergence somewhat analogous to a constrained dynamical systems trajectory. there is a significant amount of research in this vein under the heading of Maslov's method. here is another early reference on using linear programming to solve SAT:

Combining Linear Programming and
Satisability Solving for Resource Planning, Wolfram/Weld

another area that seems loosely similar is the use of artificial neural networks to solve SAT. again there is a concept of an algorithm with continuous variables that converges to a solution under update rules expressed as differential equations. see eg

A NN Algorithm for Boolean Satisfiability Problems (1996) Spears


Presburger Arithmetic Decision Procedures What are good textbook references for Presburger Arithmetic decision procedures?

John Harrison's handbook on automated theorem proving contains a fairly detailed description of Cooper's algorithm, including the steps necessary for an implementation in ML.

Harrison, J. (2009). Handbook of practical logic and automated reasoning. Cambridge University Press.


$NP$-completeness of recognizing the difference of two permutations Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two permutations. Unfortunately, I don't see a straightforward reduction from the permutation sum problem and it is useful to have the $NP$-completeness reduction for the permutation difference problem.

Permutation Difference:

INSTANCE: An array $A[1...n]$ of positive integers.

QUESTION: Do there exist two permutations $\pi$ and $\sigma$ of the positive integers $1,2, ... , n$ such that $|\pi(i) - \sigma(i)| = A[i]$ for $1 \le i \le n$ ?

  What is the reduction for proving the $NP$-completeness of recognizing the difference of two permutations?

EDIT 10-9-2014: Shor's comment gives a reduction which proves $NP$-completeness when the elements of sequence $A$ are signed differences. However, I don't see an easy reduction to my problem where all elements of $A$ are the absolute values of differences.

UPDATE: The Permutation Difference problem seems to be $NP$-complete even if one of the two permutations is always the identity permutation. Hardness proof of this special case is very welcome. So, I am interested in $NP$-completeness of this restricted version:

Restricted Permutation Difference:
INSTANCE: An array $A[1...n]$ of positive integers.

QUESTION: Does there exist a permutation $\pi$ of the positive integers $1,2, ... , n$ such that $|\pi(i) - i| = A[i]$ for $1 \le i \le n$ ?

Update 2: The restricted problem is efficiently decidable as shown by mjqxxxx's answer. The computational complexity of the original problem is not proven.

EDIT 9/6/16: I am interested in determining whether this simplification of Permutation Difference is NP-complete:

Restricted Permutation Difference:

INSTANCE: A multiset $A$ of positive integers.

QUESTION: Does there exist a permutation $\pi$ of the positive integers $1,2, ... , n$ such that  $A= \{|\pi(i) - i| :1 \le i \le n\}$ ?

The restricted problem, where one of the permutations is the identity, is certainly in $\mathsf{P}$.  Construct the bipartite graph where each vertex $i \in V_1=\{1,2,\ldots,n\}$ is connected to the element(s) $j \in V_2=\{1,2,\ldots,n\}$ such that $|i-j|=A[i]$.  Then the desired permutation $\sigma$ exists if and only if the graph has a perfect matching (i.e., a matching with $n$ edges), which can be determined in polynomial time.


Unambiguous SAT and sparse languages What is the consequence if there are only polynomially many 'yes' classes of instances of a language that is polynomial time reducible from a problem equivalent to UnambiguousSAT (such as possibly unique subset sum)?

It puts NP into P/poly, and therefore collapses PH to its second level.

By basically the same as the usual proof that BPP is in P/poly, there is polynomial advice that provides good random bits for the randomized reduction of Valiant-Vazirani. Use that advice to produce the queries to UnambiguousSAT. Apply the reduction from UnambiguousSAT to the sparse language $S$ - which is in P/poly - and use the additional advice to decide $S$.


On planarity in two related graphs Let $A$ be an $(n\times n)$-matrix with entries from $\{0,1\}$ and $B$ its biadjacency matrix $B = \begin{pmatrix} 0 & A\\ A^t & 0 \end{pmatrix}$.

My simple question is: Is there a relationship between the planar-property of the graph $\mathcal{G}_A$ (the graph constructed from the matrix $A$) and $\mathcal{G}_B$?  Note that the graph $\mathcal{G}_B$ is necessarily undirected and loop-free.

(A good answer would be, e.g., that if $\mathcal{G}_A$ is planar, $A$ has to have some additional properties therewith $\mathcal{G}_B$ will be also planar)

Update: A property $\mathcal{G}_A$ must have therewith planarity passes on to $\mathcal{G}_B$ is to be bipartite. In that case $\mathcal{G}_B$ is the graph that consists of two disconnected copies of $\mathcal{G}_A$.

$\mathcal{G}_B$ is the bipartite double cover of $\mathcal{G}_A$. So it has twice as many vertices and edges, and if  $\mathcal{G}_A$ has an embedding with $x$ even faces and $y$ odd faces then $\mathcal{G}_B$ has an embedding (possibly on a nonplanar surface) with $2x+y$ faces, formed by making two copies of each even face and replacing each odd face by its double. Therefore, by Euler's formula, when the embedding of $\mathcal{G}_A$ is planar, the genus of $\mathcal{G}_B$ is at most $(y-2)/2$. In particular, if $\mathcal{G}_A$ is already bipartite, $\mathcal{G}_B$ consists of two disjoint copies of $\mathcal{G}_A$, and if $\mathcal{G}_A$ has only two odd faces then $\mathcal{G}_B$ will still be planar.

This is not a complete characterization: It might also be possible for $\mathcal{G}_B$ to be planar in some other cases, by using a different embedding from the one derived from $\mathcal{G}_A$. For instance, if $\mathcal{G}_A=K_4$, then $\mathcal{G}_B$ is a cube, and is planar, but the embedding derived from the planar embedding of $\mathcal{G}_A$ is a toroidal embedding of the cube with four hexagonal faces (the four equators of a standard cube) instead of the usual planar embedding with six square faces.

Some planar graphs $\mathcal{G}_A$ will definitely give nonplanar graphs $\mathcal{G}_B$. For instance, if $\mathcal{G}_A$ is the graph of the regular dodecahedron, its bipartite double cover is the cubic symmetric graph on 40 vertices, which is nonplanar. In the other direction, it is also possible for $\mathcal{G}_B$ to be planar even when $\mathcal{G}_A$ is nonplanar; for instance, if $\mathcal{G}_A$ is the nonplanar graph formed from $K_{3,3}$ by subdividing the edges of a 6-cycle, then $\mathcal{G}_B$ is the planar graph of the hexagonal prism (with both of its 6-cycles subdivided in the same way).


Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map? "any two representations of reals which are acceptable are actually computably isomorphic",please see here for reference

where may proof of  this theorem   be found, and what is the the computational complexity of the computably isomorphic maps?

To turn my comment into an answer...

Andrej Bauer in this post makes the parenthetical claim

  An important theorem states that any two representations of reals which are acceptable are actually computably isomorphic.

He never explicitly defines acceptable or cites the theorem. I assume the OPs question is the following.

What theorem is Andrej Bauer referring to?

Here is a guess.  It seems that earlier in the post, Andrej is implicitly suggesting that an acceptable representation of the reals is one in which the following properties hold:

One can effectively approximate a real by a rational to within a given precision.
Addition, multiplication, and inverse are computable.
The less-then relation, $<$, is semi-decidable.
There is a computable function which takes in a rapid sequence of reals (that is a sequence $(x_n)$ of reals such that $|x_n - x_m| \leq 2^{\min{n,m}}$ and outputs the limit.

Actually (1) and (4) are enough to prove (2) and (3), since to preform those operations: one only needs to approximate the real by a rational, do the operation, and convert back to a real.  (Basic module of continuity will tell you how close the approximated answer is.  Also, one needs to be able to convert from a rational to the corresponding real.  This can be done by using (1) to find reals that are close enough to the rational, and then using (4) to take the limit of these approximations.)

Now, for any two representations satisfying (1) and (4) they are computably isomorphic.  From (1), one can go from the first representation to the rapid Cauchy representation.  (That is, represent a real as a rapid Cauchy sequence of rationals.)  From (4), one can go the other way, taking a rapid Cauchy sequence of rationals and computing the real it converges to (using the second representation).

As for the question about complexity, I think it can't be anything better than just computable, but I realize I don't know for sure, mostly, because I don't know how to formulate the question formally.


Subset Sum Variant still NP hard? I've read that this SE is for research-level CS questions; this is certainly research level, just not my field of research, so it is hard for me to assess how difficult the question really is. So in case this is well-known and easy, I'd still be grateful for a hint or a reference. Thanks!

So here is the question:
Given a multiset $S$ of integers (or rationals), does there exist a multi-subset $T\subsetneq S$ such that $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s|\le\sum_{s\in S}s$?

In case we replace the rhs with some constant $l\ge0$, this reduces to the subset sum decision variant, which is NP hard. But is this variant still NP-hard?

Thanks!
- Josely

Note that $T=S$ and $T=\emptyset$ are trivial solutions.

With the constraints $T \neq \emptyset$ and $S\setminus T \neq \emptyset$ the problem seems (unless the proof below is wrong :-) NP-complete. A possible reduction is from PARTITION: given a set $A$ of $n$ positive integers $A=a_1,..a_n$, can $A$ be partitioned in two sets $A = A_1 \cup A_2$ such that $\sum_{a_i\in A_1} a_i = \sum_{a_j \in A_2} a_j$?

Let $M = \sum_{a_i \in A}a_i$; without loss of generality we can assume that $M$ is even.

You can pick $S = A \cup \{a_{n+1}, a_{n+2}\}$ with $a_{n+1}= a_{n+2}=-M/2$; so we have $\sum_{s \in S}s = 0$ (right hand side of the equation of your problem).

The original PARTITION problem has a solution if and only if your problem has a solution.

$(\Leftarrow)$ Suppose that there exists $T$ such that $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s|\le\sum_{s\in S}s$ = 0. So the absolute value of the difference of the sums is zero: $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s| = 0$  $T$ cannot contain both $a_{n+1}$ and $a_{n+2}$, otherwise  $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s| > 0$ because at least one element $a_i>0$ must be contained in $S \setminus T$ and $|-M/2 -M/2 - a_i| > M$. For the same reason $S \setminus T$ cannot contain both $a_{n+1}$ and $a_{n+2}$. So $a_{n+1} \in T$ and $a_{n+2} \in S \setminus T$, and their contribution to the absolute value of the difference of the sums is $0$. So the remaining elements must be partitioned in such a way that the sum of the elements in $T$ equals the sum of elements in $S \setminus T$ in order to have an absolute value of the difference of the sums equal to $0$.

$(\Rightarrow)$ If the original partition problem has a solution, then it is easy to see that if $T = A_1 \cup a_{n+1}$ we get an absolute value of the difference of the sums equal to $0$.


Witness verifiable quantum advantage Update: A slightly different version of this question has been answered here.

As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results.
If the quantum computer would be powerful enough to solve problems in NP (like factoring, using Shor's algorithm), it would be easy to verify the results, however, this computational power is not available yet.
As an intermediate step,

  what could be a problem within reach of today's quantum computers whose output can be verified efficiently with a witness?

Here efficiently need not stand for the problem itself being in NP, but rather it would be sufficient that the correctness of the solution is in NP.
For example, consider a satisfiability task whose literals are $x_i$'s and $y_j$'s.
If the quantum computer can produce all the $x_i$ that are part of a solution, then a witness for its correctness would be finding the $y_j$'s that make $(x,y)$ into a solution.
The corresponding $y$ can be found with a classical algorithm, or set as a challenge, like in case of Bitcoin, to mint some quantum coin, with the computational power of all the miners looking for the witness.
In fact, miners can be also rewarded for finding another $(x',y')$ solution of the original problem, which would determine whether $x$ is useful or not.

So what could be such a problem?
Can Shor's algorithm or some other similar problem be broken into finding some $x$ with a quantum computer that can be extended into a witness with some (smaller) $y$?

Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a scheme for verifiable quantum computational supremacy based on a strengthening of trap-door claw-free functions (TCFs).

In the above scheme:

Vicky the classical verifier provides a description of a pair of functions $f_0$ and $f_1$ to Peggy the quantum prover, while saving the trapdoor to $f_0$ and $f_1$;
Peggy prepares, measures, and reports the results of a register in a quantum state to provide a $y$ such that $y=f_0(x_0)=f_1(x_1)$, keeping a superposition of $\vert b\rangle\vert x_b\rangle$;
Vicky asks Peggy to measure the superposition in either the computational basis to provide a bit $b$ and an $x_b$ such that $f_b(x_b)=y$, or in the Hadamard basis to provide a string $d$ orthogonal to $x_0\oplus x_1$; and
Based on Vicky's possession of the trapdoor, Vicky can validate results (she uses the trapdoor to deduce both $x_0$ and $x_1$ from $y$ and Peggy's response above).

Thus Peggy proves that she was able to execute a function in quantum superposition (or she has broken the security of the TCF).

The authors instantiate their TCFs with learning-with-errors (LWE), which is a leading candidate for post-quantum security.  That is, the functions they require Peggy to prepare and evaluate in superposition are associated with LWE.

My limited understanding is that the author's LWE scheme is out of reach of current and near-term noisy, intermediate-scale quantum computers.  The authors appear somewhat optimistic that about 50 bits of security may correspond to a machine with about 2000 or so qubits, or perhaps even 200-500 noisy qubits if they could optimize their LWE scheme.

Nonetheless the scheme is interesting and I think close to the spirit of the question.  For example, in this scheme Peggy does not actually find the claw by herself but only provides a proof that she possessed $x_0$ and $x_1$ in superposition.


What is the complexity of computing a compatible 3-coloring of a complete graph? Given a complete graph whose edges are colored by 3 colors, a compatible 3-coloring is a coloring of nodes such that no edge of the graph has the same color as its end-points.

The best algorithm I know is quasi-polynomial time. The problem is not known to be NP-complete. What is known about the status of this problem ?

Apparently, this paper by Cygan, Pilipczuk, Pilipczuk and Wojtaszczyk (2010+) gives a faster (polynomial time) algorithm: http://arxiv.org/abs/1004.5010

It was accepted to SODA 2011.


Weighted furthest point voronoi diagrams I found that Weighted nearest neighbor voronoi diagrams are widely studied and there are optimal algorithms for that.

But I could not find anything on Weighted furthest point voronoi diagrams !! But it is very unlikely that this version of voronoi diagrams are not studied before.

So, any link / reference will be helpful.

There's something on the multiplicatively weighted farthest neighbor query problem (but not on the associated Voronoi diagram) in my paper

Approximate weighted farthest neighbors and minimum dilation stars.
J. Augustine, D. Eppstein, and K. Wortman.
arXiv:cs.CG/0602029.
Proc. 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam.
Lecture Notes in Comp. Sci. 6196, Springer-Verlag, 2010, pp. 90-99.
Discrete Mathematics, Algorithms and Applications 2(4): 553-656, 2010.


What's the relationship between ASP-complete and #P-complete? Given that ASP-reductions by definition are parsimonious and parsimonious reductions preserve #P-completeness, one might think that the counting version of all ASP-complete problems are also #P-complete (note that e.g. #3SAT is #P-complete and 3SAT is ASP-complete).

However, ASP-completeness implies that all solutions have polynomial length, whereas no such requirement is there for #P.

Is it the case that all ASP-complete problems are #P-complete?  Is there some kind of relationship in the other direction as well?

Let an ASP-complete problem Q be given.  There is an ASP-reduction from 3SAT to Q and all ASP-reductions are parsimonious, hence it serves as a parsimonious reduction from #3SAT to #Q.  Since #Q is in #P and #3SAT is #P-hard, #Q is #P-complete.


Everyday encounters with NP-complete problems Mark Dominus collected a few examples of polynomial-time reductions from various NP-hard problems to “regular expression” matching. Envisioning polynomial-time verifications isn't an enormous leap.

How do you illustrate the class NP-complete to undergraduates or to friends in other fields who wanted to understand the recent fuss over Deolalikar's paper?

My favorite example to use with non-CS friends is this one:

Abraham, A. Blum, Sandholm.  Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges.  EC07.

Kidney exchange markets are essentially a restricted form of cycle cover.  I like this example because a) it's easy to explain the gist(if you leave out some of the more technical details) and b) it's one of the few instances I know of where better algorithms can literally save lives!

My second favorite example is the hospitals-and-residents problem (aka the college admissions problem).  Each hospital ranks all residents (graduating medical students) and residents rank hospitals.  Each hospital has a certain number of slots.  From there it's a stable matching problem and can be solved in polynomial time.

But in reality, couples can enter the system (yes, there is indeed a system) together, so that the system won't, for example, split up married couples who are both applying for residency.  The addition of couples makes the problem NP-complete.  In addition to being easy to explain, this nicely demonstrates how the introduction of long-range connections can induce NP-completeness.


What's the "smallest" complexity class for which a superlinear circuit bound is known? Apologies for asking a question that must surely be in a lot of standard references.  I'm curious about exactly the question in the title, in particular I am thinking of Boolean circuits, no depth bound.  I put "smallest" in quotes to allow for the possibility there are multiple different classes, not known to include each other, for which a superlinear bound is known.

I believe that the smallest such classes known are $S_2P$ (Cai, 2001), $PP$ (Vinodchandran, 2005), and $(MA \cap coMA)/1$ (Santhanam, 2007).  All of these are indeed known to not be in $SIZE(n^k)$ for each constant $k$.


Easy decision hard counting Parametrized It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P.
Is there a problem, that exhibits the same behavior in parametrized  complexity? (Decision in FPT and counting in #W[1] or some other counting class?)

Finding $k$-path (simple paths of length $k$) in a graph is in $FPT$ and can be done in $O^*(2^k)$ with a randomized algorithm or $O^*(2.62^k)$ deterministically.

This is while Counting $k$-paths is $\#W[1]$-hard.

A more interesting example (decision is even in $P$ while counting is parameterized-hard) would be counting $k$-matchings in bipartite graph.
Not only that the problem is $\#P$-complete, it was recently shown to be $\#W[1]$-hard as well !


Disjoint subsets problem complexity Is the decision problem below NP-complete?

Given sets $S_1, ... , S_n$, as well as bounds $b_1, ... , b_n$, is it possible to pick pairwise disjoint subsets $U_1, ... , U_n$ such that $U_i \subset S_i$ and $|U_i| \geqslant b_i$ for all $i$?

Create a bipartite graph:

For every element $x\in\bigcup_{i=1}^nS_i$, introduce a corresponding vertex $u(x)$.
For every set $S_i$, introduce a corresponding vertex $v(S_i)$.
Connect vertex $u(x)$ to vertex $v(S_i)$ by an edge, if and only if $x\in S_i$.

Then your problem essentially asks, whether there exists a subset $F$ of the edges, so that

every vertex $u(x)$ is incident to at most one edge in $F$, and
every vertex $v(S_i)$ is incident to at least $b_i$ edges in $F$.

This is an instance of the so-called $f$-factor problem, and hence solvable in polynomial time.
See for instance the book "Matching Theory" by László Lovász and Michael D. Plummer.


Is the following problem NP hard? Consider a collection of sets $F=\{F_1,F_2,\dotsc,F_n\}$ over a base set $U=\{e_1,e_2,\dotsc,e_n\}$ where $|F_i|$ $\ll$ $n$ and $e_i \in F_i$, and let $k$ be a positive integer.

The goal is to find another collection of sets $C=\{C_1,C_2,\dotsc,C_m\}$ over $U$ such that each $F_i$ can be written as a union of at most $k$ $(k<<|C|)$ mutually disjoint sets in $C$ and also we want $\sum_1^m |C_j|$ to be minimal (i.e., the aggregate number of elements in all sets of $C$ should be as small as possible) .

Note that $F$ has the same size with $U$, but the size of $C$ is uncertain.

Can anyone tell whether the above problem is NP-hard? (set covering？packing？perfect covering）

Thanks for your time.

Lemma. The problem is NP-hard.

Proof sketch.  We disregard the constraints $|F_i| \ll n = |U|$ in the posted problem, because, for any instance $(F,U,k)$ of the problem, the instance $(F'=F^n,U'=U^n,k)$ obtained by taking the union of $n$ independent copies of $(F,U,k)$ (where the $i$th copy of $F$ uses the $i$th copy of $U$ as its base set) is equivalent, and satisfies the constraint (it has $|F'_i| \le n \ll n^2 = |U'|$).

We give a reduction from 3-SAT.  For presentation, in the first stage of the reduction, we disregard the constraints $e_i \in F_i$ in the posted problem.  In the second stage we describe how to meet those constraints while maintaining correctness of the reduction.

First stage. Fix any 3-SAT formula $\phi$.  Assume WLOG that each clause has exactly three literals (each using a different variable). Produce the following instance $(F,U,k)$ of the posted problem, with $k=3$.

Let $n$ be the number of variables in $\phi$.
There are $3n+1$ elements in $U$: one element $t$ (for "true"), and, for each variable $x_i$ in $\phi$, three elements $x_i$, $\overline x_i$, and $f_i$ (for "false").

For each element in $U$ there is a singleton set containing just that element in $F$.  Any solution $C$ therefore includes each of these sets, which contribute their total size $3n+1$ to the cost of $C$.

In addition, for each variable $x_i$ in $\phi$ there is a "variable" set $\{x_i, \overline x_i, f_i, t\}$ in $F$.  For each clause in $\phi$ there is a "clause" set in $F$ consisting of the literals in the clause, and $t$.  For example, the clause $x_1\wedge \overline x_2 \wedge x_3$ yields the set $\{x_1, \overline x_2, x_3, t\}$ in $F$.

Claim 1. The reduction is correct: $\phi$ is satisfiable iff some solution $C$ has cost $\sum_j |C_j| = 5n+1$.

(only if) Suppose $\phi$ is satisfiable. Construct a solution $C$ consisting of the $3n+1$ singleton sets, plus, for each variable $x_i$, the pair consisting of the true literal and $t$.  (E.g., $\{\overline x_i, t\}$ if $x_i$ is false.)  The cost of $C$ is then $5n+1$.

Each variable set $\{x_i, \overline x_i, f_i, t\}$ is the union of three sets: the pair consisting of the true literal and $t$, plus two singleton sets, one for each of the other two elements.  (E.g., $\{\overline x_i, t\}, \{x_i\}, \{f_i\}$.)

Each clause set (e.g. $\{x_1, \overline x_2, x_3, t\}$) is the union of three sets: a pair consisting of $t$ and a true literal, plus two singleton sets, one for each of the other two literals.  (E.g., $\{x_1, t\}, \{\overline x_2\}, \{x_3\}$.)

(if) Suppose there is a solution $C$ of size $5n+1$.  The solution must contain the $3n+1$ singleton sets, plus other sets of total size $2n$.

Consider first the $n$ "variable" sets, each of the form $\{x_i, \overline x_i, f_i, t\}$.  The set is the disjoint union of at most three sets in $C$.  Without loss of generality, it is the disjoint union of two singletons and a pair (otherwise, splitting sets in $C$ achieves this without increasing the cost).  Denote the pair $P_i$.  The pairs $P_i$ and $P_j$ for different variables $x_i$ and $x_j$ are distinct, because $P_i$ contains $x_i$, $\overline x_i$, or $f_i$ but $P_j$ does not.  Hence, the sum of the sizes of these pairs is $2n$.  So these pairs are the only non-singleton sets in the solution.

Next consider the "clause" sets, e.g, $\{x_i, \overline x_j, x_k, t\}$.  Each such set must be the union of at most three sets in $C$, that is, up to two singleton sets and at least one pair $P_i$, $P_j$, or $P_k$.  By inspection of the pairs and the clause set, it must be the union of two singletons and one pair, and that pair must be of the form $\{x_i, t\}$ or $\{\overline x_j, t\}$ (a literal and $t$).

Hence, the following assignment satisfies $\phi$: assign true to each variable $x_i$ such that $P_i=\{x_i, t\}$, assign false to each variable $x_i$ such that $P_i=\{\overline x_i, t\}$, and assign the remaining variables arbitrarily.

Stage 2. The instance $(F,U,k=3)$ produced above does not satisfy the  constraint $e_i \in F_i$ stated in the problem description.  Fix that shortcoming as follows.  Order the sets $F_i$ and elements $e_i$ in $U$ so that each singleton set corresponds to its element $e_i$.  Let $m$ be the number of clauses in $\phi$, so $|F|=1+4n+m$ and $|U|=1+3n$.

Let $(F', U', k'=4)$ denote the instance obtained as follows. Let $A$ be a set of $2n+2m$ new artificial elements, two for each non-singleton set in $F$. Let $U'=U\cup A$. Let $F'$ contain the singleton sets from $F$, plus, for each non-singleton set $F_i$ in $F$, two sets $F_i\cup \{a_i, a_i'\}$ and $\{a_i,a_i'\}$, where $a_i$ and $a_i'$ are two elements in $A$ chosen uniquely for $F_i$.  Now $|F'|=|U'|=1+5n+2m$ and (with the proper ordering of $F'$ and $U'$) the constraint $e'_i\in F'_i$ is met for each set $F'_i$.

To finish, note that $(F',U',k'=4)$ has a solution of cost $|A|+5n+1$ iff the original instance $(F, U, k=3)$ has a solution of cost $5n+1$.

(if)  Given any solution $C$ of cost $5n+1$ for $(F,U,k=3)$, adding the $n+m$ sets $\{a_i, a'_i\}$ (one for each non-singleton $F_i$, so these partition $A$) to $C$ gives a solution to $(F', U', k'=4)$ of cost $|A|+cost(C)=|A|+5n+1$.

(only if) Consider any solution $C'$ for $(F', U',k=4)$ of cost $|A|+5n+1$.  Consider any pair of non-singleton sets $F_i\cup\{a_i, a_i'\}$ and $\{a_i, a_i'\}$ in $F'$.  Each is the disjoint union of at most 4 sets in $C'$. By a local-exchange argument, one of these sets is $\{a_i, a_i'\}$ and the rest don't contain $a_i$ or $a_i'$ --- otherwise this property can be achieved by a local modification to the sets, without increasing the cost... (lack of detail here is why I'm calling this a proof sketch). So removing the $\{a_i, a_i'\}$ sets from $C'$ gives a solution $C$ for $(F,U,k=3)$ of cost $5n+1$.  $\diamond$


Proof of $LP$ is in $coNP$ without showing it is in $P$? Is there a proof that linear programming is in $coNP$ without showing it is in $P$?
If so what is the strategy?

Note: all vector inequalities in this reply are to be interpreted pointwise.
Given a linear feasibility problem, you can always rewrite it in the following canonical form: given a matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^m$, does there exist an $x \geq \vec{0}$ such that $Ax \leq b$?
Farkas' lemma states that when a system of inequalities such as the above has no solution, then there exists a "witness" vector $y \in \mathbb{R}^{m}$ such that

$y \geq \vec{0}$,
$A^{\intercal}y \geq \vec{0}$, and
$b^{\intercal}y < 0$.

Effectively, $b$ gives you a nonnegative scaling factor for each constraint, such that when you add up all of the scaled constraints, the left-hand side ends up with a sum of a bunch of nonnegative terms, and the right-hand side ends up with a strictly negative value. That is, $y$ provides a direct way to prove that the inequalities are inherently contradictory.
Therefore, the existence of such a $y$ is both a necessary and sufficient condition for any given problem instance to be infeasible, meaning that it can be used as a polynomial-time checkable certificate of infeasibilty. So linear feasibility checking is in co-NP.


Gap-Hamming with different "threshold" (i.e., not $n/2$) Following a previous question, I'm trying to get a better understanding of the parameters at play in $\textsf{Gap-Hamming}$. In the "standard" setting, we have
$x,y\in\{0,1\}^n$ and the partial function
$$
\textsf{GHD}_{n,n/2,\sqrt{n}} = \begin{cases}
0 & \text{ if }\operatorname{d}_H(x,y) \leq \frac{n}{2}-\sqrt{n}\\
1 & \text{ if }\operatorname{d}_H(x,y) \geq \frac{n}{2}+\sqrt{n}.
\end{cases}$$
This can be generalized to
$$
\textsf{GHD}_{n,t,g} = \begin{cases}
0 & \text{ if }\operatorname{d}_H(x,y) \leq t-g\\
1 & \text{ if }\operatorname{d}_H(x,y) \geq t+g.
\end{cases}$$
Lemma 4.1 to Proposition 4.4 of [CR10] allow to get a lower bound on the communication complexity of $\textsf{GHD}_{n,t,g}$ for (most) of the settings of $t,g$. Another generalization is introduced and studied in [BBM13] (Lemma 2.5), $\textsf{EGHD}_{n,k,t}$, which corresponds to $\textsf{GHD}_{n,k/2,g}$ with the additional promise that that $\lvert x\rvert = \lvert y\rvert = k/2$.

However, as far as I could see none of the above covers the "corner cases" where $t$ is itself sublinear (and say, comparable to $g$), but $\lvert x\rvert, \lvert y\rvert$ are still arbitrary. Is the behaviour of the randomized communication complexity for e.g. $\textsf{GHD}_{n,2\sqrt{n},\sqrt{n}}$ obvious?

(I suppose two reasonable conjectures would be that the CC be either $\Omega(\sqrt{n})$ or $O(1)$ in this case, the first inspired by the difficulty of distinguish a coin with bias $\varepsilon$ from one with bias $2\varepsilon$ with less than $1/\varepsilon$ samples; the second because it "looks" easy, and a completely hazy feeling.However, and most likely because I'm missing something obvious, I don't really see which holds, nor how to get a general tradeoff that would cover the whole spectrum of $t,g$.)

As it turns out, the one-sided error case (public coin) was addressed in [KK16], which shows the communication complexity is then $\tilde{\Theta}\!\left(\frac{(t-g)^2}{t+g}\right)$ (the upper and lower bound are off only by a $\log(t-g)$ factor).

(so, for $\mathsf{GHD}_{n,2\sqrt{n},\sqrt{n}}$, the one-sided public-coin communication complexity is $\tilde{\Theta}\!\left(\sqrt{n}\right)$.)

[KK16] One-sided error communication complexity of Gap Hamming Distance, Egor Klenin and Alexander Kozachinsky. ECCC TR16-173, 2016.


Combining multiple time-based datasources with different periods I have two time-based data sources (one providing data by month and the other by week) that must be combined to create a third daily source (recognizing that at best we're getting one possible projection of those two data sources).  To make things really interesting, they do not cover entirely the same timeframe (the monthly stops at the most recent month end at least 45 days ago, while the weekly data covers only the last six weeks).  The main issue (for me) is addressing the days where the two datasources overlap.

Not looking for someone to give me a fish, but for some papers on how to fish (actually, I hate fishing).

(not enough rep for comment)
Can you tell us more about the data streams? I am a roboticist, and I often deal with sensors which are outputting data streams at different rates. Specifically, can you please elaborate on the following:

do the data streams have the same modality? (eg, are they all telling you the velocity of something, or is one telling you velocity and the other position, leaving you to infer velocity?)
is either stream noisy and/or can you otherwise get conflicting data from the streams? If so, do you have an error model?

Once I know more about your streams, I will try to suggest some relevant literature.


Why are these two definitions of PLS equivalent? In the definition of the complexity class $\textsf{PLS}$ we have an algorithm for improving the solutions locally. I have come across the following two definition of such an algorithm.

  there is a polynomial-time algorithm $C_P$ that, given $x\in\mathcal{I}_P$
  and $s\in\mathcal{F}_P(x)$, either outputs a better solution $s'\in \mathcal{N}_P(x,s)$, or reports that $s$ is locally optimal.

and

  there is a polynomial-time algorithm $C'_P$ that, given $x\in\mathcal{I}_P$ and $s\in\mathcal{F}_P(x)$,  returns
  $\mathcal{N}_P(x,s)$.

Here $P$ is a $\textsf{PLS}$ problem, $\mathcal{I}_P$ is a set of instances of $P$, $\mathcal{F}_P(x)$ is a set of feasible solutions of $x\in\mathcal{I}_P$, and $\mathcal{N}_P(x,s)$ is a neighbourhood of $s\in\mathcal{F}_P(x)$.

It is clear that the existence of $C'_P$ implies the existence of $C_P$. Why the existence of $C_P$ implies the existence of $C'_P$?

If it is not the case, could you give me a counterexample? Maybe it could be the case that $\mathcal{N}_P(x,s)$ has an exponential size and we can determine that $s$ is locally optimal by some other property of the instance $x$ or the solution $s$?

In general, searching a neighborhood for a better solution and reporting the whole neighborhood are two different things. There are for example some exponential neighborhoods, that is, neighborhoods whose size grows exponentially in the input length $n$, that can be searched in polynomial time for a better solution, see for example A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem by Deineko and Woeginger. The PLS framework, however, is not so much concerned with the running time of searching the neighborhood but with the number of iterations that are needed to find a locally optimal solution.


Is the cutting lemma true with O(r) lines? The cutting lemma (a.k.a. cell decomposition lemma) states that given $n$ lines in the plane it is possible to divide it into $O(r^2)$ regions (even triangles) for any $1\le r\le n$ such that the interior of any region is intersected by $O(n/r)$ lines. For more see e.g. Matousek's book Lectures on Discrete Geometry or this post.

My question is whether the plane can be divided by $O(r)$ lines (into $O(r^2)$ regions) such that the interior of any region is intersected by $O(n/r)$ of the original lines.

If the $O(r)$ lines you choose must be drawn from the original set of $n$ lines then the answer is no, it's not possible. In particular if you take $n$ lines tangent to a circle, and then choose any $r$ of them, the region containing the circle will still be intersected by all $n$ of the lines.


Hardness of constrained star system problem? A star system is a family $F$ of n subsets of n-elements set $S$. A star system is graphical if there is some graph $G(V,E)$ such that $F$ is the family of vertex neighborhoods in $G$. It is $NP$-complete to decide whether a given star system is graphical.

  What is the minimum occurrence of each element such that the problem remains $NP$-complete?

EDIT 12-12-2010: I added another question:

  What is the most restricted class of graphs for which the problem remains $NP$-complete?

For instance, Is the star system problem $NP$-complete if the target graph is cubic? If not, What is the minimum $k$ such that the problem remains $NP$-complete for $k$-regular target graphs?

 F.Lalonde, Le probleme d'etoiles pour graphes est NP-complet, Discrete Math.
33(3), 1981, 271-280.

You may take a look at The Star System Problem revived. Among other things, the authors prove that:

  if the graph $G$ is required to be $C_k$-free, i.e. not allowed to have an induced cycle of length $k$, then the problem is solvable in polynomial time for each $k \le 4$, and is NP-complete for each $k>5$.

In addition, you may find the papers in this list useful.


Papers on applying CTL over LTSs Normally model checking with specifications written in CTL*/CTL  is done over Kripke structures, however there are ways of doing it over somehow simpler Labelled Transition Systems, for instance ACTL. Does anyone has any pointer on similar logics/techniques?

The meaning of  simpler in your question is unclear. Kripke structures have a labelling function on states. LTSes have labels on transitions, which can be viewed as a labelling function on transitions. Why is one simpler than the other? In the context of your question, using acronyms like "ACTL" is ambiguous because the "A" could mean all paths or action-based.

The difference, in my opinion, between Kripke structures and LTSes is based on modelling convenience and not simplicity. There is a lot of work comparing and contrasting the two. Here are a few starting points for chasing down related work.

De Nicola and Vaandrager have a few papers on translating between Kripke structures and LTSes and how this affects logical properties. They introduce doubly labelled transition systems to move between the two types of representations and semantic interpretations.

Action versus state based logics for transition systems , De Nicola and Vaandrager, 1990

Three logics for branching bisimulation, De Nicola and Vaandrager, 1995
If the goal is verification of event-based systems, one option is to translate the LTS into a Kripke structure and use a Kripke structure model checker. The translation has to preserve the interpretation of CTL over the LTS.

An action-based framework for veryfying logical and behavioural properties of concurrent systems, De Nicola, Fantesi, Gnesi, Ristori
Translating between representations involves a blowup. For the case of LTL, there are cases when this blowup can be avoided. Here is a recent paper on the topic.

State/event-based software model checking, Chaki, Clarke, Ouaknine, Sharygina, Sinha


Running an algorithm for fixed amount of time on RAM model machine Suppose there is a deterministic algorithm of size $O(1)$ that operates on an input of size $N$ on a RAM model machine. I want to run the algorithm for $O(\sqrt{N})$ time, pause the algorithm, print "Hello", and then resume its execution, run it again for $O(\sqrt{N})$ time and repeat this cycle until the algorithm execution terminates. If the algorithm takes time $T$, then there would be $O(T/\sqrt{N})$ print statements.

It is obvious that an algorithm can be paused/resumed in constant time by storing/loading the content of all registers of the CPU in the memory. However, how is it possible to measure elapsed time in the RAM model and stop the algorithm after $O(\sqrt{N})$ steps? Does the RAM model support such an operation (a Turing machine definitely does)? Any reference or a simple argument is welcome!

One approach is to implement an interpreter for the RAM model, and then instrument the interpreter with a counter that keeps track of the number of instructions executed.  I suspect it should be possible to build an interpreter that incurs at most a $O(1)$-factor slowdown, but I haven't checked the details (the instruction set is so primitive that the programming is ugly) -- you should be able to check whether the obvious approach works.


Hardness of approximation - additive error There is a rich literature and at least one very good book setting out the known hardness of approximation results for NP-hard problems in the context of multiplicative error (e.g. 2-approximation for vertex cover is optimal assuming UGC).  This also includes well understood approximation complexity classes such as APX, PTAS and so on.

What is known when additive error is to be considered?  A literature search shows a few upper bound type results, most notably for bin packing (see for example http://www.cs.princeton.edu/courses/archive/spr03/cs594/dpw/lecture2.ps), but is there a more comprehensive complexity class classification or is there a reason why it is not so interesting or relevant?

As a further comment, for bin packing, for example, there is as far as I know no theoretical reason why a poly time algorithm which is always within an additive distance from optimal of 1 couldn't be found (although I stand to be corrected).  Would such an algorithm collapse any complexity classes or have any other significant theoretical knock-on effect?

EDIT: The key phrase I didn't use is "asymptotic approximation class" (thanks Oleksandr). It seems that there is some work in this area but it hasn't got to the same stage of maturity yet as the theory of classic approximation classes.

The question is somewhat open-ended, so I do not think that it can be answered completely.  This is a partial answer.

An easy observation is that many problems are uninteresting when we consider additive approximation.  For example, traditionally the objective function of the Max-3SAT problem is the number of satisfied clauses.  In this formulation, approximating Max-3SAT within an O(1) additive error is equivalent to solving Max-3SAT exactly, simply because the objective function can be scaled by copying the input formula many times.  Multiplicative approximation is much more essential for the problems of this kind.

[Edit: In earlier revision, I had used Independent Set as an example in the previous paragraph, but I changed it to Max-3SAT because Independent Set is not a good example to illustrate the difference between multiplicative approximation and additive approximation; approximating Independent Set even within an O(1) multiplicative factor is also NP-hard.  In fact, a much stronger inapproximability for Independent Set is shown by Håstad [Has99].]

But, as you said, additive approximation is interesting for the problems like bin packing, where we cannot scale the objective function.  Moreover, we can often reformulate a problem so that additive approximation becomes interesting.

For example, if the objective function of Max-3SAT is redefined as the ratio of the number of satisfied clauses to the total number of clauses (as is sometimes done), additive approximation becomes interesting.  In this setting, additive approximation is not harder than multiplicative approximation in the sense that approximability within a multiplicative factor 1−ε (0<ε<1) implies approximability within an additive error ε, because the optimal value is always at most 1.

An interesting fact (which seems to be unfortunately often overlooked) is that many inapproximability results prove the NP-completeness of certain gap problems which does not follow from the mere NP-hardness of multiplicative approximation (see also Petrank [Pet94] and Goldreich [Gol05, Section 3]).  Continuing the example of Max-3SAT, it is a well-known result by Håstad [Has01] that it is NP-hard to approximate Max-3SAT within a constant multiplicative factor better than 7/8.  This result alone does not seem to imply that it is NP-hard to approximate the ratio version of Max-3SAT within a constant additive error beyond some threshold.  However, what Håstad [Has01] proves is stronger than the mere multiplicative inapproximability: he proves that the following promise problem is NP-complete for every constant 7/8<s<1:

Gap-3SATs
Instance: A CNF formula φ where each clause involves exactly three distinct variables.
Yes-promise: φ is satisfiable.
No-promise: No truth assignment satisfies more than s fraction of the clauses of φ.

From this, we can conclude that it is NP-hard to approximate the ratio version of Max-3SAT within an additive error better than 1/8.  On the other hand, the usual, simple random assignment gives approximation within an additive error 1/8.  Therefore, the result by Håstad [Has01] does not only give the optimal multiplicative inapproximability for this problem but also the optimal additive inapproximability.  I guess that there are many additive inapproximability results like this which do not appear explicitly in the literature.

References

[Gol05] Oded Goldreich.  On promise problems (a survey in memory of Shimon Even [1935-2004]).  Electronic Colloquium on Computational Complexity, Report TR05-018, Feb. 2005.  http://eccc.hpi-web.de/report/2005/018/

[Has99] Johan Håstad.  Clique is hard to approximate within n1−ε.  Acta Mathematica, 182(1):105–142, March 1999.  http://www.springerlink.com/content/m68h3576646ll648/

[Has01] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM, 48(4):798–859, July 2001.  http://doi.acm.org/10.1145/502090.502098

[Pet94] Erez Petrank.  The hardness of approximation: Gap location.  Computational Complexity, 4(2):133–157, April 1994.  http://dx.doi.org/10.1007/BF01202286


Defining finite sets inductively in a proof assistant? To represent finite sets within coq, we either use something like ListSet, which are just definitions on top of list, or we build something like Compcert.Map, and then we define a set A as a map from A to ().

However, neither of these approaches manage to define sets inductively. What I want to know is a way to define a set type in the form of:

Inductive set (A: Type) : Type :=
 nil: set A | add: A -> set A -> <fill in the blanks> -> set A

Is it possible to have such an "inductive definition" for finite sets? If not, can I be supplied with a proof of why not?

My intuition is that such a thing is not possible, because an inductive type allows for equational reasoning, while sets cannot be equationally reasoned with:

$$
\texttt{add}~(1, \emptyset) = \texttt{add}(1, \texttt{add}(1, \emptyset)) \quad \text{(union is idempotent.)}
$$

however:

add 1 (add 1 nil) <> add 1 nil

So we will always have to go through some "extensional interface". Unfortunately, I don't know how to prove such a thing!

There are many variants of finite sets in constructive mathematics. One that can be defined using just inductive definitions, and is therefore amenable to formalization in type theory, is the Notherian finiteness by Thierry Coquand and Arnaud Spiwack. The idea is to define a set or a type $A$ to be finite if the following holds: every sequence $a : \mathbb{N} \to A$ contains a duplicate. The trick is to express an equivalent condition using inductive definitions, so that we get an induction principle for reasoning about such sets.

The definition of Notherian finiteness from section 2.3 of the linked paper can be translated to Coq like this:

(* [occurs x l] states that x appears in the list l *)
Inductive occurs {A : Type} : A -> list A -> Type :=
  | occurs_head : forall x k, occurs x (cons x k)
  | occurs_tail : forall x y k, occurs x k -> occurs x (cons y k).

(* [has_duplicates l] states that [l] has a duplicate, i.e., that an element appears in it twice. *)
Inductive has_duplicates {A : Type} : list A -> Type :=
  | has_duplicates_head : forall x l, occurs x l -> has_duplicates (cons x l)
  | has_duplicates_tail : forall x l, has_duplicates l -> has_duplicates (cons x l).

(* An auxiliary definition: a list `l` is said to be `notherian` if it contains a duplicate, or if every extension of `l` by one element is `notherian`. *)
Inductive notherian (A : Type) : list A -> Type :=
  | N_duplicates : forall l, has_duplicates l -> notherian A l
  | N_step : forall l, (forall a, notherian A (cons a l)) -> notherian A l.

Definition NotherianFinite A := notherian A nil.

If you're willing to use quotient types or the higher inductive types from homotopy type theory, then you can have a look at the defintion of finite sets Finite in the HoTT library. It says that a type X is finite if there is a number n such that X is merely equivalent to the standard finite set {0, 1, ..., n-1}. The word "merely" here means that we truncate the existence, i.e.,
$$\textstyle\mathsf{Finite}\, X \mathrel{{:}{=}}
\sum_{n : \mathbb{N}} \left\| X \simeq \mathsf{Fin}\,n\right\|$$
where $\mathsf{Fin}\,n$ is the standard finite set $\sum_{k : \mathbb{N}} (k < n)$.


Circuity complexity: monotone circuit of Majority function As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 log(n)+ O(1).

  http://link.springer.com/chapter/10.1007/11830924_38

My question is, what is the time-complexity of such constrution? (i.e., the time needed to construct the circuit, given n in unary)

Time complexity is often defined as the "number of operations in the worst case for a Turing machine." The monotone circuit model of computation is not the Turing time model. Thus it is not meaningful to say what the time complexity of such a circuit is.

On the other hand, if we view the monotone circuit model as a model of actual circuits, then one "time cost" of computation is the depth of such a circuit. Thus in that sense the time complexity of the circuit you mention is 5.3log(n).

Of course, in real circuits there are other factors besides "depth" that contribute to "how long it takes to do the computation." For example, the longest wire in a circuit often is bottleneck in actual VLSI computation as its larger capacitance takes longer to charge.


Polynomial algorithm for correlated equilibrium I searched through the web for a polynomial algorithm for correlated equilibrium.
I found a lot of papers by C.H. Papadimitriou that proposes a solution using the ellipsoid algorithm.

Is there a simpler algorithm to get the correlated equilibrium, or a paper to start from?

The linear program for computing a correlated equilibrium in a game has size that is polynomial in the size of the game matrix: i.e. exponential in the number of players. The scheduling game that you describe is an $n$ player game, so the linear program will not be polynomially sized. However, it is a compactly represented game, so you can in principle use the Ellipsoid approach of Papadimitirou and Roughgarden.

If you are ok with an approximate correlated equilibrium, there are much simpler and easier to implement approaches based on no-regret algorithms. For a textbook exposition, check out Chapter 4 of Algorithmic Game Theory.


Solving problems by deciding a logic I am curious to know when open problems have been solved by expressing them in a specific logic, and then showing that this logic is decidable.

I have two distinct cases in mind:

The problem is about decidability of something, and it can be reformulated in a decidable logic.
The conjecture is just a yes/no property about some mathematical object, like twin-prime conjecture. Turn it into a decidable logical sentence, and run the algorithm to know the answer.

In both cases, it would be interesting if the logic is created and shown decidable just to fit the problem.

I think the most spectacular example of this approach is Thomas Hales' proof of the Kepler conjecture (aka Hilbert's 18th problem).

In the 1950s, Fejes Toth proved that the Kepler conjecture was equivalent to a large collection of formulas in the first-order theory of real closed fields. Since Tarski had shown this theory to be decidable, he went on to speculate that if a sufficiently fast computer could be built, the Kepler conjecture could be resolved by machine.

Half a century later, Thomas Hales actually made this strategy work (after proving a lot of difficult theorems to further simplify the set of formulas the computer needed to check)!


Reduction from SAT to 0,1 integer linear program with zero or one solutions Probably this is well known. There is probabilistic reduction
from SAT to Unique SAT (0 or 1 solutions).

According to answer and comments derandomizing the reduction would imply $PH \subseteq \oplus P$.

There is simple reduction from SAT to 0,1 integer linear program with
zero or one solutions.

Given SAT formula $\phi$ on variables $x_1,\ldots x_n$,
introduce binary variables $b_i \in \{0,1\}$.

Define map literals to linear polynomials $f(x_i)=b_i$ and
$f(\lnot x_i)=1-b_i$.

For a clause $l_1 \lor \cdots \lor l_k$ add
constraint $\sum_{i=1}^k f(l_i) \ge 1$.

So far the solutions of the constraints are in one
to one correspondence with the solutions of $\phi$.

To make the solution unique, add the optimization

$$\text{maximize} \sum_{i=1}^n 2^{(i-1)}b_i$$

Two sets of distinct powers of two have equal sums
iff the sets are equal, so the objective function
have unique maximum if the constraints are satisfied.
The ordering of $x_i$ doesn't matter.
So the 0,1 ILP has zero or one solutions and it is
not easier than NP-complete and coNP-complete.

  In what complexity class is solving the 0,1 ILP?

As far as I know ILP are not a complexity class.

$\log_2(n)$ calls to NP oracle would solve it via
binary search, though I don't see a direct reduction to
SAT.

This appears close to UP though there is no certificate.

OptP-complete. Krentel showed that MAX-SAT, finding the lexicographically maximum satisfying assignment, is OptP-complete and the reduction above reduces Max-SAT to ILP. ILP sits in OptP pretty much by definition.

Note that you need n calls to an NP-oracle to solve ILP via binary search, O(log n) isn't sufficient.

There really isn't much of a connection to UP, though Mulmuley, Vazirani and Vazirani give an isolation lemma that gives an alternate proof of Valiant-Vazirani via a maximization problem.


The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers How much easier is computing the permanent of a matrix with only zeroes and ones than a matrix of only integers?

There is a polynomial-time reduction from one problem to the other, as explained on Wikipedia among other places.


Optimal payoff from sampling from a collection of Bernoulli random variables? Suppose I have several Bernoulli random variables, $\{X_1, \ldots, X_k\}$, each of which has a fixed probability $p_i$ of equaling 1 for each sample. Further suppose each $p_i$ is randomly distributed according to some known distribution, but we do not know the actual values of $p_i$.

Finally, suppose I am going to take $n$ samples in total from these variables and want to maximize the expected sum of the resulting samples. What is the best algorithm for choosing variables to sample? Obviously, if we knew which had the highest probability, we would always choose that variable, but if $n$ isn't very large, we have to be careful about balancing choosing the variable we believe has the highest $p_i$ value and sampling other variables to possibly find one with a higher $p_i$ value.

This is called the explore/exploit trade-off in machine learning.  This scenario is precisely captured by the multi-armed bandit problem with i.i.d. payoffs.  Algorithms such as UCB and Exp3 will get you an expected payoff within $\tilde{O}(\sqrt{Kn})$ of the optimal, and you asymptotically cannot do better.