texts: Deterministic communication complexity vs partition number

texts:
Background:
Consider the usual two-party model of communication complexity where Alice and Bob are given $n$-bit strings $x$ and $y$ and have to compute some Boolean function $f(x,y)$, where $f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$.
We define the following quantities:

$D(f)$ (the deterministic communication complexity of $f$): The minimum number of bits that Alice and Bob need to communicate to compute $f(x,y)$ deterministically.
$Pn(f)$ (the partition number of $f$): The logarithm (base 2) of the smallest number of monochromatic rectangles in a partition (or a disjoint cover) of $\{0,1\}^n \times \{0,1\}^n$.

A monochromatic rectangle in $\{0,1\}^n \times \{0,1\}^n$ is a subset $R \times C$ such that $f$ takes the same value (i.e., is monochromatic) on all elements of $R \times C$.
Also note that the partition number is different from the "protocol partition number", which was the subject of this question.
See the text by Kushilevitz and Nisan for more information. In their notation, what I have defined to be $Pn(f)$ is $\log_2 C^D(f)$.
Note: These definitions are easily generalized to non-Boolean functions $f$, where the output of $f$ is some larger set.

Known results:
It is known that $Pn(f)$ is a lower bound on $D(f)$, i.e., for all (Boolean or non-Boolean) $f$, $Pn(f) \leq D(f)$.
Indeed, most lower bound techniques (or perhaps all?) for $D(f)$ actually lower bound $Pn(f)$. (Can anyone confirm that this is true of all lower bound techniques?)
It is also known that this bound is at most quadratically loose (for Boolean or non-Boolean functions), i.e., $D(f) \leq (Pn(f))^2$. To summarize, we know the following:

$Pn(f) \leq D(f) \leq (Pn(f))^2$

It is conjectured that $Pn(f) = \Theta(D(f))$. (This is open problem 2.10 in the text by text by Kushilevitz and Nisan.)  However, to the best of my knowledge, the best known separation between these two for Boolean functions is only by a multiplicative factor of 2, as shown in "The Linear-Array Conjecture in Communication Complexity Is False" by Eyal Kushilevitz,    Nathan Linial, and Rafail Ostrovsky.
More precisely, they exhibit an infinite family of Boolean functions $f$, such that $D(f) \geq (2 - o(1)) Pn(f)$.

Question:

What is the best known separation between $Pn(f)$ and $D(f)$ for non-Boolean functions? Is it still the factor-2 separation referenced above?

Added in v2: Since I haven't received an answer in a week, I'm also happy to hear partial answers, conjectures, hearsay, anecdotal evidence, etc.


texts:
Given $n$ vertices of color $1$ and m vertices of color $2$, what is the maximal number of edges that can join them on the constraints - $(a)$ no edge joins has the same color ends and $(b)$ no two edges intersect when drawn on a plane (a planar graph)?

Also given such $n$, $m$ how many such graphs can be generated so that no vertex is isolated and how many maximal non-equivalent maximal graphs are possible?

Are these standard questions that have been studied anywhere?

$n = m$ is the case I am looking for a lead.


texts: Minimum Weight Disconnected Subgraph and "Opposite" problems

