Is sliding blocks linear space complete? Sliding blocks is PSPACE complete even in its simplest form involving 1x2 and 2x1 blocks (without rotation or fractional positions) in a rectangular area, with goal being to move a designated block to the designated space.  See "PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation" by Robert Hearn and Erik Demaine. However, that paper does not give a more precise characterization than PSPACE.

Is existence of a solution in sliding blocks (deterministic) linear space complete?

One choice of completeness is to use polynomial time linear space reductions with at most linear increase in instance size, but gadget based reductions also work in LOGSPACE and might even work in uniform linear size AC$^0$.

Offered using Q/A format.

Yes, sliding blocks, Rush Hour, and many other puzzles with reversible moves are (deterministic) linear space complete.  By contrast, many puzzles with irreversible moves, including Sokoban, are complete for nondeterministic linear space.

Sliding blocks is in linear space because the state has $O(n)$ bits and the moves are reversible (and undirected graph connectivity is in logspace).

In the other direction, the above paper first uses a reduction from nondeterministic constraint logic (NCL), and then reduces QBF to NCL.  The NCL to sliding blocks reduction is space-efficient (at least if the wiring of NCL is based on a two dimensional grid of cells with $O(1)$ gates per cell, which suffices).  However, even if the QBF to NCL reduction is efficient, known simulations of linear space use approximately quadratic size QBF.

Fortunately, a later paper offers a different reduction.  "[Parameterized Complexity of Graph Constraint Logic]"(https://arxiv.org/abs/1509.02683) by Tom van der Zanden shows that NCL (even for bounded width corresponding to an nxk board) can simulate H-Word Reconfiguration (which can be used to simulate string rewriting with a finite set of reversible length-preserving rules).  While the paper does not say it, H-Word Reconfiguration can be used for space-efficient (up to a constant factor) simulation of reversible Turing machines.  In turn, given unbounded time, reversible Turing machines (as a computational model) are space-efficient. (However, it remains open whether some problems in $\mathrm{TimeSpace}(n^{O(1)}, O(n))$ take exponential time for linear space reversible Turing machines.)

For appropriate board representations, we even have, for every problem in linear space, a deterministic finite state transducer that reduces instances to solvability of sliding blocks.  The transducer gives an nxk board; if we want an mxm board, linear time logspace reductions remain sufficient.


Do dependent types give you everything subtyping does? Types and Programming Languages focuses quite a bit on subtyping, but as far as I can tell, subtyping doesn't seem especially fundamental. Does subtyping give you anything more than dependent types do? Working with dependent types is bound to be more work, so I can understand why subtypes might be useful in practice. However, I am more interested in type theory as a foundation for mathematics than as a basis for programming languages, should I pay much attention to subtyping?

Subtyping and dependent types are orthogonal concepts.

Subtyping is typically equipped with a notion of subsumption, whereby an expression of one type can appear in place where a supertype is expected.

Subtyping is more likely to be decidable and is more simply to manage in implementation.

Dependent typing is vastly more expressive. But if you ever want to consider a group to also be a monoid, then you need a notion of subsumption to forget the extra structure. Often, such as when using Coq, a trivial proof obligation is generated to deal with this kind of coercion, so in practice subtyping may not add anything. What's more important is having ways of packaging together various theories to make them reusable, such as reusing the theory of monoids when talking about groups. Type classes in Coq are a recent innovation for doing such things. Modules are an older approach.

If you do a quick google of "subtyping dependent types" you find a bunch of work adding subtyping to dependent types, mostly from around the year 2000. I imagine that the meta-theory is really challenging, so no subtyping of dependent types appears in proof assistants.


Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME? Is the following problem in PTIME, or coNP-hard:

Given two Boolean expressions $e_1$ and $e_2$ in variables $x_1,\dots,x_n$, without negation (ie, the expressions are entirely built up via $\wedge$ and $\vee$). Decide whether $e_1 \equiv e_2$, that is they have the same value for all assignments to the variables.

If both expressions would be given in DNF, then the problem is in PTIME since we could first lexicographically order the conjunctive clauses and compare. But bringing an arbitrary expression to DNF can blow up exponentially. A similar argument seems to hold for binary-decision-diagrams.

Obviously, the problem is in coNP.

I was Googling around a fair amount, but couldn't find any answer.

Apologies for the elementary question.

Corollary 3.5 of [BHR84] shows that the problem is coNP-complete.

[BHR84] P. A. Bloniarz, H. B. Hunt, III, and D. J. Rosenkrantz.  Algebraic structures with hard equivalence and minimization problems.  Journal of the ACM, 31(4):879–904, Oct. 1984.  http://dx.doi.org/10.1145/1634.1639


What techniques are used for proving algorithms optimal? Possible Duplicate:
  Problems that can be used to show polynomial time hardness results

Given a polynomial time algorithm, what techniques are known for proving that an algorithm is optimal?  E.g., given an algorithm for solving, say, REACH (a P-complete problem), what are good techniques for proving that the algorithm runs with optimal complexity, assuming of course that it does and that its complexity is known.

In case that was unclear, I'll restate my question briefly:  Given a polynomial time algorithm that decides a language or computes a function, how can one prove that the algorithm's worst-case complexity cannot be improved upon with a "better" algorithm?

Edit:  By "better" what I mean is that, e.g., if a particular algorithm has been established to run in O(n^4), there does not exist any algorithm with O(n^3) complexity that solves the same problem.

Thank you,

Philip

Intuitively, proving that a problem in P requires, say, time $\Omega(n\log n)$ is not any easier than proving the same lower bound for SAT. In fact, proving this lower bound for SAT should be easier, because we think SAT is harder than any problem in P. Concrete examples are matrix multiplication or fourier transform over GF(2). These are polynomial time problems but we don't have superlinear lower bounds.

One notable exception are time hierarchy results which give you (artificial) problems that are solvable by a Turing machine in time $O(t(n))$ but not solvable in time $O(t(n)/\log(n)).$ These results are proved via diagonalization.


How to solve an unification problem on $\mathbb{N}$? Usually, the unification problem for two given terms $t$ and $s$ is to find a substitution $\theta$ such that $\theta t = \theta s$,
which is equal to finding the certain $\langle x_1 , \cdots , x_n \rangle$ such that $t = s$ holds.
But in the $\lambda$Prolog programming language, by the existence of the logical operator $\mathtt{pi}$ whose semantics resembles $\forall$, an unification problem is of the form
$$ \mathcal{Q}_1 x_1 \cdots \mathcal{Q}_n x_n \left[ t_1 = s_1 \land \cdots \land t_m = s_m \right] , $$
where $\mathcal{Q}_i$ is an universal or existential quantifier.
See Miller's paper for more details.
I made my own $\lambda$Prolog interpreter without the operator of $+$ and $\times$, in which the currently implemented are numerals and successor.
Now, what I want to do is to add both $+$ and $\times$ with their arithmetic semantics, i.e., I want to solve the decision problem:
$$ \mathbb{N} \models \mathcal{Q}_1 x_1 \cdots \mathcal{Q}_n x_n \left[ t_1 = s_1 \land \cdots \land t_m = s_m \right] , $$
where $\mathcal{Q}_i$ is a quantifier, $x_i$ is a variable, $t_j$ and $s_j$ are terms; and terms are $\lambda$-terms extended with the constants $0$, $S$, $+$ and $\times$.

I have concluded that one cannot add both + and × in the λProlog programming language with their arithmetic semantics since the decision problem is undeciable. Because if it was decidable then Hilbert's tenth problem would have a positive answer. See the Wikipedia page for Hilbert's tenth problem.


Can we compute $n$ from the bits of $3^n$ in $O(n)$ time? I'm seeking an efficient algorithm for the problem:

Input: The positive integer $3^n$ (stored as bits) for some integer $n \geq 0$.
Output: The number $n$.

Question: Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

This is a theoretical question motivated by my answer to a math.SE question How to find a formula for this bijection?.  In this question, the author wanted to find a bijection from $$\{2^n 3^m: n \geq 0 \text{ and } m \geq 0\}$$ and the natural numbers $\mathbb{N}=\{1,2,\ldots\}$.  I proposed $$2^m 3^n \mapsto 2^m(2n+1)$$ as a solution.  Another answer there asserted "there is no simple formula", which makes me wonder how (computationally) simple my proposed solution is.
With my proposed solution, if we know $n$ and $m$, we can easily compute $2^m(2n+1)$ (write the binary digits of $n$ followed by $1$ followed by $m$ zeroes).  This takes $O(n+m)$ time.
Finding $m$ from the bits of $2^m 3^n$ amounts to finding the least significant bit (which can be computed by counting right bit shifts, leaving $3^n$ in memory).  This takes $O(m)$ time.
However, we also need to find $n$, which might be more difficult.  It would be possible to find $n$ by repeatedly dividing by $3$, but this seems wasteful.  It requires $n$ division operations, each of which will take $O(n)$ time, so this is $O(n^2)$ time in total.  [Actually, the after each iteration, the number of digits will decrease linearly, but this still results in $O(n^2)$ time.]
It seems like we should be able to exploit knowing the input is a power of $3$.

The obvious approach is:

(1) Compute an approximation to $\log_2(3^n)$. You can approximate it to within an additive error of 1 by counting the number of bits in the given binary representation, and to within an additive error of $\epsilon$ by additionally looking at the top $O(\log\frac{1}{\epsilon})$ bits of the input. It should suffice to choose a constant value of $\epsilon$, so that (after combining with the error in step (2)) the final result ends up within an additive error of $1/2$ of correct.

(2) Compute an approximation to $\log_2(3)$. I'm not familiar with the algorithms for this but I expect they take time polynomial in the number of bits of precision you need, and you only need $O(\log n)$ bits of precision.

(3) Divide the answer to (1) by the answer to (2), and round to the nearest integer.

So the first step takes linear time (in most models of computation although maybe not for some underpowered ones like single-head Turing machines) and the remaining steps should be polylogarithmic.


Example problems with polynomial and exponential solutions, and tiny footprint? I'm planning on running an “experiment” when teaching my algorithms class this fall, with one very old, limited computer (main limiting factor is probably memory—possibly as low as 16KB) and one modern/standard one. The idea being to solve a problem with a polynomial one, running on the slow computer, and an exponential one on the fast one (and, of course, have the slow one win).

The problem is finding a suitable problem—one where the running times will be really different for instances of very limited size (and, preferably, where the data structures are quite simple; the primitive computer is … primitive). I originally thought about sorting algorithms (e.g., quadratic vs. linear), but that would require far too large instances (unless I went with bogosort, for example).

At the moment, the only (rather boring) example I've thought of is computing Fibonacci numbers the smart and the stupid way. It would be nice to have something a little less tired/overused, and preferably something (semi-)obviously useful. Any ideas/suggestions?

You could do regular expression matching. A naive backtracking matcher can easily be pushed into exponential behavior on inputs that a smarter matcher can handle in linear time.


Are linear feedback shift registers being generally discouraged by cryptologists? Katz and Lindell mention in their book that LFSR have been horrible as basis for pseudorandom generators, and advocate that they are not used anymore (well, they also recommend that people use block ciphers instead of stream ciphers).
But I see for example that one of the ciphers in the estream portfolio (Grain, targeted for hardware) uses an LFSR, so the opinion that LFSRs are not good is not a consensus.

I'd like to know if there many cryptologists sharing Katz and Lindell's opinion on LFSRs (and on stream ciphers)?

There are many types of cryptanalytic attacks: Linear approximations, Algebraic attacks, Time-memory-data-tradeoff attacks, fault attacks.

For example you can read the survey: "Algebraic Attacks On Stream Ciphers (Survey)"

Abstract: Most stream ciphers based on linear feedback shift registers (LFSR)
are vulnerable to recent algebraic attacks. In this survey paper, we describe
generic attacks: existence of algebraic equations and fast algebraic attacks. ...

At the end you can find other relevant references.

Another good paper about fault attacks to stream ciphers is: "Fault Analysis of Stream Ciphers"

Abstract: ... Our goal in this paper is to develop general techniques which can be used to attack the standard constructions of stream ciphers based on LFSR’s, as well as more specialized techniques which can be used against specific stream ciphers such as RC4, LILI-128 and SOBERt32. While most of the schemes can be successfully attacked, we point out several interesting open problems such as an attack on FSM filtered constructions and the analysis of high Hamming weight faults in LFSR’s.

For time-memory-data tradeoffs attacks you can read: "Cryptanalytic Time/Memory/Data tradeoffs for stream ciphers".


Are there any books containing collections of automata problems? You can find specialized books consisting entirely or problems from particular math domains (e.g. linear algebra, polynomials, combinatorics), but I've yet to find such a book for automata of any kind.

Sort of indirectly, this book is about research level automata problems:

http://www.amazon.ca/Automatic-Sequences-Theory-Applications-Generalizations/dp/0521823323

An automatic sequence is essentially a set of strings which can be computed by a DFA.


Hardness of approximation without the PCP theorem An important application of the PCP theorem is that it yields "hardness of approximation" type results. In some relatively simpler cases one can prove such hardness without PCP. Is there, however, any case where the hardness of approximation result was first proved using the PCP theorem, i.e., the result was not known before, but later a more direct proof was found that does not depend on PCP? In other words, is there any case where PCP appeared necessary first, but later it could be eliminated?

An example is this paper:

Guruswami, V., & Khanna, S. (2004). On the hardness of 4-coloring a 3-colorable graph. SIAM Journal on Discrete Mathematics, 18(1): 30-40. link

Using the PCP-Theorem, Khanna, Linial, and Safra (2000) proved that it is NP-hard to color a
3-colorable graph using just 4 colors. Later, Guruswami & Khanna (2004) gave, among other nice things, a PCP-free proof for the same result.


Does there exist polytime algorithm for this partitioning problem? I would like to know if there exists a polytime probablistic algorithm for the problem described below. It is relevant for construction of a crossvalidation-partitioning in statistics, fulfilling certain constraints.

Or is it maybe NP-complete? I don't see any direct connections to any NP-complete problem I know of.

Input: $(N,K, (\phi_1, \ldots, \phi_l))$

Informal description:

Let $ \{1 \ldots N\}$ be partitioned according to functions $\phi_1, \ldots, \phi_l$. Find a random partition $\Phi : \{1\ldots N\} \rightarrow \{1\ldots K\}$ s.t. for all $i$, elements with the same value under $\phi_i$, will get at least 2 different values under $\Phi$. Furthermore, the new partitioning should be balanced.

If no solution exists, halt with error.

Formal description:

Let $N, K \in \mathbb N$, and $\phi_i : \{1 \ldots N\} \rightarrow \{1 \ldots m_i\}$ be given for $i \in \{1 \ldots l\}$.

Find a random $\Phi : \{1\ldots N\} \rightarrow \{1\ldots K\}$ s.t.
$$
\forall i\in \{1 \ldots l\} :\forall v \in \{1\ldots  m_i\} : |\Phi( \phi_i^{-1}(v) )| \geq 2
$$
$$
\forall v \in \{1\ldots K\} :\left\lfloor \frac{N}{K} \right\rfloor \leq |\Phi^{-1}(v)| \leq \left\lceil \frac{N}{K} \right\rceil
$$

(This is about the problem in which $|\phi(\Phi^{-1}(i))|\geq 2$ instead of $|\Phi(\phi^{-1}(i))|\geq 2$. Read it too fast. On the bright side Dave fixes it in a comment to this message )

What about saying it computes a proper edge coloring of a regular graph ? This problem is NP-Complete, and amounts, given a graph as an entry, to find a partition of its edges into matchings.

Vizing's theorem says that to do that Delta (the maximum degree of your graph) or Delta + 1 colors are required, though deciding which is NP-hard.

In your case, I think setting $N$ to the be number of edges, and setting K to Delta would do the trick. You then want to split your $N$ edges into $K=\Delta$ classes, and N is a multiple of Delta (for example in 3-regular graphs, for which the problem is still NP-hard).

In order to ensure that the answer is a proper edge coloring, one can let $\phi_v$ (for each vertex $v$) be the function equal to $0$ when edge $e\in [N]$ is adjacent to $v$, and 1 otherwise. If each color class has at least two different images for each $\phi_v$, it means that each color class contains a edge incident to each vertex. As the graph is Delta-regular, it also means that all the edges around a vertex have different colors as there are only Delta edges around each vertex, and if a class had two it means one would have none.

If it's true it would mean that finding one answer to your question is hard, and sampling solutions too :-)

Nathann


How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)? In quantum computation there is a fair amount of interest in the task of simulating quantum physics. One instance of this is the problem of simulating the evolution of a system under the action of some general Hamiltonian $H$, which will be given by $e^{-iHt}$. If $H$ is sparse, and the entries of $H$ are available via some blackbox function then there are efficient algorithms to simulate this evolution operator to within some constant distance $\epsilon$ in the trace norm.

