Is there a natural restriction of VO logic which captures P or NP? The paper

Lauri Hella and José María Turull-Torres,
Computing queries with higher-order logics,
TCS 355 197–214,
2006.
doi: 10.1016/j.tcs.2006.01.009

proposes logic VO, variable-order logic.  This allows quantification over orders over the variables.  VO is quite powerful and can express some non-computable queries.  (As pointed out by Arthur Milchior below, it actually captures the whole of the analytical hierarchy.)  The authors show that the fragment of VO obtained by allowing only bounded universal quantification over the order variables exactly expresses all c.e. queries.  VO allows the order variables to range over the natural numbers, so bounding the order variables is clearly a natural condition to impose.

  Is there a (nice) fragment of VO that captures P or NP?

As an analogy, in classical first-order logic allowing quantification over sets of objects gives a more powerful logic called second-order logic or SO.  SO captures the whole of the polynomial hierarchy; this is usually written as PH = SO.  There are restricted forms of SO capturing important complexity classes: NP = $\exists$SO, P = SO-Horn, and NL = SO-Krom.  These are obtained by imposing restrictions on the syntax of allowed formulas.

So there are straightforward ways to restrict SO to obtain interesting classes.  I would like to know if there are similar straightforward restrictions of VO that are roughly the right level of expressivity for P or NP.  If such restrictions are not known I would be interested in suggestions for likely candidates, or in some arguments why such restrictions are unlikely to exist.

I have checked the (few) papers that cite this one, and checked the obvious phrases on Google and Scholar, but found nothing obviously relevant.  Most of the papers dealing with logics more powerful than first-order don't seem to deal with restrictions to bring down the power into the realm of "reasonable" computations, but seem content to dwell in the c.e. universe of arithmetic and analytic classes.  I'd be happy with a pointer or a non-obvious phrase to search on; this might be well known to someone working in higher-order logics.

For information, VO is in fact really more powerful than what you state; it contains the entire analytical hierarchy (hence, also the entire arithmetical hierarchy). The result is not published, neither submitted to any place, but you can find it on my page, www.milchior.fr/ho.pdf section 7 page 47.

In it I show how VO lets you express addition and multiplication on order variable; may be some idea in this paper can help you. In particular I gave an equivalent definition (I prove it is equivalent) and I think it is more easy to use. (I wanted to avoid the fact that, in their definition of VO $\forall i \forall X^i\forall j\exists Y^j (X^i=Y^j)$ is false while    $\forall i \forall X^i\forall i\exists Y^i (X^i=Y^i)$ is true; which means that $i$ was changed after $X$ was quantified; hence it is useless to add "$^i$" when one quantifies $X$.

One straightforward restriction would be to forbid to quantify the same variable twice. I am pretty sure that the restriction is the class ELEMENTARY. The idea is that, for every formula $\phi(i)$ with a free order variable $i$, there would be one number $k$ such that forall $i>k$ the value of $\phi(i)$ would not change; hence if we can find this $k$ (which is probably an elementary function of the size of the universe) we can avoid to really check every possible $\phi(i)$ when we want the value of $\forall i \phi(i)$ but restrict it to $\forall i < k \phi(i)$.

Else, you can certainly restrain VO by restraining the maximal order accepted; but then you obtain a "higher order" language (HO), and this is probably not what you want.


An edge partitioning problem on cubic graphs Has the complexity of the following problem been studied?

Input: a cubic (or $3$-regular) graph $G=(V,E)$, a natural upper bound $t$

Question: is there a partition of $E$ into $|E|/3$ parts of size $3$ such that the sum of the orders of the (nonnecessarily connected) corresponding subgraphs is at most $t$?

Related work
I found quite a few papers in the literature that prove necessary and/or sufficient conditions for the existence of a partition into some graphs containing three edges, which is somehow related, and some others on computational complexity matters of problems that intersect with the above (e.g. the partition must yield subgraphs isomorphic to $K_{1,3}$ or $P_4$, and no weight is associated with a given partition), but none of them dealt exactly with the above problem.

Listing all those papers here would be a bit tedious, but most of them either cite or are cited by Dor and Tarsi.

20101024: I found this paper by Goldschmidt et al., who prove that the problem of edge partitioning a graph into parts containing AT MOST $k$ edges, in such a way that the sum of the orders of the induced subgraphs is at most $t$, is NP-complete, even when $k=3$. Is it obvious that the problem remains NP-complete on cubic graphs, when we require strict equality w.r.t. $k$?

Additional information

I've tried some strategies that failed. More precisely, I found some counterexamples that prove that:

maximising the number of triangles does not lead to an optimal solution; which I find somehow counter-intuitive, since triangles are those subgraphs with lowest order among all possible graphs on three edges;
partitioning the graph into connected components does not necessarily lead to an optimal solution either. The reason why it seemed promising may be less obvious, but in many cases one can see that swapping edges so as to connect a given subgraph leads to a solution with smaller weight (example: try that on a triangle with one additional edge connected to each vertex; the triangle is one part, the rest is a second, with total weight 3+6=9. Then exchanging two edges gives a path and a star, with total weight 4+4=8.)

Here is a suggestion for how to show it's NP hard. I don't know if this works or not. First, consider the same problem on multigraphs. NP hardness may be easier to prove there. Try reducing from cubic MAX CUT which is NP hard even to approximate (Berman and Karpinski "On Some Tighter Inapproximability Results"). Divide each edge into two and at each of the new degree-2 vertices attach a vertex with self-loop. Does your maximum partition correspond to a maximum cut?

--

Here is a bit more explanation.

(1)
The problem of maximizing (number of sources+number of sinks) over all orientations of a cubic graph is related to MAXCUT by some linear function. This requires showing some corersspondence between maximal cuts and sources-and-sinks-maximal orientations. In one direction, in a maximum cut (U,V), we can orient all edge from U to V. The internal edges E(U) form a matching, so these can be oriented arbitrarily and similarly for E(V), and the total number of sources and sinks is some linear function of the size of the cut. In the other direction, given a sources-and-sinks-maximal orientation, the partition U=vertices of in-degree 0 or 1, V=vertices of in-degree 2 or 3 gives a cut.

(2)
In the edge-bisecting transformation I described above, in an optimal configuration each loop is coloured the same as the edge next to it, and w.l.o.g that edge is coloured the same as the some other (non-loop) edge next to that. So each bisected edge has one colour coming from its attached loop and one other colour. This corresponds to an orientation and (1) applies.


Is intersection of $k \ge 3$ graphic matroids in P? It is known that intersection of three general matroids is NP-hard (source), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids.

A special case of a problem I am working on can be solved by intersection multiple graphic matroids, but I haven't been able to find, whether this problem is in P.

Question: Is it known? Can someone please refer me to a paper or something?

(Note: I have asked this question on Computer Science and was referred here.)

I think it is still NP-complete, by a reduction from Hamiltonian paths in bipartite graphs with two degree-one vertices and all other vertices having degree three. (This is just the same as finding Hamiltonian cycles through a specified edge in a cubic bipartite graph — replace the specified edge by two leaves.)

To reduce from Hamiltonian paths to graphic matroid intersection, use one graphic matroid to force the subgraph you choose to be a spanning tree (true of every path) and two more graphic matroids, one on each side of the bipartition, to force the subgraph to have degree two at each degree-three vertex and to have an edge at each degree-one vertex. These are the graphic matroids of a graph with disjoint copies of $K_3$ for each degree-three vertex and $K_2$ for each degree-one vertex.


Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters? I was reading this paper, about the complexity of decision problems for
reversal bounded counter machines.
I got to Theorem 1 on Page 6.
The theorem shows that there's a log-space NTM which can determine if a non deterministic reversal-bounded counter machine is empty or not.
(A log-space NTM can be converted into a polynomial time DTM).
The proof shows that, for input machine represented as a string of length $n$,
with $m$ counters, that $O(m\log n)$ space is required.
Here's where I get lost. The paper says that, since $m$ is fixed, we can consider
the machine to take $O(\log n)$ space.
Does this mean that the algorithm is only uses log-space if $m$ is fixed? Would the corresponding deterministic algorithm then be exponential in terms of $m$?

If the number of counters or the number of reversals (or both) is part of the
input, the problem becomes coNP-complete (unless there is exactly one counter):

The upper bound was shown by Hague and Lin, using a reduction to existential Presburger arithmetic:
Hague and Lin, "Model Checking Recursive Programs with Numeric Data Types", CAV 2011, http://dx.doi.org/10.1007/978-3-642-22110-1_60.

If the number of counters is part of the input and one has exactly one
reversal, it is not hard to reduce the knapsack problem: Given
binary representations of $x_1,\ldots,x_k,y$, each containing at most $n$
bits, one can easily construct a $(k+1)n$-counter automaton $A$ that can nondeterministically pick a subset $S\subseteq \{1,\ldots,k\}$ and
produce $\sum_{i\in S} x_i$ on the first counter and then subtracts
$y$ from the first counter. Then the language of $A$ is non-empty
if and only if there is a subset $S\subseteq \{1,\ldots,k\}$ with
$\sum_{i\in S} x_i=y$.
If the number of reversals is part of the input and one has exactly
two counters, coNP-hardness was already shown in
Gurari and Ibarra, "The complexity of decision problems for finite-turn multicounter machines", http://dx.doi.org/10.1016/0022-0000(81)90028-3 .
This seems to be the journal version of the paper linked in the question.
If the number of reversals is part of the input and one has exactly
one counter, however, then the problem is NL-complete. This is a well-known
result on one-counter automata.


Verification: how 'formal' is a tool like Java Modeling Language (JML) compared to certified libraries and model checking? (note: this is probably a beginner question, and English is not my first language)

Recently, I have read a paper that used the “Java Modeling Language” (JML), see for instance:

http://www.eecs.ucf.edu/~leavens/JML//index.shtml
http://www.eecs.ucf.edu/~leavens/JML/fmco.pdf

a) certified Software
To my understanding, a sorting algorithm proven correct in the theorem prover Coq (and possibly extracted to an ocaml program) is "certified software" or formally verified software, as a mathematical proof of the correctness can be extracted and possibly manually verified.

b) model checking
software verified via model checking is not certified or formally verified software, as the model checker has to be trusted.

How does the "Java Modeling Language" (JML) compare for verification purposes?

Okay, I think I get it. It is not about software verification, as it is stated that:

The contracts are defined by program code
in the programming language itself, and are trans-
lated into executable code by the compiler. Thus,
any violation of the contract that occurs while the
program is running can be detected immediately.

I cannot find a real example of verification in the above paper, at least not in the sense of model checking or certified software, so I guess they just don't have an emphasis on formal methods.

