Partitioning graphs while minimizing inter-partition edges I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been partitioned into 4 "clusters":

What I wanted originally was an algorithm that could create partitions of approximately k triangles (there could be some error as long it wasn't too large), and I managed to figure out a $O(k^2p^2(v+e))$ algorithm (where p is the total number of partitions) that could find such a partitioning. I then realized that having large numbers of inter-partition edges were detrimental for the application I needed this algorithm for.

Ideally, I'd like an algorithm that can keep each partition within some range of $k$, ideally have it be a constant factor like 2. Also, I'd like to be able to make the number of inter-edges have an upper bound that is "low".

Additionally, another problem I have is if I have a partition that has these properties, and I modify the graph by doing one of the following:

Adding a set of edges connecting to existing vertices
Adding a vertex and a set of edges connecting to the added vertex
Removing a set of edges
Removing a vertex and all edges that connect to this vertex

I want to be able to repartition the graph and still have each partition with size $k$ and number of cut edges minimized. (This is the solution I'm putting up a bounty for). This means that using this algorithm, we can construct any partition by starting with an empty graph and adding vertices and edges one by one and repartitioning.

Here's some additional constraints to the problem:

The graph is planar
Each "triangle" is a vertex that has undirected edges to triangles it shares an edge with
From the above statement, it is obvious that each vertex in this graph has degree at most 3
The graph is connected
Each subgraph from the partition is connected
Each subgraph has approximately k vertices
There are at most $\sqrt n$ inter-partition edges (edges that contain a vertices from different partitions). If you can find a similar bound for inter-partition edges like $2\sqrt n$ or $O(\log n)$ then that could work too. I'm not entirely sure the upper bound for inter-partition edges can be less than $O(n)$ so if you can prove that its impossible to do better, that is satisfying as well.

I'm at a point where I'm stuck, so any help with this problem would be lovely. If you can flat out solve this problem, you're the bees knees. Otherwise, if you know of any papers or textbooks or algorithms you could point me to, I'd appreciate it very much.

Let me know if I need to clarify anything!

EDIT: Here are some additional constraints if it makes the problem easier.

We are dealing with constrained delaunay triangulations
Constraints will NEVER be a single vertex
The graph created from the triangulation is constructed as follows: each triangle is represented as a vertex. Each edge in the graph corresponds to an unconstrained edge in the triangulation. This means that a constrained edge between two triangles will not show up in the graph representation of the triangulation.

Another thing I realized is that we may need to modify $k$ to grow as $n$ grows, otherwise there can be no sub $O(n)$ guarantees on the number of inter-partition edges.

Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time seems possible. Recursive bisection, while not ideal, might be a feasible approach for your problem.

Satish Rao. Finding near optimal separators in planar graphs. In 28th Symposium on Foundations of Computer Science (FOCS), pages 225-237, 1987.

Satish Rao. Faster algorithms for finding small edge cuts in planar graphs (extended abstract). In 24th ACM Symposium on Theory of Computing (STOC), pages 229-240, 1992.

Horst D. Simon and Shang-Hua Teng. How Good is Recursive Bisection?
In  SIAM Journal on Scientific Computing, Volume 18, Issue 5, pages 1436-1445, 1997.

did some search on this but held off on posting immed to see what other answers would materialize & am now posting this to not throw away some misc ideas/leads which could have some value (although the question author has already indicated hes now found an acceptable answer).

on inspection there are many constraints given on this problem and it could conceivably take an entire paper to create an algorithm & prove that it satisfies all them (which of course is generally outside the scope of stackexchange format). nevertheless there are a few basic approaches to take on this type of problem

empirical. generate random graphs that fit the constraints or use graphs from some dataset that match the conditions and try different algorithms on them, and look at performance. one may find that an algorithm empirically satisfies the conditions reqd. if one is more strict, one could attempt to create a proof out of the empirical observation if its 100% satisfied by large datasets. also for empirical research it often helps to know how the datasets are obtained/generated, what their nature/origination is.
the question has no related citations of literature/refs. so what are the nearest types of algorithms in the literature? for this type of problem multiple types of research areas might overlap. there is research on planar graphs, graph partitions, graph cuts, graph separators, partitioning triangular graphs, etc.; its not obvious to figure out the main theme of this question so far as its formulated or which particular (graph algorithm) research sub-area would most directly impinge on it.

given those qualifications a basic theme of the question seems to be "partitioning planar graphs". here are some leading recent refs on that topic which might be helpful & show additional themes/angles of current related research. there are some algorithms implemented & they may be available on request from the authors.

the 3rd involves partitioning with weights, which will generalize to equal weights, but which gives an additional framework for consideration/investigation: could all the question conditions be fulfilled by some kind of weight assignment scheme? (this could also tie in with the requirement to have some kind of dynamic control or adjustment over solutions also referred to in the question.)

Spectral partitioning works: Planar graphs and finite element meshes Spielman/Teng
Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases Wada, Chen
Partitioning planar graphs with costs and weights Aleksandrov et al


What is the importance of a TCS researcher in a mostly applied CS department? Stating the title in another way, how to convince a strong applied CS department that a theorist would be a better choice than one more applied computer scientist?

I understand that it is natural for a applied department to want one more expert on a specific field. On the other hand, diversity is important and I think the importance of a theorist goes beyond better theory courses.

What is the importance of a TCS researcher in a mostly applied CS department?

I am really not qualified to give an informed answer to your question, but there are many reasons for which a theory-oriented researcher might be a good fit for a more applied environment.

The main reason that comes to mind is this: good theoretic foundations are invaluable for a thorough understanding of an application which in turn increases trust, efficiency and decreases mental effort. In general it allows work to proceed much faster, as the foundations provide a mental reference that can be easily extended or made explicit.

I'm sure there are many examples in complexity theory, where an abstract approach has led to fantastic practical improvements in concrete implementations, but the field I am the most familiar with is "theory B", in which programing language design has greatly benefited from advances in pure computing theory research.

Haskell is a particularly good example. On the theory side, we have simple core languages like system $\mathrm{F}_\omega$ which have proven to be a very useful base for the core language of the GHC compiler. The research in type inference/reconstruction and more recently, on dependent types has guided the foundations of the Haskell design, including the Hindley-Milner architecture and GADTs. Monads, of course, were introduced in the from the most abstract domain of mathematics to the computing world by Moggi, a theorist.

More pragmatically, knowledge of the theory of operational semantics turns out to be an invaluable tool for language extensions: the paper which introduces Software Transactional Memory in Haskell has explicit operational semantics for the small sub-language containing the STM constructs. This creates a reference for the implementation, and the ability to prove properties about a correct implementation, creating trust and understanding.

All this point to the fact that having a strong theory background is an important asset of every research team, including those with a strong application theme.

heres another angle on this. the question starts out with an a priori "hard sell" situation/case ie a dept that is mostly applied is already going to have an inherent bias against a more theoretical researcher, otherwise that researcher would already be in the dept.

one possible direction "in" is the following. an often overlooked area of software development/design in industry and sometimes computer science departments is architecture. sometimes even TCS does not have large awareness of architecture either, but it is better positioned to recognize it than with applied focus.

in a few words, software architecture is the study of complexity in the solution/software, and ways of minimizing it, which is a major issue esp. with large software projects, which these days are increasingly more common.

software architecture involves in part the choice of algorithms (ie choice among equivalent algorithms, in terms of input/output relationship, based on different performance and scalability characteristics). sometimes applied workers are not even familiar with the basic theory that tells you stuff like an indexed column on a database is $O(log(n))$ access time instead of $O(n)$ and why this is in fact a "big deal". architecture is also tied with very practical topics like when refactoring of code is appropriate or not.

also it seems like some complex commercial software has many dimensions of scalability. in robotics an analogous concept is "degrees of freedom". the software scales in many separate dimensions. for example, memory size, size of web pages, size of database results, etcetera. a good theoretical researcher will be able to more systematically/scientifically assist in identifying and quantifying all these dimensions, ie using the scientific method. more applied workers will tend to just resort to trial and error, sometimes over a period of years, never really understanding exactly why their software is underperforming, hitting internal ceilings, or failing.

there are a few rare researchers who can cross between theory and applied realms without difficulty, or as the vernacular goes, "feet in both worlds". maybe studying them in particular (their career directions and writing, etc) will help to develop the mindset and philosophy to "cross over". in particular, Grady Booch is one eminent figure who comes to mind. he invented much of the concepts behind OOP programming and has much excellent research/writing on the topic of software architecture. another similar researcher is Phillip Kruchten. and yes [as in comments], Peter Shor.

having worked with both, one possible distinction is that in a more applied setting the main deliverable is code and in a more theoretical setting the "deliverables" are analyses/paper(s). this can cause a cultural gap if not everyone is "on the same page" with what are the deliverables. in this case the theoretical scientist will be the one who will have to bend & be more flexible and also "be ok" with that. so the personality of this key person will be a key factor.

another emerging/very prominent area these days that has strong interdisciplinary connection/overlap between theoretical and applied scientists is datamining, reaching larger prominence with official government/corporate initiatives into big data (and again architecture is a foremost element in this).


Characterization of read-once formulae over the full binary basis Background

A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis (which has the 2-bit gates AND and OR, and the 1-bit gate NOT) and the full binary basis (which has all 2-bit gates).

So for example, the AND of 2 bits can be written as a read-once formula over either basis, but the parity of 2 bits cannot be written as a read-once formula over the De Morgan basis.

The set of all functions that can be written as a read-once formula over the De Morgan basis has a combinatorial characterization. See, for example, Combinatorial characterization of read-once formulae by M. Karchmer , N. Linial , I. Newman , M. Saks , A. Wigderson.

Question

Is there an alternate characterization of the set of functions that can be computed by a read-once formula over the full binary basis?

Easier Question (added in v2)

While I'm still interested in an answer to the original question, since I haven't received any answers I thought I'll ask an easier question: What are some lower bound techniques that work for formulae over the full binary basis? (Other than the ones I list below.)

Note that now I'm trying to lower bound the formula size (= number of leaves). For read-once formulae, we have formula size = number of inputs. So if you can prove that a function needs a formula of size strictly greater than n, then that also means it cannot be represented as a read-once formula.

I'm aware of the following techniques (along with a reference for each technique from Boolean Function Complexity: Advances and Frontiers by Stasys Jukna):

Nechiporuk's method for universal functions (Sec 6.2): Shows an $n^{2-o(1)}$ size lower bound for a certain function. This doesn't help you find lower bounds for a particular function that you might be interested in though.
Nechiporuk's theorem using subfunctions (Sec 6.5): This is a proper lower bound technique in the sense that it will provide a lower bound for any function you're interested in. For example it shows that any formula over the full binary basis that represents the element distinctness function has size $\Omega(n^2/\log n)$. (And this is the largest lower bound the technique can prove — for any function.)

there is also a method called the Krapchenko lower bound "which can be slightly larger than Nechiporuks method". see John E Savage, Models of Computation, section 9.4.2. (which is covered right after the Nechiporuk method in section 9.4.1)


Almost universal string hashing in $Z_{2^n}$ and sublinear space Here are two families of hash functions on strings $\vec{x} = \langle x_0 x_1 x_2 \dots x_m \rangle$:

For $p$ prime and $x_i \in \mathbb{Z_p}$, $h^1_{a}(\vec{x}) = \sum a^i x_i \bmod p$ for $a \in \mathbb{Z}_p$. Dietzfelbinger et al. showed in "Polynomial Hash Functions Are Reliable" that $\forall x \neq y, P_a(h^1_a(x) = h^1_a(y)) \leq m/p$.
For $x_i \in \mathbb{Z}_{2^b}$, $h^2_{\vec{a} = \langle a_0 a_1 a_2 \dots a_{m+1}\rangle}(\vec{x}) = (a_0 + \sum a_{i+1} x_i \bmod 2^{2b}) \div 2^b$ for $a_i \in \mathbb{Z}_{2^{2b}}$. Lemire and Kaser showed in "Strongly universal string hashing is fast" that this family is 2-independent. This implies that $\forall x \neq y, P_\vec{a}(h^2_\vec{a}(x) = h^2_\vec{a}(y)) = 2^{-b}$

$h^1$ uses only $\lg p$ bits of space and bits of randomness, while $h^2$ uses $2 b m + 2 b$ bits of space and bits of randomness. On the other hand, $h^2$ operates over $\mathbb{Z}_{2^{2b}}$, which is fast on actual computers.

I'd like to know what other hash families are almost-universal (like $h^1$), but operate over $\mathbb{Z}_{2^b}$ (like $h^2$), and use $o(m)$ space and randomness.

Does such a hash family exist? Can its members be evaluated in $O(m)$ time?

Yes. Wegman and Carter's "New hash functions and their use in authentication and set equality" (mirror) shows a scheme meeting the requirements stated (almost universal, over $\mathbb{Z}_{2^b}$, sublinear space and randomness, linear evaluation time) based on a small number of hash functions drawn from a strongly universal family.

This is sometimes called "tree hashing", and it is used in "Badger - A Fast and Provably Secure MAC" by Boesgaard et al.

If you want something fast and that you can use in practice, you might look at the cryptographic literature.  For instance, poly1305 and UMAC are fast, and there are many others.  Because 2-universal hashes are useful for cryptography, cryptographers have studied many constructions and found ones that are extremely efficient.

Poly1305 works like your first type of hash (called a polynomial evaluation hash), working modulo $2^{130}-5$.  The scheme shows clever tricks to make this run very fast on a modern computer.  The amount of randomness is small: 128 bits.

If you want to reduce the amount of randomness and don't care so much about practicality, you might look at the following research paper:

LFSR-based Hashing and Authentication. Hugo Krawczyk. CRYPTO 1994.

Krawczyk describes a scheme to reduce the amount of randomness basically by letting $a_i$ be the $i$th row of a Toeplitz matrix.  However, the Krawczyk scheme works over $GF(2^b)$, not arithmetic modulo $2^b$.


Is there a geometrical picture for adiabatic quantum computation? In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily coolable initial (ground) state with Hamiltonian $H_i$ and "anneal" (adiabatically perturb) towards $H_p$, i.e.

$$
H(s) = s H_i + (1-s) H_p
$$

where $s \in [0,1]$. Details about AQC: http://arxiv.org/abs/quant-ph/0001106v1

The interesting thing about this problem is to try to understand the gap between the ground state eigenvalue and the first excited state, as this determines the problem complexity. One interesting thing to do would be to try and say something about the behavior of certain types of Hamiltonians. One can analyze the energy spectrum of small qubit cases by simulation to understand the problem complexity, but this becomes infeasible very quickly.

What I'd like to know is if there is a geometrical or topological way of looking at how certain Hamiltonians behave. Someone mentioned that the above form could be looked at as a homotopy (if the scalar functions were generalized to operators), but I'm not well-versed in higher level mathematics so I'm not sure what this implies or what I could do with it.

It might help to mention that the Hamiltonians are usually Ising spin-glass Hamiltonians (at least, that is what $H_p$ is). I'm not well-read on advanced statistical mechanics literature either, so this may be another avenue.

I wondered if anyone could provide some explanation on this, or at least provide some interesting references, keywords, etc.

a very challenging/advanced/provocative question; following, a brief/sketchy/tentative answer [maybe/hopefully better than none] considering geometry in QM computing in general & a few refs/leads. geometry is used in a variety of ways in QM in general, and it appears to be somewhat of an open question and challenging work-in-progress how to determine a coherent/natural "geometric picture" for QM, and there apparently are multiple ways to do it, and currently no generally-agreed, unified or standard approach. also, some directions can be highly abstract reflecting the direction of mathematical research developed largely independently of physics.

the 2-qubit state has been more extensively studied and there is more chance of creating a picture there 1st and maybe using it as a somewhat "toy" area that can be expanded later. (note that adiabatic QM computing is still based on qubits.) also there is a relatively new study of "quantum dischord" which is seen as promising by some (but also controversial) & might be part of the answer as in the following ref.

the Bloch sphere is a clear geometric picture for a single qubit and has some generalization for pure states.
Geometric picture of quantum discord for two-qubit quantum states Shi, Jiang, Sun, Du
Geometry of Discrete Quantum Computing Hanson, Ortiz, Sabry, Tai
Quantum computing: The power of discord Merali/Nature


What is the difference between propositions and judgments? I get confused by the subtle difference between propositions and judgments when exposed to intuitionistic type theory. Can any one explain to me what is the point to distinguish them and what distinguishes them? Especially in view of the Curry-Howard Isomorphsim.

First, you should know that, in general, there is not consensus about these terms and their definitions depend on the system in which one is working.Since you asked about intuitionist type theory, I'll quote Pfenning:

  A judgment is something we may know, that is, an object of knowledge. A judgment is evident if we in fact know it.

Propositions on the other hand, according to Martin-Löf are sets of proofs. In this interpretation, if the set of proofs for a proposition is empty then it is false and otherwise true.

  A proposition is interpreted as a set whose elements represent the proofs of the proposition

says Nordström et al.  On the other hand, in classical logic and in general, propositions are objects expressed in a language which can be either "true" or "false".

To give you some extra intuition; from my point of view, judgments are metalogical and propositions logical.

I suggest "Constructive Logic" by Frank Pfenning, "Proofs and Types" by Jean-Yves Girard and "Programming in Martin-Löf's Type Theory" by Bengt Nordström et al. All three are freely available on the Internet. The last one is probably the closest to what you want as it is oriented to programming and goes into great detail, at length, about the meanings of these terms and many more.

Claims, propositions and statements are all the same; but a jugement is a proposition that has been verified (whether right or wrong), endorsed, or used as a conclusion. No need for fancy formulas like the answers above seem to abuse...


Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes? Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart.

For example, suppose a problem has a practical size* of $n = 100$ and there are two known algorithms: One is $2^n$ and the other is $n^c$ for some constant $c$. Clearly for any $c > 15$, the exponential algorithm is preferred.

*I guess practical size would mean something commonly found in the real world. Like the number of trains on a network.

How bout the simplex algorithm for linear programming?
In many occasions it is used in practice.
Edited to add:
I think it's more of a "worse-case exponential algorithm" which runs efficiently on practical instances/distributions rather than runs faster on practical sized adversarial instances.

There are some examples with (nonprobabilistic/ exact) primality detection/ testing. The AKS algorithm was the first algorithm for primality testing shown to be in P. It does not compete favorably versus some exponential time algorithms for "small" inputs. The details are somewhat tricky because showing this generally requires actually implementing the algorithms which is a challenging exercise and can depend on implementation-specific aspects.

More info/details/refs on this cs.se question:

When is the AKS primality test actually faster than other tests?


Efficient algorithm for testing planarity of the union of two planar graphs Let $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ both be planar graphs.

Is there an efficient algorithm to check whether the union $G = (V,E_1\cup E_2)$ is planar?
That is, an algorithm more efficient than the obvious one of running the standard linear planarity test on the union.

You might be interested in an online algorithm, which is one that processes the input in a serial manner. Here is a paper with fast algorithms that tests planarity after adding an edge or a vertex, and does so much faster than $O(m+n)$ time (it does so in $O(\log{n})$):

http://epubs.siam.org/doi/abs/10.1137/S0097539794280736?journalCode=smjcat

You will be interested in the edge-addition version of this. And you could ask your question with any two edge sets, but since you seem to have info that both $G_1$ and $G_2$ are planar, you can start with the one which is larger, knowing it is planar, then add edges from the other graph one at a time.

In a 'worst case' where $|E_1| = |E_2| = m$, you would have to decide when this $\frac{m}{2}O(\log{n})$ is better or worse than just applying a $O(m+n)$ planarity test.

There are a number of ambiguities in your question.  If you are given both $G_1$ and $G_2$ offline, then from a big-$O$ perspective, the problem is $\Theta(n_1+m_1 + n_2+m_2)$. If one or both are given online, then you should follow what Jim said.  It sounds like your measure of efficiency is a practical one, in which case you're better off using industrial software to run the obvious approach.


Diameter of a graph with O(|V|) edges What's the minimum diameter of a connected undirected graph with |V| vertices and O(|V|) edges?

A line graph has O(V) edges and diameter V-1. A star graph also has O(V) edges and diameter 2. So it seems that the constraint that a graph has O(V) edges places almost no restriction at all on what the diameter can be.

Of course, 2 is the minimum, since only a complete graph has diameter 1.

In general I would say the biggest lower bound is 1, as the graph

a---b

has diameter 1 and has |V|/2 = O(|V|) edges.

The same holds for

a---b---c
+-------+

and

    +-------+
a---b---c---d
+-------+

which have exactly |V|, and |V|+1 = O(|V|) edges, respectively.

This works for an arbitrary number of graphs, as long as you fix the number of nodes.

If you restrict the number of edges not to O(|V|) but to |V|, you get a biggest lower bound of 2 for graphs of at least 4 nodes.

EDIT

Since the first and second example have diameter 1 with $|E| \leq |V|$ (so, clearly $|E| \in O(|V|)$) the statement that each such graph has at least diameter 2 does not hold.


Matrix rigidity and uses of matrices with low rigidity Roughly a matrix of rank $n$ is said to be rigid, if to bring its rank down to $\frac{n}{2}$, one has to change at least $n^{1+\epsilon}$ of its entries, for some $\epsilon > 0$.

If an $n \times n$ matrix $A$ is rigid, then the smallest straight line program computing $Ax$  ($x$ is a vector of size $n$) is either super-linear size, or has super logarithmic depth.

Is there a converse to the above statement?

In other words are there uses to non-trivial and non-obvious low rigidity matrices of full rank in TCS?

Is there a notion of rigidity for matrices with lower ranks (say $\frac{n}{c}$ for some constant $c$)?

lacking further clarification of the question, heres a try/sketch of an answer. matrix rigidity has deep connections to fundamental questions in TCS/complexity theory including circuit lower bounds,[1] and thereby complexity class separations, and coding theory[2] as well as other areas. [5] is a nice slide survey.

the terms "low" and "high" in reference to rigidty of matrices are used informally and not in a precisely defined technical sense. [although Friedman did define "strong" rigidity. [6]] random matrices are known to have high rigidity but basically, its ~a 3.5 decades old open problem in this area to explicitly construct any matrix with "significantly high" rigidity.

the question doesnt further define/clarify the subjective terms "nontrivial" or "nonobvious" & will take some freedom there.

in this area there is a line of research looking at the rigidity of Hadamard matrices which have misc uses/applications in coding theory & elsewhere.

it seems fair to say a provably high rigidity result would surpass the threshhold of leading at least to "new nontrivial corollaries in complexity theory" but the best known bounds on Hadamard matrices do not suffice.[3] but neither does this conclusively prove they have limited "low" rigidity. its basically the same story with Vandermonde matrices [also applications in coding theory] considered by Lokam.[4]

so to summarize about all that can be said is that "weak lower rigidity bounds" have been proven on some matrices including Hadamard/Vandermonde matrices.

there also do not appear to be any published numerical experiments, estimates, or algorithms in the area.

[1] Boolean Function Complexity by Stasys Jukna, 2011, sec 12.8 "rigid matrices require large circuits"

[2] On matrix rigidity and locally self-correctable codes Zeev Dvir

[3] Improved lower bounds on the ridigity of Hadamard matrices Kashin/Razborov

[4] On the Rigidity of Vandermonde Matrices Lokam

[5] Mahdi Cheraghchi matrix rigidity talk

[6] J. Friedman. A note on matrix rigidity. Combinatorica, 13(2);235-239, 1993


Type-based memory safety without manual memory manage or runtime garbage collection? Let's say we wanted a typeful, pure functional programming language, like Haskell or Idris, that is aimed at systems programming without garbage collection and has no runtime (or at least not more than the C and Rust "runtimes"). Something that can run, more or less, on bare metal.

What are some of the options for static memory safety that don't require manual memory management or runtime garbage collection, and how might the problem be solved using the type system of a pure functional similar to Haskell or Idris?

Roughly speaking, there are two main strategies for safe manual memory management.

The first approach is to use some substructural logic like linear logic to control resource usage. This idea has floated around basically since linear logic's inception, and basically works on the observation that by banning the structural rule of contraction, every variable is used at most once, and so there is no aliasing. As a result, the difference between in-place update and re-allocation is invisible to the program, and so you can implement your language with manual memory management.

This is what Rust does (it uses an affine type system). If you are interested in the theory of Rust-style languages, one of the best papers to read is Ahmed et al's L3: A Linear Language with Locations. As an aside, the LFPL calculus Damiano Mazza mentioned is also linear,  has a full language derived from it in the RAML language.

If you are interested in Idris-style verification, you should look at Xi et al's ATS language, which is a Rust/L3 style language with support for verification based on Haskell-style indexed types, only made proof-irrelevant and linear to give more control over performance.

An even more aggressively dependent approach is the F-star language developed at Microsoft Research, which is a full dependent type theory. This language has a monadic interface with pre- and post-conditions in the spirit of Nanevski et al's Hoare Type Theory (or even my own  Integrating Linear and Dependent Types), and has a defined subset which can be compiled to low-level C code -- in fact, they are shipping verified crypto code as part of Firefox already!

To be clear, neither  F-star nor HTT are linearly-typed languages, but the index language for their monads are usually based on Reynold and O'Hearn's separation logic, which is a substructural logic related to linear logic that has seen great success as the assertion language for Hoare logics for pointer programs.
The second approach is to simply specify what assembly (or whatever low level IR you want) does, and then use some form of linear or separation logic to reason about its behaviour in a proof assistant directly. Essentially, you can use the proof assistant or dependently-typed language as a very fancy macro assembler that only generates correct programs.

Jensen et al's High-level separation logic for low-level code is a particularly pure example of this -- it builds separation logic for x86 assembly! However, there are many projects in this vein, like the Verified Software Toolchain at Princeton and the CertiKOS project at Yale.

All of these approaches will "feel" like a bit like Rust, since tracking ownership by restricting the usage of variables is key to them all.

A trivial scheme for the "bare metal" systems is to simply disallow all runtime memory allocations. Remember, even the C malloc/free pair requires a runtime library. But even when all objects are defined at compile time, they can be defined in a typesafe way.

The chief problem here is the fiction of immutable values in pure functional languages, which are created while the program runs. Real hardware (and certainly bare metal systems) rely on mutable RAM, which is in limited supply. The runtime of a functional language implementation in practice dynamically allocates RAM as new "immutable" values are created, and garbage collects them when the "immutable" value is no longer needed.

And for most interesting problems, the lifetime of at least some values depends on runtime (user) input, so lifetimes can't be statically determined. But even if the lifetime doesn't depend on input, it can be highly non-trivial. Take the simple program repeatedly finding primes simply by checking every number in order, checking against all primes up to sqrt(N). Clearly this needs keeps the primes and can recycle the memory used for the non-primes.


Why can machine learning not recognize prime numbers? Say we have a vector representation of any integer of magnitude n, V_n

This vector is the input to a machine learning algorithm.

First question : For what type of representations is it possible to learn the primality/compositeness of n using a neural network or some other vector-to-bit ML mapping. This is purely theoretical -- the neural network could be possibly unbounded in size.

Let's ignore representations that are already related to primality testing such as : the null separated list of factors of n, or the existence of a compositeness witness such as in Miller Rabin. Let's instead focus on representations in different radices, or representations as coefficient vectors of (possibly multivariate) polynomials. Or other exotic ones as are posited.

Second question : for what, if any, types of ML algorithm will learning this be impossible regardless of the specifics of the representation vector? Again, let's leave out 'forbidden by triviality' representations of which examples are given above.

The output of the machine learning algorithm is a single bit, 0 for prime, 1 for composite.

The title of this question reflects my assessment that the consensus for question 1 is 'unknown' and the consensus for question 2 is 'probably most ML algorithms'. I'm asking this as I don't know any more than this and I am hoping someone can point the way.

The main motivation, if there is one, of this question is : is there an 'information theoretic' limit to the structure of the set of primes that can be captured in a neural network of a particular size? As I'm not expert in this kind of terminology let me rephrase this idea a few times and see if I get a Monte-Carlo approximation to the concept : what is the algorithmic complexity of the set of primes? Can the fact that the primes are Diophantine recursively enumerable (and can satisfy a particular large diophantine equation) be used to capture the same structure in a neural network with the inputs and outputs described above.

The question is, in my opinion, quite vague and involves some misunderstanding, so this answer attempts only to provide the right vocabulary and point you in the right direction.

There are two fields of computer science that directly study such problems. Inductive inference and computational learning theory. The two fields are very closely related and the distinction is a social and aesthetic one, rather than a formal one.

Fix a finite alphabet $A$ and the set of all languages $\mathcal{P}(A^*)$ consisting of finite-length words over $A$. This is everything you can express in terms of $A$. Now consider a family of languages $\mathcal{F} \subseteq \mathcal{P}(A^*)$. You can think of this as the concepts you are interested in. You often have to fix the family of concepts you care about because, as others have pointed out, the representation of the concept and presentation of data are extremely important.

Imagine a teacher who is going to teach you a concept. The teacher will choose one of the languages without your knowledge. The teacher will then present information to you about the language. There are many presentations. The simplest is to give you examples. A presentation of positive data is a function $f: \mathbb{N} \to A^*$ satisfying that

$$\bigcup_{i \in \mathbb{N}} f(i) = T, \text{ for some } T \text{ in } \mathcal{F}.$$

So, a presentation of positive data is an enumeration of the target concept, often with some additional fairness conditions thrown in. You can similarly ask for a presentation that labels words depending on whether they are in the language or not. Again, you can add additional conditions to ensure fairness and coverage of all words.

Suppose we have a family $Rep$ of representations of languages. That means every element $M$ of $Rep$ defines a language $L(M)$. Examples of representations are Boolean formulae, finite automata, regular expressions, systems of linear equations, domain specific programming languages, etc. Anything you want, really, except various condition are usually imposed to ensure the representation has basic tractability properties.

A passive learner is a function $p: \mathbb{N} \to Rep$ that makes a conjecture after seeing each word provided by the teacher. We may often require that the learner is consistent. Meaning, the language $L(p(i))$ should contain all the words $f(j)$ for $j \le i$. The learner stabilizes if the learner's guess for the target language does not change. Specifically, there should exist some index $k$ such that for all $j \ge k$, $L(p(j)) = L(p(j+1))$. The learner succeeds if the final language equals the target language.

Let me emphasise that this is only one specific formalisation of one specific learning model. But this is step zero before you can start asking and studying questions that you are interested in. The learning model can be enriched by allowing interaction between the learner and the teacher. Rather than arbitrary families of languages, we can consider very specific languages, or even specific representations (such as monotone Boolean functions). There is a difference between what you can learn in each model and the complexity of learning. Here is one example of a fundamental impossibility result.

  Gold [1967] No family of languages that contains all finite languages and at least one super-finite language is passively learnable from positive data alone.

One should be very very careful in interpreting this result. For example, Dana Angluin showed in the 80s that

  Angluin [1982] The class of $k$-reversible languages is passively learnable in the limit from positive data.

The class of $k$-reversible languages is infinite, contains super-finite languages, but interestingly, does not contain all finite languages. Now once you change the learning model, the fundamental results change.

  Angluin [1987] Regular languages are learnable from a teacher that answers equivalence queries and provides counterexamples. The algorithm is polynomial in the set of states of the minimal DFA and length of the maximal counterexample.

This is quite a strong and positive result and recently has found several applications. However, as always the details are important, as the title of the paper below already suggests.

  The minimum consistent DFA problem cannot be approximated within and polynomial
  , Pitt and Warmuth, 1989.

Now you may be wondering, how is any of this relevant to your question? To which my answer is that the design space for a mathematical definition of your problem is very large and the specific point you choose in this space is going to affect the kind of answers you will get. The above is not meant to be a comprehensive survey of how to formalise the learning problem. It's just meant to demonstrate the direction you may want to investigate. All the references and results I quote are extremely dated, and the field has done a lot since then. There are basic textbooks you could consult to obtain the sufficient background to formulate your question in a precise manner and determine if the answer you seek already exists.

this is an old question/problem with many, many connections deep into number theory, mathematics, TCS and in particular Automated Theorem Proving.[5]

the old, near-ancient question is, "is there a formula for computing primes"

the answer is, yes, in a sense, there are various algorithms to compute it.

the Riemann zeta function can be reoriented as an "algorithm" to find primes.

seems possible to me that a GA, genetic-algorithm approach may succeed on this problem some day with an ingenious setup, ie GAs are the nearest known technology that have the most chance of succeeding.[6][7] its the problem of finding an algorithm from a finite set of examples, ie machine learning, which is very similar to mathematical induction. however there does not seem to be much research into application of GAs in number theory so far.

the nearest to this in existing literature seems to be eg [8] that discusses developing the twin prime conjecture in an automated way ie "automated conjecture making".

another approach is a program that has a large set of tables of standard functions, along with some sophisticated conversion logic, to recognize standard integer sequences. this is a new function built into Mathematica called findsequence [3]

its also connected to a relatively new field called "experimental mathematics" [9,10] or what is also called "empirical" research in TCS.

another basic point to make here is that the sequence of primes is not "smooth", highly irregular, chaotic, fractal, and standard machine learning algorithms are historically based on numerical optimization and minimizing error (eg gradient descent), and do not do so well on finding exact answers to discrete problems. but again GAs can succeed and have been shown to succeed in this area/regime.

[1] is there a math eqn for the nth prime, math.se

[2] formula for primes, wikipedia

[3] wolfram findsequence function

[4] riemann zeta function

[5] top successes of automated theorem proving

[6] applications of genetic algorithms in real world

[7] applying genetic algorithms to automated thm proving by Wang

[8] Automated Conjecture Making in Number
Theory using HR, Otter and Maple colton

[9] Are there applications of experimental mathematics in TCS?

[10] A reading list on experimental algorithmics


What kind of reinforcement learning is MENACE? The famous MENACE matchbox computer for playing tic-tac-toe, invented by Donald Mitchie, is an early example of a reinforcement learning algorithm. Here is a description:

  ...an interesting machine for playing tic-tac-toe. It was made
  entirely out of matchboxes, each one of which had a tic tac toe
  position on the top. Inside was a collection of colored beads. Each
  color specified a possible legal move for the position on top. The
  idea was that you’d play a game by drawing these beads from the
  appropriate box, and making the appropriate move. At the end of the
  game, you’d remove the bead from the last box that sent you along the
  losing path. Eventually, all the losing moves get removed, and the
  machine plays perfect tic-tac-toe. Gardner showed how this same idea
  could be used to create a matchbox computer to play hexapawn, a simple
  game played with six pawns on a 3×3 board.

My question is: what kind of algorithm is this, in modern parlance? Is it policy iteration? Q-learning? Or sooething else? I am a bit new to the subject and can't figure it out for sure.

I found this question because I was searching for an answer to it myself...so take my answer on this with a grain of salt...but I believe that it's similar to policy gradients. In policy gradients you increase the probability of taking actions when you see a large reward which followed those actions...that seems to be the idea behind MENACE as well.


A lottery that you can be convinced that it is fair (Sorry if this is well known.) I would like to give some item to one of $k$ agents, so that agent $j$ will get the item with probability $p_i$. Is there a cryptographic (or other) tool so that every agent (and even every observer) will be able to be convinced that the random drawing was indeed fair?

If I am understanding the problem correctly, it would seem to amount to public flipping a $k$-sided coin. There seem to be lots of ways to do this if you assume bit commitment. One example would be having each party generate a random integer between 0 and $k-1$, using bit commitment to publicly commit to that bit string. Then once each agent has committed, they all publicly reveal their secret integer. The winning agent is then the one indexed by the sum of the integers modulo $k$. If even one agent is honest, then the flip must be random.

Of course one problem with this is that it requires bit commitment. Information theoretic schemes for bit commitment are impossible for both classical and quantum computing (though Adrian Kent recently proposed a scheme exploiting relativity). However, secure bit commitment can be achieved with computational assumptions.

Passive observers can't verify that the drawing wasn't staged. Inputs into pseudorandom process can be chosen to give desired result.

However if the observer can supply a random number that he knows is random AND make sure that other agents won't change their inputs afterwards (because they could compensate his effect with their inputs), then he can be sure that the result was indeed random.

This requires commitment scheme which we don't know any that is mathematically proven to be secure but in practice can be realized using secure hash (such as SHA3).

Consider this example:

I've made an example implementation. You can see it live here: https://mrogalski.eu/cl/ or check sources on GitHub.


Counterexample to max-flow algorithms with irrational weights? It is known that Ford-Fulkerson or Edmonds-Karp with the fat pipe heuristic (two algorithms for max-flow) need not halt if some of the weights are irrational. In fact, they can even converge on the wrong value! However, all the examples I could find in the literature [references below, plus references therein] use just a single irrational value: the conjugate golden ratio $\phi' = (\sqrt{5}-1)/2$, and other values that are either rational, or are rational multiples of $\phi'$. My main question is:

General Question: What happens with other irrational values?

For example (but don't feel like you have to answer all of these to post - I'd find interesting an answer to any one, or to other questions that fall under the above general question):

Given any $\alpha \in \mathbb{R}$, can one construct (or even show existence of) such counterexamples?

More weakly: are there examples known that use an irrational value essentially different from $\phi'$? That is, is there some $\alpha$ which is not a rational multiple of $\phi'$ (or more strongly not in $\mathbb{Q}(\phi')$) and such that there are counterexamples to Ford-Fulkerson and/or Edmonds-Karp where all the weights lie in $\mathbb{Q}(\alpha)$?

In the other direction, does there exist an irrational $\alpha$ such that Ford-Fulkerson (resp., Edmonds-Karp) halts with the correct value on all graphs whose weights are all from $\mathbb{Q} \cup \{q\alpha : q \in \mathbb{Q}\}$? (Or more strongly, from $\mathbb{Q}(\alpha)$?)

In all cases, I want to assume something like the real RAM model, so that exact arithmetic and exact comparisons of real numbers are done in constant time.
(There are other max-flow algorithms that are known to run in strongly polynomial time, even with arbitrary real weights, which is perhaps why this type of question may not have been further explored. But having just taught these algorithms in my undergrad algorithms class, I'm still curious about this.)
References

A minimal counterexample for Ford-Fulkerson was given by Zwick TCS 1999

A counterexample for Edmonds-Karp was given by Queyranne or Queyranne Math. Oper. Res. 1980, though I don't know if that one's minimal.

These can both be found in Jeff Erickson's lecture notes, with the first in Section 23.5 and the second as Exercise 14 of Lecture 23.

The answer is that for every irrational number $r$, there exists a network

with $n=6$ vertices and $m=8$ arcs,
in which seven arcs have integer capacity,
in which one arc has capacity $r$,
and on which Ford-Fulkerson may fail to terminate.

This has been proved in the paper

  Toshihiko Takahashi:
  "The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate"
  Journal of Information Processing 24, pp 390-394, 2016.
  Link: https://www.jstage.jst.go.jp/article/ipsjjip/24/2/24_390/_article

Thank you for the question that I found not really natural but quite amusing none the less.

I have looked into the Ford-Ferkulson part and I think I have found a graph that is a counter-example and has only one edge with irrational capacity α (the graph can work for any α).

Here is a PDF summing up my attempt : https://louis.jachiet.com/tmp/jQwbrkSMLNU_draft.pdf (sorry it is a  bit laconic for the moment but don't hesitate for ask questions)

Obviously the Ford-Felkurson lets us choose augmenting path as we wish... I have not sure this would be possible for Edmond-Karp.


Can one return to a TCS research job after an excursion to a non-research industry job? I have heard from some senior researchers in theoretical computer science that working in a non-research industry job, even just for a few years, will kill your career as a TCS researcher.
However I am suspicious of the claim that the road from being a TCS researcher to a non-research job in the industry is a one-way street. I want to know if this claim is plausible and any implications of making an excursion into a non-research job in the industry in case one later decides to return to a research job in academia.

Do you know examples of people who went to non-research industry jobs after their completing their PhD, worked there for a few years, and successfully made it back into academia as researchers (e.g. got research faculty positions)?
If yes, what fraction of senior researchers (tenured) do they constitute in your department or departments you are familiar with?
What fraction of such candidates who apply for academic research positions fail to obtain one?
Does the number of years in non-research jobs before returning make a difference?
More generally, what role would such excursions play in decisions made by hiring committees?

Since the answer may vary from a region to another one (e.g. North America, Europe, etc.) please mention the region you are talking about in your answer.
For the purposes of this question, let's consider all jobs in which the main task is conducting (publishable) research as "academia" and all jobs in which the main task is not conducting (publishable) research and it is difficult to do research and publish papers as "industry".

Let me disagree with the other responses.

While there are clearly notable examples of people who can transition to industry and back (see other answers), going to a non-research industrial position, even for a couple years, will make it very hard to return to academia, unless you're already very famous.

The reason is not because academics look down on industry or will think you "impure," but rather that it's very hard to stay active publishing when your job requires all your work time be spent on something else.  And if you haven't published anything for a couple years, it will be nearly impossible to convince a hiring committee to choose you over people who have. (Again, this doesn't apply if you already have a Turing award, etc.)

But if you can find the time to stay active in research and publish while working in your industry position, then you can still be competitive.  It's just likely to be a losing battle, and your other job responsibilities will realistically probably end up taking priority over research on-the-side.

Think about it this way: once you start working in industry at a great company that changes the world (think Google), having lots of success, seeing your real-world impact, having much quicker runs of success (as opposed to trying for ages to solve a hard theory problem which in the end nobody will use and will have zero impact on the world), enjoying your life to the fullest, etc., you will not want to go back to "slave away" in academia.


Reference Request: Error correction code for a random projection I'm interested in a variant of the Binary Channel, where the bits aren't flipped with some probability, but rather they are completely erased. Output words therefore vary in length.

I'm quite sure that this subject is well researched, and all I need is the correct search term.

I think the term is deletion channel. As the Wikipedia article says, this "should not be confused with the binary erasure channel".

The term you're looking for is: Binary Erasure Channel. And here's the link: Binary Erasure channel.


Reference for fundamental theorem on tree rotations Two binary search trees are said to be linearly equivalent when they agree in their in-order traversals. The following theorem explains why tree rotations are so fundamental:

Let A and B be binary search trees. Then A and B are linearly equivalent if and only if they are connected by a sequence of tree rotations.

I noticed this result when I was first learning about data structures long ago and wanted to understand the special status of tree rotations more deeply.

The proof is simple and intuitive: Rotate the least element up to the root position along the leftward spine. By the order invariant, this rearranged tree cannot have a left subtree. Now recurse on the right subtree. The result is a normal form for testing linear equivalence.

While it's a basic theorem, I've never come across it in the literature. I would greatly appreciate a reference for the next time I need to use this result.

(Bonus brain teaser: What's the best algorithm for finding the shortest sequence of tree rotations that connect two linearly equivalent binary search trees?)

An early paper that made this observation explicitly -- that rotations preserve inorder traversals -- is (in Figure 2 of) Sleator and Tarjan's 1983 Self-adjusting binary search trees.  The move-to-root heuristic was studied in Allen and Munro's 1978 Self-Organizing Binary Search Trees paper.

A simpler proof ,also constructive ,of the simpler fact that a Hamiltonian path exits in the rotation graph can be found in this latter .


Can this randomized greedy algorithm be made online? Or being proved impossible? I am going to edge color an undirected simple graph. The following randomized offline algorithm is showed at Online Algorithms for Edge Coloring.

Offline: The potential colors are ordered 1, 2, . . . , 2$\Delta$−1. The edges are ordered at random, and we greedily assign color 1 until a
maximal matching is colored 1, then we start over with a random order of the remaining uncolored edges and we greedily assign color 2 until a maximal matching of the remaining edges is colored 2, and so on with the remaining edges and maximal matchings for colors 3, 4, . . .

In paper Online Algorithms for Edge Coloring, the authors claimed the offline algorithm is the same as the online algorithm as follows.

Online: The edges are ordered at random only once, and each edge in turn is
colored with the least valid color out of 1, 2, . . . , 2$\Delta$ − 1.

The "same" means, for a given graph. If the first algorithm needs $c$ colors with probability $p$, then the second algorithm uses needs $c$ colors with probability $p$. So there is not clear justification that the given two algorithms are same.

The paper claims "For the second algorithm, if we consider sequentially when colors 1, 2, . . . are assigned, the same bound holds.".

In fact, they turn out to be different (see the examle below). So my question is: can the offline algorithm be made onlne? I cannot handle the multi-times random ordering ( after each maximal matching is removed, the order of the remaining edges is shuffled).

Example.

Let $E_r=\{e_0, e_1, e_2\}$, $X_i$ be the indicator random variable that whether color $i$ is assigned to one edge from $E_r$.  $X_i=1$ iff the i-th color is not assigned to the edges e_0, e_1, e_2. We calulate the expected number of colors from clolrs $\{1, 2\}$ which are not assinged to any of $\{e_0, e_1, e_2\}$.

For the "first algorithm":
$E[X_1+X_2] = Pr(X_1=1)+Pr(X_2=1) $
$=Pr(X_1=1)+Pr(X_2=1|X_1=1)\cdot Pr(X_1=1) + Pr(X_2=1|X_1=0)\cdot Pr(X_1=0)$
$=(\frac{2}{3})^3 + (\frac{1}{2})^3 \cdot (\frac{2}{3})^3 + (\frac{1}{2})^2 \cdot (1- (\frac{2}{3})^3 )$
$=\frac{1}{2}$

For the "second algorithm": We list all the $9!$ orderings, and get $E[X_1+X_2]=12/27=0.44444$.

The follwoing is responce for @vzn, thanks very much.

In fact, the paper was not published as far as I know. I have contacted the first author, he have not respond it in detail. The key is that, it does not "fit" clearly.
Why I only concern the first two colors in the example. If $x$ edges from $\{e_0, e_1, e_2\}$ are not assigned to colors in $\{1,2\}$, then the algorithms needs exactly $2+(3-x)=5-x$ colors. Because for the remaining $(3-x)$ edges incident to the root not colored, $(3-x)$ new colors have to be used. While the other edges will be colored in the third color definitely. Put another way, if the two algorithms were the same, all the characterizations of them should be the same? (For example, $E[X_1+X_2]$ here. Am I right? I am not sure.)

as far as I can tell after looking into this somewhat, there is a misunderstanding of the paper in the question. the question states that some of the algorithms are offline vs some online. but the algorithms in the paper are all online it appears (but agree the authors are not clear on this point). that is what is accomplished by having random edge orderings-- the random edge ordering reflects edges coming "online" in whatever order, right?

the authors seem to make no reference to "offline" algorithms in the paper and they refer to "online" only in the introduction that I see. they dont state this but the 1st algorithm seems to allow edges to come "online" in "batches" (ie random reordering in stages) whereas the 2nd algorithm does not.

while you dont state it exactly you appear to be checking the math in proof for theorem 2.3 in the paper (p3) which establishes a lower bound on the number of colors in a tree and the authors assert it works for both algorithm 1 and 2 ("for the 2nd algorithm.. the same bound holds"). the proof is that no less than $1.23\Delta$ colors ($\Delta$=graph degree) are sufficient for all trees. it seems if this theorem is wrong as you are suggesting then one should be able to exhibit a tree that can be colored with fewer than $1.23\Delta$ colors using those algorithms. from what I can tell your math is off because you are not expressing it using the same formulas in the proof eg you do not calculate the exponential formula in the proof.

a way to empirically verify this lower bound would be to generate many random trees, or some sample from some distribution, run the two algorithms and verify that they always use at least $1.23\Delta$ colors.


What tools do you use to give presentations? I was wondering what tools that people in this field (theoretical computer science) use to create presentations. Since a great deal of computer science is not just writing papers but also giving presentations I thought that this would be an important soft question. This is inspired by the previous question what tools do you use to write papers.  The most common that I have seen are as follows.

Beamer
Microsoft PowerPoint
LaTeX
GraphViz

I was wondering if there are any other tricks that I am missing?

For drawing diagrams, there's tikz in latex, and, if you have a Mac and a bit of cash, Omnigraffle. Both produce high quality diagrams.

nobody has mentioned http://prezi.com/ - innovative tool for presentation. Yet limited on formulas and other scientific stuff, but you can embed images with your graphs.


Oracle complexity of a problem in the Counting Hierarchy In "On The Complexity of Numerical Analysis" (SIAM J. Comp. Vol. 38, 2009), Allender et al. introduce the problem of PosSLP and show that its complexity lies in the counting hierarchy, and more precisely in
$P^{\mathit{PP}^{\mathit{PP}^{\mathit{PP}}}}$.

I have a problem, call it $X$, that I have shown can be solved in
$\mathit{NP}^{\mathit{PosSLP}}$. Can I correctly conclude that $X$ lies in
$\mathit{NP}^{\mathit{PP}^{\mathit{PP}^{\mathit{PP}}}}$?

Yes. Each time your $\sf NP$ machine want to query the $\sf PosSLP$ oracle, simply simulate the polynomial time oracle Turing machine underlying the inclusion $\sf PosSLP \subseteq {P}^{{PP}^{PP^{PP}}}$, passing its oracle queries to the $\sf {PP}^{PP^{PP}}$ oracle.

Let's take this step by step, so we are not confused by that small tower of oracles.

$X \in NP^{PosSLP}$. Since $PosSLP \in P^{PP^{PP^{PP}}}$, we derive that $X \in NP^{P^{PP^{PP^{PP}}}}$. We want to prove that $X \in NP^{PP^{PP^{PP}}}$.

Since $NP \subseteq NP^{P}$ and due to oracle properties, adding the power of the same oracles to both hands of the relation preserves it. Therefore we have:
$NP^{PP^{PP^{PP}}} \subseteq NP^{P^{PP^{PP^{PP}}}}$.

So yes, the problem is in $NP^{P^{PP^{PP^{PP}}}}$.


What's the simplest noncontroversial 2-state universal Turing machine? I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness.

So far I've created a game state which encodes Alex Smith's 2-state, 3-symbol Turing machine. However, it seems (admittedly based on Wikipedia) that there's some controversy as to whether the (2, 3) machine is actually universal.

For rigour's sake, I'd like my proof to feature a "noncontroversial" UTM. So my questions are:

Is the (2,3) machine generally regarded as universal, non-universal, or controversial? I don't know where would be reputable places to look to find the answer to this.
If the (2,3) machine isn't widely accepted as universal, what's the smallest N such that a (2,N) machine is noncontroversially accepted as universal?

Edited to add: It'd also be useful to know any requirements for the infinite tape for mentioned machines, if you happen to know them. It seems the (2,3) machine requires an initial state of tape that's nonperiodic, which will be a bit difficult to simulate within the rules of a card game.

This is not a real answer to your question (I don't know much about the (2,3) machine debate); but I suggest you the paper "Small Turing machines and generalized busy beaver competition". I quickly read it some time ago, and it has a nice graph with the borderlines between the 4 types of small TMs:

decidable
open Collatz-like problem
$3x + 1$ simulation
universal

(perhaps some results have been improved).

The notion of TM used in the paper is the standard definition of TM used in papers on small universal Turing machines :

... They have a unique one-dimensional tape infinite in both directions, and a unique twoway
read–write head. There is a blank symbol denoted by 0. Initially, a
finite word, the input, is written on the tape, other cells contain the blank
symbol, the head reads the leftmost symbol of the input, and the state is the
initial state. At each step, according to the current state of the machine and
the symbol read by the head, the symbol is modified, the head moves left or
right (and cannot stay reading the same cell), and the state is modified. The
computation stops when a special halting state is reached. ...

Alex Smith's Turing-universality proof of Wolfram's-conjectured 2-state, 3-symbol Turing machine is definitely not controversial. The given universality proof (not the machine) requires an infinite pattern on the Turing tape, and the question was whether one should allow such configurations (you can think of the usually 'blank' tape as an infinite repetitive pattern of blank symbols too). The conclusion was that as long as the configuration on the machine tape is fixed (i.e. it does not change after your computation starts, and remains the same for any computation), then the universal computation is carried out by the Turing machine. Notice that this is NOT controversial for Wolfram's Elementary Cellular Automaton rule 110 that Wolfram and Cook proven universal. The universality proof of rule 110 also requires an infinite pattern on the initial configuration, one that is different on both sides, and so it is of the same nature for the 2-state, 3-symbol Turing machine. Another concern was that perhaps such a relaxation of the initial condition (blank) requirement would make some accepted non-Turing universal automata universal, such as finite-state, linear bounded or push down automata to mention some examples, but it does not and it respects the Chomsky hierarchy. So definitely it is not controversial whether the 2-state, 3-symbol Turing machine is universal, but its universality proof did require a variation of what usually is considered to be the cotents of a regular Turing machine tape. This does not imply directly, by the way, that the 2-state, 3-symbol Turing machine is not universal on a blank tape configuration, although it might be the case, but that the proof required such a configuration.


Alphabet of single-tape Turing machine Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing machine using an alphabet of size $3$ (say, $0,1,$ and blank)?

(From comments below by the OP)
Note the input is written using $0,1$, but the Turing machine using alphabet of size $k$ can overwrite the input symbols with symbols from the larger alphabet. I don't see how to encode symbols in the larger alphabet in the smaller alphabet without having to shift the input around which would cost time $n^2$.

A partial answer if TM runs in $o( |x| \log |x|)$

If TM4 is a 4-symbols TM (with alphabet $\Sigma_4 = \{\epsilon,0,1,2 \} $ ) that computes $f:\{0,1\}^* \to \{0,1\}$, i.e. decides language $L = \{ x | f(x) = 1 \}$ in $(o( |x| \log |x|))$

One tape deterministic linear-time complexity is $1DLIN = 1DTime(O(n))$

Hennie proved (1) that $REG = 1DLIN$
Kobayashi proved (2) that $REG = 1DTime(o(n \log n))$

So $L$ is regular, and is obviously still regular over alphabet $\Sigma_3 = \{\epsilon,0,1\}$

So there is a DFA that decide L and uses only symbols in $\Sigma_3$. A one-tape, 3-symbols TM3 can be built directly from the DFA and it decides L using the same unpadded input of the original TM4.

... you cannot build it directly from TM4, but TM3 exists.

If TM4 runs in $\Omega(n^2)$ then you can shift the input and make a direct conversion from TM4 to TM3.

As noticed in the comments the difficult case is when TM4 runs in $\Omega(n\log n) \cap o(n^2)$.

(1) Hennie, One-tape, off-line Turing machine computations (1965)

(2) Kobayashi, On the structure of one-tape nondeterministic Turing machine time hierarchy (1985)

For all alphabet sizes greater than $1$, runtimes only change by a constant factor since $\log_k(x) \in \Theta(\log_l(x))$ for all $k, l > 1$.

Elaboration: In $t$ timesteps, the assumed Turing machine can process at most $t$ positions/bits. Bits are taken from a $k$-nary alphabet, wlog $\{0,1,\dots,k-1\}$. Create a new Turing machine by replacing every transition by $\lceil \log_2(k) \rceil$ transitions; every old bit is encoded by $\lceil \log_2(k) \rceil$ bits in $\{0,1\}$ (blanks are reserved to mark unused cells). Note this is essentially binary coded digits.

Obviously, the resulting Turing machine executes at most $\lceil \log_2(k) \rceil \cdot t \in \mathcal{O}(t)$ steps.

Addition: Above argumentation breaks because operations that overwrite an input symbol with a bit not in $\{0,1\}$ can not be translated directly; the input has to be shifted. This can be amended by translating the original input before starting computation (essentially padding); this can be done in time $\mathcal{O}(n^2)$, resulting in a total runtime of $\mathcal{O}(n^2) + \lceil \log_2(k) \rceil \cdot t$.

Consequently, using only two symbols for encoding intermediate results is of no asymptotic impact if $t(n) \in \Omega(n^2)$, but preprocessing dominates faster algorithms. Since most interesting functions are in $\Omega(n^2)$ (e.g. adding two numbers), one might consider the problem negligable.


Can reversible computations alone be used to create a computer? We are able to perform universal computations with the reversible model. Basically, during the computations, no information should be erased, so that no involved entropy increase would occur.

Are reversible computations alone sufficient to create a complete computer? The machine should be able to:

load programs,
handle user input,
provide an output.

I suspect that, for example reading user's input requires information deletion which cannot be avoided.

You need workspace (registers set to 0) to read the user's input. Once you've read it, and completed the program, the user needs to erase the input and the output in order to restore the workspace. However, if you assume that the user wants to keep a copy of the input and the output, this is possible to do reversibly.

Similarly for the program, to erase the program from the computer there needs to be another copy stored somewhere.

If you don't allow any reversible operations between the user and the computer, and you insist that everything be done reversibly, then you can't load input into the computer, and you have a useless machine.

The above answer seems wrong to me: the basic idea is that logically reversible and physically reversible are distinct.

Consider a quantum computer (reversible by nature), in the memory you store qbits, after you do an operation, you store the qbits that are important, those qbits that are no longer useful after the operation can be expelled from the memory and discarded. (lost in the endless space of the universe) Although the operations are logically reversible, it is no longer necessary to store all the qbits and we deliberately lose some (thus not physically reversible).