texts: Maximal classes for which largest independent set can be found in polynomial time?

texts:
The ISGCI lists over 1100 classes of graphs.  For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes.  I would like to compile a list of maximal IS-easy classes.  These classes together form the boundary of (known) tractability for this problem.

Since one can just add a finite number of graphs to any infinite IS-easy class without affecting tractability, some restrictions are in order.  Let's restrict the classes to those that are hereditary (closed under taking of induced subgraphs, or equivalently, defined by a set of excluded induced subgraphs).  Moreover, let's consider only those families that are X-free for a set X with a small description.  There might are also be infinite ascending chains of tractable classes (such as $(P,\text{star}_{1,2,k})$-free and the classes described by David Eppstein below), but let's restrict attention to classes that have actually been proved to be IS-easy.

Here are the ones I know of:

perfect graphs
$(P,\text{star}_{1,2,5})$-free
$(K_{3,3}-e, P_5)$-free
co-Meyniel
nearly bipartite
chair-free
($P_5$,cricket)-free
$(P_5,K_{n,n})$-free (for any fixed $n$)
$(P_5, X_{82}, X_{83})$-free

  Are other such maximal classes known?

Edit: See also a related question asked by Yaroslav Bulatov dealing with classes defined by excluded minors what is easy for minor-excluded graphs? and see Global properties of hereditary classes? for a more general question I asked previously about hereditary classes.

As Jukka Suomela points out in comments, the minor-excluded case is also interesting (and would make an interesting question), but this is not the focus here.

To avoid David's example, a maximal class should also be definable as the X-free graphs, where not every graph in X has an independent vertex.

Classes given in answers below:

apple-free (suggested by Standa Živný)
($P_5$,house)-free (suggested by David Eppstein)
($K_2 \cup$ claw)-free (suggested by David Eppstein)

Added 2013-10-09: the recent result by Lokshtanov, Vatshelle and Villanger, mentioned by Martin Vatshelle in an answer, supersedes some of the previously known maximal classes.

In particular, $P_5$-free being IS-easy subsumes ($P_5$,cricket)-free,
($P_5$,$K_{n,n}$)-free,
($P_5$,$X_{82}$,$X_{83}$)-free, and
($P_5$,house)-free
all being IS-easy.

This means that all the hereditary graph classes defined by a single forbidden induced subgraph with up to five vertices can now be definitively classified as IS-easy or not IS-easy.

Unfortunately the proof that $P_5$-free graphs form an IS-easy class does not seem to work for $P_6$-free graphs, so the next frontier is to classify all the hereditary graph classes defined by a single six-vertex graph.

I remain especially interested in IS-easy classes of the form $X$-free for some collection $X$ of graphs with infinitely many isomorphism classes, yet where $Y$-free is not IS-easy for any $Y \subset X$.


texts: Logic Programming: Transforming B:-A C:-A to B,C:-A

texts:
I hope I've come to the right place... it's (probably) a fairly straightforward Logic Programming question.

If I have two clauses of the form:
B:-A C:-A
I can transform these into:
B,C:-A

(Edit: where B,C is a conjunction. I'm doing bottom-up evaluation and it's useful to me to represent multiple clauses with the same body using one clause with a conjunction of the respective heads. This seems trivial, but I'm wondering if there's a name for such a transformation—however, I know that the resulting clause is no longer a Horn clause.)

Does anyone know if this transformation has a name, and if so, can anyone provide a pointer (preferably online) to somewhere that describes it.

Many thanks (from a n00b).


texts: Data representation affecting problem complexity

texts:
Given some problem, could you have a situation where the problem is shown to be in P, assuming you start with a particular representation of the problem and some data structures, but that if the problem data was represented in some other way then the problem would become NP? (or some other complexity classes)

In other words have any problems been stated to be in P when this depends on the input data being formatted in a way that a would-be algorithm-user wouldn't necessarily have available so the complexity of the problem becomes drastically changed by needing to convert the data first?

This question comes from wondering how knots can be represented and wondered how this would affect comparing whether two knots are the same?


texts: Bounds on the size of the smallest NFA for L_k-distinct

texts:
Consider the language $L_{k-distinct}$ consisting of all $k$-letter strings over $\Sigma$ such that no two letters are equal:

$$
L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]: \sigma_i\in\Sigma ~\text{ and }~ \forall j\ne i: \sigma_j\ne\sigma_i \}$$

This language is finite and therefore regular.  Specifically, if $\left|\Sigma\right|=n$, then $\left|L_{k-distinct}\right| = \binom{n}{k} k!$.

What is the smallest non-deterministic finite automaton that accepts this language?

I currently have the following loose upper and lower bounds:

The smallest NFA I can construct has $4^{k(1+o(1))}\cdot polylog(n)$ states.
The following lemma implies a lower bound of $2^k$ states:

  Let $L ⊆ Σ^*$ be a regular language.  Suppose there are $n$ pairs $P = \{ (x_i, w_i) \mid 1 ≤ i ≤ n \}$ such that $x_i\cdot w_j \in L$ if and only if $i=j$.  Then any NFA accepting L has at least n states.

Another (trivial) lower bound is $log$$n\choose k$, which is the log of the size of the smallest DFA for the language.

I am also interested in NFAs that accept only a fixed fraction ($0<\epsilon<1$) of $L_{k-distinct}$, if the size of the automaton is smaller than $\epsilon\cdot 4^{k(1+o(1))}\cdot polylog (n)$.

Edit: I've just started a bounty that had a mistake in the text.

I meant we may assume $k=polylog(n)$ while I wrote $k=O(log(n))$.

Edit2:

The bounty is going to end soon, so if anyone is interested in what is perhaps an easier way to earn it, consider the following language:

$L_{(r,k)-distinct} :=\{w : w$ contains $k$ distinct symbols and no symbol appear more than $r$ times$\}$.

(i.e. $L_{(1,k)-distinct} = L_{k-distinct}$).

A similar construction as the one in the comments gives $O(e^k\cdot 2^{k\cdot log(1+r)}\cdot poly(n))$ sized automaton for $L_{(r,k)-distinct}$.

Can this be improved? What's the best lower bound we can show for this language?


texts: Can differential equations be classed into their own complexity classes?

texts:
Problems have been, as a whole, classified, thanks to Computational Complexity. But, in differential equations, is it possible to classify differential equations depending on their computational structure?

For example, if a first order non-homogeneous equation is comparatively difficult to solve than a, say, 100th order homogeneous equation, can they be classified as separate convexity classes, given the method to solve was same? If we vary the process of solving, how random shall the solutions, their existence and stability, and other properties vary?

I would assume that I am partly convinced that solving differential equations might be NP-Hard:

https://mathoverflow.net/questions/158068/simple-example-of-why-differential-equations-can-be-np-hard

This article:

http://www.cs.princeton.edu/~ken/MCS86.pdf

has been forcing me ask for the scope of computational complexity according to the solvabality of Differential Equations. Starting with ordinary differential equations, we could classify partial, delay, difference equations etc.

I had once thought of incorporating dynamic programming using the iterates that were calculated while approximating a solution, but lost myself somewhere.


texts: A substitution to add variables in the context

texts:
I'm doing type-inference in a dependently typed language, using (as is commonly done) a λ-calculus with explicit substitutions like that of Abadi (with a representation based on debruijn indices) in order to handle the issues of scoping when performing (higher-order) unification.

The "shift" operation of those explicit substitutions (denoted ↑) allows one to move a term to a larger context (i.e. applying weakening).  I.e. we can start from

Γ ⊢ e : τ

and then move this term e to a larger context:

Γ,x₁…xₙ ⊢ e[↑ⁿ] : τ

where e[↑ⁿ] is the result of n applications of ↑ to e.  So far so good.

This also works with metavariables: if a metavariable u appears within e (where it should appear as u[σ] where σ is a "pending" substitution that should be applied to u when it gets instantiated), then in e[↑ⁿ] u will get a new explicit substitution which is a combination of σ and ↑ⁿ to make sure that after instantiating u the result is properly adjusted for the context Γ,x₁…xₙ.

Now here's my problem: The metavariables in e[↑ⁿ] will never be able to refer to any of the x₁…xₙ variables.  In general, this is indeed desirable and necessary.
But in my case I know that all my metavariables's original context is Γ or some extension thereof, and I'd like to compute something like e[↑ⁿ] but where the metavariables are modified such that they can refer to the new x₁…xₙ variables.

For example: let's say we have a declaration f : List u → u, and during type inference I want to generalize this to f : ∀t. List t → t, like Twelf does.  The original term List u → u was declared within a context Γ so it looked like Γ ⊢ List u[id] → u[id] : *.  Now this term needs to be moved to the new context Γ,t but if I do it by applying ↑ I get Γ,t ⊢ List u[↑] → u[↑] : *.  But u[↑] cannot refer to t since t is at debruijn index 0 and the ↑ substitution adds 1 to the index of any variable reference, so I cannot get from List u[↑] → u[↑] to List t → t by instantiating the metavariable u (currently, I do it by manually traversing the term instead of reusing the existing metavariable instantiation infrastructure: it works but it's unsatisfactory).  Note that this is no accident: u exists (is created?) in context Γ and the explicit substitutions are designed to make it possible to use it in different contexts, not to change its own context.

My question is if it rings a bell and someone has seen a similar problem somewhere, which might help me better understand the underlying problem and maybe find a different approach.


texts: Turing reduction from integer factorization to clique

texts:
Is there a general web repository of reductions between and among various NP problems?  In particular, I'm looking for a direct Turing reduction from integer factorization (candidate for NP-Intermediate, not known to be NP-Complete) to clique (NP-Complete).

Apologies if this is below the difficulty threshold for cstheory;  I'm a graduate mechanical engineering student by training, so my google whispering skills and resources are somewhat limited (though I am ordering a copy of Arora and Barak!).

Thanks!


texts: Learning read-once branching programs with membership queries

texts:
Let $B=\{0,1\}$. A read-once branching program of width $n$ and size $w$ is given by a graph with layers $0,\ldots, n$, where the first layer has just the starting node, the last layer has nodes labeled 0 and 1, each layer has $\le w$ nodes, and each node has 2 edges labeled 0 and 1 pointing to nodes in the next layer. To evaluate the program on $x_1\ldots x_n$, simply start at the start node and follow the edges labeled $x_1,x_2,\ldots$, and read the label on the last node. Fix $n$, and let $w$-ROBP be the class of width $w$ read-once branching programs (and by abuse of notation, the functions computed by them).

Question:

Find an $\text{poly}(n,\epsilon)$ algorithm (or else show it would break some hardness assumption) such that given $f:B^n\to B$ as a black box, it computes $g\in w$-ROBP with high probability such that

$$
\mathbb{P}_{x\sim B^n}(g(x)\ne f(x))\le \min_{h\in w\text{-ROBP}} \mathbb{P}_{x\sim B^n}(h(x)\ne f(x)) + \epsilon.
$$

