Searching for the first item satisfying property with penalty for every test The problem in terms of a step function on integers: A step function of integers is $0$ until $s$ (the "item" in question) and then $1$. That is, $s$ is the first integer that satisfies the property $f(s) = 1$. The only way to find out the function's value $f(x)$ is to run a test to evaluate it, where each test has a penalty $p(x)$. Given a range $[a,b]$ in which the step is known to occur, find the stepping point $s$ with minimal total penalty.

In the case I'm interested in, $p(x) = x$.

If $p(x)$ is just a constant, then binary search is the solution (I think?).

Background: There is a process that takes X minutes before a certain event occurs, always at the same time, but this time is unknown. I need to find this time. To check, start the process, wait X minutes and then run a test to find out if the event happened or not. After testing, the process restarts (so you can't just test every minute to find out the minimum time).

Edit: I forgot to mention that for simplicity's sake the distribution of $s$ is uniform in $[a,b]$, that is $P(x=s, x \in [a,b]) = 1/(b-a+1)$. A more realistic distribution in my actual problem is monotonically increasing, for example $P(x) = 2x/(b-a+1)^2$.

Update: usul's answer (with a minor tweak) describes how to calculate the value which needs minimizing, which is the expected cost given a penalty function and the probability distribution of the target value.

The question still stands: which algorithm actually minimizes that value in the case $p(x)=x$ and the two distributions discussed above (uniform and increasing)? More generally - what's an algorithm that takes the penalty function and always yields the minimum expected cost?

Here is a writeup following up on Tsuyoshi's pointer to use DP.

Given $p(x)$, we can write any (decent, deterministic) algorithm as a binary decision tree with nodes weighted by $p(x)$. The root of the tree is the first node the algorithm selects to test; the left child of each $x$ is the next node to test if $f(x)$ is zero and the right node is the next to test if $f(x) = 1$.

An algorithm's worst-case performance on weights $p(x)$ is its weighted depth: the maximum over any path to a leaf of the sum of the path's weights.

Therefore the optimal deterministic algorithm minimizes this value.

The "minimum maximum length" or "cost" of a path starting at node $x$ is $p(x)$ plus the cost of the tree on the nodes remaining to be searched. The nodes remaining to be searched will always be an interval. This gives the DP relation:

  $cost[x, z] = \min_{y \in [x,z-1]} \left( p(y) + \max ( cost[x, y-1], cost[y, z]) \right)$

with $cost[x,x] = 0$ as a base case (except $cost[b,b] = p(b)$ unless you are promised that a $1$ occurs in the interval).

(Update)

With a probability distribution, say you want to minimize total expected cost. The expected cost for searching an interval is the cost of searching the first node $y$, plus the expected cost for searching the remainder. Using $\Pr[a,b|c,d]$ for the conditional probability of being in interval [a,b] given that we're in interval [c,d], this gives the following:

  $cost[x,z] = \min_{y \in [x,z-1]} \left(p(y) + \Pr[x,y-1|x,z] cost[x,y-1] + \Pr[y,z|x,z] cost[y,z] \right)$ .

Here's what I had before, which does something ... let's say "different" instead of "wrong."

It minimizes maximum expected cost. The idea is, given an algorithm, consider the node $y$ with highest expected cost $\Pr[y] p(y)$. We want the algorithm that minimizes this value. We might view this as risk-averse, I suppose.

  $cost[x,z] = \min_{y \in [x,z-1]} \left( p(y) + \max ( \Pr[x,y-1 | x,z] cost[x,y-1],  \Pr[y,z | x,z] cost[y,z]) \right)$.


Unique Games versus SDP procedures Unique Games results provide very interesting barriers to results through semidefinite programming. Lovasz theta ($\vartheta(G)$) function is an incarnation of SDP.

Is UG conjecture true $\iff \vartheta(G)$ is best approximation number for independence number $\alpha(G)$ of classes of graphs whose $\alpha(G)$ computation do not have efficient procedure if $P\neq NP$?

(I am adding $P\neq NP$ to avoid cases where other techniques such as Haemer's Bound gives better approximation).

As far as I know (and can interpret your question) no such result is known.
There are two reasons:

1) Generally unique games hardness results (as well as NP hardness result) do not yield "instance based" hardness. That is, the UG-hardness result have the following flavor - "if the unique games conjecture is true then for problem $P$ no algorithm can get a better approximation ratio than $\alpha$, where $\alpha$ is the ratio that the canonical SDP achieves on $P$"

2) While the theta function  is an appealing algorithm, and yields a $\sqrt{n}$ approximation for independent set for random graphs, in the worst case its approximation ratio can be close to $n$ (am not sure what's the extreme example), which can of course be achieved trivially. In fact, Hastad has gave an NP-hardness result ruling out an $n^{1-\epsilon}$ approximation for independent set for every $\epsilon>0$. So, even without the unique games conjecture, we know that essentially there is no non-trivial worst case approximation algorithm for this problem.

It would be very nice if there was a natural class of graphs where the theta function yields, say, an $O(\sqrt{n})$ approximation, and it is NP or UG hard to do better. I don't know of any such result.


Has there been a study of circuits operating on arrays? Much ink has been spilled studying the theory surrounding computation by combinatorial circuits operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any boolean function). One can consider families of these for different input sizes as opposed to general Turing machines, and consider the languages they accept or functions they compute (if they have multiple outputs); one can reason regarding their size and depth as a function of the input length; define the classes of languages acceptable by them with certain restrictions; study their composition; etc.

I've also been introduced to the Blum-Shub-Smale computational model, where the constituent operations of a program have elements of a field (e.g. the Rationals or the Reals) as inputs and outputs; and such a machine can be likened to a circuit if it has no loops or similar control structures. It's been the subject of much less theoretical literature, but I can still find tens of thousands of papers referring to the "BSS Model". And there are arithmetic circuits (with only + and * gates) which I vaguely recall from my Complexity Theory class as an undergrad (proofs about #P and PSPACE where boolean circuits get "arithmetized" -  AND into * and OR into +, with the inputs still being boolean).

But - what about circuits which operate on more complex units of data? That is, arrays of unbounded finite length - with the individual elements either all of some single type or from some vocabulary of types? Obviously, you might want to constrain the nodes in such circuits, as otherwise they would just be Turing machine or circuit families in themselves, but this is still a relevant kind of automaton to study these days - with programming models such as CUDA and OpenCL which apply these kinds of operations on very large amounts of data, controlled at the level of the entire kernels and their dependencies.

So - have circuits-operating-on-array seen any theoretical study? I've failed to find any such work so far.

Note: RAM/register machines in which registers or individual memory cells contain arrays would be a next best thing.

Not really an answer, but would've been too long a comment. The result of Ben-Or and Cleve that arithmetic formulas can be simulated by branching programs of width 3, works over arbitrary non-commutative rings (in particular over the matrix ring $M_n(F)$). A nice consequence of this is that $\# NC^1$ circuits over $M_n(\mathbb{Z})$ captures ${\text{GapL}}$ over $\mathbb{Z}$ (for which the Determinant is a hard function). See for example, the paper on catalytic space by Buhrman et al. for an interesting generalization of the work of Ben-Or and Cleve. There is a result of Capelli, Durand and Mengel which gives a characterization of the arithmetic complexity class VP as equivalent to formulas whose nodes compute tensor contractions (note that here you even lose associativity).


How can we express "$P=PSPACE$" as a first-order formula? How can we express "$P=PSPACE$" as a first-order formula?
Which level of the arithmetic hierarchy contains this formula (and what is the currently known minimum level of the hierarchy that contains it)?

For reference, see this blog post by Lipton.

Firstly, I want to address the comments to the question, where it was suggested that "false" expresses $P = PSPACE$ because the statement is false. While this might be a good joke, it is actually very much harmful to think this way. When we ask how to express a certain sentence in a certain formal system, we are not talking about truth values. If we were, then when someone asked "How do I write down the fact that there are infinitely many primes?" we could answer "3 + 3 = 6", but this clearly will not do. For the same reason "false" is not a valid answer to "how do I write down $P = PSPACE$?". I think Frege and Russell tried hard to teach us that lesson. Ok, now to the answer.

Let me show how to express $PSPACE \subseteq P$, the other direction is similar, and then you can put them together in a conjunction to get $PSPACE = P$. In any case, for your purposes it may be sufficient to express just $PSPACE \subseteq P$, depending on what you are doing.

Using techniques similar to those in the construction of Kleene's predicate $T$,
we can construct a bounded quantifer formula $accept_{space}(k, m, n)$ (which thus resides in $\Sigma^0_0 = \Pi^0_0$) saying "when we run the machine encoded by $k$ and bound its space usage to $|n|^m$, the machine accepts the input $n$." Here $|n|$ is the length of $n$. An informal way of seeing that such formulas exists is this: given $k$, $m$, and $n$ we can compute primitive recursive bound on how much time and how much space we are ever going to need (i.e., at most $|n|^m$ space and at most $2^{|n|^m}$ time). We then simply search through all possible execution traces which are within the computed bounds--such a search is rather inefficient, but it is primitive recursive and so we can express it as a bounded formula.

There is a similar formula $accept_{time}(k, m, n)$ in which the running time is bound by $|n|^m$.

Now consider the formula:
$$\forall k, m . \exists k', m' . \forall n .
accept_{space}(k,m,n) \Leftrightarrow accept_{time}(k',m', n).
$$
It says that for every machine $k$ which uses at most space $|n|^m$ there is a machine $k'$ which uses at most time $|n|^{m'}$ such that the two machines accepts exactly the same $n$'s. In other words, the formula says $PSPACE \subseteq P$. This formula is $\Pi^0_3$.

We can improve this if we are willing to express instead the sentence "$TQBF$ is in polytime" , which should be good enough for most applications, as TQBF is PSPACE complete and so it being in polytime is equivalent to $PSPACE \subseteq P$. Let $k_0$ be (the code of) a machine which recognizes TQBF in space $|n|^{m_0}$. Then "$TQBF \in P$" can be expressed as
$$\exists k', m' . \forall n . accept_{space}(k_0, m_0, n) \Leftrightarrow accept_{time}(k', m', n).$$
This formula is just $\Sigma^0_2$. If I were a complexity theorist I would know if it is possible to do even better (but I doubt it).


Decomposing Single Crossing Minor Free graphs We know that for a single-crossing graph H of size h, there exists a constant ch whose value depends only on h, such that every four-connected component of an H-minor-free graph is either a planar graph or of treewidth at most ch.
I would like to know if some sort of the reverse of this also holds. That is, can we say for every such graph G whose four-connected components are of treewidth is at most w or a planar graph, there exists a constant cw whose value depends only on w and single-crossing graphs H1, H2, ..., Hl each of size at most cw, such that G belongs to the union of H_i-minor free-graphs for each i in 1, 2, ..., l?

If I understood your statement correctly, then it is false:
In a graph of maximum degree $3$ the $4$-connected components are all single vertices (and therefore planar AND of treewidth $\leq 1$). However we can make graphs of maximum degree 3 that contain arbitrarily large cliques as minors.


