Reducing factoring prime products to factoring integer products (in average-case) My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring.

Assuming the problem of

  FACTORING:[Given $N = PQ$ for random primes $P, Q < 2^n$, find $P$, $Q$.]

cannot be solved in polynomial time with nonnegligible probability, the function

  PRIME-MULT: [Given bit string $x$ as input, use $x$ as a seed to generate two random primes $P$ and $Q$ (where the lengths of $P$, $Q$ are only polynomially smaller than the length of $x$); then output $PQ$.]

can be shown to be one-way.

Another candidate one-way function is

  INTEGER-MULT: [Given random integers $A, B < 2^n$ as input, output $A B$.]

INTEGER-MULT has the advantage that it is easier to define compared to PRIME-MULT. (Notice in particular that in PRIME-MULT, there is a chance (though fortunately negligible) that the seed $x$ fails to generate $P, Q$ that are prime.)

At least in two different places (Arora-Barak, Computational Complexity, page 177, footnote 2) and (Vadhan's Introduction to Cryptography lecture notes) it is mentioned that INTEGER-MULT is one-way assuming average hardness of factoring. However, neither of these two gives the reason or a reference for this fact.

So the question is:

  How can we reduce in polynomial time factoring of $N = PQ$ with nonnegligible probability to inverting INTEGER-MULT with nonnegligible probability?

Here is a possible approach (that as we will see does NOT work!):
Given $N = PQ$, multiply $N$ by a much (though polynomially) longer random integer $A'$ to get $A = NA'$. The idea is that $A'$ is so large that it has lots of prime factors of size roughly equal to $P, Q$, so that $P, Q$ do not "stand out" among the prime factors of $A$. Then $A$ has approximately the distribution of a uniformly random integer at a given range (say $[0,2^n-1]$). Next choose integer $B$ randomly from the same range $[0,2^n-1]$.

Now if an inverter for INTEGER-MULT can, given $AB$, with some probability find $A', B' < 2^n$ such that $A'B' = AB$, the hope is that one of $A'$ or $B'$ contains $P$ as a factor and the other contains $Q$. If that was the case, we can find $P$ or $Q$ by taking gcd of $A'$ with $N = PQ$.

The problem is that the inverter may choose to separate the prime factors, for example, putting the small factors of $AB$ in $A'$ and the large ones in $B'$, so that $P$ and $Q$ end up both in $A'$ or both in $B'$.

Is there another approach that works?

This is not really an answer, yet it sheds some light on the difficulty of demonstrating such reductions.

The problem can be summarized as follows:
Let $\mathcal{A}$ be an algorithm which solves the INTEGER-MULT problem with non-negligible probability. Let this probability be at least $n^{-c}$, for some constant $c \in \mathbb{N}$ (when the size of input is $n$). Prove that there exists a PPT (probabilistic polynomial-time) algorithm $\mathcal{A}'$ which, uses $\mathcal{A}$ as subroutine, and solves an instance of the FACTORING problem of size $n$ with probability at least $n^{-d}$, for some constant $d \in \mathbb{N}$.

Consider an algorithm $\mathcal{A}^*$ which solves the INTEGER-MULT problem if and only if the input $N$ has the special from $N = PQR$, where $P$ and $Q$ are primes of size $n/4$ and $R$ is a prime of size $n/2$, and otherwise fails. Moreover, on input an integer $N$ of the above form, it outputs $PQ$ and $R$. We first show that $\mathcal{A}^*$ has a non-negligible probability of solving the INTEGER-MULT problem. To this end, it suffices to find the fraction of $n$-bit integers of the special form, as this fraction bounds the success probability of $\mathcal{A}^*$ from below.

By prime number theorem, the number of primes whose size is $k$-bits is:

$2^k / \ln(2^k) - 2^{k-1} / \ln(2^{k-1}) = \Theta(2^k / k)$

Therefore, the fraction of $n$-bit integers of the special form is:

$\frac{\Theta(2^{n/4} / (n/4))^2 \cdot \Theta(2^{n/2} / (n/2))}{2^{n-1}} = \Theta(n^{-3})$

which is non-negligible in $n$.

Therefore, one should be able to prove the existence of a PPT algorithm $\mathcal{A}'$ which, uses $\mathcal{A}^*$ as subroutine, and solves an instance of the FACTORING problem of size $n$ with probability at least $n^{-d}$, for some constant $d \in \mathbb{N}$.

IMHO, this seems a very difficult task, since $\mathcal{A}^*$ only (partially) decomposes integers of the special form, and there does not seem to be a way to use it to decompose integers of the form $PQ$.


Guidelines to reduce general TSP to Triangle TSP I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie:

$D(a, b) \leq D(a, c) + D(c, b)$

I am not sure how to attack this kind of problem, so any pointers / explanations regarding this would be helpful. Thank you.

Here is a simple reduction for the TSP problem to the metric TSP problem:

For the given TSP instance with $n$ cities, let $D(i,j) \geq 0$ denote the distance between $i$ and $j$. Now let $M = \max_{i,j} D(i,j)$. Define the metric TSP instance by the distances $D'(i,j) := D(i,j)+M$. To see that this gives a metric TSP instance, let $i,j,k$ be arbitrary. Then $D'(i,j) + D'(j,k) = D(i,j) + D(j,k) + 2M \geq 2M \geq D(i,k) + M = D'(i,k)$. Since any tour uses exactly $n$ edges, the transformation adds exactly $nM$ to any tour, which shows the correctness of the reduction.

Remark: We can of course also allow for negative distances in the original TSP instance if you prefer by changing the reduction slightly.


For a given algorithm with expected runtime M, does there exist (in theory) an algorithm with equivalent guaranteed runtime? Title pretty much explains the question. E.g.

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Should there in theory also be an algorithm with guaranteed runtime that is also linear?

Not looking for a response to this specific case necessarily, but more generally.

Thanks all.

No. See Chapter 2 of the book Randomized Algorithms by Motwani and Raghavan. They discuss a tree-evaluation problem for which:

any deterministic algorithm takes linear time;
there is a Las Vegas randomized algorithm with sublinear expected running time.


TSP heuristics for limited distance information this is my first question on Theoretical CS. :)

I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site.

Problem:

  I'm looking for TSP heuristics in the case of limited information about the edges, for example: I have $n$ nodes but can only ask for $~\sim4n$ distances. My graphs are metric and
  I can make an estimate in advance with the euclidean distance, which provides a lower bound, but those estimates might be very bad.

Question:

  So what are the TSP-Heuristika for those distance-matrices?

Thanks in advance.

There is no algorithm that runs in time $o(n^2)$ on an $n$-point metric space and returns a tour with weight within a constant factor of the minimum weight: see the argument in Section 9 of this paper by Indyk.

On the other hand, if you just want an approximation to the weight of the optimal tour, without actually getting a tour, then you can use this algorithm by Czumaj and Sohler. Their algorithm runs in time which is nearly linear in $n/\varepsilon^{O(1)}$ and returns a $1+\varepsilon$ approximation to the weight of minimum weight spanning tree. Since the minimum weight spanning tree is a factor 2 approximation to the minimum weight TSP tour, this gives a factor $2+\varepsilon$ approximation for TSP.

Of course these are worst-case bounds, but I find it implausible to be able to find a good tour by querying $o(n^2)$ edges unless you know more about your metric space. Metric spaces are very general objects and it's easy to hide information while still satisfying the triangle inequality.


minimal finite automata given in-words and out-words this seems an interesting FSM optimization problem; have not seen it studied, wondering if it has been and/ or looking for other insight.

  given: two finite sets of words $S_{in}$ and $S_{out}$. find the smallest FSM with language $L$ such that for each $x \in S_{in}$, $x \in L$ and for each $y \in S_{out}$, $y \notin L$.

in other words one is given finite lists of words that are in the language and not in the language. there is a simple algorithm of creating an FSM with the given (non)acceptance and then minimizing it, but is this also the smallest possible? it seems to come down some to the question of cycles in the FSM graph. the simple strategy will not have cycles, so could smaller FSMs with cycles exist? there is also the question of nondeterminism.

If your FSM is a DFA, then this is the Minimum Consistent DFA Problem, which is well known in the machine learning community. This problem is NP complete

Gold1978 - Complexity of Automaton Identification from Given Data.

The problem is also known to be hard to approximate within any polynomial factor. Indeed it is even hard to find an NFA whose number of states is an approximation of the number of states of a minimum consistent DFA.

Pitt-Warmuth-1993 - The minimum consistent DFA problem cannot be approximated within any polynomial.

There are many known heuristics and algorithms for tackling this problems. A well studied algorithm is due to Angluin.

Angluin-1987 - Learning regular sets from queries and counterexamples


Why is differential privacy defined over the exponential function? For adjacent database $D,D'$, a randomized algorithm $A$ is $\varepsilon$-differential private when the following satisfies

