texts: Applying Expectation Propagation to Factor Graph

texts:
Expectation Propagation(EP) is now quite a standard technique to approximate marginal in graphical model. Moreover, EP can replace sum-product algorithm in factor graph. For this reason, I try to understand it by using very simple model but because of my limitation of knowledge, the result could not be reached. So would you please revise my progress to show me my errors?

My problem is simple. $x_1$ is the variable which is followed Gaussian distribution with the mean $\alpha$ and variance $\beta$. $x_2$ is the variable which satisfies $x_1 = x_2$. So the factor graph can be represented by

Gaussian ---$x_1$ ---- $f(x_1, x_2) $--- $x_2$

f is the factor function in factor graph and it is Dirac delta function.

$f(x_1, x_2) = \delta(x_1 - x_2)$

Based on the properties of factor graph, we have:

$p(x_1, x_2) = g(x_1) f(x_1, x_2)$

with $g(x_1)$ is the Gaussian distribution. When we take the integral over the variable $x_1$ of $p(x_1, x_2)$, we get that the marginal of $x_2$ is the Gaussian distribution with the same parameters with $x_1$.

However, I want to use EP technique to solve this problem. First of all, I will separate $f$ here like in Tom Minka's thesis

Gaussian ----- $x_1$ ------ $\tilde{f}_1(x_1)$  $\tilde{f}_2(x_2)$ ----- $x_2$

Now, I want to find the function $q(x)$ that is

$q(x_1, x_2) = g(x_1) \tilde{f}_1(x_1) \tilde{f}_2(x_2)$

$q$ is the approximate function of $p(x_1, x_2)$

I want to refine the function $\tilde{f}(x_1, x_2) = \tilde{f}_1(x_1)\tilde{f}_2(x_2)$, environment without $f$ is calculated

$q^{\f}(x_1, x_2) = g(x_1)$

so

$\hat{p}(x_1, x_2) = q^{\f}(x_1, x_2) f(x_1, x_2) = g(x_1) f(x_1, x_2)$

$\hat{p}(x_1) = g(x_1) \int_{x_2} f(x_1, x_2) dx_2$

$\hat{p}(x_2) = \int_{x_1} f(x_1, x_2) dx_1$

$q^{new} (x_1, x_2) = \hat{p}(x_1) \hat{p}(x_2)$

then

$\tilde{f}(x_1, x_2) = \frac{q^{new}(x_1, x_2)}{q^{\f}} = \int_{x_1} f(x_1, x_2) dx_1 \int_{x_2} f(x_1, x_2) dx_2$

so

$\tilde{f}_1(x_1) = \int_{x_2} f(x_1, x_2) dx_2$

$\tilde{f}_2(x_2) = \int_{x_1} f(x_1, x_2) dx_1$

Then I guess $\tilde{f}_1$ and $\tilde{f}_2$ are convergence, so

$q(x_1, x_2) = g(x_1) \int_{x_1} f(x_1, x_2) dx_1 \int_{x_2} f(x_1, x_2) dx_2$

Hence, I get stuck at this point. Would you please show me, what wrong did I do?

Thank you and looking forward to seeing your helps


texts:
Does anyone know of any good surveys on Erdős-Pósa?
I am particularly interested in what are the latest results for the bounding function for directed and even cycles in planar and minor free graphs down to the constant factor.


texts: $l$-diversity and risk of re-identification

