Decide whether a matrix's kernel contains any non-zero vector all of whose entries are -1, 0, or 1 Given an $m$ by $n$ binary matrix $M$ (entries are $0$ or $1$), the problem is to determine if there exists two binary vectors $v_1 \ne v_2$ such that $Mv_1 = Mv_2$ (all operations performed over $\mathbb{Z}$).  Is this problem NP-hard?

It is clearly in NP as you can give two vectors as witnesses.

Equivalently: Given $M$, is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

Equivalently: Given $n$ vectors $X=\{x_1,\dots,x_n\}$ over $\{0,1\}^m$, are there two different subsets $A,B \subseteq X$ such that $\sum_{x \in A} x = \sum_{x \in B} x$?

EDIT: My original proof had a bug. I now believe that it is fixed.

We reduce the problem of EQUAL SUM SUBSETS to this problem. EQUAL SUM SUBSETS is the problem of: given a set of $m$ integers, find two disjoint subsets which have the same sum. EQUAL SUM SUBSETS is known to be NP-complete.

Suppose these bit strings were not vectors but representations of $n$-bit numbers in binary. Then the problem would be NP-complete by a reduction from EQUAL SUM SUBSETS.  I will show how to make these vectors behave like they are binary numbers. What we need is to be able to do carries; that is, for every pair of adjacent coordinates, we need to be able to replace the vector ..02.. by ..10.. .

How can we do that? We need a gadget that lets us do that. In particular, we need two subsets whose sums are ..02.. x  and ..10.. x, where x is a bit string using new coordinates (i.e., coordinates which aren't any of the $n$ coordinates making up the binary representations), and where there is only one way to create two subsets with the same sum in the new bit positions corresponding to x.

This is fairly easy to do. For every pair of adjacent bit positions, add three vectors of the following form. Here the last two bits are coordinates which are non-zero only in these three vectors, and every bit not explicitly given below is 0.

  ..10.. 11
  ..01.. 10
  ..01.. 01

Let me do an example. We want to show how 5+3=8 works.

Here is 8 = 5 + 3 in binary:

  1000

=

  0101
  0011

These bit strings give the same sum in binary, but not in vector addition.

Now, we have carries in the 1, 2, 4 places, so we need to add three sets of three vectors to the equation so as to perform these carries.

  1000 00 00 00
  0001 00 00 01
  0001 00 00 10
  0010 00 01 00
  0010 00 10 00
  0100 01 00 00
  0100 10 00 00

=

  0101 00 00 00
  0011 00 00 00
  0010 00 00 11
  0100 00 11 00
  1000 11 00 00

These sets now have the same sum in vector addition. The sums are:

  1222 11 11 11

in both cases.

This construction works great if there is only one carry per position, but there could potentially be up to $n$ carries per position, and you need to make sure that your construction can handle up to $n$ carries, and that the different carries don't interfere with each other. For instance, if you added two different sets of three vectors for the same pair of adjacent positions (which is what I proposed in my original proof):

  ..01.. 01 00
  ..01.. 10 00
  ..10.. 11 00
  ..01.. 00 01
  ..01.. 00 10
  ..10.. 00 11

you have the problem that you get two different sets of vectors giving the same sum:

  ..01.. 01 00
  ..01.. 10 00
  ..10.. 00 11

=

  ..01.. 00 01
  ..01.. 00 10
  ..10.. 11 00

How to fix this? Add one set of vectors which lets you carry 1, one set which lets you carry 2, and one set for 4, 8, $\ldots$, 2$^{\lfloor \log n \rfloor}$. I'm not going to go work out the details of this construction right now, but it should be fairly straightforward. Since each number has a unique binary representation, this will let you carry any number up to $n$. For carrying 4, for example, you need find four vectors which have the same sum as two vectors, and for which this is the only linear relation between the two sets. For example, the set

  ..01.. 11000
  ..01.. 00100
  ..01.. 00010
  ..01.. 00001
  ..10.. 10001
  ..10.. 01110

works. You can easily check that the relation

  11000
  00100
  00010
  00001

=

  10001
  01110

is the only possible relation among these six vectors because the matrix formed by these six rows has rank 5.


Can Bencodes Be Described With a Context-Free Grammar? Bencoding is the encoding scheme used by Bittorrent applications. You’re probably most familiar with bencoding via the .torrent file format used by Bittorrent applications. It’s a simple encoding scheme, so I am wondering if a context-free grammar could be constructed for it. There are a couple of reasons I think  it cannot:

The location of terminals depends on the ‘interpreted’ value of certain length-prefixed values.
Terminals can be present inside of non-terminal sequences, but in principal (i.e., in well-formed Bencodes) are not ever encountered by a parser except for verification maybe. In fact, entire Bencodes (in theory) could be present as values of, let’s say, a list element of a Bencode, but in such a way that they’re meant to be interpreted as “data” and not as something to be parsed or transformed by a rule. It’s ever-so-slightly more subtle than normal recursion as far as I can tell…

Update: When thinking about this I realized something odd whereby one could convert a context-dependent grammar into a context-free grammar; i.e., consider the problem of length-prefixed values such as appear in Bencode. For convenience I will use Bencode’s syntax; so let’s consider the string 5:hello. If you have a trivial function that converts the ASCII “5” into a unary value and all the other ASCII characters into a character then you have an equivalent structure.

Viz. 5:hello becomes olleh:hello; I like the idea of reversing the string because then you could easily construct another function to map the string back onto the ASCII numeral (after appropriate checks have been made that the string is in fact the length reported as to not skew semantics; I am not considering non-conforming strings, since we are talking about grammar...).

This is of course a very simple case of dependent grammar, but I wonder 1.) if anybody else has noticed this (I am sure), and 2.) if this could resolve some other context-dependent situations.

The language of valid Bencoded values is not context-free—and nor is just the language of Bencoded strings. Let $L$ be the set of valid Bencoded values, and let $L'$ be the intersection of $L$ with the regular language [0-9]*:a*, i.e. the Bencoded strings with just the symbol a. If $L$ were context-free, so would $L'$, but $L'$ does not satisfy the pumping lemma.

Suppose $L'$ is context-free, the pumping lemma applies. Let $n$ be the pumping threshold and let $w = \mathrm{dec}(n):a^n$, where $\mathrm{dec}(n)$ denotes $n$ written in decimal. Then $w = \alpha\beta\gamma\delta\epsilon$, and $\alpha\beta^m\gamma\delta^m\epsilon \in L'$ for all $m$. The colon must appear in $\gamma$ (the other cases can easily contradicted). Then the number to the left of the colon grows exponentially in $m$ (since its length in decimal increases linearly), but the string to the right only grows linearly, so the number can't be equal to its length.

You said

  If you have a trivial function that converts the ASCII “5” into a unary value and all the other ASCII characters into a character then you have an equivalent structure.

but it turns out that this function is not trivial from the perspective of context-free grammars.


Equivalence of two basic blocks My questions:

What are other names for this and similar problems and their fields? ("equivalence of varieties in universal algebra", "equivalence of algebraic structures", "rewriting systems for searching equivalence"?)
what algorithms do you know solving this kind of problems?
What papers/books do you recommend?

Problem

I'm interested in approaches of finding, whether two computations are equivalent?

I try to find my way between rewriting systems, automated theorem proving, logic programming, varieties, or just visiting graph of all possible basic block transformations (in order to find corresponding vertices (with some luck ;) ) ).

Of course. In finite domains, I could enumerate all possible inputs for all possible symbols permutations, check whether computations gives same results, and do this in finite time. I am looking for other approaches.

Computations

Computations are given as basic blocks represented in SSA - static single assignment form. We can assume finite number integer arithmetic (for example 64bit numbers). Computations run in RAM model.

For those not familiar with compilers theory and design, Basic Block has no jumps, no loops, no function call, one exit, and one entry etc. So we can say, that each execution of BB has O(1) complexity.

SSA - static single assignment form of basic block is DAG (Direct Acyclic Graph). In that sense, there is similar question on TCS.SE about unification theory and DAG isomorphism, while my context, focus, purpose and approach is different.

Equivalence

Let me be more specific what I mean by equivalence of computations. Let's take following setup:

two computations $f$ and $g$ and treat them as functions.
$P$ is a vector of $f$'s parameters $p_1, p_2, \ldots, p_n$
$P' = \operatorname{perm}(P)$ is permutation of parameters.

By equivalence, I mean, there exist permutation $P'$ that for any inputs $P$ , we have $f(P) = g(P')$ same (vector of) results in both computations.

Another equivalence definition

I've just found, definition of basic block equivalence, very similar to mine. I hope it might clarify, what I mean by that.