According to Berry, Ahokas, Cleve and Sanders, Commun. Math. Phys. 270, 359–371 (2007) 1-sparse Hamiltonians can be simulated efficiently using only 2 black box queries. However, the citations that go with this are to a masters thesis which does not appear to be online and to a STOC 03 paper on quantum random walks by Childs, Cleve, Deotto, Fahri, Gutmann and Spielman which seems to only deal with a specific subset of such Hamiltonians.

I guess that this is in fact true for all 1-sparse Hamiltonians, as the paper seems to indicate, but there is obviously something I'm missing (which is probably in the unobtainable thesis). I would be very grateful if someone could tell me whether or not this is true in general, and if so explain how it can be done (or point to a paper which contains it).

For what it's worth, I am specifically interested in the case of simulating diagonal Hamiltonians.

Diagonal Hamiltonians are easy to simulate with 2 queries. It's very well explained (with a circuit diagram!) in Andrew Childs' PhD thesis on page 18, Rule 1.6.

The main idea is to observe that if H is the Hamiltonian with diagonal entries d(j), then simulating H for time t maps the basis state $|j\rangle$ to $e^{-id(j)t}|j\rangle$. This is performed as follows: $|j, 0\rangle \rightarrow |j, d(j)\rangle$ (this uses 1 query), then $|j, d(j)\rangle \rightarrow e^{-id(j)t}|j, d(j)\rangle$ (this is a controlled phase flip on the first register controlled by the second), and then $e^{-id(j)t}|j, d(j)\rangle \rightarrow e^{-id(j)t}|j, 0\rangle$ (this uncomputes the answer using another query).

Indeed, all 1-sparse Hamiltonians can be simulated with 2 queries. This is also explained in Andrew's thesis, towards the end of page 20. It might be a bit hard to understand since it's explained in the context of simulating a d-sparse Hamiltonian using edge coloring. But the essential idea is to reduce a d-sparse Hamiltonian to a sum of 1-sparse Hamiltonians and then simulate the 1-sparse Hamiltonian.


What subjects, topics does a computer science graduate need to learn to apply available machine learning frameworks, esp. SVMs I want to teach myself enough machine learning so that I can, to begin with, understand enough to put to use available open source ML frameworks that will allow me to do things like:

Go through the HTML source of pages
from a certain site and "understand"
which sections form the content,
which the advertisements and which
form the metadata ( neither the
content, nor the ads - for e.g. -
TOC, author bio etc )
Go through the HTML source of pages
from disparate sites and "classify"
whether the site belongs to a
predefined category or not ( list of
categories will be supplied
beforehand ) based on the page content derived from 1
... similar classification tasks on
text and pages.

As you can see, my immediate requirements are to do with classification on disparate data sources and large amounts of data.

As far as my limited understanding goes, taking the neural net approach will take a lot of training and maintenance than putting SVMs to use?

I understand that SVMs are well suited to ( binary ) classification tasks like mine, and open source frameworks like libSVM are fairly mature?

Taking forward the question assuming SVMs to be a better answer to classification of the likes of mine, how do I understand things like:

What $R^n$ stands for
or hyperplanes
or how to transform a space so that
it can be broken into two parts etc?2.

  In that case, what subjects and topics
  does a computer science graduate need
  to learn right now, so that the above
  requirements can be solved, putting
  these frameworks to use? Especially those related to SVMs.

I am willing to learn and put in as much effort as I possibly can.

Recommendations from you on learning specific portions of statistics and probability theory is nothing unexpected from my side, so say that if required!

I will modify this question if needed, depending on all your suggestions and feedback.

Cross-posted on SO:

https://stackoverflow.com/questions/3764444/what-subjects-topics-does-a-computer-science-graduate-need-to-learn-to-apply-ava

From the theory end, you should understand how SVMs work (and why they do).  For example, I like the scribe notes from this class for a quick explanation and something like this tutorial for a more in-depth one.  You might also want to consider other machine learning techniques that are suited for binary classification on large data ie. boosting, random forests, ...

As for dealing with open source code issues and with parsing HTML, stackoverflow might be a better place to seek answers.

EDIT:  Given your modified question, I can address your concrete questions about SVMs directly:

$R^n$ "stands for" the fact that the (data) points to be classified lie in a $n$-dimensional Euclidean space.  For example, points in our familiar $2$ dimensions (with, say, latitude and longitude coordinates) lie in $R^2$ -- an $n$-dimensional space generalizes this notion.
A hyperplane (in $R^n$) is a flat of dimension $n-1$.  It is what an SVN uses to classify the data (after they have been mapped to the higher dimensional space by the chosen Kernel).  For example, if your space is $R^2$ (or a plane) then a hyperplane is line, and so on.
How to transform the space? This is done via the Kernel function.  A big part of SVM design is choosing a proper Kernel for the problem at hand.

