Splitting set into subsets by criterion I am looking for an algorithm that will split a set $A = \{ a_1, a_2, ..., a_N \}$ into (possibly) multiple subsets based on a given criterion. In my case, the criterion is spatial overlap of the elements in the set, but it could be any criterion really. Let's define a function $crit(a_1, a_2)$ which takes as input two elements of $A$ and outputs a boolean indicating whether those two elements overlap.

If $crit(a_i, a_j) = false$ for all $a_i, a_j \in A$, then the output of the algorithm should be a single set containing all of the elements of $A$. If $crit(a_i, a_j) = true$ for a single pair of elements $a_i, a_j \in A$, then the output of the algorithm should be two sets, one set containing all elements except for $a_i$, and one set containing all elements except for $a_j$. We continue this pattern until we reach the other extreme case, in which $crit(a_i, a_j) = true$ for all $a_i, a_j \in A$, in which case the output of the algorithm should be a partition of $A$: $N$ sets, each containing a single element from $A$.

I would be surprised if this problem has not been formalized before. Is there an efficient algorithm for solving this problem?

Edit: For clarification, it is ok if an element ends up in multiple sets in the output. In fact, an element should be in every set that does not contain an element that overlaps with it. For example, if $A = \{ w,x,y,z\}$, $crit(w, x) = true$, $crit(w, y) = false$, $crit(w, z) = true$, $crit(x, y) = false$, $crit(x, z) = false$, $crit(y, z) = false$, then the output should be $A' = \{ \{ w, y \}, \{ x, y, z \} \}$.

Another edit: based on bbejot's response, I did a bit more looking and it does appear that I can reduce my problem to enumerating all maximal cliques of the graph represented by the adjacency matrix bbejot describes in his response. In response to my original question, there is no efficient algorithm for solving this problem, but the Bron–Kerbosch algorithm seems to be pretty standard.

I believe there are two interpretations of your criterion.  One interpretation is easily solvable, and the other is NP-Complete.

First, a greedy algorithm for what you describe:
Let $A_1$, $A_2$, ..., $A_N$ all start as the empty set.
Loop through each $a_i \in A$.
Put $a_i$ in the first $A_k$ such that for each $a_j$ already in $A_k$,
$crit(a_i, a_j) = false$.
After looping through all the elements of $A$, disregard any $A_i$ which is still empty.

This greedy algorithm holds in the three examples you give.

A second interpretation is: "Let the set $A_i$ be as large as possible but not including any elements from $A_1$ to $A_{i-1}$".  Let $A'$ be an $N \times N$ matrix where $A_{i, j}'$ is 1 if $crit(a_i, a_j) = false$ and 0 otherwise.  Then finding $A_1$ is exactly finding the maximum clique of a digraph with adjacency matrix $A'$.  This, of course, makes the problem NP-Hard.

Let's hope you only need the first.


Improved lower bound on monotone circuit complexity of perfect matching? Razborov proved that every monotone circuit that computes the perfect matching function for bipartite graphs must have at least $n^{\Omega(\log n)}$ gates (he called it "logical permanent"). Has a better lower bound for the same problem been proved since then? (say $2^{n^\epsilon}$?) As far as I remember this problem was open in the mid 1990's.

I am aware that the clique function requires exponential-size monotone circuits and so on, but I am interested in perfect matching specifically.

Eva Tardos proved that the gap is truly exponential by showing that there is a monotone boolean function that has poly size circuits but requires exponential size monotone circuits. Nothing better than super-polynomial is known for matching.

Raz has a result that monotone circuits for matching have linear depth. (Thanks Klauck, for pointing the typo.)

AFAIK, we know nothing better.

Ref: (1) http://www.springerlink.com/index/P25X5838624J0352.pdf

(2) http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pmatching.ps


Does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable? I believe the answer to this question is well-known; but, unfortunately, I don't know.

In quantum computing, we know that mixed states are represented by density matrices. And the trace norm of the difference of two density matrices characterizes the distinguishability of the two corresponding mixed states. Here, the definition of trace norm is the sum of all eigenvalues of the density matrix, with an extra multiplicative factor 1/2 (in accordance with statistical difference of two distributions). It is well-known that, when the the difference of two density matrices is one, then the corresponding two mixed states are totally distinguishable, while when the difference is zero, the two mixed states are totally indistinguishable.

My question is, does the trace norm of the difference of two density matrices being one imply these two density matrices can be simultaneously diagonalizable? If this is the case, then taking the optimal measurement to distinguish these two mixed states will behave like to distinguish two distributions over the same domain with disjoint support.

Here is one way to prove the fact you are interested in.

Suppose $\rho_0$ and $\rho_1$ are density matrices.  Like every other Hermitian matrix, it is possible to express the difference $\rho_0-\rho_1$ as
$$\rho_0-\rho_1 = P_0-P_1$$ for $P_0$ and $P_1$ being positive semidefinite and having orthogonal images.  (Sometimes this is called a Jordan-Hahn decomposition; it is unique and easily obtained from a spectral decomposition of $\rho_0-\rho_1$.) Note that the fact that $P_0$ and $P_1$ have orthogonal images implies that they are simultaneously diagonalizable, which I interpret is the property you are interested in.

The trace norm of the difference $\rho_0-\rho_1$ (as you define it, with the multiplicative factor 1/2), is given by $$\|\rho_0-\rho_1\|_{\text{tr}} = \frac{1}{2}\operatorname{Tr}(P_0) + \frac{1}{2}\operatorname{Tr}(P_1).$$  Under the assumption that this quantity is 1, we will conclude that $P_0=\rho_0$ and $P_1=\rho_1$, which proves what you want to prove.

To draw this conclusion, note first that $\operatorname{Tr}(P_0)-\operatorname{Tr}(P_1)=0$ and $\operatorname{Tr}(P_0)+\operatorname{Tr}(P_1)=2$, so $\operatorname{Tr}(P_0)=\operatorname{Tr}(P_1)=1$.  Next, take $\Pi_0$ and $\Pi_1$ to be the orthogonal projections onto the images of $P_0$ and $P_1$, respectively.  We have $$\Pi_0 (\rho_0 - \rho_1) = \Pi_0 (P_0 - P_1) = P_0$$ so $$\operatorname{Tr}(\Pi_0 \rho_0) - \operatorname{Tr}(\Pi_0 \rho_1) = 1.$$ Both $\operatorname{Tr}(\Pi_0 \rho_0)$ and $\operatorname{Tr}(\Pi_0 \rho_1)$ must be contained in the interval [0,1], from which we conclude that $\operatorname{Tr}(\Pi_0\rho_0)=1$ and $\operatorname{Tr}(\Pi_0\rho_1) = 0$.  From these equations it is not difficult to conclude $\Pi_0\rho_0=\rho_0$ and $\Pi_0\rho_1=0$, and therefore $P_0=\rho_0$ by the equation above.  A similar argument shows $P_1=\rho_1$.


Universities for Quantum Computing / Information? Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research?

The aim here is to collect a useful list for someone considering graduate study in these fields, not to discuss which is "best".  To make this list useful, please include a brief description of the part of the university where this area is pursued (in many places this is in an interdisciplinary institute that may not be familiar to everyone), and a URL.

There are two quantum wikis which provide reasonably good list of research groups in QIP: Quantiki and Qwiki. Quantiki has better European coverage, while Qwiki has better US coverage.

The geographic area I know best is the UK. In the UK there are large theory groups in Oxford, Cambridge, Bristol, University College London and Imperial College, among other places.

In Oxford, where I have spent the last 5 years, QIP research is spread across a number of departments: Physics, Computer Science, Materials Science and Maths. There isn't much of a presence in Maths, although it is Artur Ekert's official affiliation. Computer Science has a growing group that mostly looks at category theory and quantum foundations.  Physics has quite a number of different groups ranging from experiments to theory. Materials science is weirdly the department where I have been based (although I know little about materials) and there is both a theory group there and a fair number of experimentalists. Computer Science, Materials and Physics all have taught quantum computing courses which can be taken towards the course requirement of a DPhil.

Hope this is useful.


Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$ For a graph $G$, I want to test if it contains a cycle of length $k$, for some $k$ much smaller than $|G|$. I am interested in particular in an algorithm with low space complexity. The cycle need not be induced, so that I want to return success also for instance in the case that G contains a $k$-clique.
I considered first a well known much simpler case, which is testing if $G$ is in fact a $k$ cycle. This can be done using $O(\log k)$ variables: Assume for simplicity for the moment that $k=4m$. Such an algorithm then boils down to the fact that we can test if two vertices have distance $t$ in space complexity $O(\log t)$. Then we test to see if there are four vertices $x_1,x_2,x_3,x_4$ such that $d(x_1,x_3)=d(x_2,x_4)=2m$ and all other distances between the $x_i$ are $m$.
Note crucially that this algorithm will fail to report true if the graph $G$ has $k$ vertices and contains a cycle, but also some additional edges.
My question now is the following: Is there a similar (or completely different) algorithm that detects when a graph $G$ of potentially large size, contains a $k$ cycle that is not necessarily induced, that has $O((\log k)^d)$ space complexity for some fixed $d \geq  1$? Clearly such an algorithm with space complexity $ k $ exists, but I would like to do better.
P.S. I don't know if it makes much of a difference, but in the applications I am looking at, $k$ will itself be of the order $(\log n)^2$ where $n = |G|$.
P.P.S Also, the graph $G$ that I am looking at will be sparse, they are Erdos-Renyi random graphs in $\mathbb{G}(n,n^{-c})$ for some $c\in (0,1)$.

No, this is impossible for your parameters.  With $s$ bits of space, you can only visit at most $2^s$ vertices of the graph.  Now set $s = O((\log k)^d)$ and $k=(\log n)^2$ and it is clear that you cannot visit all of the graph, as $2^s = o(n)$.  Thus for any algorithm that uses only $O((\log k)^d)$ bits of space, there exist graphs where you fail to detect a $k$-cycle (e.g., because the $k$-cycle is in the unvisited part of the graph).

If $k=n^{\Theta(1)}$, and if your definition of a cycle allows repeated vertices to appear in the cycle, then an algorithm exists.  A simple approach is to guess a starting vertex $v_0$ and store it (which requires $\log n = O(\log k)$ bits); then, non-deterministically guess a path of length $k$, counting up to $k$ as you go (which requires $\log k$ bits), checking that none of the intermediate vertices are equal to $v_0$ and the final vertex is equal to $v_0$.
If $k=n^{\Theta(1)}$, and if your definition of a cycle does not allow repeated vertices to appear in the cycle, then I don't know whether an algorithm exists or not.


Why are perfect graphs called perfect? Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is the single reason they are called perfect? Or is it just a aesthetic preference by Berge?

perfect graphs were first motivated by information transmission theory originating with Shannon ie Shannon Capacity of graphs. they are called "perfect" by Berge because they can be used to model a noiseless or "perfect" information channel wrt transposition errors in transmission called "confounding". from intro in [3] which also has a very detailed history in the 1st chapter cowritten by Berge.

  When Claude Berge defined perfect graphs in 1961, he was motivated by a very practical problem: how do we maximize the rate at which information is sent through a (noisy) transmission channel while avoiding the introduction of errors because of the physical imperfections of the system?