texts:
Given a graph $G = (V,E)$ and a vertex weight $z_v$ for each $v \in V$, find an (EDIT) induced subgraph $G' = (V', E')$ with minimum weight $z_{G'}=\sum_{v' \in V'} z_{v'}$ where $G'$ is disconnected (i.e., has 2 or more maximal connected components).

The maximum weight connected subgraph problem is known to be NP-hard by reduction from MINIMUM-COVER [1].  Is this "opposite" disconnected problem easier?

Also, maybe this deserves its own question, but are there interesting (non-contrived) cases where the "opposite" of a well-known hard problem is easy?  Here's an attempt at defining opposite for vertex-weighted graph optimization problems:

The problem P is defined as follows. Given a vertex-weighted graph $G$, and a set $\mathcal{S}$ of induced subgraphs of $G$, find an induced subgraph in $\mathcal{S}$ with maximum weight. Then, the opposite of $P$ is defined as follows. Given a vertex-weighted graph $G$, and the set $\mathcal{\bar S}$ of induced subgraphs of $G$ that are not in $\mathcal{S}$, find an induced subgraph in $\mathcal{\bar S}$ with minimum weight.

(Note: since $z_v$ is not constrained to be positive, minimizing or maximizing is arbitrary.  I switch only for aesthetics related to the term "opposite".)

[1] http://prosecco.ucsd.edu/ISMB2002/nph.pdf


texts: I'm a little bit lost with the actual definition of IP, some sources define as interaction between algorithms starting with Verifier, another one does not any put restriction on who send the first message. This simple question turn things messy ahead, when take into account  the number of messages on definition of IP(k). Does matter who start the interaction?


texts: Fast sparse boolean matrix chain product

texts:
So, I've got about 100-200 very sparse square boolean matrices with side length ~several dozens, and I need to compute their product. I know that if I multiply them serially, the product will usually stay as sparse at each step.

Are there any matrix chain product algorithms that work particularly fast in this case?

On a higher level, the problem is to compute the composition of a series of one-to-many mappings on a reasonably small graph (transition functions of an NFA), where most elements map to no more than 0-3.

(please note that this is not the usual "matrix chain product" problem, because all matrices are of the same size and I don't have to choose the optimal parenthesizing)


texts:
What are the most significant annual Complexity Theory conferences?

Rules:

One conference per answer
Include a link to the conference


texts: Formal languages induced by ultrafilters

texts:
Let $I$ be the set of all recursively enumerable languages over an alphabet $\Sigma$.
Let $$S_\alpha=\{i\in I : \alpha\in i\}$$ for all $\alpha\in\Sigma^*$.
Then $$E=\{S_\alpha:\alpha\in K\subseteq\Sigma^*\}$$ can be extended to an ultrafilter $\mathscr{U}$ since $E$ has the finite intersection property:
$$\{{\alpha_1},\dots,{\alpha_n}\}\in S_{\alpha_1}\cap\dots\cap S_{\alpha_n}\text { and }\{{\alpha_1},\dots,{\alpha_n}\}\in I \text{ since it's a finite language}$$
We can define $L=\{\alpha:\{i\in I:\alpha\in i\}\in \mathscr{U}\}$.

What is the relationship between $L$ and $K$?


texts: Distinguishing between $N$ quantum states

texts:
Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$?

This problem can be turned into a two state distinguishability problem by considering the problem of distinguishing $\rho_A$ from $\rho_{B} = \frac{1}{N-1}\sum_{i\neq A}\rho_i$.

I know for two quantum states the problem has a nice solution in terms of the trace distance between the states when you minimize the maximum probability of error rather than the minimizing the average probability of error, and I was hoping that there might be something similar for this case. It is of course possible to write the probability in terms of an optimization over POVMs, but I am hoping for something where the optimization has already been performed.

I know there is a huge literature on the distinguishability of quantum states, and I've been reading through a lot of papers over the last few days trying to find the answer to this question, but I'm having trouble finding the answer to this particular variation of the problem. I'm hoping someone who knows that literature better can save me some time.

Strictly speaking, I don't need the exact probability, a good upper bound would do. However, the difference between any one state and the maximally mixed state is quite small, so the bound would have to be useful in that limit.


texts: Natural problems in $NP \cap coNP$ not in $UP \cap coUP$?

texts:
Are there any natural problems in $NP \cap coNP$ that are not (known to be/thought to be) in $UP \cap coUP$?

Obviously the big one everyone knows about in $NP \cap coNP$ is the decision version of factoring (does n have a factor of size at most k), but that is in fact in $UP \cap coUP$.


texts: Multimodal logic with quantification over modal operators

texts: I take a multimodal logic to be a logic with multiple (potentially infinitely many) primitive modal operators. I am curious if anyone has studied a logic that allows one to quantify over the modal operators themselves. Intuitively, if we think of $\langle R\rangle \varphi$ as $\varphi$ by doing $R$ (where $R$ is a program), then it should make sense to want to say ``$\varphi$ by doing something,'' hence the thought of quantifying over modal operators.


texts: Efficiently computable by a "simple" algorithm?

texts:
I am interested in the relation between "program complexity" and "computational complexity".

In particular, I was wondering

What is known about the minimal length a program must have to solve a given problem (efficiently)?

Is there such thing as "program complexity-bounded" computational complexity classes?

Any information related to the topic is much appreciated.
Is this an active research area? What are open problems?
References to textbooks, research articles? etc.

(Googling this, all I find is "resource-bounded Kolmogorov complexity" etc., but that seems to be the exact opposite of what I am looking for...)

EDIT:
Some context: In the field I am working in the argument "simple algorithms cannot possibly perform as good as complex ones", is often quoted to motivate unnecessarily complex approaches. While this is by itself an insufficient argument, I can understand that some problems indeed might require a minimal complexity to be solved (efficiently?). However, I was wondering whether there were any general theoretical results supporting this notion, or research being performed in this direction.


texts:
Are results known which rule out the existence of "too-good-to-be-true" data structures?

For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz and Sleator STOC '87) and still obtain $\mathcal{O}(1)$ time operations?

Or: can one implement an ordered set with integer keys and $\mathcal{O}(1)$ time operations? Of course this is at least as hard as discovering a linear time algorithm for sorting integers.

Has the answer been proven to be no for either of these questions? Are lower bound results known for any natural data structure?


texts: Are there any public synchronous discussion forums (slack, discord, etc.) for TCS

texts:
I'm a 2nd year masters student studying theoretical CS (algorithms to be precise). I would like to know if there are any public synchronous discussion groups (slack, discord, etc.) for TCS. CSTheory StackExchange works well when someone has a specific question/query, but I felt it would be awesome to have an online forum for people interested in TCS to discuss about various developments of the field and also talk about interesting papers and concepts.

If enough people are interested we could create one in discord.

EDIT 1

As we have gained enough traction, I would like to know your opinions on how to proceed further. Some questions on top of my mind -

How should it be structured and what is the scope of the discussion
As I'm still an amateur, I would need some guidance from mods on how to go about this in general. And preferably some more volunteers.
Also I would like to know what platforms do the people up-voted prefer.

EDIT 2

Interested people, please fill this poll

EDIT 3

I have created a group in Zulip


texts: Are endmarkers necessary for Deterministic Pushdown Automata?

texts:
In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to accept as arguments triples $(q, \sigma, \gamma)$ with $\sigma$ that might be a right endmarker symbol. It is written: "The right endmarker delimits the input string and is a necessary addition. With NPDAs, we could guess where the end of the input string was, but with DPDAs we have no such luxury." (p. 176).
Can we show that this condition is necessary? Can we give an example of a language accepted by this kind of DPDA's that is not accepted by any DPDA whose transition function has no argument with an endmarker?


texts: What is the proof of this nonstandard version of Azuma's inequality?

texts:
In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality:

  Let $C_1, \dots, C_k$ be real-valued random variables such that for every $i \in [k]$,

  $\Pr[|C_i| \leq \alpha] = 1$, and
  for every $(c_1, \dots, c_{i - 1}) \in \text{Supp}(C_1, \dots, C_{i - 1})$, we have $\text{E}[C_i \mid C_1 = c_1, \dots, C_{i - 1} = c_{i - 1}] \leq \beta$.

  Then for every $z > 0$, we have $\Pr[\sum_{i = 1}^k C_i > k\beta + z \sqrt{k} \cdot \alpha] \leq e^{-z^2/2}$.

I'm having trouble proving this. The standard version of Azuma's inequality says:

  Suppose $\{X_0, X_1, \dots, X_k\}$ is a martingale, and $|X_i - X_{i - 1}| \leq \gamma_i$ almost surely. Then for all $t > 0$, we have $\Pr[X_k \geq t] \leq \exp(-t^2/(2 \sum_{i = 1}^k \gamma_i^2))$.

To prove the version of Azuma's inequality stated by Dwork et al., I figured we should take $X_0 = 0$ and $X_i = X_{i - 1} + C_i - \text{E}[C_i \mid C_1, C_2, \dots, C_{i - 1}]$. That way, I think $\{X_0, \dots, X_k\}$ is a martingale. But all we can say is that $|X_i - X_{i - 1}| \leq 2\alpha$ almost surely, right? That factor of two causes trouble, because it means that after substituting, we merely find that $\Pr[\sum_{i = 1}^k C_i > k\beta + z\sqrt{k} \cdot 2\alpha] \leq e^{-z^2/2}$, which is weaker than the conclusion stated by Dwork et al.

Is there a simple trick I'm missing? Is the statement by Dwork et al. missing a factor of two?


texts: Algorithms to approximate a Riemann integrable function by a piecewise constant function

texts:
We know that any general function that is Riemann integrable can be approximated to arbitrary precision by piecewise constant functions. So in this regard, I was looking for references on algorithms (and info on the corresponding query complexity since I assume it should be query-based) that when given a non-negative and non-atomic Riemann integrable function $f$ defined on the interval [0, 1] and an $\epsilon > 0$, outputs a piecewise constant function $g$ such that $ \forall I$, where $I$ is an interval in $[0,1], \int_I f(x) dx \leq \int_I g(x) dx \leq \int_I f(x) dx + \epsilon$.

Edit 1: Added that the function $f$ is non-negative and non-atomic.

Edit 2: Based on discussion in the comments, changed the question to "outputs a piecewise constant function $g$ such that $ \forall I$, where $I$ is an interval in $[0,1]$, $\int_I f(x) dx \leq \int_I g(x) dx \leq \int_I f(x) dx + \epsilon$".


texts: Best known deterministic time complexity lower bound for a natural problem in NP

texts:
This answer to Major unsolved problems in theoretical computer science? question states that it is open if a particular problem in NP requires $\Omega(n^2)$ time.

Looking at the comments under answer made me wonder:

  Aside from padding and similar tricks,
  what is the best known time complexity lower bound on a deterministic RAM machine
  (or multiple-tape deterministic Turing machine)
  for an interesting problem in NP (which is stated in a natural way)?

  Is there any natural problem in NP which is known to be unsolvable in quadratic deterministic time on a reasonable machine model?

Essentially, what I am looking for is an example that rules out the following claim:

  any natural NP problem can be solved in $O(n^2)$ time.

Do we know any NP problem similar to those in Karp's 1972 paper or Garey and Johnson 1979 that requires $\Omega(n^2)$ deterministic time?
Or is it possible to the best of our knowledge that all interesting natural NP problems can be solved in $O(n^2)$ deterministic time?

Edit

Clarification to remove any confusion resulting from the mismatch between lower bound and not an upper bound:
I am looking for a problem which we know we cannot solve in $o(n^2)$.
If a problem satisfies the stronger requirement that
$\Omega(n^2)$ or $\omega(n^2)$ time is needed (for all large enough inputs) then better,
but infinitely often will do.


texts: Alternative Set Cover Algorithm With Doubling

texts:
I remember that I saw once an alternative to the greedy set cover algorithm that works as follows:

Assign weight 1 to every element in the universe. Repeat steps 2 and 3 until the universe is covered:
Pick a set for which the sum of weights of all the elements it contains is maximal.
Double the weights of all uncovered elements.

I remember that it was also log(n) approximation, though I don't know how to show it. Is there some known technique for that kind of algorithms, in which appropriate global weight/cost on all the elements can give some approximation guarantees?


texts:
Let $(\mathcal{X},\rho)$ be a metric space (say, $\mathcal{X}=[0,1]$ with the Euclidean metric). Let $\alpha:\mathcal{X}\to[0,1]$ be unknown. Suppose that $\mathcal{X}$ is endowed with a distribution $\mu$ from which $(X_1,\ldots,X_n)$ is sampled iid. Further, for each $X_i$, we observe $Y_i\sim\mathrm{Bernoulli}(\alpha(X_i))$.

Our goal is to recover $\alpha$ from the finite sample, under some loss function (I tend to favor the pointwise loss $\ell(\hat\alpha,\alpha)=$
$$KL(\hat\alpha||\alpha)
=
\hat\alpha\log(\hat\alpha/\alpha)
+
(1-\hat\alpha)\log[(1-\hat\alpha)/(1-\alpha)]
,$$
but other loss functions can be considered also.)

Obviously, there is no hope of recovering $\alpha$ without some regularity condition, such as Lipschitz continuity.

Does this problem fall under some known framework?

Edit: Following Clement's comment, a clarification. The loss I defined above is pointwise, at each $x$ --- so it should really be $\ell(\hat\alpha(x),\alpha(x))$. The overall risk is then
$$R(\alpha)=E_X[\ell(\hat\alpha(X),\alpha(X))].$$


texts:
Let $S_{n}(G)$, $C_{n}(G)$, $T_{n}(G)$ be the $n$-fold Strong Product, Cartesian Product and Tensor Product of a graph $G$ on $|V|$ vertices.

Let the chromatic number ($\chi(G)$) and the independence number ($\alpha(G)$) of $G$ be known through a (possibly exponential time) algorithm. Is it known that the calculation of $\chi(S_{n}(G))$, $\chi(C_{n}(G))$, $\chi(T_{n}(G))$,$\alpha(S_{n}(G))$, $\alpha(C_{n}(G))$ and/or $\alpha(T_{n}(G))$ require exponential in $n$ complexity for any $n$ say even when restricted to some special graphs?


texts:
If I'm not mistaken it is not known whether $E^{NP} \subseteq {\rm SIZE}(n)$
where $E^{NP}$ is the class of problems solvable by a TM which works in time $2^{O(n)}$ and is allowed to make queries of size $2^{O(n)}$ to an NP oracle, and ${\rm SIZE(n)}$ is the class of functions solvable by non-uniform circuits of size $O(n)$.

Since ${\rm NSPACE}[n]\subseteq E \subseteq E^{NP}$ the above observation implies that the question of whether ${\rm NSPACE}[n]\subseteq {\rm SIZE}[n]$ is open.

Questions:

What is the smallest function $f(n)$ such that it is known
unconditionally  that ${\rm NSPACE}[f(n)]\nsubseteq {\rm SIZE}[n]$?
What is the smallest class $\mathcal{C}$ containing $E^{NP}$ such that it is known unconditionally that $\mathcal{C}\nsubseteq SIZE[n]$?
What is a good reference for relations between uniform and non-uniform circuit classes?


texts: Clique-Percolation Algorithm's "corner cases"

texts:
I'm programming an implementation of the Clique-Percolation algorithm, but I have many doubts about some corner cases.

Imagine we want to find the communities of a graph using $k=4$. We are lucky and every node in the graph belongs at least to one k-clique (with $k \geq 4$). So it's trivial to apply the algorithm by hand (slow, but trivial).

Now imagine we add three more nodes to the graph, creating a 3-clique, and connecting this clique to the previous existing nodes with only 1 edge.

It's here where I have problems to understand what's expected of the Clique Percolation algorithm.

I have to add a new community for each new node? Only a new non-overlapping community matching the 3-clique? Nothing (not considering the new nodes in any community)?

Example initial graph:
$$
A \leftrightarrow B \\
A \leftrightarrow C \\
A \leftrightarrow D \\
B \leftrightarrow C \\
B \leftrightarrow D \\
C \leftrightarrow D \\
$$

Modified graph:
$$
A \leftrightarrow B \\
A \leftrightarrow C \\
A \leftrightarrow D \\
B \leftrightarrow C \\
B \leftrightarrow D \\
C \leftrightarrow D \\
D \leftrightarrow E \\
E \leftrightarrow F \\
E \leftrightarrow G \\
F \leftrightarrow G
$$

thanks for your time.


texts: Who said: "There is no central arbiter of truth in open distributed systems."

texts:
Can anyone give me a reference to the origin of the statement "There is no central arbiter of truth in open distributed systems."

Possibly it was Carl Hewitt in "The Challenge of Open Systems" Byte Magazine. April 1985. Can anyone confirm this?

Thanks


texts: How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction?

texts:
The following question was first presented in MATHEMATICS of StackExchange. With a simple description at first sight, it has far-reaching consequences on plenty of recent and advanced theories, such as Knowledge and Common Knowledge in game theory, logic, and distributed computing. With many excellent answers from MATHEMATICS (with my gratitude), it is still somewhat mysterious to me. So, I am here for more illumination.

Below is the original source from MATHEMATICS for your convenience.

Hua Luogeng (in Chinese, 华罗庚) took a hat-guessing puzzle as an illustration in a booklet focusing on mathematical induction. The following description is a literal translation from Chinese.

  Hat-Guessing Puzzle: A teacher wants to identify the most smartest one from his three students by the following methods: 5 hats are shown, in which 3 of them are white and the other two are black, to the three students. With eyes closed, each student is put on a white hat, while the other two black ones are hidden. Once the permissions of opening eyes are granted, the three students open their eyes simultaneously and are allowed to look at the hats of others without any communication. After a hesitation, they say that "the hat on my own hat is white" with one voice. The question is how do they make it?

The puzzle can be easily generalized to the version with $n$ persons, $n-1$ black hats, and $\ge n$ white hats and be solved by induction on $n$:

When $n$ is 2, the situation is trivial because there is only one black hat. If I am wearing the black one, then the other person can tell that the hat on his head is white, without any hesitation. However, he does hesitate. Contradiction.
Suppose that we have solved the puzzle with $n = k$.
When $n = k + 1$, the reason goes in the following way: If someone is wearing the black hat, all the other people will know that and the problem is reduced to a version with $k$ person, $k-1$ black hats and $\ge k+1$ white hats. According to the inductive hypothesis, the $k$ persons should tell that the hats on their heads are all white, without any hesitation. Contradiction.

While both the puzzle and proof sound very simple, I am very confused with the informal keyword "hesitation" in them. I even cannot tell the vagueness of hesitation clearly. For example, is the hesitation itself a suitable object which can be used in mathematical induction? Informally, my problem can be stated as follows.

  My Problem: How to formally model the hesitation in the hat-guessing puzzle?

Now, I will give an account of my confusion (after the discussion with MATHEMATICS users).

Is it suitable to model the hesitation in terms of rounds? Just like the Muddy Children Puzzle, the teacher can broadcast the following question over and over: What is the color of your hat? If the modeling is OK, is it still on the right way to prove the following statement (for the version with $n$ students) "in the first $n−1$ rounds they all say I don't know, and in the $n$th round, they all say it is white simultaneously"?
I think the statement "If someone is wearing the black hat" given in the original proof is based on the unjustified assumption about the first $n−1$ rounds. In other words, is it necessary to prove first "in the first $n-1$ rounds they all say I don't know", before proving the thing in the $n$th round? If it is, how to prove the $n-1$ part?

Thank you very much for any suggestions.


texts:
Angluin's membership+equivalence query algorithm allows to efficiently and exactly learn a target $n$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular language -- can we still learn a small DFA that approximates the target concept well?

Here's the formal setting. We have a target concept $f^\star$ and distribution $D$ over $\Sigma^*$. A membership query $MQ:\Sigma^*\to\{0,1\}$ returns the value of $f^\star(x)$. An "accuracy query" $AQ$ takes a DFA $f$ as input and returns
$$\mathrm{err}(f):=\sum_{x\in\Sigma^*}D(x)\boldsymbol{1}[f(x)\neq f^\star(x)]$$ a output.

The goal is to efficiently produce a small (up to $n$-states) DFA $f$ with small (or minimum) $\mathrm{err}(f)$ using the oracles $MQ$ and $AQ$. [A trivial solution is to brute-force search over all $n$-state DFAs.]

Have similar problems been considered in the literature? Pointers much appreciated. What is the status of the learning problem I posed?

Edit: It was pointed out off-line that for parity-type concepts, $\mathrm{err}(f)$ might be close to $1/2$. So to clarify:
the question seeks not a bound on the worst-case $\mathrm{err}(f)$,
but rather an efficient procedure of attaining it via an $n$-state DFA.


texts: Adherence of languages and the Dyck language

texts:
Let $L \subseteq X^*$ and $X = \{a,b\}$ be a language of finite words, denote by $A(u)$ the prefixes of some word (finite or infinite), then the adherence $\mbox{Adh}(L)$ is defined to be the set of infinite words such that
$$
 \mbox{Adh}(L) = \{ \xi \in X^{\omega} : A(\xi) \subseteq A(L) \}
$$
i.e. the set of infinite words all of whose prefixes are prefixes of some words from $L$. Also
write $u \le v$ if $u$ is a prefix of $v$. Define the Dyck language as
$$
 D = \{ v \in X^* : |v|_a = |v|_b \mbox{ and } \forall w \le v : |w|_a \ge |w|_b \}.
$$
Examples of words from $D$ are: $ab, abaabb, aabbab$. Then it is claimed that
$$
 \mbox{Adh}(D) = \{ \xi \in X^{\omega} : \forall v < \xi : |v|_a \ge |v|_b \}.
$$
Note that if this holds then $aaba^{\omega}$ should be in $\mbox{Adh}(D)$. I wanted to proof that claim, therefore I use the property of Adh:
$$
 \mbox{Adh}(L^*) = L^* \cdot Adh(L) \cup L^{\omega}.
$$
And define a "strict" Dyck-language $D_s := \{ a^nb^n : n \ge 0 \}$, then $D = (D_s)^*$.
It is
$$
 \mbox{Adh}(D_s) = \{ a^{\omega} \}
$$
because $A(D_s) = \{ \varepsilon, a, ab, aa, aab, aabb, \ldots \} = \{ a^i b^j : i \ge j \}$ and just the subset $a^*$ fulfills the property that there exists an infinite word $\xi$ with $A(\xi) = a^*$, for $a^ib^j$ with $j > 0, i \ge j$ just has a finite number of completions $w$ such that $a^ib^jw \in A(D_s)$ (namely by $w = \varepsilon, b, bb, \ldots, b^{i-j}$) and so could not be the set of prefixes of some infinite word (the set $A(\xi)$ for infinite $\xi$ has two properties, 1) it is infinite and 2) the words could be lineary ordered according to the prefix relation, by 2) it is enough to look at some $a^ib^j$ and see of what words from $A(D_s)$ it is a prefix of).

