Is pooling-aware bin packing NP-Hard? I am unable to prove whether the following problem is NP-Hard. It seems like a bin-packing or a partition problem, without being close enough to either of them (at least I do not see the reduction to them).

  Pooling-aware bin packing

  Consider 2 sets of non-negative numbers
  $$a=\{a_1,a_2,...,a_n\}\\b=\{b_1,b_2,...,b_n\}.$$ Which is the size of the smallest
  partition $P$ for the values $1$ to $n$ such that for every subset
  $S=\{ (a_i,b_i), (a_j,b_j),\ldots\}$ in the partition $$\max_{i\in S}a_i+\max_{j\in S}b_j\le1,\qquad \forall S\in P?$$  (I inherently
  assume feasibility, i.e.,  $ a_i+b_i\le1, i=1,...,n$)

  Simple instance:
  $$a=[0.3,0.5,0.4,0.9,0.7]\\ b=[0.6,0.3,0.6,0.1,0.2]$$

  Solution: we need 3 bins

  $[(0.9,0.1)]$
  $[(0.7,0.2),(0.5,0.3)]$
  $[(0.3,0.6),(0.4,0.6)]$

Note that maybe the most similar problem is the one in
Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-3 and discussed in
bin packing with overlapping objects.

Thoughts / similar problems / pointers?

PD: I want to apologize in advance if there is some issue with my question that I am unaware of, I am new here :)

This problem is polynomially solvable.

Claim: solving the problem on input $a = (a_1, \ldots, a_n)$ and $b = (b_1, \ldots, b_n)$ using a partition $P$ is equivalent to choosing a multiset of numbers $X$ with $|X| = |P|$ such that for $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$.

Assuming this claim, solving your problem is equivalent to finding the smallest set $X$ such that for each $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$. For any fixed $i$, this condition can be rewritten as $a_i \le x \le 1-b_i$. Thus, the problem is equivalent to finding the smallest set $X$ which includes at least one point from each interval $[a_i, 1-b_i]$.

It is easy to show that the following algorithm finds an optimal solution:

Algorithm: Initialize $X$ to be the empty set. Scan from 0 to 1. When leaving each interval during this scan, check whether the interval you are leaving already contains a point in $X$. If yes, continue without doing anything. If no, add the current value of the scan-line (i.e. the end of the interval) to $X$. Once you reach the end of the scan, output $X$.

Thus, all that's left is to prove the claim:

proof of claim:

First suppose we have a partition $P$ solving your problem. Then define $X = \{x_S~|~S \in P\}$ where $x_S = \max_{i \in S}a_i$.

If $i' \in \{1, \ldots, n\}$, then $i' \in S$ for some $S \in P$.

Since $i' \in S$, clearly we have that $a_{i'} \le max_{i \in S}a_i$. The RHS, however, is the definition of $x_S$, so this shows $a_{i'} \le x_S$.

By the conditions on the partition, $max_{i \in S}a_i + max_{i \in S}b_i \le 1$, or in other words $max_{i \in S}b_i \le 1 - max_{i \in S}a_i = 1 - x_S$. Simply applying the fact that $i' \in S$, we have that $b_{i'} \le max_{i \in S}b_i$. Putting this together, we see that $b_{i'} \le 1-x_S$.

Thus we have shown that for $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$.

Next suppose that we have a set $X$ such that for $i = 1, \ldots, n$, there exists an $x \in X$ with $a_i \le x$ and $b_i \le 1-x$.

Name the elements of $X$ as $x_1, x_2, \ldots, x_{|X|}$. Then let $S_j = \{i \in \{1,2,\ldots,n\}~|~a_i \le x_j ~\text{and}~ b_i \le 1-x_j\}$. By the property of $X$, every element of $\{1,2,\ldots,n\}$ is in at least one $S_j$. Then if we define $S_j' = \{i \in S_j~|~i \not\in S_{j'} ~\text{for}~j'<j\}$, we see that sets $S_1', \ldots, S_{|X|}'$ form a partition of $\{1,2,\ldots,n\}$.