texts:
Assuming I have an $l$-diverse ( table T and an individual $i$ providing more than one sensitive attribute to an equivalence class I'm wondering what the worst-case re-identification risk by guessing is.
My assumption is $\frac{2}{l}$ because the individual $i$ contributes two different sensitive attributes and we have at least $l$ diverse sensitive attributes.
After some discussing with fellow students I'm a bit confused if I'm right.


texts: An invariance theorem for algorithmically random data in statistical learning

texts:
Motivation:
The following invariance theorem for statistical learning in the setting of algorithmically random data occurred to me yesterday. This theorem uses the fact that the property of algorithmic randomness is transformation-invariant. I was motivated to find such a theorem for a couple reasons.
Such a theorem may be used to perform empirical tests using machine learning to determine whether a dataset was sampled from an algorithmically random process as well as to test extraordinary claims that a machine learning model can efficiently simulate algorithmically random processes.
Might this theorem be known by a particular name?
The learning problem:
Let's suppose $F_{\theta}$ is a function space that is useful for statistical learning(ex. Deep Neural Networks) such that $D_N = (X_N,Y_N)$ is a dataset where $X_N=\{X_i\}_{i=1}^{2N}$, the $X_i$ are sampled i.i.d. from a discrete random variable $X$, and $Y_N=\{Y_i\}_{i=1}^{2N} \in \{0,1\}^{2N}$ are the class labels.
If $D_N$ is split into balanced training and test sets $D_N^\text{train}$ and $D_N^\text{test}$ then we have $D_N^\text{train}=(X_N^\text{train},Y_N^\text{train})$ and $D_N^\text{test}=(X_N^\text{test},X_N^\text{test})$ such that $\lvert X_N^\text{train} \rvert = \lvert X_N^\text{test} \rvert = N$ and $X_N^\text{train} \cup X_N^\text{test} = X_N$.
Furthermore, we shall assume that the training and test sets are balanced so we have:
\begin{equation}
\frac{1}{N} \sum_i Y_i^\text{train} = \frac{1}{N} \sum_i Y_i^\text{test} = \frac{1}{2} \tag{1}
\end{equation}
Defining algorithmic randomness:
Now, $X$ is algorithmically random relative to $F_{\theta}$ if $X$ is incompressible relative to $F_{\theta}$ in the sense that for any choice of train-test split we have:
\begin{equation}
\mathbb{E}[K(X |F_{\theta})] = \min_{f \in F_{\theta}} \mathbb{E}[K(X |f)] \sim N \cdot \ln \lvert X \rvert \tag{2}
\end{equation}
where I used the fact that the expected Kolmogorov Complexity equals the Shannon entropy, and applied the Shannon source-coding theorem to i.i.d. data.
The conjecture:
In consequence, (1) implies that for a particular sample $X_N \sim X$ it may be possible to find $f \in F_{\theta}$ such that $\forall i \in [1,2N], f(X_i) = Y_i$ on the condition that the Kolmogorov Complexity:
\begin{equation}
K(f) \sim 2N  \tag{3}
\end{equation}
as this would amount to memorisation and not discovering regularities in $D_N$ since $X$ is algorithmically random relative to $F_{\theta}$. To be precise, if an arbitrary mathematical  transformation $T$(ex. random matrix) is applied to $D_N$ so:
\begin{equation}
X'_N = T \circ X_N \tag{4}
\end{equation}
given that $f(X_i)=Y_i \implies \delta_{f(X_i),Y_i} = 1$, the solution to the empirical risk minimisation problem may be formulated as follows:
\begin{equation}
\hat{f} = \max_{f \in F_{\theta}} \frac{1}{N} \sum_{i=1}^N \delta_{f(X'_i),Y_i} \tag{5}
\end{equation}
and for large $N$, the expected performance on the test set is approximated by:
\begin{equation}
\lim_{N \to \infty} \frac{1}{N} \sum_{i=N+1}^{2N} \delta_{\hat{f}(X'_i),Y_i} = \frac{1}{2} \tag{6}
\end{equation}
Note: I am implicitly interested in natural signals which exhibit algorithmic randomness, and the transformations $T$ are arbitrary to the extent that they don't change the phase-space dimension of the processes responsible for generating natural signals.
References:

Peter Grünwald and Paul Vitányi. Shannon Information and Kolmogorov Complexity. 2010.
Jerome H. Friedman, Robert Tibshirani, and Trevor Hastie. The Elements of Statistical Learning. Springer. 2001.


texts: How to map random cardesian points in a 2d array

texts:
I was wondering if there is any algorithm, theoretical or already implemented, or if its even possible at all, where, given N random points (x,y) we can relatively map them in a 2d array where each mapped point in the 2d-array has the property that its neighboring points (at most 8 points around it) are the closest to that point.

I would also like to add an extra restriction that no node in the 2d array is NULL meaning that if we have for example N = 1 Million elements then the 2d array would be sqrt(N) x sqrt(N) or 1000 x 1000 dimension, where each element of that array occupies a point.

In addition, we can also consider sorting, if it can help, as of x-coordinate and as of y-coordinate...

Thanks in advance!


texts:
Book and Greibach (V. Book, Ronald & A. Greibach, Sheila. (1970). Quasi-realtime languages. Theory of Computing Systems. 4. 97-111. 10.1007/BF01705890.) prove that non-deterministic linear time Turing machines are equivalent to quasi-real-time such machines.

The authors say: " For deterministic machines, linear time is strictly more powerful than real-time; here we show that for nondeterministic machines linear time and real-time have the same power. "
However, they do not cite or prove the claim that linear time deterministic machines are more expressive than realtime deterministic such machines.


texts: Non constructible functions and anomalous results

texts: In the Arora-Barak book, in the definition of time constructible functions, it is said that using functions that are not time constructible can lead to "anomalous results". Does anyone have an example of such an "anomalous result"? I have heard in particular that there might exist functions such that the time hierarchy theorem does not hold, does anyone have an example of such functions? Is there something about this somewhere in the litterature?


texts: PTAS (polynomial time approximatin scheme) for euclidean TSP/Minimum-Cost k-Connected subgraph problem

texts:
Problem 1
I have read "On Approximation of the Minimum-Cost k-Connected Spanning Subgraph Problem" (by A. Czumaj, A. Lingas), and even in the abstract are 2 statements "We present a polynomial time approximation scheme for Minimum-Cost k-Connected subgraph problem" and in the second paragraph of the abstract they state that there is no PTAS unless P=NP. I am sure there is a small difference between the tow problems, but I cannot see what it is. Could someone clarify for me what problem does not have a PTAS and how its different from the problem in the first paragraph of the abstract?
Problem 2
Because I didn't really get the paper from the first problem, I read "Polynomial Time Approximation Scheme from Euclidean TSP and other Geometric Problems" (by S. Arora), and I have the same problem here, he claims to give a PATS for euclidean TSP, but in the intro states "[...] showed that if P≠NP then metric TSP and many other problems do not have a PTAS". I see there some kind of contradiction, they are giving a PTAS, but say that some showed that there cannot be any. What am I missing?


texts: Bellman-Ford with Non-edge-decomposable Path Weights

texts:
Consider a directed graph $G(V,E)$ with non-negative edge weights. Also, let us define the weight of a path as non-edge-decomposable, that is, the weight of a path cannot be written as the sum of a function of the weights of its edges. Can we still use Bellman-Ford to converge to the shortest (i.e., minimum weight) path from some source $S$ to some sink $T$ after some number of iterations? Would Bellman-Ford converge eventually?

Follow up question:

The particular path weight function I am interested in uses a set operation where each edge is associated with a set of items. Each item has a weight. The weight of a path is then the sum of weights of items associated with the edges on the path. For example, in the following figure, we have items of $I_1$, $I_2$, and $I_3$ with weights $w_1$, $w_2$, and $w_3$, respectively. The weight of paths $P_1$ and $P_2$ is computed as $w_1+w_2$ and $w_1+w_2+w_3$, respectively.

$w_{P_1}$ = $\sum_{\gamma \in \{~\{I_1, I_2\}~\cup~\{I_2, I_3\}~\cup~\{I_2\}~\}} w_\gamma$

$w_{P_2}$ = $\sum_{\gamma \in \{~\{I_1, I_2\}~\cup~\{I_2\}~\}} w_\gamma$


texts: How can I find the PhD thesis of C.A. Ellis?

texts:
I've searched for this article all over the web but couldn't find it. can anyone help me?
Ellis, C.A. 1969. Probabilistic languages and automata. Rept. no. 355. Dept. Comp.
Sc. University of Illinois, Urbana, Ill.
PhD Thesis


texts: Kolmogorov's conjecture that $P$ has linear-size circuits

texts: In his book, Boolean Function Complexity, Stasys Jukna mentions (page 564) that Kolmogorov believed that every language in P has circuits of linear size. No reference is mentioned and I couldn't find anything online. Does anyone know more about this?


texts: Analytic solutions in semidefinite programming (SDP)

texts: From my experience in the application of semidefinite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example, there are SDPs whose solution is the fidelity of two operators or the trace norm of an operator. Does anyone know of more examples? Or more importantly, is there a general theory behind this notion of analytic solutions?


texts: How to justify this causally consistent execution in the $(vis, ar)$ framework for distributed consistency models?

texts:
In Figure 5.1 of the book "Principles of Eventual Consistency" by Sebastin Burckhardt, 2014, Causal Consistency (CC); wiki is (mainly) defined as the conjunction of $hb \subseteq vis$ and $hb \subseteq ar$, where $hb \triangleq (so \cup vis)^{+}$.

An execution satisfies CC if it can be extended by adding $vis$ and $ar$ to an abstract execution which justifies the conditions above; see Definition 3.5.

See also the POPL'2014 paper and the CSUR'2016 paper.

Now, consider the execution in the figure below, where $w(x)0$ denotes a write of 0 to $x$ and $r(x)0$ a read of 0 from $x$.

On the one hand, this execution satisfies CC according to the definition in wiki, because $r(x)1$ can be justified by the serial view of $w(x)0\; w(x)1\; r(x)1$ and $r(x)0$ by $w(x)1\; w(x)0\; r(x)0$.

On the other hand, however, (in my opinion,) it does not satisfy CC according to the $(vis, ar)$ definition for CC above. It is impossible to define the total order $ar$ which must put $w(x)0$ before $w(x)1$ (for justifying $r(x)1$) and put $w(x)1$ before $w(x)0$ (for justifying $r(x)0$).

My questions:

What is wrong with my argument?
How to justify this causally consistent execution in the $(vis, ar)$ framework?


texts:
If you have FPRASes for counting number of matchings of size $\leq n$ and size $\leq n-1$,
can you get an FPRAS for counting number of matchings of size $n$ (i.e perfect matchings)?


texts: Can a term on normal form prove an illogical assertion?

texts: Suppose we take a language such as Agda and disable the features that make it consistent; for example, universe polymorphism, structural recursion checks and similar. Suppose then that we take a term in normal form, i.e., with no redex left. Could that term prove an absurd claim such as, for example, 1 = 2, despite the fact it is normalised (and, thus, doesn't include infinite loops)?


texts: What is the best fitness function for detecting natural language?

texts:
First, let me apologise, as this question is far from my area of expertise, but is related to a side interest (read hobby), and so this question might be very naive. This may even be off-topic for the site, and if so I apologise.

You are given a set of $S$ strings $\{s_i\}$, each of length $n$. One of the strings (denoted $s_x$) is something a human would recognise as meaningful text in a specified language (we can assume English if that helps). Further, we can assume that all other strings $s_{i \neq x}$ have Hamming distance at least $c n$ from the nearest meaningful natural language string, for some finite constant $c$. (I'm not going to try to specify what 'meaningful' means here mathematically, and so please take it that I mean roughly something that a human would take to be a reasonable piece of natural language text. Indeed, a good definition for this might itself be the answer.)

My question then is fairly simple: Is there an efficiently computable function $F(s)$ such that $F(s_x) > F(s_i)$ for all $i \neq x$, with high probability, for sufficiently large $n$? In the case I care about $S$ is extremely large, but constant. Additionally, I care about the case where $s_i$ all have similar Kolmogorov complexity.

To me, at least, the natural candidates seem to be based on N-grams, either by computing some scalar function of N-gram frequency and computing the distance from the value for the target language (determined from a large collection of text in that language), or by computing the distance between vector formed by taking the N-gram frequences in order with that of the target language. However, a little experimentation has shown this intuition to be false, since there are many random looking strings with substantially better N-gram statistics than $s_x$.

Another approach which fails is to try to count the proportion of the string which is occupied with words in whatever language we are considering. However this fails badly because you can strings like "iiiiiiiaaaaiaiaaaaaaiiiiinoiaaaonionnoaiii" which are clearly not natural language, but which can be interpretted as a string of English language words. Potentially we could try imposing grammatical structures, but this seems like a bad (and inefficient) road to be going down. So I am wondering if there is a better approach? Is there any $F$ satisfying the above requirement which can be computed reasonably efficiently?


texts: Why may the right hand sides in Chomsky Hierachy type 1 be larger?

texts:
I'm shaking my head because of this question, my Prof. didn't explain it. We have linear space limited automata and they have to satisfy for rules a -> b that |a| <= |b|.

Why?

I would have said, that it's stupid to allow being larger, because we are space limited and still have to produce all words of a language.

Thank you in advance, an answer would mean a lot to me.


texts: Properties of Random Directed Graphs with Fixed Out-Degree

texts:
I am interested in properties of random directed graphs with fixed out-degree $d$.  I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r.

  Question: Is anything known about the stationary
  distribution and mixing times of random
  walks on these random graphs (for various
  values of $d$)?

I am particularly interested in the case where $d = 2$, which corresponds to a model of random automata over a Boolean alphabet.  (Yes, I realize these graphs are often not connected, but what happens in a given component?)  I am happy with partial results and results about other properties of these graphs.

It seems most of the literature on random graphs focuses on the Erdős–Rényi model, which has very different properties than the model I am thinking about.


texts: Has anyone used Pottier and Gauthier's polymorphic defunctionalization in a modular compiler?

texts:
Defunctionalization is a program transformation that converts higher-order programs into first-order programs. The idea is that given a program, there are only finitely many lambda-abstractions, so you can replace each lambda with an id, and each function application with a call to an apply procedure which branches on that id.  This is sometimes used in compilers for functional languages, but its applicability is limited by the fact that defunctionalization is a whole-program transformation (you must statically know all of the functions in the program), and so only whole-program compilers make use of it.

However, Pottier and Gauthier have a given a polymorphic typed defunctionalization algorithm using a more sophisticated typing involving GADTs. Now, given their encoding, it's possible to add a catch-all case to their lambda datatype that isn't a tag, but which contains a higher-order function. This means that it should be possible to use their encoding to defunctionalize on a module-by-module basis.

Has anyone done this, and point me to a compiler using this idea? (Toy compilers are okay, and in fact preferred.)


texts:
As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far:

Quantum computers are not known to solve NP-complete problems in polynomial time.
"Quantum magic won't be enough" (Bennett et al. 1997): if you throw away the problem structure, and just consider the space of $2^n$ possible solutions, then even a quantum computer needs about $\sqrt{2^n}$ steps to find the correct one (using Grover's algorithm)
If a quantum polynomial time algorithm for a NP-complete problem is ever found, it must exploit the problem structure in some way (otherwise bullett 2 would be contradicted).

I've some (basic) questions that no one seems to have asked so far on this site (maybe because they are basic). Suppose someone finds a bounded error quantum polynomial time algorithm for $SAT$ (or any other NP-complete problem), thus placing $SAT$ in $BQP$, and implying $NP \subseteq BQP$.

  Questions

  Which would be the theoretical consequences of such a discovery? How would the overall picture of complexity classes be affected? Which classes would become equal to which others?
  A result like that would seem to suggest that quantum computers had an inherently superior power than classical computers. Which would be the consequences of a result like that on physics? Would it emanate some light on any open problem in physics? Would physics be changed after a similar result? Would the law of physics as we know them be affected?
  The possibility (or not) to exploit the problem structure in a general enough (i.e. specific-instance independent) manner seems to be the very core of the P = NP question. Now if a bounded error polynomial time quantum algorithm for $SAT$ is found, and it must exploit the problem structure, wouldn't its structure-exploitation-strategy  be usable also in the classical scenario? Is there any evidence indicating that such a structure-exploitation may be possible for quantum computers, while remaining impossible for classical ones?


texts:
There is a well known fact that we can use the existence of external regret minimization algorithms to prove the minimax theorem of two-player zero-sum games.

The proof can be found in the survey Learning, Regret minimization, and Equilibria A. Blum and Y. Mansour.

Immediately arises question whether can we use external regret minimization to find mixed Nash equilibrium in finite non-zero two-player game, in other words does zero external regret leads to find mixed Nash equilibrium, in per round sense.

Intuitively it doesn't seem so, I am not sure that we can get external regret equals zero in general case, but there are polynomial time algorithm for good approximation (see the above paper), on the other hand approximation of Nash equilibrium seems like more difficult task.

I would appreciate if someone could help to answer the question.


texts: Boyd & Vandenberghe, question 2.31(d). Stuck on simple problem regarding interior of a dual cone

texts:
In Boyd & Vandenberghe's "Convex Optimization", question 2.31(d) asks to prove that the interior of the dual cone $K^*$ is equal to

(1)  $\text{int } K^* = \{ z \mid z^\top x > 0 $ for all $ x \in K \}.$

Recall that the dual cone of a cone K is the set:

$K^* = \{ y \mid y^\top \ge 0 $ for all $ x \in K \}.$

I've spent a solid chunk of time trying to prove this simple and seemingly evident statement about the interior of the dual cone but keep getting stuck on the problem of bounding the inner product of x with a perturbed version of z (details provided below).  Frustratingly, the proof in the book's answer key (available online) takes as given this very fact that that I am stuck on proving.

My work in proving statement (1) is given below.  I hope someone can show me the piece of mathematical technology I'm missing.  Thanks!

Question 2.31(d):

Let $K$ be a convex cone and $K^* = \{ y \mid y^\top x \ge 0 $ for all $ x \in K \}$ be its dual cone.

Let $S = \{ z \mid z^\top x > 0 $ for all $ x \in K \}.$   Show that $S = \text{int } K^*.$

Certainly $S \subseteq K^*.$  Now consider some arbitrary point $z_0 \in S$.  For all $x \in K$ we have $z_0^\top x > 0$.  It's clear that we need to find an $\epsilon$ such that for all $z' \in D(z_0, \epsilon)$,

$~~~~ z'^\top x > 0 $ for all $ x \in K.$

Unfortunately, I don't know how to show $z'^\top x > 0$ for $z' \in D(z_0, \epsilon)$ when $\epsilon$ is chosen sufficiently small.

I do know we can write $z'$ as $z_0 + \gamma u$ where $\|u\| = 1$ and $\gamma \in (0,\epsilon)$.  And I do know that

$~~~~ z_0^\top x - \gamma \|x\| ~\le~ z_0^\top x + \gamma u^\top x ~\le~ z_0^\top x + \gamma \|x\|$.

where $z_0^\top x > 0$ and $\gamma \|x\| \ge 0.$

However, I don't know how to show the critical piece, that

$~~~~ z_0^\top x - \gamma \|x\| > 0$

when $\epsilon$ is chosen sufficiently small since $x$ can range over $K$ and therefore $\|x\|$ can be arbitrarily large.

Frustratingly, the solution in B&V just takes it for granted that for sufficiently small $\epsilon$,

$~~~~ z_0^\top x + \gamma u^\top x > 0$.

I've looked online for some matrix perturbation theory results to apply but nothing I've found has been useful.

Any help is greatly appreciated,

Ted


texts: Denotational semantics of System $F_\omega$ with recursive types and general recursion

texts:
Is there a denotational semantics for System $F_\omega$ in literature that supports both recursive types and general recursion?

I'm looking for a model of Ralf Hinze's variant of System $F_\omega$ [4]. It has a term-level fixed point combinator
$$\mathit{fix} : \forall X:*.~(X\rightarrow X)\rightarrow X$$
and type-level fixed point combinators
$$\mu_\kappa : (\kappa\rightarrow\kappa)\rightarrow\kappa.$$
Neither the ideal model the the interval model seems to fit.

In the ideal model [1], the convertibility rule
$$\mu_\kappa T\leftrightarrow T(\mu_\kappa T)$$
is not sound, because not all ideal functions have fixed points.

In the interval model [2], it is not clear how to make the term-abstraction and term-application rules sound. Martini's interval model for $F$ [3] restricts types to maximal intervals, but such a restriction would leave the inhabited type
$$\mu_*(\lambda X.~X)\rightarrow\mu_*(\lambda X.~X)$$
without any meaning.

[1] MacQueen, Plotkin, Sethi. An ideal model for recursive polymorphic types.
[2] Cartwright. Types as intervals.
[3] Martini. An interval model for second order lambda calculus.
[4] Hinze. Polytypic values possess polykinded types.


texts: Almost regular subhypergraph of hypergraph with large minimal degree

texts:
I am interested in knowing whether the following conjecture is true or not:

For every $d \geq 1$ there exist constants $\delta,M_0 > 0$ such that the following holds for all $M \geq M_0$.
Let $\mathcal{S}$ be a finite family of sets of size at least $M$ in which each element appear at most $d$ times.
There exists a set $X$ such that $\delta M \leq |S \cap X| \leq M$ for all $S \in \mathcal{S}$.

We can also formulate this in terms of hypergraphs:

For every $d \geq 1$ there exist constants $\delta,M_0 > 0$ such that the following holds for all $M \geq M_0$.
Let $H$ be a $d$-uniform hypergraph in which each vertex has degree at least $M$. There is a subhypergraph $H'$ of $H$, obtained by only deleting hyperedges, in which the degree of each vertex is between $\delta M$ and $M$.

(If we want to make the statements completely equivalent, we should ask all hyperedges to have uniformity at most $d$ rather than exactly $d$.)
The question has the flavor of Hall's matching theorem and of Beck-Fiala, but so far I was unable to prove the conjecture using these tools. Perhaps I am missing some simple argument, or perhaps there is a simple counterexample.


texts: Proof refutation: Amateur reviews of ambitious CoRR papers

texts:
I guess that I read too many ambitious CoRR papers. The problem is that those papers are not peer reviewed, but often sound interesting and pass basic plausibility checks. Or maybe they don't, and I just need to improve my plausibility checks. Here is a recent sample of such papers:

Uniqueness Trees: A Possible Polynomial Approach to the Graph Isomorphism Problem
On the Group and Color Isomorphism Problems
Multiplicative weights, equalizers, and P=PPAD
NP vs PSPACE

After detailed reading, I often end up with the conclusion that the approach is interesting and might have some merit, but that it is insufficient to reach to huge ambitious goal announced or hinted at in the abstract. I sometimes write the authors of such papers my thoughts, but the typical reaction is to totally ignore my email such that I don't even know whether a spam filter eliminated it before reaching the author, the best reaction is an "thanks for your kind words, I'm used to much more insulting feedback". Being totally ignored feels bad, but maybe it is an appropriate reaction to "proof refutation"?

Are there good ways or places to post general feedback on "arbitrary ambitious CoRR papers"? What else can I do after I invested the effort to read such a paper? (And the hypothetical question: What could I do if I came to the conclusion that the result announced in the abstract is indeed correct?)


texts: What can be solved with semidefinite programming that can't be solved with linear programming?

texts:
I'm familiar with linear programs in that they can solve problems with linear objective functions and linear constraints. But what can semidefinite programming solve that linear programming can't? I already know that semidefinite programs are a generalization of linear programs.

Also, how does one recognize a problem that can be solved using semidefinite programming? What is a typical problem that semidefinite programming is used for that couldn't be solved via linear programming?

Thanks very much for any response.


texts: What is the notion behind proxy re-signatures?

texts:
Digital signatures allow an entity to sign a digital message so that it is easy to verify the signature, but it is hard to forge a valid signature on a given message.

It is sometimes useful to be able to delegate the signing to some proxy. The proxy signature schemes allow proxy signers to sign messages on behalf of an original signer, a company or an organization. Bruce Schneier describes this as follows:

  Alice, for instance, needs to go on a business trip to someplace which doesn’t have very good computer network access—to the jungles of Africa, for example. Or maybe she is incapacitated after major surgery. She expects to receive some important e-mail, and has instructed her secretary Bob to respond accordingly. How can Alice give Bob the power to sign messages for her, without giving him her private key?

  Proxy signatures is a solution. Alice can give Bob a proxy, such that the following properties hold:

  Distinguishability. Proxy signatures are distinguishable from normal signatures by anyone.
  Unforgeability. Only the original signer and the designated proxy signer can create a valid proxy signature.
  Proxy signer’s deviation. A proxy signer cannot create a valid proxy signature not detected as a proxy signature.
  Verifiability. From a proxy signature, a verifier can be convinced of the original signer’s agreement on the signed message.
  Identifiability. An original signer can determine the proxy signer’s identity from a proxy signature.
  Undeniability. A proxy signer cannot disavow an accepted proxy signature he created.
  In some cases, a stronger form of identifiability is required—that anyone can determine the proxy signer’s identity from the proxy signature.

But what exactly is proxy re-signatures? How and why is it performed? Does it use the same warrant generating and proxy signing mechanisms?

Context: Thinking on a new model for signatures. Was trying to combine the Sanitizable with Proxy Re-Signatures. Will it make a meaningful model and have any useful application?


texts: Decidability of first-order theory of real closed fields with functions

texts:
By a famous theorem of Tarski, the first-order theory of real closed fields is decidable, as it admits quantifier elimination. Can this result be extended so that propositions can be quantified over functions on real numbers? That is, I know that there is a decision procedure for statements like

$$\exists x \in \mathbb{R} ,\forall y \in \mathbb{R}, \exists z \in \mathbb{R}, x +y = zy$$

I'd like to know if there is a decision procedure for statements like

$$\forall f \in \mathbb{R} \to \mathbb{R}, \exists g \in \mathbb{R} \to \mathbb{R}, \forall z \in \mathbb{R}, f(g(z)) = g(f(z)) = z$$

Undecidability results would be just as interesting!


texts:
I am interested in learning about the current state of the art regarding forward chaining production systems. I understand that things haven't changed much (regarding the basic algorithms) since 1995's thesis by Robert Doorenbos, available here:

http://reports-archive.adm.cs.cmu.edu/anon/1995/CMU-CS-95-113.pdf

Am I right, or is there some other work I should be aware of?


texts: Why does not the definition of NP problems care about the complexity of guessing?

texts:
I have a question regarding the definition of NP problems. According to that, a problem is in NP if one can guess a certificate of polynomial size in polynomial time. However, this definition does not account for two things. First, how many certificates the problem can have? Should it be harder to deal with problems which have infinitely many certificates (even thought still in polynomial sizes) than ones that have only few? Why does not this feature affect the complexity of the underlying problem? Second, why does the size of the certificate (witness) but not the complexity of the guessing take a role in this definition?
I would really appreciate any clarification of this confusion.


texts: Error in entropy properties in Mathematical Theory of Cryptography by Claude E. Shannon

texts:
I am reading this classic paper by Claude E. Shannon and I think there may be a couple of errors in his description of the properties of Entropy/Uncertainty. The screenshot shown at the bottom of this post is from page 9. Firstly, I believe there is a typo at the first red circle which should read $10^{50}$. Secondly, I think the equation shown for the value of the entropy $H$ of this problem is also incorrect. I believe the correct equation for $H$ is derived as follows:
events $=\{p_1, p_2, ... , p_{10^{30}}, q_1, q_2, ..., q_{10^{50}}\}$
where events $p_i$ each have a probability $\frac{1}{2}(10^{-30})$ of occurring, and events $q_j$ each have a probability $\frac{1}{2}(10^{-50})$ of occuring
\begin{align}
H &= -\sum_{i=1}^{10^{30}} p_i\log{p_i} - \sum_{j=1}^{10^{50}} q_j\log{q_j} \\
&= -\sum_{i=1}^{10^{30}} \frac{1}{2}(10^{-30})\log{(\frac{1}{2}(10^{-30}))} -\sum_{j=1}^{10^{50}} \frac{1}{2}(10^{-50})\log{(\frac{1}{2}(10^{-50}))} \\
&= -\frac{1}{2}\log{(\frac{1}{2}(10^{-30}))} -\frac{1}{2}\log{(\frac{1}{2}(10^{-50}))} \\
&\approx 40
\end{align}
Hence, I think the equation for $H$ should read:
$H = -\frac{1}{2}\log{\frac{1}{2}10^{-30}} -\frac{1}{2}\log{\frac{1}{2}10^{-50}}$
I would really appreciate if someone could let me know if I'm correct or where I'm wrong. I am not doubting Claude, just wondering if the document itself has typos. Thanks!


texts: Minimum BoundingBox on n-dimensional case

texts:
I need to develop an algorithm to define the minimum bounding box on an N-dimensional space.

http://en.wikipedia.org/wiki/Minimum_bounding_box

Every reference to this problem that I'm able to find is related to computer graphics (so, only 2 or 3 dimensions). Where can I find some references on the generalised version of this problem?


texts: Why spectral norms are used for computing the complexity of adiabatic Hamiltonian?

texts:
In the context of adiabatic quantum computation the spectral norm was first used in the first adiabatic paper by Farhi et. al. when he demonstrated the relation of it to the conventional quantum computation. He showed that $$\Delta || H_P - H_B || << 1 $$. Later on van Dam et. al. also used spectral norm of Hamiltonian for computing the complexity. Daniel Nagaj also commented in chapter 2 of his PhD thesis that

  It is thus usual to think the required resources of an AQC algorithm as $T.||H|| ...$

Why do we need spectral norm for computing adiabatic Hamiltonian complexity? Why can't we just express it in terms of the eigenvalue of $\tilde{H}(S)$?


texts: Complexity and approximability of maximum edge biclique problem on co-comparability graphs

texts:
A subgraph $H$ of a given graph $G$ is called a biclique of $G$ if $H$ is a complete bipartite graph.  Given a graph $G$, finding a maximum edge biclique is known to be NP-complete (Peeters, Discrete Applied Mathematics 131, pages 651-654, 2003).

In fact, it is also known that it is unlikely we can obtain an $n^{\delta}$-approximation for this problem in polynomial time, for some constant $\delta > 0$ (Feige, STOC 2002; Goerdt and Lanka, ECCC 2004; Ambuhl, Mastrolilli, and Svensson SICOMP 2011).  These results hold even when $G$ is bipartite.

I was wondering whether any results are known for finding the maximum edge biclique in co-comparability graphs.  There are several equivalent definitions of a co-comparability graph.  One of them is a graph whose vertices are the elements of a partial order, and the edges are given by pairs of elements that are incomparable in the partial order.

Specific questions:

(1) Is the maximum edge biclique problem polynomially solvable for co-comparability graphs?

(2) If no polynomial time optimal algorithm is known, what is the best approximation algorithm known?


texts: Are there any references for finding non-trivial upper bounds to chromatic number using semidefinite programming?


texts: Finding the largest set of points of limited diameter (2)

texts:
Problem: Given a set of points $S = \{(x_1, y_1), (x_2, y_2),\cdots,(x_n, y_n)\}$ in $\mathbb{R}^2$ and a distance threshold $\tau$, find a subset of $S$ such that (1) the Euclidean distance between any two points of the subset is not greater than $\tau$, and (2) the subset is maximum.

In a related post, Eppstein mentions that the problem can be solved in $O(n^3\log n)$. I wonder

Is there any improvement of the complexity since then?
If we instead enumerate the maximal ones, can it be in PTIME?


texts:
Given a random walk on a graph the cover time is the first time (expected number of steps) that every vertex has been hit (covered) by the walk. For connected undirected graphs, the cover time is known to be upper bounded by $O(n^3)$. There are strongly connected digraphs with cover time exponential in $n$. An example of this, is the digraph consisting of a directed cycle $(1, 2, ..., n, 1)$, and edges $(j, 1)$, from vertices $j = 2, ..., n − 1$. Starting from vertex $1$, the expected time for a random walk to reach vertex $n$ is $\Omega(2^n)$. I have two questions :

1) What are the known classes of directed graphs with polynomial cover time ? These classes might be characterized by graph-theoretic properties (or) by properties of the corresponding adjacency matrix (say $A$). For example, if $A$ is symmetric then cover time of the graph is polynomial.

2) Are there more simple examples (like the cycle example mentioned above) where the cover time is exponential ?

3) Are there examples with quasi-polynomial cover time ?

I would appreciate any pointers to good surveys/books on this topic.


texts: Big gaps between RAM and Turing machine complexity

texts: If we only consider problems in P, are there any big gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm for particular problems? I am particularly interested if there are wide gaps for natural problems of general interest.


texts: Average message complexity for the election problem on graphs

texts:
I am currently studying the election problem in distributed algorithms. There, I stumpled over one approach to implement a Chang-Roberts-like message extinction algorithm on graphs without requiring a specific topology.

The idea is simple: each initiator starts an echo-algorithm to learn about the leader (so, to find the process with the biggest unique identifier). An initiator adds his unique id to the wave to mark the wave and allow wave extinction: if two waves "hit" each other, the one with the bigger id wins. Now, to my question, which is inspired by this problem but a little bit more abstract.

Given an arbitrary topology and an algorithm like the one described above, is it possible to come up with a model to calculate the average message complexity? I apologize if I missed something obvious to answer this, but it seems to me that I am stuck with computing the best and worst case but cannot come up with an average case description without more knowledge on the actual topology. Is this conclusion true?


texts: What's the most efficient algorithm for Divisibility?

texts:
What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask for is not (necessarily) an algorithm for Remainder Calculation. I just want to know whether $a$ divides $b$ or not. Being more specific, my question is whether exists or not some recent algorithm for Divisibility with time complexity better than $O(m\log m\log\log m)$, where $m$ is the number of bits of $\max\{a,b\}$. Further, is $\Omega(m\log m\log\log m)$ the lower bound of this problem?

Thanks and regards, and sorry if this is such a naive question.


texts: Proof that Entanglement Cannot Increase the Capacity of a Noiseless Classical Channel

texts:
I am aware that quantum entanglement cannot increase the asymptotic capacity of a noiseless classical channel. However, can anyone provide some type of reference in the literature that contains a proof of this particular feature of quantum communication? Very much appreciated.

Thanks.


texts:
I'm reading this paper, A simple NP-hard problem by Demontis, where he defines an interesting $NP$-hard set and finally he conclude with this theorem:

  Theorem: $P=NP$  if and only if it is possible to calculate in polynomial time all the
  fundamental elements of any formula.

The paper does not have an abstract and I'm kind of lost because of the new terminology used in the paper.

  Could you explain the significance of this paper? Do the fundamental elements of a formula represent the variables that have true value in every satisfying assignment? Does this theorem represent a new result? What are the insights into the $P$ vs $NP$ problem presented in the paper?

ACM SIGACT News, Volume 40 Issue 2, June 2009


texts:
It is well known that any proof resolving the P vs NP question must overcome relativization, natural proofs and algebrization barriers. The following diagram partitions the "proof space" into different regions. For example, $RN$ corresponds to the set of proofs that relativize and naturalize. $GCT$ (Geometric Complexity Theory) is of course the strictly outside region.

Name some proofs along with the best known regions they belong to. Place them in a best possible way i.e., if a proof is known to relativize, naturalize and algebrize then it should be placed in $RNA$ not just in $RN$. If a proof relativizes but does not naturalize it belongs to $R$ ${\setminus}$ $N$ and so on.


texts: What is the state of the art in theory of "Software transformations preserving behavior"?

texts:
I am interested in the field that could perhaps be referred to as "Automated Refactory" or "Preservation of Software Properties" after a transformation/change/refactory.

Saying we have an instruction/set of instructions I with some functional property P and some transformation T so that I' = T(I). Is there any research/work/papers that models P (just some properties, a group of, ...) and preservation/changes of those properties between I and I' for a set of transformations T?

First of all, what is the correct name for this fiels? Then, I would like to know if a theory to model this problem exists, which one is the most used (or the most referred to) and if any application of that system/metric/model (libraries, IDE plugins, ...) has been released.

If you can give any name, paper, ... whatever that is considered "fundamental" in this field, I will dig into this on my own.


texts: Are linear feedback shift registers being generally discouraged by cryptologists?

texts:
Katz and Lindell mention in their book that LFSR have been horrible as basis for pseudorandom generators, and advocate that they are not used anymore (well, they also recommend that people use block ciphers instead of stream ciphers).
But I see for example that one of the ciphers in the estream portfolio (Grain, targeted for hardware) uses an LFSR, so the opinion that LFSRs are not good is not a consensus.

I'd like to know if there many cryptologists sharing Katz and Lindell's opinion on LFSRs (and on stream ciphers)?


texts: Counting matchings on 3-regular bipartite graphs

texts:
What I call a graph here allows parallel edges.
Is the following problem #P-hard:

INPUT: a 3-regular bipartite graph $G$

OUTPUT: the number of matchings of $G$.

It is known that counting matchings on 2-3-regular (even planar) graphs is #P-hard: in this paper it corresponds to the problem denoted $\#[1,1,0]|[1,1,0,0]$, which is hard according to the table page 10, and in that one it corresponds to the problem $\#$2-3-RBP-$\lambda$-Matchings with $\lambda = 1$, and it is also shown to be #P-hard. In that last paper it is also shown that counting matchings on $3$-regular planar graphs is hard (see page 122, second paragraph). But what I need is 3-regular bipartite graphs.


texts:
Major rewrite justifiably asked for:

I'm currently trying to get a categorical way of doing something called the Gelfond-Lifschitz reduct on a set of single-headed Horn clauses. The semantics is the answer set semantics, and the idea is that given a program

$\Pi=\{a_i\gets L_{i_1}, \dots L_{i_k}, i\in\{1\dots n\}\}$ and a model $S$,

the Gelfond Lifschitz reduct on $\Pi$ is $\Pi$ with the following removed:

All occurences of clauses with $not\ a$ in the body for $a\in S$
All occurences $not\ a$ for all $a\notin S$.

Now, having a basic games model of this already, I'm trying to find out what further contraints on the category of games are required.

A seemingly neat way of doing the first part of the G-L reduct is being able to factor out points denoted by the model $S$ from the object denoting $\Pi$ such that every map in the denotation of $\Pi$ containing a map to the terminal object should be removed. (denoting negation as a map to the terminal object)

Similarly the second part requires a similar construct, where everything not consisdered a point by the denotation of the model should be removed entirely from the object denoted by $\Pi$.

I hope this makes more sense and I am very willing to clarify more.

More Clarification:

To summarize the semantics, we take a program $\Pi$ and denote that it itself is a category with objects as the literals and the horn clauses are the maps. We define a few operations on the category $C_{\Pi}$ denoting $\Pi$, namely the transitive closure as well as satisfiable model map which takes $C_{\Pi}$ to a category whose objects are purely points.

The point is that I have two effective issues at the same time. I need a semantics that allows the literals to be objects and the general denotation of implication to be a map between objects, and I need a set of operations on the categories denoted by the programs to constrain the categories.


texts: How to find a specific research topic to concentrate on?

texts:
I recently started my masters course. Last semester I took courses from different disciplines like networks, software engineering, architecture, etc. Recently, after taking an advanced course in algorithms and data structures I think I found a course which interests me most (including other similar topics likes programming languages, etc).

How do I find a research topic - specific data structure or algorithm I can work on for my thesis, and possibly follow up into a PhD? I am currently looking at some of the research done at my university in the same disciplines.

edit

I think some people confused the Question due to ambiguous framing from my side.
I want to find a topic for my masters thesis, I am still somewhat far awaw from starting a PhD(If I do)


texts: Remove specific edge from ST (link-cut) tree

texts:
ST (or link cut) trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time:

CUT(v) Deletes the edge from v to its parent
JOIN(v, w) Where v is a root vertex, assigns parent(v) ← w (makes v a child of w)
FIND_ROOT(v) Returns the root of the tree containing v

My question here is how to delete an arbitrary edge (u, v) from the tree, and what would be its complexity? If it is too complex or unfeasible to do that, can you point me to an algorithm ((pseudo)code) for the fully dynamic unweighted undirected graph connectivity problem. If it is of any help, the degree of every edge is guaranteed to be at most 2 at any point of the algorithm.

I've read quite a few papers on the topic but in almost all of them the authors only give us very high level descriptions of these structures, in the form of theorems.


texts:
I have the following LP:

/* Objective function */
min: 1 w + 2 x + 0.5 y + z;

/* Variable bounds */
w + x <= T1;
w + y = U1;
x + z = U2;
T1 = 50;
U1 = 70;
U2 = 25;

In this case U1 + U2 > T1 and the optimal solution is y = 70 and z = 25. I want to enforce the condition that w and x variables be assigned values before assigning values to y and z. If U1 + U2 < T1, then I want only w and x to have values and y = z = 0. Is there a way to enforce such a constraint in an LP or an MILP?


texts: Optimizing Maximum Weighted Matching (Edmonds Blossom)

texts:
Background:

I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java:

  https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java

The original Python implementation was written by Joris van Rantwijk and the papers he based it on are referenced on his website.

Unfortunately the speed is not adequate for my use case, so I'm looking to improve this. I have added some slow tests to the repo that I will use to measure the performance improvements.

I have further done some research and came up with the following three options to improve performance:

Parallelizing Edmonds Blossom, in particular reference is this implementation
Variable Dual Updates and the use of Priority Queues as described in Blossom V

Based on the Blossom V paper I'm expecting at least improvements in the order of one or two magnitudes. The reference to the parallel approach is unfortunately no longer available.

Questions:

Now before I get started on in-depth reading and more coding I have some questions that I hope will help me channel my efforts:

Are there any other algorithmic / implementation improvements available to increase performance significantly?
Are there any papers available on parallelizing the algorithm?
I want to do iterative improvements, do you see any reason why I can not add the suggested improvements independently?
What is the best order to add the improvements? What approach has the most value (complexity of implementation vs speed improvement) in your opinion (assuming ~10 cores) and why?
Is there code refactoring / separation you would recommend doing before starting on optimization?

Disclaimer / Misc:

I'm a big believer in Open Source and will keep the repository up with all the improvements I am making to it!

Note: There is also a JavaScript port available here. However not as clean as the Python or Java version.

Edit:

Found a great paper on the Blossom V performance and where to best add parallelization here. That somewhat answers question (2).

I'm now wondering if I should start from scratch and just implement Blossom V.


texts: Time Complexity for Nearest Neighbor Searches in kd-trees

texts:
Nearest neighbor searches in kd-trees run in logarithmic time, as shown by Friedman et al. However, I have some difficulty to fully understand the proof.

  In order to calculate the average number of buckets examined by the
  k-d tree searching algorithm described above, it is necessary to calculate the average number of buckets overlapped by the region $S_m(X_q)$.

$S_m(X_q)$ is the smallest ball centered at the query point $X_q$ that exactly contains the $m$ points closest to $X_q$.

I don’t get why only the regions overlapping $S_m(X_q)$ are examined. Consider the following example, where we want to compute the black point that is closest to the orange point $X_q$. $S_m(X_q)$ is the green circle in this case, so according to the proof the algorithm should only search both lower buckets.

However, the searching algorithm will find as first candidate solution the black point in the lower right region. Then, it will also search regions that intersect the blue circle, in particular the upper right region.

So, isn't it too restricted to compute only the buckets that intersect the green circle?


texts: Exact algorithm or parameterized algorithm for Maximum Edge Biclique Problem?

texts:
The Maximum Edge Biclique(MEB) problem is to find a biclique with as many edges as possible in a bipartite graph. It was proved to be NP-complete by Peeters in 2003, and then the inapproximability result for MEB was given by this paper in 2011 . But I could hardly find any exact algorithm or parameterized algorithm for MEB problem(maybe there are some).

What is the state of research on exact algorithm or parameterized algorithm for MEB problem? I appreciate if someone can provide guidance on where to look for such research and whether designing such algorithms is valid as a research point.


texts:
While Adleman's theorem shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq \mathsf{P}/\text{poly}$. What complexity-theoretic consequences would such an inclusion have?

Adleman's theorem is sometimes called "the progenitor of derandomization arguments." $\mathsf{BPP}$ is believed to be derandomizable, whereas there is no evidence that the "quantumness" of $\mathsf{BQP}$ could somehow be removed. Is this possible evidence that $\mathsf{BQP}$ is unlikely to be in $\mathsf{P}/\text{poly}$ ?


texts: Clifford group quantum operations and classical computation

texts:
The Clifford group of quantum operators is generated by the quantum operations:

Controlled-Z,
Hadamard, and
Phase ($= |0\rangle\langle0| + i |1\rangle\langle1|$).

A circuit composed only of these gates can be simulated efficiently on a classical computer. However, if I understand correctly, not all classical algorithms can be implemented efficiently using Clifford group operations, at least as far as we know.

Is there a construction to implement, even inefficiently or approximately, a classical algorithm using Clifford group operations?
For instance, how do you implement a Toffoli gate using Clifford group gates, if it's possible?


texts: Looking for a particular normal form for Context-sensitive grammar

texts:
I am wondering if there is a described normal form for Context-sensitive grammar, which is something similar to Kuroda normal form and Greibach normal form. That is to say, each rule in such form might be one of the following:

$A\beta\rightarrow a_1\dots a_k B_1 B_2\dots B_n a_{k+1}\dots a_m$

or

$A\rightarrow a_1\dots a_k B_1 B_2\dots B_n a_{k+1}\dots a_m$

where $A,B_i\in N$, $\beta\in(N\cup T)$, $a_i\in T$, $m\geq 0$, $n\geq 0$, $k\geq 0$, $(m+n)>0$.

The idea is that three conditions are satisfied:

In the left-hand side parts of rules, non-terminals always come first.
In the right-hand side parts of rules all non-terminals are grouped together.
Context-sensitive rules contain no more than two symbols in the left-hand side of the rule.

As an answer I would expect either a counter-example, which proves that it is not always possible to transform any context-sensitive grammar into this form, either a link to the existent paper where such normal form is described, either a proof that such normal form exists :-)


texts: A direct sum theorem for Resolution clause space complexity?

texts:
Resolution is a scheme to prove unsatisfiability of CNFs.  A proof in resolution is a logical deduction of the empty clause for the initial clauses in of the CNF.  In particular any initial clause can be inferred, and from two clauses $A \lor x$ and $B \lor \neg{x}$ the clause $A \lor B$ can be deduced as well.  A refutation is a sequence of deductions which ends with an empty clause.

If such refutation is implemented, we can consider a procedure that keeps some clauses in memory.  In case a non-initial clause must be used again and it is not in memory anymore, the algorithm should must it again from scratch or from the ones in memory.

Let $Sp(F)$ the smallest number of clauses to be kept in memory to reach the empty clauses. This is called the clause space complexity of $F$. We say say that $Sp(F)=\infty$ is $F$ is satisfiable.

The problem I'm suggesting is this: consider two CNFs $A=\bigwedge_{i=1}^m A_i$ and $B=\bigwedge_{j=1}^n B_j$, and let the CNF

$$A \lor B = \bigwedge_{i=1}^m \bigwedge_{j=1}^n A_i \lor B_j$$

What is the relation of $Sp(A \lor B)$ with $Sp(A)$ and $Sp(B)$?

The obvious upper bound is $Sp(A \lor B) \leq Sp(A) + Sp(B) -1$. Is this tight?


texts:
Multicuts or multiway cuts are (edge) cuts of minimum capacity that separate each pair of a set of terminals (a subset of the entire node set). For two terminals, this is the classical $s$-$t$ mincut problem. For $k \geq 3$ terminals, the problem becomes NP-hard.
Such a multicut may or may not be composed of mincuts that isolate each single terminal from the others (in case of $k=3$, 2 isolating cuts suffice to separate all pairs). I am interested in a multicut variant, where the multicut needs to be composed of such mincuts (one for each terminal). I call such a multicut a mincut-multicut (do you know a better name?).

Problem Mincut-Multicut:
Input: An undirected graph $G=(V,E)$, an edge capacity function $c:E \to \mathbb{N}$, a set $T=\{t_1, t_2, \dots t_l\} \subseteq V$ of $l \geq 2$ terminals and a number $k$ (all in binary).
Question: Is there a set $E' \subseteq E$ such that $E' = E_1 \cup E_2 \cup \dots \cup E_l$ where each $E_i$ is a $t_i$ isolating mincut, such that $\sum_{e \in E'} c(e) \leq k$?

Certainly, the capacity of such a mincut-multicut may be greater than of a conventional multicut, but not smaller. For each terminal, there may be an exponential number of mincuts isolating it from the others. For each terminal, we need to choose one of these exponentially many in order to compose the multicut.
If we can choose single terminal isolating mincuts such that the combination of them partitions the set of all nodes into $k$ sets (one for each terminal), we have found a mincut multicut of minimum capacity. It seems, however, quite challenging to determine whether such a mincut multicut exists.

Question: Is anything known about this problem or do you have any suggestions concerning its complexity?


texts:
I'm trying to do the following thing: take a set (here, nat, for the sake of simplicity), define a subset of "valid" values (here, even numbers), and then prove that two valid values with the same value are the same.

My problem is that my valid values are represented by records. And when I try to prove what I want, I try to use the f_equal tactic on that record and it does nothing. I imagine this is because both parts of the record are dependent, but I really don't know (I'm new to these).

Here is my code. Define a boolean predicate for valid values:

Fixpoint valid (n: nat) : bool :=
  match n with
    | 0 => true
    | 1 => false
    | S (S p) => valid p
  end
.

Define the type for valid values using the predicate and records:

Record valid_nat : Type :=
  { VN_value : nat ;
    VN_prop  : valid VN_value = true }
.

Prove that when the values are the same, the records are the same. I know this implies proof irrelevance, but that's not my main problem yet:

Theorem valid_nat_unique:
  forall (m n: valid_nat), VN_value m = VN_value n -> m = n
.
Proof.
  intros m n H.
  destruct m as [m_value m_prop].
  destruct n as [n_value n_prop].
  simpl in H.
  f_equal.    (* does nothing *)

Here is the goal before and after the f_equal tactic:

m_value : nat
m_prop : valid m_value = true
n_value : nat
n_prop : valid n_value = true
H : m_value = n_value
============================
 {| VN_value := m_value; VN_prop := m_prop |} =
 {| VN_value := n_value; VN_prop := n_prop |}

I was expecting to get m_value = n_value /\ m_prop = n_prop (then hypothesis H and proof irrelevance should be enough to finish. And now I'm stuck.

My Coq version is: The Coq Proof Assistant, version 8.5 (February 2016)

Any help would be highly appreciated. Thank you by advance.


texts: What is the difference between a TCS PhD thesis and Computer Science experimental PhD thesis?

texts:
I'm doing my PhD in computer science, namely theoretical computer science and currently waiting for my VIVA. I think one of my examiner is an experimental person, how can I convince her that my work have significant contribution similar to an experimental research.

I don't do experiment but I have theoretical contribution for my PhD. Can anyone recommend good literature that give comparison between theoretical and experimental computer science?

Thanks and will really appreciate your kind replies.

Pradeep


texts: Non Turing-Complete Models, Conditional-Complete function?

texts:
I know well the distinction between the class of Partial Recursive Functions, and $\mu$-Recursive, i.e. the latter is Turing Complete and the former is equivalent to the LOOP-Program model of computation.

So, LOOP programs are equivalent to an imperative language with assignment, if and for loops with computable upper bounds. Now, I wanna know two things:

1) Is there a model that corresponds to a language without iteration and with only assignment and selection (if) ?
2) Is there a model that use only assignment and arithmetic or logic expressions on int variables?

The question arise since, I was considering the transition from liner straight program with only assignment and arithmetic and bitwise operators, to the one that include if.
I suppose that functions like abs or max, min, cannot be computable without a selection than I realized that simple logical expression like: x ^ ((x ^ y) & -(x < y)); compute the max.
So basically max is computable by a very simple circuit. Now I would like to know, is there some function that require the 'conditional' to be computable or not?


texts: Message-based games with ambiguous communication

texts:
Consider the following game. We are given two sets of sentences $S_1,S_2$ where $S_1$ is the set of "ambiguous sentences"
and $S_2$ is the set of "explicit sentences". Each ambiguous sentence $s \in S_1$ can be decoded to a set $\Delta(s) \subseteq S_2$. Suppose
furthermore that to each "explicit sentence" $s \in S_2$ is associated a cost $c(s)$, e.g. evaluating the cost of the action described by the sentence.

Now the game involves $n$ players $P_1,...,P_n$ that can communicate through a common network $N$. In each turn, a player $P_i$ can broadcast a sentence $s \in S_1$, and each other player $P_j$ can interpret it as some sentence $s_j \in \Delta(s)$. Suppose that the players are scored as follows: every time a player $P_i$ sends a sentence $s$ decoded into a set of sentences $s_j$, he is charged a score of $\sum_j c(s_j)$.

Suppose for simplicity that there are two types of players: the "honest players" that always choose a minimum-cost decoding, and the "devious players" that always choose a maximum-cost decoding. Is it possible to devise an approximate strategy for the honest players in order to minimize their total score?


texts: Enumerating Minimal (a,b) vertex separators in a DAG

texts:
A vertex subset $S \subseteq V$ is an $(a,b)$ separator for nonadjacent vertices $a$ and $b$ if the removal of $S$ from a graph $G$ separates $a$ and $b$ into distinct connected components.

$S$ is a minimal $(a,b)$ separator if no proper subset of $S$ separates $a$ and $b$.

It is known [1] that all minimal $(a,b)$ separators in an undirected connected graph can be computed in $O(n^2 R_{ab})$ time, where $R_{ab}$ is the number of minimal $(a,b)$ separators.

Question 1. Are there any results showing that this enumeration can be done more efficiently when restricted to DAGs?

Question 2. Is there a simpler algorithm than [1] to do the enumeration in a DAG?

[1] Shen, Hong, Keqin Li, and Si-Qing Zheng. "Separators are as simple as cutsets." Annual Asian Computing Science Conference. Springer, Berlin, Heidelberg, 1999.


texts:
EDIT (v2): Added a section at the end on what I know about the problem.

EDIT (v3): Added discussion on threshold degree at the end.

Question

This question is mainly a reference request. I don't know much about the problem. I want to know if there has been previous work on this problem, and if so, can someone point me to any papers that talk about this problem? I'd also like to know the current best bounds on the approximate degree of $\textrm{AC}^0$. Any other information would also be appreciated (e.g., historical information, motivation, relation to other problems, etc.).

Definitions

Let $f:\{0,1\}^n \to \{0,1\}$ be a Boolean function. Let $p$ be a polynomial over the variables $x_1$ to $x_n$ with real coefficients. The degree of a polynomial is the maximum degree over all monomials. The degree of a monomial is the sum of exponents of the various $x_i$ that appear in that monomial. For example $\textrm{deg}(x_1^7x_3^2) = 9$.

A polynomial $p$ is said to $\epsilon$-approximate $f$ if $|f(x)-p(x)|<\epsilon$ for all $x$. The $\epsilon$-approximate degree of a Boolean function $f$, denoted as $\widetilde{\textrm{deg}}_{\epsilon}(f)$, is the minimum degree of a polynomial that $\epsilon$-approximates $f$. For a set of functions, $F$, $\widetilde{\textrm{deg}}_{\epsilon}(F)$ is the minimum degree $d$ such that every function in $F$ can be $\epsilon$-approximated by a polynomial of degree at most $d$.

Note that every function can be represented with no error by a degree $n$ polynomial. Some functions really do need a degree $n$ polynomial to approximate to any constant error. Parity is an example of such a function.

Problem statement

What is $\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$? (The constant 1/3 is arbitrary.)

Notes

I encountered this problem in the paper The Quantum Query Complexity of AC0 by Paul Beame and Widad Machmouchi. They say

  Also, our results do nothing to close the gap in the lower bound on the approximate degree of AC0 functions.

They mention "the problem of the approximate degree of AC0" in their acknowledgements too.

So I assume there has been some work on this problem before? Can someone point me to a paper that talks about the problem? And what are the best known upper and lower bounds?

What I know about the problem (This section was added in v2 of the question)

The best known upper bound on $\widetilde{\textrm{deg}}_{1/3}(\textrm{AC}^0)$ that is know is the trivial upper bound $n$. The best lower bound I know comes from Aaronson and Shi's lower bound for the collision and element distinctness problems, which gives a lower bound of $\tilde{\Omega}(n^{2/3})$. (For severely restricted versions of $\textrm{AC}^0$, like formulas with $o(n^2)$ formula size, or depth-2 circuits with $o(n^2)$ gates, we can prove a $o(n)$ upper bound using quantum query complexity.)

Related: threshold degree (Added in v3)

As Tsuyoshi points out in the comments, this problem is related to the problem of determining the threshold degree of $\textrm{AC}^0$. The threshold degree of a function $f$ is the minimum degree of a polynomial $p$ such that $f(x)=1 \implies p(x)>0$ and $f(x)=0 \implies p(x)<0$.

Lower bounds for the threshold degree of $\mathrm{AC}^0$ have now been improved by Sherstov. He exhibits a family of constant-depth read-once formulas on $n$ variables whose threshold degree approaches $\Omega(\sqrt{n})$ as the depth goes to infinity, which is almost tight since read-once formulas have threshold (and even approximate) degree $O(\sqrt{n})$. See http://eccc.hpi-web.de/report/2014/009/. (Jan, 2014)


texts: Classical Matrix-Vector multiplication Complexity of standard matrices

texts:
Why are standard unitary transforms such as the Fourier and the Hadamard transforms believed to have a multiplicative complexity (number of multiplications) of $O(n^{1+\delta_{m}})$ and an additive complexity of $O(n^{1+\delta_{a}})$ (number of additions) where both $\delta_{m}$ and $\delta_{a}$ cannot be $0$ simultaneously?

(Please refer: Section 2.2 Page 15 of "Complexity Lower Bounds Using Linear Algebra", by Satyanarayana V. Lokam, for candidate matrices conjectured to have an arithmetic complexity (multiplicative + additive complexity)  of $\Omega(n^{1+\delta})$).


texts: Reduction Unbounded Knapsack < k-Exact Unbounded Knapsack

texts:
I'd like to have an explicit reduction among these two problems:

(1) Unbounded Knapsack: Given a set of $n$ item types with weight $w_i$ and quality $q_i$ solve:

$$maximize \sum_{i=1}^n q_ix_i $$ with:
$$ \sum_{i=1}^n w_ix_i < W\\
x_i >= 0\ \in N
$$
i.e. fill up the knapsack as much as possible (up to W) with items, the items are not limited in numbers, you have an unbounded number of copies of item1 with weight $w_1$, and quality $q_1$, etc. So the variable $x_i$ are integers that denote how many copies of item $i$ are in a solution.

(2) The k-exact version of the above add another constraint:

$$ \sum_{i=1}^n x_i = k $$

i.e. you must take exactly $k$ item in total.

I do not need an algorithm for the problems, but I'd like to have an explicit reduction from (1) to (2). For a fixed istance of (1) the maximum number of items in a solution is limited from above by $kmax = W / \min w_i$. Then I can solve (2) for all value of $k$ from $1$ to $kmax$ and take the maximum of the solutions, but I'd like to see if there is a better way or not.


texts: Can you assign a type to any term of the λEA-calculus?

texts:
The untyped language of System-F and similar is the λ-calculus. That language has terms that can't be typed on System-F, λx.(x x) λx.(x x) being the most obvious example. The λEA-calculus, as described here, and its variants, has an interesting property that all stratified terms of the untyped language are total and strongly normalizing. That raises 2 questions:

Does that mean that, for all terms of λEA, there is a valid type derivation?
Is this a common phenomena, i.e., are there other systems with this same characteristic, or is it something particular of linear logic based proof languages?


texts:
In the Complexity Zoo, it says [1] that, in descriptive complexity, $P$ can be defined by three different kind of formulae, $FO(LFP)$ which is also $FO(n^{O(1)})$, and also as $SO(HORN)$.

However, there are some exceptions, for example, $Evenness$ can not be expressed by FP(FP has the same expressive power with LFP). $Connectivity$ and
$2-colourability$ are not definable by first-order logic. Some problems cannot even be axiomatized with a finite number of variables such as $Evenness$, $Perfect~Matching$, $Hamiltonicity$.

Immerman proposed that Fixed Point Logic + Counting(FPC) may be a possible logic for capturing P.

However, Cai Furer, Immerman showed that there are polynomial-time graph properties that are not expressible in FPC[2]. The problem of solving linear
equations over the two element field is not definable in infinitary logic with counting[3]. You may refer to [4] for more details.

So, what logic structure can capture P in general? The positive answer is that a class of ordered finite structures is definable in least fixed-point logic if, and only if, it is decidable in P by Immerman[5]and Vardi [6]. How about in the unordered case? Can you show more counterexamples of the statement in the complexity zoo?


texts: Initial population for a genetic algorithm from one individual

texts:
I'm trying to use GA solve the quadratic assignment problem (QAP). We're planning on using it to be able to provide good solutions when using branch and bound becomes impossible, and as a requirement, I have to make it work as if it "improved" an existing solution.

The problem is of course in generating the initial population. I want to ensure diversity as well as good fitness, but the starting individuals, somehow, have to come from a single input individual (it's going to be a good one, in terms of fitness).

How should I go about this? I've thought about creating an initial population consisting on half (or some proportion) of individuals similar to the initial one, and then adding the other half of new randomly (using some heuristic) generated individuals, to combine my solution with other parts of the solution space. Is this a good approach? If so, anny recommendations on the random heuristic to search for the new random individuals?


texts: Positive 1-in-3 SAT FPT or Fixed Parameter Intractable

texts:
There are a number of satisfiability problems that are difficult to solve even in the fixed parameter sense. For example, Weighted q-CNF Satisfiability is W[1]-complete when parameterized by the number of variables that are set to true.

My question is: is there any literature on whether Positive 1-in-3 is W[1]-hard or fixed parameter tractable when parameterized by the number of variables that are set to true? Positive 1-in-3 SAT is the problem where all literals in an expression are positive and exactly one literal in each clause is true.


texts: Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free?

texts:
Is the language {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} context-free or not?

I realized that I have encountered almost all variants of this question with different conditions about the relationship between i, j, and k, but not this one.

My guess is that it is not context-free, but do you have a proof?


texts:
Recently in a course I'm taking, we have been learning about the DPLL(T) algorithm for SMT solving. The basic outline goes like this:
DPLL_T(F)
  G = B(F) // where B is the boolean abstraction function
  while (true) do
    A,out = SAT-solver(G)
    if (out = UNSAT) then return UNSAT
    else
      out = T-solver(B'(A)) // where B' is the inverse of B and T is a theory solver
      if (out = SAT) then return SAT
      else G = G and !B(MinimalUnsatCore(B'(A))

This is all fine, but I struggle with the last line, MinimalUnsatCore(). Specifically, the  Minimal Unsatisfiable Core was defined as:

An Unsatisfiable Core $C$ of $A$ contains a subset of atoms in $A$ such that $B'(C)$ is still unsatisfiable.
A Minimal Unsatisfiable Core (MUC) $C^*$ has the property that if you drop any single atom of $C^*$ from $A$, the result is satisfiable.

The description for finding the MUC was that you must drop each atom from $A$, one by one, if the result of dropping a particular atom is satisfiable, then that atom must be in the MUC. This is fine, say, if there were only one conflict, for example:
$$(x = z) \wedge (x > z) \wedge (y = z)$$
The MUC would be $\{(x= z), (x > z)\}$. However if we added another contradiction unrelated to this core:
$$(x = z) \wedge (x > z) \wedge (y = z) \wedge (y > z)$$
Then at any point if we drop one individual atom, then $A$ is still not satisfiable because removing any one atom will still leave a contradiction. How do we remedy this to see that there are multiple MUCs? Can we still do this in linear time w.r.t. the number of atoms in the boolean abstraction? If not, what's the time complexity of finding all the MUCs?
See page 43 here: https://web.stanford.edu/class/cs357/lectures/lec9.pdf
MUCs are referred to as part of the concept of "Minimizing Learned Clauses". Specifically the method discussed on page 44.

If this isn't the correct place for this question (maybe better over at Math.SE or CS.SE?), please let me know.


texts: Why lower bounds for boolean Circuits does not imply arithmetic circuits lower bounds

texts:
My question is why lower bounds for depth 3 Boolean circuits with gates "and" and "xor" for determinant does not imply the same lower bounds for arithmetic circuits over $\mathbb{Z}$?

What is wrong with the following argument: Let $C$ be an arithmetic circuit calculating determinant then by taking all variables mod 2 we will get Boolean circuit calculating determinant.


texts: What paradigm of automated theorem proving is appropriate for Principia Mathematica-style formalization?

texts:
I am in possession of a book, which, inspired by Russell's Principia Mathematica (PM) and logical positivism, attempts to formalize a specific domain by determining axioms and deducing theorems from them. In short, it attempts to do for its domain what PM attempted to do for mathematics. Like PM, it was written before automated theorem proving (ATP) was possible.
I am trying to represent these axioms in a modern ATP system, and attempt to deduce theorems, initially those deduced by the author (by hand). I have not used an ATP system before, and given the plethora of options (HOL, Coq, Isabelle, and many more), each with their strengths, weaknesses, and intended applications, it is proving difficult to decide which is appropriate for my specific purpose.
The formalism of the author closely mirrors PM. There are classes (sets?), classes of classes, and so on up to 6 levels of hierarchy. There is first order, and possibly higher order logic. Given the connection to PM, I initially investigated Metamath, since several theorems of PM have been proved in MetaMath by other people. However, Metamath is of course a proof verifier and not an ATP system.
Going through descriptions of various ATP systems, I see several characteristics, such as implementations of Church's type theory, constructive type theories, intuitionistic type theories, typed / untyped set theory, natural deduction, types of lambda calculi, polymorphism, recursive function theory, and the existence of equality (or not). In short, each system seems to implement a very different language, and must be appropriate for formalizing different things. I assume that existing libraries for formalizing mathematics are not relevant to my purpose.
Any advice regarding the characteristics I should seek in choosing an ATP, or any other advice you may have after reading this question, would be much appreciated. For reference, here is a sample page from the book. Unfortunately, like PM, it is in Peano-Russell notation.

The book -
"The Axiomatic Method in Biology" (1937), J.H. Woodger, A. Tarski, W.F. Floyd
The axioms start with the mereological. For example,

1.1.2 $x$ is the sum of $\alpha$ if $\alpha$ is contained in the parts of $x$, and if when $y$ is any part of $x$ there is always a $z$
belonging to $\alpha$ having parts in common with the parts of $y$:
$$S{ = }_{ Df }\hat { x } \hat { \alpha  } \{ \alpha \subset \vec { {
P }^{ ‘ } } x:.(y):yPx.\supset .(\exists z).z\in \alpha .\vec { { P
}^{ ‘ } } y\cap \vec { { P }^{ ‘ } } z\neq \Lambda \}$$
Again, note that this is Peano-Russell notation (the notation of
Principia).

Later axioms have biological content, such as,

7.4.2 When gametes of two members of a Mendelian class unite in pairs to form zygotes, the probability of any given pair uniting is equal to
that of the other pair.
This, from what I understand, was a postulate of Mendelian genetics.
I omit the notation for this because it is three lines long, and
builds upon previously defined content.

Example of a theorem -

This apparently carries a meaningful interpretation in Mendelian genetics, which, not being a historian of biology, I do not understand. In the book, it was deduced by hand.
Thanks!


texts: Kolmogorov Complexity of the composition of two computable functions

texts:
Let's suppose we encode two computable functions $f$ and $g$ as binary strings so $f,g \in \{0,1\}^*$. What I am curious about is whether we can find good upper and lower bounds for:

\begin{equation}
K(f \circ g) \tag{1}
\end{equation}

where $K(\cdot)$ denotes Kolmogorov Complexity.

My intuition suggests that we can compress each function separately and therefore:

\begin{equation}
K(f \circ g) \leq K(f) + K(g) \tag{2}
\end{equation}

and in general I think we can demonstrate that:

\begin{equation}
K(f_n \circ f_{n-1} \circ ... \circ f_1) \leq \sum_{i=1}^n K(f_i) \tag{3}
\end{equation}

However, my intuition also suggests that this is probably not the best upper bound and I am also curious about tight lower bounds.

Might there be a general theorem that gives the best possible upper and lower bounds?


texts: Inverting a sum of easy to invert linear terms?

texts:
Below are some examples of linear equations with $d\times d$ matrices $Y,A,B,C,D$ which can be solved for unknown $d\times d$ matrix $X$ in $O(d^3)$ time. Repeated indices in each term are summed over:
\begin{align}
Y_{ik}&=A_{ij}X_{jk}+A_{kj}X_{ji}\\
Y_{ik}&=A_{ij} X_{jk} + A_{jk} X_{ij}\\
Y_{il}&=A_{ij} B_{kl} X_{jk} + C_{ij} D_{kl} X_{kj}\\
Y_{il}&=A_{ij} B_{kl} X_{jk} + C_{ij} D_{kl} X_{kj}+C_{jk}D_{il} X_{jk}\\
Y_{il}&=A_{ij} B_{kl}X_{jk} +C_{jk}D_{il} X_{jk}\\
\end{align}
Is there a generic approach for finding fast solvers for these kinds of equations? I'm wondering if there's a generic algorithm for solving sum of factored linear systems analogous to what can be done for sparse linear systems (if sparsity pattern has bounded treewidth, algebraic inversion is easy)
A generic solution for equations above takes $O(d^6)$ time, while traditional approach for a $O(d^3)$ algorithm needs some "trick" from numerical linear algebra.
More generally, what can we say about when is the following equation is easy to solve?
$$Y=g(x)=\sum_f f(X)$$
Here, $X$ is a tensor, and each $f(X)$ is a linear function of $X$ whose inversion is easy, whereas inversion of a general linear function over $X$ is considered "hard".
I suspect that one sufficient condition for easy inversion is when formulas for different $f$'s involve summations over disjoint indices of $X$. However, this is more restrictive than examples above where summation indices overlap between terms.
Edit the examples above are solved (in order) 1) utilize the fact that Y is symmetric 2) lyapunov solver 3) generalized t-sylvester solver 4) generalized t-sylvester + Sherman–Morrison 5) apply vec to both sides, use Sherman–Morrison formula, distribute inverse over Kronecker product


texts: BSP, but with curved surfaces (NURBS? kernelized support vectors?)

texts:
Let's say that I wanted to use a BSP not just for partitioning points, but also to define surfaces, i.e. that I have $\mathbb{R}^2$ and I want to be able to continuously map at least some easily known/calculated continuous subset of it to the points on the surface at every branch. Let's furthermore say that I wanted those surfaces to be curved.

I could arbitrarily approximate curved partitioning surfaces by using a helluva lot of straight planes ala the classic BSP, but that seems silly.

Is there prior art in using NURBS or kernelized support vectors or whatever to define smooth curved surfaces in a binary space partitioning tree s.t. extraction of some of the boundaries' points from the representation (enough to illustrate the boundary) is easily (and preferably deterministically, avoiding monte carlo methods) accomplished? Or is this one of those trivial knowledge-synthesis problems and I'm better off just winging it? If not, could someone please point me in the right direction?


texts: How to auto-derivate sequential iterative programs from a mathematical specification?

texts:
I had to derivate, by hand, sequential iterative programs at school using an unified Hoare-Dijkstra-Hehner programming theory.

First, write down the formal specification as a Hoare triple and figure out invariants for loops. Second, apply logic rules and theorems to find an implementation that satisfies completely the specification ensuring total correctness. Actually not an easy job.

How to automate this process? is it feasible?


texts: Is the dominating set problem constant-factor-approximable in undirected path graphs?

texts:
I am interested in the complexity of the minimum dominating set problem (MDSP) in some specific graph class.

A graph is an undirected path graph if it is the vertex-intersection graph of a family of paths in some undirected tree (this is a subclass of chordal graphs). It is known that the MDSP is NP-hard when considering undirected path graphs (see here). My question is:

  What is known about the (in)approximability of the MDSP in undirected path graphs? In particular, is there a constant-factor (polynomial-time) approximation algorithm for this problem?

Notes:
1) I could not find a reference for this question, including in this standard textbook about domination, where Chapter 8 is devoted to the complexity of the (decision problem) dominating set.
2) It is NP-hard to approximate the MDSP within $o(log(n))$ in another subclass of chordal graphs, split graphs. This follows from an easy reduction from minimum set cover (see here).
3) I think the original NP-hardness reduction for undirected path graphs from the above reference can be used to show that the MDSP admits no PTAS in this class of graphs. But would this be tight?