Now using the property it is
$$
 \mbox{Adh}(D) = \mbox{Adh}(D_s^*) = D_s^* \cdot Adh(D_s) \cup D_s^{\omega} = D_s^* a^{\omega} \cup D_s^{\omega}.
$$
But the word $aaba^{\omega}$ is not an element of this language, contradicting the first claim? Might the claim be false, or is there some flaw with my proof, I don't see it, maybe you can help?

PS: The claim (unproved) as well as the properties of the Adh-Operator is from the famous and often cited paper Adherences of Languages, which introduces those notions, so I think the claim is correct.


texts: Graph coloring minimizing the number of colors in every independent set

texts:
Is the following claim known?

Claim: For any graph $G$ with $n$ vertices there exists a coloring of $G$ such that every independent set is colored by at most $O(\sqrt{n})$ colors.


texts: Making SAT solvers competitive with specialized algorithms

texts:
What are obstacles to making SAT solvers competitive with specialized graph algorithms? In other words, is it feasible to expect SAT solvers that can replace the role of algorithm designer -- ie, be able to automatically recognize problem structure and then solve it as quickly as a specialized algorithm?

Here some examples I think are challenging for today's SAT solvers:

Counting independent sets of size $k$. Encoding "x is an independent set of size k" gives a large formula which is hard to solve. An ideal SAT solver would recognize that this problem is easy on bounded tree-width graph with an addition of an extra "count" variable for bags.
Finding minimum Steiner tree. Again, "Steiner tree" has a global constraint, however, a specialized algorithm (like here) makes the task easier by adding an extra variable
Any problem that reduces to planar perfect matchings.


texts: Is it possible to include an optimization algorithm's own running time in the cost?

texts:
Fix $f(\_; \_)$, which represents a class of optimization problems, ie, for a specific $P$, $f(\_; P)$ is a function we'd like to optimize.

Now, we have an algorithm $A$ that takes as input $P, a, b$, runs for $t$ CPU cycles, and outputs $x$ such that $a{\cdot}f(x; P) + b{\cdot}t$ is minimized.

edit (much cut): As Sasho points out, it is very tricky to define in what sense $A$ "minimizes" $a{\cdot}f(x; P) + b{\cdot}t$. I'm pretty convinced now that the criterion I gave earlier (see older version of this question) is no good. Let me try a different one similar to the one from the notes Sasho linked to.

Let $\mathcal{A}$ be the set of algorithms that take in $a, b, P$ and give out some $x$. Also say that the $P$s have "sizes" which are integers.

Say then that $A$ is optimal iff for every $A' \in \mathcal{A}$ and $a, b \in R$ there exists an $N \in Z$ such that

  $\forall{n} \ge N, ~~ \operatorname*{max}_{P \text{ with size ≤ n }}\{a{\cdot}f(x_P; P) + b{\cdot}t\} \leq \operatorname*{max}_{P \text{ with size ≤ n }}\{a{\cdot}f(x'_P; P) + b{\cdot}t'\}$

where $x, t$ are the result and running time of $A(a,b,P)$ and $x', t'$ are the result and running time of $A'(a,b,P)$.

Maybe that will work, not sure. Let me give an example.

Example: Say we take the problem of finding the smallest element in a list. Say we are given a list of size $n$, which we know contains some permutation of $1 ... n$, and we are asked to give an index at which lies a value that is as small as possible (ie, if the list were $[2, 1, 3]$ the best we could output would be $2$, then $1$, then $3$).

Say accessing the list (random access) takes $1$ step, everything else takes $0$ steps. Now our algorithm ($A$) will be:

If a > b:
    Search through the list 1 by 1 looking for the number 1,
    then output that index.
Else:
    Output 1.

For a list of size $\leq n$, the worst this can do is $min(a + b{\cdot}(n-1), a{\cdot}n)$ (note that the comparison, somewhat unrealistically, takes no time). Any algorithm guaranteed of finding a value no less than $k$ must see at least $n - k$ elements of the list, giving a worst-case score of $a{\cdot}k + b{\cdot}(n - k)$. Differentiate that wrt $k$ gives $a - b$, and substituting $1$ or $n$ for $k$ gives $a + b{\cdot}(n-1)$ or $a{\cdot}n$ respectively, so by induction $A$ scores at least as well. So, according to the above optimality constraint, $A$ is optimal.

Question: Does this problem, of including both an algorithm's own running time, and the result of another problem, in its score, have a name? Or does something similar have a name? Can such an algorithm usually exist in theory? Any other information I could check out?

(This question was inspired by a friend of mine who's computer freezes up for several minutes when he runs optimization algorithms).


texts: Nondeterministic linear time vs. the deterministic time hierarchy

texts:
How much is known about nondeterministic linear time?  I'm aware that $$ \mathrm{NTIME}(n) \neq \mathrm{DTIME}(n).$$
Is there an $m > 1$ so that $\mathrm{NTIME}(n) \not\subset \mathrm{DTIME}(n^m)$?  Are there any arguments that $\mathrm{NTIME}(n) \subset \mathrm{P}$ should be unlikely?


texts: Why use two separate tables in cuckoo hashing?

texts:
I've been reading a number of papers on cuckoo hashing, including several that generalize it by talking about cuckoo hashing with multiple tables, cuckoo hashing with a stash, the (multi)graph-theoretic properties of the cuckoo graph, etc. However, I have not seen any papers discuss why cuckoo hashing typically separates out the slots into distinct tables rather than having one larger table with multiple hash functions indexing into it (though I did come across a set of lecture notes aimed at undergraduates where this simplification is used).

Is there any particular reason for this?


texts: Is $\mathsf{MA}$ equal to $\mathsf{NP}^\mathsf{RP}$?

texts:
I haven't been able to find a statement relating $\mathsf{MA}$ and $\mathsf{NP}^\mathsf{RP}$ in the literature; pointers would be appreciated.

I believe they are equal:

$\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP}$:
The $\mathsf{NP}$ machine guesses Merlin's string, and the $\mathsf{RP}$ oracle verifies the string as Arthur would.
$\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA}$:
Merlin guesses the accepting computation of the $\mathsf{NP}$ machine, including all calls, as well as the outcomes of these calls, to the $\mathsf{RP}$ oracle. Arthur then verifies that the computation is valid and that all the guessed outcomes of calls to the $\mathsf{RP}$ oracle were correct. He uses amplification and union bounds to bound the overall total probability of error.

Is this correct?


texts: Complexity class separation in the presence of relativization barriers

texts:
Give an example of complexity classes $M$ and $N$ and oracles $A$ and $B$ such that
 1. $M^A=N^A$ and
 2. $M^B\neq N^B$ and
 3. $M \neq N$.


texts:
Natural proofs paper shows 'if there is a natural property not possessed by any function in P/poly then there is no $2^{n^\epsilon}$-hard PRG'.

Is it easy to see the converse 'if there is no $2^{n^\epsilon}$-hard PRG then there is a natural property not possessed by any function in P/poly'.

The reason I seek is following. Even if SAT and $\#$SAT have $2^{O(2^{\sqrt{\log n}})}$ randomized algorithms then P is not NP is still possible. However in this case there is no $2^{n^\epsilon}$-hard PRG at any $\epsilon>0$. Then in this situation would it be possible to prove NP is not in P/poly by a natural proof?


texts: Nondeterministic communication complexity of Hamming distance

texts:
It is something that I think should be known:
what is nondeterministic communication complexity of following task:

is $H(x,y) \geq k$?

There is an obvious upper bound $k \log(n)$. I would expect this to be tight up to a $o(\log(n))$ additive term (for small $k$). Is this known?


texts: What is the precise definition of Random K-SAT?

texts:
There are 4 different constraints we can have when defining Random K-SAT. 1)Total number of literals in a given clauses is exactly K or AT most K
2)A given literal can be used with or without replacement in the same clause (A or A or A)
3)A given variable can be used with or without replacement in the same clause (A or ~A or ~A)
4)A given clauses can be used with or without replacement in a given formula
What would be the most "correct" definition? What are the cons and pros of using these different definitions?