Showing that interval-sum queries on a binary array can not be done using linear space and constant time You are given a $n$-sized binary array.

I want to show that no algorithm can do the following (or to be surprised and find out that such algorithms exist after all):

1) Pre-process the input array using unlimited time, but only using $O(n)$ bits.

2) Answer queries in constant time, where query $(x,y)$ asks for the number of set bits between index $x$ and index $y$ in the array.

It seems that constant time per query should not allow the algorithm to read enough information to compute the number of set bits.

  How can we prove that no such algorithm exists?

A more general question would be,

  given that the algorithm is allowed to use $f(n)$ space, what lower bound on the query time can we derive?

Obviously, if we have $f=\Omega(n\log n)$ space we can store the all partial sums and answer queries in $O(1)$, but what if $f$ is smaller?

You may assume that the size of a memory word is $\Theta(\log n)$ and we can read the $x,y$ indices in constant time.

I wouldn’t be so sure such an algorithm doesn’t exist; there are certainly algorithms that get very close. Below, $\log n$ is $\log_2n$, $\log^{(k)}n$ is $\mathop{\underbrace{\log\dots\log}_{k\text{ times}}}n$, $\log^*n$ is iterated logarithm, and $\tilde O(t(n))$ is $O(t(n)\operatorname{polylog}(t(n)))$.

  Proposition: There are algorithms that achieve

  space $O(n\log^{(k)}n)$ and query time $O(1)$ for any constant $k$;
  space $O(n)$ and query time $\tilde O(\log^*n)$.

The algorithms work as follows. There are parameters $k>0$ and $n=b_0>b_1>\dots>b_k>0$ depending on $n$. We split the input size-$b_0$ array into size-$b_1$ blocks (level 1); we split each level-1 block into size $b_2$ blocks (level 2); and so on up to level $k$. (Let us pretend all $b_i$ are powers of $2$, to avoid issues with divisibility.) Then:

For each $i=1,\dots,k$ and each level-$i$ block, we store the number of set bits in the interval from the beginning of the block down to the nearest level-$(i-1)$ block boundary.
In order to resolve a query, we sum the $k$ stored numbers corresponding to the index, and count the set bits before the index in its level-$k$ block. We do all this for $x$ and $y$ separately, and subtract the results.

(If the $b_i$ parameters are not easy to compute, we might also store them.)

This arrangement uses space
$$n\sum_{i=1}^k\frac{\log b_{i-1}}{b_i},$$
and query time
$$O(k+b_k).$$

In the proposition, for 1., we let $k$ be constant, and put $b_i=\log^{(i)}n$ for $0<i<k$, $b_k=1$.

For 2., we can take $k=\log^*n$, and
$$b_i=i(\log i)^3\log^{(i)}n.$$
The space is then bounded by roughly
$$n\sum_{i=1}^k\frac{\log^{(i)}n+2\log i}{i(\log i)^3\log^{(i)}n}\le
n\sum_{i=1}^\infty\frac{3}{i(\log i)^2}=cn$$
for some constant $c$.


Is counting simple cycles in $P$ for graphs of bounded tree width? Motivation:
Determining if a graph has a Hamiltonian cycle is $NP$-hard in general. However, determining if there is a Hamiltonian cycle is in polynomial time on graphs of bounded tree width, either via some algorithm involving separators + dynamic programming, or by expressing the existence of a Hamiltonian cycle in a form that fits into Courcelle's theorem.

Counting the number of Eulerian circuits on undirected graphs is $\# P $ complete, but according to this paper it is in $P$ on graphs with bounded tree width.

Counting the number of Hamiltonian cycles is $\#P$ complete, but according to theorem 4.3 of this paper, counting Hamiltonian cycles is in $P$ for graphs of bounded tree width.

Counting simple cycles is $\# P$ hard in general...

Question: Is counting the number of simple cycles in $P$ on graphs of bounded tree width?

Notes:

My inclination is to look at the separators + dynamic programming algorithms to see if one of them can be modified, but I'm pretty sure that if one can be straightforwardly modified to count simple cycles, then someone has done that already.
I do not see a way to express 'simple cycle' in $MSOL_2$ (the best I can do is express disjoint unions of simple cycles). I'm not sure if there is a version of Courcelle's theorem for counting the set of solutions to a monadic second order logic formula -- I just got a surface level understanding of this theorem from wikipedia.
I found a simple dynamic programming style algorithm to count simple cycles on series parallel graph, but it does not generalize to bounded tree width graphs. I assume that this is well known and in the literature somewhere.
(Here is the algorithm: Initialize all edge weights $w_a$ to be $1$. Initialize $S = 0$. Every time you replace 2 parallel edges with weights $w_e$ and $w_f$, with a new edge called $ef$, set $w_{ef} := w_e + w_f$ and $S := S + w_e w_f$. Every time you replace to series edges $e$ and $f$ with a new edge called $ef$, set $w_{ef} := w_e w_f$. Apply replacements until you have $K_2$. The value of $S$ at the end is the number of simple cycles, and the weight of the edge at the end is the number of simple $s$-$t$ paths.)

A simple cycle is a connected set where every vertex has degree 2. Then you have a formula SC(X) stating X (a set of edges) is a simple cycle. You can see many versions of Courcelle's theorem for listing and counting. You can refer to this book or this paper


Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$ How can one find the $d+1$ corners of the unit cube in $\mathbb{R}^d$
nearest a point $x$ in the cube ?
Use the L1 metric, so that in 4d
|$x$ - 0000| = $\sum {x_i}$,
|$x$ - 0001| = $x_3 + x_2 + x_1 + (1 - x_0)$
($x_0$ on the right) and so on.

For an alternate formulation,
first flip $x_i$ > 1/2 and sort,
so that $ 0 \leq x_{d-1} \leq \dots\  x_1 \leq x_0 \leq$ 1/2;
by symmetry, an algorithm for this case can do any $x$ in the cube.
Define $c \equiv 1 - 2x$, $ 1\geq c_{d-1} \geq \dots\  c_1 \geq c_0 \geq 0$.
Then we want the $d+1$ corners with smallest $c \cdot$ corner.

In 4d for example, with $x_i$ decreasing 1/2 .. 0 as above,
the 5 nearest corners can be

    0 0 0 0
    0 0 0 1
    0 0 1 0

    0 1 0 0  or  0 0 1 1
                 0 1 * *

    1 0 0 0
 or 0 1 0 1

However in 5d, 6d ... the trees of increasing corners look (to me)  increasingly messy.
Heuristics for approximate-nearest would be fine.

Time $O(d^3\log d)$

lemma: Fix any $x\in[0,1]^d$.  Then there is a set $S$ containing $d+1$ corners of $\{0,1\}^d$ that are closest to $x$ and such that $S$ is connected (meaning that the subgraph of the hypercube induced by $S$ is connected).

Proof.
First consider the case that $x$ has no coordinates equal to $1/2$.

Given any corner $a$ in $S$, flipping a coordinate $a_j$ of $a$ will not increase the distance from $a$ to $x$ if $|a_j - x_j| \ge 1/2$.

Consider any two corners $a,b$ in $S$ that differ in at least one coordinate $j$, and assume WLOG that $a_j=0$ and $b_j=1$.  If $x_j<1/2$ then flipping $b_j$ in $b$ gives another point in $S$ (because it decreases the distance from $b$ to $x$).  Or, if $x_j>1/2$ then flipping $a_j$ in $a$ gives a point in $S$.  Repeating this process for each differing coordinate in $a$ and $b$ gives a path connecting $a$ and $b$ within $S$.

If $x$ has coordinates equal to $1/2$, then, in choosing $S$, break ties among equidistant points by giving precedence to those with more zero coordinates.  Then the same argument will work.  QED

By the lemma, you can use a Dijkstra-like algorithm to find $S$.  Start with a corner closest to $x$ ($a$ with $a_j = 0$ if $x_j \le 1/2$).  Then repeatedly add to $S$ a corner that is closest to $x$ among those that are adjacent to some point in $S$.  Stop when $d+1$ points have been added.

Naively (using a min-heap to find the next closest point to $x$ in each iteration), I guess there are $d+1$ iterations, and each iteration requires $O(d^2)$ work to generate the $d$ neighbors of the added node (each of which has representation of size $d$), giving run time $O(d^3\log d)$.

Time $O(d^2\log d)$

Represent each corner $a$ implicitly as a pair $(h, d)$, where $h$ is a hash of the set of indices $i$ such that $a_i=1$, and $d$ is the distance from $x$ to $a$.  From a given corner $a$, the pairs for all neighboring corners can be generated in $O(d)$ time (total).  This brings the run time down to $O(d^2\log d)$.

Faster?

To make discussion easier, let's rephrase the problem as follows.  Given a sequence of $d$ non-negative numbers $y_1 \le y_2 \le \cdots \le y_d$, find the $d+1$ minimum-cost subsets of the numbers, where the cost of a subset is the sum of the numbers in it.  (To see the connection with the previous problem, take $y_i = |x_i - 1/2|$; then each subset $Y$ of the $y_i$'s corresponds to a corner $a(y)$ of the hypercube, where $a_i(y)$ is 1 if ($x_i \le 1/2$ and $y_i\in Y$) or ($x_i>1/2$ and $y_i\not\in Y$); and the cost of $Y$ is the distance from $x$ to $a(y)$.)

Here's a general idea for a faster algorithm.  Maybe somebody can figure out how to make it work.

Define an implicit directed graph where each node is a subset $Y$ of the $y_i$'s.  The start node is the empty set.  Represent the nodes implicitly as pairs $(h, c)$ where $h$ is the hash of the subset and $c$ is the cost.  For each subset $Y$, define the neighboring subsets somehow so that (i) if $Y\rightarrow Y'$ is a directed edge then the cost$(Y') \ge$ cost$(Y)$, and (ii) for any subset $Y'$, there is a directed edge $Y\rightarrow Y'$ from some subset $Y$ where cost$(Y) \le$ cost$(Y')$.  Then run Dijkstra's on this implicit graph starting at the start node.

Choose the edges (somehow) so that (i) and (ii) both hold, and the sum of the degrees of the cheapest $d+1$ nodes is $O(d)$.  (This is always possible, for example, take the edges to be those in some shortest-path tree rooted at the start.)  But can one define such a graph without a-priori knowledge of the shortest-path tree?  If so, this could lead to an $O(d\log d)$-time algorithm (?).


Does PSPACE-completeness imply approximation hardness? It is mentioned in a comment in another cstheorySE post that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it?

Is this "tight"? (i.e., are there PSPACE-complete problems whose optimization problem admits constant factor approximation in poly time?)

What about completeness for some level of PH? Does it imply any approximation hardness?

As there is no answer yet, I turn my comment to answer, Marathe et al. in their ICALP93 paper, defined some problems which are PSPACE complete but they admit constant factor approximations, they also provide some inapproximability results. For this particular question, consider MAX3SAT, corresponding decision problem is PSPACE-complete even if the corresponding SAT graph has hierarchical structure as they defined in their paper, but this problem has a 2-approximation guarantee algorithm in hierarchical structure.


