a data structure for partial sequences We have a set of bit sequences of length $L$ with only $K$ known bits and $L-K$ gaps.
We want to store them in a data structure in a way that given a new bit sequence $x$ of length $L$, with $L$ known bits, we can efficiently search and retrieve the elements in the data structure that are sub-strings of $x$. What data structure and search method do you recommend?

for example, $L=5$, $K=3$, and data=${1.10., 11..0, 10..1, 01.1., 101..}$
given $x=10101$, following elements are returned: ${1.10., 10..1, 101..}$

In a more realistic example, we expect L=15, K=7, |data|=100,000, our priority is search time, however, the data structure (/index) size should be reasonable too (lets say smaller than 1GB)

This question was originally asked at math.stackexchange: link

EDIT: We are also interested in the more general case where data elements re nucleotide sequences (using alphabet {${A,C,G,T}$} instead of binary sequences). The main difference in that case is that number of all sequences of length L, will be $4^{L}$ instead of $2^{L}$ for binary.

A naive approach is as follows. This approach can be used when no better solution is available:

Keep a ternary search tree: Each node (except leaves) has three children: a 0, a 1, and a .. The height of tree is L. Each leaf stores 1 bit: whether the pattern denoted by the path from the root to that leaf exists in your sequence.

A full ternary search tree takes a space of $3^L$. Since L is rather small (L=15), the space will be $3^{15} \approx 14 \ MB$. Since |data|=100,000, and since K << L, it is possible to prune the tree in such a way that it takes much less space.

Now, a backtracking algorithm can search this data structure: Given input x, it starts at the root of the tree, and checks the MSB of x. This bit is either 0 or 1. Assume wlog that the bit is 0. Then, the algorithm omits the 1 child, and takes the 0 and . children. This is continued until we find a match, a mismatch, or when the number of .'s along the path becomes greater than K (assuming the tree is not pruned already).

The above algorithm may take a long time, unless you have pruned the tree properly. That is, if a node does not have a child in the data, mark it as having no child.

Note that since $\binom{15}{7} = 6435$, in the extreme case, up to 6435 patterns in data might match x (which is 6% of |data|; so even the best algorithm has to search this fraction of the database in the worst case).


Learning about EXPTIME and EXPSPACE I'd like to know some good starting points (such as books, papers, lecture notes, etc.) on EXPTIME and EXPSPACE.  I'd like to learn more about these two topics, but I'm not sure what the best approach is....

You may start from the connection between polynomial identity problem and exponential time classes. Polynomial identity problem has significant importance in both algorithm and
complexity theory. The recent breakthrough for faster exponential time exact algorithm for Hamiltonian cycle problem
was derived via a reduction to polynomial identity. From the complexity point of view,
derandomization of polynomial identity implies the separation of NEXP or PP from P/ploy.
Therefore, I believe that polynomial identity will continue to play an important role in both
algorithm and complexity theory. It is closely related to some exponential time algorithmes, and
also the separations between exponential time classes and non-uniform circuit classes.


Travelling Salesman and Planar Travel - Generalized TSP Our beloved Travelling Salesman just bought the Manual of the Planes and wants to make some use of it. He is not a great adventurer though, so he will restrain his travels in the Parallel and Fundamental Planes, which are tightly coupled with the Material Plane (and try not to spend so much time in the Quasi-elemental Plane of Minerals and all the gold that lies there!). Let's say therefore that we have M-1 Parallel Planes and our salesman can visit each city in any of them. Travel from Material Neverwinter to Astral Luskan is of course different than travel from Material Neverwinter to Material Luskan and not always in a trivial manner (might cost more, might cost less). To make matters worse, the Salesman can visit each city in only one Plane and cannot therefore benefit from a portal connecting Shadow Waterdeep with Faerie Baldur's Gate if he initially arrived in Material Waterdeep (assume Dimensional Anchors covering the cities). So the Salesman has to complete his path using these new restrictions.

A 4th Level Wizard exclaimed instantly that this Plane Travelling Salesman has a problem that is not easier than those of his normal colleagues (just assume that the travel between two cities costs the same regardless of the Planes used and you have a classic TSP). The question is: How can he convert the problem into another that has already been researched by the scholars?

Less nerdy description:

Replace each of the N nodes in the original TSP with M subnodes. Distances are given for every pair of subnodes between different nodes. For each node, a single subnode must be used in the solution. Give an algorithm for the new problem.

Edit:

It turns out that it is indeed a well-researched problem so I am adding all the aliases I found for it.

Generalized TSP
Group TSP
TSP with Neighbourhoods
Set TSP
One-of-a-Set TSP
Multiple Choice TSP
Covering Salesman Problem

If the tour is required to visit one node in each group, then the problem is called Group-TSP, or TSP-with-neighborhoods. There's a ton of work on this in the plane (just google it), and in general it's as hard as HITTING SET (the case in which your metric is all 1s). There's a paper by Safra and Schwartz that shows that Geometric group TSP (in the plane) is hard to any constant factor.