[1] C. Berge, The history of the perfect graphs, Southeast Asian Bull. Math.
20, No.1 (1996) 5-10.
[2] C. Berge, Motivations and history of some of my conjectures, Discrete Mathematics
165-166 (1997) 61-70.
[3] Perfect Graphs by Jorge L. Ramírez-Alfonsín (Editor), Bruce A. Reed (Editor), J.L.R. Alfonsin (Author). Wiley. Ch1, Origins and Genesis by Berge & Ramírez-Alfonsín


'Uniqueing' an unsorted list of integers let $A = [ a_1 \dots a_n ]$ be a sorted list of integers of length $n$. By a simple algorithm that works in-place and in linear time we can remove all duplicates and output a sorted list of unique integers that are precisely the integers which appear .

More generally, it suffices to have a list with the promise that all identical integers are merely grouped to apply the same idea.

Now let $A$ be a list of integers, neither sorted nor even grouped as above. Let us call the problem of outputting a not-necessesarily sorted list of integers that are precisely the integers appearing $A$ by the term "uniquing problem".

An algorithm to solve the "uniqueing problem" might sort the list and remove multiple entries in the obvious way, thus requireing a running time of O( n log(n) ). Can we do better? I don't think so, although there might be a speed up because we actually do not require any sorting on the output list, so this algorithm performs actually too much.

Best,
Martin

In practice you can solve this problem easily in linear expected time with a hash table: just hash everything and eliminate the duplicates when they collide with each other. See, e.g. this Python recipe which primarily uses hashing but falls back on other strategies for objects that can't be hashed.

Whether you accept this as an acceptable theoretical answer depends somewhat on your model of computation.


Possible to do Complexity theory with only counting and Pigeonhole Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient or is it just Complexity theory as we know it today outside quantum Complexity theory and undecidability just some part of large scale of things inferable from counting and Pigeonhole and where does quantum complexity theory fit in (essentially I am asking what kind of structures have been applicable and essential or can we do away with structures completely and reduce complexity theory to counting and pigeonhole?)?

If you are looking for non-pigeon-hole type arguments, then there is good news: they exist! The pigeon-hole principle is a certain template for proof by contradiction. There are concepts in TCS which are not proof by contradiction, and therefore, in particular, are not instances of the pigeon-hole principle. There are also proofs by contradiction where the pigeon-hole principle is necessary but not sufficient.

My personal opinion: It is fruitful to take apart a proof and see why it works: what are the ingredients? When you understand the ingredients, a proof ceases to be a monolithic line of reasoning and "symbol-pushing", and it will become a modular object with identifiable moving parts, which you can then reuse between proofs, eventually making your own ones. As a corollary, you are right to become wary when all your results derive most of their power from one core lemma (such as PHP in this case), because it means that you are probably working within the narrow confines of that lemma, and you may benefit from learning and incorporating other theorems from other fields into your work (See also Terry Tao's advice, and more advice on this topic)

Hence it is useful to identify which proofs, and which parts of those proofs, are the PHP or versions and extensions thereof. At the same time, however, we must be careful to mark any and every type of counting argument as a PHP-argument, and even more careful to discard any proof that incorporates a pigeon-hole argument. Usually, the counting argument is only the closing argument to "plant the flag on the mountain", but the counting argument is used at a point that you can only get to when you've already done the bulk of the work, when "you've climbed the mountain", which is arguing why the one set is bigger than the other. The IP=PSPACE example is instructive here: It is true that there is a counting argument involved, but the more sophisticated part of the proof is arguing that Arthur's random choices usually lead to acceptance. This invokes the Fundamental Theorem of Algebra, which is typically proved using complex analysis via properties of holomorphic functions (Wikipedia lists four proofs, none of which can be said to boil down to PHP).

An extreme analogy: every line of every proof is an instance of modus ponens. But would be unfair to object that proofs simply boil down to modus ponens.

The most immediate concept that is not a proof by contradiction is algorithms.

For example, the algorithm of the Cook-Levin proof that SAT is NP-Complete transforms a (Turing Machine, input)-pair to a Boolean Circuit, or to a 3-CNF formula, according to taste. The proof then argues that this transformation preserves both soundness and completeness. This is not a pigeon-hole type argument, because it is constructive in the sense that they argue that something is possible, whereas the pigeon-hole principle argues that something is impossible.

More generally, all results which state that a language $L$ is complete for a complexity class $\mathcal{C}$ are constructive in this sense.

Is IP=PSPACE a pigeon-hole type argument?

The part of the proof of the sumcheck's protocol's soundness amounts, in the end, to saying "The polynomial does not have enough zeroes, relative to the size of the field, to fool Arthur with good probability." According to taste, this sentence may or may not be an instance of the pigeon-hole principle.

The protocol's soundness relies on, not just that the field is bigger than the number of the polynomial's zeroes, but it relies on the fact that the ratio of non-zeroes to zeros is large enough (sufficiently large for Arthur to guess a non-zero in each iteration of the protocol, with $1-\frac{1}{poly(n)}$ probability). This reasoning about ratios goes beyond the pigeon-hole principle: I would say this part of the proof is by counting, but not by pigeon-hole principle.

The proof argues that the protocol terminates in polynomial time. To this end, it requires polynomial-time randomized algorithms for guessing a large prime and computing $+,-,\times$ modulo large primes. The proof also argues that the arithmetization of a Boolean formula preserves its behaviour on the Boolean cube. These ingredients are non-trivial and necessary. Hence to this end, the pigeon-hole principle may be necessary, but is not sufficient.

Is the time hierarchy theorem a pigeon-hole type argument?

The proofs of the time- and space hierarchy theorems are not necessarily pigeon-hole type, even though they are proof by contradiction. However, they are identical in structure to (perhaps inspired by) Cantor's proof that some infinities are bigger than others, establishing a pigeon-hole principle for infinite sets (in particular, I have taught a class where I proved these two theorems at the same time, on two adjacent black boards, walking over from one to the other for every new line). Cantor's proof is diagonalization, and from diagonalization follows a type of pigeon hole principle for infinite sets. However, there are two things to be said against counting the time hierarchy theorem as a pigeon-hole type argument. First, the proof is by diagonalization, not by counting. Second, there are many more ingredients in the proof, without which, it would not go through; for instance, a simulation of one Turing Machine by another; for stronger versions, an efficient simulation, which in turn uses such ingredients as shifting the tape to achieve low amortized time complexity. The diagonalization is necessary but not sufficient.


What CS blogs should everyone read? Many top notch computer science researchers and research groups) maintain active blogs that keep us updated on the latest research in the authors' fields of interest.  In most cases, blog posts are easier to understand than formal papers, because they omit most of the gory technical details and emphasize intuition (which papers generally omit).

Thus, it would be useful to have a list of recommended blogs, in the same spirit as other lists of recommended resources:

What papers should everyone read?
What books should everyone read?
What are the recent TCS books whose drafts are available online?
What videos should everybody watch?
What lecture notes should everyone read?

Of course one can follow the excellent Theory of Computing Blog Aggregator, but that list is rather overwhelming, especially for beginners.

Please highlight why you recommend them.

It might come as no surprise, but there is a substantial overlap between cstheory Q&A power-users and the blogosphere. We even had a dedicated blog for a while, with some great posts but it fell into disuse. However, I thought I would list some of the blogs run by our top 38 users that have had new posts since 2012:

David Eppstein's 0xDE: graph-theory and algorithms.
Suresh Venkatasubramanian's The Geomblog: computational geometry, algorithms, and discussions of academic life.
Jeff Erickson's Ernie's 3D Pancakes: computational topology, and community announcements.
Neel Krishnaswami's Semantic Domain: programming languages, logic, and formal languages.
Joe Fitzsimons's Quantized Thoughts: quantum information and computation, theoretical physics, and community building.
Andrej Bauer's Mathematics and Computation: HoTT, logic, category theory, and philosophy of math.
András Salamon's Constraints: computational complexity through the lens of constraint satisfaction.
Marzio De Biasi's ... nearly 42 ...: computational complexity highlighted through NP-completeness and puzzles.
Scott Aaronson's Shtetl-Optimized: computational complexity, with a primary focus on quantum computing, philosophy, humour, and community building.
Lev Reyzin's Room for Doubt: theory and practice of machine learning, and academic life.
Noam Nisan's Turing's Invisible Hand: computational economics, algorithmic game theory, and community building.
Sariel Har-Peled's Vanity of Vanities, all is Vanity: computational geometry, and general social and academic commentary.
Shiva Kintali's My Brain is Open: computational complexity, polyhedral combinatorics, algorithms, and graph theory.
Artem Kaznatcheev's Theory, Evolution, and Games Group: evolutionary game theory, and algorithmic lens on evolution, learning and philosophy.
Hsien-Chih Chang's Finite Playground: bilingual blog on computational complexity, formal languages, and concrete math.
Aaron Sterling's Nanoexplanations: distributed computing, chemoinformatics, and general social commentary.
Lance Fortnow and Bill Gasarch's Computational Complexity : Computational Complexity and other fun stuff in math and computer science.
Emanuele Viola's Thoughts: computational complexity and general commentary -- started Summer 2014.


What are some good resources for strengthening my theoretical foundation for machine learning? I'm a computer science major and I'm taking a lot of machine learning courses. I'm finding that my theoretical foundation on subjects like calculus and linear algebra are not as strong as I'd like them to be, so I'm wondering about resources for these two topics. I'm not new to either areas, but I would like to build a really solid theoretical foundation since I enjoy being rigorous and I also potentially want to do research in ML in the future.

Calculus: I took calc 1 and calc 2 in high school, but my AP class didn't really cover that much more beyond basic derivatives, integrals, and Taylor series. I took calc 3 recently but I feel that my intuition about multivariate calculus is still relatively weak.
Linear algebra: I took a rigorous proof-based book on linear algebra as a first course on linear algebra. While I enjoyed the class and did well in it, I don't know that much about the applications, and we didn't get to things like diagonalization. I've been reading Linear Algebra Done Right since it's been recommended to me by a friend and I've heard great things about it.

What are some resources (online or books) that I can use to review and strengthen my theoretical understanding on these two topics, especially calculus? Preferably I'd like something with a lot of exercises and not necessarily aimed at someone with no prior knowledge of it.

I suggest
Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal. Probability is at the foundation of machine learning and it's one of the weakest points for many beginners, in my experience.


Cubic (3-regular) graph spanning tree Considering loop free cubic graphs (graphs where every node has 3 neighboring nodes)： Is is possible to construct a spanning tree that only has nodes with 3 neighbors in the spanning tree or 1 neighbor in the spanning tree (leaves).

That is I want to be able to construct a spanning tree where there are no nodes that are connected to only 2 other nodes in the spanning tree. They should all be connected to either 1 node (a leaf) or all their edges in the underlying cubic graph should also be present in the spanning tree (ie attached to 3 nodes in the spanning tree)?

Does anyone know the answer to this? And if it is possible, how to construct such a spanning tree? Many thanks.

Here is a counterexample, which I'm too lazy to draw. Let $G_1,G_2$ be diamonds, graphs on four vertices having five of the six edges. Connect matching vertices in $G_1$ and $G_2$ so that you get a connected cubic graph. It seems that there is no spanning tree in which every internal vertex has degree exactly $3$.