texts: Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length?

texts:
S-T CONNECTEDNESS

Input: a (undirected) graph $G=(V,E)$; $s,t \in V.$

Output: number of spanning subgraphs of $G$ in which there is a path from $s$ to $t$.

S-T CONNECTEDNESS problem is known to be #P-complete ([Valiant, L. G. (1979). The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3), 410-421.]).

I'm interested in those instances of S-T CONNECTEDNESS in which all simple paths between $s$ and $t$ are of the same length. Is anything known about the complexity of the problem on these instances? In particular, does the problem remain #P-complete?

Remark: In the Valiant's reduction, there are many simple paths between $s$ and $t$ of different lengths.


texts: Simply typed lambda calculus and higher order logic

texts:
What is the relation between simply typed lambda calculus and higher order logic?

Under Curry-Howard it seems that simply typed lambda calculus corresponds to propositional logic. How is it related to higher order logic? According to this tutorial by Geuvers: http://typessummerschool07.cs.unibo.it/courses/geuvers-1.pdf the language of HOL seems to be STT. Shouldn't it be PROP? What does that mean?

Did Church have in mind HOL when defined STT?


texts: Computing every boolean function with a polynomial over $\mathbb{F}_3$?

texts: The following paper briefly mentions the power of $MOD_6$ gates (page 3), and relies on the unstated fact that every boolean function can be computed with an arithmetic circuit of depth 2 over $\mathbb{F}_3$. I'm not sure how this is done.