To understand these three points in more detail, you can read the references above.


The Examiner's Problem (uniform generation of SAT decision instances/answers) A course's teaching assistant has managed to write a program that (deterministically) generates difficult exam questions. Now, she'd like to write a program that generates the corresponding answers. The Examiner's Problem asks whether this is always possible; the Examiner's Conjecture states that, assuming, $\mathsf{P} \neq \mathsf{NP}$, it is not: coming up with problems is easier than coming up with their solutions.

More formally, let $M$ be a deterministic Turing Machine that, on input $1^n$, generates in polynomial time a Boolean formula of size $n$. I'd like to know if, for all such $M$, there exists a deterministic polynomial-time Turing Machine $M'$ that, on input $1^n$, outputs "$1$" if $M(1^n)$ has a satisfying assignment and "$0$" otherwise.

Assuming $\mathsf{P} \neq \mathsf{NP}$, has this question already been asked or answered? If not answered, what sorts of additional assumptions (e.g. one-way functions?) might bear on the result? Barring any of the above, my "conjecture" is that the "answering" TM does not always exist, but what is your intuition?

Thanks!

The question you are asking is equivalent to unary NP = unary P, which in turn is equivalent to NE = E, by padding.

From the title, perhaps you meant to ask if it is possible to generate input/output pairs such that the distribution on the inputs is "hard."  The possibility of doing this lies somewhere between P $\ne$ NP and one-way functions exist.

In restricted computational models, it is known that this is possible.  E.g. one can generate input/output pairs for the parity or majority functions in AC$^0$ or below.  See The complexity of distributions.


Why is shifting bits different from shifting qubits? In classical circuit complexity, shifting bits is considered gratis; all you have to do is reorganizing wires between corresponding gates. By contrast, shifting qubits is typically done by using a series of quantum SWAP gates, which are composed of three CNOT gates respectively; the shifting contributes to the total circuit complexity.

So where does the difference come from? Is it due to the physical implementation of qubits?

It's complicated, and depends on whether you approach quantum computing as a technology or a model of computation; and whether you are interested in universal quantum computation, or a special subclass of quantum operations.

As a technology

We're still working on how to implement a large-scale quantum computer. Part of the reason for this is that it is a non-trivial engineering problem to devise quantum memories on which we can reliably act.

Many of the proposed architectures involve physical qubits which are in a fixed(-ish) position, relative to the others. Whether these are quantum dots (attached to a substrate), ions in a linear trap (mobile but often penned in between two other ions), or even nuclear spins in liquid NMR (locations fixed mostly by the chemical bonds within each molecule), those qubits don't have much freedom to move relative to the ones you want it to interact with.
You can't necessarily shuffle them around like cups and balls.

The fixed wires in a classical circuit get around this physical location problem by being physically extended. The wire acts as if tracing out the trajectory of "moving" logical bits, and may weave around each other somewhat between two logic gates. When we draw quantum circuit diagrams, we're dreaming of this — but at least one of the dimensions in the diagram represents not space, but time between the physical operations which we perform. Not many physical architectures for quantum information admit that sort of physical extension, while keeping the quantum bit coherent and available to be acted upon. If locations are more or less fixed, this prevents us from literally swapping around the qubits.

In summary, in quantum implementation, we can't be confident that SWAP operations will be easily achievable "in hardware", i.e. by swapping around the physical qubits. We thus have to resort to be achieving SWAP operations "in software" — by performing suitable operations to 'transport' the information from one physical qubit to another. Thus our interest in decomposing SWAP in terms of elementary gates.

As a model of computation

As a part of theory of computation, you are exactly right: decompositions of SWAP are only a curiousity, much like the logical universality of the NAND gate. It is worth taking note of, in elementary courses; but much beyond that we treat decompositions of SWAP almost exactly as seriously as we do the decomposition of classical algorithms into NAND gates — not very seriously, most of the time. So long as we consider a model of computation in which elementary gates have a constant cost and which generate SWAP, then SWAP can be performed with at most a constant cost — and if the cost due to SWAP gates does not dominate the run-time of the algorithm, then talking about them doesn't really shed any insight onto the complexity of a problem.

Of course, because of the technological promise of quantum computation, the technical difficulty in implementing quantum computers, not to mention the promise of any technique (including classical ones) to simulate bits of quantum mechanics, specialized and related models of computation have attracted some theoretical interest. One of these are "matchgate" circuits, which may be described as unitary circuits in which

Qubits are arranged in a linear array;
Only two-qubit nearest-neighbor unitary transformations are allowed (and possibly Hadamard operations, on the first qubit only);
All two-qubit operations are of the form $$\begin{bmatrix} a_{00} & 0 & 0 & a_{01} \\ 0 & b_{00} & b_{01} & 0 \\ 0 & b_{10} & b_{11} & 0 \\ a_{10} & 0 & 0 & a_{11} \end{bmatrix} \quad\text{where $\begin{bmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{bmatrix}, \begin{bmatrix} b_{00} & b_{01} \\ b_{10} & b_{11} \end{bmatrix} \in \mathrm{SU}(2)$}$$
  i.e., acting unitarily (with determinant 1) on the odd- and even-parity subspaces of the pair of qubits.

These computations can be efficiently simulated by classical computers (provided that the coefficients are efficiently computable, etc.) However, if you consider circuits which have these gates, and also SWAP gates, they become universal for quantum computation. The same holds if you allow the gates to act even on next-nearest neighbour qubits, or allow Hadamard operations on other lines than just the first. What appear to be trivial modifications of the model, which one could imagine performing by just moving qubits around, transform a model which is tractible to simulate to one which (we think) is intractible to simulate. Nor, obviously, can we decompose SWAP into gates which are allowed.

In summary

From a theoretical perspective, SWAP operations are exactly as boring as you think they should be, for much of the research in quantum computation. But a model of computation is a mathematical model of something we hope to achieve in hardware: the model is not necessarily representative of reality. And even if SWAP is boring in one model of computation, that doesn't mean it is boring in another model!

We are complacent about SWAP in classical computation because electronic computers are a mature technology in which these details are mostly safe to ignore. As soon as you switch models of computation, you must check your computational assumptions.


Can Elementary Affine Logic be used as the core type system of a practical programming language? Elementary Affine Logic is a type system which captures the class of λ-terms that can be reduced in elementary time. Moreover, EAL-typeable terms can be reduced using the abstract fragment of Lamping's algorithm, which is particularly interesting to me because I'm exploring the corresponding interaction combinators.

My question is, how can one make a practical programming language using EAL as the underlying type system? I.e., what kind of extensions (fix-points, polymorphism, dependent types, datatypes, etc.) could be made to the core type system without affecting that characteristic, and would such a language be usable in practice, or would it be somehow too restrictive for reasons I'm not aware?

Something very similar, but using light affine logic (LAL) instead of EAL, was attempted a few years ago by Baillot, Gaboardi and Mogbil (you may find the paper here).  I think their work may be easily generalized to EAL, which is a more liberal system.

As for the features of such language, you have polymorphism natively (EAL is a restriction of second order linear logic). As far as I know, no-one has looked at dependent types, but I don't see why they shouldn't work.  In fact, untyped EAL works just as well as typed EAL, because its normalization properties do not depend on types.

One consequence is that in EAL you may use arbitrary fixpoint of types (see for instance this other paper by Baillot) and define data types in the natural recursive style (like $\mathtt{list\ A := nil\mathrel | A\ *\ list\ A}$), along with the less natural (from a programming perspective) system F definition.  However, by the above remark on untyped normalization, a programming language based on EAL will always be total, which means that you won't have a fixpoint combinator and the use of recursive types is not as natural as you would expect.  For instance, take Scott numerals: without recursive definitions (given by the fixpoint combinator) it is hard to express anything beyond constant-time operations with this representation of integers.  Therefore, you will still need to use Church numerals for iteration (i.e., $\mathtt{for}$ loops), by using which you will incur in the fundamental stratification restriction of light logics (which gives them their complexity properties): you cannot iterate a function $\mathsf{Nat}\rightarrow\mathsf{Nat}$ which has itself been defined by iteration ($\mathsf{Nat}$ here is the type of Church integers).

An example: with some "Church integer hacking", it is possible to define in EAL $\mathsf{dbl}:\mathsf{Nat}\rightarrow\mathsf{Nat}$ such that $\mathsf{dbl}\ \underline{n} = \underline{2n}$ without using iteration.  Then, you may iterate $\mathsf{dbl}$ to define the exponential function $\mathsf{exp}$ which, however, cannot itself be iterated.  So whatever programming language based on EAL will need to have some kind of mechanism forbidding certain definitons by iteration; it s hard to imagine how such restriction would not result in a language which feels awkward to the programmer.  Anyway, no-one forbids you to try and see what you can get!

In any case, if you are interested in the relationship between optimal evaluation, EAL and light logics in general, I suggest you take a look at Coppola's papers from the early to mid-2000s.


network flow using minimum number of nodes In a standard Ford-Fulkerson setting (directed graph $G$ with a source $s$ and a sink $t$), consider the problem of achieving a given amount of flow using the minimum number of nodes in the graph.

The familiarity with the problem discussed here: Laying paths on a network using minimum number of links/edges seems to suggest that this problem might also be NP-hard. I can split every node in $G$ into two nodes and add an edge of unit cost between them, and assign zero cost to all the original edges. Cap-SNDP (http://www.cis.upenn.edu/~sanjeev/papers/ipco11_capacitated.pdf) on this new graph is equivalent to finding the minimum number of nodes in $G$ required to support the desired flow.

1) Is this problem known to be NP-hard?

2) If I restrict attention to layered graphs, does it change anything about the complexity/approximability? (A layered graph is one in which all $s-t$ paths have the same number of edges.)

Thanks in advance.

The problem is NP-hard on layered graphs. This can be seen by reduction from Exact Cover by 3-sets (X3C). Let $A_1,\ldots,A_m$ be subsets of $\{1,2,\ldots,3n\}$ with $\vert A_i\rvert=3$ for every $i$, the problem asks if there exists a set $I\subseteq\{1,2,\ldots,m\}$ of $\lvert I\rvert=n$ indices such that $\bigcup_{i\in I}A_i=\{1,2,\ldots,3n\}$. This can be reduced to the following instance of your problem. The node set is
$$V=\{s,t\}\cup\{v_i\ :\ i=1,2,\ldots,m\}\cup\{w_j\ :\ j=1,2,\ldots,3n\}.$$
There are the following arcs:

