What kind of machine learning is this? The objective is to build a classifier that produces M correct outputs when given N inputs.

Let a "sample" be M outputs and N inputs. Each output is some function some of the N inputs but the functions are not given. You only know that some of the N inputs can possibly combine to produce each of the M outputs.

Several samples are available for the machine learning algorithm to learn from, and in each sample, the functions for each output produced from what input sets are the exactly same.

It sounds like supervised learning but it doesn't seem to match exactly.

I'll provide an example:

__Sample 1:

Inputs: people = 6; salary = 100

outputs: width = 600; height = 100

__Sample 2:

Inputs: people = 3; salary = 60

outputs: width = 180; height = 60

__Sample 3:

Inputs: people = 5; salary = 101

outputs: width = 505; height = 101

The correct functions are then: width = people * salary; height = salary

This is supervised learning with a vector-valued output, i.e. learning a vector to vector mapping.  There's a large literature on this in the neural network community. One application is generating control signals for a physical device (e.g. pointing a camera based on visual input).  Here's a typical reference:

Suh, I.H. and Kim, T.W. Fuzzy membership function based neural networks with applications to the visual servoing of robot manipulators.  IEEE Transactions on Fuzzy Systems, 2(3):203-220, 1994.

From another angle, this can be viewed as multitask learning, a currently popular area in machine learning.   If one knows more about constraints among the output values, then it could usefully be viewed as a structured prediction problem, also recently popular.


Distance between regular languages I want to define a notion of "closeness" between two regular languages of finite words in $\Sigma^*$ (and/or infinite words in $\Sigma^\omega$). The basic idea is that we want two languages to be close if they don't differ by many words. We could also use the edit distance in some way... I could not find good references on this issue.

