Rephrasing as a set system, each row represents a subset $E_i$ of some set $X$, for $i=1,2,\dots,m$. You want a set $Y \subseteq X$ with at most $k$ elements, such that $E_i \cap Y \ne \emptyset$ for ...

The eccentricity of a vertex $v$ is the length of a longest shortest path starting from $v$. The diameter is the maximal eccentricity over all vertices. Any BFS from a vertex will establish its ...

It sounds like you are interested in all-different constraints (and your last sentence is on the right track). These are non-trivial instances of the pigeonhole principle, where the number of pigeons ...

I am still unclear about the precise objective you want to optimise over, but you could look at Peter Brucker, Andreas Drexl, Rolf Möhring, Klaus Neumann, and Erwin Pesch, Resource-constrained ...

Thank you for the interesting question! First, let's consider the easy part. Given that you want the distances from every vertex for all distances, you are asking for all-pairs shortest paths. ...

Mayr and Clemente have shown that it is often possible to simplify NFAs. Their techniques rely on pruning the underlying labelled transition system via local approximations of trace inclusions. As ...

Consider $p=2q$, $q\ge 1$. Asymptotically, the quantity you are after is $2^{4q-2}$. First, let's prove a lemma of general interest. Lemma $(2^{2q}/\sqrt{\pi q})/1.136 < \binom{2q}{q} < 2^{2q}... View answer 2 votes Immunity seems to make your problem easier in one sense, as it means that infection can be modelled by a process that terminates after a linear number of infection attempts. The stipulation that the ... View answer 3 votes As pointed out by the OP (user13772), this is false. Jukna et al. constructed explicit Boolean functions$f$that require deterministic decision trees of size$2^{\Omega(\log^2 N)}$, where$N$is the ... View answer Accepted answer 6 votes There is clearly an algorithm, since the finite search space can be explored using brute force. This takes a long time... Instead of considering$f \colon \{0,1\}^n \to \{0,1\}^n$, one can look at ... View answer Accepted answer 5 votes This has been called the microstructure complement when the edges represent the forbidden partial assignments. I personally prefer the term clause structure. The clause structure of a constraint ... View answer 5 votes A better lower bound when$p=1$is$n \log n - n (\log \log n + 3/2)$bits, where$\log = \log_2$. (The$3/2$term can be made arbitrarily close to$1$for large enough$n$, and asymptotically it is$...

You ask why database aggregations have monoidal structure. Say we want to combine data values $a$ and $b$, but want to keep things general -- these may be integers, strings, floating point numbers, ...

From page 52 of Leonid Libkin's Elements of Finite Model Theory textbook: Since we know that graph connectivity is not Hanf-local and transitive closure is not Gaifman-local, we immediately obtain, ...

Database theory is a sprawling field providing many applications of logic. Descriptive complexity and finite model theory are closely associated fields. As far as I can tell, these areas all tend to ...

Notwithstanding Friedgut's theorem about $k$-SAT, while we lack techniques to get to negligible $\epsilon$ for small $k$, it seems more useful to talk about the satisfiability threshold ($\alpha - \... View answer 4 votes Reduce Garey & Johnson problem [SS8], Multiprocessor Scheduling, to your problem. This is NP-complete, even if$m=2$. In this problem there are no overlaps, and a deadline is specified. Your ... View answer 15 votes Several graph products can be recognized in polynomial time. As usual the Cartesian product is the easiest, and the Cartesian case is also the basis for the algorithms for several other products. ... View answer 12 votes Here are two applications from a different part of TCS. Semirings are used for modelling annotations in databases (especially those needed for provenance), and often also for the valuation structures ... View answer Accepted answer 15 votes As Massimo Lauria states, problems of the form CSP($\Gamma$) are rather special. So there is no contradiction. Any constraint satisfaction problem instance can be represented as a pair$(S,T)$of ... View answer 4 votes The biggest "advance" in relational databases has been the cleaving apart of the monolithic RDBMS model into discrete components, that are then put together in novel ways. These include data stores ... View answer Accepted answer 11 votes The problem of determining whether there is an equivalent CNF formula with at most a given number of literals is$\Pi_2^p\$-complete. The version minimizing the number of clauses is within a factor of ...

There does not seem to be a general algorithm. Checking whether two Datalog programs are equivalent (in the sense of producing the same output database for every possible input database) is ...

The question you begin with relates to predicting the stock market, but you seem to have broader concerns. I'll attempt to tackle your meta-question; apologies in advance for my sweeping ...

Another strict hierarchy: branching programs which only test each bit a limited number of times. The more tests are allowed, the larger the class of branching programs. Usually the branching programs ...

As Walter says, clauses of 2-SAT have a special form. This can be exploited to find solutions quickly. There are actually several classes of SAT instances that can be decided in polynomial time, and ...

Collaborative bibliography managers such as Mendeley and CiteULike have been around for several years, but have not yet caught on in the theory community (at least, they include a vanishingly low ...

Many people have tried to find an algebraic language to describe the shape of a graph. This question is essentially the one that motivates structural graph theory. At the heart of this area of ...