$$\frac{\Pr(A(D) \in S)}{\Pr(A(D') \in S)} \leq e^\varepsilon,$$ where $S$ is any range of A.

Why is the exponential function is used for the upper bounding?

Is that related to Chernoff's inequality? Since most of the textbooks that I have ever seen do not explain why the exponential is used, I have no idea about that.

This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties:

Composition: If $A(\cdot)$ is an $\varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(\cdot, a)$ is an $\varepsilon'$-DP algorithm, then the composed algorithm $A' \circ A$, defined by $A'\circ A(D) = A'(D, A(D))$, is $(\varepsilon + \varepsilon')$-DP.
Group Privacy: If $A$ is $\varepsilon$-DP, then it satisfies $k\varepsilon$-DP on pairs of data sets that differ in at most $k$ data points.

It may be more natural to define $\varepsilon$-DP with $(1+\varepsilon)$ in place of $e^\varepsilon$, but then the formulas above would be far less nice. There is no real connection with Chernoff bounds here.

Another reason is that this definition makes it more clear how the differential privacy definition is related to divergences between distributions. To see what I mean, let me define the privacy loss of an output $a$ of an algorithm $A$ (with respect to datasets $D$ and $D'$) as
$$
\ell_{D, D'}(a) = \log\left( \frac{\Pr[A(D) = a]}{\Pr[A(D') = a]}\right).
$$
Then, the expectation $\mathbb{E}[\ell_{D, D'}(A(D))]$ is simply the KL-divergence between $A(D)$ and $A(D')$. The differential privacy condition asks that this KL-divergence is bounded by $\varepsilon$, but in fact it asks much more: that the random variable $\ell_{D, D'}(A(D))$ is bounded by $\varepsilon$ everywhere in its support. There are also intermediate definitions which put bounds on moments of $\ell_{D, D'}(A(D))$, and correspond to bounding Renyi divergences between $A(D)$ and $A(D')$.


variant of Critical SAT The language Critical SAT is defined as the set of $CNF$ boolean formulas $f$ such that $f \in UNSAT$ but removing any  clause from $f$ makes it satisfiable. It is known that Critical SAT is $DP$-complete. I wonder about the following variant: given a $CNF$ formula $f$, is it the case that $f$ is in $UNSAT$ and that there exists some clause $c$ such that $f \setminus c \in SAT$ (instead of for all clauses, there exists a clause). Is this variant $DP$-complete as well?

It is clear that your language is in DP. In order to show that it is DP-hard, we will give a reduction from SAT-UNSAT to your language, which we can call CRIT-UNSAT. Given a pair of CNFs $(f,g)$, let $x,y$ be fresh variables, and let
$$
h = (f \lor \lnot x) \land (g \lor x) \land (g \lor y) \land \lnot x \land (x \lor \lnot y).
$$
Here $f \lor \lnot x$ means add $\lnot x$ to all clauses of $f$.

Suppose first that $f$ is satisfiable and $g$ is not satisfiable. Since $g$ is not satisfiable, $h$ is not satisfiable. Since $f$ is satisfiable, $h \setminus \lnot x$ is satisfiable. Thus $h$ is in CRIT-SAT.

Conversely, suppose that $h$ is in CRIT-SAT. Since $h$ is unsatisfiable, $g$ is unsatisfiable. For some clause $c$, $h \setminus c$ is satisfiable. If $c \in f \lor \lnot x$ then clearly $h \setminus c$ is still unsatisfiable. Similarly, if $c \in g \lor x$ then $h \setminus c$ is still unsatisfiable, due to $g \lor y$. If $c \in g \lor y$ or $c = x \lor \lnot y$ then $h \setminus c$ is still unsatisfiable, due to $g \lor x$.
Thus $c = \lnot x$, which means that $h|_{x=1}$ is satisfiable, that is, $f$ is satisfiable.


A mathematical (categorical) description of type classes A functional language can be viewed as a category where its objects are types and morphisms functions between them.

How do type classes fit in this model?

I assume we should only consider those implementations that satisfy the constraint that most type-classes have, but that are not expressed in Haskell. For example, we should only consider those implementations of Functor for which fmap id ≡ id and fmap f . fmap g ≡ fmap (f . g).

Or are there any other theoretical foundations for type classes (for example based on typed lambda calculi)?

How do type classes fit in this model?

The short answer is: they don't.

Whenever you introduce coercions, type classes, or other mechanisms for ad-hoc polymorphism into a language, the main design issue you face is coherence.

Basically, you need to ensure that typeclass resolution is deterministic, so that a well-typed program has a single interpretation. For example, if you could give multiple instances for the same type in the same scope, you could potentially write ambiguous programs like this:

class Blah a where
   blah : a -> String

instance Blah T where
   blah _ = "Hello"

instance Blah T where
   blah _ = "Goodbye"

v :: T = ...

main :: IO ()
main = print (blah v)  -- does this print "Hello" or "Goodbye"?

Depending on the choice of instance the compiler makes, blah v could equal either "Hello" or "Goodbye". Therefore, the meaning of a program would not be completely determined by the syntax of the program, but rather could be influenced by arbitrary choices the compiler makes.

Haskell's solution to this problem is to require that each type has at most one instance for each typeclass. To ensure this, it permits instance declarations only at the top level, and furthermore makes all declarations globally visible. That way, the compiler can always signal an error if an ambiguous instance declaration is made.

However, making declarations globally visible breaks the compositionality of the semantics. What you can do to recover is to give an elaboration semantics for the programming language -- that is, you can show how to translate Haskell programs into a better-behaved, more compositional language.

This actually gives you a way to compile typeclasses, as well -- it's usually called the "evidence translation" or "dictionary-passing transformation" in Haskell circles, and is one of the early stages of most Haskell compilers.

Typeclasses are also a good example of how programming language design differs from pure type theory. Typeclasses are a really awesome language feature, but they're quite ill-behaved from a proof-theoretic point of view. (This is why Agda does not have typeclasses at all, and why Coq makes them part of its heuristic inference infrastructure.)


Does a noisy version of Conway's game of life support universal computation? Quoting Wikipedia, "[Conway's Game of Life] has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life."

Do such results extend to noisy versions of Conway's Game of Life?
The simplest version is that after every round every live cell dies with a small probability $t$ and every dead cell becomes alive with a small probability $s$ (independently).

Another possibility is to consider the following probabilistic variant of the rule of the game itself.

Any live cell with fewer than two live neighbours dies with probability $1-t$.
Any live cell with two or three live neighbours lives with probability $1-t$ on to the next generation.
Any live cell with more than three live neighbours dies with probability $1-t$.
Any dead cell with exactly three live neighbours becomes a live cell with probability $1-t$.

Question: Do these noisy versions of the Game of Life still support universal computations? If not, what can be said about their "computational power"?

Related information on the computational power of cellular automata and noisy versions of cellular automata will be also much appreciated.

(This question developed from this question on MathOverflow. Vincent Beffara's answer on MO gave interesting references for related results on computational aspects of noisy cellular automata.)

Here are some "nearby best" references, for what it's worth. It would seem the way to go on this question is to reduce it to a question on "noisy Turing machines", which have been studied (somewhat recently), and which are apparently the nearest relevant area of the literature. The basic/general/reasonable answer seems to be that if the TM can resist/correct for noise (as is demonstrated in these references), it's quite likely the CA can also, within some boundaries/thresholds.

The question of how to reduce a "noisy CA" to a "noisy TM" (and vice versa) is more open. It may not be hard but there does not appear to be published research in the area. Another issue is that the noisy TM is a new model and therefore there may be multiple (natural?) ways to represent a noisy TM. For example, the following papers look at disruptions in the state transition function, but another natural model is disruptions in the tape symbols (the latter being more connected to noisy CAs?). There may be some relation between the two.

Fault-tolerant Turing Machine by Ilir Capuni, 2012 (PhD thesis)

  The Turing machine is the most studied universal model of computation. This thesis studies the question if there is a Turing machine that can compute reliably even when violations of its transition function occur independently of each other with some small probability.

  In this thesis, we prove the existence of a Turing machine that with a polynomial overheadcan simulate any other Turing machine, even when it is subject to faults of the above type, thereby answering the question that was open for 25 years.
  A Turing Machine Resisting Isolated Bursts Of
  Faults by Ilir Capuni and Peter Gacs, 2012
  Noisy Turing Machines by Eugene Asarin and Pieter Collins, 2005

  (Another question: could there be some connection between noisy TMs and probabilistic Turing Machines?)


How hard is counting the number of vertex covers after a small perturbation? Suppose you are given both a graph $G(V,E)$ and the exact number $C$ of vertex covers of $G$. Now suppose that $G$ is subject to a very small perturbation $P$, leading to $G'=P(G)$. More precisely, the perturbation $P$ is restricted to be one of the following:

Addition of $1$ new edge.
Addition of $2$ new distinct edges.
Removal of $1$ existing edge.
Removal of $2$ distinct existing edges.

  Question
  Given $G$, $C$, and $P$, how hard is to determine the number $C'$ of vertex covers of $G'=P(G)$? Is it possible to exploit the knowledge of $C$ and the fact that the perturbation is so tiny in order to efficiently determine $C'$?

Since counting vertex covers is #P-complete, your problem is unlikely to be in P; otherwise you could count the number of vertex covers starting from the empty graph on $|V|$ vertices, adding edges one by one.


Lexicographic perturbation for euclidean shortest path instances? Assume we have an undirected graph $G=(V,E)$ and vertex locations $\pi: V \rightarrow \mathbb{R}^2$. I am looking for a procedure to perturb the vertex positions to obtain new positions $\pi'$ such that the following statements hold:

For every pair $s\neq t \in V$, there is a unique shortest s-t-path $P_{s,t}$ in $G$ w.r.t. the euclidean weight function $c(v,w)=|\pi'(v)-\pi'(w)|_2$.
$P_{s,t}$ is also a shortest s-t-path w.r.t. the original vertex positions $\pi$.
$\pi'$ can be deterministically computed in polynomial time given $\pi$. The length of the numbers occuring in $\pi'$ are polynomially bounded in the length of those in $\pi$.

I know that lexicographic perturbation is a standard procedure to do this deterministically. Sadly there is no simple way to modify the distance of only a single edge in euclidean instances.

Is there any known approach that can be applied to those euclidean instances? Even a randomized perturbation algorithm would be interesting for me.

I think you're unlikely to get a good answer, because this is tied up in difficult and unsolved algebraic problems. The issue is that Euclidean path lengths (for points with integer coordinates) can be expressed as sums of square roots, but we don't know how small the difference between two distinct sums of square roots can be. Because of this, we also don't know how far apart the shortest path length and second-shortest distinct path length between a given pair of vertices can be, and therefore we don't know how small we have to make a perturbation to prevent it from changing the shortest path to a path that wasn't originally shortest.

For the same reason, shortest paths in Euclidean graphs are not really known to be solvable in polynomial time, in models of computation that take into account the bit complexity of the inputs, even though Dijkstra is polynomial in a model of computation allowing constant-time real-number arithmetic. So asking for a polynomial time algorithm for a more complicated variant of the problem in which the bit complexity is unavoidable seems likely to have a negative answer.


Upper bound for number of independent sets What is the tightest upper bound known for the number of independent sets in a graph?

The trivial upper bound of $2^n$ (on a graph with $n$ vertices) is as tight as you can get, since a graph that has no edges does indeed have $2^n$ independent sets.


Complexity of #PP2DNF where we also count on the number of clauses The #PP2DNF problem is the following: we have variables $X = \{x_1, \ldots, x_n\}$, $Y = \{y_1, \ldots, y_n\}$, and a positive partitioned 2-DNF formula, i.e., a Boolean formula of the form $\phi = \bigvee_{1\leq i \leq l} x_{p_i} \land y_{q_i}$, and we want to count its number of satisfying assignments, i.e., the number of Boolean functions from $X \cup Y$ such that $\phi$ evaluates to true under this valuation. This problem is well-known to be #P-hard by the work of Provan and Ball (sorry, no open-access version).

I'm interested in a variant of the problem where we also want to count on the clauses. Specifically, seeing $\phi$ as a set of clauses, I want to count the number of pairs $(\phi', \nu)$ of a subset of the clauses $\phi' \subseteq \phi$ and of a valuation $\nu$ of $X \cup Y$ such that $\phi'$ evaluates to true under $\nu$. For instance, if $\phi$ has two clauses, i.e., $\phi = C_1 \lor C_2$, I will count the number of satisfying valuations of $\phi$, plus the number of satisfying valuations of $C_1$, plus the number of satisfying valuations of $C_2$, plus 0 (the empty disjunction is always false). Equivalently I want to compute $2 n_1 + 2 n_2 + 3 n_{12}$ where $n_1$ is the number of valuations satisfying $C_1$ but not $C_2$, $n_2$ is the number of valuations satisfying $C_2$ but not $C_1$, and $n_{12}$ is the number of valuations satisfying both.

Is this version of the problem also #P-hard?

Another equivalent way to phrase the problem is in terms of bipartite graphs: we can see $\phi$ as a bipartite graph between $X$ and $Y$ (each clause being an edge, and #PP2DNF asks about the number of subsets of $X \cup Y$ that contain some pair of vertices that are connected by an edge (i.e., how many subsets are not independent sets). My version of the problem asks how many subsets of the vertex and edge sets there are such that we kept two vertices and an edge between these two vertices.

The problem is #P-hard, as we prove in a recent preprint: https://arxiv.org/abs/1908.07093

The way the preprint is phrased is closer to the equivalent formulation of the problem given at the end of my question: you have a bipartite graph $(X \cup Y, E)$ and you want to know how many triples $(X', Y', E')$ of subsets $X' \subseteq X$, $Y' \subseteq Y$, $E' \subseteq E$ there are such that we keep two vertices in $X'$ and $Y'$ connected by an edge in $E'$, i.e., $E' \cap (X' \times Y')$ is non-empty. This can again be equivalently reformulated in database or first-order logic terminology, which is what the preprint uses: you have a structure consisting of facts $R(a_1), \ldots, R(a_n)$, $T(b_1), \ldots, T(b_m)$, and $S(a_{i_1}, b_{j_1}), \ldots, S(a_{i_k}, b_{j_k})$ coding the bipartite graph (without multi-edges, i.e., $(a_{i_p}, b_{j_p}) \neq (a_{i_q}, b_{j_q})$ for all $p \neq q$), and you want to know how many subsets of these sets of facts satisfy the conjunctive query $\exists x \, y ~ R(x) \land S(x, y) \land T(y)$.

In the terminology of the preprint, this query is a self-join-free non-hierarchical conjunctive query (indeed, it is the simplest such example of a query, which we call $Q_1$), and hardness of this problem (the so-called model counting problem) is shown in the preprint: this is the simplest case of Theorem 4.2, with $r=1, s=1, t=1$.


How to translate general recursion into a set of $\mu$-recursive operator applications? I'm trying to find a scheme to translate a functional language with let rec into a set of primitives called "generalized arrows", i.e. $\kappa$-calculus with extensions. The problem is that general recursion is not expressible in $\kappa$-calculus, so I had to extend it with minimization operator.

There is a previous question asking about translation of Ackerman function into $\mu$-recursive operators, but the solution of Klaus Draeger doesn't seem to me to be generalizable.

Is there any previous work on translating general recursion into a set of $\mu$-recursive operator applications?

Klaus Draeger’s method can be fairly easily generalized, we just need one more piece to make it fully functional - a code stack. If we add in a code stack to the state, we can suddenly push things, or run multiple functions in one stack machine. The code would have only a few basic operators, a push operation and functions that are externally paired with a mu-recursive function. The mu-recursive functions take in some number of items from the top of the stack and return some items to be pushed to the stack and some code to be pushed to the code stack. To illustrate all of this, here’s an example of an addition function being defined within the machine. We will use two functions, the successor function and the addition function itself. The successor function is easy enough to define, just S(n) = <[S(n)],[]>, where <,> is the pairing function, the lists are encoded in the obvious way, and the S(n) within the definition is the standard successor function. The first list in the pair is what is pushed to the stack, and the second list is what is pushed to the code stack. More interestingly, the addition function is defined as +(0,m) = <[m],[]> and +(S n,m) = <[n,m],[+,S]>. The push operation is defined in the obvious way, push x pushes x to the stack and removes the instruction, as with every other instruction. One may ask after all this, “why is this modification required for everything but the ackermann function?” Well, simply, if you use this method to encode the ackermann function, you see that the only thing in the code stack at any point is just a string of ackermann functions, so you can simplify in the ackermann case, assume there’s nothing in the code stack but an infinite string of ackermann functions, and then eliminate the code stack entirely, using the empty stack to let you know once it’s finished evaluating.


Neural Networks: Incorporate feature-specific knowledge Has any research been done about / are people interested in incorporating prior knowledge of good high-level features into a deep neural net?

I know this somewhat defeats the purpose of feature learning but consider the following applied scenario: image classification task, 20 classes,  'small' training set (10k), expert human knowledge of high-level features.

Ideal would be to compensate for lack of training cases by incorporating knowledge of these features into the architecture (or via other means). How?

This 2013 paper integrates deep learning models with structured hierarchical Bayesian models, for the net to learn novel concepts from very few training examples. It shows encouraging results.

Another approach is to import a general-purpose top-performing neural net, and replace the top fully connected layers with initialised ones (including an output layer that corresponds to the number of classes in your specific task). OverFeat is an example, for image classification - it was trained on ImageNet.


The origin of the terms "efficient" and "feasible" computation/algorithm I would like to know about the history of these two terms: "efficient", "feasible".

Who used them about computation/algorithms the first time? (in modern sense of these terms, i.e. 20th century).
How did they become mainstream?
How did these two terms start to be used as synonyms?

I know that Cobham used the term "feasible" in the statement of his thesis which associated with polynomial time computability. But is there an earlier reference? There doesn't seem to be an explicit reference to these terms in Godel's letter to von Neumann. I was not able to find any related article predating 1960 (using Google Scholar).

Another interesting point is that the title of Cobham's paper from 1965 is "The intrinsic computational difficulty of functions". When did "computational complexity" replace "computational difficulty"?

I don't know about the terms "efficient" and "feasible."  Since these terms even today have no precise technical meaning, I suspect that the history of their usage will turn out to be murky, just as the history of most words in most languages is murky.

"Computational complexity" is a more interesting term.  With the help of MathSciNet, I find that Juris Hartmanis seems to have been the first to popularize it.  The famous 1965 paper by Hartmanis and Stearns uses the term in the title, but even before that, Hartmanis's Mathematical Review of Michael Rabin's paper "Real time computation" (Israel J. Math. 1 (1963), 203–211) says:

  This result is very instructive and contributes new techniques to the emerging theory of computational complexity of recursive sequences and functions. This theory is mainly concerned with the classification of computable problems by their degree of computational difficulty, the study of the properties of these complexity classes, their relation to each other and their dependence on the (abstract) computing devices.

Note that Rabin himself does not use the term "computational complexity" in this paper.

MathSciNet also turns up a couple of earlier reviews that use the term "computational complexity," but these seem to be spontaneous and sporadic occurrences.


Preprocessing Sparse, Directed Non-Planar Graphs for Faster Shortest Path I'm trying to preprocess a very large and sparse directed graph in order to do faster shortest path searches.  The vertices have no natural distance function, and the edges are unweighted.

One thought I had was to try and use a force directed graph layout algorithm to project the graph into space.  This way I could use cartesian distance for ASTAR and maybe get some improvements.

Constraint: There are so many vertices that any solution requiring a data with $O(n^2)$ space isn't viable.  However $O(n)$ space is fine, which is what made me think about assigning spacial coordinates to each vertex and doing distance calculations.

Any thoughts on this idea or others?

Thanks,

- Dan

UPDATE: For anyone interested, here's a paper that discusses my initial idea exactly: http://www.siam.org/meetings/alenex05/papers/02d.wagner.pdf

There have been many results on distance oracles and approximate distance oracles for directed graphs. A distance oracle for a graph is a data structure which can be queried on any pair of vertices (u,v) and returns the distance from u to v. It might also return the path realizing this distance. A good place to start (for the undirected case) would be:

Mikkel Thorup and Uri Zwick. Approximate distance oracles.
Journal of the ACM, 52(1):1–24, 2005.

For the directed case you should check out:

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick,
Reachability and distance queries via 2-hop labels
SIAM Journal on Computing 32, 1338--1355 (2003).

Some other works also manage to construct such data structures which are also dynamic, that is, it is possible to update the data structure with changes to the graph.


Arguments for existence of one-way functions I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-way functions?

Here's an argument that one-way functions should be hard to invert. Suppose there is a class of 3-SAT problems with planted solutions that are hard to solve. Consider the following map:

$$(x, r) \rightarrow s$$

where $x$ is any string of bits, $r$ is a string of bits (you could use these to seed a random number generator, or you can ask for as many random bits as you need) and $s$ is a $k$-SAT problem having $x$ as a planted solution, where the random number generator determines exactly which $k$-SAT problem you choose. To invert this one-way function, you need to solve a $k$-SAT problem with a planted solution.

This argument shows that inverting a one-way function is as hard as solving $k$-SAT problems with planted solutions. And since $k$-SAT is an NP-complete problem, if you can figure out how to construct hard instances with planted solutions for any NP problem, you can plant solutions in $k$-SAT formulas.

It has not been proven that it's possible to come up with a class of NP-complete problems with planted solutions that are just as hard as arbitrary NP-complete problems (and even if this is true, it's going to be incredibly hard to prove), but people definitely know how to plant solutions in $k$-SAT problems in ways that nobody currently knows how to solve.

ADDED: I now realize that this connection was already given (in more detail) in Abadi, Allender, Broder, Feigenbaum, and Hemachandra; they point out that one-way functions can give solved hard instances of SAT, and vice versa.

Putting it in more informal language, the non-existence of one-way functions shows that truly hard puzzles can't exist. If there is a type of puzzle where somebody can come up with both a puzzle and its solution algorithmically, then there is also a polynomial-time algorithm for finding a solution to the puzzle. This seems very counter-intuitive to me. Of course, a polynomial gap could exist; it might be the case that if creating the puzzle took $n$ steps, then solving it might take $O(n^3)$ steps. However, my intuition says that there should be a superpolynomial gap.


Factoring with LLL when the form of the factors is given Given a degree $2k$ reducible polynomial

$$f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$$

with

$$\text{gcd}(a_{2k},\dots,a_0)=1$$ that is known to be of the form $f_1(x)f_2(x)$ with $\text{deg}\big(f_i(x)\big)=\frac{\text{deg}(f(x))}{2}=k$ and each $f_i(x)$ irreducible.

Can the LLL algorithm be used to factor $f(x)$ in polynomial time and what is the complexity?

Note that $\text{gcd}(a_{2k},\dots,a_0)=1$ makes $f(x)$ primitive.

This answer tells that such polynomials have efficient factorization algorithms. Although the precise method is not mentioned there I belive LLL suffices and hence the question here. If LLL does do the job, can its complexity be improved from $(2k)^{6+\epsilon}$ arithmetic operations which is needed if the form of the factors are unknown.

Refer here for complexity of factoring primitive polynomials with integer ocefficents where the phrase

  We also mention Schönhage's method using $O(n^6+n^4\log_2^2l)$  bit operations for factoring polynomials with integer coefficients ($l$ is the length of the coefficients)

is used. $n$ is the degree and it corresponds to $2k$ here.

Yes, assuming you want both $f_1(x)$ and $f_2(x)$ with integer coefficients.

One of the reasons why LLL is so popular is precisely because it gives a polynomial time algorithm to factor polynomials with integer coefficients.

For an excellent introduction, I recommend C. Yap's "Fundamental Problems in Algorithmic Algebra" (available online, for free), specifically chapter 9 "Lattice Reduction and Applications" (section 9.6).

Following Yap, choose an approximation, $\alpha$, of a (complex) root for $f(x)$.  Setup the lattice reduction with the following basis:

$$ B_k = \begin{bmatrix}
\text{Re}(\alpha^0) & \text{Re}(\alpha^1) & \text{Re}(\alpha^2) & \cdots & \text{Re}(\alpha^k) \\
\text{Im}(\alpha^0) & \text{Im}(\alpha^1) & \text{Im}(\alpha^2) & \cdots & \text{Im}(\alpha^k) \\
c & 0 & 0 & \cdots & 0 \\
0 & c & 0 & \cdots & 0 \\
0 & 0 & c & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & c
 \end{bmatrix}
$$

Choosing $c = 2^{-4t^3}$, with $\alpha$ to have $O(t^3)$ bits for each of the real and complex portions.  Here, $t = \log ||f(x)||_{\infty}$ (that is, the cube of the number of bits of the maximum coefficient of $f(x)$).

Quoted from FPiAA:

  Theorem 9 Given a basis $A \in \mathbb{Q}^{n \times m}$, we can compute a reduced basis $B$ with $\Lambda(A) = \Lambda(B)$ using $O(n^5(s + \log n))$ arithmetic operations, where s is the maximum bit size of entries in $A$

This gives us the (polynomial) run time.  Proof of correctness that for a properly setup lattice will give you the minimal factor of a reducible polynomial is a bit more involved, but please refer to theorem 14 of the same chapter to see the relation between the reduced basis and the minimal polynomial.

By setting up the basis with dimension $n=k$ you can easily see the bound as roughly $O(k^5( \lg^3(||f(x)||_{\infty}) + \log n))$.

Since, by assumption, you know the degree of $f_1(x)$ and $f_2(x)$, the lattice reduction algorithm only needs to be run once to find one of the two factors of $f(x)$.  You can then use the discovered $f_j(x)$ to find the other by standard polynomial division.

The original paper by Lenstra, Lenstra and Lovasz, "Factoring polynomials with rational coefficients", is also quite readable and I found it to be a good compliment to Yap's introduction.


What paradigm of automated theorem proving is appropriate for Principia Mathematica-style formalization? I am in possession of a book, which, inspired by Russell's Principia Mathematica (PM) and logical positivism, attempts to formalize a specific domain by determining axioms and deducing theorems from them. In short, it attempts to do for its domain what PM attempted to do for mathematics. Like PM, it was written before automated theorem proving (ATP) was possible.
I am trying to represent these axioms in a modern ATP system, and attempt to deduce theorems, initially those deduced by the author (by hand). I have not used an ATP system before, and given the plethora of options (HOL, Coq, Isabelle, and many more), each with their strengths, weaknesses, and intended applications, it is proving difficult to decide which is appropriate for my specific purpose.
The formalism of the author closely mirrors PM. There are classes (sets?), classes of classes, and so on up to 6 levels of hierarchy. There is first order, and possibly higher order logic. Given the connection to PM, I initially investigated Metamath, since several theorems of PM have been proved in MetaMath by other people. However, Metamath is of course a proof verifier and not an ATP system.
Going through descriptions of various ATP systems, I see several characteristics, such as implementations of Church's type theory, constructive type theories, intuitionistic type theories, typed / untyped set theory, natural deduction, types of lambda calculi, polymorphism, recursive function theory, and the existence of equality (or not). In short, each system seems to implement a very different language, and must be appropriate for formalizing different things. I assume that existing libraries for formalizing mathematics are not relevant to my purpose.
Any advice regarding the characteristics I should seek in choosing an ATP, or any other advice you may have after reading this question, would be much appreciated. For reference, here is a sample page from the book. Unfortunately, like PM, it is in Peano-Russell notation.

The book -
"The Axiomatic Method in Biology" (1937), J.H. Woodger, A. Tarski, W.F. Floyd
The axioms start with the mereological. For example,

1.1.2 $x$ is the sum of $\alpha$ if $\alpha$ is contained in the parts of $x$, and if when $y$ is any part of $x$ there is always a $z$
belonging to $\alpha$ having parts in common with the parts of $y$:
$$S{ = }_{ Df }\hat { x } \hat { \alpha  } \{ \alpha \subset \vec { {
P }^{ ‘ } } x:.(y):yPx.\supset .(\exists z).z\in \alpha .\vec { { P
}^{ ‘ } } y\cap \vec { { P }^{ ‘ } } z\neq \Lambda \}$$
Again, note that this is Peano-Russell notation (the notation of
Principia).

Later axioms have biological content, such as,

7.4.2 When gametes of two members of a Mendelian class unite in pairs to form zygotes, the probability of any given pair uniting is equal to
that of the other pair.
This, from what I understand, was a postulate of Mendelian genetics.
I omit the notation for this because it is three lines long, and
builds upon previously defined content.

Example of a theorem -

This apparently carries a meaningful interpretation in Mendelian genetics, which, not being a historian of biology, I do not understand. In the book, it was deduced by hand.
Thanks!

Several points:

As far as I know, Principia Mathematica uses essentially a formalization of set theory using a typed first order logic. It would therefore be tempting to use a first-order automated theorem prover like Prover 9 or possibly ACL2 to formalize your statements. However, I am seeing several set-theoretic constructions (like $\in$, $\cap, \subset$) in there, which usually don't play very well with first order ATP.
Any modern interactive proof assistant will surely have the expressiveness to formalize and prove your statements, as Andrej has suggested. In fact, since there seem to be some statements including arithmetic, it would be wise to use a system like Isabelle, Coq or HOL which already have extensive theories to treat statements of arithmetic. My emphasis on modern is not a coincidence: great strides in usability have been made since Automath, and I honestly think you would be doing yourself a disservice by using anything that hasn't been actively developed since the 90's (if you could even get one to work!)
Finally, ITP and ATP have rather challenging learning curves, and you shouldn't expect to be able to enter these theorems into such a system as if you were writing a $\LaTeX$ proof. Expect severe frustration and lost time, especially in the first months (yes, months). You definitely need to work through some tutorials at first before getting to the main formalization.


Regular expressions aren't Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton.

For example, the “regular expression”

/^1?$|^(11+?)\1+$/

created by noted Perl personality Abigail (and part of Perl's test suite since 2002) describes a machine that accepts only composite unary numbers, but exercise 4.5 (b) in the third edition of Peter Linz's An Introduction to Formal Languages and Automata has the reader use the pumping lemma to prove that

$\mathcal{L} = \left\{ a^n : n\ \mathrm{is\ not\ a\ prime\ number} \right\}$

is not a regular language.

In contexts where the distinction is important, what should we call the strictly more powerful expressions?

Larry Wall proposed that we use "regular expression" for the formalism Kleene proposed, and "regex" for expressions for the widely used extensions.  It's a fairly widely followed convention.  If you want to make it clear that you are talking about regular expressions in the formal languages sense, it is usually not difficult to translate into talk of regular languages.

The power of regexes comes from backtracking, and there has been work done on automata for regular languages with backtracking.  See, in particular, Becchi & Crowley, 2008, Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions.


Unary language examples between L and NP I am looking for some examples of unary languages lay between $L$ and $NP$, i.e., $ L \subseteq NL \subseteq P = AL \subseteq NP $.
What I found after some search(e.g., Complexity zoo for unary languages):

It is not known whether there is a NP-Complete unary language.
There are many known results for automata models and sub-logarithmic space.
There seems no Zoo-style reference yet.

For example, is there any unary language in $ NL $ but not known in $ L $, in $ P $ but not known in $ NL $ or log-space alternating hierarchy?
Or, what are "the hardest" unary languages in $ NP $?

Classes of unary languages (above DLOGTIME) are just trivial variants of classes of usual, binary languages. Say, let us enumerate $\{0,1\}^*$ by natural numbers using the function $N(w_0\dots w_{n-1})=\sum_{i<n}2^iw_i+2^n-1$, and define the unary encoding of a language $L\in\{0,1\}^*$ to be $U(L)=\{1^{N(w)}:w\in L\}$. Then straightforward padding arguments show:

Unary languages in L are exactly the unary encodings of languages from $\mathrm{LinSPACE=DSPACE}(O(n))$.

Unary languages in NL are exactly the unary encodings of languages from $\mathrm{NLinSPACE=NSPACE}(O(n))=\mathrm{CSL}$.

Unary languages in P are exactly the unary encodings of languages from E.

Unary languages in NP are exactly the unary encodings of languages from NE.

Therefore:

There exist unary languages in $\mathrm{NL\setminus L}$ if and only if $\mathrm{LinSPACE\ne NLinSPACE}$.

There exist unary languages in $\mathrm{P\setminus NL}$ if and only if $\mathrm{NLinSPACE\ne E}$.

There exist unary languages in $\mathrm{NP\setminus P}$ if and only if $\mathrm{E\ne NE}$.

The “hardest” (under DLOGTIME reductions) unary languages in NP are exactly the languages $U(L)$ where $L$ is NE-complete under linear-time reductions (such languages exist).

Etc.


"Almost easy" NP-complete problems Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs.

In other words, there is an  $A\in$ P, such that $L\Delta A$ is vanishing, which means
$$\lim_{n\rightarrow\infty} \frac{|(L\Delta A) \cap \{0,1\}^n|}{2^n}=0.$$
It also means that on a uniform random input, the polytime algorithm for $A$ will give the correct answer for $L$ with probability approaching 1. Therefore, it makes sense to view $L$ almost easy.

Note that $L\Delta A$ does not have to be sparse. For example, if it has  $2^{n/2}$ $n$-bit strings, then it is still vanishing (at an exponential rate), since $2^{n/2}/2^n=2^{-n/2}$.

It is not hard to (artificially) construct NP-complete problems  that are  P-density-close, according to the above definition. For example, let $L$ be any NP-complete language, and define $L^2=\{xx\,|\, x\in L\}$. Then $L^2$ retains NP-completeness, but has at most $2^{n/2}$ $n$-bit yes-instances. Therefore, the trivial algorithm that answers "no" to every input, will correctly decide $L^2$ on almost all inputs; it will err only on a $\leq 1-2^{-n/2}$ fraction of $n$-bit inputs.

On the other hand, it would be very surprising if  all NP-complete problems are P-density-close. It would mean that, in a sense,  all NP-complete problems are almost easy. This motivates the question:

  Assuming P$\neq$NP, which are some  natural NP-complete problems that are not  P-density-close?

I looked into whether there is a generally accepted hypothesis in complexity theory, which implies that there must exist an NP-complete language that cannot be accepted in polynomial time on almost all inputs (as defined in the question).

Interestingly, the most "standard" hypotheses do not seem to imply it. That is, it does not appear to follow (unless I overlooked something) from P$\neq$NP, P$=$BPP,
NP$\neq$coNP, E$\neq$NE, EXP$\neq$NEXP, NP$\neq$PSPACE,  NP$\neq$EXP, NP$\not\subseteq$P/poly, PH does not collapse,  etc.

On the other hand, I found one, slightly less standard, hypothesis, which does imply the existence of the sought NP-complete problem, albeit not a natural one.  In the theory of resource bounded measure the fundamental hypothesis is that NP does not have $p$-measure zero, denoted by
$\mu_p($NP$)\neq 0$. Informally, this means that NP-languages within E do not form a negligible subset. For details, see a survey here. In this theory they prove, among many other things,  that
$\mu_p($NP$)\neq 0$ implies the existence of a P-bi-immune language in NP. A language $L$ is P-bi-immune if  neither $L$ nor its complement has an infinite subset in P. Such a language satisfies our requirement in a strong way.

However, it still remains unclear whether an example exists that represents a natural problem.


Dp completeness of a problem Given a Boolean formula $\varphi$ over the variables $\{x_1...x_n\}$ , an assignment $T_0$ for $\varphi$ and an integer $k$, I am interested in the following question:
Does $k$ is the minimal number of bits that we have to change with respect to $T_0$ to change the value of $\varphi$? I.e. there exists an assignment $T_1$ such that $T_1$ is different from $T_0$ in at least $k+1$ different places and $T_0(\varphi) \neq T_1(\varphi)$, and for all $T$ such that $T$ is different from $T_0$ in $k$ places or less, it holds that $T(\varphi)=T_0(\varphi)$.
Edit : I suspect that this problem is in dp, but can't prove its completeness. Ideas wil be welcome

Your problem is in fact in $\textsf{DP}$-complete. (For $\textsf{DP}$, see: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp.)

You can show membership in $\textsf{DP}$ by reducing your problem to the $\textsf{DP}$-complete problem SAT-UNSAT, which consists of all pairs $(\varphi_1,\varphi_2)$ of propositional formulas such that $\varphi_1$ is satisfiable and $\varphi_2$ is unsatisfiable. Given an instance $(\varphi,T_0,k)$ of your problem, we construct an instance $(\varphi_1,\varphi_2)$ of SAT-UNSAT. The problem of deciding whether there is some $T_1$ such that $T_1$ differs from $T_0$ in at least $k$ places and $T_0(\varphi) \neq T_1(\varphi)$ is in $\textsf{NP}$, so (by $\textsf{NP}$-completeness of SAT) we can construct some $\varphi_1$ in poly-time that is satisfiable if and only if an appropriate $T_1$ exists. Similarly, the problem of deciding whether for all $T_2$ that differ from $T_0$ in at most $k-1$ places it holds that $T_2(\varphi) = T_0(\varphi)$ is in $\textsf{coNP}$, so (by $\textsf{coNP}$-completeness of UNSAT) we can construct some $\varphi_2$ in poly-time that is unsatisfiable if and only if this property holds for all suitable $T_2$.

$\textsf{DP}$-hardness can be shown by a reduction from SAT-UNSAT, that I will sketch here. Let $(\varphi_1,\varphi_2)$ be an instance of SAT-UNSAT. Without loss of generality, assume that $\varphi_1$ contains exactly one variable more than $\varphi_2$. Let $x_1,\dotsc,x_{n+1}$ be the variables occurring in $\varphi_1$, and let $y_1,\dotsc,y_{n}$ be the variables occurring in $\varphi_2$. Then let the formula $\varphi'_1$ be $\varphi_1 \wedge \bigwedge_{i=1}^{n+1} (x_i \leftrightarrow \neg x'_i)$, where $x'_1,\dotsc,x'_n$ are fresh variables. Similarly, let the formula $\varphi'_2$ be $\varphi_2 \wedge \bigwedge_{i=1}^{n} (y_i \leftrightarrow \neg y'_i)$, where $x'_1,\dotsc,x'_n$ are fresh variables. We then define the formula $\varphi$ as $\varphi'_1 \vee \varphi'_2$. We let $T_0$ be the truth assignment that sets all variables to false. Finally, we let $k = n+1$. We know that $T_0(\varphi) = 0$. Satisfying $\varphi$ by flipping $k-1$ bits in $T_0$ can be done iff $\varphi_2$ is satisfiable, and satisfying $\varphi$ by flipping $k$ bits can be done iff $\varphi_1$ is satisfiable. Together, $k$ is the minimal number of bits to flip to satisfy $\varphi$ if and only if $(\varphi_1,\varphi_2) \in$ SAT-UNSAT.


Constaint Satisfaction problem with exponentially many solutions Say we have a constraint satisfaction problem parametrized by $n$ number of variables whose solution lies in a set of bounded non-negative integers of size $O(2^{n})$. Say we also know that we have $O(2^{an})$ satisfying solutions for the $n$ number of variables for some $a \in (0,1)$. Are there any known cases where such problems can be solved in polynomial in $n$ time?

Without further assumption the bound on the number of solutions you give isn't going to help. The reason is that there is an easy transformation of an arbitrary CSP problem into one that either continues to have no solutions (if the original problem had no solutions) or that has an exponential number of solutions (if the original problem has at least one solution): just add a linear number of irrelevant and unconstrained variables. So if you could find a solution quickly when there are an exponential number, you could apply this method to the output of this transformation and use it to find a solution quickly even when there is only one.


NP-hard problems on expander graphs? In a 2006 presentation titled EXPANDER GRAPHS - ARE THERE ANY MYSTERIES LEFT?
, Nati Linial posed the following open problem:

  Which $NP$-hard computational problem on graph remain hard when restricted to expander graphs?

Since then, Has any progress been made to prove such result for an $NP$-hard problem?

If "unbalanced expanders" count as expanders for the purpose of this question (an unbalanced expander: a bipartite graph $G=(A,B,E)$, such that for every subsets $A'\subseteq A$, $B'\subseteq B$, the fraction of edges between $A'$ and $B'$ is about ${|A'||B'|}/{|A||B|}$), then yes, many problems on expanders (e.g., constraint satisfaction problems) are NP-hard to approximate.

In particular, the proof of the two-query, low error, PCP Theorem [with Ran Raz in 2008] constructs expander graphs.


On the realisation of monoids as syntactic monoids of languages Let $L \subseteq X^{\ast}$ be some language, then we define the syntactic congruence as
$$
 u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L
$$
and the quotient monoid $X^{\ast} / \sim_L$ is called the syntactic monoid of $L$.

  Now what monoids arise as syntactic monoids of languages? I found languages for symmetric groups and for the set of all mappings on some underlying finite set. But what about other, are there finite monoids that could not be written as the syntactic monoid of some language?

For a given automaton, by considering the monoid generated by the mappings induced by the letters on the states (the so called transformation monoid) when function composition is read from left to right, it holds that the transformation monoid of the minimal automaton is precisely the syntactic monoid. This observation helped me in constructing the above mentioned examples.

Let me also not that it is quite simple to realise any finite monoid $M$ as the transformation monoid of some automaton, simply take the elements of $M$ as the states, and consider every generator of $M$ as a letter of the alphabet and the transitions are given by $qx$ for some state $q$ and letter $x$, then the transformation monoid is isomorphic to $M$ itself (this is similar to the Cayley theorem about how groups embed into symmetric groups).

It seems there is a paper answering this exact question, and even in the more general case of $\omega$-regular languages, but I cannot find an open-access version. If somebody finds a link without paywall it would be great. I requested the full-text on ResearchGate.

Title: Which Finite Monoids are Syntactic Monoids of Rational omega-Languages.

Authors: Phan Trung Huy, Igor Litovsky, Do Long Van

Abstract: A notion of ω-rigid sets for a finite monoid is introduced. We prove that a finite monoid M is the Arnold's syntactic monoid of some rational ω-language (ω-syntactic for short) if and only if there exists an ω-rigid set for M. This property is shown to be decidable for the finite monoids. Relationship between the family of ω-syntactic monoids and that of ∗-syntactic monoids (i.e. the syntactic monoids of rational languages of finite words) is established.

Additionally, the wikipedia page on syntactic monoids states:

Every finite monoid is homomorphic to the syntactic monoid of some non-trivial language,[1] but not every finite monoid is isomorphic to a syntactic monoid.[2]
Every finite group is isomorphic to the syntactic monoid of some non-trivial language.[1]

[1] McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph 65. With an appendix by William Henneman. MIT Press. p. 48. ISBN 0-262-13076-9. Zbl 0232.94024.

[2] Lawson (2004) p.233


NP-hardness of coloring uniform hypergraphs Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable  for $k=1,2$  is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen proofs in many places.

The situation changes if we look at $s$-uniform hypergraphs for $s \geq 3$, then the problem of deciding if an $s$-uniform hypergraph is $2$-colorable becomes NP-hard. I have read this fact multiple places, but without reference. What is the reference for classifying when the problem of deciding if an $s$-uniform hypergraph is $k$-colorable is NP-hard?

$2$-coloring $s$-uniform hypergraphs is also called Set Splitting, problem [SP4] in Garey-Johnson book.
The hardness proof is due to Lovasz in this paper.


How are safety/liveness languages defined on the set of finite or infinite words? Let $Σ$ be an alphabet (e.g., the powerset of atomic propositions coming from some Kripke structure, though such details are irrelevant here).

For infinite words, a language $P\subseteq Σ^ω$ is called a safety language iff every word $σ ∈ Σ^ω \setminus P$ has a finite prefix $σ̂$ such that $P ∩ \{σ' ∈ Σ^ω \mid σ̂\ \text{is a prefix of}\ σ'\} = ∅$.

Is there an accepted, meaningful definition of safety languages for finite words, i.e., "A set $P\subseteq Σ^*$ is called a safety language iff …"?
Is there an accepted, meaningful definition of safety languages for finite or infinite words, i.e., "A set $P\subseteq Σ^ω ∪ Σ^*$ is called a safety language iff …"?

For infinite words, a language $P\subseteq Σ^ω$ is called a liveness language iff each finite word from $Σ^*$ is a prefix of a word from $P$.

Is there an accepted, meaningful definition of liveness languages for finite words, i.e., "A set $P\subseteq Σ^*$ is called a liveness language iff …"?
Is there an accepted, meaningful definition of liveness languages for finite or infinite words, i.e., "A set $P\subseteq Σ^ω ∪ Σ^*$ is called a liveness language iff …"?

In cases 2 and 4, the definitions for finite-or-infinite words should be (intuitively speaking) compatible with the standard definitions for infinite words.

Of course, some folks prefer to speak about safety/liveness properties, which are predicates $(W)→\{0,1\}$, rather than about safety/liveness languages, which are subsets of $W$, where $W$ is the corresponding set of words ($Σ^ω$, $Σ^*$, or $Σ^ω∪Σ^*$). For this question, the preferred framework (predicates on the powerset vs. subsets) is irrelevant.

Needless to say: in case of a negative answer, please substantiate your concerns.

Crosspost: https://cs.stackexchange.com/questions/115156

The answer is yes to all questions, so it is enough to answer 2 and 4, as the definitions work in particular for languages of finite words:

A language $P\subseteq \Sigma^*\cup\Sigma^\omega$ is safety if whenever $u\notin P$, then $u$ has a finite prefix $u'\in\Sigma^*$ such that for any word $v$, $u'v\notin P$.

A language $P\subseteq \Sigma^*\cup\Sigma^\omega$ is liveness if for any finite word $u\in\Sigma^*$, there is a word $v$ such that $uv\in P$.


$\ell_1$ norm of Fourier coefficients vector for the hypercube Let $G$ be the normzlied hypercube graph on $2^d$. It is a Cayley graph and it is well known that its eigenvalues are given by $\lambda_r = 1-2\frac{|r|}{d}$ for every $r \in \{0,1\}^d$.

Given a function $f:[-1,1] \rightarrow[0,1]$, we can define for every $a \in \{0,1\}^d$ the Fourier coefficient
$$\hat{h}_a = \sum_{r \in \{0,1\}^d}f\left(1-2\frac{|r|}{d}\right)(-1)^{\left<r,a\right>}$$
Now, let $v$ be the vector of size $2^d$ so that $v_i = \hat{h}_i$ for $i \in \{0,1\}^d$.

I am looking for an upper-bound on $\frac{1}{2^{d}}\|v\|_1$ in terms of $f$.

Thank you very much for your help.

The question is about the spectral norm of the symmetric function $h: \{0,1\}^n \to [-1,+1]$ defined as $h(x) = f(1-2|x|/d)$. (I have assumed range $[-1,+1]$ instead of $[0,1]$ which is wlog by appropriate rescaling.)

Ada, Fawzi and H. Hatami show that for any boolean $g: \{0,1\}^n \to \{-1, +1\}$, $$\log \|\hat{g}\|_1 = \Theta\left(r(g) \log\left(\frac{n}{r(g)}\right)\right)$$ where $r(g) = \max(r_0(g), r_1(g))$ and $r_0(g)$ and $r_1(g)$ are minimum integers such that $g$ is either constant or perfectly correlated with parity or anti-parity for $x$ with $|x| \in [r_0(g), n-r_1(g)]$.

Now, look at the proof of Lemma 3.1 in the paper. Note that this straightforward argument also holds for functions $h$ mapping to $[-1,+1]$ instead of $\{-1,+1\}$. So, the same upperbound also holds for your case. This upperbound is tight at least for the boolean functions, but I don't know if there's a similar general lowerbound for non-boolean $h$.


Intersection models for weakly chordal graphs? Due to the apparent unpopularity of my previous posts, I'd like to post a question about graph theory which seems to be a popular topic here :)

Among the many known classes of perfect graphs, there are three classes that I find especially interesting:

(1) the weakly chordal graphs, whose obstruction set is $\{C_n,\bar{C_n} : n \geq 5\}$,

(2) the chordal graphs, whose obstruction set is $\{C_n : n \geq 4\}$,

(3) the strongly chordal graphs, whose obstruction set is $\{C_n : n \geq 4\} \cup \{S_n : n \geq 3\}$.

Here, $C_n$ denotes the $n$-cycle, and $S_n$ denotes the $n$-sun (obtained by starting from a cycle $x_1 ... x_n$ and adding the edges $x_i y_i x_{i+1}$ for $1 \leq i \leq n$).

These classes admit polynomial algorithms for clique/independent set, the most general one being for the class of weakly chordal graphs and uses a clever 'two-pair contraction' argument (see 'Optimizing weakly triangulated graphs' by R. Hayward, C.T. Hoang and F. Maffray).

Intersection models are known for classes (2) and (3) as they correspond to the clique graphs of acyclic, resp. totally balanced, hypergraphs. Are there any known results about intersection models for weakly chordal graphs?

As a side note, there is a recursive construction of totally balanced hypergraphs due to Lehel (see 'A characterization of totally balanced matrices'), and I was also wondering about possible algorithmic applications of this result?

If I would like to know something about intersection models, the first reference I would check is the "Topics in Intersection Graph Theory" by McKee and McMorris.  Theorem 1.5 answers your (combinatorial) question.


A proof that Partition into forests is NP-Complete The partition a graph into forests problem is defined as:

Given a Graph $G=(V,A)$, and a positive integer $K \le |V|$, can the vertices $V$ be partitioned into disjoint sets $V_1$, ..., $V_k$, $k \le K$, such that, for $1 \le i \le k$, the subgraph induced by $V_i$ contains no circuits?

I am trying to prove it is NP-Complete the following way:

Given an instance of the clique problem consisting of a graph $G'=(V', A')$ and a number $m$, where $m$ is odd, I will build an instance for my problem in the following way: $G=G'$, and $k = \frac{m-1}{2}$. If there is a clique with size at least $m$ in $G$, then there will be no partition of the vertices $V$ into $k$ disjoint sets such that the subgraph induced by each $V_i$ contains no circuits. And if there is no partition of the vertices $V$ into $k$ disjoint sets such that the subgraph induced by each $V_i$ contains no circuits, then there will be a clique of size at least $m$ in $G'$.

Is this proof correct?

If not, how can I prove that the partition a graph into forests problem is NP-Complete?

First, let me address what is wrong with your proof. The general idea you give for how to prove your reduction correct seems reasonable. The problem is that your reduction is not actually correct. In particular, the statement "if there is no partition of the vertices $V$ into $k$ disjoint sets such that the subgraph induced by each $V_i$ contains no circuits, then there will be a clique of size at least $m$ in $G′$" is false. Consider the following counterexample:

This graph has no 5-cliques, but also cannot be partitioned into 2 forests.

Reduction alternative

You can instead reduce from graph 3-coloring. Given a graph $G = (V, E)$, you can modify this graph by adding three new vertices $u_1, u_2, u_3$ and adding every possible edge with any of these vertices as an endpoint. Let $G'$ be this new graph. Then we claim that $G$ is 3-colorable if and only if $G'$ can be partitioned into 3 forests.

First direction:

Suppose $G$ is 3-colorable. Let $A$, $B$, and $C$ be the sets of vertices in $G$ with each of the three colors. Let $A' = A \cup \{u_1\}$, $B' = B \cup \{u_2\}$, and $C' = C \cup \{u_3\}$. Notice that by the properties of a 3-coloring, no two vertices in $A$ are adjacent. Therefore the only edges induced by $A'$ are of the form $(u_1, v)$ with $v \in V$. Clearly, the graph induced by $A'$ has no cycles. The same logic applies to show that $B'$ and $C'$ also induce forests. Thus, $A'$, $B'$, and $C'$ is a partition of $G'$ into three forests.

Second direction:

Now suppose $G'$ can be partitioned into three forests. Since $u_1, u_2, u_3, u_1$ is a cycle, the three vertices $u_1, u_2, u_3$ cannot all be in the same part of the partition. Then there are two cases.

Case 1: each vertex $u_1, u_2, u_3$ is in a different part of the partition.
Then consider any two vertices $v_1, v_2$ from the same part of $G'$ other than $u_1, u_2, u_3$. If $(v_1, v_2)$ were an edge, then there would be a cycle $u_i, v_1, v_2, u_i$ in the part containing $v_1$ and $v_2$. Since that is not the case, we see that no two adjacent vertices of $G$ are in the same part of the partition. In other words, the partition of $G'$ directly induces a 3-coloring of $G$.

Case 2: some two vertices among $u_1, u_2, u_3$ are in the same part. WLOG, suppose $u_1$ and $u_2$ are in the same part of the partition, call it $A$. Let the part of the partition containing $u_3$ be $B$ and let the final part be $C$. Note that $A$ contains no vertices from $G$ since if any $v \in V$ were in $A$ then the cycle $v, u_1, u_2, v$ would be present in one of the parts. Thus, every vertex from $G$ is either in $B$ or in $C$. Since $C$ induces a forest, it is possible to 2-color the vertices in $C$ (such that no two vertices of the same color are adjacent). If we then color the vertices of $B$ with a third color, we will have an assignment of three colors to the vertices of $G$. We already know that two of those colors have no adjacent monochromatic pairs of vertices. Using the same logic as in case 1, we can also conclude that $B$ contains no two adjacent vertices in $G$, and therefore that the third color also has no adjacent monochromatic pairs of vertices. We can conclude then that the described coloring is a valid 3-coloring of $G$.


Reference for mixed graph acyclicity testing algorithm? A mixed graph is a graph that may have both directed and undirected edges. Its underlying undirected graph is obtained by forgetting the orientations of the directed edges, and in the other direction an orientation of a mixed graph is obtained by assigning a direction to each undirected edge. A set of edges forms a cycle in a mixed graph if it can be oriented to form a directed cycle. A mixed graph is acyclic if and only if it has no cycles.

This is all standard and there are many published papers mentioning acyclic mixed graphs. So the following algorithm for testing acyclicity of mixed graphs must be known:

Repeat the following steps:

Remove any vertex that has no incoming directed edges and no incident undirected edges, as it cannot be part of any cycle.
If any vertex has no incoming directed edges but it has exactly one incident undirected edge, then any cycle using the undirected edge must come in on that edge. Replace the undirected edge by an incoming directed edge.

Stop when no more steps can be performed. If the result is an empty graph, then the original graph must necessarily have been acyclic. Otherwise, starting from any vertex that remains, one can backtrack through the graph, at each step following backwards through an incoming edge or following an undirected edge that is not the one used to reach the current vertex, until seeing a repeated vertex. The sequence of edges followed between the first and second repetition of this vertex (in reverse order) forms a cycle in the mixed graph.

The Wikipedia article on mixed graphs mentions acyclic mixed graphs but doesn't mention how to test them, so I'd like to add to it something about this algorithm, but for that I need a published reference. Can someone tell me where it (or any other algorithm for testing acyclicity) appears in the literature?

Finding mixed cycles in a mixed graph is equivalent to finding elementary directed cycles (of length >=3) in the corresponding directed graph. The corresponding directed graph is obtained from the mixed graph by replacing each undirected edge by two directed edges pointing in opposite directions. Proof: (1) Each elementary directed cycle (of length >=3) in the digraph corresponds directly to a mixed cycle in the mixed graph. (2) Each mixed cycle in the mixed graph contains an elementary mixed cycle of length >=3, and each such cycle corresponds directly an elementary directed cycle (of length >=3) in the directed graph. (1) and (2) together prove both directions of the statement, qed. So we are looking for references how to compute (all?) elementary cycles (of length >=3) in a directed graph.

The comments indicate that cs.stackexchange contains some answers to this question, but it is unclear how to organize the results into a concise answer. This blog post seems to nicely summarize the (most?) important references:

  Algorithm by R. Tarjan

  The earliest algorithm that I included was published by R. Tarjan in 1973.

Enumeration of the elementary circuits of a directed graph
R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216
http://dx.doi.org/10.1137/0202017

  Algorithm by D. B. Johnson

  The algorithm by D. B. Johnson from 1975 improves on Tarjan's algorithm by its complexity.

Finding all the elementary circuits of a directed graph.
D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975.
http://dx.doi.org/10.1137/0204007

  In the worst case, Tarjan's algorithm has a time complexity of O(n⋅e(c+1)) whereas Johnson's algorithm supposedly manages to stay in O((n+e)(c+1)) where n is the number of vertices, e is the number of edges and c is the number of cycles in the graph.

  Algorithm by K. A. Hawick and H. A. James

  The algorithm by K. A. Hawick and H. A. James from 2008 improves further on Johnson's algorithm and does away with its limitations.

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs.
Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20
www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf

  In contrast to Johnson's algorithm, the algorithm by K. A. Hawick and H. A. James is able to handle graphs containing edges that start and end at the same vertex as well as multiple edges connecting the same two vertices.

The acyclicity testing itself seems to be easy: Compute the strongly connected components of the graph. Any (elementary) cycle is completely contained in a strongly connected component. A strongly connected component contains an elementary cycle iff it is not an undirected tree.

David Eppstein's proposed algorithm additionally computes one elementary cycle as evidence, and the above algorithms enumerate all elementary cycles. Any vertex or edge not contained in an elementary cycle could be deleted as a preprocessing step to improve the speed of the above algorithms. David Eppstein's algorithm could be used for that purpose, but even if only used on the strongly connected components, it won't delete every possible vertex or edge that can be deleted. But even if it could be extended to do so (computing the block-cut tree at least allows to delete every possible vertex that can be deleted), it is unclear whether this would really improve the speed of the above algorithms.


Minor closed properties that are explicitly MSO expressible Below, MSO denotes the monadic second order logic of graphs with vertex-set and edge-set quantifications.

Let $\mathcal{F}$ be a minor closed family of graphs. It follows from Robertson and Seymour's graph minor theory that $\mathcal{F}$ is characterized by a finite list $H_1,H_2,...,H_k$ of forbidden minors.
In other words, for each graph $G$, we have that $G$ belongs to $\mathcal{F}$ if and only if $G$ excludes all graphs $H_i$ as minors.

As a consequence of this fact, we have an MSO formula $\varphi_{\mathcal{F}}$ which is true on a graph $G$ if and only if $G\in \mathcal{F}$. For instance, planar graphs are characterized by the absence of the graphs $K_{3,3}$ and $K_5$ as minors, and therefore it is easy to write explicitly an MSO formula characterizing planar graphs.

The problem is that for many nice minor closed graph properties, the list of forbidden minors is unknown. So, while we know that an MSO formula characterizing that family of graphs exist, we may not know what this formula is.

On the other hand, it may be the case that one is able to come up with an explicit formula for a given property without using the graph minor theorem. My question is related to this possibility.

Question 1: Is there a minor closed family of graphs $\mathcal{F}$, such that the set of forbidden minors is not known, but some MSO formula $\varphi$ characterizing that set of graphs is known?

Question 2:  Is some explicit MSO formula $\varphi$ known to characterize some of the following properties?

Genus 1 (the graph is embeddable in a torus)  (see EDIT below)
Genus k for some fixed $k>1$   (see EDIT below)
k-outerplanarity for some fixed $k> 1$

I would appreciate any reference or thoughts on this matter. Please feel free to consider other minor closed properties, the list given above is only illustrative.

Obs: By explicit I do not mean necessarily small. It is enough to give an explicit argument or algorithm showing how to construct the formula characterizing the given property. Similarly, in the context of this question I consider a family of forbidden minors to be known if one has given an explicit algorithm constructing that family.

EDIT: I found a paper by Adler, Kreutzer, Grohe which constructs a formula characterizing graphs of genus $k$ with basis on the formula characterizing graphs of genus k-1. So this paper answers the first two items of Question 2. On the other hand this does not answer Question 1 because there is indeed an algorithm that constructs for each k, the family of forbidden minors characterizing graphs of genus k (See section 4.2). Therefore this family is "known" in the sense of the question.

I had an answer here involving apex graphs but it fails the definition of not having an explicit obstruction set given in this question: there is a published algorithm for finding the obstruction set, even though is too slow to run so we don't actually know what the obstruction set is.

So here's another parameterizable family of answers without that flaw (at least, as far as I know). Given a minor closed family $F$, and an integer $k\ge 1$, does the given graph $G$ have a $k$-ply covering graph in $F$? Much about this sort of question remains unknown: in particular, Negami's conjecture, which would characterize the graphs that have a planar covering graph, remains unproven. And it's minor-closed because any steps that you take to make a minor from $G$ can be copied in the cover.

To test for the existence of a $k$-ply cover of $G$ in $F$, in MSO$_2$, do the following steps:

Use the depth-first-search-tree trick to get an (arbitrary) orientation of $G$.
For each pair $(i,j)$ with $0\le i,j<k$, choose a set of edges in $G$, supposedly the ones that have a covering edge that goes from ply $i$ to ply $j$.
Check that each vertex in each ply has exactly one copy of each incident edge, and thus that this information represents a valid covering graph of $G$.
Emulate the obstruction set based formula for membership in $F$ on the covering graph.


What is the complexity of model checking Process Logic (LTL fragment)? Process Logic is a modal logic allowing to reason about temporal properties of programs. Its formulae take the form similar to (Propositional) Dynamic Logic $[P]\phi$, with $P$ being a program (think regular expression) and $\phi$ being another process logic formula, however unlike PDL, it can contain temporal LTL-style modalities. Unlike LTL, the formulae are read as follows "along traces resulting from execution of $P$, $\phi$ holds", or plainly "during execution of $P$, $\phi$ holds". Temporal modalities correspond to an extension of LTL with a chop and slice operators.

I am interested in a fragment of Process Logic where $\phi$ wouldn't be a full PL formula, but rather a plain LTL formula without modalities of the form $[P]$.

Question: Are there complexity analysis results relevant to model-checking formulae of Process Logic, or related formalisms? I am interested in both, the the complexity analysis, as well as some ideas for algorithms for doing it.

More along the "related formalisms" direction.

PDL with intersection and converse: satisfiability and infinite-state model checking, Stefan Göller, Markus Lohrey, and Carsten Lutz, 2009
The Effects of Bounding Syntactic Resources on Presburger LTL, Stéphane Demri and Régis Gascon

The introduction section of the first paper has an extensive discussion of complexity results for PDL fragments and extensions. I include the second mainly because you may be be able to encode some parts of your problem as a Presburger extension and transfer some results.


Computing 'Robustness of Magic' of $n$-bit W states Question

What is the asymptotic robustness-of-magic of a $W$ state over $n$ qubits. Is it $\Theta(n)$? $\Omega(\sqrt{n})$? $O\left(\frac{n}{\lg n} \right)$?

Background

$W$ states are entangled states where exactly one qubit is ON and every qubit has an equal chance of being ON if measured. For example, $W_3 = \frac{1}{\sqrt{3}} \left( |100\rangle + |010\rangle + |001\rangle \right)$.

In the paper "Application of a resource theory for magic states to fault-tolerant quantum computing", Howard and Campbell associate a quantum state $\rho$ with a cost $R(\rho)$ called "robustness of magic" and defined as:

$$R(\rho) = \min_x \sum_i |x_i|; \rho = \sum_i x_i \sigma_i $$

Where each $\sigma_i$ is a state that can be prepared by a stabilizer circuit (i.e. using only H, S, CNOT, and measurement gates). In other words, you try to find a weighted combination of stabilizer states that produce your desired state, and the cost you minimize while doing so is the sum of the weights' magnitudes. The minimum such cost is the robustness of magic of the state.

What I've Tried

The best-scoring decomposition I've found, for the $n$-qubit $W$ state, is:

$$s_{j,k} = X_j \cdot \text{CNOT}_{j\rightarrow k} \cdot H_j \cdot |0\rangle$$

$$S_{j,k} = s_{j,k} \cdot s_{j,k}^\dagger$$

$$W_n = \left(\sum_{j=0}^{n-1} \sum_{k=j+1}^{n-1} \frac{1}{n} S_{j,k} \right) + \left(\sum_{j=0}^{n-1} \frac{2-n}{n}|j\rangle \langle j| \right)$$

Which achieves a cost of $\frac{1}{n} \cdot \frac{n(n-1)}{2} + \frac{n-2}{n}\cdot n = \frac{3}{2}n-\frac{5}{2}$.

The best circuit construction I know for producing a large W state has a T-count that also scales like $\Theta(n)$. For example, here is an example construction that shows how to create a $W_n$ state using $2n-4$ T gates if $n$ is a power of 2:

Note that, if you want to compare the $2n-4$ T-count to the $\frac{3}{2}n - \frac{5}{2}$ potential-robustness-of-magic of the best-I-found decomposition, you must account for the fact that a $|T\rangle$ state's robustness-of-magic is $\sqrt{2}$ (not $1$).

Now, obviously, trying to find better and better decompositions is a reasonable way to upper-bound the robustness of magic... but this strategy will never create a lower-bound. What kinds of strategies do work for making lower bounds on this kind of problem?

Here is a proof that $R(W_n) \in \Omega(\sqrt[4]{n})$.

Given a $W_n$ state, it is possible to create $\lg n$ T states with Clifford operations and a single additional T gate. Basically:

Xor together all the qubit's whose binary index has an odd number of 1s, apply a T gate to that xor'd value, then unxor.
Apply an S gate to every qubit whose binary index has a number of 1s that's 2 or 3 more than a multiple of 4.
Apply a Z gate to every qubit whose binary index has a number of 1s that's 4, 5, 6, or 7 more than a multiple of 8.
Compress the unary $W_n$ state down into a binary register.

Here's an example circuit turning $W_8$ into 3 $|T\rangle$ states:

I also tested turning $W_{16}$ into 4 $|T\rangle$ states.

We can produce $\lg n$ T states from a $W_n$ state and a single $T$ state. It must always be the case that an output's robustness of magic is less than or equal than the input's. Therefore:

$$R(W_n) \cdot R(T) \geq R(W_n \otimes T) \geq R(T^{\otimes \lg n})$$

In the paper "Application of a resource theory for magic states to fault-tolerant quantum computing" it is proven (see page 3) that:

$$R(T^{\otimes k}) \in \Omega(1.2^k)$$

Meaning $R(W_n) \cdot R(T)$ is greater than or equal to something asymptotically lowerbounded by $1.2^{\lg n}$. Since $R(T)$ is a constant, we can ignore it and deduce:

$$\begin{align}
R(W_n) &\in Ω(1.2^{\lg n})
       \\&= Ω(n^{\lg 1.2})
       \\&\subset Ω(n^{0.263})
       \\&\subset Ω(\sqrt[4]{n})
\end{align}$$

Therefore $R(W_n)$ is asymptotically somewhere between $\sqrt[4]{n}$ (by synthesizing into Ts) and $n$ (via the decomposition I showed in the question).


Questions about algebraic effects and handlers, decomposed handlers Can a handler always be decomposed? Say a handler for Get and Set effects could be decomposed to a handler for Get and a handler for Set.
After they could be composed again by first applying the handler for Set and after the handler for Get.

Also why do handlers have special type instead of just being a function type from effectful type to effectful type.

And last question: why are computation types used so often in the papers instead of something more like monads in Haskell (where pure functions still exist).

That's three questions.

Can handlers be decomposed?

No, a handler cannot always be decomposed because the operations may interact. It is false that you can decompose get and set into separate handlers because they have to handle a shared state. You can try these examples online in Eff. First, the ordinary state handler:

type 'a state = effect
  operation get: unit -> 'a
  operation set: 'a -> unit
end

let r = new state

let state_handler x = handler
  | val y -> (fun s -> (y, s))
  | r#get () k -> (fun s -> k s s)
  | r#set s' k -> (fun _ -> k () s')
  | finally f -> f x

;;

with state_handler 30 handle
   let x = r#get () in
   let () = r#set 20 in
   let y = r#get () in
     (x,y)
;;

The above example returns (30, 20), as it should. Now let's separate the handler into two handlers and apply them, as you suggested:

type 'a state = effect
  operation get: unit -> 'a
  operation set: 'a -> unit
end

let r = new state

let get_handler x = handler
  | val y -> (fun _ -> y)
  | r#get () k -> (fun s -> k s s)
  | finally f -> f x

let put_handler x = handler
  | val y -> (fun _ -> y)
  | r#set s' k -> (fun _ -> k () s')
  | finally f -> f x

;;

with put_handler 30 handle
with get_handler 30 handle
   let x = r#get () in
   let () = r#set 20 in
   let y = r#get () in
     (x,y)
;;

The result is (30, 30) which is unexpected. The problem is that each handler put_handler and get_handler is rolling its own state, so get takes state from one place and put places it into another place.

Why do handlers have special types?

In a language with operations and handlers we distinguish values from computations. A value is an inert piece of data which cannot trigger any effects and needs not be computed (such as a constant true, a tuple (42, false), or a function fun x => ...). A computation is an expression which must still be evaluated, and it may trigger an effect, produce a value, or diverge. Now:

functions map values to computations,
handlers map computations to computations.

The difference is visible in the types: $\alpha \to \beta$ is the function type, but $\alpha \Rightarrow \beta$ is the handler type. In operational semantics there is also a difference: we must apply a function to a value, and we must apply a handler to a computation. Thus, instead of writing

(fun x => print "Hello"; x + 3) (print "world" ; 8)

we must write

let v = (print "world"; 8) in (fun x => print "Hello"; x + 3) v

Of course this is quite annoying and the programmer doesn't have to do it by hand, at least not in Eff. Eff will perform the transformation automatically. Also note that here print "world"; 8 is evaluated first, and then the function is applied to v.

You can think of a handling construct as an application of a handler to a computation:

with H handle C

means "apply H to the computation C". Note that we do not evaluate C first, contrary to how we evaluated v above before we applied the function.

Why are computation types used?

The computation types are part of an adjunction between value types and computation types. We have a category $\mathcal{V}$ of value types and a category $\mathcal{C}$ of computation types, with two functors
$$F : \mathcal{V} \to \mathcal{C} \qquad\text{and}\qquad
  U : \mathcal{C} \to \mathcal{V}$$
such that $F$ is left-adjoint to $U$. It is a general fact that such an adjunction determines a monad $T = U \circ F : \mathcal{V} \to \mathcal{V}$. By passing from the adjunction $F \dashv U$ to the monad $T$ we lose a little bit of information (but not much, since every monad can be decomposed into an adjunction in a canonical way).

The use of computation types is thus largely a matter of mathematical setup. It is quite natural to use value and computation types when we consider handlers. This is so because operations and handlers arise from a similar picture that occurs in algebra: there is a category of sets $\mathsf{Set}$ and the category of algebras $\mathsf{Alg}$ (for the given operations), together with functors
$$F : \mathsf{Set} \to \mathsf{Alg} \qquad\text{and}\qquad
  U : \mathsf{Alg} \to \mathsf{Set} $$
where $F(X)$ is the free algebra generated by the set $X$ and $U(A)$ is the underlying set of the algebra $A$. This again is an adjunction. (In fact, handlers were discovered starting from these two functors. We massaged them until algebra became programming.) In this instance value types are sets and computation types are free algebras. For example, a computation which returns a natural number, and may trigger put and get operations, is the free algebra $F(\mathbb{N})$ for the operations put and get. A handler for such an operation has the form

handler
  put x k => P
  get x k => G
  val n => V(n)

and corresponds to an algebra homomorphism $\phi : F(\mathbb{N}) \to A$ where $A$ is an algebra with operations $P$ and $G$, and $\phi$ maps a generator $n$ to the element $V(n) \in A$.

Could we rephrase all of this in terms of the monad $T = U \circ F$? Probably, but it would be ugly, and it would start to look like we're trying to hack things in Haskell, rather than do them from foundations up.


any connection between binary/integer multiplication and matrix multiplication? is there a connection between the inherent complexity of binary/integer multiplication algorithms and matrix multiplication algorithms? if so what is a ref that outlines/discusses it?

some related history: Schonhage/Strassen give a fast algorithm for binary multiplication and Strassen also gave a faster matrix multiplication method.

A. Schonhage and V. Strassen, “Schnelle Mu ¨ ltiplikation grosser Zahlen,” Computing 7 (1971),
281–292

Here is a relevant reference and Sasho has graciously added a high-level summary.

A Group-theoretic Approach to Fast Matrix Multiplication by Cohn and Umans. (2004, arxiv).

  There is a close analogy between the framework we propose in this paper and the well-known algorithm for multiplying two degree n polynomials in O(n log n) operations
  using the Fast Fourier Transform (FFT). In this section we
  elucidate this analogy to give a high-level description of our
  technique.

On a very high level, the FFT-base polynomial multiplication algorithm can be seen as the following strategy: 1) embed the polynomials as elements of the group algebra of a not-too-large abelian group; 2) apply the DFT to the group algebra elements in order to embed them as complex-valued diagonal matrices; 3) multiply the diagonal matrices.