texts: Looking for reference on NP-Completeness of proofs of length n

texts:
Given a deductive system $\Lambda$, and some well-formed-formula S, one can ask the question "Is there a proof S in $\Lambda$ of length n?"  If n is presented in base-1 and if all the axioms of $\Lambda$ are polynomial-time verifiable, and if $\Lambda$ is sufficiently powerful to express the verification for some NP-Complete problem like 3-SAT, this problem is known to be NP-Complete.  It requires super-polynomial time if n is not.

I know how to prove this, but I am also sure that somebody else has already proven this.  Can somebody direct me to an existing published reference?


texts: What is the time complexity of increasing the precision of finding matrix eigenvalues?

texts:
There are various algorithms that output the eigenvalues of an $n \times n$ matrix in time $O(n^3)$. However, I can't find anywhere that tells me about the precision of the output of the algorithm. That is, what is the time complexity of increasing the number of bits I require the answer to?

Furthermore, how does this rely on the number of bits we use to specify the initial matrix? For example, if I specify the matrix elements to exponential precision in $n$.

Any starting point for this would be helpful.


texts: Simulate a process of state change with transition probability dependent on proportion in state in previous time

texts:
I was thinking about a reverse single transferable vote type situation (i.e. most votes is eliminated) where the process continues until there is only on state left and at each new round there really is a new vote. My suspicion is that this could be modelled by assuming like:

50% to most similar (remaining) state, 25% to next most similar state, 25% to next most similar state if present state is the most populous state

or

90% current state; 10% most similar state

This means that for each time period the number of states is reduced by one and presumes people opt for options most similar to their preference in the previous time period. That latter character reminds me in particular of Markov chains.

I would like to know how to think about doing this or what search terms would help to find someone else who has already tried this.

My instinct that it would be a bit like if you had for t=1, n=20 bins that marbles had fallen into and then count the number of marbles in each bin. For t=2, there are still n=20 bins but the most populated bin from the previous example has a 0% destination probability for all other bins/states and the destination probabilities for the other bins depend on their relationships to each other and, in particular, the "losing" bin. And the for t=3 there are now two bins with destination probabilities of 0% and so on... Being able to look at the situation for each t would be important, too.

Any language would be greatly helpful in a conceptual sense, but on a personal level I have even a cursory understanding of just R (but also some experience with and access to SAS and a bit less again, on both counts, with Stata).

Thank you (and apologies if this is in the wrong place).


texts: Easy instances for coset intersection problem

texts:
Coset Intersection Problem

Given : $K,H \le S_n$, and $\sigma \in S_n$

Find : $K \cap H\sigma$

Known results are :

$n^{O(\sqrt n )}$ time algorithm by L.Babai.
$n^{O(1)} m^{O(\sqrt m )}$, where $m$ is the length of the longest orbits of the two groups by L.Babai.
exp ($O(\sqrt n \ log n))$ by L.Babai.

Problem is in $\mathsf{P\text{}}$, if subgroup $K$ is a $S_n$ or just identity element. My question is what are the other cases, where problem is easy to solve i.e. is in $\mathsf{P\text{}}$.


texts: Justifying asymptotic worst-case analysis to scientists

