How do I choose a functional dictionary data structure? I've read a bit about the following data structures:

Bagwell's Ideal Hash Tries
Larson's Dynamic hash tables
Red-Black trees
Patricia trees

...and I'm sure there are a lot of others out there.  I've seen very little in the way of what each one is better suited for, or why I would choose one over another.  So, here are a few questions along these lines:

What functional dictionary data structures are important to know about?
What are the pros and cons of these approaches?
When does it make sense to use a more imperative data structure?

Numbers 2 & 3 are the more important ones though.  :-)

I can't really answer #2 without getting lost (there are too many dimensions along which you can compare these structures), but for #3 the answer is pretty simple.

Use an imperative data structure if: (a) there is absolutely no aliasing, or (b) you really need to use aliasing for efficient broadcast.

If there is no aliasing of your data structure at all, then you are not taking advantage of the fact that functional data structures are persistent. So there is no reason to pay for their cost. There are two caveats to this advice. First, you may prefer the simplicity of implementation of a functional data structure: implementing deletion for a functional red-black tree will make you curse, but implementing deletion in an imperative red-black tree with parent pointers will leave you contemplating suicide. Second, assignment can be more expensive than you expect in a gc'd language, since writes can get data structures moved out of the young generation. We really don't have a good theory of cache effects and gc, so you have no choice but to do benchmarking.

Second, if you need a broadcast channel, then a shared data structure is an excellent way to do it. With a constant-time update, you can tell arbitrarily many other people that a value has changed. (This is why union-find is such a great data structure.) With a purely functional setup, either you need to modify all those other people, or give them abstract pointers into a state you code up manually (which is a kind of obtuse thing to do).

If you either don't want to reason about aliasing and object ownership, or if you need multiple versions of the same data structure (you need both a new and an old version, say), then just use a functional data structure.

The place where I find following this advice the hardest is with graph algorithms. There are lots of really elegant imperative graph algorithms, but it's often the case (say, when writing compilers) that you also want persistence. People typically try to split the difference and use the cool imperative algorithm but try to bolt versioning onto the side to get persistence. This is generally pretty horrible, full of bugs, and prone to losing the performance advantage of the imperative algorithm.


Evaluating the multilinearization of an arithmetic circuit? Let $p(x_1,\ldots,x_n)$ be a multi-variate polynomial with coefficients over a field $F$. The multilinearization of $p$, denoted by $\hat{p}$, is the result of repeatedly replacing each $x_i^d$ with $d > 1$ by $x_i$. The result is obviously a multilinear polynomial.

Consider the following problem: given an arithmetic circuit $C(x_1,\ldots,x_n)$ over $F$ and given field elements $a_1,\ldots,a_n$, compute $\hat{C}(a_1,\ldots,a_n)$.

Question: Assuming field-arithmetic can be done in unit time, is there a polynomial-time algorithm for this? Added later: I would also be interested in the special case where $C$ is actually a formula (a circuit of fan-out $1$).

In the case that the field $F$ is of size at least $2n$, I think this problem is hard. More specifically, I think that if the above can be efficiently solved for $F$ this large, then CNF-SAT has efficient randomized algorithms. Say we are given a CNF formula $\varphi$. One can easily come up with an arithmetic circuit $C$ that computes an ``arithmetization'' $p$ of $\varphi$, where the polynomial $p$ agrees with the formula $\varphi$ on $0$-$1$ inputs. Consider the multilinearization $q$ of $p$. Note that $q$ agrees with $p$ and hence $\varphi$ on $\{0,1\}^n$.

I claim that $q$ is non-zero iff $\varphi$ is satisfiable. Clearly, if $q=0$, then $\varphi$ cannot be satisfied. For the converse, one can show that any non-zero multilinear polynomial cannot vanish on all of $\{0,1\}^n$. This implies that a non-zero $q$ (and hence the corresponding $\varphi$) does not vanish at some input in $\{0,1\}^n$.

Therefore, checking for satisfiability of $\varphi$ is equivalent to checking if $q$ is non-zero. Say, now, that we could evaluate $q$ over a large field $F$. Then, using the Schwartz-Zippel Lemma, we could identity-test $q$ using an efficient randomized algorithm and check if it is the zero polynomial (the size of $F$ is used to upper bound the error in the Schwartz-Zippel Lemma).


About the decidability of sets enumerated in non decreasing order It is well known that a set of numbers enumerable in nondecreasing order is
decidable. However, the typical proof, by cases on the finiteness of the
enumerated set, is not constructive. In general, it does not seem possible
to effectively derive the decider from the enumeration function (and its properties): can this be proved?

Here is a possible formalization of the problem. Let $\varphi$ be an effective enumeration of all computable functions.
Let $c_A$ be the characteristic function of $A$, Let $f$ be a function such that

$$\varphi_{f(i)} =
\begin{cases}
c_{cod{(\varphi_i})} & \mbox{if $\varphi_i$ is total and non decreasing}\\
                 \mbox{arbitrary} & \mbox{otherwise}
\end{cases}
$$
Prove that no such $f$ is computable (or that it is indeed computable).

Suppose there were a computable $f$ as described in the question. Then we could solve the Halting problem as follows.

Given a Turing machine $T$, consider the computable function $g$, defined by
$$g(k) = \begin{cases}
1 & \text{if $T$ halts in $\leq k$ steps} \\
0 & \text{otherwise}
\end{cases}$$
This is a computable, nondecreasing and total function. Therefore, we may use $f$ to establish that the range of $g$ is decidable. But now we just check whether $1$ is in the range to figure out whether $T$ halts.

Notice that I never used the finite/infinite distinction. The above argument works even if we assume that $f$ enumerates a finite set. Are you sure you got your theorem correct? The one I know says that an infinite set is decidable if it can be enumerated by a computable strictly increasing function. There is of course another theorem stating that every finite set can (obviously) be enumerated in increasing order.

Supplemental: Let us look at the matter from a constructive point of view. We have two constructive theorems, assuming Markov principle (which is generally used in computability theory):

  Theorem 1: If a finite set can be enumerated in non-decreasing order then it is decidable.

(A set is said to be finite if it is isomprhic to $\{0, 1, \ldots, n-1\}$ for some $n \in \mathbb{N}$, so the extra conditions in the theorem does not actually help, as every finite set is decidable.)

  Theorem 2: If a non-finite set can be enumerated in non-decreasin order then it is decidable.

However, we cannot just stick these two together into "any set enumerated in increasing order is decidable" because the following is not a constructive theorem:

  Theorem (classical): Every set is finite or non-finite.

In fact, in computability theory there are counter-examples. An immune set is infinite, but it does not contain any infinite computable sequence.


Testing for positivity instead of equality Alice and Bob have n-bit strings, and want to figure out if they're equal while doing little communication. The standard randomized solution is to treat the n-bit strings as polynomials of degree $n$ and then evaluate the polynomials over a few randomly chosen elements from a field of size larger than $n$. This takes $O(\log |F|)$ communication.

Suppose instead that we fix a lexicographic ordering over the strings and want instead to determine which string is "larger", which is equivalent to finding the leftmost bit where the strings differ.

  Is there a similar randomized protocol for doing this, or a known
  lower bound ? This seems to relate to testing positivity of
  polynomials.

p.s While lexicographic order seems like the most obvious, I'm fine with other orderings: for the purpose I'm interested in, all we need is some order.

This is known as Greater-Than problem in communication complexity. An algorithm with $O(\log n) $ communication complexity exists (Exercise 3.18 in Nisan-Kushilevitz book).

Edit: The algorithm is due to Nisan (page 10): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf

It uses the approach suggested by @Sasho Nikolov below --- running a binary search using equality tests with constant error to do the comparisons. This can be done with $O(\log n)$ queries using the "noisy binary search algorithm" by Feige, Peleg, Raghavan and Upfal: http://cs.brown.edu/~eli/papers/SICOMP23FRPU.pdf

To get a (non-explicit) private randomness protocol one can apply the result of Newman: http://pdf.aminer.org/000/933/113/private_vs_common_random_bits_in_communication_complexity.pdf


Intractability of NP-complete problems as a principle of physics? I'm always intrigued by the lack of numerical evidence from experimental mathematics for or against the P vs NP question. While the Riemann Hypothesis has some supporting evidence from numerical verification, I'm not aware of similar evidence for the P vs NP question.

Additionally, I'm not aware of any direct physical world consequences of the existence of undecidable problems (or existence of uncomputable functions). Protein folding is NP-complete problem but it appears to be taking place very efficiently in biological systems. Scott Aaronson proposed using the NP Hardness Assumption as a principle of physics. He states the assumption informally as "NP-complete problems are intractable in the physical world".

  Assuming NP Hardness Assumption, Why is it hard to design a scientific experiment that decides whether our universe respects the NP Hardness Assumption or not?

Also, Is there any known numerical evidence from experimental mathematics for or against $P\ne NP$?

EDIT: Here is a nice presentation by Scott Aaronson titled Computational Intractability As A Law of Physics

I don't think that the fact that $P\neq NP$ is an asymptotic statement is an automatic "dealbreaker". One can make concrete conjectures that are consistent with our knowledge but stronger than P vs NP such as "It takes at least $2^{n/10}$ steps to find a satisfying assignment for a random n variable 10SAT formula" (with "random" being e.g., the planted model of Achlioptas Coja-Oghlan, this is just an example - I don't know what are reasonable concrete numbers offhand).

Such conjecture can result in a refutable prediction that any natural system that will try to solve this will fail (e.g., get stuck in a local minima), something you can verify with experiments. Indeed, I'm not an expert on this but to my knowledge, as Joe Fitzsimons mentioned, such predictions had been confirmed with Adiabatic computing. (Scott Aaronson also had some entertaining experiments with soap bubbles.)

Of course you can also see some "empirical evidence" for $P \neq NP$  in the fact that people have been trying to solve optimization problems, cryptoanalyze encryptions, etc.. and haven't been successful so far...


Books on automata theory for self-study I need a finite automata theory book with lots of examples that I can use for self-study and to prepare for exams.

The classical reference is "Introduction To Automata Theory, Languages and Computation" (by Hopcroft, Motwani, and Ullman). Some people also recommend the much older "Formal Languages and Their Relation to Automata" (by Hopcroft and Ullman).

I, however, like "Introduction to the Theory of Computation" (by Sipser). It is very well written, and is a relatively new book.


Does coNP-complete problem have subexponential size certificate? Assuming NP != coNP, then there is no polynomial size certificate for coNP-complete problem. But what about subexponential size certificate? Particularly for coSAT, is there subexponential size proof to prove a formula is unsatisfiable? If not, what is the negative evidence? Thanks

This is the topic of proof complexity, i.e. the size of certificates for the $\mathbf{co\text{-}NP}\text{-}complete$ problem $TAUT$ ($= coSAT$).

The short answer is: it is open.

On the negative side, we cannot even show that there are not polysize $Frege$ refutations for unsatisfiable formulas (let alone the general question of showing this for an arbitrary proof system, a propositional proof system can be thought as a nondeterministic algorithm for $TAUT$).

The question is also equivalent to $\mathbf{coNP} \subseteq NTime(2^{o(n)})$.


Is there a concept of something like co-applicative functors sitting between comonads and functors? Any monad is also an applicative functor and any applicative functor is a functor. Also, any comonad is a functor. Is there a similar concept between comonads and functors, something like co-applicative functor, and what are its properties?