an arc $(s,v_i)$ with capacity 3 for every $i\in\{1,2,\ldots,m\}$,
an arc $(v_i,w_j)$ with capacity 1 for every pair $(i,j)$ with $j\in A_i$
an arc $(w_j,t)$ with capacity 1 for every $j\in\{1,2,\dots,3n\}$.

A flow of value $3n$ can be achieved using $4n$ nodes (not counting $s$ and $t$) if and only if the X3C-instance is a YES-instance.


Are there any topics in theoretical CS that are more about pure math? I am a graduate student in theoretical computer science, and in particular, approximation algorithms. I find now that I am more interested in pure math (I can say this because I seem to have enjoyed math courses more than the CS courses). I would like to ask if there are areas in theoretical computer science which are pretty much pure math (to be more precise, an area that is of interest in pure math on it's own without considering the applications to CS), or if I need to consider a major switch. I am already two and a half years into the program, so I am not sure if a switch would be a good idea at this point.

The only such thing I could find was graph minor theory, from browsing acceptance lists of top conferences. But that doesn't count as an 'area' for me that I can just focus on.

Here are three more fields that fit your criteria.

Category theory. This is clearly interesting to most pure maths
fields, but also has been very influential in the theory of
(functional, sequential) programming languages.
Logic, particularly proof theory. The connections with computer
science are too many to name, but logic is not only a rich field of
pure mathematical, but the foundation of mathematics.
Number theory, the "queen of mathematics", which was deemed to
be devoid of applications ... until cryptography came along.


What exactly is Lawler's modification to Yen's algorithm and how does it work? I recently read about Yen's algorithm, I understand the algorithm and it seems correct, however Wikipedia mentions that there exists "Lawler's modification" to the algorithm, which is described as basically caching all previous Dijkstra calls for the similar spur graphs. I have some questions about it:

According to the original research paper, the algorithm speeds up Yen's algorithm to $O(k \cdot n^3)$, but the Yen's algorithm described by Wikipedia is already of that complexity.
The original research paper actually seemingly contains 5 modifications to the original algorithm, although Wikipedia only describes one of them, what is going on here?
How does the mentioned modification in Wikipedia modify the runtime of the algorithm, according to me, the worst case time complexity is the same, or at most improved by constant time.
The last line of the Wikipedia description states "To perform this operation for $A^k$, a record is needed to identify the node where $A^{k-1}$ branched from $A^{k-2}$ ", but why? Can't we use the cached Dijkstra call from $A^{k-2}$ as well? Why is that bad? Since $B$(from pseudocode) is sorted and length of spur path + root path is increasing, it should never cause a problem? Maybe we are somehow missing testing out a root path + spur path, but it's un-intuitive to me how/why only the modification causes that(and why that wouldn't affect the original algorithm as well).

It would also be nice to get a commented and well tested implementation of the algorithm with the modification for reference, maybe that would make the modification clearer.

Yen's original paper 1, from 1971, only establishes an upper bound of $O(Kn^4)$ operations (see Table 1).
Lawler's original paper 2, from 1972, improves the time complexity upper bound to $O(Kn^3)$.
Wikipedia's analysis of Yen's algorithm, leading to the $O(Kn(m+n\log n))=O(Kn^3)$ upper bound, is based on the Fibonacci heap implementation of Dijkstra's algorithm, from 1984. [3] But even the $O(n^2)$ upper bound for Dijkstra's algorithm would be fine; the issue, as far as I can tell, is that Wikipedia is not considering the same problem.

Namely, Yen's paper, as well as Lawler's, consider graphs where negative weights are allowed. The Wikipedia seems to restrict itself to non-negative weights, so... one can use Dijkstra there.

See for instance this quote from Yen's paper (Section 5):

and this one for Lawler's paper (Section 5):

1 Finding the K Shortest Loopless Paths in a Network, Jin Y. Yen (1971).
Management Science 197117:11 , 712-716

2 A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem,
Eugene L. Lawler (1972). Management Science 197218:7 , 401-405

[3]  Fibonacci heaps and their uses in improved network optimization algorithms. Fredman, Michael Lawrence; Tarjan, Robert E. (1984). 25th Annual Symposium on Foundations of Computer Science. IEEE. pp. 338–346. doi:10.1109/SFCS.1984.715934.


Long-Standing Conjectures later trivially proved by an implication I'd like to know if there have been conjectures that have long been unproven in TCS, that were later proven by an implication from another theorem, that may have been easier to prove.

Erdös and Pósa proved that for any integer $k$ and any graph $G$ either $G$ has $k$ disjoint cycles or there is a set of size at most $f(k)$ vertices $S\in G$ such that $G\setminus S$ is a forest. (in their proof $f(k) \in O(k \cdot \log k)$).

The Erdös and Pósa property of a fixed graph $H$ known as the following (not a formal definition):

The class of graphs $\mathcal{C}$ admits the Erdös-Pósa property if there is a function $f$ such that for every graph $H\in \mathcal{C}$ and for any $k \in \mathbb{Z}$ and for any graph $G$ either there are $k$ disjoint isomorphic copy (w.r.t minor or subdivision) of $H$ in $G$ or there is a set of vertices $S\in G$, such that $|S|\le f(k)$ and $G\setminus S$ has no isomorphic copy of $H$.

After Erdös and Pósa's result for a class of cycles which are admitting this property, it was an open question to find a proper class $\mathcal{C}$. In graph minor V proved that every planar graph either has a bounded tree width or contains a big grid as a minor, by having the grid theorem in hand they showed that Erdös and Pósa property holds (for minor) if and only if $\mathcal{C}$ is a class of planar graphs. The problem still is open for subdivision, though. But the proof of theorem w.r.t minor is somehow simple and as best of my knowledge there is no proof without using the grid theorem.

Recent results for digraphs, provides answers for long standing open questions in the similar area for digraphs. e.g one very basic question was that is there a function $f$ such that for any graph $G$ and integers $k,l$, we either can find a set $S\subseteq V(G)$ of at most $f(k+l)$ vertices such that $G-S$ has no cycle of length at least $l$ or there are $k$ disjoint cycles of length at least $l$ in $G$. This is only a special case but for $l=2$ it was known as a Younger's conjecture. Before that Younger's conjecture was proven by Reed et al with quite a complicated approach.

It's worth to mention that still there are some quite non-trivial cases in digraphs. e.g Theorem 5.6 in the above paper is just a positive extension of younger's conjecture to a small class of weakly connected digraphs, but with the knowledge and mathematical tools that we have it's not trivial (or maybe we don't know a simple argument for that). Perhaps by providing a better characterisation for those graphs, there will be an easier way to prove it.


Statements that imply $\mathbf{P}\neq \mathbf{NP}$ This is sort of an open-ended question - for which I apologize in advance.

Are there examples of statements that (seemingly) don't have anything to do with complexity or Turing machines but the answer of which would imply $\mathbf{P}\neq \mathbf{NP}$?

A proof system for propositional logic is called polynomially bounded, if every tautology $\varphi$ has a proof in the system of length polynomial in the length of $\varphi$.

The statement "There is no polynomially bounded propositional proof system" is equivalent to $\mathsf{NP} \neq \mathsf{co}\text-\mathsf{NP}$ by a classic result of Cook and Reckhow, so it implies $\mathsf{P} \neq \mathsf{NP}$.


Efficient algorithm for computing equally distributed points in polytope? Given a $d$-dimensional (rational) convex polytope $P$ with vertices $v_1, \ldots, v_n$, I would like to compute many equally distributed points that lie in $P$. "Equally distributed" is of course not a precise term. It should just mean that points don't accumulate at some point in $P$ much more than at others (like they would be by doing a repeated barycentric subdivision, for example).

Now, there are two obvious solutions: First one is to just generate a lot of random points in the polytope. This can be done quickly with a software like Polymake. But the problem is that the coordinates have huge denominators which make subsequent computations very slow.

The second approach would be to generate coefficient vectors that sum up to $1$ and have entries $\geq 1/k$. The coefficients have small denominators but the algorithm would generate ${n-k-1 \choose k-1}$ coefficient vectors, while only a tiny fraction of them give distinct points in the polytope (at least for the polytopes I am interested in).

  Are there any algorithms that do what I want efficiently with small denominators?

This is an answer just to record a solution to the problem.

Given the polytope, I triangulate it without introducing new vertices. Then I generate for each simplex in the resulting simplicial complex many points in the interior with my second approach. Every coefficient vector will give distinct points because the vertices of the simplices are affinely independent. To implement this solution one can use Sage together with TOPCOM, for example.

Depending on the chosen triangulation, the dimension and and number of vertices this solution can actually be quite inefficient.


Prefix Probability in Stochastic Languages I was reading the following paper (http://aclweb.org/anthology/W/W13/W13-1801.pdf) and they state that, given a Probabilistic Finite Automata $A$ and a string $w$, finding the probability $Pr_A(w\Sigma^*)$ is simple (section 3, property 3. Just before the start of section 4). However, this isn't immediately clear to me since, even using some dynamic programming approach, you may have to compute the probability of an infinite number of paths (since it is not acyclic) starting at all of the states that are the last state reached in a path, $\Theta$, that generates $w$.

I was not able to find an answer in the references of that paper or any relevant papers on the subject.

To summarize, I am looking for an algorithm that, given a PFA $A$ and a string $w \in \Sigma^*$, returns the probability $Pr_A(w\Sigma^*)$. in other words, the probability of any string having $w$ as a prefix.

Thanks in advance.

According to their definition of PFA, to compute $Pr(w\Sigma^*)$ you simply need to compute the probability of having read $w$ after a random path of length $|w|$, which is easy.

Their model of PFA differs from the usual model: usually, for each state $q$ and letter $a$, we have $\sum_{q'} \delta(q,a,q')=1$, so you assume that in a run, the word is fixed beforehand and probabilities are played upon reading each letter.

Here, the setting is different: for each state $q$, we have $F(q)+\sum_{a,q'} \delta(q,a,q')=1$, meaning that a path is chosen at random (including the end), and induces a word. That is what makes the problem easier.


Is there a book/survey-paper outlining language class hierarchies, closure properties, etc I'm currently doing some Formal Language research involving classes of languages above Regular but below Context Free. I'm looking at things like Reversal-Bounded Multicounter Machines, Single-stack counter machines, deterministic CFLs, etc.

I'm wondering if anybody knows of a good book or survey paper which outlines the properties of these languages. Most of what I'm looking at is too obscure or too new to be in my Hopcroft-Ullman book, even the 1979 edition.

Mainly I'm looking for which language classes are contained in one-another, the closure properties of these languages, and the decidability of basic problems (F-problems) on these languages.

Some example of things I'd look up in this reference:

Are all languages accepted by Reversal-bounded Multi-counter machines also accepted by non-reversal-bounded single counter machines?
Are the deterministic reversal-bounded MultiCounter languages closed under left and right concatenation?
Is universality decidable for single-counter machines.

These are just example questions, I have many others that come up in my day-to-day work.

As a starting point, I've tried tracing which papers cite Oscar Ibarra's  "Reversal-Bounded Multicounter Machines and Their Decision Problems", but haven't found much.

Not standard topics, no. And sorry, I have no general overview.

However, I would have a look at the PhD thesis of Klaus Reinhardt for at least a picture of the various families that live in this area. See page 64 for a diagram of the zoo. Motivated by Petri Nets with inhibitor arcs Reinhardt studies priority multicounters with restrictions on when to do zero tests. Non-trivial.

By the way, your last example question was discussed in this forum by user Sam Jones. Another Ibarra reference.


A notion of time for uniform circuits Let C={Cn} be a family of uniform boolean circuits, whose size and depth are bounded by functions s(n) and d(n).

What is the upper bound on the running time of a Turing machine M that evaluates C? How tight is this upper bound?

I am assuming that we are talking about bounded fan-in circuits.

If a language can be decided by a deterministic Turing machine in time $t_n$ and space $s_n$, then it can be computed by a circuit of size $O(t_n\log s_n)$. The depth can be reduced to $d_n = l_n \log t_n = O(l^2_n)$ where $l_n = \max (s_n,\log n)$.

In the non-uniform circuit case and non-uniform TMs (NU-TM)  (when the space used by a TM includes the log of space used on the oracle tape containing the advice), if the language has circuits of size $c_n = \Omega(n)$, then it can be decided by an NU-TM where time $t_n = O(c^2_n)$ and space $s_n = O(c_n)$.

Similarly for depth $d_n = \Omega(\log n)$, we get an NU-TM with time $t_n = O(n2^{d_n})$ and space $s_n = O(d_n)$.

Form these results we get:

$Size(T^{O(1)}) = NU\text{-}Time(T^{O(1)})$ if $T(n) = \Omega(n)$,
$Depth(S^{O(1)}) = NU\text{-}Space(S^{O(1)})$ if $S(n) = \Omega(\log n)$.

I think we can extend this to uniform classes if we use appropriate uniformity conditions on both sides.

See also chapter 9 of Wegener's book "The Complexity of Boolean Functions" for more details.


Conditions for tractability of 3SAT-Satisfiability What I'm wondering specifically is if there is an interesting condition on the percentage of assignments that satisfy a 3SAT formula to guarantee that such problems are tractable.

Suppose for example the class of 3SAT problems that $\epsilon(n) 2^n$ of the $2^n$ possible assignments satisfy the boolean formula; can we efficiently find a satisfying assignment?  For what $\epsilon$ is the resulting problem in P?

Edit note:  Replaced $\epsilon$ with $\epsilon(n)$ to clear up confusion.

Yes. If $ 0< \epsilon <1$ is a constant (or $1/\textit{polylog}(n)$), and you are promised that at least $ \epsilon 2^n $ of all possible assignments are satisfying the input 3CNFs, then you can find such an assignment in deterministic polynomial-time.

The algorithms is not difficult:

Claim: Under the promise stated, there must exist a constant size set $ S $ of variables that hits all clauses in the 3CNF, in the sense that every 3-clause must contain a variable from $ S $.

Proof of claim (sketch): Otherwise, there must exist a large enough family of 3-clauses from the 3CNF, in which each variable occurs only once. But this family, when sufficiently large, has already less than $ \epsilon $ fraction of satisfying assignments. QED

Thus, you can run over all possible (constant number) of assignments to $ S $. Under every fixed assignment to $ S $, the 3CNF becomes a 2CNF, by the assumption that $ S $ hits the original 3CNF. Now, you can use the known polytime deterministic algorithm for finding a satisfying assignment for 2CNF formulas.
Overall, you get a polynomial time upper bound.

The algorithm for 2SAT is I think already in S. Cook famous 1971 paper.

The algorithm for 3CNFs is from:
L. Trevisan
A Note on Deterministic Approximate Counting for k-DNF
In Proc. of APPROX-RANDOM, Springer-Verlag, page 417-426, 2004

The original paper showing the result for 3CNF is:
E. Hirsch, A fast deterministic algorithm for formulas that have many satisfying assignments, Journal of the IGPL, 6(1):59-71, 1998


Power of randomness vs. power of indefinite computation I am writing a paragraph on the power of randomness, part of which I am trying to ground in theory of computation (I am no expert/researcher in this field).

First off, I am aware that for traditional complexity classes such as ZPP and BPP, it is open question whether they equal P. In context of this question, I am interested in a particular subset of ZPP.

Let ZPP be the set of decision problems for which there exists a Probabilistic Turing Machine (PTM) which solves it in a time that is polynomial in expectation.

Note that this definition allows indefinite computation (albeit with an infinitesimal likelihood). In fact, most membership proofs by example (I am aware of) use PTMs which exploit this fact.

Let bounded-ZPP (my own term) be the subclass of ZPP which (in addition) requires a PTM to have a bounded execution, i.e. it to halt after a finite (possibly super-polynomial) # steps.

I was wondering about the following:

Is there a more conventional name for bounded-ZPP?
Is bounded-ZPP = ZPP?
Is P = bounded-ZPP?
If (3) holds, wouldn't this suggest that a hypothetical P $\subset$ ZPP, would be more correctly attributed to allowing indefinite execution in ZPP, rather than the "power of random choice"?

Any problem in ZPP is computable (in fact, it is in the intersection of NP and coNP). Given any ZPP machine, run it in parallel with a deterministic machine that solves the same problem. This affects the running time by at most a polynomial factor (the exact factor depending on the model of computation), and so the new machine is also in ZPP. The new machine is also guaranteed to always halt. So bounded-ZPP is the same class as ZPP.


Are there semi-decision procedures for this theory? I have the following typed theory

|- 1_X : X -> X
f : A -> B, g : B -> C |- compose(g,f) : A -> C
F, f : A -> B |- apply(F,f) : F(A) -> F(B)

with equations for all terms:

f : A -> B, g : B -> C, h : C -> D |- compose(h,compose(f,g)) = compose(compose(h,f),g)
f : A -> B |- compose(f,1_A) = f
f : A -> B |- compose(1_B,f) = f
F |- apply(F,1_X) = 1_F(X)
f, f : A -> B, g : B -> C |- apply(F,compose(g,f)) = compose(apply(F,g),apply(F,f))

I am looking for a semi-decision procedure that will be able to prove equations in this theory given a set of hypothetical equations. It is also not clear whether a complete decision procedure exists or not: There doesn't seem to be any way to encode the word problem for groups into it. Neel Krishnaswami showed how to encode the word problem into this, so the general problem is undecidable. The associativity and identity subtheory can easily be decided using a monoid model of the theory, while the full problem is harder than congruence closure. Any references or pointers would be most welcome!

Here is an explicit example of something we would hope to be able to automatically proved:

f : X -> Y, F, G,
a : F(X) -> G(X), b : G(X) -> F(X),
c : F(Y) -> G(Y), d : G(Y) -> F(Y),
compose(a,b) = 1_F(X), compose(b,a) = 1_G(X),
compose(c,d) = 1_F(Y), compose(d,c) = 1_G(Y),
compose(c,apply(F,f)) = compose(apply(G,f),a)
|- compose(d,apply(G,f)) = compose(apply(F,f),b)

It looks to me that you can encode the word problem for groups within the theory of categories in the following way. Pick an object $X$, and then for each generator of the group introduce two morphisms $x,x' : X \to X$, and assume the equalities $x \circ x' = 1_X$ and $x' \circ x = 1_X$. Then you can define the unit to be the identity map, the composition to be the group multiplication, and the negation of a string $x\circ y\circ z$ to be the reverse primed string $z' \circ y' \circ x'$. Hence this problem is undecidable.

However, the word problem is solvable for many specific groups, so if you have more details about the problem this may help. In particular, one idea from the theory of groups which might help you a lot is that absolute presentations of finitely generated groups are solvable -- the inequations can prune the search space enough to make the theory decidable.

EDIT: One additional thought I had is that adding irrelations might still be a useful tool for you, even if the concrete models you're interested validate the equations. This is because in categorical situations you often only want "nice" equations, for some value of nice, and you can use the inequations to rule out solutions that are too evil for you. Your decision procedure might still be incomplete, but you might get a more natural characterization of the solutions it can find than "we search possible proof-trees to a depth of 7".

Good luck; that functor thing you're doing looks pretty cool!


Simple proof of Ω(n lg n) worst-case bound for uniqueness/distinctness? There are several proofs for the loglinear lower bound for the element uniqueness/distinctness problem (based on algebraic computation trees or adversarial arguments), but I'm looking for one that's simple enough to use in a first course in algorithm analysis and design. The same “level of difficulty” as the lower bound for sorting would be fine. Also, any approach (e.g., combinatorial or based on information theory) would be OK. Any suggestions?

I am not sure if I understand the question correctly, but the proof by Dobkin and Lipton [DL79] that the uniqueness problem on n numbers requires Ω(n log n) comparisons in the linear decision tree model is much easier than the stronger result in the algebraic computation tree model by Ben-Or [Ben83] (not surprisingly).

References

[Ben83]  Michael Ben-Or.  Lower bounds for algebraic computation trees.  In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983), pp. 80–86, April 1983.  http://doi.acm.org/10.1145/800061.808735

[DL79] David P. Dobkin and Richard J. Lipton.  On the complexity of computations under varying sets of primitives.  Journal of Computer and System Sciences, 18(1):86–91, Feb. 1979.  http://dx.doi.org/10.1016/0022-0000(79)90054-0


Rademacher Complexity of the Composition with an Indicator Consider the statistical learning setting where you have an arbitrary hypothesis space $\mathcal{H}$, a data space $\mathcal{Z}$, and a bounded loss function $\ell: \mathcal{H}\times \mathcal{Z} \rightarrow [0,1]$. Further, for $c\in(0,1)$, let $\mathcal{F}_c$ be the function class defined by
\begin{align}
\mathcal{F}_c := \{ z \mapsto  \mathbb{I}\{\ell(h,z) \leq c\}: h \in \mathcal{H}\}.
\end{align}
Question. Is it in any way possible to relate the Rademacher complexity of the function class $\mathcal{F}_c$, to that of $\ell \circ \mathcal{H}:= \{z\mapsto \ell(h,z): h \in \mathcal{H}\}$?
My goal is to show that when the complexity of the latter class is small, so is the complexity of the former.
Rademacher Complexity. The Rademacher complexity of a function class $\mathcal{F}$ is defined as
\begin{align}
\mathfrak{R}_n(\mathcal{F}) := \mathbb{E}\left[\sup_{f\in \mathcal{F}}\frac{1}{n} \sum_{i=1}^n \sigma_i f(z_i)\right], \quad n \in \mathbb{N},
\end{align}
where $(\sigma_i,z_i)$ are i.i.d. random variables with $(\sigma_i)$ having a Rademacher distribution.
Failed Attempt. There are results on the Rademacher complexity of the composition of functions, but these typically rely on some Lipschitzness properties, which do not hold for our function class $\mathcal{F}_c$ since we compose with an indicator function.

In general, composing a threshold function with a function class can arbitrarily increase the Rademacher complexity (so the answer to your question is negative). Let $\Omega$ be a finite set, $|\Omega|=N$, and let $F=[-a,a]^\Omega$ be the set of all functions from $\Omega$ to $[-a,a]$.
When $N\gg n$, the Rademacher complexity (either empirical or expected) of $F$ will be $\Theta(a)$. Let $F'$ be $F$ composed with the sign function; now $F'=\{-1,1\}^\Omega$ and its Rademacher complexity in this regime is $\Theta(1)$. Since $a>0$ can be taken arbitrarily small, this shows that the multiplicative gap can be arbitrarily large.


"Computing on data streams" clarification In the 1998 technical note "Computing on data streams" by Monika Rauch Henzinger , Prabhakar Raghavan , Sridar Rajagopalan (found here: http://www.eecs.harvard.edu/~michaelm/E210/datastreams.pdf)

They define a directed multigraph with node set V1 union V2 union …
union Vk, all of whose edges are directed from a node in Vi to a node
in Vi+1.

I cannot see how this allows for disconnected components?  Can anyone clarify this?

The definition says that every edge that exists has to go from some $V_i$ to $V_{i+1}$.  It doesn't say that every possible edge from $V_i$ to $V_{i+1}$ has to be there.  For example, $V_1=\{a,b\}$, $V_2=\{c,d\}$ with edges $ac$ and $bd$ gives a disconnected graph.


About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives What are the minimal conditions we know of under which we can prove that a stochastic gradient based algorithm can convergence to criticality on a non-convex objective?
Are there any necessary conditions that we know of that the objective, algorithm and the oracle have to satisfy to get convergence?

For example : I would be very interested to know of proofs which do not need to assume that the objective has bounded gradients (or that the function is upperbounded). These look very rare to satisfy in usual learning situations!  (What are natural non-convex learning situations which have bounded gradient losses?)

I am not considering methods like NSVRG which allow the algorithm to compute the exact gradients sometimes. I am specifically looking at algorithms where the gradient oracle is the only oracle being invoked and it is necessarily always noisy.

There is a lot of recent work on these questions spurred by interest in deep learning and other non-convex optimization tasks. If the objective is differentiable and smooth (i.e. if the gradient is Lipschitz), then you do not need to assume bounded gradients and there are quite a few assumptions on the noise you can adopt, and they are reviewed (with convergence results) in Khaled and Richtárik (2020) (conflict of interest: I'm a coauthor of this paper).

If the objective is not smooth, then all the analysis of SGD I know of assumes bounded subgradients possibly in addition to other regularity properties (see Davis and Drusvyatskiy (2019) and Zhang et al. (2020), although the latter does not analyze the vanilla SGD per-se). Note that if you enforce some sort of iterate normalization mechanism, feedforward ReLU networks do have bounded subgradients.

Unfortunately, even neural networks with differentiable losses are not globally smooth. For Adam and AdaGrad, it turns out that you do not need global smoothness as Défossez et al. (2020) show. There are a lot more results specifically for neural networks, but I will refrain from mentioning them since your question was about general assumptions.


A decision problem related to the problem of counting Hamiltonian cycles Define a decision problem H as follows. The input of H is a pair (G1,G2) of graphs, and the problem is to verify whether the number of Hamiltonian cycles in G1 is greater than the number of Hamiltonian cycles in G2. Is there a known complexity class C such that H is in C and H is C-hard under many-one reductions? Clearly H is in P^{#P}, and it is possible to prove that H is PP-hard under many-one reductions. But is H in PP? Or is H hard for the class P^{#P} under many-one reductions?

This is in PP.

Let $N$ be the size of the larger graph.  We will define a predicate $f(P, b)$ where $P$ is a permutation of the numbers from 1 to $N$ and $b$ is a single bit.

First, define a predicate $H(G, P)$ where $G$ is a graph (with nodes labeled from 1 to $n \leq N$) and $P$ is a permutation of the numbers from 1 to $N$.  Set $H$ to be true if and only if $P$ fixes the numbers from $n + 1$ to $N$ and if the permutation it induces of the numbers from 1 to $n$ defines a Hamiltonian cycle on $G$.  The number of $P$ for which $H(G, P)$ holds is then the number of Hamiltonian cycles in the graph.

Now, let $f(P, 0) = H(G_1, P)$ and $f(P, 1) = \overline{H(G_2, P)}$.  The number of $P, b$ pairs making $f$ 0 is then the number of Hamiltonian paths in $G_2$ plus the number of "Hamiltonian non-paths" in $G_1$, and vice versa holds for the number of pairs making $f$ 1.  Thus, whichever of these values is more common tells you which graph has more cycles, and this is precisely what PP allows you to do.


When is Ising partition function easy to compute? Consider Ising model on graph $G$ with uniform coupling strength $J$ and magnetic field $h$. I say its partition function $Z$ is easy to compute if $Z$ can be deterministically computed to arbitrary finite precision in time polynomial in size of the graph.

Here's when $Z$ is known to be easy to compute, what cases am I missing?

Arbitrary $J$

$G$ is planar, $h=0$
treewidth$(G)\le C$

Arbitrary $G$

$|J|$ small relative to girth($G$)
$|J|$ small relative to the branching factor of self-avoiding walks on $G$

I suspect it's easy to compute for all $J$ with minor-excluded $G$ and for all $G$ with $J>0$ because FPRAS exist for these cases. Also it seems $G$ with $|J|\ll |h|$ should be easy because of correlation decay, although I haven't seen either FPDAS or FPRAS in this case

Well, you seem to be missing cases with high symmetry. Basically, any case where there is only a polynomial number of energy eigenvalues and it is easy to compute the degeneracy of these levels and easy to find an eigenstate with each eigenvalue should make the partition function efficiently computable.

An example of this would be a maximally connected graph for arbitrary J and h.

Update

Since Yaroslav asked in a comment, here is the reasoning:

The partition function for the Ising model is (taking $\beta=1$) $Z_G=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$.

Notice that the first sum is over all configurations. We can separate this into two separate sums as follows:

$Z_G=\sum_{y=0}^n \sum_{x \in H_y} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$
where $H_y$ is the set of strings of Hamming weight $y$.

Next, note that every $x \in H_y$ has the same energy, due to the permutation invariance of the maximally connected graph. So we can define
$E_y = -\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right) = -J\left( \binom{y}{2}+\binom{n-y}{2} - y(n-y)\right)-h(n-2y)$.

This gives $Z_G=\sum_{y=0}^n |H_y| ~ e^{-E_y} = \sum_{y=0}^n \binom{n}{y} ~ e^{-E_y}$.

As the sum has only $n$ terms, and each term is efficiently computable, the entire partition function can be efficiently computed to a chosen precision for the maximally connected graph of $n$ vertices.

The approach outlined above makes use of the fact that there is only a polynomial number of distinct eigenvalues and that both the value and degeneracy of each level is known. This works in general, whenever these conditions are satisfied, since we can then express the partition function as $Z=\sum_{y=0}^{poly(n)} D_y ~ e^{-E_y}$, where $D_y$ is the degeneracy of level $E_y$. If both $E_y$ and $D_y$ are efficiently computable, then we can compute this sum directly in polynomial time. This is true of all Hamiltonians, not simply the Ising model.


Is finding the minimum regular expression an NP-complete problem? I am thinking of the following problem:
I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses).

Suppose by regular expression we mean some well-defined finite state machine, I am not familiar with the exact terminology, but let's agree on some class of allowed expressions.

Instead of manually crafting the expression, I want to give it a set of positive and a set of negative examples.

It should then come up with an expression that matches the + ones, rejects the - ones and is minimal in some well-defined sense (number of states in the automata?).

My questions are:

Has this problem been considered, how can it be defined in some more concrete way and can it be solved efficiently? Can we solve it in polynomial time? Is it NP complete, can we approximate it somehow? For what classes of expressions would it work? I would appreciate any pointer to textbooks, articles or such that discuss this topic.
Is this related in any way to Kolmogorov complexity?
Is this related in any way to learning? If the regular expression is consistent with my examples, by virtue of it being minimal, can we say something about its generalization power on yet unseen examples? What criterion for minimality would be more suitable for this? Which one would be more efficient? Does this have any connections with machine learning? Again any pointers would be helpful...

Sorry for the messy question ... Point me in the right direction to figure this out. Thanks !

Yes, it is NP-Hard.  Pitt and Warmuth showed that finding the smallest DFA consistent with a given sample cannot be approximated to within $OPT^k$ for any constant $k$, unless $P = NP$.

Regarding the learning question: Kearns and Valiant proved that you can encode RSA into a DFA.  So, even if the labeled examples come from the uniform distribution, being able to generalize to future examples (also even coming from the uniform distribution) would break RSA.  Hence, we think that in the worst case, having labeled examples does not help with learning a DFA (in the PAC model).  This is one of the classic cryptographic hardness results for learning.

Both of these issues are intertwined due to what we call the Occam's Razor Theorem.  It basically states that if we have a procedure for finding the smallest hypothesis from a given class that's consistent with a sample labeled by a hypothesis from the same class, then we can PAC learn that class.  So, given the RSA hardness result, we would expect that finding the smallest consistent DFA would be hard in general!

To add a positive learning result, Angluin showed that you can learn a DFA if you get to make up your own examples, but it requires the additional power being able to ask "is my current hypothesis correct?"  This was also a seminal paper in learning.

To answer your other question, this is all indeed related to Kolmogorov complexity, as the learning problem becomes easier when the canonical representation of the target DFA has low complexity.


Turing-complete computation models on graphs There are many Turing complete computation models and new ones are devised all the time.

  I am looking for Turing-complete computation models based on graphs?

As in my comment, the configuration graph (Chapter 4.1.1. of Arora-Barak) is a simple way to view a Nondeterministic Turing Machine (NTM) as a graph. The vertices of the graph are labeled by configurations: the internal state of the NTM, the contents of the tape, and head positions. There is a  directed edge from vertex $c_1$ to vertex $c_2$ if the NTM can move from $c_1$ to $c_2$ in one step.

This is especially useful for arguing about space-bounded computation. If the space used by the NTM is bounded by $s(n)$, then on input size $n$ you only need to consider a configuration graph with $O(2^{s(n)})$ vertices. Then a lot of complexity results follow from algorithms for directed $s$-$t$ connectivity: Savitch's theorem (NPSPACE = PSPACE) follows from an algorithm that uses $O(\log^2 |V|)$ space, PSPACE in EXP (or, scaling down, L in P) follows from DFS,  etc. Similarly, you can show that directed connectivity is complete for NL under L reductions, so NL is equal to L if and only if there is a logspace algorithm for directed $s$-$t$ connectivity.


What is the advantage of designing deterministic distributed algorithms? Distributed algorithms that are resilient to failures can either be deterministic or probabilistic. Take for example the consensus problem.

Paxos is deterministic in the sense that given the assumption it makes, it always works.
In constrast, randomized consensus works with a given probability.

What is the advantage of designing and using a deterministic algorithm?

The assumptions upon which deterministic algorithms rely have also a probability of holding in the reality (what is called their assumption coverage). Hence, there is always a probability that a deterministic algorithm does not work in the reality.

I will answer this from the perspective of distributed graph algorithms (distributed algorithms that solve a graph problem related to the structure of the communication network).

Here are some non-obvious reasons for designing deterministic distributed algorithms in this setting:

Subroutines in randomised algorithms. On p. 12–13 of these slides, Elkin outlines an algorithm design technique in which you can use a fast deterministic distributed algorithms as a subroutine in order to construct a fast randomised distributed algorithm. Interestingly, it is not possible to use a typical randomised algorithm as a subroutine in the same context (the error probability would be too high).
Fault tolerance. There is a mechanical translation that allows you to convert a fast deterministic distributed algorithm into a fast self-stabilising distributed algorithm (see e.g. Section 2.4 of this survey). A similar conversion is not known for randomised algorithms (and I think it is unlikely to exist in the general case).


Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?) I'm curious if there is a problem (e.g. something like perfect matchings on a given graph, number of solutions to a boolean equation, etc. for precise frameowork see JVV86) such that:

1) It is hard to sample approximately uniformly at random from the set of all solutions