texts: What do you call the join of two optimization problems?

texts:
I have two optimization problems, both of whose inputs are from the set $I$ and whose solutions are from the set $S$, one a minimization with objective function $m_{\min}$ and one a maximization with objective function $m_{\max}$. I am studying what I would like to call the "join" or "direct sum" of these two problems, the problem of maximizing $m_{\max}(x, w) - m_{\min}(x, w)$, though I don't know the correct name for such a problem. In my particular case, each problem on its own has a trivial algorithm that produces optimal solutions, but together, the problem is intractable. Has the structural complexity or approximability of optimization problems of this form been studied in a general way?

(The fact that one is a maximization problem and one is a minimization problem is not crucial here, they could both be the same type of optimization.)


texts:
$\mathsf{NC}$ captures the idea of efficiently parallelizable, and one interpretation of it is problems that are solvable in time $O(\log^c n)$ using $O(n^k)$ parallel processors for some constants $c$, $k$. My question is if there is an analogous complexity class where time is $n^c$ and number of processors is $2^{n^k}$. As a fill-in-the-blank question:

  $\mathsf{NC}$ is to $\mathsf{P}$ as __ is to $\mathsf{EXP}$

In particular, I am interested in a model where we have an exponential number of computers arranged in a network with polynomially bounded degree (lets say the network is independent of the input/problem or atleast somehow easy to construct, or any other reasonable uniformity assumption). At each time step:

Every computer reads the polynomial number of polynomial sized messages it received in the previous time step.
Every computer runs some polytime computation that can depend on these messages.
Every computer passes a message (of polylength) to each of its neighbours.

What is the name of a complexity class corresponding to these sort of models? What is a good place to read about such complexity classes? Are there any complete-problems for such a class?


texts: Subset sum solver. Worth continue working on this method?

texts:
I have been working in a subset sum problem solver for some time.

The implementation is an exact/exhaustive search solver.

The variable determining the asymptomatic growth rate is just $N$ (the number of elements in the input).

Current upper bound is $O^{*}(2^{log(N)^{2}})$

$M$, the bit length of each input variable from the set, does not impact/change the asymptomatic growth rate, that is, it has the same upper bound for an input set with 32 elements/32 bits per value than an input set with 32 elements using 35,50,64 (or more bits) to represent the values.

By current implementation details this is true for  $N \leq 33$. Higher values of $N$ will require to continue developing the method a bit.

Giving the above information.

Do you think it worth continue developing this method or better look to improve the upper bound before going into additional work?


texts:
A property of simple $n$-vertex graphs is said to be evasive if its deterministic query complexity is exactly maximal, $\binom{n}{2}$ (that is, the best algorithm must query all $\binom{n}{2}$ possible edges in the worst case). The Evasiveness Conjecture (see here) is a strengtheneing due to Karp says that all nontrivial monotone graph properties are evasive. The current best lower bound of $(1/3 - o(1))n^2$ is due to Scheidweiler and Triesch, and the evasiveness conjecture is known to hold for various classes of graphs (and this). The smallest open case is for graphs on 10 vertices, see e.g. Angel & Borja.

