texts: Hardness of approximation assuming NP != coNP

texts:
Two of the common assumptions for proving hardness of approximation results are $P \neq NP$ and Unique Games Conjecture. Are there any hardness of approximation results assuming $NP \neq coNP$ ? I am looking for problem $A$ such that "it is hard to approximate $A$ within a factor $\alpha$ unless $NP = coNP$".

It is known that "showing factor $n$ NP-hardness for shortest vector problem would imply that $NP = coNP$". Note that this is the "opposite" of what I am looking for.

Clarification : It is possible that $NP=coNP$ and still the P vs NP question is open. I am looking for hardness of approximation result which will become false if $NP=coNP$ but is unaffected (i.e., still remains as a conjecture) by $P \neq NP$.


texts: Is there a computing problem which is in quasi-polynomial time but is (maybe) not in $\beta P$?

texts:
Quasi-polynomial time, or QP for short, is a complexity class on deterministic Turing machine. Here is the precise definition:https://complexityzoo.uwaterloo.ca/Complexity_Zoo:Q#qp

While βP is a complexity class of limited nondeterminism. Here is the precise definition: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap

It is easy to see that any machine of βP can be simulated by a machine of QP, namely, βP $\subseteq$ QP.

But do we have an example, a problem that is in QP but not in βP, even if we just have no precise proof that the problem is not in βP?


texts: Does deterministic PIT produce deterministic irreducible polynomial generation?

texts:
In $\Bbb F_q[x]$ given $d\in\Bbb N$ there is a deterministic $O(poly(nd\log q))$ algorithm to find an irreducible polynomial with $d=deg(x)$ under $GRH$ and an unconditional randomized algorithm.

Do we know of a randomized $O(poly(nd\log q))$ algorithm to find an irreducible polynomial in $\Bbb F_q[x_1,\dots,x_n]$ given $d_1,\dots,d_n\in\Bbb N$ with $d=\max_{i\in\{1,\dots,n\}}d_i$ and $d_i=deg(x_i)$ at every $i\in\{1,\dots,n\}$?
Does derandomizing PIT derandomize these unconditionally?


texts:
Let's say we have a single-layer feed forward neural network with k inputs and one output. It calculates a function from  $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace $, it's fairly easy to see that this has at least the same computational power as $AC^0$. Just for fun, we'll call the set of functions computable by a single layer neural network "$Neural$".

It seems, however, that it might have more computational power than $AC^0$ alone.

So ... is $AC^0 \subseteq Neural$ or is $Neural = AC^0$? Also has this kind of complexity class been studied before?


texts: What is the number of languages accepted by a DFA of size $n$?

texts:
The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this:

Define a DFA as $(Q,\Sigma,\delta,q_0,F)$, where everything is as usual and $\delta:Q\times\Sigma\to Q$ is a (possibly partial) function. We need to establish this since sometimes only total functions are considered valid.
For every $n\geq 1$, define the (equivalence) relation $\sim_n$ on the set of all DFAs as: $\mathcal{A}\sim_n\mathcal{B}$ if $|\mathcal{A}|=|\mathcal{B}|=n$ and $L(\mathcal{A})=L(\mathcal{B})$.
The question is, then: for a given $n$, what is the index of $\sim_n$? That is, what is the size of the set $\{L(\mathcal{A})\mid\mathcal{A}\textrm{ is a DFA of size }n\}$?

Even when $\delta$ is a total function, it doesn't seem to be an easy count (for me, at least). The graph might not be connected, and the states in the connected component containing the initial state might all be accepting, so, for example, there are many graphs of size $n$ accepting $\Sigma^*$. Same with other trivial combinations for the empty language and other languages whose minimal DFA has fewer than $n$ states.
(A naïve) recursion doesn't seem to work either. If we take a DFA of size $k$ and add a new state, then, if we want to keep determinism and make the new graph connected (to try to avoid trivial cases), we have to remove a transition to connect the new state, but in that case we may lose the original language.
Any thoughts?
Note. I updated the question again, with a formal statement and without the previous distracting elements.


texts: Can a computer simulate itself as part of a simulated world?

texts:
Let's say you build a computer that will calculate the state of all atoms in the Universe at certain future point in time. Because the Universe is, by definition, everything that exists (and anything that interacts with the rest), it also includes the computer that you are building. Can you calculate the state of all atoms in the Universe using your computer, including the atoms of the computer itself?

If such a computer is not possible for some other theoretical or practical reason, then what is it?


texts: Program for computing Tree decomposition of a graph

texts: Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my input instances will be really small (~10 nodes) and "k" is fixed.


texts: Epsilon-closure and DFA minimization algorithms for probabilistic NFA

texts:
Are there any algorithms performing e-closures and DFA minimizations for probabilistic Finite Automata? Given that probabilistic NFAs might have multiple accepting paths for generating equivalent strings with different probabilities, do current minimization algorithms allow to reduce such amount of complexity to generating just one string with given fixed probability?
I am aware of e-closure and DFA minimization for standard Finite Automata, but I was able to find no paper/algorithm for automata with probabilities.


texts: How to build comparison operator (comparator) in an arithmetic circuit

texts:
I am trying to convert a basic program into an arithmetic circuit. I am stuck on the step of converting the greater than operator into an arithmetic circuit. To be specific, I do not know how to convert the following into an arithmetic circuit (where x,y is input):

if x >= y:
    return 1
else:
    return 0

To be clear, I need to be able to express this in terms of an ARITHMETIC circuit. Meaning that I need to be able to compute this using only addition and multiplication of numbers (in Z_p).

I've been searching all of the web for solutions, but everything I find tells me how to do this with boolean circuits. I am aware that I can convert the numbers into their bit string and do this boolean way. I would like to know of any alternative way to do this. This show be possible to do with just addition and multiplication, but I cannot figure out how to.

For context, I'm considering this in the case of Multi-Party Computation. Therefore, taking advantage of how I represent my number (i.e. two's complement) will not work because my number will be split into secret shares.


texts:
Given two directed acyclic graphs $G_1$ and $G_2$, is it NP-Complete to find a one-to-one mapping $f:V(G_1) \rightarrow V(G_2)$ such that $(v_i,v_j) \in D(G_1)$ if and only if $(f(v_i),f(v_j)) \in D(G_2)$?

$D(G)$ is defined as the set of arcs in $G$.


texts: Hyperdoctrines and Monadic Second Order Logic

texts:
This question is essentially the question I asked on Mathoverflow.

Monadic Second Order (MSO) logic is second order logic with quantification over unary predicates. That is, quantification over sets. There are several MSO logics that are fundamental to structures studied in computer science.

Question 1. Is there a categorical semantics for Monadic Second Order Logics?

Question 2. Treatments of categorical logic often talk about "higher order intuitionistic logic." Am I right to assume that they are referring to higher order functions, rather than quantification over second order predicates?