This is a strange comparison. Your question is comparable to asking "how expressive is the ANSI C language specification compared to stdlib and compilation". The comparisons don't make sense.

The Java Modelling Language can be used as a specification language to specify properties of code. The language alone does not solve the problem of verifying whether these properties are satisfied.
A model checker allows you to check if a system with a transition system semantics satisfies a logical formula. The formula is typically written in a propositional temporal or modal logic though first-order and other extensions exist. Nonetheless, most model checkers used in practice do not support specification languages with quantifiers. I do not know of a model checker that supports a specification language as rich as JML.
A certified library contains code that provides certain guarantees. Those guarantees may have been provided using a theorem prover, or a model checker, or by doing a  manual proof.

If you want a mathematical comparison, to me, it's like comparing the formulae of first order arithmetic (a language), the principle of induction (a proof technique) and a collection of theorems in a number theory textbook. They are related concepts but they do not achieve the same goal so comparing them does not make sense.


Topology/Space of Recursive Algebraic Datatypes I have a recursive algebraic datatype. I (somewhat arbitrarily) defined one function to compute distance between instances, and am trying to define a function to approximate a "vector" between instances.  I assume there's no single way to define a metric space on top of a definition of an algebraic data type, much less a vector space, but was wondering what literature exists about treating recursive algebraic datatypes as existing in a topological space with meaningful comparisons.

The reason I want to treat it like a vector space is because I want to define interpolation between two structures in some reasonable manner.

It is possible to construct recursive datatypes (algebraic datatypes are a special case) in a suitable category of complete metric spaces, see for instance P. America and J. Rutten's Solving Reflexive Domain Equations in a Category of Complete Metric Spaces, Journal of Computer and System Sciences 39, 343-375 (1989).

As for making vector spaces out of algebraic datatypes, I do not really know, but if you explain what you want them for, we might be able to suggest something.


Depth reduction for Boolean circuits This result by Tavenas, Koiran and others show that any polynomial computed by a circuit of size $s$ is computed by a depth-4 homogenous circuit of size $s^{\sqrt{d}}$.

Are there any similar results for Boolean circuits or do we know why such a thing is not possible?

Unfortunately, the best known depth reductions for Boolean circuits only work for very restricted classes of circuits. Valiant (Valiant; Viola) proved that a circuit of size $O(n)$ and depth $O(\log{n})$ can be computed by a depth-3 circuit of size $2^{O(n/\log\log{n})}$. Also, Valiant showed a similar depth reduction for linear size series-parallel circuits (a natural subclass of circuits), see Calabro.

Note that the number of gates in a depth-3 circuit computing a random function is $\Theta(2^{n/2})$ (Dančík; Sergeev), while the best lower bound we can prove is only $2^{\Omega(\sqrt{n})}$ (Håstad; Håstad, Jukna, Pudlák; Paturi, Pudlák, Zane; Boppana; Paturi, Pudlák, Saks, Zane; Meir, Wigderson).


Matching regular expressions using regular expressions Is it possible to create a regular expression that matches regular expressions in any given notation?

Or, in other words, does there exist a unambiguous and full notation for regular expressions that can be parsed with regular expressions?

Even if we require that the expressions are "human-readable", and the conversion between the standard notation and the new notation is fairly easy to compute, the answer is "yes".

For example, we can modify the standard notation as follows to obtain "compressed" regular expressions:

You are allowed to remove any prefix that consists of a sequence of ('s
You are allowed to remove any suffix that consists of a sequence of )'s