We claim that this partition is a valid solution to your problem. Consider any part $S_j'$ in this partition. Since $S_j' \subseteq S_j$, we have that $\max_{i \in S_j'}a_i \le \max_{i \in S_j}a_i \le x_j$
and $\max_{i \in S_j'}b_i \le \max_{i \in S_j}b_i \le 1-x_j$,
and so we see that $\max_{i \in S_j'}a_i + \max_{i \in S_j'}b_i \le x_j + 1-x_j = 1$. This is sufficient to show that the partition is a valid solution to your problem.


How good is the Huffman code when there are no large probability letters? The Huffman code for a probability distribution $p$ is the prefix code with the minimum weighted average codeword length $\sum p_i \ell_i$, where $\ell_i$ is the length of the $i$th codword. It is a well-known theorem that the average length per symbol of the Huffman code is between $H(p)$ and $H(p)+1$, where $H(p) = -\sum_i \, p_i \log_2 p_i$ is the Shannon entropy of the probability distribution.

The canonical bad example, where the average length exceeds the Shannon entropy by almost 1, is a probability distribution such as $\{.999, .001\}$, where the entropy is nearly 0, and the average codeword length is 1. This gives a gap between the entropy and the codeword length of almost $1$.

But what happens when there is a bound on the largest probability in the probability distribution? Suppose, for example, that all the probabilities are less than $\frac{1}{2}$. The largest gap I could find in this case is for a probability distribution such as $\{.499, .499, .002\}$, where the entropy is slightly more than 1 and the average codeword length is slightly less than 1.5, giving a gap approaching $0.5$. Is this the best you can do? Can you give an upper bound on the gap that is strictly less than 1 for this case?

Now, let's consider the case where all the probabilities are very small. Suppose you choose a probability distribution over $M$ letters, each having probability $1/M$. In this case, the largest gap occurs if you choose $M \approx 2^k \ln 2$. Here, you get a gap of around
$$ \frac{1 + \ln \ln 2 - \ln 2}{\ln 2} \approx 0.08607. $$
Is this the best you can do in the situation where all the probabilities are small?

This question was inspired by this TCS Stackexchange question.

There are lots of papers that study exactly the problem you mention. The first in the series is a paper by Gallager, "Variations on a Theme by Huffman", IEEE-IT, vol. 24, 1978, pp. 668-674. He proves that the difference between the average codeword length of an Huffman code and the entropy  (he calls that quantity "redundancy") is always strictly less than $p$ (= largest probability in the probability distribution), in the case  $p\geq 1/2$, and it is less than $p+0.086$, if $p<1/2$. Better bounds are known, you can find them in the numerous papers that quote Gallager work.


Language with extensible type system? Is there a practical programming language that has an extensible type system?
Or alternatively, an add-on type system that can be used with existing languages?

With extensible I mean that the typing rules are specified externally and can be changed by the user without rewriting the typechecking code.

The use would be to add additional checkable constraints to a program (for example physical dimensions, uniqueness types, reference frames, nulled memory etc.).

In the programming language part, one would annotate the expressions with their types:

    import units # library for physical units
    # x has type float and the type meter
    x:{float,units.meter}
    y:{float,units.meter**2}
    def f(x): return x*x
    y=f(x)

(I am using Python as an example language as the semantics are independent of the optional type annotations, but any language would do)

In the above case x has multiple types: float and a physical dimension.
Each of those have different typing rules, and it makes sense to treat them differently.
In the units type library, we would provide typing rules of the following form (assuming that the rules for float are defined elesewhere):
$$\frac{\Gamma \vdash x:Meter, n:Nat, m:Nat}{\Gamma \vdash x^\frac{n}{m}:Meter^\frac{n}{m}}$$

While for example physical dimensions can be dealt with through a runtime library somewhat unsatisfactorily, doing dimensional analysis with the tools of types is much more elegant, doesn't incur any runtime overhead and proves dimensional correctness.

For example, the only mainstream language that I am aware of that provides physical dimensions is F#, but unfortunately it is broken as it does not support fractional exponents https://stackoverflow.com/questions/11333135/fractional-power-of-units-of-measures-in-f/11334159#11334159
Providing the physical dimensions as a typing library instead of a language internal would allow the user to fix this problem and add other dimensional systems, like directional units or Siano's orientational dimensions.

The annotated AST and the typing rules would be processed by a constraint solver to issue type errors and warnings for insufficiently typed expressions.

Why am I asking for this?

It would be great for understanding type systems
Existing software could be made more secure by adding extra type constraints.

There's support for extensible type systems in JetBrains MPS (http://www.jetbrains.com/mps/). Basically it has a constraint solving engine which supports both equations (type equalities) and inequalities (subtyping). Extensions add new rules of adding constraints which are solved by the engine.

P.S. I think the question is more appropriate for stackoverflow than cstheory.


The dependence of learning generalization bounds on the dimension of the instance space Here is a popular generalization bound:

  If $X$ is the input space and
  $Y=\{0, 1\}$ is the output/label space, and
  there is a joint distribution $D$ defined on this space.
  We sample $m$ points from this joint distribution as observation/training data:
  $S = ((x_1, y_1)\ldots(x_m,y_m)) \in (X\times Y)^m$.
  Suppose $H$ is a class we (user) are choosing from, and $h \in H$.

  Define the risk (true expected error) as
  $$L_D(h) := \Pr_{(x,y)\sim D} [h(x)\neq y]$$
  the empirical risk as
  $$L_S(h) := \frac{1}{m}\sum_{i=1}^m l(h,z_i)$$
  where $z_i = (x_i, y_i)$.

  Then, with probability of at least $1 − \delta$ we have
  $$\forall h\in H, L_D(h) \leq L_S(h) +
c\sqrt{\frac{VCdim(H)+ \log(2/\delta)}{2m}} $$

Question:
Any intuition why the dimension of instance space $X$
and its size $|X|$ do not come into play in this inequality?
Intuitively the bigger the dimension is,
the harder the estimation problem should be.
(E.g. $X = \mathbb{R}^d$,
$|\mathbb{R}|=\infty$ should be harder than $|\{x\}|=1$.)

I think the VC-dimension term pretty much takes care of it. You can think of three cases:

The hypothesis space $H$ is far more "complex" than the input space $X$
$H$ and $X$ are matched up well to each other
$H$ is much "simpler" than $X$

We are usually only motivated by the second and third cases, so the VC-dimension term in your bound captures what we care about.

For example in $X=\mathbb{R}^d$, you probably want to choose a hypothesis class that depends on $d$, for instance halfspaces in $\mathbb{R}^d$, and so $d$ shows up in the VC-dimension term (in the case of halfspaces, this is $d+1$).

There are also some examples of classes with finite VC-dimension that are still interesting. Here even if $X$ is "large" or complex, we can get a small bound.


P-complete decision problems about integers Are there any known examples of P-complete decision problems which take as input a single integer? (non-unary, as unary feels like un-naturally forcing the issue)

It feels like there are many inherently sequential questions I could ask about an integer, but I don't know of any examples that have been shown to be P-complete.

Not quite what you're looking for, but the iterated mod problem is a P-complete number-theoretic decision problem.


Computing the convex hull of lattice points Consider a set of $n$ points in $\mathbb Z^2$. It is known that their convex hull can be computed in time $O(n\log n)$, or even $O(n\log h)$ where $h$ is the number of points in the convex hull. These bounds are in given (for instance) in the model of algebraic decision trees.

What is the bit-complexity of computing the convex hull of $n$ points in $\mathbb Z^2$, whose both coordinates are bounded in absolute value by $M$?

I am interested on the one hand in the dependence of the complexity in $M$, and on the other hand in the possible gain in complexity one obtains using the fact that the input points have integer coordinates. In my problem, I see $M$ as a large parameter, that is $\log(M)$ has the same order of magnitude as $n$.

Note that I am especially interested in the problem with the additional requirement that the points on the convex hull have to be listed in the order of the (say) counterclockwise rotation, beginning for instance at the leftmost point.

I am also interested in the same questions in higher dimensions.

The time is essentially the same as that for sorting numbers in the range $1,\dots M$.

Graham scan (in the version where the points are sorted by their x-coordinates (with ties broken by y coordinates) rather than the one the textbooks unaccountably use in which they are sorted radially) can find convex hulls in linear time after the sorting step. So for your problem in which the coordinates are small integers, all the standard bounds of integer sorting apply. In particular, radix sort can achieve time $O(n(1+\frac{\log M}{\log n}))$ (e.g. linear time whenever $M$ is at most polynomial in $n$), and a randomized sorting algorithm of Han & Thorup 2002 can achieve time $O(n\sqrt{\log\log n})$. These are in models of computation in which machine words hold integers of some word length that is big enough to store the numbers $n$ and $M$ and in which one can do arithmetic and table lookups in constant time.

Conversely, you could use a convex hull algorithm to sort a set of numbers $x_i$, by finding the hull of the points $(x_i,x_i^2)$. So if you could do convex hulls any faster than this, you could also improve the times for integer sorting. (The range $M$ of $y$-coordinates of these points would be the square of the range of the numbers, but since all the time bounds involve logarithms of this range, squaring $M$ makes no difference in terms of the eventual $O$-notation.)


Complexity lower bound for regular languages Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states.

I would like to claim that determining the membership of a string of length $n$ in $L$ requires time $\Omega(n\log N)$. The dependence on $n$ is obvious -- I have to read the whole string, in general, to know if it belongs to a language. The $\log N$ factor is because to know what state I am in I need to write it down, and this takes time $\log N$.

This requires arguing that there is no faster way to determine membership in $L$ than to run its minimal DFA (implicitly or explicitly). I think such an argument can be formalized (via equivalence classes, for example), but perhaps I am being naive.

Question: Is the $\Omega(n\log N)$ lower bound correct?

Edit: let me make this more formal. Is there an infinite family of distinct minimal DFAs $A_1, A_2,..$ such that some algorithm simulating the $\{A_i\}$ on a deterministic RAM machine can determine membership of $x$ in $L(A_i)$ in time $o(|x|\log|A_i|)$, where $|x|$ is string length and $|A_i|$ is the number of states?

Edit2: Kaveh's and Aaron's answers seem to indicate that my lower bound is false. But I would love to see a non-trivial counter example. Suppose:
(a) I have a family of regular languages $\{L_n\}$
(b) each $L_n$ has a compact description (say, as an NFA) of size $poly(n)$, but the minimal DFA for $L_n$ has size $2^n$
(c) for each $n$, there is no fixed-length prefix that determines membership in $L_n$ (this rules out Kaveh's examples -- you really do need to read the whole string)

Can somebody give an example of a family $L_n$ satisfying (a,b,c) for which there is a TM taking $n$ and $x\in\Sigma^*$ as inputs and deciding $x\in?L_n$ in time $o(n|x|)$?
[Note that we've switched from RAM to TM as the computational model; $n$ is given in binary.]

I'll answer my own question -- the conjectured lower bound is false. Consider
$L_n=\Sigma^* 0 \Sigma^n$ (that is, the collection of all strings with a $0$ in the $n$th location from the end). It's easy to see that there is an $O(n)$ size NFA for $L_n$, but the minimal DFA for $L_n$ is exponential. Here is a TM that decides membership in $L_n$ in time $O(|x|+n)$: scan $x$ to the end (time $|x|$) and read $n$ steps back to see if that letter is $0$.


The problem of deciding whether a monotone CNF implies a monotone DNF Consider the following decision problem

Input: A monotone CNF $\Phi$ and a monotone DNF $\Psi$.

Question: Is  $\Phi \to \Psi$ a tautology?

Definitely you can solve this problem in $O(2^n \cdot \mathrm{poly}(l))$-time, where $n$ is the number of variables in  $\Phi \to \Psi$ and $l$ is the length of input. On the other hand, this problem is coNP-complete. Moreover, a reduction which establishes coNP-completeness also shows that, unless SETH fails, there is no  $O(2^{(1/2 - \varepsilon)n} \mathrm{poly}(l))$-time algorithm for this problem (this holds for any positive $\varepsilon$). Here is this reduction. Let $A$ be a (non-monotone) CNF and let $x$ be its variable. Replace every positive occurence of $x$ by $y$ and every negative occurence of $x$ by $z$. Do the same for every variable. Let the resulting monotone CNF be $\Phi$. It is easy to see that $A$ is satisfiable iff $\Phi \to yz \lor \ldots $ is not a tautology. This reduction blows up the number of variables by a factor of 2, which implies $2^{n/2}$ (SETH-based) lower bound mentioned above.

So there is a gap between $2^{n/2}$ and $2^n$-time. My question is whether any better algorithm or better reduction from SETH is known?

Just two remarks seemingly related to the problem:

a reverse problem of whether a monotone DNF implies a monotone CNF is trivially solvable in polynomial time.
interestingly, the problem of deciding whether $\Phi$ and $\Psi$ compute the same function   can be solved in quasi-polynomial time due to Fredman and Khachiyan (On the Complexity of Dualization of Monotone Disjunctive Normal Forms, Journal of Algorithms 21 (1996), no. 3, pp. 618–628, doi: 10.1006/jagm.1996.0062)

Assuming SETH, the problem is not solvable in time $O\bigl(2^{(1-\epsilon)n}\mathrm{poly}(l)\bigr)$ for any $\epsilon>0$.

First, let me show that this is true for the more general problem where $\Phi$ and $\Psi$ may be arbitrary monotone formulas. In this case, there is a poly-time ctt reduction from TAUT to the problem that preserves the number of variables. Let $T^n_t(x_0,\dots,x_{n-1})$ denote the threshold function
$$T^n_t(x_0,\dots,x_{n-1})=1\iff\bigl|\{i<n:x_i=1\}\bigr|\ge t.$$
Using the Ajtai–Komlós–Szemerédi sorting network, $T^n_t$ can be written by a polynomial-size monotone formula, constructible in time $\mathrm{poly}(n)$.

Given a Boolean formula $\phi(x_0,\dots,x_{n-1})$, we may use De Morgan rules to write it in the form $$\phi'(x_0,\dots,x_{n-1},\neg x_0,\dots,\neg x_{n-1}),$$
where $\phi'$ is monotone. Then
$\phi(x_0,\dots,x_{n-1})$ is a tautology if and only if the monotone implications
$$T^n_t(x_0,\dots,x_{n-1})\to\phi'(x_0,\dots,x_{n-1},N_0,\dots,N_{n-1})$$
are valid for every $t\le n$, where
$$N_i=T^{n-1}_t(x_0,\dots,x_{i-1},x_{i+1},\dots,x_{n-1}).$$

For the left-to-right implication, let $e$ be an assignment satisfying $T^n_t$, i.e., with at least $t$ ones. There exists $e'\le e$ with exactly $t$ ones. Then $e'\models N_i\leftrightarrow\neg x_i$, thus $e'\models\phi$ implies $e'\models\phi'(x_0,\dots,x_{n-1},N_0,\dots,N_{n-1})$. Since this is a monotone formula, we also have $e\models\phi'(x_0,\dots,x_{n-1},N_0,\dots,N_{n-1})$. The right-to-left implication is similar.

Now, let me return to the original problem. I will show the following: if the problem is solvable in time $2^{\delta n}\mathrm{poly}(l)$, then for any $k$, $k$-DNF-TAUT (or dually, $k$-SAT) is solvable in time $2^{\delta n+O(\sqrt{kn\log n})}\mathrm{poly}(l)$. This implies $\delta\ge1$ if SETH holds.

So, assume we are given a $k$-DNF
$$\phi=\bigvee_{i<l}\Bigl(\bigwedge_{j\in A_i}x_j\land\bigwedge_{j\in B_i}\neg x_j\Bigr),$$
where $|A_i|+|B_i|\le k$ for each $i$. We split the $n$ variables into $n'=n/b$ blocks of size $b\approx\sqrt{k^{-1}n\log n}$ each. By the same argument as above, $\phi$ is a tautology if and only if the implications
$$\tag{$*$}\bigwedge_{u<n'}T^b_{t_u}(x_{bu},\dots,x_{b(u+1)-1})\to
\bigvee_{i<l}\Bigl(\bigwedge_{j\in A_i}x_j\land\bigwedge_{j\in B_i}N_j\Bigr)$$
are valid for every $n'$-tuple $t_0,\dots,t_{n'-1}\in[0,b]$, where for any $j=bu+j'$, $0\le j'<b$, we define
$$N_j=T^{b-1}_{t_u}(x_{bu},\dots,x_{bu+j'-1},x_{bu+j'+1},\dots,x_{b(u+1)-1}).$$
We can write $T^b_{t}$ as a monotone CNF of size $O(2^b)$, hence the LHS of $(*)$ is a monotone CNF of size $O(n2^b)$. On the right-hand side, we may write $N_j$ as a monotone DNF of size $O(2^b)$. Thus, using distributivity, each disjunct of the RHS can be written as a monotone DNF of size $O(2^{kb})$, and the whole RHS is a DNF of size $O(l2^{kb})$. It follows that $(*)$ is an instance of our problem of size $O(l2^{O(kb)})$ in $n$ variables. By assumption, we may check its validity in time $O(2^{\delta n+O(kb)}l^{O(1)})$. We repeat this check for all $b^{n'}$ choices of $\vec t$, thus the total time is
$$O\bigl((b+1)^{n/b}2^{\delta n+O(kb)}l^{O(1)}\bigr)=O\bigl(2^{\delta n+O(\sqrt{kn\log n})}l^{O(1)}\bigr)$$
as claimed.

We get a tighter connection with the (S)ETH by considering the bounded-width version of the problem: for any $k\ge3$, let $k$-MonImp denote the restriction of the problem where $\Phi$ is a $k$-CNF, and $\Psi$ is a $k$-DNF. The (S)ETH concerns the constants
$$\begin{align*}
s_k&=\inf\{\delta:k\text-\mathrm{SAT}\in\mathrm{DTIME}(2^{\delta n})\},\\
s_\infty&=\sup\{s_k:k\ge3\}.
\end{align*}$$
Likewise, let us define
$$\begin{align*}
s'_k&=\inf\{\delta:k\text-\mathrm{MonImp}\in\mathrm{DTIME}(2^{\delta n})\},\\
s'_\infty&=\sup\{s'_k:k\ge3\}.
\end{align*}$$
Clearly,
$$s'_3\le s'_4\le\dots\le s'_\infty\le1$$
as in the SAT case. We also have
$$s'_k\le s_k,$$
and the double-variable reduction in the question shows
$$s_k\le2s'_k.$$
Now, if we apply the construction above with constant block-size $b$, we obtain
$$s_k\le s'_{bk}+\frac{\log(b+1)}b,$$
hence
$$s_\infty=s'_\infty.$$
In particular, SETH is equivalent to $s'_\infty=1$, and ETH is equivalent to $s'_k>0$ for all $k\ge3$.


Algorithm for ranking members of a regular language? A little while back, I was reading a paper that mentioned a method for computing an integer 'rank' for a particular string $s \in L$ where $L$ is some regular language. This rank uniquely determines any string in the language and has the property that, for some lexicographic ordering, $s_1 < s_2 \implies rank(s_1) < rank(s_2)$. Another property is that given $rank(s_0)$ we can efficiently determine $s_0$ using an 'unrank' algorithm.

However, the paper wasn't very specific and I don't know where to find a more detailed description of the algorithm. Can anyone point me in the right direction?

I remember that it involves compiling a regular expression to a DFA and giving the description of the DFA to the ranking algorithm.

Thanks for your help.

Let $A = \{1, ..., k\}$ be an ordered alphabet. Then each word on $A^*$ can be viewed as a number in base $k + 1$ (note that $0$ is never used on purpose). Now define
$$
rank(u) = \begin{cases}
u &\text{if $u \in L$} \\
0 &\text{otherwise}
\end{cases}
$$
Then $rank$ preserves the shortlex (or radix) order, which is the order $\leqslant$ on $A^*$ defined by $u \leqslant v$ if and only if $|u| < |v|$ or $|u| = |v|$ and $u \leqslant_{lex} v$. That is, words are first ordered by length and words of equal length are ordered according to the lexicographic order. Now, if $L$ is regular, $rank$ is easy to compute and is of course one-to-one on $L$.


Complexity of DFA intersection in this specific case? In general, the size of the DFA that recognizes the intersection of $n$ languages is exponential in $n$. However, in my case I am computing the intersection of a very restricted subset of possible languages. I am curious if this weakens the lower complexity bound.

With an alphabet $\Sigma$, for the $i$th language, I have set $A_i \subseteq \Sigma$ and another set $B_i \subseteq \Sigma$. The $i$th language $L_i$ consists of strings containing any number of symbols in $A_i$, followed by one symbol in $B_i$, followed by any number of symbols in $\Sigma$. I would like to find a DFA that recognizes $L = L_1 \cap L_2 \cap ... \cap L_n$.

Do these restrictions on the input languages eliminate the exponential lower bound?

The precise bound is $2^n$. The lower bound was given in the comments: the state complexity of $A^*a_1A^* \cap \dotsm \cap A^*a_nA^*$ is $2^n$.
For the upper bound, it suffices to observe that if $B$ and $C$ are subsets of the alphabet $A$, then the language $B^*CA^* = (B - C)^*CA^*$ is recognised by a 2-state DFA. It follows that the complexity of the intersection of $n$ such languages is upper bounded by $2^n$.


Approximate matching in table of integer vectors Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving.

I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain 0-N sorted numbers from range [0,N-1].

Now I have a query vector Q, that - similarly to vectors in the list - can contain 0-N sorted numbers from range [0,N-1]. I have to find time efficient way of finding all vectors in the table that have Jaccard similarity coefficient (T) of k or more.

In this particular case, Jaccard similarity coefficient between two vectors a and b is defined as:

Tqb = Nqb / (Nq + Nb - Nqb)

where Nq and Nb are lengths of vectors and Nqb is the number of common elements.
The naive solution is to compute Tqb between Q and every vector from the table and discard those for which Tqb < k. A little bit better solution is to precompute vectors lengths and consider only vectors of length L such that:

T * Nq <= L <= Nq / T

where Nq is the length of the query vector Q.

Another trick is to notice that out of any

Nq − T * Nq + 1

elements chosen at random from the query vector Q, at least one must be present in any other vector to achieve a similarity above the threshold k.

After applying those two constraints the algorithm is still too slow. The lower the threshold k is, the more vectors pass constraint filtering and the longer it takes to compute coefficient. But unfortunately 'longer' means here exponentially longer not linearly longer, probably due to exponentially larger number of vectors passing filtering phase. Ideally, I would like to achieve constant time of finding similar vectors, regardless of k or Q. I'm not sure if this is possible, thought.

You are asking for the near neighbor problem for the Jaccard index. If you are ok with some approximation and randomization, I think there exist subquadratic algorithms based on Locality Sensitive Hashing (LSH). LSH schemes based on MinWise independent hashing are known for the Jaccard index: see the LSH survey by Andoni and Indyk and references therein, plus the LSH webpage (which has some code, although I am not sure if there is any for Jaccard specifically). Also see the original MinWise hashing paper.


Is there a method of solving the game of "war" I was thinking of determining the game of war. I could write a fairly simple game that takes two "decks" of cards, and plays them against each other but I do not think this is optimal.

Because in war the order of the cards matter it is also not a question of simply summing up the "power" of the cards. If the decks were Q-Q-J-J and K-K-1-1 then the game would go as follows even though the first player has more power:

Q-K (QJJ, K11)

Q-K (JJ, 11QK)

J-1 (J, 1QKQK)

J-1 (1J, QKQK)

1-Q (J1J, KQK)

J-K (1J, QK1Q)

1-Q (J, QK1QJK)

J-K (∅, K1QJK1Q)

∅ (∅, 1QJK1QJK)

I've been trying to think of a method of determine the winner of the game without going through the entire deck each and every time (and thus possibly going for thousands of iterations.)

If you could provide me with some pointers to start thinking about this question - that would be great!

I wasn't exactly sure where to ask this question: so if this is off topic here please redirect me.

I've been working on war for the past couple of days.

In particular I've been interested in the longest possible game, given no cycles. By backtracking, starting from the end position, I managed to avoid anything that goes into cycles. I used a dynamic greater-than relation to avoid having to decide what cards had what value from the start.

Even with those optimizations, I've only managed to create the following table, where the left column is the number of cards in play, and the right column is the length of the longest possible game:

1   0       13  62
2   1       14  467
3   3       15  85
4   7       16  261
5   9       17  107
6   17      18  >=935
7   17      19  137
8   29      21  168
9   31      23  209
10  53
11  45
12  79

Interestingly I found, that odd number of cards, give a much larger chance of cycles. This makes it much easier to find the longest game, as there are far fewer positions to consider. The maximum length of these games is ery close to a second order polynomial.


Which monotone Boolean functions are representable as thresholds on sums? I will introduce my problem with an example. Say you are designing an exam, which consists of a certain set of $n$ independent questions (that the candidates can get either right or wrong). You want to decide on a score to give to each of the questions, with the rule being that candidates with total score above a certain threshold will pass, and the others will fail.

In fact, you are very thorough about this, and you have envisioned all the possible $2^n$ results, and decided for each of them whether a candidate with this performance should pass or fail. So you have a Boolean function $f : \{0, 1\}^n \to \{0, 1\}$ that indicates whether the candidate should pass or fail depending on their exact answers. Of course this function should be monotone: when getting a set of questions right makes you pass, getting any superset right must make you pass as well.

Can you decide on scores (positive real numbers) to give to the questions, and on a threshold, so that your function $f$ is exactly captured by the rule "a candidate passes if the sum of scores for the correct questions is above the threshold"? (Of course the threshold can be taken to be 1 without loss of generality, up to multiplying the scores by a constant.)

Formally: Is there a characterization of the monotone Boolean functions $f: \{0, 1\}^n \to \{0, 1\}$ for which there exist $w_1, \ldots, w_n \in \mathbb{R}_+$ such that for all $v \in \{0, 1\}^n$, we have $f(v) = 1$ iff $\sum_i w_i v_i \geq 1$?

It is not so hard to see that not all functions can be thus represented. For instance the function $(x_1 \wedge x_2) \vee (x_3 \wedge x_4)$ cannot: as $(1, 1, 0, 0)$ is accepted we must have $w_1 + w_2 \geq 1$, so one of $w_1, w_2$ must be $\geq 1/2$, and likewise for $w_3, w_4$. Now, if it is, e.g., $w_1$ and $w_3$, we have a contradiction because $w_1 + w_3 \geq 1$ but $(1, 0, 1, 0)$ is rejected; the other cases are analogous.

This looks to me like a very natural problem, so my main question is to know under which name this has been studied. Asking for a "characterization" is vague, of course; my question is to know whether the class of functions that can be represented in this way has a name, what is known about the complexity of testing whether an input function belongs to it (given as a formula, or as a circuit), etc.

Of course one can think of many variations on this theme. For instance, on real exams, questions are not independent, but there is a DAG on questions indicating the dependence, and candidates can only answer a question if all prerequisites have been answered. The condition on the monotone functions could then be restricted to valuations in $\{0, 1\}^n$ that satisfy the dependencies, and the question would be to determine whether an input function can be thus captured given an input DAG on the variables. One could also think of variants where the scores are $k$-tuples for fixed $k$ (summed pointwise, and compared pointwise to a threshold vector), which can capture more functions than $k = 1$. Alternatively you could want to capture more expressive functions which are not Boolean but go to a totally ordered domain, with different thresholds that should indicate your position in the domain. Last, I'm not sure about what would happen if you allowed negative scores (so you could drop the monotone restriction about the functions).

(Note: What made me wonder about this is the Google Code Jam selection round, where candidates are selected if they reach a certain score threshold, and the scores of problems are presumably carefully designed to reflect what sets of problems are deemed sufficient to get selected. Code Jam has a dependency structure on the questions, with some "large input" questions that cannot be solved unless you have solved the "small input" one first.)

It was mentioned in the comments that these are the positive threshold functions.

As for other characterizations, I found the following to be interesting. Suppose we have a positive threshold function with decreasing weights $w_1\ge w_2\ge\dots w_n$:
$$f(v_1,\dots,v_n)=1 \iff \sum_i w_iv_i\ge 1.$$
Then in particular the set of inputs $(v_1,\dots,v_n)$ for which $f(\vec v)=1$ is an order ideal of the binary majorization lattice with $2^n$ points, which is studied in

  Donald Knuth, "The Art of Computer Programming", Exercise 109 of Section 7.1.1.

To put it informally, $f$ is the kind of function where making earlier bits 1 makes $f$ more likely to be 1: so e.g. $f(0,1,1)\le f(1,0,1)\le f(1,1,0)$. That is, "some bits matter more", and to remove redundant isomorphic cases we assume earlier bits matter more.

However, not all such functions are positive threshold functions! That is, just because you've ordered the exam questions from most important to least doesn't mean your pass/fail rule is based on just adding up some scores.

Indeed, the number of positive threshold functions (with decreasing weights) on $n$ variables is given by the sequence
$$2,3,5,10,27,119,\mathbf{1113},\dots$$
(oeis.org sequence A000617)
whereas the number of such order ideals is
$$2,3,5,10,27,119,\mathbf{1173},\dots$$
(oeis.org sequence A132183)


Is $P^{NPI}$ different from $P^{NP}$? Can we prove that for every language $L\in\mathsf{NP}$ that is not $\mathsf{NP}$-hard (this assumes $\mathsf P \ne \mathsf{NP}$), $\mathsf{P}^L \ne \mathsf{P}^{\text{SAT}}$?  Alternately, can this be proven under any reasonable assumptions?

Depends on your definition of NPI. If A is incomplete for Turing reductions, the answer is yes since SAT is not in $P^A$.

If A is just many-one incomplete then we don't know how to prove it. We have a relativized world with there is a set A in NP such that A is not NP-complete via many-one reductions but SAT can be computed by a single query to A. (Theorem 1.9 in this paper).


Reference for CTL* logic I need a reference for CTL* logic (preferably easy to understand).

I have gathered some disperse information regarding temporal and CTL logic but I need a more orderly coverage. A chapter of the multi-agent systems book I read depends on this subject and I am stuck.

See Venema, Yde. Temporal Logic. The blackwell guide to Philosophical Logic.


Alternating tree automata for arbitrary arity tree Could alternating tree automata be used for recognizing set (language) of arbitrary-arity trees?

More specifically, as an example: let $\Sigma = \{a,b,c\}$ - labels for tree nodes. Trees from $T$ are of the form: from each node only one of the following children could appear: $\{a,b\},\{b\},\{c\}$.

I.e. tree will be of the form, smth like this ($e$ on picture is just root of the tree, indexes on labels are just features of drawing tool, they aren't related to the question):

An alternating tree automaton for arbitrary degree trees has a transition function of the following type:
$$\delta:Q\times \Sigma\times D\to {\cal B}(\mathbb{N}\times Q)$$ where ${\cal B}$ is the set of Boolean functions over the given set.

This has a limitation that $\delta(q,\sigma,d)$ only outputs values between $1,...,d$ (so it fits the degree of the tree).

Thus, the transition function is defined separately for each degree, so it's effectively a family of automata. In particular, this means that if you want to handle arbitrary degrees, you need an infinite description (or a finite description of an infinite object). While this is mathematically possible, it can of course make things undecidable, if (for example) your transition function is given by a TM.

In your example, you can clearly construct such an automaton, since you can construct one for every degree.


Simple and practical deterministic algorithm, complicated running time Very often, if the running time of an algorithm is a complicated expression, the algorithm itself is also complicated and impractical. Each of the cube roots and $\log \log n$ factors in the asymptotic running time tends to add complexity to the algorithm and also hidden constant factors to the running time.

Do we have striking examples in which this rule of thumb fails?

Of course it is easy to find examples of algorithms that are very difficult to implement even though they happen to have a very simple worst-case running time. But what about the converse?

  Do we have examples of very simple and practical deterministic algorithms that are easy to implement but happen to have a very complicated expression as its worst-case asymptotic running time?

Please note the keywords "deterministic" and "worst-case"; the analysis of simple randomised algorithms fairly easily leads to complicated expressions.

Of course what is "complicated" is a matter of taste. Anyway, I would prefer to see an expression that is far too ugly to put in the title of your paper. And I would prefer a complicated function of one natural parameter (input size, number of nodes, etc.).

PS. I thought I would not make this a "big-list question", and not CW. I'd like to find a single excellent example (if it exists at all). Hence please post another answer only if you think that it is "better" than any of the answers so far.

The union-find data structure operations seem to meet your criteria:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure


How do you go from insights to formal solutions? My question pertains to the problem of translating ideas and insights to the solution (of some problem) into formal notations, thus expressing the answer formally.
In other words, having a bunch of ideas (pertaining to the solution) and transforming them into a well composed, formal solution is a process which I often find difficult.

It might be because (at times) I am not aware of enough literature in the problem domain and so have the problem of not knowing how to express my ideas. However, I would like to know if this is something that can be improved upon and if so, how?

Transforming intuition into formal argument is difficult, and the degree to which it is viewed as necessary is sociological, and varies by community. In general, arguments tend to be less formal in AI conferences, reasonably formal in the "Theory A" community, and extremely formal (i.e. machine verifiable) in parts of the programming languages "Theory B" community.

Probably the best way to develop this skill is to take rigorous courses that require formal argument on problem sets. You can also just read papers in the community that you would like to publish in, but you have to make sure to actually read the arguments carefully for this to be helpful. i.e. it is easy to read a paper and feel that you understand it, but be unable to reproduce key parts of the argument. A good way to do this is to plan to actually present the paper to a group of friends. If you actually have to present the arguments on a board and answer questions, you will be able to force yourself to really understand.

Do this a few times and you should be able to construct formal arguments of your own.


Linear Genetic Programming I have a few questions about linear genetic programming. I'm struggling to find much information on them, hopefully someone here can help me, it would be much appreciated.

1) Initialisation: When initialising the population, does each individual point to the same set of registers or register values, or is a separate space allocated to each individual ?

2) Crossover / mutation: Are the registers crossed over and mutated as well as the program bodies, or just the program bodies ? I am guessing they're not, but then how would one go about optimising the values in the registers ?

3) Crossover cont: What, based on your experience, is the most efficient method of crossover ?  I have written a linear GP, and have applied to various datasets for time series forecasting. One being linear, a few trigonometric, and some economic data. It works fine when given anything except the economic data. Why could this be ? My guess is that is has something to do with crossover, which at present is two point. Although i have tested other methods such as one point and uniform but they have not in any way improved the performance? The first few generations are ok, and then the fitness of the population seems to fluctuate randomly with no improvement whatsoever :(

These may seem like very simple, or strange questions. I have only just begun learning about this so please be nice ! :)

Many Thanks

1) I think this depends on the implementation of linear GP you use. Since you're writing your own implementation, I would recommend looking at some other people's implementations. IMO, this really depends on what kind of linear GP system you wrote/are using. I haven't looked myself, but ECJ might have an implementation that you can reference.

2) There are TONS of methods to crossover/mutate your individuals. I would argue that you could perform crossover using either of the approaches you mention. The one you should use will depend on the problem you're tackling and how you represent your individuals. Sometimes it's best to design crossover and mutation methods specifically for your system. A Google Scholar search for various mutation and crossover operations in GP, GAs, and linear GP will give you A LOT to work with.