In other words, find an agnostic PAC-learning algorithm for $w$-ROBP.
Even a weaker bound depending on $\min_{h\in w\text{-ROBP}} \mathbb{P}_x(h(x)\ne f(x))$ would be interesting. I'm convinced that I have an algorithm for when $f\in w$-ROBP (so that the max is 0) but it doesn't generalize to this setting.

A quick literature search shows intractability results for more powerful classes such as width 3 (read-many) branching programs, and learning algorithms for finite automata (which are ROBP's with each layer the same), and not much on ROBP's. I would also appreciate any other results/references on learning for ROBP's.


texts: What is the meaning of an Oracle in data clustering?

texts: I am not sure whether this is the best place to ask this question. I am in the process of researching the area in data clustering as well as the algorithms that are associated with it and the term Oracle keeps appearing. Can anyone explain what this is in terms of clustering? I cannot seem to find a refined definition for it.


texts: Computing the DAG of a program given source code or AST

texts:
I've seen many papers on scheduling components or tasks once a DAG for the program is known, either by user-input or by domain restriction (i.e. all cross shaped 5-pt stencil codes have a known DAG).

Is there an algorithm for taking code (or Abstract syntax trees) from a language, say Python, and generating a DAG for it? I've been searching for a paper related to this for a long time and haven't found anything on google scholar.

Intuitively, I'd say that it's not possible, since some languages (such as Python) can change just about everything at run-time, and thus to determine the behavior and dependencies of a given program you would have to run it first for every possible set of inputs.

EDIT: I'm using DAG in this sense as the Directed Acyclic Graph for the dependencies (i.e. which parts depend on which other parts)


texts:
Which missing TCS topics on Wikipedia would you most like there to be an article about?

They could be glaring omissions or just topics you think should really have an article.

One topic per answer please so that the most wanted ones can be voted up.

Update 5/2/2017: Shuchi Chawla is leading an effort to improve TCS coverage on wikipedia. I'm adding this update in the hopes that people will update their answers as appropriate, add more answers, and/or contribute to the effort!


texts: Is Non-linear Constrained Optimal Exact Cover NP-Hard?

texts:
Playing around I ran into a problem which looks like a Exact Set Covering / Partition Problem, but I am unable to find a reduction to categorize the complexity of the problem, despite it looks NP-Hard. I will informally state the problem and some of the properties, since describing the problem as a whole would be too lengthy.

  Non-linear Constrained Optimal Exact Cover

  Consider a finite set $C=\{1,2,\ldots,m\}$ of elements and a vector $\mathbf{w}=\{w_j ~|~ j\in C\}$ of associated weights.
  The collection $S=\{s_1,s_2,\ldots, s_n | s_i\subset C\}$ contains every subset of combinations of elements of $C$ that fulfills:  $$f(\mathbf{w}_{s_i})\ge 0, \forall s_i\in S;\quad \text{ where } \mathbf{w}_{s_i}=\{w_j ~|~ j\in s_i\}. $$
  Find the subcollection ${S}^{*}$ of $S$ such that

  ($i$) each element in $C$ is contained in exactly one subset of ${S}^{*}$

  ($ii$) $g(S^*)=\sum\limits_{i=1,\ldots,n} g(\mathbf{w}_{s_i})$ is maximized.

  Example:
  $C=\{1,2,3,4\}$ and $\{w_1,w_2,w_3,w_4\}$.

  Given the weights, the non linear constraint $f(\mathbf{w_{s_i}})\ge 0$ implies:
  $$S=\{\{1\},\{2\},\{3\},\{4\},\{1,2\},\{2,3\},\{1,4\},\{1,2,3\},\{1,3,4\}\}$$
  having each subset $s_i\in S$:
  $$\{g(\mathbf{w_{s_i}}) ~|~ s_i\in S\}=\{4,2,1,5,2,7,8,2,3\}.$$
  Solution: $S^*=\{\{2,3\},\{1,4\}\},$ since each of the elements of $C$ is contained in exactly one subset of $S^*$ and $g(S^*)$ is the maximum possible.

Note that the Minimum Exact Cover Problem is related but deals with a different objective function (minimize the cardinality of the set) and the general description of the problem does not constrain the subsets that can appear in an instance for S (unlike this problem).

My feeling is that the problem is NP-Hard, since as increasing the size of $C$, the possible set of partitions increase quickly (Catalan numbers). However, I do understand that the reduction in the feasible space may vary the complexity.

My goal is to find the conditions on the functions such that the
problem remains NP-Hard or, if none if it is NP-hard for any pair besides the trivial functions. I have been working a bit into that, but this is not my field of expertise and I am suspicious that a similar work has been done or that a reduction in trivial for expert eyes or at least a categorization of the problem.

  Notes

  $ ~ f$ and $g$ are non linear functions that depends on the
  partition. It is hard to define them hereby, but they aim to
  evaluate the subset similarity, e.g., $f(\mathbf{w}_{s_i})\ge 0$ ensure
  that the elements weights are similar enough among each other.
  For any instance of the problem there exists at least one feasible
  partition. The partition that includes each element in a subset
  ${S}^{'}=\{\{1\},\{2\},\ldots,\{m\}\}$ is feasible (fulfills
  condition ($i$)), but it may not be optimal.
  Clearly, there are some functions for which the problem seems
  trivial, i.e., if the constraints are $f(\mathbf{w}_{s_i})=-|\mathbf{w}_{s_i}|+1 \ge 0$ then
  only the partition
  $S^{'}$ is feasible and then the solution
  can be obtained in O(1).


texts:
It is well-known that it is NP-complete to decide whether in a 2-CNF at least s clauses are satisfiable. It also follows from the reduction from 3-SAT-3 that we can suppose that every literal occurs in at most k clauses of the 2-CNF for some constant k. Can someone give me a good bound on k?

Can we suppose that every variable occurs at most twice negated or at most twice unnegated?


texts: What's the status of Babai's Graph isomorphism result?

texts:
It's been over a year since his January 2017 retraction and correction.
Is there news?
If not is this normal for validation to take this long? I would expect it would get plenty of attention.
Has anyone of note spoken up to support/doubt the quasi-polynomial result?


texts: Belief propagation for approximate real 3LIN?

texts:
In a Science paper from 2002, Mezard, Parisi and Zecchina put forward the belief propagation heuristic for random 3SAT. Experiments indicate that the heuristic works well for ratios of constraints-per-variable for which a satisfying assignment is likely to exist.

My questions are:

(1) What if you consider random 3LIN instead of random 3SAT? (each constraint is a random linear equation over GF(2))

(2) What if you consider random approximate real 3LIN? Is it conceivable that the performance of (an appropriately adapted) belief propagation heuristic would be easier to analyze in this case?

The approximate version, defined in a recent work with Subhash Khot, is as follows: the variables can assume real values and not just binary values. We consider only assignments of norm 1.
Each equation is of the form $c_1 x_1 + c_2 x_2 + c_3 x_3 = 0$, where $c_1,c_2,c_3$ are normally distributed, and $x_1,x_2,x_3$ are chosen uniformly from the set of variables. An equation is satisfied if $|c_1 x_1 + c_2 x_2 + c_3 x_3|\leq \epsilon$, and not just if there is an exact equality.

The intuition is that in the approximate version, changes to the belief (what should be the assignment of a variable) could happen in a continuous/incremental way.


texts: Complexity of checking if two words have an interleaving in a language

texts:
For a fixed language $L$ on some alphabet $A$, let us consider the following problem, that I call $L$-INTERLEAVING:

Input: two words $u, v \in A^*$
Output: whether there exists an interleaving of $u$ and $v$ which is in $L$.

Here, an interleaving of two words $u$ and $v$ is a word $w$ that can be obtained intuitively by taking the letters of $u$ and $v$ while keeping their relative order. Formally, $w$ is an interleaving of $u$ and $v$ if we can partition it into two disjoint subsequences, one which is equal to $u$ and the other which is equal to $v$. For instance, "bheleloll" is an interleaving of "hello" and "bell".

What is the complexity of the $L$-INTERLEAVING problem, depending on the language $L$? In particular:

If $L$ is regular, then we can solve the problem with a dynamic algorithm on the two strings which shows it to be in the class NL. Is it NL-hard for some regular languages? However, for some regular languages, the problem is clearly in L (deterministic logspace). Is there some characterization of the languages for which the problem is in L?
If $L$ is not regular, the problem is still in NL when $L$ has polynomial online deterministic space complexity (see here for this notion, or my earlier question). However, this does not cover, e.g., all context-free languages; yet, some others (e.g., palindromes) can be also shown to be NL (e.g., by doing a dynamic algorithm simultaneously from the beginning and from the end). Is there a context-free language whose $L$-interleaving problem is NP-hard?


texts: Encoding sets of permutations with a generating set and a set of excluded elements

texts:
Polynomial-time algorithms are known for finding generating sets of permutation groups, which is interesting since we can then represent those groups succinctly without giving up on polynomial-time algorithms for answering many interesting questions related to these groups.

However, we may sometimes be interested in a set $R$ of permutations that does not form a group, so that set would be represented by $R=\langle S\rangle \setminus T$, where $\langle S\rangle$ is the group generated by a set $S$ of generators and $T$ is a set of permutations that are not in $R$, instead of just $\langle S\rangle$.

Has any work been done on computing such an encoding in the form of a pair $\{S,T\}$, possibly with the additional, natural goal of minimising $|S|+|T|$?


texts: How/Why are linear systems so crucial to computer science?

texts:
I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network flows, edge/vertex cover, travelling salesman etc.) I know that some of them are NP-hard, but the point being that they can be 'framed as a linear program' if not solved optimally.

That got me thinking: We've always been taught systems of linear equations, linear algebra all throughout school/college. And seeing the power of LPs for expressing various algorithms it's kinda fascinating.

Question: Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science? I do understand that they help simplify the understanding and are computationally tractable most of the times but is that it? How good is this 'approximation'? Are we over-simplifying and are the results still meaningful in practice? Or is it just 'nature' i.e. the problems that are the most fascinating are indeed simply linear?

Would it be safe to safe that 'linear algebra/equations/programming' are of the corner stones of CS? If not then what would be a good contradiction? How often do we deal with non-linear stuff (I don't necessarily mean theoretically but also from a 'solveability' standpoint i.e. just saying it's NP doesn't cut it; there should be a good approximation to the problem and would it land up being linear?)


texts: The Examiner's Problem (uniform generation of SAT decision instances/answers)

texts:
A course's teaching assistant has managed to write a program that (deterministically) generates difficult exam questions. Now, she'd like to write a program that generates the corresponding answers. The Examiner's Problem asks whether this is always possible; the Examiner's Conjecture states that, assuming, $\mathsf{P} \neq \mathsf{NP}$, it is not: coming up with problems is easier than coming up with their solutions.

More formally, let $M$ be a deterministic Turing Machine that, on input $1^n$, generates in polynomial time a Boolean formula of size $n$. I'd like to know if, for all such $M$, there exists a deterministic polynomial-time Turing Machine $M'$ that, on input $1^n$, outputs "$1$" if $M(1^n)$ has a satisfying assignment and "$0$" otherwise.

Assuming $\mathsf{P} \neq \mathsf{NP}$, has this question already been asked or answered? If not answered, what sorts of additional assumptions (e.g. one-way functions?) might bear on the result? Barring any of the above, my "conjecture" is that the "answering" TM does not always exist, but what is your intuition?

Thanks!


texts: Is the dominating 7-set problem known to be solvable in  n$^{7+\hspace{.03 in}o(1)}$  time?

texts:
This paper says "For k ≥ 7, k-Dominating Set can be solved in nk+o(1) time.",

but Reference 17 only makes that claim for  ℓ ≥ 8 ,  and it seems like on the

"Proposition 2" page, the matrices would actually have height  $\binom{n}{\hspace{-0.02 in}\lceil k/2\rceil \hspace{.02 in}}$  and  $\binom{n}{\hspace{-0.02 in}\lfloor k/2\rfloor \hspace{.02 in}}$ .

(I asked Ryan Williams about this 3 days ago and he hasn't responded yet.)


texts:
For those doesn't know about linear datalog, linear datalog is a datalog rule in which the number of IDB predicate in each rule is less or equal than one.

My question is, why is this interesting? What differ this with the "normal" datalog program?

NB: I put this question also in math.stackexchange. According to my experience, I am afraid that this question shouldn't be in this site, but I don't see any reason why I should put  deductive database question in math section.


texts: First register in the hidden subgroup representations of Simon's and graph isomorphism problems

texts:
The Simon's problem involves a function which takes binary strings as inputs. One seeks to find the period of the function which acts on those inputs. In the standard method, the first register has the capability to encode the inputs.

The graph isomorphism problem is defined over two input graphs. The hidden subgroup representation of the problem involves a function which doesn't take the graphs as inputs. Rather it takes permutation over the vertices as input. Those permutations are agnostic of the input graphs. In the standard method, the first register doesn't have the capability to encode the inputs i.e. the graphs.

Can anyone explain why the HSP representations of these two problem are so different in the sense that in the standard method of an hidden subgroup approach the first register of one of them encodes the inputs but the other doesn't?


texts: Hardness of approximating fractional chromatic number on bounded degree graphs

texts: Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?


texts:
I am looking for a book on advanced data structures that goes beyond what is covered in standard textbooks like Cormen, Leiserson, Rivest, and Stein's "Introduction to Algorithms".
A book that can be used for teaching a graduate level course on advanced data structures like Erik Demaine and André Schulz's Advanced Data Structures course at MIT.
An encyclopedic handbook of data structures would be even nicer.


texts: Does it matter who begins communication in $IP(f(x))$?

texts:
Consider $IP(f(x))$, in other words, the class of languages that admit a private coin protocol $(P, V)$ running in $f(x)$ rounds (often in terms of the size of $x$), satisfying standard constraints.

Does it matter who sends the first message?


texts: Linear ordering from weighted directed graph (kittens)

texts:
I want to build a website to find the cutest kitten(TM) there is. People can upload photos of their kittens, but also can vote on which kitten is the cutest. However, I don't want them to rate on a 1 to 10 scale, but kitten cuteness is relative to other kittens.

Every voter is presented with 3 kittens and needs to order them by cuteness using drag and drop.

From these votes I can compute a weighted cyclic graph with the kittens being nodes and the edges being number of votes

Is there an algorithm to approximate a (partial) linear ordering that takes transitive votes into account ? So one can put the kittens on a 1 to 10 scale after all ?


texts:
Lets say I have a finite set of items like the following:

{$a_1, a_2, ... , a_n$}

And I have a finite list of sets of these items. For example:

[{$a_1$}, {$a_1, a_2$}, {$a_1, a_2, a_3$}, {$a_1, a_3$}, {$a_2$}, {$a_2$}, {$a_2$}, {$a_3$}]

I then take one item from each set. For example, in the above case, I could do:

$a_1$ <- {$a_1$}
$a_2$ <- {$a_1, a_2$}
$a_1$ <- {$a_1, a_3$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1$ <- {$a_1, a_2, a_3$}
$a_3$ <- {$a_3$}

In this case, the totals are:

$a_1$: 3
$a_2$: 4
$a_3$: 1

And the minimum is 1.

But lets say I want to maximise the minimum. I could instead select the items like:

$a_1$ <- {$a_1$}
$a_2$ <- {$a_1, a_2$}
$a_3$ <- {$a_1, a_3$} (changed)
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1$ <- {$a_1, a_2, a_3$}
$a_3$ <- {$a_3$}

And the totals are:

$a_1$: 2
$a_2$: 4
$a_3$: 2

And the minimum is 2.

Lets say also I allow the items to be assigned in a weighted way. Like the following:

$a_1$ <- {$a_1$}
$a_1$ <- {$a_1, a_2$} (changed)
$a_3$ <- {$a_1, a_3$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_2$ <- {$a_2$}
$a_1: 0.5, a_3: 0.5$ <- {$a_1, a_2, a_3$} (changed)
$a_3$ <- {$a_3$}

And the totals are:

$a_1$: 2.5
$a_2$: 3
$a_3$: 2.5

And the minimum is 2.5.

We can't evenly assign the items in these sets because three of them only contain {$a_2$}.

So what's a fast algorithm for doing the above, i.e. finding the maximum "minimum"? I need something exact, not an approximation.


texts: Weakly normalizing + confluent = strongly normalizing?

texts:
I was reading this abstract and saw that they prove weak normalization and confluence. My limited understanding suggests that those two properties should provide strong normalization, which then leaves me confused about why they'd leave that out in the abstract, thus suggesting I might be wrong.

Is it the case that a confluent weakly normalizing system is strongly normalizing? Why/why not?


texts: Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth

texts:
I would like to cite a paper/report/etc that solves the following problem polynomially in $n$:

Given a weighted directed graph $G=(V,E)$, $|V|=n$, of bounded treewidth $k \in \mathbb{N}$ and a source-destination pair $s,t\in V$, find a longest path (not walk) from $s$ to $t$.

The corresponding Wikipedia article (https://en.wikipedia.org/wiki/Longest_path_problem#Parameterized_complexity)  implies that it is possible:

  the longest path problem is [...] fixed-parameter tractable when parameterized by the treewidth of the graph

Sadly, my knowledge of treewidth-techniques is rather small.

I found the following paper, but it is on undirected (?unweighted?) graphs:

Confronting Hardness Using a Hybrid Approach: Cites a paper of Bodlaender (in Section 2.2.1), where Theorem 2.2 states that the longest path problem is solvable in $O(2^k k! n)$ (assuming a treewidth decomposition is given)

Is it easy to see that this technique also extends to directed weighted graphs? What happens when the weights are encoded in binary, i.e., they can be exponential in $n$?

There is also a nice discussion here, but it also seems to rely on undirected (?unweighted?) graphs.

Thank you!


texts: Need a term for a graph-theoretic/metric concept

texts:
Let $(X,d)$ be a metric space, and define $\rho$ to be the largest distance of any $x\in X$ to its nearest neighbor.

Formally,
$$ \rho = \sup_{x \in X}~ d(x, X \setminus \{x\}). $$

Does this quantity have a name? It's zero in continuous spaces and is only interesting in discrete ones.


texts: Is Ralf Hinze's Discriminator sort parallelizable?

texts:
According to this slide - the following sorting algorithms

Merge Sort
Insertion Sort
Bubble Sort
Quicksort
Bogosort

all rely on cmp - which has a fixed upper limit of n log n.

Ralf Hinze's Discriminator sort is incredibly performant in linear time. According to these tests in Scala it runs faster than cmp-based sorts for a linear operation.

My question is - can the disciminator sort be parallelized?


texts: Are Shannon entropy and Boltzmann entropy mutually convertible?

texts: Are Shannon entropy and Boltzmann entropy mutually convertible, much like mass and energy according to Einstein's formula?


texts:
Define LOGLOG as the class of languages which can be computed in space O(loglog n) by a deterministic Turing machine (with two-way access to the input). Similarly define NLOGLOG as the class of languages which can be computed in space O(log log n) by a non-deterministic Turing machine (with two-way access to the input). Is it really not known that these classes differ?

I could only find some older surveys and a theorem that if they equal then L=NL (which is not just a trivial padding argument!), but somehow I feel that separating these classes cannot be that hard. Of course I might be completely wrong, but if every second bit of the input is the numbers from 1 to n in increasing order in binary, separated by some symbols, then the machines can already learn loglog n and with every other second bit we can input a problem that can fool a deterministic machine but not a non-deterministic one. I don't see yet exactly how this could be done but feels like a possible approach, as with this trick we can basically input a depth log n binary tree along with its structure instead of the usual linear tape.


texts: FASTA algorithm - how should the diagonal runs be combined?

texts:
I tried implementing the FASTA algorithm. I selected the 10 best diagonal runs. These are subalignments which do not contain any indels. I want to combine these to get a more optimal run which may contains indels. What is the best way to do it, what graph algorithm should be used?
I was thinking of creating a graph where the vertices are the subalignments and the edges between them are their original score minus the insertions/deletions we need to connect them, but I'm not sure what graph algorithm would work here.


texts: How can I formalize key value stores with set theory?

texts: I'm currently developing a simple key-value NoSQL store and want to build its formal model. I'm interested in knowing if there some work about formalization of key-value stores outside of category theory? I want to use some more simple and lightweight mathematics for the mathematical description of key-value stores. Set theory looks like it might offer some possibilities.


texts:
Is the decision problem below NP-complete?

Given sets $S_1, ... , S_n$, as well as bounds $b_1, ... , b_n$, is it possible to pick pairwise disjoint subsets $U_1, ... , U_n$ such that $U_i \subset S_i$ and $|U_i| \geqslant b_i$ for all $i$?


texts: Are there incompressible strings $S$ such that $K(SS) \lt K(S)$?

texts:
This question was inspired by Sune Jakobsen's question and Tsuyoshi's answer. In Kolmogorov-complexity, a string is incompressible if $K(S) \ge |S|$.

Is there incompressible string $S$ such that $K(SS) \lt K(S)$? Is there an infinite set of such strings? What is the theoretical consequence if such infinite set of strings does exist?


texts: Complexity of $\oplus$ 3-REGULAR BIPARTITE PLANAR VERTEX COVER

texts:
The $\oplus$3-REGULAR BIPARTITE PLANAR VERTEX COVER problem consists in computing the parity of the number of vertex covers of a 3-regular bipartite planar graph.

  Question

  Which is the complexity of such problem? Is it $\oplus$P-hard, or is it in P?
  What if we remove the planarity restriction (i.e. $\oplus$3-REGULAR BIPARTITE VERTEX COVER)?

The closest I was able to find is that $\oplus$3/2 BIPARTITE PLANAR VERTEX COVER is $\oplus$P-complete (see Theorem 2.2 in this paper).


texts: Is there an approximation algorithm for the three-person stable roommates problem?

texts:
While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the threesome roommates problem, is NP-complete.
However, I'm wondering if there's an approximation algorithm. This is for a specific use case - grouping people into tables for conversation, based on their preferences - and it doesn't need to be perfect.
While it would be interesting to know if such an article has been described in an academic paper, I'm primarily looking for an implementation of such an algorithm (in any language).
An algorithm for a foursome version would also be interesting.


texts: Complexity of coloring in weakly perfect graphs?

texts:
A graph is weakly perfect if the clique number equals the chromatic
number, i.e. $\omega(G)=\chi(G)$. Deciding membership is NP-complete
according to the paper.

Because of the inequality $\omega(G) \le \chi(G)$ a $k$-clique is certificate
that there isn't smaller than $k$ coloring.

  What is the complexity of deciding if a weakly perfect graph is
  $k$-colorable?

Appears to me it might not be NP-complete because the certificate
will involve co-NP.

Also it might not be in P since it will decide coloring graphs for which
the inequality happens "by chance" and possibly by adding disjoint
cliques might be improved.

Searching the web found algebraic constructions of weakly perfect.
In all papers coloring was polynomial via closed form.

Related to this.


texts: Polynomial-time reductions between undecidable languages

texts:
The Turing degree $\mathbf{0}'$ is defined as
all languages Turing-equivalent to the halting problem.
In fact any recursively enumerable language is
polynomial-time reducible to the halting problem.

My question is, are all languages with Turing degree $\mathbf{0}'$ Turing-reducible to each other in polynomial time?
If not, can the fastest reduction between two $\mathbf{0}'$ languages get arbitrarily slow, and
are there known subsets of $\mathbf{0}'$ that are polynomial-time reducible to each other?


texts: How hard it is to approximate the ground state of the (2-D) Hubbard model

texts:
The Hubbard model (see also the wikipedea article on the Bose-Hubbard model) is a basic quantum model of solid-state physics.

Question: What is the computational complexity of approximating the ground state of a 2-D Hubbard model?

Remarks:

1) This question is inspired by lecture-series by Frank Verstraete in Jerusalem. (See here for the videotaped lectures.)

2) The question is a "tiny input" question, (see this question:Counting Isomorphism Types of Graphs  ) so hardness result for questions of this kind is largely an uncharted territory.

We can ask:

1) is there a polynomial time algorithm?

2) Is there a polynomial time quantum algorithm?

Frank suggested that algorithms based on adiabatic evolution (starting from a product state) would work, since gaps at phase transitions typically only scale as 1/poly in the system size, (which keeps it in BQP). My question is if this is known/proven.

3) Is the problem in NP?


texts:
Assume I have a parametrized graph. The parameters are two integers $x$ and $y<x$.
Let $S(x)=\{1, \ldots, x\}$.
The vertices of the graph are all the subsets of $S(x)$ of size $y$. Two vertices share an edge if their intersection is empty.
I need to find the chromatic number of this graph.
Is this problem NP-hard ?

Thank you in advance for your help.


texts: Spectral techniques for genus of a graph

texts: A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in bipartite graphs.


texts: Deterministic approximation algorithms for treewidth

texts: As far as I understand, the factor $O(\sqrt{\log OPT})$ approximation algorithm for treewidth of Feige, Hajiaghayi, and Lee is randomized, and no deterministic approximation algorithm with this factor is known. Is this correct? Is any deterministic approximation algorithm with factor below $O(\log OPT)$ known?


texts: Are there non-constructive algorithm existence proofs?

texts:
I remember I might have encountered references to problems that have been proven to be solvable with a particular complexity, but with no known algorithm to actually reach this complexity.

I struggle wrapping my mind around how this can be the case; how a non-constructive proof for the existence of an algorithm would look like.

Do there actually exist such problems? Do they have a lot of practical value?


texts: Second eigenvalue and the last eigenvalue

texts:
Note : All eigenvalues that I would referring to below would of the adjacency matrix of the graph

My question arises from having read about Expander Graphs from a few different sources. The most common definition of Expander Graphs that have seen is in terms of the spectral gap which is $d - \lambda _2$ where $\lambda _2$ is the second highest eigenvalue. However certain sources also like to define expansion in terms of $\lambda$ which is the second highest eigenvalue in absolute value. Now I am slightly confused about what is a better definition and why these two values are so mixed in literature ?

For instance Cheeger's inequalities are defined in terms of $\lambda _2$ and the Expander Mixing Lemma is defined is terms of $\lambda$ (I am not sure if there exist versions of each in terms of the other quantity). Also I have seen versions of the Alon-Bopanna bound in terms of both $\lambda$ and $\lambda _2$.

I guess my question is that is there a fundamental connection between these two quantities and is one more natural than the other to be used to define expansion ?

Also is there something fundamental that $\lambda _n$ (by $\lambda _n$ I mean the smallest eigenvalue) represent ?

I am not sure if I have been able to express my confusion clearly but I am sure I am missing something fundamental in my understanding.

Thanks


texts: Complexity analysis on a parameterized recurrence relation

texts:
In order to analyse the complexity of our algorithm, we try to solve this recurrence:

$T(n)=3T(n-1)-T(n-2)+T(n-k)+3^k$ ; in which $k$ is a parameter to be fixed.

We know that this kind of recurrence means $T(n)=O(\alpha^n)$, where $\alpha$ is the zero root of the equation $f(x)=x^n-3x^{n-1}+x^{n-2}-x^{n-k}-3^k$.

The term $3^k$ expects a small value of $k$, while the rest terms want a big value of $k$, therefore we believe that there should be a best choice of $k$.

So the question is how to choose $k$, $(k=g(n))$ in order to minimize $\alpha$?

Thank you in advance for any idea.

UPDATE 1:

The recurrence has been corrected, and yes, $\alpha$ should be between 2 and 3.
Please note that $k$ is a dynamic value, which changes during the recursion. So it's better to consider the recurrence as $T(n)=3T(n-1)-T(n-2)+T(n-g(n))+3^{g(n)}$

UPDATE 2:

To somewhat simply the problem, we may consider $g(n)=\beta n$ and try to find the $\beta$ ?


texts: White elephant gift exchanges: mechanisms for fair division

texts:
A popular game at holiday parties in North America is the white elephant gift exchange. In brief (ignoring variations) it works as follows:
There are $n$ people and $n$ wrapped gifts. Players are ordered arbitrarily. In the $i^{\text{th}}$ round, player $i$ either

chooses a wrapped gift and unwraps it as their present
"steals" one of the already opened gifts (from some player $k < i$).

If a player's gift is stolen, they now have the opportunity to do the same thing. A round is complete when a player chooses a wrapped gift.
While there are many variations in the system, one point to note is that the player going last has an unfair advantage because they alone are guaranteed the ability to choose any unwrapped gift.
THis falls under the class of fair-division methods pertaining to indivisible goods (unlike cake cutting).
My questions is:

Are there mechanisms for disbursing the gifts that are fair (in that
each player has the same opportunity to choose a high value gift under
their valuation) ?

Note that some flexibility will be needed in the definition of fair since the goods are indivisible and we are not introducing monetary compensation for players.


texts: Data-structure for functions of independent sets

texts:
Suppose I have a graph $G$, with nodes $\{1,2,\ldots,n\}$, subsets of nodes $\{b_1,\ldots,b_k\}$ and functions $\{f_1,\ldots,f_k\}$ where $f_i$ maps independent subsets of $b_i$ to reals. The operation on $f$ is setting or getting all values in "canonical order", ie, $\langle f(\emptyset),f(\{1\}),f(\{2\}),f(\{3\}),f(\{1,2\}),\ldots \rangle$.

What is a way to do this more efficiently than with an array of size $2^{|b_i|}$ for $f_i$? This comes up when counting independent sets on graphs


texts: Counting words of length $n$ in an inherently ambiguous CFG?

texts:
There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, the algorithm only computes the number of parse trees resulting in strings of length $n$. Therefore, this result is not the number of words of length $n$ in an ambiguous CFG.

Is there a result (other than testing all possible strings of length $n$) for inherently ambiguous CFGs?


texts:
I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's.
In both cases the ultimate goal is to differentiate some object, though the conditions are quite different.
I would like to know what people more familiar with Babai's proof think about whether some of the ideas there are applicable to word separation or not.


texts: I've been researching Parameterized Complexity Theory, and I've been puzzled by the definition of W[P]. Why is the number of non-deterministic steps bounded by $log|n|$? What is the intuition I should have for problems in W[P]?


texts: Relationship between Pataraia's theorem and inductive-recursive definitions?

texts:
Pataraia's fixed point theorem gives a constructive proof of the fact that if you have a monotone function $f$ on a DCPO, then it has a least fixed point. I've frequently used this fixed point theorem to construct logical relations for proving properties about dependent type theories.

The idea is that you can view a syntactic type system as a pair $(U, \phi)$ of a partial equivalence relation (or PER) $U$, representing the codes of types, and an interpretation function $\phi : U \to \mathrm{PER}$, sending each type code to its interpretation. Semantic type systems can be equipped with a domain structure, by saying that $(U', \phi') \sqsubseteq (U, \phi)$ just when $U' \subseteq U$, and for every type $A \in |U'|$, we have that $\phi(A) = \phi'(A)$. The empty type system is the obvious bottom element, and joins exist in the obvious way. Then a logical relation can be constructed as a fixed point of a monotone map with respect to this ordering.

However, this semantic definition also bears a strong relationship to inductive-recursive definitions, where the set $U$ and the interpretation $\phi$ are defined simultaneously. (Unsurprisingly, since generalizing universe constructions was  the prime motivation for the invention of induction-recursion.)

Has anyone looked at the relation between the two? It's not obvious to me, since the proof of Pataraia's theorem, while constructive, is rather impredicative (it seems to rely essentially upon the powerset operation). So:

Can Pataraia's theorem be used to prove  the soundness of the full induction-recursion schema?
To what extent can induction-recursion be used to prove the converse? (I assume it won't go all the way, but maybe I'm wrong!)


texts: Practical polynomial-time implementation of bounded degree graph isomorphishm

texts:
There's a well-known article for solving graph isomorphism problem in polynomial time. Many other articles on the subject of isomorphism mention it as a possible "alternative", but note that is not applicable in general case and move on presenting their approach.

However, I'm interested in solving subgraph isomorphism in the context of chemical structures. Majority of graphs in this domain are, in fact, of bounded degree. This is a result of chemical properties, where bonds (edges) are result of valence electron pairings. Because there's only limited number of electrons on valence shelve, so is the number of edges limited. I doubt there are chemical structures where atom has more than 7 bonds. Even if such exotic example would arise, it would be easy to identify and use more general algorithm for it.

The problem is I didn't find any practical implementation of the polynomial-time algorithm or any follow up work that would consider the idea from more practical perspective. The established algorithm for subgraph isomorphism in chemoinformatics seems to be VF2. There were some other related questions asking for a more digestible explanation, but I'm specifically looking for implementation and why can't I find any. Is the approach somewhat obsolete, forgotten, too hard to explore, or is there other issue why not use it?


texts: Comparison of Hashing and Modular Exponentiation

texts:
Suppose we want to compare two protocols on the computational costs. One of the protocols is designed using random oracle model (we call it the first protocol) and the other protocol uses is designed over common reference string (we call it the second protocol).

Now if we want to compare these two, we have to rely on the most costly operation in them. In the first protocol it is the hashing operation and in the second, the modular exponentiation. How can I compare these two protocols assuming both of them work over the same length of security parameter.

For simplicity, assume that the first protocol uses "n" hashing operation to complete and the second protocol uses "2n" modular exponentiation to output the result.

  Is there any way to compare these two? What measures should I consider when comparing these protocols?

To give a little background on the models, the Common Reference String (CRS) is the model which a global coin is assumed, which means a reference string (mostly a random one) is distributed among the parties. The random oracle model is the model which is essentially formalizing the hash functions. In this model, every party has oracle access to a random function (i.e., they submit the query to a function (oracle) some where and get the results, which in this case is a random string). When implementing a protocol with this model, the queries are replaced by calculating a hash function.


texts: What would a quantum computer architecture look like?

texts: More specifically, assuming we manage to make an efficient quantum switch, some kind of "quansistor"(quantum transistor) and manage to resolve the problem of joining a bunch of them together without losing the quantum properties that we want, where in a modern computer would these quansistors come in to create a quantum computer? As in would the entire computer be made of quansistors? or would only some parts be quansistors and the rest be standard eletronics. would the logic of the processor(the ALU and such...) be made with quansistors? would the storage? down to what level? just the registers or the RAM too? I imagine that having the part of the storage that stores the instructions of the running program be affected by the randomness of quantum behaviour would cause some problems. Really my question comes down to where in the standard computer processing pipeline does the quantumness come in, in order to produce the intended theoretical behaviour of quantum computer?


texts: Does anyone know of online video courses (in english) on randomness in theoretical computer science?

texts:
I have found some video courses like this one but they are all in russian or other languages I don't understand. I'll like to know if anyone has come across lectures (courses) of this kind which are in english.

I am also aware that there are questions which are similar to this one on stackexchange e.g.this one, but I couldn't find any course of this kind among the answers given.

P.S: I'm interested in anything involving randomness in TCS as long as it is a full video course.


texts: Why do we need formal semantics for predicate logic?

texts:
Consider this question solved. I will not pick a best answer as all of them have contributed to my understanding of the topic.

Im unsure what benefit we have by formally defining the semantics of predicate logic. But I do see value in having a formal proof calculus. My point is that we would not need formal semantics to justify the inference rules of proof calculi.

We could define a calculus that mimicks the "laws of thought", i.e. the rules of inference that have been used by mathematicians for hundreds of years to proof their theorems. Such a calculus already exists: natural deduction. Then we would define this calculus to be sound and complete.

This can be justified by realising that the formal semantics of predicate logic is just a model. The appropriateness of the model can only be justified intuitively. Thus, by showing that natural deduction is sound and complete with reference to the formal semantics does not make natural deduction more "true". It would be just as good if we would directly justify the rules of natural deduction intuitively. The detour using formal semantics gives us nothing.

Then, having defined natural deduction to be sound and complete, we could show the soundness and completeness of other calculi by showing that the proofs they produce can be translated to natural deduction and vice versa.

Are my reflections above correct?
Why is it important to prove the soundness and completeness of proof calculi by reference to formal semantics?


texts: Status of the Junta Problem (soft question)

texts:
Does the learning theory community in general believe that juntas can be learned in polynomial time?

The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta problem in nearly O(n^(2logn/3)) time, which as far as I can tell is the best upper bound today.

Do more than 50% of experts believe that the Junta problem IS solvable in polynomial time?

Thanks.


texts: Continued Fraction Algorithm in Shor's Algorithm

texts:
I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$.

We have a number $\psi$, which for a rational number $\dfrac{s}{r}$ satisfies
\begin{equation}
\Big| \dfrac{s}{r} - \psi \Big| \leq \dfrac{1}{2r^{2}}
\end{equation}
which means that if $\psi$ has continued fraction algorithm $[a_0,\dots,a_N]$ then $\dfrac{s}{r}$ has continued fraction $[a_0,\dots,a_k]$ for $k \leq N$.

The book just says that then applying the continued fractions algorithm to $\psi$ we obtain $r'$ which is our estimate for $r$. I'm not too sure how exactly we arrive at this value of $r'$. Is it just that once we obtain our expansion $\psi = [a_0,\dots,a_N]$, we obtain a value $r'_{m}$ for each of the $m^{th}$ convergent expansions and see which one is correct?


texts: How much is known about coloring of planar graphs with degree bounds?

texts:
Are there any references that address the following (open?) questions:

1) Is there an algorithm that 4-colors any planar graph of maximal degree at most 5 in linear time?