Solving multiple instances of 3SUM generated from the same set (this is a follow-up of my previous question, which uses the 3SUM' problem instead of 3SUM)

Suppose we have a list $S$ of $n$ integers.
Usually, for 3SUM, we only determine if there exist $a$,$b$,$c$ $\in S$ such that $a+b+c=0$. That's done in $O(n^2)$, and obviously the same thing can be done for $a+b+c=d$, with $d$ an integer.

Now, I use a somewhat modified version of this problem. Someone randomly picks $n$ triplets of elements of $S$, and for each of them, computes the sum of its elements. Let's call the list of these sums $Y$. That's $n$ instances of 3SUM built on the same set.

My goal is to invert one element of $Y$., i.e. is to find one element in $Y$, along with its corresponding elements in $S$. (To solve one of the possible instances of 3SUM, no matter which one)

I'm looking for a $O(n)$ solution. If we feed this solution some particular $S$ and $Y$ ,and we want to find a particular $d$ in $Y$, it would take the solution $O(n)$ attempts to find the $d$ we're looking for, thus running in $O(n^2)$, which is the 3SUM complexity.

I tried to use randomness in my solutions, without success. Someone also advised me to have a look at FFTs, but I can't see how I could use them in this case.

The best that I can do now, is to have $Y$ built with $n^{1.5}$ triplets instead of $n$, and then I can use the birthday paradox. If I pick $O(n^{1.5})$ triplets at random, I have a constant probability to find the same triplet twice. ($n^{1.5} = \sqrt{n^3}$)

It's not linear time, but here at least is an $O(n^{3/2})$ randomized solution to the problem in which you are given a set of $n$ elements together with the sums of $n$ randomly-generated triples of the elements, and you have to find a triple that matches one of the given sums.

Pick randomly two subsets $A$ of $n^{3/4}$ elements and $B$ of $n^{1/2}$ elements. With constant probability at least one of your 3SUMs is in $A+A+B$.
Compute the set $A+A$ and store it in a hash table for fast lookups.
For each pair of a value $x$ in $B$ and a target value $z$ of one of the input 3SUMs, test whether $z-x$ is one of the stored values of $A+A$, and if so whether the resulting triple(s) of numbers $A+A+B$ that sum to $z$ are distinct from each other.

I originally thought this would work equally well for an adversarially-selected set of 3SUMs (instead of the randomly-selected set in your question), but now I'm not sure sure about that part: the expected number of 3SUMs you hit with your choice of $A+A+B$ is always constant, but maybe the adversary could fix things so that you have a high probability of hitting none of them and a small probability of hitting many at once? I'm not sure this is possible but it would take more analysis than I've done so far to be certain.


Approximation for counting the number of simple $s$-$t$ paths in a general graph I have been told that there are some good polynomial time algorithms for approximating the number of simple paths in an directed graph from given starting vertex $s$ to given ending vertex $t$. Does anyone know of a good reference on this subject?

Background: counting the exact number of paths in a general graph is #P-complete but there may exist polynomial time approximations for the problem. I'm especially interested in random approximations.

Thanks in advance.

This problem should be NP-hard by reducing from the maximum length of s-t paths.

The reduction simply replace every edge by, say, $k$ parallel edges. (If you are uncomfortable with a multi-graph, replace each edge by a path of length 2.) The effect of this is that the number $C_{\ell}$ of paths of length $\ell$ becomes $k^\ell C_{\ell}$. Thus, if $k$ is suitably large, the term corresponding to the longest paths in the original graph will dominate everything else (even if $C_{\ell_{max}}=1$). From there you can easily recover the length of the longest s-t path.


Canonical labeling of special classes of DAGs Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known.

  What are some special classes of DAGs that can be canonized in polynomial time ?

To start with the obvious: DAGs containing a Hamiltonian path, using the uniqueness of their topological orderings, and polytrees, as an orientation-labeled variant of trees.

On the other hand, it's tempting to list multitrees (as I did in an earlier incorrect version of this answer), using canonization of trees to prioritize their topological orderings, but they're GI-complete (subdivide each edge of an undirected graph into two directed edges oriented outwards from the subdivision point), so that doesn't work.


Is it possible to compute whether two functions are extensional equal? If you have two functions implementing a different sorting algorithm, is it then possible to infer by source code that they both have the same external properties? Meaning that they both will have a possible unsorted sequence as their input and have a sorted sequence as their output? In what way could these external properties be determined by the source code? And how would you describe these external properties? What notation would be used?

The external properties could be made known by defining them explicitly, for example within a type system, but I am wondering whether this could be done implicitly. Or is it somehow theoretically impossible to infer this kind of semantics? I am interested in whether this is possible for arbitrary functions, not just for sorting algorithms, assuming things like functions will always halt and have no side-effects.

Should I look at denotational semantics, or is unrelated?

I'm interested in pointers to research in this area and to different terms used to describe the subject that might help my literature search.

Yes. If you can verify that they are the same, then so can a computer.

Here's a quick specification for an integer sort in Coq:

Inductive natlist : Type :=
| nil : natlist
| cons : nat → natlist → natlist.

Fixpoint is_sorted (l : natlist ) : bool :=
    match l with
    |  nil => true
    |  (cons x nil) => true
    |  (cons x (cons y r)) => if x <= y then is_sorted (cons y r) else false
    end.

...

Theorem sort_spec : forall l, is_sorted (sort_list l).

A specification can be directly encoded into the declaration of sort using dependent types.

For this particular problem, John Darlington demonstrated in the 70s that 6 families of sorting algorithms can be derived by mechanically transforming the specification of a sort into an implementation; I believe this goes under the name "semantics-based program derivation."

In the software-engineering world, finding extensionally equivalent functions is known as "semantic clone detection."

Dave Clarke also gave a good answer to this question on the CS StackExchange: https://cs.stackexchange.com/questions/2059/how-do-you-check-if-two-algorithms-return-the-same-result-for-any-input

This all falls under the umbrellas of formal methods and programming languages. Denotational semantics are one class of techniques for modeling semantics, but they've fallen out of favor for being difficult to use compared to operational semantics.


Citation style for CS publications What is the recommended citation style for use with CS (and related) publications?

I tried looking at submissions at http://arxiv.org/archive/cs but all of them seem to use different citation styles.

I'm doing an academic project and I'm writing a project report for the same. So, is there a (possibly 'standard') citation style that is preferred over other citation styles (such as those listed at  http://en.wikipedia.org/wiki/Wikipedia:Citing_Wikipedia#Examples) for CS publications (like research papers, project reports, books, presentations etc.)?
Or, is it a matter of personal choice/preference (and sticking to it forever)?

Most CS conference publications use the ACM BibTeXstyle file (or the plain style file) to cite papers, and that constitutes the de facto 'style'. Different journals and conferences often prescribe their own citation format via a different BibTeX style.

So the short answer to your question is that there isn't a common style, and if you believe in using BibTex, then merely changing the style file can allow you to accommodate different styles.


Computing every boolean function with a polynomial over $\mathbb{F}_3$? The following paper briefly mentions the power of $MOD_6$ gates (page 3), and relies on the unstated fact that every boolean function can be computed with an arithmetic circuit of depth 2 over $\mathbb{F}_3$. I'm not sure how this is done.

Every function $\mathbb{F}_p^n \longrightarrow \mathbb{F}_p$ (where $p$ is prime) can be written as a polynomial. For the proof, consider all $p^n$ monomials, and show that they are linearly independent.


What is the complexity of this edge coloring problem? Recently, I have encountered the following variant of edge coloring.

  Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying the constraint that, for every vertex $v$, the edges incident to $v$ use at most two colors.

My first guess is that the problem is NP-hard. Classical NP-hard proofs for graph coloring problems are mostly by reduction from 3SAT. But in my opinion, these proofs are not useful for this problem because edges incident to a vertex can be colored with the same color, so we cannot construct logic components in the graph.

Could this problem be NP-hard? If yes, what is a proof? If we cannot fine a proof, is there any method to determine the complexity of this problem?

Thanks!

This problem is NP-hard and APX-hard; see: Adamaszek and Popa,
Approximation and Hardness Results for the Maximum Edge $q$-coloring
Problem, Lecture Notes in Computer Science 6507 (2010) 132-143.

The parameterized complexity aspects of this problem is addressed in this recent paper.


On facets of 01-polytope $0,1$-polytopse are fundamental objects in combinatorial geometry and comvex optimization. I am interested in the size of binary representation of hyperplanes to use in the framework of computational complexity theory.

Let $v_1, v_2, \dots, v_N$ be points in $\{0,1\} \subseteq \mathbb{R}^n$.  Does every facet of the convex hull of these points lie on a supporting hyperplane $$\sum_{i=1}^n a_i x_i = t,$$ where every coefficient $a_i$ is either 0 or 1?
If not, how many bits are needed to express the coefficients $a_i$ of a facet hyperplane?

For your second question, the number of bits is $O(n^2 \log n)$ (i.e. $O(n\log n)$ per coefficient) and there are examples where it is $\Omega(n^2\log n)$, i.e. the bound is tight. See Corollary 26 here.

The ideas are standard, and anyone who has seen an analysis of the ellipsoid algorithm will be familiar with this. Say you have a facet in the hyperplane spanned by vertices $v_1, \ldots v_{n-1}$. If the hyperplane is through the origin, it is defined by $a^T x = 0$ for the vector $a$ satisfying $V^Ta = 0$ where $V$ is the matrix containing $v_1, \ldots, v_{n-1}$ as columns. Using the fact that $V$ is a 0-1 matrix, you can bound the coefficients of $a$ using Cramer's rule and the Hadamard bound. If the hyperplane is not through the origin the argument is the same but the defining  equality is $a^T x = 1$ and the system of equalities you need to solve is $V^Ta = e$ where $e$ is the all-ones vector.

The lower bound is based on observing that everything above is tight and constructing a matrix $V$ such that removing any row from $V$ gives a matrix with a huge determinant. This construction is the one thing about your question which is research level, see the book or this paper by Alon and Vu


Is the proceedings of WG 2015 published? Within theoretical computer science, the "Workshop on Graph-Theoretic Concepts in Computer Science (WG)" is one of the main specialized venues for publication of papers dealing with graph theory. It's 41st edition, WG 2015, happened in June 2015.

For several reasons I need to provide the full reference of a paper which appeared at WG 2015. However I could not find the proceedings online. It should have been published in LNCS. My questions are the following.

Were the proceedings already published?
If not, when will the proceedings be published?
What can I do to get the full reference information of the paper if the proceedings are not yet out?
Is it normal for a conference to take so long to publish the proceedings?

I am an author of a paper that is to appear in the WG 2015 proceedings. As far as I know, they have not appeared yet, which is indeed quite strange.

Early February I emailed the chair (Ernst Mayr) to ask for the page numbers of my paper; they were not yet known at that time. The chair informed me that he encountered a big technical problem when producing the files for the proceedings, but that the problems were cleared up and that he was in almost done compiling. If you want up to date info, I suggest emailing Ernst Mayr.

PS: The LNCS volume number will be LNCS 9224.


NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following:

There is a value $\epsilon_1$ such that approximation within a factor of $\epsilon_1$ is possible in polynomial time.
There is a value $\epsilon_2$ such that approximation within a factor of $\epsilon_2$ is NP-hard.
There is some value $\epsilon$ between $\epsilon_1$ and $\epsilon_2$ such that approximation within a factor of $\epsilon$ are neither in polynomial time nor NP-Hard.

(There is a general question about NP-intermediate problems here, but it is much more general in its problem domain, as well as oriented towards the exact-answer setting)

The sidebar algorithm has done its work, and linked to this similar question. The accepted answer there explains that under the Unique Games Conjecture, no such regimes exist.


How hard is this combinatorial optimisation problem? Suppose we have multiple intervals $R_1,R_2,...,R_i$ of non-negative integers. These intervals may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th interval $R_h$, and $x_R$ to denote the interval that the integer $x$ comes from. It is possible that two integers $x$ and $y$ are equal but they come from different intervals (i.e., $x=y$ but $x_R\neq y_R$).
Suppose we have a threshold $T$, a positive integer $N$, and a function $f(x)$ whose input is an integer $x$ and it is defined as: $f(x)=x$, if $x \leq N$. $f(x)=max(0,2N-x)$, if $x>N$.
I want to choose integers from intervals $R_1,R_2,...,R_i$ to maximise the cumulative scores $f()$ without exceeding the threshold $T$.
There are two constraints

Chosen integers must come from different intervals

Given two chosen integers $x$ and $y$, if $x_R(\mathrm{median}) \leq y_R(\mathrm{median})$, then
$$
\frac{x_R(\mathrm{median})}{x} \leq \frac{y_R(\mathrm{median})}{y}.
$$

The objective is maximising the following:
$$
\sum_{x \in R_1,R_2,...,R_i} p_x f(x)
$$
subject to:

$p_x=\{0,1\}$,
$\sum_{x \in R_1,R_2,...,R_i} xp_x \leq T$,
$\forall (x, y)$, if $p_x=p_y=1$, then $x_R \neq y_R$,
$\forall (x, y)$, if $p_x=p_y=1$ and $x_R(\mathrm{median}) \leq
    y_R(\mathrm{median})$, then  $$ \frac{x_R(\mathrm{median})}{x} \leq
    \frac{y_R(\mathrm{median})}{y}. $$

I have proved that this problem is weakly NP-hard by reduction from knapsack problem when each range contains exactly one integer. But I think the my problem should not be just weakly NP-hard. I know this problem can be reduced to the Knapsack Problem with conflict graphs, but not vice versa. Is it possible to perform reduction from existing strongly NP-hard problems to the one described above?

This problem can be solved with dynamic programming in pseudo-polynomial time (proof below). Therefore, it is not possible to show that this problem is strongly NP-hard (unless P=NP).

First, let's restate the problem:
Given: values $N$ and $T$ and positive integer intervals $R_1$, $R_2$, $\ldots$, and $R_n$
Output: the largest possible value of $\sum_{i=1}^nf(x_i)$ (where $f$ is defined in terms of $N$ as described above) such that the variables $x_1, x_2, \ldots, x_n$ satisfy all of the following:

$x_i \in R_i$ for $i = 1,2,\ldots,n$
$\sum_{i=1}^nx_i \le T$
for all pairs $i,j$, if $\text{median}(R_i) \le \text{median}(R_j)$ then $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_j)}{x_j}$