(Note: the group algebra here is the algebra of formal "linear combinations" of group elements with complex or real coefficients).

The same approach almost works for matrix multiplication. Step 1) becomes hard, where it was trivial with polynomials. The embedding can be done with abelian groups of size $n^3$, and no better, so for $n^{2 + o(1)}$ size groups you need to abandon commutativity. Then 2) turns out to still be doable with non-abelian groups using the appropriate generalization of DFT that you get from representation theory, but the resulting object is a block-diagonal matrix rather than a diagonal matrix. Then 3) is no longer the trivial pointwise multiplication operation, but multiplication of smaller matrices. Bounding the sizes of these matrices is a question about dimensions of irreducible representations of the group we used.

See also the follow-up Group-Theoretic Algorithms for Matrix Multiplication by Cohn, R. Kleinberg, Szegedy, and Umans (2005, arxiv).

Perhaps there have been advancements (or even a survey) since then. Of course this probably doesn't answer your question about how the complexities of the problems are related....


Delimiting the roots of a polynomial Given a polynomial of degree $n$, namely, $y=a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0$, with $a_i\in \mathbb{R}$,  I would to know if it is possible to compute a rational number $K$ such that the distance between each of the (at most $n$) real roots of the polynomial is $K$.

You can (without too much work) find a number $K$ such that if $|x| > K$ then $|a_n x^n| > \sum_{k<n} |a_k x^k|$, and so all roots are inside $(-K,K)$ and the distance between them is smaller than $2K$.