2) What is the largest number d for which there exist an algorithm that 4-colors any planar graph of maximal degree at most d in linear time?

3) Is every planar graph of maximal degree 5 or less 4-choosable?

4) What is the largest number d for which every planar graph of maximal degree at most d is 4-choosable?

Comments: For (1-2) it is not known whether there exists a linear algorithm for 4-coloring of planar graphs without bounded degrees. Even if there exists a linear algorithm for every degree bound d, it does not imply that one exists when degrees are unbounded. (3) might help to show (1). It is known that the d in (4) exists, since there are non-4-choosable planar graphs.


texts: Equivalence relations on strongly regular graphs with same parameters

texts:
Let $\mathcal{S}$ be the set of all strongly regular graphs with parameter
$(n, k, \lambda, \mu)$. Are there any (interesting) equivalence relations defined on this set?

My motivation is to approach isomorphism partition (equivalence relation is being isomorphic) via other coarser partition.


texts: Maximum matching M with the condition G[M] is 2K_2-free

texts:
Is there anything in the literature close to the following problem:

Given a bipartite graph $G(V,E)$ with balanced bipartition $ \{U,W\}$ , does there exist a perfect matching $ M $ in $ G $ such that for every 2 edges $u_1w_1, u_2w_2\in M $, there is an edge $u_1w_2$ or edge $u_2w_1$ (or both) in $ G $?