\begin{array}{c}
\end{array}
\begin{array}{cc}
\mbox{Functors} & & \mbox{Functors} \\
\uparrow & & \uparrow \\
\mbox{Applicative functors} & & ??? \\
\uparrow & & \uparrow \\
\mbox{Monads} & & \mbox{Comonads} \\
\end{array}

Update: I'd be also interested in possible uses of such a concept.

First of all:

  Any monad is also an applicative functor and any applicative functor is a functor.

This is true in the context of Haskell, but (reading Applicative as "strong lax monoidal functor") not in general, for the rather trivial reason that you can have "applicative" functors between different monoidal categories, whereas monads (and comonads) are endofunctors.

Further, identifying Applicative with strong lax monoidal functors is slightly misleading, because to justify the name (and the type signature of (<*>)) requires a functor between closed monoidal categories which preserves both the monoidal structure and the internal hom. This could plausibly be called a "lax closed monoidal functor", except that a functor between monoidal closed categories that preserves either property preserves the other in the obvious way. Because Applicative describes only endofunctors on Hask preserving the monoidal structure of (,), its instances gain a lot of properties automatically, including their strength, which can thus be elided.

The apparent connection with Monad is arguably an artifact of the implicit limitations on Applicative causing aspects of their respective monoid structures to coincide, a happy coincidence which unfortunately does not survive dualization.

Just as a comonad on a category $C$ is a monad on $C^{op}$, an oplax monoidal functor $C \rightarrow D$ is a lax monoidal functor $C^{op} \rightarrow D^{op}$. But $ \boldsymbol{Hask}^{op}$ is not monoidal closed, and a co-Applicative that doesn't include function application hardly merits the name. Anyway, the result wouldn't be terribly interesting:

class (Functor f) => CoMonoidal f where
    counit :: f () -> ()
    cozip :: f (a, b) -> (f a, f b)

We could instead imagine a notion of "colax closed functor", which would look much more like Applicative if it existed. Unfortunately, $\boldsymbol{Hask}^{op}$ is not (to the best of my knowledge) a closed category at all: newtype Op b a = Op (a -> b) in $\boldsymbol{Hask}$ corresponds to morphisms $b \rightarrow a$ in $\boldsymbol{Hask}^{op}$, but Op b a doesn't work as an internal hom there--because the arrows are reversed some sort of co-function would be required instead, which we can't define in general for $\boldsymbol{Hask}$.

If we simply pretend that "colax closed functors" existed for $\boldsymbol{Hask}$, and furthermore worked in the way we'd naively hope they would, a co-Applicative based on that would probably look like this:

class (Functor f) => CoApplicative f where
    copure :: f a -> a
    coap :: (f a -> f b) -> f (a -> b)

Adding duplicate :: f a -> f (f a) to copure would produce a comonad (assuming the laws are satisfied), of course. But there's no obvious relationship between coap--whatever it might be--and extend :: (f a -> b) -> f a -> f b. Comparing the types it becomes clear that the dualization is happening in different ways: the comonoidal structures underlying duplicate and cozip have little to do with each other or with coap (which probably doesn't make sense anyway), whereas liftA2 (,) and (<*>) are equivalent and can be derived from join.

Another possible way of dualizing Applicative, which has even less to do with comonads, is to consider contravariant monoidal functors:

class (Contravariant f) => ContraMonoidal f where
    contraunit :: f a
    contrazip :: f a -> f b -> f (Either a b)

But this runs afoul of the same issues as above, namely that $\boldsymbol{Hask}^{op}$ is not a closed category. If it were, we would have some type b <~ a such that we could write functions like contracurry :: (Either c b <~ a) -> (c <~ (b <~ a)) and contraapply :: b -> Either a (a <~ b) and so on that actually worked as expected.

If memory serves me, the obstacles here are not specific to Haskell, but rather arise from $\boldsymbol{Hask}$ being cartesian closed (up to the usual hand-waving, of course), a property it shares with most typed lambda calculi, so you're not likely to get very far with a CoApplicative in most settings.

However, in a monoidal closed category more hospitable to dualization you might have better luck. In particular, I believe both Kleisli (Cont r) and its opposite category are monoidal closed, so that might be a better context to explore these ideas.


2D grid placement problem Data for the problem:

2D grid(lattice) of size NxN
n nodes placed on the grid:node_1,node_2,…node_n
Each of nodes contain some data:

a.   node_i is presented by 3 parameters (x_i,y_i,t_i)

b.       x_i and y_i represent the coordinates on the grid

c.       t_i represent the time when the node`s data  is ready
Given a node_(n+1) and t_(n+1)  I should find x_(n+1) and y_(n+1):
Such that, if  we define l_i  = (x_(n+1)-x_i) +( y_(n+1)-y_i) ,
For  every 1<=i<=n the will take place t_i + l_i <= t_(n+1)
If the above is impossible the max( t_(n+1) – (t_i + l_i)) should be minimized

For example please take a look for the following examples when n = 2

Node_1 :x_1 = 0,y_1 = 0,t_1 =1

Node_2 :x_2 = 4,y_2= 3,t_2 = 4

Node_2 :x_3 =?,y_3 = ?,t_3 = 6

-> x_3 = 3?,y_3= 2

Node_1 :x_1 = 0,y_1 = 0,t_1 =0

Node_2 :x_2 = 4,y_2= 4,t_2 = 0

Node_2 :x_3 =?,y_3 = ?,t_3 = 4

-> x_3 = 2?,y_3= 2

I need general algortithm for finding x_(n+1) and y_(n+1).Does anyone have some clue how to solve such a problem.
Thank you.

If I understand your problem correctly, it seems like you're looking to examine a furthest-point weighted Voronoi diagram under the Manhattan ($\ell_1$) distance. The transformation is as follows.

For each point $p_i$ on the grid, define the distance function $$d_i(x) = \max(0, \|x - p_i\|_1 - (t_{n+1}-t_i))$$ Then $d_i(x)$ is the (truncated) distance of $x$ from the ball of radius $t_{n+1}-t_i$ around $p_i$ under the $\ell_1$ distance.

You want to find
$$ x^* = \arg \min \max_i \ d_i(x) $$
which can be obtained by computing the furthest-point weighted Voronoi diagram under the $\ell_1$ distance (the weighted part is because of the offset associated with the $t_i$).

If you want code, then I'm not sure where you might find it, but this site has an amazing collection of Voronoi demos written in Java (including furthest point Manhattan distance) and you might be able to adapt it for for your needs.


Randomized Algorithm with random input As per the Yao's principle, in order to lower bound the cost of Randomized algorithm it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm can perform well against that distribution.

Suppose we have a boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$ and we are given a distribution over the inputs. I would like to ask whether I can apply Yao's principle when there is already some distribution given over inputs? If yes, then how?

I was reading the paper by Scott Aaronson and could not understand why he simply stated that by Yao's principle we can assume that algorithm is deterministic while there was already a distribution given over the inputs.

As you said, it is enough to point out a distribution (this could be any distribution) on which every deterministic algorithm fails. Now, if there is already a distribution given, and you can show that any deterministic algorithm fails on this one, then this provides also a lower bound for randomized algorithms. You can use any distribution in order to apply Yao's principle.


The use of crossovers in Genetic Algorithm My questions concern the use of crossovers in genetic algorithms. The three basic ingredients of genetic algorithms are:

selection
mutation
crossover

If we think of genetic algorithm acting on binary strings…

Crossover is the process by which two parent strings get mixed to give born to offspring strings. For example: 11000 and 00010 can create the offspring 11010 by crossover only.

In some genetic algorithm people authorize double-crossover. For example the two parents: 110011 and 001100 can give birth to 111111.

I don't fully understand the advantageous of crossovers! It seems to me that one can obtain similar results with algorithms that do not contain crossover.

My questions

Under what conditions is the use of crossover in genetic algorithm beneficial? why?
Under what conditions is the use of double-crossover more beneficial than single crossover? why? What about triple crossover?

When I say "Under what conditions", I mean "for what fitness landscape" or "for what problem type".

By fitness landscape, I mean a mapping of each possibility to fitness (reproductive success) in a hyperspace of $n+1$ dimensions where $n$ is the length of the string (the additional dimension being the fitness).

If crossover is excluded from genetic algorithms, they become something between the gradient descent and the simulated annealing. The main effect of crossover consists in the exchange of parts of different solutions.  If an optimization task can be loosely decomposed into somewhat independent subtasks, and this decomposition is reflected in genes, then crossover will increase performance of GAs. For example, if there is a function f(x,y)=g(x)+h(y), and x and y are encoded consequently in the genome, and e.g. g(x) has larger influence, then the part of genome that stands for x will be optimized in the first place, and it will become nearly the same for the whole population thanks to crossover. After this, h(y) term will be optimized. That is, crossover helps to loosely decompose the task into subtasks without prior knowledge (but dependent on the encoding scheme), if it is possible (otherwise it will yield no benefit, or even will make search less efficient). This is actually the main additional metaheuristic of GAs in comparison with other metaheuristic optimization methods.

Double-point crossover (or other more “clutter” types of crossover) can be more beneficial, if the most crucial parts of solutions are encoded in the middle of the genome or if they are placed in separate locations. The simplest example is the function f(x,y,z)=h(x,z)+r(y)+g(z), where h(x,z) has the highest influence, and genes encode the string xyz. Single-point crossover will prefer to take x from one parent, and z from another parent. However, (x,z) determine the solution quality together. If one individual will occasionally have optimal components (x*,z*), they will not appear simultaneously in its children after single-point crossover, so it will be more difficult for these parts of the genome to stabilize.


Computing the Löwner-John ellipsoid of a polyhedron The Löwner-John ellipsoid of a convex set $C$ is the minimum-volume ellipsoid (MVE) that encloses it. The ellipsoid can be computed using Khachiyan's method, and there are a number of approximations available if $C$ is (the convex hull of) a set of points.

Are there fast (i.e non-ellipsoid-method based) approximations to the MVE of a bounded polyhedron presented only in terms of the halfplanes whose intersections define it ? In particular, I'd be interested in methods that run in time polynomial in the dimension and the inverse error $1/\varepsilon$.

According to Boyd, it's NP-hard: http://youtu.be/mNzu42FrlHo?t=41m3s


Curious about computer-assisted NP-completeness proofs In the paper "THE COMPLEXITY OF SATISFIABILITY PROBLEMS" by Thomas J. Schaefer, the author has mentioned that

This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity could be explored with the help of a computer. The computer would be instructed to randomly generate various input configurations and test whether the defined relation was non-affine, non-bijunctive, etc.

Of course, this is a limitation:

The fruitfulness of such an approach remains to be proved: the enumeration of the elements of a relation on lO or 15 variables is Surely not a light computational task.

I am curious that

  Are there follow-up researches in developing this idea of "computer-assisted NP-completeness proofs"? What is the state-of-the-art (may be specific to $\textsf{3SAT}$ or $\textsf{3-Partition}$)?
  Since Schaefer has proposed the idea of "computer-assisted" NP-Completeness proof (at least for reductions from $\textsf{SAT}$), does this mean there are some general principles/structures underlying these reductions (for the ones from $\textsf{3SAT}$ or $\text{3-Partition}$)? If so, what are they?
  Does anyone have experience in proving NP-completeness with a computer-assistant? Or can anyone make up an artificial example?

As for question 2, there are at least two examples of $NP$-completeness proofs that involve computer-assistant.

Erickson and  Ruskey provided a computer-aided proof that Domino Tatami Covering is NP-complete. They gave a polynomial time reduction from planar 3-SAT to tatami domino covering. A SAT-solver (Minisat) was used to automate gadgets discovery in the reduction. No other $NP$-completeness proof is known for it.

Ruepp and Holzer proved that pencil puzzle Kakuro is $NP$-complete. Some parts of the $NP$-completeness proof were generated automatically using a SAT-solver ( again Minisat).


Max-Cut algorithm that shouldn't work, unclear why OK, this might seem like a homework question and, in a sense, it is. As a homework assignment in an undergraduate algorithms class, I gave the following classic:

Given an undirected graph $G=(V,E)$, give an algorithm that finds a cut $(S,\bar{S})$ such that $\delta(S,\bar{S})\geq |E|/2$, where $\delta(S,\bar{S})$ is the number of edges crossing the cut. Time complexity must be $O(V+E)$.

For some reason, I got a lot of the following solution. Now, it does use too much time, so it's not a matter of grading, but I got curious. It doesn't "seem" correct, but all my attempts at counterexamples have failed. Here it is:

Set $S\leftarrow \emptyset$
Let $v$ be a max degree vertex in the graph
Add $v$ to $S$
Delete all edges adjacent to $v$
If $\delta(S,\bar{S}) < |E|/2$ return to 2

Note that $E$ in step 5 refers to the original graph. Also note that had we skipped step 4, this would obviously be wrong (for example the union of a triangle with two isolated edges).

Now, any simple proof has the following problem - it might be that when we add a new vertex $v$ we actually remove $|S|$ edges from the cut while adding $d(v)$ new edges (where $d(v)$ refers to the graph with edges deleted). The thing is, that if this is detrimental to our cause, it means that this vertex $v$ "used to" have an ever higher degree, so it "should have been" selected earlier.

Is this a well known algorithms? Is there some simple counterexample for it?

My earlier claim of $\frac{2}{c+6}$ did not take into account the cut of size $n^2/4$ already present in the graph. The following construction appears to result (emperically - I have created a question at math.stackexchange.com for a rigorous proof) in a $O\left(\frac{1}{\log c}\right)$ fraction.

The algorithm performs badly on unions of several disconnected, differently sized complete graphs. We denote the complete graph on $n$ vertices as $K_n$. Consider the behavior of the algorithm on $K_n$: it repeatedly adds an arbitrary vertex not yet in $S$ to $S$ - all such vertices are identical and so the order does not matter. Setting the number of vertices not yet added to $S$ by the algorithm $|\bar{S}| = k$, the size of the cut at that moment is $k (n-k)$.

Consider what happens if we run the algorithm on several disconnected $K_{x_i n}$ graphs with $x_i$ constants between 0 and 1. If $k_i$ is the number of elements not yet in $S$ in the $i$th complete graph, then the algorithm will repeatedly add a vertex to $S$ from the complete graph with highest $k_i$, breaking ties arbitrarily. This will induce `round' based additions of vertices to $S$: the algorithm adds a vertex from all complete graphs with the highest $k = k_i$, then from all complete graphs with $k_i=k-1$ (with $k_i$ updated after the previous round), and so on. Once a complete graph has a vertex added to $S$ in a round, it will do so for every round from then on.

