texts: Convergence theorem for Genetic Programming?

texts:
Genetic Programming (GP) is stochastic algorithm, there has been early attempts to explain its convergence with the Schmea Theorem (Holland 1975) for Genetic Algorithm adapted for GP such as (Koza 1992) (O'Reilly 1994) (Altenberg 1994) (Rosca 1997), but I was wondering if someone could point me to the generally agreed theorem that proves GP's covergence? Does it exist?

References:

[Altenberg 1994]: Altenberg, Lee. "Emergent phenomena in genetic programming." Evolutionary Programming—
Proceedings of the Third Annual Conference. World Scientific Publishing, 1994.
[Goldberg 1989]: Goldberg, David. “Genetic Algorithms in Search, Optimization and Machine Learning.” Addison-
Wesley Professional, Reading, MA 1989.
[Koza 1992]: Koza, John R. Genetic programming: on the programming of computers by means of natural selection.
[O'reilly 1994]: O'Reilly, Una-May, and Franz Oppacher. Using Building Block Functions to Investigate a Building Block Hypothesis for Genetic. No. 94-04-020. 1994.
Vol. 1. MIT press, 1992.
[Rosca 1997]: Rosca, Justinian P. "Analysis of complexity drift in genetic programming." Genetic Programming
(1997): 286-294.


texts:
Suppose we have a multigraph (later, a multihypergraph). An edge-clique is a set of edges which all pairwise intersect (have at least one common vertex). Then any edge-clique $C$ in a multigraph always falls into one of two categories:

A star: there is a vertex such that every edge of $C$ contains it
A triangle: there are three vertices such that every edge of $C$ goes between two of them

This leads to an easy $O(n^3)$-time algorithm to compute the largest edge-clique.

I am pretty sure one can show more generally, that for every $r$, in multihypergraphs with maximum edge size $r$, you can prove a certain structure theorem for hyperedge-cliques, and get a polynomial time algorithm to find the maximum clique.

Is there anything related to this result known? Also, the algorithm I have in mind is extremely high degree polynomial; it would be nice to get something with running time $n^{\mathrm{poly}(r)}$ or better.

I found this interesting since the maximum edge-clique is a lower bound on the edge-chromatic number (a.k.a chromatic index).

Edit: In the cross-post, the reference about kernels leads to a $2^{2^{\mathrm{exp}(r)}}n^{\mathrm{exp}(r)}$-time algorithm: guess the kernel and guess the restriction of the clique to the kernel.


texts: About using smoothness of the Hessian for getting to approximate criticality of a non-convex objective

texts: Is there any algorithm which shows that under the assumption of Lipschitz smoothness of the Hessian of a non-convex function one can get to its critical point faster?


texts: What's the relation and difference between Calculus of Inductive Constructions and Intuitionistic Type Theory?

texts: As stated in the title, I wonder any relation and difference between CIC and ITT. Could someone explain or point to me some literature that compares these two systems? Thanks.


texts: Is a turing machine with random number generator more powerful?

texts:
Let's extend the Turing machine so that it can read from a stream of random number generators (in addition to an infinite tape to read and write). Certainly the TM with randomness can do whatever a classical TM do, but what about the converse?

One can argue that the classical TM will always generate the same result given the same input,  while the TM with randomness can behave randomly, it can do more. But, then random-valued functions are not really what we call computable. I am aware of randomized algorithms and BPP and what not, but is there an extension of computability that deals with these kind of questions?


texts: Distance between Sum Sets and Another Point

texts:
Let $a_1,\cdots,a_n$ and $\theta$ be positive reals, define $A^{k}$ to be:

$A^0=\emptyset;\text{ } A^k=A^{k-1}\cup \{\sum_{i\in S}a_i\mid S\subseteq [n], |S|=k\},$

namely the sum set without repetition.

And the distance between two point sets are defined as $d(A,B)=\min_{x\in A; y\in B} \{|x-y|\}$, explore the property of sequence $\{d(A^n,\{\theta\})\}_{n=1}^{\infty}$, or given $\delta << \theta$, estimate the minimal $k$ such that $d(A^k, [\theta-\delta, \theta+\delta])=0$.

This math problem has concrete connection with communication complexity of linear threshold function, where every bit of input is obtained via AND of corresponding bits from two parties. If the decreasing of sequence $\{d(A^n,\{\theta\})\}_{n=1}^{\infty}$ is rapid, then if furthermore linear threshold function has high communication complexity, then we can obtain smooth property about its weights: they would be distributed "almost log-uniformly" on the certain interval of axis, where by "log-unifrom" we mean, after taking logarithm of the coefficients of the weights, the "log-weight" appears to be uniformly distributed in certain interval.

I wonder if there is some previous research on this? Any previous results or ideas on it would help. Thanks a lot.


texts:
Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is not necessarily Theoretical Computer Science but I think similar things come up sometimes, for instance in randomness extraction.
Define:
$d(x,y)=$ the Hamming distance between binary strings $x$ and $y$ of length $n$, $=$ the cardinality of $\{k: x(k)\ne y(k)\}$.
For a set of strings $A$,
$d(x,A)=\min \{ d(x,y): y\in A\}$.
The $r$-fold boundary of $A\subseteq \{0,1\}^n$ is
$$\{x\in\{0,1\}^n: 0 < d(x,A)\le r\}.$$
Balls centered at $0$ are given by
$$ B(p)=\{x: d(x,0)\le p\}, $$
where $0$ is the string of $n$ many zeroes.
A Hamming-sphere is a set $H$ with $B(p)\subseteq H\subseteq B(p+1)$. (So it's more like a ball than a sphere, but this is the standard terminology...)
Now, Harper in 1966 showed that for each $k$, $n$, $r$, one can find a Hamming-sphere that has minimal $r$-fold boundary among sets of cardinality $k$ in $\\{0,1\\}^n$. So a ball is a set having minimal boundary -- just like in Euclidean space.
The cardinality of $B(p)$ is ${n\choose 0}+\cdots {n\choose p}$.
The $r$-fold boundary of $B(p)$ is just the set $B(p+r)\setminus B(p)$, which then has cardinality ${n\choose p+1}+\cdots+{n\choose p+r}$.
So far, so good. But now suppose we replace $d$ by a different metric $D$: first let $d_j(x,y)$ be the Hamming distance between the prefixes of $x$ and $y$ of length $j$, and then
$$ D(x,y)=\max_{j\le n}\ \frac{d_j(x,y)}{f(j) }$$
where $0\le f(j)\le j$. (For example we could have $f(j)=\sqrt{j}$, or $f(j)=j/\log j$.)
This is supposed to make $D(x,y)$ small if the differences of $x$ and $y$ do not clump together at small values of $j$.
Questions

Is the minimum $r$-fold boundary (under $D$) realized by a $D$-ball?
Is there a better definition of $D$?
Under the metric $D$, what's the minimum size of the $r$-fold boundary of a subset of $\\{0,1\\}^n$ having cardinality $k$? (A reasonable lower bound would be nice.)

(Cross-posted on MathOverflow).


texts: Parametrized complexity of sparse optimization

texts:
Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so if anyone has one handy, please say so in the comments!] The $\ell_0$ "norm" is the number of non-zero elements in the vector $x$. A common way to solve such problems is via a convex relaxation: relax $||x||_0\le k$ to $||x||_1\le k$ and solve the resulting linear program. With luck, one can quantify how close the relaxed solution is to the optimal.
My question is: What if we try a more gradual relaxation, via the $\ell_p$ norm for $0<p<1$? These result in non-convex programs, but the non-convexity degree can be tweaked. Surely the $p=0.999$ case, for reasonably set other parameters, cannot be much harder than the $p=1$ case?.. Has anybody tried this approach? The idea is to seek a better efficiency/optimality tradeoff via values of $p$ other than $1$.


texts: How to prove that a formula can not be expressed in LTL, but can be in Buchi automata?

texts:
I am looking for a general technique which can help me to prove not just that Buchi automata is more expressive model than LTL, but that the specific formula can/can't be expressed in LTL.

For example, "$p$ occurs at least on even positions" can be described by the following Buchi automata: $({q_0, q_1}, \Sigma, \delta, q_0, \{q_0\})$ where $\delta(q_1, *) = q_0$ and $\delta(q_0, p) = q_1$.

I've read that that automata can't be expressed in LTL, but I don't understand how to formally prove it.

Thanks.


texts: Conditional entropy: $H(X | Y)$ large implies $H(X | Y, X \neq Y)$ large?

texts:
Suppose that $X$ and $Y$ are two random variables that are defined on the same support. Furthermore, suppose that $H(X | Y) = \log n$ for some $n$. I am now interested in how much the term $H(X | Y, X \neq Y)$ may differ from $H(X | Y)$.

Suppose that $X|Y=y$ is uniformly distributed (for every y). Intuitively, as $H(X | Y) = \log n$, for a typical element $y$ in the support of $X$ and $Y$, we also have $H(X | Y=y) = \log n$. Thinking about a uniform distribution, X takes on at least n different values, and, therefore, we should expect $H(X | Y, X \neq Y) \ge \log(n-1)$ as the conditioning on $X \neq Y$ eliminates only a single potential element.

Can such a result be obtained in full generality?

Thanks very much for your answers. I am new to stackexchange so I don't know yet where and how to respond to suggested answers.

The fact that you can bound $H(X|Y) - H(X|Y, X \neq Y) \le \log(\frac{n}{n-1})$ is very interesting, as you can compute:
$\log(\frac{n}{n-1}) = \log( \frac{1}{1-\frac{1}{n}} ) = - \log(1-\frac{1}{n}) = -\Theta(\log(e^{-\frac{1}{n}})) = \Theta(\frac{1}{n})$. This result matches the intuition very well as if the entropy $H(X|Y) = \log(n)$ then knowing that $H(X|Y, X \neq Y)$ essentially eliminates only one possible choice for $X$. This is somehow quantified by the $\Theta(\frac{1}{n})$.


texts: Given an ideal $I$ over $\mathbb{C}$ and P, a polynomial, is it decidable whether $P\in I$?


texts: When can an inner existential quantifier be eliminated in favour of a function relating terms?

texts:
I have a question which somehow relates to the great answer by Bauer in the question Techniques for Reversing the Order of Quantiﬁers, where he discusses how the possibility of quantifier reversing depends on properties like companctness of the domain.

Let the quantifiers for $x,y$ range over the appropriate domain. The expressions I'm interested in are of the form

$$\forall x\ \exists y\ \phi(x,y),$$

as in $\ \forall x\ \exists y\  \left( f(x,y)=g(x,y) \right)$, e.g. $\ \forall x\ \exists y\ \left( \text e^{-x\ y}=x \right)$.

What are conditions so that the inner bounded variable can by elimninated by transforming the statement in the following sense:

$$\forall x\ \forall i \ \phi(x,\hat y(x,i)),$$

where $\phi$ is unchanges, but I scanned for all solutions $y(x)$ and indexed them by $i$. In this way, I've essentially solved the problem (the difficult part being to find $\hat y$) and obtained the true formula

$$\phi(x,\hat y(x,i))$$

where above the free variables are implicitly taken to be universally quantified.

The form $\forall x\ \forall i \ \phi(x,\hat y(x,i))$ looks similar to the one in the link to the other question, except for me having introduced the disjuctions for different cases by another universal quantifier in $\forall i $. The point is that I didn't just reverse the order of quantifiers $\forall, \exists$, I literally solved the $\exists$-question. For the numberical problem $\ \forall x\ \exists y\ \left( \text e^{-x\ y}=x \right)$ this works, as there is the a function reklating $x$ and $y$ (the soltion being expressible in terms of the W-function, not that this matters here). I can also view $\hat y$ as implicitly definded by the initial expression.

When can I expect this not to work? And is this just strictly a stronger requirement than being able to transform the expression to, roughly, "$\exists y\ \forall x \ \phi(x,y)$"?


texts: Precise definition of syntatic categories / syntatic domains in abstract syntax

texts: I have read the introductory parts of a couple of books on programming language semantics (Gordon, Winskel, Nielson & Nielson, Allison, Stump, Schmidt), and while I do understand what they mean by syntactic categories, or syntactic domains, I didn't find a rigorous and straightforward definition of those. Is there a standard definition, maybe in earlier works?


texts: Question on subtyping of handlers in "An Effect System for Algebraic Effects and Handlers"

texts:
I had a question on subtyping in the paper "An Effect System for Algebraic Effects and Handlers". I was wondering why there isn't a subtyping rule for adding effects on both sides of a handler type, something like this:

$$
\frac{
}{
T!A \;\Rightarrow\; R!B \;\leqslant\; T!(A \cup C) \;\Rightarrow \;R!(B \cup C)
}
$$

This would be useful when apply a variable with a handler type to a computation with more effects than the handler type has in its left side.

You can add effects to both sides of a handler type using the typing rule for handlers, but that won't work for variables. For example when the handler is an argument to a function.


texts:
I have a domain $X$ and a set system $R$ on $X$, such that the sets in $R$ are one included in the other, that is, for any $A,B\in R$, either $A\subseteq B$ or $B\subseteq A$. The sets are not all equal: there is at least a pair of sets $A,B\in R$ such that $A\subsetneq B$ The VC-dimension for this set is therefore 1.

I seem to recall that the usual random sampling theorem to obtain an $(\varepsilon,\delta)$ approximation of the sizes of all the sets in $R$ can be used only if the range space has VC-dimension at least 2, but now I cannot find this explicitly stated anywhere. Could anyone please tell me whether I am just remembering it wrong and the theorem can be used for range spaces of any VC-dimension?

If not, are there other techniques I can use or do I have to resort to Chernoff+union bounds?


texts: Is the class of primitive recursion functionals equivalent to the class of functions which Foetus proves to terminate?

texts:
Foetus, if you have not heard of it, can be read up on here. It uses a system of 'call matrices' and 'call graphs' to find all 'recursion behaviors' of recursive calls in a function. To show that a function terminates it shows that all the recursion behaviors of recursive calls made to a function obey a certain 'lexicographic ordering'. It's termination checker allows all primitive recursive functions and functions such the Ackermann function. Basically it allows multi-argument primitive recursion. This is also basically the the termination checker of Agda; I believe that Coq has some similar facilities as well though perhaps more general.

From reading the paper "Total Functional Programming" by D.A. Turner. He explains that his proposed language would be able to express all "primitive recursive functionals" as seen in System T studied by Godel. He goes on to say that this system is "known to include every recursive function whose totality can be proved in first order logic".

Dose Foetus allow all primitive recursive functionals? If so does it allow functions which are not primitive recursive functionals? Can a citation be provided for the answer to this? (this is not actually necessary as I'm just interested; it's just that some reading marital on the matter would be nice)

Bonus question:
Primitive recursive functionals have a very concise definition in terms of combinators: typed S and K (that can't express the fixed point combinators), zero, the successor function, and the iteration function; that's it. Are there other more general such languages which have such a concise definition and in which all expressions terminate?


texts: How does complexity of a counting problem influence wether it admits a closed form formula or not?

texts:
In https://arxiv.org/abs/1412.1505, the section "Results on Data Complexity" mentions the fact that since the authors are about to proove $\#P_1$ complexity for weighted model counting in Fist Order Logic. Hence, such a problem cannot admit a closed form formula.
Why is this claim true ? Are there counting problems which are hard in general but admit a closed form counting formula ?
PS:

FO$^2$ admits model counting in polynomial time with respect to the domain elements, and also admits a closed form formula for counting.


texts:
This maybe is either a question out of place or it is a very elementary one. I wonder what kind of optimization problems can be solved by Binary Search. Looking around some coding competitions, there are a bunch of 'optimization' problems (find the minimal/maximal of ... such that ...) that can be solved by Binary Search, sometimes very easily. Is there any theory that tell us what kind of optimization problems can be solved by that algorithm?, or maybe, are all optimization problems solvable by Binary Search (theoretically)?.

Thanks,
Mario.


texts: Fast classical simulation of quantum algorithms

texts:
Are there examples of cases where the classical simulation of a quantum algorithm for a problem outperforms the best previously known classical algorithm for this problem? "Outperforms" doesn't have to mean different complexity class, it could simply be better scaling.

This question was inspired by the case of efficient classical simulation of a quantum recommendation algorithm.


texts: Are there analogous works to PPSZ algorithm for #P?

texts:
The PPSZ algorithm tells us that we can do SAT-solving for
$k-$CNF in time at-most $2^{1-(1-o(1))\frac{\pi^2}{6k}}$.
My question is that do we know such results for counting problems in class #P too ? For example, for #SAT do we know any algorithm that provably runs better than $O(2^n)$ ?


texts: Finding a special cut-set in an weighted undirected graph

texts:
I encountered this sub-problem while working on a problem about robustness of networks against link failures. Suppose we have an undirected graph $G=(V,E)$ such that edges in $E$ have weights taking values from $\{-1,+1\}$. We define the cut-set for $S\subseteq V$ as the set of edges connecting nodes in $S$ to those in $V\backslash S$ (the standard definition), and the cut value of the cut-set as the sum of weights of the edges in it.

It is known that one can find the cut-set with least cut value (min-cut) in polynomial time (in terms of |V|, |E|). I am interested in finding the cut-set whose cut value is the least and greater than zero (i.e., number of edges of weight +1 exceeds the number of edges of weight -1 in the cut-set) - does there exist a polynomial-time algorithm for generating such a cut-set?


texts:
What is the complexity of computation  of zero point by  Rieman zeta function?
That is, given s, whether ζ(s)=0? Is it in P? Any reference is appreciated.


texts: Do there exists polynomial size CFG that describe this finite language?

texts:
Do there exists permutations $\pi_1,\pi_2$ and polynomial size (in $|w|=n$) context free grammar that describe the finite language $\{w \pi_1(w) \pi_2(w)\}$ over alphabet $\{0,1\}$?

UPDATE: For one permutation $\pi$ it is possible. $\pi$ is the reversal or relatively minor modification of the reversal.


texts: Noisy channel coding theorem in quantum information

texts:
Why Shannon's noisy channel coding theorem can't be used for quantum communication applications?
Schumacher proved the first Noiseless theorem and there are quantum error correction mechanisms out there.
I guess I am not sure what is the gap in knowledge to prove the noisy channel coding theorem?


texts:
I am trying to learn how to find modular decomposition of graph using the method given in the paper Simpler Linear-Time Modular Decomposition via Recursive Factorizing Permutations.
I am unable to understand the method properly which is given in the paper.
Can some one explain the procedure to find the modular decomposition of graph with example using the procedure given in this paper [ or using any other simpler algorithm available in literature ]

Thank you.


texts: The complexity of the permanent of low rank matrices

texts: I know that for an arbitrary $n \times n$ matrix, Ryser's algorithm can compute the permanent in $\mathcal{O}(2^n n^2)$ time. I'm interested in computing the permanent of $n \times n$ matrices of rank $m$. A few sources told me that this algorithm is exponential in $m$. The algorithm must also depend on $n$, so what is the $\mathcal{O}$-notation for this? $\mathcal{O}(2^m n^2)$? $\mathcal{O}(n^m)$?


texts: Counting occurences of 'a' in a book faster than O(n)?

texts:
I was asked the following question in an interview:

  How would you count the occurrences of character a in a 500-page book? For simplicity, assume that you are given the book content as a string.

I answered that linear traversal through the book is the best possible solution, since the character can randomly occur in any position, and we cannot figure out until we check every character. However, the interviewer kept insisting on a more efficient algorithm. What algorithm would be more efficient than O(n) for this problem? (if any)


texts: A function is lambda-2-definable iff it is HG computable and provably type correct in lambda-PRED2

texts:
I'm having a problem regarding Theorem 5.4.40.3 of Barendregt's Lambda calculi with types (1992), a chapter in Handbook in logic in computer science. (I'm referring to the PostScript version available on the Web.)

The theorem states that a function is $\lambda$2-definable iff it is HG (Herbrand-Goedel) computable and provably type correct in $\lambda$PRED2.  The author delegates the proof to a proceeding in FOCS, i.e., Reasoning about functional programs and complexity associated with type disciplines (1983) by Leivant.  The corresponding theorem in the proceeding is Theorem 3.1 and Corollary 3.2, although they are stated in terms of provable type-correctness in $\lambda$2, not in $\lambda$PRED2.

The first problem I'm running into is that the definition of HG computability by Barendregt doesn't make sense.  IMHO, the equation in Definition 5.4.39.1 should be replaced by
$$
\mathit{HG} \vdash p:(f_n(t^\sim) =_L (f(t))^\sim).
$$

Assuming this, I tried to prove the equivalent of Theorem 3.1 (Leivant) in terms of $\lambda$PRED2, but in vain.  Leivant's proof is informal and I have hard times formalizing it. (By using Barendregt's notation, I'm pretty sure that if $B$ is the proof of $f$'s type correctness then $[B]$ is a $\lambda$2-term that represents $f$, but I am unable to prove this.)  Besides, his proof deals with only one direction of the equivalence (provably type correct $\Rightarrow$ $\lambda$2-definable) and the rest is left unstated.  I suppose the opposite direction involves the formalization of SN, but I am unsure.

I would be the most grateful for detailed explanation of Theorem 5.4.40.3 by Barendregt.


texts:
We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of computation).

Are there any tools which do this translation? I.e. I can put in a set of transition functions and it will return an equivalent CFG.


texts: The motivation for using Karp-reductions in the theory of $\mathcal{NP}$-completeness

texts:
The notion of polynomial time reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using an algorithm for a different problem.

However, in the theory of $\mathcal{NP}$-completeness, the notion of $\mathcal{NP}$-hardness is captured via mapping reductions (Karp reductions). This concept of "restricted" reductions is much-less intuitive (at least to me). It even seems a bit contrived, as it creates a somewhat less intuitive notion of hardness; by that I'm referring to the fact that $\mathcal{NP}$ does not trivially contains $co-\mathcal{NP}$. Although in complexity theory we are very used to the concept that being able to solve a problem such as $\mathsf{SAT}$ does not imply that we can solve $\overline{\mathsf{SAT}}$, in natural settings (which are captured by Cook reductions), assuming we have an algorithm for solving $\mathsf{SAT}$, we can solve $\overline{\mathsf{SAT}}$ just by running the algorithm for $\mathsf{SAT}$ and returning the opposite.

My question is why should we use Karp reductions for the theory of $\mathcal{NP}$-completeness? What intuitive notion does it capture? How does it relates to the way we understand "hardness of computation" in the real world?


texts: Are there Belief Revision techniques for quantified data?

texts:
Are there Belief Revision techniques that aren't based solely in formal logic propositions?

For example, if one agent believes the temperature for an area is 85 degrees and another believes the temperature is 79 degrees, is there a technique in the literature that has been proposed to to harmonize their beliefs?


texts:
Factoring is not known to be NP-complete. This question asked for consequences of Factoring being NP-complete. Curiously, no one asked for consequences of Factoring being in P (maybe because such a question is trivial).
So my questions are:

Which would be the theoretical consequences of Factoring being in P? How the overall picture of complexity classes would be affected by such a fact?
Which would be the practical consequences of Factoring being in P? Please do not say that banking transactions could be in jeopardy, I already know this trivial consequence.


texts: What Fuzzy techniques can combine conflicting quantified data?

texts:
I have been reading Fuzzy Belief Revision and trying to determine how the methods could be used to combine readings from conflicting sensors. For example, if one sensor reads 70 degrees and another reads 75 degrees.

This paper uses examples that combine subjectively defined properties. For example, a car may have the properties expensive, economical, and powerful with subjectively defined values 0.75, 0.50, and 0.75, respectively.

I can't see a way to apply these techniques to quantified data but this paper, and many other papers on Fuzzy Systems, make reference to applying Fuzzy techniques to "imprecise sensors".

Is there a paper that deals directly with combining sets of conflicting sensor readings using Fuzzy methods? Or otherwise combining quantified information rather than subjective properties?


texts: Expansion normal forms of confluent term rewriting systems

texts:
Suppose one has two rewrite rules $\to^\eta,\to^\beta$, both of which are confluent and such that $\to^A := \to^{(\eta \cup \beta)}$ is also confluent.  Define a $\beta$-normal form relative to $\eta$ to be $m$ such that

$m$ is a $\beta$ normal form;
$m \to^\eta n$ implies $n \to_{\beta}^* m$

One may think of $\to^\eta$ as being some kind of expansion that could prevent any term from having an $\to^A$ normal form.

Does anyone know of a definition like this, and/or nice properties such as: "relative normal forms if they exist are unique."

One can show that if $\eta$ requests $\beta^*$ : i.e. if there is a divergence between $n \to^\eta n'$ and $n \to_{\beta}^* n''$ then there is a join $n' \to_{\beta}^* m$ and $n'' \to^\eta \cdot \to_\beta^* m$, then relative normal forms (if they exist) are unique.

In fact, one can show that if the confluence of $\to^A$ is proved by decreasing diagrams with $\eta$ bigger than $\beta$, then again the property holds.  Essentially one proves the following first: if $m$ is a relative normal form with

$\newcommand{\ra}[1]{\kern-1.5ex\xrightarrow{\ \ #1\ \ }\phantom{}\kern-1.5ex}
\newcommand{\ras}[1]{\kern-1.5ex\xrightarrow{\ \ \smash{#1}\ \ }\phantom{}\kern-1.5ex}
\newcommand{\da}[1]{\bigg\downarrow\raise.5ex\rlap{\scriptstyle#1}}
\begin{array}{c}
 s & \ra{\eta} & t \\
\da{\beta^*}\\
 m
\end{array}$

then $t \to_\beta^* m$.

The above then implies that any $\to^A$ sequence leaving a relative normal form will return by a $\beta$ sequence.  This in turn, along with the confluence of $\to^A$ can be used to show that relative normal forms are unique.

I can certainly fill in the details if anyone likes; however, this seems like something that should be generally true.  Does anyone know of any such results or counterexamples?


texts: Translation of context-free parsing into SAT

texts: Is there a published algorithm for translating a context-free parsing problem into SAT? That is, an algorithm that translates a context-free grammar and an input string into a set clauses that is satisfiable iff the input string is well-formed according to the grammar.


texts: Maximizing a submodular function with restricted values

texts:
Maximizing a general monotone submodular function $f$ under the constraint that $|S|\leq k$, can be approximated to $(1-1/e)$.  I am wondering if a better approximation algorithm exists if the function $f$ has these additional properties for any element $x$ and subset $S$:

$f(\{x\}) \in \{0, 1, 2\}$
$f(S \cup \{x\}) - f(S) \in \{0, 1, 2\}$

or even the more restricted properties :

$f(\{x\}) \in \{0, 1\}$
$f(S \cup \{x\}) - f(S) \in \{0, 1\}$


texts: Are all computational models of quantum computing equivalent?

texts:
So the question was inspired by a seminar which presented the following models of quantum computing:

Quantum Computing with Photons
Quantum Computing with Rydberg atoms
Quantum Computing with trapped ions
Quantum Computing with Josephson Junction

Are these computational models completely equivalent to one another i.e the complexity of every problem is equivalent in all these models ?
I am asking here because the answers I got from Physicists were not very rigorous (I am a Physicist).


texts:
We know that the first level of the polynomial hierarchy (i.e. NP and co-NP) is in PP, and that $PP \subseteq PSPACE$. We also know from Toda's Theorem that $PH \subseteq P^{PP}$.

Do we know whether $PH \subseteq PP$? If not, why is it that $P$ with a $PP$ oracle is stronger than $PP$? Is it possible that $PH \nsubseteq PP$ and $PP \nsubseteq PH$?

This question is very simple, but I haven't found any resources addressing it.

I asked this related but much less specific question on math overflow before learning more about the topic.

Here is a somewhat related (but different) question: Is $coNP^{\#P}=NP^{\#P}=P^{\#P}$?

Update: Take a look at Noam Nisan's question here: More on PH in PP?


texts:
With Turing machines, by imposing certain restrictions on the form of the transition function, one can get a machine that accepts only regular languages. I am wondering what is the counterpart in lambda calculus? In other words, how to restrict lambda calculus so it accepts only regular languages?

Related papers would be great, just as an explanation if my question does not make any sense, if that is the case.


texts: How much larger than the relaxation time can the mixing time be?

texts:
The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer.

Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite state space. The relaxation time $t_{\mathrm{rel}}$ is the reciprocal of the absolute spectral gap. The $\epsilon$-mixing time $t_{\mathrm{mix}}(\epsilon)$ is the shortest time in which, regardless of any initialization, the state becomes $\epsilon$-close to the stationary distribution in the total variation sense. The two are related as:

  Levin-Peres-Wilmer (Theorem 12.3, 12.4)
  $$(t_{\mathrm{rel}}-1)\log\frac{1}{2\epsilon}\leq t_{\mathrm{mix}}(\epsilon)\leq t_{\mathrm{rel}}\log\frac{1}{\epsilon\min_x\pi(x)}~,$$
  where $\min_x\pi(x)$ is the smallest atom of the stationary distribution.

If the Markov chain is a random walk on a 3-regular expander graph, then $t_{\mathrm{rel}}$ is a constant, but $t_{\mathrm{mix}} = \Theta(\log n)$ if the graph has $n$ vertices. Thus, the upper bound here better describes the behavior of the mixing time relative to the relaxation time, since $\pi(x) = \frac 1n$ for all $x.$

My question is: How large can the ratio $\frac{t_{\mathrm{mix}}(1/8)}{t_{\mathrm{rel}}}$ be? From above theorem, it is at most $\log\frac{8}{\min_x\pi(x)},$ but can it indeed be as large as this when $\min_x \pi(x)$ may be very very tiny? I conjecture that

$$\frac{t_{\mathrm{mix}}(1/8)}{t_{\mathrm{rel}}}\leq O(\log n)~.$$

Any proofs or counterexamples?


texts:
I am doing some research on machine learning algorithms in the context of a seminar, which focuses on Energy-Based Modeling vs Deep Learning specifically in working with images Modeling. Now I know these are broad topics, but I was wondering what some specific similarities and differences are. I have read countless papers that say "EBMs have properties that make them better than DL in certain tasks" but I haven't really found a comprehensive motivation

What is the problem that EBM is solving compared to DL?
Why are we doing this?

I hope this is the right site for this question, https://meta.stackexchange.com/questions/130524/which-stack-exchange-website-for-machine-learning-and-computational-algorithms brought me here.
Thanks in advance


texts:
Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition is strongly NP-complete problem even if input integers are bounded by a polynomial.

  Assuming, $\mathsf{P \ne NP}$, Can we prove that intermediate NP-complete problems must exist? If the answer is yes, Is there such "natural" candidate problem?

Here, Intermediate NP-complete problem is a problem that neither has a pseudo-polynomial time algorithm nor NP-complete in the strong sense.

I guess that there is an infinite hierarchy of intermediate NP-complete problems between weak NP-completeness and strong NP-completeness.

EDIT March 6th: As mentioned in the comments, an alternative way to pose the question is:

  Assuming, $\mathsf{P \ne NP}$, Can we prove the existence of NP-complete problems that neither have polynomial time algorithm nor NP-complete when the numerical
  inputs are presented in unary? If the answer is yes, Is there such "natural" candidate problem?

EDIT2 March 6: The reverse direction of the implication is true. The existence of such "intermediate" $NP$-complete problems implies $\mathsf{P \ne NP}$ since if $\mathsf{ P=NP}$ then unary $NP$-complete problems are in $P$.


texts: How to detect dead ends on a board / in a graph?

texts:
Given a (2D) board of quadratic cells (movement allowed between 4-neighbours), many of which are blocked, and given a certain starting position, how can I efficiently detect dead ends, i.e. regions of connected free cells that can be reached from the starting position only through the same connection? Can this be done in O(n)?

Obviously this can also be formulated as a graph problem, but the board shape imposes restrictions (most significantly: no more than 4 edges per vertex) that may lead to a more efficient algorithm.


texts: mathematical study of the 'Church-Turing thesis'

texts:
The Church-Turing thesis postulates that essentially all models of computation -Turing machines, Post systems, lambda-definability etc yield the same class of computable functions. Now we can think of a much wider class of models of computation including dynamical systems, DNA and molecular models, quantum computers, chemical reactions, etc.

Can we regard the notion of computation as analogous to that of  an abstract group and in analogy to Cayley theorem of group theory (every group can be realized as a subgroup of a permutation group),  a computation as a realization in a particular model. More abstractly, the realization of computation in any of the different models is similar to the notion of group representation, in which the same abstract group can be realized variously as a  group of linear automorphisms of a chosen linear space. Is this view of computation correct or reasonable?
Why does (or should)  a mathematical structure carry a generic computation? Just as symmetries of physical systems give rise to conservation laws in physics (Noether's theorem), are there analogs  in  this setting?
How do we determine whether a mathematical structure has a rich or poor computational structure?
How is the notion of computation  supported in each structure? Is it always carried in the same way? I am looking for ideas in analogy to that of 'configuration space' or phase space in a dynamical system which has the structure of  a  symplectic manifold and is the cotangent bundle of the dynamical system  enabling the Hamiltonian formulation of dynamics (which holds uniformly for classical as well as quantum mechanics)
Are there any possible approaches towards a mathematical proof (or disproof) of the 'Church-Turing thesis'?


texts: Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

texts:
Crossposted from MO.

Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).

  Are there NP-hard graph problems that can be solved in
  polynomial time for $C$ other than Clique and Clique
  cover?

If I remember correctly, this is impossible for
independent set (unless $P=NP$).

Search in graphclasses.org didn't find any.

A class for which Clique and Clique cover are
polynomial is C5,C6,X164,X165,sunlet4,triangle-free

Edit

Negative for IS and Domination is in this paper. Page 2, the graphs $S_{i,j,k}$.


texts:
Given a finite group $G$ of size $n$ by the table representation. I want to compute the conjugacy classes of group $G$. A trivial algorithm seems to take $O(n^2)$ operation ( $b = g^{-1}a g$ type checking ). For each pair (I know I don't need to do for all pairs ) of elements in $G$ check $b = g^{-1}a g$. I tried to search on internet but did not find anything specific about it in general.

Question : What is the fastest known algorithm for finding conjugacy classes?


texts: Who coined the term "empirical entropy"?

texts:
I know of Shannon's work with entropy, but lately I have worked on succinct data structures in which empirical entropy is often used as part of the storage analysis.

Shannon defined the entropy of the information produced by a discrete information source as $-\sum_{i=1}^k p_i \log{p_i}$, where $p_i$ is the probability of event $i$ occurring, e.g. a specific character generated, and there are $k$ possible events.

As pointed out by MCH in the comments, the empirical entropy is the entropy of the empirical distribution of these events, and is thus given by $-\sum_{i=1}^k \frac{n_{i}}{n} \log{\frac{n_{i}}{n}}$ where $n_{i}$ is the number of observed occurrences of event $i$ and $n$ is the total number of events observed. This is called zero-th order empirical entropy. Shannon's notion of conditional entropy has a similar higher order empirical version.

Shannon did not use the term empirical entropy, though he surely deserves some of the credit for this concept. Who did first used this idea and who first used the (very logical) name empirical entropy to describe it?


texts:
Path coloring is the problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors.

We know that coloring a set of paths with the minimum number of colors is in $\sf{P}$, if the underlying graph is also a path. It is known that path coloring in trees is $\sf{NP}$-hard. There is a greedy algorithm by Raghavan and Upfal (Efficient routing in all-optical networks,  STOC 1994), which colors any set of paths of load $L$ on an undirected tree using at most $3L/2$ colors. This bound is tight, since there exists a set of undirected paths on an undirected binary tree, which requires at least $3L/2$ colors.

What are the results known for general graphs, both approximation algorithms and lower bounds?


texts: Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

texts:
This is a follow up to this question, and is related to this question of Shiva Kinali.

It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use hierarchy theorems. I want to know if the proofs are "pure" diagonalization theorems, or if they use something more that usual diagonalization. So my question is

  is there a reasonable relativization which puts permanent in uniform $\mathsf{TC^0}$?

Note that I am not sure how to define oracle access for uniform $\mathsf{TC^0}$, I know that finding the correct definition for small complexity classes is nontrivial. Another possibility is that permanent is not complete for $\mathsf{\#P}$ in the relativized universe, in which case I should use some complete problem for $\mathsf{\#P}$ in the relativized universe in place of it, and I think $\mathsf{\#P}$ should have a complete problem in any reasonable relativized universe.


texts:
Consider $X$ an $\mathsf{NP}$-complete language e.g. $3-SAT$. I'm looking for an algorithm $A$ for solving $X$ with the following property. Given $M \subset \lbrace 0, 1 \rbrace^*$ any set of words s.t. $X$ with promise $M$ is decidable in polynomial time, I require $A$ to decide $X$ with promise $M$ in polynomial time

  Does such $A$ exist?

The motivation for the question comes from Levin search which would satisfy the above condition if we considered the candid search problem instead of the decision problem

Is the answer affected by adding the assumption $M \in \mathsf{P}$?


texts: A question to the #P-complete proof of the permanent from Ben-Dor/Halevi

texts:
In the paper of Ben-Dor/Halevi [1] it is given another proof that the permanent is
$\#P$-complete. In the later part of the paper, they show the reduction chain
\begin{equation}
\text{IntPerm} \propto \text{NoNegPerm} \propto \text{2PowersPerm} \propto \text{0/1-Perm}
\end{equation}
while the permanent value is preserved along the chain. Since the number of satiesfying assignments of a 3SAT formula $\Phi$ can be obtained from the permanent value, it is sufficient to compute the permanent of the final $0/1$-matrix. So far so good.

However, it is well known that the permanent of a $0/1$-matrix $\text{A}$ is equal to the number of perfect matchings in the bipartite double cover $G$, i.e., the graph from the matrix $\begin{pmatrix} 0 & \text{A} \\
\text{A}^t & 0 \end{pmatrix}$. And this number can be computed efficiently if $G$ turns out to be planar (using Kastelyens algorithm).

So in total this means, someone could compute the number of satiesfying assignments of a boolean formula $\Phi$ if the final graph $G$ is planar.

Since the embedding of $G$ depends heavily on the formula $\Phi$, the hope is, that there exists certain formulas that lead more often into planar bipartite covers.
Does anyone know if it has ever been investigated how large the chances are that $G$ will be planar?

Since counting satiesfying solutions is $\#P$-complete, the graphs will be for sure almost always non-planar, but i can not find any hints regarding this topic.

[1] Amir Ben-Dor and Shai Halevi. Zero-one permanent is #p-complete, a simpler proof. In 2nd Israel Symposium on Theory of Computing Systems, pages 108-117, 1993. Natanya, Israel.


texts:
Motivation: A coauthor edits a manuscript and I would like to see a clear summary of the edits. All "diff"-like tools tend to be useless if you are both moving text around (e.g., re-organising the structure) and doing local edits. Is it really so hard to get it right?

Definitions: I would like to find the minimum edit distance, where the permitted operations are:

"cheap" operations: add/change/delete a single character (the usual Levenshtein operations),
"expensive": operations: move a substring to a new location ($abcd \mapsto acbd$ for any strings $a$, $b$, $c$, $d$).

Given two strings $x$ and $y$ and integers $k$ and $K$, I would like to solve the following problem:

can you transform $x$ into $y$ using at most $k$ cheap operations and at most $K$ expensive operations?

Questions:

Does this problem have a name? (It sounds like a very standard question in the context of sequence alignment.)
Is it hard?
If it is hard, is it fixed-parameter tractable with $K$ as the parameter?
Are there efficient approximation algorithms? (E.g., find a solution with at most $2k$ cheap and $2K$ expensive operations if a solution with $k$ cheap and $K$ expensive operations exist.)

I tried to have a look at the string metrics listed in Wikipedia, but none of them looked right.


texts:
What are some interesting open or solved-but-hard questions around problems having linear-time solutions?  Ala riffle shuffles.

I'm especially curious about problems which people believe to be linear-time but for which either no linear-time algorithm is known or for which finding one proved difficult.

As a technical matter, I'm perhaps most interested in weak-linear-time on a single-tape nondeterministic machine, but other linear-time models are still interesting, ala deterministic or multi-tape models.  I'm aware that strong-linear-time on a single tape nondeterministic machine is regular, hence linear-time on a single-tape deterministic machine is regular too.


texts: Non-isomorphic minimal non-deterministic finite automata

texts: Can somebody provide an example of two equivalent (recognizing the same language) minimal non-deterministic automata (NFA) which are not isomorphic?


texts:
Can the type theory of Coq (pCuIC) be modeled in all higher Grothendieck toposes?
First of all, even the set theoretical model is not complete (e.g. inductive types in Prop). Although, this is expected to work.
Shulman has shown that type theory with W-types can be interpreted in higher Grothendieck toposes. Inductive families can be reduced to W-types. These are claimed to be similar to the inductive families of Coq. However, I am not sure I’ve ever seen a precise result along these lines.
Voevodsky has made a similar reduction for Coq’s inductive types, but I am not sure it’s entirely up to date, or complete. The note was never published. Moreover, it was written before pCuIC came out.
Finally, Coq also has co-inductive types. Again, M-types can be interpreted in HoTT, but I am not aware of a reduction of Coq's co-inductive types to M-types.


texts:
For a set of sets $A$, let $\cup A := \cup_{S \in A} S$.

Consider the following problem:

Input:

a list of $m$ weights $w = (w_1, \ldots, w_m)$,
a list of $n$ distinct subsets $T = (S_1, \ldots, S_n)$ such that $\bigcup_{S\in T} S = [m]$,
an integer $k$.

Let $P$ be a partition of $T$.
We say $P$ is a $k$-good partition when
the size of each part is at most $k$:
$\forall p \in P \ |p| \leq k$.
The cost of $P$ is defined as
the sum of weight of items counted once for each part they appear in, i.e.
$$cost(P) := \sum_{p\in P} \ \sum_{x\in \cup p} w_x $$

Output: a $k$-good partition of $P$ of $T$ minimizing $cost(P)$.

  What is the complexity of this problem?
  Is it NP-hard or is there a polynomial-time algorithm?

Example:
$m = 7$, $w=(2,2,3,4,1,2,2)$,
$n = 3$, $T=(S_1=\{1,2,3\}, S_2=\{3,4,5\}, S_3=\{5,6,7\})$
$k=2$

In this case, since $k<|T|$,
it is obvious that more than one partition is needed.
Moreover,  $S_1$ and $S_2$ should be packed together in the same configuration because of their heavy overlap ($S_1 \cap S_2$ gives the biggest overlap in our example - we pay 3 less cost units). So the optimal $P$ is $\{S_1, S_2\}, \{S_3\}$ with the total cost 12+5=17.

The unweighted version (when the weights of the elements are all 1)
is also very interesting to me.


texts:
DISCLAIMER: This is an open ended question and stackexchange puritans would probably feel an extraordinary urge to vote it down to oblivion. However, I cannot think of any other forum more appropriate and promising for getting answer to this question.

While working on a research problem for course project I realize that if I model my problem in a particular way I could use techniques from a specialized track [for the recent case - PASCAL Recognizing Textual Entailment Challenge]. After the initial joy, I'm generally puzzled by the numerous papers with all of them silently shouting "Read me, else you'll miss the best way to solve the problem!". How does one learn to filter which paper to read and which one to discard in the face of deadline? Anything other than sort_by_citation count?


texts: Why are simulations defined as relations and not as functions?

texts:
I am interested in simulations between labelled transition systems (LTS).

LTS are basically relational systems, in particular they can be viewed as structures for a purely binary relational signature (i.e. a signature having only binary relation symbols).

In my understanding simulations between LTS should be regarded as some form of morphisms between these structures.

So why do we use simulations as congruence relations (that is relations compatible with the transition relations) instead of homomorphisms of the relational structures?

Is there any theoretical reason that makes relations more suited than functions for the purposes of similarity-bisimilarity?


texts:
Dequantumizable problems have been taking some headlines these days (for example https://www.scottaaronson.com/blog/?p=3880 and https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/).

What are some problems that are currently considered for dequantumization?
Is there any governing principles to look for in warning signs in attempting or abandoning dequantumization?


texts: Better approximation for special case of 3-hitting set

texts:
I have a question based on 3-Hitting Set problem. In this problem, we are given a universal set U of size n and a set of subsets S such that $\forall $ s $\in$ S |s|<=3.
FOr this problem, Integer programming formulation is given by
$x_{a}+x_{b}+x_{c} >=1 $ (a,b,c) $\in$ S

$\forall x_{i} \in $(1,0) where $i=1,2 \ldots n $

minimize $\sum x_{i} $

where each variable $x_i$ corresponds to element $i\in$ U.

A Linear programming relaxation would be
0<=$x_{i}$=<1 instead of $x_{i} \in$ {1,0}

After performing linear  programming we know that
In Every s $\in$S x_{a}+x_{b}+x_{c} >=1  at least one of  $x_{i}>=\frac{1}{3}$
so $x_{i}>=\frac{1}{3}$   is made as 1 and the corresponding elements are selected in the solution. There may exist a set s such that  $x_{a}+x_{b}+x_{c} >=1$ so that $x_{a},x_{b},x_{c}>=\frac{1}{3}$ and we will be picking all three elements. This way, we will get a three approximation after rounding $x_{a},x_{b},x_{c}$ to 1.

My question is

I look at a  special case of 3 -hitting set H' in which size of each set s is exactly 3 and optimal solution for linear programming problem is $ \forall x_i  =\frac{1}{3} $. Now, is it possible to improve the approximation factor to less than 3


texts: Enumerating all (super)orientations of an undirected graph

texts:
Given an undirected graph $G$, an orientation of $G$ is a directed graph obtained by assigning every edge a direction, a superorientation of $G$ is a directed graph obtained by orienting every edge in one direction or both ways.

Aim:
Enumerate all superorientations (isomorphic superorientations count as one) of an undirected graph.

What for:
Compute all kernels (absorbing independent vertex sets) in as many digraphs as possible by using polyhedral descriptions of kernels, which are essentially linear programs (hence the problem can be solved efficiently).

Current solution (for enumerating all superorientations):
Given an undirected graph $G=(V,E)$,
for each edge $uv\in E$ generate 3 different arc sets $\{(u,v)\},\{(v,u)\} $ and $\{(u,v),(v,u)\}$ first.
Then enumerate all combinations of arc sets, which yields precisely $3^{|E|}$ digraphs in the result.

Code in Mathematica:

SuperOrientation[g_Graph]:= Module[{el,tal,al},
  el=EdgeList[g];
  tal=DirectedEdge@@@el;
  al=Flatten/@Tuples[Subsets[#,{1,2}]&/@Thread[List[tal,Reverse/@tal]]];
  Graph/@al];

Problem:
Current solution gives too many isomorphic digraphs, especially for highly symmetric graphs.
I can delete isomorphic superorientations "efficiently" in Mathematica (the isomorphism test in Mathematica is implemented by NAUTY, which claims to be the fastest graph isomorphism test program in practice).
But testing graph isomorphism is still quite time consuming due to the fact that graph isomorphism problem is NP-intermediate.

Question:
Is there a way to generate as less isomorphic graphs as possible in the enumeration before the isomorphism test?
It is unlikely to have a general solution.
But how about some special classes of graphs, say highly symmetric graphs.
Complete graphs, or subgraphs of complete graphs with only a few edges missing might be good starts, as my isomorphism test for superorientations of $K_7$ never ends.


texts: What kind of theoretical object corresponds to a C++ concept?

texts: I am lacking a background in theoretical computer science but I would have liked to understand to what kind of theoretical objects C++ concepts corresponds to. Basically, C++ concepts allow to define a set of types that satisfy a list of constraints. So, from a theoretical standpoint, what C++ concepts correspond, or roughly correspond (and in that case what are the differences), to?


texts: Proof assistant formalizations of Finite Model Theory

texts:
I'm wondering if anyone knows of a formalization (even limited) of any part of finite model theory in any of the major proof assistants. (I'm most familiar with Coq, but Isabelle, Agda, etc. would acceptable.)

Especially of interest would be any of the results in descriptive complexity.


texts: Find all nearby points in a set, for each element of the set

texts:
Given a finite set $S$ of points in $\mathbb R^p$ and a number $\rho$, my collaborators and I want to find, for each $s\in S$, the other points in $S$ that are within $\rho$ of $s$. Of course there's the obvious $O(|S|^2)$ algorithm, and we also came up with something (roughly, sort in each dimensions, then for each dimension and for each element of $S$ mark nearby points in some sparse matrices, and then combine the sparse matrices) that has better running time under certain assumptions, but not in the worst case.

I feel that this must be a standard problem, but I haven't been able to find references. I was wondering if someone here knows what I should search for or can suggest a good reference to start from?

Thanks in advance!


texts: Can one return to a TCS research job after an excursion to a non-research industry job?

texts:
I have heard from some senior researchers in theoretical computer science that working in a non-research industry job, even just for a few years, will kill your career as a TCS researcher.
However I am suspicious of the claim that the road from being a TCS researcher to a non-research job in the industry is a one-way street. I want to know if this claim is plausible and any implications of making an excursion into a non-research job in the industry in case one later decides to return to a research job in academia.

Do you know examples of people who went to non-research industry jobs after their completing their PhD, worked there for a few years, and successfully made it back into academia as researchers (e.g. got research faculty positions)?
If yes, what fraction of senior researchers (tenured) do they constitute in your department or departments you are familiar with?
What fraction of such candidates who apply for academic research positions fail to obtain one?
Does the number of years in non-research jobs before returning make a difference?
More generally, what role would such excursions play in decisions made by hiring committees?

Since the answer may vary from a region to another one (e.g. North America, Europe, etc.) please mention the region you are talking about in your answer.
For the purposes of this question, let's consider all jobs in which the main task is conducting (publishable) research as "academia" and all jobs in which the main task is not conducting (publishable) research and it is difficult to do research and publish papers as "industry".


texts: Known properties of a specific class of quantum states

texts:
Recently, I have been studying a quantum protocol for the "Hidden Matching" problem that makes use of states that can be expressed as

$|\psi\rangle=\frac{1}{\sqrt{n}}\sum_{i=1}^n (-1)^{x_i}|i\rangle$,

where $x_i\in \{0,1\}$ and $n$ is a power of 2. Note that instead of an $n$-level system we can consider these as states of $\log_2 n$ qubits. I suspect these states to have appeared in other contexts as they are a straightforward and useful way to map an $n$ bit string into an exponentially smaller amount of qubits. Hence I am wondering: have the properties of these types of states been already extensively studied?

I am particularly interested in how the reduced density matrix of each qubit and the entanglement of the state depend on the bit values $x_i$.

Thank you!


texts: What is known about the hardness of the chromatic index for restricted graph classes?

texts:
There is a nice paper from 1991 that contains three diagrams about different graphclass-families showing what is known about the hardness of determining the chromatic index for them.
Are there any news since then on these?

I'm most interested in what is known about graphs with a bounded chromatic number.
My curiosity has been raised by https://mathoverflow.net/questions/238448/hypergraph-edge-colouring.


texts: What Is the Complexity of This Two-to-One Matching Problem?

texts:
Given a graph $G=(V,E)$ and a function $c:V\mapsto\{1,2\}$. The function $c(\cdot)$ divides the vertices into two disjoint sets $V_1$ and $V_2$, where for all $v_1\in V_1$, we have $c(v_1)=1$ and for all $v_2\in V_2$, we have $c(v_2)=2$. There is no edge between $v_2\in V_2$ and $v_2'\in V_2$. There are edges between $v_1\in V_1$ and $v_2\in V_2$ and between $v_1\in V_1$ and $v_1'\in V_1$ (for $v_1\ne v_1'$). Find a two-to-one matching between $V_1$ and $V_2$ of maximum cardinality. That is, a set $S:=S_1\times S_2\subset V_1\times V_2$ such that:

cardinality($S$) is maximum;
for each $(s_1,s_2)\in S$, $\{s_1,s_2\}\in E$ ;
$S_1$ is an independent set;
for each $s_2\in S_2$, degree($s_2$) is at most $2$; and
for each $s_1\in S_1$, degree($s_1$) is at most $1$. $\leftarrow$ EDIT

Is this problem NP-hard?

I was trying to prove that this problem is NP-hard by reduction from Conflict-Aware Weighted Bipartite B-Matching Problem (CA-WBM).

The authors proved that CA-WBM is NP-hard by a reduction from weighted independent set problem. Since I do not have weights in my problem, I was able to prove that even the Conflict-Aware Unweighted Bipartite B-Matching Problem (CA-UBM) is NP-hard (since the unweighted independent set is NP-hard). But I could not reduce CA-UBM to my problem. The issue is that in my problem the cost function is restricted to take only two values $\{1,2\}$.


texts:
I need a fast min-dominating-set code for some complexity lower bounds research I am doing.

I could transform to SAT and use an off the shelf SAT solver; but I was hoping min-dom-set had something out there comparable to Cliquer for max-clique.

Suggestions?

--Update--
Currently using Z3 SMT Optimize Python bindings subject to minimizing sum of dominating vertices. 0 = default, 1 = dominating. Sum of vertex and neighborhood must be >= 1 for each vertex. Here is the source code.


texts:
In John Mitchell's book "The Foundations of Programming Languages", he considers a typed lambda calculus with unit, exponential, product, (binary) coproduct types, and arbitrary recursive types (p126). Later in the book he shows how to construct models of all these types. (I'm pretty new to all of this, but I assume this is a pretty standard system.)

It looks as though it is not possible to extend this system with a 0 type for the following reason:

Let $\sigma$ be $\mu t.t\to 0$. $\mbox{unfold}: \sigma \to \sigma \to 0$ and $\mbox{fold}: (\sigma \to 0)\to \sigma$. Then $W(\mbox{unfold})(\mbox{fold}(W(\mbox{unfold}))): 0$, where $W = \lambda xy.xyy$.

From this you can prove all equations between terms (e.g. from the existence of a closed term $t:0$, $\lambda x.t:A \to 0$ is an isomorphism between any type $A$ and $0$.)

A natural thought would be to work in a linear or affine type theory where the $W$ combinator isn't allowed, and which therefore might allow solutions to type equations like $\sigma = \sigma \to 0$.

My questions is: Is the resulting type theory consistent, and can anyone explain to me how to go about constructing models? (References would also be welcome, but the papers I've looked at so far have generally presupposed more knowledge than I have).


texts: Why do theoreticians in CS use multiple-letter variables?

texts:
This is a "dual" question of a popular post on math.se.

Some mathematical objects in computational complexity theory have multiple-letter names.   Complexity classes such as $\mathbf{BPP}$ have an established multiple-letter name.  So do some computational problems, although the naming convension seems to vary.

I am happy with names such as $\mathbf{BPP}$; however, when I write $\mathbf{PromiseBPP}$ on paper or blackboard over and over, I wish its name were more concise (in fact, some authors prefer to write it as $\mathbf{prBPP}$).
In a popular textbook in complexity, a polynomial that appears in the chapter on algebraic complexity of the book is named as $\mathtt{EXACTLY-ONCE}$, which I do not think is a suitable name to write by hand.

Considering the arguments in the original post on math.se, the pros of shorter names seem to apply more to TCS than those of longer names.  After all, what theoreticians do is to work on paper and blackboards, not to write large and complex software with editors that do auto-completion.

Some early literature takes different approach to names.  In Cinderella Book, computational problems have concise names such as $L_{\mathrm h}$ (which stands for the Hamiltonian path problem).

Thus the question is: why do theoreticians in CS use multiple-letter variables?  Or do we have to give long names to objects we are working on?


texts: complexity of greatest common divisor (gcd)

texts:
Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest complexity class this problem is contained in? Can you provide a reference?

In this question I am not primarily interested in asymptotic bounds on the running time, but rather in complexity classes. Is the problem in AC? Can it be proven not to lie in AC0? What are other complexity classes inside P that are of relevance here?


texts: What is necessary and/or sufficient requirement for a subring of a field to be computable?

texts:
As title asks, what is necessary and/or sufficient requirement for a subring of a field to be a computable ring?

Conditions on either field or subring are fine.


texts: Complexity status of restricted k-clique

texts:
Restricted $k$-clique:

Input: $(G,v,k)$ where $v$ is vertex in $V$

Output: k-clique containing vertex $v$.

What is the space and time complexity status of this Restricted $k$-clique problem?

Is it same as $k$-clique problem?

I trying to show this problem is in $L$ or $NL$


texts: Does focused proof search ever have to backtrack across the choice of focus formula?

texts:
There are a lot of different "focused" sequent calculi for lots of different logics, but my understanding is that many or most of them have the following flavor.  First one divides the connectives into "left-asynchronous / positive" (e.g. $\vee$, $\oplus$, $\otimes$, $\exists$), whose left rules are invertible, and "right-asynchronous / negative" (e.g. $\wedge$, $\Rightarrow$, $\multimap$, $\forall$), whose right rules are invertible.  Then the focused proof search (i.e. building a sequent calculus proof bottom-up) has two phases.  First we apply all the asynchronous/invertible rules, in any order.  Second, we focus on some formula and apply all of its synchronous rules, keeping focus on the formulas thereby generated and immediately applying any applicable asynchronous rules (or, equivalently, reverting to phase one in all generated subgoals), until we reach an atomic formula.  At that point we can either finish the proof with an identity rule, or re-focus on a different formula.
At least some systems require the proof to finish as soon as the focus formula becomes atomic, which I believe means that if you chose the wrong formula to focus on in the first place you may have to backtrack.  My question is rather about what happens if we allow the proof to re-focus on a different formula when it reaches an atomic one.  In that case, is it possible to "choose the wrong formula" to focus on and have to backtrack?  In other words, is it ever possible that there are synchronous formulas that must not be decomposed in a proof, or that must be decomposed in a particular order?
It's easy to come up with examples where you can get in trouble if you try to apply synchronous rules before asynchronous ones, e.g. $p\vee q \vdash q\vee p$.  But the focused method requires all asynchronous rules to happen immediately, so this sort of problem doesn't arise.
Note also that there is another unrelated source of backtracking that this says nothing about, involved in individual synchronous rules.  For instance, there are two $\& L$ rules that we have to choose between, and in a rule like $\otimes R$ we have to decide how to split the context between the two premises, and it's certainly always possible to make wrong choices there and have to backtrack.  That's not what I'm asking about.
I've phrased this as a general question about all focused sequent calculi, but of course it's possible that the answer depends on the logic or on the details of the calculus.  In that case I would be interested to know what properties of a logic or calculus lead to different behavior.


texts: Efficiently computable function as a counter-example to Sarnak's Mobius conjecture

texts:
Recently, Gil Kalai and Dick Lipton both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the Riemann Hypothesis.

  Conjecture. Let $\mu(k)$ be the Möbius function. Suppose $f: \mathbb{N} \to \{-1,1\}$ is an $\mathsf{AC}^0$ function with input $k$ in the form of binary representation of $k$, then
  $$ \sum_{k \leq n} \mu(k) \cdot f(k) = o(n) \text.$$

Note that if $f(k) = 1$ then we have an equivalent form of the Prime number theorem.

UPDATE: Ben Green on MathOverflow provided a short paper which claims to prove the conjecture. Take a look at the paper.

On the other hand, we know that by setting $f(k) = \mu(k)$ (with slight modification so the range is in $\\{-1,1\\}$), the resulting sum has the estimation
$$ \sum_{k \leq n} \mu(k)^2 = \Omega(n) \text.$$
There is an upper bound that $\mu(k)$ can be computed in $\mathsf{UP} \cap \mathsf{coUP} \subseteq \mathsf{NP} \cap \mathsf{coNP}$, so the constraint proposed on $f(k)$ in the conjecture cannot be relaxed to an $\mathsf{NP}$ function.
My question is:

  What is the lowest complexity class $\mathsf{C}$ we currently know, such that a function $f(k)$ in $\mathsf{C}$ satisfies the estimation
  $$ \sum_{k \leq n} \mu(k) \cdot f(k) = \Omega(n) \text{?}$$
  In particular, since some of the theorists believe that computing $\mu(k)$ is not in $\mathsf{P}$, can we provide other $\mathsf{P}$ functions $f(k)$ which implies a linear growth in the summation? Can even better bounds be obtained?


texts:
What tools do you use to write
  papers?

From the little experience that I have, theoreticians spend a large amount of time writing and refining papers, besides actually being creative. That is, communicating their work to other people. Maybe papers are not the right way to do so, but that should be left for another discussion. In any case, it seems like one wants to reduce the time spent writing up the results by using as good software tools as possible. So, this questions aims at finding out about some hidden treasures out there.

I think most of us use LaTeX and some system for organizing paper references. But there are also vim/emacs and some very nifty libraries which have been a huge time saver for me. Therefore I wanted to know about the setup you use for writing papers, and maybe also some things you've tried to learn and didn't work for you. I would be especially interested in things which might not be as well known but have turned out to speed up things, even if it is, say, some very specific software for drawing graphs or auto-completion features.

Don Knuth tells about his setup in an interview here. Search for the question "What set of tools do you use [...]".

UPDATE: Sadeq pointed me to a discussion about tools for drawing diagrams here.


texts: What is the complexity of minimum weight odd T-join?

texts:
Let $G=(V,E)$ be an undirected graph and let $T \subseteq V$. A subset $J$ of $E$ is called a $T$-join if $T$ is equal to the set of vertices of odd degree in the graph $(V, J)$. Further $J$ is an odd (even) $T$-join if it contains an odd (even) number of edges.

It is well known that the following problem has a strongly polynomial time solution (Schrijver, Theorem 29.1):

  Given a graph $G = (V,E)$, a weight function $w \in \mathbb{Q}^E$, and the vertex set $T \subseteq V$, find a $T$-join of minimum total weight.

However, I am interested the complexity of the following problem:

  Given a graph $G = (V,E)$, a weight function $w \in \mathbb{Q}^E$, and the vertex set $T \subseteq V$, find an odd (or even) $T$-join of minimum total weight.

The problem is still interesting even if we assume all edge weights are non-negative. In fact, efficient algorithms for both the odd and even case with non-negative weights would imply efficient algorithms for both cases with negative weights.

Cook, Espinoza, and Goycoolea describe an $O(2^{|T|} + |T|^2|V|^2 + |V|^3)$ time algorithm for a slight variation on the problem where edges are colored red and blue and you want an odd number of red edges. The colored variant is equivalent though simple reductions. Unlike the algorithms for minimum weight $T$-join that ignore parity, the algorithm by Cook et al. takes time exponential in $|T|$. Also, their algorithm depends upon the weights being non-negative, as the reduction to the non-negative case could increase the cardinality of $T$.

Also, there are strongly polynomial time algorithms for finding shortest simple $s,t$-paths with an odd number of edges, and shortest $s,t$-walks with an odd number of edges that do not repeat any edges. Again, these algorithms assume non-negative weights. Both are described by Schrijver. Note that the odd path and walk problems are not special cases of the odd $T$-join problem where $|T| = 2$. A minimum weight odd $T$-join with $T = \{s,t\}$ could contain an even $s,t$-path and an odd cycle as separate components.

So in summary:

  Is there a (strongly) polynomial time algorithm to find a minimum weight odd (or even) $T$-join? Is the problem NP-hard?


texts: Hardness of ancilla free quantum circuit extraction from circuit with ancillas

texts:
Is there any known result regarding the hardness of the following problem:

  Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that implements the same unitary.

I'm assuming that the ancilla qubits are supplied in computational basis states. It might be that the result is different depending on whether the ancilla bits are required to be left clean.
I seem to recall a result stating that the verification of an ancilla qubit being left clean is a hard problem, but I don't know the specifics.

A related problem would be to require the circuits to be reversible classical circuits. I don't think this problem is strictly a subset however, as the unitary without ancillae could take 'shortcuts' using quantum operations not available in classical reversible circuits.


texts: Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

texts:
Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio better than 6/5 would imply $P=NP$.

1) Does this imply that the problem is $APX$-hard as well?

2) Is there a common way of stating this inapproximability fact, besides stating that "it is $NP$-hard to approximate with an approximation ratio strictly better than 6/5"?

Thank you!


texts: Any algorithmic problem has a time complexity dominated by counting?

texts:
What I refer to as counting is the problem that consists in finding
the number of solutions to a function. More precisely, given a
function $f:N\to \{0,1\}$ (not necessarily black-box), approximate
$\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|$.

I am looking for algorithmic problems which involve some sort of
counting and for which the time complexity is greatly influenced by
this underlying counting problem.

Of course, I am looking for problems which are not counting problems themselves. And it would be greatly appreciated if you could provide documentation for these problems.


texts: Is there a language with strong typed interfaces where types resolution are "delayed"?

texts:
I know that this question it not entirely theoretical, but I think that's the place where is more probable that someone knows the answer.

The question is: is there any OO strong typed language where I could "delay" the definition of the method's arguments types?

I'll write an example. Imagine I want to model abelian additive groups, and I program the following interface:

interface AbelianAdditiveGroup
{
    public method add(b final_class) : final_class;
    public method additiveInverse() : final_class;
}

Where final_class is a keyword to tell the compiler to use the implementation class, not the AbelianAdditiveGroup or any other intermediate abstract class.

That's an example of what I'm searching. I think that using fixed interfaces or classes as argument types in these methods is a bad approach in a lot of cases because this causes that we have to do multiple runtime type checks in our code.

If there is no language with this feature... is there any good reason for this?

Thanks in advance :) .


texts: Separation of limited nondeterminism classes?

texts:
It is interesting to find the best lower bound on the  number of nondeterministic bits needed to solve satisfiability problem. Let $\beta_k P$ be the class of problems solvable by a  nondeterministic Turing machine in polynomial time and using $O(\log^k n)$ nondeterministic bits.

$P=\beta_1P$. Notice that $O(\log n)$-clique
 is in $\beta_2P$.
It is an open problem whether $\beta_1 P = \beta_2 P$. It is known that
$\beta_1P \neq \beta_2P$ implies $P \neq NP$

  What is the most serious attempt at separating  $\beta_1P$ from $\beta_2P$?

Does $\beta_kP=NP(\log^k n)$ form an infinite hierarchy?

This reference contains a survey of limited nondeterminism:

A SURVEY OF LIMITED NONDETERMINISM
IN COMPUTATIONAL COMPLEXITY THEORY


texts:
Playing more Flow Free, I think I've realized why I'm so amazingly brilliant at this game:

  The objective is to connect all pairs while covering the entire board, but in every puzzle there is always a unique solution connecting all pairs (even without the board-filling constraint).

So in a mathematical language, we are given $t$ pairs of vertices in an $n\times n$ grid, with the promise that there is only one collection of vertex disjoint paths that connects each pair, and furthermore, this unique collection covers the entire grid.

  What is the complexity of this problem?

Without the promise, the problem becomes NP-hard, here is the related question with many links.
(Note that the reduction in the above paper does not work for our promise version).

Update: I've realized that in the Hexagonal grid version game that I'm playing a unique solution practically (!) implies that the whole board is covered, so it's not really a big difference.


texts:
Given $k$ deterministic FSAs of $n$ states the intersection of their languages is empty is decidable in $n^{o(k)}$ time is an open problem.

For unbounded $k$ it is known the problem is $PSPACE$ complete. What is the scale of $k$ for the problem to be PSPACE complete? Is it $k=\Omega(n)$?

What is the consequence the problem is in $FPT$ having $f(k)poly(n)$ complexity for $f(k)=2^{poly(k)}$?

Is there a result on intersection of deterministic DFSAs which is consistent to $CH$ is $NL$ or $L$ hypothesis (which provides $P=CH\neq PSPACE$)?

How about if the $FSA$s are all non deterministic?


texts: Rank Queries of Uniformly Drawn Order Statistics

texts:
Put a uniform distribution on the integers $\{1,\cdots, M\}$. Draw $N$ samples, and sort them as $x_1 \leq \cdots \leq x_N$. A rank query calculates $rank(j) = \mbox{card} \{ i : x_i \leq x_j \}$ for any $1 \leq j \leq N$.

What is the most space-efficient data structure that can handle rank queries in constant time (or perhaps $O(\log\log N)$ time)?

I think that for $M = N$ it is possible to use an Elias-Fano representation to obtain the structure with $2N + o(N)$ bits of space. Can one exploit the uniform distribution assumption to do better? I am also very interested in the $M > N^2$ case, which is the transition where "birthday collisions" $x_i = x_j, i \neq j$ are no longer expected.


texts:
Given a field $\mathbb{F}$ and a consistent underdetermined system $Ax=b$ over $\mathbb{F},$ $A\in \mathbb{F}^{m \times N}$ and $b \in \mathbb{F}^m,$ finding a vector $z \in \mathbb{F}^N$ such that $Az=b$ and $\|z\|_0 \leq \|x\|_0$ for all $x \in \mathbb{F}^N$ such that $Ax=b$ is NP-hard.

A proof exists in the literature from Simon Foucart for the cases where the base field is $\mathbb{R}$ or $\mathbb{C}.$ Although Foucart didn't prove this exact problem, but something similar, and although Foucart's work was not concerned with finite field case, I believe my interpretation and extension of Foucart's proof establishes NP-Hardness for any field of any characteristic.

What I intend to do here is to merely check this proof for validity; since I am a doctoral candidate writing my dissertation in mathematics and my since my (now retired) advisor is unfamiliar with combinatorial optimization, I figured this board would be the best place to turn for guidance on this problem, as its proof is needed for the backdrop leading to the main analysis of underdetermined systems in my thesis.

To the proof: we reduce from 3-SET-COVER, which asks whether there exists a (nonoverlapping) partition $C_j, j \in J$ within a given collection $\mathbf{C}$ of three-element subsets of some set $S,$ where $S$ has cardinality $|S|=m=3k$ for some natural number $k$ (hence without loss of generality we can refer to $S$ as the set $[m]=\{1, \ldots, m\}$ ).Papadimitriou and Steiglitz have shown that 3-SET-COVER is NP-Complete by reduction from 3-D MATCHING.

Here, $\|x\|_0$ simply means the number of nonzero components in the vector $x.$

For a given set $S$ and collection $\mathbf{C_i}, i \in [N]$ of three-element subsets of $S$ as described above, construct a matrix $A \in \mathbb{F}^{m \times N}$ with columns $a_i$ such that $a_{i,j}=1$ if j $\in C_i$ and $a_{i,j}=0$ if $j \not \in C_i.$ Additionally, let $b=\mathbf{1},$ the vector in $\mathbb{F}^m$ whose components are all equal to $1 \in \mathbb{F}.$ It is obvious this system can be constructed in polynomial time on $m$ and $N.$

Let $z$ be such that $Az=b$ and $\|z\|_0 \leq \|x\|_0$ for all $x$ such that $Ax=b.$ If $\|z\|_0 < \frac{m}{3}$ then $\|Az\|<3\cdot\frac{m}{3}=m=\|b\|_0,$ a contradiction since $\|b\|_0=m.$ Hence $\|z\|_0 \geq \frac{m}{3}.$

Run an algorithm solving for a minimal support solution of $Ax=b$ with output $z.$ There are two cases remaining: first, if $\|z\|_0 = \frac{m}{3},$ then $C_j, j \in supp(z) $ covers $[m]$ exactly. Second, if $\|z\|_0 > \frac{m}{3}$ then the collection $\mathbf{C}$ contains no subcollection covering $[m]$ exactly; if such a subcollection $C_j \subset \mathbb{C}$ existed, the $\frac{m}{3}$ corresponding columns $a_j$ add to $\mathbf{1},$ contradicting the initial assumption for the second part.

This means any algorithm solving the $\ell_0$ minimization problem solves any 3-EXACT COVER problem through a polynomial transformation, and the proof is complete.

=====

Is this proof valid? My main worry is that if $\mathbb{F}$ is a finite field, then the cyclic nature of addition could produce a cover, but the cover could not be exact, since this minimal support solution involves columns of $A$ corresponding to overlapping subsets within $\mathbf{C}$ in this case.

Thanks for any help ahead of time!


texts: Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?

texts:
Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart.

For example, suppose a problem has a practical size* of $n = 100$ and there are two known algorithms: One is $2^n$ and the other is $n^c$ for some constant $c$. Clearly for any $c > 15$, the exponential algorithm is preferred.

*I guess practical size would mean something commonly found in the real world. Like the number of trains on a network.


texts: Efficient transformation of clausal proof into resolution proof

texts:
Clausal proof is used to certify unsat results of SAT solvers. However the main theoretical results are on resolution proof (for instance, the non existence of a polynomial resolution proof for the pigeon hole problem).

How can a clausal proof efficiently (i.e. in polynomial time) be converted to a resolution proof?

Is there any relationship between the size of the clausal proof and the corresponding size of the transformed resolution proof?


texts: In a shortest path between two nodes, find if a certain node is unique

texts: So my exact problem is, I have to find if there is any node which is unique in a shortest path. For example, in a square, any node is in the shortest path between any two adjacent nodes,but it is not unique because even if we delete that we will have another shortest path of exactly the same length.


texts: Lower Bound on the difference between uniform and prefix-free complexity

texts:
The uniform Kolmogorov complexity (also known as decision complexity) of a string $\sigma$ is defined as follows: let $\phi: 2^{<\omega} \times \mathbb{N} \rightarrow {0,1}$ be a partial computable function. A string $\tau$ is called a description of $\sigma$ relative to $\phi$ if $\phi(\tau,i) = \sigma_i$ for $i = 1 \cdots l(\sigma)$, where $l(\sigma)$ denotes the length of $\sigma$. The uniform complexity $Ku(\sigma)$ of $\sigma$ is defined as the length of the shortest description of $\sigma$ relative to a universal machine.

It is clear that $Ku(\sigma) \le K(\sigma) + O(1)$ when $K$ is the prefix-free complexity. But how good is this inequality? More specifically I look for infinitely many strings $\tau_i$ with $Ku(\tau_i) \ge K(\sigma) - O(1)$. I can find such strings if the uniform complexity is replaced by the a priori complexity (sometimes denoted by $KM$), but I can't find these strings for $Ku$ (which would be a stronger statement).

The existence of such strings is equivalent to the existence of strings $\tau_i$ with $\sum_i 2^{-Ku(\tau_i)} \le c$ for some constant $c$.

I think that these string have to be incomparable relative to the prefix ordering (take for example the strings $0^n1$), but I don't know how proof the claim.

Thanks and
aurevoir


texts:
Are there interesting problems that are in $\mathsf{NC}$ but not known to be in $\mathsf{NC^{2}}$? In the paper 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook mentions that MIS was known to only be in $\mathsf{NC^{5}}$ but this has since been brought down to $\mathsf{NC^{2}}$. I am wondering if there are any other problems with polylog-depth parallel algorithms where we seem to be stuck on improving the depth.

To narrow down even further, are there any problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$?


texts: Is there a theory of computation that takes failure and decay of the computation substrate into account?

texts: There are obvious differences between a Turing machine and a real computer. Not only is the latter finite in size, it is also prone to failures and it is made from decaying matter. The kind of framework I have in mind is this (but please excuse the handwavy vagueness): In some sense, (quasi)particles that constitute matter can be thought to perform computation: They have state that persists at least for some time (properties such as position, spin, charge, momentum) and they can change their state in feedback loops by interacting with other particles. The more elementary particles locally affect each other, the more complex the state and feedback loops can be. What kinds of computation we can perform on such a substrate depends on the configurations and rules that govern the particles, in particular, how many feedback loops they allow to simultaneously affect a local arrangement of particles. In this sense I'm looking for a framework that is analogous to the Chomsky hierarchy, i.e. in which the complexity of the system is successively extended to eventually build up to a notion of general computation. Is there something similar to this in the literature?


texts: General definitions for mixed graphs? (degrees, connectivity, etc)

texts:
I'm writing a framework for some graph theorical tasks and am unsure about some definitions regarding mixed graphs. Degrees and connectivity in particular.

  A mixed graph G is a graph in which
  some edges may be directed and some
  may be undirected.

I couldn't find any comprehensive definitions for mixed graphs on the web and am kind of stuck here as I don't want to unintentionally contradict general graph theoretical principles by just following my gut feelings of what feels right for me.

One of those uncertainties being:
How is in-degree (and out-degree respectively) defined in mixed graphs?

Is it this?:

inDegree():
    directedEdgeCount = count(incoming directed incident edges)
    #undirected edges being ignored
    return directedEdgeCount

…or is it this?:

inDegree():
    directedEdgeCount = count(incoming directed incident edges)
    undirectedEdgeCount = count(undirected incident edges)
    return directedEdgeCount + undirectedEdgeCount

I found some general graph definitions saying that:

degree():
    return inDegree() + outDegree()

Which makes perfect sense for strictly directed/undirected graphs if first version of inDegree() was to be used. It would count undirected edges twice though, if second version of inDegree() was to be used.
My gut says that undirected edges lacking any direction basically allow flow in both directions and thus should be included in inDegree()/outDegree(), shouldn't they?

And coming from the above I have to ask:

If this is correct:

isDirectNeighborOf(other):
    return (self has any edge connecting it to/from/between other)

…which it is, from my understanding.

Then which one of these is correct? Is it this?:

isDirectPredecessorOf(other):
    #ignoring undirected edges
    return (self has outgoing directed edge to other)

…or this?:

isDirectPredecessorOf(other):
    return (self has outgoing directed or undirected edge to other)

Concrete example:

What is the in-degree of B? (my gut says 3)
What is the out-degree of C? (my gut says 3)
What is the in-degree of D? (my gut says 2)
What is the out-degree of D? (my gut says 2)
Is D direct predecessor of B? (my gut says YES)
Is D direct successor of B? (my gut says YES)

Does anybody here happen to have a comprehensive set
of definitions regarding mixed graphs?

As with many graph types the theoretical sonstruct mixed graph is ambiguously used.
Hence I'm not so much searching for a universally accepted definition, but rather looking for any at all.


texts:
Does Shor's algorithm produce factors of a $n$-bit number and discrete log modulo $n$-bit prime in $O((\log n)^{2+\epsilon})$ bit operations using fast multiplication? I am trying to read from wikipedia. If not what is the 'right' number of comparable 'bit' operations in the classical model?

What is the hidden constant in $O((\log n)^{2+\epsilon})$?

As far as we know the $2$ in the exponent could be brought down to $1$. There have been many techniques in classical factoring/discrete log calculation that tried to reduce complexity over many decades. Has there been any attempt to bring the exponent from $2$ down to $1$? Or is there a proof that $2$ is the best that can be done?


texts: 2DFA that requires many states in equivalent DFA?

texts:
Is there a 2DFA with $n$ states (where $n$ is nontrivial, say at least 4) that requires at least $2^n$ states to simulate using any DFA?

A two-way DFA (2DFA) is a deterministic finite-state automaton that is allowed to move back and forth on its read-only input tape, unlike finite-state automata that may only move the input head in one direction.

It is well-known that 2DFAs recognize precisely the same class of languages as DFAs, in other words the regular languages.  Less well-understood is the question of how efficient the simulation is.  The original constructions from the late 1950s by Rabin/Scott and Shepherdson used a notion of crossing sequences and are quite hard to analyse.  Moshe Vardi published another construction that shows an upper bound of $2^{O(n^2)}$ states, but this bound may have some slack.

I am asking whether any (families of) 2DFAs are known that require many states in any DFA simulating them, even after Myhill-Nerode minimization of the DFA.  Moreover, would there be any interesting consequences of knowing such 2DFAs?

Moshe Y. Vardi, A Note on the Reduction of Two-Way Automata to One-Way Automata, IPL 30 261–264, 1989.  doi:10.1016/0020-0190(89)90205-6 (preprint)


texts: Is there any programming language in which any equivalent program has a unique, decidable normal representation?

texts:
Is there any programming language in which any equivalent program has a unique normal representation, and that normal representation is decidable?

Is other words, suppose A and B are programs written on that hypothetic language. Suppose, too, that for any input x, A(x) = B(x) - that is, those programs are equivalent. There should, then, be an algorithm Z for which Z(A) = Z(B).

Finally, that language should be able to encode boolean logic.

Is there such a language?


texts: Using Dependent Type Theory for Categories that are not LCCC

texts:
I have recently been working with polynomial functors and monads based mostly on Gambino-Kock. There they define polynomial functors in a Locally Cartesian Closed Category (LCCC) and extensively use dependent type theory to define constructions on polynomials because working in the internal language is much easier than the diagrammtic language.

However, I am interested in polynomial monads for their application to defining flavors of multi-category and for that I need to use polynomals in Cat and similar categories, which have pullbacks, but are not locally closed. There you instead require in the polynomial diagrams

$$I \leftarrow E \to B \to J$$

that the middle arrow $E \to B$ is exponentiable, since that is the only $\Pi$ you use. The only paper I know of that does this is this which doesn't use the internal language at all and is much more difficult for me at least because of it.

Is there some kind of restriction I can put on dependent type theory so that I can use it as an internal language for a category with pullbacks rather than an LCCC? Specifically I want to be able to manipulate exponentiable morphisms as dependent types that I can take $\Pi$ of, but not every dependent type should be exponentiable. Then hopefully the usual proofs using dependent type theory would still be valid, because every use of $\Pi$ would be modeled by an exponentiable morphism.

My own idea would be to have dependent types interpreted as exponentiable morphisms and other terms interpreted as arbitrary morphisms, but since you can define from any $x : A \vdash t : B$ (where $\cdot \vdash B$) the dependent type:
$$b : B \vdash \sum_{x:A} t = b$$
it seems like the type theory would make every morphism exponentiable.


texts:
Matrix $A$ has dimension $n \times n(n-1)$. We want to fill $A$ using integers between $1$ and $n$, inclusive.

Requirements:

Each column of $A$ is a permutation of $1, \dots, n$.
Any submatrix formed by two rows of $A$ cannot have identical columns.

Question:

Is it possible to fill the matrix satisfying the requirements?

Relation to cryptography:

Each row number corresponds to a plaintext. Each column corresponds to a key. Since a key defines an injection, each column must be a permutation. The second requirement is for perfect secrecy for two messages.


texts: Maximum Polyhedron Volume in Given $n$ Points

texts:
Suppose we are given $n$ points $v_1,v_2,\cdots, v_n\in \mathbb{R}^k$, I want to find $k+1$ points $v_{i_1}, v_{i_2},\cdots,v_{i_{k+1}}$ such that the volume of the convex body spanned by them maximized (where any $k$ vectors in $v_{i_j}$s should be linear independent, otherwise the volume can simply be $0$).

I know the Minimizing version of this problem can be shown to be NP-Hard, e.g. one can reduce the subset sum problem to it as follows:

For given $n$ distinct reals $a_1,a_2,\cdots, a_{n-1}$, we want to know if there are $k$ numbers in $a_i$s that sum to $\beta$
Define $v_i=[1,a_i,a_i^2,\cdots,a_i^{k-1}]$ and $v_n=[0,\cdots,0,1,\beta]$, one can show (by Vandermonde matrix) that the problem in $1$ is true iff there are $k$ vectors in $v_i$s are linear dependent

  My question is: does the Maximizing version of this problem also NP-Hard? or Can one find a polynomial algorithm for it?

I was trying to find a similar reduction as above, but there seems to be a lot difficulty.

Edit: Actually, this paper provided a rather simple reduction from X3C as follows:

let $Q=\{q_1,q_2,\cdots, q_m\}$ and $C=\{c_1,c_2,\cdots, c_n\}$ be an instance of X3C, we want to find $C'\subset C$ such that $c_1'\cap c_2' =\phi$ for all $c_1'\not=c_2'\in C'$ and $\bigcup_{c'\in C'}c'=Q$.
for each $q_i$, define $v_i[j]=1/\sqrt{3}$ if $q_i\in c_j$ and $v_i[j]=0$ otherwise.

clearly, the instance in 1 is true iff the maximal volume is 1. (though this approach only gives a hardness result with constant approximate ratio)


texts: Why are linear bounded automata not as popular as other automata?

texts: In my experience, context-sensitive languages and linear bounded automata are frequently skipped or breezed over in computability theory courses, and are even left out of some notable text books, although finite and pushdown automata receive a lot of attention. Surely there must be a good reason for why LBAs are given less focus than their counterparts?


texts: Defining binary natural numbers without quotient types

texts:
Let's say we work in a dependent type theory with W-types and we want to have a type for binary natural numbers. We don't want to add quotient types or higher inductive types to the system.
How to represent the idea that leading zeroes don't change the natural number? Do we necessarily enter setoid territory at this point?


texts: What's the complexity of Spearman's rank correlation coefficient computation?

texts:
I've been studyin' the Spearman's rank correlation coefficient.
If computed for two list that have both size $N$, what's the complexity of the algorithm?

$O(N)$ ?

Thanks in advance.


texts: Zero knowledge proof for value of a hash function

texts:
Is there a zero knowledge proof which demonstrates that Peggy knows a value v whose hash-function is w?

In my understanding of the general theorems on zero-k there EXISTS such a function if the has-function has polynomial time complexity. However, I would like to know how such the protocol would look like for the case of SHA-256. My problem is, that the usual proof requires me to reduce the fact of having a certain SHA-256 to Graph 3 Coloring, for example, and I do not see how this could be done practically.


texts: Scaling procedures to address false 0's after multiplying probabilities

texts:
I need to translate a training algorithm that involves sums and multiplications of probabilities to actual code. For that I need some sort of scaling procedure that allows me to avoid underflows, that is, misleading 0 probabilities.

A typical method is to apply the logs of probabilities but because of the sums this is not readily possible for my case. Another approach I saw in Rabiner's tutorial on HMMs, was his scaling procedure only dependent on t (time) applied to the forward algorithm and (the other way around) the backward algorithm, that when combined cancel each other to obtain the desired trained probabilities.

My question
I wonder if there are books or text resources explaining common approaches to tackle the underflow problem that results in working with continuous multiplications of probabilities. Do you know any?

I hope I can get some ideas from that.


texts:
It is known that it is NP-hard to distinguish whether a set system has discrepancy $0$ or $O(\sqrt{n})$, given that the set system has $n$ elements and $m=O(n)$ sets.

In general if it is so hopeless to estimate or upper-bound discrepancy , then why do we care about algorithms that give colorings of $O(\mathrm{herdisc}(C)(\log m\log n)^{1/2})$ discrepancy ? I am interested in applications of discrepancy in approximation algorithms.


texts: Topology/Space of Recursive Algebraic Datatypes

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

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