In other words, is there a perfect matching $M$ such that the induced subgraph $G[M]$ is $ 2K_2 $-free.
(With balanced bipartition, I meant $|U|=|W|$.)

The extra condition is something like an opposite extreme of that used in induced matching problem. Another possibly related one is the problem of finding maximum size matching $M$ in bipartite graph $G$ such that contraction of edges in $M$ minimizes the number of edges left in the graph.

I checked the list of matching related problems given by Plummer in Matching and vertex packing: how "hard" are they? without success.

PS: This problem is a special case of this decision problem :- For a given $k\in\mathbb{N}$, is there a maximum matching $M$ of a bipartite graph $G$ such that $G[M]$ is $2K_2$-free and $|M|>k$. If the input graph is balanced bipartite and $k=|U|$, we get the above problem.

Thank you.


texts: Max Non-overlapping Path in Weighted Graph

texts:
I have a sparse weighted graph, and I want to find the longest path from a given vertex to any other vertex which does not go through the same vertex twice. You can think of it as, I am here, and I want to take the longest walk possible in my graph without walking through the same place twice. Where ever that ends me up, I don't care, and I don't necessarily have to travel through every point on the graph, if those points do not lie on the longest path.  All edges have positive weights.

Can anyone describe an algorithm for this that is not a complete enumeration of all paths?