2) It is easy to approximately integrate any (polynomially computable) function over the solutions.

I would also be happy with replacing 2) by the weaker:

2') It is easy to approximate the expectation of any polynomially computable function over the uniform distribution on the solutions.

My thoughts:

If 2) holds, then by integrating the constant function $1$, one can approximately count the number of solutions to the problem.
If 2) holds but 1) does not, then the problem cannot be self-reducible, as otherwise by reductions in JVV86 there would be an efficient algorithm for approximate uniform sampling by using the observation of the previous bullet.
A reasonable candidate technique for accomplishing 2) without 1) is importance sampling.
I know of situations where sampling is easy and counting is hard (so integration is hard); the case of uniformly sampling solutions to a DNF equation is explained in JVV86 section 4.
A specific candidate problem I would be interested in is the problem of sampling directed simple cycles from a digraph. (It is shown in section 5. of JVV86 that this problem is hard.) However, I know that counting the number of directed simple cycles is NP-hard, by a similar argument to that presented in JVV, and therefore so is integrating over them. However, perhaps 2') can be solved in this case?

--

Any references that seem relevant would be very appreciated, even if they are not a direct answer to my question.

There is no such problem.  If it's hard to sample, it's hard to integrate.

Here is a sketch of the reason why.  Represent every solution $x$ by a $n$-bit string $x_1,\dots,x_n$.  If you can integrate over the set of all solutions, here is an algorithm to sample from all solutions:

Count the number of solutions; call it $N_0$.  (As you say, this can be done efficiently, as it is just an integral.)  Count the number of solutions $x$ such that $x_1=1$; call it $N'_0$.  (This is an integral of the function $f(x)$ over all solutions, where $f(x_1,\dots,x_n) = x_1$, so it can be computed efficiently.)  With probability $N'_0/N_0$, set $y_1 = 1$, else set $y_1 = 0$.
Count the number of solutions $x$ such that $x_1=y_1$; call it $N_1$.  (This is another integral.)  Count the number of solutions $x$ such that $x_1=y_1$ and $x_2=1$; call it $N'_1$.  With probability $N'_1/N_1$, set $y_2 = 1$, else set $y_2 = 0$.
Count the number $N_2$ of solutions $x$ such that $x_1=y_1$ and $x_2=y_2$, and the number $N'_2$ of solutions $x$ such that $x_1=y_1$ and $x_2=y_2$ and $x_3=1$.  With probability $N'_2/N_2$, set $y_3=1$, else set $y_3=0$.
And so on.  When this procedure finishes, output $y_1,y_2,\dots,y_n$.  This will be a valid solution, sampled uniformly at random from the set of all solutions.

It's easy to see that if you have a way to compute the exact integral, you'll obtain a way to sample exactly uniformly at random.  I expect it will follow that if you can approximate the integral, you can sample approximately uniformly at random; I'll let you compute the parameters and relation between the two approximations.