3) Time series forecasting is a particularly difficult problem. In my very limited experience, economic data can be pretty volatile. Using a standard linear GP algorithm probably won't give you especially good results. With a problem that difficult, you're going to need more advanced approaches than just different crossover/mutation operators. It might be worth your time to look into some probabilistic, generalization, or strongly-typed GP approaches. Check out the Field Guide to GP for some more on those. Again, Google Scholar is a great resource for learning more about those.

I hope this helps!


For a random oracle R, does BPP equal the set of computable languages in P^R? Well, the title pretty much says it all.  The interesting question above was asked by commenter Jay on my blog (see here and here).  I'm guessing both that the answer is yes and that there's a relatively simple proof, but I couldn't see it offhand.  (Very roughly, though, one could try to show that, if a language in $P^R$ were not in $BPP$, then it must have infinite algorithmic mutual information with $R$, in which case it wouldn't be computable.  Also, note that one direction is trivial: the computable languages in $P^R$ certainly contain $BPP$.)

Note that I'm not asking about the class AlmostP, which consists of those languages that are in $P^R$ for almost every $R$ (and is well-known to equal $BPP$).  In this question, we first fix $R$, then look at the set of computable languages in $P^R$.  On the other hand, one could try to show that, if a language in $P^R$ is computable, even for a fixed random oracle $R$, then in fact that language must be in $AlmostP$.