texts:
I wonder1 whether there is a known relativization barrier against proving $L\neq NP$. Hence I'm looking for a language $A$ for which $L^A=NP^A$.

My first idea was to try $A:=SAT$, but then I thought that $L^A\subset P^A = \Delta_2^P$ and $NP^A=\Sigma_2^P$. This seems to disqualify not only $A:=SAT$, but any complete problem $A$ from the polynomial hierarchy for my purpose.

My next idea was to try $A:=TQBF$, where $TQBF$ is the $PSPACE$-complete problem to decide true quantified Boolean formulas. But $P^A=NP^A$ is well known, and $L^A=NP^A$ is a stronger statement, so $L^A=NP^A$ would be well known, if anybody had proved it.

  My question is just whether there is a known relativization barrier. We certainly can't prove that such a language $A$ can't exist, because otherwise we would get $L\neq NP$ as corollary.

 1. I know that logarithmically space bounded TMs with stack recognize exactly the languages from $P$, independent of whether the TM is deterministic or not. I don't know whether this result relativizes, but I guess it does. So I wonder whether there can be a language $A$ with $NL^A=P^A$. But asking for $L^A=NP^A$ instead seems easier, because of the connection to the polynomial hierarchy.


texts: Is there a constant approximation algorithm for longest path for 3-connected cubic planar graphs or maximal planar graph?

texts:
optimization problem

Input: a 3-connected cubic planar graph

feasible solution: A simple path

measure to optimize: length of the simple path

Is there a constant approximation algorithm for this problem?

The Hamiltonian circuit problem on 3-connected cubic planar graphs is NP-Complete in this paper.

A relevant question about for cubic Hamiltonian graph shows that there is no constant approximation algorithm for longest path on cubic graphs.

I'm also interested in the version where the input is a maximal planar graph.


texts: Is there an efficient construction for a trilinear pairing that has been used in theory or practice

texts:
A trilinear pairing is defined a function $e:G_1^3 \rightarrow G_2$, such that it satisfies the property $e(k_1^a, k_2^b, k_3^c) = e(k_1,k_2,k_3)^{abc}$