You can also implement this algorithm using expectations.  Let $X$ be a r.v. that is uniformly distributed on the set of all solutions.  Set $y_1=1$ with probability $\mathbb{E}[X_1]$; set $y_2=1$ with probability $\mathbb{E}[\mathbf{1}_{X_1 = y_1} \cdot X_2] / \mathbb{E}[\mathbf{1}_{X_1 = y_1}]$; and so on.  Here I use $\mathbf{1}_{e(X)}$ to represent a function that is 1 if $e(X)$ holds, and 0 otherwise.  Why does this work?  Well, $\Pr[X_1=1] = \mathbb{E}[X_1]$, and

$$\Pr[X_2=1|X_1=y_1] = {\Pr[X_1 = y_1 \land X_2=1] \over \Pr[X_1=y_1]}
= {\mathbb{E}[\mathbf{1}_{X_1 = y_1} \cdot X_2] \over \mathbb{E}[\mathbf{1}_{X_1 = y_1}]}.$$


What's the nature of hypercomputing and relativity? Somewhere I read something like "a hypercomputer rotating around a rotating black hole" would have some esoteric properties e.g. would produce other answers than other hypercomputers and other computing. Is there any support for this, do I remember incorrectly, or is this claim known to be nonsense?

There are actually sort-of-researchy things one can say about rotating black holes. Namely it is known that sufficiently quick rotation produces time-like simple closed curves, leading to interesting questions about how to model time-travel paradoxes in complexity theory; see Aaronson and Watrous, "Closed Timelike Curves Make Quantum and Classical Computing Equivalent", arXiv:0808.2669

I have no particular opinion about combining hypercomputers with time travel that does not generalize to my opinion about hypercomputers in general, so probably it's best if I just point you to the one paper I could find that both cites Aaronson and Watrous and discusses hypercomputers:

Hajnal Andréka, István Németi, and Gergely Székely, "Closed Timelike Curves in Relativistic Computation", Parallel Processing Letters, 2012 and arXiv:1105.0047


Typechecking liveness properties of coprograms Clarification: in Total Functional Programming terminology, a program terminates with useful input, while a coprogram doesn't necessarily terminates, and repeatedly produces useful input.

I am investigating the relationship between model checking and type theory. It is straightforward to encode safety properties in the type of a program. It seems like typing coprograms would be the best way to check liveness properties, but where is the literature on the subject? I can't find any papers about the general case.

To expand on pedagand's answer: productivity is the term used for the computational dual (in some precise sense) of termination. Formally, a program f : CoData is productive if running the computation f eventually produces a constructor of CoData, and every (recursive) sub-term of that constructor is also productive.

For example

primes = filterBy prime [0..]

in haskell is productive, since there is an infinite number of prime numbers and so computing primes will always eventually produce a cons constructor.

There has been a number of works on using types to check for productivity of a given definition. One nice overview is Abel, Iteration and Coiteration Schemes for Higher-Order and Nested Datatypes from 2005.


Find all hyperplanes separating unique sets of `k` points I have a series of n points in d-dimensional continuous space.  I want to find a series of hyperplanes such that k points are below the hyperplane and that the set of k points below each hyperplane is a unique set.  It does not matter what the hyperplane is (e.g. if it connects d points or if it is another hyperplane not intersecting any points).  I can discretise the space if it helps.  "below" is defined as the negative direction for the first dimension.

The way I have approached is to try all hyperplanes defined by all sets of d points, project each point on to this hyperplane, and test if the projection is above the point.  This results in n^(d+1) complexity.

Is there a better way?  What is it?

If I understand well, you are interested in the $k$-set problem:
http://en.wikipedia.org/wiki/K-set_(geometry)

In general their number can be $O(n^{\lfloor d/2\rfloor}k^{\lceil d/2\rceil})$ and though I could not find references now, I think you can also compute them in about this much time.


Converting a pictorial representation of a directed graph to a adjacency matrix I am not sure if there is a better forum to ask this question, so I will try here.

Consider an image, say in .jpeg format, representing a directed graph, with nodes. Is there an algorithm, be it a machine learning/image processing/computer vision algorithm, that can read and process this image, and generate a potential adjacency matrix representation of this graph? What if the graph isn't planar, i.e. edges can intersect.

The graph itself could be unshaded circles representing nodes, with an arrow representing an edge from one node to another.

Obviously, as it is a supervised learning problem, some training data needs to be provided, but if this can be done, how would I go about doing it? If someone can point me to research in this problem, I'd appreciate it, as my search seems to have been to no avail.

See

Christopher Auer, Christian Bachmaier, Franz-Josef Brandenburg, Andreas Gleißner, Josef Reislhuber:
Optical Graph Recognition.
Graph Drawing 2012, pp. 529-540
http://dx.doi.org/10.1007/978-3-642-36763-2_47


SUBSET-SUM with binary - unary - "positional" encoding I don't know if my question is too simple (I'm not an expert, so feel free to delete it)

SUBSET-SUM (given a set of integers $<x_{1},...,x_n>$, find if the sum of one or more non-empty subset equal 0) is NP complete

If we use unary encoding $<x_{1},...,x_{n}> = 0^{x_{1}}1...0^{x_{n}}1$ we fall back in P (UNARY-SUBSET-SUM)
Proof: if m is the initial length of the unary input, reduce input size to $log(m)$ switching to binary representation -> simulate a nondeterministic TM that solves the SUBSET-SUM in polynomial (linear) time $O(log(m))$ -> the simulation is $O(2^{log(m)})$ -> welcome in P .

But if we map $<x_{1},...,x_{n}>$ to a number N in which each bit "positionally" represents $x_{i}$, i.e.
if $x_{i} = -1$ then set bit 0
if $x_{i} = 1$ then set bit 1
if $x_{i} = -2$ then set bit 2
if $x_{i} = 2$ then set bit 3
... and so on (for example we encode the subset $<-1,-2,2,4>$ with $10110001$ (bit 0 is on the left), the subset $<1,3,-4>$ with $0100011$, ...)
(perhaps the simplest enumeration of finite subsets of $Z$) ... I'll call it POSTIONAL-SUBSET-SUM (perhaps it has another name :-)