We can assume without loss of generality that the $R_i$s are sorted by median. That is, assume that $\text{median}(R_1) \le \text{median}(R_2) \le \ldots \le \text{median}(R_n)$. If we do, the final condition can be simplified. It is both necessary and sufficient that $\frac{\text{median}(R_1)}{x_1} \le \frac{\text{median}(R_2)}{x_2} \le \ldots \le \frac{\text{median}(R_n)}{x_n}$.
(Note: this is not precisely correct. Assuming no intervals have the same median, this is correct, but if multiple intervals have the same median it is actually also necessary that the $x_i$ values chosen for those intervals have to all be the same. This makes things more complicated without really making the problem any harder, so I'm going to ignore this possibility for the rest of this answer.)

With that done, we can define the subproblems that we will use for our dynamic programming solution.
Given: all the inputs for the problem as well as (1) an index $k$ with $1 \le k \le n$, (2) a threshold $t$ with $0 \le t \le T$, and (3) a value $X \in R_k$
Output: the largest possible value of $\sum_{i=1}^kf(x_i)$ such that the variables $x_1, x_2, \ldots, x_k$ satisfy all of the following:

$x_i \in R_i$ for $i = 1,2, \ldots, k$
$x_k = X$
$\sum_{i = 1}^kx_i \le t$
for $i = 1,2, \ldots, k-1$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$

Let $S[k][t][X]$ denote the output of this subproblem.

Note that the overall problem's answer can be expressed in terms of several subproblems: the overall answer is $\max_{X \in R_n}S[n][T][X]$.
Note also that the number of subproblems is small (polynomial in the size of the numbers in the input of the problem). In particular, $k$ takes on $n$ possible values, $t$ takes on $T+1$ possible values, and $X$ takes on $\sum_{i=1}^n|R_i|$ possible values. Each of these is polynomial in the numbers used as inputs to the problem. Therefore, the overall number of subproblems is also polynomial in the numeric value of the input. Thus, provided we can show that each subproblem can be solved in pseudo-polynomial time, it will also be the case that all the subproblems together can be solved in pseudo-polynomial time, and therefore that the overall problem can be solved in pseudo-polynomial time.

In order to actually solve the subproblems, we will use dynamic programming. In other words, we will build up a table of values for $S[k][t][X]$. We can compute these subproblems in order primarily by $k$. In other words, we can assume that by the time we are computing $S[k][t][X]$, the value of $S[k'][t'][X']$ has already been computed provided $k' < k$.
So how do we actually compute these values?
The base case, where $k=1$, is easy. $S[1][t][X]$ is defined as the largest possible value of $\sum_{i=1}^kf(x_i) = f(x_1)$ where $x_1 = X \le t$. Therefore, provided $X \le t$, we have that $S[1][t][X] = f(X)$. Otherwise, no such value is possible and so we can set $S[1][t][X]$ to $-\infty$ to indicate that no real value is achievable.
Otherwise, let's say we're trying to compute $S[k][t][X]$ for some $k > 1$. This value is defined as the largest possible value of $\sum_{i=1}^kf(x_i)$ subject to the following constraints:

$x_i \in R_i$ for $i = 1,2, \ldots, k$
$x_k = X$
$\sum_{i = 1}^kx_i \le t$
for $i = 1,2, \ldots, k-1$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$

Since we know $x_k = X$, the value we are maximizing is $\sum_{i=1}^kf(x_i) = f(x_k) + \sum_{i=1}^{k-1}f(x_i) = f(X) + \sum_{i=1}^{k-1}f(x_i)$. This is the same as just maximizing $\sum_{i=1}^{k-1}f(x_i)$. What conditions do the variables $x_1, \ldots, x_{k-1}$ have to satisfy? We can reframe the above conditions as follows:

$x_i \in R_i$ for $i = 1,2, \ldots, k-1$
$\sum_{i = 1}^{k-1}x_i \le t - X$
for $i = 1,2, \ldots, k-2$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$
it is the case that $\frac{\text{median}(R_{k-1})}{x_{k-1}} \le \frac{\text{median}(R_{k})}{X}$

By the final condition, only some of the possible values of $x_{k-1}$ are actually permissible values. In particular, we have the condition that $\frac{\text{median}(R_{k-1})}{x_{k-1}} \le \frac{\text{median}(R_{k})}{X}$, which can be rearranged to be $x_{k-1} \ge X \times \frac{\text{median}(R_{k-1})}{\text{median}(R_{k})}$. Thus, $x_{k-1}$ must be some value from $R_{k-1} \cap [X \times \frac{\text{median}(R_{k-1})}{\text{median}(R_{k})}, \infty)$. Call this other interval $R_{k-1}'(X)$
Suppose we fix some value $Y \in R_{k-1}'(X)$ and add the constraint that $x_{k-1} = Y$. At that point, we're trying to maximize $\sum_{i=1}^{k-1}f(x_i)$ subject to the following:

$x_i \in R_i$ for $i = 1,2, \ldots, k-1$
$x_{k-1} = Y$
$\sum_{i = 1}^{k-1}x_i \le t - X$
for $i = 1,2, \ldots, k-2$, it is the case that $\frac{\text{median}(R_i)}{x_i} \le \frac{\text{median}(R_{i+1})}{x_{i+1}}$

But this is just the definition of $S[k-1][t-X][Y]$.
It should be pretty clear at this point that $S[k][t][X]$ is just the maximum over $Y \in R_{k-1}'(X)$ of $f(X) + S[k-1][t-X][Y]$. Note: if $R_{k-1}'(X)$ is empty then no choice of values is possible and so we again set $S[k][t][X]$ to $-\infty$. Similarly, we can assume that if $t-X < 0$ then the value $S[k-1][t-X][Y]$ is just defined to be $-\infty$ by default. (Note that this formula appropriate handles the case where some of the $S[k-1][t-X][Y]$ values are $-\infty$).
Anyway, assuming you deal with all the edge cases, this shows that you can compute $S[k][t][X]$ in terms of the previous values $S[k'][t'][X']$ with $k' < k$. The runtime of this computation is linear in the size of $R_{k-1}'(X)$, which is at most $|R_{k-1}|$. Therefore, the computation of each $S[k][t][X]$ is pseudo-polynomial in the input, implying (as previously argued) that the computation of all the subproblems together also runs in pseudo-polynomial time.

EDIT: I was asked to address two specific issues in the comments. First of all, what happens if the function $f$ can depend on which interval $R_i$ it is taken from. And second, what happens if not every interval has to contribute a value (i.e. if you are allowed to skip an $x_i$). I believe the problem is still solvable with the same pseudo-polynomial time dynamic programming approach. I also mentioned earlier that the solution above ignores the possibility that multiple ranges share the same medians. I have not edited the solution above, but to address these concerns, I'm adding a coded up version of my algorithm (using python), fixed to address all these issues.
I assume that the input consists of a value T (representing $T$) and a list Rs, whose elements represent the ranges $R_i$ and which can be looped over. I assume that the elements of Rs are in sorted order by median and that there exists a function median that can identify the median of any such range. I also assume that there exists a function f which takes as input two values: an index i and a value x. f(i, x) is used to represent $f_i(x)$.
def solve(T, Rs):
  if len(Rs) == 0:
    return 0

  # S is going to be the subproblem lookup table. S[k][t][X] will denote
  # the largest possible output value using xs only from ranges Rs[0]
  # through Rs[k] (with each range contributing at most one x), such that
  # the sum of the xs is at most t, and such that range Rs[k] does contribute
  # a value, and the value it contributes is X.
  S = []

  # base case
  layer = [{X: float(-inf) for X in Rs[0]} for t in range(T+1)] # default to -inf
  S.append(layer)
  for t in range(T+1):
    for X in Rs[0]:
      if X <= t:
        S[0][t][X] = f(0, X)

  # inductive case
  for k in range(1, len(Rs)):
    layer = [{X: float(-inf) for X in Rs[0]} for t in range(T+1)] # default to -inf
    S.append(layer)
    for t in range(T+1):
      for X in Rs[k]:
        # the minimum necessary condition is that X <= t
        if X <= t:
          # if no other range contributes an x, then the smallest possible
          # value is f(k, X)
          layer[t][X] = f(k, X)
          # if some other range does contribute an x, then there is a largest
          # index range which does so; the index of that range is some i < k
          # and we can loop over the possibilities
          for i in range(k):
            # we can also loop over the possible values of what x that range
            # contributed
            for Y in Rs[i]:
              # in order for this to be valid, the following must hold:
              if median(Rs[i]) / Y <= median(Rs[k]) / X:
                # also, if the medians are the same, we also have the
                # constraint that X=Y; therefore, this case is only valid
                # if the following holds
                if median(Rs[i]) != median(Rs[k]) or X == Y:
                  # the best possible value in this case is the following
                  value = f(k, X) + S[i][t-X][Y]
                  # if this is better than anything so far, use this value
                  S[k][t][X] = max(S[k][t][X], value)

  # Now lets actually get the overall answer. One possibility is to use no xs
  # from any range:
  best = 0

  # otherwise, there will be some largest index range which contributes an x
  # and it will contribute some specific X
  for k in range(len(Rs)):
    for X in Rs[k]:
      # the largest possible value in that case subject to all the constraints:
      value = S[k][T][X]
      # we can use that value instead of the best one saved if it's better
      best = max(best, value)

  return best


Continued Fraction Algorithm in Shor's Algorithm I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$.

We have a number $\psi$, which for a rational number $\dfrac{s}{r}$ satisfies
\begin{equation}
\Big| \dfrac{s}{r} - \psi \Big| \leq \dfrac{1}{2r^{2}}
\end{equation}
which means that if $\psi$ has continued fraction algorithm $[a_0,\dots,a_N]$ then $\dfrac{s}{r}$ has continued fraction $[a_0,\dots,a_k]$ for $k \leq N$.

The book just says that then applying the continued fractions algorithm to $\psi$ we obtain $r'$ which is our estimate for $r$. I'm not too sure how exactly we arrive at this value of $r'$. Is it just that once we obtain our expansion $\psi = [a_0,\dots,a_N]$, we obtain a value $r'_{m}$ for each of the $m^{th}$ convergent expansions and see which one is correct?

Yes, that's exactly the idea.  It is inspired by the following fact:

Theorem. Let $\psi$ be an irrational number, and suppose $|\psi - s/r| \le 1/2r^2$.  Then $s/r$ is one of the convergents of the continued fraction expansion of $\psi$.

In other words, every "very good" approximation to $\psi$ can be obtained by computing the continued fraction representation of $\psi$ and looking at one of its convergents.

In the specific situation you mentioned, we know $\psi$, and we don't know $s$ or $r$.  However, we know that there exist $s,r$ such that $|\psi - s/r| \le 1/2r^2$.  It follows from the theorem that $s/r$ must be one of the convergents of the continued fraction of $\psi$.

Therefore, if we iterate through the convergents of the continued fraction for $\psi$, this is guaranteed to find $s,r$.  Moreover, this procedure is efficient: you'll only have to look at $O(\lg r)$ convergents, so the running time will be polynomial in $\lg N$.

See also https://math.stackexchange.com/q/1139381/14578.


Has ping based failure detector 'strong completeness' and 'weak accuracy'? I was reading 'Unreliable Failure Detectors for Reliable Distributed Systems' (PDF) and I was wondering if ping (with increasing timeouts in case of failure) is in class S of failure detectors:

strong completeness
weak accuracy

There is a lot that needs to be clarified about the model (ping) in which we want to evaluate. What are the processes IDs ? Is it IPs (IP network) ? Is the IPs permanent ? Can the IP change ? Are they connected point wise or there is a router/switch ? Can the switch fail ? Are the connections trusted or can a connection fail between two correct processes ?

I'll give counter examples assuming the TCP/IP model, where there are not permanent IPs (DHCP based IP configuration).

Strong completeness requires that every process that crashes is permanently suspected by every correct process.

Counter-example: Take process A and B, with IPs IP1 and IP2. Process A crashes permanently, releasing the IP. Process B makes a brief disconnection and acquires a new IP, which happen to be IP1.

Solution: We must assume IPs are strictly bound to each process, and can never change. Unless you identify processes with other application layer unique IDs.

Weak accuracy requires some correct processes are never suspected. Actually, if the switch/router fails for a few minutes, every process might suspect all other processes, even if all of them are correct.

The ping is delusive  because it is on the IP level. To avoid these complexities and be able to reduce the needed assumptions to a minimum, think about some level of abstraction, like an application-level failure detector. However if you will really get down to the details, there is a lot to consider in the physical layer (wifi, ethernet) and on other layers as well (TCP, UDP, NAT) etc.


Classes with oracles forcing the caller to immediately accept (or reject)? Usually an oracle operates as a black box, simply returning an yes or no answer to the machine calling it; once it has the result, the caller is free to proceed as it sees fit.

However, what happens if the caller must accept or reject (exactly one of the two) immediately as a function of the oracle's output? Say, for example, the caller has access to a SAT oracle, but must always accept (unconditionally) whenever the oracle answers with "yes"; this means the caller can continue its operation if and only if the query formula is unsatisfiable.

This imposes a restriction, obviously; are there cases in which this yields — or there is reason or evidence enough to suspect it yields — a strict subset of decision problems when compared to the "usual" behavior?

I am particularly interested in the case of $\mathsf{P}^{\mathsf{NP}}$ or similar classes in the polynomial hierarchy, but other classes and oracles are relevant too.

The question is not entirely clear to me. However, concerning the example that is spelled out more precisely: if a language is recognizable by a poly-time machine with a SAT oracle which must accept whenever the oracle answers “yes”, it is in fact in NP. First, observe that regardless of the oracle answers, we can simulate in polynomial time the only possible run of the algorithm by pretending all answers are “no”. (In particular, we can compute the list of all oracle queries beforehand.) Then, the original algorithm accepts iff one of the oracle answers in the simulated run is actually “yes”, or the simulated algorithm accepts in the end. This is an NP property.

More generally, if we use an arbitrary oracle $A$ in the above scenario in place of SAT, a language can be computed in the indicated way iff it is poly-time dtt-reducible to $A$.


Homoiconic languages which are not Turing complete Does there exist a programming language which is homoiconic (in the sense that any code can be represented as a data structure, can be altered, and can be run after being altered) but not Turing complete?

For instance, one may avoid "for loops" by preventing data (which could represent code) from being copied.

You can turn every programming language $L$ into a homoiconic language $L_{hom}$ by adding a suitable representation of programs, such as ASTs (abstract syntax trees) or quasi-quoted programs, together with some operations that mediate between $L$ and the representation of $L$-syntax (e.g. evaluation or splicing instructions). The details of this depend on your precise rendering of homoiconicity (e.g. compile-time as in Template Haskell vs run-time as in the MetaML family of languages or Javascript).

One extreme example is the empty language $L^{\emptyset}$ that has no programs. Clearly its  homoiconic variant $L^{\emptyset}_{hom}$ isn't Turing complete. For more interesting examples, you can take any of the usual type theories such as the simply typed $\lambda$-calculus, System F or the Calculus of Constructions. Of course one would have to prove that the homoiconified version of such type-theories doesn't allow us to encode recursion somehow. I doubt that this has been done. Cody's comment below suggests that this might not be possible.


How many minimal $k$-cycles can you put in a graph? I wish to construct an unweighted, undirected graph on $n$ nodes that maximizes the number of minimal cycles of size $\ge k$.  What is known about this problem?  How many cycles can I squeeze in?

Additionally, how does the problem change if I require that my graph has $\ge m$ edges?

Clarification: I care purely about the existence of a many-cycled graph; it doesn't need to be efficiently constructable.

If $k$ is divisible by 2 we can take a clique on $n/2$ vertices and subdivide each edge once.
This graph will have ${n/2 \choose k/2} \cdot (k/2-1)!/2$ cycles of length $k$.

Hence the total number of cycles is $\frac{1}{2} \sum_{i=k/2}^{i=n/2} {n/2 \choose i} \cdot (i-1)!$


Reducing P vs. NP to SAT The following question uses ideas from cryptography applied to complexity theory. That said, it is a purely complexity-theoretic question, and no crypto knowledge whatsoever is required to answer it.

I deliberately write this question very informally. Lacking details, it is possibly stated a bit incorrectly. Please feel free to point out the corrections in your answers.

In the following papaper:
Nonmalleable Cryptography, Danny Dolev, Cynthia Dwork, and Moni Naor, SIAM Rev. 45, 727 (2003), DOI:10.1137/S0036144503429856,
the authors write:

  Suppose researcher A has obtained a proof that P ≠ NP and wishes to communicate this fact to professor B. Suppose that, to protect herself, A proves her claim to B in a zero-knowledge fashion...

There are several standard NP-complete problems, like satisfiability (SAT), Graph-Hamiltonicity, and Graph-3-Colorability (G3C), for which zero-knowledge proofs exist. The standard way of proving any NP-theorem is to first reduce it to an instance of the aforementioned NP-complete problems, and then conduct the zero-knowledge proof.

This question pertains to such reduction. Assume that the P vs. NP is settled in any of the following ways:

P = NP
P ≠ NP
P vs. NP is independent of the standard axiomatic set theory.

Let σ denote the proof. Then, P vs. NP is in an NP language (since there exists a short proof for it). The reduction from the theorem (say, P ≠ NP) to the NP-complete problem (say SAT) is independent of σ. That is:

There exists a formula ϕ which is satisfiable if and only if P ≠ NP.

This is well beyond my imagination! It seems that, even if we are given the proof σ, it is unlikely that we can construct such formula ϕ.

  Could anyone shed some light on this?

In addition, let L be an NP language in which P vs. NP lies. The language is consists of infinitely many theorems like P vs. NP, of arbitrary sizes.

  What is a candidate for L?
  Can L be NP-complete?

The way to view testing a math statement (e.g., a resolution of P vs NP) as a question of the form "is formula .. satisfiable" is the following:

Fix some axiom system.
Given a string of length n, whether the string is a proof for the math statement in the axiom system, is something one can define in a straightforward manner:
the string should consist of propositions. Each proposition should either be an axiom, or should follow from the previous propositions by one of the inference rules.

It's not a problem to define a Boolean formula that verifies all this.
All you should know is the length n of the proof!


Common solutions to 3SAT and 2SAT models comprised of the same variables I have a problem which is a combination of 3SAT & 2SAT instances.
Consider $L$ is a set of variables $(x_1 ... x_n)$. $S_3(L)$ is a 3-SAT instance and $S_2(L)$ is a 2SAT instance, both made of variables in L.
The actual boolean formula to solve is $B = S_3(L) \wedge S_2(L)$. So the solution for B is an intersection of the solution sets of $S_3(L)$ and $S_2(L)$.
Both $S_3$ and $S_2$ can be solved separately, and then we can select a common solution to solve B. I was wondering if I can use the 2SAT solution to more efficiently solve the 3SAT instance, for e.g. can I use the implication graph from the solution of the 2SAT instance to guide the search for solution to the 3SAT instance?
I am aware we build an implication graph when solving a 3SAT instance through DPLL. So can we use an existing graph to guide the DPLL solver?
Edited to better (hopefully) specify the problem

No, in general you cannot.  If $S_2(L) = (x_1 \lor \neg x_1)$, say, then the implication graph for $S_2(L)$ gives you no information on the solutions to $S_3(L)$ or $B$.
If you want to know how to solve it in practice, throw $B$ into a SAT solver.  No need to distinguish between the two types of clauses: SAT solvers already do everything there is to do.


Analytic Number theory in TCS Are there any applications of analytic number theory in TCS?

Codes/Lattices are certain combinatorial objects that are commonly used within TCS. A basic question for both of them is finding "short" codewords/lattice points, known as the Minimum Distance problem/Shortest Vector problem (MDP/SVP).

Both have been known to be NP-hard under randomized reductions for 20+ years. Roughly 10 years ago, the NP hardness proof for MDP was derandomized using some Analytic Number Theory (Weil's Character Sum bound).
SVP has still not been derandomized, but can be derandomized if the following result in analytic number theory is proven:

  For any $\epsilon > 0$, there exists $c\in\mathbb{N}$ such that for all sufficiently large $n$, the interval $[n, n + n^\epsilon]$ contains a square-free integer with no prime factors larger than $\log^c(n)$

Details of both of the above are described in Micciancio's paper Locally Dense Codes.

It's worth mentioning that this "existence of smooth numbers in short intervals" question is known within analytic number theory. For example, section 1.2 of Smooth numbers: computational number theory and beyond mentions that a slight relaxation of the problem (no prime factors larger than $n^\epsilon$) implies Vinogradov's conjecture, a problem in analytic number theory with no progress in 40 years.
There are definitely recent publications on this problem (say this), but I am not an expert, and can't say what the limits of current techniques are.


Is subtractive dithering the optimal algorithm for sending a real number using one bit? Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner.
We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,1/2]$ that they can use for choosing $X$ and estimating $x$.
Subtractive dithering is an algorithm that sends
$$X =
\begin{cases}
1 & \mbox{if $x+h\ge 1/2$}\\
0 & \mbox{otherwise}
\end{cases}.
$$
In turn, the subtractive receiver estimated $x$ as $\widehat x=X-h$.
It is possible to show that $\widehat x\sim U[x-1/2,x+1/2]$, and thus $\mbox{Var}[\widehat x]=1/12$.

Is there an unbiased algorithm (i.e., with $\mathbb E[\widehat x]=x$) that uses a single bit and has a variance lower than $1/12$ for all $x\in[0,1]$?

Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$.
We can at least prove that if $x$ is chosen uniformly from $[0,1]$, then the average variance must be at least $\pi^2/64 - 1/12$. There is a dithering algorithm that achieves this average-case variance, as follows. We interpret the shared randomness as a uniformly random point $(s,t)$ from the disk with radius $1/2$ and center $(1/2,0)$. The sender sends a $1$ if $x > s$ and a $0$ otherwise, while the receiver takes $\hat{x} = 1/2 + \frac{\pi}{8}\sqrt{s/(1-s)}$ if they receive a $1$, and $\hat{x} = 1/2 - \frac{\pi}{8}\sqrt{(1-s)/s}$ if they receive a $0$. To see that this is unbiased, note that $s$ has probability density function $\frac{8}{\pi}\sqrt{s(1-s)}$, so the expected value of $\hat{x}$ is
$$\int_0^x \Big(1/2 + \frac{\pi}{8}\sqrt{s/(1-s)}\Big)\frac{8}{\pi}\sqrt{s(1-s)}\ ds + \int_x^1 \Big(1/2 - \frac{\pi}{8}\sqrt{(1-s)/s}\Big)\frac{8}{\pi}\sqrt{s(1-s)}\ ds\\
= \int_0^1 \frac{4}{\pi}\sqrt{s(1-s)} + s\ ds - \int_x^1 1\ ds
= x.$$
To see that this is optimal for the average-case variance, let's first make a framework to describe the most general possible algorithm. For every possible value of the shared randomness $h$, the receiver will estimate $\hat{x}$ as one value $a(h)$ if they receive a $0$ bit, and will estimate $\hat{x}$ as a different value $b(h)$ if they receive a $1$ bit. We may as well assume that $a(h) \le b(h)$ for all $h$.
On the sender's side, imagine that the functions $a, b$ are fixed and $x$ is known, but that the sender hasn't yet peeked at the randomness $h$. The sender has to divide the possible values of $h$ into disjoint sets $A(x)$ and $B(x)$, with the plan of sending a $0$ bit if $h \in A(x)$ and sending a $1$ bit if $h \in B(x)$, subject to the constraint
$\mathbb{E}_h[a(h)\cdot\mathbf{1}_{h \in A(x)} + b(h)\cdot\mathbf{1}_{h \in B(x)}] = x$,
such that the variance of the random variable $a(h)\cdot\mathbf{1}_{h \in A(x)} + b(h)\cdot\mathbf{1}_{h \in B(x)}$ is minimized. Since the mean is fixed, minimizing the variance is equivalent to minimizing the second moment
$\mathbb{E}_h[a(h)^2\cdot\mathbf{1}_{h \in A(x)} + b(h)^2\cdot\mathbf{1}_{h \in B(x)}]$.
Since $\frac{b^2 - a^2}{b - a} = a+b$, and since we assumed that $a(h) \le b(h)$ for all $h$, the optimal strategy for the sender is to greedily set
$A(x) = \{h \mid a(h) + b(h) > t(x)\}, B(x) = \{h \mid a(h) + b(h) < t(x)\}$
for some threshold $t(x)$ which is chosen to satisfy the constraint on the mean:
$\mathbb{E}_h[a(h)\cdot\mathbf{1}_{a(h) + b(h) > t(x)} + b(h)\cdot\mathbf{1}_{a(h) + b(h) < t(x)}] = x.$
(If $a(h) + b(h) = t(x)$ with positive probability, then we divide the set of $h$s with $a(h) + b(h) = t(x)$ in any way we like to make the constraint on the mean work out.)
By rearranging the internals of the algorithm, we may now assume that $a(h) + b(h)$ is an increasing function of the random variable $h$, so the sender's strategy can be expressed as: send $0$ if $x < s(h)$ and send $1$ if $x > s(h)$, where $s$ is another threshold function, which satisfies
$\mathbb{E}_h[a(h)\cdot \mathbf{1}_{x < s(h)} + b(h)\cdot \mathbf{1}_{x > s(h)}] = x$.
From this, we can deduce that
$\mathbb{E}_h[a(h)s(h)^n + b(h)(1-s(h)^n)] = \mathbb{E}_{x,h}[a(h)\cdot nx^{n-1}\mathbf{1}_{x < s(h)} + b(h)\cdot nx^{n-1} \mathbf{1}_{x > s(h)}] = \mathbb{E}_x[nx^n] = \frac{n}{n+1}$
for every $n$, and that $b(h) - a(h) = s'(h)$.
Using the above identities, we can check that the expected variance is
$$\mathbb{E}_{x,h}[a(h)^2\cdot \mathbf{1}_{x < s(h)} + b(h)^2\cdot \mathbf{1}_{x > s(h)} - x^2]\\
= \mathbb{E}_{h}[a(h)^2s(h) + b(h)^2(1-s(h)) - 1/3]\\
= \mathbb{E}_h[(a(h)s(h) + b(h)(1-s(h)) - 1/2)^2 + (b(h) - a(h))^2s(h)(1-s(h)) - 1/12]\\
\ge \mathbb{E}_h[(b(h) - a(h))^2s(h)(1-s(h)) - 1/12].$$
By Cauchy-Schwarz, we have
$$\mathbb{E}_h[(b(h) - a(h))^2s(h)(1-s(h))]\\
\ge \mathbb{E}_h[(b(h) - a(h))\sqrt{s(h)(1-s(h))}]^2\\
= \mathbb{E}_h[s'(h)\sqrt{s(h)(1-s(h))}]^2\\
= \Big(\int_0^1 \sqrt{s\cdot (1-s)}\ ds\Big)^2 = \frac{\pi^2}{64},$$
which finishes the proof.
Edit: We can actually combine the disk-based example algorithm above (with the least possible average variance) and the subtractive dithering algorithm to create a dithering algorithm which has variance strictly less than $1/12$ for every $x$. The main idea is that the set of functions
$x \mapsto \operatorname{Var}[\hat{x}]$
coming from unbiased dithering algorithms is a convex set: given any pair of dithering algorithms, we can use shared randomness to randomly choose between them. Our plan is to first perturb the subtractive dithering algorithm in a way which keeps its average variance (for $x$ uniformly in $[0,1]$) approximately the same but which makes the variance lower for $x$ closer to $0$ and $1$ and higher for $x$ close to $1/2$, and then to take a weighted combination of this perturbed subtractive dithering algorithm with the disk-based example algorithm described above.
To perturb the subtractive dithering algorithm, we will stick with the choice of threshold $s(h) = h$, but we will perturb the functions $a(h), b(h)$. The perturbed functions will be given by
$$a(h) = h - 1/2 + \delta'(h)\\ b(h) = h + 1/2 + \delta'(h)$$
for some small function $\delta(h)$ - as long as $\delta(1) - \delta(0) = \mathbb{E}_h[\delta'(h)] = 0$, this perturbed algorithm will be unbiased. The variance of the perturbed subtractive dithering algorithm is then given by
$$\operatorname{Var}[\hat{x}] = \mathbb{E}_h[a(h)^2\cdot \mathbf{1}_{x < h} + b(h)^2\cdot \mathbf{1}_{x > h} - x^2]\\
= \tfrac{1}{12} + \mathbb{E}_h[(2h-1)\delta'(h)\cdot \mathbf{1}_{x < h} + (2h+1)\delta'(h)\cdot\mathbf{1}_{x > h} + \delta'(h)^2]\\
= \tfrac{1}{12} + 2\delta(x) - 2\int_0^1 \delta(h)\ dh + \int_0^1 \delta'(h)^2\ dh.$$
As you can see, the average value of $\operatorname{Var}[\hat{x}]$ increases by only $\int_0^1 \delta'(h)^2\ dh$, so by taking $\delta(x)$ a sufficiently small multiple of the difference of the two variance functions for the two algorithms in question, we get the perturbation we need. (While the resulting combination of the perturbed dithering algorithm and the disk-based algorithm outperforms subtractive dithering for all $x$, it is almost certainly not optimal, so I won't work out the gory details.)


Which results make quantum space interesting? Time-bounded quantum computation is obviously very interesting. What about space-bounded quantum computation?

I know many interesting results for quantum computation with sublogarithmic space bounds and various kind of quantum automata models.

On the other hand, it was shown that unbounded-error probabilistic and quantum space are equivalent for any space constructable $ s(n) \in \Omega(\log(n)) $ (Watrous, 1999 and 2003).

I wonder whether there are some specific results making quantum space interesting (by excluding sublogarithmic-space and automata models).

(I am aware of this entry: Quantum analogues of SPACE complexity classes.)

I think Amnon Ta-Shma's new result is a good answer to my own question.

Amnon Ta-Shma: Inverting well conditioned matrices in quantum logspace. STOC 2013: 881-890. (copy from author's website)

  ...  We show that the inverse of a well conditioned matrix can be approximated in quantum logspace with intermediate measurements. This should be compared with the best known classical algorithm for the problem that requires $\Omega(\log^2 n)$ space. We also show how to approximate the spectrum of a normal matrix, or the singular values of an arbitrary matrix, with $\epsilon$ additive accuracy, and how to approximate the singular value decomposition (SVD) of a matrix whose singular values are well separated. ...


Maximum imbalance in a graph? Let $G$ be a connected graph $G = (V,E)$ with nodes $V = 1 \dots n$ and edges $E$. Let $w_i$ denote the (integer) weight of graph $G$, with $\sum_i w_i = m$ the total weight in the graph. The average weight per node then is $\bar w = m/n$. Let $e_i = w_i - \bar w$ denote the deviation of node $i$ from the mean. We call $|e_i|$ the imbalance of node $i$.

Suppose that the weight between any two adjacent nodes can differ by at most $1$, i.e.,
$$ w_i - w_j \le 1\; \forall (i,j) \in E.$$

Question: What is the largest possible imbalance the network can have, in terms of $n$ and $m$? To be more precise, picture the vector $\vec{e} = (e_1, \dots, e_n)$. I'd be equally content with results concerning $||\vec{e}||_1$ or $||\vec{e}||_2$.

For $||\vec{e}||_\infty$, a simple bound in terms of the graph diameter can be found: Since all $e_i$ must sum to zero, if there is a large positive $e_i$, there must somewhere be a negative $e_j$. Hence their difference $|e_i - e_j|$ is at least $|e_i|$, but this difference can be at most the shortest distance between nodes $i$ and $j$, which in turn can be at most the graph diameter.

I'm interested in stronger bounds, preferably for the $1$- or $2$-norm. I suppose it should involve some spectral graph theory to reflect the connectivity of the graph. I tried expressing it as a max-flow problem, to no avail.

EDIT: More explanation.
I'm interested in the $1$- or $2$-norm as they more accurately reflect the total imbalance. A trivial relation would be obtained from $||\vec{e}||_1 \leq n|||\vec{e}||_\infty$, and $||\vec{e}||_2 \leq \sqrt{n}||\vec{e}||_\infty$. I expect, however, that due to the connectedness of the graph and my constraint in the difference of loads between adjacent nodes, that the $1$- and $2$-norms should be much smaller.

Example: Hypercube of Dimension d, with $n = 2^d$. It has diameter $d = \log_2(n)$. The maximum imbalance is then at most $d$. This suggest as an upper bound for the $1$-norm $nd = n\log_2(n)$. So far, I have been unable to construct a situation where this is actually obtained, the best I can do is something along the lines of $||\vec{e}||_1 = n/2$, where I embed a cycle into the Hypercube and have the nodes have imbalances $0$, $1$, $0$, $-1$ etc. So, here the bound is off by a factor of $\log(n)$, which I consider already too much, as I'm looking for (asymptotically) tight bounds.

Since $|e_i|$ is bounded by the diameter $d$, the $\ell_1$ norm is going to be trivially bounded by $nd$, likewise for the $\ell_2$ norm, except by $\sqrt{n}d$ (in fact the $\ell_p$ norm is bounded by $n^{1/p}d$).

The $\ell_1$ case turns out to be surprisingly easy to analyze.

For a path, it's easy to see that $\|\vec e\|_1$ is $O(n^2)$, so you can't do any better than $O(nd)$.

For a complete $k$-ary tree, you can divide it in half at the root, setting $w_{\text{root}} = 0$, ascending one side and descending the other until the leaves have $|e_i| = |w_i| = \log_k n$, producing $O(n\log_k n) = O(nd)$ again.

For a clique it doesn't really matter how you distribute the weights, since they'll all be within $1$ of each other, and that will yield $O(n) = O(nd)$ again.

When you realize that what we're talking about here is a function $e : \mathbb{Z} \to [-d/2,d/2] \subset \mathbb{R}$, and then we're taking its $\ell_1$ norm, as long as you can arbitrarily distribute weights $e_i \in [-d/2,d/2]$ evenly across the range, the bound will be $O(nd)$.

The only way to change this is to play games with the mass. For instance, if you have several giant cliques at points that are necessarily balanced, like a giant clique with two paths of equal length jutting out of it, then you can count on a bound of only (for example) $O(d^2)$.

This may be true for expanders to some degree as well, but I'm not sure. I could imagine a case where you set $w_1 = 0$ in a regular graph and then let the values increase subsequently from every hop. It seems likely that the mean could possibly have the most mass, but I don't know if it would be enough to affect the bound.

I think that you could reason similarly about $\ell_2$.

EDIT:

In the comments we figured out a (loose) $\ell_2$ bound of $O(|E|/\lambda_2(L))$ using the constraints of the problem and some basic spectral graph theory.


Relation between vertices, cells, and vertex-cell-incidences in 3D subdivisions Consider a planar subdivision, with F faces, V vertices, E edges, and I face-vertex incidences. For simplicity, assume a "non-degenerate" situation in which each vertex occurs on the boundary cycle of each face only once. Then I is the sum over all faces of the number of vertices per face, or equivalently, the sum over all vertices of the number of incident faces. We have I = 2E, and therefore Euler's formula gives us:

F + V = I/2 + 2.

All I actually care about is:

F + V < I/2.

Does this also hold in for three-dimensional subdivisions, when F is the number of three-dimensional cells of the subdivision, and V and I are as defined above?

Note that I am looking for an inequality that is independent of the number of one- and two-dimensional faces in the subdivision. When the cells are convex I can get something using quite a bit of geometry, but it seems to me that the requirement that the cells be convex is an artifact of my proof technique, and something more general should be possible and/or known. Does anybody have an idea where to look for the answer?

Doesn't $F + V \le 2I$ hold trivially for every system of incidences between things called vertices and things called faces? Under some reasonable assumptions, every vertex has at least one incidence, and every face has at least one incidence. If you add those incidences together you count each incidence at most twice.

To get from there to your desired $F + V \le I/2 + O(1)$ you'd need to use some actual geometry show that the vertices and faces each have at least four incidences on average. This is obvious for convex subdivisions but maybe needs more assumptions in general (e.g. consider a system of bubbles in 3d space, linked one to the next in a chain: each face has no vertex-face incidences, because there are no vertices).


Complexity of finding 2 vertex-disjoint $(|V|/2)$-cycles in cubic graphs? I posted this on mathoverflow but with no luck:

Finding a connected 2-factor is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding two vertex-disjoint $(|V|/2)$-cycles in cubic graphs.

I suspect that it is $NP$-complete but I'm not able to find a reference. Also, What is the complexity of finding two vertex-disjoint $(|V|/2)$-cycles with equal cardinality in planar cubic bipartite graphs? Is it $NP$-complete?

Providing references is highly appreciated. $NP$-completeness refers to the decision version of the problem.

I assume, as stated in the comments, that the problem is to find a 2-factor with two cycles of length $|V|/2$ each in a cubic graph.
This problem is NP-complete:

1) HC in cubic graphs is NP-complete.

2) The following problem HC' is also NP-complete: Given a cubic graph $G$ and an edge $e$
in $G$, is there a Hamiltonian cycle through $e$. We can reduce HC to it: Given a graph $G$, replace one arbitrary vertex (left hand side) by a triangle with another vertex in it (right hand side):

Call this new graph $G'$.
$G'$ is Hamiltonian iff $G$ is. Furthermore, if $G'$ is Hamiltonian, then for any red edge, there is a Hamiltonian cycle that contains this red edge. (Without the vertex in the middle, every Hamiltonian cycle contains two green edges and any green edge can then be replaced by two red ones.) The reduction from HC to HC' maps a cubic graph $G$ to $G'$ together with any red ege.

3) Finally, we reduce HC' to the problem of the question. Given an instance
$(G,e)$, we create two copies of $G$, subdivide $e$ in each copy and connected the two vertices that subdivide the two copies by a new edge $f$. This edge $f$ is a bridge in the new graph. If $G$ has a Hamiltonian cycle through $e$, then the new graph has a 2-factor consisting of two cycles of the same size.
Conversely, if the new graph has such a 2-factor, then it cannot use $f$. Therefore, it splits into two Hamiltonian cycles of the two copies. Since in these copies, the vertex subdividing $e$ has degree two, we get a Hamiltonian cycle of $G$ that contains $e$.


Finding a maximum acyclic sub-tournament given two acyclic sub-tournaments Given a tournament $T$ where $S_1$ and $S_2$ be two acyclic sub-tournament of $T$.

  Is the following problem NP-Complete: Finding a maximum acyclic sub-tournament $S$, which is subset of $S_1 \cup S_2$?

Can the given problem be solved in polynomial time? If not please state the NP-Completeness.

By keeping $S_1$ as such and removing only the vertices from $S_2$, an $S'$ maximal acyclic tournament belonging to $S_1 \cup S_2$ can be obtained in polynomial time. The solution $S'$ thus obtained may not be the same as the maximum acyclic sub-tournament $S$.

The polynomial time algorithm is based on compression step in iterative compression algorithm for feedback vertex set in tournament from the paper

  Fixed-parameter tractability results for feedback set problems in tournaments, Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, Anke Truss, Journal of Discrete Algorithms 8 (2010) 76–86.

If finding a maximal acyclic sub-tournament $S$ is NP-complete then I have no choice except to find $S'$, so I wish to know whether finding $S$ is NP-complete or not.

consider the reduction from vertex cover to the above problem.

consider graph $G(V,E)$ with vertex V={1,2,..n}

let T be the tournament with vertices $x_{i},y_{i},z_{i}$ for vertex i=1,2...n

construct the tournament with edges in order of  $x_{1},y_{1},z_{1},x_{2},y_{2},z_{2}...x_{n},y_{n},z_{n}$.if there exist a edge(i,j) then $z_{j},x_{i}$.  $x_{i},y_{i}$ belongs to $T_{1}$ for i=1,2...n and $z_{i}$ belongs to $T_{2}$ for i=1,2...n. It is clear that $T_{1}$ and $T_{2}$ are acyclic.

Example for the construction

consider the graph G(V,E) with vertex set {1,2,3} and edges be (1,2)(2,3)
construction as follows

Tournament has vertices $x_{1},y{1},z{1},x_{2},y_{2},z_{2},x_{3},y_{3},z_{3}$
with construction as follows

Step1
$x_{1}$ has directed edges to all vertices.

$y_{1}$ has directed edges to all vertices except $x_{1}$

$z_{1}$ has directed edges to all vertices except $x_{1},y_{1}$

$x_{1}$ has directed edges to all vertices except $x_{1},y_{1},z_{1}$

and repeat the process till all edges for the tournament constructed

step 2: (1,2) has a edge so swap the edge direction from $(x_{1},y_{2})$ to $(y_{2},x_{1})$ similarly for (1,3)
claim: G has a vertex cover of size k only if T has feedback vertex set of size k

one case is clear, if G has a vertex cover of size k then surely T has a fvs of size k

other way is, if there is edge (i,j) where $i<j$ if both $x_{i},z_{j}$ is not picked into the solution then we are forced to pick all vertices $y_{i},z_{i},x_{k},y_{k},z_{k},x_{j},y_{j}$ where for all k such that $i<k<j$. so picking $x_{i},z_{j}$ will result in better solution.hence proved

please see and verify.


Upper bound on Chaitin's constant for lambda calculus and SKI combinatory logic I'd like to have proof that Chaitin's constant for lambda calculus and/or SKI combinatory logic is pretty small. I've found some approximations (accurate to about 63 binary digits) for truing machines and as expected they were low, below 1% in fact. I can't find any bounds for lambda calculus or combinatory logic. I'd really just like to show that it is less than 10% to 20%. Does anyone know of such a paper or how to get such an awnser?

I also found this but it doesn't have a reference for how it got that answer. If correct it would show that the probability is between 0.125 and 0.0625 which is great for me! Does anyone have a citation for this?

You probably want to look at David et al's paper, Asymptotically Almost All λ-terms are Strongly Normalizing:

We present a quantitative analysis of various (syntactic and behavioral) properties of random λ-terms. Our main results show that asymptotically, almost all terms are strongly normalizing and that any fixed closed term almost never appears in a random term.
Surprisingly, in combinatory logic (the translation of the λ-calculus into combinators), the result is exactly opposite. We show that almost all terms are not strongly normalizing. This is due to the fact that any fixed combinator almost always appears in a random combinator.

You should be able to cook up a bound from looking at the details of their proof.


Is there a notion of "sequential" idempotence? TL;DR: I have a definition, and I'm wondering if it already has a name or has been studied.

Suppose we have a sequence of operations (or if we want to be mathematical, functions whose domains and ranges are all the same) $f_1, f_2, ..., f_n$.

I'll call the sequence idempotent if the composition $f_1f_2...f_n$ is idempotent.

But I call the sequence strongly idempotent if any initial subset of the operations $f_1...f_k$ is idempotent for all $1 \leq k \leq n$.

For example, if we take the domain of integers, set $f_1(x) = x + 1$ and $f_2(x) = 0$, then the sequence $(f_1, f_2)$ is idempotent but not strongly idempotent.

My question is, does this definition/idea already have a name? Are there any known useful properties of strong idempotency, or is it known to be useful in any particular areas?

Your question would probably fit better on MathsStackExchange, but here is an answer.

I don't think there is any specific name for your definition. Since any semigroup is isomorphic to a transformation semigroup, your question is about finitely generated semigroups that are quotients of the semigroup $S_n$ with presentation
$$
\langle a_1, \ldots, a_n \mid a_1^2 = a_1, (a_1a_2)^2 = a_1a_2, \ldots, (a_1 \dotsm a_n)^2 = a_1 \dotsm a_n \rangle
$$
It turns out that $S_n$ is infinite for $n > 1$, but I don't know whether it has been studied in the literature.


Enumerating topological sorts of a vertex-labeled DAG Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a topological sort of $G$ is a bijection $\sigma$ from $\{1, \ldots, n\}$ to $V$ (i.e., an ordering of $V$ in a sequence) such that whenever $(v, v') \in E$ then $\sigma^{-1}(v) < \sigma^{-1}(v')$ (i.e., if there is an edge from $v$ to $v'$ then $v$ occurs before $v'$ in the sequence). The label of $\sigma$ is the word $\sigma(1) \cdots \sigma(n)$ in $L^n$.

Given $(G, \lambda)$, I would like to enumerate the labels of topological sorts of $G$ efficiently. What is the complexity of enumerating the labels of topological sorts? Of course, as there can be exponentially many, I want to study complexity as a function of the size of the output, or in terms of delay. In particular, can enumeration be performed with polynomial delay? (or even constant delay?)

In the case where all vertices of $G$ carry distinct labels (or, equivalently, the vertices are $\{1, \ldots, n\}$ labeled by themselves), I know that labels can be enumerated in constant amortized time, by this result on enumerating linear extensions of posets (which is the same thing as enumerating topological sorts of a DAG). However, when vertices are labeled arbitrarily, it could be the case that a very large number of topological sorts have the same label, so you can't just enumerate topological sorts of $G$ and compute their labels to get an efficient way to enumerate the labels. In poset terminology, the labeled DAG $(G, \lambda)$ can be seen as a labeled poset, and I couldn't find enumeration results about those.

I already know the hardness of some related problems thanks to answers to my other questions here. In particular, I know that finding the lexicographically minimal label is NP-hard. I also know that deciding whether a given label can be achieved by some topological sort is NP-hard (from the hardness of this problem: given a candidate label sequence $s$, ask for a topological sort of $G$ where each vertex must occur at a position where the right label occurs in $s$). However, I don't think that any of this implies hardness for enumeration, as you may enumerate in any order you like (not necessarily lexicographic), and an enumeration algorithm can't be used to decide efficiently whether a label is achievable, even with constant delay (as there may be exponentially many sequences to enumerate first).

Note that, it is obviously easy to enumerate a first label $s$ (just take any topological sort). To enumerate another label than $s$, you can proceed by imposing that some element $v$ of $V$ gets enumerated at some position $i \in \{1, \ldots, n\}$ where $s_i \neq \lambda(v)$: try out every $v$ and $i$, and check if $G$ has a topological sort where $v$ is at position $i$, which can clearly be done in PTIME. But as you output more and more labels, I'm not sure of how to generalize this approach.

One of the simplest way to compute topological ordering is performing a Depth First Search on the given DAG. Different topological orderings can be generated by exploiting the flexibility of choosing the next vertex $v$ to be traversed from the unvisited neighbours of the current vertex $u$.
Since, it is a recursive procedure enumerating all possible traversals (and hence topological orders) would be simple, by choosing different orders in which unvisited neighbours of $u$ are traversed.

Now, in order to limit repeating the same traversal because of similar labels, one can compare the unvisited neighbours $v_1,v_2,...,v_k$ of $u$ having similar labels. Consider two vertices $v_i$ and $v_j$ that have the same unvisited neighbours when the traversal reaches $u$. Surely choosing either of them first would generate the same DFS tree and hence any one of them can be avoided.

Now, comparing the neighbours of all $v_1,...,v_k$ would lead to an overhead of $O(n^2)$ on the total time, but can be performed more efficiently in $\tilde{O}(n)$ by using appropriate data structures.


Heapsort:Heaps =~ Quicksort:BSTs =~ Mergesort:___? Please excuse the terseness of the title, I may have sacrificed clarity on the altar of conciseness.

One can see that inserting elements of an array into a binary search tree and reading them back out requires (on insertion) the same comparisons as running Quicksort on that array. The sequence of pivots that Quicksort uses is the sequence of insertions into the binary search tree.

This is also trivially true for Heapsort and heaps, since Heapsort is literally doing such a series of insertions and then reading the elements back out.

Does there exist an analog of this in the case of, say, Mergesort? Is there a deeper connection here, or is it an interesting coincidence between data structures and sorting algorithms?

The Bentley-Saxe logarithmic method can sort a set in $O(n \lg n)$ time by merging sorted lists of equal size, much like merge sort.


Finding the penumbra of a Constraint Satisfaction Problem The following question has come up a number of times when testing the security of a system or model.

Motivation: Software security flaws often come not from bugs due to valid inputs, but bugs resulting from invalid inputs that are sufficiently close to valid inputs to get past many of the straightforward validity checks. The classic example is of course buffer overflows, where the input is reasonable, except that it is too large. Compilers and other tools can help address these problems by modifying the layout of the stack and heap and by other obfuscation techniques. An alternative is to remove the problems from the source code itself. One technique called fuzzing bombards the program with inputs are close to expected inputs, but are in some places unreasonable (large values for integer or string fields). I would like to understand fuzzing (as one example) from a more formal perspective.

Assume that the space of valid inputs is described by constraints $\Phi$. Let $M$ be the set of solutions of such constraints, namely  $M=\lbrace m\in\mathcal{M}~|~m\models\Phi\rbrace$, where $\mathcal{M}$ is the space of possible inputs.

I'm looking for work describing the following notions:

The penumbra of $M$ is a set $M'\subseteq \mathcal{M}$ such that for each
$m\in M'$ $m\not\models\Phi$ and in some sense the elements of $M'$ are close to the elements of $M$. One can think of the penumbra as the almost solutions. Of course, this notion will not be unique.
Ways of relaxing the constraints $\Phi$ to $\Phi'$ such that firstly $\Phi\Rightarrow\Phi'$ and $\Phi'\land\neg\Phi$ is, in a sense, the syntactic penumbra of $\Phi$.

"Penumbra" is a word I selected to describe the concept. It may well be called something else.

I found inspiration in
mathematical morphology, hence my visual metaphor, but the two worlds are parsecs apart. Is there any useful work there? Or perhaps in the world of rough sets?

Can anyone shed light?

Much of the attention paid to optimization variants of the constraint satisfaction problem (CSP) has focused on satisfying some number of constraints (MAX-CSP), or in the Boolean case on picking the solution which assigns as many variables as possible the value 1 (MAX-ONES, there is also MIN-ONES).

Instead, you are asking about a variant that could be called MAXIMUM PARTIAL CSP.  This was studied at least as far back as the late 1960s, but I'm not aware of it having an established name.  It is a natural problem, and it would be good to see more work investigating it.  Thank you for providing another potential application for this problem!

Ambler, A. P. and Barrow, H. G. and Brown, C. M. and Burstall, R. M. and Popplestone, R. J., A versatile system for computer-controlled assembly, Artificial Intelligence 6 129–156, 1975. doi: 10.1016/0004-3702(75)90006-5

A set of variable-value assignments is called a partial assignment.  One can write a variable-value assignment as a (variable, value) tuple.  Partial assignments are then simply functions from variables to values.  Props are partial assignments that don't violate any constraint.  Equivalently, a prop contains no partial assignment forbidden by some constraint (as a subset).

One way to express the optimization problem is as follows.

  MAXIMUM PARTIAL CSP:
  Input: CSP instance
  Output: prop $f$
  Criterion: maximize $|f|$

In an instance with $n$ variables, clearly a prop of cardinality $n$ will be a solution.  There may exist large props, with cardinality up to $n-1$, that are not contained in any solution.

In the terminology you propose, the set of props with maximum cardinality $k$ forms the penumbra, perhaps even with some additional leeway $d$ (so cardinality at least $k-d$).

The second part of your question also appears highly interesting, but I am not aware of any work related to it.

Footnote: The term prop is from my thesis; it is meant to convey the idea that such partial assignments are proper, and also that they support the set of solutions.  This is in contrast to a nogood, which is the accepted term to describe a partial assignment that cannot be extended to a solution.  The word "nogood" was introduced by Richard Stallman and Gerald Sussman in 1976, when RMS was still an AI researcher instead of software freedom activist.

Stallman, Richard M. and Sussman, Gerald Jay, Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis, MIT Artificial Intelligence Laboratory Memo No. 380, 1976. (PDF)


Minimal bandwidth required to synchronize two sets of values We consider two computers who possess two sets of fixed-size values (ie. $k$-bit numbers for some constant $k$), and we assume that the two sets have a large overlap (ie. a large proportion of the values are present on both hosts). We want to find an protocol to synchronize the two sets (ie. give to each host the knowledge of the values of the other hosts) in a way which minimizes the quantity of information transferred between the two hosts.

In particular, if we denote by $N_1$, $N_2$ the size of the sets and $K_1$ (resp. $K_2$) the number of values present only on computer 1 (resp. only on computer 2), the trivial algorithm where both computers exchange their sets is $O(N_1+N_2)$, and the trivial lower bound on the quantity of information to exchange is $O(K_1+K_2)$. Is it possible to reach this bound?

This appears to be known as the "set reconciliation" problem. The key paper appears to be Minsky & Trachtenberg, "Set Reconciliation With Nearly Optimal Communication Complexity", IEEE Transactions on Information Theory (2003). Also, here is some subsequent work on this problem by the same authors: "Practical Set Reconciliation".