Difference between infinite state machines and turing machines Finite state machines (FSM) are strictly less powerful than turing machines (TM).  But this is not the case with infinite state machines (ISM).  For example, every TM can be embedded into some ISM.  The opposite (that for every ISM there exists a TM that can be embedded within the ISM), however, is not true.  We can construct a counterexample from any FSM by adding an infinite number of states and no transitions.

I have two questions:

Are all ISMs equivalent to either a FSM or TM?  (For example, does there exist an ISM that can recognize a context-free grammar, but nothing more powerful?)
Is there an algorithm for determining how powerful an ISM is?

EDIT: If such an algorithm doesn't exist, are there any reasonable heuristics or rules of thumb?

Let me provide you with an algorithm for recursively constructing an infinite state machine to decide any language $L \subseteq \{0,1\}^\ast$ that you like.

Make the initial state accept if the empty string is in the language.
Create two states for the strings 0 and 1, which the initial state branches to depending on whether the first symbol is 0 or 1. Label these $q_0$ and $q_1$. If either of the strings 0 or 1 are in $L$, make the corresponding state accept.
For a given $n \geqslant 1$, and for each state $q_x$ for $x \in \{0,1\}^n$, create two states $q_{x0}$ and $q_{x1}$, to which the state $q_x$ branches depending on whether the next symbol is 0 or 1. If either $x0 \in L$ or $x1 \in L$ is in the language, make the corresponding state accept. Having performed this for all $x \in \{0,1\}^n$, proceed to the next value of $n$, ad infinitum.

This produces an infinite state machine which decides the language $L$. In particular, it decides $L$ regardless of whether $L$ is even computable, and even regardless of its position in the arithmetic hierarchy. So not only can you have infinite state machines which have power intermediate between FSMs and Turing machines, you can make it have as much or as little power as you like.

As to algorithms, note that the ISMs constructed this way have the same structure for any language: an infinite balanced binary tree. It in essence also represents the language directly, in that it effectively is equivalent to an infinite boolean string representing the characteristic function of the language $L$. As such, the subset of these ISMs which represent regular languages is not recursively enumerable: there is no way to conclude after a finite number of steps that the language recognised is regular, because for any candidate language that the ISM recognises, there could always be some exception — but the ISM might still represent some more complicated regular expression, so neither can one conclude in a finite number of steps that the language it decides is not a regular language. The complete lack of compression in the description of the language (which is necessary to be able to represent arbitrary languages using a common structure) makes it effectively impossible to decide such problems.


Example of pairwise independent random process with expected max load $\sqrt{n}$ This question was previously posted at https://math.stackexchange.com/questions/1220292/example-of-pairwise-independent-random-process-with-expected-max-load-sqrtn where it has no answers. I now realise this is relevant to hashing so I am reposting it here.

Throw $n$ balls into $n$ bins.  Each bin is selected uniformly at random but the process is only pairwise independent.  Call the maximum number of balls in any bin the max load.

Lemma 2 in these notes tells us that the max load is at most $\sqrt{2n}$ with probability at least $1/2$.

  Can we give an explicit uniform but only pairwise independent random process for selecting the next bin to put a ball into which gives the
  expected max load to be $\Theta(\sqrt{n})$ asymptotically?

Here's how to do it.

First, choose a random $k$ between 1 and $n$ to be the "crowded bin".
Next, choose a random permutation $\pi$ of $1,2,\ldots, n-1$.

Now, for $1 \leq i \leq n-1$,
$$ \mbox{put ball } i \mbox{ into bin }
\begin{cases} k \ \ \ \ \ \ \ \ \ \ \ \ \mbox{with probability }\ \frac{1}{\sqrt{n}}, \\
k + \pi(i) \mbox{ with probability }1 - \frac{1}{\sqrt{n}},
\end{cases}$$
where the sum is taken mod $n$.

Put ball $n$ into a random bin.

Consider balls $i,j$ where $1 \leq i < j \leq n-1$. The bins these two balls fall into are independent. They both go into the crowded bin with probability $\frac{1}{n}$, and the crowded bin is equally likely to be any of the $n$ bins. And if they don't both go into the crowded bin, by symmetry they are equally likely to be in any two different bins. Thus, the bins these two balls are placed into are independent.

Since ball $n$ is placed into a random bin, it is independent of the other balls.

The expected max load here is essentially the expected number of balls in the crowded bin, which is
$$\frac{n-1}{\sqrt{n}}+\frac{1}{n} = \sqrt{n} + o(1).$$


Finding a sub rectangle with maximum sum Given a $n \times n$ matrix filled with positive or negative numbers, find a sub rectangle with maximum sum and output the sum.

There's a well-known algorithm which runs in $O(n^3)$, but can the complexity be improved any further?

In Tadao Takaoka, Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, In Electronic Notes in Theoretical Computer Science, Volume 61, 2002, Pages 191-200 you can find a simplified algorithm (the original is by Tamaki and Tokuyama) that runs in sub-cubic time for $m \times n$ arrays:

$$O ( m^2 n (\log \log m / \log m)^{1/2}) $$

From the paper: ... Bentley's algorithm is cubic and the Tamaki-Tokuyama algorithm is sub-cubic for a nearly  square array. Their algorithm is heavily recursive and complicated. We simplify the latter algorithm, and achieve sub-cubic time for any rectangular array ...

They also give a more practical algorithm whose expected time is close to quadratic for a wide range of random data.


Give a simple way to augment Van emde boas tree, to find/delete median in O(log log u) time I need a simple augmentation to support median/order statistic queries in
O(log log n) time,without increasing the time for other operations.

I agree with Kaveh that this looks like an exercise, but I disagree that adapting the idea of rank-augmented binary search trees is the way to solve it. And 2.5 years later there should be no issue with accidentally spoiling someone's homework assignment.