Let me cite from C Decompilation: Is It Possible? by Katerina Troshina, Alexander Chernov and Yegor Derevenets:

  Let $f$ be an object renaming transformation (...) $f(C_1) = C_2$ if there exists a renaming of named objects such as registers, labels, etc, preserving program semantics and making the programs $f(C_1)$ and $C_2$ syntactically indistinguishable. Existence of such an f transformation is a sufficient condition of program equivalence. (...) Equivalence of basic blocks may be checked by reducing them to a RISC-like representation. Let $h$ be a basic block reduction transformation. Let $B_1$ and $B_2$ be basic blocks, let $B'_1 = h(B_1)$ and $B'_2 = h(B_2)$ be the corresponding basic blocks in the RISC-like representation. Let $g$ be an instruction reordering transformation preserving the program semantics. If for the basic blocks $B_1$ and $B_2$ there exist transformations $f$ , $g$ and $h$ making $g(f(h(B_1))$ and $h(B_2)$ syntactically indistinguishable, basic blocks $B_1$ and $B_2$ are equivalent.

Although, their approach is more focused on assembly code, my approach is more in direction of path-algebra for algorithm pattern matching. What it implies, I'd like to take into account, not only instruction reordering, but equations they represent as well. (Simple example : $(a + b) / 2$ is different to $a / 2 + b / 2$ on $k$-bits integer computations - modular arithmetic. When $a + b \ge 2^k$ results are different. While algorithms, authors/implementators intentions might be the same. That's why I'd like to mix approaches from different fields).

The actual field you seem to be talking about is formal methods, and in particular, formal semantics of programming languages. The particular programming language you have (the machine language of the processor) seems to be without recursion and with some global state involved. This kind of effectful semantics has been well investigated in various forms and approaches.

The fields involved have developed so much that a full overview is out of the question. Also, these not only contain results, but tools employed to attack the difficulties inherent in establishing eqivalences. I will try to mentionsome keywords and topics.

One famous approach is that of axiomatic semantics. In this approach one interleaves the program with formulae from a prespecified logic, used to reason about the language. For example, in your case this logic might encode statements about the state of the processor's registers: $\exists n: r_1 =n \wedge r_2 >n^2+n-5$. These combine to form a logic (rigorous reasoning system), where statements have the form $\{\phi\}C\{\psi\}$. $\phi$ is a formula in this logic representing a precondition known about the state of the world prior to the execution of the program phrase $C$. $\psi$ is a formula representing the postcondition, guaranteed to be valid in state of the world (under the assumption that the precondition held).

The semantics is then given axiomatically as a collection of pre/post-conditions and inference rules. For instance, the semantics of register addition may look like this:
$\{r_1 = n \wedge r_2 = m\} {\rm addi\ r3,r1,r2}\{r_3=m+n\}$. The inference rules may include rules for using intermediate formulae to compose smaller phrases into larger ones.

So in your case, you will need to show that for all preconditions and postconditions, the statement $\{\phi\}B_1\{\psi\}$ is valid iff $\{\phi\}B_2\{\psi\}$ is valid. There are several such systems, applied academically and industrially. The keywords are Hoare logic, separation logic, invariants.

Another approach is operational semantics. In this approach the meaning is given by an implementation of the language. It is desirable to give an abstract implementation, so that rigorous reasoning is possible. Nowadays it is also reasonable to expect this semantics to be structural: the operation of the machine is directed by the structure of the languages syntax, and the meaning of a composite program is given by the meaning of its components.

The implementation is commonly given as a transition system, where each state is a configuration containing the current program phrase that awaits execution. Some keywords and tools that are useful for your problem: structural operational semantics, structural induction, small-step and big-step semantics, observational equivalence, contextual equivalence.

A third approach is denotational semantics. In this, the meaning of a program phrase is given by a mathematical function of its components. This semantics tends to give a global understanding of the mathematical  structure of the semantics. As a consequence, their presentation is a lot less elementary, and tend to lag behind the other approaches. On the other hand, this global understanding may give rise to deep insights about the behaviour and structure of the language. Some keywords: domain theory, category theory, monads, call-by-push-value.

The bottom line is that program equivalence has been investigated quite a lot.  It is one of the most fundamental questions in semantics. In your case, determining algorithmically and tractably whether two such computations are equivalent will probably involve tools from model checking.  Indeed, if you have $n$ registers of $k$ bits then the state-space has at least $n2^k$ points. An exhaustive search of this space is then $\Omega(n2^km)$ where $k$ is the length of the program. Of course, it might even be much worse than this.  So I guess you'll need to employ some non-trivial reasoning to establish such equivalences. Some keywords: the state-space explosion, abstract and symbolic interpretation, normalization by evaluation.

Some places to start looking at things. The Handbook of Theoretical Computer Science (Volume B) has some chapters covering various topics in semantics (Chapters 7, 9, 11, 12, 15 and 19). By now these topics are taught to undergraduates in various universities, they usually concentrate on operational and axiomatic semantics (as they are more elementary).  There is a related question about that here at TCS@SE.

I'm sorry for speaking in such broad terms, but the body of knowledge and tools underlying this problem is quite extensive. I hope that I at least given you somewhere to start looking!

It is a pet peeve of mine that the formal semantics community, who explores these  questions inherent to compiler theory, have drifted apart from the compiler community. This is not entirely the semantics' community fault: first, as usual in TCS, a big body of theory needs to be developed before a substantial application is possible. Also, Moore's law and other advances in computer science allowed compiler writers to concentrate on other problems, and dismiss formal semantics as abstract nonsense. Another observation I heard from Paul Levy is that people from outside the community take interest because of the usefulness of the problems, and then become so fascinated with the theory that they join the community.

Finally, i'll mention that the gap is closing. There are researchers around the world from both communities that take interest in each other and in closing the gap. A few local names in the semantics world: Nick Benton, Gordon Plotkin, Peter Sewell.


Minimizing Automata accepting $\omega$-words (i.e. infinite words) What is the standard approach on minimizing Büchi-Automata (or also Müller-Automata)? Transfering the usual technique from finite words, i.e. setting two states to be equal if the words "running out" of the states which are accepted are the same, will not work. For example consider the Büchi-Automoton accepting all words with an infinite number of a's consisting of two states,  a initial and a final state, and the final state is entered each time an a is read, and the initial state is entered each time a different symbol is read. Both states are considered equal by the above defintion, but collapsing them yields an automata consisting of a single state, and thereby accepting every words.

This question generated a lot of literature in the 80's, partly due to a bad approach to the problem. This is a rather long story that I will try to summarize in this answer.

1. The case of finite words

One can find two definitions of a minimal DFA in the literature.
The first one is to define the minimal DFA of a regular language as the complete DFA with the minimum number of states accepting the language.
The second one is longer to define but is mathematically more appealing than the first one and it gives stronger properties.

Let us recall that a DFA $(Q, A, \cdot, i, F)$ is accessible if for all $q \in Q$, there is a word $u \in A^*$ such that $i \cdot u = q$. It is complete if $q \cdot a$ is defined for all $q \in Q$ and $a \in A$.

Let ${\cal A}_1 = (Q_1, A, \cdot, i_1, F_1)$ and ${\cal A}_2 = (Q_2, A,
\cdot, i_2, F_2)$ be two complete, accessible DFAs. A morphism from $\mathcal{A}_1$ to $\mathcal{A}_2$  is a function $\varphi:Q_1 \to Q_2$ such that

$\varphi(i_1) = i_2$,
$\varphi^{-1}(F_2) = F_1$,
for all $q \in Q_1$ and $a \in A$, $\varphi(q)\cdot a=\varphi(q\cdot a)$.

One can show that these conditions imply that $\varphi$ is necessarily surjective (and thus $|Q_2| \leqslant |Q_1|$). Furthermore, there is at most one morphism from ${\cal A}_1$ to ${\cal A}_2$ and if this morphism exists, then ${\cal A}_1$ and ${\cal A}_2$ recognize the same language. Now, one can show that for every language $L$, there is a unique complete accessible DFA ${\cal A}_L$ accepting $L$ and such that, for every complete accessible DFA $\cal A$ accepting $L$, there is a morphism from $\cal A$ onto
${\cal A}_L$. This automaton is called the minimal DFA of $L$. Note again that since
the number of states in ${\cal A}_L$ is smaller than the number of states in $\cal A$, ${\cal A}_L$ is also minimal in the first sense.

It is worth mentioning that there is also a suitable algebraic definition for incomplete DFAs. See [Eilenberg, Automata, Languages and Machines, vol. A, Academic Press, 1974] for more details.

2. Back to infinite words

Extending the first definition does not work, as shown by Shaull in his answer. And unfortunately one can also show that the universal property of the second definition does not extend to infinite words, except in a few particular cases.

Is it the end of the story? Wait a second, there is another minimal object that accepts regular languages...

3. The syntactic approach

Let us first return again to finite words. Recall that a language $L$ of $A^*$ is
recognized by a monoid $M$ if there is a surjective monoid morphism
$f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Again, there exists a monoid $M(L)$, called the syntactic monoid of $L$, which recognizes $L$ and is a quotient of all monoids recognizing $L$. This syntactic monoid can be defined directly as the quotient of $A^*$ by the syntactic congruence $\sim_L$ of $L$, defined as follows:
$$
  \text{$u \sim_L v$ if and only if, for all $x, y \in A^*$, $xuy \in L \iff xvy \in L$}
$$
The good news is that this time, this approach has been extended to infinite words, but it took a long time to discover the appropriate notions.
First, the suitable notion of a syntactic congruence was found by A. Arnold (A syntactic congruence for rational $\omega$-languages, Theoret. Comput. Sci. 39,2-3 (1985), 333–335).
Extending syntactic monoids to the setting of infinite words required a more sophisticated type of algebras, called nowadays Wilke algebras in honor of T. Wilke, who was the first to define them (T. Wilke, An algebraic theory for regular languages of finite and infinite words, Int. J. Alg. Comput. 3 (1993), 447–489). More details
can be found in my book Infinite words coauthored with D. Perrin.

4. Conclusion

Thus there is a mathematically sound notion of a minimal object accepting a given regular $\omega$-language, but it does not rely on automata.
This is actually a rather generic fact: automata are a very powerful algorithmic tool, but they are not always sufficient to treat mathematical questions on languages.


How many tautologies are there? Given $m, n, k$, how many of $k$-DNFs with $n$ variables and $m$ clauses are tautology? (or how many $k$-CNFs are unsatisfiable?)

The answer depends on $k$, $m$, and $n$. Exact counts are generally not known, but there is a "threshold" phenomenon that for most settings of $k$, $m$, $n$, either nearly all $k$-SAT instances are satisfiable, or nearly all instances are unsatisfiable. For example, when $k=3$, it has been empirically observed that when $m < 4.27 n$, all but a $o(1)$ fraction of 3-SAT instances are satisfiable, and when $m > 4.27n$, all but a $o(1)$ fraction are unsatisfiable. (There are also rigorous proofs of bounds known.)

One starting point is "The Asymptotic Order of the k-SAT Threshold".

Amin Coja-Oghlan has also done a lot of work on these satisfiability threshold problems.


TIME(n) versus TIME(nlogn) The time hierarchy theorem implies TIME($n$) is strictly contained in TIME($n\log^{1+ε}n$) for all ε>0. Is the relationship between TIME($n$) and TIME($nlogn$) known?

For all $a≥0$ and $ε>0$, $\mathrm{DTIME}(O(n \log^{a} n))$ is strictly contained in $\mathrm{DTIME}(O(n \log^{a+ε} n))$; see my answer here.

To recap, the logarithmic overhead comes from tape reduction (and is not needed if the number of tapes is fixed and is at least two).  There is a nonconstructive argument that converts the logarithmic overhead into time hierarchy at $\log^{ε} \mathrm{time}$ multiplicative precision for well-behaved (time-constructible and in a certain sense continuous) time bounds.

A constructive proof of the strict inclusion of $\mathrm{DTIME}(O(n))$ in $\mathrm{DTIME}(O(n \log n))$ remains (to my knowledge) an open problem.


General definitions for mixed graphs? (degrees, connectivity, etc) I'm writing a framework for some graph theorical tasks and am unsure about some definitions regarding mixed graphs. Degrees and connectivity in particular.

  A mixed graph G is a graph in which
  some edges may be directed and some
  may be undirected.

I couldn't find any comprehensive definitions for mixed graphs on the web and am kind of stuck here as I don't want to unintentionally contradict general graph theoretical principles by just following my gut feelings of what feels right for me.

One of those uncertainties being:
How is in-degree (and out-degree respectively) defined in mixed graphs?

Is it this?:

inDegree():
    directedEdgeCount = count(incoming directed incident edges)
    #undirected edges being ignored
    return directedEdgeCount

…or is it this?:

inDegree():
    directedEdgeCount = count(incoming directed incident edges)
    undirectedEdgeCount = count(undirected incident edges)
    return directedEdgeCount + undirectedEdgeCount

I found some general graph definitions saying that:

degree():
    return inDegree() + outDegree()

Which makes perfect sense for strictly directed/undirected graphs if first version of inDegree() was to be used. It would count undirected edges twice though, if second version of inDegree() was to be used.
My gut says that undirected edges lacking any direction basically allow flow in both directions and thus should be included in inDegree()/outDegree(), shouldn't they?

And coming from the above I have to ask:

If this is correct:

isDirectNeighborOf(other):
    return (self has any edge connecting it to/from/between other)

…which it is, from my understanding.

Then which one of these is correct? Is it this?:

isDirectPredecessorOf(other):
    #ignoring undirected edges
    return (self has outgoing directed edge to other)

…or this?:

isDirectPredecessorOf(other):
    return (self has outgoing directed or undirected edge to other)

Concrete example:

What is the in-degree of B? (my gut says 3)
What is the out-degree of C? (my gut says 3)
What is the in-degree of D? (my gut says 2)
What is the out-degree of D? (my gut says 2)
Is D direct predecessor of B? (my gut says YES)
Is D direct successor of B? (my gut says YES)

Does anybody here happen to have a comprehensive set
of definitions regarding mixed graphs?

As with many graph types the theoretical sonstruct mixed graph is ambiguously used.
Hence I'm not so much searching for a universally accepted definition, but rather looking for any at all.

The definition I found in Zhang, On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias (Section 2.1) is:

  A mixed graph is a vertex-edge
  graph that can contain three kinds of
  edges: directed ($\rightarrow$), bi-directed
  ($\leftrightarrow$) and undirected ($-$), and at most
  one edge between any two vertices.

  ...

  Two vertices are said to be
  adjacent in a mixed graph if there is an edge (of any kind) between them.
  Given a mixed graph $G$ and two
  adjacent vertices A,B therein, A is a
  parent of B and B is a child of A if A $\rightarrow$ B is in $G$; A is called
  a spouse of B (and B a spouse of
  A) if A $\leftrightarrow$ B is in $G$; A is called a
  neighbor of B (and B a neighbor of A) if A $-$ B is in $G$.

  ...

  A directed path from $V_{0}$
  to $V_{n}$ in $G$ is a sequence of distinct vertices
   such that for 0
  $\leq$ i $\leq$ n-1, $V_{i}$ is a parent of
  $V_{i+1}$ in $G$. A is called an
  ancestor of B and B a descendant of A if A = B or there is a directed path from A to B.

Richardson and Spirtes give another nice and simple definition of mixed graphs in Ancestral Graph Markov Models (Section 2.2).

  Note that the three edge types should be considered as distinct symbols, and in particular

  A $-$ B $\neq$ A $\leftrightarrows$ B $\neq$ A $\leftrightarrow$ B.

However, none of them defines in and out degree.


How common is phase transition in NP-complete problems? It is well known that many NP-complete problems exhibit phase transition. I am interested here in phase transition with respect to containment in the language, rather than the hardness of the input, relative to an algorithm.

To make the concept unambiguous, let us formally define it as follows. A language $L$ exhibits phase transition (with respect to containment), if

There is an order parameter $r(x)$, which is a polynomial time computable, real valued function of the instance.
There is a threshold $t$. It is either a real constant, or it may possibly depend on $n=|x|$, that is, $t=t(n)$.
For almost every $x$ with $r(x)<t$, we have $x\in L$. (Almost every means here: all but vanishingly many, that is, the proportion approaches 1, as $n\rightarrow\infty$).
For almost every $x$ with $r(x)>t$, we have $x\notin L$.
For almost every $x$, it holds that $r(x)\neq t$.  (That is, the transitional region is "narrow.")

Many natural NP-complete problems exhibit phase transition in this sense. Examples are numerous variants of SAT, all monotone graph properties, various constraint satisfaction problems,  and probably many others.

Question: Which are some "nice" exceptions? Is there a natural NP-complete problem, which (probably) does not have a phase transition in the above sense?

expert researchers in this area basically assert that phase transitions are a universal feature of NP complete problems although this has yet to be formulated/ proven rigorously and it is not yet widely regarded/ disseminated in the larger field (it emanates more from an empirical-oriented branch of study). its nearly an open conjecture. there is strong evidence. there are no plausible candidates for non phase-transition NP complete problems. here are two refs that support this pov:

Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science / Moore
Phase transition behavior / Walsh (ppt)

here is a rough sketch of the truth of the assertion. it has to do with P contained in NP complete. an NP complete problem/ language must have instances that are solvable in P time and others that are solvable in exponential (or at least superpolynomial-) time if P≠NP. but there must always be some way to "group" the P instances from the "non-P" instances. therefore there must also always be some "transition criteria" between the P and non-P instances. in short, maybe this phenomenon is intrisically coupled with P≠NP!

another rough argument: all NP complete problems are interchangeable via reductions. if a phase transition is found in a single one, it must be found in all of them.

more circumstantial evidence for this, more recently (~2010) it was shown the phase transition shows up for lower bounds on monotone circuits for clique-detection on random graphs.

Average case complexity of detecting cliques / Rossman

full disclosure: Moshe Vardi has studied phase transitions particularly in SAT and has a contrasting more skeptical view in this talk/ video.

Phase transitions and computational complexity


Sublinear finite-precision sampling in a stream I am looking to sample a single item from a stream such that each item in the stream has an equal probability of being selected. This is a restricted version of the reservoir sampling problem.

On a stream of length $n$, I would like to make $o(n)$ calls to my random number generator (henceforth "RNG"). Additionally, I would like to work in finite precision. Is there a data structure that supports this?

As usual with reservoir sampling, I want to preserve that:

Each item is selected with equal probability
The total time used is $O(n)$ with high probability. A Las Vegas algorithm would be just fine
No more than $O(1)$ machine words and $O(1)$ stream items are stored between stream items arriving
Only one pass is made over the stream

Results that I know about that do not meet my requirements include:

The standard reservoir sampling data structure makes $\Omega(n)$ calls to the RNG.
"Random sampling with a reservoir" by Jeffrey S. Vitter and "Reservoir-sampling algorithms of time complexity $O(n(1 + \log(N/n)))$" by Kim-Hung Li need only $o(n)$ calls to the RNG but use arbitrary precision arithmetic.
"Sampling in Space Restricted Settings" by Bhattacharya et al. describes a data structure that meets the above criteria but can fail to sample an item with non-zero probability.
Exact minwise hashing (in which each index in the stream is hashed and the reservoir holds the item at the index with the lowest hash value seen so far) would suffice, but exact minwise hashing families have size at least $e^{n - o(n)}$ according to Theorem 1 of "Min-Wise Independent Permutations" by Broder et al.. Storing a member of the family would require using at least $(\lg e)(n - o(n))$ bits of space between the arrival of stream items.

The strategy will be to use Vitter's algorithm, but replace the arbitrary-precision random number with online generation of the bits of that random number.

Building block: sampling without arbitrary precision arithmetic

Suppose we want to sample a discrete random variable $X$ from a distribution with cdf $F$ (i.e., $F(x) = \Pr[X \le x]$).  Then one approach is to sample $y$ uniformly at random from $[0,1]$, find $x$ such that $F(x-1) < y \le F(x)$, and output $x$.  This requires arbitrary precision arithmetic.

Here is a variant that avoids the need for arbitrary precision arithmetic, at the cost of making the algorithm a Las Vegas algorithm (so the worst-case running time is unbounded but the expected running time is nicely bounded).  Basically, we sample the bits of $y$ one at a time, and stop as soon as we know what answer the prior method would output.  At the $b$th stage, we know the first $b$ bits of $y$, i.e., we know $\tilde{y}$ such that $y \in [y, y + 1/2^b)$ and $2^b \tilde{y}$ is an integer.  Now, we find $x$ such that $F(x-1) < \tilde{y} \le F(x)$.  If $F(x-1) < \tilde{y}$ and $\tilde{y} + 1/2^b \le F(x)$, then we output $x$ and stop.  (In this case, we don't know what the exactly value of $y$ is, but we still know it satisfies $F(x-1)< y \le F(x)$, so $x$ is certainly the right answer.)  Otherwise, we output nothing and continue, sampling the next bit of $y$.

What's the running time of this procedure?  The expected time until termination is $O(\lg n)$, where $n$ is the number of different possible values of $X$.  (Why?  Because at the $b$th stage, at most $n$ out of the $2^b$ possible values for $\tilde{y}$ will cause us to continue on to the $b+1$th stage.  In particular, once $b$ exceeds $\lg n$, each stage has at least a one-half probability of terminating.)  So, this gives a Las Vegas algorithm to sample from $X$, with exactly the right distribution, and with $O(\lg n)$ expected bits sampled from the RNG.

Solving your problem

Now we can solve your particular problem.  We simply apply Vitter's algorithm (e.g., Algorithm Y), but instead of sampling the random value $\mathscr{S}$ using arbitrary-precision arithmetic, instead use the method described above.

How many random bits do we need?  Based on the results in that paper, the expected number of times we need to sample $\mathscr{S}$ is $O(\log n)$, where $n$ is the length of the stream.  Also each time we sample $\mathscr{S}$ the expected number of bits we need to sample is $O(\log n)$.  Therefore, we'll need $O((\log n)^2)$ bits from the RNG, on average.

Also the total (expected) running time will be $O(n)$, if you use Vitter's efficient algorithms for sampling $\mathscr{S}$ (e.g., Algorithm Y and binary search or Newton's method).


From Church-encoding to induction principle I am looking for an algorithm to go from a Church-encoded datatype to their induction principle in the Calculus of Constructions. For example:

Unit = {t : *} -> t -> t
~>
(x : Unit) -> {P : Unit -> *} -> P (\{t} x. x) -> P x

Nat = {t : *} -> t -> (t -> t) -> t
~>
(x : Nat) -> {P : Nat -> *} -> P (\{t} z s. z) -> ({m : Nat} -> P m -> P (\{t} z s. s (m {t} z s))) -> P x

It seems like this should be possible for any Church-encoded datatype. Does anybody know such an algorithm/translation or resources on it?

Let $F : \mathsf{Type} \to \mathsf{Type}$ be a type constructor and let $W_F$ be the inductive type defined by $W_F = F W_F$. Not every $F$ has such an inductive types, but this is not important for this discussion.

The starting point of Church's encodings is the observation that $W_F$ ought to be
$$\forall T : \mathsf{Type} \,.\, (F T \to T) \to T.$$
Thus, to get an induction principle out of a Church encoding, we take the following steps:

Rewrite the Church encoding in the form $\forall T : \mathsf{Type} \,.\, (F T \to T) \to T$ for a suitable $F$.
Derive an induction principle for $F$, as in your own answer to your own question.

Let us try a couple of examples.

Unit type

\begin{align*}
\mathsf{unit} &= \forall T . T \to T \\
&= \forall T . (1 \to T) \to T \\
&= \forall T . (F T \to T) \to T
\end{align*}
where $F X = 1$.

Empty type

\begin{align*}
\mathsf{unit} &= \forall T . T \\
&= \forall T . 1 \to T \\
&= \forall T . (0 \to T) \to T \\
&= \forall T . (F T \to T) \to T
\end{align*}
where $F X = 0$.

Natural numbers

\begin{align*}
\mathsf{nat} &= \forall T . (T \to T) \to (T \to T) \\
&= \forall T . (T \to T) \times T \to T \\
&= \forall T . T \times (T \to T) \to T \\
&= \forall T . ((1 + T) \to T) \to T \\
&= \forall T . (F T \to T) \to T
\end{align*}
where $F X = 1 + X$.

Binary trees

We can also go backwards. The binary trees are the inductive type for $F X = 1 + X \times X$, thus their Church encoding is

\begin{align*}
\mathsf{tree} &= \forall T . (F T \to T) \to T \\
&= \forall T . ((1 + T \times T) \to T) \to T \\
&= \forall T . (T \times (T \times T \to T) \to T \\
&= \forall T . T \to (T \to T \to T) \to T
\end{align*}

It all works beautifully.


Lower bounds for Polynomials computing the boolean functions Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields.
One of the most popular examples is Fourier Analysis e.g.  http://analysisofbooleanfunctions.org/ .
Another topic is transforming small depth circuits to polynomials over the integers with small degree and  magnitudes of small weights. For example, the transformation from ACC circuits to polynomials proved by Yao and Beigel and Tarui is notable.
My questions are:

Qestion A. Is there a list of results about lower bounds and remarkable techniques for polynomials computing boolean functions.
I know Williams' separation between NEXP and ACC.
Question B. Does the recent separation result about ACC $\circ $ THR circuits by Williams contain some interpretation relating with polynomials computing boolean funcitons ?
Question C. Is proving lower bounds on the number of monomials or the degree or other  formally defined complexity measures related with algebraic complexity theory and arithmetic circuit complexity established by Valiant with VP v. VNP problem??
I am reading the survey written by Shiplka, and have met a difference between boolean complexity and arithmetic complexity: semantic versus syntatic.

Here is a response to the J's question.
The survey has a remark about the difference between polynomial and polynomial function.
Taking an example, $x^{2}-x$ is a polynomial which is NOT identicdally zero but is a polynomial function $GF(2)^{n}\rightarrow GF(2)$ identically zero over $GF(2)$.
In algebraic complexity, Valiant's question is  about complexity of the expressing polynomial (not polynomial function).
However, I mainly want to consider polynomial functions. Thanks.

Regarding Question C: Number of monomials is essentially the same thing as circuit size of depth-2 algebraic circuits (unless the polynomial is a product of linear polynomials, in which case one could also consider a depth-2 circuits with a multiplication gate at the top).

Degree is very closely related to the depth of algebraic circuits, as in the results of Hyafil and Valiant-Skyum-Berkowitz-Rackoff.


Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$? We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a regular tree grammar (Chapter 2). Both formalisms hold close resemblances to the well-known string analogues.

  Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

Obviously there are tree languages such that the height of a tree is linear in its size; and in the book Analytic Combinatorics it is shown e.g. that binary trees of size $n$ have average height $2\sqrt{ \pi n}$. If I understand Proposition VII.16 (p.537) of the mentioned book correctly, then there is a wide subset of regular tree languages that have average height of $\Theta(\sqrt{n})$, namely those in which the tree language is also a simple variety of trees fulfilling some extra conditions.

So I was wondering whether there is a regular tree language showing a different average height or if there is a true dichotomy for regular tree languages.

Note: This question has been asked before on Computer Science, yet it has been unanswered for more than three months. I would like to repost it here because the question is too old to migrate and because there is still an interest in the question. Here is a link to the original post.

I believe that the answer is as you suggest that no other asymptotics than $\Theta(1)$, $\Theta(\sqrt{n})$ and $\Theta(n)$ are possible. A promising route to prove this could be to apply the techniques from the paper which derives the $\Theta(\sqrt{n})$ asymptotics to the run trees of the regular language. Notice that a tree is accepted if there exists a run tree so it should be possible to first derive (using loc.cit.) the average height of a randomly generated run tree and take it from there, i.e. show that projecting away the states does not change the average height.


"The Solution Problem" - How to get credit for your work as an undergrad? I have come to a rather startling discovery in regards to a question that has been posed to me a number of times through my now almost 1 year of CS studies.

Solving this problem is of great interest to many people, and if I have indeed done so... What do I do?

I see a few options, but none seem to ensure that my work gets recognized as my own: I could stash away the notes till the time comes for my masters thesis. This would force me to share both work and credit with my supervisor, though. I could attempt to publish it... But who would want to take work from a 9 months old computer scientist?

I am at a loss - in attempting to solve a difficult problem I have only given rise to an even more difficult one!

Worrying about someone taking credit for your work is very common among amateurs and people just starting out, but in my experience is far less common with more experienced researchers. I'm not really sure exactly what the reason for this is, but I have encountered this phenomenon numerous times. I would venture that it is perhaps because those with more experience in the field know how uncommon it is for one person to essentially steal another's results. Most people are relatively good, or at worst benign, and wouldn't dream of taking credit for work they haven't contributed to. Couple that with the fact that being caught plagiarizing someone else's work would be career suicide, and you can be pretty confident that no one you talk to is likely to write up your idea and pass it off as their own.

As Suresh says, you could always upload it to the arxiv, but I would be inclined not to do this, as if it turns out that the work is not novel or there is a major error, then you cannot actually delete the paper, but rather will have to post a retraction, and the original will still be there for all to see. Even now, I still ask colleagues to check any paper I consider relatively important before uploading a manuscript.

If I were you, I would be inclined to talk to one of my lecturers in the first instance, as they can probably give you a feel for whether your solution is novel (and correct), and if it meets both of these criteria, they should be able to give you an idea of how best to proceed. Alternatively, you could just post it as a question here, asking if the result was previously known, or if anybody could point you to a good survey paper on the problem. You'd have a time stamp from the post time, so you wouldn't have to worry about that. If you got an encouraging response here (i.e. that it was not currently known), then you could consider how to proceed from there. If on the other hand, it was already known, or there was a flaw, then it wouldn't really matter.

Technically, you could also simply write it up and submit it to a journal. As Dave says, no one involved in the process will actually know your level (the first time, it's kind of a kick when you get the correspondence addressed to you as either Dr. or Professor), unless one of the reviewers happens to know you personally. However, I would not suggest doing so. You need to search the literature to make sure your idea is actually novel, and as Dave mentions, the writing of papers is an art in and of itself. You would probably need to read a lot of journal articles to even get the style right.


Complexity of a linear algebra problem Let matrix $M \in \{0,1\}^{r \times s}$ ($s>r$), let function $f:\Bbb Z^{} \rightarrow \pm1$ and let $\alpha \in \Bbb Z \cap (0,s)$ be given.

Is it NP-complete to decide if $\exists u \in \{0,1\}^{1 \times r}$ with $v=uM$: $|f(v)| = {\sum_{i=1}^{s}f(v_{i})^{}} \geq \alpha$?

Yes, it is NP-complete, by reduction from 3SAT.  In particular, we will go through an intermediate problem, which I will define as follows:

Definition.  The 1-to-3 of $k$ problem is as follows: given $n$ sets $S_1,\dots,S_n$, decide whether there exists $y_1,\dots,y_m \in \{0,1\}$ such that $1 \le \sum_{j\in S_i} y_j \le 3$ holds for all $i$.

Theorem 1. The 1-to-3 of $k$ problem is at least as hard as 3SAT.

Proof: Suppose we have a formula $\varphi$ with $n$ clauses over $m$ variables, $x_1,\dots,x_m$.  Introduce $m'=2m$ variables, $y_1,\dots,y_m$.  The intent is that these will correspond to the $2m$ literals $x_1,\dots,x_m,\neg x_1,\dots,\neg x_m$ (e.g., $y_i=1$ if and only if $x_i=\text{True}$; $y_{m+i}=1$ if and only if $x_i=\text{False}$); we will introduce a few sets to enforce this intent.  There are $n'=n+m+\lceil m/3\rceil$ sets, as follows:

First, there are $n$ sets, one for each clause of $\varphi$.  If $\varphi$ has the clause $(y_a\lor y_b\lor y_c)$ (where $y_a,y_b,y_c$ are three literals), then we'll add a set $S=\{a,b,c\}$ to enforce that at least one of $y_a,y_b,y_c$ must be true.
The next $m$ sets enforce that $x_i \lor \neg x_i$ is true for all $i$.  In particular, for each $i$, we add a set to enforce that at least one of $x_i, \neg x_i$ must be true, e.g., the set $S=\{i,i+m\}$ (if $y_i$ corresponds to $x_i$ and $y_{i+m}$ corresponds to $\neg x_i$).
Finally, the last $\lceil m/3 \rceil$ sets enforce that $x_i$ and $\neg x_i$ are not allowed to both be true.  We'll do this by enforcing that one, two, or three of $x_1,\neg x_1,x_2,\neg x_2,x_3,\neg x_3$ are true (e.g., the set $S=\{1,2,3,m+1,m+2,m+3\}$), and that at least one, two, or three of $x_4,\neg x_4,x_5,\neg x_5,x_6,\neg x_6$ are true (e.g., the set $S=\{4,5,6,m+4,m+5,m+6\})$, and so on.   Notice that, thanks to the previous category of sets, surely at least three of these 6 literals will be true, so asking that "one, two, or three should be true" amounts to asking that exactly three of them must be true -- which has the desired effect.

Finally, it is easy to see that this 1-to-3 of $k$ problem has a solution if and only if $\varphi$ has a satisfying assignment.  That completes the proof.

Theorem 2. Your problem is at least as hard as the 1-to-3 of $k$ problem.

Proof. Suppose we have a 1-to-3 of $k$ problem with $s$ sets over variables $y_1,\dots,y_r$.    Define $f(0)=0$, $f(1)=1$, $f(2)=1$, $f(3)=1$, and $f(k)=0$ for all $k>3$.  Define the matrix $M$ based upon the sets $S_1,\dots,S_s$.  In particular, if $S_i=\{a,b,c,\dots\}$, the $i$th column of $M$ has a 1 in the $a$th, $b$th, $c$th, $\ldots$ rows and is zero elsewhere ($M_{j,i}=1$ if and only if $j \in S_i$).  Finally, set $\alpha=s$.

Now $|f(v)|\ge \alpha$ holds if and only if $f(v_1)=f(v_2)=\dots=f(v_s)=1$.  Thus, this choice of $f$ and setting of $\alpha$ ensures that the only way to satisfy the equation $|f(v)|\ge \alpha$ is if each $v_i$ is 1, 2, or 3.  If we focus on $v_i$, corresponding to the set $S_i=\{a,b,c,\dots\}$, then $f(v_i)=1$ if and only if $1 \le y_a+y_b+y_c+\dots \le 3$.  Therefore, this instance of your problem has a solution if and only if the original 1-to-3 of $k$ instance does.


More efficient Cook-Levin reduction In the Arora-Barak book, in the Cook-Levin reduction, the resulting SAT formula is of size $T(n)\log(T(n))$, where $T(n)$  is the running time of the given Turing machine.

Is there a method to get a $O(T(n))$ length SAT formula?

The original TM is made oblivious (a TM is oblivious if the position of the head at the $i$th step depends only on the length of the input string). This step brings the $O(\log(n))$ factor. Once we have an oblivious TM that takes time $T'(n)$, the SAT formula is of length $O(T'(n))$.

Can we somehow bypass the step of making the TM oblivious?

The obliviousness of the Turing machine is very crucial for Cook-Levin construction to run in time $t(n) \log t(n)$. If the Turing machine is not-oblivious (that is the head position at $i^{th}$ step of computation is not a function of input length ) then, on different inputs, the head position at $i^{th}$ step can be at various positions. But then writing a constant size formula which depends only on the two cells adjacent to head position and head position itself, to ensure correctness of transition from one configuration to the next, cannot be written without knowing the input(As Kaveh pointed out, it is easy to get a $t(n)^2$ formula without the TM being oblivious). But whereas if the Turing machine is oblivious, we can know the position of head at step $i$ on a input of length $n$. Hence can write this formula for correctness between two adjacent configurations. So I guess you should be asking for a better simulation of oblivious Turing machines which beats $O(m \log m)$. It is already asked here : Oblivious Turing Machine emulation lowerbound.


Complexity of constructing minimum depth decision trees I am interested in the computational complexity of

Problem 1: Given a finite, non-empty set $J$, given $A, B \subseteq \{0,1\}^J$ such that $A \cap B = \emptyset$, and given $n \in \mathbb{N}$, does there exist a binary decision tree of depth at most $n$ with decisions $x_j \overset{?}{=} 1$ for any $x \in \{0,1\}^J$ and any $j \in J$ such that, at any leaf of the tree, there are only elements of $A$ or only elements of $B$?

I often see claims of Problem 1 being NP-complete due to a famous reduction of 3-dimensional perfect matching, via exact cover by 3-sets, by Hyafil and Rivest (1976). My understanding, however, is that they establish NP-completeness of the slightly different

Problem 2: Given a finite, non-empty set $J$, given $A \subseteq \{0,1\}^J$ and given $n \in \mathbb{N}$, does there exist a binary decision tree of depth at most $n$ with decisions $x_j \overset{?}{=} 1$ for any $x \in \{0,1\}^J$ and any $j \in J$ such that, at any leaf of the tree, there is at most one element of $A$?

Can anyone help me fill the gap or point me to other work establishing complexity results for Problem 1?

Remark: While Hyafil and Rivest (1976) establish a result for an average depth, their argument is easily adapted to the minimum depth.

One further remark (risking to make the question seem less relevant to some):
Consider the following generalization of Problem 1 that specializes to the latter for $m = 2$.

Problem 3: Given a finite, non-empty set $J$, given $m \in \mathbb{N}$, given pairwise disjoint $A_1, \ldots, A_m \subseteq \{0,1\}^J$, and given $n \in \mathbb{N}$, does there exist a binary decision tree of depth at most $n$ with decisions $x_j \overset{?}{=} 1$ for any $x \in \{0,1\}^J$ and any $j \in J$ such that, at any leaf of the tree, there are elements of at most one of the sets $A_1, \ldots, A_m$?

Problem 2 is polynomially reducible to Problem 3, for instance, by defining for each $a \in A$ of Problem 1 a separate subset $A_a = \{a\}$ of Problem 3. This reduction requires, however, that we can choose $m = |A|$. It is not generally possible in the special case of Problem 3 where $m = 2$, which is Problem 1.

At the same time, reducibility of Problem 2 to Problem 3 is sufficient for  many informal claims, e.g., of exact learning of binary classification trees from examples being NP-hard due to Hyafil and Rivest (1976), or of extending partial pseudo-Boolean functions by minimum depth decision trees being NP-hard due to Hyafil and Rivest (1976).
I just do not see how this holds for two-class classification and Boolean functions, respectively.

I think I can see a fairly easy reduction from 3DM. Let $B=\{0^J\}$, i.e., it is a singleton set with the only zero element. The points of $A$ correspond to the points of the 3DM that are to be matched. If a triple is matchable, then there is a coordinate where these 3 points are 1, while all other points are 0. The equivalence is straightforward.

I think an interesting question left open is if A is given (as part of the input), and our goal is to separate it from $\{0,1\}^J\setminus A$.


Two papers give contradictory bounds on linear probing. How do I resolve the disparity? I've been reading over two papers recently. The first, "Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream" proves that, assuming there is sufficient entropy in a data source, weak hash functions end up producing distributions very close to truly uniformly random distributions. The other paper, "On the $k$-Independence Required for Linear Probing and Minwise Independence" gives strong lower bounds on the expected cost of linear probing lookups assuming different strengths of hash functions.

I'm having trouble reconciling the results of these two papers. The first paper proves that using 2-wise independent hash functions, if the entropy of the data source generating the elements of a linear probing hash table is sufficiently high, then the expected cost of a lookup is O(1) (and, more strongly, is equal to the bound assuming totally uniform hashing plus an o(1) term). On the other hand, the second paper proves that there exists a family of 2-universal hash functions for which the expected cost of a lookup in a linear probing hash table is $\Theta(\sqrt n)$.

These statements seem at odds with one another. I suspect that there's some technical condition from one of the two papers that I'm missing that make these bounds not conflict.

How can both of these statements be true at the same time?

The first one is average-case analysis, for sets of keys that are already somewhat randomly distributed (chosen either before or after the choice of hash function but with a probability distribution that is independent of the hash function). The second one is worst-case analysis, for sets of keys that are not random but are instead specially chosen to make the algorithm look bad (chosen before the hash function's random seed is known, for a specific 2-independent hash function that is also chosen to make the rest of the algorithm look bad). So it shouldn't be surprising that with two different input models you get two different results.


Is it decidable to determine if a given shape can tile the plane? I know that it is undecidable to determine if a set of tiles can tile the plane,
a result of Berger using Wang tiles.
My question is whether it is also known to be undecidable to determine
if a single given tile can tile the plane, a monohedral tiling.

If this remains unsettled, I would be interested to know what is the minimum
cardinality of a set of tiles for which there is an undecidability proof.
(I have not yet accessed Berger's proof.)

According to the introduction of [1],

The complexity of determining if a single polyomino tiles the plane remains open [2,3], and
There is an undecidability proof for sets of 5 polyominoes [4].

[1] Stefan Langerman, Andrew Winslow. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino. ArXiv e-prints, 2015. arXiv:1507.02762 [cs.CG]

[2] C. Goodman-Strauss. Open questions in tiling. Online, published 2000.

[3] C. Goodman-Strauss. Can’t decide? undecide! Notices of the American
Mathematical Society, 57(3):343–356, 2010.

[4] N. Ollinger. Tiling the plane with a fixed number of polyominoes. In
A. H. Dediu, A. M. Ionescu, and C. Mart´ın-Vide, editors, LATA 2009,
volume 5457 of LNCS, pages 638–647. Springer, 2009.


Geometric picture behind quantum expanders (also asked here, no replies)

A $(d,\lambda)$-quantum expander is a distribution $\nu$ over the unitary group $\mathcal{U}(d)$ with the property that: a) $|\mathrm{supp} \ \nu| =d$, b) $\Vert \mathbb{E}_{U \sim \nu} U \otimes U^{\dagger} - \mathbb{E}_{U \sim \mu_H} U \otimes U^{\dagger}\Vert_{\infty} \leq \lambda$, where $\mu_H$ is the Haar measure. If instead of distributions over unitaries we consider distributions over permutation matrices, it's not difficult to see that we recover the usual definition of a $d$-regular expander graph. For more background, see e.g.: Efficient Quantum Tensor Product Expanders and k-designs by Harrow and Low.

My question is - do quantum expanders admit any kind of geometric interpretation similar to classical expanders (where spectral gap $\sim$ isoperimetry/expansion of the underlying graph)? I don't define "geometric realization" formally, but conceptually, one could hope that purely spectral criterion can be translated to some geometric picture (which, in the classical case, is the source of mathematical richness enjoyed by expanders; mathematical structure of quantum expanders seem to be much more limited).

[This answer was copied from my answer on the now-defunct theoreticalphysics stackexchange site.]
For classical expanders, the spectral definition can be expressed in terms of the second-smallest eigenvalue of the graph Laplacian, which can be thought of as the minimum of a quadratic form over all unit vectors orthogonal to the all-ones vector.  If we restrict this minimization to vectors of the form (a,a,...,a, b,b, ..b), then this yields the edge expansion of the graph.  here is a discussion.  The rough equivalence of these two definitions is known as Cheeger's inequality.

This suggests that for the quantum case we should consider the action of the channel (formed by applying a random unitary from the expander) on projectors.  A result analogous to Cheeger's inequality is derived in Appendix A of arXiv:0706.0556.

On the other hand, while this is mathematically analogous, we do still know of many fewer applications of quantum expanders than are known for classical expanders.


Generalized Geography on graphs of bounded treewidth Generalized Geography (GG) is played on a directed graph where a token is moved along arcs alternatively by two players. The vertices from which the token leaves are deleted. When a player cannot play anymore he loses (and his opponent wins).

GG is PSPACE-complete (see page 11, Figure 1 of "On the complexity of some two-person perfect-information games" of Schaefer) while its variant on undirected graphs is polynomial time solvable (see for instance here).
In the technical report Complexity of Path Forming Games of Hans L. Bodlaender (1989), it is shown that GG becomes polynomial time solvable in graphs of bounded treewidth.

I have two questions concerning that result:
1) Do you agree the algorithm is designed for undirected GG? (which is anyway in P for general graphs). Look at figure 4.1 for instance, plus the fact that the treewidth is not re-defined for directed graphs.
2) As mentioned by Saeed in a related post, "The problem is PSPACE-complete even on digraphs of directed tree width 1".
Now, even if we consider (directed) GG, and the treewidth of the undirected graph obtained by changing each arc into an edge, it seems to be untrue that GG is easier with bounded treewidth: take any instance of QBF with bounded pathwidth (which remains PSPACE-complete, result of Atserias and Oliva), number the variables by their order of appearance in bags going from "left to right", and do the reduction of Schaefer (see also the link given by Saeed). The treewidth of the undirected version of the digraph produced by this reduction is bounded. No?