Lattice generation inside d-dimensional unit ball I am interested to know if there is a standard algorithm for generating all the lattice points inside the $d$-dimensional unit ball (with respect to the $\ell_2$-norm).

The brute force approach is to generate the lattice over the $\ell_\infty$ unit ball and then loop through each of the points and remove those with norm strictly greater than $1$. I was wondering if there is a more elegant approach to solving this problem. My initial thoughts are to attempt to cover the $d-1$ dimensional sphere with $n$ points and try and use those points to find out the "limits" that I can then use to generate the lattice coordinate vectors. Then I would define the lattice over the intervals defined by these limits $[a_1,b_1] \times [a_2,b_2] \times … \times [a_d,b_d]$. However, in my mind it is non-trivial to decide how many points to put on the sphere and the algorithm for actually determining the aforementioned limits.

Another approach would be to think of what are the coordinates of the maximum volume polyhedron that can be inscribed in the ball and then somehow constrain them to be on the lattice...Again, this seems to be non trivial. A similar line of thought would be to find the minimum volume polyhedron in which we can include the unit ball by enforcing the constraint that its vertices are lattice points. Then we can just subtract the distance between two lattice points and end up inside the sphere...

Are any of these problems with known solutions/non-trivial to solve?

Thank you in advance.

In general, even telling whether any such point exists is hard; it is equivalent to the Shortest Vector Problem (SVP), and it is conjectured that there is no polynomial-time algorithm for this problem.