texts:
I've been working on on introducing some results from computational complexity into theoretical biology, especially evolution & ecology, with the goal of being interesting/useful to biologists. One of the biggest difficulties I've faced is in justifying the usefulness of asymptotic worst-case analysis for lower bounds. Are there any article length references that justify lower bounds and asymptotic worst-case analysis to a scientific audience?
I am really looking for a good reference that I can defer to in my writing instead of having to go through the justifications in the limited space I have available (since that is not the central point of the article). I am also aware of other kinds and paradigms of analysis, so I am not seeking a reference that says worst-case is the "best" analysis (since there are settings when it very much isn't), but that it isn't completeletely useless: it can still gives us theoretically useful insights into the behavior of actual algorithms on actual inputs. It is also important the writing is targeted at general scientists and not just engineers, mathematicians, or computer scientists.
As an example, Tim Roughgarden's essay introducing complexity theory to economists is on the right track for what I want. However, only sections 1 and 2 are relevant (the rest is too economics specific) and the intended audience is a bit more comfortable with theorem-lemma-proof thinking than most scientists[1].

Details
In the context of adaptive dynamics in evolution, I've met two specific types of resistance from theoretical biologists:
[A] "Why should I care about behavior for arbitrary $n$? I already know that the genome has $n = 3*10^9$ base pairs (or maybe $n = 2*10^4$ genes) and no more."
This is relatively easy to brush-off with the the argument of "we can imagine waiting for $10^9$ seconds, but not $2^{10^9}$". But, a more intricate argument might say that "sure, you say you care about only a specific $n$, but your theories never use this fact, they just use that it is large but finite, and it is your theory that we are studying with asymptotic analysis".
[B] "But you only showed that this is hard by building this specific landscape with these gadgets. Why should I care about this instead of the average?"
This is a more difficult critique to address, because a lot of the tools people commonly use in this field are coming from statistical physics where it is often safe to assume a uniform (or other specific simple) distribution. But biology is "physics with history" and almost everything isn't at equilibrium or 'typical', and empirical knowledge is insufficient to justify assumptions about distributions over input. In other words, I want an argument similar to that used against uniform distribution average-case analysis in software engineering: "we model the algorithm, we can't construct a reasonable model of how the user will interact with the algorithm or what their distribuition of inputs will be; that is for psychologists or end users, not us." Except in this case, the science isn't at a position where the equivalent of 'psychologists or end users' exists to figure out the underlying distributions (or if that is even meaningful).
Notes and related questions

The link discusses cognitive sciences, but the mindset is similar in biology. If your browse through Evolution or Journal of Theoretical Biology, you will seldom see theorem-lemma-proof, and when you do it will typically be just a calculation instead of something like an existence proof or intricate construction.
Paradigms for complexity analysis of algorithms
Other kinds of running time analysis besides worst-case, average-case, etc?
Ecology and evolution through the algorithmic lens
Why economists should care about computational complexity


texts: Why can a Predictive Parser contain E' -> TE' | ε

texts:
I am studying the basics of predictive parsing and I think I have missed a concept that I would like to understand instead of just accepting and memorizing. I am watching this video and I am confused as to why

E' -> TE' | ε is valid

because

E -> E + T is not valid since we have "left recursion" (a variable that calls itself).

in other words, why doesn't E' -> TE' | ε or T' -> *FT' have left recursion? To me it looks a lot like E' and T' are calling themselves.


texts: Are there intermediate eta theories for the lambda calculus?

texts:
There are two main, studied theories of the lambda calculus, the beta theory and its Post-complete extension, the beta-eta theory.

Do these two theories have an in-between, a kind of intermediate eta rule that gives a confluent rewrite theory?  Is there some interesting notion of partial extensionality that it corresponds to?

This is the second question I have asked in pursuit of intermediate eta, the previous being Extensions of beta-theory of lambda calculus, which led to question about an orthogonal notion of extension, Characterising invisible equivalences by confluent rewrite rules, which sought to clarify an answer to that earlier question.


texts: Minimal elements of a monotonic predicate over the powerset $2^{|n|}$

texts:
Consider a monotonic predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking for an algorithm to find all the minimal elements of $P$, i.e., the $x \in 2^{|n|}$ such that $P(x)$ but $\forall y \subset x$, $\neg P(y)$. Since the width of $2^{|n|}$ is $n \choose n/2$, there could be exponentially many minimal elements, and therefore the running time of such an algorithm could be exponential in general. However, could there exist an algorithm for this task which is polynomial in the size of the output?

[Context: A more general question was asked but there was no attempt in the answers to evaluate the complexity of the algorithm in the size of the output. If I assume that there is only one minimal element, for instance, then I can perform a binary search following this answer and find it. However, if I want to continue finding more minimal elements, I need to maintain the current information I have about $P$ in a way which would make it tractable to continue the search without wasting time on what is already known. Is it possible to do this and find all the minimal elements in polynomial time in the size of the output?]

Ideally, I would like to understand if this can be done with general DAGs, but I already don't know how to answer the question for $2^{|n|}$.


texts: Expected value of a random experiment in a graph

texts:
I need to find the expected value of R in the random experiment below.
$$
R = \frac{1}{K} \sum_{C \in \mathcal{H} } \ [\frac{1}{2} |V(C)| * (|V(C)| - 1) - |C|]
$$
$\mathcal{H}$ is a partition on edges, such that each edge belongs to one and only one community C. V(C) is all the nodes touched by one or more edges in C. K is a constant.
In other words: R is the sum of the number of node-pairs in each V(C) that does not have an edge between them belonging to C.

The random experiment is as follows:

We start out with some partition $\mathcal{H}$, with edge-communities C. We then keep the nodes and the size of the edge-communities but randomly assign the edges of each community to nodes. The resulting partition will have edge-communities of the same size as $\mathcal{H}$ but the edges will be randomly placed so V(C) will change.

How can I find the expected value? I have tried to find the expected value of V(C), but I don't think it helps since $E[ |V(C)|*(|V(C)| -1)] \neq E[|V(C)|]*E[|V(C)| - 1]$.


texts:
I'm reading through "Type Theory & Functional Programming" by Simon Thompson and it says

  We shall not distinguish between expressions which are equivalent up to change of bound variable names in what follows. (As an aside, this convention which is easy to state, and indeed for us to follow, is surprisingly difficult to implement.)

This seems quite straightforward to implement though:

Given two sets $\Gamma_1$ and $\Gamma_2$, where $\Gamma_1$ = $\Gamma_2$ = $\varnothing$, a $\lambda$-expression $e_1$ is $\alpha$-equivalent to a $\lambda$-expression $e_2$ (that is, $(e_1, \Gamma_1) \equiv_\alpha (e_2, \Gamma_2)$) iff

$e_1$ and $e_2$ are variables and $e_1 \in \Gamma_1$ and $e_2 \in \Gamma_2$
$e_1 \equiv (e_1'e_1'')$ and $e_2 \equiv (e_2'e_2'')$ are applications and $(e_1', \Gamma_1) \equiv_\alpha (e_2', \Gamma_2)$ and $(e_1'', \Gamma_1) \equiv_\alpha (e_2'', \Gamma_2)$
$e_1 \equiv (\lambda x_1.e_1')$ and $e_2 \equiv (\lambda x_2.e_2')$ are abstractions and $(e_1', \Gamma_1 \cup x_1) \equiv_\alpha (e_2', \Gamma_2 \cup x_2)$

Is there something wrong with my interpretation of the problem and consequent answer or is the author simply misinformed?


texts: What are the hardness results known for CSP over $\mathbb{F}_q$?

texts:
I found two related papers,

There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf
A kind of a stronger result might be found in these two other papers, http://www.csc.kth.se/~austrin/papers/maxkcsp_full.pdf and http://eccc.hpi-web.de/report/2012/110/download/
There is an approximation threshold with respect to Lasserre rounds here,
http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf

Are there other important papers in this topic? Like has anyone shown SOS hardness for this? (I don't see a way to dualize Madhur's Lasserre results to get that!) I would be glad to know what other papers in this topic should one look up.


texts: Difference between NP-Hard and NP-Complete

texts: Can someone please summarize the exact difference between NP-Complete and NP-Hard problems in simple language? Wiki and my standard books aren't exactly helping.


texts: Should reductions make us more or less optimistic for the tractability of a problem?

texts:
It seems to me that most complexity theorists generally believe the following philosophical rule:

  If we can't figure out an efficient algorithm for problem $A$, and we can reduce problem $A$ to problem $B$, then there probably isn't an efficient algorithm for problem $B$, either.

This is why, for example, when a new problem is proved NP-Complete we simply file it away as "too hard" rather than getting excited about a new approach (problem $B$) that might finally show $P = NP$.

I was discussing this with a fellow grad student in another scientific field.  She found this idea hugely counterintuitive.  Her analogy:

  You're an explorer, searching for a bridge between the North American and Asian continents.  For many months you have tried and failed to find a land bridge from the mainland United States area to Asia.  Then you discover that the mainland US is connected by land to the Alaskan area.  You realize that a land bridge from Alaska to Asia would imply a land bridge from the mainland US to Asia, which you're pretty sure doesn't exist.  So you don't waste time exploring near Alaska; you just go home.

Our previous philosophical rule sounds pretty silly in this context.  I couldn't think of a good rebuttal!  So I'm turning it over to you guys: Why should we treat a reduction $A \to B$ as making problem $B$ harder rather than making problem $A$ easier?


texts:
Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps?

For rectangular maps, for example, I intend maps that are made from overlapping rectangular faces as shown here: Rectangular and circular maps.
And here is the proof.

I don't know if this is a new result or not (I did not find it on internet) and I don't even know if this may be useful to help finding a "pencil and paper", elegant and human checkable proof for the four color problem.

What is known about this? Has it been studied before?


texts: NEXPTIME-completeness with more time for reductions

texts:
One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large complexity class.

This definitely makes sense for P and NP, but how about EXPTIME and NEXPTIME?

So my question is this: What is the subset of NEXPTIME comprised of problems exp-time reducible from every other problem in NEXPTIME? If EXPTIME != NEXPTIME, is this class distinct from both NEXPTIME and NEXPTIME-complete?


texts:
If I must connect: $$2^k$$ terminals in a Steiner Tree choosen randomly and connect them with the cheapest component; "loss - contracting algorithm" is a good way? Or is an "Iterative Randomized Rounding" more appropriate? At the end the cost of minimum spanning tree should be: $$c(T)<=1+(1/k)$$

Thanks


texts: Is there a linear-time algorithm for max flow on dags

texts:
What is the fastest known algorithm for max flow on dags?
Can there be a linear-time algorithm running in time $O(|V|+|E|)$?

Input: a weighted dag $G=(V,E,w)$ where
$E$ is given as an edge list $E$ and
$w$ is the edge weight function; and
two vertices $s$ and $t$.

Output: a max flow from $s$ to $t$.

The dag is simple (no loops, no parallel edges).
Edge weights are positive integers.


texts: Is $\mathrm{DTISP}(n^a,n^b) \subseteq \mathrm{DSPACE}(n^{b/2})$?

texts:
The title question arose in the course of discussing a question on MathOverflow.  Obviously, from the space hierarchy theorem we know that not only is it false that $\mathrm{DSPACE}(n^b) \subseteq \mathrm{DSPACE}(n^{b/2})$, but there is a proper inclusion in the other direction.  But once we limit the time budget of the left-hand side to $n^a$, I'm no longer sure what we can say.

If the question can't be answered unconditionally, then can we answer it conditional on some standard hypothesis or relative to some oracle?


texts: How much memory is needed for counting distinct elements in a stream exactly with high probability

texts:
Assume we know a parameter $n\in\mathbb N$, and then get to observe a sequence of elements $x_1,\ldots, x_n$, one at a time.

Our goal is to count the number of distinct elements in $x_1,\ldots, x_n$, and succeed with probability $1-\epsilon$.

A simple approach would be to compute a $\log\left({n\choose 2}\epsilon^{-1}\right)$ bits fingerprint of each element, and then count the number of distinct fingerprints.

Since the number of distinct elements is a most $n$, with probability of at least $1-\epsilon$, all fingerprints of distinct elements will be different.

This gives us a total of $\approx n\log (n^2\epsilon^{-1})-n$ bits of space.

But is this anywhere close to optimal? Can we perhaps use only $O(n\log\epsilon^{-1})$ bits for the problem? What would be a lower bound for this problem?

EDIT: I'm specifically interested in computing the number of distinct elements exactly, with high probability, and not in approximation algorithms.

In the paper An Optimal Algorithm for the Distinct Elements Problem, the authors give a $O(\gamma^{-2}+\log n)$ bits algorithm for computing a $(1+\gamma)$ approximation with high probability, and claim that this is optimal.

However, setting $\gamma<n^{-1}$ for getting exact count with high probability gives a $\Omega(n^2)$ bits algorithm, which seems worse than the $O(n\log n)$ proposed above.

They do not assume that $n$ is known in advance, which may explain this difference.


texts: Is there any triangle-free, star-cutset-free, circle graph, with more than n edges?

texts:
I'm trying to find a graph with those properties for my studies, but unfortunately I can't find such graph.

Does anyone know if there is that graph, or why is it impossible to exist?


texts: Indications that strengthen the conjecture: NEXP ⊊ EXP^NP

texts:
I am trying to find indications that strengthen the conjecture of NEXP ⊊ EXP^NP.

Clearly NEXP ⊆ EXP^NP, and there are some hints that this inclusion is proper.

Some Examples:
1.  A paper by Shuichi Hirahara: “Identifying an honest EXP^NP oracle among many”, which states that “No instance checker for EXP^NP -complete languages exists unless EXP^NP = NEXP” https://arxiv.org/abs/1502.07258

A paper by Laszlo Babai, Lance Fortnow and Carsten Lund: “NON-DETERMINISTIC EXPONENTIAL TIME HAS TWO-PROVER INTERACTIVE PROTOCOLS” which states that we do not know whether NEXP provers are sufficient to prove any NEXP language to a verifier, but the best upper bound we know on the power of the provers for NEXP is EXP^NP
http://people.cs.uchicago.edu/~fortnow/papers/mip2.pdf

Are there any additional known results on the conjecture of NEXP ⊊ EXP^NP?
What are its implications on the separation of other classes?

Thanks


texts:
The Walsh-Hadamard transform (WHT) is a generalization of the Fourier transform, and is an orthogonal transformation on a vector of real or complex numbers of dimension $d = 2^m$. The transform is popular in quantum computing, but it's been studied recently as a kind of preconditioner for random projections of high-dimensional vectors for use in the proof of the Johnson-Lindenstrauss Lemma. Its main feature is that although it's a square $d\times d$ matrix, it can be applied to a vector in time $O(d \log d)$ (rather than $d^2$) by an FFT-like method.

  Suppose the input vector is sparse:
  it has only a few nonzero entries (say
  $r \ll d$). Is there any way to
  compute the WHT in time $f(r,d)$ such
  that $f(d,d) = O(d \log d)$ and
  $f(r,d) = o(d \log d)$ for $r = o(d)$
  ?

Note: these requirements are merely one way of formalizing the idea that I'd like something that runs faster than $d \log d$ for small $r$.


texts: A sequence wherein the Kolmogorov complexity of the terms does not increase

texts:
I am looking for an algorithm $A$ - which for any non-null  input  string $s_1$ produces a sequence     $s_1, s_2...$ such that :

  It can be proved in some axiomtic system $S$ that:           $\forall j> i; K(s_j) \ngtr K(s_i)$;                                                        K(s) being the Kolmogorov complexity of string
  $s$.

  ie complexity of terms in the sequence does not increase.
  For any given $ s_1 , \not\exists $ Algorithm B  such that $ |A| >|B| $ and given $m,n$: B can decide "$|s_m|>|s_n|$"

  ie There does not exist any algorithm B with program length less than A which can decide, given any two indices, which one the terms at those indices is smaller.


texts: What is it the relationship between the number of support vectors in an SVM and its generalization ability?  When lots of support vectors are used to classify, is the error rate minimized, but only to certain threashold?


texts: Can words in regular languages be generated by automata in a unique way?

texts:
If $L\subset \Sigma^\ast$ is a regular language then it is known that we can find a directed graph (aka automaton) $G$ with edges labelled with symbols from $\Sigma$, an ‘initial’ vertex, and a set of ‘terminal’ vertices, with the property that a word $w$ is in $L$ iff $w$ is the sequence of edge labels along a path from the initial vertex to a terminal vertex.

It’s possible that the same word can appear as a result of different paths in $G$. Can we guarantee that for any regular $L$ we can find a $G$ such that each word in $L$ appears as a path in $G$ in a unique way?

(I’m interested in this because I want to know whether the solution to the problem I worked on here applies cleanly to any regular language, or just for a certain class of them.)


texts:
What are the compelling reasons for believing $L\neq P$? L is the class of log-space algorithms with pointers to the input.

Suppose L=P for the moment. What would a log-space algorithm for a P-complete problem look like in its general outlines?


texts: Complexity for single-linkage clustering with max norm

texts:
Let $S\in\mathbb Z^d$ be a set of points, with some notion of distance $d(x,y)$ between two points $x,y\in S$. I am specifically interested in the max distance, that is $d(x,y)=\max_{1\le i\le d} |x_i-y_i|$ where $x=(x_1,\dotsc,x_d)$ and $y=(y_1,\dotsc,y_d)$.

Single-linkage clustering consists in computing a tree $T$ on the set $S$ of minimal distances, that can be defined by the following algorithm that computes the set $E$ of edges of $T$ as follows:

Set $E=\emptyset$ [each point is a cluster]
While $|E|<|S|-1$, add to $E$ a pair $(x,y)$ such that

$x$ and $y$ are in distinct connected components of $T$;
$d(x,y) = min_{u,v} d(u,v)$ where the minimum is taken over all pairs of points $u$, $v$  that are in distinct connected components of $T$.

If one first computes all the distances between pairs of points in $S$ and sort them, the above algorithms allows to compute the tree $T$ in time $\tilde O(n^2)$ if one assumes that the distance can be computed in time $O(1)$. Here the notation $\tilde O(\cdot)$ hides poly-logarithmic factors.

  What is the complexity of computing this tree, when the distance is the max distance?

  If $d=2$, is there a quasi-linear algorithm (that is in time $\tilde O(n)$)?
  More generally, if $d$ is fixed, is there a quasi-linear algorithm?
  Or is there a quadratic lower bound (in some reasonable model)?

Note: I asked a similar question some days ago on cs.sx. I had no answer, so I re-post it here with a new (and I guess better) formulation.


texts: How much would a SAT oracle help speeding up polynomial time algorithms?

texts:
Access to a $SAT$ oracle would provide a major, super-polynomial speed-up for everything in ${\bf NP}-{\bf P}$ (assuming the set is not empty). It is less clear, however, how much would $\bf P$ benefit from this oracle access. Of course, the speed-up in $\bf P$ cannot be super-polynomial, but it can still be polynomial. For example, could we find a shortest path faster with a $SAT$ oracle, than without it? How about some more sophisticated tasks, such as submodular function minimization or linear programming? Would they (or other natural problems in $\bf P$) benefit from a $SAT$ oracle?

More generally, if we can pick any problem in ${\bf NP}-{\bf P}$, and use an oracle for it, then which of the problems in $\bf P$ could see a speed-up?


texts:
Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two permutations. Unfortunately, I don't see a straightforward reduction from the permutation sum problem and it is useful to have the $NP$-completeness reduction for the permutation difference problem.

Permutation Difference:

INSTANCE: An array $A[1...n]$ of positive integers.

QUESTION: Do there exist two permutations $\pi$ and $\sigma$ of the positive integers $1,2, ... , n$ such that $|\pi(i) - \sigma(i)| = A[i]$ for $1 \le i \le n$ ?

  What is the reduction for proving the $NP$-completeness of recognizing the difference of two permutations?

EDIT 10-9-2014: Shor's comment gives a reduction which proves $NP$-completeness when the elements of sequence $A$ are signed differences. However, I don't see an easy reduction to my problem where all elements of $A$ are the absolute values of differences.

UPDATE: The Permutation Difference problem seems to be $NP$-complete even if one of the two permutations is always the identity permutation. Hardness proof of this special case is very welcome. So, I am interested in $NP$-completeness of this restricted version:

Restricted Permutation Difference:
INSTANCE: An array $A[1...n]$ of positive integers.

QUESTION: Does there exist a permutation $\pi$ of the positive integers $1,2, ... , n$ such that $|\pi(i) - i| = A[i]$ for $1 \le i \le n$ ?

Update 2: The restricted problem is efficiently decidable as shown by mjqxxxx's answer. The computational complexity of the original problem is not proven.

EDIT 9/6/16: I am interested in determining whether this simplification of Permutation Difference is NP-complete:

Restricted Permutation Difference:

INSTANCE: A multiset $A$ of positive integers.

QUESTION: Does there exist a permutation $\pi$ of the positive integers $1,2, ... , n$ such that  $A= \{|\pi(i) - i| :1 \le i \le n\}$ ?


texts: How can I reduce this kind of BinPack algorithm? ("MinBreak-BinFill")

texts:
I have a special variant of BinPack problem.
Does anyone know how to reduce this problem to something known?

The problem:
There are items $I$ and bins $B$ in specific quantity and size.

$|I| ∈ ℕ, |B| ∈ ℕ$

$s : (I ∪ B) → ℕ$

The sum of all item-sizes is not less than the sum of all bin-sizes.

$∑ _{i∈I} s(i) ≥ ∑ _{b∈B} s(b)$

Each bin has to be filled with items or parts of items so that it is filled completely. $s(b,i)$ is the size of that part of $i$ that is in $b$, or $0$ iff not.

$∀ b ∈ B, i ∈ I: s(b,i) ∈ ℕ ∪ \{0\}$

$∀ i ∈ I: ∑ _{b∈B} s(b,i) ≤ s(i)$

$∀ b ∈ B: ∑ _{i∈I} s(b,i) ≥ s(b)$

The goal is to minimize the number of item-parts used to fill all bins.

$numparts = |\{ (b,i) ∈ B×I\ |\ s(b,i)>0 \}|$

$minimize\ numparts$

Example 1:

$I=[100,5]$

$B=[10,10,7]$

$allparts=[10,10,7,73,5]$ after partitioning the first item

$usedparts=[10,10,7]$ because we do not need the other parts anymore

$numparts=3$

Example 2:

$I=[8,14,5]$

$B=[10,10,7]$

$allparts=[8,10,2,2,5]$ after partitioning the second item

$usedparts=[8,2,10,5,2]$ because we need all to fill the bins

$numparts=5$


texts: What language does Zeno machines recognize?

texts:
A Zeno machine of order 1 is a Turing machine that uses half the time it ran its $(n-1)$th step to run its nth step, hence can run infinite steps in just 2 seconds. This is called one step of order 1.

A Zeno machine of order $n$ is a Zeno machine of order $(n-1)$ that runs infinite steps (of order $n-1$) in $2^n$ seconds first step (of order $n$), but in $2^{n-1}$ seconds second step, and in $2^{n-m}$ seconds the mth step.

So, exactly what type of formal language is a Zeno machine of order $n$ capable of recognizing?


texts: Stochastic optimization with erroneous oracles

texts:
I am interested in a class of optimization problems of which we know that the input variable is first subjected to noise $\xi$ before entering the data-producing process $f$.

I write the objective in probability, e.g. $x^* = \underset{x \in X}{\arg } \{ P[\partial f(x + \xi)^\intercal w \leq \epsilon_1 ] \geq 1 - \epsilon_2\}$ where $X \subset \mathbb{R}^d$ and $\epsilon_i$ and $w$ are constant w.r.t $x$.

Notes :

$f$ is not known explicitly but is continuous and quite regular, so we are able to compute subgradients for any realization of $\xi$. I am pretty sure it is not convex over all $X$.
We do not know the distribution of $\xi$ and it might have a dependency on $x$.

Question :

I've seen many works in stochastic approximation dealing with additive noise (noisy zeroth and first- order oracles); is there any relevant literature on "noisy control variables" ? I would be very grateful for any pointers, especially to approximation algorithms.

Thank you in advance


texts: Longest path among all pairwise shortest paths in unweighted undirected biconnected planar graphs

texts:
Consider an unweighted undirected bi-connected planar graph.

Let $l_{v,u}$ be the length of the shortest path between nodes $v$ and $u$.

Let $l_{max}$ be the length of the longest shortest path from any node to any other node.

The question is:

  Are there any known non-trivial upper/lower bounds for $l_{max}$?

It would also help if the bounds are for more general types of graphs.

Another interesting way of looking at the problem is:

$l_{max}$ is the maximal number of hops it takes to send a packet in a network from any terminal to any other, when using the shortest possible path.

Please post any link/reference that might be relevant, even if it does not directly solve the problem.
Thanks in advance!


texts: Formal theory about explaining algorithms

texts:
There is a lot of algorithms written in formal languages, but I have never seen any formal system which target is to explain or give a rationale behind an algorithm. It seems that when constructing examples, authors have to create both interesting, somewhat random, and small samples. I think this task could be formalized to some degree.
I wonder if there is such theory or maybe attempts to formalize explanations?
Edit: I was looking for a theory that describes how to teach other people an algorithm. As mentioned by jmite, it is possible to create a self-explaining algorithm using dependent types to solve this problem.


texts: Are there digraphs such that any two arborescences are arc-disjoint?

texts:
Let $D=(V,A)$ be a directed graph with root $r$.
An $r$-arborescence of $D$ is a subgraph such that for any $v\in V-r$, there is exactly one directed path from $r$ to $v$.
Hence an $r$-arborescence is a directed spanning tree whose arcs are directed away from $r$.

Question:
Is there a directed graph $D=(V,A)$ with root $r$ such that any two $r$-arborescences of $D$ are arc-disjoint?


texts: Finding a minimal context free grammar that recognizes a finite set of strings of bounded length

texts:
Problem:

Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that recognizes all of these strings.

If $k$ is a constant, and $n = poly(\ell)$, what can one say about this problem's complexity as $\ell$ grows?

This seems similar to the smallest grammar problem, which is NP-Hard for the optimization problem. However it is a little different because of having multiple strings, since now one needs to recognize each string independently instead of recognizing all of them at once. The smallest grammar problem is clearly a subset of this, but for small $\ell$ this might be much easier to solve, I'm not sure.

Is there a way to approximately solve this problem efficiently?


texts:
How can we chose to place $k$ points in $[0,1]^d$, such that the minimum Euclidian distance between any two points is maximized?

Is there a more common term for these combinatorial designs than unit hypercube encodings?

Example:  For $d=2$ and $k=3$ we could have the points (0.23,0.33), (0.24,0.37), and (0.94, 0.81). The first two points are closest, and this design is far from optimal.

One could also think of this as a Voronoi diagram in the unit hypercube where the minimum distance between any two centroids is maximized.

Here is a the discrete analogue where we force ourselves to use only the value zero or one in each dimension, and Hamming instead of Euclidian distance: http://www.win.tue.nl/~aeb/codes/binary-1.html

Also see, "Sphere Packings, Lattices, and Groups", http://www.springer.com/us/book/9780387985855, which covers dense packings in $R^{n}$, but not packings of points into the unit hypercube from what I can see. In our case the hyperspheres would only be required to have their center point in the unit cube.

SigGraph paper shows success in 2D with uniform sampling then walking each point towards the farthest, http://dl.acm.org/citation.cfm?id=2018345


texts: Using MATLAB's CVX Package for Semidefinite Programming in Quantum Information

texts:
I'm attempting to formulate the semidefinite programs used in the paper "Hedging Bets with Correlated Quantum Strategies" (specifically those on page 7) into CVX so that I can play around with the values of the SDPs. The CVX package seems to be very straightforward to get up and running, but I'm a bit unsure in how to convert the SDPs in this scenario and how to interpret the results. For completeness and to try to be a bit helpful, the primal and dual problems for the maximization constraint are replicated from the paper below.

Primal Problem:

maximize: $\langle Q_a, X \rangle$

subject to: $Tr_{\mathcal{Y}}(X) = \mathcal{I}_{\mathcal{X}},$

$\qquad \qquad X \in Pos(\mathcal{Y} \otimes \mathcal{X})$

Dual Problem:

minimize: $Tr(Y)$

subject to: $\mathcal{I}_{\mathcal{Y}} \otimes Y \geq Q_a,$

$\qquad \qquad Y \in Herm(\mathcal{X})$

In this case, these are the SDPs which correspond to Bob's maximum probability for winning some quantum protocol between two parties (more information is in the paper, but if you're going to take the time to help me, by all means ask if I can clarify something in a bit more detail). The variables $Q_a$ and $X$ correspond to the Choi-Jamiolkowski representation of the channel for Alice and Bob respectively. My attempt at putting this into MATLAB is as follows:

n = 3;
cvx_begin sdp
    variable Y(n,n) hermitian;
    dual variable X;
    maximize ( trace ( Y ) );
    subject to
       X : kron(eye(n), Y) >= 0;
cvx_end

Since I don't have a partial trace operation, I'm essentially flipping the roles of the primal and dual functions by swapping the maximization and minimization constraints. This may not be the right way to go about it though, so any feedback would certainly be helpful.  Basically my understanding is that if you provide the primal problem, CVX is smart enough to solve the corresponding dual (Section 3.7 of the CVX manual).

Running the above works, but yields a status failed result, leading me to think that there is something I'm most likely missing here:

Status: Failed
Optimal value (cvx_optval): NaN


texts: Probabilistic circuit complexity or size of probabilistic 2-way automata for Boolean functions

texts:
If we consider circuits with arbitrary binary logic gates one can prove by a counting argument that there exists a Boolean function on $n$ variables that require a circuit of size $ \Theta \left( 2^n/n \right) $ (in fact almost all of them are such).

This follows from the fact that there are $2^{2^n}$ Boolean functions on $n$ variables and only at most $16^k (k+n+1)^{2k} k / k!$ different Boolean functions on $n$ variables can be computed by circuits of size $k$ (for each gate there are $16$ possibilities to choose its type and $b+n+1$ possibilities to choose its two predesscors (the other $k-1$ gates, $n$ variables and $2$ constants), $k$ possibilities to choose the final gate and there are $k!$ possibilities to renumber the gates)

I am interested in probabilistic circuits in the following (nonstandard) sense - using gates which can have arbitrary rational probability distribution of which binary function to output. For example a gate which works as AND(x,y) with probability $\frac{7}{13}$, as OR(x,y) with probability $\frac{5}{13}$ and outputs constant $0$ with probability $\frac{1}{13}$.
The computation is allowed to have 2 sided bounded error - that is, we say that the circuit computes a function f if for every input $x_1, \ldots, x_n$ it outputs the correct result $f(x_1, \ldots, x_n)$ with probability $\geq 2/3$.