A closely-related question is whether, with probability 1 over a random oracle $R$, we have

$ AM = NP^R \cap Computable.$

If so, then we get the following interesting consequence: if $P=NP$, then with probability 1 over a random oracle $R$, the only languages that witness the oracle separation $P^R \ne NP^R$ are uncomputable languages.

Yes.

First, since it took me a minute to figure this out myself, let me formalize the difference between your question and $\mathsf{AlmostP}$; it's the order of quantifiers. $\mathsf{AlmostP} := \{L : Pr_R(L \in \mathsf{P}^R) = 1\}$, and the result you allude to is $\forall L\, L \in \mathsf{BPP} \iff Pr_R(L \in \mathsf{P}^R) = 1$. If I've understood correctly, you are asking if $Pr_R(\forall L\, L \in \mathsf{P}^R \cap \mathsf{COMP} \iff L \in \mathsf{BPP}) = Pr_R(\mathsf{P}^R \cap \mathsf{COMP} = \mathsf{BPP}) = 1$.

Consider

$p := 1-Pr_R(\mathsf{P}^R\cap \mathsf{COMP} = \mathsf{BPP}) = Pr_R(\exists L \in \mathsf{P}^R \cap \mathsf{COMP} \backslash \mathsf{BPP})$.

By the union bound, the $p$ is upper-bounded by $\sum_{L \in \mathsf{COMP}} Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP})$. (Note that the latter sum is countable.) Now, by the 0-1 law - which applies since all the relevant statements do not change if we change $R$ finitely much - each individual probability in this sum is either 0 or 1. If the answer to your question is no, then $p=1$, so there must be some $L \in \mathsf{COMP}$ such that $Pr_R(L \in \mathsf{P}^R \backslash \mathsf{BPP}) = 1$. But this contradicts the fact that $\mathsf{AlmostP} = \mathsf{BPP}$.

Update Oct 10, 2014: As pointed out in the comment by Emil Jeřábek, the same argument applies to $\mathsf{AM}$ vs. $\mathsf{NP}^R$, since we also know that $\mathsf{AlmostNP} = \mathsf{AM}$.

He also points out that we didn't use anything about $\mathsf{COMP}$ other than that it is a countable class that contains $\mathsf{BPP}$ (resp., $\mathsf{AM}$). So the "interesting conclusion" in the OQ actually applies to any countable class of languages $\mathcal{C}$ that contains $\mathsf{AM}$: if $\mathsf{P} = \mathsf{NP}$, the "only" languages that witness the oracle separation $\mathsf{P}^R \neq \mathsf{NP}^R$ are outside of $\mathcal{C}$. But the latter statement feels somewhat misleading to me (it makes it sound like, for any $L_0$ we could consider $\mathcal{C} = \mathsf{AM} \cup \{L_0\}$, and thereby "show" that no $L_0$ realizes $\mathsf{NP}^R \neq \mathsf{P}^R$, contradicting the well-known theorem). Rather, writing it out symbolically, we've shown:

If $\mathsf{P} = \mathsf{NP}$, then $\forall \text{countable } \mathcal{C} \supseteq \mathsf{AM}\, Pr_R(\mathsf{NP}^R \neq \mathsf{P}^R \text{ and } \mathsf{NP}^R \cap \mathcal{C} = \mathsf{P}^R \cap \mathcal{C}) = 1$.

Note that, crucially, probability 1 is not the same thing as all $R$, and which full-measure set of $R$ satisfy the argument to $Pr_R$ can depend on $\mathcal{C}$. So if we try to alter $\mathcal{C}$ to $\mathcal{C} \cup \{L_0\}$, it at most removes a measure 0 set of $R$ that satisfy this statement.


Question about Mapping Reductions (Clarify Example) I cannot for the life of me wrap my head around these reductions.

Specifically, the example I'm wrestling with:

REGULAR = {<M> | M is a Turing Machine and L(M) is regular}

Reduction to ACCEPT_TM where ACCEPT_TM = {<M,w> | M is a TM and w is a string, M accepts w}

Construct TM M':
M' = "On input x
    1. If x has the form 0^n1^n, accept
    2. Otherwise, run M on input w and accept if M accepts w."

If M accepts w, M' accepts SIGMA*
If M does not accept w, M' accepts 0^n1^n