In view of 1) and 2) why do we think that bounded treewidth makes GG easier?

The proof in my 1989 paper does not rely on the fact that the graph is undirected.

Directed treewidth is a different notion than the treewidth of the undirected graph obtained by changing each arc to an edge.


What are good conferences for algorithms about finite automata? I am writing a research paper, which describes some properties about finite automata. It also provides a couple of algorithms that can measure some aspects of the properties.

Could you point out some related conferences that this topic can well fit? And how good they are?

The main conferences where automata are among the main topics are ICALP, LICS, STACS, CSL, MFCS, FSTTCS.

If you feel your paper is not strong enough for these conferences (which accept about a quarter of the papers that are sent each year), you can send to conferences which are a little less exigeant.

The ICALP submission deadline is soon (in a week), after this the next in the list is FSTTCS I believe.

These conferences are all european (except FSTTCS from India), it seems that automata are less popular in USA, but it might be that your results interest some people at STOC or FOCS.


Textbook/resources for a beginning researcher in (Machine) Learning Theory I'm looking to begin understanding basic concepts, notions, results and definitions in the area of Computational Learning Theory (or the theory of Machine Learning), as is done in the theoretical computer science community (those represented mainly in STOC/FOCS). My goal is to do research in the area from the strictly theoretical perspective.