Let $c$ be the number of complete graphs. Let $0 < x_i \leq 1$ with $0 \leq i \leq c - 1$ be the size modifier for the $i$-th complete graph. We order these size modifiers from large to small and set $x_0 = 1$. We now have that if there are $c'$ graphs with exactly $k$ elements not yet added to $S$, then the size of the cut at that time is $\sum_{i=0}^{c'-1} k (x_i n - k) = k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$. The total number of edges is $|E| = \sum_{i=0}^{c-1} \frac{x_i n (x_i n - 1)}{2} \approx \frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2$.

Note that $k n \sum_{i=0}^{c'-1} x_i - c' k^2$ is a quadratic function in $k$ and hence has a maximum. We will therefore have several locally maximal cuts. For example, if $c=1$ our maximal cut is at $k=\frac{n}{2}$ of size $\frac{n^2}{4}$. We are going to pick $x_1$ so that $x_1 = 1/2 - \varepsilon$, which means the second complete graph will not change the size of this locally maximal cut at $k=\frac{n}{2}$. We then get a new locally maximal cut at $k=3/8 n - \varepsilon'$ and so we pick $x_2 = 3/8 n - \varepsilon''$ (with $\varepsilon, \varepsilon', \varepsilon''$ small constants). We will ignore the $\varepsilon$s for the moment and just assume we can pick $x_1 = 1/2$ - we should ensure $x_1 n = \frac{n}{2} - 1$, but this will not affect the final results if $n$ is large enough.