I don't call it a distance because I don't require all the distance axioms to be true (although it's not bad if they are).

A first attempt is to define $$d(L,K)=  \limsup_{n\to\infty} \frac{|L_n\Delta K_n|}{|L_n\cup K_n|}$$ where $L_n$ and $K_n$ are the restrictions of $L$ and $K$ to $\Sigma^n$, and $\Delta$ is the symmetric difference.

Is this "distance" studied? Are there references on the subject (possibly with alternative choices for distance function)? Any help or pointer would be appreciated, thanks.

As you perhaps already know, a common metric on words is the Cantor metric, which is defined as:

$$
d(l, k) = \left\{ \begin{array}{ll}
                     0 & \mbox{if } l = k \\
                     2^{-n} & \mbox{where } n = \min\{i\in\mathbb{N} \;|\;l_i \not=k_i\}
                  \end{array}
          \right.
$$

Roughly speaking, if a string is a sequence of events, the distance between two strings is $2^{-n}$, where $n$ is the first time they differ.
This can be lifted to a metric on (nonempty) languages by using the Hausdorff metric. (If you allow infinite strings, you also have to ensure that the languages are Cauchy-complete.)

This metric shows up a lot in verification. The first reference to this that I know is Alpern and Schneider 1985, Defining Liveness. (Sorry for the absence of a link, but I couldn't find an online copy.)

Jean-Eric Pin has written a survey article, Profinite Methods in Automata Theory, in which he surveys some more general metrics, and also draws some connections to Stone duality.


Solving a Number-Hopper Maze My 8-yr old has gotten bored creating conventional mazes, and has taken to creating variants that look like this:

The idea is to start from x and reach o via the normal rules.  Additionally, you can "hop" from any integer $a$ to any other integer $b$, but you must pay $|a-b|$ dollars for the privilege.  The goal is to solve the maze for the least cost.  In the example above, we could go from x to o via x-14-18-27-28-o at cost 5, but it's cheaper to go x-13-11-9-8-29-28-o for only 4.

So here is my question: what is the best solution (in terms of asymptotic running time) you can think of for solving this?  You may make any reasonable assumptions about the input format.

Note: I am using the "puzzles" tag here because I have an $O(n^2)$ answer in mind, but I'm not sure it's optimal and would like to see if someone else can improve my solution.  (Here $n$ is the number of integers in the maze.)

You can solve this in $O(n\log n)$ time using a variation of Dijkstra's algorithm. We can get away with not performing all distance updates when we visit a new node. If we visit a node $y$, we need only to update the distances of everything walkable from $y$ to 0, and to update the distances to the two nodes $y_-$ and $y_+$ with the closest values to $y$ less and greater than $y$ which have not been picked yet.

These updates are sufficient to keep the heap returning the minimum element because any closest node you jump to must have been numerically just above or just below an already visited node.

Each node gets updated to 0 at most once (if we pop out all zero distance nodes from the queue to avoid quadratic behavior), and each time we add a node, we only do O(1) other updates. Finding the values $y_-$ and $y_+$ can be done in linear time if we also keep an ordered doubly-linked list of all the nodes, sorted by their integer values. Building this doubly-linked list takes $O(n \log n)$ time, and finally the $O(n)$ updates to and pops from the heap take $O(n \log n)$ time, for a total runtime of $O(n \log n)$


Running a BPP algorithm with a half-random, half-adversarial string Consider the following model: an n-bit string r=r1...rn is chosen uniformly at random.  Next, each index i∈{1,...,n} is put into a set A with independent probability 1/2.  Finally, an adversary is allowed, for each i∈A separately, to flip ri if it wants to.

My question is this: can the resulting string (call it r') be used by an RP or BPP algorithm as its only source of randomness?  Assume that the adversary knows in advance the entire BPP algorithm, the string r, and the set A, and that it has unlimited computation time.  Also assume (obviously) that the BPP algorithm knows neither the adversary's flip decisions nor A.

I'm well-aware that there's a long line of work on precisely this sort of question, from Umesh Vazirani's work on semi-random sources (a different but related model), to more recent work on extractors, mergers, and condensers.  So my question is simply whether any of that work yields the thing I want!  The literature on weak random sources is so large, with so many subtly-different models, that someone who knows that literature can probably save me a lot of time.  Thanks in advance!

What you need is a "seeded extractor" with the following parameters: seed of length $O(\log n)$, crude randomness $n/2$, and output length $n^{\Omega(1)}$. These are known. While I'm not up to date with the most recent surveys, I believe that section 3 of Ronen's survey is enough.

The only thing you will need to show is that your source has sufficient "min-entropy", i.e. no n-bit string gets a probability of more than $2^{-n/2}$, which I think is clear in your setting.


Understanding efficient classical simulation of quantum computing I want to understand the Gottesman-Knill theorem, which basically says that using some subclass of unitary transformations (from the Clifford group) there is no quantum speed-up ie. we can simulate the system efficiently on a classical computer.

I want to understand the claims presented in http://core.ac.uk/download/pdf/11923581.pdf .
The author says that the reason that using only Clifford group brings efficient classical simulation is because the transformations in Clifford group inlcude only rotations of the Bloch sphere by multiples of $\pi/2$. He then goes on to explain that these transformations don't violate Bell's inequalities (specifically CHSH inequalities):

  In an entangled quantum system, no amount of $k\pi/2$
  transformations of one of the constituent systems will cause it to take on an
  orientation with respect to the other subsystems that is not a multiple of $\pi/2$ (unless it was so oriented initially).And as we have seen above, the statistics of compound
  states for which the difference in orientation between subsystems is a multiple of $\pi/2$
  are capable in general of being reproduced by a classical hidden variables theory.

I wan't to know if this claim is correct and first of all, I would be happy if someone explained this to me on an example. I heard that stabilizer formalism can violate Bell's inequalities so this is all weird to me.

PS. My basic intention is to have a clearer picture of why some subclass of transformations can be efficiently simulated classicaly and I thought this would be a nice way to understand it (if of course it is true). If anyone has any other ideas as to how to explain the Gottesman-Knill (besides stabilizer formalism), I would be very happy.

Brief (negative) answer

This claim is incorrect as soon as you have three (or more) qubits, as shown by the GHZ paradox, briefly described below, which shows a 3-partite Bell inequality which is beaten by a state stabilized by Pauli operators, which can be prepared and measured by Clifford operations. This paradox is named after Greenberger, Horne and Zeilinger, who found it in 1989 (2007 arXiv reprint here).

The point is that the Gottesman-Knill theorem does not care about locality, but on simplicity. The Gottesmann-Knill theorem (wiki, arXiv) gives a polynomial hidden variable theory for a state constructed with Clifford gates. Nothing prevents this theory to be nonlocal, as the GHZ state shows, but its complexity is bounded : a $n$-qubit state is described by $2n²$ binary hidden variables.

On the other hand Bell inequalities characterize local hidden variable theories, without taking care of their complexity. The violation of a Bell inequality by the GHZ states means that it cannot be described by a model where each player has access to a different local hidden variable.

Details of the GHZ paradox

The paradox can be explained by the following game, with 3 cooperating players and a referee. the referee asks a question, either $X$ or $Y$ to each player, which answers ±1 without communicating with the other players. The referee either asks $X$ to all the players or asks $X$ to one of them and $Y$ to the others. The players win if the product of their answers obeys the equality below corresponding to the question asked:
$$\begin{align}
XXX&=+1\\XYY&=-1\\YXY&=-1 \\YYX&=-1
\end{align}$$
It is easy to see that the above set of equation is not consistent, and tha no local hidden variable theory allows to win the game with a probabiliyt greater than 3/4.

On the other hand, if each of the player has a qubit of a GHZ state $|\mathrm{GHZ}\rangle:=(|000\rangle+|111\rangle)/\sqrt2$, they can win with certainty. Indeed, $|\mathrm{GHZ}\rangle$ is stabilized by the following Pauli operators :
$$\begin{align}
S_0&=+XXX\\S_1&=-XYY\\S_2&=-YXY \\S_3&=-YYX.
\end{align}$$
Therefore, measuring the Pauli operators corresponding to the referee’s question allows the players to always win the game, and therefore violate a Bell inequality with certainty. Furthermore, this state can be prepared from Clifford operations, which invalidates the idea expressed in the paragraph you cite.


Testing for finite expectation The mean of a positive random variable $X$ is either finite or infinite; define $J(X)$ to be $0$ in the former case and $1$ in the latter case. Claim: there does not exist a function $J_n$ from the iid sample of size $n$ to $\{0,1\}$ such that
$J_n\to J(X)$ in probability.
This claim (which is undoubtedly true) appears to be folklore knowledge among statisticians, but I have not been able to find a formal proof in the literature. The closest result I could find is the one by
Hawkins, which proves the impossibility of a sequential test with finite stopping time.
Can anyone give a pointer to a book/paper where the folklore claim is formally proven?

This seems to be addressed in the following paper by Joseph P. Romano, Section 3  [1] (specifically, Example 1):

Example 1 (Finite versus not finite mean). Let $X$ be $X_1, \dots, X_n$, $n$ i.i.d. observations on the real line. As remarked by Bahadur & Savage (1956), "it would be interesting to know whether, in comparable non-parametric situations, tests of the existence of $\mu$ are equally unsuccessful"; here, $\mu$ refers to the mean of an observation. So, let $P_0$ be the family of distributions on the real line with a finite mean, and let $P_1$ be the distributions without a finite mean. Condition B readily holds. [...] Hence, the conclusion of theorem 1 holds, and so it is impossible to construct a test with power greater than the size of the test.

[1] Romano, Joseph P. “On Non-Parametric Testing, the Uniform Behaviour of the t-Test, and Related Problems.” Scandinavian Journal of Statistics, vol. 31, no. 4, 2004, pp. 567–584. JSTOR, www.jstor.org/stable/4616851. Accessed 15 Sept. 2020.


What does 'gadget' mean in NP-hard reduction? This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what gadget means in 'clause gadget' or 'variable gadget'. The dictionary says a gadget is a machine or a device, but I'm not sure what colloquial meaning it has in the context of NP-complete proof.

A "gadget" is a small specialized device for some particular task. In NP-hardness proofs, when doing a reduction from problem A to problem B, the colloquial term "gadget" refers to small (partial) instances of problem B that are used to "simulate" certain objects in problem A. For example, when reducing 3SAT to 3-COLORING, clause gadgets are small graphs that are used to represent the clauses of the original formula and variable gadgets are small graphs that are used to represent the variables of the original formula. In order to ensure that the reduction is correct, the gadgets have to be graphs that can be 3-colored in very specific ways. Hence we think of these small graphs as devices that perform a specialized task.

In many cases, the main difficulty of proving NP-hardness is constructing appropriate gadgets. Sometimes these gadgets are complicated and moderately large. The creative process of creating such gadgets is sometimes called "gadgeteering."


Boolean formula balancing in $\mathsf{AC^0}$ I am looking for references about the complexity of Boolean formula balancing problem. In particular,

Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$?
Is there a simple proof of Boolean formula balancing being in $\mathsf{AC^0}$?

By "simple" I mean a proof simpler than the one I mention below, in particular I am looking for a proof which doesn't depend on Boolean formula evaluation being in $\mathsf{NC^1}$.

Background
Here all mentioned complexity classes are the uniform ones.

BFB (Boolean formula balancing):
Given a Boolean formula $\varphi$,
Find an equivalent balanced Boolean formula.

I am interested in the complexity of this problem, in particular simple proofs showing the problem is in $\mathsf{AC^0}$ (or even $\mathsf{TC^0}$ or $\mathsf{NC^1}$). The common balancing arguments like those based on Spira's lemma apply repeated structural modifications to the formula tree which seem to only give $BFB \in \mathsf{NC^2}$.
I have a proof for $BFB \in \mathsf{AC^0}$, however the proof is not simple and depends on the proof of $BFE \in \mathsf{NC^1}$.

BFE (Boolean formula evaluation)
Given a Boolean formula $\varphi$ and a truth assignment $\tau$ for variables in $\varphi$,
Does $\tau$ satisfy $\varphi$ ($\tau \vDash \varphi$)?

It is known from Sam Buss's celebrated result that Boolean formula evaluation ($BFE$) can be computed in $\mathsf{NC^1} = \mathsf{ALogTime}$ (see [Buss87] and  [BCGR92]).
It follows (quite surprisingly, at least to me) that Boolean formulas balancing ($BFB$) is also in $\mathsf{NC^1}$:
The idea is that we can hardcode $\varphi$ in the input gates of $BFE$ to obtain a formula equivalent to $\varphi$ and this is a completely syntactic operation computable in $\mathsf{AC^0}$. Since $BFE$ has balanced formulas we obtain a equivalent balanced formula for $\varphi$. In other words, the algorithm is:
$$\ulcorner \varphi \urcorner \mapsto \ulcorner \lambda \vec{p}. Eval(\ulcorner \varphi \urcorner, \vec{p} )\urcorner$$
Motivation
A simpler argument for $BFB$ being in $\mathsf{AC^0}$ (or $\mathsf{TC^0}$ or even $\mathsf{NC^1}$) would give a new simpler proof of $BFE \in \mathsf{NC^1}$ since it is easy to see that the balanced version of BFE can be solved in $\mathsf{NC^1}$ and we can compose it with $BFB$ and the result will be in $\mathsf{NC^1}$.

Questions

Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$ ($BFB\in \mathsf{AC^1}$)?
Is there a simpler argument (e.g. not relying on $BFE\in \mathsf{NC^1}$) for $BFB\in\mathsf{AC^0}$?

I am not sure if this is very relevant but in Log-Space Algorithms for Paths and Matchings in k-Trees (building on a long history of past work and specifically on Arithmetizing classes around NC1 and L by Limaye-Mahajan-Rao) we show how to find recursive balanced separators for a tree in Logspace. This bound may very well be improvable to $\mathsf{NC}^1$ if the input tree is directly given in the string representation.

The basic idea is to represent the tree as a parenthesis expression and find balanced separators for these. Notice that we find leaf separators i.e. subtrees which are balanced w.r.t. number of leaves.


Largest embeddable hypersphere given membership oracle I have a membership oracle to tell me whether a point is inside of some set, S. I would like to find the radius of the largest (origin-centered) hypersphere that is contained in S.

Do you know any good references for this problem? (I'm looking for an algorithm along with a confidence that the hypersphere is fully contained in S).

If S is convex, that this is a linear programming problem. It can as such be solved/approximated in polynomial time using the standard sequence of reductions to the ellipsoid algorithm. I do not know any reference that describe it cleanly, but the following book describe it:

Geometric Algorithms and Combinatorial Optimization (Algorithms and Combinatorics) [Paperback]
Martin Grötschel, Laszlo Lovasz, Alexander Schrijver


Approaches for Theoretical Analysis of Estimates of Probability Distributions Consider that you have a probability distribution p of some quantity X and you have obtained (via some algorithm) an estimate q of p according to some definition of closeness. Are there methods/papers that theoretically analyze and bound the estimate?

As a more concrete example, consider this paper which designs a streaming algorithm to estimate the degree distribution of a graph and defines a new notion of closeness called Relative-Hausdorff Distance (RHD). The paper experimentally validates their estimate to be close (according to RHD) to the actual distribution for several real-world graphs. I want to know if there are methods/references in literature that one can use to give provable (theoretical) guarantees of their closeness.

Disclaimer: I am biased, in that I will suggest a survey which I have written.

What you seem to be looking for can be captured under the field of distribution testing, a subfield of Property Testing initiated in TCS by the work(s) of Batu, Fortnow, Rubinfeld, Smith, and White in 2000.

Most of the works in this field answers questions of the following sort:

  Given i.i.d. sample from one (or several) unknown propbability distribution(s) over a known discrete domain, and a parameter $\varepsilon > 0$, how to distinguish between (i) the distribution has some prespecified property of interest $\mathcal{P}$ and (ii) it is at distance at least $\varepsilon$ (in total variation distance/statistical distance/$\ell_1$ distance) from every distribution that has this property?

For instance, defining the property to be the singleton $\{p\}$ (where $p$ is a known, fixed distribution of interest) you get the identity testing problem.

People have considered many variants, including varying the metric ($\ell_2$, Hellinger, Earthmover, $f$-divergences). It dates back to last year, but here is a list of references (from the second survey below).

There has been a lot of work in this area: I would suggest the following pointers and surveys:

Chapter 11 of the upcoming Introduction to Property Testing book by O. Goldreich
A Survey on Distribution Testing: Your Data is Big. But is it Blue?
(C. Canonne, 2015)
http://eccc.hpi-web.de/report/2015/063/
Taming Big Probability Distributions (R. Rubinfeld, 2012)
https://people.csail.mit.edu/ronitt/papers/xrds-rr-dist.pdf

(There are others -- see e.g. the surveys referenced by Ronitt Rubinfeld here for property testing in general, and some discussion of distribution testing.)

Some slides:
http://www.cs.columbia.edu/~ccanonne/files/talks/candidacy-2015-04-20-columbia.pdf

Now, this is trying to address the question "after coming up with a (set of) hypotheses, how to test whether they are good. (Hence the testing and tolerant testing focus.) You may also want to start from the start, and ask how to learn the distribution itself, or the relevant parameter (i.e., learning instead of testing). Not surprisingly, this becomes distribution learning (or density estimation), with all its variants (proper learning, agnostic learning, etc.). I am a bit more out of my depth there, but if that's what you are after you may want to have a look at

Learning Structured Distributions (I. Diakonikolas, 2016)
Invited Book Chapter, Handbook of Big Data, Chapman and Hall/CRC.
http://www.iliasdiakonikolas.org/distribution-learning-survey.pdf

and things like this (slightly outdated) workshop from STOC'12.


Finding distances in graphs where shortest path has a large number of nodes I was wondering what is the most efficient way to find the shortest distances between all pairs of vertices in a graph where the shortest path between those vertices has length $\geq L$.  The only way I know of so far is to choose a smaller "hitting set" $B$ such that each long shortest path contains at least one node from $B$ with high probability.  Then you can find all distances from nodes in $B$ to all nodes in the graph, and get $d(u, v) = \min_b d(u, b) + d(b, v)$.

Are there any faster methods?

Thanks!

If you accept approximations to the distances, you can take a look at distance oracles.  A good source is the paper on distance oracles by Thorup-Zwick, Approximate Distance Oracles (STOC 2001).

Distance oracles can offer constant (but approximate) look-up.


Why backward symbolic execution is so unpopular? Looking at the DARPA’s Cyber Grand Challenge, it seems that (forward) Symbolic Execution (SE) is the tool of choice for all the top teams. For example:

Mayhem, the winner of the $2 millions prize
Driller, ranked 2nd or 3rd.

Maybe this is a stupid question, but if the purpose is to find the input that reach a location, e.g. the one that causes SIGSEGV, then intuitively going backward from that location is much easier that searching from forward. However, obviously those well-known scientists did not think so, and I wonder why.

Moreover, papers about forward SE appear in all software engineering conferences, and there is a survey every 2 or 3 years. But I don't remember the last time I read a paper about backward SE (that's why there is this possibly stupid question).

Are there any challenges that make backward SE either:

significantly more difficult to implement than forward SE, or
much less scalable than forward SE, or
...

Forward SE is easier to implement, composes better with other testing methods, and thus is more scalable.

Usually, on industrial-scale workloads, it's not possible to enumerate all paths in the program under test -- there are simply too many paths. So we need some way to deal with this and sample only a subset of paths, while still having a reasonable chance of finding bugs.  With forward SE, there is an easy way to deal with this: if you have a test case, you can run the program concretely for a while, then switch to forward SE partway through execution.  Or, you can run the program concretely until it terminates, recording the path it took, and use SE to generate new inputs that will cause it to go down a similar but not identical path.  The state-of-the-art tools tend to combine fuzzing (random testing) with SE, and this approach is a nice way to enable that sort of composition.

Second, forward SE has implementation benefits.  Inevitably there are some kinds of operations that you can't or don't want to model symbolically (e.g., floating point, system calls, etc.).  With forward SE, that's no problem: you just execute the program concretely and keep only part of the state symbolic, treating the results of those operations as concrete (you concretize by forcing their inputs to match the observed concrete value, and same for the outputs).  It's usually not possible to do that concretization with backwards SE.  So forward SE allows "concolic execution", where some of the state of the program is concrete (a single value) and some is treated as symbolic (represented by some variables that we accumulate constraints on).

Finally, many modern tools are path-based: they consider a single path through the program, and construct a path expression -- a set of constraints that characterize the set of inputs that will cause the program to follow that path.  This is convenient for multiple reasons.  When you take this approach, the differences between forward SE and backwards SE largely disappear, as there is no state merging; you only consider a single path at a time.  So if you're taking this approach, in some sense you don't need to choose between the two, or the choice is inconsequential (both are basically equivalent) -- you can choose whichever you want based on which one you find a more convenient  way to think about it.


Which Integer Linear Programs are easy? While trying to solve a problem, I ended up expressing part of it as the following integer linear program. Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ are all positive integers given as part of the input. A specified subset of the variables $x_{ij}$ is set to zero, and the rest can take positive integral values:

Minimize
$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$
Subject to:
$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$
$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

I would like to know if this integer program is solvable in polynomial time; my original problem is solved if it is, and I have to try some other way if it isn't. So my question is:

How do I figure out if a certain integer linear program can be solved in polynomial time? Which integer linear programs are known to be easy? In particular, can the above program be solved in polynomial time? Could you point me to some references on this?

It is a special case of the transportation problem (or the minimum-cost flow problem), and so can be solved in polynomial time.  The coefficient matrix is totally unimodular since it is the incidence matrix of a bipartite graph.

The following Wikipedia articles could be useful.

http://en.wikipedia.org/wiki/Minimum_cost_flow_problem
http://en.wikipedia.org/wiki/Unimodular_matrix


How many DFAs accept two given strings? Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected, minimal, or non-degenerate ones); thus, $|DFA(n)| = n^{2n}2^n$.

Now consider two strings $x,y\in\Sigma^*$ and define $K(x,y)$ to be the number of elements of $DFA(n)$ that accept both $x$ and $y$.

Question: What is the complexity of computing $K(x,y)$?

This question has implications for machine learning.

Edit: Now that there's a bounty on this question, I suppose a bit more precision in the formulation is in order. For $n\ge1$, let $DFA(n)$ be the collection of $n^{2n}2^n$ automata, as defined above. For $x,y\in\{0,1\}^*$, define $K_n(x,y)$ to be the number of automata in $DFA(n)$ that accept both $x$ and $y$. Question: can $K_n(x,y)$ be computed in time $poly(n,|x|,|y|)$?

So the question is pretty brief but very interesting. I suppose that the input is $n$ in unary, and $x$ and $y$ in binary (or we have problems, as pointed out by Kai's answer).

First of all, if you are interested in knowing $K(x,y)$ approximately, then you can just generate a few random DFA's and this will give you (whp) a good approximation. (I wonder if this complexity class has a name.)

Then knowing $K(x,y)$ precisely seems like a tough problem. As pointed out in the comments by a3_nm and Kaveh, the question is equivalent to determining the number of automata for which $x$ and $y$ go to the same state. I will denote the probability that they go to the same state by $p$.

Update: Some of the things I wrote here were not true, now I fixed them.

It is easy to see that $p \ge 1/n$. We have equality, if $x$ is all 0's and $y$ is all zero except for its last bit, which is a 1. Are there other cases? I don't know. If for example $x$ is the empty string and $y=00$, then $p= \frac{n+1}{(n-1)n}$.

To simplify the problem, I even started to think about what happens if $x$ and $y$ are unary. If both are at least $n$ and their difference is divisible by $n!$, then $p=1$. Is there a simple formula for the unary version?


If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases? NP-hard problems are not used in cryptography, because they are believed to be computationally-intractable in the worst case but are not computationally-intractable in the average case.

Is there a way to identify whether a given problem instance (for example, of 3SAT) is computationally-intractable before attempting to solve it? Are there characteristics common to all pathological instances?
If we can identify the characteristics of computationally-intractable problem instances, why are those considered to be the same problem as other problem instances which are easily solvable? It seems like the real NP-Hard problem statement should be "3SAT instances with structure {x, y, z}" not just "3SAT".

For example, any 2SAT problem instance (solvable in polynomial time) can be restated as a 3SAT problem instance:

$(x_0 \lor x_1) \land (x_0 \lor \lnot x_2) = (x_0 \lor x_1 \lor x_1) \land (x_0 \lor \lnot x_2 \lor \lnot x_2)$

Generally speaking, for typical NP-complete problems, we don't have a good way to identify the computationally-intractable problems.  For instance, given an instance of SAT, we don't have any good methods to predict how long a SAT solver would take.  And for the most part we don't have anything that comes with any useful proofs.

So, in cryptography, we use cryptographic hardness assumptions, where the assumption does imply (in some sense) that we know which instances are computationally intractable.


Does Huffman coding always produce shorter codes than the Shannon code? Let $X\in\{1,2,\ldots,m\}$ be a discrete random variable with $X\sim p$.
Let $C$ be a code for $X$ with $l_i$ being the length $i$-th codeword and
let $L(C)$ be the expected length of the code.
The Shannon code produces a prefix code $C_{Sh}$ with
the lengths of the codewords $l_i =\lceil \log_2 \frac{1}{p(i)}\rceil $.
The Huffman code produces a prefix code $C_{Hu}$ which
is minimal in expected length, but
with non-explicit individual codeword lengths.
Let $H(X)$ be the entropy of $X$.
We have
$$H(X)\leq L(C_{Hu}) \leq L(C_{Sh})\leq H(X)+1.$$

My Question:
Though Huffman code produces expected lengths at least as low as
the Shannon code, are all of it's individual codewords shorter?

Follow-up Question:
If not, do the lengths of all the codewords in a Huffman code
at least satisfy the inequality:
$$ l^{Hu}_i<\log_2 \left(\frac{1}{p_i}\right)+1 ? $$

(I'm looking for proofs/counterexamples.)

This is actually problem 5.12 in Cover and Thomas's information theory textbook; show that the probability distribution ${1/12,1/4,1/3,1/3}$ gives a counterexample.

And if you want a really nice counterexample, consider the many non-isomorphic Huffman trees you can make when you have probabilities proportional to $$1,1,1,2,3,5,8,13,21,34$$ (the Fibonacci series with an extra 1). Figure out what the maximum and minimum depths are for a Huffman tree with this probability distribution. This calculation will lead to a counterexample for your follow-up question.


Is scope extrusion necessary in the Pi-calculus? What is the real benefit of scope extrusion in the Pi-calculus? I read that it adds more flexiblity to the overly restrictive prior process algebra where the scope of a newly created channel was limited. However, taking a first serious look into Pi-calculus, I came to think that this $\nu$-binder is a source of confusion between channel names and bound variables, which should be considered separately.

There are two binders in pi-calculus. One is a normal binder (just like the one in lambda calculus) in the receive $c(x).Q$ where $x$ is bound in $Q$. However, $(\nu x).P$ is a very strange binder because the scope of $x$ can extend over other parallel processes by an axiom, which is just strange, reminding me of dynamic scoping.

IMHO, this is all due to overloading variables and channel names. If we separate the notion of channel names from variables, we can make the $\nu$-binder a true binder where the variable following $\nu$ is a normal bound variable and we only need to add a reduction rule for it, which is just like the reference cell allocation in ML:
$$ (\nu x)P \longrightarrow P[c/x] $$
where $c$ is a globally fresh channel name. Then, everything made sense to me.

So, what is the benefit of having this strange axiom for scope extrusion when we can simply model it as new channel creation, which to me is much more intuitive and also closer to real implementations.

If we separate the notion of channel names from variables, we can make the ν-binder a true binder where the variable following ν is a normal bound variable and we only need to add a reduction rule for it, which is just like the reference cell allocation in ML:

(νx)P ⟶ P[c/x]

  where c is a globally fresh channel name. Then, everything made sense to me.

You are basically correct.

The reason most people don't do this is that to model your side condition "where $c$ is a globally fresh channel name", you need to give an operational semantics for the $\pi$-calculus which tracks the set of names $\Sigma$ allocated so far. I.e., the rule above would become:

\begin{array}{lcll}
  \langle\Sigma; \nu x.P\rangle & \to & \langle\Sigma \uplus \{c\}; P[c/x]\rangle & \mbox{where } c \notin \Sigma
\end{array}

Then you'd also need a condition that a configuration is well-formed if the set of names $\Sigma$ is bigger than the free names in $P$, and you'd also need to prove some equivariance/permutation lemmas that configurations and reduction sequences are stable under finite permutations of names.

You get this all for free from the $\alpha$-equivalence of $\pi$-calculus terms, at the price of introducing the (admittedly somewhat ugly) scope extrusion rule.
However, if you don't like it, you're in good company. Bob Harper does things the way you suggest in his book Practical Foundations for Programming Languages.


On the complexity of a "list" datastructure in the RAM model I am interested in the complexity of a data-structure equipped with the following operations (similar to a list):

insertion of an element at a given position within the list
deletion of an element at a given position within the list
get the value of an element at a given position within the list

For instance "insert $v_3$ at position 3"; modifies the list $e_1 e_2 e_3 e_4$
into $e_1 e_2 v_3 e_3 e_4$ and "delete at position 4" would produce the list $e_1 e_2 v_3 e_4$.

Obviously a list can be used to answer all these questions but with a $O(n)$ complexity for all three operations. We can also use an array to have 3. with $O(1)$ complexity but with $O(n)$ complexity for 1. and 2. Finally we can use a balanced tree structure to get all three operations in $O(\ln(n))$. Is there any other known structure that achieves an interesting compromise?

A second but related question: If the operation 3. is limited to retrieve the value of the first element, can we do any better than this? Of course for this a list achieves $O(n)$ for 1. and 2. but $O(1)$ for the first element. With a bit of modification I think we can make the array-based solution work in $O(n)$ for deletion of the first element but $O(1)$ for everything else. With the balanced tree approach we can make $O(\ln(n))$ for 2. and 3. and $O(1)$ for 1. Are there any structure with a better compromise here?

Finally a third (and last) question, when 3. is limited to ask for the first element, what is the best that can be achieved for the sum of the complexities of 1., 2. and 3.? Are there any known lower bounds for this? Is there a better upper bound than $O(\ln(n))$?

It appears that all of these operations can be performed in time $O(\log n/\log\log n)$ on a RAM, by combining methods for maintaining a dynamic labeling of the list elements by integers of polynomial magnitude (e.g. Bender et al, "Two Simplified Algorithms for Maintaining Order in a List", ESA 2002, https://erikdemaine.org/papers/DietzSleator_ESA2002/) with methods for ranking and unranking sets of small integers (Pătraşcu and Thorup, "Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search", FOCS 2014, https://arxiv.org/abs/1408.3045).

Operation 3 (get the value at a given position) is the simplest: it's just unranking. To insert or delete at a given position, use unranking to find which list element is there, do the insert or delete operations in your list at or near that element, use the order-maintenance structure to modify the numbering of elements, and then update the ranking-and-unranking data structure according to those modifications.

Update 2020-05-25: Kasper Green Larsen emailed me the following lower bound proof and suggested I post it here:

We can prove the following lower bound: Let $t_u$ denote the update time and $t_q$ the query time of a data structure for the list problem. Both are worst case times. Then we have the following lower bounds (when the word size is logarithmic): If $t_u$ is polylog$(n)$, then $t_q = \Omega(\log n/\log\log n)$. If $t_q$ is polylog$(n)$, then $t_u = \Omega(\log n/\log\log n)$.

The proofs follow by reduction from 1-bit partial sums; see Pătraşcu and Demaine (SODA'04) [DE: See also Fredman and Henzinger, "Lower bounds for fully dynamic connectivity problems in graphs", Algorithmica 1998]. In 1-bit partial sums, we have a bit vector of length $n$. An update flips the value of a bit. A query asks for the parity in a prefix of the array. In that paper, they prove exactly the above lower bounds for 1-bit partial sums, although their lower bound also holds if we change to amortized update and query time. The reduction I have loses that property (it can probably be fixed, see comment at the end). To give the reduction, we need to carefully examine the proof of Pătraşcu and Demaine to realize that their lower bound for partial sums holds even if the data structure is allowed to perform an arbitrary amount of preprocessing before seeing any updates or queries, as long as the word size is logarithmic, we have the lower bound (this observation is not necessary for the fix for amortized vs worst case). The initial input array in partial sums is all-0s and the sequence of operations for which they prove their lower bounds has only $n$ operations on the array.

We will reduce from 1-bit partial sums in an array of size $\sqrt n$ (and thus only $\sqrt n$ operations in the hard sequence) to the list problem in a list of up to $n$ elements. It goes as follows:
As a preprocessing step, set the list to contain $\sqrt n$ batches of the numbers $0,\dots,\sqrt{n} - 1$, i.e. the list looks like:

$$0,1,\dots,\sqrt{n}-1,0,1,\dots,\sqrt{n}-1,\dots,0,1,\dots,\sqrt{n}-1$$

with a total of $n$ elements.

Upon an update to flip the $i$th bit of the partial sums array, we remove element $i \sqrt n$ from the list.

To compute the prefix sums up to index $i$ in the array, we retrieve element $i\sqrt n$ from the list and return its parity.

Let us see that the reduction works. First observe that before any updates are made to the list, a prefix sums query for an index $i$ will retrieve the "0" element in the $i$th batch. Moreover, since we have only $\sqrt n$ operations, and all operations remove at most one element from the list, a prefix sums query for element $i$ will always retrieve an element that comes from the original $i$th batch. Finally, observe that when we delete the $(i\sqrt n)$th element of the list, all prefix sums queries for entries $j<i$ are unaffected since the first part of the list doesn't change. Also, for all queries $j\ge i$, we will now return the next element of the list since the list indices on or after $i\sqrt n$ all change by one. This next element will come from the same original batch and have a value one larger than before because we haven't deleted from this part of the original batch (this is where we use that we have $\sqrt n$ copies in each batch). Thus the answers to all queries $j\ge i$ correctly have their parity flipped.

The lower bound for 1-bit prefix sums on arrays of size $\sqrt n$ is the same as on arrays of size $n$ since $\log n$ only changes by a factor $2$. Also, the lower bound holds even if we ignore all time that was spend during preprocessing, so we get our sought lower bound.

The reason why we lose the amortized lower bound is that we need to do $n$ initial operations to create the list. Thus even if we spend $\sqrt n$ time on each of the operations after preprocessing, the amortized time to process the whole sequence is only $O(1)$ per operation. This can probably be fixed as follows: Run $\sqrt n$ copies of the hard distribution for 1-bit partial sums, where after each sequence of $\sqrt n$ operations, we re-insert all elements that have been deleted. Then we get a total of $n$ updates and queries that all have a large amortized lower bound from 1-bit prefix sums. This is not completely formal, but I'm certain it can be formalized.


Literature around NP vs EXPTIME Even if it isn't a crucial point, I don't see any literature around this question. Are there relativisation results ?

Wouldn't it be quite straightforward to prove strict inclusion by adapting non-deterministic time hierarchy theorem by exploring all possible paths of the NP machine ?

The Complexity Zoo says:

... There exist oracles relative to which $EXP=NP=ZPP$ [Hel84a], [Hel84b], [Kur85], [Hel86],....

See for example Two oracles that force a big crunch.

Perhaps the original oracle used by Dekhtyar is less powerful (and simpler): On the relativization of deterministic and nondeterministic complexity classes in Proc. Mathematical Foundations of CS 1977 ... but I don't have his paper.


Are there common names for the subtiers of PTIME? We all know P, or PTIME, I think, as a common name for the class of polynomial-time problems. Are there common names for the first few levels inside P; that is, for constant-time, linear-time, quadratic-time, cubic-time, ...? How do those names interact with common building blocks like "-SPACE" or "/poly"?

For linear-time algorithms, the Complexity Zoo gives LIN as a name, and extends that to NLIN by analogy with P and NP. In a drawing I made based on my reading of "Comparing Complexity Classes", I built the names "LINSPACE" and "NLINSPACE" according to what I think are community conventions.

If none exist, I have been imagining "KONST" for constant-time, "QUAD" for quadratic-time, and "CUB" (pronounced like "cub", "cube", or "kyubei", not sure) for cubic-time. I'm hoping that better community conventions already exist.

For examples of natural usage of these classes, I'd like to use the Chomsky hierarchy. Here, we have four extremely natural problems, and each corresponds to a level of complexity that has no nice name, but probably ought to:

REG, the class of regular languages, is also DSPACE(1), or "KONSTSPACE" in my nonce terms.
CFL $\subseteq$ DTIME($n^3$), or "CUB". This fact isn't in Complexity Zoo, which makes me feel a little strange; it's not a secret, is it? This class also closely relates to matrix multiplication, as CFL $\subseteq$ MM.
CSL is also NSPACE(n), or "NLINSPACE".
RE is fine as-is; we know quite a bit about RE.

In general, I see interesting things happening up to the third level of many hierarchies, and I think that even merely labeling up to the third level can be very useful.

I should divulge that I have a bias; I think mathematical objects should be nameable using only Unicode, and these clarified names clearly work towards that goal. Of course, "DTIME(n³)" is also still Unicode, but longer to spell, write, and say than "CUB".

As complexity classes LIN, QUAD, CUB etc are not well-behaved, and not easy to handle.

In the definition, you must freeze the model of computation (that is, deterministic Turing machines with one tape). So you will do complexity theory in a single artificial model.
The definition of these classes is fragile: In contrast to our standard complexity classes, the classes LIN, QUAD, CUB do not remain stable if you move to other models, like RAMs or Turing machine with two tapes.
There also is no natural reduction concept available on LIN, QUAD, CUB (except for reductions that are equally strong as the class itself).

Summary: All in all this means trouble, and the classes are not very appealing.


3-color a cubic graph such that a MIS receives only two colors According to Brooks'_theorem, a cubic graph (3-regular graph) containing no $K_4$ can be properly colored by three colors.  (Such a color can actually be found in linear time, which is not our primary concern.)

The questions are:

  Does there always exist a $3$-coloring that uses at most two colors for some maximum independent set of this graph?
  If the answer to question 1 is yes, can such a coloring be found in polynomial time?

It at least doesn't work out that for every maximum independent set there is a 3-coloring of the graph which 2-colors the independent set. Here is a counterexample to that stronger version of your question:

The circles represent vertices. You can also easily check that the graph is 3-regular and isn't $K_4$. Open circles define the maximum independent set which gives the counterexample. (Unfortunately, there are many other non-isomorphic maximum independent sets in this graph, and at least one of them does get 2-colored by some 3-coloring of the graph.) It's not too hard to see that each of the two "halves" that make up this graph can have an independent set of size at most three, and hence the graph as a whole has all independent sets having size at most six. Thus the independent set given here is indeed maximum.

It's fairly straightforward to show that there's no 3-coloring that 2-colors the independent set. Let's try to color the vertices in the independent set Red or Blue, leaving Green as the third color, and derive a contradiction. We'll start at the bottom: the triangle there (with the red edge) needs to have one vertex of each color. Since the top vertex in the triangle can't be Green, then, by symmetry, we can assume wlog that the bottom left vertex is assigned Green. This forces the top of that same triangle to be Red-or-Blue, and the other vertex of the triangle to be Blue-or-Red (the opposite). The bottom right vertex being Blue-or-Red then forces the vertex above it to be Red-or-Blue. The two white vertices both being Red-or-Blue force the left vertex of the inner triangle (with all black edges) to be Red-or-Blue. This in turn forces the remaining white vertex in the bottom half to be assigned Blue-or-Red. The top two white vertices in the bottom half are then Red-or-Blue and Blue-or-Red, which forces the top-most black vertex in the bottom half to be Green. Repeating this argument for the top half, we eventually get that the edge that bridge the two halves is Green on both sides, a contradiction.


How did Knuth derive A? When interpreting keys as natural numbers we can use the following formula.

\begin{equation}
h(k) = \lfloor m (kA\bmod{1}) \rfloor
\end{equation}

What I am having trouble understanding is how we choose the value of A where:

\begin{equation}
0 < A < 1
\end{equation}

According to Knuth an optimal value is:

\begin{equation}
A \thickapprox (\sqrt{5} - 1) / 2 = 0.6180339887...
\end{equation}

So my question is how did Knuth come to this and how could I calculate an optimum value for my specific data?

See exercise 9 of section 6.4 of The Art of Computer Programming.

Any irrational $A$ would work, because $\{kA\}$ breaks up a largest gap of $\{A\}, \{2A\}, \ldots, \{(k-1)A\}$ (I use the notation $\{x\}$ for $x\mod 1$).

But if $A = \phi^{-1}$ or $A = \phi^{-2}$, it has a special property: these are the only values for which neither of the two newly created gaps is more than twice as long as the other.


How can you build a coinductive memoization table for recursive functions over binary trees? The StreamMemo library for Coq illustrates how to memoize a function f : nat -> A over the natural numbers.  In particular when f (S n) = g (f n), the imemo_make shares the computation of recursive calls.

Suppose instead of natural numbers, we want to memoize recursive functions over binary trees:

Inductive binTree : Set :=
| Leaf : binTree
| Branch : binTree -> binTree -> binTree.

Suppose we have a function f : binTree -> A that is structurally recursive, meaning that there is a function g : A -> A -> A such that f (Branch x y) = g (f x) (f y).  How do we build a similar memo table for f in Coq such that the recursive computations are shared?

In Haskell, it is not too hard to build such a memo table (see MemoTrie for example) and tie-the-knot.  Clearly such memo tables are productive.  How can we arrange things to convince a dependently typed language to accept such knot tying is productive?

Although I've specified the problem in Coq, I wouldd be happy with an answer in Agda or any other dependently typed language as well.

It's easy enough to get the recursion pattern to work with sized types.
Hopefully the sharing is preserved through compilation![1]

module _ where

open import Size
open import Data.Nat

data BT (i : Size) : Set where
  Leaf : BT i
  Branch : ∀ {j : Size< i} → BT j → BT j → BT i

record Memo (A : Set) (i : Size) : Set where
  coinductive
  field
    leaf : A
    branch : ∀ {j : Size< i} → Memo (Memo A j) j

open Memo

trie : ∀ {i} {A} → (BT i → A) → Memo A i
trie f .leaf = f Leaf
trie f .branch = trie (\ l → trie \ r → f (Branch l r))

untrie : ∀ {i A} → Memo A i → BT i → A
untrie m Leaf         = m .leaf
untrie m (Branch l r) = untrie (untrie (m .branch) l) r

memo : ∀ {i A} → (BT i → A) → BT i → A
memo f = untrie (trie f)

memoFix : ∀ {A : Set} → A → (A → A → A) → ∀ {i} → BT i → A
memoFix {A} lf br = go
 where
  go h : ∀ {i} → BT i → A
  go = memo h
  h Leaf = lf
  h (Branch l r) = br (go l) (go r)

[1] https://github.com/agda/agda/issues/2918


Problem property name where an optimal solution in a graph can be used as a solution in any subgraph Suppose one is given a graph optimization problem where the optimal solution $S$ for the problem on graph $G$ can be used as a solution for any subgraph of $G$. In other words, given $S$ is an optimal solution for the problem on $G$, then $S \wedge G_i$ is a solution on $G_i$ all $G_i \subseteq G$. Is there a canonical name for this property for a graph optimization problem?

A master solution for an instance of a combinatorial problem is a solution with the property that it is optimal for any sub instance.
$~$

  Martijn van Ee, René Sitters:
  On the Complexity of Master Problems.
  Proceedings of MFCS-2015, LNCS 9235, pp 567-576
  https://link.springer.com/chapter/10.1007%2F978-3-662-48054-0_47

$~$

  Deineko, V.G., Rudolf, R., Woeginger, G.J.:
  Sometimes travelling is easy: The master tour problem.
  SIAM Journal on Discrete Mathematics 11, 1998, pp 81–93.
  https://epubs.siam.org/doi/10.1137/S0895480195281878


A topological space related to SAT: is it compact? The Satisfiability problem is, of course, a fundamental problem in theoretical CS. I was playing with one version of the problem with infinitely many variables. $\newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}}$

Basic Setup. Let $X$ be a nonempty and possibly infinite set of variables. A literal is either a variable $x \in X$ or its negation $\neg x$. A clause $c$ is a disjunction of finite number of literals. Finally, we define a formula $F$ as a set of clauses.

An assignment of $X$ is a function $\sigma : X \to \{0,1\}$. I will not explicitly define the condition for when an assignment $\sigma$ satisfies a clause; it is slightly cumbersome, and is the same as in standard SAT. Finally, an assignment satisfies a formula if it satisfies every constituent clause. Let $\sat(F)$ be the set of satisfying assignments for $F$, and let $\unsat(F)$ be the complement of $\sat(F)$.

A topological space.

Our goal is to endow the space of all assignments of $X$, call this $\Sigma$, with a topological structure. Our closed sets are of the form $\sat(F)$ where $F$ is a formula. We can verify that this is indeed a topology:

The empty formula $\emptyset$ containing no clauses is satisfied by all assignments; so $\Sigma$ is closed.
The formula $\{ x, \neg x \}$ for any $x \in X$ is a contradiction. So $\emptyset$ is closed.
Closure under arbitrary intersection. Suppose $F_{i}$ is a formula for each $i \in I$. Then $\sat \left(\bigcup_{i \in I} F_i\right) = \bigcap_{i \in I} \sat(F_i)$.
Closure under finite union. Suppose $F$ and $G$ are two formulas, and define
$$
F \vee G := \{ c \vee d \,:\, c \in F, d \in G \}.
$$
Then $\sat(F \vee G) = \sat(F) \cup \sat(G)$.This needs an argument, but I'll skip this.

Call this topology $\mathcal T$, the "satisfiability topology"(!) on $\Sigma$. Of course, the opens sets of this topology are of the form $\unsat(F)$. Moreover, I observed that the collection of open sets
$$
\{ \unsat(c) \,:\, c \text{ is a clause} \}
$$
forms a basis for $\mathcal T$. (Exercise!)

Compact? I feel that this is an interesting, if not terribly useful, way to look at things. I want to understand whether this topological space possesses traditional interesting properties like compactness, connectedness etc. In this post, we will restrict ourselves to compactness:

  Let $X$ be a countably infinite collection of variables.1 Is $\Sigma$ compact under $\mathcal T$?

One can prove the following

  Proposition. $\mathcal T$ is compact if and only for all unsatisfiable formulas $F$, there exists a finite unsatisfiable subformula $\{ c_1, c_2, \ldots, c_m \} \subseteq F$.

(Not-so-hard exercise!) After several days of thinking, I do not have much progress in answering this question. I also do not have strong evidence for or against compactness. Can you suggest some approach?

Finally, as a bonus question:

  Has such a structure been studied before?

1The restriction to countable $X$ is just for simplicity; it also feels like the next natural step from finite number of variables.

What you are doing is deriving a topological representation of a Boolean algebra. The study of representations of Boolean algebras goes back at least to Lindenbaum and Tarski who proved (in 1925, I think) that the complete, atomic Boolean algebras are isomorphic to powerset lattices.

There are however, Boolean algebras that are not complete and atomic. For example, the sequence $x_1, x_1 \land x_2, \ldots$, is a descending chain that has no limit in the Boolean algebra defined over formulas. The question of whether arbitrary Boolean algebras, such as the one you mention, also had set-based representations was solved by Marshall Stone, who put forth the maxim "always topologize" (Marshall H. Stone. The representation of Boolean algebras, 1938).

  Stone's Representation Theorem for Boolean Algebras Every Boolean algebra is isomorphic to the lattice of clopen subsets of a topological space.

The main idea is to consider what in your case are the satisfying assignments to a formula. In the general case, you consider  homomorphisms from a Boolean algebra into the two element Boolean algebra (the truth values). The inverse of $\mathit{true}$ gives you the sets of satisfying assignments, or what are called ultrafilters of the Boolean algebra. From these, one can obtain a topology called the spectrum or Stone space of a Boolean algebra. Stone provide the answer to your question too.

  The Stone space of a  Boolean algebra is a compact, totally disconnected Hausdorff space.

There have been several results that extend and generalise Stone's representation in various directions. A natural question is to ask if other families of lattices have such representations. Stone's results also apply to distributive lattices. Topological representations for arbitrary lattices were given by Alasdair Urquhart in 1978. Distributive lattices enjoy greater diversity in structure, compared to Boolean algebras and are of great interest. A different  representation for the distributive case was given by Hilary Priestley in 1970, using the idea of an ordered topological space. Instead of set-based representations, we can find poset-based representations and topologies.

The constructions in these papers have one remarkable property. Stone's construction maps not just Boolean algebras to topological spaces: structural relationships relating Boolean algebras translate into structural properties between the resulting topologies. It is a duality between categories. The entire gamut of such results is called Stone Duality. Informally, dualities give us precise translations between mathematical universes: the combinatorial world of sets, the algebraic world of lattices, the spatial world of topology and the deductive world of logic. Here are a few starting points that may help.

Chapter 11 of Introduction to Lattices and Order, by Davey and Priestley covers Stone's theorem.
Matthew Gwynne's slides  cover the theorem and give a proof of compactness. Matthew (in the comments) also suggests Introduction to Boolean Algebras by Paul Halmos.
In moving from propositional logic to modal logic, the Boolean algebra is extended with a join-preserving operator and topology with an interior.  Jónsson and Tarski's 1952 paper, Boolean Algebras with Operators is extremely readable and consistent with modern notation.
Chapter 5 of Modal Logic by Blackburn, de Rijke and Venema covers Stone's theorem and its extension to Boolean algebras with operators.
Stone Spaces by Peter Johnstone reviews such results for various other kinds of algebras.


Computing the Levenshtein distance quickly Given a huge database of allowed words (alphabetically sorted) and a word, find the word from the database that is closest to the given word in terms of Levenshtein distance.

The naive approach is, of course, to simply compute the levenshtein distance between the given word and all the words in the dictionary (we can do a binary search in the database before actually computing the distances).

I wonder if there is a more efficient solution to this problem. Maybe some heuristic that lets us reduce the number of words to search, or optimizations to the levenshtein distance algorithm.

Links to papers on the subject welcome.

What you are asking about is the problem of near-neighbor search under the edit distance. You didn't mention whether you're interested in theoretical results or heuristics, so I'll answer the former.

The edit distance is somewhat nasty to deal with for building near-neighbor search structures. The main problem is that as a metric, it behaves (sort of) like other well known bad metrics like $\ell_1$ for the purpose of dimensionality reduction and approximation. There's a rather vast body of work to read on this topic, and your best source is the set of papers by Alex Andoni: by following pointers backward (for example from his FOCS 2010 paper) you'll get a good set of sources.


Where can I find a copy of Guy Jacobson's thesis "Succinct Static Data Structures"? I'm looking for a copy of Guy Jacobson's PhD thesis: http://dl.acm.org/citation.cfm?id=915547 but I couldn't find it so far. Does anybody know where can I access it ? I really need it.

Thanks in advance.

You could try writing CMU to ask for a copy of the technical report version; Jacobson's thesis is technical report number CMU-CS-89-112.  No idea if this would actually work though.

It's also possible, but unlikely, that Jacobson's advisor has an electronic copy.

As a last resort, you (or your advisor, or your university library) can order a copy from ProQuest, the entity formerly known as University Microfilms. [Sorry, there's no way to link directly; just search for "Guy Jacobson".]  A PDF copy costs \$37; a softbound paper copy costs \$59.


Why are folded Reed Solomon Codes considered non linear? This is for my understanding. What am I missing?

Suppose we consider $s$-folded Reed-Solomon codes that are based on polynomials over a field $\mathbb{F} = \mathrm{GF}(p^t)$. Then the alphabet of those codes is of size $p^{t \cdot s}$. Hence, in order to be linear, those codes should be closed under multiplication by scalar from the field $\mathbb{F}' = \mathrm{GF}(p^{t \cdot s})$. There is no apparent reason why they should be closed under such operation.

However, it is true that they are closed under multiplication by scalar from $\mathbb{F}$. In other words, the codes are $\mathbb{F}$-linear.


Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$? My understanding of the Presburger arithmetic decision problem is that it requires doubly-exponential time, but only singly-exponential space, meaning that it is in $EXPSPACE \setminus EXP$.  Obviously, if this set is not empty, then $P \subsetneq PSPACE$, solving a major open problem, so my understanding is probably wrong.  Where did my reasoning fail?

The problem of determining whether a sentence of Presburger arithmetic is true is in between 2-NEXP and 2-EXPSPACE. When the number of quantifier alternations is fixed and at least two, the problem is in between NEXP and EXPSPACE. The existential fragment is NP-complete. For more details, see e.g. Christoph Haase, Subclasses of Presburger Arithmetic and the Weak EXP Hierarchy, CSL/LICS 2014.


Generalizing the "median trick" to higher dimensions? For randomized algorithms $\mathcal{A}$ taking real values, the "median trick" is a simple way to reduce the probability of failure to any threshold $\delta > 0$, at the cost of only a multiplicative $t=O(\log\frac{1}{\delta})$ overhead.
Namely, if the $\mathcal{A}$'s output falls into a "good range" $I=[a,b]$ with probability (at least) $2/3$, then running independent copies $\mathcal{A}_1,\dots,\mathcal{A}_t$ and taking the median of their outputs $a_1,\dots,a_t$ will result in a value falling in $I$ with probability at least $1-\delta$ by Chernoff/Hoeffding bounds.

Is there any generalization of this "trick" to higher dimensions, say $\mathbb{R}^d$, where the good range is now a convex set (or a ball, or any sufficiently nice and structured set)? That is, given a randomized algorithm $\mathcal{A}$ outputting values in $\mathbb{R}^d$, and a "good set" $S\subseteq \mathbb{R}^d$ such that $\mathbb{P}_r\{ \mathcal{A}(x,r) \in S \} \geq 2/3$ for all $x$, how can one boost the probability of success to $1-\delta$ with only a logarithmic cost in $1/\delta$?

(Phrased differently: given fixed, arbirary $a_1,\dots, a_t\in \mathbb{R}^d$ with the guarantee that at least $\frac{2t}{3}$ of the $a_i$'s belong to $S$, is there a procedure outputting a value from $S$? If so, is there an efficient one?)

And what is the minimum set of assumptions one needs on $S$ for the above to be achievable?

Sorry if this turns out to be trivial -- I couldn't find a reference on this question...

What you're looking for is almost the same a robust central tendency: a way of reducing a cloud of data points to a single point, such that if many of the data points are close to some "ground truth" but the rest of them are arbitrarily far away, then your output will also be close to the ground truth. The "breakdown point" of such a method is the fraction of arbitrarily-bad outliers it can tolerate. The difference is that in your case you want to replace "close to" by "within the convex hull of".

One way to capture this is with the notion of Tukey depth. A point has Tukey depth $p$ (with respect to a given set of $n$ data points) if every halfspace containing the given point also contains at least $pn$ data points. If there is a good convex subspace that you want to be inside, then a point with Tukey depth $p$ will be inside it as long as there are at least $(1-p)n$ of the data points inside it. So the breakdown point of this method is the largest value of $p$ that you can attain.

Unfortunately this breakdown point is $1/(d+1)$, not close to 1/2, both for Tukey depth and for your problem. Here's why: if your data are clustered near the $d+1$ vertices of a simplex, then as long as fewer than $1/(d+1)$ fraction of them are outliers (but you don't know which ones) then any point in the simplex is safe to pick as it will always be within the convex hull of the non-outliers. But if more than $1/(d+1)$ of the points can be outliers, there is nowhere that is safe to pick: whichever point in the simplex you choose, the outliers could be all of the points from the nearest simplex vertex, and you'd be outside the hull of the non-outliers.

If you're willing to tolerate a worse breakdown point, more like $O(1/d^2)$, there's a randomized method for finding a deep point that's polynomial in both $n$ and $d$: see my paper

Approximating center points with iterated Radon points,
K. Clarkson, D. Eppstein, G.L. Miller, C. Sturtivant, and S.-H. Teng,
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 91–98,
Int. J. Comp. Geom. & Appl. 6 (3): 357–377, 1996,
http://kenclarkson.org/center/p.pdf


Algorithmic Complexity Attacks I am studying algorithm construction and weaknesses to resource consumption.  One vulnerability that really caught my eye was the Apache Range Header DoS Vulnerability.  The following quote was taken from Apache developers discussing the flaw:

  From looking at the code, I think the problem is the bucket structs.
  With N the number of requested ranges, the initial brigade is
  partitioned into 2*N buckets at the maximum. Then those buckets are
  copied into the output brigade N times, which means that O(N^2)
  buckets are created. The data is not copied, and only N "A-B" strings
  are allocated from the pool.

Does anyone else know of other resources about building algorithms that are resistant to resource exhaustion attacks?   Does anyone of interesting papers related to Algorithmic analysis and susceptibility to resource exhaustion?  Do you know of other resource consumption vulnerabilities that where caused by flawed algorithms?

Do you know of other resource consumption vulnerabilities that were caused by flawed algorithms?

this can be a subtle issue because basically any algorithm that processes requests with responses is subject to a Denial of Service attack vulnerability due to being overwhelmed with requests, such that even efficient algorithms can be overwhelmed. in a sense the algorithms are not considered "flawed" until an attacker exploits them, during an ongoing, adaptive race between hackers and researchers employing countermeasures.

one famous example from history is the so-called Ping of Death which led to large attacks in 2000 against Yahoo, CNN, eBay, Dell, & Amazon by the hacker "mafiaboy". ref [1] lists the 10 most famous attacks of the past 25 years several of which are DoS attacks. however, some other algorithms are not discovered to be inefficient until hackers find methods/attack vectors for "bogging them down" and the Apache vulnerability you mention apparently fits into that category.

there are large amounts of research into DoS prevention techniques eg refs below.

[1] Hackers’ Most Destructive Attacks, DailyBeast

[2] Preventing Internet Denial-of-Service with Capabilities Anderson, Roscoe, Wetherall

[3] Denial of service attacks and how to defend against them Razmov

[4] Internet denial of service attacks and defense mechanisms Abliz


Complexity of solving systems of linear equations with hash preimages Introduction: I'm researching a decision problem that I thought was in NP because there are certificates for its instances that have a polynomial number of elements. However, I realized that there are subproblems one can construct by using hash functions that would probably make this problem fall in a higher complexity class.

Problem: Let $H$ be an arbitrary cryptographic hash function. The goal is to solve the following system of linear equations with integer coefficients

$$\boldsymbol A \boldsymbol x = \boldsymbol c$$

$$\boldsymbol x = \left[\begin{array}{c}
x_1 \\
\vdots \\
x_n
\end{array}\right]$$

where the values assigned to the variables are required to be integers and are restricted by the following constraints

$$H(x_i) = z_i, \hspace{1cm} \text{for } i = 1 \dots n$$

where $z_i$ are arbitrary but fixed hashes.

Question: What is the time complexity of finding values for $\boldsymbol x$ that fulfill these constraints? Are there any references that look into problems similar to this one?

Notes: The problem of finding an $x$ that fulfills $H(x) = z$ for an arbitrary $z$ is in $O(1)$ because all outputs of $H$ have the same size and one could have a table with a precomputed preimage for each hash. Therefore, the additional difficulty would stem from the fact that each hash can have multiple preimages with unbounded sizes. It's pretty easy to see that if any solvable system like this had polynomial-sized solutions the problem would belong to NP. Nevertheless, the fact that there probably isn't any upper bound on the size of the solutions probably means that the problem is infeasible but I can't think of any obvious way to prove this.

It depends what you mean by "arbitrary cryptographic hash function".  If you care about practical cryptography, I think the most natural interpretation is to model $H$ as a random oracle (i.e., the random oracle model for hash functions).

In this setting, the problem is hard.  As a lower bound, it requires exponential running time.

To prove this, let $u=(1,2,4,\dots,2^{n-1})$ and let $A$ be a $n\times n$ matrix of rank $n-1$ such that $\operatorname{Ker} A$ is spanned by $u$.  (Such a matrix exists.)  Let $c=0$.  Then the problem amounts to: find a constant $\alpha \in \mathbb{Z}$ such that $x=\alpha u$ and $H(x_i)=z_i$ for $i=1,\dots,n$.  Treating $H$ as a random oracle, any candidate value of $\alpha$ has a $1/d^n$ chance of meeting all the $H(x_i)=z_i$ requirements, where $d$ is the size of the range of $H$; so you'll need to try about $d^n$ different values of $\alpha$ before finding the first that is satisfactory [*].  The size of all integers is at most $n \log d = \Theta(n)$ bits, so the time to try each is polynomial.  Thus, the total running time is $2^{\Omega(n)}$ for this case.

I don't know what the complexity is.  I suspect that for a random matrix $A$ you might be able to solve this by enumerating solutions to $Ax=c$.  You can enumerate solutions using Hermite normal form.  This equation has either 0 solutions, 1 solution, or infinitely many solutions.  If it has no solutions, you can immediately conclude that your problem has no solutions.  If it has 1 solution, you can find it with Hermite normal form and then test whether it meets your $H(x_i)=z_i$ requirement.  If it has infinitely many solutions, you can use Hermite normal form to sample from the space of all solutions and check for each whether it satisfies all of the constraints.  There are degenerate cases where this approach might be very inefficient or may never terminate. I suspect for a random matrix $A$ it will typically take at most exponential time, but I have no proof of this.

Alternatively, suppose you intended for "arbitrary cryptographic hash function" to mean that $H$ is an arbitrary function from the integers to a finite domain.  I'll assume $H$ is represented as an oracle.

In this case, the problem is undecidable: there is no algorithm that is guaranteed to always terminate and always output the correct answer.

To show this, it suffices to consider the one-dimensional case, $n=1$, where $A=0$, $c=0$, $z=1$.  Then the problem amounts to: find $x \in \mathbb{Z}$ such that $H(x)=1$.  Consider running the algorithm with the hash function $H_0$ defined by $H_0(x)=0$ for all $x$.  Let $m$ be the largest number that is queried to the oracle (i.e., the largest number that we use as input to $H_0$) when the algorithm is run with $H_0$.  Define $H_1$ by $H_0(x) = 0$ if $x\le m$, or $1$ otherwise.  Then the algorithm's behavior on $H_0$ and $H_1$ is identical, so the algorithm is wrong on at least one of those two.

If neither of those capture what you intended by "arbitrary  cryptographic hash function", then you'll need to define your setting more precisely (what are the inputs? how is $H$ modelled?  how is it represented and provided as input to the algorithm? etc.).

Footnote [*]: I over-simplified a little bit: technically, the attacker could potentially gain up to a $2n$ improvement in success probability by using the fact that $H(\alpha u)$ tells you something about $H(2 \alpha u)$.  But this can be accounted for in the proof by treating each query $w$ to $H$ as providing $2n$ guesses at a good $\alpha$, for free (namely, $w/2^{n-1},\dots,w/2,w,2w,\dots,2^{n-1}w$).  In this way, one can adapt the proof to show that you'll need at least about $d^n/(2n)$ queries to $H$ to have a good chance of finding a valid solution, and that is still $2^{\Omega(n)}$.


Does cryptography have an inherent thermodynamic cost? Reversible computing is a computational model that only allows
thermodynamically reversible operations.  According to Landauer's
principle, which states that erasing a bit of information releases $kT
\ln(2)$ joules of heat, this rules out transition functions that are not
one-to-one (e.g., the Boolean AND and OR operators).  It is well known
that quantum computation is inherently reversible because the allowed
operations in quantum computation are represented by unitary matrices.

This question is about cryptography.  Informally, the notion of "reversibility" seems anathema to the fundamental goals of cryptography, thus suggesting the question: "Does cryptography have an inherent thermodynamic cost?"

I believe that this is a different question than, "Can everything be done in quantum?"

In his lecture notes, Dr. Preskill states,  "There is a general strategy for simulating an irreversible computation on a reversible computer. Each irreversible gate can be simulated by a Toffoli gate by fixing inputs and ignoring outputs.  We accumulate and save all 'garbage' output bits that are needed to reverse the steps of the computation."

This suggests that these reversible quantum simulations of irreversible operations take an input as well as some "scratch" space. Then, the operation generates output along with some "dirty" scratch bits. The operations are all reversible with respect to the output plus garbage bits, but at some point, the garbage bits are "thrown away" and not considered further.

Since cryptography depends on the existence of trapdoor one-way
functions, an alternative statement of the question might be, "Are
there any trapdoor one-way functions that can be implemented using
only reversible logical operations, without additional scratch space?"  If so, is it also possible to COMPUTE an arbitrary trapdoor one-way function using only reversible operations (and no scratch space)?

As I mentioned in my comment above, and as you allude to in the question, every computation can be made reversible, and by simply retaining the extra bits, there is no inherent thermodynamic cost.

Every circuit generated by using Toffoli gates and ancillas to replace irreversible gates becomes as efficient to reverse as it is to compute assuming you have access to all output bits. This is clearly not the case for the functions considered in cryptography, since many ancillae are used and discarded. It is by keeping secret this extra bits that makes the computation hard to reverse.

However, by computing the function reversibly, making a copy of the subset of bits corresponding to the output, and then inverting the function the total energy cost for computing and inverting the function will be zero, while the only cost incurred will be in making the copy of the output bits, which depends only on the number of output bits and not the function being computed. This is clearly the best you can do, since it costs the same energy as simply writing the output string to an empty register.

Turning to your restated question:

  "Are there any trapdoor one-way
  functions that can be implemented
  using only reversible logical
  operations, without additional scratch
  space?"

The answer is trivially no. If you apply the inverse of each gate in reverse order you compute the inverse of the function. Assuming a model where gates act on a fixed number of qubits at a time, then the inverse of each elementary reversible gate can be applied in constant time. Hence such a function is as easy to invert as to compute (up to a multiplicative constant), and hence is not a trapdoor function.


Using an oracle to find a vector $b$ for which $Ax=b$ has a solution There is an oracle built around a hidden $m\times n$ matrix $A$ all of whose entries are 0 or 1, where $m>n$.   The oracle takes as input an integer vector $b$ with positive entries, and answers as follows:

The oracle answers YES, if there exists a real vector $x$ with $Ax=b$.
The oracle answers NO, if no such real vector $x$ exists.

It is furthermore known that there exists some YES-vector $b$, whose entries are all bounded by the known (explicitly given) constant $c$.

  Question: What conditions on $A$ would enable us to find a YES-vector $b$ in polynomial time?

I'm actually working on a slightly different problem, and the context is a bit hard to explain: in my problem matrix $A$ represents an incidence matrix for a minimum edge clique cover of a graph $G$. Each column of $A$ is a (maximal) clique in $G$, with a $1$ in entry $i,j$ if vertex $i$ is in clique $j$. Ideally, such an $A$ would satisfy the problem statement.

I am interested in deterministic algorithms, not a randomized algorithm.

I was wondering which search terms I should put into Google, and what type of literature exists on this problem.

We can make one observation: adaptive access to the oracle doesn't help.  You might as well fix in advance the set of queries you plan to make to the oracle.  So, the condition is that there has to exist a polynomial-size set of candidate values of $b$, such that it is likely that at least one of those will work.

Why doesn't adaptive access help?  That's because you can assume without loss of generality that every oracle query returns 0.  In other words, given an adaptive algorithm for generating queries, run that algorithm with a fake oracle that always returns "no solution", record the list of queries it makes, and there's a list of candidate values of $b$ that a non-adaptive algorithm can use.  This yields a non-adaptive algorithm that performs as well as the adaptive algorithm.

As a consequence, since you want a deterministic algorithm that always succeeds, a necessary and sufficient condition is that there must exist a polynomial-sized, polynomial-time-constructible set $B \subset \mathbb{Z}_{>0}^m$ such that for all possible matrices $A$ there exists at least one $b \in B$ that works for $A$ (i.e., such that there exists $x$ so that $Ax=b$).


Complexity of a GLR parser on an ambiguous grammar Let's consider the following expression grammar that is ambiguous:

$E ::= E + E~|~a$

Although GLR parsing (recognition actually, I'm not interested in parse tree creation)
is worst case $O(n^3)$, but how does a GLR parser behaves on this grammar that is
not worst-case?

I suspect the complexity is $O(n^2)$ or close to it. Can anyone reason about the
complexity of this grammar in a generalized setting like GLR that explores all the paths?

This example grammar is worst case ambiguity, unless I do not
understand what you mean by worst case ambiguity. Why do you think it
should not be? Try to analyse $a+a+a+a+a$.

It's time complexity is $O(n^3)$ with any general CF parser, such as
CKY, Earley, GLR, GLL, etc. However, you need only $O(n^2)$ space if
you do not keep parse-tree information (though I would have to check how you manage not to keep it in GLR ... it may require minor modification).

But then, if you are not interested in parse-trees, but only in
recognition, you should forget ambiguities, and just change it for a
regular grammar that recognizes the same language, in linear time.

Reasonning with GLR is a bit of a pain. But you can do it easily
enough with CKY. There is no essential difference in principle (see
the second part of my answer to a previous question), but reasonning
with the more complex construction of GLR is more obfuscated.

Alternatively, take the code of a GLR parser, and add counters in
proper places. Then run a few example and you will see that it checks
with $O(n^3)$. The last reference of the question I answered actually
did that (though I do not recall which general CF parser flavors they
tried).

Answering comments, and sketching a proof:

Regarding worst case grammar, you suggest $S \rightarrow SSS \mid SS
\mid a$ given in a paper by Mark Johnson.  I do not have the paper
handy, but my guess is that he uses the $S \rightarrow SSS$ rule to
show that the complexity will $O(n^4)$ unless specific steps are taken
to binarize this rule (there are actually 2 ways to do it). The reason
is that the polynomial complexity exponent can be the length of the
longest right hand side (RHS), at least in non terminals. So he
deliberately uses a RHS with 3 non-terminals. Your example grammar
does not have that problem, and in that sense you can indeed consider
that it is not as bad. Johnson's example would be even worse with a RHS of length 4, or more.

I questioned your "not a worst case" statement because, it is easy to bring time complexity
down to $O(n^3)$ by binarization of right-hand sides, which is straightforward and changes
the trees only in an obvious and very readable way. However, in the
current state of the art, you cannot go below $O(n^3)$, unless you use
very complex recognition techniques that do not give you parse trees
and are based on a reduction to matrix multiplication as
shown by Leslie Valiant in 1974.  Since then, the theoretical
complexity of these multiplication algorithms has gone down fron the
$O(n^{2.807})$ of Strassen algorithm to $O(n^{2.373})$ of Williams
algorithm, though those faster than Strassen are unusable in practice.
It is not known (afaik) whether this bound can be brought down further.
These bounds can certainly apply to your grammar, as well as they do
to all others, but I would not call it "parsing".

Going back to the more classical parsing algorithms, I guess one can
give a common proof based on the following remark: all classical
parsing algorithms are based on the (non-deterministic) pushdown
automaton (PDA) model (it is not always very visible, but it is always
there). The deterministic algorithms, like precedence, LR(k) or LL(k)
and their variants are just deterministic PDAs built in some
systematic way (when possible), that correspond to a technique using
the grammar to walk the (unique) parse-tree as efficiently as
possible. These techniques are limited to subclasses of CF grammars
and languages.

The general context-free parsing algorithms can handle all CF grammars
and languages. They are usually built using the very same techniques,
but the consruction accepts that there may be conflicts in the the
steps to be applied. These conflicts are simply non-deterministic
choices. But the construction is basically the same as in the deterministic case. That means that
the resulting non-deterministic PDA can walk all possible parse-trees,
sometimes having to walk parse-tree fragments that do not belong to a
full parse-tree (for example in unambiguous CF languages that are not
deterministic).

So these algorithms walk all parse-trees, independently of whether
they actually produce these parse-trees as output. There may be
exponentially many (even sometimes infinitely many) such parse trees.
The General CF parsers use a tabular (dynamic programming /
memoization) technique to share computation, in order to do the work
a bit faster. They all use the same tabular technique (from an
abstract point of view) and get all the same worst case complexity
$O(n^3)$. They may however differ on some example, for example if a
grammar falls in the domain wherhe one PDA construction gives a
dterministic PDA, while another does not. But they all have $O(n^3)$
time complexity when there are exponentially many parse trees as in
your example.

I do not believe I ever encountered a parsing algorithm that does not
fall in this schematic description (up to some bells and whistles). This is essentially the basis of the work in the Billot & Lang paper cited above.

Now, as I said, if you are not interested in parse-tree, you can
always modify one of these algorithms to do better in some cases. For
example, as I said, the rules $S \rightarrow SS \mid a$ could be
noticed by the recognizer (no longer parser) construction
technique, and replaced by the simpler rules $S \rightarrow aS \mid
a$. But then it is no longer the same "parsing" algorithm.

For an analysis of tree sharing into forests and the effect on parsing complexity, you may want to read
"Observations on Context Free Parsing" by Beau Sheil In Statistical
Methods in Linguistics, 1976:71-109. The point is that all general CF
parsing algorithms walk this shared forest completely. And it has size
$O(n^3)$ for your example grammar.


What tools do you use to write papers? What tools do you use to write
  papers?

From the little experience that I have, theoreticians spend a large amount of time writing and refining papers, besides actually being creative. That is, communicating their work to other people. Maybe papers are not the right way to do so, but that should be left for another discussion. In any case, it seems like one wants to reduce the time spent writing up the results by using as good software tools as possible. So, this questions aims at finding out about some hidden treasures out there.

I think most of us use LaTeX and some system for organizing paper references. But there are also vim/emacs and some very nifty libraries which have been a huge time saver for me. Therefore I wanted to know about the setup you use for writing papers, and maybe also some things you've tried to learn and didn't work for you. I would be especially interested in things which might not be as well known but have turned out to speed up things, even if it is, say, some very specific software for drawing graphs or auto-completion features.

Don Knuth tells about his setup in an interview here. Search for the question "What set of tools do you use [...]".

UPDATE: Sadeq pointed me to a discussion about tools for drawing diagrams here.

In addition to what others say, I like the package todonotes for LaTeX that allows to have colorful reminders of what remains to do in the text.


fast range summable hash functions I'm finding is there any range summable hash function.

ADD: The hash function I refer to is the one that is typically used in tug-of-war sketch(AMS sketch). Please refer to The space complexity of approximating the frequency moments.

Improved range-summable random variable construction algorithms gives one for any k-wise independence,
but its author Martin J. Strauss shows it is incorrect from his homepage.

The only one I can find is from One-Pass Wavelet Decompositions of Data Streams, where a 4-wise one is given. It used second-order Reed-Muller hash functions.

Are there any other range summable hash functions with 4 or more independence?

I have found the newest one that gives 7-wise independence using MR code, also two others based on BCH and EH code with 3-wise independence. They are tested to be good enough for AMS sketch in this paper


Given a set of distances (no info regarding what points the distances correspond to) from a complete graph, is the realization of the graph unique? There are $n$ points in $R^2$ (i.e. the 2D real space). We can think of them as a complete graph where edge weights correspond to the distance between points.

Let $D$ be the distance matrix between all pairs of points, such that entry $D_{ij}$ corresponds to the distance between points $i$ and $j$. This matrix is of size $n \times n$ and the upper-triangle contains the distances between unique pairings of points.

Now imagine I put the elements from the upper triangle into a set, such that you no longer know which pairs of points produce the distance values. This is essentially the set of edge weights, with no information regarding the relationship between the weight and the edge the weight belongs to.

If you are given two sets and they are identical, does this imply the graphs corresponding to each set are also essentially the same?

I think the following example with four points answers your question (though it gives multi-sets of distances). See Reconstructing Sets From Interpoint Distances by Skiena, Smith, and Lemke for more information.


Deciding whether a context-free language is regular Does anyone know whether the following decision problem is decidable:

Given a context-free language $L$, is $L$ regular?

Here $L$ can be expressed, e.g., using a context-free grammar. Does anyone know an algorithm that takes as input a context-free grammar $G$ and outputs an equivalent regular grammar $G'$, i.e. $L(G) = L(G')$, if $L(G)$ is regular?

Regularity is decidable for DCFL, but it is undecidable for general Context-Free Languages.

Regarding DCFL, I have two references (from Hopcroft+Ullman 79):

A regularity test for pushdown machines,  R.E. Stearns, Information and Control, 1967 (full text by clicking on the page)
Regularity and Related Problems for Deterministic Pushdown Automata, Leslie G. Valiant, JACM 1975

Regarding a procedure to get a regular version when possible, I have no suggestion.


Complexity of determining unique elements of each cycle in a permutation It is a well known fact that a permutation is a set of cycles, and that one can find all cycles of a permutation in $O(n)$ time, where $n$ is the length of the permutation.

But suppose that we know that the number of cycles in the permutation is less than a fixed number $k$. Can we find $k$ distinct elements belonging to the $k$ cycles in less than $O(n)$ time? Clearly, if $k=1$ this is true. But is it true for all $k$?

More specifically, suppose we know that $k$ is $O(log{\text{ n}})$, does this information help in anyway? I'm interested in understanding the time complexity of this problem, but if it's possible to give an efficient randomized algorithm for this problem, that will also be interesting in itself.

I have tried to find papers on this topic without any luck so any relevant paper or material will be greatly appreciated.

Even for $k=2$ when the instance may have two cycles of length $n/2$,
any sublinear algorithm can only build chains of length $\ll n/4$, so no deterministic algorithm can guarantee that the two vertices it outputs belong to distinct cycles.

I doubt (though I am not sure and do not have a proof) that the problem would admit a solution in sublinear expected time even for algorithms with probabilistic guarantees.


Minimal Number of Symbols in Context-Free Grammar for a Special One-Letter Language Given is the language
$$L_n = \{a^n\},$$
where $n$ is a natural number and $a$ is a letter. What are the productions/rules of a minimal context-free grammar according to the number of symbols of the productions (e.g. the number of symbols of the productions $\{ S \rightarrow a, S \rightarrow aS \}$ is 7).

For $n = 1$ the (only) rule is $\{ S \rightarrow a \}$ and for $n = 2$ we get $\{ S \rightarrow aa \}$, which can be proved easily. The number of symbols are $3$ and $4$, respectively. You may think, that $\{ S \rightarrow a^n \}$ ($2 + n$ Symbols) is always the shortest rule according the number of symbols for $L_n$ but $L_{10} = \{a^{10}\}$ can be constructed by $\{ S \rightarrow A^5, A \rightarrow aa \}$ that has only $11$ symbols (instead of $2 + 10 = 12$). This looks like an optimal compression problem.

This is essentially the problem of "addition chains", discussed in great detail in many papers and in Knuth's The Art of Computer Programming.  In brief:  the problem as you have stated it is not known to be NP-hard, but nobody knows an efficient algorithm to find the absolutely minimum.  However, there are good algorithms that come reasonably close to the minimum.


Is simply typed lambda calculus equivalent to primitive recursive functions It's well known that the computation models untyped lambda calculus and $\mu$-recursive function are equivalent in terms of computability (in fact they are both Turing complete.) It is also well known that, among some of the variations of them, the simply typed lambda calculus ($\lambda_{\rightarrow}$) and the primitive recursive function ($R_p$), are less powerful (i.e. neither of them is Turing complete.)

Since the intuition of the essential restrictions applied in both cases feels similar, I have the instinct that the class of functions computable by either of them is the same, i.e. $\lambda_{\rightarrow} \cong R_p $; but I cannot find any literature discussing this issue myself after a quick search.

Thus, I'd like to ask 1) whether simply typed lambda calculus and primitive recursive function are equivalent and 2) if so, is there any literature that I can have a look at discussing this?

The simply-typed λ-calculus with β-equality at type (o → o) → o → o  (which can be seen as type of the natural numbers, whenever o is any base type) can define exactly the extended polynomials (= polynomials with if-then-else), see (1). Other notions of equality change this. (2) shows that using $\beta\eta$-equality leads to a larger class of definable functions, although no simple
characterisation is given.

Schwichtenberg's result
can be generalised to functions on words over the binary alphabet,
represented as type (o → o) → ((o → o) → o → o), see (3), and also to
free algebras, see (4).

H. Schwichtenberg, Definierbare Funktionen im λ-Kalkül mit Typen.
M. Zakrzewski, Definable Functions in the Simply Typed λ-Calculus.
M. Zaionc, Word operation definable in the typed lambda-calculus.
M. Zaionc, λ-Definability on free algebras.


What is the reason for using a "Lines-Oracle" in the PCP Theorem? I'm trying to understand the proof of the PCP Theorem in "Complexity and Approximation" by  G. Ausiello et al. and came across the low degree test which is used to check if a function $f$ given as oracle (or "auxiliary proof") is close to some degree $d$ polynomial. The test uses another "Lines-Oracle" for retrieving $d+1$ coefficients for univariate polynomials defined on lines. Then the test simply compares the univariate polynomial with respect to a random line on a random point with $f$. Why is this "Lines-Oracle" necessary? I mean one could just interpolate $f$ on a random line (with the same amount of queries) and do the same check. Is this just for convenience?

The lines oracle is used to decrease the query complexity of the test from $d+1$ to $2$, at the expense of using a larger alphabet.

If you don't mind making $d+1$ queries, then the lines oracle is indeed unnecessary. However, it is usually better to make two queries over a large alphabet than $d+1$ queries over a small alphabet.

One reason is that, very roughly speaking, we have a technique, called PCP composition, which can be used to reduce the alphabet size of PCPs, but cannot be used to reduce the query complexity. Hence, it is preferable to have small query complexity and large alphabet size rather than the other way around.

A second reason, which is very related to the first one, is that many hardness-of-approximation results are proved based on $2$-query PCPs, but can not be proved using based on a PCP with more queries.

It should be mentioned that there are also generic techniques for reducing the query complexity at the expense of the alphabet size, so one could avoid the lines oracle and apply those techniques instead. However, using the lines oracle gives a more direct proof.


Original proof that "almost all decision problems are uncomputable"? Who gave the original proof that "almost all decision problems are uncomputable"? Any hint at the original paper appreciated, thanks!

So the answer to my original question is the following: Because the statement is a corollary of the two facts that

every program (Turing machine) is a finite binary string, i.e., a natural number,
every decision problem is a function $f: \mathbb{N} \to \{0,1\}$ and hence corresponds to a number $x \in [0,1)$ (and every such $x$ indeed encodes a meaningful decision problem, see Sasho Nikolov's first comment above)

the question about the original author / paper of this simple corollary is not that much interesting. (And the origins of the mentioned facts themselves I can trace back, of course.)

EDIT: I add here that this is the answer modulo the objection by Damiano Mazza (see in the comments above), which I need to check/think about first.