Are there good locally decodable _erasure_ codes Are there known locally decodable erasure codes with

  linear codeword length and $\:n^{o(1)}\:$ query complexity?

According to pages 1 and 4 of this link (which annoying does not give its own date,

though it cites references from 2011), locally decodable (error-correcting) codes

with linear codeword length are only known with query complexity $n^{\epsilon}$ for $\: \epsilon > 0 \;$.

i.e., Does considering erasure codes instead change that?

Such a code could be used for showing that a data host has random access to a given file.

Locally decodable codes and locally decodable erasure codes are qualitatively equivalent. Both imply $\Omega(m)$ many disjoint $q$-tuples from which one can recover a given message coordinate, where $m$ is the codeword length and $q$ is the query complexity. A formal argument appears in Section 3.4 of Kerenidis and de Wolf's paper.


Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value Here is a problem with a similar flavor to learning juntas:

Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$.

Goal: Find a subcube $S$ of $\{0,1\}^n$ with volume $|S|=2^{n-k}$ such that $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.1$. We assume such a subcube exists.

It is easy to get an algorithm that runs in time $n^{O(k)}$ and returns a correct answer with probability $\ge 0.99$ by trying all $(2n)^k$ ways to choose a subcube and sampling the average in each one.

I'm interesting in finding an algorithm that runs in time $poly(n,2^k)$. Alternatively, a lower bound would be great. The problem has similar flavor to learning juntas, but I don't see an actual connection between their computational difficulty.