Is it possible to similarly prove that there exists a Boolean function that requires probabilistic circuit of a superpolynomial size?
The problem is that there are infinitely many different types of gates. Is there any neat trick that could be applied?

The question I actually am interested in is the following - does there exist a Boolean function such that every 2-way probabilistic finite automata (having arbitrary rational transition probabilities) that recognizes it with 2-sided error has superpolynomial number of states? Just thinking that people are more familiar with circuits than 2-way automata and the proof could be transferred from one domain to another.

Update:

More formally I want to prove the following:

  There exists an infinite sequence of Boolean functions $f_1, f_2,
\ldots$ of $n_1, n_2, \ldots$ ($n_1 < n_2 < \ldots$) variables such
  that for every sequence of 2pfas $P_{f_1}, P_{f_2}, \ldots$ such that
  $P_{f_i}$ recognizes $f_i$ with 2-sided bounded error (that is for
  every word $x_1, \ldots, x_{n_i}$ accepts it with probability $\leq
\frac{1}{3}$ if $f_i(x_1, \ldots, x_{n_i}) =0$ and probability $\geq
\frac{2}{3}$ if $f_i(x_1, \ldots, x_{n_i})=1$) the number of states
  grows superpolynomially: for every polynomial $p(n)$ exists $i$ such that the number of
  states $\left| P_{f_i} \right| > p(n_i)$.

If we allowed the 2pfa to have only transition probabilities of $\{0, \frac{1}{2}, 1\}$ (or some other restricted set (size of which might depend on $n$ and even grow exponentially in terms of $n$)) then it is provable by a counting argument. Question is - is it still true if all rational transition probabilites are allowed?


texts:
It is well-known that the set of languages having two-prover interactive proof systems, in which the verifier runs in polynomial-time (MIP), is NEXP. But are there bounds known on the power of such interactive proofs when the provers are restricted in power? E.g., what is the class of languages that admit two-prover interactive proofs with polynomial-time provers?

More precisely, let's say that on an input x I allow the provers arbitrary pre-computation time, but once the interaction with the verifier starts they are restricted to using polynomial space (including storing the results of any pre-computation), and polynomial time to compute their answers to the verifier's question. Let's also assume that these space and time bounds are a fixed polynomial in the length of the questions that will be sent by the verifier (instead of the length of x), in order to preclude a more trivial solution in which the verifier would somehow exhaust the prover's space bound by asking polynomially more questions.

Clearly, this is enough for NP. What about PSPACE? If there was only the space bound they could do it, but what with the time bound? Are there any interesting results in that direction?

I am also interested in other limitations that one might consider on the provers. One of those would be the amount of communication prover->verifier, which I think has been thoroughly studied in the context of PCPs. What are the other interesting constraints?


texts: Cobham's Result on Efficient Computations

texts:
In the following paper:

Alan Cobham (1965), "The intrinsic computational difficulty of functions", Proc. Logic, Methodology, and Philosophy of Science II, North Holland.

Cobham defined the class P as the class for efficient computations. He stated that his notion is machine-independent.

Unfortunately, I don't have access to this paper. Can anyone clarify the points he made there? Is it just a thesis, or something proved?


texts:
If simply typed lambda calculus corresponds to cartesian closed categories, what types of categories do other calculi in the lambda cube correspond to?
https://en.m.wikipedia.org/wiki/Lambda_cube


texts:
Arora/Barak, in Chapter 21, Theorem 21.9, Page 428, proves:

  Algebraic Expansion implies Combinatorial Expansion

  If G is a $(n, d, x)$ expander graph, then it is an $(n, d, (1-x)/2)$
  edge expander.

(good, I understand this part)

They they go on to state:

  Combinatorial Expansion implies Algebraic Expansion

  If G is a (n, d, p) edge expander, then i's second largest eigen
  value (without taking the absolute values) is at most $1 - p^2/2$.
  Furthermore, if G has all self loops, then it is an $(n, d, 1-\epsilon)$
  expander where $\epsilon = min(2/d, p^2/2$).

Now, this is the part I am unhappy with. Here is what I understand:

If G is bipartite, it has an eigen value of -1, and thus we can't say much about the 2nd largest absolute value of the eigen values.

If G has all self loops, it's clearly not bipartite.

However, the above theorem does not make any guarantees about graphs G, which are:

(1) non-bipartite
(2) do not contain all self loops.

For graphs in this class, do we have a proof of "combinatorial expansion" implies "algebraic expansion"? [If the answer is yes, can you please provide a reference?]

Thanks!


texts: Some problems involving polynomials of public and private variables over GF(2).

texts:
Suppose there are a set of low degree (less than some degree $z$) polynomials $P_0, P_1, ..., P_k$ each of which is defined over two types of variables, red variables ${v_r}_0, {v_r}_1, ..., {v_r}_n$ and blue variables ${v_b}_0, {v_b}_1, ..., {v_b}_m$ (all in $\mathbb{F}_2$).

Suppose also that you are given a description of $P*$, a polynomial defined over the collection $P_0, P_1, ..., P_n$.

Blue variables are 'mutable' and public, and may be set to any constant term ${0, 1}$ or to dynamically represent a polynomial combination of other red and blue variables. Red variables are static and are 'unknown'.

Here are some problems I would like to automate. Each bulletpoint below represents a slightly different optimization problem. Given $P*$, $P_0, P_1, ..., P_n$, $z$ and $k$ and $n$ and $m$ and $d$, how should I set the value of blue variables in order that:

The number of red variables in the largest degree term of $P*$ is minimized.
The number of polynomials $P_0, P_1, ..., P_n$ forced to the value 0 is maximized.

Both problems are subject to the constraints that:

There will only be one term of the highest degree in $P*$ with red variables.
$P*$ is of degree $d$ or less (viewed as a polynomial over red and blue variables).

I'm looking to understand the complexity of finding solutions which optimize one of the two first goals in the list. Additionally, I'd like to know how hard it is to find some satisfying assignment (or prove that none exist) - without considering the optimization in either problem above.

Does anyone have a reference to a similar problem that might be adaptable to these scenarios? A hunch or intuition about the correct way to approach the problem? Or (ideally) an answer to these questions with referenced papers or solid proof?


texts: Quantum query complexity and certificate complexity