That is, ((a|b)*c)de(f|g) can be expressed in the "compressed" notation using, for example, any of the following forms: a|b)*c)de(f|g or ((a|b)*c)de(f|g or (a|b)*c)de(f|g).

The compressed notation is unambiguous in the sense that you can recover a semantically equivalent expression by simply adding a sufficient number of leading and trailing parentheses to make everything balanced. Of course, a|b)*c)de(f|g might represent ((a|b)*c)de(f|g) or (((a|b)*c)de(f|g)), but adding extra parentheses does not change the language defined by the expression.

The "compressed" notation is a regular language.

And yes, this is cheating.


Finding a biased coin using a few coin tosses The following problem came up during research, and it's surprisingly clean:

You have a source of coins. Each coin has a bias, namely a probability that it falls on "head".
For each coin independently there's probability 2/3 that it has bias at least 0.9, and with the rest of the probability its bias can be any number in [0,1]. You don't know the biases of the coins. All you can do at any step is toss a coin and observe the outcome.

For a given n, your task is to find a coin with bias at least 0.8 with probability at least $1-\exp(-n)$. Can you do that using only O(n) coin tosses?

The following is a rather straight-forward $O(n \log n)$ toss algorithm.

Assume $1-\exp(-n)$ is the error probability we are aiming for. Let $N$ be some power of $2$ that is between say $100n$ and $200n$ (just some big enough constant times $n$). We maintain a candidate set of coins, $C$. Initially, we put $N$ coins in $C$.

Now for $i=1,\dots,\log N$, do the following:
Toss each coin in $C$ for $D_i = 2^i  10^{10}$ times (just some big enough constant).
Keep the $N/2^i$ coins with most heads.

The proof is based on a couple of Chernoff bounds. The main idea is that we half the number of candidates each time and thus can afford twice as many tosses of each coin.


Maximal munch rule issue for lexers: is detection decidable? Edit: I realise that one of my problems is that I don't have a clear definition of my problem, which makes the question of whether it is detectable hard to answer.

I'm therefore already happy with any reference in which this particular problem is discussed at all - I haven't found any such reference myself, and with any luck, I can derive a good definition of my problem from that, which will hopefully lead to a solution.

Original:

Suppose we have this lexical definition:

X := a*
Y := a

and this context-free grammar:

S := X Y

and we use any lexer and parser combination to generate a recogniser for this language, in which the lexer uses the 'maximal munch' or 'longest match first' rule.

The specification might seem to be trivially equivalent to the regular expression "$a$+", but it isn't: in fact, it recognises no strings at all. The reason is that $X$ 'eats' all the $a$ characters present in the input because of 'maximal munch', leaving none for $Y$ to consume, so the parser always rejects the input.

I'd like to know if it is decidable if such a problem is present in a given lexer and parser specification.

Note that this is decidable if only a single token is the culprit. Let $L_T$ be the language generated by some token (= regular expression) $T$, and let $L_R$ be the language generated by the 'follow' language of this token, that is, the language of all strings that are postfixes of the occurrence of $T$ in the specification. In the example above, $T=X=a^*$ and $R=Y=a$, though in general, $R$ will be a lot more complicated.

The problem can then be formulated as (where $+\!\!\!\!+\,$ denotes concatenation):

$(L_T +\!\!\!\!+\, L_R) \cap L_T \neq \emptyset$

If this intersection is nonempty, then $T$ will eat up the match made by $R$. As $L_T$ is regular, this is decidable. (note that a better, less stringent rule might be that $L_T +\!\!\!\!+\, L_R$ is not a subset of $L_T$, I'm not sure)

Unfortunately, grammars like $a b a^* b^* a b$ (split into 6 tokens) do not accept the string $abab$, and here no single token is the culprit, so the above method doesn't work.

Searching the web turned up nothing, not even that anyone else has ever noticed this problem, although I might just be using the wrong keywords. This surprised me somewhat, so chances are I'm either wrong or this is never a problem in practice.

I stumbled upon the above problem when toying with modularised parsing, but the above problem isn't specific at all for modularised parsing (though it can more easily become a problem if someone forgets to declare whitespace somewhere, in which case I'd like to warn the user, hence the above question).

To answer in the large, the fact that the syntax of programming languages is not context-free is not news (see e.g. Floyd, 1962).

To answer more precisely, in a context of scannerless parsing like yours, a way to implement maximal munch is to employ so-called follow restrictions (van den Brand et al., 2002) by forbidding some language to follow a given rule.  In your example, you could write a restriction X -/- a forbidding an $a$ after the token $X$.  Provided your forbidden languages are regular, these restrictions can be compiled back into the grammar (however in van den Brand et al.'s formalism, the forbidden language can be context-free and $X$ can be any nonterminal, and this clearly leads to an undecidable emptiness problem).

Another formalism for scannerless parsing is that of parsing expression grammars (Ford, 2004), which has a greedy, maximal-munch type semantics, and an undecidable emptiness problem.

Now, it doesn't look like your specific maximal munch semantics would allow you to reduce from these undecidable problems.  For a start, it seems to me that, rather than emptiness of the generated language, a tool should more broadly warn the user about any case where a token might "eat" a (non-empty) prefix of its follow language, i.e. whenever $(L_T\cdot\mathrm{Pref}_+(L_R))\cap L_T\neq\emptyset$, regardless of whether this prefix is mandatory of not.  This would capture your $aba^\ast b^\ast ab$ example if I understand correctly how you would tokenize it.

To conclude, here is an attempt to formalize your notion of maximal-munch-caused emptiness: let $\langle N,T,P,S\rangle$ be a context-free grammar with nonterminal alphabet $N$, terminal alphabet $T$, production set $P$ and axiom $S$.  Each terminal symbol $X\in T$ is associated with a regular language $L_X\subseteq\Sigma^\ast$ used for its tokenization.  For every occurrence of a terminal symbol $X$ in some production $A\to \alpha X\beta$ of your grammar where $\alpha,\beta$ are sequences of mixed terminals and nonterminals, construct the follow language $L_{\beta,A}$ of this particular occurrence (this is a context-free language) and consider the residual language of the token $L^{\text{max-munch}}_X=(L_X^{-1}\cdot L_X)\cap\Sigma^+$, which is a regular language of strings that will be "eaten up" by the maximal munch semantics.  In fact the language $L^{\text{max-munch}}_X$ is the language one would put in the follow restriction for $X$.  Then, if $$L_{\beta,A}\subseteq L^{\text{max-munch}}_X\cdot\Sigma^\ast\;,$$ or equivalently $L_{\beta,A}\cap (\Sigma^\ast\backslash(L^{\text{max-munch}}_X\cdot\Sigma^\ast))=\emptyset$, any string allowed to follow this occurrence of $X$ will be "eaten", and the language of the rule $A\to\alpha X\beta$ is empty.  Using the classical algorithm for emptiness checking with this extra twist for handling terminal symbols might solve your emptiness problem.


Span programs, witness size, and certificate complexity A span program is a linear-algebraic way of specifying a boolean function introduced here. Recently, this model was used to show that the negative adversary method provides a tight characterization (at least up to $\log n/ \log \log n$) of quantum query complexity.

The complexity measure connecting span programs to quantum query complexity is witness size. This measure seems rather similar to certificate complexity. Are there known connections between the two measures? What about the size (number of input vectors) measure for span programs and other measures like deterministic and randomized query complexity? What are the best known classical algorithms for evaluating span programs?

EDIT (after an answer by Martin Schwarz):

Of particular interest are conceptual connections that go directly through span programs as opposed to through the correspondence between witness size and quantum query complexity. Are there classical results that provide intuition about span programs/witness size and how they relate to deterministic and randomized query complexity?

The minimum witness size over all witnesses of a span program for a given function equals the generalized adversary bound, as shown e.g. in Theorem 1.7 here. Further, the generalized adversary bound is just a semi-definite relaxation of certificate complexity, see e.g. slide 40 in Reichardt's tutorial. The relation to deterministic and randomized query complexity is discussed in these tutorial slides as well.


Continuity vs Uniformity when designing Hash functions Reading available literature (yep, including wikipedia), I see that hash functions should have (continuity) and map values that differ very little to similar/same hash codes, in particular for (hash tables that use linear search) ... if that makes any sense. Supposedly, this would help linear search benefits from locality of reference.

OTH, a hash function should be uniform, in the sense that hash values are uniformly distributed. Unless I'm misunderstanding something, it looks to me as if these two properties are in conflict.

Let's say we have a sequence $S$ of input values $(s_1, ..., s_n)$ such that the delta between any two value pairs is small and similar across the set.

That is

$$\forall s_i, s_j \in S\,\,|\,\varepsilon_{min} < \delta(s_i, s_j) < \varepsilon_{max}$$

and with the differences between any two values ($\delta(s_i,s_j)$) being uniformly distributed. In such a case the values in the sequence have a uniform distribution.

Let's suppose we aim to store these values in a hash table with open addressing (linear probing) and a hash function $h$. Obviously, we assume that the hash table is large enough to accommodate all input values (and to be below an initial load factor.)

If the hash function $h$ exhibits continuity, then it will map all the values in $S$ very close to one another (if not, to the same hash code) ergo increasing collisions. That is, it would exhibit clustering.

Wouldn't that then, deteriorate the search performance (via liner probing) as a result of the resulting collisions. If continuity is desirable when using linear probing, then how does one cope with the collisions when a large part of the values are close to one another?

--- EDIT ---

Sorry, I left some things out. $\delta(s_i,s_j)$ represents the number of symbols by which the strings $s_i$ and $s_j$ differ (or the number of changes that need to occur to convert $s_i$ into $s_j$.)

For a better example, let $\Sigma = {\sigma_1, \sigma_2, ... , \sigma_n}$ be an alphabet, and $L(i, n)$ be a language over $\Sigma$ such that

$$
L(i,n)\,\triangleq \{s| (s=\sigma_i^*\sigma_k\sigma_i)\wedge (|s| = n) \wedge (\{\sigma_i,\sigma_k\} \subset \Sigma)\}
$$

So, if we were to consider input strings, all of length $n$ such as
$$aaa..., baaa..., abaa..., ....aaab, caaa..., acaa$$

that only differ on one character, the value and position of which is uniformly distributed among the input strings, then a hash function $h$ that possess continuity will cluster them all on top or near the same hash value.

-- ADDITIONAL EDIT --

The only place I've read so far that mentions continuity as a desirable property has been in the Wikipedia article for hash functions. I've consulted all the other books I have on Algorithms (CLRS, Sedgewick's, Berman and Paul's and others), and I've not found any such assertion on hash functions.

So it seems to me that continuity is not a desirable trait despite what the Wiki entry says. Or am I missing something????

While continuity in a strong sense is probably too much to ask for, locality sensitive hashing (LSH) achieves a very similar goal: given a set of items $x_1, \ldots, x_n$ which belong to some metric space with metric $d$, an LSH family of hash functions (parametrized by $D, c, p, q$) maps $x_i$ and $x_j$ into the same bucket with probability $\geq p$ if $d(x_i, x_j) \leq D$ and maps $x_i$ and $x_j$ into different buckets with probablity $\geq q$ if $d(x_i, x_j) > cD$. Of course there is tension in the requirements, so one looks for tradeoffs. Look at the wiki page and Alex Andoni's webpage, especially the CACM survey.

For context, LSH is a tool to solve the approximate nearest neighbor problem in high dimensional metric spaces. There exist solutions for various metrics, like hamming distance and $\ell_p$ norms, see the CACM survey. The approximate nearest neighbor problem is an important problem in computational geometry, and the high-dimensional version comes up in a variety of applications, for example in computer vision and information retrieval.

The way LSH is used to solve approximate near neighbor search is a fairly natural two-level hashing scheme. As you note, there is tension between the "continuity" property and bounding the number of collisions. For that reason, usually the gap between $p$ and $q$ (as I defined them above) is pretty small. To overcome this we construct a new hash function by choosing several functions from an LSH family and taking their concatenation. The resulting universe is too big, so it is reduced using traditional hashing. Then we build several hash tables using these hash functions. A query is answered by hashing the query point and inspecting the other points in the same bucket(s) to determine if they are close enough (this is the linear search part). Parameters can be chosen so that a query is answered in sublinear time.


Is the problem NP-C or polynomially solvable? I am considering a problem of the following: Given a set $X$ of integers and another integer B, are there two subsets of $X$, say $X_1$ and $X_2$, such that $X_1-X_2=B$ ? (Here, $X_i$ also denotes the sum of integers in the set $X_i$)

I wonder whether this problem is solvable in polytime or NP-complete? Thanks.

As said by RB in the comment, if $X_1 \cup X_2  = X; X_1 \cap X_2 = \emptyset$, then setting $B=0$ makes your problem equivalent to PARTITION. But even with the relaxed conditions:
$X_1,X_2 \neq \emptyset, X_1, X_2 \subseteq X;  X_1 \cap X_2 = \emptyset$  (i.e. $X_1,X_2$ not necessarily form a partition of $X$) the problem is still NPC: set $B = 0$ and it becomes equivalent to the EQUAL-SUBSET-SUM problem.

I don't bear papers behind paywalls :-), so this is a quick sketch of an alternative simple reduction from SUBSET-SUM:

Given non-negative integers $A = \{ a_1,a_2,...,a_n\}$ and a target sum $S$, let $k = \lceil \log \sum a_i \rceil$.

For $i = 1,...,n$, set $x_i = 2^{k+3i} + a_i$,
add $n$ new integers $x'_i = 2^{k+3i}$,
add two dum integers $d_1 = d_2 = 2^{k+3(n+1)}$ that are used only to make $X_2$ nonempty
and finally set as target sum (for your problem) $B = S + \sum_{i=1}^n 2^{k+3i}$

The following figure should make things clearer:

(empty cells represent zeros)

If there is a subset $A'$ that sums to $S$ in the original problem, then $X_1 = \{ x_i \mid a_i \in A' \} \cup \{ x'_i \mid a_i \notin A'\} \cup \{d_1\}$, $X_2 = \{d_2\}$ are such that $X_1 - X_2 = B$.

In the opposite direction, suppose that $X_1 - X_2 = B$, then it is easy to prove that if you include one of the $x_i$ (or $x'_i$) in $X_2$, i.e. you subtract them, you'll not be able to "totalize" the $2^{k+3i}$ component of the target sum $B$ anymore. So none of the $x_i$ can be included in $X_2$, and $\sum_{\{ i \mid x_i \in X_1\}} a_i = S$


Is there a 'very fast growing' hierarchy that would capture System F? Particular ordinals in slow-growing and fast growing hierarchies can capture the expressiveness of many predicative type systems.

Is there a hierarchy of function that could possibly capture impredicative System F?

Typically, fast growing hierarchies are characterized by ordinal notations, which are really just ways to express fast-growing functions (but it's sometimes convenient to see them as ordinals in the mathematical sense).

There is a somewhat generic way of assigning an ordinal (notation) to a consistent theory, though it is very non-constructive. For various technical reasons, the ordinal for $\mathrm{PA}_2$ corresponds to the fast growing functions expressible in system $F$.

So the question really is:

  Is there an ordinal notation for $\mathrm{PA}_2$?

As far as I am aware, we do not know the answer to this question, and it is a very important open question in proof theory/ordinal analysis.

The following mathoverflow question explains this idea in more detail:

https://mathoverflow.net/questions/144041/proof-theoretic-ordinal-of-zfc-or-consistent-zfc-extensions


How to prove $P^{Halt} = PSPACE^{Halt}$ Halt means the halting set. $PSPACE^{Halt}$ is the class of problems that can be solved with polynomial memory (possibly exponential time), given a halting oracle.

Using $n$ calls to the halting oracle and time $O(n^2)$, you can compute the first $n$ bits of the Chaitin's constant.  Using the $n$ bits of the Chaitin's constant and unbounded time, all queries to the halting oracle of length approximately $≤n$ (depending on the representation) can be eliminated.  Finally, the result can be obtained in bounded time by querying the halting oracle.

Additional Details: In the relativization of $\mathrm{PSPACE}$ here, the oracle tape counts against space usage, so a $\mathrm{PSPACE}^\mathrm{Halt}$ machine can only use queries of length $n^{O(1)}$ (though the number of the queries can be exponential).  The digits of the Chaitin's constant can be used to get the number of machines of length $≤n$ that halt, and by simulating all these machines until the right number halts, we can find out exactly which of the (roughly $2^n$) machines halt.  The digits of the Chaitin's constant, or just the number of the halting machines, can be computed in $n^{O(1)}$ queries by bisection.


For which graphs is the DFS tree always a path? For which undirected graphs are all depth-first-search trees (for all possible starting vertices and for all choices of which neighbors to search first) directed paths? That is, every DFS tree should have only one leaf, and every other vertex should have exactly one child.

For instance, it's true for cycles, complete graphs, and balanced complete bipartite graphs.

Finding a DFS tree that is not a path is obviously in NP. Is it NP-complete, or polynomial?

This is equivalent to the property that you can construct a Hamiltonian path by greedily taking an arbitrary edge at every vertex. Searching for greedy Hamiltonian path turned up: Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests, Tankusa and Tarsib, doi:10.1016/j.disc.2006.09.031, which points to Randomly Traceable Graphs, Chartrand and Kronk, SIAM J. Appl. Math., 16(4), 696–700, doi:10.1137/0116056 as characterising these graphs as precisely the graphs you mention in the question.


Literature for Generalized Load Balancing i am looking for literature on this kind of problem.
$$
\begin{align}
\min_x \max_k &\quad \sum_{i,j} x_{ij}c_{ijk}\\
\text{subject to}&\\
&\sum_j x_{ij}=1,&& \forall i\in\mathcal J\\
&x_{ij}\in\{0,1\},&& \forall i\in\mathcal J, j\in\mathcal M
\end{align}
$$

$\mathcal J$ is a set of Jobs and $\mathcal M$ is a set of Machines.
$c_{ij}$ is a vector and describes the cost of the job $i$ on the machine $j$.
So the cost has multiple dimension.

The Aim of the programm is to find a schedule so that each job is scheduled on a machine and the biggest dimension of the add up cost vector is minimized.

The problem is described here:

http://arxiv.org/pdf/1211.5729v2.pdf (Page 2 left column bottom) as Generalized load balancing

and here:

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A8FEB960E21CA0361066CD5200C02718?doi=10.1.1.380.8241&rep=rep1&type=pdf (Page 4 left column) as  generalized AP association
problem

EDIT

load balancing can be generalized in several ways, i.e. restrict that each job can only run on a specific set of machines.
This is also a generalization of the scheduling problem.

I'm interested in the case where the scheduling is restricted and multidimensional.
I'm looking for more literature for this problem.

Thank you

Appreciable literature is available in this standard book on Approximation Algo by Vazirani
http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf

Refer to chapter 10 for details.


Maximizing a convex function with linear constraints I have the following optimization problem:
$$
\arg\max_{\{\phi_p\}_{p=1}^M}\sum_{i=1}^N \max_{p=1,\ldots,M}\{\phi_p a_{ip}\}
\mbox{ such that }\sum_{p}\phi_p\leq 1\mbox{ and }0\leq \phi_p\leq 1,\forall p=1,\ldots,M,
$$
where $a_{ij} \geq 0,\forall i,j$. The objective function is clearly convex since $\max_{p}\{\phi_p a_{ip}\}$ is convex in $\{\phi_p\}$.

I realize that, in general, convex maximization problems can be NP-hard but I was wondering whether there are any known efficient solutions for this specific problem structure.

I apologize but there was a typo in my question. The constraint is supposed to be $\sum_{p}\phi_p\leq K$. Hence, I need to search over ${M\choose K}$ vertices, which may be an exponential number of vertices if $K=O(M)$.

Your problem in revision 3 of the question is NP-hard by a reduction from the vertex cover problem.  Slightly more precisely, even if aip’s are restricted to 0 or 1, it is NP-complete to decide whether the maximum value in the question is equal to N or less than N.  (Note that the maximum value cannot be greater than N if aip’s are 0 or 1.)  The detail is left as an exercise.


Recent fundamental results in algorithms? I dont know if this question belong to this forum, but I will ask it anyway

To your opinions, what are the most recent fundamental results in the field of algorithms ? [Results that can be taught in an advanced undergrad or graduate algorithms course]

In here, I am talking about results with high applicability to computer science, a continuation to what is usually taught in a general algorithm course. For instance, if we were in 1995 I would call skiplists and randomized rounding as new fundamental results in CS.

My main goal: build material for an advanced course on algorithms [that does not get into specific research areas and applications]

(Let's restrict recent to papers published in the late 1990's).

Cache-oblivious algorithms were first conceived of (according to Wikipedia) in 1996.

An algorithm is cache-oblivious if it uses caches in an optimal way, without knowing the size of the cache (which also means that if there is more than one level of cache, as in a modern PC, it is also used optimally).


Which (almost) balanced Boolean function has smallest "total" influence The well known Kahn–Kalai–Linial (KKL) Theorem says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$
$$
\max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot \Omega\Bigl(\frac{\log n}{n}\Bigr).
$$
The lower bound on maximum influence is achieved by the $\mathsf{Tribes}_n$ function. I have two questions in this regard:

What is a lower bound on total influence (as opposed to maximum influence) of Boolean functions? For a meaningful answer, it is necessary to consider functions that are (almost) balanced like $\mathsf{Tribes}_n$. For instance, a constant function has $0$ total influence.
Which almost balanced Boolean function achieves the lower bound on total influence? i.e., which balanced function has the smallest total influence? This question is a natural follow-up to the first question.

Thanks in advance!

Edit:

As Clement C. pointed out, there is a simple solution to the question for the Dictator function. Perhaps more interesting is to have the constraint that all variables $x_1, \dots , x_n$ have non-zero influence.

Questions:

What is a lower bound on total influence (as opposed to maximum influence) of Boolean functions where each coordinate $i \in [n]$ is influential?
Which almost balanced Boolean function, whose every coordinate has non-zero influence has the smallest total influence?

You have the lower bound of $\mathbf{Inf}[f] \geq \operatorname{Var}[ f ]$ for $f\colon  \{-1,1\}^n\to\mathbb{R}$ (Poincaré Inequality), so that for an (almost) balanced $f\colon  \{-1,1\}^n\to\{-1,1\}$ one must have
$$
\mathbf{Inf}[f] \gtrsim 1 \tag{1}
$$
(say, $1-\epsilon$, depending on the near-unbalanced assumption). Further, for a dictator function, this is tight:
$$
\mathbf{Inf}[\chi_1] = \mathbf{Inf}_1[\chi_1] = 1\,. \tag{2}
$$


Need a good overview for Succinct Data Structure algorithms (already asked on main site, but asking also here for better coverage, sorry)

Since I knew about Succinct Data Structures I'm in a desperate need of a good overview of most recent developments in that area.

I have googled and read a lot of articles I could see in top of google results on requests from top of my head. I still suspect I have missed something important here.

Here are topics of particular interest for me:

Succinct encoding of binary trees with efficient operations of getting parent, left/right child, number of elements in a subtree.

The main question here is as following: all approaches I know of assume the tree nodes enumerated in breath-first order (like in the pioneer work in this area Jacobson, G. J (1988). Succinct static data structures), which does not seem appropriate for my task. I deal with huge binary trees given in depth-first layout and the depth-first node indices are keys to other node properties, so changing the tree layout has some cost for me which I'd like to minimize. Hence the interest in getting references to works considering other then BF tree layouts.
Large variable-length items arrays in external memory. The arrays are immutable: I don't need to add/delete/edit the items. The only requirement is O(1) element access time and as low overhead as possible, better then straightforward offset and size approach. Here is some statistics I gathered about typical data for my task:

typical number of items - hundreds of millions, up to tens of milliards;

about 30% of items have length not more then 1 bit;

40%-60% items have length less then 8 bits;

only few percents of items have length between 32 and 255 bits (255 bits is the limit)

average item length ~4 bit +/- 1 bit.

any other distribution of item lengths is theoretically possible but all practically interesting cases have statistics close to the described above.

Links to articles of any complexity, tutorials of any obscurity, more or less documented C/C++ libraries, - anything what was useful for you in similar tasks or what looks like that by your educated guess - all such things are gratefully appreciated.

Update: I forgot to add to the question 1: binary trees I'm dealing with are immutable. I have no requirements for altering them, all i need is only traversing them in various ways always moving from node to children or to parent, so that the average cost of such operations was O(1).

Also, typical tree has milliards of nodes and should not be fully stored in RAM.

I assume that you are interested in succinct external memory data structures that are efficient in practice. In that case, you can probably get what you want with a few basic techniques and some engineering.

For trees, I would start with reading Arroyuelo et al.: Succinct Trees in Practice. The paper deals with trees in main memory, but most of the techniques can be used in external memory with similar choices as below.

As for your second question, the most important choice is deciding which encoding you use for the items. Given the distribution you describe, I would first try using $\gamma$-codes or $\delta$-codes. When you have chosen the encoding, the next step is to encode the array in blocks of size $B$, where the block size is chosen so that random disk reads of size $B$ are efficient in practice.

To find the correct block quickly, you need a rank dictionary that resides in main memory. Assuming that you have $n$ items, you build a binary sequence $S$ of length $n$, where $S[i] = 1$ iff item $i$ starts a new block. Gap encoding compresses the sequence well; Gupta et al.: Compressed data structures: dictionaries and data-aware measures gives one example of such index. If you want to find item $j$, then you need to retrieve block $rank(j)$ and decode it to get the item.

If you want to keep the rank index small, you have to make the block size quite large (probably kilobytes or tens of kilobytes), making the above basic solution CPU-intensive. This can be solved by adding a little overhead to the blocks stored on disk. Basically you apply the same solution recursively, so that each disk block stores a number of small blocks as well as another rank index. When you have retrieved the correct disc block, you use the rank index within it to find the right small block to decode, instead of decoding the entire block. With this secondary index, random accesses probably become I/O-bound even with the fastest solid-state drives available.


Maximum ball transform Consider a finite uniform grid $G$ in three dimensions with a function $f$ mapping integer grid positions $p$ to a boolean value $f(p)$ (i.e., a black/white volume image.)

A ball in $f$ is a set of grid points with center $c$ and radius $r$ where $f(p)$ is true for all $p \in G$ with euclidean distance $|c-p| \leq r$.

The maximum ball transform $MB$ finds for each grid point $p$ the radius $r$ of the largest ball in $f$ containing that point.  (Note: This is probably not the actual, commonly used name for this. However I don't know what else to call it.)

Are there good algorithms to compute this transform?

I assume this is related to the (euclidean) distance transform. (Find for each grid point $p$ the radius of the largest disk in $f$ with center $p$.)

$DT(p) = min_{x \in f} |p-x|$

$MB(p) = max_{|x-p| < DT(x)} DT(x)$

In the literature I can find algorithms that compute the euclidean $DT$ (and its reverse) in linear time. There are also algorithms to compute the medial axis transform $MAT$ (the set of all center points of the maximum balls).

Is there a faster algorithm than computing the $MAT$, iterating over all found maximum balls and naively tracking the largest one for each grid point?

Edit:
It seems this is sometimes known as Thickness Distribution or Euclidean Opening Function.

A recent paper computes an approximation: Fast and Accurate Approximation of the Euclidean Opening Function in Arbitrary Dimension (D. Coeurjolly, 2010), (presentation)

This answer has a problem; see comments below.

Following up on my comments, here is the rest of the full answer:

First, take a look at the 2008 paper Euclidean Skeletons of Digital Image and Volume Data in Linear Time by the Integer Medial Axis Transform
 by Hesselink and Roerdink.

From my reading of your question, Section 2 of the paper is answering your question fairly explicitly. In particular, the process they use is essentially a scan across grid points.

Additionally, I wouldn't worry about the runtime being excessive. The algorithms involved are all linear time, and in fact experimental results from the paper show that the $IMA$ transform can be computed in a matter of seconds on a modern computer, even on data sets in the tens of millions. An especially nice piece of this: It appears $MB$ is computed along the way (again, Section 2), so if you simply stop the algorithm at that point, you should have an even faster runtime than "a matter of seconds" in practice.


Name a set of program variables I am interested in the set of the variables that satisfy the following properties. I would like to find a proper name for them.

We assume that a program $\phi$ has a set of variables $v_0, \ldots, v_n$. I am interested in a subset $S$ of $\{v_0; \ldots; v_n\}$, that informally speaking impacts the execution of the program (i.e., any execution of its statements). For instance

1) For the statement $v_0 := v_1$ that may be executed, $v_1$ impacts the execution of the statement. Thus, $v_1 \in S$ and $v_1 \in SY$.

2) For the statement $v_0 := v_1 * 0$ that may be executed, $v_1$ impacts the execution of the statement, because if $v_1$  is a string value, the multiplication of string and $0$ raises a type error. Thus, $v_1 \in S$ and $v_1 \in SY$.

3) In the statement "If true Then $v_1$ := 1 Else $v_1$ := $v_2$ End", $v_2$ does NOT impact the execution of the statement, because the else branch of the statement will never be executed; the value of $v_2$ will never be read here. Thus, $v_2 \notin S$, but $v_2 \in SY$.

I will define the semantics properly, but before that I would like to find a proper name for the set $S$ that fits the convention. I am thinking of read variables? input variables? possible input variables? precedent variables? dependancy variables? or supporting variables?

Could anyone help?

Edit 1:

Thanks for all the comments, they are really helpful. I decide to edit the OP to make the question clearer.

Actually, I planed to introduce the notion of a set S about semantics, and then another set SY about syntax that is always a superset of S (because S is hard to analyse). Then, I will make a static analysis to over-approximate SY, thus it over-approximates also S. My question here is about a consistent terminology about S and SY (for the case of read/input).

I have added the case for SY in the 3 examples above. You mentioned another 2 examples:

4) For "If factorial(3)==6 Then v_1 := 1 Else v_1 := v_2 End" (babou), we have $v_2 \notin S$ and $v_2 \in SY$.