It seems that we cannot apply the same strategy used to prove that UNARY-SUBSET-SUM is in P
(for some inputs switching from "positional" to binary representation expands the input)

So, my question: is POSITIONAL-SUBSET-SUM in P ?
If not ... is POSITIONAL-SUBSET-SUM NP-complete ?

Thank you in advance,
Vor

If an instance of POSITIONAL-SUBSET-SUM has input length $N$, then each integer in the set $\{x_1, x_2, ..., x_n\}$ must satisfy $|x_i| \le N$, and the set itself must have size $n \le N$.  So the input length for the corresponding instance of UNARY-SUBSET-SUM is $O(N^2)$, and it is easy to see that mapping one input format to the other can be done in polynomial time.  Therefore, since UNARY-SUBSET-SUM $\in \text{P}$, we have POSITIONAL-SUBSET-SUM $\in \text{P}$ as well.


Select in union of sorted arrays: Already known? I am looking for bibliographic references for the following algorithm/problem: I named it "BiSelect" or "t-ary Select" or "Select in Union of Sorted Arrays", but I guess it was introduced before under another name?

Problem

Consider the following problem:

  Given $k$ disjoint sorted arrays $A_1,\ldots, A_k$, of respective sizes $n_1,\ldots,n_k$, and an integer $t\in[1..\sum n_i]$, what is
  the $t$-th value of their sorted union $\cup_i A_i$?

Solutions

There is a very simple and elegant algorithm running in time $O(\lg\min\{n_1,n_2,t\})$ if $k=2$: if $k=2$, just compare $A_1[t/2]$ with $A_2[t/2]$ and recurse on $A_1[t/2..t]$ and $A_2[1..t/2]$ or $A_1[1..t/2]$ and $A_2[t/2..t]$ accordingly, in both cases with parameter $t/2$ (and some minor optimizations when $n_1$ or $n_2$ are smaller than $t$).

This generalizes to a slightly more sophisticated algorithm running in time $O(k\lg t)$ for larger values of $k$, based on computing the median of the values $A_i[t/k]$ for $i\in[1..k]$: the $t/k$  smallest elements can be further ignored in the $k/2$ arrays where $A_i[t/k]$ is smaller than the median, and the elements of ranks in $[t-t/k..]$ can be further ignored in the $k/2$ other arrays, resulting in a halving of $t$ in each recurrence (and a cost of $O(k)$ for the median).

References?

I am happy with my solution(s), but I suppose that the problem (and its solution) was already known. It is related to the linear time algorithm for computing the median (by sorting groups of size $5$, and recurse on the median of their middles), but is slightly more general. I asked several colleges at Madalgo in Aarhus (Denmark), and then some others at the workshop Stringology (Rouen), without success:  I am hoping that someone more knowledgeable might help on Stack Exchange...

Motivations

Solutions to this problem have applications to Deferred Data Structure on arrays (indeed, it can be seen as an operator in a deferred data structure for the union of sorted arrays); and in a more convoluted way, to the adaptive computation of optimal prefix free codes.

Frederickson and Johnson obtained an optimal result in the 80s. Let $p=\min(k,t)$, then there exist an algorithm solves your problem in $O(k+p \log \frac{t}{p})$.

Reference

G.N. Frederickson, D.B. Johnson "The complexity of selection and ranking in x+y and matrices with sorted columns"
J. Comput. System Sci., 24 (2) (1982), pp. 197–208


Is there a theory of overloading types? There is a sound theory of overloading operators and functions realized by type classes in Haskell, and to rougher extent by traits in Rust, etc.

In mathematics however, there are many situations where one set carries the same structure in multiple ways, like the integers being a monoid under both addition and multiplication.

We normally just give these different names, but potentially one wants to abstract some tougher mathematical function, or a proof done in the type system.

In principle, one could do this the way mathematicians do it, by applying a type class to a type that associates the operations to the base type, as opposed to just the set itself with a fixed association.

Is that the "right" or "only" way to gain this flexibility?  Or is there something else?

In particular, there are a bunch of languages like Scala that do overloading of overloading rules in a rather dangerously complex ways, well even incoherent instances in Haskell probably.  It'd be interesting if there were clearer "more parametric" way to achieve the ends that motivates those design decisions.

As far as I know, there is no "right" or "only" way of associating operations of theorems to mathematical structures. Certainly there is no canonical way, and even on paper you often see sentences such as "we write foo instead of foobar when no ambiguity occurs". Even this does not prevent misunderstandings, and often clarification by the author or guesswork by the reader is required.

There has been a lot of work in disambiguating mathematical statements of the kind you describe, especially in mathematical proof assistants like Coq, Isabelle, Mizar, etc., but there are many annoyances in practice, and a lot of compromise to design a disambiguation system which insures:

Inferring reasonable statements, i.e. $1+\pi$ should be easy to recognize as a real number
Acceptable performance, i.e. $1+1$ in $\mathbb{N}$ should be recognized nigh-instantaneously, even as part of a much larger expression
Understandable error messages, i.e. $\pi+\mathbb{Z}$ should fail because $\mathbb{Z}$ is not (coercible to) a real number, rather than some crazy failure involving additive structure on quotient sets.

I can't understate how important (and difficult) point 3 is: experimentally, it's better to fail predictably than succeed in a bizarre manner, as I'm sure Scala users are aware.

Another issue is that notations like $+$ and $\cdot$ are often used to describe abstract operations like commuative monoids, but also concrete operations on the sets that support them, so if you want to write
$$ \forall\ x\ y\ z,\ (x\cdot y)\cdot z=x \cdot (y\cdot z)$$
for any monoid, you have to imagine instantiating $\cdot$ by addition in the naturals.

In general, the idea of applying an operation to a whole structure rather than just the carrier set is called the bundled approach, and it is mostly used in the mathematical components library which was used in the recent formalization of the Feit-Thompson theorem in Coq.

One big disadvantage of the bundled approach is that, as you noticed, mathematical sets often carry a great deal of structure, e.g. $\mathbb{R}$ is a group, and a ring and a field (as well as a topological space, and a great many other things) and one wants to exploit the knowledge that the additive group operation of $\mathbb{R}$ is the same as the $+$ operation of the ring, and that the order $\leq$ is compatible with them.

The unbundled approach is much more amenable to these kinds of mixins, which are more severe in mathematics than in CS, as properties need to be supported in addition to simply operations.

The Mathematical Components team has written about these issues in the 2009 paper Packaging Mathematical Structures, as have we in the context of the Lean interactive theorem prover in the paper Elaboration in Dependent Type Theory.

I feel that the question of a reasonable inference mechanism for disambiguation is still a very open question though.


Fibers of hash functions Let $\{0,1\}^{<\omega}$ denote the collection of finite binary sequences. By a hash function we mean a computable map $$h: \{0,1\}^{<\omega} \to \{0,1\}^n$$ for some fixed $n\in\omega$. Define $\text{Fib}(h) = \{h^{-1}(\{y\}) : y \in \{0,1\}^n\}$ to be the set of fibers of $h$. (That is, every element of $\text{Fib}(h)$ is the set of inputs being mapped to some fixed $y\in\{0,1\}^n$.)
It is clear that some elements of $\text{Fib}(h)$ will be infinite. For a hash function to be "fair" in some sense, we would like all fibers to be infinite. Now, given a hash function $h: \{0,1\}^{<\omega} \to \{0,1\}^n$, there is no procedure to determine whether all fibers are infinite.
Question. If we take $h$ to be one of the well-known hash functions (such as MD5, SHA-256, xxHash64,...), is it known whether all their fibers are infinite? Or, more basically, if these functions are surjective, that is, $\varnothing \notin\text{Fib}(h)$?

Cryptographic hashes
I don't think anything is known unconditionally.
We can analyze this question using a random oracle assumption.  MD5, SHA1, SHA256, etc., have a Merkle-Damgaard structure: they split the input $x$ up into blocks $x_1,\dots,x_n$, then compute
$$h_i = F(x_i,h_{i-1})$$
where $h_0$ is a constant and $h_n$ is used as the output of the hash function.  Now let's analyze this structure under the assumption that $F$ can be modelled as a random function (which is believed to be a good heuristic).
Suppose we want to construct a message $x_1,\dots,x_n$ that hashes to output $y$.  Pick $x_1,\dots,x_{n-2}$ arbitrarily; this determines $h_{n-2}$.  Now let's consider all possibilities for $x_{n-1},x_n$, and the derived values of $h_{n-1},h_n$.  If we focus on MD5, each $x_i$ is 512 bits and each $h_i$ is 128 bits.  Since $F$ is a random function, the chances that any particular value of $h_{n-1}$ is never reached by any choice of $x_{n-1}$ is $(1 - 1/2^{128})^{2^{512}} \approx 1-1/2^{384}$; therefore it is overwhelmingly likely that all $2^{128}$ possible values of $h_{n-1}$ are attainable.  Now consider all $2^{640}$ possible combinations of $(h_{n-1},x_n)$, and consider the resulting value of $h_n = F(x_n,h_{n-1})$.  Since $F$ is a random function, the chance that none of these combinations yields $h_n=y$ is $(1-1/2^{128})^{2^{640}} \approx 1/2^{512}$, i.e., vanishingly unlikely.  In conclusion: if you pick $x_1,\dots,x_{n-2}$ arbitrarily, it is overwhelmingly likely that there will exist a way to pick $x_{n-1},x_n$ so that the resulting hash function outputs the value $y$.
It follows that, for MD5, there are infinitely many $x$'s that yield the hash $y$, assuming that treating $F$ as a random function is a good model.  In other words, for MD5, we expect all fibers to be infinite.
You can do the same for other Merkle-Damgaard hashes, like SHA1 or SHA256, and you'll reach the same conclusion: for SHA1 and SHA256, we expect all fibers to be infinite.  If they're not, then there is likely some deeper structural problem with the hash ($F$ doesn't behave like a random function).
Of course none of this is a proof.  The random oracle model has well-known limitations.  But it is a heuristic that might help you form a conjecture about what we expect the answer to be.
xxHash64
For xxHash64, it is not a cryptographic hash, so it is more amenable to analysis.  The answer is yes, all fibers are infinite.  In particular, xxHash64 works with four 64-bit "accumulators".  If we are given the value of an accumulator before and after a single iteration, it is easy to find a value of the 64-bit message (input) that causes the accumulator to evolve in that way (and it is unique).  So, this makes it easy to prove that all fibers are unique: given $y$, we can choose the first $n-32$ bytes arbitrarily, then choose the last 32 bytes (using the previous observation) to force its output to be $y$, and that will give a $n$-byte message that hashes to $y$.  Since we can do that for all $n$ and all choices of the first $n-32$ bytes, all fibers are infinite.