texts:
A certificate for an input $x$ is a subset of bits $S \subseteq \{1,...,n\}$ such that for all inputs $y$, $(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$. Then $C_x(f)$ is the minimum size of a certificate for input $x$ and the certificate complexity $C(f) = \max_x C_x(f)$. Thus, certificate complexity can be seen as a form of query complexity for nondeterministic machines: guess the smallest certificate for $x$ and then verify with $C_x(f)$ many queries. This is used as an intermediate complexity measure when proving relationships between deterministic query complexity ($D(f)$) and quantum query complexity ($Q_2(f)$).

Is it known, or believed that for a total functions $f$, $C(f) \leq Q_2(f)$? Are there any total functions $f$, where it is know that $C(f) \in o(Q_2(f))$ (or vice-versa)? And just for fun: does this question correspond in some formal way to the questions associated NP vs. BQP?


texts: How to efficiently read the theoretical computer science research papers?

texts:
I am a computer science graduate student works in theory. The general advice is to go through the paper and then in the second or third round try to understand the detail. Read the abstract, introduction and then main results(just the results). I go through research paper multiple times, each time keep record of confused things. Many time I have to spend more than a week to understand even the bigger picture. Once I have bigger picture, then it is easy for me to understand the paper quickly.

Reading is taking quite long time. I am even about to graduate but it takes me couple of weeks to read a single paper. I have to many times present research papers in front of senior researchers. So I prepare, but as I mentioned that reading is taking too much time.

Is there any better way to speedup the reading? Efficiently means getting the overall idea with less number of passes.

Question :  How to efficiently read  the theoretical computer science research papers ?


texts: How hard is counting vertex covers / edge covers on the following graph class?

texts:
Let $G=(V,E)$ be a graph having all the following restrictions:

Every vertex $v \in V$ has degree $4$.
Every vertex $v \in V$ belongs to at least $2$ triangles.
For every vertex $v \in V$, if $v$ belongs to exactly $2$ triangles then such $2$ triangles do not share any edge.

I would like to know whether such kind of graphs have been studied, what is known about them, and in particular which is the computational complexity of counting vertex covers and edge covers (even modulo $2$) on them.


texts: Is it possible that feedback vertex set problem has an $O(k^2/\log k)$ kernel？

texts:
(This question also suits for other similar natural $\mathrm{NP}$-hard problems)
I know that there is a $4k^2$ vertex kernel (and $8k^2$ edge kernel) by Thomasse [Thomasse09] for Feedback Vertex Set (FVS) problem.
Harnik and Naor [HN06] introduced a notion of compression with the goal of succinctly storing instances of computational problems.
As argued by Dell and van Melkebeek [DV14], for every real number $\varepsilon > 0$, FVS does not admits a polynomial compression with bitsize $O(k^{2−\varepsilon})$, unless $\mathrm{NP} \subseteq \mathrm{coNP/poly}$.
It shows that obtaining kernels for the FVS problems with a strictly subquadratic number of edges is implausible (since $O(k^{2−\varepsilon})$ edges can be encoded in $O(k^{2−\varepsilon}\log k)$ bits).
However, it seems hard to understand, using solely the notion of the compositions as a tool, whether obtaining a kernel for FVS with a subquadratic number of vertices is possible or not.
Is it possible that FVS has an $O(k^2/\log k)$ kernel?
In general, if there do exist an $O(\mathrm{poly}(k))$ kernel for a natural (graph) problem and it has a lower bound of size $O(\mathrm{poly}(k))$ bit. Is it still possible that this problem has an $O(\mathrm{poly}(k)/\log k)$ kernel?
Do we have any evidences or obversations to believe or doubt it?


texts: Is Prime Bounded Quadratic Congruence NP-complete?

texts:
Bounded Quadratic Congruence:

Instance: Three positive integers $a$, $b$ and $c$.

Question: Is there a positive integer $x<c$ such that $x^{2} \equiv a \, (mod \ b)$?

Bounded Quadratic Congruence is $NP$-$complete$ [1].

Prime Bounded Quadratic Congruence:

Instance: Three positive integers $a$, $b$ and $c$ such that $b$ is a prime number.

Question: Is there a positive integer $x<c$ such that $x^{2} \equiv a \, (mod \ b)$?

Is this problem $NP$-$complete$ as well?

Reference:

[1] Kenneth L. Manders and Leonard M. Adleman, NP-complete decision problems for binary quadratics, Journal of Computer and System Sciences 16 (1978), no. 2, pp. 168–184.


texts: Are single hidden-layered neural networks at least as good as multi hidden-layered neural networks?

texts:
If I have a multi hidden-layered neural network that is getting a better approximation for a function than a single one, does that mean that there is something "fishy" about my multi layered one because of the Universal Approximation Theorem?

I am assuming here that all weights are pre-initialized to 1 (I have my reasons) and they are trained on the same exact dataset.


texts:
I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$:

$\mathcal{F}$ consists of all languages of the shape $\{a_{i_1}^{c_1}a_{i_2}^{n_2}a_{i_3}^{c_3}\ldots a_{i_{k-1}}^{n_{k-1}}a_{i_k}^{c_k}: n_2,n_4,\ldots,n_{k-1} \geq 0 \wedge R(n_2,n_4,\ldots,n_{k-1})\}$, where $c_1,c_3,\ldots,c_k$ are fixed nonnegative constants and $R$ is any fixed relation on $m$ variables $u_1,u_2,\ldots,u_m$ such that for some $S \subseteq \{1,2,\ldots,m\} \times \{1,2,\ldots,m\}$, $R(u_1,u_2,\ldots,u_m)$ holds iff $\left((\forall i,j \in \{1,\ldots,m\})[u_i = u_j \Leftrightarrow (i,j) \in S]\right)$.

So $\mathcal{F}$ contains languages like $\{a_1^n a_2^n a_3^n: n \geq 0\}$ (the "standard" context-sensitive but non-context-free language) and $\{a_1^2 a_1^n a_2^m a_1 a_1^m a_2^n a_1: n,m \geq 0\}$.

This family of languages cropped up in my work recently and I was wondering whether anything interesting could be said about it..

Thank you!


texts: Regular expressions without union but with backreferences

texts:
As a follow-up to my question Regular expressions without alternation, I was wondering what was known about the power of regular expressions in which union is not allowed but backreferences are.

I'm familiar with a number of papers discussing regular expressions with the addition of backreferences, but none that I've seen address the union-free version. This class would be incomparable with the class of regular languages, but are they as hard to recognize as full regular expressions with backreferences?  (I've seen several terms used for this; none seem to be standard.)  In the case without backreferences, removing union seems to reduce expressibility without making membership tests much/any faster.

As before union means the same as alternation, logical OR, | (in standard regexes), / (ABNF), ∪, etc.


texts: Complexity of finding semi-ordered Eulerian tours in a 4-regular graph

texts:
I'm trying to figure out the time-complexity of the problem I describe below, which I call the semi-ordered Eulerian tour problem or the SOET problem. Either finding an efficient algorithm for this problem or proving that this is actually in NP-hard would settle this question for me. Below I describe the problem, give two examples of instances to the problem and explain what I have realized so far. To be precise, my questions are:

What is the time-complexity of this problem?
Is this problem NP-hard?
If it exists, what is an algorithm that solves this problem in polynomial time in terms of both $n$ and $k$? (see below)

The SOET problem

Given a 4-regular graph $G=(V,E)$, i.e. a graph where each vertex have degree 4, the problem is to find a semi-ordered Eulerian tour (defined below). Note that the graph is not assumed to be simple, so multi-edges and self-loops are allowed.

Definition (semi-ordered Eulerian tour):
Let $S\subseteq V$ be a subset of the vertices in $G$ and $s=s_1s_2\dots s_k$ be a permutation of $S$. The Eulerian tour $U$ is a semi-ordered Eulerian tour with respect to $S$ if, $U=As_1Bs_2\dots s_kXs_1Ys_2\dots s_kZ$ for some $s$ and where $A,B\dots,X,Y,\dots,Z$ are words with letters in $V\setminus S$. That is, $U$ traverses $s$ in some order once and then again in the same order. To be clear, which specific $s$ that satisfies this is unimportant.

Note that since $G$ is 4-regular an Eulerian tour always exists and furthermore it will pass each vertex exactly twice.

Examples

Here I give two examples of 4-regular graphs. The first one, G_1, there is a SOET with respect to $\{a,b,c,d\}$, since there is a Eulerian tour $U=abcdaebced$. In the second example, G_2, there is none.

Current status

I have realized that this problem is at least fixed-parameter tractable in terms of $k$, i.e. there is an algorithm with time-complexity $\mathcal{O}(f(k)p(n))$, where $k=|S|$, $n=|V|$ and $p$ is some polynomial. This can be seen by mapping the problem to $k!k^3$ edge-disjoint paths problems (DPP) where you try to find paths between pairs of vertices in $S$. This has to be done for all permutations of the vertices in $S$, the reason for the factor $k!$ in the number of DPP:s. Furthermore each vertex has to be split into two vertices and connected by edges in one out of three ways (vertically, horizontally or diagonally), to actually give a Eulerian tour. This are in total another $3^k$ DPP:s. Note that this does not necessarily exclude the possibility of an algorithm which is also polynomial in $k$.

Note regarding duplicate:

I have also asked the same question on MathOverflow but after two weeks of no response I thought that this might be the better place for this question.


texts: Tree-decomposition with clique interfaces

texts:
Let $G=(V,E)$ be a finite undirected graph. A tree decomposition $(T,\lambda)$ of $G$ is a tree $T$ with labeling function $\lambda : T \to 2^{V}$ such that:

For every edge $\{v_1,v_2\} \in E$, there exists a node $n$ of $T$ such that $v_1,v_2 \in \lambda(n)$.
For every vertex $v \in V$, the set $\{n \in T \mid v \in n\}$ forms a connected subtree of $T$.

For my purposes (namely, showing the tractability of model-checking for a particular logical fragment), I am interested in a restricted kind of tree decompositions, that satisfies an additional condition. I call a tree-decomposition with clique interfaces a tree decomposition $(T,\lambda)$ of $G$ that respects the following additional property:

For every two adjacent nodes $n_1$ and $n_2$ of the tree decomposition $T$, we require that the interface $\lambda(n_1) \cap \lambda(n_2)$ forms a clique in $G$. In other words, for every pair of distinct elements $a,b$ occurring both in $n_1$ and $n_2$, we must have $\{a, b\} \in E$.

As usual, the width of such a decomposition is $max_{n \in T}|\lambda(n)|-1$ and the width of $G$ is the minimal width of such a decomposition.
Note that, of course, the width of $G$ according to this definition is necessarily greater than its treewidth in the usual sense.

My question is to know if this notion of width has already been studied and has an established name. In particular, I am interested in alternative characterization of graphs whose width is low in this sense, in the complexity of computing it, etc.

This could be related to the notion of $k$-trees. In k-trees, we impose in tree decompositions that $\lambda(n)$ forms a clique for all $n$ and that the interfaces are of size $k$. However not all graphs have such a decomposition, while for the notion that I propose, all graphs would have a decomposition (at worst the trivial one with width $|V|-1$) so it looks like this notion could have been studied in a general context.


texts: How common is phase transition in NP-complete problems?

texts:
It is well known that many NP-complete problems exhibit phase transition. I am interested here in phase transition with respect to containment in the language, rather than the hardness of the input, relative to an algorithm.

To make the concept unambiguous, let us formally define it as follows. A language $L$ exhibits phase transition (with respect to containment), if

There is an order parameter $r(x)$, which is a polynomial time computable, real valued function of the instance.
There is a threshold $t$. It is either a real constant, or it may possibly depend on $n=|x|$, that is, $t=t(n)$.
For almost every $x$ with $r(x)<t$, we have $x\in L$. (Almost every means here: all but vanishingly many, that is, the proportion approaches 1, as $n\rightarrow\infty$).
For almost every $x$ with $r(x)>t$, we have $x\notin L$.
For almost every $x$, it holds that $r(x)\neq t$.  (That is, the transitional region is "narrow.")

Many natural NP-complete problems exhibit phase transition in this sense. Examples are numerous variants of SAT, all monotone graph properties, various constraint satisfaction problems,  and probably many others.

Question: Which are some "nice" exceptions? Is there a natural NP-complete problem, which (probably) does not have a phase transition in the above sense?


texts: Minimum length cuts needed to remove holes in a polygon

texts:
Suppose I'm given a connected polygon in the plane with holes. I can "remove" a hole by drawing a straight line from the boundary of a hole to another boundary (either of another hole, or the boundary separating the polygon from the exterior).

  Let's say the "cost" of a cut is its length. What is the minimum cost set of cuts needed to remove all holes in a polygon ?

At first I thought this would be easy: write down the distances between each pair of holes and each hole and the polygon boundary, and compute an MST. But it's not obvious to me that this is correct.

Is this a known problem ?


texts: How hard is recognizing a permutation that is a square for the shift product?

texts:
This is a continuation of my attempts to generate simple combinatorial computational problems that turn out to be computationally hard (NP-complete). In this pursuit, I came up with a permutation problem (How hard is reconstructing a permutation from its differences sequence?) which turned out to be NP-complete. Here, I propose another computational problem which I highly suspect that it is NP-complete.

The shift of a permutation $\pi(i)$ of numbers $1, 2, \ldots n$ is defined as $\sigma(i)$= $\pi(i+k \mod n)$ for some fixed $k$,  $1 \le k \lt n$. The shift product of a permutation $\pi$ is defined as $ \pi(i+k \mod n) \circ \pi(i)$. We say that a permutation $\pi$ is a square for the shift product if there is a permutation $\tau$ such that $\pi$ is the shift product of $\tau$ (i.e. $\pi(i)=  \tau(i+k \mod n) \circ \tau(i)$).

I did not find a notion of shift product for permutations in the literature.

Formally,

Square Permuation

Instance: A permutation $\pi$ of $1, 2, \ldots n$

Question: Is permutation $\pi$ a square for the shift product?

  Is there an efficient algorithm to determine whether a given permutation $\pi$ is a square for the shift product of some permutation $\tau$, or is it NP-complete?

The problem appears to be hard even when the shift amount $k=1$.

This was posted on mathOverflow.


texts: How to compute ROOK Polynomials for NxM Matrices for k objects ?


texts: Has there been any development of complexity theory for other Turing degrees than 0?

texts:
(I'm not sure if this question is better suited for MathOverflow or here.  I'll try here first, and move over to MO later if it appears to be more appropriate.)
Complexity theory can be very broadly described as the finer structure of the subsets of $\mathbb{N}$, or functions $\mathbb{N}\to\mathbb{N}$, constituting the Turing degree $\mathbf{0}$ (of computable sets), where we ask ourselves “OK, this set is computable by a Turing machine, now how much resources (time, memory, etc.) does it take to actually compute it?”.
This suggests the following natural question: is there some analogous theory for the finer structures of other Turing degrees, or Turing ideals?
Of particular interest would be $\mathbf{0}'$ (sets computable with an oracle solving the halting problem) or hyperarithmetic sets.  One naïve attempt at creating a kind of complexity theory for $\mathbf{0}'$ (the simplest Turing degre beyond $\mathbf{0}$) would be to count the number of calls to the oracle as “resource” taken (or somewhat relatedly, simply use standard complexity classes like $\mathbf{P}$ and so on, but relativized to the halting oracle), but maybe this is too simplistic.
Hyperarithmetic sets are another interesting possibility because there is a classical analogy (due, I think, to Kreisel) between computability and hyperarithmetical theory, and “hyperarithmetic machines” can be described as Turing machines with access to a certain kind of generalized oracle (viz., the type-2 functional $\mathsf{E}$: intuitively, a hyperarithmetic machine can ask “does this (other) hyperarithmetic machine, which always terminates, ever produce a value $>0$?”, so we could try counting the number of times it does this); also, hyperarithmetic sets come with their own hierarchy from the Turing degrees (the hyperarithmetic hierarchy, constructed by transfinitely iterating the Turing jump up to $\omega_1^{\mathrm{CK}}$, which may or may not provide a satisfactory “complexity theory”.
So, anyway, have such theories been developed?  I would expect that a natural analogue of $\mathbf{PR}$ (primitive recursive functions) is easy to define for higher Turing degrees, but what about finer classes like $\mathbf{P}$?


texts: Specification language for specifying both Objects and Primitive data types

texts: I am looking for an specification language, which supports both primitive data types and objects. I already know about Object-Z. But I am wondering if there is any other Specification language that I can use.