5) For "x := x" (Martin Berger), one understanding is that the value of x is first still read, then be assigned to x, so $x \in S$; another understanding is that the value of x does not impact the execution of this statement, so $x \notin S$. I will be OK with both of them (though personally I prefer the latter), as long as if I give a terminology and a definition to S, it is consistent for all the examples. In any case, based on the syntax, we always have $x \in SY$.

Regarding "live variables" (Klaus Draeger), indeed, as babou understood, I am not concerned about "a point in the program regarding what variables are still be needed to finish execution from that point".

Regarding "use-define or use-definition" (babou), from that web page, my understanding is UD is about syntax, and it is what I am going to do with SY (e.g., see what is on the left-hand/right-hand side of an assignment). If I call SY used variables, what should I call S?

This new version of the answer tries to take into account the changes
 in the question, and the information exchanged in the comments.

This answer assumes that $S$ should be the set of variables that have a
content that is used in some defined fragment of the program, rather
than, at some point in the program, the variables with a content that
will be needed before the end of the program.

For the latter, the usual term is live variables, as remarked in a comment by Klaus Draeger.

The former is a generalisation of the concept of use, as appears
in dataflow analysis, and particularly in such concepts as
Use-Define or Use-Definition chains (UD chains), as well as
Definition-Use chains (DU chains). The concept of use is usually
intended for elementary program statements such as an expression
appearing in an assignment or a function call. Recall that this
originates with analysis and optimization of old Fortran programs in
the late 1960s and in the 1970s, and the was no real concept of a
compound statement at the time in the Fortran language.