In general I am trying to solve the following problem,
given a tuple $$(g, g^s, g^{r_1}, g^{r_2}, k_1, k_2, k_1^{r_1s},k_2^{r_2s'} )$$
where $g, k_1,k_2 ∈ G_1$ and $r_1, r_2, s,s' ∈ {Z_q}$

Is it possible to predict if $s = s'$?

One of the easy ways is to use trilinear mapping function $e$ to evaluate
$$e(g^{r_2}, k_1^{r_1s}, k_2 ) = e(g^{r_1}, k_1, k_2^{r_2s'})$$

However this can only be true if there exists an efficient construction of a trilinear pairing...
Is there a feasible construction available for a trilinear mapping or at least is it/has it been used in theory and in proofs?
Is there any other way to examine the same?


texts: Smallest vertex cover which is also an independent set

texts:
The vertex cover and independent set as a subset of nodes are always considered in a dual relationship. Have they been looked at together? What I mean is: start from a minimum vertex cover, and if it is not an independent set, add or remove vertices to make it one. So for instance, if there is an edge whose both endpoints are included in the vertex cover, remove one of them and add other nodes to maintain the covering property, but also achieve independence.

Does this kind of a subset of nodes have a name, and has it been studied? At least for acyclic graphs, it seems like there should be a "minimum deviation" way to convert a minimum vertex cover to a vertex cover which is also an independent set.

Thanks!


texts: Complexity theory when an oracle is part of the input

texts:
The most common way in which oracles occur in complexity theory is as follows: A fixed oracle is made available to, say, a Turing machine with certain limited resources, and one studies how the oracle increases the computational power of the machine.

There is, however, another way in which oracles sometimes occur: as part of the input.  For example, suppose I want to study algorithms for computing the volume of a given high-dimensional polytope.  Classically, the polytope would need to be specified by providing a list of its facets or some other explicit representation.  However, we can also pose the problem of computing the volume of a polytope that is specified by a volume oracle, that takes the coordinates of a point in space as input and outputs "yes" if and only if the given point lies inside the polytope.  Then we can ask what computational resources are needed to compute the volume of a polytope that is specified in this manner.  In this particular case we have the very nice polynomial time approximation scheme of Dyer, Frieze, and Kannan and, interestingly from the complexity theory point of view, a proof that randomness helps in an essential way for this problem, in that no deterministic algorithm can perform as well as the Dyer-Frieze-Kannan algorithm.

Is there a systematic way to study the complexity theory of problems in which oracles are provided as part of the input?  Does it somehow reduce to the usual theory of complexity classes with oracles?  My guess is no, and that because there are too many different ways that an oracle could be supplied as part of the input, every problem of this sort has to be handled in an ad hoc manner.  However, I would be happy to be proved wrong on this point.


texts: Is where an oracle B in EXP that $P^B$ $ \ne$ $NP^B$?

texts: According to Baker, Gill, Solovey where is an oracle A in EXP, so $P^A$ = $NP^A$. But is there an oracle B in EXP, what $P^B$ $\ne$ $NP^B$?


texts:
Out of curiosity, I tried finding the original paper showing that there are graphs that require $n/\log n$ pebbles in the sense of Hopcroft, Paul, and Valiant’s seminal paper “On Time Versus Space”. (Which you can access here: http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/p332-hopcroft.pdf).

Sadly, this result is cited as “personal communication,” and any other lower bounds I could find use the different definition of pebbling in graph theory. Does anyone know where I could find a construction of a graph requiring $n/\log n$ pebbles?


texts:
Bee swarm plots are a way of visualizing one-dimensional data sets, similar to box plots. The idea is that if there's not too many points (e.g. <300) we can just plot them along the $x$-axis with the $y$-offset chosen such that the points don't overlap, thus giving a "truthful" visual impression of the distribution. Sample image from https://seaborn.pydata.org/generated/seaborn.swarmplot.html:

As far as I can tell, this library chooses the $y$-offset greedily, that is, it just plots the points in increasing order, and chooses the minimum (absolute) $y$-offset above or below the $x$-axis such that the circle marker does not overlap with any already plotted point. This leads to these "whiskers", which obscure the actual distribution of the data point. It would be nice to find an arrangement that is "optimal" in some sense. The most obvious formulation is:

Given $x_1, \dots, x_n$
find $y_1, \dots, y_n$ that minimizes $|y_1| + \cdots + |y_n|$
subject to $\text{dist}((x_i, y_i), (x_j, y_j)) > d$ for $i \neq j$, where $\text{dist}$ is Euclidean distance and $d$ is some constant (diameter of the circle markers).

This seems like a fairly basic problem, but I couldn't find anything about it in the literature. In particular I'm wondering whether it is NP-hard, and what approach might be feasible for optimally solving it. I tried an ILP formulation but it has extremely bad performance (can solve only ~40 points).


texts:
I'm interested in why natural numbers are so beloved by the authors of books on programming languages theory and type theory (e.g. J. Mitchell, Foundations for programming languages and B. Pierce, Types and Programming Languages). Description of the simply-typed lambda-calculus and in particular PCF programming language are usually based on Nat's and Bool's. For the people using and teaching general-purpose industrial PL's it is great deal more natural to treat integers instead of naturals. Can you mention some good reasons why PL theorist prefer nat's? Besides that it is a little less complicated. Are there any fundamental reasons or is it just an honour the tradition?

UPD For all those comments about “fundamentality” of naturals: I'm a quite aware about all those cool things, but I'd rather prefer to see an example when it is really vital to have those properties in type theory of PL's theory. E.g. widely mentioned induction. When we have any sort of logic (which simply typed LC is), like basic first-order logic, we do really use induction — but induction on derivation tree (which we also have in lambda).

My question basically comes from people from industry, who wants to gain some fundamental theory of programming languages. They used to have integers in their programs and without concrete arguments and applications to the theory being studied (type theory in our case) why to study languages with only nat's, they feel quite disappointed.


texts: Proof techniques for showing that dependent type checking is decidable

texts:
I'm in a situation where I need to show that typechecking is decidable for a dependently-typed calculus I'm working on. So far, I've been able to prove that the system is strongly normalizing, and thus that definitional equality is decidable.

In many references I read, the decidability of typechecking is listed as a corollary of strong normalization, and I believe it in those cases, but I'm wondering how one goes about actually showing this.

In particular, I'm stuck on the following:

Just because well typed terms are strongly normalizing, doesn't mean that the algorithm won't loop forever on non-well typed inputs
Since logical relations are usually used to show strong normalization, there's not a convenient decreasing metric as we progress typechecking terms. So even if my type rules are syntax directed, there's no guarantee that applying the rules will eventually terminate.

I'm wondering, does anyone have a good reference to a proof of decidability of typechecking for a dependently typed language? If it's a small core calculus, that's fine. Anything that discusses proof techniques for showing decidability would be great.


texts: Approximation algorithm to a minimization problem with optimization function going to zero

texts: I have a simple function to minimize, but it is not discrete: $f(x) = 2x - \alpha x - c(x)$, where $x$ is a natural number, $\alpha$ is a rational number, $0 \leq \alpha \leq 1$, and $0 \leq c(x) \leq x$. Thus, $f(x)$ is zero if $c(x) = x$ and $\alpha = 1$, and this is the best possible value to $f$. This function comes from a NP-hard problem. Could I say that is not possible to approximate this problem with a constant approximation factor? I mean, it is possible to obtain a class of instances such that an optimal solution $f^*(x)$ is very close to zero and any heuristic solution $f(x)$ with cost greater than zero would be too far from the optimal solution. That is, $f(x)/f^*(x) \rightarrow \infty$.


texts: Are Reversal-bounded Multicounter Machines closed under reversal?

texts:
This is a problem I have found very difficult to solve, given how the two different uses of "reversal" confuses search engines.

Reversal-bounded multicounter machines are described at length in his paper "Reversal Bounded Multicounter Machines and their Decision Problems". Essentially, the bound on reversals refers to the number of times any of the counter are allowed to switch from incrementing to decrementing.

Let $DCM$ be the family of languages accepted by deterministic reversal-bounded multicounter machines, and $NCM$ the nondeterministic class.

Let $L^R = \{w^R | w \in L \}$ where $w^R$ is $w$ reversed.

I'm wondering, for $L \in DCM$, is $L^R \in DCM$? Are there subclasses of $DCM$ which have this property?

"Formal Modelling of Viral Gene Compression" by Daley and McQuillan tells that $NCM$ is closed under reversal, but I have found no such reference for the deterministic case.


texts:
Given a family $\mathcal F$ of at most $n$ subsets of $\{ 1, 2, \dots, n \}$.
The union closure $\mathcal F$ is another set family $\mathcal C$ containing every set that can be constructed by taking the union of 1 or more sets in $\mathcal F$.
By $|\mathcal C|$ we denote the number of sets in $\mathcal C$.

What is the fastest way to compute the union closure?

I have showed a equivalence between the union closure and listing all maximal independent sets in a bipartite graph, therefore we know that deciding the size of the union closure is #P-complete.

However there is a way to list all maximal independent sets (or maximal cliques) in $O(|\mathcal C| \cdot nm)$ time for a graph with $n$ nodes and $m$ edges Tsukiyama et al. 1977.
But this is not specialized for bipartite graphs.

We gave an algorithm for bipartite graphs with runtime $|\mathcal C| \cdot \log |\mathcal C| \cdot n^2$ http://www.ii.uib.no/~martinv/Papers/BooleanWidth_I.pdf

Our method is based on the observation that any element in $C$ can be made by the union of some other element of $C$ and one of the original sets.
Hence we will whenever we add an element to $C$ try to expand it by one of the $n$ original sets.
For each of these $n \cdot |C|$ sets we need to check if they are still in $C$. We store $C$ as a binary search tree, so each lookup takes $\log |C| \cdot n$ time.

Is it possible to find the union closure $\mathcal C$ in $O(|\mathcal C| \cdot n^2)$ time?
Or even in time $O(|\mathcal C| \cdot n)$?


texts: Kolmogorov Complexity applications in Number Theory

texts:
What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.)

One of the nice proofs i have come across is the proof of the existence of infinite number of primes, using the definition of Kolmogorov Complexity and the compression factor.

Also, what is the importance of Kolmogorov Complexity in Cryptography?


texts: A simple decision problem whose decidability is not known

texts:
I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability.  I want to give an example of a problem that we do not currently know to be decidable or undecidable.  There are many such problems, but none seem to stand out as nice examples so far.

What is a simple-to-describe decision problem whose decidability is open?


texts: Why is triangle inequality needed for indexing?

texts:
Maybe this is a silly question but I actually can't fulfill that by myself. I'm reading some papers about similarity metrics and I always find that for a distance function $d$ the triangle inequality is needed in order to support in indexing techniques and to implement, for instance, nearest neighbors queries.

Thus my question is: why is that property needed? Isn't indexing possible in presence of a distance function which does not fulfill the triangle inequality?

Thanks for your insights!


texts: Complexity of computing Earth Mover's Distance when the costs satisfy the triangle inequality

texts:
Let p and q by two categorical probability distributions over $\{1,2,...,k\}$. Given a set of costs $c_{ij} \ge 0, i,j \in \{1,2,...,k\}$ that satisfy the triangle inequality, that is $c_{ij} \le c_{ik} + c_{kj}, i,j,k \in \{1,2,...,k\}$, what is the complexity of the best known algorithm for computing the  Earth Mover's Distance between p and q , EMD(p,q) ?

I found that the time complexity is in general $O(n^3)$ and some linear time approximations are known, but it is not clear to me if any improvement was achieved if the costs satisfy the triangle inequality.


texts: A variant of randomized co-ordinate descent

texts:
Let us consider the following optimization problem.
$\mathcal{P} =\{P_1,\cdots,P_n\}$, where $P_i\subset\mathbb{R}^d$. Let $m = max_i\lvert P_i\rvert$. The goal is to find a point $c$ such that following function is minimized.
$F(c) = \sum_{P_j\in \mathcal{P}}max_{p\in P_j}\Vert p-c\Vert^2$. The following observations can be drawn

F(.) is convex.
Given a point $c\in\mathbb{R}^d$, let $p_j$ be the farthest point in $P_j$ from $c$. Then $G(c) =\sum_{P_j\in\mathcal{P}}2(c-p_j)$ is a "subgradient" of $F$ at $c$.

Note that computing $G(c)$ requires $O(nmd)$ time. Instead if we uniformly sample an index $j\in[n]$ and define a random variable $X(c,j) = 2(c-p_j)$, then $\mathbb{E}_j[X(c,j)] = \frac{G(c)}{n}$ and computing the random variable requires time $O(n+md)$.
Now instead of doing the "full" gradient descent(using $G(c)$), I am trying to use the random variable $X(c,j)$. So one step of this "randomized" gradient descent looks something like
$c^\prime = c -\alpha X(c,j)$. Here $\alpha$ is some step size.
The above step is similar to "randomized coordinate descent" (see Algorithm 3 Coordinate Descent Algorithms or for the more general formulation Efficiency of coordinate descent methods
on huge-scale optimization problems)
The analysis given here depends on the fact that only a single coordinate is sampled during a single iterarion( more generally, if the underlying space can be partitioned into "disjoint" "block"s, then a single block is sampled, see here). This can not be applied here in a straight forward manner(I think).
Does this variant of gradient descent appear in the literarure? More formally if the (sub)gradient is sum of a finite number of vectors, then can we use one uniformly sampled vector in the "descent" step?
Thanks you.


texts: How to determine if a labelled digraph contains a cycle with given labels?

texts:
Suppose $G = (V, E)$ is a digraph of bounded degree. Suppose each edge in $E$ is labelled with a number from the set $X = \{1, ..., n\}$ and for each vertex $v \in V$ and each $x \in X$ there is at most 1 edge labelled $x$ connecting out of $v$, i.e. there is at most one edge labelled $x$ with tail $v$.

Let $w$ be a word made using elements of $X$ as letters. For a given vertex $v$, $w$ defines a path through G by following the correctly labelled edges (if they exist) starting at $v$. I would like to determine if a $w$ forms a cycle anywhere within G.

  Is there a more efficient way to determine if there is a $v \in V$ such that $w$ forms a cycle when started at $v$ than checking where the path $w$ terminates for every starting vertex?


texts: Self-intersecting walk in expander graphs

texts:
Consider a random walk in an expander graph.
How much time it typically takes to visit the same vertex twice.
It seems to me that it should be something between $\sqrt{n}$ to $\sqrt{n}\log n$.
Is there any reference on this or similar things


texts: The originator of the fixed point theorem for DCPOs

texts:
Pataraia proved in

  "A constructive proof of Tarski’s fixed-point theorem for dcpo's", presented in the 65th Peripatetic Seminar on Sheaves and Logic, in Aarhus, Denmark, November 1997

that in a directed-complete partial order (dcpo) with a minimum element each monotone map has a fixpoint. (For the purpose of this particular theorem, a directed set is a poset in which each finite subset is bounded from above, and a dcpo is a poset in which each directed subset has a supremum.) Dito Pataraia is mostly acknowledged for the new proof method rather than the theorem itself.

Who was the first to actually state and prove this theorem is any way? One can argue that the proof of Markowski's Theorem 9(i) in "Chain-complete posets and directed sets with applications" can be adapted to our situation. Still, the clear-cut statement of the aforementioned theorem is not present in Markowski's paper.


texts: Hardness of finding if a vertex lies on a simple directed path between two vertices

texts:
Given a directed graph $G = (V, E)$ and three vertices $u, v, w \in V$. Is it NP-Hard to find whether there is a simple path from $u$ to $v$ passing through $w$?

I found a couple of hardness statements of similar problems referring all to the same paper [The directed subgraph homeomorphism problem, Fortune, Hopcroft and Wyllie, 1980]. The papers include

two disjoint directed paths,
and directed simple cycle passing through two vertices.

However, it is not very clear to me, if this case reduces directly to the paper as in the case of these to problems.


texts: Why do multi-stack visibly pushdown languages label each call/return with a particular stack?

texts:
In A Unifying Approach for Multistack Pushdown Automata, multistack visibly pushdown automata are defined in terms of an alphabet where each symbol is either a call or return for a particular stack or internal.

My question is, why is it necessary (or advantageous) to associate each call and return with a particular stack? Why is it not sufficient to label symbols with just call or return and let the same symbol push/pop from different stacks?


texts: Resources for Church's paper "An Unsolvable Problem of Elementary Number Theory"?

texts:
I'm trying to understand and breakdown into simple English Church's paper for "An Unsolvable Problem of Elementary Number Theory" but I'm not finding anything useful online, only citations and links to the full paper.

Does anyone know any resources I can get to help me understand this paper?


texts: Is anything known about Sokoban with only 1 box?

texts:
This is intended to be a simpler version of my earlier question here.
In this post, 1-Sokoban-search is Sokoban with only 1 box, 1-Sokoban-decision is
the corresponding decision problem, and 1-Sokoban refers to both of those problems.
(You get to choose whether that also means there's only one storage location or
still allows more storage locations.  Everything I say here applies in either case.)
1-Sokoban is trivially in NL.  Since, regardless of whether the ?s are X or blank, the region
?  X
X
XXX?

will have no box and no storage location and be such that the box can be pushed
from the top to exit out the right but can't be pushed from the right to the top, (directed) Grid Graph Reachability / (directed) GG search   can easily be reduced to  1-Sokoban-decision / 1-Sokoban-search  respectively,
so 1-Sokoban is NC1-hard and not known to be solvable by L.
Grid Graph distance is known to be in  UL ∩ coUL ,  so by any search-to-value
reduction, that is no obstacle to putting 1-Sokoban in  UL ∩ coUL .
(However, I don't have any evidence for 1-Sokoban being in even LpromiseFewL.)

Is anything else known about 1-Sokoban?

In particular, I have been unable to come up with any decision-to-search reduction in which the search oracle incorrectly reporting "no solution" never causes false negatives / search-to-decision reduction by any slightly-"natural" class, even with a GGsearch oracle, that can't obviously already solve all of  NL / FNL respectively, and I've also been unable to come up with any
evidence for or against hardness of 1-Sokoban, beyond the reduction from Grid Graphs.


texts: What's the probability for a random graph with degrees greater than 1 to be Hamiltonian?

texts: Given a random graph by the Erdős–Rényi model, if the minimal node degree is greater than 1 (or $\geq 2$), or randomly select a graph from the graphs with node degrees greater than 1 ($\geq 2$), what's the probability for it to be a Hamiltonian graph?


texts: Complete problems and universal simulator machines

texts:
I'm trying to get straight in my mind the relation between complete problems and universal simulator machines.  Some notions of computability have universal machines (Turing-computability) and some don't (FDAs).

When we say that there are $\mathsf{NP}$-complete problems (to take an example) is this the same as saying that a polynomially hampered universal Turing machine is universal for the notion of polytime-computability?

My colleague Ashley Montanaro here (who kindly told me about this site) told me once that the class of $\mathsf{DSPACE}(o(\log\log n))$ problems is the same as the class of regular languages.   Does this mean that there is no universal machine for the $\mathsf{DSPACE}(o(\log\log n))$ problems?


texts: Well known classes of boolean formulas that require exponentially long resolution proofs

texts:
You might often find cutting plane methods, variable propagation, branch and bound, clause learning, intelligent backtracking or even handwoven human heuristics in SAT solvers. Yet for decades the best SAT solvers have relied heavily on resolution proof techniques and use a combination of other things simply for aid and to direct resolution-style search. Obviously, it's suspected that ANY algorithm will fail to decide the satisfiability question in polynomial time in at least some cases.

In 1985, Haken proved in his paper "The intractability of resolution" that the pigeon hole principle encoded in CNF does not admit polynomial sized resolution proofs. While this does prove something about the intractability of resolution-based algorithms, it also gives criteria by which cutting edge solvers can be judged - and in fact one of the many considerations that goes into designing a SAT solver today is how it is likely to perform on known 'hard' cases.

Having a list of classes of Boolean formulas that provably admit exponentially sized resolution proofs is useful in the sense it gives 'hard' formulas to test new SAT solvers against. What work has been done in compiling such classes together? Does anyone have a reference containing such a list and their relevant proofs? Please list one class of Boolean formula per answer.


texts: Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

texts: What is the fastest known undirected graph isomorphism algorithm?


texts: Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

texts:
Let $\mathcal A$ be an automaton, then I define the following $\omega$-language accepted by $\mathcal A$:
$$
 L'(\mathcal A) := \{ \eta \in X^{\omega} : v \sqsubset \eta \mbox{ implies } v \in L(\mathcal A) \}
$$
where $v \sqsubset \eta$ means $v$ is a finite prefix of $\eta$ and $L(\mathcal A)$ denotes the finite (regular) language accepted by $\mathcal A$.

For $k > 0$ denote by $PF_k(\eta)$ the set of all $\omega$ words $\xi$ such that the first $k$ letters of $\eta$ and $\xi$ are the same (they share a common prefix of length $k$) and the infixes (or factors) of length $k$ are the same, i.e. if $F_k(\eta)$ denotes the factors of length $k$ then $PF_k(\eta) = \{ \xi : \eta[0...k] = \xi[0...k], F_k(\eta) = F_k(\xi) \}$.

Now I want to show, if $\eta \in L'(\mathcal A)$, then there exists a $k > 0$ such that $PF_k(\eta) \subseteq L'(A)$. First I thought that this does not hold, so that for every $\eta \in L'(A)$ and $k > 0$ you can find some $\xi \notin L'(A)$ such that $\xi \in PF_k(\eta)$, but didn't succeeded in constructing a counter-example, so I guess it holds but I have no idea how to proof it?


texts: Finding the identity with permutation chains

texts:
I have the following problem: I'm given a list of size $K$ of random integer permutations of $[1..n]$, named $P_1$ to $P_K$, and an additional random permutation $Q$.

How hard is to find a sequence $s(j)$ of $U$ subscripts in $[1..K]$, such that $P_{s1}(P_{s2}(...(P_{sU}(Q(i))))) = i$  for every $1\leq i \leq n$, where Q is an initial random permutation.

In other words, the composition of a subset of the given permutations must be the inverse of $Q$.

I suppose this problem, as $n$ grows, is exponential.

Note: the result must be the list of $s(j)$ values, and that list should be polynomial to $n$ in size. I cannot accept something like "apply P1 2^456 times" as an answer.

It is related to any $\sf{NP}$-Complete problem?

Any idea? Thanks!


texts: Find the maximum set whose subset sum is unique for every of its subset

texts:
We are given a set of $n$ positive integers.
We assume all of them are bounded by a polynomial of $n$.
We would like to find a subset $S$ of these $n$ numbers such that
for any $T_1,T_2\subseteq S$, the sum of numbers in $T_1$ is not equal to that of $T_2$.
We want the size of $S$ is maximized.
Clearly, the problem is in NP and can be solved in $n^{O(\log n)}$ time (Since $|S|\leq O(\log n)$).
Is this problem polynomial time solvable?
Is this problem studied before? Any help is appreciated.


texts: Tenth Hilbert problem on interval arithmetic

texts:
What is the decidability status of Hilbert's Tenth problem interpreted over interval arithmetic?
In details, let $p\in\mathbb{Q}[x_1,\ldots,x_n]$ be a Diophantine polynomial. The problem is that of deciding whether there exist $n$ intervals $v_1,\ldots,v_n$ with bounds in $\mathbb{N}$ such that $0\in p(v_1,\ldots,v_n)$ (where $p$ is evaluated using standard interval arithmetic).
Is the problem decidable?


texts: Are there protein-based computational models?

texts:
Is there a framework/formalism that defines computational models based on proteins other than Adleman's DNA model or this work by Cherry and Qian?

Edit 2020 (related models/ideas based on DNA):
DNA allows to store large amount of data, it seems to me that the combination of DNA-based memory methods and technologies like CRISPR as computational workers might be an interesting and relevant venue.

DNA-sequencing-based readers
DNA sequencing is the most direct way to extract information from DNA-based recording devices. Sanger sequencing can provide low-throughput but high-accuracy sequences of ~800 bp. Nucleotide polymorphism frequencies across a population at specific DNA addresses can also be determined from Sanger chromatograms88. Alternatively, NGS can determine the sequence of DNA addresses at a much larger scale, and progress in this arena14 has enabled analysis of many recent recording devices. Short-read sequencing-by-synthesis (from Illumina) can currently provide the highest throughput and read quality, albeit with a maximum read length of ~600 bp89. For DNA addresses with longer lengths (for example, large recombinase-targeted loci87,90), long-read sequencing technologies such as single-molecule real-time sequencing (SMRT; from Pacific Biosciences) or nanopore sequencing (from Oxford Nanopore Technologies) are necessary. Although long-read sequencing modalities currently have a relatively lower throughput and lower quality than more mature short-read NGS platforms, portable instruments such as the MinION nanopore sequencer offer exciting real-time readout of DNA data storage91.

Sheth, Ravi U., and Harris H. Wang. "DNA-based memory devices for recording cellular events." Nature Reviews Genetics 19.11 (2018): 718-732.
As mentioned in the answers, $\pi$-calculus and bioambinet calculus are relevant here as well:

An Abstract Machine for the Stochastic Bioambient Calculus by Andrew Phillip
The π-calculus as an Abstraction for Biomolecular Systems by Aviv Regev & Ehud Shapiro


texts: Bounds on the smaller eigenvalues of the adjacency matrix of a graph

texts:
Are there any known (non-trivial) bounds (combinatorial in nature, based on poly-time computable properties of a graph) on the third, down to the smallest, eigenvalue of an (un-weighted) adjacency matrix? For example we know that the largest eigenvalue admits the following bounds
$$\max(\sqrt{d_{\max}}, d_{\text{ave}})\le \lambda_{\max}=\lambda_1 \le d_{\max}$$
Anything of the above flavor for $\lambda_i$, $i\ge 3$?
(Given that these can be negative, (lower) bounding $|\lambda_i|$ might seem more appealing.)


texts: Facility Location problem, multiple facilities with no specific locations

texts:
My problem is as follows:

I have $n$ customers, each with a predetermined location in the plane, i.e. $(x,y)\in\mathbb{R}^2$. I have $k$ facilities I want to distribute such that each one of them can serve up to $m$ customers.

I'm struggling with how I should formulate the cost function so I can solve it with non-linear programming (I'm going to start off by using http://abel.ee.ucla.edu/cvxopt/).

I have also though about just using a modified $k$-means method if everything else fails but I really want to try the other option first.

Edit: If the task above is too hard I could consider skipping the requirement that each facility can only serve $m$ customers and that I only have to distribute the facilities to minimize distance to their customers.

Edit 2 (real scenario to explain the reason for this formulation): A company has location information for all their customers, the company is going to open $k$ facilities (e.g. shops). Each facility can serve up to $m$ customers, how should we place the facilities such that the total distance to the customers they serve is minimized?


texts: Background Required to understand Quantum Monte Carlo techniques?

texts:
I'm trying to decide whether or not to do a project for a professor.

The project involves writing a survey paper (of high enough quality to get his research group up to speed for a peripheral project) about Quantum Monte Carlo. The application they have in mind is calculating the energy of a quantum system and comparing QMC to a different method of doing such calculations.

What sort of background knowledge is required to get a grip on QMC (enough to be able to understand the significance of foundational and some more recent papers in the field). The survey paper would be due sometime by the end of school.

Don't skip anything I really need to know - assume I only an average upper-level undergrad CS major's knowledge of physics and computer science.

Reference suggestions are very welcome.


texts: Subquadratic 3SUM when one set is in [n^1.99]

texts:
Chan and Lewenstein (STOC 2015) said:

  3SUM for three integer sets where only one set is assumed to be in $[n^{2−\delta}]$ can still be solved
  in subquadratic time (by doing several FFTs, without requiring additive combinatorics - a simple exercise we leave
  to the reader).

Note, that the other 2 sets can be from $[n^{3+o(1)}]$.

Nevertheless I have no idea how to solve this exercise. Do you have any hints? (probably you can use their paper but it looks like an overkill)


texts: When does randomization speed up algorithms and it "shouldn't"?

texts:
Adleman's proof that $BPP$ is contained in $P/poly$ shows that if there is a randomized algorithm for a problem that runs in time $t(n)$ on inputs of size $n$, then there also is a deterministic algorithm for the problem that runs in time $\Theta(t(n)\cdot n)$ on inputs of size $n$ [the algorithm runs the randomized algorithm on $\Theta(n)$ independent randomness strings. There must be randomness for the repeated algorithm that is good for all $2^n$ possible inputs]. The deterministic algorithm is non-uniform - it may behave differently for different input sizes.
So Adleman's argument shows that - if one doesn't care about uniformity - randomization can only speed-up algorithms by a factor that is linear in the input size.

What are some concrete examples where randomization speeds up computation (to the best of our knowledge)?

One example is polynomial identity testing. Here the input is an n-sized arithmetic circuit computing an m-variate polynomial over a field, and the task is to find out whether the polynomial is identically zero. A randomized algorithm can evaluate the polynomial on a random point, while the best deterministic algorithm we know (and possibly the best that exists) evaluates the polynomial on many points.

Another example is minimum spanning tree, where the best randomized algorithm by Karger-Klein-Tarjan is linear time (and the error probability is exponentially small!), while the best deterministic algorithm by Chazelle runs in time $O(m\alpha(m,n))$ ($\alpha$ is the inverse Ackermann function, so the randomization speed-up is really small). Interestingly, it was proved by Pettie and Ramachandran that if there's a non-uniform deterministic linear time algorithm for minimum spanning tree, then there also exists a uniform deterministic linear time algorithm.

What are some other examples?
Which examples do you know where the randomization speed-up is large, but this is possibly just because we haven't found sufficiently efficient deterministic algorithms yet?


texts: Fast approximate middle of points in a metric space?

texts:
Given $N$ points $X_i$ in a metric space
and a measure of "middleness"
$ \qquad \qquad \mathsf{middle}( X_i ) \equiv
\frac{1}{N} \sum_j \mathsf{metric}( X_i, X_j ) $
can one find an $X_i$ near the middle of all $N$ points,
i.e. roughly minimizing $\mathsf{middle}( X_i )$,
in time and space both better than $O( N^2 )$ ?
If not in general, are there cases that can be done — trees, Euclidean metrics ?

Clarification: by "space better than $O(N^2)$" I mean,
are there approximate methods that give many nearby pairs
after looking at $O(N^{1+\epsilon})$ of all pairs ?
This is broader than just middles.
Of course, guarantees are then gone, or empirical or statistical.
But methods that work for $N$ 10000 or 1000000
would have broad application.
(Is that clear, is it worth a separate question ?)


texts: Recent TCS publications with philosophical aspects

texts:
Many computer science publications from the 1950s and 1960s contain fascinating philosophical speculations on the nature of the mind and the meaning of information in relation to the physical world. Famous examples are the "Turing Test", Zuse's "Calculating Space", Wheeler's "it from bit" etc.

Today such themes are widely covered in popular science books, but seem all but gone from serious research publications. What are some examples of recent TCS publications with philosophical content or implications?


texts: Is "Experimental Complexity Theory" being used to solve open problems?

texts:
Scott Aaronson proposed an interesting challange: can we use supercomputers today to help solve CS problems in the same way that physicists use large particle colliders?

  More concretely, my proposal is to
  devote some of the world’s computing
  power to an all-out attempt to answer
  questions like the following: does
  computing the permanent of a 4-by-4
  matrix require more arithmetic
  operations than computing its
  determinant?

He concludes that this would require ~$10^{123}$ floating point operations, which is beyond our current means.  The slides are available and are also worth reading.

Is there any precedence for solving open TCS problems through brute force experimentation?


texts: Reference for unpublished but quoted manuscript

texts:
Is there a place to locate the reference
"[Smi88] D. V. Smirnov, ``Shannon's Information Methods for Lower Bounds for Probabilistic Communication Complexity,'' Master's thesis, Moscow University, 1988"
mentioned in this paper http://cs.au.dk/~bromille/Papers/asym.pdf?


texts: What are some good resources (books, articles, sites) about polygon intersection and union algorithms?


texts: What are the known pseudo-polynomial PSPACE-complete problems?

texts:
please can you provide either a reference, or give particular examples of PSPACE-complete problems which are solvable in pseudo-polynomial time?

Additonal Notes:

Definition of pseudo-polynomial time: http://en.wikipedia.org/wiki/Pseudo-polynomial_time

In reply to some comments mentioned earlier. I have asked earlier if there were any problems which were PSPACE-complete which had an FPTAS. The surprizing answer was YES!

Does There exist a particular PSPACE Complete Problem which has a FPTAS algorithm?

This is therefore a follow-up question.

(Note that the EXP conjecture apply to the complexity class NP, yet there exists NP-complete problems which are solvable in psuedo-polynomial time!)

Addendum...
Sasho Nikolov asked about FPT and Pspace. I know that there are FPT problems which are Pspace , Exp, Exp Space complete etc... Unfortunately I do not have references... Will correct when I remember

Thanks!!!

Zelah


texts:
Here is a variant of the classic partition problem: Given a list of integers can it be partitioned into $S_1$, $S_2$, and $S_3$, with $S_1$ and $S_2$ nonempty, so the sum of elements in $S_1$ equals the sum of elements in $S_2$?

Is this problem NP-hard?


texts: Is there a list of notations developed for regular expressions?

texts:
There is, of course, PCRE.
I know also of Olin Shiver's Structural Regular Expressions, and Rob Pike's Structural Regular Expressions.
I also understand that Raku's regexps are different from perl's implementation
Are there other ways to express regular expressions? Like, is there a syntax based on Object Oriented Programming? Concatenative Programming? Visual ways to represent the action of the regexp?
I'm thinking of a list of answers like this one for visualizations of lambda calculus by prathyvsh