Question 3. (Added, 08 Nov 2013, after Neel's answer) My understanding of first-order quantification (in terms of the presentation of Pitts mentioned below) is that it is defined with respect to the pullback $\pi^*$ of a projection morphism $\pi$. Specifically, universal quantification is interpreted as the right adjoint of $\pi^*$ and existential quantification is interpreted as the left adjoint of $\pi^*$. These adjoints have to satisfy some conditions, which I have sometimes seen referred to as Beck-Chevalley and Frobenius-Reciprocity conditions.

Now if we want to quantify over predicates I assume I'm in a Cartesian closed category, the picture is nearly the same, except that $X$ below has a different structure from before.

$$  \exists_{I,X}, \forall_{I,X}: P_C(I\times X) \to P_C(I) $$

Is that right?

I believe my mental block was because I was previously dealing with first-order hyperdoctrines and did not need the category to be Cartesian closed and did not consider it later.

Background and Context.
I have been working with the presentation of categorical logic by Andy Pitts in his Handbook of Logic in Computer Science article, but I'm also familiar with the treatment of Tripos theory in his doctoral dissertation, as well as the notes of Awodey and Bauer. I started out studying Crole's Categories for Types and the book by Lambek and Scott but it's been a while since I consulted the last two texts.

For motivation, I am interested in the kind of MSO logics appearing in the theorems below. I do not want to deal with a logic that is expressively equivalent to one of these. Meaning, I do not want to encode monadic predicates in terms of higher order functions and then deal with another logic, but I'm happy to study a semantics that includes such an encoding under the hood.

(Buechi and Elgot Theorem) When the universe of structures is finite words over a finite alphabet, a language is regular exactly if it is definable in MSO with an interpreted predicate for expressing consecutive positions.
(Buechi's Theorem) When the universe of structures is $\omega$-words over a finite alphabet, a language is $\omega$-regular exactly if it is definable in MSO with an appropriate interpreted predicate.
(Thatcher and Wright Theorem) A set of finite trees is recognizable by a bottom-up finite tree automaton exactly if it is definable in MSO with an interpreted predicate.
WS1S is the Weak Monadic Second order theory of One Successor. Formulae define sets of natural numbers and second order variables can only be interpreted as finite sets. WS1S can be decided by finite automata by encoding tuples of natural numbers as finite words.
(Rabin's Theorem) S2S is the Second order theory of Two Successors. S2S can be decided by Rabin automata.


texts: Do you know a shortest path algorithm for weighted graphs with hard time windows on the edges and waiting allowed?

texts:
Title says it all. I have a weighted Graph G={V,E,ETW} where V is the node set, E the edge set and ETW is a set of edge time windows. A edge time window is a 3-Tuple (edge, starttime, endtime) with the meaning that in the intervall [starttime, endtime] the given edge is not available. The problem now is to find a shortest path from a start node to an end node in which it is allowed to wait at the nodes (to use a edge after it´s time window).

Does anybody know a algorithm for this problem? (and in the best case the paper in which the algorithm was published)

Greetings, Christoph


texts: Is it possible to evaluate interaction combinators efficiently using a path-traveling strategy?

texts:
Interaction combinators can be evaluated using a path traversing strategy. That is, instead of applying annihilation/commutation rules to active pairs, one simply walks through the graph using a 2-stack machine to keep track of the exit ports.

It is known that this strategy, used naively, can have an exponential slowdown in relation to the former strategy. But that doesn't consider the possibility of jumps. Suppose that, instead of merely walking through the graph, the cursor also keeps track of the nodes it passed through. It it comes back to the same node, it jumps directly to the node whose active port would-be to interact with that one.

Is it possible to use this strategy to evaluate interaction combinators? Can it be as efficient as the graph-reduction view?


texts: Finding vertex separator such that the induced subgraph has minimal number of edges

texts:
My problem is related to edge and vertex cuts with a little twist.
Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that the induced subgraph $G[S]$ has minimal number of edges.
Consider the following graph:

The red edges are the minimal edge cut. The blue vertices are the minimal vertex cut. The green vertices are a vertex cut such that the induced subgraph has the least number of edges. I try to find the green cut. In fact, the number of vertices is not required to be minimal as long as the number of edges in $G[S]$ are minimal.
Is there an algorithm in $P$ to solve this problem? Do you have an idea how to approach the problem?


texts:
The weakest precondition of while loop $\mathtt{while}(G)\{C\}$ with respect to postcondition $P$ can be characterized by the least fixed point of the predicate transformer

$X ~\mapsto \neg G \wedge P ~\vee~ G \wedge \mathsf{wp}(C, X)$

where $\mathsf{wp}(C, X)$ is the weakest precondition of loop body $C$ with respect to postcondition $X$.

How can strongest postconditions of while loops be defined/characterized in a similar fashion, i.e. given a precondition $Q$ and a predicate transformer $\mathsf{sp}(C, {\cdot})$, how can one characterize the strongest postcondition of $\mathtt{while}(G)\{C\}$ with respect to precondition $Q$ as a fixed point of some predicate transformer?


texts: Construction of a graph which has regular subgraphs at each iteration of a recursive process

texts:
I am studying Graph Isomorphism and also trying to figure out the complexity of a certain class of graph. The graph I am studying at the moment is described below

Description :

$G$ is a $r$ regular graph, $k$ connected( not a complete , cycle graph).  A vertex of $G$ is $x_1$.
All vertices which are not adjacent to $x_1$ create a sub-graph $C_1$.
  All vertices adjacent to $x_1$ create a sub-graph $, D_1 $.
A vertex of $D_1$ is $x_2$.

Using same method, based on adjacency of $x_2$ , $D_1$ can be divided.

All vertices which are not adjacent to $x_2$ create a sub-graph $C_2$.

All vertices adjacent to $x_2$ create a sub-graph $, D_2 $.
    In general , $ D_{y-1} $ is a graph and can be divided/ partitioned  in to 2 sub graphs $C_y,  D_y $ .

There are 2 restrictions, they are-

$C_y,  D_y $  are $s_y , t_y > 0 ; s_y \neq t_y; $ regular graphs respectively for all iteration $y$
$C_y,  D_y $  cannot be complete bipartite graph (utility graph), complete graph or disjoint union of complete graphs.

$G$ can be divided/ partitioned maximum $\log_2(|G|)$ times , using  this dividing process recursively if $G$ is a 3 clique free graph , this condition  implies $t_y \leq |D_y|/2$.

Questions :

Does there exist such graph in current literature  as described above(follows restriction 1 or 2 or both)?

Motivation : An algorithm  runs faster than existing results for this kind of graphs.

Related  papers:

V.A.Taskinov. Regular subgraphs of regular graphs. Sov.Math.Dokl.26(1982), 37-38 .
In this paper he proved the following : Let $0<k<r$ be positive odd integers. Then every $r$-regular graph contains a $k$-regular subgraph (Here, the graph need not be simple).
N. ALON,S. FRIEDLAND,G. KALAI.   Regular Subgraphs of Almost Regular Graphs. JOURNAL OF COMBINATORIAL THEORY, Series B 37, 79-91 (1984)

Any advice will help.


texts: For which graphs is the DFS tree always a path?

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

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

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


texts: Closure ordinals for inductive types with function spaces

texts:
Functors built from finite products and sums have closure ordinal $\omega$, detailed nicely in
this manuscript by Francois Metayer. i.e. we can reach the inductive type $nat := \mu X. 1 + X$ by iterating the functor $1 + X$, which reaches its fixed point after $\omega$ iterations.

But once we allow constant exponentiation, such as in $\mu X. 1 + X + (nat \rightarrow X)$, then $\omega$ isn't enough.

I'm looking for results that include exponentiation. What kind of ordinals are sufficient?

Especially appreciated would be a reference that presents a proof that such functors are $\alpha$-continuous for some ordinal $\alpha$ like in the above manuscript.


texts: Why is the consensus problem so important in distributed computing?

texts:
In distributed computing, the consensus problem seems to be one of the central topics which has attracted intensive research. In particular, the paper "Impossibility of Distributed Consensus with One Faulty Process" received the 2001 PODC Influential Paper Award.

So why is the consensus problem so important? What can we achieve with consensus both in theory and in practice?

Any references or expositions would be really helpful.


texts: Is there a version of MIP=NEXP with relatively efficient provers?

texts:
(My question is not a duplicate of this question.)

Fix a good coding of non-deterministic random-access machines.

For non-negative integers $m$ that code such a machine, let

$\operatorname{states}(m)$ denote the number of internal states in the coded machine.

("hc" stands for "hard-coded".)

Choose some polynomial function $hcpoly$, and let $L$ be the language

$\{\langle m\hspace{.02 in},\hspace{-0.025 in}t,\hspace{-0.02 in}s\hspace{-0.02 in}\rangle \;\; : \;\; m$ codes such a machine and $\:t\leq 2^{hcpoly(\operatorname{states}(m))}\:$ and

there is a sequence of non-deterministic choices which will make that machine

accept the empty string in at most $t$ time without using more than $s$ space$\}\;$.

  Is there a MIP protocol for $L\hspace{.02 in}$ in which the provers use not

  much more than $t$ time and/or not much more than $s$ space?

That could just mean $\:poly(\hspace{.02 in}\operatorname{length}(\langle m\hspace{.02 in},\hspace{-0.025 in}t,\hspace{-0.02 in}s\hspace{-0.02 in}\rangle))\:$ time and space, although

ideally it would be $\:poly(\operatorname{states}(m))\hspace{-0.03 in}\cdot \hspace{-0.03 in}t\:$ time and $\:poly(\operatorname{states}(m))\hspace{-0.03 in}+\hspace{-0.03 in}s\:$ space.


texts:
I am trying to find any described formalism which introduces free variables into word grammars (I emphasize here word in order not to be confused with very similar thing in tree grammars).

What I mean is something like this:

$AX_1B\rightarrow AX_1CX_1B$

where $X_1$ can be substituted by any sequence $\alpha$ of terminals and non-terminals ($\alpha\in (T\cup N)^+$).

Say, if our derivation is $AbEdB$, then this rule will give next derivation as:
$AbEdB\Rightarrow AbEdCbEdB$.

More generally, rules of this form can be described as:
$\alpha\rightarrow\beta$, where $\alpha,\beta\in (T\cup N\cup X)+$, where $X=\{X_1,\dots,X_n\}$. For more details, please see the updates below.

It is clear that variables them self do not add anything new into grammars per se. But what I am looking for is existent works which describe how such free variables fit into known classes of grammars. For instance, will such grammar be weak-equivalent to the context-sensitive grammar under some circumstances or not?

UPD: Answering commentary: $X_i$ is a kind of pattern, so that all $X_i$ can be replaced by regular expression groups. Like in the foregoing example, it is "$A(.+)B$", where $(.+)$ is a named group "$X_1$". In other words, the rule containing $X_i$ variables can be applied if its entire left-hand side string, considered in the mentioned way, conforms as pattern to any substring within the current derivation.

UPD-2: Answering commentary #2:

1) Each $X_i$ from the left-hand side should  necessarily be present in the right-hand side.

2) Each $X_i$ always represent $(.+)$, i.e. it can not have an empty value.

3) For each rule, set of variables $\{X_i\}$ is unique. So they should not be considered as something spread across several rules.

4) Yes, each rule can contain multiple free-variables. Further more, each $X_i$ can be present in the left-hand side only once, while in the right-hand side more than one time (arbitrary number of times, but not zero).

5) There are no any restrictions on the variables order. They can have arbitrary order as in the left-hand side, so as in the right-hand side (i.e. the rule $AX_1BX_2C→DX_2EX_1F$ is valid).


texts: Does every online algorithm has an offline counterpart?

texts:
According to the wikipedia page for Online algorithms, it states:

  "Not every online algorithm has an offline counterpart."

At the time of asking this question there is no citation for this claim.
How it possible to not have an offline counterpart? What is an example of an  algorithm that is online only?


texts: Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

texts:
Many believe that $\mathsf{BPP} = \mathsf{P} \subseteq \mathsf{NP}$. However we only know that $\mathsf{BPP}$ is in the second level of polynomial hierarchy, i.e. $\mathsf{BPP}\subseteq \Sigma^ \mathsf{P}_2 \cap \Pi^ \mathsf{P}_2$. A step towards showing $\mathsf{BPP} = \mathsf{P}$ is to first bring it down to the first level of the polynomial hierarchy, i.e. $\mathsf{BPP} \subseteq \mathsf{NP}$.
The containment would mean that nondeterminism is at least as powerful as randomness for polynomial time.
It also means that if for a problem we can find the answers using efficient (polynomial time) randomized algorithms then we can verify the answers efficiently (in polynomial time) .

Are there any known interesting consequences for $\mathsf{BPP} \subseteq \mathsf{NP}$?
Are there any reasons to believe that proving $\mathsf{BPP} \subseteq \mathsf{NP}$ is out of reach right now (e.g. barriers or other arguments)?


texts: Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?

texts:
Lets define the class

$ZBQP = \{ L \mid \exists \textit{P-uniform circuit family } \{C_i\}, \forall n \in \mathbb{N}, |x| = n, |\langle 0|C_n|x \rangle - I(x \in L)| \leq 9/10 \Longleftrightarrow x \in L\}.$

We note a construction of Ashley Montanaro, that for any quantum circuit $C$ there exists some multilinear polynomial of size linearly proportional to $C$, $f_C$, such that

$\langle 0 | C|0\rangle = \frac{gap(f_C)}{2^n}$

where $n$ is the number of variables in the polynomial and

$gap(f) = |f^{-1}(0)| - |f^{-1}(1)|.$

We now define CAPP, the Circuit Approximate Probability Problem, which is a function problem:

$C \mapsto v \textit{ where } |v - Pr_x(C(x) = 1)| \leq 1/10.$

Using this problem, we can get a $2/10$ error approximation for $gap(f)$, as

$gap(f) = 2^n (Pr(f(x) = 0) - Pr(f(x) = 1))$

and thus we can get an approximation for $\langle 0|C_n|0 \rangle$ (or for $\langle y| C_n |x \rangle$ by modifying the circuit and thus $f_C$ in the obvious way). As we have a two sided error for $ZBQP$ and this approximation gets us close enough to distinguish which side we're on, it seems that this allows us to solve $ZBQP$ problems in basically whatever function classes where we can do $CAPP$, which is suspected to be in $FP$ and is already in $FBPP$.

Does $ZBQP \neq BQP$ for any reason I'm missing? It seems like they may be equal, but I dunno.


texts: What Topics Are Suggested for Ph.D. Research?

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

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

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

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

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