But there is no reason not to extend the concept to larger program
fragments that form a meaningful whole. Thus used variable or
used set seem to be exactly the concepts and terminology that you
are looking for.

Now, there may be a difficulty in defining what is implied in the
expression "is used by". It may just mean: "syntactically appears in",
which is as simple as you can make it. This is indeed purely
syntactic, but rather non satisfactory, because the variable may well
appear only in a statement that changes its value, rather than use the
value it already has. This is too simplistic is is clearly not what
was intended by the creators of the concept.

Then a better definition will state that the occurrence of a variable
must imply that its value is actually used.  But as soon as you say
that, you are no longer in syntax since you must use some of the
meaning of the program fragment to know whether the occurrence of the
variable is for using or for changing its value (or possibly is simply
irrelevant). And when you start using the semantics of the language
construct, there is no clear limit on how much of the semantics you
can use.

The definition given in page 632 of the Dragon Book 1988 is:

  We say that a variable is used at a statement $s$ if its $r$-value may be required.

First one should note the use of if rather than iff, which clearly
indicates that some variables not meeting the condition may end up
being qualified as used. This even reinforced by the may be.

Then, this almost definition does not bring much light on the issue. What does it mean to
be required. Typically, if a variable is an argument to a subprogram
(procedure, function, method, ...), you may think it is required.  But
if further analysis shows that the value of this argument is not
actually used in the subprogram, and the argument is only used to
return a result, the $r$-value of the variable is not required.  Some
may object that this could be handled by an appropriate type system,
which they consider syntax (I do not).  But the fact that a value is
not required may depend on deeper semantic analysis (such as in
example 4 of the question). Furthermore, the evolution of type systems
and type theory tends to allow inclusion in types of most thing you
may want to say or prove about a variable, which would hardly qualify
as syntactic.

Thus the situation is that there is not really an undisputable
syntactic (?) reference definition of "used variable", and it depends
essentially on an arbitrary choice implied by the set of techniques
used to analyze the program and the level of knowledge it brings
regarding actual use of the variable value at run-time.

On the other hand it is possible to give a reference semantic
definition for a set $S$ of used variables:

  A variable is used in some program fragment iff there is a computation of that program such that the results and effects
     of executing that fragment depend on the value of that variable before execution.

This is not completely satisfactory, because there are other
parameters that could be considered, and might suggest a different
terminology, though not change the above remarks about syntax and
semantics.

For example, in a sequential context, the above definition is clear,
and refers to the value of the variable before executing the program
(fragment).  However, one may still question what is considered an
effect, what is an impact on execution. Execution time could well be
part of the semantics of a program, or not.  Then, in a parallel
execution context, you would consider more than the initial value of
the variable. But I will ignore this, as the question has not been
considering it (as far as I can see), and I will stick to the
definition above.

The set $S$ thus defined semantically is the most precise
(i.e. minimal) set of variables that can matter in any computation,
though some may not matter in some computation.

But this set is not necessarily computable. It is recursively
enumerable, since a Turing Machine could simulate in parallel all possible
computations, and enumerate all the variables that turn out to be used
effectively (in the sense of our definition) in some computation. But
determining that some variable will not be used in a computation is
undecidable.

The best we can hope for is to exhibit a superset of $S$, such that we
are sure not to miss any relevant variable. This is precisely what is
done by the various techniques that can be called upon to determine
the used variables. But they do not all produce the same result and
the results they give can be more or less precise.

If some program analysis technique $T_i$ produces a set $S_i$ of used
variable, we say that $T_i$ is correct iff $S\subseteq S_i$.

If two techniques $T_1$ and $T_2$ produce respectively the sets $S_1$
and $S_2$, then $T1$ is better, more precise than $T_2$ iff
$S\subseteq S_1\subseteq S_2$.

The only thing that has a precise definition (up to the above caveat)
is the set S, enven though possibly not computable. It is also the
reference for any other set to be considered acceptable in practice, and is the smallest, the most precise of them all.

Hence, the expressions "used set" and "used variable" should be
reserved for that set.

And I suggest that the other sets that are considered in practice,
should use the same name, qualified with the name of the technique
that produced them. If the technique is unique and unnamed, it could
be called the computed use set (what is called SYin the question),
or just used set when there is no ambiguity.


Terminology and references for a learning model Let's say we're doing regression over $[0,1]^d$ -- either in the PAC sense with bounded-range agnostic noise or in the more classical-statistics sense with additive Gaussian noise. Suppose further that an additional hindrance stands between the data and the learner: The space $[0,1]^d$ is divided into a grid of cubes with side length $\eta$, and rather than seeing the full labeled sample $(X_i,Y_i)$, the learner only knows how many points $X$ fell into each of the grid cubes and the average of their $Y$ values in that cube.

Questions: 1. Terminology: Is there a name for this learning setting? "Summary" or "aggregate" statistics come to mind, but I want to be consistent with the known literature. 2. Prior results: Either in the PAC or the the additive-noise setting, is anything known? Efficient algorithms, minimax rates?

The related work I know of is experimental, but a similar setup has been called Learning from Label Proportions: https://link.springer.com/article/10.1007/s13278-017-0478-6


Deterministic Büchi + its complement covers LTL? It is well known that deterministic Büchi automata (DBA) are less expressive than non-deterministic Büchi automata (NBA), and in particular DBA are not enough to cover linear temporal logic (LTL). However, the argument often used is that DBA are not closed under complementation - that is there is a language $\mathcal D$ recognized by DBA, but $\mathcal D^c$ is not recognized by any DBA. As an example, $\mathcal D = (b^*a)^\omega$ and $\mathcal D^c = (a+b)^*a^\omega$.

I wonder though, whether for any $\omega$-regular language $\mathcal L$ it holds either $\mathcal L$ is recognized by some DBA, or $\mathcal L^c$ is recognized by some DBA. If not, what is an example of a language which is not recognizable by DBA and which complement is not recognizable either?

From your example, it is easy to derive a language $L$, such that neither $L$ nor its complement is recognized by a DBA.

Take an alphabet of four letter $\{a,b,c,d\}$, and let $L=((a+b)^* a^\omega)+(c^*d)^\omega$. It is not DBA-recognizable because of the $\{a,b\}$-part, and its complement is not because of the $\{c,d\}$-part.

For a less artificial example, you can for instance take on alphabet $\{a,b,c\}$ the language $L$ of words with infinitely many $b$ and finitely many $c$. Both $L$ and its complement have to check that the number of something is finite, so both are not DBA-recognizable.


Removing recursion - a look into theory behind the scenes I am new to this site and this question is certainly not research level - but oh well. I have a little background in software engineering and almost none in CSTheory, but I find it attractive. To make a long story short, I would like a more detailed answer to the following if this question is acceptable on this site.

So, I know that every recursive program has an iterative analog and I kind of understand the popular explanation that is offered for it by maintaining something similar to the "system stack" and pushing environment settings like return address etc. I find this kind of handwavy.

Being a little more concrete, I would like to (formally) see how does one prove this statement in cases where you have a function invoking chain $F_0 \rightarrow F_1 \ldots F_i \rightarrow F_{i+1} \ldots F_n \rightarrow F_0$. Further, what if there are some conditional statements which might lead an $F_i$ make a call to some $F_j$? That is, the potential function call graph has some strongly connected components.