What kind of textbooks/resources, basic papers are available for me?
What kind of knowledge I need to have? Algorithms theory, or computational complexity theory? Or probability/probabilistic-methods (a la, Alon-Spencer)?

I have only seen a single textbook An Introduction to Computational Learning Theory by Michael Kearns and Umesh Virkumar Vazirani (1994), but I don't know if this is adequate/up to date.

So the question shortly is:
How can a researcher start obtaining knowledge in theoretical Machine Learning? (Note I'm not interested as of now in any form of applications of ML.)

People are going to recommend

http://www.cs.nyu.edu/~mohri/mlbook/

and

http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf

-- so I might as well do it first :)

I still think the Anthony-Bartlett is a better start for the mathematically oriented beginner.


question about concurrent ZK paper by Prabhakaran & Sahai Concurrent Zero Knowledge Proofs with Logarithmic
Round-Complexity

Page numbers are from the paper itself, and not the pdf.

From page 3,

  "An interactive proof system is said to be black-box (computational) zero

  knowledge if there is a probabilistic polynomial time oracle machine $S$ such that

  for any probabilistic polynomial time verifier $V^*$ and for all $\:x \in L\:$, the distribution

  of the output produced by $S^{V^*}$  on input $x$ is computationally indistinguishable

  from the view of the verifier at the end of the interaction $(P,V)(x)$."

