Forcing an honest behavior How can you force a party to be honest (obey protocol rules)?

I have seen some mechanisms such as commitments, proofs and etc., but they simply do not seem to solve the whole problem. It seems to me that structure of the protocol design and such mechanisms must do the job. Does any one have a good classification of that.
Edit
When designing secure protocols, if you force a party to be honest, the design would be much easier though this enforcement has its own pay-off. I have seen when designing secure protocols, designers assume something which does not seem realistic to me, for instance to assume all the parties honest in worst case or assuming honesty of server which maintains user data. But when looking at design of protocols in stricter models, you rarely see such assumptions (at least I haven't seen it - I mostly study protocols over UC framework of Canetti which I think it is not totally formalized yet). I was wondering, is there any good classification of the ways in which you can force a party to be honest or is there any compiler which can convert the input protocol to one with honest parties?
Now I am going to explain why I think this merely does not do the job though it may seem irrelevant. When designing protocols in the UC framework, which benefits from ideal/real paradigm, every communication link in the ideal model is authenticated, which is not true in the real model. So protocol designers seeks alternative methods to implement this channel through means of PKI assumption or a CRS (Common Reference String). But when designing authentication protocols, assuming authenticated channels is wrong. Suppose that we are designing an authentication protocol in the UC framework, there is an attack in which adversary forges identity of a party, but due to assumption of authenticated links in the ideal model this attack is not assumed in this framework! You may refer to Modeling insider attacks on group key exchange protocols. You may notice that Canetti in his seminal work Universally composable notions of key exchange and secure channels mentions a previous notion of security called SK-Security which is simply enough to assure security of authentication protocols. He somehow confesses (by stating that this is the matter of technicality) that UC definition in this context is too restrictive and provides a relaxed variant called non-information oracle (which confused me, cause I haven't seen this model of security any where, I cannot match this security pattern with any other security pattern, probably my lack of knowledge :D).

[As a side note, You can nearly have any Sk-secure protocol converted to a UC secure one regardless of simulator time. For instance you may just remove the signings of the messages and have the simulator simulate the whole interactions in dummy way. See Universally Composable Contributory Group Key Exchange for proof! Now suppose this is a group key exchange protocol with polynomially many parties, what would be the efficiency of the simulator?? This is the origin of my other question in this forum.]

Anyway, due to lack of commitment in the plain model (over UC), I sought other means to make the protocol secure by just bypassing the need for that relaxation. This idea is so very basic in my mind and has come to my mind by just having studied latest commitment scheme of canetti in the plain model: Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions.
BTW, I don't seek zero-knowledge proofs because due to reason which I don't know, whenever someone has used one of them in a concurrent protocol (over UC framework), the others has mentioned the protocol as inefficient (may be due to rewinding of the simulator).

Alas, you can't force people to do what the protocol says they should do.

Even well-meaning people who intended to follow the protocol occasionally make mistakes.

There seem to be at least 3 approaches:

crypto theory: assume "good" agents always follow the protocol, while "malicious" agents try to subvert the protocol. Design the crypto protocol such that good agents get what they need, while malicious agents get nothing.
game theory: assume every agent looks out only for his own individual interest. Use mechanism design to maximize the total benefit to everyone.
distributed fault-tolerant network: assume every agent makes an occasional mistake, and a few 'bot agents spew out many maliciously-crafted messages. Detect and isolate the 'bot nodes until they are fixed; use error detection and correction (EDAC) to fix the occasional mistake; use convergent protocols that eventually settle into a useful state no matter what initial mis-information is stored in the routing tables.

mechanism design
In game theory, designing a situation (such as setting up the rules of an auction) such that people who are selfishly looking out only for their own individual interests end up doing what the designer wants them to do is called "mechanism design".
In particular, using implementation theory, situations can be designed such that the final outcome maximizes the total benefit to everyone, avoiding poorly-designed situations such as the "tragedy of the commons" or "prisoner's dilemma" where things happen that are not in anyone's long-term interest.

Some of the most robust such processes are designed to be incentive compatible.

The game theory typically makes the simplifying assumption that all relevant agents are "rational".
In game theory, "rational" means that an agent prefers some outcomes to other outcomes, is willing and able to change his actions in a way that he expects (given the information available to him) will result in a more preferred outcome (his own narrow self-interest), and he is smart enough to realize that other rational agents will act similarly to try to obtain the outcome that is most preferred out of all the possible outcomes that might result from that choice of action.

A designer may temporarily make the simplifying assumption that all people only act according to their own narrow self-interest.
That assumption makes it easier to design a situation using implementation theory.
However, after the design is finished,
it doesn't matter whether people act according to their own narrow self-interest ( "Homo economicus" ),
or whether they are altruistic and want to maximize the total net benefit to everyone -- in a properly designed situation, both kinds of people make exactly the same choices and the final outcome maximizes the total benefit to everyone.

convergent protocols

When designing a routing protocol,
each node in the network sends messages to its neighbors passing on information about what other nodes are reachable from that node.

Alas, occasionally these messages have errors.
Worse, sometimes a node is mis-configured and spews out many misleading and perhaps even maliciously-crafted messages.

Even though we humans know the message might be incorrect, we typically design the protocol so that a properly-functioning node trusts every message and stores the information in its routing table, and makes its decisions as if it believes that information to be entirely true.

Once some human turns off a bad node (or disconnects it from the network), we typically design the protocol to rapidly pass good information to flush out the corrupt information, and so quickly converge on a useful state.

combined approaches

Algorithmic mechanism design
seems to try to combine the fault-tolerant network approach and the game-theory mechanism approach.

@Yoichi Hirai and Aaron, thank you for pointing out some interesting attempts to combine game theory and cryptography.


Viola's Reduction of 3XOR to listing triangles Apparently this was due to Pătraşcu, but in this report on the ECCC server, Viola states that 3XOR can be reduced to listing triangles.

  Assume that given a graph in adjacency list format, with $m$ edges, $z$ triangles, $O(m)$ nodes, one can list $\min\{z,m\}$ triangles in time $m^{(4/3)-\varepsilon}$ for $\epsilon>0$ constant. Then one can solve 3XOR on a set of size $n$ in time $n^{2-\epsilon'}$ with error $1\%$ for a constant $\epsilon'>0.$

My question is the reverse. If one were to have an efficient algorithm for 3XOR, what could one say about efficiently listing triangles?

[Copying here the answer from here]

  In this paper, Corollary 1, we show that if you solve 3XOR in close to linear time then you can list $t$ triangles in a graph with $m$ edges in time $m\cdot t^{1/3},$ ignoring lower-order terms.


Compactness of domino tilings I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted.  This sounds like a compactness property, but I don't see how easy can be proven.

I added the tag "automata theory" because there is a correspondence between Wang tilings and finite state transducers.

Yes, this is a compactness property.

Let $X$ be the region you want to tile, and $T$ the finite set of possible tiles. The space $T^X$ of all assignments of tiles to $X$ is compact by Tychonoff’s theorem. For any finite $X_0\subseteq X$, the set $C_{X_0}\subseteq T^X$ of all correct tilings of $X_0$ is closed (in fact, clopen), and since $C_{X_0\cup X_1}\subseteq C_{X_0}\cap C_{X_1}$, they generate a filter. Thus, assuming every finite subset of $X$ can be tiled, the system $\{C_{X_0}:X_0\subseteq X\text{ finite}\}$ has fip, and by compacteness, its intersection is nonempty. This intersection is the set of all correct tilings of $X$.

Instead of all finite $X_0$, it suffices to use any family of finite subsets which is upwards directed and covers $X$, such as, in your case, the set of all finite square subregions of the plane.

Alternatively, you may set up the argument to use the compacteness of classical propositional logic: let $\{p_{x,t}:x\in X,t\in T\}$ be a set of propositional variables, and let $C$ be the theory consisting of the formulas
$$\begin{gather*}
\bigvee_{t\in T}p_{x,t},\qquad x\in X,\\
\neg(p_{x,t}\land p_{x,t'}),\qquad x\in X,t\ne t'\in T,
\end{gather*}$$
and
$$\neg(p_{x,t}\land p_{x',t'})$$
for all $x,x'\in X$ that are neighbours, and $t,t'\in T$ that are incompatible when placed on $x$ and $x'$, respectively. If each finite subset of $X$can be tiled, then $C$ is consistent, and any satisfying assignment gives a tiling of $X$.


A Simple Auction Game You are playing the following game.

You have a budget of $B$ dollars. There are $n$ days. Every day $d$, you have to make a bid $b_d\geq0$ that does not exceed your budget. After making the bid, a product appears with price $p_d\leq B$ dollars. If your bid is larger than the price, you buy the product, i.e., $b_d\geq p_d$, and you lose $b_d$ from your budget. Otherwise, you will be left with the same budget as before but you don't buy the product, i.e., if $b_d<p_d$. The next day the same thing happens and so forth. You stop the game when you spend all of your budget or day $n$ is reached. Your objective is to buy as much products as possible with budget $B$.

Can we find a policy that competes against an adversary and buy a "good" number of products? Good here means, for example, a policy with low regret, so the difference between what the adversary bought and what you bought is not large. If we can't, what assumptions could we make to make the regret low?

My policy so far is:

For each day $d=1..n$, bid $b_d=B_r/(n-d+1)$, where $B_r$ is your remaining budget.

I was trying to find an input sequence that makes my policy perform badly but I didn't succeed (for large $n$). I think if $n$ is large, then we may reach a low regret with this policy. I am still trying to prove this.

The problem is equivalent to online knapsack problem. Let $n$ represents the number of items. Let the knapsack has capacity $B$. Every item $i$, has value $v_i=1$ and weight $w_i=p_i$.

The offline optimal solution:

Sort the items in increasing order of their weights ($p_{\sigma(1)}\leq p_{\sigma(2)}\leq \cdots \leq p_{\sigma(n)}$ for some permutation $\sigma$).
Let $S\gets\emptyset$.
For $i\gets1$ to $n$: add $\sigma(i)$ to $S$ unless $\sum_{i\in S}p_i>B$.
For each $i\in S$, bid $b_i=p_i$ and for each $i\notin S$, bid $b_i=0$.

Claim: No online algorithm can achieve any non-trivial competitive ratio [1].

If we assume that $p_i=o(B)$ and $L\leq p_i\leq U$, then there is a competitive ratio of $\ln(U/L)+1$ [2].

For the regret, I don't know if there is some algorithm that achieves low regret (under some assumptions).


A subset grouping problem I'm trying to reduce the following problem to a more well-known formulation.

I have a bunch of subsets $\{S_i \}_{i \in I}$ of some finite set.

I would like to put them into (disjoint) groups $\{ G_j \}_{j \in J}$ such that $\max_{j \in J} \left| \bigcup \{S \in G_j\} \right|$ is as small as possible.
The number of groups $|J|$ is a fixed constant $k$.

An example: $k = 2$, $S_1 = \{a, b\}$, $S_2 = \{b, c\}$.

If $G_1 = \{S_1\}$ and $G_2 = \{S_2\}$, then

$$ \max_{j \in J} \left| \bigcup \{S \in G_j\} \right| = \max\{|S_1|, |S_2|\} = 2$$

If instead $G_1 = \{S_1, S_2\}$ and $G_2 = \{\}$, then

$$ \max_{j \in J} \left| \bigcup \{S \in G_j\} \right| = \max\{|S_1 \cup S_2|, |\{\}|\} = 3$$

so the latter grouping is worse than the former.

The problem is NP-complete already for $k=3$ (and I guess also for $k=2$).
We reduce the following problem to it:
For an input $r$-regular graph $G$, decide whether $G$ has an equitable $3$-coloring, i.e., one where the size of each color class is the same.
(I couldn't find a reference for this, but one can easily reduce the classical $3$-coloring problem to this by adding a few extra vertices and edges.)

The reduction is as follows.
For each vertex $v$ of the input graph $G$, define a set $S_v=\{\{u,v\}\mid uv\notin E(G)\}$.
For any subset $X$ of the vertices we have

$$|\cup_{\{v\in X\}} S_v|=|X|(n-1-r)-|X_2|$$

where $X_2$ is the set of non-adjacent pairs in $X$.
If $|X|\ge n/3$, this is at least

$$\frac{n(n-1-r)}3-\binom{\frac n3}{2}$$

with equality only if $|X|=n/3$ and all pairs in $X$ are non-adjacent.
Since in any grouping of the $S_v$ into three groups we have such an $X$, we are done.


Exponential Concentration Inequality for Higher-order moments of Gaussian Random Variables Let $X_1,\ldots, X_n$ be $n$ i.i.d. copies of  Gaussian random variable $X \sim N(0, \sigma^2)$. It is known that
\begin{align}
\mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n X_j \Bigl| >t\Bigr) &\leq 2 \exp( cnt^2)~~\text{and}\\
\mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n (X_j^2 - \mathbb{E}X_j^2) \Bigl| >t\Bigr) &\leq 2 \exp( cn\min \{t^2, t\}).
\end{align}
These two results follows from the concentration inequality of sub-Gaussian and sub-exponential random variables and the second one is a Bernstein-type inequality. I wonder if there are similar results for the higher moments of Gaussian random variables. Can one have
\begin{align}
\mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n (X_j^4 - \mathbb{E}X_j^4) \Bigl| >t\Bigr) \leq 2 \exp( cnt)?
\end{align}
And more generally, for a centered random variable $Y$ satisfying $\mathbb{P}(|Y| > t) \leq 2 \exp(c t^{\alpha})$ for $\alpha > 0$, can we get an exponential inequality for the concentration of $\sum_{i=1}^n Y_i$? That is, can we have
\begin{align}
\mathbb{P}\Bigl( \Bigl|\frac{1}{n}\sum_{j=1}^n (Y_j - \mathbb{E}Y_j) \Bigl| >t\Bigr) \leq 2 \exp( cnt^\beta)
\end{align}
for some $\beta > 0$？

See Theorem 23 in Section 9.3 of Ryan O'Donnell's book Analysis of Boolean functions. Even though the theorem there is stated for $\pm 1$ variables, it holds for Gaussians as well (see Chapter 10 of the book for details on that).

For the more general statement, see Exercise 7 in these lecture notes of Terry Tao.


Applications of metric structures on posets/lattices in theoryCS Since the term is overloaded, a brief definition first. A poset is a set $X$ endowed with a partial order $\le$. Given two elements $a,b \in X$, we can define $x \vee y$ (join) as their least upper bound in $X$, and similarly define $x \wedge y$ (meet)(join)as a greatest lower bound.

  A lattice is a poset in which any two
  elements have a unique meet and a
  unique join.

Lattices (in this form) show up in theoryCS in (briefly) the theory of submodularity (with the subset lattice) and clustering (the partition lattice), as well as in domain theory (which I don't understand too well) and static analysis.

But I'm interested in applications which use metric structures on lattices. A simple example comes from clustering, where any antimonotone submodular function $f : X \rightarrow R$ (antimonotone means that if $x \le y, f(x) \le f(y)$) induces a metric
$$d(x,y) = 2f(x \wedge y) - f(x) - f(y)$$

This metric has been used extensively as a way to compare two different clusterings of a data set.

Are there other applications of lattices that care about metric structures ? I've been interested in the domain theory/static analysis application, but so far I've not seen any need for metrics.

First, a comment. Your question sort of depends on how geometrically you intend to mean the word "metric". It's reasonably common to use ultrametrics in semantics and static analysis, but ultrametrics tend to have a combinatorial rather than a geometric interpretation. (This is a variant of the observation that domain theory has the flavor of a combinatorial rather than geometric use of topology.)

That said, I'll give you an example of how this comes up in program proofs. First, recall that in a program proof, we want to show that a formula describing a program holds. In general, this formula does not necessarily have to be interpreted with the booleans, but can be drawn from the elements of some lattice of truth values. Then a true formula is just one which is equal to the top of the lattice.

Furthermore, when specifying very self-referential programs (for example, programs that make extensive use of self-modifying code) matters can get very difficult. We typically want to give a recursive specification of the program, but there might not be an obvious inductive structure upon which to hang the definition. To solve this problem, it's often helpful to equip the truth value lattice with extra metric structure. Then, if you can show that the predicate whose fixed point you want is strictly contractive, you can appeal to Banach's fixed point theorem to conclude that the recursive predicate you want is well-defined.

The case I am most familiar with is called "step-indexing". In this setting, we take our lattice $\Omega$ of truth values to be downwards-closed subsets of $\mathbb{N}$, whose elements we can loosely interpret as "the lengths of the evaluation sequences on which the property holds". Meets and joins are intersections and unions, as usual, and since the lattice is complete we can define the Heyting implication as well. The lattice can also be equipped with an ultrametric by letting the distance between two lattice elements be $2^{-n}$, where $n$ is the smallest element in one set but not the other.

Then, Banach's contraction map thoerem tells us that a contractive predicate $p : \Omega \to \Omega$ has a unique fixed point. Intuitively, this says that if we can define a predicate which holds for $n+1$ steps using a version which holds for $n$ steps, then we actually have an unambiguous definition of a predicate. If we then show that the predicate equals $\top = \mathbb{N}$, then we know that the predicate always holds of the program.


Is it worthwhile to try to prove a conjecture by mapping it to a Turing machine? Lets assume the proof of a conjecture, for example, the famous Goldbach conjecture. Is it possible to try to prove or disprove such a conjecture by devising a Turing machine that accepts if the proof is possible.
So, for Turing machine M,

If, the conjecture is provable, accept, else reject.

So, in essence, we don't try to find a proof of the conjecture, but, try to find whether its provable, something like zero-knowledge proofs.

Additional Details:
I felt the way most of these conjectures go, is they say: For all n, C holds true.
So, in essence, even if it can be shown that C holds up to some n, but, it hasn't been able to be derived for all n. And, this seems to bear a striking similarity to the Halting problem. So, I felt a mapping must be worthwhile to study/research.

First, you don't need to turn them into Turing machines, it is essentially the same as running a proof search algorithm. The logical complexity of the formula (which in the cases you have in mind are $\Pi^0_1$) has no effect on this, searching for proofs in any effective theory (like ZFC, for proof to make sense you have to fix a theory) can be done in a straight forward manner, the set of provable statements for any effective theory is $\Sigma^0_1$ and therefore computable enumerable.  But there are no reasons to do that, you don't gain anything a priori just by adding one extra unnecessary layer of coding, it has no benefit (AFAIK).

Also don't confuse proof search with a direct reduction from the truth of a $\Pi^0_1$ statement to the halting problem (which exists as not halting is $\Pi^0_1$-complete).

Second, consider the much simpler case of propositional tautologies in place of first-order statements like GC. (propositional tautologies is a coNP set also known as $\Pi^B_1$). The state of art proof search algorithms (i.e. SAT solvers) are exponentially inefficient in finding proofs of very simple finitary mathematical statements like the pigeon-hole principle tautologies. You can run a first-order proof search program to look for a ZFC proof of GC but I haven't seen any interesting mathematical statement being discovered/proven by unguided brute-force search of proofs. So there is no example of this being useful. (For human-guided use of computer in proving mathematical theorems we have the four colors theorem.)

Third, if you use a proof search algorithm you will only know if there is a proof, if there isn't any you will not know and the algorithm will continue forever without halting. In other words, you can't write a program like the one you have stated in the question (which is why I commented that this is more suitable for CS Q&A site since this is very basic mistake in computability theory).

See also my answers to similar questions on math and CS.


Normal forms for intuitionistic formulas? It is well-known that DNFs/CNFs and prenex normal forms generally do not exist for intuitionistic logic.

Are there any nice results about formula normalization for IL?  I've tried googling this but the results just end up being about normal forms for proofs.

There are two main ways you could take this.

If you are interested in provability, then what you want is the Gödel-Tarski embedding of intuitionistic logic into classical S4 modal logic.  The  idea is that you can interpret the box modality of modal logic as a "provability" modality, and then stick a box in front of each connective. Then you can put the formula into whatever variant of modal CNF you need.
See Mints' paper The Gödel-Tarski Translations of Intuitionistic Propositional Formulas.

If you are interested in retaining the ability to translate intuitionistic proofs, then one popular idea is to use Tarski's "high school identities" to put intuitionistic formulas into a normal form related to the exponential polynomials. This gives a normal form for types, whose translation preserves the beta-eta equivalence of proofs of that type.
See Danko Ilik's The exp-log normal form of types.

Both of these papers are about the propositional case. I don't know what happens with first-order quantifiers.


Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees? I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally:

It uses O(1) space
It can be updated to reflect an insertion or deletion in O(1) time
Two identical collections (i.e., collections that have the same elements with the same multiplicities) should always hash to the same value, and two distinct collections should hash to different values with high probability (i.e., the function is independent or pairwise independent)

One initial attempt at this would be to store the product modulo a random prime of the hashes of the individual elements. This satisfies 1 and 2 but it's not clear whether it, or a close variation, would satisfy 3.

I originally posted this on StackOverflow.

*Properties 1 and 2 could be relaxed a little to, say, O(log n), or a small sublinear polynomial. The point is to see whether we can identify multi-sets and reliably test equality without storing the elements themselves.

If you think of sets as living in universe $[u]$, it is quite easy to solve your problem with $O(\lg u)$ update time. All you need is a fast hash function for a vector of $u$ numbers, with fast "local updates".

Wikipedia/Universal hashing suggests $h(\vec{x}) = \big(\sum_{i=1}^{u} x_i a^i \big) \bmod{p}$, where $p$ is a large enough prime and $a$ is uniformly drawn from $[p]$. When you add or remove element $i$, you have to add/subtract $a^i$ from the hash code, which takes $O(\lg i)$ time using divide and conquer for the exponentiation. Since a polynomial of degree $u$ can only have $u$ roots, the probability of collision for two distinct sets is $O(u/p)$. This can be made very small by taking $p$ to be large enough (for instance, $p=u^2$ and you work in "double precision"). If the sets are much smaller than $[u]$, you can of course begin by hashing the universe down to a smaller universe.

Does anybody know a solution with $O(1/p)$ collision probability when hashing to range $[p]$? This ought to be possible.


What is this notation style called? I was reading a paper about implementing the statistical programming language R on the JVM, and encountered this notation I haven't seen before (I'm not formally CS-trained). What is the name of notational style? I've seen it before in other papers--usually as it related to functional programming and the REPL.

It is notation for Formal Proofs and specification of language grammar in Backus-Naur Form.


Connectivity of a random regular graph of degree $d$ An Erdos-Renyi graph over $n$ vertices and average degree $d$ is not connected whp iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be connected? In particular will this be connected for some degree less than $\log n$?

For constant $d \geq 3$, a random $d$-regular graph is connected with high probability. In fact, it is an expander with high probability. See for example this note by David Ellis. Friedman even showed that a random $d$-regular graph has nearly optimal spectral gap, with high probability.


Undecidable problems not Turing-complete? are there systems whose nontrivial properties can't be decided by Turing machines, but for which a Turing machine with an oracle able to find out these properties isn't able to solve the Halting problem (for ordinary TMs)?

Yes, there are intermediate degrees.  One way to see this is that there are computably enumerable sets that are Turing incomparable.  See https://secure.wikimedia.org/wikipedia/en/wiki/Turing_degree for some basic information.


On theoretical aproaches for solving $\mathsf{SAT}$ in special cases In what cases $\mathsf{SAT}$ can be solved in polynomial time?

I know two cases: $2$-$\mathsf{SAT}$ and Horn-$\mathsf{SAT}$.

Question 1: Is there a reference with algorithms for solving $\mathsf{SAT}$ effectively in some other cases?

I think that it is important to understand in what case $\mathsf{SAT}$ can be solved effectively. It can be related to the problem of understanding of effectivity of $\mathsf{SAT}$-solvers. And this is why I am surprised why there are small papers about this theme (it would be nice if I am wrong).

In fact there is a simple method for generating examples when $\mathsf{SAT}$ can be solved effectively:  Consider some $\mathsf{L}\in\mathsf{P}$.  For every $x$ there exists $\mathsf{CNF}$ $\phi_x$ such that $x\in\mathsf{L}\iff\phi_x$ is satisfiable. So, for $\mathsf{CNF}$ of kind $\phi_x$ there exists a polynomial algorithm for $\mathsf{SAT}$.

Example: Consider $\mathsf{L}$ to be $2$-$\mathsf{COLORING}$. This problem is reduced to $2$-$\mathsf{SAT}$ problem.

Question 2: Are there any other examples when a problem from $\mathsf{P}$ can be reduced to $\mathsf{CNF}$ of some adequate form (i.e. it is possible to analyse it and understand why it can be solved in polynomial time)?

Concerning Question 1, there have mainly been two lines of work to find tractable restrictions of SAT.

The first one that you are already familiar with is to restrict the types of the clauses that you are allowed to use. For example, in 2-SAT, you are only allowed to use size two clauses. In Horn-SAT, you only allow Horn clauses etc. The tractable restrictions for SAT have been completely classified by Schaefer in 1978 [1] in his celebrated dichotomy Theorem. The result is a dichotomy in the sense that Schaefer showed that the restriction gives you either a problem in P or an NP-complete problem. It has later been generalized to the problem of counting the satisfying assignments [2] or to the problem of enumerating them [3].

Some of these restrictions indeed lead to better performances of SAT solvers. For example, on a 2-SAT instance, unit propagation will naturally solve the instance in polynomial time and one can observe a similar behavior for Horn clauses. However SAT solvers rarely try to detect if the input is of such a form as it would be too costly to scan all clauses (for hardcore SAT-solver people, linear time is already too slow ;)). So for example, affine formulas will often not be detected (CryptoMiniSat may be an exception here).

The second line of research is to look for tractable instances by trying to uncover some structure in the way the variables interact with the clauses. For example, given a CNF formula, you can look at its incidence graph: it is a bipartite graph whose vertices are the variables and the clauses of the formula and you have an edge between a clause $C$ and a variable $x$ if $x$ or $\neg x$ is in $C$. Now, if this graph is a tree, you can solve SAT in polynomial time by doing some dynamic programming on the tree.

Many results extend this observation and most of them are interested in the parametrized complexity of SAT. For example, a well-known parameter of graphs is the treewidth, an integer that intuitively measures how far a graph is from being a tree. Now, if the incidence graph from above has treewdith $k$, we know algorithms to solve SAT in time $2^{O(k)}\mathsf{size}(F)$, that is, a linear time algorithm if the treewidth is bounded. An early and good survey of these results have been written by Szeider in 2003 [4]. The earliest result of this kind for SAT I am aware of is a paper by Dantsin [5] where he apparently shows the tractability of SAT on bounded branch width graphs (the paper is in Russian and I have never read it but I trust Alekhnovich and  Razborov [6] which improved the result in 2002). Many things have been understood since, for more general parameters and for more general problems (#SAT for example). I am shamelessly citing my thesis here as it contains a whole chapter reviewing most recent improvements on the question since then [8].

The idea of restricting the structure of the input through some associated graph has however been transpiring in computer science in many other domains as early as the 80's. See for example the Yannakakis algorithm for conjunctive queries in databases [7].

Now these tractable instances of SAT do not explain the good performances of SAT-solvers at all. Most of the algorithms used to solve these instances are not directly related to the way SAT-solvers work. But for more complex problem such as #SAT, the links between the theoretical algorithms and the way solvers work in practice is much stronger.

Some work has been done to understand the performances of SAT solvers by analyzing the structure of the formula (by detecting communities for example) but I do not know the literature well enough and let someone more competent than me answer this. All I can say is that it is not really related to the fact that the input belongs to some tractable instance. What you need is good heuristics to quickly converge to one solution. When there is no solution, then proof complexity is also a way of understanding the performances of a SAT-solver as it constructs a refutation of the formula while solving it. Thus, if no small refutation exists, then you can derive a lower bound on the runtime of the solver. But again, this is not completely enough to explain the performances of the SAT solver.

Concerning Question 2, I am not aware of any problem that have been discovered to be in P by reducting to a tractable class of SAT as usually, it is easier to program an algorithm than to encode it into a restricted formula. Moreover one generally prefers direct algorithms because they give more insights on the problem. However, a recent paper by Lampis, Mengel and Mitsou [9] shows the tractability of many parametrized problems by reducing them to SAT with bounded treewidth (which is known to be tractable). In this case, it is indeed usually simpler to writer the reduction instead of redoing complex dynamic programming algorithms again.

References

[1] Schaefer, Thomas J. (1978). "The Complexity of Satisfiability Problems". STOC 1978 https://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem

[2] Creignou, Nadia, and Miki Hermann. "Complexity of generalized satisfiability counting problems." Information and computation 125.1 (1996): 1-12.

[3] Creignou, Nadia, and J-J. Hébrard. "On generating all solutions of generalized satisfiability problems." RAIRO-Theoretical Informatics and Applications 31.6 (1997): 499-511.

[4] Szeider, Stefan. "On fixed-parameter tractable parameterizations of SAT." International Conference on Theory and Applications of Satisfiability Testing. Springer, Berlin, Heidelberg, 2003.

[5] E. Dantsin. Parameters defining the time of tautology recogni-
tion by the splitting method. Semiotics and information science, 12:8–17, 1979.

[6] Alekhnovich, Michael, and Alexander A. Razborov. "Satisfiability, branch-width and Tseitin tautologies." The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.. IEEE, 2002.

[7] Yannakakis, Mihalis. "Algorithms for acyclic database schemes." VLDB. Vol. 81. 1981.

[8] Capelli, Florent. Structural restriction of CNF-formulas: application to model counting and knowledge compilation, Thèse de Doctorat, Université Paris-Diderot, 2016.

[9] Lampis, Michael, Stefan Mengel, and Valia Mitsou. "QBF as an Alternative to Courcelle’s Theorem." International Conference on Theory and Applications of Satisfiability Testing. Springer, Cham, 2018.


What's the proof of this lemma by Hajnal about the randomized query complexity of monotone graph properties? In this paper, Hajnal states the following lemma:

  Let $\mathscr{G}_{n, m}$ be the set of all bipartite graphs with $n$ vertices in the left part and $m$ vertices in the right part. Suppose $\mathscr{P} \subseteq \mathscr{G}_{n, m}$ is nontrivial, monotone, and invariant with respect to bipartite graph isomorphisms. Order the set of minimal graphs with property $\mathscr{P}$ lexicographically according to the sorted list of degrees of left vertices, and let $G$ be the first minimal graph with property $\mathscr{P}$ according to this order. Then the zero-error randomized query complexity of $\mathscr{P}$ is $\Omega(\frac{\Delta_L(G)}{\delta_L(G)} n)$, where $\Delta_L(G)$ is the maximum degree of any vertex in the left side of $G$ and $\delta_L(G)$ is the average degree of the vertices in the left side of $G$.

(In fact, Hajnal actually uses a slight extension of the above lemma.) The same lemma is also used by Gröger in this other paper and by Chakrabarti and Khot in this other paper. But I can't figure out the proof of Hajnal's lemma. Hajnal attributes the lemma to Yao and cites this paper. But Yao's paper doesn't actually claim that lemma in that form.

Yao's paper does prove a closely related lemma. (Lemma 5 in Yao's paper, or equivalently Lemma 6 in this journal version of Yao's paper.) By adapting the proof of the lemma in Yao's paper, I see how to prove Hajnal's lemma under the extra assumption that $\delta_L(G) \geq \Omega(1)$. I'm having trouble with the case that $\delta_L(G)$ is subconstant.

(I'll now assume that the reader is familiar with Yao's proof.) My understanding is that to prove Hajnal's lemma, the idea is to modify Yao's proof by essentially just replacing $\lambda(n)$ with $\delta_L(G)$ and $\mu(n)$ with $\Delta_L(G)$ everywhere. At a high level, with these modifications, Yao's reasoning still makes sense, and shows that to "discover enough missing edges", the query algorithm will need to make at least about $\frac{\Delta_L(G) - 4\delta_L(G)}{\lceil 4 \delta_L(G) \rceil} \cdot \frac{n}{2}$ queries.

The issue is that when $\delta_L(G)$ is subconstant, because of the ceiling operation, that lower bound is only $O(\Delta_L(G) n)$, which is much smaller than the bound $\frac{\Delta_L(G)}{\delta_L(G)} n$ that appears in Hajnal's lemma. (Concretely, the issue is that each set $T_i'$ needs to have an integer number of vertices in it.)

How can the proof be patched?

I sent an email to Péter Hajnal, and he kindly confirmed that the bound in the lemma should be $\Omega(\frac{\Delta_L(G)}{\lceil \delta_L(G) \rceil} n)$.


Results in Theoretical CS independent of ZFC I'm going to ask a quite vague question, since the borderline between theoretical computer science and math is not always easy to distinguish.

QUESTION: Are you aware of any interesting result in CS which
is either independent of ZFC (i.e. standard set theory),
or that was originally proven in ZFC (+ some other axiom) and only later proven in ZFC alorne?

I'm asking because I'm close to finish my PhD thesis, and my main result (the determinacy of a class of games which are used to give "game semantics" to a probabilistic modal $\mu$-calculus) is at the moment proven in ZFC extended with other Axioms (namely the negation of the Continuum hypothesis $\neg CH $ and, Martin's Axiom $MA$).

So the setting is clearly Computer Science (the modal $\mu$-calculus is a temporal logic, and I'm extending it to work with probabilistic systems).

I would like to cite in my thesis other examples (if you are aware of any) of this kind.

Thank you in advance,

bye

Matteo

While I am not aware of any such results, other than your own, I think you could broaden the scope somewhat and ask: what results in TCS have been proved using (any kind of) non-standard axioms. By non-standard here I mean something other than classical logic with ZF (or ZFC).

A beautiful example of the kind of work I have in mind are Alex Simpson's results on properties of programming languages using synthetic domain theory. He uses intuitionistic set theory with axioms that contradict classical logic.

Also, Alex and I used intuitionistic axioms with anti-classical continuity principles to show results about Banach-Mazur computabilty.

However, none of the mentioned examples have an "open" status, like your proofs, because we know that the non-standard axioms we used can be understood simply as working inside a model of intuitionistic mathematics, where the model can be shown to exist in ZFC. So the non-standard setup is really a way of getting things done more elegantly, and in principle they could be done in straight ZFC (although I am afraid to think about how exactly that would go).


Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al This is about Proposition 7.4 here. I think there is a slight error in the proof of this proposition. Basically, authors have taken $g$ to be the odd part of the function $f$. Due to which we can say that $\mathbb{E}[g] = 0$, $\operatorname{Inf}_{i}(g) \leq \operatorname{Inf}_{i}(f)$ for all $i$, and $S_{\rho}(f) \geq S_{\rho}(g) = -S_{-\rho}(g)$.

So, applying MIS on $g$, we get

$S_{\rho}(g) \leq 1 - \frac{2}{\pi}\arccos(\rho) + \epsilon$ for $\rho$ from 0 to 1.

which implies

$-S_{-\rho}(g) \geq -\left(1 - \frac{2}{\pi}\arccos(-\rho) + \epsilon\right)$ for $\rho$ from -1 to 0.

Therefore,

$$S_{\rho}(f) \geq -1 - \frac{2}{\pi}\arccos(\rho) - \epsilon$$

But in the statement of the proposition, authors have written $S_{\rho}(f) \geq 1 - \frac{2}{\pi}\arccos(\rho) - \epsilon$. Is it really an error? Or I am missing something?

"So, applying MIS on $g$"

To apply the Majority is Stablest theorem, you need to apply it to a non-negative parameter $\rho'\in[0,1)$ (read the statement of the theorem). Since in Proposition 7.3 the parameter $\rho\in(-1,0]$ is non-positive, this means you here apply it to $\rho' \stackrel{\rm def}{=} -\rho\in[0,1)$, giving $$\mathbb{S}_{-\rho}(g) \leq 1-\frac{2}{\pi}\arccos(-\rho)+\epsilon =  -1+\frac{2}{\pi}\arccos(\rho)+\epsilon$$
using that $\arccos x+\arccos(-x) = \pi$ for all $x$ (This may very well be the part you are missing. $\arccos$ is not an odd function).
Then
$$\mathbb{S}_{\rho}(f) \geq -\mathbb{S}_{-\rho}(g)  \geq -\left(-1+\frac{2}{\pi}\arccos(\rho)+\epsilon\right) = 1-\frac{2}{\pi}\arccos(\rho)-\epsilon$$
as stated.


Array-like data structure with O(1) worst-case concatenate/join? I am looking for a data structure $D$ which supports the following operations
(preferably a (binary) tree-like structure):

$D$ is indexed, i.e.
there is a mapping from $\{1, \ldots, n\}$ to items in $D$,
where $n$ is the size of $D$ (the number of items in $D$).
$k$-th item in $D$ can be accessed in $\mathcal{O}(\lg n)$ worst-case (non-amortized).
The operation should not modify the data structure,
it should be completely "read-only"
(e.g. no finger searches are allowed).
(Once the pointer to the $k$-th item is obtained,
further changes should be supported in $O(1)$
without modification to the state of the data structure apart from the actual stored item (e.g. if it is a tree-like data structure, this means no rotation is allowed).
two instanced $D$ and $D'$ can be merged in time $\mathcal{O}(1)$ worst-case (non-amortized). Destruction of $D$ and $D'$ is fine.
The result should contains the union of the elements;
those that come $D$ retain their indices,
while indices of those coming from $D'$ get incremented by the size of $D$,
e.g. if we are merging
$D=\{ 1 \to x_1, 2 \to x_2 \}$ with
$D'=\{ 1 \to y_1, 2 \to y_2, 3 \to y_3 \}$
we should get
$\{ 1 \to x_1, 2 \to x_2, 3 \to y_1, 4 \to y_2, 5 \to y_3 \}$.

In essence, this data structure should have the properties of
the fast-mergeable array/vector with asymptotically slower random-access,
but extremely fast merge/concatenation ($\mathcal{O}(1)$).
It would also be cool if elements could be listed in order in linear time.

I would be mostly interested in the references to existing work / papers
which describe such a data structure or algorithm on an existing data structure.

I think Purely Functional Worst Case Constant Time Catenable Sorted Lists by Brodal et al. supplies what you want.


Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers It is often said that memoization brings the complexity of recursive-descent parsers
from exponential to polynomial. However, I had a hard time finding an example grammar
that triggers the exponential case.

Because recursive descent parsers cannot (naturally) deal with left-recursion,
the example should not contain left-recursive rules.
BTW, I'm familiar with PEG and Packrat parsers, and I'm not looking for examples
in the that domain. To be more precise, can someone please give me a non-left-recursive
context-free grammar that triggers exponential behaviour?

Here is a grammar that should meet your specification, though it
generates the very simple language $a^+(b+c)$.  (A simpler grammar has been added below)

$S \rightarrow ab \mid aBb \mid ac \mid aCc$
$B \rightarrow a \mid aB \mid aBB$
$C \rightarrow a \mid aC \mid aCC$

How was it built:

I started from the grammar
$\{S \rightarrow S S \mid a\}$ which is very ambiguous, so that trying all
parses of a string $a^n$ takes exponential time.

I put it in Greibach Normal Form, so as to remove any left recursion,
giving

$S \rightarrow a \mid aB$
$B \rightarrow a \mid aB \mid aBB$

Then I introduced $C$ to duplicate the possibilities of derivation,
with $b$ or $c$ as end marker to discover at the very end whether I
should have been using $B$ or $C$ as non-terminal in my derivation,
i.e,, whether the first rule to apply was $S \rightarrow aBb$ or $S
\rightarrow aCc$. But if the choice of rule made at the very beginning
was wrong, the backtracking process will have first to try all parsing
possibilities for the string of $a$, which has exponential cost.

Since the recursive descent has to try first one of the two rules,
there will always be a string (requiring the other rule) that takes
exponential time to parse, because of the useless backtracking with the wrong non-terminal.

Memoisation brings this down to cubic time. Naive memoisation will make it $O(n^4)$, but a bit of currification can correct that to cubic time.

A simpler solution (thought of later)

All that matters in the above grammar is to force an early choice of
the terminal marker $b$ or $c$, while having that choice checked only at the end
of the parsing process.

Hence the following grammar is enough to get the desired exponential
behaviour. Actually it is a (renaming) homomorphic image of the first
grammar above, and leads to exactly the same computation up to that
renaming.

$S \rightarrow ab \mid aXb \mid ac \mid aXc$
$X \rightarrow a \mid aX \mid aXX$

The rules $S \rightarrow ab \mid ac$ are not actually necessary for
our purpose, but that is minor. Removing them would change the language to $aa^+(b+c)$. Then, it is also possible to remove the initial $a$ in the rules $S \rightarrow aXb \mid aXc$ without introducing left recursion, thus getting back the initial language $a^+(b+c)$. But the grammar is no longer in Greibach normal form (which was not a requirement of the problem). This gives a solution with only 5 rules:

$S \rightarrow Xb \mid Xc$
$X \rightarrow a \mid aX \mid aXX$


Does anyone know of online video courses (in english) on randomness in theoretical computer science? I have found some video courses like this one but they are all in russian or other languages I don't understand. I'll like to know if anyone has come across lectures (courses) of this kind which are in english.

I am also aware that there are questions which are similar to this one on stackexchange e.g.this one, but I couldn't find any course of this kind among the answers given.

P.S: I'm interested in anything involving randomness in TCS as long as it is a full video course.

leading expert on the topic Wigderson at IAS has recently been lecturing/researching/survey/overviewing this important/emerging/crosscutting area.

Avi Wigderson -- "Randomness" youtube
Professor Avi Wigderson on a computational theory of randomness youtube/ETH Zurich

written notes similar to/overlapping these lectures:

Tao notes on Widgerson power/weakness of randomness in computation Terence Tao blog
COMPUTATIONAL INTRACTABILITY AND PSEUDORANDOMNESS essay by Wigderson


Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space? There are some NP-Complete problems ($ \mathsf{SAT} $, $ \mathsf{SUBSETSUM} $, etc.) known to be in $ \mathsf{DSPACE(n)} $. What about the sub-linear spaces?

  Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?

The planar version of many NP-complete problems belong to $NTISP(n,n^q)$ for some $q<1$

See for example "Lower Bounds and Complete Problems in Nondeterministic Linear Time and
Sublinear Space Complexity Classes" by P. Chapdelaine and E. Grandjean (2006)


Complexity of exponential function We know that the exponential function $\exp(x,y) = x^y$ over natural numbers is not computable in polynomial time, because the size of the output is not polynomially bounded in the size of the inputs.

Is this the main reason for the difficulty of computing the exponential function, or is exponentiation inherently difficult to compute, independently of this consideration?

  What is the complexity of the bit graph of the exponential function?
  $$\{\langle x,y,i \rangle \mid x,y,i\in\mathbb{N} \text{ and the $i$-th bit of $x^y$ is $1$} \}$$

Here are some upper bounds.

By repeated squaring, the problem is in PSPACE.

There is a slightly better upper bound.  The problem is a special case of the BitSLP problem: Given a straight-line program starting from 0 and 1 with addition, subtraction and multiplication representing an integer N, and given i∈ℕ, decide whether the i-th bit (counting from the least significant bit) of the binary representation of N is 1.  The BitSLP problem is in the counting hierarchy (CH) [ABKM09].  (It is stated in [ABKM09] that it can be shown that the BitSLP problem is in PHPPPPPPPP.)

The membership to CH is often considered as an evidence that the problem is unlikely to be PSPACE-hard, because the equality CH=PSPACE implies that the counting hierarchy collapses.  However, I do not know how strong this evidence is considered to be.

As for the hardness, BitSLP is shown to be #P-hard in the same paper [ABKM09].  However, the proof there does not seem to imply any hardness of the language X in the question.

References

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen.  On the complexity of numerical analysis.  SIAM Journal on Computing, 38(5):1987–2006, Jan. 2009.  http://dx.doi.org/10.1137/070697926


Conceptually simple linear-time suffix tree constructions In 1973 Weiner gave the first linear-time construction of suffix trees. The algorithm was simplified in 1976 by McCreight, and in 1995 by Ukkonen. Nevertheless, I find Ukkonen's algorithm relatively involved conceptually.

Has there been simplifications to Ukkonen's algorithm since 1995?

I'm not sure if there were any new results directly simplifying the construction of suffix trees. However, there has been at least one result giving a very simple algorithm for constructing suffix arrays in linear time.

Note that there's more than a conceptual equivalence between these two data structures, since you can use a suffix array (with $\cal{O}(1)$ time for querying the longest common prefix) to build an equivalent suffix tree. This should be a relatively simple exercise, but I can give more details if required.

Also, for practical purposes it's even easier to build suffix arrays in $\cal{O}(n \lg n)$ time, but I guess I'm going slightly off-topic here.


Is a CS degree for me? I'm a UK student who will soon be going to university and would like some advice from people who have already done this on what course to take.

I really enjoy the theoretical side of computer science, especially the more mathematical concepts. I do enjoy the other area such as algorithm design and programming as a hobby, but I wouldn't really want to be a programmer/tech support/algorithm designer as a job. Those sort of jobs are just not for me. I would prefer a research type job, maybe in quantum computing. I currently' finishing my A-levels in physics and further maths, and I'm expecting A*s in both fields.

Sorry if all this is a bit vague, but I would like some ideas from people about what the best degree is to take to get where I want, and what sort of jobs are out there. Also, if anyone knows what's some universities in UK to study this sort of thing at , I'd very much appreciate the advice.

In the UK, some of the universities to study at are Oxford, Cambridge, York and Imperial College London, though this list will vary depending on precisely which topic you are interested in. The group of Abramsky at Oxford does research in Quantum Computation, so going there and following courses he offers (and related ones) would certainly help you reach your goal.

It would be a good idea to go through the web sites of the computer science departments of the above mentioned universities and see whether they offer courses (or even a program) that heads in the right direction. Look not only at the descriptions of courses, but also of the personal web pages of the researchers, who will often have some description of their research interests, which may differ from the courses on offer, but will be available to study as you enter later phases of your study.


Learning using  decision trees I have a quick question that I'm stumped on. This is about constructing a decision tree using information gain (entropy). Let's say we have a dataset with two input attributes such that the information gain at the root of the tree for both attributes is zero, but this tree is still a decision tree of depth two (so two questions must be asked) that is consistent with the data.

How would this be constructed? I don't understand how I can get to a deeper depth without knowing have any information gain...

Without looking at specifics, growing a tree using information gain is a greedy procedure and won't always get you to the smallest tree consistent with the data, even if one exists.  If there are ties among attributes, you break them arbitrarily.


Examples for derandomization via small sample spaces I read the book the Probabilistic Method and the lecture note Pseudorandomness to study techniques of derandomization and completed some of exercises.

I'm trying the technique of "Derandomization" for some algorithms, and I find some samples using the derandomization via small sample spaces and feel very interested.

To deepen the impression on derandomization via small sample space, I want to see more papers using that.

Here is an example from low degree testing literature: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/BSVW03/BSVW03.pdf.

High-level summary: Consider BLR linearity testing algorithm that given oracle access to a function $f:\mathbb{F}^m \rightarrow \mathbb{F}$, first, samples $x,y$ uniformly randomly from $\mathbb{F}^m$ and then tests if $f(x)+f(y)=f(x+y)$ by querying the function at required points. This paper reduces the amount of randomness usage by sampling $y$ from an epsilon-biased set instead of sampling from the entire space.


Chain rule for KL divergence Is there an inequality to relate the KL divergence of two joint distribution and the sum of the KL divergence of their marginals? Or in particular, is there a proof or a counter example for the following:

$D(q(x,y)\|p(x,y)) \geq D(q(x)\|p(x)) + D(q(y)\|p(y))$.

I don't think the given inequality is true (I am not sure about the reverse inequality). Recall that $$
D_{KL}(q(x,y)\| p(x,y))=\sum_{x\in \mathcal{X}}\sum_{y\in \mathcal{Y}} q(x,y)\log\bigg(\frac{q(x,y)}{p(x,y)}\bigg).
$$
Consider non-identical joint distributions $p$ and $q$ over $\mathcal{X}\times\mathcal{X}$ (so $\mathcal{Y}=\mathcal{X}$), with $p(x,y)=q(x,y)=0$ for $y\neq x$ (so the supports of both distributions are on the diagonals). Then
\begin{align}
D_{KL}(q(x,y)\|p(x,y))&=\sum_{x_1\in \mathcal{X}}\sum_{x_2\in \mathcal{X}}q(x_1,x_2)\log\bigg(\frac{q(x_1,x_2)}{p(x_1,x_2)}\bigg)\\
&=\sum_{x\in \mathcal{X}} q(x)\log\bigg(\frac{q(x)}{p(x)}\bigg)\\
&=D_{KL}(q(x)\|p(x))=D_{KL}(q(y)\|p(y)).
\end{align}
In general, these are not all zero or infinite, so the stated inequality will not hold.

However, I think one can say that
$$
D_{KL}(q(x,y)\|p(x,y))\geq \frac{D_{KL}(q(x)\|p(x))+D_{KL}(q(y)\|p(y))}{2}.
$$
This should follow from the Chain Rule:
\begin{align}
D_{KL}(q(x,y)\|p(x,y))&=D_{KL}(q(x)\|p(x))+D_{KL}(q(y\vert x)\|p(y\vert x))\\
&=D_{KL}(q(y)\|p(y))+D_{KL}(q(x\vert y)\|p(x\vert y)),
\end{align}
summed twice and then using the nonnegativity of divergence.


Data Mining of self-replicators My current (very limited) understanding of the creative process that leads to the design of self-replicators is that any particular self-replicator, like Universal Constructor, Langton's loop or Evoloop, are designed by painstaking, lengthy, meticulous design/engineering, which often involves composing units designed by previous mathematicians/hobbyists into more advanced and better behaved self-replicators. In other words, I believe that the current process of designing a self-replicator is following:

Take a self-replicator somebody designed before.
Get an idea of improving it, based on some theoretical research that somebody did, a gut feeling, an idea that's been floated around, a dream you had last night etc. The idea should improve the self-replicator with respect to some property that is commonly recognised to be worth improving (lower period, less fragility, sexual reproduction, etc.).
Try to make it work by working through multiple versions of the design, continuously refining the idea, and doing a ton of micro-optimisation. If you succeed go to step 1, and try to improve your new replicator. If you fail, go to step 2 and pick a different idea.

This method obviously works very well, as shown by the progress in the field, and is not very different from how in general progress in mathematics works. However, I've been thinking lately of a different approach to the problem, and I couldn't find any prior art trying this approach.

The process, let's call it "Self-Replicator Data-Mining" would be following:

Take the largest grid you can quickly evolve on your hardware. Size would most likely be limited by the amount of RAM you can devote to a GPU shader, which assuming to be 12 GB, gives a grid of about 100,000^2 squares.
Pick a "rich" set of rules, like Brian's Brain, to get a lot of chaos (you'll have to work on a torus).
Run it for about 8 months, periodically saving the state to a hard drive for backups. A back-of-envolope calculation shows that this would give you about billion steps of a simulation.
In meantime, design an algorithm which can recognise a self-replicator by looking at the grid after the nth iteration. The algorithm might be very slow, because it only needs to work once. It does sound like the biggest challenge -- and probably would involve some machine learning/ pattern recognition. In principle a parent can replicate to a slightly mutated child, which would make data mining of self-replicators even more difficult.
Publish your newly discoverd self-replicator(s) if you manage to find any. Or go to step 2 and pick a different set of rules, or wait for a graphics card with 120 GB of RAM, or run your simulation for 8 years, or abandon the method entirely in favour of something more fruitful.

Has anything like this ever been tried? Is it a path worth pursuing or are there any obvious flaws?

Most of the patterns in my collection at http://www.ics.uci.edu/~eppstein/ca/replicators/ were found with a somewhat different heuristic search process, that was intended to find puffers but also turns out to work for replicators:

Pick a small random seed pattern
Simulate a moderate number of steps of a modified version of the cellular automaton rule, starting with that seed. The modification is: if you find a small enough set of live cells, separated by far enough from the rest of the pattern, delete them.
If the simulation finds two states that have the same pattern of cells (but possibly shifted with respect to each other), check it against a collection of known repetitions and shifts and, if it seems new, report it. See https://en.wikipedia.org/wiki/Cycle_detection for efficient methods of finding repeated patterns that don't involve testing all against all.

Many replicators eventually reach a state with just two copies of the replicator far from each other, after which the modification to the rule deletes one of them and you get a repetition.


How can you prove that a problem is not solvable in a certain time complexity? One of the most interesting questions in computer science is of course whether $P = NP$ or $P \neq NP$. If one wants to prove that $P \neq NP$ one can try to prove that an NPC problem is not solvable in polynomial time. However, I can't quite figure out how it would be possible to prove such a thing.

How can you prove that there is no better solution possible to a problem than a solution which has a certain time complexity?

I understand that there are no problems known in NP for which is proven that it cannot be solved in polynomial time, but are there problems known for which a proof does exists that it cannot be solved in for example constant or linear time? Perhaps an example of such a problem can help me understand this better.

EDIT: If you down vote this question could you please at least post a comment why you did so? I'd love to improve my question, but down votes alone don't tell me what I did wrong.

One area where unconditional and nontrivial time lower bounds are known is in data structures, where the time is for individual data structure operations (or sequences of operations). The standard model for this sort of thing is called the "cell probe model"; it assumes only that main memory is divided into words of a certain size and that the CPU has a very limited amount of local storage (e.g. in registers or cache), and bounds the number of word read/write operations that must be performed.

For instance, in the cell probe model one can prove that the problem of maintaining prefix sums of word-length values (that is, maintain an array of values subject to operations that change one value in an array or that query the sum of a prefix of the values) requires $\Omega(n\log n)$ time to perform a sequence of $n$ operations on an array of length $n$. The difficulty here comes in part from the fact that the operations have to be performed online (not knowing in advance the sequence of future operations).

Fredman and Saks' STOC'89 paper "The cell probe complexity of dynamic data structures" and Patrascu and Demaine's SICOMP'05 "Logarithmic lower bounds in the cell-probe model" are probably good starting points; look up cell probe lower bounds in Google scholar for much more.


Type theory for memory safe data structures Data structures such as a doubly linked list and a B+ tree have blocks of memory that have multiple pointers to it. This creates the risk that a bug will allow memory to be accessed after being freed.

I have heard of ideas based around linear typing for guaranteeing memory safety in the case of a single pointer to the memory. I believe the Rust language is based around this.

But suppose, for example, I wanted a memory safe implementation of a B+ tree in a systems language that has no garbage collection or reference counting. What exists in type theory that could be used to guarantee that the B+ tree implementation is memory safe?

There has been a lot of work around the idea of statically checking the memory safety properties of programs.

Francois Pottier give an excellent overview of various approaches in this presentation. The main technique you probably would be interested in is region typing.

The Wikipedia article is quite complete, but the basic idea is to keep explicit regions which references are required to explicitly be assigned to a given region, which can be managed by the programmer or left to be inferred by the compiler. This is somewhat reminiscent of the RAII approach to memory management used mainly in C++ (the wiki article is terrible however).

In practice, region inference hasn't gained widespread use in compilers, mainly because of the complexity of the analyses involved.

Again related, there has been a flurry in work on separation logic over the last decade, which is an extension of Hoare Logic which allows reasoning over separate regions of the heap, in order to analyze whether objects can share memory locations or not. This method of reasoning is quite difficult to apply to a language like C with "real" pointers, because of the possibility of pointer aliasing.


Theta functions of automata relations Let $A,B$ be two automata over the same alphabet $\Sigma$; they are supposed to be complete, strongly connected DFAs. We denote by $._A$ (resp. $._B$) the action induced by $\Sigma^*$ over $Q(A)$, i.e. $u ._A s$ designates the state reached from $s$ upon reading $u$ - note that this is more commonly denoted by $\delta_A(u,s)$ but we adopt the first notation for conciseness.  Say that an "automata relation" between $A$ and $B$ is a relation $R \subseteq Q(A) \times Q(B)$ such that:

(*) if $R(s,t)$ holds, then for any $u,v \in \Sigma^*$ we have: $u ._A s = v ._A s \Rightarrow u ._B t = v ._B t$.

Given $R$ and $t \in Q(B)$, we then define $R^{-1}(t) = \{ s \in Q(A) : R(s,t) \text{ holds} \}$.

Given such a relation, it is possible to define an action of $Q(A)$ over $Q(B)$ as follows: given $t \in Q(B)$ and $s \in Q(A)$, we define $s^{-1} t$ as the unique state $t' \in Q(B)$ such that for every $s' \in R^{-1}(t)$, $L_A(s',s).t = \{t'\}$. Note that the existence of $t'$ follows from the strong connectedness of $A$, and that the unicity follows by observing that if $u,v \in L_A(s',s)$, we have $u ._A s' = v ._A s' = s$ and thus $u ._B t = v ._B t = t'$.

Now, given the tuple $T = (A,B,R)$ and given two weight functions $f,g$ over $Q(B)$, let us define the "theta function" $\Theta_{T,f,g}(s) = \sum_{t \in Q(B)} f(t) g(s^{-1} t)$.

Question: what are the interesting questions to ask about this notion?

(Some examples and suggestions should follow, I'm still trying to clear my thoughts on this problem.)

Your definition seems to extend the notion of "convolution products" in groups; this can be seen as follows. Consider a finite group $G$ with generating set $\Sigma$, with the corresponding map $i_G : \Sigma^* \rightarrow G$. Construct the corresponding automaton $\cal{A}(G,\Sigma)$ with state set $G$ and which contains a transition $x \rightarrow_a a.x$ for every $x \in G, a \in \Sigma$.

Let $H$ be a normal subgroup of $G$, and consider the quotient $Q = G / H$; we can view $Q$ as a finite group with generating set $\Sigma$, up to identifying each $a \in \Sigma$ with its class $aH$. By the factor theorem, there is a projection $j : G \rightarrow Q$ (mapping $x$ to $xH$) and an homomorphism $i_Q : \Sigma^* \rightarrow Q$ such that $i_Q = j \circ i_G$.

Consider the corresponding automata $A = \cal{A}(G,\Sigma)$ and $B = \cal{A}(Q,\Sigma)$. Define the relation $R$ by: $R(a,bH) \Leftrightarrow a \in bH$. This defines an automata relation: for every $u,v \in \Sigma^*$ such that $u.a = v.a$, we have $i_G(u) = i_G(v)$ and thus $i_Q(u) = i_Q(v)$, implying that $u.(bH) = v.(bH)$.

Consider the tuple $T = (A,B,R)$. For every coset $k = tH \in Q$, it is easy to see that the set $R^{-1}(k)$ consists exactly of the elements of $k$, and that given an element $s \in G$, the operation $s^{-1} k$ gives the coset $(s^{-1} t) H$. As $H$ is a normal subgroup of $G$, we have $(s^{-1} t) H = (s^{-1} H) (t H)$, and in this case we obtain a "convolution product" over $Q$: given two weight functions $f,g$ over $Q(B)$, we obtain $\Theta_{T,f,g}(s) = \sum_{t \in Q} f(t) g(s^{-1} t)$. In particular, the function is stabilized by $H$, as for $r \in H$ the function $t \rightarrow (s^{-1} r s) t$ is a bijection over $Q$.

This suggests a possible connection with Fourier analysis and with the theta functions of integer lattices; there might be also a relation with the notion of harmonic functions over group actions. I'm not sure though if this is the kind of questions you are interested in.


Is adiabatic quantum computing as powerful as the circuit model? Much of the quantum computing literature focuses on the circuit model. Adiabatic quantum computing is not based on applying a sequence of unitary operators, but on changing a time-dependent Hamiltonian. I am looking for insight into any of the following.

Is adiabatic quantum computing as powerful as the circuit model, or is it inherently less powerful?
Are there complexity classes specifically related to adiabatic computing as opposed to the circuit model?
How does one quantitatively measure the power of adiabatic computing versus the power of the circuit model?

Two quick clarifications:

Adiabatic QC is typically "based on qubits" just as much as circuit-based QC is -- I don't know where you got the idea that it isn't!  (Though one could also use qutrits or other building blocks, in either the circuit or the adiabatic models.)
As Mateus pointed out, the justly-famous result of Aharonov et al. says that "adiabatic QC is equivalent to standard QC."  But that result needs to be interpreted with a bit of care.  It holds if the final state of the adiabatic computation can be arbitrary -- so that, in particular, the final state can encode the entire history of a circuit-based quantum computation.  However, if the final state needs to be a classical computational basis state---as it typically is in the adiabatic optimization algorithm (the "original" example of adiabatic QC)---then adiabatic QC can certainly be simulated in the circuit model, but the reverse is not known and is far from clear.  So with the latter assumption, it's possible that adiabatic optimization really does give rise to a new complexity class intermediate between BPP and BQP.


Is black box parallel quantum speedup ever nontrivial? Grover's algorithm is not parallelizable, in that $p$ quantum processors searching over $n$ elements can't do better than $O(\sqrt{n/p})$ queries.

Are there any oracle problems where quantum computers see some polynomial speedup over classical, but where the algorithm is nontrivially parallelizable?  Here's one attempt at formalizing this:

Question: Are there any oracle problems such that

The classical complexity is $O(t)$, and achieves perfect parallel speedup to $O(t/p)$.
The quantum complexity is $O(t^\alpha)$ for $\alpha \in [1/4,1)$.
The parallel quantum complexity is $O(t^\alpha / p^\beta)$, with $\beta \in (\alpha,1]$.

Even better, is there a problem where $\beta = 1$ (perfect parallel quantum speedup)?

Methinks, you do not understand the black-box magic of quantum processors.

It shall cover all n elements of a task by its cubits, otherwise, there would not be happen collapse of superposition over all input's elements and you would not even calculate anything.

For example, factorization algorithm: There shall be n + k cubits, where n - is a dimension of input, and k is support engine.

If your processor can not reach this dimension, you are not able to split input in n/p parts and feed p different processors to summarize result after, on exit...

Super-position of sum of p processors will be much lesser then super-position of one big n dimension processor. And quantum magic is exactly hidden in this dimension, means - number of cubits.

E.g. 3 CPU x 3 cubits each; This will give us such fields:

1st 2nd 3rd
000 000 000
001 001 001
010 010 010
011 011 011
100 100 100
101 101 101
110 110 110
111 111 111

This is how superposition will looks like. Three small quantum registers. And this field - is our calculation power here.

But, when you'll take One Big CPU with 9 cubits, this will give you 2^9 dimension = 512 different boolean vectors. And system will be in all of its while in super-position.

The "memory" of such quantum computer in super position will be much bigger:

000000000 000000001 000000010 000000011 000000100 000000101 000000110 000000111
000001000 000001001 000001010 000001011 000001100 000001101 000001110 000001111
000010000 000010001 000010010 000010011 000010100 000010101 000010110 000010111
000011000 000011001 000011010 000011011 000011100 000011101 000011110 000011111
000100000 000100001 000100010 000100011 000100100 000100101 000100110 000100111
000101000 000101001 000101010 000101011 000101100 000101101 000101110 000101111
000110000 000110001 000110010 000110011 000110100 000110101 000110110 000110111
000111000 000111001 000111010 000111011 000111100 000111101 000111110 000111111
001000000 001000001 001000010 001000011 001000100 001000101 001000110 001000111
001001000 001001001 001001010 001001011 001001100 001001101 001001110 001001111
001010000 001010001 001010010 001010011 001010100 001010101 001010110 001010111
001011000 001011001 001011010 001011011 001011100 001011101 001011110 001011111
001100000 001100001 001100010 001100011 001100100 001100101 001100110 001100111
001101000 001101001 001101010 001101011 001101100 001101101 001101110 001101111
001110000 001110001 001110010 001110011 001110100 001110101 001110110 001110111
001111000 001111001 001111010 001111011 001111100 001111101 001111110 001111111
010000000 010000001 010000010 010000011 010000100 010000101 010000110 010000111
010001000 010001001 010001010 010001011 010001100 010001101 010001110 010001111
010010000 010010001 010010010 010010011 010010100 010010101 010010110 010010111
010011000 010011001 010011010 010011011 010011100 010011101 010011110 010011111
010100000 010100001 010100010 010100011 010100100 010100101 010100110 010100111
010101000 010101001 010101010 010101011 010101100 010101101 010101110 010101111
010110000 010110001 010110010 010110011 010110100 010110101 010110110 010110111
010111000 010111001 010111010 010111011 010111100 010111101 010111110 010111111
011000000 011000001 011000010 011000011 011000100 011000101 011000110 011000111
011001000 011001001 011001010 011001011 011001100 011001101 011001110 011001111
011010000 011010001 011010010 011010011 011010100 011010101 011010110 011010111
011011000 011011001 011011010 011011011 011011100 011011101 011011110 011011111
011100000 011100001 011100010 011100011 011100100 011100101 011100110 011100111
011101000 011101001 011101010 011101011 011101100 011101101 011101110 011101111
011110000 011110001 011110010 011110011 011110100 011110101 011110110 011110111
011111000 011111001 011111010 011111011 011111100 011111101 011111110 011111111
100000000 100000001 100000010 100000011 100000100 100000101 100000110 100000111
100001000 100001001 100001010 100001011 100001100 100001101 100001110 100001111
100010000 100010001 100010010 100010011 100010100 100010101 100010110 100010111
100011000 100011001 100011010 100011011 100011100 100011101 100011110 100011111
100100000 100100001 100100010 100100011 100100100 100100101 100100110 100100111
100101000 100101001 100101010 100101011 100101100 100101101 100101110 100101111
100110000 100110001 100110010 100110011 100110100 100110101 100110110 100110111
100111000 100111001 100111010 100111011 100111100 100111101 100111110 100111111
101000000 101000001 101000010 101000011 101000100 101000101 101000110 101000111
101001000 101001001 101001010 101001011 101001100 101001101 101001110 101001111
101010000 101010001 101010010 101010011 101010100 101010101 101010110 101010111
101011000 101011001 101011010 101011011 101011100 101011101 101011110 101011111
101100000 101100001 101100010 101100011 101100100 101100101 101100110 101100111
101101000 101101001 101101010 101101011 101101100 101101101 101101110 101101111
101110000 101110001 101110010 101110011 101110100 101110101 101110110 101110111
101111000 101111001 101111010 101111011 101111100 101111101 101111110 101111111
110000000 110000001 110000010 110000011 110000100 110000101 110000110 110000111
110001000 110001001 110001010 110001011 110001100 110001101 110001110 110001111
110010000 110010001 110010010 110010011 110010100 110010101 110010110 110010111
110011000 110011001 110011010 110011011 110011100 110011101 110011110 110011111
110100000 110100001 110100010 110100011 110100100 110100101 110100110 110100111
110101000 110101001 110101010 110101011 110101100 110101101 110101110 110101111
110110000 110110001 110110010 110110011 110110100 110110101 110110110 110110111
110111000 110111001 110111010 110111011 110111100 110111101 110111110 110111111
111000000 111000001 111000010 111000011 111000100 111000101 111000110 111000111
111001000 111001001 111001010 111001011 111001100 111001101 111001110 111001111
111010000 111010001 111010010 111010011 111010100 111010101 111010110 111010111
111011000 111011001 111011010 111011011 111011100 111011101 111011110 111011111
111100000 111100001 111100010 111100011 111100100 111100101 111100110 111100111
111101000 111101001 111101010 111101011 111101100 111101101 111101110 111101111
111110000 111110001 111110010 111110011 111110100 111110101 111110110 111110111
111111000 111111001 111111010 111111011 111111100 111111101 111111110 111111111

You can factorize number lesser than 2^9, for example 465 on such QCPU, but you can not factorize this number on bunch of little QCPU with 3 cubits per each.

465 - it is 111 010 001. So, how do you plan to split it, to feed by parts to each little QCPU? First will factorize 111, second 010, third 001? And how to sum such result on exit? There is no way.

As you can see, 3 QCPU x 3cubits - is not the same as 1 QCPU x 9cubits.
And each new cubit increase power of QCPU by multiplying its calculation field on two. x2, x2, x2, x2... so, you could fast reach the number of stars in the visible universe or even atoms, or quarks,.. photons... and even exceed it... Simply, knot more and more cubits in superposition. But you can not achieve the same, by printing more and more small quantum computers, because the effect will be linear, not exponential.


Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$ Many believe that $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$. However we only know that $\mathsf{BPP}$ is in the second level of polynomial hierarchy, i.e. $\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2$. A step towards showing $\mathsf{BPP} = \mathsf{P}$ is to first bring it down to the first level of the polynomial hierarchy, i.e. $\mathsf{BPP} \subseteq \mathsf{NP}$.
The containment would mean that nondeterminism is at least as powerful as randomness for polynomial time.
It also means that if for a problem we can find the answers using efficient (polynomial time) randomized algorithms then we can verify the answers efficiently (in polynomial time) .

Are there any known interesting consequences for $\mathsf{BPP} \subseteq \mathsf{NP}$?
Are there any reasons to believe that proving $\mathsf{BPP} \subseteq \mathsf{NP}$ is out of reach right now (e.g. barriers or other arguments)?

For one, proving $BPP \subseteq NP$ would easily imply that $NEXP \neq BPP$, which already means that your proof can't relativize.

But let's look at something even weaker: $coRP \subseteq NTIME[2^{n^{o(1)}}]$. If that is true, then polynomial identity testing for arithmetic circuits is in nondeterministic subexponential time. By Impagliazzo-Kabanets'04, such an algorithm implies circuit lower bounds: either the Permanent does not have poly-size arithmetic circuits, or $NEXP \not\subset P/poly$.

I personally don't know why it looks "out of reach" but it does seem hard to prove. Certainly some genuinely new tricks will be needed to prove it.


Problem understanding "connectivity" characteristic for the $k$-connected subgraph problem I am reading this article, and I am having trouble to understand the 11th definition (page 7) about the connectivity characteristic. I do understand the raw definitions, but have no idea what this gives my intuitively.

The definition:

  For each pair of distinct vertices v, u of H: let $Com_{H}(v, u)$ be the set of portal completions which augment H to a graph with k internally vertex-disjoint paths between v and u.
  For each vertex v of H, let $Path_{H}(v)$ be the set of pairs (U, Q) where U is a multiset of P(H) with vertex multiplicities bounded by from above by the vertex degrees in H and Q is a partial g-matching on the complete multigraph on P(H) with g(w) equal to the difference between the degree of w in UH and the multiplicity of w in U such that there are $|U|+|Q|$ internally vertex-disjoint paths in H connecting v with each copy a vertex in U, and connecting each pair of endpoints of each edge in Q, respectively.
  $Path_{H}$ is the set of all Q for which $(\phi, Q)$ is in $Path_{H}(v)$ for an arbitrary vertex v in P(H).
  We will call the triple ($Com_{H}(v, u)$, $Path_{H}(v)$, $Path_{H}$) the $connectivity\ characteristic$ of H.

Context: The paper presenta a PTAS for minimum-cost k-connected subgraph problem. This is done by dissecting the graph into smaller parts, brute-forcing a solution on the small parts, and then connecting them in a way that doesn't increase is stays a $(1+\epsilon)$-approximation. This connectivity characteristic is a property of the subgraphs that is maintained by the algorithm while augmenting the big graph from the smaller parts. A foot note at page 6 states that it models "missing" connectivity, that will be added later by the augmentation of the regions.
Note that there is also (m, r)-blue which is another property that should be maintained. Could be that only both give something useful.
The definition of an (m, r)-blue graph is at page 10. Mainly says that a facet is being crossed at portals, and not too often.

Could someone give me some intuitive explanation about what this characteristic is, and why its helpful?

I think I figured it out.

$Com_{H}(v, u)$ are paths leaving the region and connecting through some vertices outside the region.

$Path_{H}(v)$ are the paths connecting $v$ to the vertices that are not included in this region.

$Path_{H}$ are paths inside the region

If this is true, then the proof of Lemma 3.2 has some typing errors (the 2 a.m. kind). And it should be:

  To compute $Com_{H}(v, u)$ where u, u v are non-portal vertices in $H$, for each competition $D$ in $Com_{H}(v, u)$, we insert D and the set difference $D\backslash B$ into $Com_{H \cup B}(v, u)$ (not $H \cup C$).
  [The rest is good]

I am not really sure, so please let me know what you think about this via comments \ up-votes \ telepathy.


How much would a SAT oracle help speeding up polynomial time algorithms? Access to a $SAT$ oracle would provide a major, super-polynomial speed-up for everything in ${\bf NP}-{\bf P}$ (assuming the set is not empty). It is less clear, however, how much would $\bf P$ benefit from this oracle access. Of course, the speed-up in $\bf P$ cannot be super-polynomial, but it can still be polynomial. For example, could we find a shortest path faster with a $SAT$ oracle, than without it? How about some more sophisticated tasks, such as submodular function minimization or linear programming? Would they (or other natural problems in $\bf P$) benefit from a $SAT$ oracle?

More generally, if we can pick any problem in ${\bf NP}-{\bf P}$, and use an oracle for it, then which of the problems in $\bf P$ could see a speed-up?

Actually, acceptance of nondeterministic Turing machines in time $t$ is $O(t \log t)$-time reducible to SAT (the construction is via oblivious simulation, see Arora-Barak), so typically any time a nondeterministic machine is appreciably faster than a deterministic one, we'll see at least some speedup with a SAT oracle.

To be more concrete, primality testing comes to mind, as the best variant of the AKS algorithm appears to test primality of an $n$-bit number in time $O(n^6 \; \text{polylog}\; n)$. But if we go "old school", Pratt gave a nondeterministic TM to decide primality in time $O(n^3 \; \text{polylog}\; n)$. Acceptance of this machine can be reduced (deterministically) in $O(n^3 \; \text{polylog}\; n)$ time to a SAT instance.

The 3SUM problem may be another example, as it seems like one can guess a solution and check it in subquadratic time, and then acceptance of such a machine can be reduced to SAT in subquadratic time.


What kind of mathematical background is needed for graph theory? It is going to be the first time for me to learn graph theory. What kind of mathematical background do I need to prepare master theses about this subject in following years?
Which subjects should be reviewed and is there any book that covers all of them?

There are plenty of good books on graph theory. Start with something introductory like Graph Theory: Modeling, Applications and Algorithms, or one of the many more or less equivalent books at that level. Then move onto something more advanced, such as

Graph Theory: An Advanced Course (Graduate Texts in Mathematics) by Adrian Bondy and U.S.R. Murty,
Modern Graph Theory (Graduate Texts in Mathematics) by B. Bollobás or
Graph Theory (Graduate Texts in Mathematics) by Reinhard Diestel.

Also building on your background in discrete mathematics is invaluable. A book such as

Concrete Mathematics: Foundation for Computer Science by Ronald L. Graham, Donald E. Knuth, Oren Patashnik

would be provide you will a solid grounding.

Most of these books would then serve as references for life.

See also this question What kind of mathematical background is needed for complexity theory?, as much of the background will overlap, in particular wrt combinatorics and stochastics (probability and statistics).


Why naturals instead of integers? I'm interested in why natural numbers are so beloved by the authors of books on programming languages theory and type theory (e.g. J. Mitchell, Foundations for programming languages and B. Pierce, Types and Programming Languages). Description of the simply-typed lambda-calculus and in particular PCF programming language are usually based on Nat's and Bool's. For the people using and teaching general-purpose industrial PL's it is great deal more natural to treat integers instead of naturals. Can you mention some good reasons why PL theorist prefer nat's? Besides that it is a little less complicated. Are there any fundamental reasons or is it just an honour the tradition?

UPD For all those comments about “fundamentality” of naturals: I'm a quite aware about all those cool things, but I'd rather prefer to see an example when it is really vital to have those properties in type theory of PL's theory. E.g. widely mentioned induction. When we have any sort of logic (which simply typed LC is), like basic first-order logic, we do really use induction — but induction on derivation tree (which we also have in lambda).

My question basically comes from people from industry, who wants to gain some fundamental theory of programming languages. They used to have integers in their programs and without concrete arguments and applications to the theory being studied (type theory in our case) why to study languages with only nat's, they feel quite disappointed.

Short answer: the naturals are the first limit ordinals. Hence they play a central role in axiomatic set theory (eg, the axiom of infinity is the assertion they exist) and logic, and PL theorists tend to share foundational preoccupations with logicians. We want to have access to the principle of induction to prove total correctness, termination, and similar properties, and the naturals are an (er) natural choice of well-order.

I don't want to imply that finite-width binary integers are any less cool objects, though. They are representations of the p-adics, and permit us to use power series methods in number theory and combinatorics. This means that their significance becomes more visible in algorithmics than PL, since this is when we start caring more about complexity rather than termination.


Construction of graphs where every pair of vertices have an unique common neighbor Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise from A Course in Combinatorics, van Lint and Wilson, to prove that such a graph is regular.

My question, however, is whether graphs satisfying the given constraints even exist. While discussing the original exercise during a problem-solving session, someone asked if we could come up with an example of a graph where every pair of vertices have an unique common neighbor, and there are no global vertices. Neither were we able to come up with a concrete example or procedure for construction, nor did we establish a proof that no graph has these properties.

Any suggestions?

Note: as for proving that such a graph is regular, it turns out to be fairly straightforward, the rough idea is to pair off the neighbors of every pair of vertices using the unique-common-neighbor criteria to establish the fact that every pair of vertices have the same degree, and then a transitivity argument, with the help of the no-global-vertex constraint, gives us that the graph is regular.

If you get rid of the "no vertex of degree $n-1$" condition, the graphs with the property that every two vertices have exactly one common neighbor are exactly the friendship graphs (a set of triangles glued together at a common vertex); as the linked article describes, this is a theorem of Erdős, Rényi, and Sós. But obviously, all such graphs have a vertex of degree $n-1$; the only regular one is a triangle. So the answer to your question is that, no, a graph with the common neighbor property and without a degree-$n-1$ vertex does not exist.


Definition of k-set cover I'm trying to understand the sparsification lemma by Impagliazzo, Paturi and Zane (IPZ) (from this article) and in their proof they reduce the k-SAT problem to the k-set cover problem. But their definition of the problem seems to be different from the definition found in other articles where the problem is simply the normal set cover with the addition that each set is limited to contain a maximum of k elements from the universe, as can be seen in eg. this description from Führer and Yu (taken from this article):

The solution to this problem then consists of a collection of sets whose union covers the universe. But IPZ states the problem in this way:

and in that, the solution is defined as a set C that contains at least one element from each of the sets S in $\mathscr{S}$. It is not stated that the collection of sets necessarily covers the universe. Finding a C of size |$\mathscr{S}$| is therefore trivial and finding a minimal C corresponds to finding elements that overlap different sets from $\mathscr{S}$ in the best possible way.

After this lengthy intro my question is this: Am I somehow not reading the definition given by IPZ correctly and is it just an other way of stating the same problem? Or is this two different problems that unfortunately has been given the same title?

The second definition uses the hitting set formulation, which is equivalent to the set cover problem. To see that, you may reverse the roles of sets and elements.  You can find more information on the wikipedia page.


How difficult is it to use the Mulmuley-Sohoni GCT approach to show *known* complexity separations? In this guest post by Josh Grochow at the complexity weblog he reports on a recent workshop devoted to GCT that was held at Princeton in July.
Several of the attendees argued that we should use GCT to attack easier problems than $\mathsf{P}$ vs. $\mathsf{NP}$ in order to build intuition and see if the method has potential.

The question that has been bugging me:

  Is it possible to use GCT to show known separations like $\mathsf{P} \neq \mathsf{EXP}$ or $\mathsf{L} \neq \mathsf{PSPACE}$?

Does something like $\mathsf{L} \neq \mathsf{PSPACE}$

Not even make sense in the GCT context, or
Is utterly trivial and uninteresting in GCT framework, or
Lead to conjectures just as hard as $\mathsf{P}$ vs. $\mathsf{NP}$  ?

Short answer: probably not (1), definitely not (2), and possibly (3).

This is something I have been thinking about off-and-on for a while now.  First, in a sense GCT is really aimed at giving lower bounds on computing functions, rather than decision problems. But your question makes perfect sense for the function class versions of $L$, $P$, $PSPACE$, and $EXP$.

Second, actually proving the boolean versions -- the ones we know and love, like $FP \neq FEXP$ -- is probably incredibly difficult in a GCT approach, since that would require the use of modular representation theory (representation theory over finite fields), which is not well understood in any context.

But a reasonable goal might be to use GCT to prove an algebraic analog of $FP \neq FEXP$.

To get to your question: I believe that these questions can be formulated in a GCT context, though it's not immediately obvious how. More or less, you need a function that is complete for the class and characterized by its symmetries; extra bonus if the representation theory associated to the function is easy to understand, but this latter is usually quite difficult.

Even once the questions are formulated in a GCT context, I have no idea how difficult it will be to use GCT to prove (algebraic analogs of) $FP \neq FEXP$ etc.  The representation-theoretic conjectures that will arise in these contexts will likely have a very similar flavor to the ones arising in $P$ vs $NP$ or permanent vs determinant.  One might hope that the classical proofs of these separation results might give some idea of how to find the representation-theoretic "obstructions" needed for a GCT proof.  However, the proofs of the statements you mention are all hierarchy theorems based on diagonalization, and I do not see how diagonalization will really give you much insight into the representation theory associated with a function that is complete for (the algebraic analog of) $FEXP$, say.  On the other hand, I haven't yet seen how to formulate $FEXP$ in a GCT context, so it's a little early to say.

Finally, as I mentioned in that blog post, Peter Burgisser and Christian Ikenmeyer have attempted to re-prove the lower bound on the border-rank of $2 \times 2$ matrix multiplication (which was proven to be 7 in 2006 by Joseph Landsberg).  They were able to show the border-rank is at least 6 by a computer search for GCT obstructions. Update April 2013: they have since managed to re-prove Landsberg's result using a GCT obstruction, and to show an asymptotic $\frac{3}{2}n^2 - 2$ lower bound on matrix multiplication using such obstructions. Although GCT has not so far reproduced the known lower bound on matrix multiplication, it does enable a computer search more efficient than the alternative (which would involve Grobner bases, which are doubly-exponential time in the worst case).  In their talks at the workshop, both Peter and Christian pointed out (correctly, I'd say) that what we really hope to get of computing small examples is not re-proving known lower bounds, but some insight that will let us use these techniques to prove new lower bounds.

The nice thing about GCT in the context of matrix multiplication is that the technique easily generalizes from $2 \times 2$ to $3 \times 3$ matrix multiplication (although computing the obstructions with the current techniques obviously gets more expensive), whereas Landsberg's approach seems very difficult to implement even for the $3 \times 3$ case.  A similar thing could be said about the complexity class separations you mention: GCT is general enough that it may apply not only to known results like $FP \neq FEXP$, but also to unknown ones like $P \neq NP$, whereas we know diagonalization does not.


FPT vs W[P] - Parameterized Complexity In parametrized complexity, $\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$. It is conjectured that each of the containments is proper.

If $\mathsf{FPT}=\mathsf{W}[P]$ then $\mathsf{P}=\mathsf{W}[P]$.

But does it follow that

If $\mathsf{FPT}=\mathsf{W}[1]$ then $\mathsf{FPT}=\mathsf{W}[P]$ ?
or
If $\mathsf{W}[t-1]=\mathsf{W}[t]$ (for some t) then $\mathsf{FPT}=\mathsf{W}[P]$ ?

This question is tricky as the answer (as far as I know) is still "don't know".

To add some weight to this, Flum & Grohe [1] give as open problems (p. 164):

  Is the $\mathrm{W}$-hierarchy strict under the assumption $\mathrm{FPT} \neq \mathrm{W[P]}$?
  For $t \geq 1$, does the equality $\mathrm{W}[t] = \mathrm{W}[t + 1]$ imply $\mathrm{W}[t] = \mathrm{W}[t + 2]$?

Moreover, in Downey and Fellow's recent monograph [2] the strongest (outright) statement they make is (p. 521):

  A more subtle hypothesis is that the $\mathrm{W}$-hierarchy is proper, and, in particular, $\mathrm{W}[1] \neq \mathrm{W}[2]$.

There is no following (or later) statement along the lines "otherwise the $\mathrm{W}$-hierarchy would collapse", or similar.

This is also preceded by:

  A weaker hypothesis might be that for some $t$,
  $$\mathrm{FPT} \neq \mathrm{W}[t]$$

Implying that it is possible that $\mathrm{FPT} = \mathrm{W}[t-1]$ with no other effects on the hierarchy.

References:

J. Flum and M. Grohe, "Parameterized Complexity Theory", Springer, 2006.
R. Downey and M. Fellows, "Fundamentals of Parameterized Complexity Theory", Springer, 2014.


What is the origin of logical relations? I actually have two questions:

Who first used logical relations to relate semantics?

I traced them back to Reynold's "On the Relation Between Direct and Continuation Semantics", but I can't claim to have made an exhaustive search.

I have found references to logical relations dating earlier (Tait, '67), but not for relating semantics.
What is the best current introduction for logical relations?

I know of Mitchell's "Type Systems for Programming Languages" from the Handbook of TCS. What other expositions are there?

Plotkin used logical relations in his unpublished but nevertheless widely circulated and influential 1973 paper "Lambda Definability and Logical Relations". I have a copy of this note on my webpage.

I used to think that this is where the name came from, but when I asked Rick Statman about this, he told me that Mike Gordon coined the term logical relation to describe Tait's method, and that he and Gordon Plotkin picked it up from him. I think this is how it entered programming language jargon, though you could make sure by asking Plotkin.


Diophantine equations and complexity classes LINEAR DIOPHANTINE EQUATIONS
(given natural numbers $a, b, c$, are there natural numbers $x$ and $y$ such that $ax + by + c = 0$?) are solvable in polynomial time.

QUADRATIC DIOPHANTINE EQUATIONS ($ax^2 + by + c = 0$) are NP-complete (NP-complete decision problems for quadratic polynomials).

General DIOPHANTINE EQUATIONS are undecidable (Davis-Putnam-Robinson-Matiyasevich theorem).

Are there other classes of Diophantine equations (with restrictions on their arguments/variables) that capture other complexity classes (in particular PSPACE) ?

This paper, Computational complexities of Diophantine equations with parameters by Tung, proves co-NP-completeness of a variant with parameters over natural numbers.


Is it in NP to check if the convex hull contains the unit ball? Given a set of $n$ points in $d$ dimensional Euclidean space, the problem is to determine if the convex hull contains the unit ball centered at the origin.

  Is this problem in NP?

It is in co-NP as one can give a point in the ball outside the convex hull as a witness and verify this fact using linear programming.

My focus here is not in computer precision relating to square roots although this may also be interesting.

(Related to https://mathoverflow.net/questions/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball .)

The problem is NP-hard; see my answer at mathoverflow. Thus there is no polynomial-size certificate that the unit ball is contained in the convex hull of given points unless $\text{NP} = \text{co-NP}$ (if $\text{NP} = \text{co-NP}$ then the polynomial hierarchy collapses).