I would like to know how can these situations be handled by let us say some recursive to iterative converter. And is the handwavy description I referred to earlier, really enough for this problem? I mean then why is it that I find removing recursion in some cases easy. In particular removing recursion from pre-order traversal of a Binary tree is really easy - its a standard interview question but removing recursion in case of post order has always been a nightmare for me.

What I am really asking is $2$ questions

(1) Is there really a more formal (convincing?) proof that recursion can be converted to iteration?

(2) If this theory is really out there, then why is it that I find, for eg, iteratizing preorder easier and postorder so hard? (other than my limited intelligence)

You might want to look at the SECD machine. A functional language (though it could be any language) is translated into a series of instructions that manage things such as putting arguments of stacks, "invoking" new functions and so forth, all managed by a simple loop.
Recursive calls are never actually invoked. Instead, the instructions of the body of the function being called is placed on the stack to run.

A related approach is the CEK machine.

These have both been around for a long time, so there's plenty of work out there on them. And of course there are proofs that they work and the procedure for "compiling" a program into SECD instructions is linear in the size of the program (it doesn't have to think about the program).

The point of my answer is that there is an automatic procedure for doing what you want. Unfortunately, the transformation won't necessarily be in terms of things that are immediately easy for a programmer to interpret. I think the key is that when you want to iterize a program, you need to store on the stack what the program needs to do when you return from an iterized function call (this is called a continuation). For some functions (such as tail-recursive functions) the continuation is trivial. For others the continuation maybe very complex, especially if you have to encode it yourself.


What are alternatives to the random oracle model for modelling hash functions? I was looking for more realistic alternatives to the ROM for describing hash functions in theoretical proofs. I came across the common reference string model (where hash functions can be modeled as having been picked from a family of functions). Are there any other?

EDIT -- To make my question less vague: It seemed to me that the ROM or CRS was not modeling what a hash function is in reality and so proofs of security in the ROM model were problematic (considering all real hash functions are deterministic, keyless, and WILL always have collisions that can be found -- facts ignored by ROM and CRS). So I was looking for alternatives.

David Cash pointed out the Rogaway paper that deals exactly with the problem I'd been having. His reply below summarizes how the paper deals with this issue -- i.e., by requiring the explicit knowledge of the collision finding algorithm by an adversary.

(I am interpreting this question in the following way due to the comments.)  In implementations of cryptographic systems, hash functions like the SHA-256 are defined by a deterministic algorithm mapping arbitrary-length bit-strings to some fixed-length bit-strings.  This situation is troublesome for formal analyses (reductions) of these systems because, when modeled in the straightforward way, there is no obvious way to "assume" some important security notions like collision-resistance for such functions.  To be explicit, we might take a function $H:\{0,1\}^* \rightarrow \{0,1\}^{256}$ and say that

  $H$ is collision-resistant if no probabilistic poly-time algorithm outputs distinct $x,y$ such that $H(x) = H(y)$.

