András Salamon
  • Member for 11 years, 5 months
  • Last seen more than a week ago
Binary matrix column subset selection complexity
Accepted answer
8 votes

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 ...

View answer
Graph classes for which the diameter can be computed in linear time
Accepted answer
9 votes

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 ...

View answer
An easy case of SAT that is not easy for tree resolution
Accepted answer
10 votes

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 ...

View answer
Capacity planning algorithm resources
1 votes

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 ...

View answer
Number of vertices at distance $k$ for each vertex of restricted sparse graph
Accepted answer
6 votes

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. ...

View answer
Simplification of weighted NFA
2 votes

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 ...

View answer
Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$
Accepted answer
3 votes

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
An algorithm for calculating the probability of a disease spreading through a graph
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
Size of decision tree for f is polynomial in the DNF size of f and CNF size of f
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
Inferring simplest method to convert bit array 1 to bit array 2
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
How is this graphical representation of SAT/CSP instances called?
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
Lower bound of checking graph connectivity on stream
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 $...

View answer
How do database aggregations form a monoid?
Accepted answer
14 votes

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, ...

View answer
How do you argue a query is impossible in a query language like SPARQL or SQL?
Accepted answer
5 votes

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, ...

View answer
Pointers for CS applications of logic
7 votes

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 ...

View answer
Current tightest bounds for critical 3-SAT density
17 votes

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
Is this multiprocessor scheduling problem with overlaps NP-Hard?
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
Complexity of "is a graph a product"
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
Uses of algebraic structures in theoretical computer science
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
Ladner's Theorem vs. Schaefer's Theorem
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
What are recent advances in relational databases?
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
Shortest Equivalent CNF Formula
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 ...

View answer
Minimize a datalog program
6 votes

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 ...

View answer
Computational complexity in quantitative finance
Accepted answer
9 votes

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 ...

View answer
What hierarchies and/or hierarchy theorems do you know?
9 votes

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 ...

View answer
Why is 2SAT in P?
20 votes

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 ...

View answer
What is the best place to get BibTeX entries for computer science articles ?
3 votes

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 ...

View answer
Are there any 'graphical' algebras that can describe the 'shape' of graphs?
Accepted answer
6 votes

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 ...

View answer
Gröbner bases in TCS?
12 votes

Gröbner bases have been applied to constraint satisfaction problems (see this grant). At this point Gröbner basis techniques do not appear to be useful for the applications of constraint satisfaction,...

View answer
Is the MapReduce framework a type of BSP?
5 votes

Yes, my opinion is that classical MapReduce is a BSP model (and therefore has its inherent limitations on the maximum possible parallel performance that can be achieved). However, newer work on ...

View answer