Very recently, Aaronson, Ben-David, Kothari, and Tal used Huang's proof the Sensitivity Conjecture to show that the quantum query complexity of any nontrivial monotone graph property is $\Omega(n)$, which is optimal up to a constant.

The Evasiveness Conjecture conjectures the exact form of the deterministic query complexity of such properties.

  Is there a natural conjecture as to the exact form of the quantum query complexity of nontrivial monotone graph properties? If so, what is it, and how close/far are the current results from it?

The Evasiveness Conjecture has also been generalized to various classes of functions; I'd be interested to know about the same in the quantum setting as well.

Buhrman, Cleve, de Wolf, and Zalka (1999) mention quantum evasiveness, but only to show that some monotone graph properties do not require $\Omega(n^2)$ quantum queries. I had trouble finding anywhere else that discusses quantum evasiveness.

Update 2020 May 05: As pointed out by smapers in the answer & its comments, since the quantum query complexity of non-emptiness is $\Theta(n)$ (using Grover for the upper bound) and that of connectivity is $\Theta(n^{3/2})$, there is no function $f(n)$ that only depends on $n$. Leading me to refine the question to:

  Is there some nice (meta-)property of the monotone property such that there is a reasonable conjecture that depends on $n$ and that meta-property?

Really I'm just curious about a conjecture more refined than big-Theta.