Under this definition, no function $H$ is collision resistant:  By the pigeon-hole principle such an $x,y$ exists, and there also exists a constant-time algorithm that outputs them.  (We're leaving aside the additional problem that "probabilistic poly-time" is ill-defined here.)  Most modifications of the definition, like asking for long $x,y$ or something, are unsatisfying.  Let me mention also that some properties are (I believe) achievable, such as when the $x$ is chosen at random and the adversary has to find a $y$ that collides.

But if one models the hash as a keyed function that take an additional key input, then these security notions can be plausibly assumed to be achieved.  Thus we often give security reductions where a keyed hash function is used and random hash key is chosen in the model.  Though this is incongruous with reality, it seems fine.

To better address this disparity, Rogaway in suggested that we forget about the formal assumption per se and instead focusing on the existence of an explicit reduction to doing something with the hash function.  This is exploiting the fact that we apparently don't "know" of an algorithm finding collisions in SHA-256, even though there is a "constant-time" algorithm for doing exactly that.

By the way, the random oracle model generally addresses a different issue:  sometimes we don't have any way to reduce security to any reasonable property of our (keyed or keyless) hash function, so we instead analyze the system in a model where the evaluations of the hash are replaced by evaluations of a random oracle (which everyone can access).  Incidentally, doing this also makes the hash appear to be keyless and thus superficially "closer to reality," but this is in fact not the case:  Now the entire function has become the key, and indeed an exponentially long key.


What's the relation between the dominating set and vertex cover? I wonder if the minimal dominating set is always a subset of the minimal vertex cover in any graph. If so, what's the proof?

Since there is no single minimal dominating set nor minimal vertex cover, I interpret your question as:

  There exist one minimal dominating set $D$ and one minimal vertex cover $C$ such that $D \subseteq C$.

No.

If by any graph you also consider non-connected graphs, then you have a trivial counterexample in $G=(V,E)$ with $V\neq\emptyset$ and $E=\emptyset$,
i.e. at least one vertex and no edges.
The minimal vertex cover is $C=\emptyset$, since there are no edges to cover,
but the only dominating set is $D=V$, and clearly $D\not\subseteq C$.

Even if you restrict it to connected graphs, the answer is still no. Consider the cycle graph $G=(V,E)$ of six vertexes $V=\{a,b,c,d,e,f\}$ and $E=\{(a,b), (b,c), (c,d), (d,e),(e,f),(a,f)\}$.

The vertex cover sets of minimal size have three elements, obtained by skipping one vertex in two: $\{a,c,e\}$ and $\{b,d,f\}$.
The dominating sets of minimal size are obtained with opposing vertexes, $\{a,d\}$, $\{b,e\}$, and $\{c,f\}$.

None of the dominating sets is a subset of any vertex cover set.


Sufficient conditions to guarantee unique fixpoint (not unique least/greatest fixpoint) for monotone functions on complete lattice Tarski's fixpoint theorem states, that the fixpoints of a monotone operator on a complete lattice is a complete lattice. By consequence, we have a unique greatest fixpoint and unique least fixpoint for a monotone operator on a complete lattice.

The fixpoints can be unique but in general can be many.

My question would be, under which conditions can a monotone function have a unique fixpoint on a complete lattice? Is there some practical sufficient conditions to guarantee a unique fixpoint? It would useful to know this, because sometimes you have a monotone operator that specifies a property. It can be non-trivial to spell out whether it is the greatest fix point or the least fix point you really want to specify. In some cases, the two coincide, and you know to iterate from top or from bottom yields the same result and you would be happy to pick up the one that is more simple or more efficient.

Constant functions have unique fixed points. Another criterion that may be applicable is to compare approximations, $\mu_i = \bigcup_{k<i}f^k(\bot)$ and $\nu_i = \bigcap_{k<i}f^k(\top)$, of the least and the greatest fixed points. Trivially, as soon as $\mu_i = \nu_i$ for some $i$, it has been settled that $f$ has a unique fixed point. The problem with this characterization is that, depending on the lattice and $f$, it is incomplete unless you are prepared to explore transfinite approximations.


Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"? While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around:

  Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent to the notion of self-reducibility. This is the case not only due to syntactic considerations, but also due to the following inherent reason. An oracle to any decision problem returns a single bit per invocation, while the intractability of a search problem in $\mathcal{PC}$ must be due to lacking more than a "single bit of information" [...].

For those unfamiliar with Goldreich's text, self-reducibility is used in the sense that a search problem $R$ is Cook-reducible to deciding membership in the respective solution set (i.e., the problem "given $x$, is $x$ a solution to $R$?"). $\mathcal{PC}$ is the class of polynomially verifiable search problems. The text in this chapter appears to be an expanded version of an article intitled "On Teaching the Basics of Complexity Theory" by the same author (Springer, non-paywall link).

Regarding the last quoted sentence, the text refers to an exercise to prove that, for any search problem which is in $\mathcal{PC}$ but not in $\mathcal{PF}$ (i.e., the class of search problems for which the solution can be found in poly-time) and which is self-reducible, the respective (Cook-)reduction performs at least (asymptotically) log queries to its oracle. (The proof is also not hard; if using only log queries, then the oracle may be replaced by a brute force subroutine without affecting the reduction's poly-time complexity.)

My question is two-fold:

What does Goldreich mean by "syntactic considerations"? Does he simply mean it is cumbersome to define self-reducibility by other means than using reductions?
What relation does the exercise referred to in the text have to the claim regarding "lacking more than a 'single bit of information'"? (After all, the exercise is about log many queries, not a single one.) And what does this have to do with the inherentness of reductions to self-reducibility?

I assume Goldreich is alluding to widely-known facts here. Apologies if this can only be answered by the man himself.

I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (in the sense Goldreich uses it), but rather about Cook reductions being inherent to this notion, in the sense that they cannot be replaced by  Karp reductions. Goldreich makes a distinction between a "general notion of reduction", meaning a Cook reduction, and the restricted notion of a Karp reduction. Then he points out that the fact that Cook reductions in his definition of self-reducibility cannot be replaced by Karp reductions is not merely because of some formality (i.e. "syntactic considerations") but is inherent because a Karp reduction only makes a single query to the decision problem oracle, and, hence, only reveals "a single bit of information". The exercise shows that many more than a single bit of information need to be revealed (log many bits, as you point out).


Church-style CoC with axiom for induction over Church-encoded unit, is it consistent? If we start with the Calculus of Constructions, and then use the following definitions for the Church-encoded Unit:

UnitType = (t : *) -> t -> t
Unit = \(t : *) (x : t). x

And the add the following construct indUnit:

G |- P : UnitType -> *
G |- pu : P Unit
G |- u : UnitType
--------------
G |- indUnit P pu u : P u

With reduction rule:

indUnit P pu Unit ~> pu

Basically this adds induction over the Church-encoded unit type.

Is this consistent?
If we change the reduction rule to:

indUnit P pu x ~> x (P x) pu (if x is a closed term)

Is it still consistent?

It seems to me that this is consistent.

Yes, it's consistent. Probably the easiest account is in my 2013 CSL paper with Derek Dreyer, Internalizing Parametricity in the Extensional Calculus of Construction, which is all about adding this style of parametricity axiom to the CoC.


Is this a known combinatorial optimization/scheduling problem? We are given $n$ stacks which hold "items" of different colour and a machine that can process multiple items of the same colour in one go. At each step, we can remove one item from the top of each stack and put it into our machine (so effectively the machine can process at most $n$ items in one step - for that to happen, all stacks must have items of the same colour on top). The goal is to process all items in minimal time.

Example input:

One possible solution is a greedy algorithm: at each step, just take as much items as possible and stuff them all into the machine. Unfortunately, the greedy algorithm is not optimal - it produces the following schedule for the example input:

The optimal schedule is the following:

I plan to go with some form of state space search, but maybe there is a more problem-specific and efficient approach? Links to relevant literature appreciated.

Your problem is equivalent to Shortest Common Supersequence (SCS) and was considered in $[1]$ by the name Scheduling on batch machines with precedence constraints as chains and compatibilities. If items in the problem are of the same color then such problem is in P and can be solved in $O(n^2)$  $[2]$.

What concerns approximability a good source is A compendium of NP optimization problems.

The lastest results on SCS can be found in $[3,4]$.

For practical algorithms see $[5]$ whose author states that "Hybrid MA-BS is a current state-of-the-art technique for the SCSP $[6]$ ".

Brauner N., Naves G. Scheduling chains of operations on a batching machine with disjoint sets of operation compatibility.
Brucker P. Scheduling algorithms (Chapter 8. Batching Problems).
Timkovsky V. G. Some Approximations for Shortest Common Nonsubsequences and Supersequences.
Gotthilf Z. and Lewenstein M. Improved Approximation Results on the Shortest Common Supersequence Problem.
Kubalik J. Efficient stochastic local search algorithm for solving the shortest common supersequence problem.
Blum, C., Cotta, C., Fernandez, A. J., Gallardo, J. E. A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem.


How to generate graphs with known optimal vertex cover I'm looking for a way to generate graphs so that the optimal vertex cover is known. There are no restrictions on the number of nodes or edges, only that the graph is completely connected.

the idea is to generate a graph that's not easy to find the optimal vertex cover, to be able to test different heuristics on it

I found the paper Arthur, J. & Frendeway, J. Generating Travelling-Salesman Problems with Known Optimal Tours, The Journal of the Operational Research Society, Vol. 39, No. 2 (Feb., 1988), pp. 153-159 for generating TSP with known optimal, alas I cannot access it.

Is there a known algorithm?

Expanding vzn's comment into an answer: The standard reduction from CNF-SAT to vertex cover is pretty easy: make a vertex for each term (variable or its negation), connect each variable to its negation by an edge, make a clique for each clause, and connect each vertex in the clique to the vertex for one of the terms in the clause. If you start with a satisfiability problem with a known satisfying assignment, this will give you a vertex cover problem with a known optimal solution (choose the term vertices given by the assignment, and in each clause clique choose all but one vertex, so that the clause vertex that is not chosen is adjacent to a term vertex that is chosen).

So now you need to find satisfiability problems that have a known satisfying assignment but where the solution is hard to find. There are many known ways of generating hard satisfiability problems (e.g. generate random k-SAT instances close to the satisfiability threshold) but the extra requirement that you know the satisfying assignment restricts the possibilities. One thing you can do here is go through another level of reduction, from a cryptographically hard problem such as factorization. I.e. choose two large primes p and q, set up a Boolean circuit for multiplying p and q as binary numbers, and translate it into a CNF formula in which there is a variable for each input (p and q) and for each intermediate value on a wire in the circuit, a clause for each output forcing it to have the right value, and a clause for each gate forcing the inputs and outputs of the gate to be consistent with each other. Then translate this CNF formula into vertex cover.

For a simpler strategy, choose the satisfying assignment to a 3CNF formula first, and then generate clauses at random, keeping only the clauses that are consistent with the assignment, and then convert to vertex cover. If the clauses have uniform probability this will be vulnerable to a degree-based heuristic (the term vertices that match the chosen assignment will have lower degree than the term vertices that do not) but this shortcoming can be avoided by adjusting the probabilities of the clauses according to how many of the clause's terms agree with the chosen assignment. Probably this is vulnerable to some kind of polynomial time attack but it might not be one that's natural for vertex cover, so it might make a good set of test instances despite not having much guarantee of hardness.


Is Clique completion for intersection models hard? The following seems like a natural problem and I'm surprised I can't find any literature on it... but maybe it's because I don't know the name for it.

Given a list of sets $S_1, S_2, S_3, \ldots$
Can we make $k$ additions (that is, adding an element to any single $S_i$ ) so that every pair of sets has nonempty intersection?

If we treat each subset $S_i$ as a vertex and say two vertices are adjacent if their corresponding sets have at least one common element, this is like an intersection model for a graph and we are augmenting the representation to turn the graph into a clique. I think of this as some sort of "clique completion" problem, but I don't know if it has been studied in another context under a different name.

Does anyone know of this problem?

Good question. I hope this is not a homework problem.

I don't know if this problems exists in the literature, so let's call your problem Min Set Clique Completion Problem (MSCC). Here is a reduction from Hitting Set Problem to MSCC. Hitting Set problem is a well-known NP-complete problem.

Instance of Hitting Set problem is as follows : Let $U = \{1,2,\dots,n\}$ be the ground set. Let $T_1, T_2, \dots, T_l$ be $l$ subsets of $U$. Find a set $H \subseteq U$ that has at least one element from each set $T_i$. The goal is to minimize $|H|$.

We construct an instance of MSCC with $U' = U \cup \{n+1\}$ and sets $S_1, S_2, \dots, S_{l+1}$ such that for $1 \leq i \leq l$, $S_i = T_i \cup \{n+1\}$ and $S_{l+1}$ is an empty set. (Edit : this is wrong as pointed out in the comment.)
We construct an instance of MSCC with $U' = U$ and sets $S_1, S_2, \dots, S_{l+1}$ such that for $1 \leq i \leq l$, $S_i = T_i$ and $S_{l+1}$ is an empty set (Edit : Use this along with Karolina's fix in the comments).

Now if we run MSCC on this instance the solution $S_{l+1}$ returned by MSCC is precisely the hitting set of the sets $T_1, T_2, \dots, T_l$.


Complexity of edge coloring in planar graphs 3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable".

  What is the complexity of 3-edge coloring of cubic planar graphs?

Also, It is conjectured that $\Delta$-edge coloring is $NP$-hard for planar graphs with maximum degree $\Delta \in${4,5}.

  Has any progress been made towards resolving this conjecture?

Marek Chrobak and Takao Nishizeki. Improved edge-coloring algorithms
for planar graphs. Journal of Algorithms, 11:102-116, 1990

Every bridgeless planar cubic graph can be 3-edge-colored in quadratic time, as this task is equivalent to four-coloring a planar graph, which can be done in quadratic time. (See Robertson, Sanders, Seymour and Thomas: http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps )

EDIT: As Mathieu points out, cubic graphs with bridges are never 3-edge colourable.


Subset product problem We have $m$ list of integers $L_1,\dots,L_m$ and each list $L_i$ contains $n$ distinct integers $L_i(1),\dots,L_i(n)$.

You are given two integers $a$ and $b$ with $b<a$ and we know $n=O(2^{(\log b)^\alpha})$ and $m=O({(\log b)^\beta})$ for $0<\alpha,\beta<1<\alpha+\beta$.

I want to check to see if I can pick one integer from each list to check if product mod $b$ is $a\bmod b$.

Is there a faster than $n^m$ brute force way to search for this? Is this NP hard (Andrew below sort of gives a pseudo polynomial algorithm)?

Let $S_0=\{1\}$. For $i = 1,...,n$, set $S_i\gets \{xy\mod b : x\in S_{i-1},y\in L_i\}$. Then just check whether $a \in S_n$.

It's obviously correct, since $S_i$ contains the residues which can be expressed as a product of elements, one each from $L_1,\ldots,L_i$.

Just using the definition of $S_i$ to compute it, you get a running time of $O(m n b)$, which is significantly better than brute force when $b$ is smaller than $n^m$.

By replacing the linear sweep by divide and conquer, you might be able to improve the running time even more, though I didn't check. (It will still have a factor of $b$ though.)


Finding a path with certain properties in a directed graph Define a directed graph $G(V,E)$. We divide its vertex set $V$ into $t$ partitions: $p_1, p_2, \ldots, p_t$. Suppose we have a path $v_1 \to v_2 \to v_3 \to \ldots \to v_n$ where the same vertex can be visited multiple times.

We define the valid point of partition $p_i$ as the last point $\in p_i$ appearing in the abovementioned path. For example, if the path goes through $y, x, z$ and $y, x, z \in p_i$ holds, the valid point of $p_i$ is $z$.

Given $k$ vertices as input (we guarantee that these $k$ vertices belong to different partitions), if there exists an $s-t$ path, such that all these $k$ vertices are all valid points of their respective partitions.

Can we find a polynomial-time algorithm?

If all partitions contain only a single vertex and you're given all of them as your initial set of $k$ vertices then the path you seek must be a Hamiltonian path. So it's NP-complete.

However, it's fixed-parameter tractable when parametrized by $t$ — it can be turned into a reachability problem on a larger graph where each vertex is a pair $(S,v)$ of a set $S$ of the partition sets whose valid point has already been passed and a vertex $v$ of the original graph. So the time is $O(\binom{t}{\le k}(m+n))=O(2^t(m+n))$.


Papers on fault handling in distributed systems What papers on handling errors in distributed systems do you recommend?

You might want to have a look at the works that won Tushar D. Chandra, Vassos Hadzilacos, and Sam Toueg the Edsger W. Dijkstra Prize in 2010:

Tushar D. Chandra and Sam Toueg. Unreliable Failure Detectors for Reliable Distributed Systems, Journal of the ACM, 43(2):225-267, 1996
Tushar D. Chandra, Vassos Hadzilacos and Sam Toueg. The Weakest Failure Detector for Solving Consensus, Journal of the ACM, 43(4):685-722, 1996.

These papers introduce the notion of failure detectors in a distributed system in a general and precise framework. Intuitively, they tried to study the minimal amount of failure information needed to solve consensus. It turns out that you don't need a perfect failure detector to solve consensus. Even unreliable failure detectors satisfying certain minimal conditions will suffice for the task. These papers were very influential on how to deal with failures in distributed systems.


Practical/heuristic algorithm for multi set-cover Consider a universe $N$ containing $n$ elements, and a collection of sets $\mathcal{C}$, over $N$. The $k$-multiset multicover (MSMC) problem is to cover all elements of the universe $N$ at least $k$ number of times using minimum number of sets from $\mathcal{C}$. (When $k=1$, the problem reduces to min-set cover).

Are there any heuristics out there with 'good' performance on 'real' data for $n=1000$ and $|\mathcal{C}| = 1000$?

You'd have to tweak the limits (in particular max_level may be too low), but for at least some "real" problems this is within the bounds of Knuth's algorithm M.

See also

The documentation of algorithm D, which describes the basic file format; the documentation of algorithm M just explains the changes made to generalise it;
the latest preprint of fascicle 5c of The Art of Computer Programming, which at some point will get as far as explaining the algorithm, but already has a number of exercises that will give you an idea of the problems that Knuth has solved with it.


Is there good open source project that apply semantic web, modal logics, and similar technologies Recently such themes as semantic web, modal logics, business rules have seen increased interest as research topics in computer science (alhough many of then have more than 80 years of history), but are there any open source projects (even better if they are actively used in commercial applications as well) that use these technologies and where one can participate and get new challenges for research?

I have found a lot of research projects (e.g. satisfiability solvers, logic programming environments) but at present I don't know many succesfull applied applications. There have been few reports on some of them in the jornal of "Theory and Practice of Logic Programming" - mostly about solving scheduling problems with logic programming methods. But maybe there is some open source projects as well?

Sometimes it seems to me that modal logics (semantic web is part of them) and logic programming gives false impression about their power and their generality has few applications, e.g. the concrete algorithms of integer programming or scheduling are more powerfull and ready for applications than general methods suggested by the former ones.

Not open source, but the AI engines of some successful computer games are based on modal logic, see e.g. "Using Exclusion Logic to Model Social Practices" and "Introducing Exclusion Logic as a Deontic Logic"  by Richard Evans.


Approximating Max-Coverage when the elements need to be covered multiple times In the set multicover problem we are given a set N of n elements and a set S of m subsets of N. Additionally, each element has a coverage requirement, i.e. the number of times it has to be covered. The question is to cover N with the minimum number of subsets from S. I'm aware of the approximation algorithms for this problem (Rajagopalan & Vazirani).

I'm interested in a different version of the problem (max multi-coverage). We are given K and we ask for the maximal number of the elements from N we can cover with K subsets from S. We count an element as covered if it is covered at least the required number of times. Are there any approximation algorithms for this case? Are there any lower bounds for this case (or even for the standard set multicover problem)?

Thanks in advance!

If the required number of times we need to cover an element is 2, we have the following densest k-subgraph problem: (Imagine the edges are elements and nodes are sets.)

  Given a graph $G$ and an integer $k$, find a subgraph of $G$ on $k$ nodes with maximum density.

Khot proved that no PTAS exists under plausible complexity assumptions; there is an $O(n^{1/4+\epsilon})$ approximation to the problem by Bhaskara, Charikar, Chlamtac, Feige and Vijayaraghavan; a polynomial integrality gaps result by Bhaskara, Charikar, Guruswami, Vijayaraghavan and Zhou.  Therefore I believe your question is hard to approximate in the most general case.


Least fixed point logic is efficiently $\operatorname{P}$-bounded for $\operatorname{P} \Leftrightarrow L_\leq$ is a logic for $\operatorname{P}$ A least-fixed point (LFP) formula is $\leq m$-invariant iff f.a. structrues $\mathcal{A}$ with $|A| \leq m$ and all orderings $<_1,<_2$ on $A$

$$(\mathcal{A},<_1) \models_{LFP} \varphi \Leftrightarrow (\mathcal{A},<_2) \models_{LFP} \varphi.$$

The logic $L_\leq$ is defined such that the modelling-relation is

$$ \mathcal{A} \models_{L_\leq} \varphi \Leftrightarrow \varphi \textrm{ is $\leq |A|$-invariant and } (\mathcal{A},<)\models_{LFP}\varphi \textrm{ for some} <.$$

A logic $L$ is efficiently $\operatorname{P}$-bounded for $\operatorname{P}$ if

for each $Q \in \operatorname{P}$ there is a $\varphi \in L$ which axiomatizes $Q$
for each $\varphi \in L$ there is polynomial $p$ such that the modelling
relation $\mathcal{A} \models_L \varphi$ can be decided by an algorithm in
$\leq p(\|\mathcal{A}\|)$ steps

A known result is that LFP is an efficiently $\operatorname{P}$-bound logic for $\operatorname{P}$ on the class of ordered structures. A paper states that one can easily deduce from the result that $L_\leq$ is a logic for $\operatorname{P}$. Any ideas how?

People informally use the phrase "a logic for P" for the notion of a logic that captures P, which corresponds to Chen and Flum's definition of a "P-bounded logic for P". Essentially, this means that the logic defines exactly the polynomial-time properties of relational structures and formulae can be evaluated in polynomial time.1 Specifically, it's no use if your logic defines exactly the polytime properties but it takes exponential time to figure out whether a formula's true.

I think the confusion has arisen because Chen and Flum use the phrase "a logic for P" to mean just any logic that defines exactly the polytime properties of structures, without the requirement that formulae can be evaluated in polytime.  The logic $L_\leq$ is a logic for P in this specific sense.  Every polytime property is definable by a formula $\phi\in L_\leq$ but the semantics of the logic requires testing whether $\phi$ is $|A|$-invariant and there is no known way to do that in polynomial time.

$L_\leq$ defines all polytime properties because, by the result of Immerman and Vardi cited by Chen and Flum, LFP captures P on the class of ordered structures. More specifically, any ordering of the structure's universe lets you use tuples in $A^k$ to represent $k$-digit numbers in base $|A|$, which you can use as both for timestamps and to say "the $i$th character on the tape is $c$. You can then use a fixed-point formula that says, "If the configuration at time $t$ is $C_t$, then the configuration at time $t+1$ is $C_{t+1}$. The resulting formula doesn't depend on which ordering is chosen, so it's order-invariant, as required. Choosing a different ordering is just permuting the meaning of the digits in your base $|A|$ numbers.

Note that order-invariance in general is not decidable, which is why Chen and Flum restrict to order-invariance only on structures up to the size of the one we're evaluating the formula on. That's decidable but not known to be in P.  (But the formulas constructed above are, in fact, order-invariant across all structures.)

1 More formally, for every formula $\phi$, there is a deterministic algorithm and a constant $k$ such that the algorithm decides whether $\cal{A}\vDash\phi$ in time at most $|A|^k$.


Can NP-hard statements be proved by PCPs that only involve reading 2 bits? For non-negative integers q, let PCP(q) denote the set of promise problems

that have polynomial-length probabalistically checkable proofs

over the binary alphabet in which the verifier only reads q bits.

(with no restriction on the amount of randomness that the verifier can use)

Let sPCP(q) denote the analogous class in which the verifier has

perfect completeness and chooses the bits to read non-adaptively.

(sPCP stands for "strong PCP", a term I made up for this question)

Obviously, $\:$PCP(0) = promiseBPP$\:$.

It is slightly less obvious, but still easy to show, that $\:$PCP(1) = promiseBPP$\:$.

It is known, though highly non-trivial, that $\:$NP $\subseteq$ sPCP(3)$\:$.

Since $\:$2SAT $\in$ P$\:$, $\:$ one has $\:$sPCP(2) $\subseteq$ promise-coRP$\:$ by reasoning similar to the PCP(1) equality.

However, that does yield any comparison between PCP(2) and NP.

  Is either $\;\;\;$NP $\subseteq$ PCP(2) $\:$ or $\:$ PCP(2) $\subset$ NP$\;\;\;$ known to hold under plausible assumptions,

  such as the promise versions of $\:$ P = BPP $\subset$ NP = MA ≠ coNP $\:$ ?

Such a characterization of NP follows from the NP-hardness of any gap problem for a binary CSP with constraints of arity 2.

A binary CSP with arity 2 constraints is given by a family $\Pi$ of arity 2 relations on $\{0, 1\}^n$. An instance is given by a set of constraints. The GapCSP$_\Pi$($c$,$s$) problem for the CSP is the promise problem of distinguishing between CSP instances where at least a fraction $c$ of the constraints can be satisfied and instances where at most a fraction $s$ of the constraints can be satisfied. If such a GapCSP$_\Pi$($c$, $s$) problem is NP-hard for constants $c > s$, then we get a 2-bit PCP for NP in the usual way: the proof is a variable assignment, and can be verified by sampling a constraint and checking if it is satisfied.

In Some Optimal Inapproximability Results, Håstad shows that the GapCSP$_\Pi$($\frac{3}{4} - \delta$, $\frac{11}{16} + \delta$) problem is NP-hard for any constant $\delta$ when $\Pi$ is the family of constraints of the type $x_i + x_j = c \pmod 2$. There are two components to the reduction:

the famous optimal hardness of 3-variable linear equations mod 2: $\text{GapCSP}{_\Pi}$($1 - \delta'$, $\frac{1}{2} + \delta'$) is NP-hard for any constant $\delta'$ and $\Pi$ the family of constraints of the type $x_i + x_j + x_k = c \pmod 2$ (equivalently, this is a result about optimal 3-bit PCP for NP)
a gadget reduction from 3-variable linear equations to 2-variable linear equation; each 3-variable equation is replaced by sixteen 2-variable equations over the original variables and some auxiliary ones, so that if the original equation is satisfied, then 12 of the new equations can be satisfied by some assignment of the auxiliary variables, and if the original equation is not satisfied, then no assignment of the auxiliary variables satisfies more than 10 of the new equations (Theorem 5.14 in the paper)

You can get a better ratio between $c$ and $s$ if you assume the Unique Games conjecture: Khot, Kindler, O'Donnel, and Mossel showed that for $\Pi$ the max cut constraints $x_i \neq x_j$, solving GapCSP$_\Pi$($\frac{1}{2}(1 - \rho)$, $\frac{1}{\pi}\arccos(\rho) - \delta$) is as hard as Unique Games for any $\rho \in (-1, 1)$ and any constant $\delta > 0$. Optimizing over $\rho$ gives $\frac{s}{c}$ arbitrarily close to the Goemans-Williamson constant.


What Topics Are Suggested for Ph.D. Research? Since this community seems to include a lot of Ph.D. students, and because there is a provision for attracting even more, I think this question is very appealing:

  What topics do you suggest for Ph.D. students to consider for their thesis?

I intentionally didn't restrict the topic to any field in TCS.

Obviously, very broad subjects of study, such as "logic" or "complexity theory" are not adequate answers.

On the other hand, ideas like "combine logic X with Y algebra to solve problem Z" are completely acceptable. (Since this is not MathOverflow, "problem Z" should have some TCS flavor.)

The more you elaborate, the better!

It is an extremely broad question, and probably the wrong question, but I actually think the answer is pretty short. I'll just give you the advice that I was given (from multiple people), and the advice that most people I know would give:

http://matt.might.net/articles/phd-school-in-pictures/

In other words, you start with an interest, and that interest develops into a specialty. You deepen that interest, and then you expand a small amount on it in your PhD. Telling you what to do not only in some ways would defeat the purpose of you actually getting a PhD (i.e., you picking a specialty and pursuing it because you like it), but it says some pretty strong things about a PhD: that is, I personally think it's more helpful to think of a PhD not as the crowning achievement of your career, but as a good start, and since yours will almost certainly not be revolutionary (like, say Syntactic Structures), it is much more descriptive to explain the process than it is to tell you what specifically to do.

Good luck, though!