I assume they mean $\:\left(P,V^*\right)(x)\:$ at the end, otherwise this

just defines Honest Verifier Computational Zero Knowledge.

From page 7,

  "If the simulator does not abort till all the sessions are over (or the

  verifier terminates), it outputs the view of the verifier at that point."

From the third paragraph on page 8,

  "If the depth counter indicates that we are just one level above the leaves, then the

  simulator has to wait for the next two preamble messages, i.e., it has to move through

  the two leaves, and then return. For this the simulator keeps modifying the current view

  by letting the (modified) prover and the verifier run, until two preamble messages arrive."

It seems to me like this can't work, since the prover's message

at that stage is just a statistically binding commitment.

Let $\: p: \omega \to \omega \:$ be a polynomial that bounds the number of oracle queries $S$ makes when $V^*$ only requests one proof. $\:$ Suppose the statistically binding commitment scheme being used

is such that it is easy to compute a predicate which commitments have a probability of approximately $\: \frac1{2\cdot p(k)} \:$ of satisfying (for example, Naor commitments or commitment from an injective pseudo-random generator). $\:$ Have the cheating verifier $V_1$ request only one proof and then behave like the honest verifier except that, at one level above the leaves, it will terminate

if the prover's commitment does not satisfy the predicate. $\;\;$ The probability of $\:\left(P,V_1\right)(x)\:$ succeeding is obviously approximately $\: \frac1{2\cdot p(k)} \:$, $\:$ whereas by the union bound, but by the