Is there a hidden link between the existence uncountable sets and the undecidability of the halting problem? Since both proofs make use of the diagonal argument, I’m wondering whether there is an obscure link between the existence of uncountable infinite sets and the undecidability of the halting problem. Would the halting problem be decidable if all sets were countable?

It's not a hidden link but one that has been made explicit using the language of category theory and also a very natural question to ask and study. There is a fair bit of material on the subject.

CS Theory question asking the same thing
Andrej Bauer's blog post about fixed point theorems and Cantor's theorem.
A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points, Noson Yanofsky, 2003. Gives you a gentle introduction to Lawvere's paper, below.
Diagonal arguments and cartesian closed categories, F. William Lawvere, 2006 republication of a 1969 article making these connections precise.
Incompleteness in a General Setting, John Bell, 2007
From Lawvere to Brandenburger-Keisler: interactive forms of diagonalization and self-reference, Samson Abramsky and Jonathan Zvesper, 2010. Extension of the Lawvere arguments to game-theoretic impossibility results.


Which algorithms can be expressed using a total functional language with data parallel operators? Imagine a functional programming language whose only data types are numerical scalars and arbitrary nestings of arrays. The language lacks any means of unbounded iteration, so the following are disallowed:

explicit loops (not much use without side-effects anyhow)
recursion
arbitrary first-class functions (no y-combinator)

The language does, however, have:

top-level functions
lexically scoped let bindings
branching control flow
common scalar math and logic functions
some simple array constructor like fill(n,x) which creates an n-element array with identical values x
most importantly: a restricted set of higher-order operators which perform parallel structured iteration (such as map, reduce, scan, all-pairs).

To be more specific about the data parallel operators:

y = map(f,x) => y[i] = f[i]
y = reduce(f, a, x) => y = f(a, f(y[p[0]], f(y[p[1]], ...))) for some permutation p
y = scan(f, a, x) => y[i] = reduce(f, a, y[0...i-1])
y = allpairs(f, x, y) => y[i,j] = f(x[i], y[j])

We could have other operators as well, but to qualify they should have polynomial running time, be implementable under some reasonable model of data parallel computation, and use at most polynomial space.

There are obviously some constructs which can't be expressed in this language, such as:

while f(x) > tol:
    x <- update(x)

What can we express in this system? Are we limited only to search problems in FP? Can we capture all polynomial time algorithms? Also, is there some minimal set of operators for this class?

You might want to look at the old programming language NESL which took these ideas seriously. The language is based on operations on collections, essentially lists and lists of lists and so forth, but I think trees and graphs were also considered, via tricky encodings. Some of the research done in that project (in the mid 1990s) could help answer your question. The PhD thesis (available as a book) Guy E. Blelloch. Vector Models for Data-Parallel Computing. MIT Press, 1990 may provide some answers. It was some time ago since I looked at it.

Work done on the Bird-Meertens Formalism (BMF) falls into this category too, as did the language Charity. From the Charity wikipedia page it says that the language is not Turing complete, but can express Ackermann's function, which means that it's more than primitive recursive. Both BMF and Charity involve operators like folds and scans (catamorphisms, anamorphisms, etc), and they have their roots in Category Theory.

I short, imprecise answer is that you can express quite a lot.


Finding triangles in a graph: other approaches besides property testing? We're working on a paper that presents some algorithms for finding triangles and network motifs (constant size subgraphs, also known as graphlets) in a distributed setting. We characterize the tradeoff between the number of triangles in the graph and the communication load necessary. I am looking for references to work done on this question in the centralized model.

The problem is that nearly everything I found on this topic that had a theoretical flavor to it was within the framework of property testing. To illustrate the difference - consider the case of a graph with $n$ vertices, that is comprised of $n-2$ triangles all sharing the edge $\left(1,2\right)$. From the point of view of property testing, this graph is very close to be triangle-free (removing that critical edge does the job), whereas it has a linear number of triangles, which is a lot by our standards.

Any references at all will be appreciated.

Edit: I'm mainly interested in algorithms that can determine whether the graph contains triangles quickly. For triangle (or other subgraph) listing algorithms, the running time is naturally bounded from below by the number of triangles in the graph, as the algorithm needs to list them all, making such instances harder in a sense. From the point of view of a decision problem ("triangle-free or not"), having many triangles actually makes the problem easier, since you can easily find one.