The more you elaborate, the better!


texts: Research and open challenges in Programming Language Theory

texts:
In the spirit of some general discussions like this one, I'm opening this thread with the intention to gather opinions on what are the open challenges and hot topics in research on programming languages. I hope that the discussion might even bring to surface opinions regarding the future of research in programming languages.

I believe that this kind of discussion will help new student researchers, like myself, interested in PL, as well as those who are already somewhat involved.


texts: Are there good locally decodable _erasure_ codes

texts:
Are there known locally decodable erasure codes with

  linear codeword length and $\:n^{o(1)}\:$ query complexity?

According to pages 1 and 4 of this link (which annoying does not give its own date,

though it cites references from 2011), locally decodable (error-correcting) codes

with linear codeword length are only known with query complexity $n^{\epsilon}$ for $\: \epsilon > 0 \;$.

i.e., Does considering erasure codes instead change that?

Such a code could be used for showing that a data host has random access to a given file.


texts: Minimum cut with nonlinear objective function

texts:
Let $G$ be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut $C\subseteq E(G)$, such that $|C|$ is minimum.

Let us generalize it the following way: let $f$ be a polynomial time computable function on the subsets of the edge set, and we look for a cut $C$, such that $f(C)$ is minimum.

Depending on the function, this problem can be easy or hard:

If $f$ depends only on $|C|$, and it is a monotone increasing function of $|C|$, then $f(C)$ will still be minimized by a minimum cut, which can be found in polynomial time.
If $f$ depends only on $|C|$, and it is a strictly monotone decreasing function of $|C|$, then minimizing $f(C)$ is equivalent to finding a maximum cut, which is known to be NP-hard (or, regarding decision, rather than search, it is NP-complete).

Question: In general, how does the complexity of the problem depend on the choice of the function? Which are some (non-trivial) cases, other than case 1 above, when it is solvable in polynomial time?

Furthermore, I would like to propose the following conjecture:

Conjecture: There is a dichotomy here, that is, for every function the problem is either solvable in polynomial time, or else it is NP-hard (assuming we do not restrict the graph to some special graph class).

Is anything known about this?


texts: Downward self-reducibility of factorization

texts: Is integer factorization downward self-reducible? Is anything known about this?


texts: What's the example of natural transformation in 'Type" that is not a parametric function?

texts:
Take a type theory of your choice (perhaps System Fω).
Parametric functions are known to be natural transformations in 'Type' category. Yet not every natural transformation in 'Type' is a polymorphic function.

What is the counter-example?


texts: The chromatic number of a graph as a functor

texts:
I was fooling around with some concept and was wondering if this viewpoint is explored at all. Let INJ-GRAPH be the subcategory of graphs (with morphisms as homomorphisms) whose morphisms consist only of the graph homomorphisms which are injective as sets. Then clearly for such a homomorphism $f : G \to H$ of graphs, the chromatic number of $H$ is at least as large as the chromatic number of $G$. Thus one gets a covariant functor from INJ-GRAPH to the order category of $\mathbb{N}$ (i.e. the category whose objects are natural numbers and there is a unique arrow $a \to b$ if and only if $a \leq b$)

What's more is that this functor preserves coproducts. Indeed the coproduct of two graphs is given by the disjoint union of the graphs, and the chromatic number of this graph is the maximum of the chromatic number of the two graphs. I'm unsure if it preserves more general colimits, but I think at least if they are small then it should be ok.

Anyway, the question is, has this kind of category-theoretic reasoning been investigated in the literature? It currently seems like abstract nonsense, but perhaps it is indicative of something deeper.


texts: Dynamical systems analysis of deep learning

texts:
I am interested in finding out references that apply dynamical systems analysis to develop the "theory" of deep learning, specifically (say) feedforward deep neural nets. The only paper I seem to have found is "Dynamics of learning in deep linear neural networks" from 2014.

I would like to understand if dynamical systems approach makes sense in developing the theory and analysis of deep learning methods.


texts: Should experts in TCS charge money to read proofs that P != NP?

texts:
It's well-known that there are tons of amateurs--myself included--who are interested in the P vs. NP problem.  There are also many amatuers--myself still included--who have made attempts to resolve the problem.

One problem that I think the TCS community suffers from is a relatively high interested-amateur-to-expert ratio; this leads to experts being inundated with proofs that P != NP, and I've read that they are frustrated and overwhelmed, quite understandably, by this situation.  Oded Goldreich has written on this issue, and indicated his own refusal to check proofs.

At the same time, speaking from the point of view of an amateur, I can assert that there are few things more frustrating for non-expert-level TCS enthusiasts of any level of ability than generating a proof that just seems right, but lacking both the ability to find the error in the proof yourself and the ability to talk to anyone who can spot errors in your proof.  Recently, R. J. Lipton wrote on the problem of amateurs who try to get taken seriously.

I have a proposal for resolving this problem, and my question is whether or not others think it reasonable, or if there are problems with it.

I think experts should charge a significant but reasonable sum of money (say, 200 - 300 USD) in exchange for agreeing to read proofs in detail and find specific errors in them.  This would accomplish three things:

Amateurs would have a clear way to get their proofs evaluated and taken seriously.
Experts would be compensated for their time and energy expended.
There would be a significantly high cost imposed on proof-checking that the number of proofs that amateurs submit would go down dramatically.

Again, my question is whether or not this is a reasonable proposal.  Obviously, I have no ability to cause experts to adopt what I suggest; however, I'm hoping that experts will read what I've written and decide that it's reasonable.


texts: Existence of certain graph gadget related to coloring odd hole free graph

texts:
Crossposted from MO.

Wondering about the existence of graph gadget related to coloring
(or 3-coloring) odd hole free graphs.

Let $G$ be simple $k$-chromatic connected graph with two
vertices $u,v$.

Is it possible $G$ to satisfy:

All induced $uv$ paths have odd order (even number of
edges).
In all proper $k$ colorings, $u$ and $v$ have distinct colors
(optional) $G$ doesn't contain induced $C_{2n+1}$ for $n>1$

If this is possible, there is reduction $F$ to odd hole free $F'$.

Replace an edge $u'v'$ by the gadget $G$ where $u'=u,v'=v$ and the
rest vertices of $G$ are new vertices.

According to graphclasses coloring odd hole free is NP hard
and 3-coloring is unknown.

Computer search suggest small gadgets don't exist (modulo errors).


texts: Maximum weight matching with classes of edges in a multi-edge bipartite graph

texts:
Posted a similar question in mathoverflow, have tried to reduce this to Ford Fulkerson, but been stuck. Thought I'd ask TCS community to see if there are any ideas from individuals, here.
Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)_r, (x,y)_b$. We can imagine that we are assigning these edges a "color". Given that each edge $e \in E$ has a weight assigned to it $w(e)$, is it possible to find the maximum weight matching in this graph, subject to constraints on the number of $\leq r$ edges and $\leq b$ edges?
I believe I have a proof that this problem is NP hard (reduction to 3-matching) when I can freely adjust the number of colors, but in the case of two colors, I haven't been able to find anything. I've been searching for the past couple of days for any existing literature on similar problems with no avail. I would appreciate any suggestions or directions in moving forward.
Some ideas I've tested have included reductions to flow/matching problems with disjunctive constraints.
When I posted this question on Math Overflow, I received help from an individual who believed this problem was not NP. He suggested I look into path augmenting algorithms like Ford-Fulkerson, but unfortunately I have not found this to work; the idea of "backwards" flow doesn't make much sense when working with a color constraint.


texts:
My questions are:

[Solved by Dave] Given a learner N, can you design a learner M that behaves differently from N? No.

and

[Solved by Dave] Given a learner N, can you design a learner M that is more powerful than N? No.

and

[Solved by Dave] Given a learner N that always halts, can you design a learner M and a set of natural numbers L, such that (a) for every text T that contains exactly L, M converges on T and (b) there exists a text T' that contains exactly L, such that N diverges on T'? No.

and especially

[Open] Given a learner N that is prudent and always halts, can you effectively design a learner M such that there exists a set of natural numbers L such that

for every text T that contains exactly L, M converges on T and
there exists a text S that contains exactly L, such that N diverges on S?

Note that the difference between the fourth and the third questions is that N is required to be prudent. But M is not required. So N can't simulate M and follow exactly what M does -- M may conjecture a set it does not always converge on.
Also note that a yes answer to the open problem (discussed below) will imply a no answer to the fourth question. I'm saying this because, if you follow Dave's line of thought, you are solving the open problem, which is a stronger statement than (a negative answer to) my question.
And a yes answer to the fourth problem implies a no answer to the open question.
Now come the definitions.
A learner is a Turing machine that, when the input is a (finite) sequence of natural numbers, outputs a program that enumerates a subset of natural numbers.
A text is an infinite sequence of natural numbers.
A learner is said to converge on a text if, when feeding successively longer initial segments of the text, there exists a point after which the learner outputs the same enumeration procedure that enumerates exactly the elements in the text.
A learner diverges on a text if it does not converge on it.
Learner A is said to behave differently from learner B if there exists a text on which A converges but B diverges or A diverges but B converges.
Learner A is said to be more powerful than learner B if A converges on (strictly) more texts than B.
A learner M is prudent iff, if on some initial segment of some text it conjectures a set S, it converges on all texts for S.
Discussion
The background of these problems is the open question whether there exists a program that when given a learner outputs a prudent learner that converges on a superset of texts. Mark Fulk proved that the prudent learner exists (in Theorem 15 of the article "Prudence and other conditions on formal language learning"), but his proof is non-constructive because it has a seemingly undecidable case distinction. The open problem is to give a constructive proof of this theorem.


texts:
Let $(A, \leq)$ be a totally ordered alphabet.

The packing ${\tt pack(u)}$ of a word $u \in A^*$ is the word of $\lbrace 1, \dots, k \rbrace^*$, where $k$ is the number of different letters of $u$, obtained by crushing every letter of $u$.

Formally, let $f_u:A\to \lbrace 1, \dots, k \rbrace$ such that $f_u(x)\leq f_u(y) \Leftrightarrow x\leq y$. Then, if $u=u_1 \dots u_n$, ${\tt pack(u)}$ is the sequence $f_u(u_1) \dots f_u(u_n)$.

For instance, let $A$ be the alphabet $\lbrace a_i : i \in \mathbb{N} \rbrace$ where $a_i \leq a_j$ if and only if $i \leq j$ and $u := a_6 a_2 a_2 a_5 a_1 a_9 a_1$. Then, we have ${\tt pack(u)} = 4223151$.

Questions are

What is the best algorithm to compute the packing of a word?
What is the (time and space) complexity of this problem assuming $\leq$ is computable in constant space and time?