union bound and the independence of the simulator's, the probability that $S^{V_1}$ outputs a

succeeding view is not non-negligibly more than $\: \frac1{4\cdot p(k)} \:$. $\;\;$ This means that for sufficiently

large $k$, the probability of $\:\left(P,V_1\right)(x)\:$ succeeding will be more than $\: \frac1{5\cdot p(k)} \:$ greater than

the probability $S^{V_1}$ has of outputting a succeeding view. $\;\;$ That means the distribution

of $S^{V_1}$ is computationally distinguishable from the distribution of $\:\left(P,V_1\right)(x)\:$.

Is this an error in the paper? $\:$ If no, what am I missing?

I'm one of the authors. Someone pointed me to this question. Based on a quick reading, here's an attempt at answering your concern.

What may not be very clear from this version of the description of the simulator (this was the first time I was describing a simulator, and admittedly it reads a bit too much like machine language) is that the view output by the simulator, after all the pushing and popping of the stack, corresponds to only the traversal through edges labeled with L1 and R1. So even if the verifier aborts somewhere else, it just get popped off, and the simulator continues.

I'd recommend the FOCS proceedings version (or a slightly expanded version that is available from my homepage) over this e-print version. In terms of the description in the proceedings version, the simulator's output corresponds to the "main thread" of the simulation, and doesn't include any aborts that may happen in the look-ahead blocks. (Just looking at the paper: see Figure 3 for an illustration.)

Hope that helps.

-Manoj


Lower bounds for inversion counting in comparison model? For counting the number of inversions in an array, there are many $O(n \log n)$ algorithms, e.g. the one that modifies Merge Sort. There is an easy $\Omega(n)$ lower bound simply because you have to look at all the elements.

I saw some faster algorithms in the RAM model, such as this $O(n \sqrt{\log n})$ algorithm for a permutation on $n$ elements: http://people.csail.mit.edu/mip/papers/invs/paper.pdf.

Is anything else known in the comparison model for inversion counting? I'm mainly curious if there are better lower bounds.

I'm not totally sure, but it seems you can get $\Omega(n \log n)$ lower bound.

Suppose in the worst case we use $o(n \log n)$ queries. Consider a decision tree for our algorithm. Cause of depth of the tree there should be a leaf such that there are at least two permutations which correspond to it.

Now consider all queries with answers on a path from the root to the leaf. We know that they set a partial, not total, order. Consider two elements, which can not be compared. Take any permutation, which corresponds to this order, and swap these elements.

I don't have a strict proof, but it seems to be true, that after such a swap number of inversions should be changed. If so, we broke our algorithm and obtained lower bound.


Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices What is the complexity of the following problem?

Input:

$H$ a Hamiltonian path in $K_n$
$R \subseteq [n]^2$ a subset of pairs of vertices
a positive integer $k$

Query: is there a matching $M$ such that
for every $(v,u) \in R$, $d_G(v,u) \leq k$?
(where $G = ([n], M\cup H)$)

I have been having a discussion with a friend about this problem.
My friend thinks the problem is in polynomial time.
I think it is NP-complete.

This answer is incorrect.

Your friend is right. Your problem (as interpreted by Sasho) does not place any restriction on the cardinality of the matching $C$. Therefore, choose $C$ to be a matching between the pairs in $R$. Then for any positive integer $k$, the distance between every pair in $R$ is less than $k$.

Your problem becomes interesting if you force paths to contain edges from both the matching $C$ and the path $P$.


Question on cryptographic advantage In Provably Secure Steganography by Hopper, et al, we  have the following definition

Cryptographic notions

Let $F:\{0,1\}^k \times \{0,1\}^L \rightarrow \{0,1\}^l$ denote a family of functions. Let $A$ be an oracle probabilistic adversary:

Define the $prf$-advantage of $A$ over $F$ as

$$Adv^{prf}_F(A)= | Pr_{K \leftarrow U(k), r\leftarrow \{0,1\}^*}[A_r^{F_k(.)}=1]- Pr_{g \leftarrow U(L,l), r\leftarrow \{0,1\}^*}[A_r^{g}=1] |.$$

where $r$ is the string of random bits used by adversary $A$. Define the insecurity of $F$ as

$$InSec^{prf}_{F}(t,q) = max_{A\in \mathcal{A}(t,q)} \{ Adv_F^{prf}(A)\}$$

where $U(k)$ is a uniform distribution over $k$ bits, $U(L,l)$ is a uniform distribution on functions from $\{0,1\}^L$ to $\{0,1\}^l$, and $F_K$ is a function $F_K:\{0,1\}^k\times\{0,1\}^L\to\{0,1\}^\ell$. But honestly, I don't know how I'm supposed to understand or parse the definition. Intuitively, I get the adversary $A$ is outputting $1$ if it decides that $F_K$ is not sufficiently different from a sample $r$ drawn from the channel distribution. But can someone walk me through, like I'm an idiot, as to what role each part of the definition plays in the overall mechanism of prf-advantage?

Link to paper: https://www.cs.cmu.edu/~biglou/PSS.pdf

If you're totally lost, you might not have the needed background to get much use out of the paper.  The paper draws on many concepts and foundational ideas from theoretical cryptography (including how to formalize notions of security for various cryptographic tasks), and it assumes familiarity with those ideas.  If the definition looks confusing, it's probably because you don't have that familiarity; the paper's intended audience was cryptographers who already have that familiarity.

You might want to spend a few weeks studying theoretical cryptography (foundations of cryptography), e.g., from Lindell-Katz, the Goldreich book, and/or many lecture notes online on the foundations of cryptography.  You'll find that this kind of definition is routine, and studying that material will prepare you to be able to understand this material and work through the definitions on your own.


Resource listing models with known VC dimension Is there any reference resource gathering models with known VC dimension? I am looking for an exhaustive list of models with their VC dimension (and ideally the associated proof or a pointer to it).

It would be in the same spirit as the Complexity Zoo, which gathers most of the known complexity classes, or the textbook Computers and Intractability, which catalogues many NP-Complete problems.

Rather than computing the VC dimension of a particular function class, it's usually more interesting to understand how generic properties of a function class relate to its VC dimension. For example, function spaces with linear dimension $d$ have VC-dim at most $d$. You can also bound the VC-dim of a function class realized by circuits with bounded depth/fanin (Lemma 8.6 in Bartlett and Anthony, Neural Network Nearning) or the VC-dim of a neural network with a certain number of nodes (Thm. 3.6 in Kearns & Vazirani,  An Introduction to Computational Learning Theory.


Algorithms and computational complexity of clique and biclique covers I've been reading a paper by a mathematical chemist.  He proposes some indices to measure the complexity of molecules.  From here on in, instead of molecules, think undirected connected graphs: a vertex is an atom, and an edge is a bond between atoms.  It's possible to consider colorings of the vertices, to tell the Nitrogens apart from the Carbons, say, but I'll ignore that part for now.

The point: the indices he suggests are motivated by heuristics and experimental "looks good so far"-ness.  I think there must be some actual theory known about some of these quantities, and I'm hoping to get some pointers here.