For several references for the problem of testing for the existence of a triangle (exactly, not in the property testing framework), see Triangle-free graph on Wikipedia. In particular Alon, Yuster, and Zwick (ESA'94) give an O(m^{1.41}) algorithm, and it can also be done in fast matrix multiplication time which is better for dense graphs.

If you're ok with something in the dynamic graph algorithms setting, I also have one for counting the triangles:

The h-index of a graph and its application to dynamic subgraph statistics, D. Eppstein and E. S. Spiro, arXiv:0904.3741 and WADS 2009.

In our paper we cite Chiba and Nishizeki (SICOMP 1985) and Itai and Rodeh (SICOMP 1978) for the basic static-algorithm facts that a graph with m edges can have at most O(m^{3/2}) triangles in the worst case and that they can be listed in that amount of time.


Parametricity and projective eliminations for dependent records It's well-known that in System F, you can encode binary products with the type
$$
A \times B \triangleq \forall\alpha.\; (A \to B \to \alpha) \to \alpha
$$
You can then define projection functions $\pi_1 : A \times B \to A$ and $\pi_2 : A \times B \to B$.

This isn't so surprising, even though the natural reading of the F type is of a pair with a
let-style elimination $\mathsf{let}\;(x,y) = p \;\mathsf{in}\; e$, because the two kinds of pair
are interderivable in intuitionistic logic.

Now, in a dependent type theory with impredicative quantification, you
can follow the same pattern to encode a dependent record type $\Sigma x:A.\; B[x]$ as
$$
\Sigma x:A.\;B[x] \triangleq \forall\alpha.\; (\Pi x:A.\; B[x] \to \alpha) \to \alpha
$$
But in this case, there isn't a simple way of defining the projective eliminators
$\pi_1 : \Sigma x:A.\;B[x] \to A$ and $\pi_2 : \Pi p:(\Sigma x:A.\;B[x]).\; B[\pi_1\,p]$.

However, if the type theory is parametric, you can use parametricity to show that $\pi_2$ is definable. This appears to be known --- see, for example, this Agda development by Dan Doel in which he derives it without comment --- but I can't seem to find a reference for this fact.

Does anyone know a reference for the fact that parametricity allows defining projective eliminations for dependent types?

EDIT: The closest thing I've found so far is this 2001 paper by Herman Geuvers, Induction is not derivable in second order dependent type theory, in which he proves that you can't do it without parametricity.

I just talked to Dan Doel and he explained that his reference was in fact one Neel Krishnaswami. He saw a comment on n-cafe by you that one could do strong induction using parametricity, so he went ahead and did it as an exercise, not realizing that doing it for sigma was apparently a novel result.

The precise quote: "My reference was him. I thought he said it was possible, so I did it."


Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures I've been trying to understand Bits-back coding (Frey, B. J., and G. E. Hinton. 1997.) a bit more (pun intended), which can be used to encode data with latent variable models. This tutorial by Pieter Abbeel et al. sums up the procedure with an example which I present below, but with an explicit auxiliary variable (i.e. I added the variable $k$).
Consider a mixture of Gaussians where $i$ indexes the Gaussian from which the data $x$ is sampled; $p(x\vert i) = \mathcal{N}(x|\mu_i, \sigma^2_i)$. Assume, although possibly intractable, the true posterior $p(i \vert x, k)$ is available from which it is possible to sample and encode values $i$, where $k \sim p(k)$ is some auxiliary information used to sample $i$. Note that $k$ is used solely in the process of selecting $i$, therefore $k \rightarrow i \rightarrow x$ forms a Markov chain and $p(x \vert i, k) = p(x \vert i)$
Given a data point $x$ to compress, bits-back coding then proceeds to

Sample $k$ from $p(k)$
Sample $i$ from $p(i \vert x, k)$
Encode $i$ with a prior $p(i)$, resulting in code-length $\log_2(1/p(i))$
Encode $x$ with $p(x \vert i)$, resulting in code-length $\log_2(1/p(x \vert i))$
Although $i$ was encoded with $p(i)$, given that we know $p(i \vert x, k)$, it is possible to get "bits back" (hence the name) by reconstructing $k$.

My goal is to understand this concretely, since most tutorials I've found stop here and never actually give an example. Hence, consider the following:
Say there are 4 modes (Gaussians) of the mixture represented by $i \in \{0, 1, 2, 3\}$ and $k \in \{0, 1\}$. For a given point $x_o$, assume the given values for $p(i \vert x_o, k)$ and $p(i)$, as well as the code used to represent them from a binary alphabet, are the following:
$$\begin{array}{c|c|c}
i & p(i) & \text{code-word} \\ \hline
0 & 1/4  & 00 \\
1 & 1/4  & 01 \\
2 & 1/4  & 10 \\
3 & 1/4  & 11 \\
\end{array}$$
$$\begin{array}{c|c|c}
k &i & p(i \vert x_o, k) \\ \hline
0 & 0 & 1/2 \\
0 & 1 & 1/4 \\
0 & 2 & 1/4 \\
0 & 3 &   0 \\
1 & 0 &   0 \\
1 & 1 & 1/2 \\
1 & 2 & 1/4 \\
1 & 3 & 1/4
\end{array}$$
I've conveniently made the symbols I.I.D. with dyadic probability mass functions, therefore making traditional Huffman Coding optimal.
On the receiving end, if $i=0$, surely $k=0$ since $p(i=0 | x_o, k=1) = 0$. Similarly, $i=3$ implies $k=1$. In general:
$$\begin{array}{c|c|c}
i & p(k=0 \vert x_o, i) & p(k=1 \vert x_o, i) \\ \hline
0 &   1 &   0 \\
1 & 1/3 & 2/3 \\
2 & 1/2 & 1/2 \\
3 & 0 & 1
\end{array}$$
Therefore, we are able to recover $k$ to some extent.
I have 2 questions:

is this the bits-back coding scheme or am I missing something?
For $i=0$ and $i=3$ we can recover $k$, but for $i \in \{1, 2\}$ all we have are the probabilities over $k$. How do we get these bits-back?

Apparently, no. This is a generalization where the relationship between $k$ and $i$ is stochastic (i.e. defined by a distribution and not deterministic).
To recover the original bits-back argument, we would need to pick a value $i_k$ for each possible value of $k$ and force $p(i=i_k \vert x, k)=1$ and 0 if $i \neq i_k$. Naturally, we would need to extend the support of $k$ to the same of $i$. In this particular example, $k \in \{0, 1, 2, 3\}$


Name the graph class: Disjoint union of a clique and an independent set Let $G$ be a graph which is the disjoint union of a clique and an independent set, i.e.
$$G = K_{n_1} + \overline{K_{n_2}} = K_{n_1} + I_{n_2} .$$

The graph class of all such graphs is characterized by the forbidden induced subgraphs set $\mathcal{H} = \{2K_2, P_3\}$ and is thus the intersection of a cluster graph and a split (or threshold) graph.

Does this (very simple) graph class have a name?  I was unable to find the graph class on ISGCI, and the papers I know on the topic (e.g. Editing Simple Graphs and On the clique editing problem) do not refer to the class by a name.

Here is a figure of such a graph:

The edge-complement of graphs in your class are complete split graphs: they can be partitioned into an independent set and a clique, such that every vertex in the independent set is adjacent to every vertex in the clique (see, for example, http://www.mathcove.net/petersen/lessons/get-lesson?les=30 ). Hence you could call your graph class co-complete split graphs.


Papers on Prolog-like languages without closed world assumption (CWA) Prolog execution process may be seen as a search that model scientific search for a proof of a proposition. At the same time, real world scientific search greatly differs from Prolog search in the following way:

As we know, Prolog is based on closed world assumption (CWA) -- that is, if a proposition is not in the fact database and not derivable from the fact database, then it is not true. So Prolog search may yield 2 results:

proposition is proved; here is the proof: ...
proposition is false or it can not be proved using fact database

At the same time, scientific search is not limited by CWA and may be seen in at least 4 states:

proposition is proved; here is the proof: ...
proposition is disproved by counter-example; here is the counter-example: ...
proposition is neither proved, nor disproved to the specified (current) time
proposition is proved to be independent from the axiom set; here is the proof: ...

I suspect that, because of popularity of Prolog in the end of the XX century, there were successful attempts to improve it by removing CWA in order to better model scientific search in resulting language. CWA removing seems to open possibility to use 3 or even all the 4 above-mentioned states in programming language execution process.

So, I suspect, there are papers that describe such attempts and explore theoretic foundations of such a prolog-like languages. If so, please point out a survey or a bunch of most significant of such a papers.

Thank you for a great question! I am looking into papers on related subjects myself--I'll post anything worthwhile that I come across, and would appreciate if you would do the same. = ) Off the top of my head, you might be interested in ileanTAP, a Prolog theorem prover for intuitionistic logic (includes a short paper). Just so the term is not left undefined:

  Intuitionistic logic, or constructive logic, is a symbolic logic system
  differing from classical logic in its definition of the meaning of a statement
  being true. In classical logic, all well-formed statements are assumed to be
  either true or false, even if we do not have a proof of either. In constructive
  logic, a statement is 'only true' if there is a constructive proof that it is
  true, and 'only false' if there is a constructive proof that it is false.
  Operations in constructive logic preserve justification, rather than truth. (Wikipedia)

Have you read Kuhn on scientific paradigm shifts? The problem you have described is generally applicable to all of science: theories (and coherent theoretical domains) are abstracted axiomatic systems, and updating a scientific domain (as opposed to "filling out the missing bits" by using what's already established as "axioms") requires switching from one isomorphic system to another (two systems are isomorphic if they have identical or similar outputs for some narrow set of parameters, e.g. Newtonian physics and GR).


Typing of substitution in a bidirectional type system In most typed lambda calculi, we have the following lemma:

If $\Gamma \vdash t_1 : \tau_1$ and $\Gamma, x : \tau_1, \Delta \vdash t_2 : \tau_2$ then $\Gamma,\Delta[t_1/x] \vdash t_2[t_1/x] : \tau_2[t_1/x]$

However, I'm wondering how we'd phrase such a lemma in a bidirectional typing system, with synthesis $\Rightarrow$ and checking $\Leftarrow$ judgements.

The main problem is that substitution does not preserve synthesis. For example, in most systems, $\Gamma \vdash x \Rightarrow T$ if $x : T \in \Gamma$, but  $[(\lambda y \ldotp t)/x]x$ won't synthesize any type if there are only checking rules for $\lambda$.

Potential solutions I can think of:

Restrict to substituting with synthesizing expressions. This seems like it would give us the induction hypothesis we need (since, in most systems, all synthesizing expressions also check), but is very restrictive.
Only show that substitution preserves checking. This is a weaker result, and I'm unsure of whether it gives us a strong enough inductive hypothesis, since it would be difficult to rebuild typing derivations with synthesis judgements in the premises.

This seems like a pretty basic metatheoretic property, so I'm sure I'm not the first one to have encountered this. Does anyone have a reference to a bidirectional system that cleanly solves these issues? Is there an obvious solution I am missing?

One solution is indeed to restrict to substituting with synthesizing expressions. You can only hope to replace variables with terms of the same mode (i.e. inferrable terms), anything else just won't fit. It is not that restrictive in the sense that usually a checkable term together with a type annotation gives you an inferrable term. This embedding is typically called cut because well... this is what it is. This restriction is described (and deployed) in I Got Plenty o’ Nuttin’.

Alternatively (which is also mentioned in IGPoN) you can define hereditary substitution (a formalised account for STLC) whereby if you are about to form a redex because of the checkable you just plugged in, you fire it. And again. And again. And again. Until your substitution is not creating any new redexes.


Practical implementation of Hindley–Milner with typeclasses — matching vs most general unifier I'm trying to get a deep understanding of a (great) paper "Typing Haskell in Haskell". I'm having difficulties understanding the implementation of two methods there — the mgu and match.

Let's talk about the TAp case (full implementation in the article):

-- Substitutions are from a type variable to a type
type Subst  = [(Tyvar, Type)]

-- Calculate most general unifier 's' so that:
-- prop> apply s t1 = apply s t2
mgu :: Monad m => Ty.Type -> Ty.Type -> m Subst
mgu (TAp l r) (TAp l' r') = do s1 <- mgu l l'
                               s2 <- mgu (apply s1 r) (apply s1 r')
                               return (s2 @@ s1)              -- <=== THIS
-- ...snip...

-- Matching of t1 and t2 finds a substitution 's' so that:
-- prop> apply s t1 = t2
match :: Monad m => Type -> Type -> m Subst
match (TAp l r) (TAp l' r') = do sl <- match l l'
                                 sr <- match r r'
                                 merge sl sr                  -- <=== THIS
-- ...snip...

-- Substitution composition such that:
-- prop> apply (s1 @@ s2) = apply s1 . apply s2
(@@)       :: Subst -> Subst -> Subst
s1 @@ s2    = [ (u, apply s1 t) | (u,t) <- s2 ] ++ s1

-- A `symmetric' composition of substitutions such that:
-- prop> apply (s1++s2) = apply (s2++s1)
merge :: Monad m => Subst -> Subst -> m Subst
merge s1 s2 = if agree then return (s1 ++ s2) else fail "merge fails"
  where agree = all (\v -> apply s1 (Ty.TVar v) == apply s2 (Ty.TVar v))
                    (map fst s1 `intersect` map fst s2)

match is used only for matching predicates, mgu is used more often e.g. for actual type inference.

I can't wrap my head on why in the mgu the substitution composition is sequential and in match a symmetric composition is used. Why's that?

Furthermore, would it make a difference if I'd change the ordering of unification, so mgu would read:

mgu (TAp l r) (TAp l' r') = do s1 <- mgu r r'
                               s2 <- mgu (apply s1 l) (apply s1 l')
                               return (s2 @@ s1)

Ok, so I figured it out the next day. It's all dead simple as it came out.

Let's use an example – type applications z a a and z a b where z :: * -> * -> *. The unification will yield that (without further context) z a a is the most general type for both giving substitution {b↦a}. On the other hand, z a a cannot be matched to z a b, as they are simply different.

So now let's dissect the implementations. The mgu x@(TAp l r) y@(TAp l' r') first compares l and l' giving a substitution s1 <- mgu l l'. The s1 is a knowledge of how part of x and y are different. With that knowledge, we can investigate further; that's why we use apply in s2 <- mgu (apply s1 l) (apply s1 l') which gives us next premises on how different x and y are. So the summary is to compose the knowledge: s2 @@ s1 (ordering is as in function composition, e.g. g (f (x)) can be written as (g ∘ f) (x)).

I believe (without a proof though) that it's possible to just use s2 <- mgu r r' and then try to combine s1 with s2 though some kind of recursion would be required. Also, I believe it's possible to match r with r' first and then match l with l'; the ordering is just to make error messages more obvious (order of reading in a file).

The match x@(TAp l r) y@(TAp l' r') is different. We must not approve the first example: z a a vs z a b. In order to do that we need to:

note that a from x would need to become a from y
note that a from x would need to become b from y
tell that the above two premises are contradictory

That's the reason to yielding strange substitutions like {a↦a} which is semantically equivalent to {} but allows for taking #1 into account.
The symmetric composition takes this additional information. It doesn't put apply in the second sub-matching (match (apply s1 r) (apply s1 r')) since applying a substitution would make us lose information about contradictory premises.


Equilibrium in a Halting Game Consider the following 2-player game:

Nature randomly picks a program
Each player plays a number in [0, infinity] inclusive in response to nature's move
Take the minimum of the players’ numbers, and run the program for (up to) that many steps (unless both players chose infinity)
If the program halts, the player who played the minimum number gains 1 point. If the program does not halt, that player loses 1 point. Any player who played a non-minimum number receives 0 points, and both players receive 0 if they both play infinity.

(Corner cases may be handled in whatever way best preserves the spirit of the problem - e.g. upper semicontinuity may be helpful.)

The question: does this game possess a computable Nash equilibrium?

Without the computability requirement, each player just plays the exact number of steps in which the program halts (or infinity, if it does not halt).

If you try the usual diagonalization argument for the halting problem, you'll find that an equilibrium exists in mixed strategies, so the obvious approach does not immediately work. Maybe there's some way to tweak it?

On the other hand, the equivalence of real closed fields means that finite games with computable payoffs have computable equilibria. This game is not finite, but the strategy space is closed and the payoffs computable, so maybe the same trick could be applied with Glicksberg's Theorem or something in that vein? The problem is, without the computability requirement, the equilibrium is in pure strategies, so any attempt to prove existence of a computable equilibrium using existence of a maybe-computable equilibrium has to explain why the equilibrium is downgraded from pure to mixed.

This seems like the sort of problem where people may not have addressed this exact question before, but might have looked at something similar. I haven't been able to turn up much, but if anyone knows of something in spirit, please let me know!

Motivation: there's a common intuition that self-reference is the main block to computability - i.e., that any uncomputable problem somehow embeds self-reference. If a game roughly like this has a computable Nash equilibrium, it would provide evidence for that intuition.

UPDATE: To clarify, the equilibrium should be "computable" in the sense of computable real numbers: the probabilities describing the mixed strategy distribution should be computable to arbitrary precision. (Note that only finitely many probabilities will be above any particular precision cutoff.) This also means that we can sample from an arbitrarily close approximation of the equilibrium strategy.

Even if you have a one-player game there is no computable equilibrium. Consider nature putting probability $1/2^i$ on program $i$. Any computable strategy will achieve some value strictly less than one or you could use it to solve the halting problem. But you can achieve any value less than one by the strategy that for some fixed sufficiently large $t$, simulates nature's program $j$ for $t$ steps and outputs the number of steps it takes program $j$ to halt if $j$ halts in $t$ steps, infinity otherwise.


Consequences of nondeterminism speeding up deterministic computation If $\mathsf{NP}$ contains a class of superpolynomial time problems, i.e.

  for some function $t \in n^{\omega(1)}$, $\mathsf{DTIME}(t) \subseteq \mathsf{NP}$,

then if follows from the deterministic time hierarchy theorem that
$\mathsf{P} \subsetneq \mathsf{NP}$.

But are there any other interesting consequences nontrivial
(i.e. not a consequence of $\mathsf{P} \subsetneq \mathsf{NP}$)
if nondeterminism can speed up deterministic computations?

I found one related consequence.

Let's say $NEXP$ contains $DTIME(2^{O(t)})$, where $t = n^{\omega(1)}$.  It turns out this is just enough time to diagonalize against $P/poly$.  Specifically, build the following machine:

On input $x$ of length $n$, consider the $n^{th}$ Turing machine $M$.  For every possible advice string of length $t$ and every possible bitstring $b$ of length $n$, run $M$ on $b$ with advice $a$, and reject after $t$ steps if you haven't accepted yet.  Record your results in a table.  This procedure runs in $DTIME(2^{O(t)})$.

On input $0^n$, if at least half the advice strings cause $M$ to reject, then instead we define it to be correct for our algorithm to accept (otherwise, it is correct for our algorithm to reject).  Any advice strings that caused $M$ to get $0^n$ wrong (that is, at least half the advice strings) now get thrown out of the table.  We then repeat the process on input $0^{n-1}1$: if at least half the surviving advice strings cause $M$ to reject, then our algorithm will accept (and reject otherwise).  Continue like this for all inputs of length $n$ (although really, only $t$ of them are needed - after that many inputs, we have thrown out all possible advice strings).

Clearly this language can be decided in $DTIME(2^{O(t)})$, which we have assumed is in $NEXP$.  On the other hand, it cannot be in $P/Poly$: the set of length $n$ inputs diagonalizes against the prospect of $M_n$ being used to decide the language.

So we get $NEXP \not \subset P/poly$, which would be interesting.

I'm going to leave the question open in case someone comes up with something else.


VC dimension of Voronoi cells in R^d? Suppose I have $k$ points in $\mathbb{R}^d$. These induce a Voronoi diagram. If I assign to each of the $k$ points a $\pm$ label, these induce a binary function on $\mathbb{R}^d$. Question: what is the VC-dimension of all such possible binary functions induced by some $k$ points and some labeling of these points?

Please check Theorem 21.5, Section 21 in the book "A probabilistic Theory of Pattern Recognition (1996)" from Devroye, Gyorfi, and Lugosi. I think the following upper bound is valid: VC $\leq$ $k + (d+1)k^2\log k$.


Hardness of Vertex Separators For a given graph $G$, the Separator Problem asks whether a vertex or edge set of small cardinality (or weight) exists whose removal partitions $G$ into two disjoint graphs of approximately equal sizes. This is called the Vertex Separator Problem when the removed set is a vertex set, and the Edge Separator Problem when it is an edge set. Both problems are NP-complete for general unweighted graphs. What is the best known hardness of approximating vertex separator ? Is a PTAS ruled out ? What are the best known hardness results in the directed setting ?

Correction : The following links and answers did not help me because I did not state my question correctly. My question is related to the following theorem of Leighton-Rao :

Theorem : There exists a polynomial time algorithm that, given a graph $G(V,E)$ and a set $W \subseteq V$, finds a $\frac{2}{3}$ vertex separator $S \subseteq V$ of $W$ in $G$ of size $O(w.{\log}n)$, where $w$ is the minimum size of a $\frac{1}{2}$-vertex separator of $W$ in $G$.

Given a graph $G(V,E)$ and a set $W \subseteq V$, I want to find a $\delta$-vertex separator (where $\frac{1}{2} \leq \delta \leq 1$ is a constant) of size $w$, where $w$ is the minimum size of a $\frac{1}{2}$-vertex separator of $W$ in $G$. What is the best known hardness of this problem ? The above theorem gives an $O({\log}n)$ approximation for this problem.

Note that I am allowing constant factor blow-up in the size of the resulting components after removing the separator, but I want to minimize the size of the separator itself. The links mentioned in the comments point to minimum b-vertex separator, in which we insist that the size of the resulting components is at most $|V|/2$.

In the edge setting, the problem you're referring to is the bisection problem, and the size of such a minimum edge is called the bisection width. There's a ton of research on this problem, and the best known approximation for the problem is $O(\log n)$ by Racke.

A good review of the known work on this problem (which connects to sparsest cut, spreading metrics, and even the unique games conjecture) is in this recent paper on generalizations of bisection width by Krauthgamer, Naor and Schwartz.


Approximation algorithm for finding the maximum common subgraph in two DAGs Suppose we have two directed acyclic graphs $A$ and $B$ and we look to find the subgraph that is common to both graphs and has the most number of vertices. That is to find the biggest graph which is a subgraph of both $A$ and $B$. The vertices are not labeled, but of course, the directions on edges do matter.

Noting that this solves the graph isomorphism, the problem is not known to be solvable in polynomial time. So I was looking for an approximation algorithm. Can you think of any?

Isn't there a straightforward approximation-preserving reduction from maximum independent set (MIS) in undirected graphs to your problem?

Given undirected graph G=(V,E), form DAG A=(V,E') by ordering the vertices arbitrarily and directing the edges accordingly, then take B=(V,{}) to be the DAG with the same vertices but no edges.

Any subgraph common to A and B corresponds to an independent set in G, and vice versa, no?

If this reduction is correct, then your problem is as hard to approximate as MIS; which is to say, forget about it. :-)


What is the best known FPT result for 3-hitting set? My research problem involves solving a special instance of the 3-Hitting Set problem, and I was wondering whether my result is actually significant (i.e. if it is better than the best known result for 3-Hitting Set).

I'm specifically interested in the case where the parameter is the optimal hitting set size.

I know the paper by Niedermeier and Rossmanith that presents an algorithm of run-time $O(2.27^k + n)$, but that paper is pretty old.

According to the Parameterized Complexity Wiki, the currently best known FPT algorithm for 3-Hitting-Set has a complexity of $2.076^k \cdot n^{O(1)}$, the algorithm is from the PhD thesis of Magnus Wahlström.


Where do most REGEX implementations fall on the complexity scale? Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do these features let them parse statements that can't be described with a finite, non-pushdown automaton? How much closer to turing complete does this make them if they can?

I don't think that the real problem is the question of what unbounded means; this is no worse than any other situation in parsing.

The trouble lies with characterizing backreferences, which are both very powerful and very limited: they allow description of some non-context-free languages, without allowing some context-free languages. For example, the regex (a*)b\1b\1 matches strings of the form $a^n \cdot b \cdot a^n \cdot b \cdot a^n$, and you can use the pumping lemma to show this is not a context-free language. However, on the other hand, regexes with backreferences don't seem to be sufficient to match the balanced parenthesis language, which is the prototypical context-free language.

It's easy enough to give a denotational semantics saying what strings are in a language to regexes, but giving a good automata-theoretic characterization seems much more challenging. It's something like a register machine, into whose registers you can copy substrings of your input, and which you can use to test your current string against, but for which you lack the ability to modify these registers.

People doing finite model theory have a bunch of funky machine models, and it would be interesting to know if this corresponds to any of their models.


Small steps for better TCS conferences? Often, when we take part in TCS conferences, we notice some little details that we wish the conference organisers would have taken care of. And when we are organising conferences, we have already forgotten it.

Hence the question: Which small steps we could easily take to improve TCS conferences?

Hopefully, this question could become a resource that we could double-check whenever we are organising conferences, to make sure that we do not repeat the same mistakes again and again...

I am here interested in relatively small and inexpensive details – something that conference organisers could have easily done if only they had thought about it in time. For example, it might be a useful piece of information that could be put on the conference web page well in advance; a five-dollar gadget that may save the day; something to consider when choosing the restaurant for the banquet; the best timing of the coffee breaks; or your ideal design of the conference badges.

We can cover here all aspects of conference arrangements (including paper submissions, program committees, reviews, local arrangements, etc.).

This is a community wiki question. Please post one idea per answer, and please vote other answers up or down depending on how important they are in your opinion.

Keep prices down: you can get lovely hors d'oeuvres at a $750-per-seat hotel-hosted conference, it is true, but it tends to detract from the intellectual atmosphere you can get with a $100-per-seat university-hosted conference.  Also, you don't just get the people attending who deliver talks.  Allow students at the university to attend for free;
Space parallel sessions, so that people can really move between them;
But also encourage interaction between speakers and attendees at parallel sessions beforehand, so that parallel sessions are also autonomous communities.  This encourages interaction, and the sense that parallel sessions are moving the discussion in their subfield forward.  Some conferences (e.g., the German linguistics conference, DGfS) have taken this to the conclusion of having all parallel sessions be independent workshops.


Hierarchy theorem for approximation ratios? As is well known, NP-hard optimization problems can have many different approximation ratios, ranging all the way from having a PTAS to not being approximable within any factor. In between, we have various constants, $O(\log n)$, $poly(n)$, etc.

What is known about the set of possible ratios? Can we prove any sort of "approximation hierarchy"? Formally, for what functions $f(n)$ and $g(n)$ can we prove that there exists a problem with approximation ratio $f(n)\leq \alpha < g(n)$?

In the case that $\alpha=O(1)$, does there exist a problem with approximation ratio exactly $\alpha$?

There is an approximation hierarchy, the main known examples: FPTAS $\subseteq$ EPTAS $\subseteq$ PTAS $\subseteq$ APX. But for inapproximability there also is NPO-PB.

There are a lot of results about the set of possible ratios, going from results like this one:

  $P||C_{max} \in$ EPTAS$\backslash$ FPTAS, unless $P=NP$,

to defining APX/NPO-PB-hard problems.

Some references:

ON PTAS: M. Cesati and L. Trevisan. On the efficiency of polynomial time approximation schemes, 1997.
On NPOPB: V. Kann. Strong lower bounds on the approximability of some NPO PB-complete maximization problems

But I suggest the best will be to check the Complexity Zoo because it has many more information and references on those examples, even Wikipedia

Furthermore, as stated in the comments the tight bound when $\alpha=O(1)$, was shown for many problems such as bin packing, machine scheduling (see iris.gmu.edu/~khoffman/papers/set_covering.html).


Embedding points in Euclidean space into a box If I give you a set of points in Euclidean space, is there a criterion to determine whether there exists a (potentially higher-dimensional) rectangular prism / box that has these points as their vertex set?

For instance, an equilateral triangle has this property, as (1,0,0), (0,1,0), and (0,0,1) form an equilateral triangle and are corners of the unit cube.

This is related to some larger work on L1 and L2 embeddings into a box, on which I have some passing familiarity with the literature (Menger's theorem, Schoenberg, etc.).

Solved. The answer is to square the edge lengths and test if the result is L1 embeddable. Details to come at some unspecified future time.


Integer relation detection for Subset Sum or NPP? Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer?  If not definitely, then in some probabilistic sense?

I know that LLL (and perhaps PSLQ) have been used with moderate success in solving Subset Sum problems in the 'low-density' region, where the range of numbers chosen is greater than $2^N$, but these methods don't scale well to instances of larger size and fail in the 'high-density' region, when the range of numbers chosen is much smaller than $2^N$.  Here low-density and high-density refers to the number of solutions.  The low-density region refers to the few or no solutions that exist whereas high density refers to a region with many solutions.

In the high density region, LLL finds (small) integer relations amongst instances given, but as instance size increases, the probability of the relation found being a viable Subset Sum or Number Partition Problem solution becomes decreasingly small.

Integer relation detection is polynomial to within an exponential bound of optimal whereas Subset Sum and NPP are obviously NP-Complete, so in general this is probably not possible, but if the instance is drawn uniformly at random, could this make it simpler?

Or should I not even be asking this question and instead be asking if there is a way to reduce the exponential bound from the optimal answer in lieu of an exponential increase in computation?

Let m be the logarithm of the largest number.
If $m=O(\log n)$ then it is solvable in polynomial time using dynamic programming.
In general, every known algorithm take at least $\Omega(2^{m})$ time. There is no known polynomial time algorithm when $m=\omega(\log n)$ and $m=o(n)$

However, Flaxman and Przydatek provide an algorithm that solves Medium-Density Subset Sum Problems in Expected Polynomial Time.

Check this reference:

Flaxman and Przydatek, Solving Medium-Density Subset Sum Problems in Expected Polynomial Time


Is there known any complexity class containing online counterparts of optimization problems? Is there known any complexity class containing online counterparts of optimization problems? If not, then how such class can be defined?

We know that many problems have their online version: e.g. online version of bin packing problem. The online problems are harder as measured by their competitive ratios.

And I haven't found anything similar in complexity zoo.

Essentially, we could say that there are no online problems, but only online algorithms for offline problems. However, if there are online problems, why there can't be complexity class containing them?

One tricky aspect of defining complexity classes for online problems is that there's in principle no limit on what kinds of computations I can do once I've read the input. In other words, online problems are hard even if I have (for example) an NP oracle processing the input once it arrives.

It's conceivable that with a more limited processor, even simpler prediction tasks become harder to perform, but in general the difficulty of designing online algorithms comes from the ability of the adversary to change the input after you've built a prediction model.


Any fundamental papers in TCS which were found to be incorrect/wrong later? I am asking this question out of curiosity.

I recently encountered this well-known paper on (published in 2009):
the hardness_of_Euclidean_kmeans

The paper showed that the previous NP-hardness result (link) for the Euclidean k-means (discovered in 2004 and a preliminary version appeared in 1999) was wrong. Note that after around 5 years somebody pointed out that the previously known result was incorrect.
They also mention that many of the well-known papers (like kmeans++ paper) cited the incorrect hardness result till then.

Even when I read a paper, I find some minor mistakes. However, they are easily fixable and do not change the main result very much.

I want to ask if there had been any fundamental or highly cited paper, which was later found to be incorrect, and due to which the entire understanding of the field changed.

Edit: After reading some of the answers, I want to point out another issue that, why these incorrect papers are not updated after being pointed out wrong. I mean some kind of notice must be provided by the governing body who shares the link. In my case (for the example I gave above), it took me two years to figure out why people in the year 2002 were designing the PTAS for the k-means problem(for fixed k) if the result of hardness came later in the year 2009. It can be quite frustrating for a person who is not familiar with that field.

One example is the claimed proof of the Gilbert-Pollak conjecture on the Steiner ratio, which appears in FOCS'90, and Algorithmica. The conjecture is now considered open.

Another examples include a sequence of algorithms on graph embedding.

There are more examples, but without similarly published refutations as above, it is difficulty to list due to the subtle nature.


Languages whose Parikh image is recognizable Let $\Sigma$ be some alphabet, and $p : \Sigma^* \to \mathbb N_0^{|\Sigma|}$ the Parikh map. A formal language $L \subseteq \Sigma^*$ is called a slip-language, if $p(L)$ is a semilinear set. By Parikh's theorem, every context-free language is a slip-language. But not every slip-language is context-free. For example, the commutative closure of $(abc)^*$ is not context-free.
In $\mathbb N_0^k$ with $k = |\Sigma|$, the semilinear set are precisely the rational sets. The recognizable set in $\mathbb N_0^k$ are finite unions of sets of the form $R_1 \times \ldots \times R_k$, with each $R_i$, for $i \in \{1,\ldots, k\}$, either finite or ultimately periodic.
The slip languages are an established concept. For example, we have work from the 70's, and such neat results as that the commutative closure of binary slip languages is context-free.
Now I am just curious. Is there anything known, or is there any research, on languages whose Parikh image is recognizable?
As recognizability is preserved under inverse homomorphism, the commutative closure of such a language is regular. But, there exist non-regular languages whose Parikh image is recognizable. For example, the language given by the context-free grammar $A \to aBaA | \varepsilon, B \to bAbB |\varepsilon$. It has the commutative closure
$$
 \{ w \in \{a,b\}^* \mid |w|_{a} \equiv 0 \pmod{2}, |w|_b \equiv 0 \pmod{2},
 |w|_a \ge \min\{1, |w|_b\}. \},
$$
where $|w|_a$ and $|w|_b$ denote the number of $a$'s, respectively $b$'s, in $w$.
EDIT (8/5/2020): There was an error in the specification of the context-free grammar. I corrected it. Also I will give the proofs, just to be on the safe side. Let $L$ be the language generated by the grammar. Suppose it where regular with pumping constant $N$. Consider $w = (ab)^N(ba)^N \in L$, and let $v$ be some pumpable factor in $(ab)^N$. As any word in $L$ must have even length, this factor itself must have even length. Hence it starts with different symbols. So, we either have $w = (ab)^x(ab)^y(ab)^z(ba)^N$ with $N = x+y+z$ and $v = (ab)^y$, or $w = (ab)^xa(ba)^yb(ab)^z(ba)^N$ with $N - 1 = x+y+z$ and $v = (ba)^y$. But in either case, none of the pumped up strings would be in $L$, as they still only contain $bb$ as a factor with two consecutive equal symbols. But if the factor $bb$ (or $aa$) only appears once in a given word from $L$, it must have the form $(ab)^k(ba)^k$ or $(ab)^{k-1}aa(ab)^{k-1}$ for some $k > 0$. Alternatively, we could note that an infinite accepting automaton is given by the state set $\{1,2,3,\ldots\}$, with the letter $a$ interchanging $1$ and $2$, $3$ and $4$, and so on, and $b$ interchanging $2$ and $3$, $4$ and $5$ and so. As this is a permutation automaton with the single final state $\{1\}$, it is minimal.
Finally, as $(aa)^{n-1}a(bb)^ma \in L$ for each $m \ge 0$, $n > 0$, and $(aa)^m \in L$ for each $m \ge 0$, and every word in $L$ has an even number of $a$'s and $b$'s, the claim about the commutative closure is implied.

I seems that I was quite confused back then. This language class is precisely the language class of those languages, whose commutative closure is regular.
Let $\Sigma = \{a_1, \ldots, a_k\}$. One implication is given in the question. For the other, suppose the commutative closure of $L \subseteq \Sigma^*$ is regular, i.e., the set $p^{-1}(p(L))$ is regular.
Then,  $p^{-1}(p(L)) \cap a_1^* \cdots a_k^*$ is regular, bounded and has the same Parikh image as $L$ or its commutative closure. By an old result of Ginsburg (see below), we can write this language as a finite union of languages of the form $A_1 \cdots A_k$, where each $A_i$ is a regular subset of $a_i^*$. Now, the Parikh image of one such set has the form $R_1 \times \ldots \times R_k$ with $R_i \subseteq \mathbb N$ recognizable. So, by a condition written in the question, the Parikh image of $L$ is recognizable.
Alternatively, without citing other results, suppose we have a morphism $h : \Sigma^* \to M$ with $M$ finite such that $p^{-1}(p(L)) = h^{-1}(h(L))$. We can assume $M$ is commutative (for example, by taking the syntactic monoid).
Hence, the map $\varphi : \mathbb N_0^k \to M$ given by $\varphi(n_1, \ldots, n_k) = h(a_1)^{n_1} \cdots h(a_k)^{n_k}$ is a morphism.
Then, $p(L) = \varphi^{-1}(h(L))$ and so $p(L)$ is recognizable.
Now, identifying language classes whose commutative closure is regular is quite an active field of research. For example, see the second reference below.
S. Ginsburg, Bounded Regular Sets, Amer. Math. Soc. 17 (1966), 1043-1049.
Antonio Cano Gómez, Giovanna Guaiana, Jean-Éric Pin:
Regular languages and partial commutations. Inf. Comput. 230: 76-96 (2013)


Long distance string problem We are considering length n strings over the alphabet S.

The goal is to compute a set of string, M, such that for any string, x, in S^n there exists a string, y, in M such that the hamming distance between x and y is at least r.

A way of thinking of this is that we want to guarantee that for any string, we have a string in our solution M which is far away from the given string.

For a given S (with size at least 3), n and r (which may be a funciton of n, for example n/2) for many strings a needed to include in M to guarantee that for any string in S^n, we have a string in M which has a hamming distance to it of at least r.

I have a feeling this is well studied and might be related to covering designs. Can someone give me a good reference (or insight)? I would be very grateful.

Look up the concept of anticodes. Some bounds exist.

Also if you have a linear $t-$error correcting code over $GF(q)$ with length $n$ and covering radius $r$ and use homogeneity under translations by adding vectors $n-d=n-2t-1$ would seem to be your answer but I haven't checked carefully. Cohen and Litsyn have a book on covering codes.

A Simple Construction

Fix $k\geq 1$ and let $v=\lceil n/k \rceil$ and consider the strings as $GF(q)^n.$ Generate all $k-$tuples over $GF(q)$ to obtain $M=q^k$ codewords. Map these codewords to $GF(q)^n$ by expanding by $v$ for the first $k-1$ coordinates and expanding by $n-(k-1)v$ for the last coordinate. For example, let $q=3,$ $n=5$ and $k=2.$ Your codewords are
$$
\begin{array}{cc}
0&0\\
0&1\\
0&2\\
1&0\\
1&1\\
1&2\\
2&0\\
2&1\\
2&2\\
\end{array}
$$

which become upon expansion with $v=4$

$$
\begin{array}{c}
0000~000\\
0000~111\\
0000~222\\
1111~000\\
1111~111\\
1111~222\\
2222~000\\
2222~111\\
2222~222\\
\end{array}
$$
Now, for any possible vector in $GF(3)^7$ there is a codeword which is quite far from it.
Namely, if there are fewer than 2 symbols for that vector in a block, there is a codeword which is at Hamming distance $v$ from it. If all 3 symbols occur, there is a codeword at Hamming distance $\geq \lfloor 2v/3 \rfloor$ from it. Since all possible constant blocks occur, for any possible vector in $GF(3)^7$ there is a codeword in this code of only $M=9$ codewords which is at Hamming distance $\geq k \lfloor (q-1)v/q \rfloor \approx n(1-\frac{1}{q}).$ Choosing $v$ a multiple of $q$ will make this more efficient.


What is known about multi-prover interactive proofs with short messages? Beigi, Shor and Watrous have a very nice paper on the power of quantum interactive proofs with short messages. They consider three variants of 'short messages', and the specific one I care about is their second variant where any number of messages can be sent, but the total message length must be logarithmic. In particular they show that such interactive proof systems have the expressive power of BQP.

What I want to know is whether there are analogous results for the multi-prover setting, either for classical or quantum verifiers. Are any non-trivial complexity results known for multi-prover interactive proofs where the total length of all messages is restricted to be logarithmic in the problem size?

Completely classical case (MIP)

If the verifier is classical and there is no prior entanglement among provers, your class contains BPP∪NP and is contained in MA.

It is trivial that BPP is a lower bound.  To show that the class contains NP, consider the standard two-prover one-round interactive proof system for 3-colorability with perfect completeness and soundness error 1−1/poly.  If you want to reduce the soundness error to a constant, combine this with the PCP theorem.

As for the upper bound, the following stronger statement holds: MIP with the restriction that the total message length from the verifier to each prover is O(log n) is equal to MA.  This is because a strategy of each prover can be described by a string of polynomial length.

Interestingly, another upper bound exists when the system has perfect completeness.  Namely, multi-prover interactive proof systems with perfect completeness with O(log n)-bit total communication recognize at most PNP[log], and this holds even if we allow unbounded soundness error.  To prove this in the case of two provers, let xs be the concatenation of all answers given by the first prover when the concatenation of all questions to the first prover is s, and define yt analogously for the second prover.  To be accepted by the verifier with certainty, these variables xs and yt must satisfy certain constraints, and note that this is a 2CSP.  There are at most poly(n) choices for tuples (s, t, xs, yt), and for each choice, we can use the NP oracle to test whether the verifier rejects that tuple.  Therefore, with the NP oracle, we can list up all the constraints on the variables xs and yt in polynomial time.  Finally, we use the NP oracle once more to test whether there is an assignment to these variables which satisfies all the constraints.  Although this algorithm uses the NP oracle polynomially many times, all the queries except for the last one can be made in parallel, and therefore this can be converted to a PNP[log] algorithm.  The case of more than two provers is analogous.

This upper bound implies that although every MA system can be turned to one with perfect completeness, we cannot hope for a multi-prover interactive proof system with perfect completeness with O(log n)-bit communication unless MA⊆PNP[log].  I do not know how unlikely the inclusion MA⊆PNP[log] is, but I just note that Complexity Zoology states that there is an oracle relative to which BPP⊈PNP (and therefore clearly MA⊈PNP[log]).

(In the case of single prover, Theorem 2 of Goldreich and Håstad [GH98] implies that IP with the total message length O(log n) bits is equal to BPP.)

Added.  A necessary and sufficient characterization is as follows.

To explain this characterization, we need a variant of the notion of Karp reducibility (polynomial-time many-one reducibility).  For two decision problems A and B, let’s say that A is FPBPP-reducible to B (I know, this is an awful name) when there is a deterministic polynomial-time Turing machine M with access to the BPP oracle which maps yes-instances to yes-instances and no-instances to no-instances, where we allow “non-smart” oracle access (meaning that M can make a query to the BPP oracle about an instance which does not satisfy the promise of the BPP problem, in which case then oracle returns yes or no arbitrarily).  Then it can be proved that the following conditions on a problem A are equivalent.

(i) A has a multi-prover interactive proof system with O(log n)-bit communication and two-sided bounded error.
(ii) A has a two-prover one-round interactive proof system with O(log n)-bit communication, exponentially small completeness error, and constant soundness error.
(iii) A is FPBPP-reducible to a problem in NP.

(Proof idea: Implication (ii)⇒(i) is trivial.  Implication (i)⇒(iii) can be obtained in a similar way to the above proof in the case of one-sided error.  Implication (iii)⇒(ii) follows from the PCP theorem because the class of problems satisfying condition (ii) is closed under FPBPP-reducibility.)

Classical verifier with entangled provers (MIP*)

Next consider the case with a classical verifier and entangled provers.  In this case, the class with bounded error again contains BPP∪NP.

Kempe, Kobayashi, Matsumoto, Toner, and Vidick [KKMTV11] shows that every problem in NP has a three-prover one-round interactive proof system with perfect completeness and soundness error 1−1/poly where the total length of messages is O(log n) bits, and the soundness holds against entangled provers.  Therefore, MIP* with total message length O(log n) bits and bounded error contains NP.  A later result by Ito, Kobayashi, and Matsumoto [IKM09] (shameless plug) reduces the number of provers from three to two.  The case of constant soundness is open at the top of my knowledge.

It is not known whether MIP* with total message length O(log n) bits is contained in the class R of decidable problems or not, and this question is equivalent to whether MIP*⊆R (another open problem) by the padding argument.

References

[GH98] Oded Goldreich and Johan Håstad.  On the complexity of interactive proofs with bounded communication.  Information Processing Letters, 67(4):205–214, Aug. 1998.  http://dx.doi.org/10.1016/S0020-0190%2898%2900116-1

[IKM09] Tsuyoshi Ito, Hirotada Kobayashi, and Keiji Matsumoto.  Oracularization and two-prover one-round interactive proofs against nonlocal strategies.  Proceedings: Twenty-Fourth Annual IEEE Conference on Computational Complexity (CCC 2009), 217–228, July 2009.  http://dx.doi.org/10.1109/CCC.2009.22

[KKMTV11] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick.  Entangled games are hard to approximate.  SIAM Journal on Computing, 40(3):848–877, 2011.  http://dx.doi.org/10.1137/090751293


Piecewise Linear Circuit Identity Testing A circuit is used to express a piecewise linear function of one variable $\ f:\mathbb{Q}\to\mathbb{Q}$  The component gates are:

add the outputs of two other gates together
scale the output of one other gate by some constant
offset the output of one other gate by some constant
take as input the outputs of three other gates, labeled X, Y, C.  If C is less than some constant, output X from this gate, otherwise output Y

Given such a circuit, how efficiently can one verify whether $f(x)=0$ for all $x$?

My apologies that I don't have references to possibly related problems.  I tried searching piecewise linear (identity/equivalence) testing without much luck.  Randomized polynomial identity testing could possibly be tropicalized, but I don't have high hopes for that avenue of attack.

Also, I should mention that this came out of a practical problem involving document layout, in case the existence of applications is motivational.

Addendum:  Here is a non-standard "circuit" problem, which is closer to the intended application.

Consider a DAG with a unique root.  Each node in the DAG represents a function of type $f:\mathbb{Q}\to\mathbb{Q}$:

Leaf $\ f(w) = w\ $ This node has no children.
Linear $\ f(w) = child(aw + b)\ $ This node has one child, with function $child(w)$
Branch $\ f(w) = \left\{\begin{array}[ll]\\ left(w) & w < c\\ right(w) & w\geq c\end{array}\right.\ \ $  This node has two children, whose functions are $left(w)$ and $right(w)$ respectively.

Then, the DAG as a whole represents a piecewise linear function, namely the composition of the atomic functions beginning at the root.  Again, the problem is to determine whether the piecewise linear function is $0$. Or, equivalently (I haven't verified the reduction works both ways) whether for two such piecewise linear functions $f=g$?

In the general case, your problem is NP-hard, if you are working over a finite field (say, the integers modulo $p$).  It is easy to see that the language of such circuits that are not identically zero is in NP (if it isn't identically zero, there exists a witness: an input that makes its output non-zero).

Also, we can reduce SAT to this problem.  Consider a formula $\varphi$ in CNF, over variables $x_1,\dots,x_n$.  As is standard, we'll let $1$ represent "true" and $0$ represent "false".  Now it is easy to build a subcircuit that computes logical NOT ($x \mapsto 1-x$, and $1-x$ is linear), a subcircuit that computes logical OR (using your conditional gates), and a subcircuit that computes logical AND (again, using your conditional gates).  Thus, we can transform $\varphi(x_1,\dots,x_n)$ to one of your circuits, where the inputs are $x_1,\dots,x_n$ and the output is the truth value of $\varphi(x_1,\dots,x_n)$.  This circuit will be not identically zero if and only if $\varphi$ is satisfiable.  Also, the size of this circuit is polynomial in the size of $\varphi$.  Thus, if we could solve your problem in polynomial time for arbitrary circuits, then we could solve SAT in polytime and we'd have $P=NP$ -- which seems unlikely.

So, you should not expect an efficient and fully general solution to your problem, at least if you are working over a finite field.

If you are working over $\mathbb{Q}$ or $\mathbb{R}$, I don't have a proof that your problem is NP-hard (I suspect it probably still will be but I have no proof).

Of course, one pragmatic approach might be to try converting your problem to a SAT instance and applying an off-the-shelf SAT solver.  If you are working over the integers ($\mathbb{Z}$), you might also want to try formulating it as an integer linear programming (ILP) problem and then apply an off-the-shelf ILP solver.

Depending upon the size and complexity of your circuits, this might work reasonably well in practice -- though there is no guarantee that it will always run efficiently.

Incidentally, your problem is equivalent to the question: "given a linear decision tree, test whether its output will be identically zero for all inputs".

The equivalence can be seen by topologically sorting the circuit so it can be computed sequentially, and then noting that it forms a decision tree: each of the first three gates can be absorbed into the linear expression, and each instance of the fourth gate corresponds to a boolean decision (testing whether some linear expression of the inputs is $\ge 0$ or not).  In the subtree where this value is $<0$, you substitute in $X$ for each mention of the output of this gate; and substitute $Y$ in the subtree where this value is $>0$.  The depth of the decision tree is equal to the number of type-4 gates in your circuit.

I don't know the complexity of this problem, but perhaps these search times will help you identify whether there is anything relevant in the literature.


Featherweight Generic Java formalization in Coq I've been searching for some nice formalization of FGJ (Featherweight Generic Java) in Coq. I am going to develop an extension of FGJ in Coq, so I hope there is an appropriate Coq implementation which I can base my work on.

I have found this one. I haven't yet read corresponding paper carefully, but it looks like a whole «framework» for building up FGJ extensions. The Coq files seem to be quite difficult to dive in (probably after reading the paper they'll become clearer).

Is anybody aware of another Coq formalizations of FGJ?

I guess somewhat more realistic task would be to find Coq's formalisation of FJ itself (probably with some extensions, but not necessarily FGJ). The one which I googled easily is:

  Encoding Featherweight Java with Assignment and
  Immutability using The Coq Proof Assistant by Mackay et al. (2012)

[the paper, PDF],
[Coq sources, ZIP].

Seems a little bit more recent than the one you mentioned. They also mention Delaware et al. (your reference) in Related work section.


Enumerator for the language w#w^R? I'm trying to build a Turing machine diagram for the language w#w^R, where w^R is the reverse of w, and w is a word made up of 0's and 1's. I'm trying to think of an algorithm but I can't think of something not extremely complicated that goes over all combinations of the alphabet for a given word length, then type # onto the print tape and copies it back in reverse.

Is there something I'm missing here? Could there be a simpler algorithm here?

Thanks in advance.

Here is a simple Turing machine segment that reads a binary word $w$ starting at a position immediately to the right of the delimeter symbol # and replaces it with $w$'s successor in the lexicographic ordering. Here, L,R,S indicate moving the read/write head Left, Right, or Stay.

This simple and powerful (standard) trick avoids a brute-force enumeration by using the results of previous computations to produce future ones. If you're allowed multiple tapes, it's now quite easy to accomplish the task you defined. Otherwise, there are standard $k$-tape to $1$-tape conversions.


Approximate bound/algorithm for "product of sums maximization" problem I am looking for some approximate algorithm with upper/lower bound for the following problem:

Given a set of positive integers $\{a_1, a_2, \dots, a_n\}$, partition $\{1, 2, \dots, n\}$ into disjoint sets $S_1, S_2, \dots, S_k$ so that the following function is maximized:

$$
\prod_{i=1}^{n} \sum_{j \in S_i} a_j
$$

Here is a few things I guess about the above problem (Let's call it PSM),

PSM is very similar to the multi-processor scheduling problem (with k processors and $a_i$'s as the job lengths) with a slightly different objective function. This is quite simple to show that PSM is at least as hard as multi-processor scheduling problem. Assume we are given a solution to PSM. The makespan of the solution must be minimum (it means this is a solution to the multi-processor scheduling problem as well), otherwise the product of sums is not maximized (right?).
We cannot have an FPTAS for PSM since multi-processor scheduling is strongly NP-hard.
For $k$ even, assume we have a $(1+\alpha)$-approximate algorithm for the multi-processor scheduling problem. The algorithm gives an upper bound of $(1-\alpha^2)^{k/2}$ for the PSM problem. That's because the worst case happens when $k/2$ of the sums are $(1+\alpha)\times OPT_{makespan}$ and the rest of them are equal to $(1-\alpha)\times OPT_{makespan}$. Therefore, we find a $((1+\alpha)(1-\alpha))^{k/2} \times OPT_{PSM}$ solution.

By the way, this is a wireless network scheduling problem. I have already discussed a variation of the problem here.
Any hint, solution, inapproximability result, reference to a book or a paper is appreciated.

Intuitively, you are looking for partitioning the given numbers into k sets that are all have the same sum. Indeed, otherwise, you can benefit by taking two of these sets, and make them as balanced as possible.

As such, you can take an approximation algorithm for subset sum, and turn it into an approximation algorithm to partition. Then extend it to handle $k$-sides partitions, and you would get the required approximation. See for example here: http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/08_approx_III.pdf

Then you need to modify it to care about your target function....

I assume that going through the details, you would get an $(1+\epsilon)$-approximation algorithm and its running time would be $(n/\epsilon)^{O(k)}$. But better running time might be possible if you are more careful.


Find two sequences of integers that have sum N but that don't have sub-sequences starting at the head of equal sum This question arose from a discussion between a friend and I.

$A$ is a sequence of length $T$ where for any $a_i$ in $A$,  $a_i \in  \left\{{1, 2, 3}\right\}$

$B$ is a sequence of length $U$ where for any $b_i$ in $B$,  $b_i \in  \left\{{1, 2, 3}\right\}$

And the following conditions:

1) They possess equal sum,

$N = \sum_{\forall a \in A} a = \sum_{\forall b \in B} b$

2)  They don't possess sub-sequences starting at the head of equal sum,

$\sum_{i=1}^c a_i \neq \sum_{i=1}^d b_i$

for any $c < T$ and $d < U$,

where $a_i \in A$ and $b_i \in B$

Question: For given $N$, find an algorithm that calculates in polynomial time the number of possible pairs $(A, B)$ that satisfy these conditions.

It's very easy to write an algorithm that satisfies condition 1) using dynamic programming, but I simply cannot figure out how to make it satisfy 2) as well.

Good luck!

You can solve this with dynamic programming as well.

To see this, first realize you can see this problem as splitting the numbers between $0$ and $N$ into two subsets $X$ and $Y$ (the cumulative sums) that cannot overlap except at $0$ and $N$ (and must overlap there), and where the difference between consecutive elements of a subset is at most 3.

Reformulating the problem this way, you can have the state of your dynamic programming be:

"The number of ways of splitting the numbers between $0$ and $i-1$ into two sequences in the fashion described in the second paragraph, where the the numbers in positions (i, i-1, i-2) have assignments (j,k,h)", with $3 \leq i \leq N-1$, and $(j,k,h) \in \{X,Y,None\}$.

Using the states for $i=k$ to compute the states for $i=k+1$, it does take $\Theta(N)$ time to compute this. Let me know if more details are required.

Edit: I had missed in the previous answer the fact that $T$ and $U$ are fixed. You can take care of this by adding in your state how many positions so far have assignment to $X$, and how many have assignments to $Y$. Sadly, this brings the complexity up to $\Theta(T*U*N)$. Also, note that the solution generalizes to a larger number of sequences, and their values being in a larger range $\{1, \ldots, k \}$.


Tight Lower bounds on Savitch's theorem First of all, I apologize in advance for any stupidity. I am by no means an expert on complexity theory (far from it! I am an undergraduate taking my first class in complexity theory) Here's my question. Now Savitch's Theorem states that
$$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right)$$
Now I'm curious if if this lower bound was tight, i.e that is something along the lines of
$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^{1.9}\right)$ is not achievable.

It seems like something there should be a straightforward combinatorial argument to be made here - each node in the configuration graph for a Deterministic Turing machine has only one outgoing edge, while each node in the configuration graph of a Non-Deterministic Turing machine can have more than one outgoing edge. What Savitch's algorithm is doing is converting configuration graphs with any number outgoing edge to configuration graphs with $<2$ outgoing edges.

Since the configuration graph defines a unique TM (not sure about this), the combinatorial size of the latter is almost certainly larger than the former. This "difference" is perhaps a factor of $n^2$, perhaps less - I don't know. Of course, there are lots of little technical issues to be worked out, like how you need to make sure there are no loops and so forth, but my question is if this is a reasonable way to begun proving a thing like this.

This is a well known open question. You will see in complexity theory many open questions for which you'd wonder how come no one managed to solve them. Part of the reason is that we need new people like you to help us solve them :)

For the latest result in this area, showing that Savitch's algorithm is optimal in some restricted model, see Aaron Potechin's FOCS paper.

Specifically, he starts from the nice observation that because the configuration graph of a deterministic TM has only one outgoing edge (after fixing the input), one can think of it as an undirected graph, and so the question becomes something like the following: given a directed graph $G$ of $n$ vertices with two special vertices $s,t$, if we map it to an $N$ vertex undirected graph $G'$ (also with special vertices $s',t'$) such that the existence of each edge in $G'$ depends on one edge in $G$ and there is a path from $s$ to $t$ in $G$ iff there's a path between $s'$ and $t'$ in $G'$, how much bigger $N$ has to be from $n$.

To show that Savitch's algorithm is optimal, one needs to show that $N$ has to be at least $2^{\Omega(\log^2 n)}  = n^{\Omega(\log n)}$. To show $L\neq NL$, it suffices to show the weaker bound that $N > n^c$ for every constant $c$.  I'm pretty sure that even $N > n^{10}$ is not known, though perhaps something like $N \geq n^2$ is known for some not so interesting reasons.


LTL property - safety or liveness? How can I check if an LTL (Linear Temporal Logic) property is safety or liveness? Is it right to say that a property is safety OR liveness (or neither)?

How can I evaluate this:

G(x -> (a U y) )

Your first question is answered in this paper: https://www.cs.cornell.edu/fbs/publications/RecSafeLive.pdf
Given an LTL formula, translate it into a Büchi automaton, and remove states that have no path to an accepting state. Then, change all states to be accepting. If the language of the automaton does not change, then the property is a safety property. If the language of the automaton becomes $\Sigma^\omega$, then it is a liveness property.


How can you state how abstract interpretation gets around Rice's Theorem succinctly? At this question, abstract interpretation has a nice in-depth look. However, I'd like someone to clearly and very precisely state how abstract interpretation takes the result of Rice's Theorem over the Turing-complete programming languages/Turing machines, and uses abstract interpretation to get similar results for decidability for non-trivial program properties; or, rather, how does abstract interpretation get around Rice's Theorem/the Halting Problem?

To be as clear and concise as possible, I'd try saying this

  Abstract interpretation may only over-approximate properties of programs: the most precise abstract value of a program $P$ may be $a$, but any algorithm for computing an abstract value will in general compute some value $a'\geq a$ for $P$ (possibly $\top$ in the worst case).


Edit distance algorithms that depend on alphabet The best known algorithm for computing the exact edit distance between two strings is I believe an algorithm by Masek and Paterson that runs in time $O(n^2/\log^2 n)$, for binary alphabets.

Is there any algorithm that possibly by taking advantage of larger alphabet sizes (and potentially the possibility of few matches to explore) can run in time that might be strictly better than the above bound for large (i.e non-constant sized) alphabets ? Or is there some easy reason why this would be as hard as the case for a binary alphabet ?

The answer is certainly yes. Assume for simplicity that the two strings are of equal length $n$. If the "induced" alphabet of each string is also of size $n$, then both strings are permutations, and the problem degenerates to the classical longest increasing subsequence (LIS) problem: it is easy to see that the edit distance between a given permutation $\pi$ and the sorted permutation $1,2,\ldots,n$ is $n-LIS(\pi)$. The LIS problem was studied as early as 1930s by Erdos and Szekeres, and by Robinson. The best algorithms for LIS run in time $O(n \log n)$ or $O(n \log\log n)$, depending on the computation model. Such algorithms were (re)discovered dozens of times (or perhaps hundreds of thousands, considering that the problem makes a good programming exercise), often with various twists. It is easy to find the relevant papers, since most of them cite previous work. The most recent result I am aware of, and a good point to start exploring the references, is the $O(n \log\log LIS(\pi))$ algorithm by Crochemore and Porat:

M. Crochemore and E. Porat. Fast computation of a longest increasing subsequence and application. Information and Computation, 208(9):1054--1059, 2010. http://dx.doi.org/10.1016/j.ic.2010.04.003

The same paper also describes how to interpolate between this extreme case and the general edit distance problem, taking the total number of character matches as a parameter. This is relevant when your "induced" alphabet size is large, but not exactly equal to $n$. For smaller "induced" alphabet sizes (say $n/2$), it is easy to construct examples that are essentially binary over a significant part (say, one half) of each input string, so a large "induced" alphabet over the whole string won't help more than by a constant factor.