I understand the first implication (if M accepts w, M' accepts SIGMA*).

What I don't understand is the implication that if M does not accept w, then M' accepts strings of the form 0^n1^n.  How are they reaching this conclusion?  To me, it seems like "If x is in the form 0^n1^n, then don't run M", which doesn't seem logically equivalent.

If M does not accept w, then the only case in which M' accepts is if its input is of the form 0^n 1^n.


Minimum path covering problem We are working in distributed computers, and we came up with a complexity problem which reduces to a minimum path covering problem. We currently do not know how to solve it. The problem is the following:

Let $k$ be some integer, and let $Z_k$ be a graph containing $\frac{k(k+1)}{2}$ vertices.
We label each vertex with a couple $(i,j)$ such that $1 \leq i \leq j \leq k$.
Hereafter, we name vertices using their label.
The set of edges in $Z_k$ is defined as follows  :
$\{ ((i,j),(i',j')) | i' >i \land j' \geq i \}$.

What is the minimal path covering of $Z_k$ ?

Reading
"On Path Cover Problems in Digraphs and Applications to Program Testing"
by Ntafos et al. , we have seen that the minimal path covering equals
the cardinal of the greatest incomparable vertex set.
We were thinking about the following set:
$S= \{ (i,j) : i \geq k/2 \land j < k/2 \}$
which has a cardinal of $\frac{k^2}{4}-\frac{k}{2}$.

Sincerely,

Pierre

It sounds like your graph is a transitively closed DAG, right? If so (and this is probably a restatement of what you say in your citation of Ntafos et al) the minimum number of paths needed to cover the DAG is just the maximum number of pairwise incomparable elements; this is Dilworth's theorem.

Your example may be simple enough that one can identify this maximum incomparable set directly, but in general it is possible to find this set in polynomial time, by an algorithm based in graph matching. The "Proof via König's theorem" section of the Wikipedia article on Dilworth's theorem explains how.


complexity of games with just doors and keys (This essentially copies my unaswnered question

from math.stackexchange.com/questions/275685)

I was reading http://arxiv.org/abs/1201.4995, and I thought

back to a game I used to play, which is close to being covered

by Metatheorem 3 (on page 5), but does not have one-way paths.

  What is the computational complexity of the following problem?

For an undirected graph G whose vertices have non-negative integer weights,

for vertices s and t, is there a path from s to t such that the sum of the weights

of the vertices (including s) reached at any given point along it is always

greater than the number of distinct edges traversed to get to that point?

(The vertices are not counted with multiplicity either.)

If I understand your question correctly, by path you mean that we build up a tree starting from s by always taking an edge adjacent to our current tree. This problem is NP-complete, the reduction is from SAT.

The main part of the graph will consist of n cycles of length four attached to each other at vertices s=v0, v1, v2, .., vn. So from s we have two paths of length two to v1, from v1 two paths to v2 and so on. From vn there will be a path of length N+1 to t.
We will have only enough weights to use one of each pair of paths and depending on which path we use, the value of the variable xi will be true or false. The weight in s is N+2n, where N is some big number.

Each clause is represented by an additional vertex that is connected by a path of length N to the center vertex of the path that corresponds to its literals and it has value N+epsilon (I know we need integers, but we can multiply up and replace each edge by 1/epsilon edges), where 1/epsilon is the number of clauses. So we have to visit every clause-vertex to get to t.


Defining binary natural numbers without quotient types Let's say we work in a dependent type theory with W-types and we want to have a type for binary natural numbers. We don't want to add quotient types or higher inductive types to the system.
How to represent the idea that leading zeroes don't change the natural number? Do we necessarily enter setoid territory at this point?

Use an auxiliary type of positive natural numbers.
data positive : Set where
  one : positive
  s0  : positive → positive -- multiply by 2
  s1  : positive → positive -- multiply by 2 and add 1

data N : Set where
  zero : N
  pos : positive → N

Supplemental: Another option, which I found on my whiteboard today (probably put there by Egbert Rijke months ago) is this:
-- Dyadic natural numbers without redundancy
data N : Set where
  zero : N      -- 0
  suc0 : N → N  -- suc1 n = 2 * n + 2
  suc1 : N → N  -- suc1 n = 2 * n + 1

I think you'll probably prefer this one.


Finding containing sets, within sets of sets Let $s = \{\sigma_1, \sigma_2 \ldots \sigma_n\}$, where $\sigma_i \in \Sigma$, denote a set of alphabet characters.
And $s \in S$ where $S$ denotes a set of sets.
Given a new set $s' = \{\sigma'_1, \sigma'_2, \ldots \sigma'_n \}$ is there an efficient algorithm for getting all sets, $s'' \in S$, where $s' \subset s''$
In other words, given a set of sets, is there a way of getting the subset of sets the contain specific set of attributes?
I would be willing to build data structures with search and update complexities in the $O(\log (n))$ range, $n$ being the number of sets - also I would like the alphabet $\Sigma$ to be infinite.
The alphabet size is not known in advance.
This seems like a pretty simple problem, I am however not able to get my head around it.
Example:
Given the dataset $S$:

$s_1$: {a,b,c,d}
$s_2$: {a,c,d}
$s_3$: {b,c,d,f}
$s_4$: {a,b,d,h}

and the query string $s'$ = {a,b}
I would like the result :

$s_1$: {a,b,c,d}
$s_4$: {a,b,d,h}

The only sets containing the two elements.

The problem you are trying to solve is called PARTIAL-MATCH: given a database of sets, and a query set, find all sets in the database that contain the query.

The most relevant paper is one by Charikar, Indyk and Panigrahy from ICALP 2002:
New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems

That's on the theoretical side. In practice, many simplifications can be made if one knows something about the sets and the query. For example if $|Q|$ is small, you might be able to get away with an inverted index.


Is the "Fewest Discriminating Bits" problem NP-complete? That is a name I have made up for this problem.  I have not seen it described anywhere before.  I have not been able to find a proof of NP-completeness nor a polynomial time algorithm for this problem yet.  It is not a homework problem -- it is related to a problem I have come across in my work.

FEWEST DISCRIMINATING BITS

INSTANCE: A set T containing bit vectors, where each bit vector is exactly N bits long.  Every element of T is unique, as one would expect from a set in math.  An integer K < N.

QUESTION: Is there a set B of at most K bit positions (i.e. integers in the range [0,N-1]) such that when we remove all bits except those in B from every vector in T, the remaining shorter vectors are all still unique?

Example 1: For the instance N=5, T={00010, 11010, 01101, 00011}, K=2, the answer is yes, because we can select the bit positions B={0,3}.  Using the convention that bit position 0 is the rightmost, and the bit position numbers increase right-to-left, removing all bit positions except those in B from the vectors in T leaves T'={00, 10, 11, 01}, and those are all unique.

Example 2: N=5, T={00000, 00001, 00010, 00100}, K=2.  The answer is no, because no matter which two bit positions we select, none of the 2-bit vectors will be equal to 11, so at least two of the 2-bit vectors will be equal to each other.

We can of course solve this problem by enumerating all (N choose K) subsets with size K of the N bit positions, and determining which satisfy the condition of the question.  However, that is exponential in the input size.

This problem is NP-complete.  A proof based on reduction from 3-SAT is as follows:

Consider an instance of 3-SAT with $n$ variables and $m$ clauses.  We will construct $2n + 2m$ bit vectors ("rows") of length $2n + \lceil \log_2(n + m) \rceil$, such that the smallest number of discriminating bits is $n + \lceil \log_2(n + m) \rceil$ iff the original 3-SAT instance is satisfiable.

The first $2n$ bits will correspond to the literals $\left\{ x_1, \neg x_1, x_2, \neg x_2, ..., x_n, \neg x_n \right\}$.  With respect to these bits, the first $2m$ rows will come in pairs, the first of which will have a $1$ for each literal included in the corresponding clause, and the second of which will consist entirely of $0$'s.  The remaining $2n$ rows will also come in pairs, the first of which will have $1$'s for the corresponding literal and its negation, and the second of which will consist entirely of $0$'s.  Finally, the last $\lceil \log_2(n + m) \rceil$ bits will be used to "sign" each pair of rows with its index, from $0$ to $n+m-1$, written in binary.

In order to distinguish each "literal" row from its successor, either the bit corresponding to that literal or the bit corresponding to its negation must be retained.  Also, in order to discriminate among the $n+m$ "zero + index" rows, all $\lceil \log_2(n + m) \rceil$ index bits must be retained.  The minimum possible number of discriminating bits is therefore $n + \lceil \log_2(n + m) \rceil$.  Finally, in order to distinguish each "clause" row from its successor, at least one of the three bits corresponding to literals included in that clause must be retained.  If the 3-SAT instance is satisfiable, this last condition will not require any extra bits (in particular, we do not need to retain the bits corresponding to both $x_i$ and $\neg x_i$ for any $i$); and conversely, if there are $n + \lceil \log_2(n + m) \rceil$ bits that discriminate among all $2n+2m$ bit vectors, they must contain exactly one of $x_i$ and $\neg x_i$ for each $i$, and hence correspond to a satisfying assignment of truth values to the $n$ variables.


Does every regular language contains a strictly locally testable language? Let $L$ be an infinite regular language, then does there exists a strictly locally testable  infinite language $P$ such that $P \subseteq L$?

The answer is no. The argument was suggested by phs, but you have to start with a different language. Take $L = (aa)^*$. Then any regular language $K$ contained in $L$ is of the form
$$
 K = \{(aa)^n \mid n \in U \}
$$
 for some ultimately periodic subset $U$ of $\mathbb{N}$. If $K$ is infinite, then the period $p$ of $U$ is not $0$ and thus $K$ is not star-free (hence not locally testable and not strictly locally testable).


Reaching the double exponential upper bound in Fourier-Motzkin elimination One round of Fourier-Motzkin elimination may yield $n^2/4$ inequalities where $n$ is the original number of linear inequalities, whence an upper bound of $n^{2^d}/2^{2^{d+1}-2}$ for $d$ rounds of elimination without removal of redundant constraints.

I'm wondering whether it is possible to meet this upper bound.