Update: @Thomas below proves that the sample complexity of this problem is $poly(2^k,\log n)$. The interesting issue is, still, the computational complexity of the problem.

Edit: you can assume for simplicity that there exists a subcube with $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.2$ (notice the gap: we're looking for a subcube with average $\ge 0.1$.) I'm pretty sure any solution to the problem with the gap will also solve the problem without the gap.

Here is a better bound on the sample complexity. (Although the computational complexity is still $n^k$.)

Theorem. Assume there exists a subcube $S$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S}[f(x)]| \geq 0.12$. With $O(2^k \cdot k \cdot \log n)$ samples we can, with high probability, identify a subcube $S'$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S'}[f(x)]| \geq 0.1$.

Note the small loss in parameters ($0.12$ is optimal versus guarantee of $0.1$).

Proof. Pick $m$ points $P \subset \{0,1\}^n$ uniformly at random and query $f$ at each $x \in P$.

Fix a subcube $S$ of size $2^{n-k}$. We have $\mathbb{E}[|S \cap P|]=m 2^{-k}$. By a Chernoff bound, $$\mathbb{P}[|S \cap P| < m 2^{-k-1}] \leq 2^{-\Omega(m 2^{-k})}.$$ Also $$\mathbb{P}[| \mathbb{E}_{x \in S \cap P}[f(x)] - \mathbb{E}_{x \in S}[f(x)] | > \varepsilon] \leq 2^{-\Omega(|S \cap P| \varepsilon^2)}.$$

By a union bound over all ${n \choose k}2^k$ choices of $S$, we have $$\mathbb{P}[\forall S ~~ | \mathbb{E}_{x \in S \cap P}[f(x)] - \mathbb{E}_{x \in S}[f(x)] | \leq \varepsilon] \geq 1 - {n \choose k} 2^k 2^{-\Omega(m 2^{-k} \varepsilon^2)}.$$ So by picking $m = O(2^k/\varepsilon^2 \cdot k \log n)$, we can ensure that, with probability at least $0.99$, we can estimate $\mathbb{E}_{x \in S}[f(x)]$ to within $\varepsilon$ for all subcubes $S$ of size $2^{n-k}$.

Setting $\varepsilon=0.01$, we prove the theorem: picking the subcube with the largest $| \mathbb{E}_{x \in S \cap P}[f(x)]|$ will, with high probability, satisfy the requirements. Q.E.D.