Fix a graph $G$.  Let $C$ and $C'$ be two covers of $G$.  Say $C$ and $C'$ are the same kind of cover if they contain the same types of subgraphs in equal numbers.  (Note $C$ and $C'$ do not have to be isomorphic.)  Now we define the following quantities:

$k_S(G) =$ number of kinds of minimal edge clique covers of $G$
$k_T(G) =$ total number of minimal edge clique covers of $G$
$k^{bi}_S(G) =$ same as $k_S(G)$ but for bicliques
$k^{bi}_T(G) = $ same as $k_T(G)$ but for bicliques
$p_S(G) =$ number of kinds of partitions of the edges of $G$ into cliques
$p_T(G) =$ total number of partitions of the edges of the graph into cliques
$p^{bi}_S(G), p^{bi}_T(G)$ as above, but with partitions of $G$ into bicliques

Empirically, it is apparently easier to calculate the $p$ measures than it is to calculate the $k$ measures.  I expect something must be known somewhere about calculating some of these quantities.  Can anyone provide algorithms, computational hardness, etc.?  Thanks.

I am not sure if this is what you need.

Both Edge Clique cover and Edge Clique partition are in FPT, see

Data reduction and exact algorithms for clique cover

Parameterized complexity of the clique partition problem

Biclique cover is also studied and shown to be in FPT.


Why were Finite Automata and Turing Machines created? It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed independently of each other. So 'what' were the founding reasons of each of them? Why were they developed? What questions were each of the mathematical models aiming to answer?

I'm aware of TMs being created for answering the Entscheidungsproblem proposed by David Hilbert and it's leading to answer questions as to what is computable and what isn't. Then what about FAs? On another question an answer pointed me to a paper talking about nerve nets and Kleene's papers (both of which I hadn't read before. I didn't even know FAs were traced back to nerve nets.) So what was it that FAs were trying to answer at that time that wasn't answerable by TMs or was too cumbersome to do so? (I don't really know what nerve nets are and what FAs have to do with them. Perhaps the answer lies there?)

Reason for question: ToC is usually taught in a progression from D/N-FAs to PDAs to TMs but all of them were independently created, decades apart. The logical progression subconsciously implies a chronological sequence of 'discovery' but that isn't true and am trying to understanding their genesis better, out of curiosity. It'd be great to have the 'intentions/needs' of creating both of them in one place to better my understanding of the same. I'd also like to use this as a teaching aid if possible for the undergrads who fail to understand the essence of ToC

There are different questions being asked here. It is important to keep in mind that most courses on this topic are designed to clearly communicate and deepen a student's understanding of the concept of computation.

Historical motivation and precedence is not usually required to communicate the current understanding of the concepts or even their current relevance. Moreover, historical and philosophical issues are often subtle and doing them academic justice requires time and training that is not usually part of a computer science curriculum.

The creation of Turing Machines I think it is simplistic to believe that Turing Machines were created only to address the Entscheidungsproblem. The theory of computation was an idea whose time has arrived. There were several equivalent models of computation developed in that period with different motivation. The different models were not developed in isolation. Post developed a model of mechanical calculation in addition to more mathematical models of Church and Kleene. Electro-mechanical calculational devices were also in the background of such developments. Turing may have developed his model specifically motivated by a specific problem, but he did not work in a vacuum and his historical and intellectual context should not be discounted.
The creation of Finite Automata I would disagree that finite-automata were over two decades apart from the development of computational devices. McCulloch and Pitts proposed a model similar to finite automata while studying human cognition in the early 40s. The modern heritage of finite automata goes back to Rabin and Scott. Their paper is a model of clarity and is one search away. The first two words  "Turing machines" show that they were clearly aware of Turing machines.
The modern presentation of computability theory It is not true that the material we learn and teach about finite automata was developed independently of work on Turing machines. The material you are taught was developed in the awareness of results of Turing machines and the motivation for these results is clearly available in the work of Rabin and Scott.

I appreciate the desire to know about historical origins, but it is very important to appreciate that this is a nuanced topic and you cannot always find simple answers. Often, we do not even know when or why a concept was developed.

Regarding your last paragraph, the historical origins are, in my opinion, not a good source of motivation for or understanding about the essence of computation. In fact, they are a pretty bad source for undergrads. There are many contemporary essays, books, talks and the like about why computation is important, universal, beautiful, fascinating, and deep. That's where you should be looking. Here are a few random starting points in no particular order.

The Algorithm: Idiom of Modern Science
The emotion universe
The Computational Universe
Great Ideas in Theoretical Computer Science
The Computational Universe
Computers Ltd. What They Really Can't Do
The Unusual Effectiveness of Logic in Computer Science
And Logic Begat Computer Science: When Giants Roamed the Earth


Is there a name for this concept in Communication Complexity? Let Alice and Bob compute boolean function $f(x_1,\dots,x_{2n})$.

Select a random subset $\mathcal I\subseteq\{1,\dots,2n\}$ of cardinality $n$ and let $\mathcal J=\{1,\dots,2n\}\backslash\mathcal I$.

Let Alice get variables $x_i$ where $i\in\mathcal I$ and Bob get $x_j$ where $j\in\mathcal J$.

Let communication complexity of this function under this partition be $CC_{\mathcal I,\mathcal J}(f)$

Define $$cc_{min}(f)=\min_{\substack{\mathcal I\subseteq\{1,\dots,2n\}\\\mathcal J=\{1,\dots,2n\}\backslash\mathcal I\\|\mathcal I|=|\mathcal J|=n}}CC_{\mathcal I,\mathcal J}(f)$$
$$cc_{max}(f)=\max_{\substack{\mathcal I\subseteq\{1,\dots,2n\}\\\mathcal J=\{1,\dots,2n\}\backslash\mathcal I\\|\mathcal I|=|\mathcal J|=n}}CC_{\mathcal I,\mathcal J}(f)$$

Is there a term for $cc_{max}(f)-cc_{min}(f)$ and $\frac{cc_{max}(f)}{cc_{min}(f)}$?

Is the related concepts introduced and studied anywhere?

I am also interested in scenarios where $|\mathcal I|\neq\mathcal J|$ under condition $||\mathcal I|-\mathcal J||\leq \log n$.

What you call $cc_{max}$ is known as the worst-case partition communication complexity, and what you call $cc_{min}$ is known as the best-case partition communication complexity.
These have been studied for several functions, you can find some results in the book of Kushilevitz and Nisan in chapter 7.
I'm not aware of anyone introducing the difference or the ratio as a parameter to study.


Lower bound for finding repeated elements in sorted array This is inspired by [1] (which still needs answers).

  What is the tight lower bound (or optimal algorithms) for the "finding repeated elements" problem: Given a sorted integer array of size $n$, how to determine whether there exists some element which occurs more than $\lfloor n/k \rfloor$ times?

Note 1: The original problem [1] focuses on $k=2$, i.e., the "majority detection" problem. There is a simple $\Theta(\log n)$ algorithm for it: Only the median, called $m$, can be the majority. We can learn the length of the $m$ contiguous block using binary search.

  However, is $\Omega(\log n)$ a lower bound for $k = 2$?

Note 2: For unsorted array, [2] gives an optimal $O(n \log k)$ algorithm. The lower bound is proved using the decision-tree technique (section 5). I failed to extend it to the sorted case.

[1] Lower bound of finding majority element in an ordered array. @ cs.exchange

[2] Finding Repeated Elements by J. Misra and David Gries, TR, 1982.

Any algorithm would need $\Omega(\log n)$ queries.

To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. We assume that $x$ appears in $A[m],A[m+1],\dots,A[M]$, and that $k\triangleq\min\{a, m-1, n-M\}$.

Notice that in these notations we are looking to bound $f(\lfloor n/2 \rfloor)$.

Claim: $f(k)\ge \log k$.

Proof:

Consider the first query made by the algorithm.

If it was done within radius $k/2$ of the interval (i.e. somewhere in $[m-k/2,\ldots,M+k/2]$), and found the median at the spot, then we still need at least $f(k/2)$ queries to decide the problem.

If it was done outside that radius, consider the case where the queried cell did not contain the median. Once again, this leaves us with at least $f(k/2)$ queries to be made.

Continue with induction and you get the $\Omega(\log n)$ bound.


Adjacency-Preserving 2D Grid Embedding Consider a 2D grid, and a given planar graph $G$ with $\Delta<4$ (max node degree) and without odd cycles. What conditions should $G$ satisfy so that when it is mapped (or embedded) into the 2D grid, the adjacency of the nodes is maintained (i.e., all adjacent nodes in $G$ remain adjacent in the 2D grid). Accordingly, after embedding of $G$ in the 2D grid, the shortest path distance between adjacent nodes is still 1.

The alternative question is what is the condition for a given planar graph (with $\Delta<4$ and w/o odd cycles) to be a 2D grid?

Thanks!

Embedding planar graphs (with max degree four) in an adjacency-preserving way onto a grid is NP-complete, meaning that there's unlikely to be simple necessary and sufficient conditions. Actually that's still true even for embedding trees into a grid. See:

S. Bhatt and S. Cosmodakis. The complexity of minimizing wire lengths in VLSI layouts.
Inform. Proc. Lett. 25:263–267, 1987.


Modeling objects (OOP) in dependent type theory I am interested in modeling objects, from object oriented programming, in dependent type theory. As a possible application, I would like to have a model where I can describe different features of imperative programming languages.

I could only find one Paper on modeling objects in dependent type theory, which is:
Object-oriented programming in dependent type theory by A. Setzer (2006)

Are there further references on the topic that I missed and perhaps are there more recent ones?

Is there perhaps an implementation (i.e. proof) available for a theorem prover, like Coq or Agda?

Some early(?) work done in this area was by Bart Jacobs (Nijmegen) and Marieke Huisman. Their work is based on the PVS tool and relied on a coalgebraic encoding of classes (if I remember correctly). Look at Marieke's publication page for papers in the year 2000 and her PhD thesis in 2001. Also look at the papers by Bart Jacobs cited in the A Setzer paper you mention.

Back in those days, they had something called the LOOP tool, but it seems to have vanished from the internets.

There is a workshop series known as FTfJP (Formal Techniques for Java-like Programs) that addresses the formal verification of OO programs. Undoubtedly some of the work uses dependent type theory/higher-order logic. The workshop series has been running for some 14 years.


When have we found better bounds for known algorithms? Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - obviously that's happened! But better analysis leading to a better bound on an existing algorithm

I thought matrix multiplication was an example of this, but I have talked myself out of it (perhaps incorrectly!) after trying to understand Coppersmith–Winograd and its friends better.

The Union-Find algorithm, which Tarjan1 showed had complexity $n \alpha(n)$, where $\alpha(n)$ is the inverse Ackermann function, had been analyzed previously by several people. According to Wikipedia, it was invented by Galler and Fischer2, but this seems to be incorrect, as they did not have all the components of the algorithm needed to make it run that quickly.

Based on brief scans of the papers, it appears that the algorithm was invented by Hopcroft and Ullman3, who gave an (incorrect) $O(n)$ time bound. Fischer4 then found the mistake in the proof and gave an $O(n \log\log n)$ time bound. Next, Hopcroft and Ullman5 gave an $O(n \log
^*n)$ time bound, after which Tarjan1 found the (optimal) $O(n \alpha(n))$ time bound.