The trick is to maintain, separately from the VEB-tree, the value of the median, and the total number of elements in the tree (from which you can also calculate the rank of the median value that you're storing). Then, when you insert or delete in the VEB-tree, you can compare the changed value to the median you are storing to determine how the change affects its rank. If this change causes it to stop being the median, then the new median is only a successor or predecessor query away, and those sorts of queries are what the VEB-tree is good at.

Unlike rank-augmented binary search trees, I don't know of a good way to do more general queries for finding the kth smallest element in a VEB-tree.


What is the following variation on Set Cover known as? What is the following variation on set cover known as?

Given a set S, a collection C of subsets of S and a positive integer K, do there exist K sets in C such that every pair of elements of S lies in one of the selected subsets.

Note: It is not hard to see that this problem is NP-Complete:  Given a normal set cover problem (S, C, K), make three copies of S, say S', S'', and S''',  then create your subsets as S''', |S| subsets of the form {a'} U {x in S'' | x != a} U {a'''}, |S| subsets of the form {a''} U {x in S' | x != a} U {a'''}, {a', a'' | a in C_i}.  Then we can solve the set cover problem with K subsets iff we can solve the pair cover problem with K + 1 + 2 |S| subsets.

This generalizes to triples, etc.  I would like to be able to not waste half a page proving this, and it is probably not obvious enough to dismiss as trivial.  It is certainly sufficiently useful that someone has proved it, but I have no idea who or where.

Also, is there a good place to look for NP-Completeness results that are not in Garey and Johnson?

To answer your second question, the Kahn-Crescenzi compendium of NP-hardness results is a valuable source for hardness results, and also covers many variants of core G&J problems. The entry for set cover is a good example of this.


Parameterized complexity of inclusion of regular languages I am interested in the classic problem REGULAR LANGUAGE INCLUSION. Given a regular expression $E$, we denote by $L(E)$ the regular language associated to it. (Regular expressions are on a fixed alphabet $\Sigma$, with the operations union, Kleene-star and concatenation.)

Input: Two regular expressions $E_1$ and $E_2$
Question: Is it true that $L(E_1)\subseteq L(E_2)$?

REGULAR LANGUAGE INCLUSION is known to be PSPACE-complete [1].

The classic way to solve it (in PSPACE) is to construct the NFAs $A_1$ and $A_2$ associated to $E_1$ and $E_2$, to build a DFA $D_2$ from $A_2$, complement it into a DFA $D_2^C$, and finally, build the intersection automaton $A_P$ from $A_1$ and $D_2^C$ corresponding to the intersection of $L(E_1)$ and $L(E_2)^C$. Now $L(E_1)\subseteq L(E_2)$ if and only if there no an accepting path in $A_P$.

If I am not mistaken, the whole process can be done in polynomial time when $E_2$ is a fixed language, since the only exponential blow-up comes from transforming $A_2$ into $D_2$. Even better, the problem is FPT when parameterized by $|E_2|$, the length of $E_2$.

This motivates my question:

  Question: When $E_1$ is a fixed expression, what is the complexity of REGULAR LANGUAGE INCLUSION? Does it remain PSPACE-complete?

[1] L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: preliminary report. Proceedings of the fifth annual ACM Symposium on Theory of Computing, STOC '73, pp. 1-9.

Remark: Being a non-expert in the field, I find [1] (and related papers of that time) quite unreadable, and couldn't find another proof of the PSPACE-completeness - any pointer to a modern proof, such as in a book, is very welcome! Also, the authors seem to allow squaring in their regular expressions, which is nowadays rather non-standard, I believe.)

The particular case of language universality (are all words accepted ?) is PSPACE-complete for regular expressions or NFAs. It answers your question: in general the problem stays PSPACE-complete even for fixed $E_1$, since language universality corresponds to $E_1=\Sigma^*$.

It is indeed hard to find a modern readable PSPACE-hardness proof for regular expression universality, as it is now considered folklore. Here is a quick proof scheme that allows you to rebuild the proof:

Consider a Turing Machine $M$ on alphabet $\Sigma$ using polynomial space $p(n)$, and let $w\in\Sigma^*$ be an input word for $M$. We will build a  regular expression $e$ that accepts all words if and only if $M$ has no accepting run on $w$.

Consider the language $L_M$ consisting of words of the form $\$C_0\$ C_1\$\dots\$ C_f\$$, where each $C_i$ is a configuration of $M$ of length exactly $p(n)$, $C_0$ is the initial configuration with $w$ on the tape, $C_f$ is accepting, and each $C_i\to C_{i+1}$ is a valid transition of $M$. A word in $L_M$ describes an accepting run of $M$.

We build $e$ on alphabet $\Sigma'=\Sigma\cup\{\$\}$ such that $e$ accepts exactly words that are not in $L_M$, by looking for a violation of the definition of $L_M$. The expression $e$ will be a big disjunction $e_1+e_2+\dots+e_k$, where each $e_i$ looks for a different kind of violation. For instance $$e_1=(\Sigma')^*\$(\Sigma^{<p(n)}+\Sigma^{>p(n)})\$(\Sigma')^*$$ looks for a violation of the fact that each $C_i$ has size exactly $p(n)$. The most tricky part is guessing a violation between $C_i$ and $C_{i+1}$: the expression can compare a local pattern in $C_i$ and its image in $C_{i+1}$, using $t(\Sigma')^{p(n)}t'$, where $t$ and $t'$ are expressions for local patterns. With this we can guess a violation of the transition function of $M$ on a local pattern, or a violation of the identity outside of this pattern. In the end, we obtain that $$L(e)\neq (\Sigma')^*\text{ if and only if }L_M\neq\emptyset\text{ if and only if $M$ accepts }w$$ therefore we reduced (polynomially) an arbitrary PSPACE problem to universality of a regular expression.
I left out some details, but this should allow you to build a complete proof.

Of course, as pointed out by Michael Wehar in the comments, for others $E_1$ the problem can become simpler. Classifying the complexity of this problem  has been studied extensively in this paper [1] for equivalence, containment, and covering. You can see a summary of the results for the equivalence problem in this answer (there does exist NP-complete cases).

As for your remark on squaring: allowing squaring in regular expressions make the inclusion and universality problem EXPSPACE-complete [2]. Remark that this can be seen in the proof scheme above, since $(\Sigma')^{p(n)}$ can now be expressed with a logarithmic-size expression in $p(n)$ using its binary decomposition, so we can go up to an exponential $p(n)$ while keeping the size of the expression polynomial.

[1] On the equivalence, containment, and covering problems for the regular and context-free languages
Harry B.Hunt, Daniel J.Rosenkrantz, Thomas G.Szymanski.
Journal of Computer and System Sciences.
Volume 12, Issue 2, April 1976, Pages 222-268

[2] The equivalence problem for regular expressions with squaring requires exponential space. Meyer, A.R. and L. Stockmeyer. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.


Algorithms from the Book. Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book.

If God had a similar book for algorithms, what algorithm(s) do you think would be a candidate(s)?

If possible, please also supply a clickable reference and the key insight(s) which make it work.

Only one algorithm per answer, please.

Union-find is a beautiful problem whose best algorithm/datastructure (Disjoint Set Forest) is based on a spaghetti stack. While very simple and intuitive enough to explain to an intelligent child, it took several years to get a tight bound on its runtime. Ultimately, its behavior was discovered to be related to the inverse Ackermann Function, a function whose discovery marked a shift in perspective about computation (and was in fact included in Hilbert's On the Infinite).

Wikipedia provides a good introduction to Disjoint Set Forests.


Algebraic data type - rewrite system Let's define the integer ADT.

It has, as generators, the constant 0 (a generator) and the succ operation.
Moreover, it also contains the add operation defined by the (usual) axioms

  add (0, x) = x (where x is a variable of type integer)
  add (succ(x), y) = succ(add(x,y)).

Let's assume that I have two terms: add(x, succ(succ(succ(succ(0))))) and succ(succ(succ(succ(succ(succ(0)))))).

Is there an algorithm that finds all the substitutions allowing the first term to be rewritten to the second term?

Thanks in advance,
Ayroles

You could encode these into Horn Clauses (= Prolog) and use resolution (= Prolog's implementation technique).

More explicitly, your Prolog code file will look like the following:

add( 0,    N, N ).
add( succ(N), M, succ(Sum) ) :- add( N, M, Sum ).

Asking the following query at the command prompt in a prolog interpreter will give you an answer for X:

add( X, succ(succ(succ(succ(0)))), succ(succ(succ(succ(succ(succ(0))))))).

Which is:

X = succ(succ(0)) .

Using tracing within the Prolog interpreter will give you the series of substitutions used.

Fill all the gaps in yourself, and you will learn a lot.


What is the complexity of (possibly succinct) Nurikabe? Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid which is to be filled with on/off values for each cell, with each number indicating a region of connected 'on' cells of that size, and some minor constraints on the region of 'off' cells (it must be connected and can't contain any contiguous 2x2 regions). The Wikipedia page has more explicit rules and sample puzzles.

Generically, puzzles of this sort tend to be NP-complete, and Nurikabe is no exception; they fall into NP because the solution itself serves as a (polynomially-verifiable) witness to the problem.  But unlike most similar puzzles, Nurikabe instances might be succinct: Sudoku on an $n\times n$ grid requires $\Theta(n)$ givens to be solvable (if less than $n-1$ givens are offered, then there's no way of distinguishing between the missing symbols), Nonograms obviously require at least one given for each row or column, and Minesweeper must have givens on at least $1\over16$ of the cells or there will be cells not next to a given (and whose status therefore can't be determined).  But while the givens of a Nurikabe puzzle have to sum to $\Theta(n^2)$, it's possible to have $\mathrm{O}(1)$ givens each of that size, so that $\Theta(\log(n))$ bits might be enough to specify a Nurikabe puzzle of size $n$ - or inverting, $k$ bits may be enough to specify a Nurikabe instance of size exponential in $k$, meaning that the only guarantee is that the problem lies in NEXP.

Unfortunately, the proofs of Nurikabe's hardness I've found all use constructions with $\Theta(n^2)$ givens of constant size, so their instances are polynomial in the grid size rather than logarithmic, and I can't rule out that all solvable 'succinct' Nurikabe puzzles have additional structure such that solutions can be described and verified just as succinctly; for instance, the one example I know of a puzzle with 2 givens of size $\Theta(n^2)$ leads to regions of both on and off cells that are each the union of $\mathrm{O}(1)$ rectangles, and so have a succinct description of their own.  Does anyone know of additional research that's been done into this puzzle beyond the basic NP-completeness result, and in particular any further complexity results for the possibly-succinct cases?

(note: this was originally asked over at math.SE, but there haven't been any answers there yet and this seems appropriately research-level for this site)

You seem to be really asking: is Nurikabe in NP?

Nurikabe is NP-hard, since one can build polynomial-size gadgets that can be used to reduce an NP-complete problem to a Nurikabe decision problem.  This is what Holzer, Klein, and Kutrib do, and also McPhail and Fix in their poster (both referenced from the Wikipedia article).

Both groups of authors assume that the problem is trivially in NP, and wave away the question of membership.  Your unease about succinct instances seems spot on -- I do not believe the problem is in NP.  Consider the following way to formalise the decision problem:

  BINARY NURIKABE
  Input: integers m and n in binary, representing a Nurikabe board, and a list of triples, each indicating a position on the board and a positive integer written in that position.
  Question: can the remaining board positions be coloured with two colours, respecting the Nurikabe constraints?

If $m$ and $n$ are instead specified in unary, then the decision problem of determining if there exists some (not necessarily unique) solution to a given Nurikabe instance is in NP, as a solution can be specified in at most $mn$ bits which is then polynomial in the input size.

In contrast, with a binary encoding, there is a problem (as you point out): if one has just one large constraint (say, the number $(m-2)(n-2)$ placed in the middle of the $m \times n$ board), then a solution will require $mn-1$ bits to represent, which is exponential in the size of the input $\Theta(\log\, m + \log\, n)$.  This means that the problem is not in NP, unless small certificates always exist.

Your question then becomes: do there exist polynomial-sized certificates for all binary Nurikabe instances, which can be checked in polynomial time?

It is not obvious to me that such certificates necessarily exist.  Nor is it obvious how one would go about proving that succinct, quickly-verifiable certificates cannot exist.

However, the restriction to unique solutions means that the problem is actually US-hard, so co-NP-hard, and therefore unlikely to be in NP.  The point is that if one regards "has a unique solution" as a Nurikabe constraint (as opposed to a desirable feature of instances that are presented to humans), then it is not sufficient to demonstrate that there is a solution, but one must also demonstrate that no other solutions are possible.  This requirement alone is then enough to ensure the problem is probably not in NP.  This is true even for the unary version of the problem.

In summary: if one relaxes the unique solutions requirement, and specifies the board size in unary, then the decision problem is in NP; with non-unique solutions and binary board size, it is unclear whether the decision problem is in NP; and with unique solutions the decision problem is US-hard and therefore unlikely to be in NP, for either encoding of the board size.


How to go about proving the basic operators in relational algebra are independent of each other? The five basic operator select, project, cross, union and diff in relational algebra are independent of each other. I'm trying to formally prove this statement but can only progress for cross product as it would have columns greater than the rest which cannot be made possible by others. But can't think of anything for Select etc.

Here are some hints:

Select: consider the relation $\{(1),(2)\}$.
Project: number of columns can't decrease.
Cross product: number of columns can't increase.
Union: consider the database $\{(1)\},\{(2)\}$ with identical attributes.
Difference: similar to union.


What are the popular science books that inspire TCS? There is a reputation, that in computer science, we do not have popular science books. Of course that's not really true!

(In the same spirit of list of What Books Should Everyone Read?, What papers should everyone read?, What videos should everybody watch? and inspired from Favorite popular math book)

What are the popular science books or resources that inspire CS Theory?

Please have some description about why the book would be nice.

I know of many theoretical computer scientists whose first inspiration came from reading Godel, Escher, Bach

Its becoming a bit dated at this point, but is still an excellent read.


How to auto-derivate sequential iterative programs from a mathematical specification? I had to derivate, by hand, sequential iterative programs at school using an unified Hoare-Dijkstra-Hehner programming theory.

First, write down the formal specification as a Hoare triple and figure out invariants for loops. Second, apply logic rules and theorems to find an implementation that satisfies completely the specification ensuring total correctness. Actually not an easy job.

How to automate this process? is it feasible?

Short answer: no.

Long answer: No, because the synthesis problem is in general undecidable once you allow for a modest amount of expressive power in the assertions (pre- and post-conditions).

The specification for your synthesizer $S$ would look something like this. Its type would be $S:\mathit{Assn}^2\rightarrow\mathit{Prog}$, that is, given two assertions (a pre- and a post condition) it would return a program. Its functionality would be given by $\{\phi\}S(\phi,\psi)\{\psi\}$, for all $\phi,\psi\in\mathit{Assn}$. I understand your question as "is $S$ computable?"

Before we need to get technical, note that we've been a bit sloppy. $S$ can hardly be a total function for we could feed it an infeasible spec such at $[\mathit{true},\mathit{false}]$. Consequently, the best we could hope for is a partial function that works for all implementable specifications.

To answer the refined question we need to answer another first.

What expressive power would we need in the assertion language?

Firstly, assuming that we're living in a simple world where we only deal with integers, we require the usual operations from integer arithmetic.

Secondly, we need a mechanism to refer in the post-condition to the value of a program variable in the pre-condition. Without such a mechanism, we cannot even specify an increment-by-one function. Various such mechanisms exist. Let us here use one borrowed from the Z specification language: in the post-condition primed occurrences $x'$ of a variable $x$ refer to its value after the program has terminated whereas unprimed occurrences denote its value in the pre-condition. With this convention the increment-$x$-by-one function is specified by $[true,x'=x+1]$.

Thirdly, we'd also want quantifiers so we can at least specify simple examples such as

a primality checker

$[x > 0, x=x'\land(p\Leftrightarrow x>1\land\forall k(k>1\land \exists j(kj=x)\Rightarrow k=x))]$, and

a sorter that takes arrays of arbitrary size as inputs

$[\mathit{true},\mathit{length}(a)=\mathit{length}(a')\land\mathit{elements}(a)=\mathit{elements}(a')\land\forall i(1\leq i <\mathit{length}(a')\Rightarrow a'[i]\leq a'[i+1])]$.

With those ingredients, we have quite some power at our disposal, too much as it turns out. Even the domain of $S$ is undecidable because we would need to say whether a spec $[\mathit{true},\phi]$ is implementable or not, for arbitrary formulas $\phi$ of Peano arithmetic, before worrying about how to synthesize implementations. But that is already undecidable.


What functions can read-once branching programs compute? Barrington's Theorem gives us that polynomial size and bounded width Branching programs can compute exactly functions in $NC_1$, are there any results known about read-once BPs - bounded width and polynomial size?

Barrington's theorem shows that polynomial size, bounded width branching programs compute exactly the languages in $NC^1$. (Specifically, he shows this for branching programs with width at least 5, and a later result shows that 5 is necessary to capture $NC^1$). However, it's easy to see that any function is computable by an exponential size, read-once branching program (just take a decision tree which branches on every variable and outputs the truth-table of the function). If we wanted to focus on, say, polynomial size, read-once branching programs, then nothing is really known in terms of a standard complexity class. The "bounded replication" classes of branching programs (i.e. branching programs with a restriction on the number of times variables appear) don't really offer themselves well to such characterizations. Rather, the complexity classes for which we do have branching program characterizations are natural, given the model (i.e. like $L/poly$) or given via an algebraic approach, like Barrington's theorem or related results (e.g. this paper).

There is an excellent book by Jukna which studies different types of branching programs in depth.


Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm? It is well known that the NP-Complete Problem called Subset Sum has a FPTAS. I was wondering if there existed an PSPACE Complete problem which also has a FPTAS? Thanks in advance.

It is possible to define artificial PSPACE-HARD problems with an FPTAS: define $f(x)=2^{|x|}+g(x)$
where $g(x)$ is a Boolean PSPACE-hard problem whose complexity is at most $2^n$, then $f$ is also PSPACE-hard, but it has an FPTAS: if $\epsilon \gt 2^{-|x|}$ then return $2^{|x|}$ else we have enough time to compute $f$ exactly.


Why is 2-connectedness characterized by the existence of an ear decomposition ? Reading the book "Introduction to Graph Theory" (West, 2nd ed.) I have come across the following definition and statement:

Why is this statement true ?

Suppose I have a graph $G$ that consist of a cycle $C$ and a path $P$ that share no vertices. Then $G$ has an ear decomposition ? Well, I can decompose $G$ into $P_o = C$ and $P_1 = P$ ? $P_o$ is a cycle and $P$ is an ear of $P_0 \cup P_1$ - $P$ is a maximal path whose interval vertices have degree $2$ in $G$ ? But $G$ is not connected and therefore is $0$-connected and not $2$-connected ?

"Ear decomposition" is not a term I've heard before but it's incorrectly defined, as you've observed, since it doesn't require that the graph be connected, let-alone 2-connected.  An "ear" needs to be defined as having each endpoint adjacent to at least one further vertex of $G$.  (Actually, each endpoint would have to be adjacent to at least two further vertices, or the path wouldn't be maximal.)

With the correct definition, the theorem is true.


Janson-type inequality, limited dependence So I am trying to figure out an upper bound on the probability of the following...

This is a question related to a problem I am working on (not for a class, just for fun)

Let $\Omega=\{X_{1},\dots,X_{n}\}$
  where each $X_{i}$
  is i.i.d
  Bernoulli with success probability 1/2.
  Let $Y=\{Y_{1},\dots,Y_{N}\}$
  where $Y_{i}\subset\Omega$
  and $|Y_{i}|=t$.
  Let $Z_{i}$
  indicate the event that $\sum_{X\in Y_{i}}X\geq k$,
  where $k$
  is some value close to $t$. Let $Z=\sum_{i=1}^{N}Z_{i}$

Say that $I_{r}=
  \{\{Y_{i},Y_{j}\}:|Y_{i}\cap Y_{j}|=r\}$,
  that is, $I_{r}$
  is the set of all pairs from $Y$
  that share $r$
  elements from $X$.
  I am looking for an upper bound on $Pr[Z\leq\mathbb{E}[Z]-t]$.

I've seen Janson's inequality and notice that it looks quite similar to this, but I'm not sure where to go from here. Any help or any references would be greatly appreciated.

I'm posting a suitable answer that I found for this problem. The approach linked here does not exploit the fact that no $t$-tuples of elements of $\Omega$ are present in too many subsets $Y$ (for arbitrary $t$), but it does end up giving me a good enough bound anyway.


Where does a C-like language without heaps belong in the automata hierarchy? Assume that the language C', unlike C, has well-defined semantics, but has similar features: pointers and manual memory management through malloc and free. Assume that C'' is the same as C' without malloc and free; thus,the concept of a heap is absent in C''. Is C'' fundamentally weaker than C'? (I have a sense that this is the case because I cannot create lists and trees in C'', but can't be sure.) Can we map C' and C'' to deterministic TM and PDA, or some other automata, respectively?

Is there a work(s) that explores the computational powers associated with different language features? Roughly speaking, the answer I am trying to get at from the above paragraph is how important is the heap in the design of C.

Assuming we have an unbounded stack and pointers, it's a Turing machine. Since the stack is unbounded, we can get by very easily using a CPS-like style. Whenever we need to allocate memory, we'll just do it on a stack frame, then continue with the computation on the next. If our stack frames were bounded in size, of course we'd be a finite state machine. Here's a little example machine with no imports whatsoever (including no malloc). Of course on a real computer we'll eventually get a stack overflow with this. This model could be easily adjusted to have correct space usage, by adding a new stack frame only once we need to allocate.

#define NULL 0

typedef enum {
    ZERO,
    ONE,
} symbol;

typedef struct tape {
    struct tape* left;
    symbol sym;
    struct tape* right;
} tape;

typedef enum {
    A, B, DONE
} state;

int handle(tape* tape, state state);
int move_right(tape* tape, state state);
int move_left(tape* tape, state state);

int main() {
    tape start = {NULL, ZERO, NULL};
    return handle(&start, A);
}

int handle(tape* tape, state state) {
    // do some stuff
    switch (state) {
        case B:
            switch(tape->sym) {
                case ZERO:
                    return move_left(tape, DONE);
                case ONE:
                    tape->sym=ONE;
                    return move_left(tape, A);
            }
            break;
        case A:
            switch(tape->sym) {
                case ZERO:
                    tape->sym=ONE;
                    return move_right(tape, B);
                case ONE:
                    tape->sym=ZERO;
                    return move_right(tape, B);
            }
            return move_right(tape, state);
        case DONE:
            return tape->sym;
    };
};

int move_right(tape* tape0, state state) {
    tape new_tape;

    if (tape0->right == NULL) {
        new_tape = (tape){tape0, ZERO, NULL};
        tape0->right = &new_tape;
        return handle(&new_tape, state);
    } else {
        return handle(tape0->right, state);
    }
};

int move_left(tape* tape0, state state) {
    tape new_tape;

    if (tape0->left == NULL) {
        new_tape = (tape){NULL, ZERO, tape0};
        tape0->left = &new_tape;
        return handle(&new_tape, state);
    } else {
        return handle(tape0->left, state);
    }
};


Are Boolean circuits 'universal' I have a question, but I don't seem to know enough computer science terminology in order to look up an answer. So I wonder if you guys could help a poor physicist like me.

I would like to know if Boolean circuits are what I would call universal. By this I mean that, given an infinite number of NAND gates and wires, could I solve any problem on any input?

Equivalently (I think) could I simulate any given instance of a universal Turing machine using some particular Boolean circuit? By 'a given instance' I mean that the action table and input tape are set in stone, so we know exactly what process that our Boolean circuit is to simulate before we start wiring all the NAND's together.

It is important to remark that a specific boolean circuit only treats inputs of a given size, unlike a Turing Machine that can take inputs of any size.

So a language with inputs of arbitrary size is usually treated by a family of circuits, one for each size of input.
The problem with this definition is that it allows circuit to solve uncomputable problems, since we could for instance answer 1 if $|x|\in H$ and $0$ if $|x|\notin H$, where $H\subseteq \mathbb N$ is any set. Take for instance $H$ to be an enconding of the halting problem.

To circumvent this problem, we usually look at uniform families of circuits, where there is a fixed Turing Machine $M$ which on input $n$ outputs the circuit for size $n$ inputs.

There is now a hope that circuits are equivalent to Turing machines.

Unfortunately, the model of circuits have computations that always halt (or you can define circuits with loops that never halt but they are useless). This limitation alone suffices to prove that they cannot be Turing complete, because any Turing-complete model must allow infinite computation.

However notice that you have a uniform family of circuits for any language that is decided by a total Turing machine: on input $n$ you can build your circuit for size $n$ by listing all inputs of size $n$ accepted by your machine.
The things that you miss are recursively enumerable languages, such as the Halting problem.


What is the minimum number of bits required to store a sudoku puzzle? Note: This is about the standard 9x9 sudoku puzzle. The solution only has to support solved, legal puzzles. So a solution doesn't need to support empty cells and can rely on the properties of a solved sudoku puzzle.

I was wondering this, but I couldn't think of an answer that I was content with. A naive solution would use one byte for each cell (81 cells), totalling 648 bits. A more sophisticated solution would store the entire sudoku puzzle in a base-9 number (one digit per cell) and require $\lceil\log_2(9^{81}))\rceil = 257$ bits.

But it can still be improved, for example, if you know 8 of the 9 numbers in a 3x3 subgrid you can trivially deduce the 9th. You can continue these thoughts to the point where this question boils down to What is the amount of unique solved sudokus? Now you can use a huge lookup table that maps each binary number to a sudoku puzzle, but that wouldn't be an usable solution.

So, my question:

Without using a lookup table, what is the minimum amount of bits required to store a sudoku puzzle and with what algorithm?

Along the same lines as ratchet freak's answer, if you fill in the non-starred cells in the following matrix, a 3x3 box at a time, always choosing the next box to fill in to be one that shares rows or columns with a box you've already filled in, you get a pattern like the following for the number of choices per step (filling in the top middle box first, the top right box next, etc).

In each 3x3 box after the first, once you've filled in one row or column of the box, three of the remaining six digits are localized to a single row. Choose their locations first, and then fill in the remaining three cells. (So the actual order of which cells to fill in might vary depending on what you already know, but the number of choices is never more than what I've shown.)

After you've filled in these cells the stars are all determined.

* * *    9 8 7    6 5 4
* * *    6 5 4    3 3 2
* * *    3 2 1    3 2 1

6 5 4    * * *    6 3 3
3 3 2    * * *    5 3 2
3 2 1    * * *    4 2 1

6 3 3    6 5 4    * * *
5 3 2    3 3 2    * * *
4 2 1    3 2 1    * * *

If I've calculated correctly, this gives 87 bits. There's some additional savings to be had in the last 3x3 block, per the comment by Peter Shor: every value is localized to one of four cells, and every row contains at least one cell with only four possible values, so certainly the factors in that block should start with 4 not 6, but I don't understand the remaining factors in Shor's answer.


Non-hamiltonian Graphs with unique hamiltonian path between exactly 4 pair of vertices Need some example graphs which are not Hamiltonian, i.e, does not admit any Hamiltonian cycle,  but which have Hamiltonian path. It has Hamiltonian paths between exactly 4 pair of vertices. I have identified one such group of graphs. Would like to see more such examples.[Redundant information deleted; thanks to Sadeq Dousti for pointing it out]

Here's a trivial example class [and now, also generalized slightly in view of Esha's comment]: graphs G(h,k,n) constructed from a path of length n, by adjoining a cycle of length h and a cycle of length k to the two ends. If the two cycles are

  A1 – P0 – A2 – ... – Ah−1 – A1

and

  B1 – Pn – B2 – ... – Bk−1 – B1 ,

connected by the path

  P0 – P1 – ... – Pn ,

then there are Hamiltonian paths between each vertex pair {Aa , Bb} for a,b ∈ {1,2} but for no others.


Resources to find the "best" algorithm for a problem? There are many question that pose a none obscure problem and ask for the "best" algorithm, whatever "best" means.

For example, Given a graph, decide if its edge connectivity is at least n/2 or not,

The normal process is to search the literature with every single name of the problem, and find a recent paper. Usually the "best" result will be the one of the references. A more recent approach is to ask the question here.

Are there websites specifically dedicated with information like this? A database of problems and list of algorithms with their complexities? I am imagining an OEIS for problems instead of integer sequences.

There's an attempt to build such a resource. It's called the Complexity Garden and is "the botanical companion to the Complexity Zoo". Also see this meta discussion.


What is the deterministic complexity of counting the number of global minimum cuts on an unweighted undirected graph? I know as a consequence of Karger's algorithm that the number of minimum cuts is bounded by $\binom{n}{2}$. In the comments of

Counting the number of distinct s-t cuts in a oriented graph

It says that due to this consequnce, the cuts of an unweighted graph can be listed in polynomial time, but the claim is unreferenced.

If you want exact minimum cuts then one can construct a cactus representation of the minimum cuts deterministically in polynomial time and use that to enumerate all minimum cuts. See below for a reference. https://www.sciencedirect.com/science/article/pii/S0196677499910398

More interesting and difficult case is $\alpha$-approximation mincuts for $\alpha > 1$. One can use Karger's randomized algorithm for this purpose. Simply run it sufficiently many time. However, if you want a deterministic algorithm, one can do it via tree packings. See Thorup's paper on k-cuts. https://dl.acm.org/citation.cfm?id=365415


SC^2 algorithms for st-connectivity Savitch gave a deterministic algorithm to solve st-connectivity using $O({\log}^2{n})$ space, implying $NL \subseteq DSPACE({\log}^2{n})$. Savitch’s algorithm runs in time $2^{O({\log}^2{n})}$. It is a major open problem whether st-connectivity can be solved by a deterministic algorithm in polynomial time and $O({\log}^2{n})$ space i.e., whether $NL \subseteq SC^2$. $RL$, which lies between $L$ and $NL$, is known be in $SC^2$. Hence reachability in directed graphs with polynomial mixing-time is in $SC^2$.

I am looking for special cases of st-connectivity (that are not known to be in $L$) that have $SC^2$ algorithms. Is anything known about planar graphs, planar DAGs ?
 Note that st-connectivity in DAGs remains NL-complete.

There are two related complexity classes in $\text{NL}$ which are also in $\text{LogDCFL}$, which puts them in $\text{SC}^2$ (by Cook).

The first is $\text{RUL}$, for "Reach-Unambiguous Log-space" which has reachability in mangroves (graphs where every pair of vertices has at most one directed path between them) as a complete problem.  This class has been discussed before.
The second is $\text{ReachFewL}$, which has reachability complete for graphs with at most a polynomial number of paths between any pair of vertices.

Performing depth-first search on these graphs using a stack has a guarantee that it will take polynomial time, so these classes are in $\text{LogDCFL} \subseteq \text{SC}^2$.


Representing boolean function by a polynomial Supposing we have a boolean function from $f:\{0,1\}^n\rightarrow\{0,1\}$. It is clear that a real multivariate polynomial $p(x)$ such that $f(x)=p(x)$ on $x\in\{0,1\}^n$ can be multilinear. What are some interesting classes of boolean functions for which the minimal degree of $p(x)$ is known? Do we have concrete examples?

Any function which has non-zero correlation with parity has degree $n$. That is, if $$\sum_{x \in \{0,1\}^n} (-1)^{\sum_i x_i}f(x) \neq 0$$
then the unique multilinear expansion of $f$ contains the monomial $x_1\cdots x_n$. Indeed, since $(-1)^{x_i} = \frac{1-x_i}{2}$, the Fourier expansion of $f$ (expressed in terms of products of $\frac{1-x_i}{2}$) will contain the term $\prod_i \frac{1-x_i}{2}$, and the corresponding monomial $\prod_i x_i$ doesn't appear in any other term.

Nisan and Szegedy proved that functions of degree $d$ depend on at most $d2^d$ variables. For $d = 1$ we can be more exact: the function must depend on at most one coordinate.


Euclidean Capacitated Facility Location Problem In the Capacitated Facility Location Problem (CFLP), we are given a
set of clients $C$ and a set of potential facilities $F$. Each client $j \in C$ has a demand $d_j$ that must be served by one or more open facilities. Each facility $i \in F$ has an opening cost $f_i$ and has a capacity $u_i$, which is the maximum demand that facility $i$ can serve. The cost of serving one unit demand of client $j$ in facility $i$ is $c_{ij}$. We want to open a subset of facilities and assign demand of clients to open facilities such that the demands of all the clients are met, no capacity constraint violated and the total cost of opening facilities and servicing clients is minimized. Service costs are nonnegative, symmetric, and satisfy the triangle inequality.

Arora in [1, page 21] states that "Arora, Raghavan and Rao [2] give a PTAS for the geometric case. They extend the algorithm to the capacitated case but the final solution may violate capacity constraints by small amount." What does he mean by "small amount"? I guess it means they give a PTAS that violates capacity constraints within factor $(1+\epsilon)$ for an arbitrary $\epsilon > 0$. Is this right?

When I looked in [2], the only related result that I found was a $n^{O(\log^2 (n / \epsilon))}$ time algorithm for finding a $(1+\epsilon)$-approximate solution for the Capacitated $k$-median problem when we have uniform capacities. Does Arora refer to above result in [1]?

[1] S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey. In Math. Programming, Ser. B, vol. 97, pp 43-69, 2003.

[2] S. Arora, P. Raghavan, and S. Rao. Approximation schemes for the Euclidean
k-medians and related problems. In Proc. 30th ACM Symposium on Theory
of Computing, pp 106–113, 1998.

If I rmemeber correctly, you have to approximate the number of clients connected to each gate. Otherwise, you would immediately get something like $O(n^{O(g)})$, where $g$ is the number of gates in a subproblem. By approximating this number up to a facotr of $(1+\varepsilon/\log n)$ throughout the dynamic programming one can get a $(1+\varepsilon)$ error in the end. That would yield running times similar to what you stated above.


reset and shift only one level deep (delimited continuations)? I'm looking at the following tutorial on delimited (or composable) continuations:

http://community.schemewiki.org/?composable-continuations-tutorial

The author(s) propose the following "rewrite rule"

 (reset (...A... (shift K E) ...B...))
 ; -->
 (let ((K (lambda (x) (reset (...A... x ...B...)))))
   (reset E))

 (reset E)
 ; -->
 E

This is vastly smaller than anything else I've been able to find on delimited continuations, and doesn't rely on Haskell's Cont monad or on Scheme's call/cc and unique macro system. Therefore, it looks like I can implement this myself to play with outside of Haskell or Scheme / Racket, and that would be grand (see my Mathematica version below).  Problem is that I don't think it's right.

If I fire up Racket, do (require racket/control) and then

(reset (+ 1 (shift k (k 42)))  ~~>  43

as expected and as consistent with the above.  If I do

(reset (+ 1 (* 2 (shift k (k 42)))))  ~~>  85

this looks right, but doesn't match the prescription above.  That prescription, if I read it correctly, should lead to the second rewrite rule and just produce (+ 1 (* 2 (shift k (k 42)))) because it can't "see" the shift at the second level, "inside" the (* 2 (shift ...)) subexpression.

My straight transcription into Mathematica confirms this behavior,

reset[h_[As___, shift[k_, E_], Bs___]] :=
  Block[{K = Function[x, reset[h[As, x, Bs]]]},
   reset[E /. {k -> K}]]
reset[E_] := E

One level deep (like almost all the concrete examples I've found in papers! so the wiki authors are exonerated), and everything is fine:

reset[1 + shift[k, k[42]]] ~~>
reset[Plus[1, shift[k, k[42]]]] ~~>
(* h -> Plus, As -> {1}, E -> k[42], Bs -> {} *)
reset[Plus[1, 42]] ~~>
43

But then I try this:

reset[1 + (2 * shift[k, k[42]])] ~~>
reset[Plus[1, Times[2, shift[k, k[42]]]]] ~~>
1 + (2 * shift[k, k[42]])

This fires the second, transparent rewrite rule because shift is too far down; the first pattern h[As___, shift[k_, E_], Bs___] can't see it -- it's inside Bs, which matches the second-level AST Times[2, shift[...]].

So the final question is:

Can I just patch the rewrite rule above, perhaps like this:

 (reset (...A... (shift K E) ...B...))
 ; -->
 (let ((K (lambda (x) (reset ( (reset ...A...) x (reset ...B...))))))
   (reset E))

 (reset E)
 ; -->
 E

or am I doomed to take the long, scenic tour through vast landscapes of Haskell and OchaCaml and call/cc and denotational semantics just so I can create a small, but correct, toy implementation?

I think you might be misreading those rewrite rules.

A call to shift will find to the nearest enclosing call to reset, regardless of how deeply nested it is. Other examples in the tutorial you linked to should confirm that.

The Racket Reference has a slightly different set of rewrite rules for reset/shift, that might make things a little clearer.

(reset val) => val

(reset E[(shift k expr)]) =>
  (reset ((lambda (k) expr)
          (lambda (v) (reset E[v]))))

Using your example:

(reset (+ 1 (* 2 (shift k (k 42)))))
=>
(reset ((lambda (k) (k 42))
          (lambda (v) (reset (+ 1 (* 2 v))))))
=>
(reset (reset (+ 1 (* 2 42))))
=> 85

I don't speak Mathematica, but it might be possible to transcribe the rewrite rules from the Racket Reference to get what you want.


Complexity of the simplex algorithm What is the upper bound on the simplex algorithm for finding a solution to a Linear Program?

How would I go about finding a proof for such a case?
It seems as though the worst case is if each vertex has to be visited that is it $O(2^n)$. However in practice the simplex algorithm will run significantly faster than this for more standard problems.

How can I reason about the average complexity of a problem being solved using this method?

Any information or references are greatly appreciated!

The simplex algorithm indeed visits all $2^n$ vertices in the worst case (Klee & Minty 1972), and this turns out to be true for any deterministic pivot rule. However, in a landmark paper using a smoothed analysis, Spielman and Teng (2001) proved that when the inputs to the algorithm are slightly randomly perturbed, the expected running time of the simplex algorithm is polynomial for any inputs -- this basically says that for any problem there is a "nearby" one that the simplex method will efficiently solve, and it pretty much covers every real-world linear program you'd like to solve.  Afterwards, Kelner and Spielman (2006) introduced a polynomial time randomized simplex algorithm that truley works on any inputs, even the bad ones for the original simplex algorithm.


String distance communication complexity Consider $(\alpha,t)$-String distance where Alice has $x\in\{0,1\}^n$ and Bob has $y\in\{0,1\}^n$ and they have to decide if $(1-\alpha)t\leq|x\oplus y|\leq (1+\alpha)t$ or not when $\alpha\in[0,1)$ and $0\leq t\leq n$ holds. The problem interpolates somewhere between an equality function and set disjointness problem.

What is the deterministic and randomized communication complexity for $(\alpha,t)$-String distance?

Consider $t$-String distance where Alice has $x\in\{0,1\}^n$ and Bob has $y\in\{0,1\}^n$ and they have to decide if $t\leq|x\oplus y|$ or not.

What is the deterministic and randomized communication complexity for $t$-String distance?

After the OP's edit (see comments below), this answer is outdated and does not address the question. Leaving it for the said comments.

This seems to be asking the same as in this question of mine (which only has a partial answer, fitting for a partial function). Quoting from the question:

  [Consider, for $x,y\in\{0,1\}^n$] the partial function
  $$
\textsf{GHD}_{n,t,g} = \begin{cases}
0 & \text{ if }\operatorname{d}_H(x,y) \leq t-g\\
1 & \text{ if }\operatorname{d}_H(x,y) \geq t+g.
\end{cases}$$
  Lemma 4.1 to Proposition 4.4 of [CR10] allow to get a lower bound on the communication complexity of $\textsf{GHD}_{n,t,g}$ for (most) of the settings of $t,g$.

As answered there, the general one-sided version is solved in the following paper of Egor Klenin and Alexander Kozachinsky [1], who show that (with your notations) $\tilde{\Theta}\!\left(\frac{t}{(1-\alpha)^2}\right)$ bits are necessary and sufficient.

[1] One-sided error communication complexity of Gap Hamming Distance, Egor Klenin and Alexander Kozachinsky, 2016. ECCC TR16-173.


Number of equivalence classes in regular languages as a function of DFA size This question is related to a recent
question
by Janoma.
Background
In constraint programming, a regular global constraint $c$ over a
domain $D$ is a pair $(s, M)$ with $s$ a tuple of variables (the
scope) and $M$ a DFA over the domain $D$. An assignment $\theta$ to
$s$ satisfies $c$ if $M$ accepts the string
$\theta(s_1)\theta(s_2)\ldots\theta(s_n)$.
Below, assume that the domain $D$ is fixed. Define an equivalence
relation $\sim$ over the set of strings $T = D^{|s|}$ such that $a
\sim b$ if for every DFA $M$ either $a, b \in L(M)$ or $a, b \not\in
L(M)$. Intuitively, two strings are equivalent iff no DFA can
distinguish them. If that is true, then they also satisfy the same
regular constraints.
If we do not restrict the DFAs in any way, then the set of equivalence
classes $T/{\sim}$ is just $T$ itself. I am interested in the number of
equivalence classes wrt. $\sim$ as a function of the number of states $n$
that we allow for the DFA. Clearly, if $n = |D|^{|s|}$ (ignore
constants) then $|T/{\sim}| = |T|$. (Of course, $n$ here will itself be a
function of $|s|$.)
Questions

What is the smallest $n$ for which $|T/{\sim}| = |T|$?
What happens below that? In particular,

is there an $n$ such that $|T/{\sim}| = O(|s|^{|D|})$?
is there an $n$ such that $|T/{\sim}| = O(|s| \times |D|)$?

My motivation for this question is that having a polynomial
($|s|^{|D|}$) number of equivalence classes like this gave me a
tractable case of constraint problems with cardinality constraints. I
am now trying to see if something along these lines can be done for
the regular constraint.
Edit: Note also this answer by Hermann Gruber to the question referenced at the top. The bounds in the paper the answer links should yield a $k$ such that the answer to question 1 must be $\geq k$, but it is not obvious to me.

Answer to Question 1,

  What is the smallest $n$ for which $|T/{\sim}|=|T|$?

We have $$n=\max_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x)$$
where $\mathrm{sep}(w,x)$ is the smallest number of states in any DFA that accepts one of $w$ and $x$, but not the other.
The best known upper bound on $n$ is then (see some slides by Jeffrey Shallit)

  $n=O(s^{2/5}(\log s)^{3/5})$.

which was obtained in

Robson, J. M., Separating strings with small automata, Inf. Process. Lett. 30, No. 4, 209-214 (1989). ZBL0666.68051.


Data structures in programming language with linear types Assume we are dealing with a programming language that has support for linear types (terms of linear type can be used at most once, so to say). This allows for treating some computational effects (such as mutation, even changing the type of the operand) in a way that is problematic for languages, the type systems of which operate only on "eternal truths".

Many data structures can be characterized with inductive types (lists and trees are canonical examples). If we add linear inductive types to the mix, we can also handle mutable data structures.

However, it is not clear to me how to represent data structures that exhibit sharing and cyclic references in a programming language with linear types (examples of such data structures are DAGs and other graphs, represented by adjacency lists or something else, cyclic lists). Can we do that? If it isn't possible, in which way should we extend the language so as to accommodate such data structures?

The most involved example I've found so far is a doubly-linked list. Are there other examples?

Linearity is not a sufficient constraint to pin down a unique stateful representation, and so the answer to your question depends on how you interpret linear logic in terms of state. This will typically be reflected in how you must interpret the $!A$ modality.

If your intended semantics of references says that all pointers are unique values (i.e., there is at most a single reference to an object) then dags and graph structures are not expressible, for the sort of tautological reason that a dag may contain multiple references to the same object. In this case, $!A$ must be a computation which creates a new value of type $A$, since you want maps $\delta_A : !A \multimap !A \otimes !A$ and $\epsilon_A : !A \multimap A$.

However, suppose that you want $!A$ to represent sharing. Then, objects can be garbage-collected with reference counting, with the maps  $\delta_A : !A \multimap !A \otimes !A$ and $\epsilon_A : !A \multimap A$ can be realized as operations which just bump reference counts. In this case, you can't use linearity to assume that it's always safe to mutate values, since there's sharing. But you can ensure that all memory allocation is explicit in your program, and that there are no cycles in the heap.

Most practical implementations of linear types use neither of these two interpretations. Instead, references are viewed as freely duplicable entities, and what we track linearly are in fact capabilities. Capabilities are not runtime values; they are purely conceptual entities which are intended to represent the permission to access a reference. The idea is that you program in a permission-passing style, and so even if there are many references to the same object, a read or modification of a piece of state can only occur if you also have the capability to access it. And since the capability is linear, you know that only you can change it.

$$
\array{
\mathsf{new} & : & \forall \alpha. \;\alpha \multimap \exists c : \iota. \mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \\
\mathsf{get} & : & \forall \alpha, c:\iota. \;\mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \multimap \alpha \otimes \mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \\
\mathsf{set} & : & \forall \alpha, c:\iota. \;\mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \otimes \alpha \multimap \mathsf{cap}(c) \otimes \mathsf{ref}(\alpha, c) \\
\mathsf{copy} & : & \forall \alpha, c:\iota.\; \mathsf{ref}(\alpha,c) \multimap \mathsf{ref}(\alpha,c) \otimes \mathsf{ref}(\alpha,c)
}
$$

In the API sketched above, $c$ ranges over $\iota$, some domain of compile-time indices, and $\alpha$ ranges over types. We have a type $\mathsf{cap}(c)$ which is a capability indexed by $c$, and a type $\mathsf{ref}(\alpha, c)$, which is a type of references to $\alpha$ accessed by a capability $c$. Calling $\mathsf{get}$ and $\mathsf{set}$ on a reference requires the capability $c$, and calling $\mathsf{new}$ creates a new reference and a new capability sharing a common index. However, $\mathsf{copy}$-ing a reference does not require access to any capability, so anyone can copy a reference as long as they don't look inside it.


$L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability Suppose we have a hypothesis class $\mathcal{H}$ that is non-uniform learnable via sample compelxity function $m_{\text{NUL}}:[0,1]^2 \times \mathcal{H} \rightarrow \mathbb{N}$.
If we define $\mathcal{H}_n=\{h \in \mathcal{H}: m_{\text{NUL}}(0.1,0.1,h) \le n\}$, why is $\mathcal{H}_n$ PAC-learnable?

This argument is used in proof of theorem 7.2 in this book
http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf

It is stated that, by assuming realizability, using the same learning algorithm $A$, with probability at least $0.9$ over sample $S \sim \mathcal{D}^n$, we have $L_{\mathcal{D}}(A(S)) \le 0.1$.
But I don't see immediately why this is PAC-learnable because we should be able to compress the error below any $\epsilon$ with arbitrarily high probability $1-\delta$. What is the trick?

The end of the proof of Theorem 7.2 explicitly states "Using the fundamental theorem of statistical learning, this implies that the VC dimension of $\mathcal{H}_n$ must be finite, and therefore $\mathcal{H}_n$ is agnostic PAC learnable."
Now, this is confusing, since looking at this "fundamental theorem of statistical learning" (Theorem 6.7 in this book), it looks like we want to use the implication $(4) \Rightarrow (6)$, namely PAC learnability implies finite VC dimension. But, as you point out, instead of PAC learnability we only have the seemingly weaker guarantee you wrote:

With probability at least $6/7$ over $S\sim \mathcal{D}^m$ we have $L_{\mathcal{D}}(A(S))\leq 1/8$

using the notation of the book. However, if you look at the proof of Theorem 6.7, $(4) \Rightarrow (6)$ follows from the No-Free-Lunch theorem (Theorem 5.1), or rather its implication in terms of VC dimension (Corollary 6.4, and then Theorem 6.6). I'll let you check the details, but essentially it proves the stronger-looking statement you need:

Let $\mathcal{H}$ be a class of infinite VC dimension. Then, for every $m$, and every learning algorithm $A$, there exists a distribution $\mathcal{D}$ and a predictor $h\in\mathcal{H}$ such that (i) $L_{\mathcal{D}}(h) = 0$; but (ii) with probability at least $1/7$ over $S\sim \mathcal{D}^m$ we have $L_{\mathcal{D}}(A(S)) > 1/8$.


Complexity of factoring in number fields What is known about the computational complexity of factoring integers in general number fields? More specifically:

Over the integers we represent integers via their binary expansions. What is the analogous representations of integers in general number fields?
Is it known that primality over number fields is in P or BPP?
What are the best known algorithms for factoring over number fields? (Do the $\exp \sqrt n$ and the (apparently) $\exp n^{1/3}$ algorithms extend from $\mathbb{Z}$?) Here, factoring refers to finding some representation of a number (represented by $n$ bits) as a product of primes.
What is the complexity of finding all factorizations of an integer in a number field? Of counting how many distinct factorizations it has?
Over $\mathbb{Z}$ it is known that deciding if a given number has a factor in an interval $[a,b]$ is NP-hard. Over the ring of integers in number fields, can it be the case that finding if there is a prime factor whose norm is in a certain interval is already NP-hard?
Is factoring in number fields in BQP?

Remarks, motivations and updates.
Of course the fact that factorization is not unique over number fields is crucial here. The question (especially part 5) was motivated by this blog post over GLL (see this remark), and also by this earlier TCSexchange question. I presented it also over my blog where Lior Silverman presented a thorough answer.

The following answer was originally posted as a comment on Gil's blog

(1) Let $K=\mathbb{Q}(\alpha)$ be a number field, where we assume $\alpha$ has a monic minimal polynomial $f\in\mathbb{Z}[x]$.  One can then represent elements of the ring of integers $\mathcal{O}_K$ as polynomials in $\alpha$ or in terms of an integral basis -- the two are equivalent.

Now fixing $K$ as in (1) there's a polynomial-time reduction from the problem over $K$ to the problem in $\mathbb{Q}$.  To verify that the computations (e.g. intersecting an ideal with $\mathbb{Z}$ or factoring a polynomial mod $p$) can be done in polynomial time see Cohen's book referred to in the previous answer.

As a precomputation for each rational prime $p$ dividing the discriminant of $\alpha$ (that is the discriminant of $f$) find all primes of $\mathcal{O}_K$ lying above $p$.

(2) For primality testing, given an ideal $\mathfrak{a}\triangleleft\mathcal{O}_K$ let $p\in\mathbb{Z}$ be such that $\mathfrak{a}\cap\mathbb{Z} = p\mathbb{Z}$ (this can be computed in polynomial time and the number of bits of $p$ is polynomial in the input).  Check in polynomial time whether $p$ is prime. If not then $\mathfrak{a}$ is not prime.  If yes then find the primes of $\mathcal{O}_K$ lying above $p$ either from the precomputation or by factoring $f$ mod $p$.  In any case if $\mathfrak{a}$ is prime it must be one of those primes.

(3a),(6a) For factoring into primes, given an ideal $\mathfrak{a}\triangleleft\mathcal{O}_K$ find its norm $y = N^K_\mathbb{Q}(\mathfrak{a}) = [\mathcal{O}_K:\mathfrak{a}]$. Again this can be found in polynomial time and consequently is not too large. Factor $y$ in $\mathbb{Z}$ (either classically or using Shor's algorithm, depending on the reduction you want).  This gives a list of rational primes dividing $y$, and hence as in 2 we can find the list of primes of $\mathcal{O}_K$ dividing $y$.  Since $\mathfrak{a} | y\mathcal{O}_K$ this gives the list of primes dividing $\mathfrak{a}$.  Finally it is easy to determine the exponent to which a prime divides a given ideal.

(3b),(6b) But Gil wants factorization into irreducibles, not into primes. It turns out that given the prime factorization of $x\mathcal{O}_K$ it is possible to efficiently construct one factorization of $x$ into irreducible elements of $\mathcal{O}_K$.  For this let $h_K$ be the class number, and note that it is possible to efficiently compute the ideal class of a given ideal. Now to find an irreducible divisor of $x$ select $h_K$ prime ideals (possibly with repetition) from the factorization of $x$.  By the pigeon-hole principle some subset of those multiplies to the identity in the class group; find a minimal such subset.  Its product is then a principal ideal generated by an irreducible element.  Divide $x$ by this element, remove the relevant ideals from the factorization and repeat.  If the factorization has less than $h_K$ elements then just take a minimal subset of all the factors.

(4) I think it's possible to count the factorizations into irreducibles, but this is a bit of extra combinatorics -- please give me time to work it out.  One the other hand, determining all of them is not interesting in the context of sub-exponential factorization algorithms since there are in general exponentially many such factorizations.

(5) I have no idea.


Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$? If it is unknown, are there reasons to believe that they might not be equal?

First, this result is listed in the complexity zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp. Alternatively, it's possible to prove without much trouble (which I do below).

We want to show that $P^{NP \cap coNP} = NP \cap coNP$. Clearly, one direction is obviously true: $NP \cap coNP \subseteq P^{NP \cap coNP}$. To prove the other direction, it is sufficient to show that $P^{NP \cap coNP} \subseteq NP$ since then $P^{NP \cap coNP} \subseteq coNP$ follows simply by complementing all the languages involved and as a result $P^{NP \cap coNP} \subseteq NP \cap coNP$.

So let's prove that $P^{NP \cap coNP} \subseteq NP$.

Suppose we have a deterministic polynomial time machine $M$ which makes oracle queries for languages in $NP \cap coNP$. We define a new, non-deterministic machine $M'$ based on $M$ as follows:

Simulate $M$ until $M$ needs to run an oracle query on some input $x$ for some language $L$. At that point, run a subroutine which branches $M'$ into some number of branches each of which attempts to learn the answer to the oracle query. The subroutine is designed so that no branch learns the wrong answer, at least one branch learns the correct answer, and some branches get "inconclusive" as a result when trying to learn the answer to the query. In $M'$, the branches with inconclusive results then reject. At this point, the only branches left are ones which know the correct answer to the query. Thus we can continue the simulation of $M$ in these branches. At the end of the simulation, the only branches which haven't rejected are the ones which successfully got through all of the steps of the simulation. These branches accept iff $M$ accepts, so the overall $NP$

Since $L \in NP \cap coNP$, there exists a NP machine $N_L$ with language $L$ and another machine $N_{\neg L}$ whose language is the complement of $L$. To simulate the oracle query (is $x$ in $L$), $M'$ first runs $N_L$ on $x$ and then runs $N_{\neg L}$ on $x$ in every branch. Every resulting branch will have one branch of $N_L$'s computation and one branch of $N_{\neg L}$'s computation. Within any single branch, both the $N_L$ computaion and the $N_{\neg L}$ computation cannot be accepting since that would require $x$ to both be in $L$ and in $\neg L$. Thus each branch will have either the $N_L$ computation accepting, the $N_{\neg L}$ computation accepting, or neither computation accepting. Furthermore, there must be at least one accepting branch of either $N_L$ or $N_{\neg L}$. Next, $M'$ rejects in the branches in which the computations of both $N_L$ and $N_{\neg L}$ reject. In all other branches, $M'$ has learned the answer to the oracle query (since either $N_L$ or $N_{\neg L}$ accept $x$ in the particular branch considered in this $M'$ branch). At that point, $M'$ can continue the simulation of $M$. Note that the simulation will actually continue in at least one branch since at least one accepting branch of either $N_L$ or $N_{\neg L}$ exits.


Support size lower bound for $k$-wise uniform distribution So I have this question which I can't seem to find a solution to:

  Prove that if $X = (X_1, ... X_n)$ is $k$-wise uniform* and each $X_i$ is Boolean then $\left|\operatorname{Supp}(X)\right| \geq \mathbf B(\frac{k}{2}, n)$, where $\mathbf B(r, n)$ is the number of words of weight at most $r$.

$*$ Where $k$-wise uniform means that, for each subset $S=\{i_1,\dots, i_s\}\subseteq [n]$ of size $s\leq k$, the distribution of $(X_{i_1},\dots,X_{i_s})$ is uniform.

I believe this question was answered positively in three independent papers:

C. R. Rao (1947), "Factorial experiments derivable from combinatorial arrangements of arrays", Journal of the Royal Statistical Society 9:1, 128-139.

B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, and R. Smolensky (1985), "The bit extraction problem or t-resilient functions", 26th IEEE Symposium on Foundations of Computer Science, 396-407.

N. Alon, L. Babai, and A. Itai (1986), "A fast and simple randomized algorithm for the maximal independent set problem", Journal of Algorithms 7:4, 567-583.


Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$? A complete problem for $\mathsf{PPP}$ is the pigeon problem which is 'Given a Boolean circuit ${\displaystyle C}$ having the same number ${\displaystyle n}$ of input bits as output bits, find either an input ${\displaystyle x}$ that is mapped to the output ${\displaystyle C(x)=0^{n}}$, or two distinct inputs ${\displaystyle x\neq y}$ that are mapped to the same output ${\displaystyle C(x)=C(y)}$'.

$\mathsf{PPP}$ contains functional version of integer factorization, discrete logarithm etc. (page $148$ in https://simons.berkeley.edu/sites/default/files/docs/15391/ppp.pdf is reference). Decisional version of the problems are in $\mathsf{UP}$. So is $\mathsf{PPP}\subseteq\mathsf{FP}^\mathsf{UP}$ or $\mathsf{UP}\subseteq\mathsf{P}^{\mathsf{PPP}}$ believed?

Similarly is $\mathsf{TFNP}\subseteq\mathsf{FP}^\mathsf{UP}$ or $\mathsf{UP}\subseteq\mathsf{P}^{\mathsf{TFNP}}$ believed?

I doubt any of these inclusions hold, though probably proving that is hard.

$\mathsf{UP} \subseteq \mathsf{P}^{\mathsf{PPP}}$: this seems unlikely because PPP only captures one style of reasoning, whereas problems in UP can have unique witnesses for many different kinds of reasons. (It would be interesting to know if there are natural candidates witnessing this separation, even if the absence of natural candidates doesn't prove the containment.)

$\mathsf{PPP} \subseteq \mathsf{FP}^{\mathsf{UP}}$: This seems unlikely because there is no reason that either kind of output (a preimage of $0^n$ nor a collision) should be unique. Even though the proof that one of these two things must occur has one branch of the conditional being that $C$ is a bijection, that is not the only way for $0^n$ to be in the image.

For the other two, note that $\mathsf{TFNP}$ is sometimes said to correspond to $\mathsf{NP} \cap \mathsf{coNP}$, though I think more accurately it is like $\mathsf{NPMV}_t$. So it's sort of somewhere between $\mathsf{NP} \cap \mathsf{coNP}$ and $\mathsf{NP}$, but either way, it being contained in $\mathsf{FP}^{\mathsf{UP}}$ would be surprising. (Though with randomized reductions it might be interesting to think about Valiant-Vazirani in this context.)

If you think of $\mathsf{TFNP}$ as like $\mathsf{NP} \cap \mathsf{coNP}$, then $\mathsf{UP} \subseteq \mathsf{P}^{\mathsf{TFNP}}$ would be morally like $\mathsf{UP} \subseteq \mathsf{coNP}$.


Complexity of finding an edge set yielding specified vertex degrees I'm trying to figure out if the following two problems are known in general to be in P or NP-complete:

Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'\subset\,E$ such that in the graph $G'=(V,E')$ the degree of each vertex $v_i\in\,V$ is $d_i$?
Q2: Given a graph $G=(V,E)$ and integers $x_i,\,y_i,\,1\leq\,i\leq\,|V|$, does there exist a subset $E'\subset\,E$ such that in the graph $G'=(V,E')$ for every $v_i\in\,V$ we have $x_i\leq\deg(v_i)\leq\,y_i$?

I know already that certain restrictions of Q1 are known to be in P.

If all of the $d_i=1$ then the problem is finding a perfect matching
If all of the $d_i=2$ then the problem is finding a vertex cycle cover.
If $G$ is a complete bipartite graph then the problem can be solved by the Gale-Ryser theorem.

However, I haven't found an efficient algorithm for Q1 in general and nothing specific for Q2. Is anything else known?

What you look for in question Q1 is known as an $f$-factor of the graph. Here $f$ is a non-negative integer valued function on the vertices, $f(v)$ specifying the degree we want in the subgraph at vertex $v$.

Q2 is looking for a so called $(g,f)$ factor, where $g(v)$ is a lower bound and $f(v)$ is an upper bound on the degree of the sought subgraph at each vertex $v$.

Both problems can be solved in polynomial time, see https://www.sciencedirect.com/science/article/pii/S0012365X06005486


Is there computable function to compute each computable real number? Recall that a computable real number is one which can be calculated to any precision, like $\pi$ or $e$. It does not matter that these numbers are irrational, computability is about being able to compute rational approximations.

Is there a computable function which outputs an (infinite) sequence of Turing machines, each of which computes a real number, and such that all real numbers are so included?

There is a real question behind the confusion.

A real number $x$ is said to be computable if there a Turing machine, which upon input $n \in \mathbb{N}$ outputs a pair of numbers $a, b \in \mathbb{N}$ such that $|x - a/b| < 2^{-n}$. That is, there is a machine that computes arbitrarily precise rational approximations of $x$.

We can ask whether there is a machine that outputs an infinite list of machines, such that each of the listed machines computes a real number, and all computable real numbers are so included. That would be the way to make sense of the question.

The answer is negative. There is no such machine. The proof is essentially the diagonalization argument that show that a sequence of reals cannot exhaust the set of reals, except it is modified to work for computable reals and computable sequences.


Where is the error in the following P != NP pseudo-proof ? Here is a necessarily wrong proof of $P \neq NP$ as it relativizes, but I can't find the error :

Le $U$ be a universal Turing machine, whose inputs are restricted to Turing machines accepting languages in P.
Let $L = \mathcal{L}(U)$ the language accepted by $U$, hence the acceptation language restricted to P.

L is in NP as for each instance  where $\mathcal{L}(M) \in P$ and $x$ an input of $M$, the certificate of $x$ is a certificate for L too
L is not in P as it would be in $DTIME(n^k)$ for a fixed $k$ and as $DTIME(n^{m+1}) - DTIME(n^m) \neq \emptyset$, if we choose a M in $DTIME(n^{k+1})$ and fix it, U would decide the problem in $\mathcal{O}(n^k)$

You are being a little sloppy with your definitions: what exactly is the input to U, and what exactly are the conditions to accept? In particular, you probably need to include in the input  to U not just a Turing machine but also a specific polynomial that bounds the running time of the machine, because otherwise it's undecidable whether any particular TM really is polynomial time. But that's not the real problem.

The actual problem is that L(U) is not in NP. To be in NP, there needs to be a single polynomial p(n) that bounds the time to check a solution. But in your case this time is bounded by a polynomial q(n) that depends on the particular TM given as input. It's easy to choose inputs that cause q(n) to be larger than any fixed choice of p(n).


How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts? I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring nodes have. I would like to run this algorithm in parallel in the public cloud. Unfortunately, I cannot find a way to split my graph for maximum computation efficiency. All of my workers end up hitting the network to access neighbouring nodes. I need a way to split my graph to minimise network I/O between workers.

Ideally I want to split my graph into (approximately) balanced parts and minimize the number of edges crossing the parts.

I thought that ordering all nodes in some kind of 'locality-preserving' order is an option since I might not know upfront how many workers I have.

One natural thing would be to try a separator kind of trick. If the Voronoi cells are fat, and of similar size then a randomly shifted grid of the right side would do reasonably well. in particular, there is a paper by Miller and Thurston (and some other people - their names escape me) about finding a separator if you have fat regions covering space, and every point is covered only a constant number of times. It is essentially an extension of their proof of the existence of a planar separator to these more general settings.


Definition and Computational Model of EnumP Valiant [1] defined the $P$-enumerable problem in which he used the Counting Turing Machine Model: A counting Turing machine is a standard nondeterministic TM with an auxiliary output device that (magically) prints in binary notation on a special tape the number of accepting computations induced by the input. It has (worst-case) time complexity $f(n)$ if the longest accepting computation induced by the set of all inputs of size n takes $f(n)$ steps (when the TM is regarded as a standard nondeterministic machine with no auxiliary device).

A relation $R$ is $P$-enumerable iff there is a polynomial $p$ such that for all $x$ the set $\{y|R(x, y)\}$ can be enumerated in time $|\{y|R(x, y)\}|\cdot p(|x|)$.

However, in [2], they used the Random Access Machine (RAM) model to give the definition of $EnumP:$ Let $C$ be a set of binary predicates, $Enum · C$ is the set of problems $A$ such that $A \in C$.

It seems that $EnumP$ is more general than the definition of $P$-enumerable. Only the notations are easily confusing.

Why do they use different models for the enumerating problem? What is the connection between the Counting Turing Machine and RAM model when deal with the enumeration problem?

For the difference of TM and RAM can be referred to [3].

[1] Valiant, Leslie G. "The complexity of enumeration and reliability problems." SIAM Journal on Computing 8.3 (1979): 410-421.

[2] Capelli, Florent, and Yann Strozecki. "On The Complexity of Enumeration." arXiv preprint arXiv:1703.01928 (2017).

[3] https://cs.stackexchange.com/questions/22418/what-is-the-difference-between-ram-and-tm

First, you have to know that enumeration complexity is not as cleanly defined as other fields of complexity theory. People are still looking for the right definitions. Notions of reductions or completeness for example do not seem to generalize well. You will then have plenty of different names and notations for the same thing depending on the authors. For general overview of these notions, you can read the preliminaries of several thesis: Wojciech Kazana [4], Yann Strozecki [5] etc. The preprint [2] you cite is still a work in progress.

Now a clarification: Valiant does not use his Counting Turing Machines for defining P-enumerable. He uses them to define #P then reverts back to deterministic TM and defines P-enumerable. He is not really interested in enumeration complexity. He only vaguely defines it (he says that the set can be enumerated without defining it formally) to show that some #P-complete problems can still be enumerated (using fact 7, also known as "flashlight method" for enumeration).

Finally the answer. EnumP and P-enumerable are different indeed but not comparable. EnumP only says that the predicate you want to enumerate behave "nicely", that is, you can verify in PTIME that the outputs of your algorithms are indeed solutions. It does not says anything on the complexity of the problem of enumerating.

The notion of P-enumerable of Valiant corresponds to what is called Output polynomial algorithm, that is, you can enumerate the set in time polynomial in its size and the input size. This is what is called $OutputP^F$ in [2], as the "uniformity" condition (that the predicate should be in EnumP) is not present in Valiant's work. For example $SAT(\phi) = \{\tau \mid \tau \models \phi \}$ is in EnumP but not P-enumerable. See Proposition 7 of [2] for example to see a problem P-enumerable but not in EnumP.

As for the choice of RAM over TM for enumeration, the polynomial time is usually not affected by this choice, so this does not make a huge difference for complexity classes. However, such a choice is common in enumeration complexity as people are often interested in constant or linear delay, which is more robust on RAM than on TM (see for example, Wojciech Kazana thesis [4] for constant delay or the work of Étienne Grandjean for consideration on the class of linear time solvable problem).

[4] http://www.lsv.ens-cachan.fr/~kazana/PAPERS/Wojciech_Kazana_16Septembre2013_QueryEvaluationWithConstantDelay.pdf

[5] http://www.prism.uvsq.fr/~ystr/these_strozecki


Cryptography without assumptions -- seeking an overview Suppose $P = NP$ and a fast linear-time algorithm for SAT appears tomorrow.  Suddenly RSA is insecure, much of our modern communication system is broken, and we need to reconsider how to keep secrets from each other.

Question: Is there a good single reference (or short list) to gain a big-picture view of what is possible in crypto (and in the allied field of "security") without intractability assumptions? This could save civilization one day, and would also be nice to peruse in the meantime.

Discussion: Most of the cryptographic tasks we now study (OWFs, PRGs, PKE) are provably impossible in the $P = NP$ world (a world dubbed "Algorithmica" in an influential essay by Impagliazzo), but some things remain possible: communication with a one-time pad; distributed secret sharing; private info retrieval; and some other nice things.
(Certain kinds of physical mechanisms such as locked boxes, devices implementing oblivious transfer, and quantum states can also come in handy.  Of course there is always some kind of physical assumption about who can see what information.)

One can distinguish between information-theoretic security (which works against a computationally unbounded adversary) and "unconditional" security (which may require a bounded adversary, but still shows security under no unproven assumptions).  I'm most interested in the info-theoretic case.

For starters, here is one bibliography of information-theoretic security (which, for my purposes, is unmanageably long and disparate).

The key phrases you are probably looking for are "information-theoretic cryptography" and "quantum cryptography".  Searching the literature on these topics will turn up lots of work of the sort you are looking for.  Some example highlights below:

For confidentiality: the one-time pad, the Wyner wiretap channel, secret sharing, quantum key exchange, etc.
For integrity and authentication: universal hash functions.
For anonymity: anonymous communication (e.g., DC nets, onion-based schemes, p2p networks based upon rapidly mixing random walks), distance bounding protocols.
For security based upon physical assumptions: PUFs (physically unclonable functions), integrity codes (Capkun et al.), quantum cryptography, security using TPMs or tamper-resistant hardware.

There are lots of papers on those topics; too many to summarize all the results in the literature.


Why is lambda calculus so "function" oriented? I've always had this question nagging at me subconsciously but have never been able to intuitively grasp it. Why does $\lambda$-calculus have a functional notation? Why is everything a function?

It seems it has something to do with the evolution of Logic (See History of the Function Concept) and trying to "nail down" what was really meant by a function. Going through the history - FO-logic, intuitionistic logic, combinatory logic, lambda calculus etc., I still am a bit unsure about why did Church go with the function-oriented view of things. I know he was trying to work on a system for foundations of logic/math which led to the creation of $\lambda$-calculus. But what I wish to understand is his thinking and reasoning that led to the use of functions as the vehicle of choice, for getting there.

The idea of how to 'mechanize mathematical proof' was a hot topic at the time; more specifically, Hilbert posed the Entscheidungsproblem - could we have a machine in some factory somewhere that takes mathematical statements in, and outputs proofs of the truth or falseness of those statements, as easily as machines might weave cotton or drill holes in steel?

If one was 'merely' dealing with the mathematical concept of a function, then we can define such a function whose input is a mathematical statement (formally, a first order sentence in the language of number theory) and whose output is either 'True' or 'False'.

This is perfectly satisfactory as a mathematical function (once one has properly defined what it means for a statement to be true or false) but now one has a constructibility problem; the mere existence is not useful when your main goal is to actually evaluate this function on given inputs.

The purpose of the lambda calculus, and equivalent models such as Turing machines, is to provide this construction. When a mathematical function matches the input/output behavior of a Turing machine, or (equivalently) has a representation in terms of the lambda calculus, then such a function is called 'computable'.

Gödel's Incompleteness Theorem states that the true/false function described above is not computable. It is generally believed that the only mathematical functions that can be evaluated in the 'real world' are exactly the computable ones (this is the Church-Turing Thesis). Therefore, despite existing as a mathematical function, we have absolutely no way to evaluate that function in general (of course, there are still specific inputs where we can evaluate that function)


exact cover set problem i am searching an heuristic algorithm for a weighted exact cover problem shown here: http://en.wikipedia.org/wiki/Exact_cover

On my research i only found algorithm which calculates all solutions without any cost function, like http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

Do you know some algorithm for that?

My problem has a Universe of size 200 and about 500 000 subsets, so it is not possible to calculate all solutions.

--------------EDIT--------------

Example:

Universe = { 1, 2 ,3 ,4 ,5 ,6 ,7}

Sets=[

{1,2,3,4}, Cost 10

{5,6,7}, Cost 20

{5}, Cost 5

{6,7}, Cost 10
]

On this example i have to possible solutions {1,2,3,4} and {5,6,7} with cost 30 and the second solution is {1,2,3,4}, {5} and {6,7} with cost 25.

To convert to MaxSAT:

For each set $ S $ introduce a fresh variable $ X_S $.
If two sets $ S $ and $ D $ intersect, produce the hard clause $\lnot X_S\lor \lnot X_D$.
For each element $e$ produce the hard clause $\bigvee_{e\in S} X_S$, making sure that at least one set that contains $ e $ is selected.
For each set $ S$ with weight $W$ produce the soft clause $\lnot X_S$ with weight $W$, to minimize the total weight of selected sets.

I wrote a Python script for this (http://sat.inesc-id.pt/~mikolas/excover). This is the most naïve encoding. I believe there are ways how to make it smaller.


Why does the Complexity Class PostBQP makes proving PP greater than or equal to QMA easier? PP was proved greater than QMA in by Kitaev and Watrous 2000 -
Parallelization, Amplification, and Exponential Time Simulation of Quantum Interactive Proof Systems.

Later Aaronson proved that PostBQP was equal to PP in his PHD 2004.

It has been stated that the knowledge that PostBQP = PP makes proving PP is greater than or equal to QMA a lot easier.

Is there a short explanation of this. Or if not could someone provide a reference detailing this fact?

I think the reason PostBQP contained in PP makes it easier to show QMA in PP is that it's easy to show QMA in PostBQP. (Note that we don't really need PostBQP contains PP, we only need the reverse containment, which is easier to show.)

QMA can be shown to be in PostBQP in exactly the same way that one would show MA is in PostBPP (also known as BPPpath). First use error amplification to reduce the error of the MA machine to something more than exponentially small in the size of the witness. Now if you use a random witness, in the yes case there will be some probability of it being accepted (although exponentially small), whereas in the no case the probability of acceptance will be even lower. In the quantum case, we choose the maximally mixed state as the witness and use strong error amplification for QMA. (Both of these ideas are explained in John Watrous' survey on quantum complexity theory.)

Now we need to use the power of post-selection to distinguish these two cases. This is not too hard, but it might sound complicated when I explain it. If you have a machine that accepts yes instances with probability $1/2^k$ (say) and no instances with probability $1/2^{k+4}$. Let our machine with the power of post-selection do the following: With probability $1/2^{k+2}$ just set the post-selection bit (let's call this the PSB) to 1 and the output bit to 0 and end the computation. Otherwise just run the previous machine and set the PSB and the answer bit equal to the output of the computation.

Now in the yes case, with probability $1/2^{k+2}$ the machine with have the PSB equal to 1 and answer bit equal to 0, and with probability at least $1/2^k$ it will have the PSB equal to 1 and answer bit equal to 1. So conditioned on the PSB being 1, there's a much higher chance that it accepts than rejects. Similarly, in the no case, conditioned on the PSB being set to 1 there will be a higher chance of rejecting than accepting.

You might have to tweak the constants a bit to make this idea work exactly, but I think it contains all the ideas needed to make the proof go through.


How to design an online algorithm for secretary problem with multiple players? We have $k$ bins of capacity $c_i$ each. These bins appear in an online fashion, say on day $i$, bin $i$ appears. There are $l$ balls. Ball $j$ has weight $w_{ij}$ with bin $i$.

Each ball knows that there will be $k$ bins. On day $i$, bin $i$ appears and ball $j$ gets to know the bin and its capacity $c_i$. Also, ball $j$ gets to know $w_{i1},w_{i2},\ldots,w_{il}$; the weights of all balls with bin $i$ (including her weight of course). Ball $j$ must decide either to put herself into bin $i$ or not, once and forever (i.e., once decided, the game is over for ball $j$).

Each ball wants to be satisfied, that is, puts herself into a bin that has enough capacity. Ball $j$ does not know if some other balls have chosen bin $i$ or not. Also, Ball $j$ knows only the current information, does not know the weights of the balls with bins that will appear in the future.

Is there a way to find an online algorithm that maximizes the number of satisfied balls? I think this is somehow related to secretary problem but I am not sure how to prove this claim.

Per @usul's suggestion, consider the following online greedy algorithm $A$.  When bin $i$ is revealed, $A$ considers all subsets $S$ of not-yet assigned balls such that all balls in $S$ can fit together in bin $i$.  It chooses any largest such set, say $A_i$, then assigns all balls in $A_i$ to bin $i$.

The post asks for an algorithm that each ball can use independently.  To achieve this, just have each ball independently simulate $A$, and decide to join a given bin only if $A$ says it should.

Lemma 1. This greedy algorithm is 0.5-competitive.

Proof. Let $A^* = \bigcup_{i} A_i$ denote the set of balls assigned by $A$.  Let $O_i$ denote the set of balls assigned by OPT to bin $i$.  Let $O^* = \bigcup_i O_i$ be the set of all balls assigned by OPT.

The set $O_i \setminus A^*$ is one possible set that $A$ could have assigned to bin $i$.  Set $A_i$ is at least as large as this set, so $|O_i \setminus A^*| \le |A_i|$.  Summing over $i$ gives $|O^*\setminus A^*| \le |A^*|$.  That is, the number of balls assigned by OPT but not $A$ is at most the number assigned by $A$.  This implies the desired bound.  Specifically, as $O^* \subseteq A^* \cup (O^*\setminus A^*)$, it follows that
$$|O^*| \le |A^*| + |O^*\setminus A^*| \le |A^*| + |A^*| = 2|A^*|.~~~~~~~~\Box$$

If you want a polynomial-time algorithm, you can modify $A$ to choose each set $A_i$ so that it is within a factor of $1-\epsilon$ of the largest possible.  (E.g., to achieve $\epsilon=1/2$ just order the not-yet-assigned balls by increasing $w_{ij}$, and take as many as will fit in bin $i$.  Or use a PTAS at each step to achieve any fixed $\epsilon>0$.)  Then $|O_i \setminus A^*| \le |A_i|/(1-\epsilon)$ and the algorithm will be $(1-\epsilon)/(2-\epsilon)$-competitive.  (E.g. $1/3$-competitive for $\epsilon=1/2$.)

And just for the record, per OP's comment:

Lemma 2. No deterministic online algorithm has competitive ratio more than 0.5.

Proof. Consider the instance with two balls and two capacity-1 bins, where each ball has weight 1 for bin 1, but only the ball put by the online algorithm in bin 1 can fit in bin 2.$~~~\Box$


Relationship between $O(\log n)$ (bounded) treewidth and H-minor-free What is the relationship between graphs which have $O(\log n)$ treewidth and $\mathcal{H}$-minor-free graphs? Are graphs which have $O(\log n)$ treewidth $\mathcal{H}$-minor-free? I know that graphs which are $\mathcal{H}$-minor-free have treewidth $O(\sqrt{n})$ but I am concerned more with the relationship between $O(\log n)$ treewidth graphs and $\mathcal{H}$-minor-free graphs.

A proper minor-closed family of graphs has bounded treewidth if and only if it's forbidden minors includes a planar graph. Thus, either the family contains all planar graphs or has bounded treewidth. In the former case the treewidth can be $\Omega(\sqrt{n})$ and in the latter case the treewidth is $O(1)$.


Complexity results for Lower-Elementary Recursive Functions? Intrigued by Chris Pressey's interesting question on elementary-recursive functions, I was exploring more and unable to find an answer to this question on the web.

The elementary recursive functions correspond nicely to the exponential hierarchy, $\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots$.

It seems straightforward from the definition that decision-problems decidable (term?) by lower-elementary functions should be contained in EXP, and in fact in DTIME$(2^{O(n)})$; these functions also are constrained to output strings linear in their input length [1].

But on the other hand, I don't see any obvious lower bounds; at first glance it seems conceivable that LOWER-ELEMENTARY could strictly contain NP, or perhaps fail to contain some problems in P, or most likely some possibility I've not yet imagined. It would be epicly cool if LOWER-ELEMENTARY = NP but I suppose that is too much to ask for.

So my questions:

Is my understanding so far correct?
What is known about the complexity classes bounding the lower elementary recursive functions?
(Bonus) Do we have any nice complexity-class characterizations when making further restrictions on recursive functions? I was thinking in particular of the restriction to $\log(x)$-bounded summations, which I think run in polynomial time and produce linear output; or constant-bounded summations, which I think run in polynomial time and produce output of length at most $n + O(1)$.

[1]: We can show (I believe) that lower-elementary functions are subject to these restrictions by structural induction, supposing that the functions $h,g_1,\dots,g_m$ have complexity $2^{O(n)}$ and outputs of bitlength $O(n)$ on an input of length $n$. When $f(x) = h(g_1(x),\dots,g_m(x))$, letting $n := \log x$, each $g$ has output of length $O(n)$, so $h$ has an $O(n)$-length input (and therefore $O(n)$-length output); the complexity of computing all $g$s is $m2^{O(n)}$ and of $h$ is $2^{O(n)}$, so $f$ has complexity $2^{O(n)}$ and output of length $O(n)$ as claimed.

When $f(x) = \sum_{i=1}^x g(x)$, the $g$s have outputs of length $O(n)$, so the value of the sum of outputs is $2^n 2^{O(n)} \in 2^{O(n)}$, so their sum has length $O(n)$. The complexity of summing these values is bounded by $2^n$ (the number of summations) times $O(n)$ (the complexity of each addition) giving $2^{O(n)}$, and the complexity of computing the outputs is bounded by $2^{n}$ (the number of computations) times $2^{O(n)}$ (the complexity of each one), giving $2^{O(n)}$. So $f$ has complexity $2^{O(n)}$ and output of length $O(n)$ as claimed.

Concerning (bonus) question 3: the functions definable in the variant with $\log(x)$-bounded summation are all in the complexity class uniform $\mathsf{TC}^0$. This follows from the construction in Chandra, Stockmeyer and Vishkin "Constant depth reducibility", SIAM J. Comput. 13 (1984) showing that the sum of $n$ numbers of $n$ bits each can be computed by poynomial size constant depth circuits with majority gates.

With constant bounded summation you get a subclass of uniform $\mathsf{AC}^0$. Constant bounded summation can be reduced to addition and composition, and addition can be computed by constant depth boolean circuits using the carry-lookahead method.