texts: Verifying consistency of strict and non-strict partial orders constraints

texts:
I am building a set of constraints of the kind $x < y$ and $x \leq y$, where $<$ is a strict order and $\leq$ is a non-strict order on the same set, and $x$ and $y$ are abstract variables representing elements of the set.  The laws that relate the two orderings are the same as $<$ and $\leq$ for integers.  I need to make sure that each constraint that I add does not make the set inconsistent (e.g. adding $x < y$ and then $y < x$ I'd get an error).

Now, if I had only the $<$ constraints I could get away with generating a graph and then doing a topological sort, or with disjoint-sets.  The problem is that I'm not sure how to handle the additional $\leq$ constraints.

One idea is to express $x \leq y$ as $\neg (x > y)$, and to keep two graphs:  one for the actual $<$ relations and one for the negated ones.  Then we'd need to check, at each new constraints, whether there are overlapping paths between the two graphs, in which case we'd have a problem.  However this seems rather costly since it seems to me that we'd need to analyze all the pairs each time.

Another idea would be to 'collapse' $\leq$ relations to equalities or $<$ when needed, but again I'm quite uncertain on the details.

Is this problem described somewhere?  As a bonus, I'd like the data structures involved to be purely functional.


texts: Transfering properties from subsets of $X^*$ to subsets of $X^{\omega}$ by using the topology induces by Cantor space

texts:
A language $L \subseteq X^*$ is non-counting of order $n > 0$ iff for all $u,v, w \in X^*$
$$
 uv^nw \in L \Leftrightarrow uv^{n+1} w \in L.
$$
A $\omega$-language (set of infinite sequences) $L \subseteq X^{\omega}$ is non-counting of order $n > 0 $ iff for all $u,v \in X^*, \eta \in X^{\omega}$
$$
 uv^{n}\eta \in L \Leftrightarrow uv^{n+1} \eta \in L.
$$

When talking about languages over finite words, i.e. subsets $L$ of $X^*$ every regular, noncounting languages of order $n > 0$ fullfills the following property: Let $u,v \in X^*$ with
$$
 P_n(u) = P_n(v), I_n(u) = I_n(v), S_n(u) = S_n(v)
$$
and $u \in L$ (where $P_n, S_n, I_n$ denote the prefix, suffix and infixes of length $n$) then also $v \in L$, meaning if two words coincide in their prefix, suffix and infixes of fixed length $n > 0$ then they are either both in $L$ or both not in $L$.

Now when considering subsets of infinite words (and so just prefix and infixes), i.e. $L \subseteq X^{\mathbb N}$, then this does not hold any longer. For consider $L = X^* 0^{\omega}$, then $L$ is regular and non-counting for each $n > 0$. Fix some $n > 0$ and consider
$$
 \xi = 0^n1^n0^{\omega} \quad \mbox{ and } \quad \eta = 0^n1^n0^n1^{\omega}
$$
then $P_n(\xi) = P_n(\eta)$ and $I_n(\xi) = I_n(\eta)$ but $\xi \in L$ and $\eta\notin L$.

The space $X^{\omega}$ is naturally topologized as the Cantor space, i.e. the space with the common-prefix-metric, or equivalently generated by the basis $v\cdot X^{\omega}$, $v \in X^*$. Now the set $L = X^* 0^{\omega}$ is not closed in Cantor space, for example $1^n0^{\omega}$ is in $L$, but its limit $1^{\omega}$ is not in $L$. So I conjecture that if $L$ is closed then the property from finite sets also hold for infinite sequences, i.e. if $L$ is regular and non-counting, then if two words coinside in their prefix and infixes of some specified length, then they are either both in $L$ or not both. A language $L$ is closed in Cantor space iff if it has the property that if $\xi$ is such that every prefix of $\xi$ is the prefix of some words from $L$, then $\xi \in L$.

I conjecture that for closed sets $L$, that if $L$ is regular and non-counting, then membership could be decided by comparing prefix and infixes, but I am stuck with the proof, so any hints or suggestions for me?

EDIT: There is a certain problem with the way it is stated, instead of locally testable use star-free, and instead of just presuppose a set to be closed I will presuppose it to be open or closed, so that the proposition is stable under complementation (which are the star-free and non-countable languages), see the comments.


texts: Smallest disjoint union chain containing a sequence of sets

texts:
Let $\mathcal{A}=\{A_1,\ldots,A_n\}$ be a family of sets, we have the property that $A_1=\emptyset$, and one can obtain $A_i$ from $A_{i-1}$ by adding or deleting a single element.

A family $\mathcal{B}$ is a disjoint union chain, if every set in $\mathcal{B}$ of size at least $2$ can be expressed as a union of two disjoint non-empty sets in $\mathcal{B}$.

The smallest disjoint union chain containing $\mathcal{A}$ has size $O(n\log n)$.

To see this, view a set $A_i$ as leaves of a balanced binary tree. Going from $A_i$ to $A_{i+1}$, we maintain it dynamically using rotations. For each internal node, the set of leaves would be an element in $\mathcal{B}$. Each rotation changes only 2 sets, and there are only $O(\log n)$ rotations. Similarly for insertion and deletions too.

Is there an example where this upper bound is tight?


texts:
In many machine learning algorithm, it is often assumed that outputs of unknown function and their corresponding inputs are given to estimate the unknown function. However, I wonder whether there exist some algorithms which can estimate unknown function using derivative data of unknown function and their corresponding inputs. For example,

$$
\mbox{Given }D = {(x_1, y_1),\ldots,(x_n, y_n)}$$
$$\mbox{ where }y_{1} = \frac{d{f(x)}}{dx}\Bigg|_{x=x_1},\ldots,y_n=\frac{d{f(x)}}{dx}\Bigg|_{x=x_n}$$
$$\mbox{ Find  } f(x).$$

I found one curve fitting method which is called Hermite interpolation in wiki and some papers about Hermite learning. However, in these methods, outputs of unknown function and derivative outputs of it and corresponding inputs are given. Especailly, I want to know there exist some methods that utilize only derivative data. Also is it possible to find unknown function from derivative data, in particular, the error bound between unknown function and our estimator can decrease as the number of training data increases. How can we prove it?


texts: Learning road map for functional programming from the viewpoint of category theory

texts: I am now considering about studying functional programming from the viewpoint of category theory. There are a lot of books about functional programming and category theory, I want some suggestions regarding some comprehensive books and reference materials (like online notes, courses etc)that would contain category theory viewpoint rather than plain functional programming. I have a solid background in Abstract Algebra,commutative algebra, functional programming and bit of category theory too.


texts:
It is well known that a mistake bound can be converted to a PAC bound. I know how to prove a sample complexity of
$$ O( (1/\epsilon)[M + \log(M/\delta)] ), $$
where $M$ is an upper bound on the number of mistakes.
I am told that Nick Littlestone sharpened this to
$$ O((1/\epsilon)[M + \log(1/\delta)])$$
in his 1989 COLT paper. Can anyone describe the proof, or better yet, help me find a copy of this paper? Is this the best possible?


texts: Complexity of enumerating over promise problems and circuits?

texts:
Given an enumeration over all Turing Machine which run with increasing length, is there a ``complexity class'' which describes the complexity of determining whether a given TM satisfies the promise for MA (or QMA for a quantum computer). That is, it outputs 1 if the TM we have selected decides correct with probability p>2/3, and outputs 0 otherwise. Presumably such a task is at least (Q)MA-hard?

If, for whatever reason it is not possible to do this for TMs, can we ask the same questions about an enumeration of circuits with increasing depth/gate number?


texts: Upper bound for number of independent sets

texts: What is the tightest upper bound known for the number of independent sets in a graph?


texts: Approximating the Radius of a (Dense) Graph

texts:
For a (dense) graph, computing its radius is as hard as computer "All Pairs Shortest Paths" (APSP) [1]. So we can focus on approximating the radius.

A $(1+\epsilon)$-approximating of APSP for a directed graph with edge weights in range $[1, M]$ can be found in $O(n^{\omega}/\epsilon \log(M/\epsilon))$, where $\omega$ is the matrix multiplication exponent ($\omega < 2.373$) [2]. Therefore, we have a $(1+\epsilon)$-approximating algorithm for radius with the same running time.

If we restrict our algorithm not to use matrix multiplication (intuitively, only combinatorial algorithms), then we have a (3/2)-approximation algorithm in time $O(n^{2.5})$ [3] (Theorem 3).

My questions are:

Is there any other algorithm for approximating the radius in (dense) graphs?
Is there any hardness results for approximating the radius in (dense) graphs?

[1] Abboud A, Grandoni F, Williams VV. Subcubic equivalences between graph centrality problems, APSP and diameter. In SODA, 2015, SIAM.

[2] Zwick U. All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms. In FOCS, 1998, IEEE.

[3] Roditty L, Williams VV. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, 2013, ACM.

Dense graph: a graph with no restriction on the number of edges, in contrary to a sparse graph which can have only a few edges.

Radius of a graph G = $min_{c\in V(G)} max_{v\in V(G)} dis(c, v)$


texts: Conditions for tractability of 3SAT-Satisfiability

texts:
What I'm wondering specifically is if there is an interesting condition on the percentage of assignments that satisfy a 3SAT formula to guarantee that such problems are tractable.

Suppose for example the class of 3SAT problems that $\epsilon(n) 2^n$ of the $2^n$ possible assignments satisfy the boolean formula; can we efficiently find a satisfying assignment?  For what $\epsilon$ is the resulting problem in P?

Edit note:  Replaced $\epsilon$ with $\epsilon(n)$ to clear up confusion.


texts: Algorithm for 'k'' most frequently occurring numbers

texts:
I have been searching for the most efficient (streaming??) algorithm that tells me the 'k' most frequently occurring elements in a data stream at any point in time. This post: "Divide and conquer" data stream algorithms got me interested in it.

For example, suppose there are numbers: (4,3,5,1,6,2,4,3,3,8,9,1) and I query for the 3 most frequently occurring numbers (say), then I should get (3,4,1) as the answer.

I tried searching online, but couldn't find any place that gives an approach and says that that is the best. A trivial solution would be to use a heap or a balanced binary tree, but I think there is a better way and I wanted to know if it is documented somewhere.

Edit: I'm looking for an algorithm that always gives the correct answer as opposed to a appromixation algorithm (many of which pop up in search results) which rely on the distribution of data in some way or other


texts: How the Number of Clauses Change the Complexity of Worst Case k-SAT ?

texts:
Is there a conjecture such that if the conjecture holds then the following (1) and (2) hold ?

(1)The worst case time complexity of k-SAT with n variables and m clauses reaches the maximum value, if m is Cn where C is a constant.

(2)The exponential time hypothesis

This question comes from a view about input size of problems. For example, an instance of 3-SAT with n variables is a 3CNF formula and the length of the formula  could be O(n^3). The complexity of obvious algorithm for 3-SAT with n variables is 2^n. 2^n is strictly smaller than 2^{ O(n^3) }. The complexity is defined as the function of input size like the length of formula and the exponential function of input length is 2^{ O(n^3) } and is not 2^n. 2^n time seems to be a sub-exponential time if the statement (1) does not hold.


texts:
Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences of unweighted edges), but do not know $G$ itself. Can we produce any $G$ that would have given these paths as the shortest in polynomial time? The weaker version: can we decide in polynomial time if such $G$ exists?