1 R.E. Tarjan, "Efficiency of a good but not linear set union algorithm" (1975).
2 B.S. Galler and M.J. Fischer, "An improved equivalence algorithm" (1964).
3 J.E. Hopcroft and J.D. Ullman, "A linear list merging algorithm" (1971).
4 M.J. Fischer, "Efficiency of equivalence algorithms" (1972).
5 J.E. Hopcroft and J.D. Ullman, "Set-merging algorithms" (1973).


Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete? Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3?

I know it is NP-complete for the class of planar graphs of maximum degree 3 (see the Garey and Johnson book), as well as for bipartite graphs of maximum degree 3 (see M. Chlebík and J. Chlebíková, "Approximation hardness of dominating set problems in bounded degree graphs"), but could not find the combination of the two in the literature.

What if you simply do the following: Given a graph $G = (V,E)$, construct another graph $G' = (V \cup U, E')$ by subdividing each edge of $G$ in 4 parts; here $U$ is the set of new nodes that we introduced, and $|U| = 3|E|$.

The graph $G'$ is bipartite. Moreover, if $G$ is planar and has max. degree 3, then $G'$ is also planar and has max. degree 3.

Let $D'$ be a (minimum) dominating set for $G'$. Consider an edge $(x,y) \in E$ that was subdivided to form a path $(x,a,b,c,y)$ in $G'$. Now clearly at least one of $a,b,c$ is in $D'$. Moreover, if we have more than one of $a,b,c$ in $D'$, we can modify $D'$ so that it remains a valid dominating set and its size does not increase. For example, if we have $a \in D'$ and $c \in D'$, we can equally well remove $c$ from $D'$ and add $y$ to $D'$. Hence w.l.o.g. we have $|D' \cap U| = |E|$.

Then consider $D = D' \cap V$. Assume that $x \in V$ and $x \notin D'$. Then we must have a node $a \in D'$ such that $(x,a) \in E'$. Hence there is an edge $(x,y) \in E$ such that we have a path $(x,a,b,c,y)$ in $G'$. Since $a,b,c \in U$ and $a \in D'$, we have $b, c \notin D'$, and to dominate $c$ we must have $y \in D'$. Hence in $G$ node $y$ is a neighbour of $x$ with $y \in D$. That is, $D$ is a dominating set for $G$.

Conversely, consider a (minimum) dominating set $D$ for $G$. Construct a dominating set $D'$ for $G'$ so that $|D'| = |D| + |E|$ as follows: For an edge $(x,y) \in E$ that was subdivided to form a path $(x,a,b,c,y)$ in $G'$, we add $a$ to $D'$ if $x \notin D$ and $y \in D$; we add $c$ to $D'$ if $x \in D$ and $y \notin D$; and otherwise we add $b$ to $D'$. Now it can be checked that $D'$ is a dominating set for $G'$: By construction, all nodes in $U$ are dominated. Now let $x \in V \setminus D'$. Then there is a $y \in V$ such that $(x,y) \in E$, and hence along the path $(x,a,b,c,y)$ we have $a \in D'$, which dominates $x$.

In summary, if $G$ has a dominating set of size $k$, then $G'$ has a dominating set of size at most $k + |E|$, and if $G'$ has a dominating set of size $k + |E|$, then $G$ has a dominating set of size at most $k$.

Edit: Added an illustration. Top: the original graph $G$; middle: graph $G'$ with a "normalised" dominating set; bottom: graph $G'$ with an arbitrary dominating set.


"The" category of Turing machines? Disclaimer: I know very little about complexity theory.

I'm sorry but there is really no way to ask this question without being (terribly) concise:

  What should be the morphisms in "the" category of Turing machines?

This is obviously subjective and depends upon one's interpretation of the theory, so an answer to this question should ideally give some evidence and reasoning supporting the answer as well.

I'd like to emphasis the point that i'm looking for a category of Turing machines and not of formal languages for example. In particular I think my morphisms should contain finer information then reductions or anything like that (I'm not sure though).

Of course if there's already a well known and used category in the literature i'd like to know what it is.

If your objects are Turing machines, there are several reasonable possibilities for morphisms. For example:

1) Consider Turing machines as the automata they are, and consider the usual morphisms of automata (maps between the alphabets and the states that are consistent with one another) which also either preserve the motions of the tape head(s), or exactly reverse them (e.g. whenever the source TM goes left, the target TM goes right and vice versa).

2a) Consider simulations or bisimulations.

2b) Along similar lines, you can consider when one TM can be transformed (by a computable function) to simulate the other one. This can be done at the level of step-wise behavior, or as Yuval suggested in the comments, at the level of input-output, that is, a morphism from $T_1$ to $T_2$ (or maybe the other way around) is a computable $f$ such that $T_1(x) = T_2(f(x))$ for all $x$.

3) Consider the transition graph of the Turing machine (each vertex is a complete description of the state of the machine and the tapes, with directed edges corresponding to the transitions the TM would make) and consider morphisms of graphs. For TMs this is a very coarse relationship, however, as it essentially ignores the local nature of computation (it ignores, for example, what the contents of the tapes are).

I think the real question is: what is it you want to know about TMs or to do with them? In the absence of this, it's hard to give arguments for any one definition over another, beyond naturality (in the usual sense of the word, not the categorical sense).


Physical realization of nonlinear operators for quantum computers. I have read in a paper where nonlinear operators for quantum computers implies the solving of problems in #P time. See http://arxiv.org/pdf/quant-ph/9801041 .
What would be the simplest realization of this? Could you limit its power to solve easy problems in #P Also is this equiavlent to $PostBQP$ or any other complexity class?

Short answer: if you believe quantum mechanics is an accurate description of nature, then since QM is a linear theory, it isn't possible to physically realize nonlinear operations.

As far as we know, the only nonlinear operation in quantum mechanics is that of measurement, but it's of a very restricted kind: measurement only happens at the end of your computation, and it doesn't allow you to amplify exponentially small amplitudes into non-trivial ones (except with negligible probability).

On the other hand, the kinds of nonlinearities discussed by the Abrams and Lloyd paper (as well as others) are generally those that allow you to take a quantum state with exponentially small amplitude, and amplify it to something nontrivial. We don't believe that it is possible to physically realize these nonlinear operations. Why? If it were possible, then you would be able to solve #P problems efficiently! From a complexity point of view, this consequence effectively chucks out the assumption. Being able to solve NP-complete problems efficiently is laughable; to handle #P with ease is a bad joke taken a little too far. The Abrams and Lloyd paper can be understood as an argument against the possibility of nonlinear quantum mechanics.

To try to answer the last part of your question: if there existed nonlinear quantum gates like described in the Abrams and Lloyd paper, then PostBQP could certainly be simulated by their nonlinear quantum computer (because PostBQP = PP by a result of Aaronson, and their nonlinear quantum computer can solve #P-complete problems efficiently).


Complexity theory when an oracle is part of the input The most common way in which oracles occur in complexity theory is as follows: A fixed oracle is made available to, say, a Turing machine with certain limited resources, and one studies how the oracle increases the computational power of the machine.

There is, however, another way in which oracles sometimes occur: as part of the input.  For example, suppose I want to study algorithms for computing the volume of a given high-dimensional polytope.  Classically, the polytope would need to be specified by providing a list of its facets or some other explicit representation.  However, we can also pose the problem of computing the volume of a polytope that is specified by a volume oracle, that takes the coordinates of a point in space as input and outputs "yes" if and only if the given point lies inside the polytope.  Then we can ask what computational resources are needed to compute the volume of a polytope that is specified in this manner.  In this particular case we have the very nice polynomial time approximation scheme of Dyer, Frieze, and Kannan and, interestingly from the complexity theory point of view, a proof that randomness helps in an essential way for this problem, in that no deterministic algorithm can perform as well as the Dyer-Frieze-Kannan algorithm.

Is there a systematic way to study the complexity theory of problems in which oracles are provided as part of the input?  Does it somehow reduce to the usual theory of complexity classes with oracles?  My guess is no, and that because there are too many different ways that an oracle could be supplied as part of the input, every problem of this sort has to be handled in an ad hoc manner.  However, I would be happy to be proved wrong on this point.

It's called Type-2 Complexity Theory. There's a paper by Cook, Impagliazzo and Yamakami that ties it nicely to the theory of generic oracles.


Finding outer face in plane graph (embedded planar graph) I have a planar graph, for which I have computed a combinatorial embedding and coordinates in the plane. So all my arcs are now oriented in the plane, respective to their end vertices.

Computing a list of all faces of the graph (as a list of oriented walks along their arcs) is fairly straightforward.

On the other hand, finding a simple way to pick the outer face out of the list of faces does not seem as easy: it is included in the list of faces, but since its orientation is "reversed" (i.e. relative to the outer region, rather than the inside of the graph boundary), all its properties in terms of neighbouring faces are identical to other faces.

Short of using plane coordinates to painstakingly identify the outer nodes/arcs of the graph, is there a more straightforward way to pick the outer face out of the list of faces using the combinatorial embedding (given as a table of arc successors in the oriented plane)?

Edit: Upon reading the comments, I realised that my wording was ambiguous (verging on the incorrect): while I have the combinatorial embedding and would like to use it (or the information derived from it), I also have coordinates derived from a drawing of that graph (hence the plane graph, not simply planar graph), ensuring that there is, indeed, a specific outer face.

What I meant to say is that I am looking for a method that would do more (or rather: less) than just looking at the coordinates of all faces and (for example), compute their orientation.

To be precise, the embedding and plane drawing give me:

a list of all faces (as an oriented walk of vertices).
for each arc: the face left and right of it.
for each vertex: an oriented walk of its ingoing/outgoing arcs (actually, my graph of interest is undirected, but that is probably not very relevant).

Edit 2: Despite the upvotes, the first comment does not really solve much (it essentially boils down to a recursive answer: "in order to find the outer face, use the leftmost vertex, then find the outer face", which isn't as trivial to solve as its commenter seemed to think.

@Zsbán provided what looks like the most efficient and elegant solution. Thanks!

First, suppose that your arcs are embedded to the plane as straight lines.  Then, the following three step algorithm works.

First, compute the leftmost vertex (as David Eppstein suggested).  This vertex will be on the unbounded face.

Second, among the arcs from that vertex, find the one whose slope is largest. This arc will be a side of the unbounded face.  (You must consider the slope; taking the arc with the leftmost destination vertex wouldn't work.  You may have to handle the case when this vertex is isolated somehow.)

Thirdly, take the face on the left hand side of this arc.  That face is the outer face.

If the edges aren't embedded as straight lines, then you need some extra information about the embedding.  Indeed, in any plane graph (with at least one cycle), you could just take an edge of the outer face and lift it around the whole embedding.  This changes the outer face, but doesn't move the vertexes, and doesn't change the cyclical orientation of arcs from the vertexes.

In particular, if the edges are open polygons given with the coordinates of the list of inner vertexes, then divide each such edge to a path and run the previous algorithm in the subdivided graph.  This may choose such an internal vertex in the first step.