texts: How fast can we find and disconnect roots in a forest?

texts:
Consider a forest of rooted trees. The problem is to support two operations:

disconnect(v): if v is the root of some tree in the forest, remove all edges of v;
findroot(v): find root of the tree containing node v.

Are there known worst-case lower bounds for such operations? In particular, is it possible to support both operations in $O(1)$ worst-case time?

Note that this problem is equivalent to the following version of marked ancestor problem:

mark(v): mark node v of the rooted tree, if its direct parent already marked or if v is the root;
firstmarked(v): return nearest marked ancestor of v.

There is a known lower bound trade-off if we allow mark(v) to mark any node:

  We present a new lower bound for the marked ancestor problem in the cell probe model with word size b between the update time $t_u$ and the query time $t_q$, $$t_q = \Omega(\frac{\log n}{\log(t_u b \log n)})$$

  BRICS RS-98-7 Alstrup et al.: Marked Ancestor Problems

For a reasonable word size $b$, this trade-off implies that it is impossible to support both operations within $O(1)$ worst-case time.

Alstrup et al. prove the same trade-off for various related problems. However I couldn't find any assertions about my version: their proof technique seems to rely on arbitrary gaps between marked nodes.


texts: Spell Checker with BK tree and edit distance that accounts for transpositions

texts: I want to try and write code for a BK tree using a certain edit distance that accounts for transpositions for a spell corrector. I've looked into Damerau-Levenshtein distance, but the triangle inequality required for a BK tree does not hold. Any suggestions?