Proving membership in W-hierarchy when problem is not parameterized by its solution size I'm curious about the following general problem:
Suppose that we have a parameterized problem whose input is $x$ and parameter is $k$ (which is NOT the size of a solution but something about the input), and we know that its solution size can be as big as $|x|$ in general.
One example is the Independent Set Problem parameterized by the max-degree of a vertex, where we ask whether there exists an independent set of size at least $s$ (which is NOT the parameter) given a graph of $n$ vertices with max-degree $d$ (which is the parameter).
(Compare this with the Clique problem with bounded degree, which is in FPT -- here, the size of a solution (clique) is also bounded because of the bounded degree, so it's different.)
(1) First of all, is this even a fair parameterized problem, when the size of a solution is only polynomially bounded by the size of an input (because $s$ can be as large as $n$)?
The reason for this first question is mainly because I can't imagine how this problem can be reduced to the weft-t weighted circuit satisfiability problem to show that it belongs to W[t] (for t >= 1), in particular, if it does belong. Specifically, a solution (= a large independent set) would have to contain $s$ vertices, but we can only set $f(d)$ input nodes to true in a hypothetical WCSAT instance we create (since $d$ is the only parameter being considered).
This makes me think that perhaps the problem I wrote above is ill-defined in the first place (or, maybe it trivially implies that it can't belong to W[t] for any fix t, but this is what I am confused about). As a follow-up if the above problem is well-defined and it actually belongs to W[t] for some constant t, I'd love to know how one can show that.
Update: After my initial post, I realized that this is (probably) para-NP-hard since the independent set problem is already NP-hard when $d = 3$, and so is the vertex coloring problem. What I meant to ask was (not specifically about the independent set problem I wrote) whether this is in general true: When a problem is parameterized by something other than the size of a solution (and as a result, the size of a solution is still unbounded in terms of the parameter), then does it imply that the parameterized problem is W[t]-hard for all t, at least?
(2) My next question is (if this question makes sense):
When we try to show that a problem that is not parameterized by the size of a solution AND its solution size (under the said parameterization) is still only polynomial in input size, what are some known techniques for doing this? Are there any known problems (assuming that my question in the previous paragraph was "NO, it's not always implied")?
I'd love to see relevant examples and papers, if anyone can recommend.
I've searched a few references, but I couldn't quite find an answer to my questions.

The answer to your updated Question (1) "When a problem is parameterized by something other than the size of a solution (and as a result, the size of a solution is still unbounded in terms of the parameter), then [is it] W[t]-hard for all t, at least?" is no. Independent Set for example is FPT with respect to the treewidth $\omega$ of the input graph. The solution size $k$ (essentially the size of a largest independent set of the input graph) can be much larger than $\omega$.
In general, a parameter can be anything that is related to the input instance. The standard parameter solution size is just one of many different ways to parameterize a problem.


Jumping (Busy) Beaver variant Is the following Busy Beaver variant known?

A Universal Turing machine $J$, feeded with a description of a deterministic Turing machine $M_i$, starts simulating $M_i$ on inputs $x_j = 1,2,3,...$ for $|x_j|^i$ steps until $M_i(x_j)$ accepts; then $J$ outputs $x_j$ (if $M_i$ doesn't halt in $|x_j|^i$ steps  $J$ continues with the next $x_j$). In other words:

$$J(M_i) = min\{ x \mid M_i(x) \text{ halts and accept in less than } |x|^i \text{ steps}\}$$

Fancifully, $J(M_i)$ - when defined - represents how high the polynomial-time Turing machine $M_i$ can "jump". So, for every $n$, we can define the Jumping Beaver as the Turing machine $M$ of size $n$ that achieve the highest jump $j(n) = max \{ J(M) \mid |M| = n\}$ .

But in a similar way we can define $J'$ that "measures" the jumps of a nondeterministic Turing machine $N_i$ ($J'$ simulates all branches of $N_i$ on input $x$ for at most $|x|^i$ steps).

  Do nondeterministic jumping beavers perform better than deterministic jumping beavers? I.e. does $j'(n) > j(n)$ hold? (for some values of $n$ or infinitely often)
  What about the limit $\lim_{n \to \infty}j'(n)/j(n)$?

Note: the enumeration of the deterministic Turing machines $M_i$ is different from the enumeration of the nondeterministic $N_i$ (due to the nondeterministic transitions), so, to make $J$ and $J'$ directly comparable, we can follow this alternative approach: $J$ simulates $M_i$ on input $x_j \# 0^{|x_j|}$;  $J'$ can take as input a deterministic Turing machine $M_i$, too but simulates it on inputs $x_j \# y$ for all $y \in \{0,1\}^{|x_j|}$ and stops its search if at least one computation accepts. In this setting that seems equivalent to the formulation above (indeed $J'$ seems to capture all the power of NP), it is easy to see that $j(n) = j'(n)$.

the halting problem does not seem to be studied much for nondeterministic TMs (there is no single obvious way to extend the halting problem to NTMs) and most problems associated with undecidability seem to be defined in terms of non-NTMs (ie DTMs). however here is one generalization that could be related to your question.

A Parameterized Halting Problem Yijia Chen and Jorg Flum

  The parameterized problem p-Halt takes as input a nondeterministic Turing machine M and a natural number n, the size of M being the parameter. It asks whether every accepting run of M on empty input tape takes more than n steps. This problem is in the class XPuni, the class “uniform XP,” if there is an algorithm deciding it, which for fixed machine M runs in time polynomial in n. It turns out that various open problems of different areas of theoretical computer science are related or even equivalent to p-Halt ∈ XPuni. Thus this statement forms a bridge which allows to derive equivalences between statements of differ- ent areas (proof theory, complexity theory, descriptive complexity, . . . ) which at first glance seem to be unrelated. As our presentation shows, various of these equivalences may be obtained by the same method.


Find the Discrete Pair of {x,y} that Satisfy Inequality Constriants This question has been asked at StackOverflow ( a variant of this has been asked at Math SE), but so far there is no great response. So I'm going to reask here-- with a bit of twist.

I have a few inequalities regarding $x,y$ ( both must be integer), that satisfies the following equations:

$$x>=0$$
$$y>=0$$
$$100 \leq x^2+y^2 \leq 200$$

Is there an algorithm (non-brute force!) that allows me to find every admissible pair of $x,y$?

The $100 \leq x^2+y^2 \leq 200$ is just an example; in general the constraint equation(s) can be of polynomial functions with any degree.

This is a rasterization problem. For linear inequalities, the regions are polygonal. The classical approach to polygon rasterization is scan conversion; you may learn about it in any textbook on computer graphics.

Preparatory to scan conversion, you will need to convert your linear inequalities (defining half-planes) into an oriented list of edges. One way is to compute the convex hull of the dualized inequalities.

For general polynomial inequalities, the problem is considerably harder. Scan conversion with plane sweeping and active edge lists will do the trick. Detecting sweep events requires you to solve systems of polynomial equations in two variables, which may be done with a combination of numerical and symbolic methods. One way uses resultants and root finding to determine the intersection events up front. Another approach is more incremental, less efficient but significantly simpler:

Assume a bounding box is given. For each y going from the maximum to the minimum, incrementally evaluate the coefficients of the polynomials as functions of y using forward differencing, yielding polynomials depending only on x for each scan-line. Their roots will serve as the rasterization bounds for that scan-line, and you can learn how to find them in a book on numerical methods (Numerical Recipes is popular).

Edit: When I wrote my answer, the last inequality had subscripts rather than superscripts, so it appeared linear. Now I see it is quadratic. That still makes it a rasterization problem although a non-polygonal one. For this specific case you can use circle rasterization to cut out the annulus. In the most general case, you will need polynomial techniques along the lines of my last paragraph. I added some more detail on this.


k-clustering problems I'm interested in open questions from the book Approximation Algorithms for NP-Hard Problemss dedicated to k-clustering. They are:

  Is Euclidean max cut solvable in polynomial time? If not, how well can
  it be approximated?

  Does the problem minimizing the sum of distances from points to their
  cluster centers has good approximation algorithm ?

The problem of minimizing the sum of distances from points to cluster centers is called the $k$-median problem. In a general metric space, the $k$-median can be approximated to within a factor of $3+\epsilon$ and is $\mathsf{MAX SNP}$-hard. In Euclidean space, the problem admits a PTAS. This is a good survey and has references for the above facts.


Maximal/maximum independent sets Is there something known about the class of graphs with the property that all maximal independent sets have the same cardinality and are therefore maximum ISs?

For example, take a set of points in the plane and consider the graph of intersections among all segments between pairs of points in the set. (segments->vertices, intersections->edges). This graph will have the above property, as all maximal ISs correspond to triangulations of the original point set. Are there other categories of graphs known to have this property? Can this property be easily tested?

Such graphs are called well-covered graphs.  Here is a recent paper on the subject that lists several useful references.  As Suresh mentioned, the recognition problem is co-NP-complete.

Note that the independent sets of a graph form an abstract simplicial complex.  Simplicial complexes that arise in this way are called "independence complexes" or "flag complexes."  A simplicial complex is said to be pure if every maximal simplex has the same cardinality.  So you may find some relevant papers by searching for "pure independence complex" or "pure flag complex."


Ajtai's Proof of Theorem 1 in 'Generating Hard Instances of Lattice Problems' My question pertains to the proof of Ajtai's main theorem in his groundbreaking 1996 paper, Generating hard instances of lattice problems, which indicates a connection between worst-case hard and average-case hard lattice problems.
This proof is  difficult for me to understand. Is there a clear exposition of this proof in the literature?

You can try reading more recent papers such as Worst-case to Average-case Reductions based on Gaussian Measures by Miccancio and Regev, or Regev's  lecture notes on the subject (you might want to read through the entire course).


Running Simon's algorithm on D-wave machine I was wondering whether Simon's algorithm could be run on a D-wave machine.
The Simon's algorithm is a promise problem. On the other hand the D-wave machine can run only quadratic unconstrained binary optimization problems. So, we need to convert the Simon's algorithm into an optimization problem. Is that possible?

Simon's algorithm is special because of its query complexity. Hypothetically, each query may correspond to a clock cycle. In that case, the difference between the number of cycles on a classical and a quantum computer will be different. On a D-wave computer we don't run a program over clock cycles. But it is true that the evolution of the Hamiltonian is traced over iterations and it could be correspondences to hypothetical clock cycles. Is there any way we could redefine the query complexity in the context of D-wave computer?

D-wave's famous Chimera architecture is a bipartite graph. Can we create an instance of Simon's algorithm on the bipartite graph?

Short answer: No.

There are really two separate issues to unpack here:

Even if it worked exactly as advertised (which, as you might have heard, is somewhat disputed at present... :-) ), D-Wave's machine, by the company's own account, is only for adiabatic optimization.  There's no particular reason to think that it could implement (e.g.) Shor's factoring algorithm, or other algorithms in the usual quantum circuit model.
Even if you had a standard, universal quantum computer---so, not any of D-Wave's current or planned devices, but a "gate model" QC capable of running Shor's factoring algorithm and so forth---even then, Simon's algorithm in particular requires that the QC make quantum queries to a hypothetical black box.  So in order to run Simon's algorithm, you need some explicitly-computable function that "instantiates" the black box.  Right now, however, no one has a very clear idea whether there exist such explicitly-computable functions that satisfy the Simon promise, for which a classical algorithm couldn't also use the explicit descriptions to solve Simon's problem efficiently.  Note that Shor's and Simon's algorithms are very similar at some level.  The main advantage of Shor's over Simon's is that, with the former, we do know an explicitly-computable function---namely, the modular exponentiation function---that "instantiates" the abstract periodic black box (and that, moreover, has some practical importance...).


P vs NP: Instructive example of when Brute Force search can be avoided To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately understandable and the trick should neither be too easy nor too hard.

The best I've come up with so far is

SUBSET_PRODUCT_IS_ZERO

The problem is easy to understand (given a set of integers, can a subset with product 0 be formed?), but the trick is too easy (check if 0 is among the given numbers, i.e. it's not necessary to look at a lot of subsets).

Any suggestions?

I recommend Jenga!

Assuming you have two perfectly logical, sober, and dextrous players, Jenga is a perfect-information two-player game, just like Checkers or Go.  Suppose the game starts with a stack of $3N$ bricks, with 3 bricks in each level.  For most of the game, each player has $\Theta(N)$ choices at each turn for the next move, and in the absence of stupid mistakes, the number of turns is always between $N$ and $6N$.  So crudely, the game tree has $N^{\Theta(N)}$ states.  If you explored the game tree by brute force, you might spend exponential time to find a winning move or convince yourself that you can't win.

But in fact, Uri Zwick proved in 2005 that you can play Jenga perfectly by keeping track of just three integers, using a simple set of rules that you can easily fit on a business card.  The three numbers you need are

$m =$ the number of levels (not counting the top level) with three bricks.
$n =$ the number of levels (not counting the top level) with two bricks side by side.
$t =$ the number of bricks in the top level (0, 1, 2, or 3).

In fact, most of the time, you only have to remember $n\bmod 3$ and $m\bmod 3$ instead of $n$ and $m$.  Here is the complete winning strategy:

Here I-I means you should move the middle brick from any 3-layer the top, II- means you should move a side brick from a 3-layer to the top, -I- means you should move a side brick from a 2-layer to the top, and the bob-omb means you should think about death and get sad and stuff.  If there's more than one suggested move in a box, you can choose any one of them.  It's trivial to execute this strategy in $O(1)$ time if you already know the triple $(m,n,t)$, or in $O(N)$ time if you don't.

Moral: Jenga is only fun if everyone is clumsy and/or drunk.


Is there a simpler proof of Beigel and Tarui's transformaion of ACC0 circuits Beigel and Tarui's transformation of $\mathsf{ACC}^0$ circuits to depth 2 circuits with a polylog symmetric function on top is one of important results in the circuit complexity. For example, the recent breakthrough separation between $\mathsf{NEXP}$  and $\mathsf{ACC}^0$ by Ryan Williams uses this transformation to design a fast $\mathsf{ACC}^0$-CircuitSAT algorithm.

I think the proof in their paper is a little complicated and too technical for me. Is there a simpler proof of their result?

This result is presented in the Web Addendum of Arora-Barak, which can be found here.


Resources (books, etc) to learn about concurrency theory I want to know more about concurrency theory from a formal/mathematical point of view, I know there are a lot of computer science branches that relates to concurrency theory like process algebra, Petri nets, Actor model, CSP, etc.

But I don't know about classic books on that topics, and also I would like to know in which order it's better to study, I'm new to this field, I have some basic knowledge on λ-calculus and Turing machines theory.

What resources do you recommend to begin with this theory?

There are not that many books on this subject, as it continues to evolve at a rapid pace.

Classic books on process calculi (that don't focus on π-calculus-like mobility) are:

C. A. R. Hoare, Communicating Sequential Processes.
A. W. Roscoe, The Theory and Practice of Concurrency.
M. C. B. Hennessy, Algebraic Theory of Processes.
R. Milner, Concurrency and Communication.

There are two main books on π-calculus:

R. Milner, Communicating and Mobile Systems: The Pi Calculus.
D. Sangiorgi, D. Walker, The Pi-Calculus: A Theory of Mobile Processes.

The Sangiorgi/Walker book is not easy reading. The others books above can be used by a learner.

All of the books above are (mostly) about untyped processes. There is a single book on types for interactive processes (from June 2017).

S. Gay, A. Ravara, Behavioural Types: from Theory to Tools.

Regarding recommendations, that would depend on your background and specific goals. The Milner and Hoare books should be easy to access. After those you can read the original papers.


Is there algorithmic mathematical analysis? There are algorithmic graph theory/number theory/combinatorics/information theory/game theory.

  Is there algorithmic mathematical analysis?

According to wiki, mathematical analysis includes the theories of differentiation, integration, measure, limits, infinite series, and analytic functions. It is OK to focus on real analysis (wiki) that deals with the real numbers and real-valued functions of a real variable.

"Algorithmic" means studying something from the perspectives of computability theory and complexity theory.

Googling of "algorithmic mathematical analysis" leads me to "mathematical analysis of algorithms" or "applications of analysis to algorithms", which is not what I mean.

Check out
the Computability and Complexity in Analysis network. Quote:

The topics of interest include foundational work on various models and approaches for describing computability and complexity over the real numbers. They also include complexity-theoretic investigations, both foundational and with respect to concrete problems, and new implementations of exact real arithmetic, as well as further developments of already existing software packages.


Finite state transducer that sorts Is it possible to sort a string of arbitrary length with a finite-state transducer? How big would this transducer be (the smaller the better)? (I'm not a computer scientist, so less technical answers are best.)

If you allow me to give an answer that uses "technical" terminology: the output of a finite state transducer on any given regular language is again a regular language. The sort of regular $(ab)^*$ equals non-regular $\{ a^nb^n \mid n\ge 0\}$. Thus that cannot be performed by a FST.

(added) The fact that regular languages are closed under FST is a consequence of Nivat's Theorem. Every FST $T$ can be decomposed into a regular language $R$, and morphisms $g,h$ such that $T(L) = g(h^{-1}(L) \cap R)$. In short $R$ consists of "letters" of the form $(a,b)$ where $a,b$ are from the input and output alphabets respectively (or empty), and $h,g$ select  the input/ output components from those pairs.


Minimum Union-Sum Cost Path I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path have that type of cost. For example, in the example below, cost of the red path that goes from S to D is C(F1)+C(F2). Although both F1 and F2 appear multiple times along the path, each one of them is only counted once. This path also is the minimum cost path since any other path will have F3 as well and so its cost will be C(F1)+C(F2)+C(F3). Costs are positive real numbers and are known for each item.

I named it Union-Sum Cost since if we look at different edges, cost of a path is the sum of costs of the union of items associated with the edges on the path.

Has this problem been solved before? (like an approximation algorithm) Is there a well-known graph problem that resembles this? And do you think this is a hard problem?

EDIT (Jan 2019): Lemma 2 as currently stated below is wrong. (Indeed, given any instance, adding a single edge with a single type of very large cost will not change the instance but will yield $N(I)=1$, in which case the lemma claims that the algorithm will give an optimal solution.  The proof is wrong because the function $\Phi$ defined there is not supermodular.)  I do believe that the proof can be fixed, and the algorithm there can be patched, to obtain an $O(\log n)$-approximation algorithm.  I'll correct it  hopefully later this month. -NY

Your problem generalizes Set Cover, and in turn is a special case of the classical problem of minimizing a linear cost function subject to a submodular constraint, a problem for which the greedy Set-Cover algorithm and its logarithmic approximation ratio naturally extend (as observed e.g. by Wolsey in the 1980's).  Consequently, there is a poly-time log-approximation for your problem, and (unless P = NP) that is the best you can do. Here are the details.

Given any instance $I$ of your problem, define $N(I)$ to be the minimum, over all source-to-destination paths $p$, of the sum, over the edges $e$ in $p$, of the number of labels $F_i$ that $e$ has.  Unless P=NP, the best approximation-ratio obtainable for your problem is $\ln N(I)$ (up to lower-order terms). The reasoning is in two steps: a hardness result, then a poly-time $\ln N(I)$-approximation algorithm.

Here's the hardness result, showing that your problem subsumes Set Cover.

Lemma 1. Unless P=NP, the problem has no $((1-\epsilon)\ln N(I))$-approximation algorithm for any $\epsilon>0$.

Proof. We give an approximation-preserving reduction from unweighted Set Cover.  Given an unweighted Set-Cover instance $(S_1, S_2, \ldots, S_m)$ on a universe $U=\{1,2,\ldots,n\}$, construct a multigraph with vertex set $\{1,\ldots,n,n+1\}$ where, for each element $i\in U$, for each set $S_j$ containing $i$, there is an edge $(i, i+1)$ with a single label $F_j$.  Set $C(F_j) = 1$ for each $j$.

(Note: If a multigraph is not allowed, one can simply split each $(i, i+1)$ with label $F_j$ into a path $(i, v(i,j), i+1)$ where $v(i,j)$ is a new vertex, edge $(i, v(i,j))$ has label $F_j$, and edge $(v(i,j), i+1)$ has no label...)

Then for any path $p$ from vertex $1$ to vertex $n+1$ there is a set cover $C(p) = \{S_j : F_j \text{ is the label of some edge on } p\}$ of size equal to the cost of $p$, and vice versa.  Also, $N(I)$ for this instance $I$ equals $n$.

So, if there is a $(1-\epsilon)\ln N(I)$-approximation algorithm for your problem, then there is a $(1-\epsilon)\ln n$-approximation algorithm for Set Cover.  Unless P=NP, there is no such algorithm. $~~~\Box$

EDIT: The remaining part is wrong, see comment at top.

Here's the upper bound, showing that your problem is a special case of minimizing a linear cost function subject to a submodular constraint.

Lemma 2. The problem has an $H_{N(I)}$-approximation algorithm, where $H_i \approx \gamma + \ln i$ is the $i$'th Harmonic number.

Proof. Fix an instance $I$ of the given problem. Assume without loss of generality that each edge in the graph has only one label.  (Otherwise, for any edge having, say, labels $F_{i_1}, F_{i_2},\ldots,F_{i_k}$, replace the edge by a path of $k$ edges, where the $j$th edge has label $F_{i_j}$.  This does not change $N(I)$.)

Given any set $S$ of labels, define $\phi(S)$ to be the minimum, over all paths $p$ from the source to the destination, of the number of edges on $p$ whose label is not in $S$.  Define the cost of $S$ to be the sum of the costs of the labels in $S$. Then

$\phi$ is supermodular,  $\leftarrow$ EDIT: THIS IS NOT NECESSARILY TRUE
$\phi(\emptyset) = N(I)$,
$\phi(S) = 0$ if and only if there is a path from the source to the destination that uses only labels in $S$, and
the cost of $S$ is the cost of the labels in $S$.

Now apply Wolsey's generalization of the greedy-set-cover algorithm (for minimizing a linear function subject to a submodular constraint) to find an approximately minimum-cost set $S$ with $\phi(S) = 0$.  That algorithm is:

$S \leftarrow \emptyset$
while $\phi(S) > 0$:
. . choose label $F_i$ maximizing
$\displaystyle\frac{\phi(S) - \phi(S\cup\{F_i\})}{C(F_i)}.$
. . add $F_i$ to $S$
return $S$

That algorithm is known to compute a solution $S$ of cost at most $H_D$ times the minimum, where $D = \max_{S,F_i} \{ \phi(S)-\phi(S\cup\{F_i\}) \le \phi(\emptyset) = N(I)$.

By inspection the algorithm can be implemented to run in polynomial time.

And, given the set $S$ with $\phi(S)=0$, one can easily compute in poly-time a path $p$ from the source to the destination with cost at most the cost of $S$.  $~~\Box$

Did I miss anything here?

Wolsey's original paper:

[1] L. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385–393, 1982. (See here for a summary.)


Solve a simple system of linear inequalities in natural numbers I want to find a solution to a system of linear inequalities of the following form

\begin{aligned}
a_1 + b &\ge a_2 \\\
\vdots \\\
a_4 + c &\ge a_1
\end{aligned}

where $a_i \in \mathbb N \setminus \{0\}$ and $b,c \in \mathbb Z$. All inequalities consist of exactly two variables and one free factor. All $a_i$ appear as they are, and have no coefficient other than $1$.

The goal is to find a solution (perhaps more than one, but not necessarily), or declare the system as not having one. Such a solution would be vastly preferable to any linear programming ones.

I do remember some algorithm based on constructing a graph and then launching Floyd-Warshall algorithm could solve a similar problem, but I'm not sure.

EDIT: Problem expansion - how can I find such a solution that the number of distinct integers in the solution is maximized (the default Bellman-Ford behavior minimizes it)

Construct a graph with one vertex per variable, and one extra vertex $s$. Make an edge from $s$ to all other vertices, of length zero. For each inequality $a_i + c \ge a_j$, make an edge of length $c$ from $a_i$ to $a_j$. Then if your graph has a negative-length cycle, your inequalities have no solution, and if it does not have a negative-length cycle then the distance from $s$ to each vertex gives a solution. You can use Floyd or Bellman–Ford or any other shortest path algorithm that can allow negative weights.


Selecting papers to read DISCLAIMER: This is an open ended question and stackexchange puritans would probably feel an extraordinary urge to vote it down to oblivion. However, I cannot think of any other forum more appropriate and promising for getting answer to this question.

While working on a research problem for course project I realize that if I model my problem in a particular way I could use techniques from a specialized track [for the recent case - PASCAL Recognizing Textual Entailment Challenge]. After the initial joy, I'm generally puzzled by the numerous papers with all of them silently shouting "Read me, else you'll miss the best way to solve the problem!". How does one learn to filter which paper to read and which one to discard in the face of deadline? Anything other than sort_by_citation count?

If possible, find a survey, book, or a lecture note. This will help a lot to see the jungle through the trees! To find books, Google Books is your friend. Search the keywords in the Google Books, and try to find a relevant book on the subject.
Take the top-down / bottom-up approach, and alternate. That is, read the most recent papers first (the top research), and references thereof (bottom). Why? Because the top research is likely to be better, and has probably surveyed bottom works and improved them. However, to understand top, it is usually the case that you need to skim the bottom works. Important: Don't get stuck at the bottom. After reviewing older works, take the bottom-up approach. Finally, alternate between the top-down and bottom-up approaches.
Don't read a paper unless you are somehow sure that it is really relevant. The relevancy depends on several factors: The amount of citations, the fame of authors, the conference/journal it is published in, and so on.
Be sure to read the title and abstract carefully, and skim the sections. Decide if you should ever read this paper now, and to what extent.
If a paper has a conference version and a journal (full) version, select the first one. The conference version usually gives the general idea, and avoids cumbersome proofs. Read the full version only when you really need to learn the proof details/technique.

Edit 1: Some of my colleagues use reference manager tools like Zotero to help them organize their references. I'm not acquainted with such tools, but I think you should give it a go.


Coding theory and complete problems Coding theory is an useful topic in theoretical computer science. There are known examples of problems coming from coding theory which turn out to be NP complete.

My questions are the following:

$(1)$ Are there natural good examples of coding theory problems that lie in different levels of the polynomial hierarchy above NP and are complete for those levels?

$(2)$ Are there natural good examples of coding theory problems that are PSPACE complete? (Note that a coding theory approach is used to show IP=PSPACE in http://www.math.ias.edu/~ormeir/papers/ip_pspace.pdf)

An answer to the first question can be found in a paper by Schaefer and Umans, Completeness in the polynomial-time hierarchy: A compendium (2002).

In subsection "Coding and cryptology" (see p. 24), two $\Pi_2^p$-complete problems appear: checking an upper bound on the covering radius of a linear code, and deciding whether a linear code is $r$-identifying ($r$ part of the input). A certain $\Sigma_3^p$-complete problem called "Minimum block decoder" can be found on p. 28 (see also $\Sigma_2^p$-complete "Minimal block encoder and decoder", p. 25).

I guess following the references should help in digging out more related problems.


Deterministic Parity Automata require unbounded index Deterministic parity automata $(Q, \Sigma, q_0, \Delta, c)$ are powerful enough to recognize all $\omega$-regular languages. However, the number of priorities they require for a language can become arbitrarily high. For example, the languages $L_{i,j} = \{ \alpha \in \{i, \dots, j\}^\omega \mid \text{The highest number occurring infinitely often in } \alpha \text{ is even} \}$ require at least $j-i+1$ priorities. I was not able to prove this theorem so far by myself, in particular I am stuck at the case that the automaton uses exactly the priorities from $i+1$ to $j$. I could not lead this assumption to a contradiction.

Any help or link to a paper would be appreciated.

Take a look at the following paper:
Relating hierarchies of word and tree automata.
They cite the result you are interested in.

As a more concrete answer, consider the following argument: let's look at the language $M_n=\{w\in \{0,...,n\}^\omega: \limsup w_i \text{ is even}\}$ (the same as your language with $i=0$), and assume it has a parity automaton $A$ with ranks $1,...,n+1$ (note that proving it doesn't have a parity automaton with ranks $1,...,n$ is not enough, as it's still possible for it to have ranks $0,...,n-1$).

We will construct a word that is accepted by $A$, but is not in the language (or vice-versa). Denote by $k$ the number of states in $A$. Consider the run of $A$ on the word $0^\omega$. It's accepting, so the limsup degree is even, and so at least $2$. Moreover, it must occur during the first $k$ steps, otherwise, since $A$ is deterministic, we have a non-accepting cycle. In addition, this is true for every $0^k$ infix of any word.

Now, consider the word $(0^k1)^\omega$. This word is not accepted, so the limsup degree is odd, but must be at least 3, since the $0^k$ infixes induce the degree $2$. Finally, this odd degree must occur within the first $k$ cycles of $0^k1$, for similar reasons as above.

We can repeat these alternating examples, constructing a word of the form $(0^k1)^k2$, and so on, with each word requiring a higher degree. However, since we only have degrees $1,...,n+1$, then eventually we will have a word that uses the letters $0,...,n-1$, whose limsup degree is $n+1$. From there, continuing this construction will still leave the limsup degree $n+1$, but will change the word from accepted to non-accepted, or vice-versa. In either case, the automaton fails to recognize the language.


Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem? Many theorems and "paradoxes" - Cantor's diagonalization, undecidability of hatling, undeciability of Kolmogorov complexity, Gödel Incompleteness, Chaitin Incompleteness, Russell's paradox, etc. - all have essentially the same proof by diagonalization (note that this is more specific than that they can all be proved by diagonalization; rather, it feels that all of these theorems really use the same diagonalization; for more details see, e.g. Yanofsky, or for a much more brief and less formalized account  my answer to this question).

In a comment on the above-mentioned question, Sasho Nikolov pointed out that most of those were special cases of Lawvere's Fixed Point Theorem. If they were all special cases, then this would be a good way to capture the above idea: there really would be one result with one proof (Lawvere's) from which all of the above followed as direct corollaries.

Now, for Gödel Incompleteness and undecidability of the halting problem and their friends, it is well-known that they follow from Lawvere's Fixed Point Theorem (see, e.g., here, here or Yanofsky). But I don't immediately see how to do that for the undecidability of Kolmogorov complexity, despite the fact that the underlying proof is somehow "the same." So:

  Is the undecidability of Kolmogorov complexity a quick corollary - requiring no additional diagonalization - of Lawvere's Fixed Point Theorem?

EDIT: Adding the caveat that Roger's fixed-point theorem may not be a special case of Lawvere's.

Here is a proof that may be "close"... It uses Roger's fixed-point theorem instead of Lawvere's theorem.  (See comment section below for further discussion.)

Let $K(x)$ be the Kolmogorov complexity of string $x$.

lemma.  $K$ is not computable.

Proof.

Suppose for contradiction that $K$ is computable.
Define $K'(x)$ to be the minimum encoding length of any Turing Machine $M$ with $L(M) = \{x\}$.
There exists a constant $c$ such that $|K(x) - K'(x)|\le c$ for all strings $x$.
Define function $f$ such that $f(\langle M \rangle) = \langle M' \rangle$ where $L(M') = \{x\}$ such that $x$ is the minimum string such that $K(x) > |\langle M\rangle| + c$.
Since $K$ is computable, so is $f$.
By Roger's fixed-point theorem, $f$ has a fixed point, that is, there exists a Turing Machine $M_0$ such that $L(M_0) = L(M_0')$ where $\langle M_0' \rangle = f(\langle M_0\rangle)$.
By the definition of $f$ in line 4, we have $L(M_0) = \{x\}$ such that $K(x) > |\langle M_0\rangle| + c$.
Lines 3 and 7 imply $K'(x) > |\langle M_0\rangle|$.
But by the definition of $K'$ in line 2, $K'(x) \le |\langle M_0 \rangle|$, contradicting line 8.


Techniques for proving NP completeness for a specific sequence of instances Most NP-completeness proofs I have seen pertain to proving that a problem on a class of instances is NP-complete. E.g., satisfiability is NP-complete on the class of instances with clauses having three literals. Usually these proofs exploit the room that the definition of the class allows to reduce every instance from a known NP-complete class to an instance in the class of interest.

The question I am interested in is somewhat nonstandard: suppose I have a sequence of instances $P_1,P_2,...$ with size of input $n_1,n_2,...$. The size  $n_k \rightarrow \infty$ as $k\rightarrow \infty$. I want to claim that this specific sequence of instances is NP-complete. I know the instances are in NP, only NP-hardness remains to be shown.

Here's the challenge. Because I have a specific instance for each $k$, I don't have adequate room in the definition to reduce the known broad classes to this class. Furthermore, the sizes of my instances are also fixed, which restricts me further. Conceptually, I think I will have to argue that for every instance in some NP-complete class, there exists a $k$ such that this instance reduces to $P_k$. But I am not aware of techniques that reduce known instances to instances of interest with such specificity.

So my question is: are there techniques for proving NP-completeness/NP-hardness type results for a specific sequence of instances?

In case it helps, the instances $P_k$ are 0-1 integer programming problems with specific constants; in fact the constraint matrix of $P_k$ contains that of $P_{k-1}$ as a submatrix for all $k$ and the number of variables $n_k = 2^k$. Notice also that the set of instances $P_k$ has cardinality of $\mathbb{N}$, which is also the cardinality of the number of SAT instances (or finite graphs, or integer programs etc); thus as far as I understand, there is nothing in principle preventing my sequence instances from being NP-complete.

If I understand the question correctly, I think that you are essentially asking whether a problem can be NP-hard even when it is defined on a sparse set of input strings.  If your notion of NP-hardness is under polynomial-time many-one reducibility, such a problem cannot exist (unless P=NP) because of Mahaney’s theorem.

See a blog article about Mahaney’s theorem by Lance Fortnow for a nice explanation of Mahaney’s theorem and related results.


How to state the adequacy of an encoding of lambda calculus in itself? In the paper Discriminating coded lambda terms - Henk Barendregt a coding $\ulcorner M \urcorner$ of a lambda term $M$ is a term such that $M$ (and its parts) can be reconstructed from it in a lambda-definable way. Essentially we need to be able to write a self-interpreter $\mathsf E$:

$$\mathsf E \ulcorner M \urcorner =_\beta M.$$

There are a variety of encodings like Kleene's which uses natural numbers and the most efficient modern encoding is a higher-order syntax by Mogensen. Another possible (trivial) encoding is the identity function, then the interpreter is again the identity function.

  Is there any reasonable notion of an "adequate encoding" that outlaws trivial encodings?

This question came up when considering the halting problem applied to lambda calculus rather than Turing machines: If stated in terms of the trivial encoding then it holds for the trivial reason that there is essentially nothing we can do with a quoted lambda term.

Put differently: What is the set of functions that we should expect to be able to compute on quoted lambda terms?

I can list a few like: counting the depth of the term, taking subterms, telling if the root node of a term is a lambda or application, ... but I would hesitate to define an "adequate encoding" by just listing assorted functions that came to mind.

As pointed out by others, the obvious definition of an "adequate" coding is that it is equitranslatable with any standard one.  The question is therefore to characterize such codings in terms of more elementary properties.

(Historical note.  Smullyan studied this question in the context of combinatory logic.  When I was a student, Henk Barendregt suggested Smullyan's conjectures to me as a research problem -- which led to my first scientific publication.)  See

http://drops.dagstuhl.de/opus/volltexte/2011/3249/
$\newcommand{\code}[1]{\overline{#1}}$

To summarize, given a map $\code{\cdot} : \Lambda \to \Lambda$, we consider whether there exist combinators satisfying certain properties.  The most significant ones are:

$A\, \code{M}\, \code{N} = \code{MN}$
$B\, \code{M} = \code{\code{M}}$
$P_i\, \code{M_0 M_1} = \code{M_i},\quad i \in \{0,1\}$
$Z_b\, \code{M} = \begin{cases} \lambda x y.x &M \equiv b \in \{I,K,S\}\\
\lambda xy.y &otherwise
\end{cases}$
$\Delta\, \code{M}\, \code{N} = \begin{cases}
\lambda x y. x &M \equiv N\\
\lambda x y.y &otherwise
\end{cases}$
$U\, \code{M} = \code{M}^s$, where $\code{\cdot}^s$ is some standard coding
$U^{-1}\, \code{M}^s = \code{M}$

It is easy to see that any adequate coding has these properties.  The main result of the paper (Corollary 14) is that, for an adequate coding, one of the following suffices:

$A + \Delta$;
$U^{-1} + \Delta$;
$U^{-1} + P_i + Z_b$;
$P_i + Z_b + $ "the range of $\code{\cdot}$ is contained in a recursively enumerable set and there is a combinator that decides whether a given element of this set is in the range or not".


Is the problem of finding the chromatic number of a modified interval graph NP-Complete Few days ago I was working on interval graphs to solve the known problem of resource allocation, as we know there is a greedy approach that solves this problem (chromatic number) in polynomial time and gives us the colors of each vertex in the interval graph (the problem of finding the chromatic number in general graphs is NP-Complete (3-satisfiability reduction by Karp)).

  I was wondering: if had a graph that is not an interval graph but it is because it has one and only one chordless cycle of length > 3 (there is an edge that, when you remove it, the graph becomes an interval graph), does it makes the problem of finding the chromatic number on this kind of graph NP-Complete?

I believe these graphs can be colored in polynomial time. Moron has already provided a reference, but here's an explicit algorithm.

Suppose that $G-uv$ is an interval graph, for edge $uv$, and form an interval representation for it. We can assume without loss of generality that no two intervals have the same endpoint. We can also assume without loss of generality that $u$ and $v$ are the two extreme intervals; for, if some other interval were extreme, we could remove it, optimally color the resulting smaller graph (also of the form interval+one edge), and then optimally extend the coloring to the removed vertex (because its neighborhood is a clique).

So the remaining question is: does $G-uv$ have an optimal coloring in which $u$ and $v$ have different colors, or does edge $uv$ require us to use one more color? But this is easily solved by a dynamic program on the subintervals of the interval representation.

In more detail, for subinterval $i$ let $C[i]$ denote the set of intervals (vertices of G) that cover that subinterval, let $D[i]$ be a Boolean value, true if there exists a coloring of the subinterval (in an optimal coloring of $G-uv$) that does not use the same color as $u$, and let $E[i]$ be the set of vertices that can be colored with the same color as $u$ (again, in an optimal coloring). As a base case, $C[0]=E[0]=\{u\}$ and $D[0]$ is false. When going from subinterval $i$ to subinterval $i+1$, across the right endpoint of an interval $w$, we set $D$ to be the disjunction of its old value and the predicate $w\in E[i]$, and we then remove $w$ from $C[i]$ and $E[i]$. When going across the left endpoint of an interval $w$, we add $w$ to $C[i]$, we add it to $E[i]$ if $D$ is true, and we change $D$ from true to false if the new size of $C[i]$ equals the number of colors in an optimal coloring of $G-uv$.

Then, the optimal number of colors of $G$ is the same as for $G-uv$ iff either D is true for the final subinterval, or E[i] has more than one member in the final subinterval. Otherwise, the optimal number of colors for $G$ is one plus the optimal number of colors for $G-uv$.


Purely Functional Equivalent of B-Tree? I am exploring the idea of writing a DBMS in purely functional way. The traditional data structure used for indexing is B-Tree. I'd like to know some purely functional equivalent of B-Tree that would be optimized to minimize disk access. Thanks.

I know more about purely-functional data structures than external-memory data structures, but I'll give this a go.

A B-tree can be written in a purely-functional way by path copying. The path will be short ($O(\log_B n)$), but copying each block takes $O(B)$ writes in $O(1)$ blocks.

If you're willing to let the structure be just fully persistent, rather than purely functional, I think you can reduce the number of writes in a node copy to $O(\lg w)$ expected amortized, where $w$ is the word width, using the fully persistent arrays in "Confluently Persistent Tries for Efficient Version Control"

You might want to watch this presentation about RethinkDB, which uses purely-functional data structures because of the cost of writes in SSDs.


Deterministic Realtime Languages Book and Greibach (V. Book, Ronald & A. Greibach, Sheila. (1970). Quasi-realtime languages. Theory of Computing Systems. 4. 97-111. 10.1007/BF01705890.) prove that non-deterministic linear time Turing machines are equivalent to quasi-real-time such machines.

The authors say: " For deterministic machines, linear time is strictly more powerful than real-time; here we show that for nondeterministic machines linear time and real-time have the same power. "
However, they do not cite or prove the claim that linear time deterministic machines are more expressive than realtime deterministic such machines.

In a 1967 pager, Al Rosenberg gave the example of a language which is deterministic linear time but not deterministic quasi-realtime that Book & Greibach probably refer to.
Rosenberg mentions that such examples were published previously by himself and Cole.


Theoretical explanations for practical success of SAT solvers? What theoretical explanations are there for the practical success of SAT solvers, and can someone give a "wikipedia-style" overview and explanation tying them all together?

By analogy, the smoothed analysis (arXiv version))for the simplex algorithm does a great job explaining why it works so well in practice, despite the fact that it takes exponential time in the worst case and is NP-mighty (arXiv version).

I have heard a little bit about things like backdoors, structure of the clause graph, and phase transitions, but (1) I don't see how these all fit together to give the larger picture (if they do), and (2) I don't know whether these really explain why SAT solvers work so well, for example, on industrial instances. Also, when it comes to things like structure of the clause graph: why is it that current solvers are able to take advantage of certain clause graph structures?

I only find the results about phase transitions partially satisfying in this regard, at least in my currently limited understanding. The phase transition literature is about instances of random k-SAT, but does that really explain anything about real-world instances? I don't expect real-world instances of SAT to look like random instances; should I? Is there a reason to think phase transitions tell us something, even intuitively, about real-world instances even if they don't look like random instances?

Related questions that help, but don't completely answer my question, particularly the request for tying things together into a coherent picture:

Why is there an enormous difference between SAT solvers?
Which SAT problems are easy?
What's the correlation between treewidth and instance hardness from random 3SAT?

I am assuming that you are referring to CDCL SAT solvers on benchmark data sets
like those used in the SAT Competition.
These programs are based on many heuristics and lots of optimization.
There were some very good introductions to how they work at
Theoretical Foundations of Applied SAT Solving workshop at Banff in 2014
(videos).

These algorithms are based on DPLL backtracking algorithm which
tries to find a satisfying assignment by setting values to variables
and backtracks when it finds a conflict.
People have looked at how much impact these heuristics have. E.g. see

Hadi Katebi, Karem A. Sakallah, and Joao P. Marques-Silva, "Empirical Study of the Anatomy of Modern Sat Solvers", 2011

It seems that the efficiency of these SAT solvers on the benchmarks comes mainly from two two heuristics (and their variants):

VSIDS heuristic fir selecting which variable to branch on next.
CDCL: conflict-driven clause learning heuristic which learns a new clause from a conflict.

It is well-known that DPLL proofs correspond to proofs in resolution.
Without CDCL the only resolution proofs we can get are tree resolution proofs
which are much weaker than general resolution proofs.

There are results that show with CDCL we can get any general resolution proof.
However there are caveats, they need many artificial restarts, artificial branching, and/or particular preprocessing,
so it is not clear how close these are to what these programs do in practice.
See e.g. the following paper for more details:

Paul Beame and Ashish Sabharwal, "Non-Restarting SAT Solvers With Simple Preprocessing Can Efficiently Simulate Resolution", 2014

CDCL is essentially cutting branches from search space.
There are various ways of deriving a new learnt clause from a conflict.
Ideally we would add a set of minimal clauses which implied the conflict,
but in practice that can be large and can be expensive to compute.
Top SAT solvers often delete learned clauses regularly and
that helps in practice.

The other heuristic VSIDS essentially maintains a score for each variable.
Every time there is a conflict,
all scores are adjusted by multiplying them with a value $\alpha$<1 and
adding a constant to those which were "involved" in the conflict.
To see what this means think about the sequence $F(v,i)$ which is 1
if variable v was "involved" in the $i$th conflict.
Let $0<\alpha<1$ be a fixed constant.
The score of variable $v$ at time $n$ is then:
$$\sum_{i<n} F(v,i)\alpha^{(n-i)}$$

Intuitively one can say that this tries to emphasize variables which were
consistently involved in recent conflicts.
You can also think of it as a simplistic but extremely cheap way
of predicting which variables will be involved in the next conflict.
So VSIDS branches first on those variables.
One can claim that the algorithm is essentially a fail-fast algorithm,
find conflicts fast.
Fast is related to smaller number of variables set,
which means blocking large subtrees of the search tree.
But this is mostly intuition,
afaik no one has formalized it very careful to test it on SAT data sets.
Running a SAT solver on one of these data sets is not cheap,
let alone comparing it with the optimal decisions
(smallest extension of the current assignment to variables which would violate one of the clauses).
VSIDS also depends on which variables we bump as each conflict,
there are various ways to define when a variable is involved in a conflict.

There are results that show particular implementation of these ideas
correspond to a time-weighted centrality of vertices in dynamic graphs.

There are also suggestions that excluding adversarial instances like those based on NP-hard problems and crypto primitives and random instances
(which CDCL SAT solvers are not good at)
the rest of instances come from very well structured things
like software and hardware verification and
somehow these structures are exploited by CDCL SAT solvers
(lots of ideas have been mentioned like backdoors, frozen variables, etc.)
but afaik they are mostly ideas and
do not strong theoretical or experimental evidence to back them up.
I think one would have to fist rigorously define the properly and
show that the instances on which these algorithms work well
have the property and
then show that these algorithms exploit those properties.
What happens in practice is that people are mostly interested in
faster algorithms and if someone comes up with an algorithms
that is somehow got inspired by one of these ideas and
that algorithms beats other algorithms they go with the claim.

Some people keep insisting that the clause ratio and
thresholds are the only game in the town.
That is definitely false as anyone who is slightly familiar with
how industrial SAT solvers work or
has any knowledge of proof complexity would know.
There are lots of things that make a SAT solver work well or not
on an instance in practice and the clause ratio is just one of the things
that might be involved.
I think the following survey is a good starting point to
learn about the connections between proof complexity
and SAT solvers and perspective:

Jakob Nordstrom, "On the Interplay Between Proof Complexity and SAT Solving", 2015

Interestingly even the threshold phenomenon
is more complicated than most people think,
Moshe Vardi stated in his talk
"Phase transitions and computational complexity"
that the median running time of GRASP remains exponential
for random 3SAT formulas after the threshold
but that the exponent decreases
(afaik, it is not clear how fast it decreases).

Why are we studying SAT solvers (as complexity theorists)? I think the answer is the same as for other algorithms: 1. compare them, 2. find their limitations, 3. design better ones, 4. answer fundamental questions of complexity theory.

When modelling a heuristic we often replace heuristic with nondeterminism. The question then becomes is it a "fair" replacement? And here by fair I mean how close is the model in helping us answer the question above.

When we model a SAT solver as a proof system we are partly showing it limitation because the algorithm will be inefficient for statements which have lower bounds in the proof system. But there still is a gap between what the algorithm actually finds and the optimal proof in the proof system. So we need to show that the reverse as well, i.e. the algorithm can find proofs that are as good as those in the proof system. We are not close to answer that question, but the amount of heuristic that is replace by non-determinism defines how close the model is to the proof system. I don't expect that we completely drop the replacement of heuristics with nondeterminism, otherwise we would get automatizability results which have consequences on open problems in crypto, etc. But the more nondeterminism the model has the less convincing it is in explaining the behaviour of the SAT solver.

So the question when looking at a model becomes: how much does the models help explain why SAT solver A is better than SAT solver B? How helpful are they in developing better SAT solvers? Does SAT solver find proofs in practice that are close to optimal proofs in the model? ... We also need to model the practical instances.

Regarding the intuition that CDCL SAT solvers "exploits the structure of practical instances" (whatever that structure is) is generally accepted intuition I think. The real question is to give a convincing explanation of what that means and demonstrate that it is indeed true.

See also Jakob Nordstrom's own answer for more recent developments.


Kth best problem that is NP-hard for K polynomial A Kth best problem is, given some constraint, to find a solution that has the Kth best value compared to all solutions that meet the constraint. One way to write this as a decision problem is to decide whether there are K solutions that achieve a given value.

Garey and Johnson list several NP-hard Kth best problems: Kth Best Spanning Tree, Kth Shortest Path, Kth Largest Subset, and Kth Largest m-Tuple. However each of these problems can be solve in polynomial time if K is restricted to be polynomial in the size of the rest of the input.

Is there a Kth best problem that is NP-hard even if K is restricted to be polynomial in the size of the rest of the input (but poly-time solvable for K=1)? The problem should be natural enough that other Kth best problems can reduce to it, or at least be a good example for how to show NP-hardness of a Kth best problem.

Here is an example of something fairly contrived, but which might be a good starting place for reductions to other problems:

Input:  a boolean formula $\phi$ and a satisfying assignment $x$.
Goal:  find a satisfying assignment $y$ to $\phi$ which has as few variables set to true as possible, but at least as many variables set to true as in $x$

This (well, its decision variant) is obviously in $\mathsf{P}$ ($x$ is itself a solution), but finding the next-best assignment (forcing $y \ne x$) is $\mathsf{NP}$-hard: you can force all satisfying assignments to an arbitrary formula to have a superfluous 1, and then plant the all-zeros assignment. You can also fairly easily plant as many (polynomially many, possibly more if you're clever) assignments as you want.


Finding the closest point to a sets of discrete points In a paper I am reviewing, the authors define the following problem and construct an algorithm. They give no further references and I suspect it has appeared somewhere in the literature before.

Let $P_1,\ldots,P_n$ be sets of points in a space with a metric $d$. Define the distance to a set as
    $$\operatorname{dist}(x, P_i) = \min\{ d(x,p) \,|\, x \in P_i\}.$$
The problem is to compute
    $$\min_x \sum_{i=1}^n \operatorname{dist}(x, P_i).$$
What is the name of this problem? Has it been discussed in the literature? What if $d(x,P_i) = ||x - P_i||_2?$

It is called p-Median and is known to be NP-hard.
Refer to the following paper for more info:

  O. Kariv and S. Hakimi, “An Algorithmic Approach to Network Location
  Problems. II: The p-MEDIANS,” SIAM Journal on Applied Mathematics,
  vol. 37, no. 3, pp. 539–560, December 1979.


Advantages and specific applications of massively parallel programming thesis idea I'm nearly graduated in computer science engineering and my thesis should discuss the massively parallel computational model of CUDA and its advantages/applications.

I'm searching for an application field (an idea) to show off some of CUDA capabilities and (definitely) also my skills as programmer and engineer.

I'm up for a bit of challenge to integrate an interesting work into my thesis project and discussion so I'm asking for advices or ideas

Build a "CUDA-SAT solver" and outperform the winners of the annual Sat competitions ! :-)

Edit: I posted the answer quickly ... but - after a Google search - I found that my idea is not so original, see: NVIDIA CUDA Architecture-based Parallel Incomplete SAT Solver ... however I think that a public available project/source code of a CUDA-powered SAT solver that can be compiled and used on a standard PC (Linux and/or Win) equipped with a CUDA GPU graphics card would be very appreciated.

As a second best, I suggest you to try to implement a parallel genetic algorithm and pick one (or more) of the many possible applications to show the performance gains due to the parallelization.


Cleaning images in order to perform feature detection I have a set of images (e.g. cars) and trying to perform feature detection using SIFT (actually, SIFT modification - A-SIFT, which is more robust to affine transformations) and I'm getting an extremely low results in matching even on the same models, same color and closely same view point.
I'm barely sure, that the problem is car's surface is glossy (that's leads to huge variation of reflections on surface) and shadows & lighting (that's depends on location where photo was taken). Is there's image processing algorithms that can help me clean up images and/or decrease influence of that factors?
I had a quick look at CiteSeerX and Google Scholar but found nothing.

A common preprocessing tactic is to smooth the image prior to feature extraction using for instance a Gaussian kernel or a low pass filter. This allows for the high frequency spurious details to be removed.


Probability for an element to appear in at least one set Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct.

What is the probability that $j$ ($j=1,...,M$) elements appear at least once in the (union of the) sets?

We know that for $j = N$ the probability is $1$. For $j > N$ I wanted to use the binomial distribution, but the parameter $p$ should be conditioned somehow on the number of elements that already appear in the sets. Should I use some recursive formula for this?

Edit:

(1) This maybe also be formulated as the famous balls in bins problem, with the twist that the balls are thrown $N$ at a time to $M$ bins, where it is known that each group of $N$ balls falls into distinct $N$ bins.

(2) Another option to see this is as the (extended) Coupon Collector's Problem, who acquires $N$ (instead of $1$) distinct coupons at a time, from a set of $M$ distinct coupons. Denoting by $W_t(j)$ the probability that he acquired $j$ distinct coupons at time $t$, my questions is what is the probability distribution of $W_t(j)$, for $j=N,N+1,...,M$, for each time (or set in the original formulation) $t=1,2,...,k$. I saw something relevant here:
https://math.stackexchange.com/questions/100175/probability-of-non-empty-bins-after-randomly-inserting-balls-by-pairs

For very crude bounds, you could use Chebyshev's inequality.

Let $x$ denote one (fixed) value from the set of $M$ possibilities.  The probability that $x$ appears at least once in the union of the sets is something like

$$p = 1 - \left({{M-1 \choose N} \over {M \choose N}}\right)^k.$$

Now if we let the random variable $X$ denote the number of elements that appear at least once in the union of the sets, we can use linearity of expectation to get that $\mathbb{E}[X] = Mp$.  You should be able to compute $\text{Var}[X]$ using similar methods.  Then, you should be able to use Chebyshev's inequality to bound the probability that $X$ is far away from its expected value.

This will give a pretty weak bound, so it's unlikely that this is the best approach.  Hopefully others will suggest better methods.


What are Zhang's molecules? I'm currently looking into the representation theory of Scott domains. In his paper "dI-Domains as prime information systems" (1992), Guo-Qiang Zhang uses prime information systems to represent dI-domains. A prime information system is an information system where additionally we have linearity and finiteness of entailment, in the following sense:

$X \vdash b$ implies $\{a\} \vdash b$, for some $a \in X$, and
the deductive closures $\overline{X} = \{b \mid X \vdash b\}$ are finite.

If $A$ is a (prime) information system, write $Pt(A)$ for the points (also "elements", "ideals") of $A$, that is, for the usual consistent and deductively closed (possibly infinite) sets of tokens in $A$; for the finite ones write $Pt_f(A)$. Then, a stable approximable mapping between two prime information systems with carriers $A$ and $B$, according to Zhang, is a relation $r \subseteq Pt_f(A) \times B$, such that

if $(a_i,p_i) \in r$, for $i = 1, \ldots, m$ and $\bigcup_i a_i \in Con_A$, then $\{p_1, \ldots, p_m\} \in Con_B$,
if $a \cup b \in Pt_f(A)$, and $(a, p) \in r$, $(b, p) \in r$, then $a=b$, and
if $(a, p) \in r$ and $\{p\} \vdash_B q$, then $(b, q) \in r$, for some $b \subseteq a$.

Now in Definition 5.4 he writes:

  Let $A = (A, Con_A, \vdash_A)$ and $B = (B, Con_B, \vdash_B)$ be prime information systems. A molecule $m$ is a finite stable approximable mapping, such that for some $(a , p) \in m$, $b \subseteq a$ and $\{p\} \vdash q$, for any other $(b , q)$ in $m$.

He then uses molecules as tokens of an appropriate function space and goes on to show cartesian closure of the category of prime information systems with stable approximable mappings. My problem is that my intuition is too low to allow me to even parse the definition.

My questions: What is the defining formula of a molecule, and in particular, how are these $b$'s quantified? What would be your intuition of a molecule?

Restating the definition to make the quantifiers easier to understand:

  A molecule is a finite stable approximable mapping, such that there exists a largest pair $(a,p) \in m$, such that for all other pairs $(b,q) \in m$ we have $b \subseteq a$ and $\{p\} \vdash q$.

In other words, a molecule is a mapping that closes off neatly, having a largest pair.


Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof? Good Evening!

I am aware that the minimum (cardinality) vertex cover problem on cubic graphs ($3$-regular) graphs is $NP$-hard.  Say positive integer $k>2$ is fixed. Has there been any computational complexity proof (aside from the $3$-regular result, note this would be $k=3$,) that shows the minimum (cardinality) vertex cover problem on $k$-regular graphs is $NP$-hard (e.g., $4$-regular)?  Since $k$ is fixed, you aren't guaranteed the cubic graph instances needed to show the classic result I mentioned above.

Note that this problem would be straightforward to see is $NP$-hard from the result I mentioned at the start if we were to state that this were for any regular graph (since $3$-regular is a special case), we don't get that when $k$ is fixed.

Does anybody know of any papers that address the computational complexity of minimum (cardinality) vertex cover on a $k$-regular graph, when $k$ is fixed/constant?  I have been having difficulties trying to find papers that address this (in the slew of documents that cover the classic result of minimum (cardinality) vertex cover on cubic graphs being $NP$-hard.)

Thank you so much!

EDIT (again): @R B gave a construction below!

By adding a small ($O(k)$) sized graph to each vertex you could reduce $VC$ of size $m$ in a 3-regular graph $G$ to $VC$ of size $m+2k|V|$ in a $k-regular$ graph.

Here is a reduction for 5-regular graphs, and I believe you can easily generalize it for every $(2k+1)$-regular graphs, for every integer $k$, and perhaps some trickery would allow similar construction for $2k$-regular graphs;

Consider the graph $H$ in the photo:

(all vertices has degree 5, except for the blue vertex).

For every vertex $v$ in the 3-regular graph $G$, create two copies of $H$ and connect $v$ to their blue vertices.

It is easy to see that regardless of whether $v$ was selected for the cover, you have to include at least $5$ vertices from $H_v$ in the cover (you can take the blue and green ones).

Hence every vertex cover of size $m$ in $G$ corresponds to a $m+10|V|$ sized cover in the new 5-regular graph, and vice versa.

EDIT:

Similar trick could be applied to get $2k$-regular graphs as well. Consider for example the following reduction from 3-regular to 4-regular graphs;

Partition the graph vertices into pairs (duplicate the graph if the number of vertices is odd), and for every pair $u,v$ connect each to a blue vertex in the following structure:

For example, if your initial cubic graph is:

Then the resulting $4$-regular graph is:

And the 5-regular graph would be:


Arguments for/against Kolmogorov's conjecture about the circuit complexity of P According to (unverified) historical account, Kolmogorov thought that every language in $\mathsf{P}$ has linear circuit complexity. (See the earlier question Kolmogorov's conjecture that $P$ has linear-size circuits.) Note that it implies $\mathsf{P}\neq \mathsf{NP}$.

Kolmogorov's  conjecture, however, is viewed likely to fail. For example, Ryan Williams writes in a recent paper: "The conjecture would be surprising, if true. For languages in $\mathsf{P}$ requiring $n^{100^{100}}$
time, it appears unlikely that the complexity of such problems would magically
shrink to $O(n)$ size, merely because a different circuit can be designed for each
input length."

On the other hand, Andrey Kolmogorov (1903-1987) is widely recognized as one of the leading mathematicians of the 20th century. It is rather hard to imagine that he would have proposed a completely absurd conjecture. Therefore, to understand it better, I tried to find some arguments that might actually support his surprising guess. Here is what I could think up:

Assume $\mathsf{P}\not\subseteq \mathsf{SIZE}(lin)$. Then we can pick a language $L\in \mathsf{P}$, such that $L$ has superlinear complexity both in the uniform and in the non-uniform model. There are then two possibilities:

There is a known  explicit algorithm (Turing machine) that accepts $L$. From this we can construct an explicit function family that must have superlinear circuit complexity. However, this may be viewed  unlikely, since no one has been able to find such an example in more than 60 years of intense research on circuits.
There is no known explicit algorithm for $L$. For example, its existence is proved via non-constructive means, such as the Axiom of Choice. Or, even if the explicit algorithm exists, no one has been able to find it. Given, however, that there are infinitely many languages that can play the role of $L$, it is unlikely again that they all behave in this unfriendly way.

But then, if we dismiss both options as unlikely, the only remaining possibility is that such an $L$ does not exist. That means  $\mathsf{P}\subseteq \mathsf{SIZE}(lin)$, which is precisely Kolmogorov's conjecture.

  Question: Can you think of any further argument for/against Kolmogorov's conjecture?

The footnote of my paper that you cite refers to a heuristic "argument" as well, at least, what we think was Kolmogorov's intuition -- the positive resolution of Hilbert's thirteenth problem.

http://en.wikipedia.org/wiki/Hilbert's_thirteenth_problem

In particular, it was proved by Kolmogorov and Arnold that any continuous function on $n$ variables can be expressed as a composition of $O(n^2)$ "simple" functions: addition of two variables, and continuous functions on one variable. Hence, over the "basis" of one-variable continuous functions and two-variable addition, every continuous function on $n$ variables has "circuit complexity" $O(n^2)$.

It seems Kolmogorov believed there is a discrete analog, where "continuous in $n$ variables" becomes "Boolean in $n$ variables and poly$(n)$-time computable", and where the "basis" given above becomes two-variable Boolean functions.


Max network flow with arbitrary source / sink I'm wondering: given a fixed graph G, if we're to calculate the max flow between the vertices s and t, how different is the problem to calculate the max flow between the vertices s' and t, or similarly, s and t' (on the same graph)?

I've just started reading a paper by Altner and Ergun -- Rapidly Solving an Online Sequence of Maximum Flow Problems -- where they discuss a method to efficiently recalculate the max flow of a graph given small pertubations in the topology of that graph (for example, deleting or adding an edge). They do this by using the results from the previous max flow as a 'warm start' to calculating the new max flow.

I'm wondering if there is a similar story for recalculating the max flow given a change in source or sink? That is, is it possible to 'warm start' a max flow problem when a different source or sink is chosen?

Any pointers at all would be most welcome :)

Finding max flow from arbitrary source/sink can be reduced to finding max flow under insertion/deletion of edges.

We modify the graph by adding two vertices $s^*$ and $t^*$ not connected to any vertex. We maintain the data structure to compute max flow from $s^*$ to $t^*$ under insertion/deletion of edges. Now, whenever we want to calculate max flow from any source $s'$ to any sink $t'$, we simply add edges $(s^*,s')$ and $(t',t^*)$ with infinite capacity. The max flow from $s^*$ to $t^*$ would then essentially be the max flow from $s'$ to $t'$.

In case you want to change the source and sink to $s''$ and $t''$ respectively, simply delete $(s^*,s')$ and $(t',t^*)$ and add $(s^*,s'')$ and $(t'',t^*)$. The max flow from $s^*$ to $t^*$ would now represent the max flow from $s''$ to $t''$.

This technique was earlier used to show the equivalence of All Pair Shortest Path and Single Source Shortest Path in the dynamic environment.
Similarly, it can also show equivalence of All Pair Reachability and Single Source Reachability in the dynamic environment.


Caterpillar decomposition of trees Can any tree on $n$ nodes be decomposed into a set of $O(\log n)$ caterpillars? If not, what is the maximum number of caterpillars required? Are there efficient algorithms for finding the decomposition?

Any papers on this topic will be highly appreciated.

It seems this is false in general. Take the tree with a central node $x$, connected to a bunch of nodes $y_1,\dots,y_n$. Each node $y_i$ is additionally connected to a node $z_i$.

The total number of nodes is $N=2n+1$.

Any caterpillar in this tree can contain at most two $z$ nodes, and therefore, $n/2$ caterpillars are needed to cover it. So it is impossible to cover it with $O(log N)$ caterpillars.


Voronoi Diagram of Lines Let $S$ be a set of lines (or line segments) in $\mathbb{R}^3$. Consider the Voronoi diagram $VD(S)$. The best lower bound on the complexity of $VD(S)$ is $\Omega(n^2)$ and the best upper bound is $O(n^{3+\epsilon})$ [1]. What is the current state of research on this problem? Is anything more recent than the references in [2] known?

[1] Almost tight upper bounds for lower envelopes in higher dimensions.

[2] http://cs.smith.edu/~orourke/TOPP/P3.html

In 2010 Hemmer et al. gave an exact algorithm for the Voronoi diagram of lines in $\mathbb{R}^3$. In their introduction, they state that the $\Omega(n^2)$ lower bound and $O(n^{3+\varepsilon})$ upper bound are still the best known on the combinatorial complexity of the resulting Voronoi diagram. Their algorithm runs in time $O(n^{3+\varepsilon})$, matching the upper bound on the combinatorial complexity.

As far as I know, theirs was the first (and still, only) exact algorithm for this problem, so I would guess that there haven't been any further improvements on the combinatorial complexity front either.


Voronoi diagram on surface of polyhedron Does anyone know of work on computing the Voronoi diagram of a set of points on a polyhedron, where distance is measured by shortest paths on the surface?
I am particularly interested in convex polyhedra.  I have a vague memory that this has been explored, but my memory is too vague to locate any papers.  Thanks for pointers!

You can just use MMP k times, if you have k sites. For every face, you have to compute the additive weighted Voronoi diagram, and the overlay of k such diagrams still have linear complexity (because, it is just a planar additive weighted Voronoi idagram). As such, for a polytope with n faces and k sites, this takes $O(n^2 k \log n)$ time. You can use the latest monstrorisity by Sharir and Schriber and do it in $O(nk log n)$ time - but is not clear how to overlay the diagrams on every face. It is probably a good idea to look at their paper and see if they do something for this case.

As far as approximation, it is not hard to show that one can build a space decomposition of complexity $O(k/\epsilon^{O(1)} )$ such that given a query point, one can report the approximate nearest-neighbor on the polytope in $O( \log (k/\epsilon) )$ time. I think using some newer machinery, one can in fact also return the approximate distance in this time.


Packing problems with repetitions In packing problems, we need to select a set of sets of items, such that no item is chosen twice (in $Set-Packing$, the actual items must not be packed twice, in $Graph-Packing$ the copies of the graph has to be vertex disjoint, in multidimensional matching every item has to appear once, etc.).

Are there any studied problems that ask for packing such that every item is packed at most $p$ times?

For example, is there any known reference for (perhaps under a different name?)-

$repetition-Set-Packing$:

given a universe $\mathcal{U}=\{e_1,..,e_n\}$, two numbers $k,r\in \mathbb{N}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k$ such that every item in $\mathcal{U}$ appears in at most $r$ sets in $S'$?

Are there any other works on packing with limitied repetitions?

Yes, people do consider these problems but there is no standard name. A useful way to think about these problems is via packing integer programs. Consider the problem $\max wx$ such that $Ax \le b, x \in {0,1}^n$ where $A$ is a $m \times n$ non-negative matrix. The width of the program is $\min_{i,j} b_i/A_{i,j}$ (which we can assume is at least $1$). If $A$ is a $0,1$ matrix and $b$ is an integer vector then this captures packing problems where one allows repetitions up to $\min_i b_i$. Packing problems become easier as width increases. For Set Packing one can get an approximation of the form $d^{1/W}$ where $W$ is the width and $d$ is the maximum set size and this is more or less tight from hardness of maximum independent set. In particular when $W = \Omega(\log d)$ one gets a constant factor approximation.


Is there a complexity theory analogue of Rice's theorem in computability theory? Rice's theorem states that every nontrivial property of the set recognized by some Turing machine is undecidable.

I am looking for complexity-theoretic Rice-type theorem that tells us which nontrivial properties of NP sets are intractable.

Proving such a complexity theoretic version of Rice's Theorem was a motivation for me to study program obfuscation.

Rice's theorem says in essence, that it is hard to understand the functions that programs compute, given the program.  However, the reason these problems are undecideable is that they are infinitary.  Even on one input, a program may never halt, and we need to consider what
the program does on infinitely many inputs.

A finitary version of Rice's theorem would fix the input size and running time of a program,
and say that the program is hard to understand.  Once you've fixed these, you might as well
view the program as a Boolean circuit.  What properties of the function computed by a Boolean circuit are hard to compute?  One example is ``not always 0'', which is the NP-complete
Satisfiability problems.    But unlike Rice's Theorem, there are some properties that are
non-trivial but easy, even without understanding the circuit.  We can always know that:
the function computed by a circuit has a bounded circuit complexity (the size of the circuit).  Also, we can always evaluate the circuit on inputs of our choice.

So say a property of $f_C$ is easy with Black-box access if it can be compute,d
in probabilistic polynomial time by an algorithm that gets as input $n$, a bound on $|C|$ and oracle access to $f_C$.  For example, satisfiability is not easy with black-box access, because we could imagine a circuit of size $n$ that only produces answer 1 on a
randomly chosen input $x$.  No black box algorithm could distinguish such a circuit from one that always returned 0, since the probability of querying the oracle on $x$ is exponentially small.  On the other hand, the property $f(0..0)=1$ is black-box easy.
The question is:  are there any properties of $f_C$ that are decideable in probabilistic polynomial-time that are not easy with Black-box access?

While this question is open as far as I know, our intended approach was ruled out.  We had
hoped to prove this by showing that cryptographically secure program obfuscation was possible.  However, Boaz proved the opposite: that it was impossible.  This implicitly shows that black-box access to circuits is more limited than full access to the circuit description, but the proof is non-constructive, so I can't name any property as above
that is easy given the circuit description but not with black-box access.  It is interesting (at least to me) if such a property could be reverse engineered from  our paper.

Here is the reference:Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (Im)possibility of Obfuscating Programs. CRYPTO 2001:1-18


Can true randomness (provably) be replaced with Kolmogorov randomness for RP? Have there been any attempts to show that Kolmogorov randomness would be sufficient for RP? Would the probability used in the statement "If the correct answer is YES, then it (the probabilistic Turing machine) returns YES with probability ..." be always well defined in that case? Or would there only be upper and lower bounds for that probability? Or would there only always be some probabilistic Turing machine, for which the probabilities would be well defined (or at least the lower bound which should be bigger than 1/2)?

The class RP here is relatively arbitrary, and one could also ask this question for weaker notions of (pseudo-)randomness than Kolmogorov randomness. But Kolmogorov randomness seems to be a good starting point.

Making sense of the word "probability" would be part of an attempt to show that Kolmogorov randomness works for RP. However, let me try to describe one possible approach, to clarify what it could mean, and why I talked about upper and lower bounds:

Let $s$ be a (Kolmogorov random) string. Let $A$ be a the given probabilistic Turing machine corresponding to a language from RP. Run $A$ with $s$ as source for random bits $n$ times, continuing to consume previously unconsumed bits from $s$ one after the other.

For $p_n^s:=\frac{\text{#YES result in first $n$ runs of $A$ on $s$}}{n}$, let $p_+^s:=\limsup_{n\to\infty}p_n^s$ and $p_-^s:=\liminf_{n\to\infty}p_n^s$. Observe that $p_+^s$ and $p_-^s$ are well defined for a given string $s$, even if it would not be random. But one may wonder whether $p_+^s=p_-^s$ in case $s$ is Kolmogorov random, or whether $p_-^{s_1}=p_-^{s_2}$ for two arbitrary Kolmogorov random strings $s_1$ and $s_2$. Or whether there exists a $p\geq 1/2$ such that $p\leq p_-^s$ for any Kolmogorov random string $s$.

I think the question being asked here is roughly "is there a sense in which we can replace the sequence of random bits in an algorithm with bits drawn deterministically from an appropriately long Kolmogorov random string?" This is at least the question I will attempt to answer! (The short answer is "Yes, but only if you amplify the error probability first")

Yes...

We can certainly say something here. Let $L$ be some language and let $A$ be an algorithm which takes as input $x$ and a random string $r\in U_{f(|x|)}$ (the uniform distribution over $\{0,1\}^{f(|x|)}$) s.t. $\Pr[A(x,r)=L(x)]>1-\epsilon(x)$. In other words, $A$ is an algorithm which errs with probability at most $\epsilon(\cdot)$.

Notice now that if $A$ gives the wrong answer on $(x,r)$ ie, $A(x,r)\not=L(x)$, this gives us some means of describing $r$, in particular, we can describe it as the $i$-th string which causes $A$ to err on $x.$ To do this, we simply make the machine which has hard-coded $x$, $A$, $i$, and a bit $b=1\iff x\in L$, and simply enumerates choices of $r'$ from $\{0,1\}^{f(|x|)}$ until it finds the $i$-th choice of $r'$ such that $A(x,r')\not= b$.

So now that we know we can leverage being a bad choice of random string into a description, let's observe some conditions which are sufficient for turning our description of $r$ into a compression. To describe $r$, we require enough bits to describe $x$, $i$, $b$, and then the code for our procedure (the code for $A$ and the routine we described), giving as a description of length $$|x|+|i|+O(1)=|x|+\log_2(2^{f(|x|)}\epsilon(x))+O(1)=|x|+f(|x|)-\log(1/\epsilon(x))+O(1).$$

Recall that $r$ is length $f(|x|)$, so this is a compression of $r$ if $$\log(1/\epsilon(x)) = |x|+\omega(1),$$ for example, when $\epsilon(x)=1/2^{2|x|}$.

Finally, observe that if $r$ were a Kolmogorov random string, then we could have no such compression, so as long as the error probability of $A$ is sufficiently small, a Kolmogorov random string in place of the sequence of random bits will cause $A$ to answer correctly!

Notice that the only thing we leverage about $A$ is that its error probability is small. We don't care if $A$ has an extremely long run time or if $A$ has one or two sided error.

Bringing this back to the question of $RP$ (or $coRP$ or $BPP$), this says that as long as we amplify the error probability of our algorithms, we can use Kolmogorov random strings in place of their random bits.

...But only if we amplify first.

A followup question may be "can I do this without amplifying the error probability?" Consider the following algorithm $A$ which decides $\{0,1\}^*$ and has error probability $1/2^n$.

On input $x$:

Generate a string $r\in\{0,1\}^n$
If $r=x$, reject.
Accept.

Notice that for every choice of $r$, there is some choice of $x$ such that $A$ errs on $x$, namely the choice of $r$ that is $x$, so we can not replace the random sequence of bits used by $A$ with a Kolmogorov random string without amplifying it's error probability!

A note about the source: I'm not sure if any of this is novel, but I included the first argument in my writeup for my qualifying exam which will eventually be available online after I finish revising it.


Do such instances always admit a 3D matching? I want to know whether the following kinds of special instances of the 3D Matching problem are ``yes" instances, i.e., admit a 3D matching.
We are given 3 sets $A,B,C$ containing $m$ elements each, and $n$ tuples $\{T_i\}_{i\in [n]}$ where $T_i \in A\times B\times C$. We further know:
(i) Each element of $A\cup B \cup C$ occurs exactly in two tuples. Simple counting shows $n = 2m$.
(ii) The elements of $A\cup B \cup C$ can be partitioned into $m$ singleton elements, and $m$ pairs $(x,y)$ where $\{x,y\} \subset T_i$ for some $i\in [n]$.
I want to know if such an instance admits a 3D matching. Is there a simple counter-example?


Trivial upper bound for distribution testing There is an obvious algorithm that tests any property of most discrete distributions. This algorithm works by learning the distribution. This is done by just learning the histogram for enough number of samples. In particular, I have the following analysis,
Let $p_x$ be the probability of item $x$ and $m_x$ be the number of occurrences of $x$ in $m$ samples. Then by Chernoff's bound, $Pr(|\frac{m_x}{m}-p_x|>\epsilon)<2.\exp(-2m\epsilon^2)$. Taking union bound over all $x$ in the sample space we can get $Pr(\sum_x|\frac{m_x}{m}-p_x|>\epsilon|\Omega|)<2|\Omega|\exp(-2m\epsilon^2)$. Scaling down $\epsilon$ by a factor of $|\Omega|$, we get $O(\ln |\Omega|\frac{|\Omega|^2}{\epsilon^2})$ samples are enough.

It seems there are folklore algorithm to do this in $O(\ln |\Omega|\frac{|\Omega|}{\epsilon^2})$ as well as in $O(\frac{|\Omega|}{\epsilon^2})$ samples. But I am unable to prove it. A similar question was asked here: Are there distribution properties which are "maximally" hard to test?

You might find this short note helpful ($\LaTeX$ code available [1]
 if the binary link breaks). I am reproducing the relevant part below:

  Theorem. (Folklore)  Learning an unknown distribution over a known domain of size $n$, up to total variation $\varepsilon\in(0,1]$, and with error probability $\delta\in(0,1]$, has sample complexity $O\!\left(\frac{n+\log(1/\delta)}{\varepsilon^2}\right)$. (Moreover, this can be done efficiently.)

Proof. Consider the empirical distribution $\tilde{p}$ obtained by drawing $m$ independent samples $s_1,\dots,s_m$ from the underlying distribution $p\in\Delta([n])$:
\begin{equation}\label{def:empirical}
\tilde{p}(i) = \frac{1}{m} \sum_{j=1}^m \mathbb{1}_{\{s_j=i\}}, \qquad i\in [n]
\end{equation}

First, we bound the expected total variation distance between $\tilde{p}$ and $p$, by using $\ell_2$ distance as a proxy:
$$
    \mathbb{E}{ d_{\rm TV}(p,\tilde{p}) }
    =\frac{1}{2}\mathbb{E}{ \lVert{p-\tilde{p}}\rVert_1}
    =\frac{1}{2}\sum_{i=1}^n\mathbb{E}{ \lvert{p(i)-\tilde{p}(i)}\rvert }
    \leq\frac{1}{2}\sum_{i=1}^n\sqrt{\mathbb{E}{ (p(i)-\tilde{p}(i))^2} }
$$
the last inequality by Jensen. But since, for every $i\in[n]$, $m\tilde{p}(i)$ follows a $\operatorname{Bin}({m},{p(i)})$ distribution, we have
$\mathbb{E}{ (p(i)-\tilde{p}(i))^2} = \frac{1}{m^2}\operatorname{Var}[m\tilde{p}(i)] = \frac{1}{m}p(i)(1-p(i))$, from which
$$
    \mathbb{E}{ d_{\rm TV}(p,\tilde{p}) } \leq\frac{1}{2\sqrt{m}}\sum_{i=1}^n\sqrt{p(i)} \leq \frac{1}{2}\sqrt{\frac{n}{m}}
$$
the last inequality this time by Cauchy—Schwarz. Therefore, for $m\geq \frac{n}{\varepsilon^2}$ we have $\mathbb{E}{ d_{\rm TV}(p,\tilde{p}) }\leq \frac{\varepsilon}{2}$.
Next, to convert this expected result to a high probability guarantee, we apply McDiarmid's inequality to the random variable $f(s_1,\dots,s_m) \stackrel{\rm def}{=} d_{\rm TV}(p,\tilde{p})$, noting that changing any single sample cannot change its value by more than $c\stackrel{\rm def}{=} 1/m$:
$$
    \mathbb{P}\left\{ \lvert{f(s_1,\dots,s_m) - \mathbb{E}{f(s_1,\dots,s_m)}\rvert} \geq \frac{\varepsilon}{2} \right\} \leq 2e^{-\frac{2\left(\frac{\varepsilon}{2}\right)^2}{mc^2}} = 2e^{-\frac{1}{2}m\varepsilon^2}
$$
and therefore as long as $m\geq \frac{2}{\varepsilon^2}\ln\frac{2}{\delta}$, we have $\lvert{f(s_1,\dots,s_m) - \mathbb{E}{f(s_1,\dots,s_m)}\rvert} \leq \frac{\varepsilon}{2}$ with probability at least $1-\delta$. $\square$

There is a second proof, somewhat more fun, given in that short note (credit to John Wright for pointing it out, and emphasizing it's the "fun" one). Here it is:

Proof. Again, we will analyze the behavior of the empirical distribution $\tilde{p}$ over $m$ i.i.d. samples from the unknown $p$.  Recalling the definition of total variation distance, note that $d_{\rm TV}({p,\tilde{p}}) > \varepsilon$ literally means there exists a subset $S\subseteq [n]$ such that $\tilde{p}(S) > p(S) + \varepsilon$. There are $2^n$ such subsets, so we can do a union bound.

Fix any $S\subseteq[n]$. We have
$$
\tilde{p}(S) = \tilde{p}(i) = \frac{1}{m} \sum_{i\in S} \sum_{j=1}^m \mathbb{1}_{\{s_j=i\}}
$$
and so, letting $X_j \stackrel{\rm def}{=} \sum_{i\in S}\mathbb{1}_{\{s_j=i\}}$ for $j\in [m]$, we have
$
\tilde{p}(S) = \frac{1}{m}\sum_{j=1}^m X_j
$ where the $X_j$'s are i.i.d. Bernoulli random variable with parameter $p(S)$. Then, by a Chernoff bound (actually, Hoeffding):
$$
    \mathbb{P}\left\{ \tilde{p}(S) > p(S) + \varepsilon \right\} = \mathbb{P}\left\{ \frac{1}{m}\sum_{j=1}^m X_j > \mathbb{E}\left[\frac{1}{m}\sum_{j=1}^m X_j\right] + \varepsilon \right\} \leq e^{-2\varepsilon^2 m}
$$
and therefore $\mathbb{P}\left\{ \tilde{p}(S) > p(S) + \varepsilon \right\} \leq \frac{\delta}{2^n}$ for any $m\geq \frac{n\ln 2+\log(1/\delta)}{2\varepsilon^2}$. A union bound over these $2^n$ possible sets $S$ concludes the proof:
$$
    \mathbb{P}\left\{ \exists S\subseteq [n] \text{ s.t. }\tilde{p}(S) > p(S) + \varepsilon \right\} \leq 2^n\cdot \frac{\delta}{2^n} = \delta
$$
and we are done. $\square$

Note: a lower bound of $\Omega(\frac{n}{\varepsilon^2})$ (also folklore) is easy to derive from Assouad's lemma, by considering the family of distributions over $[n]$ where each pair of consecutive elements $(2i,2i+1)$ has either probabilities $(\frac{1+c\varepsilon}{n},\frac{1-c\varepsilon}{n})$  or $(\frac{1-c\varepsilon}{n},\frac{1+c\varepsilon}{n})$ for some suitable constant $c>0$. (Intuitively and a bit misleadingly: any learning algorithm has to "figure out" at least $\Omega(n)$ of these independent choices, but each of them requires $\Omega(1/\varepsilon^2)$ samples.)

[1] Public GitHub: https://github.com/ccanonne/probabilitydistributiontoolbox (includes the source for the note on Assouad's lemma as well).


Efficiently computing the exact union of 'N' intersecting circles on a plane I have a set of $N$ circles with a set of known radii $r_i$ on a plane of some surface area $A$.  If intersection is allowed between circles, how can I most efficiently compute the exact (not approximate) surface area of their union?

See this earlier MathOverflow question: the union of circles can be constructed (as its set of boundary arcs) in $O(n\log n)$ time. Once you have that, it's straightforward to use Green's theorem to calculate the area.