The obvious necessary condition is the following: for every pair of paths their intersection is a path too. Is this condition sufficient?


texts: Is there any natural Karp reduction from Independent Set problem to SAT?

texts: Is there a natural Karp reduction from Independent Set to SAT ? That is, a reduction that does not rely on the Turing machine (as the case in proof of Cook's theorem) but the combinatorial structure.


texts: Is there a concept of something like co-applicative functors sitting between comonads and functors?

texts:
Any monad is also an applicative functor and any applicative functor is a functor. Also, any comonad is a functor. Is there a similar concept between comonads and functors, something like co-applicative functor, and what are its properties?

\begin{array}{c}
\end{array}
\begin{array}{cc}
\mbox{Functors} & & \mbox{Functors} \\
\uparrow & & \uparrow \\
\mbox{Applicative functors} & & ??? \\
\uparrow & & \uparrow \\
\mbox{Monads} & & \mbox{Comonads} \\
\end{array}

Update: I'd be also interested in possible uses of such a concept.


texts: Type theory for memory safe data structures

texts:
Data structures such as a doubly linked list and a B+ tree have blocks of memory that have multiple pointers to it. This creates the risk that a bug will allow memory to be accessed after being freed.

I have heard of ideas based around linear typing for guaranteeing memory safety in the case of a single pointer to the memory. I believe the Rust language is based around this.

But suppose, for example, I wanted a memory safe implementation of a B+ tree in a systems language that has no garbage collection or reference counting. What exists in type theory that could be used to guarantee that the B+ tree implementation is memory safe?


texts:
I'm a linguist (and not a computer scientist!) investigating a new sort of linguistic formalism for mapping phonological strings into other strings - and I'm wondering if it's a regular relation that could be done on a finite-state transducer.

I give the machine a description of a string to look for, and when it finds a string that fits its description, it maps it to another string that's a function of the input string.

Examples of things this machine can do:

"if the string contains a /b/, map that /b/ to /p/"
"if the string contains a /t/, map that /t/ to /ts/"
"if the string contains a sequence /dw/, map that /dw/ to /p/"
"if the string contains a /z/, delete the /z/"
"if the string contains a /d/ with a /g/ anywhere later than it, map that /d/ to /t/"
"if the string contains a /t/ or it contains a /k/, add a /d/ to the end"
"if the string contains a sequence /ti/ and it contains a sequence /in/ (which may or may not be overlapping), add a /d/ to the end"
"if the string does not contain a /k/, add a /d/ to the end"
"if the string contains a /w/ and a /y/ with anything intervening, swap around the /w/ and the /y/"

In other words, it applies to an input string if that string has some (not necessarily contiguous) substring - and then applies some simple function, like mapping the relevant substring to something else, or adding something to the end of the string. And it can have words like and, or, and not in the descriptions of the strings it applies to.

Is there anything in here (if it's possible to tell from a prose description) that a finite-state transducer wouldn't be able to do? I have an intuition that there isn't, but I'm not able to prove that.


texts: Calculating the distance to the kth nearest neighbor for all points in the set

texts:
For a machine learning application, my group needs to calculate the Euclidean distance to the $k$th nearest neighbor in a set $X$ for each $x \in (X \cup Y) \subset \mathbb R^d$ (for $d$ between 5 and about 100, and $|X| \approx |Y|$ a few hundred up to a few million). We're currently using either the brute-force $O(d \lvert X \rvert \lvert X \cup Y \rvert)$ approach or the obvious one with a kd-tree on $X$, which when $d$ is high and $|X|$ is relatively low doesn't ever win. (Everything is in-memory.)

It seems like there must be a better way than brute-force, though -- at least one that takes advantage of the triangle inequality, or maybe with locality-sensitive hashes. A reasonably tight approximation is also potentially okay.

The research I've been able to find seems to focus on the problem of finding the single nearest neighbor (or one that is approximately the nearest). Does the problem I'm looking for go by some other name, or is there a connection to a related problem that I haven't thought of?


texts: How many edges are cut in a balanced partition of a graph?

texts: Consider a graph on n nodes and e edges that is partitioned into k "balanced" subgraphs in the sense that each block has an equal number of nodes and the number of cut edges is minimized. Is there a formula for the number of cut edges in this situation?


texts: Simplifying the disjoint union of wildcard strings

texts:
Setting: patterns with "don't care" symbols, binary alphabet.

For example, pattern $x = 001?$ represents the set $L(x) = \{0010, 0011\}$.

We are given a set $P$ of disjoint patterns: $L(x) \cap L(y) = \emptyset$ for all $x, y \in P$, $x \ne y$.

The task is to find the smallest possible set of disjoint patterns $Q$ such that $P$ and $Q$ represent the same set of strings: $$\bigcup_{x \in P} L(x) = \bigcup_{y \in Q} L(y).$$

Examples:

$P = \{01?, 1?0, ?01, 000, 111\}$, $Q = \{???\}$.
$P = \{01?, 1?0, ?01, 000\}$, $Q = \{0??, 10?, 110\}$.

Question: Does anyone recognise this problem? For example, is this a well-known NP-hard problem?

I am mainly interested in positive results — efficient algorithms for exact solutions or good approximations. Algorithms that are exponential in anything (the number of patterns, the length of a pattern, the number of wildcards in a pattern) are too slow for my purposes.

Notes: The problem is fairly easy to solve if we are lucky and there is a solution with $|Q| = 1$. Also it is fairly easy to verify that a given solution is feasible.

Motivation: We encountered a closely related problem recently when we were doing this work. Very briefly, our goal is to simplify a machine-generated case analysis by merging similar cases.


texts:
I have a finite undirected graph with a probability $p_e$ given for each edge $e$. This gives a random graph by removing each edge e with probability $1-p_e$ independently of the others.

I'm interested in computing probabilities like the probability that some given subset of the graph is connected (in particular pairs of vertices). This seems hard to do exactly. Has it been proven to be hard? Are there approximation algorithms?

Also, I am interested in sampling from the distribution conditioned on certain subsets being connected (again, just conditioning on a pair of vertices being connected seems interesting enough). How to do this?


texts:
Determinant of integer matrix modulo $2$ is complete for the class $\oplus L$. Is determinant modulo $2^k$ computable in $\oplus L$ at any fixed $k$?
How about if $k=o(n)$ where matrix is $n\times n$?


texts: QUBO formulation of a discrete-variable optimization problem

texts:
I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic non-linear real-valued function $f:S \to \mathbb{R}$ which takes values on a certain set $S \subseteq \mathbb{Z}^9$.  The goal is to find $\theta^* \in \mathbb{Z}^9$ corresponding to the minimum of the function.  The total number of possible configuration of the system is high but finite ($\sim10^7$).

Recent quantum annealing techniques allow to take advantage of quantum effects to solve computationally hard optimization problems. Quantum annealers are designed to minimize Quadratic Unconstrained Binary Optimization (QUBO) problems, i.e. the cost function is of the form

$$F(x)=\sum_{i<j}J_{ij}x_ix_j+\sum_{i}h_{i}x_i$$

with $x\in\{0,1\}^n$ and $J_{ij},h_{i}\in \mathbb{R}$.

How do I remap my problem into a QUBO problem? I can associate each configuration of my discrete problem into a binary number, but what does the matrix $J$ represent in this context? What about my non-analytic function $f$ which has to be minimized? Has anyone attempted this in a similar way and how?

Here https://www.hindawi.com/journals/complexity/2017/8404231/ I found the best formalization of the issue.


texts: Finding shortest calculation of the sum of a subset of a group, given sums for other previously summed subsets

texts:
Say $S=\{g\in G\}$ is a set of elements in an abelian group $G$ whose group operation $(+)$ is expensive to compute. Given a subset $T\subset S$, we want to compute the sum of $T$'s elements, $\sigma_T=\sum_{g\in T}g$. Say we have a collection of other subsets of $S$, $U=\{T_i\}$, for which the sums $\sigma_{T_i}=\sum_{g\in T_i}g$ are already known. We can assume $U$ contains the singleton subsets of $S$, since $\sigma_{\{g\}}=g$. Hence   $\sigma_T$ can always be expressed as a linear combination of the $\sigma_{T_i}$'s, namely $\sum_{g\in T}\sigma_{\{g\}}=\sum_{g\in T}g=\sigma_T$. I'd like to find the linear combination$\sum_i a_i\sigma_{T_i}=\sigma_T$, which minimizes $\sum_i|a_i|$, i.e., which computes the sum with the least number of group operations.

It seems likely that the problem of actually finding this optimum is NP-complete, so I'm looking for good heuristics, ideally with some reasonable bound on the distance from optimality. Also, any references to papers discussing this problem would be great. Finally, storing the $\sigma_{T_i}$'s is somewhat expensive for me, too, so I'm also interested in heuristics for deciding which $\sigma_{T_i}$'s should be stored, given a sequence $\{T_1, T_2, \ldots\}$, and fixed costs for storage, retrieval and group operations.


texts: Best sources for communication complexity

texts: What are some of the best sources (books and papers) to motivate and learn communication complexity on its own and in connection with its relation to computational complexity theory?


texts: Statistical distance between uniform and biased coin

texts: Let $U$ be the uniform distribution over $n$ bits, and let $D$ be the distribution over $n$ bits where the bits are independent and each bit is $1$ with probability $1/2-\epsilon$.  Is it true that the statistical distance between $D$ and $U$ is $\Omega(\epsilon \sqrt{n})$, when $n \le 1/\epsilon^2$?


texts: Planar separator theorem and tree decomposition

texts:
The Wikipedia article about the Planar Separator Theorem states that it is possible to use a hierarchy of separators to construct a tree decomposition for a planar graph and moreover provides an $\mathcal{O}(\sqrt{n})$ upper bound for the tree width of an $n$ vertex planar graph.

I have difficulties in understanding the hierarchy and moreover in checking that the resulting binary tree is a tree decomposition.

I would really appreciate if you could help me or point to a reference that elaborates on it.


texts: Who introduced the notion of Non-Deterministic Polynomial time?

texts:
In his 1972 paper, Richard Karp provides a definition of NP (section 3, definition 4, p.91). It this the original definition of the class NP or is there a previous one?
Edit
Edmonds mentions the idea of backtracking in his 1965 paper and says it was already suggested by Berge in his 1957 paper. However, they do not formalize the notion of polynomial verifiers, although they explicitly use it.


texts:
How to "proof"  that type theory is correct? Or at least explain that it's meaningful in some sense. In what extent is this a mathematical question and in what is a philosophical one?

When type theories are introduced for example in Luo's book, the following properties are proved:

Subject reduction
Reduction termination
Church-Rosser property

As far as I understand, what these properties describe is that we have a decidable type checking, and that the language of type theory is meaningful in some sense, but nothing more than this.

I asked a question on violation of strict positivity for inductive types (Example of where violation of strict positivity condition in inductive types leads to inconsistency) and in the answer I was told that non strictly positive types might lead to non existence of set theoretic model. Why we need type theoretic model here? And what it gives to us?


texts: Is it decidable whether the langauge accepted by a reversal-bounded counter machine is deterministic?

texts:
I'm wondering if anyone can point me to either an algorithm or an undecidability proof for the following question:

Given a non-deterministic reversal-bounded multicounter machine $M$,
is there some deterministic reversal-bounded multicounter machine $M'$
such that $L(M) = L(M')$?

For anyone interested, reversal-bounded counter machines are described at length
in Oscar Ibarra's Paper about them.


texts: What kind of answer does TCS want to the question "Why do neural networks work so well?"

texts:
My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to machine learning, stumbled across statements such as "No one understands why neural networks work well," which I found interesting.

My question, essentially, is what kinds of answers do researchers want?  Here's what I've found in my brief search on the topic:

The algorithms implementing simple neural networks are pretty
straightforward.
The process of SGD is well-understood mathematically, as is the statistical theory.
The universal approximation theorem is powerful and proven.
There's a nice recent paper https://arxiv.org/abs/1608.08225 which essentially gives the answer that universal approximation is much
more than we actually need in practice because we can make strong
simplifying assumptions about the functions we are trying to model
with the neural network.

In the aforementioned paper, they state (paraphrasing) "GOFAI algorithms are fully understood analytically, but many ANN algorithms are only heuristically understood." Convergence theorems for the implemented algorithms are an example of analytic understanding that it seems we DO have about neural networks, so a statement at this level of generality doesn't tell me much about what's known vs. unknown or what would be considered "an answer."

The authors do suggest in the conclusion that questions such as effective bounds on the size of the neural network needed to approximate a given polynomial are open and interesting. What are other examples of mathematically specific analytical questions that would need to be answered to say that we "understand" neural networks? Are there questions that may be answered in more pure mathematical language?

(I am specifically thinking of methods in representation theory due to the use of physics in this paper --- and, selfishly, because it is my field of study. However, I can also imagine areas such as combinatorics/graph theory, algebraic geometry, and topology providing viable tools.)


texts: Is the traveling salesman problem still NP-hard if all edges need to be covered as well?

texts:
If we formulate the travelling salesman problem with an added edge-covering constraint as follows, is it still NP-hard?

Given a graph G with non-negative edge weights, is there a circular walk in G that covers all edges and has weight at most t?


texts: Does "Productive function" mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes?

texts:
M.E. O'Neill in the Epilogue of "The Genuine Sieve of Eratosthenes" (preprint http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf DOI 10.1017/S0956796808007004) quotes Richard Bird that "union is defined in the way it is in order to be a productive function."

Is that the technical term referring to productive sets and creative sets, or is it just a manner of speaking?

The function union is defined there in the following Haskell code:

primes = 2:([3..] `minus` composites)
  where
    composites = union [multiples p | p <- primes]

multiples n = map (n*) [n..]

(x:xs) `minus` (y:ys) | x< y = x:(xs `minus` (y:ys))
                      | x==y = xs `minus` ys
                      | x> y = (x:xs) `minus` ys

union = foldr merge []
  where
    merge (x:xs) ys = x:merge' xs ys

    merge' (x:xs) (y:ys) | x< y = x:merge' xs (y:ys)
                         | x==y = x:merge' xs ys
                         | x> y = y:merge' (x:xs) ys

I haven't learned about productive sets. If it's helpful for understanding this point, I will.


texts:
Suppose we have two points, A and B, each point has its own clock.

We are able to send messages between A and B, the message takes some random delay to be delivered:
$$min < delay < max,$$for each message the actual delay is unknown.

In this setup:

Can we sync clock at this points perfectly?
Can we prove that it is impossible to sync perfectly?
Can we prove that it is impossible to sync this clock with a precision, which is better than some $f(min, max)$? (In other words, that after any sync process, this clock will still have difference at least $f(...)$)

Precision is the difference between this clock after actually syncing.


texts:
Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables.
The goal is to compute the minimum number of XOR operations you need to perform to compute all these y_1...y_m functions.

Note that the result of an XOR operation,
say x_1 XOR x_2 might be used in computation of multiple y_j's but is counted as one. Also, note that it might be useful to compute XOR of a much larger collection of x_i's (larger than any y_i function, e.g. computing XOR of all x_i's) in order to compute y_i's more efficiently,

Equivalently, suppose we have a binary matrix A, and a vector X and the goal is to compute vector Y such that A.X=Y where all operations done in GF(2) using minimum number of operations.

Even when each row of A has exactly k one's (say k=3) is interesting.
Does anybody know about the complexity (hardness of approximation) for this question?

Mohammad Salavatiopur


texts: Counting subsets of bipartite graph part which admit an induced perfect matching

texts:
Given a bipartite graph $G=(U \sqcup V, E)$, count $U^\prime \subseteq U$ for which $\exists V^\prime \subseteq V$ such that the induced subgraph $G[U^\prime \sqcup V^\prime]$ contains a perfect matching.

I believe that this problem is at least #P-hard, but I can't find anything that states such.
I've found a similar question on cstheory which states that counting subsets of vertices on a general graph for which there is an induced perfect matching is #P-Complete. The difference between our questions is I consider $U^\prime$ unique whereas they consider $U^\prime \sqcup V^\prime$ unique.
An alternative expression of my question could be: count $U^\prime \subseteq U$ for which the induced subgraph $G[U^\prime \sqcup V]$ contains a (maximum, potentially imperfect) matching $M$ where $\lvert M \rvert = \lvert U^\prime \rvert$, i.e. every $u^\prime \in U^\prime$ is adjacent to some $m \in M$.


texts: Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$

texts: Which natural (well studied) classes of graphs have treewidth that scales as $\Theta(n^\alpha)$ in the number $n$ of vertices, with $1/2 < \alpha < 1$?


texts: Count $k$-hop neighborhood for every vertex

texts:
For a node $v$ of a directed unweighted graph $G$, I define the $k$-hop neighborhood of $v$ as the set of vertices that are reachable from $v$ in $k$ hops or fewer (that is following a path with  $k$ edges or fewer).  I would like to compute the cardinality of this $k$-hop neighborhood for very node $v$ in $G$.

One option is to simply raise the adjacency matrix of $G$ to the power $k$ using Boolean arithmetic and then sum the rows.  This is however rather slow and seems wasteful (consider for example the complete graph or a very sparse graph). Another approach is to naively search from each node but this is at least $O(n d^k)$ time for a $d$-regular graph, for example. This naive method is also wasteful as it doesn't take advantage of any previous computations it has done.  The sizes of the neighborhood of two adjacent nodes are surely not independent.

Is there a fast, perhaps randomized,  way of solving this problem?


texts: What is the difference between LTL and CTL?

texts: I already read examples of formulas in CTL but not in LTL and vice-versa, but I'm having trouble gaining a mental grasp on LTL formulas and really what, at the heart, is the difference.


texts: Constant-time bounds on offline 2-choice hashing?

texts:
I'm reading up on cuckoo hashing and came across Michael Mitzenmacher's blog posts on the subject. In his motivation of why cuckoo hashing seems like a reasonable strategy, he mentions a connection to 2-choice hashing:

  In the course of these results [about 2-choice hashing], the question arose as to whether one could do better if placing the elements offline. That is, if you had all n elements and their hashes in advance, could you place each element in one of their bucket choices and achieve a better load than the O(log log n) obtained by the sequential placement? The answer turns out to be yes. The best placement only has a constant maximum load. Another way to think of this is to say that if we place the elements sequentially, but retain the power to move them later, as long as each element ends up at one of its bucket choices, we could get down to constant maximum load.

I found this result really intriguing and have been trying to track down a source on it. However, I can't seem to find any papers on the subject that prove this particular result. I'm aware that cuckoo hashing itself can be thought of as an offline version of 2-choice hashing, but given that cuckoo hashing sometimes fails and requires a rehash, it doesn't seem like the traditional analysis of cuckoo hashing itself would meet the description given above (or does it?)

Does anyone have a source I could use to learn more about this?


texts: Complexity of $FP^{NP[O(n)]}$ with advice string?

texts:
$FP^{NP[O(n)]}$ is the functional complexity class with $O(n)$ queries to an $NP$ oracle.

Are there any interesting classes $\mathcal C$ such that
$$FP^{NP[O(n)]}\subseteq\mathcal C/\log$$
besides $FP^{NP[O(n)]}$ itself?
In particular, can we show that $FP^{NP[O(n)]}\subseteq FP^{NP[f(n)]}/\log$ for some $f(n) = o(n)$?


texts: What is the "question" that programming language theory is trying to answer?

texts:
I've been interested in various topics like Combinatory Logic, Lambda Calculus, Functional Programming for a while and have been studying them. However, unlike the "Theory of Computation" which strives to answer the question of "computability" i.e., things that can/cannot be computed with various constraints, I'm struggling to find the analog for "Theory of Programming"

Wikipedia describes it as:

  Programming language theory (PLT) is a branch of computer science that
  deals with the design, implementation, analysis, characterization, and
  classification of programming languages and their individual features.

This is like saying "everything" which isn't really specific.

The common progression of the topics is usually like so:

  Combinatory Logic > Lambda Calculus > Martin Lof Type Theory > Typed Lambda Calculus > (Something happens here) > Programming languages developed - that have very little connection with CL/$\lambda$

I can see the underlying "math" involved with CL/$\lambda$ and interesting proofs that come out as a result including the Church-Rosser theorem and that's neat. However, I'm struggling to understand the "end goal" of all this undertaking? What's the holy grail of PLT if you will? For now it seems to just be scratching an intellectual itch but I can't really cross the bridge from research/theory to anything practical.

Note: I do get it up until using the $\lambda$-calc for undecidability proofs. But beyond its applicability to "computability" I just don't get it and am having a hard time even understanding the need for research in PLT from this narrow POV. Any existing books, references that can throw light on the "big picture" of PLT?


texts: Provable statements about genetic algorithms

texts:
Genetic algorithms don't get much traction in the world of theory, but they are a reasonably well-used metaheuristic method (by metaheuristic I mean a technique that applies generically across many problems, like annealing, gradient descent, and the like). In fact, a GA-like technique is quite effective for Euclidean TSP in practice.

Some metaheuristics are reasonably well studied theoretically: there's work on local search, and annealing. We have a pretty good sense of how alternating optimization (like k-means) works. But as far as I know, there's nothing really useful known about genetic algorithms.

Is there any solid algorithmic/complexity theory about the behavior of genetic algorithms, in any way, shape or form ?  While I've heard of things like schema theory, I'd exclude it from discussion based on my current understanding of the area for not being particularly algorithmic (but I might be mistaken here).


texts: Why backward symbolic execution is so unpopular?

texts:
Looking at the DARPA’s Cyber Grand Challenge, it seems that (forward) Symbolic Execution (SE) is the tool of choice for all the top teams. For example:

Mayhem, the winner of the $2 millions prize
Driller, ranked 2nd or 3rd.

Maybe this is a stupid question, but if the purpose is to find the input that reach a location, e.g. the one that causes SIGSEGV, then intuitively going backward from that location is much easier that searching from forward. However, obviously those well-known scientists did not think so, and I wonder why.

Moreover, papers about forward SE appear in all software engineering conferences, and there is a survey every 2 or 3 years. But I don't remember the last time I read a paper about backward SE (that's why there is this possibly stupid question).

Are there any challenges that make backward SE either:

significantly more difficult to implement than forward SE, or
much less scalable than forward SE, or
...


texts:
According to ncatlab's page on category theory and haskell,
"we can identify a subset of Haskell called Hask that is often used to identify concepts used in basic category theory. One considers Haskell types as objects of a category whose morphisms are extensionally identified Haskell functions."

So types are objects, and functions are morphisms.  How, then, does a value, such as the list [1,2,3] or the boolean "true", fit into a category-theoretic definition of Haskell?  (I realize that lists, as monads, are presumably different in any category theoretical representation than booleans, which could be described as a coproduct, but I don't understand how the actual values in either case are related to the definition of Hask).


texts: Complexity Lower Bounds for 3D Sparse Gaussian Elimination

texts:
I'm interested in lower bounds on the complexity in the real-RAM model of solving systems of linear equations which have the sparsity pattern of a three-dimensional cubic mesh. Specifically, consider a matrix $A$ whose rows and columns are indexed by points in $\{1,\ldots,\sqrt[3]{N}\}^3$ with a nonzero entry in row $(i_1,i_2,i_3)$ and column $(j_1,j_2,j_3)$ only if $|i_1 - j_1| + |i_2 - j_2| + |i_3 - j_3| \le 1$. The problem is:

Given the $\mathcal{O}(N)$ nonzero entries comprising $A$ and $m$ right-hand sides $b_1,\ldots,b_m$, compute $x_1 = A^{-1}b_1,\ldots,x_n = A^{-1}b_n$.

The prototypical example of this is the discrete Poisson equation in 3D or more generally a (generalized) Laplacian matrix on the three-dimensional mesh graph. There are results which show that if one additionally assumes $A$ is diagonally dominant, then approximate solutions $\tilde{x}_1,\ldots,\tilde{x}_n$ can be computed in $\tilde{\mathcal{O}}(mN)$ time. I'm interested in the case where there is no diagonal dominance assumption, and am in particular curious about the case where $x_1,\ldots,x_n$ are required to be computed exactly.
My understanding is the lower bound of Lipton, Rose, and Tarjan extends to the 3D case and thus solving such systems by Gaussian elimination requires $\mathcal{O}(N^2 + mN^{4/3})$ arithmetic operations, where $\mathcal{O}(N^2)$ are required to compute the factorization and $\mathcal{O}(N^{4/3})$ operations are required per right-hand side to do back- and forward-substitution. I believe this can be improved to $\mathcal{O}(N^{2\omega/3} + mN^{4/3})$ by using fast matrix multiplication algorithms, where $\omega \ge 2$ is the exponent of matrix multiplication. It seems that, in some sense, Gaussian elimination with a good elimination ordering is the "natural" algorithm for this problem. However, I am not aware of any truly general lower bounds for this problem. I know algebraic complexity bounds are hard to prove, but are such results known?


texts: Network Flow with Non-contiguous Capacities

texts:
I have a problem that I can model as a minimum cost network flow. The only problem is that I need to be able to set the flow through some arcs to be either 0 or at least 5. That is, the arc cannot carry an integer flow of 1 through 4, but is otherwise okay. Can anyone point me in the direction of any pre-existing work on a problem like this?

Thank you!


texts:
How can I check if an LTL (Linear Temporal Logic) property is safety or liveness? Is it right to say that a property is safety OR liveness (or neither)?

How can I evaluate this:

G(x -> (a U y) )


texts: Negative results on identical particles approach to Graph Isomorphism (GI) problem

texts:
There has been some efforts to attack graph isomorphism problem using quantum random walk of hard-core bosons (symmetric but no double occupancy). Symmetric power of adjacency matrix, which seemed promising, was proved to be incomplete for general graphs in this paper by Amir Rahnamai Barghi and Ilya Ponomarenko. Other similar approach was also refuted in this paper
by Jamie Smith. In both of these papers, they use the idea of coherent configuration (schemes) and alternative but equivalent formulation of cellular algebra (matrix subalgebra indexed by a finite set -here vertex set- closed under point-wise multiplication, complex conjugate transpose, and containing Identity matrix I and all-one matrix J) respectively to provide necessary counter arguments.

I find it very difficult to follow those arguments and even if I follow individual arguments vaguely I do not understand the core idea. I would like to know if the essence of the arguments can be explained in generic terms -may be at the cost of slight rigour- without using  the language of scheme theory or cellular algebra.


texts: Inspirational talk for final year high school pupils

texts:
I am often asked by my department to give talks to final year high school pupils about the more mathematical elements of computer science. I do my best to pick topics from TCS which might inspire their interest (which mostly involves something to do with the Halting problem) but would love hear other people's ideas/successes/failures.

The remit is that these are pupils who are considering applying for a CS undergraduate degree at a decent university but may be more attracted by maths or another one of the sciences.  I find that the usual topics of shortest path algorithms or faster sorting methods don't really work any more to pique their interest.


texts: Does kd-tree search look at more leaves in L1 than in Lmax ?

texts:
Dear theorists and experimenters,

I find that kd-tree search looks at many more leaves in $L_1$ than in
$L_{max}$ ($L_\infty$).
Does anyone else see this ? If so,

why ?
(An $L_1$ simplex of volume 1 is much wider than a unit cube —
the back of my envelope says ~ dim/$e$ —
but that doesn't get me very far.)
is there some way of using fast $L_{max}$ search to speed up slow $L_1$ ?

Some numbers for dim=16, on data uniform$^3$ to model some clumping:

L1: 0.72 sec  p=1 dim=16 N=10000 nask=100 nnear=2 eps=0 leafsize=10
    100 queries looked at av 64 % of the 10000 points, 80 % of 1909 boxes

L2: 0.36 sec  p=2 dim=16 N=10000 nask=100 nnear=2 eps=0 leafsize=10
    100 queries looked at av 25 % of the 10000 points, 37 % of 1909 boxes

Lmax: 0.06 sec  p=inf dim=16 N=10000 nask=100 nnear=2 eps=0 leafsize=10
    100 queries looked at av 6.2 % of the 10000 points, 10 % of 1909 boxes

A plot of 5 queries:

One sees here that the distances to box edges (blue) increase slowly in $L_1$
—
for this limited data.

(Can someone please add tag "kd-tree", thanks.)


texts: How to find the first $k$ points of high enough level using a priority search tree?

texts:
In reading Chan's paper,
Closest Point Problems Simplified on a RAM,
the following came up as a sub-problem:

Given a set $P$ of points in the plane, and a query point $q$, find the first $k$ points (ordered by $x$-coordinate) which dominate $q$.

Chan asserts that this query can be answered in $O(\log n + k)$ time using a priority search tree, but doesn't give details, and the details are not clear to me. The traditional query for a priority search tree is a 3-sided range query, but this query is different because we are given a 2-sided range (an upper-right quadrant) and a maximum number of points to report. We should report the $k$ "leftmost" points in the 2-sided range.


texts: Decidability of rank-k polymorphism vs. System F

texts:
There's a paper by Kfoury from 1992, "Type Reconstruction in Finite Rank Fragments of
the Second-Order $\lambda$-Calculus", that proves that type inference for Curry-style rank-$k$ polymorphic lambda calculus is undecidable if $k \ge 3$. My thought was that since there must be terms that can be typed in rank-3 but not rank-2, and since System F is rank-$n$ (i.e. the union of all finite rank-$k$), surely this implies that Curry-style System F type inference is undecidable as well. However, its undecidability isn't proven until 1996 by Wells in "Typability and Type Checking in the Second-Order $\lambda$-Calculus Are Equivalent and Undecidable", which explicitly mentions Kfoury's paper (along with others) and states that decidability of both type inference and type checking have not yet been proven until then.

So given that rank-3 polymorphic lambda calculus is a fragment of System F, why doesn't the former's undecidability imply the undecidability of the latter?


texts: Question about a unary language construction

texts:
For any language $L$, let us define another language $Tally(L)$, as follows:
$$Tally(L)=\{1^n\;|\;\exists x \;\mbox{with}\; x\in L \;\mbox{and}\; |x|=n\}$$
That is, $Tally(L)$ encodes whether there is an $n$-bit string in $L$ or not. (Remark: there may be a standard name/notation for this construction, but I am not aware of it.)

$Tally(L)$ seems interesting for the following reasons:

If $L\in \mathsf{NP}$, then $Tally(L)\in \mathsf{NP}$. The reason is that one can witness $1^n\in Tally(L)$ by an $x$ with $|x|=n$ and $x\in L$, along with a polynomially sized witness $y$ for $x\in L$. Then $(x,y)$ can serve as a polynomially sized witness for $1^n\in Tally(L)$.
While $L\in \mathsf{NP}$ implies $Tally(L)\in \mathsf{NP}$, yet $Tally(L)$ cannot be $\mathsf{NP}$-complete, even if $L$ is $\mathsf{NP}$-complete (assuming $\mathsf{P}\neq\mathsf{NP}$). This is because $Tally(L)$ is a unary language, and it is well known that a unary (or even a sparse) language cannot be $\mathsf{NP}$-complete, if $\mathsf{P}\neq\mathsf{NP}$, due to Mahaney's Theorem (the unary version was proved earlier by Berman).
At the same time, it also seems unlikely that $Tally(L)\in \mathsf{P}$ for every $L\in \mathsf{NP}$. This would mean that for every $\mathsf{NP}$-property we could decide in polynomial time whether there is an $n$-bit string with the property. Or, similarly, for every graph property in $\mathsf{NP}$, no matter how complicated,  we could always  decide in polynomial time if there is an $n$-vertex graph with the property or not.

Question: Is anything nontrivial known about this?


texts: Are variables in RHS of Chomsky Normal Form productions distinct?

texts:
I'm wondering if it is permitted for production rules in a context-free grammar (CFG) in Chomsky Normal Form (CNF) to have multiple occurences of the same variable in the right-hand side of the productions.

e.g. is this permitted:

$A \to BB$

or must one do something like

$A \to B_1 B_2$

$B_1 \to B$

$B_2 \to B$

The only definitions of CNF I have found define production rules of the form $A \to B C$ , but none ever state that $B \neq C$


texts: Where is the proof of universality of Rule110 in Stephen Wolfram's book?

texts:
I have Stephen Wolfram's book A New Kind Of Science. And I want to find the proof of the universality of Rule 110. I couldn't find the clue in the contents page since it only shows 12 chapters and no details.

Could some one help me please? Does he show the proof in his book at all? What is the page number where he shows the proof?

I'm reading the paper by Matthew Cook for sure. It's just more pictures help me understand things better. I now know pretty well what is the tag system and the cyclic tag system, but still trying to find a way to visualize the equivalence between the tag system and the turing machine. Other resources about this are welcome, too!

Many thanks!


texts: What's the simplest to implement of all decent LTL-to-Buchi translation or other LTL verification algorithms?

texts:
I'm writing a toy modelchecker, and I'm at the point where it's time to implement LTL to Buchi automata translation.

For a variety of obvious reasons, I wish the algorithm to be simple :) e.g. I want the code to remain extremely clear and concise for as long as possible.

I've looked at the "local automata + eventuality automata" approach, described in multiple tutorials, but it seems to be neither simple to implement/understand (the correctness proof is quite large), nor does it yield small automata. So I'm not implementing it until I'm sure I won't regret it :)

So, I'd be grateful for references to papers describing simple and efficient algorithms for this translation, or perhaps simple and inefficient ones - then papers on minimization of Buchi automata would be welcome too :)

...Or perhaps there are interesting alternative approaches to LTL verification?

For reference, here's a genealogy of LTL-to-Buchi translation algorithms http://spot.lip6.fr/wiki/LtlTranslationAlgorithms . Can anyone say something about these?


texts: What graphs on $\mathbb{N}$ can be encoded as regular languages?

texts:
Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers into a formal language $V$:

$0 \mapsto x$, $1 \mapsto sx$, $2 \mapsto ssx$, $3 \mapsto sssx$, etc

So $V = \{x, sx, ssx, sssx, ... \}$ is a regular language generated by the regex $s^*x$.
Now, Suppose $G = (\mathbb{N},E \subset \mathbb{N} \times \mathbb{N})$ is a directed graph.  An edge $e = (n, m) \in E$.  I now define an encoding $\beta : E \rightarrow W$ of edges into a new language $W$ using the following encoding
$(n,m) \mapsto \alpha(n),\alpha(m)$ (i.e. concatenate the encoding of each number's encoding with a separating comma).  For example, $W((3,1)) = $"sssx,sx"

Question:  For what graphs $G$ of this type is $W$ a regular language?

Obviously if $E$ has a product structure such as $E = \{ (n, m) \ | \ n \in R_1, \ m \in R_2\}$ where each $R_i \subset \mathbb{N}$ corresponds to a regular language, then $W$ would be regular.  But what about more "natural" relations on $\mathbb{N}$?  In particular, here are two particular examples I am especially interested in:

Ex 1:  $E_1 = \{ (n, n+1) \ | \ n \in \mathbb{N} \}$.  Is $\beta(E_1)$ a regular language?

Ex 2:  $E_m' = \{ (n, n \times m) \ | \ n \in \mathbb{N} \}$ (i.e. an edge from each natural number to its product with a fixed natural number $m$).  Is $\beta(E_m')$ a regular language?

Any help is much appreciated :)


texts:
Informal Question

How hard is it to generate a set of relatively prime numbers between two given bounds?

Decision Problem

Given $a$, $b$, and $k \in \mathbb{N}$.  Does there exist a set $S \subseteq \mathbb{N}$ satisfying the following:

(a) for every $x \in S$, $a \leq x \leq b$

(b) for every $x, y \in S$, $x$ and $y$ are relatively prime

(c) $\vert S \vert = k$

Questions

(1) How hard is this decision problem?  Is it as hard as factoring or any other well studied problems in NP?  @YonatanN in the comments below explains why it is at least as hard as prime counting.

(2) In terms of $k$, how large does $b - a$ have to be to guarantee that such a set exists?

Any references would be greatly appreciated.  Thank you!


texts: Can I bound the cardinality of a set if testing for membership in it is known to be NP-complete?

texts:
I would like to have a bound on the cardinality of the set of unit disk graphs with $N$ vertices. It is known that checking whether a graph is a member of this set is NP-hard. Does this lead to any lower bound on the cardinality, assuming P $\neq$ NP?

For example, suppose there is an ordering on all graphs with $N$ vertices. Would NP-hardness then imply the cardinality exceeds $2^N$, in that otherwise you could test for membership in polynomial time by doing a binary search through the set? I think this would assume that you have somehow stored the set in memory... Is this allowed?

Defintion: A graph is a unit disk graph if each vertex can be associated with a unit disk in the plane, such that vertices are connected whenever their disks intersect.

Here is a reference on NP-hardness of membership testing for unit disk graphs:
http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf


texts: Is there notation for converting a multi-set to a set?

texts: Suppose we have a multi-set $S$. For example,  $S = \{ 1,2,2,3 \}$. Suppose we also have a set $T$, e.g., $T=\{1,2,3\}$. I would like to say, compactly, that $S$, when its duplicates are removed, is equal to $T$. Is there a simple, standard notation to do this?


texts: Best upper bound on rate for q-ary codes

texts:
Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (derived through a linear programming relaxation approach) which states that the rate $R(\delta)$ corresponding to a relative distance of $\delta$ is such that:
\begin{equation*}R(\delta) \leq H_2(\frac{1}{2}-\sqrt{\delta(1-\delta)}) \end{equation*}
where H is the (binary) entropy function.
(A slight improvement of the above exists in the binary case, but within the same framework)
In the case of q-ary codes, i.e. codes over $\mathbb F _q ^n$, the above bound is generalized to:
\begin{equation*}R(\delta) \leq H_q(\frac{1}{q}(q-1-(q-2)\delta-2\sqrt{(q-1)\delta(1-\delta)})) \end{equation*}
My question is as follows:
For larger alphabet size q, the above bound seems to weaken significantly. In fact, observing the growth of the above bound as $q \rightarrow \infty$, we see that:
\begin{equation*} R(\delta) \leq 1-\delta+\mathcal{O}(\frac{1}{\log{q}})  \end{equation*}
Thus, it seems to get worse than even the Singleton bound $R(\delta) \leq 1-\delta$.

So which is the best bound for large alphabet size $q$? Or am I wrong in the above conclusion that the MRRW bound is worse than even the Singleton bound for larger $q$?
Also, could someone direct me to references for comparisons of different upper bounds for larger $q$? I am able to find reliable comparisons only for $q=2$.


texts:
Is there anything in the literature on the following problem?:

Take a sequence of operations of Insert(element) and PopMin and apply them to an initially empty heap like this

def run(seq):
  heap = empty()
  for op in seq:
    case op:
      Insert(x) -> heap = insert(x, heap)
      PopMin -> heap = popMin(heap)
  return heap

We can naturally run the pseudo code above in O(n log n) time. Can we simulate their outcome in linear time in the number of operations, such that simulate(seq) = run(seq)? (Where heaps are compared by which elements are in them?)

Or alternatively, can we prove that such a simulation is not possible?

The only operation allowed one elements is comparison. (But I'm interested in results that make stronger assumption as well.)

I've looked through the literature and found a few special cases:

If all inserts come before all pops, this reduces to finding quantiles of unsorted lists. Median-of-median algorithm can solve this in linear time.
If the elements to be inserted are the integers 1..n (but in arbitrary order), this is known as the offline minimum problem, and solvable in linear time with an offline variant of union-find. You can even get specific order elements for popped in. (Which you can not get in my version, otherwise a O(n log n) lower bound applies.)
Solving the special case of repetitions of two inserts followed by a pop, is enough to solve the whole problem.
I have a linear time verification algorithm.
The problem is an instance of matroid optimization.

I have a candidate algorithm using soft heaps that might work in linear time, but I haven't proven it yet. I also imagine that a random sampling scheme might work and be more elementary than soft heaps, but so far the math of analysing it has proven too much for me.


texts: Unification-based elimination rule for equality

texts:
A few years back, I ran across the following left-rule for equality in sequent calculus:

$$
\frac{s \doteq t \leadsto \theta \qquad
       \theta(\Gamma) \vdash \theta(C)}
     {\Gamma, s \doteq t \vdash C}
$$

Here, $s \doteq t \leadsto \theta$ computes the most general unifier $\theta$ for $s$ and $t$, and then applies the substition to the conclusion $C$ and all the hypotheses in the context $\Gamma$.

The interesting thing about this unification is that it equates finds a substitution for universal (i.e., skolem) variables.

However, I cannot remember where I read this, and was wondering if anyone could help me find a reference to it.


texts: Need a good overview for Succinct Data Structure algorithms

texts:
(already asked on main site, but asking also here for better coverage, sorry)

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

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

Here are topics of particular interest for me:

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

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

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

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

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

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

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

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

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

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

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


texts: Smallest set that intersects some given sets

texts:
Let $S_1,S_2,\ldots,S_n$ be sets that may have elements in common.  I'm looking for a smallest set $X$ such that $\forall i,\,X\cap S_i \ne \emptyset$.

Does this problem have a name?  Or does it reduce to some known problem?

In my context $S_1,\ldots,S_n$ describe the elementary cycles of a strongly connected component, and I'm looking for a smallest set of vertices $X$ that intersects all cycles.


texts: Complexity to compute the eigenvalue signs of the adjacency matrix

texts: Let $A$ be the $n\times n$ adjacency matrix of a (non-bipartite) graph. Assume that we are given the amplitudes of its eigenvalues, i.e., $|\lambda_1|=a_1,\ldots, |\lambda_n|=a_n$, and we would like to calculate their signs. Is there a faster way of computing the signs of these eigenvalues, other than recomputing the eigenvalues themselves?