We wish to find the local maxima of our cuts. We differentiate $k n \sum_{i=0}^{c'-1} (x_i) - c' k^2$ to $k$, yielding $n \sum_{i=0}^{c'-1} (x_i) - 2 c' k$. Equating to $0$ gives $k = \frac{n}{2c'} \sum_{i=0}^{c'-1} x_i$, which gives a cut of size $\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$.

Let $k_i$ be the $k$ determined in the previous paragraph if $c'=i$. We will ensure that the formula holds by demanding that $x_i n < k_i$ - all complete graphs $i'$ with $i'>i$ are then smaller than the $k_i$ of this locally maximal cut and hence do not increase the size of the cut. This means we have $c$ cuts at these $k_i$ that are larger than all other cuts found by the algorithm.

Filling in $x_i n < k_i$, we get the recurrence $x_i = \frac{1}{2c'} \sum_{i=0}^{c'-1} x_i$ (plus some small $\varepsilon$) with $x_0 = 1$. Solving this yields $x_i = \frac{\binom{2i}{i}}{4^i}$: see my question on math.stackexchange.com for the derivation by @Daniel Fisher. Plugging this into $\frac{n^2}{4c'} \left(\sum_{i=0}^{c'-1} x_i\right)^2$ and using our insight into the recurrence gives us cuts of size $\frac{n^2}{4c'} \left(2c' \frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = n^2 c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2$. Using properties of this central binomial coefficient, we have $\lim_{c' \to \infty} c' \left(\frac{\binom{2c'}{c'}}{4^{c'}}\right)^2 = \frac{1}{\pi}$ (also see my question on math.stackexchange.com).

The number of edges is approximately $\frac{n^2}{2} \sum_{i=0}^{c-1} x_i^2 = \frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{\binom{2i}{i}}{4^i}\right)^2$. By known properties we have $\frac{1}{\sqrt{4i}} \leq \frac{\binom{2i}{i}}{4^i}$. Filing in gives at least $\frac{n^2}{2} \sum_{i=0}^{c-1} \left(\frac{1}{\sqrt{4i}}\right)^2 = \frac{n^2}{8} \sum_{i=0}^{c-1} \frac{1}{i}$ which is asymptotically $\frac{n^2}{8} \log c$ as $c$ goes to infinity.

We therefore have $\frac{\delta(S, \bar{S})}{|E|}$ is asymptotically equal to $\frac{8}{\pi \log c}$ as $c$ goes to infinity, showing that the algorithm can return cuts that are arbitrarily low fractions of $|E|$.


Highest lower bound on NP problems (TSP) I'll try another question that I haven't been able to find almost any kind of information about, thanks a lot for any kind of pointers or explanations.

Is there a list of the proven lower bounds of NP algorithms (particularly for the TSP problems)?

Like one might imagine that someone already has proven 3SAT to run at at least 2n² for example.

Thanks again

The best known lower bounds for TSP are essentially the same as those for 3SAT (within polylogarithmic factors), and they apply the fact that there are very efficient reductions from 3SAT to Hamiltonian Path. (So, a good algorithm for Hamiltonian path would imply one for 3SAT, but certain lower bounds show that sufficiently good algorithms don't exist for 3SAT.)

For the best 3SAT lower bounds known, see this answer. The bottom line is that the only non-trivial lower bounds known for these problems impose a space restriction on the candidate algorithm, as well as a time restriction. So for example, we can say TSP cannot be solved in $n^{1.5}$ time and $O(log n)$ space, but we don't know if TSP can be solved in $n^{1.5}$ time (with no space restriction).


Generating a tower defense maze, aka Finding the K most vital nodes ("nodewise interdiction") in an unweighted grid-graph In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls.

Enemies take the shortest path from start to finish without passing through any walls (they aren't usually constrained to the grid, but for simplicity's sake let's say they are.  In either case, they can't move through diagonal "holes")

The problem (for this question at least) is to place up to K additional walls to maximize the path the enemies have to take, without completely blocking start from the finish.  For example, for K=14

I've determined that this is the same as the "k most vital nodes" problem:

  Given an undirected graph G = (V,E) and two nodes s,t ∈ V, the k-most-vital-nodes are the k nodes whose removal maximizes the shortest path from s to t.

Khachiyan et al1 showed that, even if the graph is unweighted and bipartite, even approximating the length of the max-shortest-path within a factor of 2 is NP-Hard (given k,s,t).

All is not lost, however:  later, L. Cai et al2 showed that, for "bipartite permutation graphs" this problem can be solved in pseudo-polynomial time using the "intersection model."

I haven't been able to find anything on unweighted grid-graphs specifically, and I can't figure how "bipartite permutation graphs" are related, if at all.  Has there been any research published relating to my problem - maybe I am looking in the completely wrong place?  Even a decent pseudo-polynomial approximation algorithm would work well.  Thanks!

1 L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf and J. Zhao "On Short Path Interdiction Problems: Total and Node-Wise Limited Interdiction," Theory of Computer Systems 43 (2008), 2004-233.  link.
2 L. Cai and J. Mark Keil, "Finding the k most vital nodes in an interval graph."  link.

Note: this question is a follow-up to my stackoverflow question found here.

This appears to be NP-complete by a reduction from Hamiltonian cycle in planar graphs of degree at most three. Hamiltonian cycle should still be hard in planar graphs of degree at most three that contain two adjacent degree-two nodes (this is the part I haven't checked very carefully). Embed the given planar graph into the grid in such a way that each vertex becomes a grid point, each edge becomes a grid path, and all edges have the same length $\ell$ (pad the shorter ones by zigzagging if necessary to achieve this). Let $s$ and $f$ be two adjacent degree-two nodes. Include walls in the initial placement of walls so that only the vertices and edges of the embedding remain available to connect $s$ to $f$. Let $n$ and $m$ be the numbers of vertices and edges in the original graph. Then, the original graph has a Hamiltonian cycle if and only if it is possible to place $m-(n-1)$ more walls in such a way that the new shortest path from $s$ to $f$ has length $(n-1)l+(n-2)$. A path of that length must be a Hamiltonian path in the original graph which together with the edge from $s$ to $f$ forms a Hamiltonian cycle, and conversely if the graph contains a Hamiltonian cycle then you can force the path from $s$ to $f$ to be that long by placing a wall in each other edge.


Space-time tradeoff lower bounds Following the discussion on lower bounds for 3SAT [1], I'm wondering what are the main lower bound results formulated as space-time tradeoffs.  I'm excluding results such as, say, Savitch's theorem; a good entry would focus on a single problem and its bounds.  An example would be :
"Let T and S be the running time and space bound of any SAT algorithm. Then we must have T⋅S≥n2cos(π/7)−o(1) infinitely often." (Given in [1] by Ryan Williams.)
or
"SAT cannot be solved simultaneously in n1+0(1) time and
n1-ε space for any ε>0 on general
random-access nondeterministic Turing machines." (Lance Fortnow in 10.1109/CCC.1997.612300)
Further, I'm including definitions of natural space-time tradeoff complexity classes (excluding circuit classes).

Here are a few additional references. More can be found by looking at the papers that cite these.

Duris and Galil (1984) give a language in $P$ which requires $T^2 S \geq \Omega(n^3)$ on one-tape Turing machines with any constant number of read-write heads. Karchmer (1986) showed that the same lower bound holds for the element distinctness problem.

Babai, Nisan, and Szegedy (1989) give a very natural language (generalized inner product) that is solvable in $O(n)$ time and $O(1)$ space on a $k+1$-head one-tape Turing machine, that requires $T S \geq \Omega(n^2)$ on any $k$-head one-tape Turing machine.

Ajtai (1999) shows time-space tradeoffs for deterministic random access machines computing element distinctness. In particular if $S \leq o(n)$, then $T \geq \omega(n)$. Subsequent work by Beame, Saks, Sun, and Vee (2000) proves time-space tradeoffs for randomized computations.

Santhanam (2001) showed that $TS \geq \Omega(n^2)$ holds for multitape Turing machines solving SAT, building on Cobham's analogous lower bound for PALINDROMES.


Why non-uniform learnability does not imply PAC learnability? PAC guarantees provide us a a learning algorithm $A_n(\cdot)$ and sample complexity bound $n_{\mathcal{F}}(\epsilon,\sigma)$ that ensures
$
P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\geq 1-\sigma
$
when $n>n_{\mathcal{F}}(\epsilon,\sigma)$.

On the other hand we say that the hypothesis class $\mathcal{F}$ is non-uniformly learnable if we can provide a sample complexity $n_{\mathcal{F}}(\sigma,\epsilon,f)$ and a learning algorithm $A(\cdot)$, such that
$
P\left[L_P(A(\mathcal{D}^n))-L_P(f)\leq \epsilon\right]\geq 1-\sigma
$ when $n>n_{\mathcal{F}}(\sigma,\epsilon,f)$.

Non-uniform learnability is a relaxation of PAC learnability since
$
P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\geq 1-\sigma \implies P\left[L_P(A(\mathcal{D}^n))-L_P(f)\leq \epsilon\right]\geq 1-\sigma
$
but the contrary is not true, namely $\mathcal{F}$ may be non-uniform learnable but not PAC learnable. My question is, if we are given a non-uniformly learnable class $\mathcal{F}$ and we define $n_{\mathcal{F}}(\sigma,\epsilon)=\sup_{f \in \mathcal{F}} n_{\mathcal{F}}(\sigma,\epsilon,f)$, does it become PAC learnable? or the supremum over an uncountable set nullifies the implication? Making the complexity bound vacuous?

Thanks for any clarification

The following answer is based on chapter 6/7 of the book »Understanding Machine Learning: From Theory to Algorithms«, by Shalev-Shwartz and Ben-David (especially Example 7.1).

It states that the class $\mathcal{H}$ of all polynomial classifiers over $\mathbb{R}$ is not PAC learnable ($\mathrm{VCdim}(\mathcal{H}) = \infty$). We might rewrite $\mathcal{H}$ as $\bigcup_{n \in \mathbb{N}} \mathcal{H}_n$, where for every $n \in \mathbb{N}$, $\mathcal{H}_n$ is the class of all polynomial classifiers over $\mathbb{R}$ of degree $n$.

Each $\mathcal{H}_n$ is PAC learnable with $\mathrm{VCdim}(\mathcal{H}_n) = n + 1$, so using the fundamental theorem of statistical learning (quantified version), we know that the sample complexity of each $h \in \mathcal{H}_n$ is in $\Theta\left(\frac{(d + 1) + \log(1 / \delta)}{\epsilon^2}\right)$, so strictly increasing in $d$, but finite.

So for $0< \epsilon, \delta < 1$, the set $\{ n_{\mathcal{H}}(\epsilon, \delta, h) \mid h \in \mathcal{H} \}$ is not upper bounded. Yet, as a union of PAC learnable classes, $\mathcal{H}$ is nonuniform learnable.


Heuristic with worst-case exponential complexity I have been working with some colleagues on a metaheuristic for an NP-Hard optimization problem. It is a genetic algorithm using a steady-state population replacement strategy (at each iteration a single new chromosome is created and used to replace an older one). The algorithm iterates until it fails to find a solution which is better than the current incumbent optimum for a pre-set number of consecutive iterations.
The algorithm has been tested on benchmark instances and proved empirically to be fast and effective, outperforming previous approaches.

We submitted our work to a journal and received rather favorable reviews. Among the modification requests, we were asked to state the time complexity of the procedure. While we have no difficulty to evaluate the (polynomial) complexity of a single iteration, we realized that, given the exponentially large solution space and our termination criterion, our algorithm could theoretically iterate an exponential number of times. Is this considered acceptable for a heuristic? After all, I was thinking, the same conclusion may even apply to a simple local search scheme, should it keep finding marginal improvements in its neighborhoods indefinitely without getting trapped in a local optimum.

Should we look into complexity analysis different from worst-case? Do you have references to works we may look into? Apologies if the question is too trivial, we are not "pure" computer scientists (although we submitted this work to a CS journal since we thought it was the right outlet for it).

While there are many heuristics (arguably all of them) that take exponential time in the worst-case, what usually makes them attractive (and marketable) is that they "appear" to perform much better in practice, and in fact it's hard to find examples where they are provably exponential.

Two canonical examples are the simplex algorithm for linear programming and the $k$-means heuristic for clustering.

It seems highly unlikely that you'll be able to show a worst-case running time that's better than exponential for a GA-like heuristic. As Tobias points out, it would be useful to know if there's some kind of guarantee of quality if the heuristic is terminated early - but I'm pessimistic that this can be done as well.


How can we derive this lower bound of a special cut in a graph? I have another question about this paper. There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in this situation on page 9.

If you have a partition $C\cup (V\setminus C)$ with $s\in C$ and $t\in V\setminus C$, the $k$-uniform cut capacity $c_k(C)$ is the maximal volume of a packing of $k$ identically sized packages into the bins with size corresponding to the edges from $C$ to $V\setminus C$. The minimum $k$-uniform $s$-$t$ cut, $c_k(s, t)$, is defined by $c_k(s,t):=\min\{c_k(C)|s\in C\subset V\setminus \{t\}\}$

My question is then about Theorem 7. How can we derive this lower bound of $k$ for a standard minimum $s$-$t$ cut in the graph $G'$?

Consider a cut $C$ in $G^\prime$. Let $c_k(C)$ be its uniform cut capacity in $G$. Then $c_k(C) \geq c_k(s,t)$. By definition of $c_k(C)$, exactly $k$ packets, each of size $c_k(C)/k$ can be packed into the cut $C$. So sum of $\lfloor ku_e /c_k(C) \rfloor$ over the cut is at least $k$. As $c_k(C) \geq c_k(s,t)$, $ku_e /c_k(C) \leq ku_e /c_k(s,t)$. So

$$
\sum_C u_e^\prime = \sum_C \lfloor ku_e /c_k(s,t)\rfloor \geq \sum_C \lfloor ku_e /c_k(C)\rfloor \geq k
$$


What are those deterministic algorithms for k-SAT that are not derandomization of random algorithms like PPSZ and Schöning's local search? I am doing a survey on k-SAT where time complexity is in terms of n, i.e. the number of variables in a formula.
As for the fast algorithms for k-SAT, we see
biased-PPSZ, PPSZ, Schöning's local search, algorithms which combine PPSZ and Schöning's local search, algorithms which derandomize PPSZ or Schöning's local search.

There are many papers which are discussing improvement and property of PPSZ.
However, where are other deterministic algorithms going? Is there no future for every deterministic algorithm which is not a derandomization of PPSZ or Schöning's local search or their improvement,combination?

There exists deterministic fast branching algorithms which are not derandomization from some randomized algorthms for k-SAT where time complexity is in terms of m and l, i.e. the number of clauses in a formula and the length of a formula. And there is a branching algorithm, and in the early papers which discuss k-SAT in terms of n, there is also algorithm using branching algorithm to obtain a speed which is from Burkhard Monien and Ewald Speckenmeyer. For 2-SAT, there is linear time deterministic algorithm based on strongly connected components of a contructed graph.

After Hertli reveals that unique-SAT bounds for PPSZ hold in general, work turns from derandomizing and improving Schöning's local search to derandomize PPSZ and improve that. Are there any possibilities for those deterministic algorithms without derandomization like some branching algorithms? What if some techniques like measure and conquer are contributed to k-SAT? No matter how, it must be admitted that PPSZ and Schöning's local search are both simple and efficient.

Papers I mention are as follows.

schöning, A Probabilistic Algorithm for k-SAT and Constraint Satisfaction k Problems
Evgeny Dantsin, Andreas Goerdt, Edward A Hirsch, Ravi Kannan, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, and Uwe Sch¨oning. A deterministic (2-2/(k+1))n algorithm for k-sat based on local search. Theoretical Computer Science, 289(1):69–83, 2002.
S. Cliff Liu, Simpler Partial Derandomization of PPSZ for k-SAT
Daniel Rolf. Derandomization of PPSZ for unique- k-sat. In 8th International Conference on Theory and Applications ofSatisfiability Testing, SAT 2005, pages 216–225, 2005.
S. Cliff Liu, Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT∗
Robin A. Moser and Dominik Scheder, A full derandomization of schöning’s k-sat algorithm. In 43rd Annual ACMSymposium on Theory ofComputing, STOC 2011, pages 245–252, 2011.
Hertli, 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
Dominik Scheder and John P. Steinberger, PPSZ for General k-SAT – Making Hertli’s Analysis Simpler and 3-SAT Faster∗
Pavel Pudlák, Dominik Scheder, and Navid Talebanfard, Tighter Hard Instances for PPSZ
Burkhard Monien and Ewald Speckenmeyer. 1985. Solving satisfiability in less than 2n steps. Discrete Applied Mathematics 10, 3 (1985), 287–295.
Jianer Chen and Yang Liu, An Improved SAT Algorithm in Terms of Formula Length
Bengt ASPVALL, Michael F. PLASS and Robert Endre TARJAN, A LINEAR-TIME ALGORITHM FOR TESTING THE TRUTH OF CERTAIN QUANTIFIED BOOLEAN FORMULAS
Timon Hertli. 2014. Breaking the PPSZ Barrier for Unique 3-SAT. In Proc. of41st ICALP I. 600–611.
Ramamohan Paturi, Pavel Pudlák, and Francis Zane. 1999. Satisfiability Coding Lemma. Chicago J. Theor. Comput. Sci. (1999).
Tong Qin and Osamu Watanabe. 2018. An Improvement of the Algorithm of Hertli for the Unique 3SAT Problem. In International Workshop on Algorithms and Computation. Springer, 93–105.
Thomas Hofmeister, Uwe Sch¨oning, Rainer Schuler, and Osamu Watanabe. A probabilistic 3sat algorithm further improved. In 19th Annual Symposium on Theoretical Aspects ofComputer Science, STACS 2002, pages 192–202. Springer, 2002.
Improving PPSZ for 3-SAT using Critical Variables

If I may interpret your question as a reference request: Donald Knuth recently finished the part of TAOCP that deals with satisfiability:

Donald E. Knuth, The Art of Computer Programming, Volume 4 Fascicle 6, Satisfiability (2015), xiii+310pp. ISBN 978-0-13-439760-3.

Although I did not work through it yet (no pun intended), it is well known that Don Knuth usually puts a clear emphasis on the structure of the different algorithmic approaches, and he gives a very detailed account on the history of ideas. My bet is that you'll find the answer to your question in the fascicle. (Maybe someone else who is more knowledgeable about SAT can give a less indirect answer )


A first order logic extended with binding terms like the familiar set descriptors $\{x:\varphi\}$ First order logic comes equipped with two kinds of terms:

Variable: those terms of the form $x$ for some variable $x$, of which there are infinite.
Function application: those terms of the form $f(t_1,\dots,t_n)$ for some $n$-place function symbol $f$, of which there are infinite, and some $n$ terms $t_1, \dots, t_n$.

In practice, one more kind of term is commonly used informally in the context of set theory: set descriptors of the form $\{x:\varphi\}$, where $x$ is a variable, and $\varphi$ is a first order well-formed formula. This term cannot be rewritten as a function application, since $\varphi$ is not a term. This term creates a scope in which the variable $x$ is bound, similar to the way the quantified formulas of the form $\forall x\varphi$ and $\exists x\varphi$ work.

One way to introduce set descriptor terms into the logic, which then will no longer be a first order logic, so lets call it extended first order logic, is by introducing an infinite set of binding term constructors that is disjoint from the the first order logic vocabulary (consisting of logical symbols, variables, function symbols, and relation symbols), and a new way of forming terms: $Cx\varphi$, for every binding term constructor $C$, every variable $x$, and every extended first order well-formed formula $\varphi$ (the definition of function application and of a well-formed formula should be modified to accomodate this new kind of term). Let's call such terms binding terms.

We can now set aside one of the new-fangled binding term constructors, say $\sigma$, and interpret every binding term of the form $\sigma x\varphi$ as $\{x:\varphi\}$.

Set descriptors are probably the most familiar example of binding terms, but two others that I know of have been proposed in the past by mainstream mathematicians, likewise in the context of set theory: Hilbert's epsilon operator and Bourbaki's $\tau$ operator, which, though similar, are not the same operator, as they satisfy slightly different axioms.

Note that extending first order logic with binding terms necessitates a corresponding extension of the inference system, say Gentzen's Natural Deduction.

Has the combination of extended first order logic with a corresponding inference system been studied? Where can I read more about it?

I would recommend looking at higher-order logics (HOL), for instance Lambek and Scott's Introduction to Higher-Order Categorical Logic. Such a logic will set up binding of bound variables and treat variable contexts properly (single-sorted first-order logic tends to have a somewhat simplistic view of those).

Note that your suggestion to always bind just a single variable does not cover operators that require simulatneous binding of several variables. They are uncommon, but do appear occasionally.

To get what you're asking for, we can cut down on the order. In HOL there is a single sort of types, including a type of propositions $\Omega$, which are closed under formation of function spaces, so that higher-order predicates are formed as $\Omega$, $A \to \Omega$, $(A \to \Omega) \to \Omega$. To prevent these, we can stratify the types into several sorts:

the sort of primitive types $A$, $B$, $C$, ... (in first-order logic you often have just a single one, which is not mentioned at all)
the sort of propositions $\Omega$
the sort of first-order functions $(A_1, \ldots, A_n) \to B$, where $A_i$ and $B$ are primitive types
the sort of (first-order) propositional functions $(A_1, \ldots, A_n) \to \Omega$, where $A_i$ are primitive types.

Variables always range over primitive types. A context $\Gamma$ is a list of variables with their (primitive) types, $\Gamma \equiv x_1 : A_1, \ldots, x_n : A_n$. We never speak of an expression without specifying its context, so that we can keep track of which variables are allowed to appear.

If $S$ is a sort, we write $\Gamma \vdash e : S$ when $e$ is an expression of sort $S$ in context $\Gamma$. For example,
$$x : \mathbb{R}, y : \mathbb{R} \vdash (\exists z : \mathbb{R} . x + z = y) : \Omega$$
is the assertion that $\exists z : \mathbb{R} . x + z = y$ is a proposition (in the given context). It is not the assertion that $\exists z : \mathbb{R} . x + z = y$ holds! For that we postulate a new judgement of the form
$$\Gamma \mid \theta_1, \ldots, \theta_n \vdash \psi \ \mathsf{true}
\tag{1}$$
which states, intuitively, that propositions $\theta_1, \ldots, \theta_n$ jointly entail the proposition $\psi$. If we also have equations (at all types), (1) can be replaced with
$$\Gamma \mid (\theta_1 \land \cdots \land \theta_n) \land \psi =_\Omega \theta_1 \land \cdots \land \theta_n.$$
This is the approach taken by Lambek and Scott. Its main advantage is that the formal system is more like algebra, since it is just a bunch of (fancy) operations and equations.

Another example (where I am using the notation $\langle x_1 : A_1, \ldots, x_n : A_n \rangle . e$ to express the fact that the variables $x_1, \ldots, x_n$ are bound in $e$):
$$x : \mathbb{R} \vdash (\langle y : \mathbb{R}, z : \mathbb{R} \rangle . y^2 + x \cdot z) : (\mathbb{R}, \mathbb{R}) \to \mathbb{R}.$$
This says that there is a function taking $(y, z)$ to $y^2 + x \cdot z$.

We can now introduce first-order binders as operations that map first-order (propositional) functions to primitive sorts and propositions, for instance:

$\forall$ is an operation which takes a propositional function $(A) \to \Omega$ to a proposition. The formation rule would read as follows:
$$\frac{\Gamma \vdash p : (A) \to \Omega}{\Gamma \vdash \forall p : \Omega}$$
En example of such an expression would be $\forall (\langle x : \mathbb{R} \rangle . x^4 - 5 x^2 + 7 > 0)$.
Assuming there is a primitive type $\mathsf{Set}$ of sets and a relation symbol $\in$ of sort $(\mathsf{Set}, \mathsf{Set}) \to \Omega$, subset formation $\sigma$ is an operation which takes $s : \mathsf{Set}$ and $p : (\mathsf{Set}) \to \Omega$ and yields $\sigma(s, p) : \mathsf{Set}$. We also need some rules regarding these, e.g.,
$$
\Gamma \mid \vec{\theta}, e \in s, p(s) \vdash e \in \sigma(s, p) \ \mathsf{true}.
$$
We can also do unrestricted comprehension $\sigma'$, the kind that leads to Russell's paradox. It takes $p : (\mathsf{Set}) \to \Omega$ to $\sigma' p : \mathsf{Set}$. Assuming there is also $\epsilon : (\mathsf{Set}, \mathsf{Set}) \to \Omega$ and negation, we can define Russell's paradoxical $R$ as $\sigma' (\langle x : \mathsf{Set} \rangle . \lnot (x \in x))$.
For a "non-logical" example, let us introduce the $\lambda$-notation from $\lambda$-calculus. Suppose for every primitive types $A$ and $B$ there is a primitive type $A \Rightarrow B$ (normally written as $A \to B$ but I am using a different arrow to avoid confusion). For all primitive types $A$ and $B$, we can introduce an operator $\lambda_{A, B}$ which takes $f : (A) \to B$ to an expression $\lambda_{A,B} f : A \Rightarrow B$. The identity map on $A$ is thus written as $\lambda_{A,A} (\langle x : A \rangle . x)$. This is an example of a higher-order calculus of types with first-order logic layered on top of it (as opposed to HOL, where $\Omega$ is mixed with $\Rightarrow$ freely).

I do not know of any texts that would carefully developed this sort of calculus. I do not know why that is. Traditional logic textbooks usually simplify matters by considering a single-sorted first-order language, whereas the newer computer-sciency texts dive for fancier stuff with unrestricted order. You're asking for a bastard child of higher-order logic, I suppose.


Is embedding a solution feasible for SAT? I am interested in "hard" individual instances of NP-complete problems.

Ryan Williams discussed the SAT0 problem at Richard Lipton's blog.  SAT0 asks whether a SAT instance has the specific solution consisting of all 0's.  This got me thinking about constructing SAT instances that are likely to be "hard".

Consider a SAT instance $\phi$ with $m$ clauses and $n$ variables, where $\alpha = m/n$ is "large enough", in the sense that it falls into the region beyond the phase transition, where nearly all instances are unsatisfiable.  Let $x$ be a random assignment to the values of $\phi$.

  Is it possible to modify $\phi$ to obtain a new instance $\phi|x$, so that $\phi|x$ is "largely similar" to $\phi$, but so that $x$ is a satisfying assigment for $\phi|x$?

For instance, one could try to add to each clause a randomly chosen literal from the solution, that does not already occur in the clause.  This will guarantee that $x$ is a solution.

Or is this hopeless, leading to a fast algorithm for finding the "hidden" solution, along the lines of the following recent paper?

Uriel Feige and Dorit Ron, Finding hidden cliques in linear time, DMTCS proc. AM, 2010, 189–204.

I am aware of the discussion by Cook and Mitchell and work they reference.  However, I couldn't find anything about what happens to the structure of a formula when one tries to explicitly embed a satisfying assignment into it.  If this is folklore, pointers would be very welcome!

Stephen A. Cook and David G. Mitchell, Finding Hard Instances of the Satisfiability Problem: A Survey, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 35 1–17, AMS, ISBN 0-8218-0479-0, 1997. (PS)

You can take any formula $\varphi$ and change it to the formula $\varphi \vee \psi_x$ where $\psi_x$ is a "hard" SAT instance whose only solution is $x$. One way to construct such a formula is using cryptography:  if $f:\{0,1\}^n\rightarrow \{0,1\}^n$ is a one-way permutation and we choose $x$ at random and set $y=f(x)$, then one can convert $y$ into a SAT formula such that $x$ is its only solution and thus finding $x$ corresponds to inverting $f$. (We need for this $x$ to be random, but this something similar is anyway assumed if we think finding $x$ should be hard.)


Dependence of decidability on the encoding of Turing machines Let $f : \{0, 1\}^* \to \{0, 1\}^*$ be a computable function. Given any encoding $\left<M\right>$ of Turing machines over binary (i.e., a function from the set of Turing machines to the set of strings over $\{0, 1\}^*$), consider the following language:
$$ L_f = \{\left<M\right> \mid M \mathrm{\ accepts\ } f(\left<M\right>)\} $$
Question: Does there exist a function $f$ for which the decidability/recognizability of this  language depends upon the particular encoding used?

For a given computable $f$, the decidability of $L_f$ is independent of the encoding of Turing machines if and only $f$ is eventually injective (i.e., there exists a finite $X\subseteq\def\N{\mathbb N}\N$ such that $f\restriction(\N\smallsetminus X)$ is injective, or equivalently, $\{\def\<#1>{\langle#1\rangle}\<n,m>:n\ne m,f(n)=f(m)\}$ is finite).

If $f$ is computable and eventually injective, then $L_f$ is undecidable for any encoding.

Assume for contradiction that $L_f$ is decidable. Then
$$\{m\in\N:\exists n\in\N\:(f(n)=m\land n\notin L_f)\}$$
is r.e., hence it is accepted by infinitely many Turing machines; in particular, using the assumption, it is accepted by a TM $M$ such that $f(n)\ne f(\<M>)$ for all $n\ne\<M>$. Then
$$\<M>\in L_f\iff M\text{ accepts }f(\<M>)\iff\<M>\notin L_f,$$
a contradiction.

If $f$ is not eventually injective, then the decidability of $L_f$ depends on the encoding.

As shown in Aryeh’s answer, $L_f$ is undecidable under the standard encoding, hence it suffices to exhibit an encoding that makes $L_f$ is decidable. Let $\{M_m:m\in\N\}$ be any enumeration of TMs, and define $X\subseteq\N$ by
$$n\in X\iff|\{m<n:f(n)=f(m)\}|\text{ is even.}$$
We define a new enumeration $\{M'_n:n\in\N\}$ by
$M'_n=M_{m(n)}$, where $m(n)$ is defined by induction on $n$:
$$m(n)=\begin{cases}
  \min\bigl\{m\in\N\smallsetminus\{m(i):i<n\}:M_m\text{ accepts }f(n)\bigr\},&\text{if }n\in X,\\
  \min\bigl\{m\in\N\smallsetminus\{m(i):i<n\}:M_m\text{ does not accept }f(n)\bigr\},&\text{if }n\notin X.
\end{cases}$$
To see that $\{M'_n:n\in\N\}$ indeed enumerates all TMs, assume for contradiction that $m$ is least such that $m\ne m(n)$ for all $n\in\N$. Since $f$ is not eventually injective, there are $n<n'$ such that $f(n)=f(n')$ and $\{0,\dots,m-1\}\subseteq\{m(i):i<n\}$. We may assume $n'>n$ is smallest such that $f(n')=f(n)$, which implies
$$n\in X\iff n'\notin X.$$
Thus, either $n''=n$ or $n''=n'$ satisfies
$$M_m\text{ accepts }f(n'')\iff n''\in X,$$
which implies $m(n'')=m$ by the definition of $m(n'')$, a contradiction.
Thus, we may define an encoding of TM by $\<M'_n>=n$, and then it follows from the definition that
$$L_f=X,$$
which is decidable.

The answer above assumes that an encoding of TM has to be injective; this is not specified in the OP, but I suppose this is just an omission, as I fail to see how something that assigns the same code to two different TM can be considered an “encoding” of TM.
Anyway, if we allow non-injective encodings, the answer is that the decidability of $L_f$ depends on the encoding for every $f$: it is undecidable under the standard encoding by Aryeh’s answer, while it is trivially decidable (because finite) for the constant encoding $\<M>=0$.


Logic programming with integer or even floating point domains I am reading a lot about logic programming - ASP (Answer Set Programming) is one example or this. They (logic programs) are usually in the form:

[Program 1]
Rule1: a <- a1, a2, ..., not am, am+1;
Rule2: ...

This set of rules is called the logic program and the s.c. model is the result of such computation - some kind of assignment of True/False values to each of a1, a2, ...
There is lot of research going on - e.g. how such kind of programs (rules) can be integrated with the (semantic web) ontologies to build knowledge bases that contain both - rules and ontologies (some kind of constraints/behaviour and data); there is lot of research about ASP itself - like parallel extensions, extensions for probabilistic logic, for temporal logic and so on.

My question is - is there some kind of research and maybe some proof-of-concept projects where this analysis is extended from Boolean variables to variables with integer and maybe even float domains? Currently I have not found any research that could address the following programs:

[Program 2]
Rule1 a1:=5 <- a2=5, a3=7, a4<8, ...
Rule2 ...
...
[the final assignment of values to a1, a2, etc., is the solution of this program]

Currently - as I understand - if one could like to perform some kind of analysis on Program-2 (e.g. to find if this program is correct in some sense - e.g. if it satisfies some properties, if it terminates, what domains are allowed not to violate some kind of properties and so on), then he or she must restate Program-2 in terms of Program-1 and then proceed in way which seems to be completely unexplored - to my knowledge (and I don't believe that is it unexplored, simply - I don't know some sources or trend). There is constraint logic programming that allow the use of statements with inequalities in Program-1, but it is too focused on Boolean variables as well. Actually - Programm-2 is of kind that can be fairly common in business rules systems, that was the cause of my interest in logic programming.

SO - my question has some history - my practical experience has led me to appreciate business rules systems/engines, especially - JBoss project Drools and it was my intention to do some kind of research of theory underlying s.c. production rules systems (I was and I am planning to do my thesis about them - if I would spot what can be done here), but I can say that there is little to do - after going over the literature (e.g. http://www.computer.org/csdl/trans/tk/2010/11/index.html was excellent IEEE TKDE special issues with some articles about them, one of them was writter by Drools leader) one can see that there is some kind of technical improvements of the decades old Rete algorithm but there is no theory of Drools or other production rule systems that could help with to do some formal analysis about them. So - the other question is - is there theory of production rule systems (for rule engines like Drools, Jess, CLIPS and so on) and is there practical need for such theory and what are the practical issues of using Drools and other systems that can be addressed by the theory of production rule systems.

p.s. I know - all these are questions that should be directed to thesis advisor, but my current position is that there is no (up to my knowledge) person in department where I am enrolled with who could fit to answer them, so - I am reading journals and also conference proceedings (there are nice conference series series of Lecture Notes in Computer Science - RuleML and RR)...

Thanks for any hint in advance!

The first question can be solved by googling integer logic programming.

http://en.wikipedia.org/wiki/Constraint_logic_programming

The second question is called the theory of expert programming. I was also able to google this.

http://en.wikipedia.org/wiki/Expert_system

There is a practical need for expert systems and rule based systems. They are used in many domains as you can see from here.

http://en.wikipedia.org/wiki/Expert_system#Examples_of_applications


Number of vertices at distance $k$ for each vertex of restricted sparse graph My graphs has following restriction: undirected, connected, simple, unweighted,
and maximum degree of any vertex is 8. These are actually molecular graphs. Almost always maximum degree will be 4 but in some cases I have seen it to be 5 or 6, so I am keeping the limit as 8.Usually I will have around 100 vertices.

I want to compute for each verticex $v$, the number of vertices at distance $i$ from $v$. I found several reference to algorithm for all-pair-shortest-path problem of Floyd-Warshall type. However, i do not need the exact paths, and not even the distances.  These algorithms, can solve my problem, but they do more than what I want. For me time is very critical ( computation over millions molecules), so I want an algorithm which is optimal for above restrictions possibly at the cost of not being generalizable. Solution should be exact and deterministic. I would worry not just about the order of complexity but also of the constants.

Thank you for the interesting question!

First, let's consider the easy part.  Given that you want the distances from every vertex for all distances, you are asking for all-pairs shortest paths.

Therefore you need to find $|V|(|V|-1)/2$ distances between pairs of vertices, and you cannot do better than essentially $c|V|^2/2$ steps for some small constant $c$.

Your restriction to low bounded degree $d$ implies that $|E| \le d|V|/2$.  For $d\le 8$ this means $|E| \le 4|V|$.

As Shir points out in a comment, running BFS starting from each vertex therefore takes at most $C(|V|+|E|)|V| \le C(|V| + 4|V|)|V| = 5C|V|^2$ steps for some small constant $C$.  The actual running time will probably be less, since your $d\le 8$ is an upper bound; depending on the graph the multiplier may be closer to the average degree.

So the solution will have an unavoidable $|V|^2$ factor, multiplied by a constant between $c/2$ and $(1+(d/2))C$.

That is as far as a purely asymptotic analysis goes.
However, you indicate you need to do this millions of times (presumably for different graphs), so even a small improvement is likely to be worthwhile, and that it would be worth improving the constants.

Assuming that $c$ and $C$ are similar, the question is then whether it is possible to reduce the multiplier from the $(d/2)+1$ upper bound (which seems to be around $3$ in your setting), to get it closer to the optimal $1/2$.

Depending on the structure of the graph, a modified BFS may give a lot of information about intermediate shortest paths.  If you start a BFS at $u$, then see vertex $v$ in the search at distance $d$, then see vertex $w$ at distance $d+e$ in the subtree rooted at $v$, you can conclude that $d(u,w)=d+e$ and $d(u,v)=d$, but also that $d(v,w)=e$.  In short, one can extract some of the entries $d(v,w)$ in the distance matrix (where $v$ and $w$ are different from $u$) from the shortest path tree rooted at $u$.  This seems to be essentially the idea of this SO answer to a related question.

Whether the cost of extracting additional information out of the shortest path trees is worth the cost depends on the structure of your graphs.  For this to be worthwhile, it should allow a lot of information to be extracted from the first few BFS searches, so that many of the later vertices from which a BFS would be started already have their entries in the distance matrix filled in and can be skipped.

The following question then seems interesting:

  How should a "good" set of starting vertices be chosen?

With "good" I mean a small set $U$ of vertices so that after modified BFS has been run with each $u\in U$ as the starting vertex, then all (or nearly all) of the remaining vertices all have their shortest path vectors fully computed.  Examining some low-degree graphs this seems to be an interesting idea: for a path, either endpoint allows a single BFS to compute all the distance vectors; for a cycle, taking two vertices far apart works.  For trees, a single BFS starting from an internal vertex $u$ can be used to derive the distance matrix, since if $d(v,w)$ is not known at the end of the BFS, then $v$ and $w$ must be descended from different children of $u$, and then $d(v,w) = d(v,u)+d(u,w)$ which are both known.

The Nash-Williams decomposition of a graph into edge-disjoint forests might then be relevant.  The arboricity of a graph with maximum degree $8$ seems to be at most $4$ (I might be wrong here; however, David Eppstein confirms that arboricity of bounded degree graphs is bounded).  So it might be possible to find a small number of vertices from which BFS search trees yield all relevant shortest path information, i.e. so that the distance matrix can always be computed using these trees, and so that the edges of the BFS search trees cover the graph.  I do not know how large "small" is in this statement, or even if it can always be made to be $4$.

David Eppstein, Arboricity and bipartite listing algorithms, IPL 51, 207–211, 1994.  doi:10.1016/0020-0190(94)90121-X (preprint)

I didn't find anything solving this particular version of the problem when searching, but expect it has been thought about already.
There is a recent paper which uses a distributed Nash-Williams decomposition to obtain maximal independent sets.
Perhaps someone else has a pointer to a more directly relevant paper.

Leonid Barenboim and Michael Elkin, Sublogarithmic Distributed MIS Algorithm for Sparse Graphs using Nash-Williams Decomposition, Distributed Computing 22, 363–379, 2010.  doi:10.1007/s00446-009-0088-2 (preprint)


Is deterministic pseudorandomness possibly stronger than randomness in parallel? Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a different name).  Define the class DBPNC similarly, except that all processes have random access into a random stream of bits fixed at algorithm startup.

In other words, each process in BPNC has access to a distinct random source, while DBPNC algorithms have a shared perfectly random counter mode generator.

Do we know whether BPNC = DBPNC?

They are the same: BPNC = DBPNC.

Say a BPNC machine is given as input a DBPNC program to simulate.  Execute the program in lock step.  First assume that the indices between different steps are distinct, so that we do not need to remember old random bits.  At each step, each processor asks for a random bit at a specific index into the shared stream.  Compute and distribute the random bits as follows:

Sort the indices among the processors and remember the origin of each bit.
Coordinate among adjacent processors to compute the ranges of identical indices.
Compute each random bit on the first processor that owns it after sorting.
Scatter throughout the identical ranges.
Send back to the origin process (if necessary by reversing the sorting algorithm).

To allow processors to ask for old indices, have each processor remember the (results) of all previous sorting epochs.  To check whether newly requested indices occurred in a given previous epoch, do

Sort the new indices.
Merge the lists of old and new indices (e.g., with Cole 1988).
Scatter appropriately.


A boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$ is chosen at random from all $2^{2^n}$ such $f$. What do the Fourier coefficients look like? As in the title.

I'm not sure where to start here. My guess is that in expectation at least a constant fraction are non zero, and as a result there would exist some "large" coefs. and some "small" coefs..

Any further intuition would be appreciated.

Thanks.

Here's one way of attacking the problem.
Any boolean function $f: [2]^n \rightarrow [2]$ can be written as
\begin{equation}
f(\alpha) = \sum_{\beta \in [2]^n} \chi_{\beta}\delta_{\beta} (\alpha)
\end{equation}
where $\chi_{\beta} \in [2]$ and $\delta_{\beta}$ is defined as
\begin{equation}
\delta_{\beta} (\alpha) = \begin{cases} 1 & \text{if } \alpha = \beta \\ 0 & \text{o.w.} \end{cases}.
\end{equation}
Choosing an $f$ at random is equivalent to independently and identically giving each $\chi_{\beta}$ the probability $p(\chi_{\beta} = i ) = 1/2$; i.e. each $\chi_{\beta}$ is an uniformly random i.i.d. binary random variable and $f$ is the sum of these random variables. The Fourier transform of this function is
\begin{equation}
 \widehat{f} (\gamma) = \frac{1}{2^n}\sum_{\alpha \in [2]^n} f(\alpha)e^{ \left\langle \gamma , \alpha \right\rangle  \pi i}
\end{equation}
where $ \left\langle \gamma , \alpha \right\rangle $ is the dot product in $\mathbb{F}^n_2$.
However, plugging in our previous definition/identity for $f$ we have that
\begin{equation}
 \widehat{f} (\gamma) = \frac{1}{2^n}\sum_{\alpha \in [2]^n} \sum_{\beta \in [2]^n} \chi_{\beta}\delta_{\beta} (\alpha)e^{ \left\langle \gamma , \alpha \right\rangle  \pi i} = \frac{1}{2^n}\sum_{\alpha \in [2]^n}  \chi_{\alpha} e^{ \left\langle \gamma , \alpha \right\rangle  \pi i};
\end{equation}
therefore the expected value of $\widehat{f}$ can be written as
\begin{equation}
 \mathbb{E}[\widehat{f} ]  = \frac{1}{2^n} \sum_{\gamma \in [2]^n} \widehat{f}(\gamma) = \frac{1}{2^n} \sum_{\gamma \in [2]^n} \left(\frac{1}{2^n}\sum_{\alpha \in [2]^n}  \chi_{\alpha} e^{ \left\langle \gamma , \alpha \right\rangle  \pi i}\right) \end{equation}
\begin{equation}
= \frac{1}{2^n} \sum_{\alpha \in [2]^n}  \chi_{\alpha} \left(\frac{1}{2^n}\sum_{\gamma \in [2]^n} e^{ \left\langle \gamma , \alpha \right\rangle  \pi i}\right) ;
\end{equation}
which we can simplify that as
\begin{equation}
 \mathbb{E}[\widehat{f} ]  = \sum_{\alpha \in [2]^n} \frac{\chi_{\alpha} }{2^n}  \mathbb{E}[ e^{ \left\langle \gamma , \alpha \right\rangle  \pi i}]  ;
\end{equation}
so that we can consider the subproblem $ \mathbb{E}[ e^{ \left\langle \gamma , \alpha \right\rangle  \pi i}] $ instead.
Now we use the following fact from combinatorics

Lemma $\mathcal{E}$=(The number of binary strings with even number of ones) = (The number of binary strings with odd number of ones)=$\mathcal{O}$
(Proof): Binary strings in $[2]^m$ are in 1-to-1 correspondence with subsets of $[m]$; but by the binomial theorem $(1-1)^m = \sum_{k} \binom{m}{k}(-1)^{k} = \mathcal{E} - \mathcal{O} = 0 $. QED

Therefore we have the following (if $\alpha \neq 0^n$)

Corrollary $e^{ \left\langle \gamma , \alpha \right\rangle  \pi i}$ is equal to 1 as often as it is equal to -1; i.e. $ \mathbb{E}[ e^{ \left\langle \gamma , \alpha \right\rangle  \pi i}] = 0 $
(Proof): If the support of the string $\alpha$ has $m$ 1's then we can break up the sum by the substrings on the support. In particular there are $[2]^{n-m}$ possible strings that are equal on the $[2]^m$ different strings on the support, then apply the previous lemma. QED

We, therefore, have that $ \mathbb{E}[\widehat{f} ]  = \sum_{\alpha \in [2]^n} \frac{\chi_{\alpha} }{2^n}  \mathbb{E}[ e^{ \left\langle \gamma , \alpha \right\rangle  \pi i}]  = 2^{-n}\chi_0 $ for any fixed $f$. Therefore $\mathbb{E}_{\chi}[\mathbb{E}_{\gamma }[\widehat{f} ]]=2^{-(n+1)}$ for a random $f$ or more simply put we have that:
For a random $f$ we have that the mean value of $\mathbb{E}[\widehat{f} ]$ is equal to $2^{-(n+1)}$.
If we wanted a more precise answer we could have gone an alternate route:
What is $p(\widehat{f} (\gamma)= i )$?
We can split this up into two sets like in the proof of the lemma; i.e.
\begin{equation}
\frac{1}{2^n}\sum_{\alpha \in [2]}\chi_{\alpha}e^{ \left\langle \gamma , \alpha \right\rangle  \pi i} = \frac{1}{2^n}\sum_{\alpha \in \mathcal{E} }\chi_{\alpha} - \frac{1}{2^n}\sum_{\alpha \in \mathcal{O} }\chi_{\alpha}
\end{equation}
But the $\chi_{\alpha}$ are i.i.d. and therefore this looks just like a random walk that is normalized by $2^{n}$.
The $\widehat{f} $ follows the binomial distribution of the form
\begin{equation}
p\left(\widehat{f} (\gamma)= \frac{i}{2^{n-1}} \right) =  \binom{2^n}{2^{n-1}+i}\frac{1}{2^n}
\end{equation}
if $\gamma \neq 0^n$;
i.e. the distribution on $\widehat{f} $ looks like what would happen if you took a binomial distribution on $[2^n]$ and shited it to the left by $2^{n-1}$ and then divided by $2^{n}$.


Is a "complete" cipher possible? Is a "complete" symmetric cipher possible?  By this I mean a symmetric cipher that is provably secure under the assumption that a secure symmetric cipher exists.

Yes, you can use Levin universal search to construct a "universal one-way function" (e.g., these lecture notes). From this one-way function you can then construct symmetric-key encryption primitives (pseudorandom generators, block ciphers, CPA/CCA-secure encryption) using standard theoretical constructions.

One-way function $\to$ pseudorandom generator:

  Håstad, J., Impagliazzo, R., Levin, L.A. and Luby, M., 1999. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4), pp.1364-1396.

Pseudorandom generator $\to$ pseudorandom function:

  Goldreich, O., Goldwasser, S. and Micali, S., 1986. How to construct random functions. Journal of the ACM (JACM), 33(4), pp.792-807.

Pseudorandom generator $\to$ block cipher / pseudorandom permutation:

  Luby, M. and Rackoff, C., 1988. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2), pp.373-386.

Block cipher $\to$ CCA-secure encryption:

  CBC mode + CBC-MAC


Why may the right hand sides in Chomsky Hierachy type 1 be larger? I'm shaking my head because of this question, my Prof. didn't explain it. We have linear space limited automata and they have to satisfy for rules a -> b that |a| <= |b|.

Why?

I would have said, that it's stupid to allow being larger, because we are space limited and still have to produce all words of a language.

Thank you in advance, an answer would mean a lot to me.

It is not allowed to be larger, it has to be larger! If you allow the right side being shorter, you have context sensitive deleting grammars which have the same power as unrestricted grammars, thus leaving the realms of CSL.

The space limitation you mention relates to the automaton concept that is equivalent to context sensitive grammars, not the grammars itself.


Graph factors of maximum weight I am trying to find references to a weighted version of the graph factor problem for the case when the "target degree" is a set of integers with "gaps" of size at most one.  The unweighted version of the problem can be defined as follows.

We are given a graph $G = (V, E)$ and a set of integers $B(v)$ associated to each vertex.  The goal is to find a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph (V, F) is one of the integers in the associated set $B(v)$.

The problem is known to be solvable in polynomial time if $B(v)$ does not have gaps of length greater than one for any $v$.  For example the set $B(v) = \{5, 7, 8\}$ is OK (the gap between 5 and 7 is of length 1) but the set $B(v) = \{5, 8\}$ is not OK (the gap between 5 and 8 is of length 2).

My question is whether there are any known results for the weighted version of this problem.  So far I found a 1995 survey (Pulleyblank, "Matchings and Extensions") saying that the weighted version has not been solved: "Recently Cornuejols(1988) developed a polynomially bounded extension of the blossom algorithm for this problem when no gap of size greater than one is permitted. However, the corresponding weighted problem has not yet been solved." (p. 212 of "Handbook of combinatorics" vol. 1)

Has this problem been solved since?

The case where all gaps have the same parity was solved by Jácint Szabó.

There is a very recent arXiv post by Szymon Dudycz and Katarzyna Paluch. They claimed to have solved the problem.


Proof of decidability of type checking of calculus of (co)inductive constructions? I often see it asserted that type checking is decidable for CIC, but I haven't seen it proven. Is there a good paper (or simple demonstration) of this?

I found another reference that goes through a detailed proof of the decidability of typechecking for systems of dependent types up to the CIC:

Chapter 2 of Advanced Topics in Types and Programming Languages: Dependent Types, David Aspinall & Martin Hofmann.

As you probably know, the proof of decidability is conditional on decidability of $\beta$-equality, which itself is implied by the normalization of the calculus.

The proof of that statement is significantly more difficult, partly because it implies consistency of the logical system.


Reinforcement Learning and Optimistic Decisions Sutton recommended using an optimistic heuristic on decision making by considering the upper bound of the confidence range of an action-value.  From my testing, it seems to work.  I find this fascinating and wonder if it could be proven that optimistic thinking (within these limits) is actually a sound policy for life in general.  This may sound a bit off-topic, but I don't think so.  I universal truth that can actually be codified would be a real discovery, imho.

Question: is it a universally sound policy to use the "high" confidence probability in the formula:

$ActionValue = P(X) \cdot Value(X)$ <- utility theory, reinforcement learning

So, $P(X)$ will have a confidence interval based on the number of samples.  You can optimistically just use $P(X) + confInterval / 2$ to get $Popt(X)$.  This seems to work well in practice.  Is this a universal truth?

The main idea of following upper confidence bounds is minimizing regret, that is, the difference between the received reward and the maximum. The paper to read on this is: "Finite-time analysis of the multiarmed bandit problem" by Peter Auer, Nicoló Cesa-Bianchi, and Peter Fischer.

If we interpret life as a Markov Decision Process, then most reinforcement learning theories apply quite well. I.e. we want to keep an open mind, but we want to do what we think is best exponentially more often than exploratory actions.

Of course, interpreting life as an MDP is a bit of a stretch — foresight, for example, has to be interpreted as simulated experience, but I believe one can find quite a lot of wisdom in reinforcement learning and artificial intelligence in general.


Does an initial algebra for a class have to belong to the class itself? In the context of algebraic data types, a concept of initial algebras is usually defined, e.g., in the following way:

  An algebra $S$ is initial in a class $C$ of algebras iff for every $A\in C$ there exists a unique homomorphlsm $h_A\colon S → A$.

At least "Initial Algebra Semantics and Continuous Algebras by" J. A. Goguen, J. W. Thatcher, E. G. Wagner, J. B. Wright states it this way. The proofs in that paper seem to imply that $S$ is assumed to belong to $C$ in the above definition.  Now, I'm wondering whether this restriction is meaningful. Put differently, has some reputable work defined an initial algerba for a class in such a way that the algebra is allowed to lie outside of the class?

Yes, the initial algebra is by definition one of the members of the class for which it is initial.

You may however be interested in the category-theoretic concept of a limit. Given a diagram (a collection of objects and morphisms between them), we can ask for an object which "best approximates" the diagram, but needs not be an element of the diagram. There are two such "best approximations", namely limit and colimit. The limit is like an initial algebra.


Stable order on binary strings I need some order on binary strings such that if I have a small (but superlinear in their length) number of sufficiently different strings, the order will stay the same if I change a few bits in the strings.

For example, lexicographic order does not satisfy this property because it may be possible to change the order of the string by changing just one bit.

On the other hand, order according to the number of ones is not good either because it only works for linear number of strings.

Is there such an ordering?

Edit: A solution which only works for random strings is also of interest to me.

No. Given any linear ordering of the $n$-bit strings, find a sequence of at most $n+1$ strings going from the first string in the ordering to the last string in the ordering by single-bit changes per step. Some two adjacent strings $x$ and $y$ in this sequence must be at least $2^n/n$ steps apart from each other in the ordering. But then, unless your definition of "far" only allows linearly many strings to be far apart from each other, there must be some $z$ that is far from $x$ and $y$ but between them in the ordering. So changing one bit from $x$ to $y$ reverses the ordering with $z$.


Explain P = NP problem to 10 year old It is my first question on this site. I am taking a master's course on theory of computation. How you would explain P = NP problem to a 10 year old child and why it has such a monetary reward on it?

Your take?

I will update the question as my head gets clear about it.

I use these 3 slides to show why it so hard (impossible?) to come up with a fast algorithm for an NP problem:


Problems with exponential lower computational complexity bound I am looking for problems which have an algorithm with asymptotically optimal exponential computational complexity or the problem has a lower bound of exponential computational complexity for algorithms to solve the problem.

I am not looking for problems, where this is implied because the solution can be exponential in size.

If you know any, it would be very kind if you can share it with me.

Given a Turing machine $T$ and an a number $n$ encoded in unary, decide whether $T$ halts in time $2^n$. There is an $O(C^n)$ algorithm for this, and there's an almost matching $\Omega(c^n)$ lower bound (where $c < C$). See the proof of the Time Hierarchy Theorem.

If you're looking for more natural problems, Wikipedia has a list of EXPTIME-complete problems, such as evaluating positions in certain generalized versions of board games, and problems involving succinct circuits.


Terminology for sparse cuts in graphs I have found some ambiguity in how the graph parameters edge-expansion, uniform sparsest cut and conductance are defined and denoted.

My questions are: what are the definitions that best match the primary sources and the current use? Does what follows sound right?

(1) The Cheeger constant of a graph, denoted $h$ is

$h(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\min\{ |S|, |V-S| \}}$

where $\textrm{Edges}(S,V-S)$ denotes the number of (or the total weight of) edges with one endpoint in $S$ and one endpoint not in $S$.

(2) The uniform sparsest cut of a graph, denoted $\phi$ is

$\phi(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{|S| \cdot |V-S|}$

Notes:

 $h$ is also called the edge expansion of $G$
 $h$ and $|V|\cdot \phi$ are within a factor of 2, so approximating one problem is equivalent to approximating the other, up to a constant loss in the approximation ratio

(3) The conductance of a graph, unfortunately also usually denoted $\phi$. Maybe we should use $\sigma$ for the sparsest cut parameter?

$\textrm{conductance}(G) := \min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\min\{ \textrm{vol}(S), \textrm{vol}(V-S) \}}$

where $\textrm{vol}(S)$ is the sum of the degrees of the vertices of $S$

Note:

 If $G$ is $d$-regular, then $\textrm{conductance}(G) = h(G)/d$. In the irregular case, the conductance is incomparable with $h$ and $\phi$

(4) Finally, as an intermediate problem to use to give relaxations of the conductance problem, I have seen the following problem, that does not seem to have a name ("volume-weighted sparsest cut"? what letter should be used to denote it?)

$\min_{S\subseteq V, S\neq \emptyset, S\neq V} \frac{\textrm{Edges}(S,V-S)}{\textrm{vol}(S) \cdot \textrm{vol}(V-S)}$

which is $\phi/d^2$ in regular graphs, and that scaled by $\textrm{vol}(V)$ is within a factor of 2 from the conductance.

I think (2) is called the uniform sparsest cut. The term non-uniform is used for the version where each pair ij of vertices has a separate demand d(ij) and the cut sparsity is E(S,V-S)/d(S,V-S) where d(S,V-S) is the demand between S and V-S.


Difference between Types and Sorts This may be a very simple question.

But what is the difference between types and sorts?

My current understanding is that you have a type theory with type rules that give a notion of a well-typed statement but sorts are more basic, differentiating symbols into different sorts of symbols and introducing basic rules on function application etc.

Perhaps there is little difference, maybe they just come from different fields. But I can't seem to find a clear description of their relation.

The way I understand the difference is that the two concepts are used to give slightly different emphasis, but ultimately they are kind of the same thing. Since neither has a formal definition we cannot expect an exact answer without first limiting the scope to a particular understanding of "type" and "sort".

"Sort" is used when we want to say that there are several different, well, sorts of things that we need to distinguish. An example would be a theory of geometry with sorts "point" and "line".

"Type" is used when not only is there a need to distinguish different sorts of things, but proper attention is paid to the structure of the sorts/types themselves. Thus, typically we can form new types from old ones (products, sums, function types), we can have interesting relations between types (type equality, subtyping), etc. In contrast, one typically just specifies some sorts at the beginning, and then never pays much attention to the structure of the class of all sorts.

This at least is how I percieve the difference, other people may have different experiences.


Counting the number of K4 I was going over this paper and I don't understand a certain proof (section five phase 2).

Given a graph G=(V,E) partitioned into the sets of vertices L and H. The vertices in L are at most D where D is an arbitrary number and the rest of the vertices are in H.

If we take a closer look at Phase 2 (Theorem 5). For each vertex x in L compute the square of the adjacency matrix of G[N(x)] to decide whether G[N(x)] contains a triangle.

We know that the fastest way to find a triangle in a graph is using fast matrix multiplication algorithm which is $O(n^\alpha)$. So, we can define a running time of $\sum_{x \epsilon L}^{ } d(x)^\alpha$. Since we know that |L| can be at most e (number of edges) if we choose a bad D and d(x) is at most D, why Phase 2 can be done in $O(D^{\alpha-1}e)$. I was under the impression that it was $O(D^{\alpha}e)$ i.e. where is the $\alpha-1$ coming from? I'm pretty sure it's trivial, but I'm missing the point.

The sum of all degrees $d(x)$ in a graph is at most $2e$. The sum of all $d(x)^{\alpha}$ is at most $(max degree)^{\alpha -1}$ times sum of all $d(x)$. Together these give the upper bound.


Common insights into hypothetical complexity of graph problems I came across two examples of hypothetical hardness of some graph problems. Hypothetical hardness means that refuting some conjecture would imply the NP-completeness of the respective graph problem. For instance, Barnette's conjecture states that every 3-connected cubic planar bipartite graph is Hamiltonian. Feder and Subi proved that refuting the conjecture would imply the NP-completeness of the Hamiltonian cycle problem on graphs in the class of the conjecture.

Tutte's 5-flow Conjecture states that every bridgeless graph has a nowhere-zero 5-flow. Kochol showed that if the conjecture is false, then the problem of determining whether a cubic graph admits a nowhere-zero 5-flow is NP-complete.

  Are there common insights into the above conjectures that explain the hypothetical NP-completeness of the corresponding graph problems? Are there other examples of hypothetical complexity in the above sense?

P.S. This was posted on MathoverFlow without getting an answer.

Here are two references for the second part of your question.

The paper [1] addresses certain types of colorability of sparse graphs with given girth $g$. For every fixed $g$, they show that the associated decision problem is either trivial (every graph in the class has a coloring) or NP-complete. But determining which is the threshold value of $g$ remains a difficult open problem!
Edit: One of the considered problems is related to Jaeger's conjecture, that every planar graph of girth $4k$ admits a homomorphism to $C_{2k+1}$. It is shown in [1] that any counterexample directly provides a hardness proof. (A similar conjecture by Klostermeyer and Zhang exists for the odd-girth.) For the other problems considered in [1], there is no official conjecture, but for any guess about the correct threshold value $g$ that one can make, if proved false by a counterexample, the latter directly implies a corresponding hardness proof.

In the introduction of the above cited paper is also mentioned the following interesting result about SAT [2]. It is proved there that for every $k$, there exists a function $f(k)$ such that $(k,f(k))$-SAT (i.e. $k$-SAT where each variable occurs $f(k)$ times) is trivial, but $(k,f(k)+1)$-SAT is NP-complete. (The precise value of $f(k)$ seems unknown, although some estimate is given.)

[1] L. Esperet, M. Montassier, P. Ochem and A. Pinlou. A complexity dichotomy for the coloring of sparse graphs. Journal of Graph Theory 73:85-102, 2012. link + PDF on an author's website

[2] J. Kratochvil, P. Savicky and Zs. Tuza. One more occurrence of variables makes satisfiability jump from trivial to NP-complete. SIAM Journal on Computing 22:203-210, 1993. link


Why is Metric TSP's best possible achieved approximation ratio believed to be 4/3? Is it just that integrality gaps (LP/IP) for specific instances do not give more than 4/3? Thanks in priori.

To my knowledge this is the only reason and I am not sure whether everybody in the fields agrees with this.

The optimistic reasoning is: Since there has not been any progress in getting a larger lower bound, $4/3$ is the right bound. And once we know this for sure, we "only" need a polynomial time rounding algorithm.

More pessimistic people will view the $4/3$ only as a lower bound. To beat this,
you need an algorithm that does not "use" the Held-Karp relaxation, even not in a hidden way.

Even more pessimistic people would say that $3/2$ is the right bound, because nobody could improve Christofides algorithm (ignoring some of the recent progresses.)

Note that for metric ATSP, the integrality gap is at least $2 - \epsilon$
(Charikar, Goemans, Karloff, FOCS 2004)