texts: The Complexity of Properly Learning Decision Trees

texts:
Where does this paper prove the middle bullet point of its abstract?

I have looked through that paper fairly thoroughly.

There are three things I want to read how they're getting around.

Reductions from NP problems to SAT may have the effect

of applying arbitrarily large polynomials to the input size.
Theorems 2 and 3 and 20 restrict the runtime of their learning algorithms.
Theorems 2 and 3 and 20 consider randomized algorithms.


texts: What logic(s) exist for attributing belief?

texts:
I'm looking for an appropriate formalism to represent "traceability" in claims, especially connecting conclusions to source materials in a rigorous way.  For example, I'd like to be able to represent something like the following chain of thoughts (Assume "I" is well-defined here):

Consider document X (stored in some format).
I believe that X corresponded to the URL https://www.iaea.org/sites/default/files/gov2010-46.pdf as of 10/24/2017, because I downloaded it from there on that date.
I believe that the text "Implementation of the NPT Safeguards Agreement and relevant provisions of Security Council resolutions in the Islamic Republic of Iran" occurs at position Y in the file, because Adobe Acrobat extracted it.
I believe that those words are the title of the document, because I looked at it and I say so.
I believe that the text "3 On 28 August 2010, of the 8856 centrifuges which had been installed at FEP, 3772 centrifuges were being fed with UF6." appears in the document at position Z, because Adobe Acrobat extracted it.
I believe that text is "Footnote 3 of paragraph 4 in section A.1" because I looked at it and I say so.
I believe that Document X is asserting this statement to be true, because of my human judgment of the context.
I believe that "On August 28 2010 there were 8856 centrifuges installed at FEP" is equivalent to or implied by that statement, because of my human interpretation of those words"
I believe that, in that text, "FEP" means "The Fuel Enrichment Plant at Natanz" because of human judgment of the context.
I believe that Formula FOO represents the english-language statement "On August 28 2010 there were 8856 centrifuges installed at the Fuel Enrichment Plant at Natanz" because I wrote it and assert that it's an accurate encoding.
I believe that document X was written by "The Director General of the IAEA" because ___ .
I believe that document X is dated "6 September 2010" because ___ .
I believe that "'The Director General of the IAEA' asserts what X asserts, as of 9/6/2010" by inference from the previous 2 statements.
I believe that "As of 9/6/2010, 'The Director General of the IAEA' asserts FOO", by inference from the preceding statements a,b, and c.

It would additionally be nice to represent derivations like:

I believe that "As of 9/6/2010 FOO" because I trust 'The Director General of the IAEA' (possibly in some limited scope).

At this point, I'm not yet looking at complete reasoning over such a chain of attribution, though of course that's a desirable end state.  Right now, I'd like to be able to do more ad-hoc queries like "Person B does not trust the Director General, should B believe FOO" -- to which the answer would be no, given only the evidence we've shown here.  Depending on the object language in which I we wrote FOO, it would be nice to be able to say "Bob should still believe Formulas BAR and BAZ for other reasons; those imply FOO or imply something close to FOO."

After all that -- does anyone know of formalisms that can capture this sort of epistemic assertions?  Double bonus if it's somewhat tractable to reason over.  I've so far assumed that "the logic for beliefs" and "the logic for the word" are unrelated, but if a single logic can capture both, that's even better.


texts: NP-completeness of a specific topological sorting problem

texts:
Consider $(V, E)$ be a DAG, and $p_1, \dots, p_n$ be its topological sorting (i.e. such permutation $p$ of $V$ that $\forall(x, y) \in E.\ p^{-1}(x) < p^{-1}(y)$). Let's call the goodness of $p$ a number of positions $i$ such that $p_i + 1 = p_{i+1}$ (the number of consecutive numbers which are also consecutive in $p$).

The problem itself: find a topological sorting with maximal goodness. Or, as a decision version: is there one with goodness at leask $k$?

The problem is clearly in NP, but I couldn't find out whether it is NP-hard or polynomially solvable. I could apply no type of a dynamic programming or flows or any other competitive programming technique. The problem itself looks like being NPC, reminding of this, for instance, but at a glance I didn't manage to reduct anything classical to it.

I googled for some related articles, but the best results I found were on NP-hardness of crossing number and optimal linear arrangement, which are somewhat related but do not help.

I wonder if this problem is classical or has some trivial solution which just eludes my mind.


texts: Can there exist a single Turing machine complete for PTIME, or for $\#P_1$?

texts:
In "The Complexity of Enumeration and Reliability Problems", Valiant mentions the existence of a single Turing machine that is complete for the class $\#P_1$ (i.e., $\#P$ with unary input). On page 419, he writes:

  it is sufficient to simulate just the following fixed TM, $M$, which
  is clearly complete for $\#P_1$: on unary input $n$, $M$ first
  verifies that ... and then simulates the $i$th machine in $\#TIME(n)$
  on input $j$ (or vice versa)

I find the existence of such a machine surprising:

Does there exist a machine complete for PTIME that can simulate any
other PTIME machine. That is, a PTIME machine that takes a number $i$ and a string $s$ as input, and then executes the $i$th PTIME machine
with input $s$?
Would the existence of such a machine not lead to a
contradiction, because it would have a complexity $O(n^k)$, which means that no PTIME machine can have complexity $O(n^{k+1})$.
If this is indeed not possible for PTIME, why is it possible for $\#P_1$?