(Note: this is a distinct question from that of counting the number of true faces in a projection, that is, after removal of redundant constraints, for which McMullen's upper bound provides a tighter bound.)

I think this upper bound is tight. As an example, consider the following system

\begin{align*}
+x_0 & +\frac{1}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
+x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2  \le 0 \\
+x_0 & +\frac{1}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
+x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2  \le 0 \\
-x_0 & +\frac{1}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
-x_0 & +\frac{1}{2} x_1 +\frac{1}{4} x_2  \le 0 \\
-x_0 & -\frac{3}{2} x_1  +\frac{1}{4} x_2 \le 0 \\
-x_0 & -\frac{3}{2} x_1 -\frac{7}{4} x_2  \le 0 \\
\end{align*}

It has 8 inequalities. Though some of them are identical, it is not a problem since we do not remove redundant constraints. One can also add dummy variables to make them different. Reducing $x_0$, we obtain system with 16 inequalities. Then, reducing $x_1$, we obtain system with $64$ inequalities.

More generally, let $S_{n}^k$ denote the following system of inequalities over $x_0, x_1, \ldots, x_{k - 1}$. Here we assume that $k \le n, n\ge 2$. There will be $2^n$ inequalities in $S_{n}^ k$. Take any $m \in\{1, 2, \ldots, 2^n\}$.  Let $m^{th}$ inequality of $S_{n}^ k$ be
$$\alpha^m_0 x_0 + \ldots + \alpha^m_{k - 1} x_{k - 1} \le 0,$$
where
$$\alpha^m_i = \begin{cases} 2^{-i} & \mbox{if $m \le 2^n - 2^{n - i - 1}$}, \\ -2 + 2^{-i} & \mbox{otherwise.} \end{cases}$$

Here we use a restriction mentioned above : provided $k\le n$, we have that $2^{n - i - 1}$ is an integer.

For example, system above is $S_{3}^3$. It is easy to verify that if we eliminate $x_0$ from $S_{n} ^k$, we obtain $S_{2n - 2} ^{k - 1}$. Indeed, when we eliminate $x_0$, we add up all the inequalities from the first half with all the inequalities from the second half.  Thus we get $2^{n - 1} \cdot 2^{n - 1} = 2^{2n - 2}$ inequalities. What happens with $x_i$ for $i > 0$? In the first $$2^{n - 1} \cdot (2^{n - 1} - 2^{n - i - 1}) = 2^{2n - 2} - 2^{2n - 2 - i} = 2^{2n - 2} - 2^{(2n - 2) - (i - 1) - 1}$$ inequalities a coefficient before $x_i$ will be $2^{-i} + 2^{-i} = 2^{-(i - 1)}$. In the last $2^{-i} + (-2 + 2^{-i}) =  2^{(2n - 2) - (i - 1) - 1}$ inequalities a coefficient before $x_i$ will be $2^{-i} + (-2 + 2^{-i}) = -2 + 2^{-(i - 1)}$. This is $S_{2n - 2}^{k - 1}$, but over variables $x_1, \ldots, x_{k - 1}$. Since, $2n - 2 \ge n - 1 \ge k - 1$, a restriction on the number of variables is also preserved.

Further, if we eliminate $x_1$, we obtain $S_{4n - 6}^{k - 2}$, and so on. After $d$ steps we will have $S^{k - d}_{2^d n - (2^{d + 1} - 2)}$. The latter has exactly
$$2^{2^d n - (2^{d + 1} - 2)} = N^{2^d}/ 2^{2^{d + 1} - 2}$$
inequalities, where $N = 2^n$ is the number of inequalities of the initial system.


Consequences of a distillation algorithm for PSPACE The following notion of a distillation algorithm comes from "On Problems Without Polynomial Kernels".

  Let a language $L$ be given.  A distillation algorithm for $L$ takes a given
  list of input strings $\{ x_i \}_{i \in [t]}$ and computes an output string
  $y$ such that:

  (1) $y \in L$ if and only if there exists $i \in [t]$ such that $x_i \in L$

  (2) $\vert y \vert \leq p(Max_{i\in[t]} \vert x_i \vert)$ for some polynomial $p$

  (3) The algorithm computes $y$ in at most $q(\sum_{i\in[t]}\vert x_i \vert)$ time for some polynomial $q$

It has been shown that if there exists a distillation algorithm for an $NP$-complete problem, then $coNP \subseteq NP/poly$.  Moreover, $PH = \Sigma_3$.

  See details and discussion in:

  "Infeasibility of Instance Compression and Succinct PCPs for NP"
  "On Problems Without Polynomial Kernels"
  "Lower bounds on kernelization"

Questions:

Could there exist a distillation algorithm for a $PSPACE$-complete
problem?
If such an algorithm existed, what complexity consequences would we
get?

Theorem 15.3 of the recent "Parameterized Algorithms" textbook by Cygan et al. states the following:

"Let $L, R ⊆ \Sigma^*$ be two languages. If there exists an OR-distillation of L into R, then $L\in coNP / poly$"

So, I think that if there exists an OR-distillation from a PSPACE-complete language $L$ to itself, then $PSPACE \subseteq coNP/poly$, i.e. not only does the polynomial-hierarchy collapse, but also PSPACE collapses with it.


What is known about $CFL \cap coCFL$? CFL is the class of context-free languages; co-CFL the languages whose complements are context-free.  So CFL $\neq$ co-CFL.

Are there any nice characterizations or other basic facts about CFL $\cap$ co-CFL?

Two easy examples of the kind of fact I have in mind (but one would like more precise information):

DCFL $\subseteq$ CFL $\cap$ co-CFL.
pCFL $\subseteq$ CFL $\cap$ co-CFL, where pCFL is the class of CFLs that are permutation-closed.  It's closed under complement by Parikh's theorem and the fact that semilinear sets are definable in Presburger arithmetic.

Another related question: given a CFL $L$, it's undecidable whether $L \in$ DCFL.  Is the same true for pCFL?

About the last question, the usual undecidability proof for universality could be adapted.

Recall that in this proof, one considers an instance $\langle \Sigma,\Delta,u,v\rangle$ of Post's correspondence problem, where $\Sigma$ and $\Delta$ are two disjoint alphabets, and $u$ and $v$ are two homomorphisms from $\Sigma^\ast$ to $\Delta^\ast$.  Then $$L_u=\{a_1\cdots a_n(u(a_1\cdots a_n))^R\mid n>0\wedge\forall 0<i\leq n.a_i\in\Sigma\}$$ and $$L_v=\{a_1\cdots a_n(v(a_1\cdots a_n))^R\mid n>0\wedge\forall 0<i\leq n.a_i\in\Sigma\}$$—where $w^R$ denotes the reversal of word $w$—are two DCFLs s.t. $L_u\cap L_v=\emptyset$ iff the original PCP instance was negative.  Letting $$L=\overline{L_u}\cup\overline{L_v}\;,$$one thus defines a CFL (since DCFLs are effectively closed under complement and CFLs under union), which is universal, i.e. equal to $(\Sigma\cup\Delta)^\ast$, iff the original PCP instance was negative.

Now, if $L$ is universal, i.e. if $L=(\Sigma\cup\Delta)^\ast$, then $L$ is closed under permutations.  Conversely, if $L$ is not universal, i.e. if $L_u\cap L_v\neq\emptyset$, there is at least one word $x$ of form $x=w(u(w))^R=w(v(w))^R$ for some $w$ in $\Sigma^+$.  Then $x$ does not belong to $L$, but it's easy to find a permutation of $x$ that belongs to $L$: for instance, permute the last letter of $w$ (which is in $\Sigma$) with the first of $(u(w))^R$ (which is in $\Delta$) to obtain a word in $\Sigma^\ast\Delta\Sigma\Delta^\ast\subseteq L$.

Hence $L$ is closed under permutation iff it is universal iff the original PCP instance was negative.


Automata Theory / Formal Language Thesis Topic Hey All,
  I'm currently trying to find a solid masters thesis topic pertaining to some branch of automata theory or related to formal languages. I'm trying to generate some good ideas for what an acceptable topic would be, something ambitious but something doable at the same time.

Any suggestions would be very much appreciated!

I think David Eppstein is too dismissive of the area of automata theory and formal languages.  The claim that "getting it published in top-level conferences and convincing someone to hire you once you graduate may be problematic" seems to be what Haldane called Aunt Jobiska’s Theorem: "It’s a fact the whole world knows."

In fact, there are good conferences (such as STACS and ICALP) that routinely publish results in automata theory and formal languages; there are well-attended conferences (such as DLT) that focus on the area; it is a very active area in Germany, France, and Italy; there are great open problems in the area; and I know many students that have had no problem getting jobs.


Connection between PCP and L=SL The book by Arora and Barak contains in chapter notes on PCP

  We note that Dinur's general strategy is somewhat reminiscent of the zig-zag construction of expander graphs and Reingold's deterministic logspace algorithm for undirected connectivity described in Chapter 20, which suggests that more connections are waiting to be made between these different areas of research. (pg 494)

What precisely is meant by this reminiscence? Is there a common property/lemma than can be "factored out" of these two proofs?

The precise answer to your question is given by Oded Goldreich in his article "Bravely, Moderately: A Common Theme in Four Recent Works".

Here is the link: http://www.wisdom.weizmann.ac.il/~oded/COL/brave.pdf


Can we confirm that 2-SAT can indeed be transformed into Horn-SAT in this manner? In the question, Translating SAT to HornSAT, Martin Seymour gives a method due to Joshua Grochow.  It transforms 2-SAT into Horn-SAT, by creating a variable for every possible 2-SAT clause.  Then, if a clause (or new variable) follows from two other clauses (variables) from "a single resolution step", it adds this implication to the formula.  Finally, the unit clauses are added, along with a clause signifying not empty.

Can someone please explain, in detail, why we add clauses from "single resolution steps"?  Am I correct in assuming that this means a single resolution step from unit propagation?  Also, and perhaps most importantly, can someone prove that this method works?

Essentially, I'd like to know everything I can to ensure that I can implement this method, and also prove that it works.  I'm also wondering if perhaps this method can be found in the literature somewhere.

Resolution in this context is broader than unit propagation, since a 2-CNF might not have any unit clauses. Instead resolution refers to the inference rule that given a pair of clauses $C = (x \vee y), \hat{C} = (\neg x \vee z)$ that contain a variable and its negation respectively, we can infer the new clause $(y \vee z)$. In addition, let $(x \vee x), (\neg x \vee \neg x)$ infer the empty clause $()$ which we will declare not satisfiable.

See here for an excellent explanation of why repeated application of this resolution rule will always lead to the empty clause iff the 2-CNF was unsatisfiable.

If the 2-CNF is satisfiable, then set $z_C = 1$ for every clause $C$ occurs in or that is inferred by resolution on the 2-CNF, and $0$ for every other clause. Every implication is satisfied, and every unit clause is satisfied. So the Horn formula is satisfied.

If the 2-CNF formula is unsatisfiable, then resolution will generate the empty clause. By the implications in the generated Horn formula, setting $z_C=1$ for each clause $C$ in the 2-CNF implies $z_{empty}=1$. But the unit clause $\neg z_{empty}$ prohibits this. Therefore, the Horn formula is unsatisfiable.


Approximating distributions from samples One claim I find in many papers about identity testing, and closeness testing is that any distribution over $[n]$ can be approximated to within $\ell_1$ distance $\epsilon$ in $O\left(\frac{n}{\epsilon^2}\right)$ samples.

I do not seem to be able to find a proof of this anywhere. On trying to prove it, I seem to be able to prove it if I assume that there exists $\delta>0$, such that, $\min_{i \in [n]} P_i > \delta$, where $P$ is the true distribution. However, I do not seem to be able to prove it in the general case.

My attempt at a proof is the following:

Let $P$ be any distribution over $[n]$. Let $X_1,X_2,\cdots,X_{\frac{n}{\epsilon^2}}$ be iid samples of $P$. Let $m=c\frac{n}{\epsilon^2}$. Define $C_i$, $1 \leq i \leq n$, as

$$C_i= \sum_{j=1}^{m} 1(X_j=i).$$

We note that $\mathbb{E}[C_i]= mP_i$.

Further from Chernoff bounding, we get that,

$$P[C_i > (1+\epsilon)mP_i] \leq \exp(-\epsilon^2 \frac{mP_i}{3})= \exp(-\frac{cnP_i}{3}).$$

Similarly,
$$P[C_i < (1-\epsilon)mP_i] \leq \exp(-\frac{cnP_i}{2}).$$

Thus defining $\hat{P}_i= \frac{C_i}{m}$, and $\hat{P}=(\hat{P}_1,\cdots,\hat{P}_n)$, by union bounding, we get that with probability at least $1-\sum_{i=1}^n 2\exp(- \frac{cnP_i}{3})$, we have that $||\hat{P}-P||_1 \leq \epsilon$. This gives a proof of the claim as long as there exists $\delta>0$, such that, $\min_{i \in [n]} P_i > \delta$ (as the probability can be made arbitrarily close to 1 by increasing the constant).

However, I do not know how I can generalise this result to the general case. I'd appreciate any help with respect to this.

I think it's a simple application of Hoeffding's inequality. Using your notation, let $Q_i = \frac1m C_i$, i.e. $Q$ is the empirical distribution that approximates $P$. The total variation distance between $P$ and $Q$, i.e. half the $\ell_1$ distance, is
$$
\max_{S \subseteq [n]} \left| \sum_{i \in S}{P_i} - \sum_{i \in S}{Q_i}\right|.
$$

Let $P(S):= \sum_{i \in S}{P_i}$ and define $Q(S)$ analogously. The expectation of $Q(S)$ is $P(S)$ and by Hoeffding,
$$
\mathbb{P}(|Q(S) - P(S)| > \epsilon) \leq 2e^{-\epsilon^2 m}
$$

If we take $m$ a large enough multiple of $n/\epsilon^2$, we have that $\mathbb{P}(|Q(S) - P(S)| > \epsilon) < 2^{-n}/3$ and by a union bound

$$
\mathbb{P}(\max_S |Q(S) - P(S)| > \epsilon) < 1/3.
$$
So with probability at least 2/3, the total variation distance is at most $\epsilon$.


Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only? $\DeclareMathOperator*{\argmin}{arg\,min}$Can something be said about the difficulty of minimizing the quantity

$$g(x) = \sum_{i=1}^n\sum_{j=i+1}^n f(x_i, x_j)$$

of some string of symbols $x \in \Sigma^n$ solely through permuting $x$? That is, finding

$$\underset{\sigma\in S_n}{\argmin}\ g(\sigma(x))$$

$f: \Sigma \times \Sigma \to \mathbb{R}$ is here a black-box function with no other properties.

Your problem is at least as hard as the NP-hard problem called Minimum Feedback Arc Set.

Consider a directed graph and set $f(u,v)=1$ if it contains an arc from $u$ to $v$, and $0$ otherwise. Then your problem corresponds to finding a minimum feedback arc set: a minimum set of arcs whose removal yields a directed acyclic graph (DAG). From such a DAG, one can obtain the desired permutation using a topological sort, and the corresponding value of $g$ will be the size of the feedback arc set.

Moreover, the problem of deciding whether there is a permutation $\sigma$ with $g(\sigma(x))\leq k$ is in NP: just guess the permutation and compute $g$.


Where does randomness help when deciding algebraic geometry over $\mathbb{C}$? If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether the equation is always true.  We can similarly decide if a single polynomial inequation is always true over $\mathbb{C}$, since $p(z_1,\ldots,z_n) \ne 0$ for all $z_i$ iff the polynomial is a nonzero constant.

Does the simplicity of randomized checking extend to any systems of multivariate polynomial equations?  In particular, is there a simple algorithm for deciding whether
$$p(z_1,\ldots,z_n) = 0 \implies q(z_1,\dots,z_n) = 0$$
where $p,q$ are straight line programs over $\mathbb{C}$ with integer coefficients?  I'm fairly sure randomness does not provide simple algorithms if we go to arbitrary systems of equations and inequations, but I'm curious where the boundary is between easy and hard.

For the question of when does $p=0 \Rightarrow q=0$, randomness can indeed help, as follows. First, factor $p$ (uses randomness when $p$ is given as a straight-line program; doesn't need randomness if $p$ is given as a coefficient vector). Let $\tilde{p}$ denote the square-free version of $p$ - that is, if $p=p_1^{k_1} p_2^{k_2} \dotsb p_\ell^{k_\ell}$ then $\tilde{p} = p_1 p_2 \dotsb p_\ell$. Then $q=0$ follows from $p=0$ iff $\tilde{p}$ divides $q$, which happens iff $q$ is of the form $q=p_1^{k'_1} \dotsb p_\ell^{k'_\ell} f$ with all of the $k'_j$ strictly positive. The latter can be checked by factoring $q$ (uses randomness, as before).
For the general question of $p_1=\dotsb=p_k=0 \Rightarrow q=0$, randomness seems not to help from the complexity perspective, as this problem is $\mathsf{EXPSPACE}$-complete (randomness may help in practice though...).
For the problem of telling whether the variety $\{\vec{x} : p_1(x)=\dotsb=p_k(x)=0\}$ is empty or not (for polynomials given by a list of monomials and coefficients - which is "sparse but not succinct", that is, not SLPs), randomness also seems to help: assuming GRH, this problem is in $\mathsf{RP}^{\mathsf{NP}}$ by a result of Koiran. It is $\mathsf{NP}$-hard, and not known to be in $\mathsf{P}^{\mathsf{NP}}$.


Parallel algorithms for directed st-connectivity Chong, Han and Lam showed that undirected st-connectivity can be solved on the EREW PRAM in $O({\log}n)$ time with $O(m+n)$ processors. What is the best known parallel algorithm for directed st-connectivity ? Please state the running time, deterministic/randomized algorithm and the PRAM model used (assuming the number of processors is polynomial). Are there any $o({\log}^2{n})$ time parallel algorithms known for any special cases of directed st-connectivity ?

Directed s-t reachability can easily be done using O($n^3$) processors and O$(\log n$) time on a CRCW-PRAM, or in O($n^\omega$) processors and  O($\log^2 n$) time on a EREW-PRAM
 where $\omega<2.376$ is the matrix multiplication exponent and $n$ is the number of vertices. The following paper claims O($n^\omega$) and  O($\log n$) time on a CREW-PRAM: "Optimal Parallel Algorithms
for Transitive Closure and Point Location
in Planar Structures" by Tamassia and Vitter. Other papers claim the same thing and cite the Karp and Ramachandran survey (Parallel algorithms for shared-memory machines, in: J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science). The survey itself does mention that transitive closure is in AC1 and hence can be solved in O(log n) time on a CRCW-PRAM, but the part about CREW-PRAM is missing.

All Strassen-like algorithms for matrix multiplication (including the one by Coppersmith-Winograd) are essentially parallel algorithms that run in O$(\log n)$ time; transitive closure incurs an extra log (but if you allow unbounded fan-in the trivial O($n^3$) matrix mult can be done in constant depth and so reachability is in O$(\log n)$ time on a CRCW-PRAM). It's an open problem to improve the number of processors from the current best ~$n^{2.376}$; it is also a major open problem if reachability is in NC1, as it would imply L=NL among other things.


Predict user's future location - location awareness mobile computing This question is a part of an online course (Mobility Data Management) that I am currently auditing. A part of the project is to implement a system that can predict user's future location. This kind of application has recently got some interests from database and mobile application developers.

This is the problem statement: Assume that we are given a road network G (V,E), the recent motion history (trajectory) T, and current instant velocity v of a user, a temporal duration dt, and (optional) a historical trajectory database D of other users’ movements. Our goal is to estimate user’s location after dt.

I found that the following paper has a good description about what a road network and the trajectory data is: http://www.sis.pitt.edu/~xliu/papers/ceus.pdf

Does anyone has an idea on how to formulate a simple solution of this mobility awareness problem (predicting user's future location), and how to start the implementation (how you formulate the problem in an OOP way, such as: what classes are needed to represent the problem correctly). I cannot find the correct tags for this question, probably the moderator can add new tags such as: graph-networks, mobility-data, trajectory, etc.

My professor uses a hidden markov model based upon the previous routes that the bus has been. See http://www.cs.uic.edu/~jakob/papers/transitgenie-sensys09-demo.pdf for a paper on it. Although the paper doesn't go into the architecture I remember it from a lecture he gave on the application.


Can Lenstra's algorithm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k? It is well-known that Lenstra's famous algorithm (presented in the paper
Integer programming with a fixed number of variables) can solve an ILP problem in $O^*(f(k))$ time where k is the number of variables occur in the ILP.

My question is that whether the algorithm or any of its improved versions can output all feasible solutions in $O^*(f(k))$ time?

No. The number of feasible solutions cannot be upper bounded by $f(k)n^{O(1)}$.

Consider the integer program
$I_n: 1 \le x\le 2^n$
with the integer variable $x$. So, $k=1$ and the program can be described with $O(n)$ bits. But it has $2^n$ solutions, which is exponential in the instance size.


Complexity of smooth non-linear functions EDIT: A more straightforward way of asking this question is: does evaluating a non-linear function require performing at least one multiplication?

ORIGINAL QUESTION:

I have an infinitely differentiable function f(x) which takes as input an $n$-bit integer $x$ and outputs a $kn$-bit integer, where $k$ is a contant. I know that $f(x)$ is not a linear function of $x$, and I want to argue that the complexity of evaluating $f$ on $x$ is at least $n \log n$.

I think this should be true, since I can write $f(x) = f(x_0) + f'(x_0)(x-x_0) +  f''(x_0)(x-x_0)^2 + ...$ and computing $(x-x_0)^2$ requires at least $n \log n$ operations.

However, I don't think this ``proof by Taylor series" would yield a proof, and this would rule out smooth non-linear functions that have complexity $n \log \log n$, for instance.

Any suggestions on how to prove this / give a counterexample?

Thanks!

Note that proving that evaluation of $f$ takes at least as much time as integer multiplication only shows that it needs time $\Omega(M(n))$; while this is generally assumed to be at least $n\log n$, no superlinear bound has been proven. (However, I disagree that this wouldn’t yield anything nontrivial, as was formerly stated in Joshua Grochow’s answer. For one thing, there are plenty of analytic functions such as exp, log, sin where this $\Omega(M(n))$ bound is close to optimal up to one more logarithmic factor. For another thing, we normally regard a proof of NP-completeness of some problem as a strong evidence that it is hard, despite that with the current state of knowledge it doesn’t imply any superlinear lower bound either.)

As pointed out by Joshua Grochow, you cannot say anything useful about the complexity of evaluation of analytic functions at integers. The correct statement you are looking for is that approximation of smooth functions on short real intervals is at least as hard as integer multiplication. This indeed follows from Taylor expansion, though in full generality there are some messy details where the devil is (in particular, we a priori know nothing about the coefficients of the Taylor series).

As usual in this context, it is convenient to restrict attention to time bounds obeying some basic regularity conditions. Let me say that $T(n)$ is a reasonable bound if $T$ is nondecreasing, and
$$c_1T(n)\le T(2n)\le c_2T(n)$$
for some constants $1<c_1\le c_2$. Commonly encountered bounds of polynomial growth involving powers of $n$, $\log n$, and similar, are all reasonable.

In order to avoid issues with representation of real numbers, we will only considered real functions on bounded intervals. An $n$bit approximation of $x$ is then a dyadic rational $x'$ written in the usual binary notation with $n$ bits after the radix point, such that $|x-x'|\le2^{-n}$. A function $f\colon[a,b]\to\mathbb R$ can be computed in time $T(n)$, if given a dyadic rational $x\in[a,b]$ with $n$ bits after the radix point, we can compute in time $T(n)$ an $n$bit approximation of $f(x)$.

  Proposition: If $T$ is a reasonable bound, and $f\colon[u,v]\to\mathbb R$ (where $u<v$ are real) a nonlinear $C^3$ function that can be computed in time $T(n)$, then multiplication of $n$bit integers can be computed in time $O(T(n))$.

Proof:

Note that any Turing machine computing $f$ must read the whole input (at least for some inputs of every length $n$), thus we must have $T(n)\ge n$.

Since $f''(x)$ is continuous and not constantly $0$, we can find $x_0\in(u,v)$ of the form $x_0=k2^{-l}$ such that $f''(x_0)\ne0$. Since $f(x_0+x)$ is also computable in time $O(T(n))$, we can assume that $u<0<v$ and $f''(0)\ne0$. Likewise, $f(2^{-l}x)$ is computable in time $O(T(n))$ for fixed $l$, hence we may in fact assume $[u,v]=[-1,1]$.

By Taylor’s theorem, we have
$$|a_0+a_1x+a_2x^2-f(x)|\le M|x|^3,\qquad x\in[-1,1],$$
for some constants $a_0,a_1,a_2,M\in\mathbb R$, where $a_2\ne0$. We can compute $f(x)-a_0$ in time $O(T(n))$ by subtracting an $(n+1)$bit approximation of $a_0=f(0)$ from an $(n+1)$bit approximation of $f(x)$, hence we can assume $a_0=0$.

Then we can also compute $a_1x$ in time $O(T(n))$ using a $(2n+m)$-bit approximation of $f(2^{-(n+m)}x)$, where $m$ is a suitable constant: we have
$$|2^{n+m}f(2^{-(n+m)}x)-a_1x|\le|a_2|2^{-(n+m)}|x|^2+M2^{-2(n+m)}|x|^3
\le(|a_2|+M)2^{-(n+m)},$$
hence it is enough to take $m>\log_2(|a_2|+M)+1$. This means we can compute $f(x)-a_1x$, hence we can as well assume $a_1=0$.

Using the same trick once more, we have
$$|2^{2(n+m)}f(2^{-(n+m)}x)-a_2x^2|\le M2^{-(n+m)},$$
hence we can compute $a_2x^2$ on $x\in[-1,1]$. By scaling, we can compute it on any fixed bounded interval, and we can also compute
$$a_2xy=\tfrac14\bigl(a_2(x+y)^2-a_2(x-y)^2\bigr).$$
Now we need to get rid of the $a_2$ factor. Since
$$xy=a_2x(a_2ya_2^{-2}),$$
it is enough to compute the constant $a_2^{-2}$ (meaning, given $n$ in unary, compute an $n$bit approximation of $a_2^{-2}$ in time $O(T(n))$). This can be done with Newton iteration: $a_2^{-2}$ is the unique root of the function $g(x)=1-(a_2^2x)^{-1}$. Thus, if $x_0$ is a suitable good appromixation to $a_2^{-2}$, the sequence given by
$$x_{k+1}=x_k-\frac{g(x_k)}{g'(x_k)}=2x_k-a_2^2x_k^2=2x_k-a_2x_k(a_2x_k1)$$
converges quadratically to $a_2^{-2}$. In order to approximate $a_2^{-2}$ to $n$ bits, we need $O(\log n)$ iterations; the final iteration needs to be computed with $n$ bits of precision, the last but one with $n/2$ bits, and so on, hence the total time is linear in
$$T(n)+T(n/2)+T(n/4)+\cdots\le(1+c_1^{-1}+c_1^{-2}+\cdots)T(n)=O(T(n)).$$
Thus, we can approximate $xy$ for $x,y\in[0,1]$ to $n$ bits of precision in time $O(T(n))$. Then we can multiply two $n$bit integers by scaling them to $[0,1]$, approximating the product, and scaling back.


How do journals serve the TCS community? In the past, journals were the main way scientific/mathematical discoveries were disseminated and vetted. In some areas, they still are. However, in (theoretical) computer science that role is almost entirely performed by conferences and open web-based dissemination (e.g. arxiv or personal homepages).

There are still TCS journals (like ToC and JACM), but they seem to primarily publish papers that have already appeared in conferences and usually have an arxiv preprint. So I don't understand what value they are adding.

What purpose do journals serve in TCS?

I have heard three arguments in favour of journals, but I don't find any of them convincing:

Journals supposedly have higher standards for reviewing than conferences. It is true that conference reviewing is under greater time pressure, but it is still the same pool of reviewers (and the amount of time the reviewer is given to read the paper has very little correlation with how long they actually spend reading the paper). As a reviewer, I don't fundamentally treat a journal review request any differently than I treat an external review for a conference.
Journal versions are higher quality than conference versions. This is true, but it is moot, as most people will read neither. When I want to read a paper, I search for it and click on the most promising link, which is almost always the arxiv version. Thus it is extremely rare for me to read a journal version of a paper even if it exists.
Journals can provide an additional quality signal on top of which conference the paper appeared in. This seems superfluous and a lot of effort for very little signal.

I have only submitted to TCS journals when invited. I have found the process tiresome, since it creates extra work and drags on for years. Thus I am not inclined to submit otherwise. Is there a good reason for me to submit?

The process of journal reviewing shakes out bugs. Conference reviewers tend not to look at papers with a fine-tooth comb; the program committee process gives them too many papers to review in too short a time to do that. The main things that one should get out of a conference review are whether there are obvious flaws (these are rare) and whether the results are interesting. A journal review should evaluate those things too, of course, but it also needs to check the details of the proofs to make sure that they all work and are clearly and correctly stated.

If you are treating your journal reviewing tasks as if they were conference reviews, and only giving them a high-level interestingness check, you are doing it wrong, and depriving journal authors of a valuable service. If you are treating your conference reviews like journal reviews, spending the time to go over them carefully, and making sure that papers don't get accepted until all the details are correct, congratulations and thank you for doing such a good job, but I don't think that's the case for most STOC/FOCS/SODA program committee members.

Secondarily, many conferences still have artificially small page limits, and the journal provides space to fill in the details. The preprint version does that, too, but doesn't provide any assurance that someone has checked it carefully.

If I see a paper published five or more years ago in a conference, making claims that are not backed up by full and clearly-written detail in the proceedings, and with no journal version, I am likely to consider it untrustworthy. Is that the future you want for your research?


Tradeoff Bounds for Halfspace Range Counting What is the current best bound for performing halfspace range counting queries on a set of $d$-dimensional points, expressed in the form of a time/space tradeoff.  According to Matousek's seminal 1993 paper (Theorem 6.2, Range Searching  with Efficient Hierarchical  Cuttings), we can do range counting for queries that are the intersection of $p$ halfspaces, for $1 \le p \le d+1$, using a data structure of size $O(m)$, for $n \le m \le n^d$, in $O\left(\frac{n}{m^{1/d}}\log^{p-(d-p+1)/d} \left(\frac{m}{n}\right)\right)$ time.  For $p=1$ this is $O(n/m^{1/d})$ time.  However, Agarwal's survey on range searching (Table 36.3.2) claims the bound is $O\left(\frac{n}{m^{1/d}}\log(\frac{m}{n})\right)$.  What is the correct statement of the bound?  Alternatively, what am I misunderstanding?  Finally, is there any hidden log term when $m=n^d$?

Matoušek's stronger time bound is correct.

The proof of Theorem 6.1 (in the journal version) uses an indirection trick that reduces the space bound required for logarithmic query time from $O(n^d)$ to $O(n^d/\operatorname{polylog} n)$.  Intuitively, the trick is to cluster the points into subsets of polylogarithmic size, build a linear-space data structure for each subset, and then build a standard logarithmic-query-time structure over the subsets.  Plugging the improved space bound into  Matoušek's multi-level/tradeoff machinery—described in gory generality in the longer version of Agarwal's survey—gives Matoušek's form of the time-space tradeoff.  (In fact, the indirection trick is just a very careful application of the standard tradeoff machinery.)


On complexity of permanent ${}\bmod 2^t$? Valiant showed $\mathsf{Per}(M)\bmod 2^t$ can be computed in $O(n^{4t-3})$ operations where $M\in\Bbb Z^{n\times n}$ holds. Has there been a better algorithm since then?

One can compute it in $\sum_{i=0}^{t-1} \binom{n}{i}n^3$ expected time. Consider a $(n+1)\times(n+1)$ matrix

$M^+ = \left[\begin{array}{ll} M & v \\ 0 & 1 \end{array}\right],$

where $v$ is a random vector with elements chosen from $\{0,1\}$, uniformly and independently. Note that $\operatorname{per}(M^+)=\operatorname{per}(M)$. Now consider Ryser's formula

$\operatorname{per}(M^+)=\sum_{(n+1)\in X\subseteq [n+1]} (-1)^{n+1-|X|}T(X)$, where $ T(X)=\prod_{i=1}^{n+1} \sum_{j\in X} M^+_{ij}.$

Note that for many $X$, the term T(X) will be zero modulo $2^t$, namely at least for all $X$'s that make $t$ or more row sums $\sum_{j\in X} M^+_{ij}=0 ( \operatorname{ mod} 2)$. We can list only those terms $X$ that stand a chance of contributing a non-zero term by solving $\sum_{i=0}^{t-1} \binom{n}{i}$ linear equation systems over GF($2$), where we guess what rows will be zero modulo $2$. In expectation there will be one solution for each guess, so by the linearity of expectation the runtime follows.

[This is proven in a paper by B., Husfeldt, and Lyckberg currently under submission.]


For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete? It is well known that the following problem is PSPACE-complete:

Given regular expression $\beta$, does $L(\beta) = \Sigma^*$?

What about determining equivalence to other (fixed) regular expressions $\alpha$?

Given regular expression $\beta$, does $L(\beta) = L(\alpha)$?

The following is known:

For $\alpha = (0+1)^*$, the problem is PSPACE-complete

For $\alpha = \emptyset$, or more generally $\alpha$ that describes a finite set, the problem is decidable in polynomial time.

It also seems likely to me that the problem is in P if $\alpha$ is a unary language.
So my questions are:

For which $\alpha$ is the above decision problem PSPACE-complete? Is there a complete characterization?
Are there any $\alpha$ for which the decision problem has some intermediate complexity (like NP-complete)?

This question is addressed in Section 2 of [1], which shows (Theorem 2.6) that the problem is

in P if $L(\alpha)$ is finite;
coNP-complete if $L(\alpha)$ is infinite but bounded (i.e. $L(\alpha)\subseteq w_1^*w_2^*\ldots w_k^*$ for some $w_1,\ldots, w_k$);
PSPACE-complete otherwise.

[1] Harry B. Hunt, Daniel J. Rosenkrantz, Thomas G. Szymanski, On the equivalence, containment, and covering problems for the regular and context-free languages, Journal of Computer and System Sciences, Volume 12, Issue 2, 1976, Pages 222-268, ISSN 0022-0000, http://dx.doi.org/10.1016/S0022-0000(76)80038-4.
(http://www.sciencedirect.com/science/article/pii/S0022000076800384)


What kind of computational model is the brain? I was wondering what kind of computational model is the human brain (as it seems superior to a Turing machine).
Another thing that should be a separate question, What would be a perfect computer model be like, is our brain any close to it?
Apology for putting the ideas in a very beginner way, which ofcourse I am.

This is pretty much an open problem and subject to active research. There are a few proposals available. Here are some of the latest ones:

Brain computation by assemblies of neurons Christos H. Papadimitriou, Santosh S. Vempala, Daniel Mitropolsky, Michael Collins, Wolfgang Maass Proceedings of the National Academy of Sciences Jun 2020, 117 (25) 14464-14472; DOI: 10.1073/pnas.2001893117 [Link]

Manuel Blum's model of consciousness: [Video]


VC dimension for balanced binary decision trees What is the VC dimension of all balanced binary decision tree of
depth $k$ in $\{0,1\}^d$? Does it depend on depth $k$ or dimension $d$?

It is shown here (slide 10) that if $H_{d,k}$ is the number of depth-$k$ decision trees over $d$ input bits, then
$$v:=\log_2(H_{d,k})=
(2^k-1)(1+\log_2(d))+1
.
$$
So $v$ is an upper bound on the VC-dimension of your class. I don't know how tight it is, since you have the additional constraint of the trees being balanced.


Recovering a parse forest from an Earley parser? I was recently reading up on the Earley parser and think it's one of the most elegant algorithms I've seen to date.  However, the algorithm in its traditional sense is a recognizer and not a parser, meaning that it can detect whether a string matches a particular CFG but not produce a parse tree for it.  My question is how to recover not a parse tree, but rather the parse forest of all possible parses of the given input string.

In Grune and Jacob's "Parsing Techniques: A Practical Guide" they illustrate an algorithm that can be used to recover a parse forest from the result of the Earley recognizer, but it is based on Unger's parsing method, whose runtime is O(nk + 1), where k is the length of the longest production in the grammar.  This means that the runtime is not a polynomial in the size of the grammar.  Moreover, Earley's original paper on the algorithm, which suggests an algorithm for recovering parse forests, is incorrect (see, for example, page 762 of this article by Tomita), although many sources still cite it as the appropriate way to recover the parse forest.

My question is whether it is possible, in polynomial time, to recover a parse forest for a given input string.  I have found a paper here that provides an algorithm for producing cubic-size parse forest representations for any parse using a simulation of a PDA, so this seems like it should be possible, but I have yet to find any way to do this.  Ideally, I'd like to do this without converting the input grammar to CNF (which would indeed solve the problem), since the resulting parse forest would be pretty messy.

Thanks for any help you can offer!

Doing that would of course depend on the right representation for a "packed forest" that represents all parse trees for a given sentence.

I think the place you want to start looking is at Joshua Goodman's thesis (parsing inside out, Harvard, 1999). Basically, the idea is that you can define a parsing algorithm under a certain semiring. Depending on the semiring, you would be able to calculate all kind of quantities and structures instead of the bare parse tree (as a recognizer or as a parser). One semiring that you could define (which Goodman does in his thesis) is a semiring where the values are sets of parses. When you eventually finish parsing a sentence, you'd get all parse trees in the main parse node.

Again, you have to be careful about making it possible through the right representation.


VC-dimension of spheres in 3 dimension I am searching for the VC-dimension of the following set system.

Universe $U=\{p_1,p_2,\ldots,p_m\}$ such that $U\subseteq \mathbb{R}^3$. In the set system $\mathcal{R}$ each set $S\in \mathcal{R}$ corresponds to a sphere in $\mathbb{R}^3$ such that the set $S$ contains an element in $U$ if and only if the corresponding sphere contains it in $\mathbb{R}^3$.

Details which I already know.

The VC-dimension is atleast 4. This is because if $p_1,p_2,p_3,p_4$ are 4 corners of a tetrahedron then it can be shattered by $\mathcal{R}$
The VC-dimension is atmost 5. This is because the set system can be embedded in $\mathcal{R}^4$ with spheres in $\mathcal{R}^3$ corresponding to hyperplanes in $\mathcal{R}^4$. It is known that hyperplanes in $\mathcal{R}^d$ have VC-dimension $d+1$.

My solution is incorrect. See other answer...