texts: Would it be possible for a compiler to convert a recursive sum into the average formula?

texts:
def sum1(n):
    if n==0: return 0
    else: return n + sum1(n-1)

def sum2(n):
    return n*(n+1)/2

A compiler can not convert sum1 into sum2 because function equality in turing-complete languages is undecidable. My question is: is there a system strong enough to express both functions, that is also weak enough to a compiler can make the conversion? Or, even better, is there a simple system where the mere reduction of sum1 would fall into sum2?


texts: Family of formulas for which Gabbay's separation algorithm explodes nonelementarily

texts:
It is repeated throughout the literature that Gabbay's algorithm for
separation of LTL with Since and Until can produce nonelementary blow-up
of the size of the formula, but I have never seen a proof of this.

I'm looking for a family of formulas that exhibits this nonelementary blow-up. Or some other proof of this.


texts: In-approximability results in severely restricted graph classes

texts:
Longest path problem is not polynomial-time approximable to any constant factor in cubic Hamiltonian graphs (Longest path $\notin APX$ unless $P=NP$). I don't know if it remains in-approximable in cubic bipartite Hamiltonian graphs. Maximum independent set is not in $APX$ unless $P=NP$ but it is in $APX$ for cubic graphs. David Eppstein pointed out that it is $NP$-complete to find maximum clique in claw-free graphs and it is not clear to me if it is any easier to approximate than in general graphs.

I'm interested in optimization problems that remains in-approximable in severely restricted classes of graphs (for instance, cubic planar bipartite graphs or trees of bounded degree).

A problem $L$ is In-approximable means that  $L \notin APX$. It is $NP$-hard to approximate to any constant factor in polynomial-time.


texts: What is the grammar of network protocols and file formats?

texts:
For network protocols and/or file formats with fixed length fields, the grammar is fairly simple, and can be explained with a regular expression.

However, for protocols with varying data lenghts, there is almost always a fixed-length field preceding the data that gives the length of that data.

Without going into details of protocol/format specifications, we can talk about its equivalents in grammar notation. For example, consider the following production rule:

A -> anb^n

where 'a' is some fixed-length symbol, 'n' is a non-negative integer, and b^n is b repeated n times.

I'm having trouble understanding how such a rule can capture the fact that the value of 'n' is somehow related to how many b's are present in the sentence.

Where in the Chomsky hierarchy do such grammars lie? Also is it possible to automatically generate parsers for such grammars?


texts:
Let $\Pi$ be an $\mathsf{NP}$-complete problem. It is standard that $3SAT$ and $\Pi$ are reducible from each other.

Let UnambiguousSAT, or USAT for short, denote the promise problem which is 3SAT but with the promise that there is $\leq 1$ solution (that is, it is in $\mathsf{PromiseUP}$). Valiant-Vazirani gives a randomized reduction from SAT to USAT.

For some natural problem $\Pi$, let U$\Pi$ is the corresponding promise problem in $\mathsf{PromiseUP}$, and suppose that $\Pi$ randomly reduces to U$\Pi$.

Is it reasonable to expect reduction from U$\Pi$ to USAT and vice versa? Would that mean $\mathsf{PromiseUP}$ has complete problem?

In general if USAT is in $\mathsf{RP}$ then $\mathsf{NP}=\mathsf{RP}$. Can we get something similar for U$\Pi$ as above?


texts: lower bound for difference between max cut and min cut

texts:
Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e.
$$M^+=\max\limits_{(U_1,U_2)}\left\{\sum_{e=\{u,v\}\in E\,:\,u\in U_1,v\in U_2}w_e\ :\ U_1\cup U_2=V,\ U_1\cap U_2=\emptyset\right\},$$
$$M^-=\min\limits_{(U_1,U_2)}\left\{\sum_{e=\{u,v\}\in E\,:\,u\in U_1,v\in U_2}w_e\ :\ U_1\cup U_2=V,\ U_1\cap U_2=\emptyset\right\}.$$
I'm interested in possible ratios between the difference $M^+-M^-$ and $\sum_{e\in E}\lvert w_e\rvert$. From Corollary 3.7 in the paper Some results on the strength of multilinear functions it follows that $M^+-M^-\geqslant\frac{1}{n-1}\sum_{e\in E}\lvert w_e\rvert$. Taking complete bipartite graphs and choosing the weights independently and uniformly at random from $\{\pm 1\}$ we find that there are graphs with $M^+-M^-=o(1)\sum_{e\in E}\lvert w_e\rvert$.

Are there better lower bounds known? Maybe under additional assumptions on the weight fun (for instance if $w_e\in\{1,-1\}$ for all $e$)?
What are known constructions with $M^+-M^-\leqslant f(n)\sum_{e\in E}\lvert w_e\rvert$ for some "small" function $f$? For instance, can we replace the $o(1)$ in the random construction by $O(1/n)$?

Cross posted on MO.


texts: Tree rotation, a problem similar to Huffman coding

texts:
I am not sure whether the following problem has been studied.

We have a undirected tree $T$.
We would like to construct another tree $T'$.
$T'$ is a binary tree. Each inner nodes of $T'$ is an edge of $T$.
The set of leaves of $T'$ is the same as the set of leaves of $T$.
$T'$ is constructed as follows:

We pick an edge $e$ in $T$, which breaks $T$ into two parts $T_1$ and $T_2$.
$e$ is the root of T'.
we recursively construct the left and right subtrees of T' from $T_1$ and $T_2$ respectively.
The cost of T' is $\sum_{v:leaves}Length_{T'}(P_v)$ where $P_v$
is the path from the root to $v$.
We would like to find the tree T' that minimizes the cost.

I suspect the optimal algorithm is to pick the edge which split the number of leaves
as evenly as possible and recurse.
However, it seems to be a clean problem that has been studied. But I have no idea what to search.
Any help will be appreciated.


texts: AC0 many-one reduction of Mod_3 to PRIMES?

texts:
Let Mod$_3$ be the language of binary strings with the sum of the bits divisible by 3, and PRIMES be the set of prime integers.

In a 2001 paper A Lower Bound for Primality, Allender, Saks, and Shparlinski say that Mod$_3$ is AC$^0$ Turing-reducible to PRIMES, but ask whether it is possible to find an AC$^0$ many-one reduction from Mod$_3$ to PRIMES.

  Has there been progress on this question?

A reduction from Mod$_3$ to PRIMES is easy by using the observation that 3 divides $4m + k$ iff 3 divides $m + k$, so 3 divides $n$ iff 3 divides the sum of the base-4 digits of $n$.  This can be achieved by a logarithmic depth circuit, but for an AC$^0$ reduction one of course needs a fixed-depth circuit.

Allender et al. provide a probabilistic fixed-depth circuit for the reduction, and by Adleman's 1978 argument there must then exist a deterministic circuit that performs the same function.  This yields a non-uniform AC$^0$ reduction.

(This question follows-on from Eric Allender's answer Are the problems PRIMES, FACTORING known to be P-hard? where he states that the lower bound for PRIMES of TC$^0$ has not been improved since their paper.)


texts:
CSP optimization problem is approximation resistant if it is $NP$-hard to beat the approximation factor of a random assignment. For instance, MAX 3-LIN is approximation resistant since  a random assignment satisfies $1/2$ fraction of  the linear equations but achieving approximation factor $1/2+ \epsilon$ is $NP$-hard.

MAX CUT is a fundamental $NP$-complete. It can be formulated as CSP problem of solving linear equations modulo 2 ($x_i + x_j= 1$ mod 2). A random assignment achieves  $1/2$-approximation factor (of the total number of edges $|E|$). Haglin and Venkatesan proved that achieving an approximation factor $1/2+ \epsilon$ is $NP$-hard (i.e. finding a cut better than $|E|/2$). However, Hastad showed that MAX CUT is not approximable to $16/17+ \epsilon$ factor within the optimal cut unless $P=NP$. Goemans and Williamson gave a SDP-based polynomial time algorithm with 0.878 approximation factor (within the optimal cut) which is optimal assuming the Unique Games Conjecture. It seems to me that expressing the approximation factor relative to total number of constraints ($|E|$) is more natural and consistent with the convention used for MAX 3-LIN problem.

  Why is the approximation factor for MAX CUT given relative to the size of optimal cut instead of the number of constraints (# of edges)? Am I right in concluding that MAX CUT is approximation resistant when the approximation factor is relative to the total number of constraints ($|E|$)?


texts:
A field is a set with two binary operations called addition and multiplication satisfying various axioms. Wikipedia article: Field_(mathematics)

A field extension is when you add a new element and then have to add all arithmetic combinations of that new element with the existing elements, e.g. adding i to the real numbers to get the complex numbers. If F is a subfield of K then K is called an extension field of F.

Technically you aren't adding new elements, but defining a new field which has a subset isomorphic to the orginal field, e.g. the complex numbers x+0i are identified with the real numbers x.

Wikipedia: Field_extension

Finite field extensions are useful in the construction of BCH codes which are codes over the finite fields of order q=pn which are extensions of the fields of order p where p is prime. These finite fields known as Galois fields GF(p) are extended to GF(q) by adding roots of polynomials that are irreducible (non-factorable) over GF(p).

Wikipedia: BCH_code

Where else in CS does the concept of extension fields arise ? A fundamental appearance in some subject would be more interesting than an occurence in some proof, but if it is used frequently in a common proof stategy then such a proof strategy would also be an interesting answer here.


texts: Complexity of finding weighted edge-disjunctive triangles in a graph

texts:
Given a simple graph, in which the edges are weighted with values from the set $\{-1,1\}$. Three pairwise adjacent edges define a triangle. A triangle is called valid, iff two edges have positive weight and one edge has negative weight.

Find a set $S$ of valid, edge disjunctive triangles, such that the cardinality of $S$ is maximized.

Background: An answer to the above question can be used to calcualte an upper bound for the Clique-Partitioning-Problem (Grötschel, Wakabayashi (1989): A CUTTING PLANE ALGORITHM FOR A CLUSTERING PROBLEM, Math. Prog.)

I assume that the problem is NP-complete. However, I failed to reduce "Independent set", "3D Matching", and "Partition into triangles" to the above problem. (Of course there still may be such reduction)


texts: Useful notion of ambiguous growing context-sensitive language

texts:
As far as I understand there is no useful notion of ambiguous context-sensitive language.
For example for any inherently ambiguous context-free language there is a context-sensitive grammar generating it such that every string has a unique derivation tree https://mathoverflow.net/a/172786
What if we restrict to growing context-sensitive languages? Is there a useful definition of ambiguity then?


texts: In what class are randomized algorithms that err with exactly 25% chance?

texts:
Suppose I consider the following variant of BPP, which let us call E(xact)BPP:
A language is in EBPP if there is a polynomial time randomized TG that accepts every word of the language with exactly 3/4 probability and every word not in the language with exactly 1/4 probability. Obviously EBPP is contained in BPP but are they equal? Has this been studied? What about the similarly definable ERP?

Motivation. My main motivation is that I wanted to know what the complexity theoretic analogue of the ``correct in expected value'' randomized algorithm of Faenza et al. (see http://arxiv.org/abs/1105.4127) would be. First I wanted to understand what decision problems such an algorithm can solve (with worst case polynomial running time). Let us denote this class by E(xpected)V(alue)PP. It is easy to see that USAT $\in$ EVPP. Also easy to see that EBPP $\subset$ EVPP. So this was my motivation. Any feedback about EVPP is also welcome.

In fact, their algorithm always outputs a nonnegative number. If we denote the decisions problems recognizable by such an algorithm by EVP(ositive)PP, then we still have USAT $\in$ EVPPP. While EBPP might not be a subset of EVPPP, we have ERP $\subset$ EVPPP. Maybe using these we can define a (nonnegative) rank for decision problems.


texts: Binary vector $t$ in $span(S)$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$ $\Rightarrow$ $t$ in $span(S)$ over $\mathbb{Z}$?

texts:
I have a set of $n$ binary vectors $S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\}$ and a target vector $t = 1^k$ which is the all-ones vector.

  Conjecture: If $t$ can be written as a linear combination of elements of $S$ over $\mathbb{Z}/q\mathbb{Z}$ for all prime powers $q$, then $t$ can be written as a linear combination of $S$ over $\mathbb{Z}$, i.e., there is a linear combination with integer coefficients which sums to $t$ over $\mathbb{Z}$.

Is this true? Does it look familiar to anyone? I'm not even sure what keywords to use when searching for literature on this topic, so any input is appreciated.

Observe that the converse certainly holds: if $t = \sum_{i=1}^n \alpha_i s_i$ for integers $a_i$, then evaluating the same sum mod $q$ for any modulus $q$ still gives equality; hence a linear combination with integer coefficients implies the existence of a linear combination for all moduli.

Edit 14-12-2017: The conjecture was initially stronger, asserting the existence of a linear combination over $\mathbb{Z}$ whenever $t$ is a linear combination mod $q$ for all primes $q$. This would have been easier to exploit in my algorithmic application, but turns out to be false. Here is a counter-example. $s_1, \ldots, s_n$ are given by the rows of this matrix:

$\left(
\begin{array}{cccccc}
 1 & 0 & 0 & 1 & 1 & 1 \\
 0 & 1 & 0 & 1 & 1 & 1 \\
 0 & 0 & 1 & 1 & 1 & 1 \\
 0 & 0 & 0 & 0 & 1 & 1 \\
 0 & 0 & 0 & 1 & 0 & 1 \\
 1 & 1 & 1 & 0 & 0 & 1 \\
\end{array}
\right)$

Mathematica verified that the vector $t = (1,1,1,1,1,1)$ is in the span of these vectors mod $q$ for the first 1000 primes, which I take as sufficient evidence that this is the case for all primes. However, there is no integer linear combination over $\mathbb{Z}$: the matrix above has full rank over $\mathbb{R}$ and the unique way to write $(1,1,1,1,1,1)$ as a linear combination of $(s_1, \ldots, s_6)$ over $\mathbb{R}$ is using coefficients $(1/2, 1/2, 1/2, -1/2, -1/2, 1/2)$. (You cannot write $t$ as a linear combination of these vectors mod $4$, though, so it does not contradict the updated form of the conjecture.)


texts: Rigorous proof that a random function and a random permutation cannot be distinguished in polynomial time

texts:
I have a background in number theory and I'm trying to learn how to reason rigorously about algorithms. I'm reading chapter 2 of Katz and Lindell's Introduction to Modern Cryptography.

Show that no probabilistic polynomial-time algorithm $A$ can distinguish between a random function $f:\{0,1\}^n\to \{0,1\}^n$ and a random permutation $g:\{0,1\}^n\to \{0,1\}^n$ when in each case $A$ is given oracle access to the tested function. Distinguish here is of course except with a negligible probability.

Proof idea: $A$ can make at most $q(n)$ queries to the oracle for some polynomial $q(n)$. The chance that $A$ will find out that the given function is not injective is at most whatever probability comes out of the birthday problem of probability theory, but this is negligible in terms of $n$.

If $A$ does not find a collision among the $q(n)$ queries, then $A$ can't know where the $2^n-q(n)$ remaining elements are mapped, so the function can be any function out of

$$(2^n)^{2^n-q(n)}$$

possibilities of which $(2^n-q(n))!$ are permutations, which is a negligible fraction.

Now fix the algorithm and assume it's been given the function $F$ as an oracle. Say $A^F$ returns $1$ if $F$ is determined to be a random permutation by $A$ and $0$ if not. The problem is that I can't know anything about the strategy that $A$ uses and in order to rigorously prove the problem, I would need to show that

$$|P(A^f(n)=1)-P(A^g(n)=1)|\leq \epsilon(n),$$

where $\epsilon$ is a negligible function. How is this done in a mathematically precise way? Where (even though the book is very vague about this), the probability of each term is taken over the choice of $f$ and $g$ and whatever coin flips $A$ does.


texts: I was reading Arora and Barak's book on computational complexity and in the section on 'criticism on Turing machine model and the class P' along with quantum computer it also mentions possibilities of other physical systems for computation such as string theory based computing. Are there any models that use string theory in particular?


texts:
It's well known that planar graphs from a closed-family with forbidden minors $K_{3,3}, K_{5}$, graphs with bounded treewidth also are closed family graphs with no $H_{k}$ as minor.

I assume that graphs with bounded max cut form closed family graphs. Given arbitrarily graph $G$ that doesn't contain $H$ as a minor, how to find max cut approximately.

Thanks!

Addendum:

The relevant topic can be found on On the complexity of the Maximum Cut problem Chapter 6. Graphs with bounded treewidth. The PTAS begins with making modification to the tree decomposition without increasing it's treewidth.

1) $T$ is a binary  tree.

2) If a node $i \in I$ has two children $j_{1}$ and $j_{2}$, then $X_{i}=X_{j1}=X_{j2}$.

3) If a node $i \in I$ has one child $j$, then either $X_{j} \subset X_{i}$ and $|X_{i}-X_{j}|=1$, or $X_{i} \subset X_{j}$ and $|X_{j}-X_{i}|=1$.

In my opinion it's very strong modification, and actually I don't get the idea behind this modification. On the 2th condition if I understood rigth, if there is a node with two neighbors then all of then contain actually the same set of the vertexes, but what for?


texts: Equivalent definitions of time constructibility

texts:
We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ steps and for each $n$ there exists some input of length $n$ on which $M$ makes exacltly $f(n)$ steps.
We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is fully time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes exactly $f(n)$ steps.

Q1: Does there exist a function which is time-construcible and not fully time-constructible?

The answer is yes (see this answer), if $EXP-TIME \neq NEXP-TIME$. Can the condition for "yes" be strengthened to $P\neq NP$? Can "yes" be proven?

Q2: Does the class of (fully) time-constuctible functions changes if we allow only 2-tape Turing machines in the definition?
Q3: What are the "provable" reasons for believing that all nice functions are fully time-constructible?

The paper
Kojiro Kobayashi: On Proving Time Constructibility of Functions. Theor. Comput. Sci. 35: 215-225 (1985)
partially answers Q3. The partial summary and upgrade of it is in this answer. I take Q3 as answered.
Historically, the notion of real-time countable function was used instead of (fully) time-constructible. See this question for more.


texts:
Where to find info on (polytime) approximability of  various discrete optimization problems?
Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of various optimization problems?


texts: Finding Most Compressible Vector Within Bounds?

texts:
Given large positive integers $m$ and $n$:

Let $S$ be the set of integers $\{1,2,\dots,m\}$

We are given as input two vectors $L$ and $U$ both over $S^n$ such that:

$$\bigwedge_{i=1}^{n}{L_i \le U_i}$$

We are interested in the set of vectors $X$ over $S^n$ such that:

$$\bigwedge_{i=1}^{n}{L_i \le X_i \le U_i}$$

Notice that if we define $D = U - L$ than there are:

$$\prod_{i=1}^{n}(D_i+1)$$

valid $X$ vectors.

We want an algorithm that takes $L$ and $U$ and generates a self-contained program as output.  That program when executed may output any one valid $X$, and be as small as possible (in terms of total code and data).

Therefore we would like to know which valid $X$ vector is the one that is the "most compressible".  We can then generate a program that contains that vector compressed in its data section, and the program will simply decompress it and output it.

How can we determine which $X$ is most compressible as a function of $L$ and $U$?


texts: Is it possible to represent a regular expression with bounded captures using a DFA and O(1) additional processing?

texts:
It's well known that a regular expression can be converted to a non-deterministic finite state automaton, which can in turn be converted in to a deterministic finite state automaton. These DFAs can then be compiled directly into code as in e.g. re2c.

However, most libraries for regular expressions allow for captures - where the portion of the string representing a certain portion of the regex is saved for further analysis. With captures things get more complex - a state node passed in an early match may not be able to commit to a capture, as whether the capture is correct or not depends on later nodes.

Although a turing machine can obviously handle such expressions by treating the regex as a NDFA, and maintaining a stack of non-deterministic state transitions (ie backtracking), it's desirable to avoid the unbounded additional memory/CPU usage and allocations this entails.

So: Is it possible to compile a regular expression with a bounded number of captures $(< k)$ into a DFA, allowing $O(1)$ additional processing at each node, and $O(k)$ additional storage?
If not, is there a proof to this effect?


texts: The relation of Gödel's Incompleteness Theorems to the Church-Turing Thesis

texts:
This may be a naive question, but here goes. (Edit -- it is not getting upvotes, but nobody has offered a response either; perhaps the question is more difficult, obscure, or unclear than I thought?)

Gödel's First Incompleteness Theorem can be proven as a corollary of the undecidability of the halting problem (e.g. Sipser Ch. 6; blog post by Scott Aaronson).

From what I understand (confirmed by the comments), this proof does not depend on the Church-Turing thesis. We derive a contradiction by showing that, in a complete and consistent formal system, a Turing Machine could solve the halting problem. (If on the other hand we had just shown that some effective procedure could decide the halting problem, we would need to also assume the Church-Turing thesis to get a contradiction.)

So, we might say that this result provides a bit of intuitive support for the Church-Turing thesis, because it shows that a limitation of Turing Machines implies a universal limitation. (Aaronson's blog post certainly supports this view.)

My question is whether we can gain something more concrete by going in reverse: What formal implications do Gödel's theorems have for the Church-Turing thesis? For instance, it seems intuitively possible that the First Incompleteness theorem implies that no effective procedure can determine if an arbitrary Turing Machine halts; the reasoning might go that the existence of such a procedure implies ability to construct a complete $\omega$-consistent theory. Is this correct? Are there any results along these lines?

(I'm asking out of curiosity -- I don't study logic myself -- so I apologize if this is well-known or not research-level. In that case, consider this a reference request! Thanks for any comments or responses!)

Question that sounds related, but isn't: Church's Theorem and Gödel's Incompleteness Theorems

EDIT: I'll try to make the question more clear! First -- my naive intuition is that Gödel's Incompleteness should imply at least some limitations on what is or is not computable. These limitations would be unconditional, i.e., they should apply to all models of computation rather than just Turing Machines.

So I am wondering if this is the case (there must be some implication, right?). Assuming it is, I'm most curious about how it impacts the Church-Turing Thesis -- the notion that anything effectively calculable can be computed by a Turing Machine. For example, it seems possible that the existence of an effective procedure for deciding whether a Turing Machine halts would contradict  the First Incompleteness Theorem. This result would demonstrate that no possible method of computation can be "much" more powerful than Turing Machines; but is this result true? I have a couple similar questions in the comments. I would be very interested to hear an answer to one of these questions, a pointer to an answer in the literature, an explanation of why my entire reasoning is off-base, or any other comments!


texts: Question about non-private databases and $1^n$

texts:
I am reading a paper called "Revealing Information while Preserving Privacy", by Dinur and Nissim.  There is a definition in the paper called

Definition 3 (Non-Privacy).  A database $\mathcal{D} = (d, \mathcal{A})$ is $t(n)$-non-private if for every constant $\epsilon > 0$ there exists a probabilistic Turing Machine $\mathcal{M}$ with time complexity $t(n)$ so that Pr[$\mathcal{M}^{\mathcal{A}}(1^n)$ outputs $c$ s.t. $dist(c, d) < \epsilon n$] $\geq 1 - neg(n)$.  The probability is taken over the coin tosses of $\mathcal{A}$ and $\mathcal{M}$.

As I understand it, this basically means that with high probability, we can always find some algorithm that essentially outputs the database (or a version of the database that differs on an arbitrarily small fraction of rows) in $t(n)$ time.

But I am having trouble understanding the part about $\mathcal{M}^{\mathcal{A}}(1^n)$.  Is $1^n$ just the number $1$ repeated $n$ times?  Why would we want to use $1^n$ as the input to the algorithm?

Thanks.


texts: Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem

texts: What is the difference between Multiple Knapsack problem and Multidimensional Knapsack Problem? (http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints) According to the literature, Multiple Knapsack problem has integrality gap of 2, what is the integrality gap for Multidimensional Knapsack Problem ?


texts: Original proof that "almost all decision problems are uncomputable"?

texts: Who gave the original proof that "almost all decision problems are uncomputable"? Any hint at the original paper appreciated, thanks!


texts: Where do people publish/submit their work on type theory?

texts:
Besides the most common venues (perhaps POPL, ICFP, LICS and FSCD), where else are papers on type theory commonly published?

Especially, I'm looking for more "pure mathematical" venues/journals which publish work on type theory (especially of the more theoretical kind) from time to time.


texts: Difference between statically and dynamically typed languages

texts:
When writing a course on computer science where students get an introduction to both Python and OCaml, I was on the verge of saying that Python is dynamically typed and OCaml is statically typed. I imagine that we all agree this is true even if nobody seems to agree on what exactly is a dynamically typed language. I came across several definitions which don't suit me :

Some of them talks about type errors detection at compile time and at run time. As C can be compiled but also interpreted (well, this is very unusual, but it can be), I don't like this definition as it relies much more on the implementation of a language rather than on its semantics.
Some ask that types should be attached to variables and not to values for a type system to be static. For instance, in C one can assign an int to a given variable : int n =1. But one cannot assign a double to this variable later. That would make the C language statically typed (well it is, but for other reasons). I don't like this definition as it seems it would not be too difficult to turn any statically typed language into a dynamic one.
Many other definition which turned out to be wrong

I now believe that static/dynamic typed languages are not correctly defined as most serious books seems to be reluctant to define it. In "Types and programming languages" by B. Pierce, the author seems to imply that a language that can write:

if cond then 1 else "one"

should be dynamically typed. I've also seen the definition: "A statically typed language is a language where expression have types, whereas a dynamically typed language is one where values have a type". I am not quite sure to understand what it means. But my feeling is the following : a static language is a language where we can infer the type of an expression from the types of all its functions and its values. That would be a language where only functions whose output type is known from its input types are allowed. Julia people call it "type stable functions".

So my question is the following: Are statically typed languages, those who only allow "type stable functions"?


texts: Solving the Halting problem for most inputs

texts:
Is it possible to solve the following version of the Halting problem : given any Turing machine and some input tape, the program should answer if this pair halts or not except possibly for one Turing machine.

There are other modifications one can make - it should answer halting for all Turing machine/input tape pairs except possibly for one pair, or for finitely many pairs or for finitely many Turing machines.

The standard proof doesn't seem to extend to these cases in an easy way.


texts: When is hypertree width more useful than generalized hypertree width?

texts:
In analysis of CSPs, there are three width notions that are analogous to treewidth: hypertree width (hw), generalized hypertree width (ghw) and fractional hypertree width (fhw). Moreover the inequalities $\text{fhw} \le \text{ghw} \le \text{hw}$ are known. The only motivation for hw instead of ghw that I have seen is that there is an XP algorithm for computing hw, but not for computing ghw. Is there any other motivation for hw instead of ghw? More concretely:

What algorithmic results there are that work when a hypertree decomposition of the smallest width is given, but not when a generalized hypertreewidth decomposition of the smallest width is given?


texts:
The subgraph isomorphism problem problem is to determine given $G$ and $H$ whether $G$ is a subgraph of $H$.

Let $G$ and $H$ be regular graphs with degree of $H$ greater than degree of $G$.

Does the subgraph isomorphism problem remain NP-complete for the following case:

$1.$ Girth of $G$ and $H$ are fixed, say $girth=3$ or a fixed $h$?

How large should a fixed $k$-diameter $d_H$-regular graph $H$ be for it to have a fixed $k$-diameter $d_G$-regular subgraph $G$ of vertex count $n_G$ when both have the same girth?


texts: Can we benefit the linear relation between $\sigma$ and best convergence speed in $(\mu,\lambda)$-ES and $(\mu+\lambda)$-ES?

texts:
$(\mu,\lambda)$-ES and $(\mu+\lambda)$-ES are two well-known Evolution Strategies. One variant of these algorithms is when we set a constant value for $\sigma$ and generate off-springs for $x$ as:

$$
x'=x+\mathcal{N}(0,\sigma)
$$

The value of $\sigma$ has a direct effect on convergence of algorithm. In page 91 of (1) the relation between $\sigma$ and convergence speed, $\varphi'_2$, for several $(1,\lambda)$-ES and $(1+\lambda)$-ES strategies is plotted as:

The dotted curve, $\varphi^{'*}_2$, indicates the location of the maxima of the curves. This curve can be approximated with a line (especially for $\sigma>1$). My question is, how could this fact help us and how we can take advantage of it?

The very first idea is we can predict best convergence speed given an optimal $\sigma$, but this does not help very much in practical problems since:

We usually don't know optimal value of $\sigma$, rather we are looking for optimal $\sigma$,
While this line can predict best convergence speed, it doesn't tell us which setup for $(\mu,\lambda)$ or $(\mu+\lambda)$ could reach to that speed (i.e. we don't know which of two ES algorithms and values for $\mu$ and $\lambda$ to use).

So, can this linear relation between $\sigma$ and best convergence speed (indicated by $\varphi^{'*}_2$ curve) help us to have a better use of $(\mu,\lambda)$-ES or $(\mu,\lambda)$-ES algorithms?

In the other hand, what would we lose if this relation weren't linear at the first place?

(1) Thomas Bäck. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford University Press, Dortmund, Germany, 1996


texts: Suppose we have the following symbols: $\{a,b\}$. Now there are some rules. More than 3 $b$'s are now allowed and $aa$ is not allowed. So $ababab$ is allowed, but for example $abbbbaba$ not (more than 3 $b$'s). There is an easy way to get this working. Suppose you have a string of $n$ characters. Just add between every two numbers a new number so the string is correct. Decoding is not hard: just remove all numbers on even positions. So $abbbbaba \rightarrow axbxbxbxbxaxbxax$ and decoding is the same as just removing the $x$'s. But the problem is that the string size doubles. Is there a more efficient way to accomplish encoding and decoding? So encoding means encode all strings to valid strings and decoding means decode that string back to the original string.


texts: Is this behavior in a programming language inconsistent?

texts:
I'm developing a tiny programming language to try to wrap my head around type inference, and I'm trying to figure out if its behavior makes sense or not. Here's the problem:

The identity function \x.x can't be unified to a single type, but applied to something, it can, i.e. (\x.x) 10 : Int. However, right now, the expression:

((\x.x) (\x.x)) 10

can't be unified, because the expression (\x.x) (\x.x) doesn't have a single type. The type checker doesn't do any evaluation, so it can't tell that the above expression is equivalent to \x.x. The type checker only sees the expression, tries to determine the type of it, and fails before trying to apply it to 10.

Is this typical behavior, or am I being inconsistent with my type inference?


texts:
Consider a graph with $n$ vertices and $m$ edges. The vertices are labelled with real variables $x_i$, where $x_1=0$ is fixed. Each edge represents a "measurement": for edge $(u,v)$, I obtain a measurement $z \approx x_u - x_v$. More precisely, $z$ is a truly random quantity in $(x_u - x_v) \pm 1$, uniformly distributed and independent of all other measurements (edges).

I am given the graph and the measurements, with the distribution promise for above. I want to "solve" the system and obtain the vector of $x_i$'s. Is there some body of work on problems of this type?

Actually, I want to solve an even simpler problem: somebody points me to vertices $s$ and $t$, and I have to compute $x_s - x_t$. There are many things to try, like finding a shortest path, or finding as many disjoint paths as possible and averaging them (weighted by the inverse of the square root of the length). Is there an "optimal" answer?

The problem of computing $x_s - x_t$ is itself not completely defined (e.g. should I assume a prior on the variables?)


texts: Adjective for: algorithm that outputs its input if it is one of its outputs?

texts:
Is there a well established adjective or name for an algorithm such that, given as input any of its own output, always outputs it unchanged? In other words, an algorithm such that it implements a function $f$ with the property $f\circ f=f$. What would be a reference?

My application is a cryptographic security reduction. An example would be an algorithm which on input $X\in\{0,1\}^*$, outputs $1^{|X|}$.

Besides identity, an algorithm implementing $X\mapsto|X|$ in one of $\Bbb Z$, $\Bbb Q$, $\Bbb R$, $\Bbb C$ also comes to mind.

Stationary algorithm or circular algorithm would do, but neither googles. In my experience that means quickly it will google here, bringing circularity to a new level!


texts: Extended version of the paper "Consistent Hashing and Random Trees" with proofs

texts:
I've been reading the following paper:

David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Mathew Levine, Daniel Lewin, "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web", 1997. pdf

In the paper the authors mention that
the proofs will be available in the "full paper".
But I cannot find any extended version of the paper with proofs.
Can someone direct me to a version with the proofs?


texts: communication complexity lower bound for computing median

texts:
In the textbook by Kushilevitz/Nisan, they give an $O(\log n)$-bit protocol for computing the median in the standard 2-party model of communication complexity, where Alice is given a set $X \subseteq [n]$ and Bob is given $Y \subseteq [n]$ and they need to output the median of the multiset $X \cup Y$.

However, it is not mentioned whether there is any non-trivial lower bound. Thus, my question is:

  Are there any non-trivial lower bounds known for finding the median in the 2-party model?


texts: Starting point for cache-oblivious algorithms?

texts:
I'm interesting in learning more about cache-oblivious algorithms and data structures, but there are so many papers out there that I honestly don't know where to start.  I've found Prokup's original thesis on the subject, which seems like a good starting point, but if there's a simple and accessible introduction to the subject I'd much rather start there.  Is there a standard "go-to" reference on the subject?

Thanks!


texts: How come Wikipedia says that Random Turing Machines can provide uncomputable output?

texts:
Wikipedia article mentioned : Hypercomputation
The third paragraph starts off with:

Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses instead on the computation of deterministic, rather than random, uncomputable functions.

Furthermore, according to another article, Random Turing Machine:

In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution.

Am I then correct to say, that in this context, the word random actually means unknown secondary input?
Because from my understanding:

Probability is a well defined area of mathematics
Randomness is rather a layman's term for "I don't really know what's going on here" or rather "I can't know what's going on here".

Sort of like seeds in PRNGs, an argument can be made that PRNGs are not random at all, after all, the very word pseudo-random is an oxymoron. Given an input and the "hidden input" (seed) I can get the same input back every time.
So in this context, is the output of a RTM reaaaallly uncomputable?


texts: Configurations from arrangement of lines

texts:
Suppose we have an arrangement of $n$ lines in the plane. This partitions the plane into regions. We can label each region by a string in $\{+1, -1\}^n$, where the $i$'th coordinate is +1 if the region lies above the $i$'th line and -1 if it lies below the $i$'th line. (By rotating the arrangement if necessary, we can assume that no line is perfectly vertical.)

Say that a subset $S$ of $\{+1,-1\}^n$ is realizable by a linear arrangement if there exists a linear arrangement such that the labels of the regions are exactly the strings in $S$. Is there previous study of which subsets of $\{+1, -1\}^n$ are realizable by linear arrangements? One can also ask the same question for hyperplane arrangements.


texts: Longest path in Complete Directed Graphs

texts:
I searched in Google and checked similar questions on this site, but couldn't find an answer for my problem. I hope this place is appropriate for my problem.
The problem is formulated as follows:

We are given a weighted digraph with the following properties:

The weights are real numbers

Each vertex has a directed edge into every vertex, but without self-loops (i.e. the graph is complete, each vertex has |V|-1 in and out degree)

The weight for some edge $X \rightarrow Y$ is not necessarily the same as for $Y \rightarrow X$ (therefore we can't treat the graph as an undirected graph)

We are also given a source s and a sink t.
The problem is to find the longest path from s to t.
(Obviously the path should not contain any loops, and can contain at most |V|-1 edges)

Even though the problem is NP-hard and even finding a constant factor approximation is NP-hard for the general case, I wonder if for that kind of graphs we can do better.
The questions are:

Is the problem NP-hard?

If yes, how good can the problem be approximated? I would prefer fast running time over good results.

Do you know any good heuristics for the problem? (that work well in practice)

Any comment/answer/reference is appreciated. Thanks in advance!


texts: Fixed parameter Integer Programming circuit depth complexity

texts:
It is well known Lenstra's and Kannan's algorithm achieves $n$-variable parameter $L$-bit integer programming solvability in $O(n^nL)$ time and $O(L)$ space.

If implemented as an arithmetic circuit does it require $\Omega(\log L)$ depth to achieve polynomial size when $n$ is fixed or is the depth just $O(1)$?
How does the depth change if $n$ changes?
Is there a way to measure its bit and boolean circuit complexity?


texts: What is known about lower bounds on the algorithm if P=NP

texts:
I recall Scott Aaronson making the claim that either $P\neq NP$ or he has superpowers.

What reason is there, if any, to believe that it is not the case that any decision procedure has constants (or exponents) that would make an ultrafinitist squirm?

That is to say, if I take "has superpowers" to mean "is capable of practically deciding reasonably sized pathological instances of insert NP-complete problem here", why should I believe that there isn't a third option?


texts: Philosophy behind monotonicity requirement for inductive types

texts:
Is there a good philosophical reason for why inductive types with negative occurrences or non-monotonicity should not be considered valid constructions?  According to my understanding of the Bishop/Martin-Löf view of mathematics, to construct a set is to say how to construct elements of said set (as well as say how elements are identified, but that's not so important for this discussion).  That's fine, but then I don't see why the standard inductive presentation of the naturals is a valid construction, but something like

Inductive bad :=
  | b : (bad -> bad) -> bad.

is not.  To be clear, I understand how such definitions yield inconsistencies and so I certainly understand from a purely pragmatic perspective why such restrictions need to be made.   However, it's one thing to be able to banish inconsistency, and another to be able to give a natural explanation for why such restrictions should be made.


texts: Language of stack configurations of a pushdown automaton

texts:
Consider a pushdown automaton $A$ with stack alphabet $\Gamma$. Let $L$ be the language on $\Gamma$ of the stack configurations encountered during accepting runs of $A$. Is $L$ a context-free language?

Preliminary observations:

$L$ is prefix-closed (any prefix of $L$ is in $L$)
Using Bar-Hillel's lemma, pumping on the context-free language amounts to pumping on the stack language like a regular language. Hence, $L$ can be pumped as a regular language.


texts: A Context-Sensitive Grammar which cannot be recognised by a Parsing Expression Grammar

texts:
It is (currently) an open question of whether every context-free grammar can be recognised by some parsing expression grammar. [1]

However, has it been proven that there exists an example of a context-sensitive grammar which has been proved to be unrecognised by every parsing expression grammar? Or is it theoretically possible that every context-sensitive grammar can be recognised by a parsing expression grammar too?

For example, the canonical context-sensitive grammar which is not context-free, $\{a^nb^nc^n\}$, can be parsed by a parsing expression grammar. [2]


texts: What type system fits the subclass of λ-terms that can be reduced optimally?

texts:
There is a subset of λ-calculus terms that can be reduced by Lamping's Abstract Algorithm without using the Oracle. That is an interesting subset, because only for those terms it is proven that Lamping's algorithm is optimal and superior to naive strategies.

In order to use this in practice, one can write programs on the untyped lambda calculus and experimentally test if Lamping's Algorithm works on them for some inputs. It it does, the term is probably on that subset. For example, my answer to this question is a Church-nat sorting algorithm that was developed this way. That is inconvenient for 2 obvious reasons:

You can't be 100% sure an algorithm will work for all inputs by experimenting it on some.
Programming on the untyped lambda calculus can lead to human type errors.

An immediate solution to problem #2 would be to instead write your programs in a type system on the Lambda Cube (such as System F), but that doesn't work quite well in practice because algorithms on the optimal subset often rely on Scott-encoded data structures (as depicted on my answer above), which are excluded from those type systems. And about problem #1, I'm aware of some type systems based on light logics, but I found them overly complicated and I'm not sure how they could be used in practice.

What type system better fits the subclass of λ-terms that can be reduced optimally, in a way that could be used as the type system of a practical programming language?


texts:
The Hypercontractivity theorem (or Bonami Beckner inequality) is a very useful tool. Unfortunately, it isn't easy to carry over to other spaces than the uniform boolean cube.

In Ryan O'Donnel's Analysis of Boolean Functions, he mentions the following theorem which considers the more general problem of general product spaces:

The "normal" Bonami Beckner however also has a two-function version:

Do you know of anything similar for the case of general product spaces, or $p$-biased functions in particular?


texts: Representing non-planar graphs with overlapping circles

texts:
We know that we can represent any planar graph by a set of circles in the plane, known as a coin graph. Each circle represents a vertex and there is an edge between two vertices if and only if the circles "kiss" at their boundary.

Suppose that instead we allow the circles to overlap, and represent an edge by a pair of circles that intersect in their interior? What class of graphs can we represent in this model? Clearly we can represent complete graphs (every circle intersects every other circle). Can we represent all graphs like this?


texts: Observable correlation vs non-observable causality

texts:
It is frequent to find statistical studies observing some correlation between two events; this correlation is often interpreted by the medias as a causality relation (e.g. "blue-eyed people have more kids" or "obese people have more chronic diseases") although most often there is little scientific support in favor of one causality relation rather than the other. So the reasonable conclusion is that these studies can only observe "correlation" but not "causality". Now suppose that a correlation between two events $A$ and $B$ could be interpreted not as a binary causality (e.g. $A$ implies $B$) but as a ternary relation involving an unobservable "cause factor" trigerring an observable "correlation" (e.g. $K$ implies $A$ and $B$).

This leads to some basic questions that might have some connection with computer science / graph theory. First, even if we cannot detect the "cause factor", can we distinguish experimentally between the above two scenarii? Second, is it still possible to prove "causality" with a more fine-grained knowledge of reality, or do we have to abandon it completely? I guess this second question hinges on physics and philosophy, as it depends on the assumed model of physical reality -- for instance causality makes sense in a deterministic, sequential world but maybe not in some alternate models involving quantum theory and branes ??-

(NOTE ADDED: I expect that my answer will be labeled as "off-topic" but there might still be some cross-disciplinary people interested in it)


texts: Why don't we use larger classes to study determinism vs non-determinism?

texts:
In a previous question about time hierarchy, I've learned that equalities between two classes can be propagated to more complex classes and inequalities can be propagated to less complex classes, with arguments using padding.

Therefore, a question comes to mind. Why do we study a question about different types of computation (or resources) in the smallest (closed) class possible?

Most researchers believe that $P \neq NP$. This distinction of classes wouldn't be between classes that use the same type of resource. Therefore, one might think of this inequality as a universal rule: Nondeterminism is a more powerful resource. Therefore, although an inequality, it could be propagated upwards via exploiting the different nature of the two resources.So, one could expect that $EXP \neq NEXP$ too. If one proved this relation or any other similar inequality, it would translate to $P \neq NP$.

My argument could maybe become clear in terms of physics. Newton would have a hard time understanding universal gravity by examining rocks (apples?) instead of celestial bodies. The larger object offers more details in its study, giving a more precise model of its behavior and allowing to ignore small-scale phenomena that might be irrelevant.

Of course, there is the risk that in larger objects there is a different behavior, in our case that the extra power of non-determinism wouldn't be enough in larger classes. What if after all, $P \neq NP$ is proven? Should we start working on $EXP \neq NEXP$ the next day?

Do you consider this approach problematic? Do you know of research that uses larger classes than polynomial to distinguish the two types of computation?


texts: Lower bounds for Nondeterministic Multiparty Communication

texts:
This is a continuation of my previous question on communication lower bounds for partial boolean functions.

Can someone suggest any reference on lower bounds for nondeterministic multiparty communication? I've been surveying the papers in the field, but everybody seems to show separations of the following type: a lower bound for randomized protocol and an (smaller) upper bound for a nondeterministic protocol. See for example, David, Pitassi, and Viola 2009, Gavinsky and Sherstov 2010, Beame, David, Pitassi, and Woelfel 2010.

Specifically, I would like to know if there exists a norm (e.g. $\gamma_k$ for $k$ parties) that lower bounds nondeterministic multiparty communication in either the number-in-the-forehead or number-in-hand model.


texts:
Suppose I give you $n$ labelled coins $C_1, \cdots, C_n$ of unknown bias. I promise you that

the coins have been sorted by bias (i.e. $\forall i~~\mathbb{P}[C_i=1]\leq\mathbb{P}[C_{i+1}=1]$) and
at least one of the coins is unbiased (i.e. $\exists i~~\mathbb{P}[C_i=1]=\frac12$).

Your task is to find an approximately unbiased coin. That is, you must find $i_*$ such that $\mathbb{P}[C_{i_*}=1] \in [\frac13,\frac23]$. To do this, you should flip as few coins as possible.

Here is an algorithm that completes the task by flipping $O(\log n \cdot \log \log n)$ coins: Perform a binary search over the coins - this takes $O(\log n)$ steps. For each step, flip the coin $O(\log \log n)$ times so that the bias of the coin can be approximated to within $0.1$ with probability at least $1-1/O(\log n)$. A union bound shows that this will be correct with high probabiliy.

Can we do this using $O(\log n)$ coin flips?


texts: I've implemented a neural network (using the back-propagation algorithm) in a digital marketing application, where the algorithm classifies words according to quality, price and another characteristics in an AdWord Campaign.  I would like to know if there is a paper or book (preferably free) that discusses the accuracy rate of acceptance that a neural network should have.


texts: Boolean Functions Where Sensitivity Equals Block Sensitivity

texts:
Some of the work on sensitivity vs. block sensitivity has been aimed at examining functions with as large a gap as possible between $s(f)$ and $bs(f)$ in order to resolve the conjecture that $bs(f)$ is only polynomially larger than $s(f)$. What about the opposite direction? What is known about functions where $s(f) = bs(f)$?
Trivially, constant functions have $0=s(f)=bs(f)$. Also trivially, any function with $s(f) = n$ also has $s(f) = bs(f)$. It is non-trivial but not too hard to show that any monotone function also satisfies this equality. Are there any other nice classes of functions that have $s(f) = bs(f)$? A complete characterization would be ideal. What if we further strengthen the requirements to $s^0(f) = bs^0(f)$ and $s^1(f) = bs^1(f)$?
The motivation for this question is simply to get some intuition for how sensitivity relates to block sensitivity.
Definitions
Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function on $n$-bit words. For $x \in \{0,1\}^n$ and $A \subseteq \{1,\ldots,n\}$, let $x^A$ denote the $n$-bit word obtained from $x$ by flipping the bits specified by $A$. In the case that $A = \{i\}$, we will simply denote this as $x^i$.
We define the sensitivity of $f$ at $x$ as $s(f,x) = \# \{ i | f(x^i) \neq f(x)\}$. In other words, it is the number of bits in $x$ that we can flip in order to flip the output of $f$. We define the sensitivity of $f$ as $s(f) = \text{max}_x s(f,x)$.
We define the block sensitivity of $f$ at $x$ (denoted $bs(f,x)$) as the maximum $k$ such that there are disjoint subsets $B_1, B_2, \ldots, B_k$ of $\{1,2,\ldots, n\}$ such that $f(x^{B_i}) \neq f(x)$. We define the block sensitivity of $f$ as $bs(f) = \text{max}_x bs(f,x)$.
Finally, we define the 0-sensitivity of $f$ as $s^0(f) = \text{max} \{ s(f,x) | f(x) = 0 \}$. We similarly define 1-sensitivity, 0-block sensitivity, and 1-block sensitivity , denoted $s^1(f)$, $bs^0(f)$, and $bs^1(f)$, respectively.


texts: Name and references for balanced variant of the long code?

texts:
The long code (arising in PCP theory etc) is an encoding of a set of $k$ values, using binary strings of length $2^k$ (double exponential in the number of bits needed to specify a value), with one coordinate position in the encoding for each of the $2^k$ different binary functions on the input values. Instead, I want to consider a shorter but still doubly exponential code, with one coordinate position for each of the $\tbinom{k}{k/2}/2$ partitions of the $k$ values into two equal-sized subsets (assuming $k$ is even). Each partition can be thought of as corresponding to two different binary functions (the functions whose inverse images form the given partition) and we choose arbitrarily which one of these two functions to use.

The minimum distance of the code (and in fact the distance between all pairs of codewords) is $\tbinom{k-2}{(k-2)/2}$, smaller than the length of the code by only a factor of $\tfrac{k}{2k-1}>\tfrac{1}{2}$. For instance for $k=8$ we get a code of length 35 with minimum distance 20, which http://www.codetables.de/ tells me matches the Griesmer bound for binary linear codes of the same size (rank 3 or size 8).

I am interested in this for reasons only vaguely related to coding theory, but it seems likely to me that the coding theorists have already studied this code. Unfortunately, I don't know of a good way of looking up coding schemas by the formulas for their parameters. If it has been previously studied, what is it called? And what are some references to it?

(BTW, the property I actually care about, which is easy enough to prove using Sperner's theorem, is that this is the longest possible binary code in which each two positions are independent of each other, in the sense that all four possible combinations of symbols in the two positions are realized by codewords. There appears to be something in the literature called a Sperner code but it's transposed from this — each codeword has equally many zeros and ones, rather than the property of the code I'm looking at, where each bit position has equally many codewords for which that position is a 0 or 1.)


texts: Which well-known algorithmic problem is this an instance of?

texts:
Consider that you have n counters initialised with numbers $M_1 \dots M_n$. In each round you decrement exactly $k$ out of these counters. Keep doing this until at least $n-k+1$ counters are zero, so you can't continue. Determine the maximum number of rounds.

This can be illustrated with muffins, e.g. 18 nuts, 12 apple, 10 chocolate, 9 blueberry available. Form a maximum number of plates @ 3 different muffins each.

One can solve this with a greedy approach which always decrements the k largest counters. The proof that this is optimal is not hard but also non obvious.

My question is under what name this apparently rather natural question appears in the literature.


texts: Using an oracle to find a vector $b$ for which $Ax=b$ has a solution

texts:
There is an oracle built around a hidden $m\times n$ matrix $A$ all of whose entries are 0 or 1, where $m>n$.   The oracle takes as input an integer vector $b$ with positive entries, and answers as follows:

The oracle answers YES, if there exists a real vector $x$ with $Ax=b$.
The oracle answers NO, if no such real vector $x$ exists.

It is furthermore known that there exists some YES-vector $b$, whose entries are all bounded by the known (explicitly given) constant $c$.

  Question: What conditions on $A$ would enable us to find a YES-vector $b$ in polynomial time?

I'm actually working on a slightly different problem, and the context is a bit hard to explain: in my problem matrix $A$ represents an incidence matrix for a minimum edge clique cover of a graph $G$. Each column of $A$ is a (maximal) clique in $G$, with a $1$ in entry $i,j$ if vertex $i$ is in clique $j$. Ideally, such an $A$ would satisfy the problem statement.

I am interested in deterministic algorithms, not a randomized algorithm.

I was wondering which search terms I should put into Google, and what type of literature exists on this problem.


texts:
Tree decomposition is hard in the worst case but greedy method seems to be near-optimal on small real-life networks.

Is anything known about hardness of tree decomposition of a "typical" instance of some class of graphs?
Is there example of a family of graphs where greedy methods for tree decomposition do badly?


texts: Complexity of listing all minimal cut sets / connected 2-partitions of a graph

texts:
I am trying to find an algorithm that would give me for a given graph all minimal cut sets or equivalently all ways to partition the graph in two connected components. I am searching for an algorithm that ideally would have the complexity linear in the number of cut sets, however, I only find papers describing algorithms that would generate all minimal cut sets between a fixed vertex pair. I would then have to run any algorithm for each pair and remove duplicates, so I am searching for a better approach. Does someone of you know any upper/lower bounds of the complexity of this problem (or even better, an optimal algorithm)? I would also be interested in results concerning special graphs, e.g. max degree k or so.

Best,
Vany


texts: Embedding a n-tree into a b-dimensional space

texts:
Given a (directed) n-tree $T=(N,E,r)$ rooted in $r\in N$, I want to represent each node $n\in N$ at most as a $m$-dimensional vector $v_n\in \mathbb{R}^m$ (From the current Yuri's reply, m cannot be $b$). In particular, given $h$ the height of the tree (that is, the maximum path length starting from $r$), I want to guarantee that $\forall a,b\in N. \|v_a-b_b\|_2\leq h$ if and only if there exists a directed path $\pi(a,b)$ or $\pi(b,a)$ in $T$.

Example, given the following tree rooted in $1$, $(\{1,2,3,4\},\;\{(1,2), (1,3),(3,4)\},1)$, I would instantiate the distance constraints as follows:

$\forall (a,b)\in E\cup \{(b,a)|(a,b)\in E\}. \|v_a-v_b\|_2\leq 1$
$\|v_1-v_4\|_2\leq 2$ by transitive closure
$\forall (a,b)\in V^2\backslash (E\cup \{(b,a)|(a,b)\in E\}. 3\leq \|v_a-v_b\|_2\leq 4$

I was thinking to reduce this problem into the Distance Geometry Problem, and to use the former distances to feed known solvers like DGSOL or MD-Jeep: while the first commits non-negligible errors, MD-Jeep returns some errors during the computation of the torsion angle, and therefore cannot provide a viable solution. Is this a problem of the Distance Geometry Problem itself, or are there other implementations that would not suffer from the same problem? Alternatively, is it possible to express this problem using mathematical programming, i.e. using one of the already existing libraries?


texts: What's the hardest problem with a non-trivial exact algorithm?

texts:
Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough.

I’ve also came across some algorithms which are not practical even for very small inputs, and their importance is questionable.

I’m wondering what's the "hardest" (time complexity-wise) problems people have worked on its exact solution:

The problem is in NP.
A non-trivial exact algorithm is known for the problem (preferably from the last few years).
No better algorithm is known.

For example, the minimum dominating set of queens has an algorithm which runs in $O(39.51^n\cdot poly(n))$ time.


texts: Good MCMC methods for exploring the space of independent sets

texts:
Let $G$ be an edge-weighted graph, and let (S, V-S) be a feasible pair if S is a maximal independent set. The weight of a feasible pair is computed by finding for each element of V-S the lightest edge connecting it to S, and summing the costs (such an edge must exist since S maximal). The goal is to find a minimum weight pair.

This problem is NP-hard and is likely to be fairly hard to approximate (it encodes vertex cover at the very least). We're looking at heuristics that might be effective in practice, and one idea is to do some kind of metropolis-hastings-type walk on the space of all independent sets (since given an independent set, computing the weight is easy).

I know that there's a fair bit of study of sampling over independent sets (for example, this). My question is:

  Are there good sampling procedures
  that can be adapted to this weighted
  case ? I suspect I'd like some kind of
  procedure that does a
  metropolis-hastings-type step to
  decide whether to move or not, and so
  the question really is: what are good
  local moves  ?


texts: Does this variant of Multiplicative Linear Logic with mix rule enjoy cut elimination?

texts:
In Multiplicative Linear Logic (MLL), addition of the mix rule eliminates 'connectedness' from Danos-Regnier criterion. I'm investigating how the criterion changes if we do not distinguish between tensor and par.

Let's take a MLL inference rules with the mix rule and forget the difference between tensor and par:

$$ \frac{}{\vdash A, A^\bot} \;\mathtt{id} $$
$$ \frac{\vdash \Gamma_1, A\quad \vdash \Gamma_2, A^\bot}{\vdash \Gamma_1, \Gamma_2} \;\mathtt{cut} $$
$$ \frac{\vdash \Gamma_1 \quad \vdash \Gamma_2}{\vdash \Gamma_1, \Gamma_2} \;\mathtt{mix}$$
$$ \frac{\vdash \Gamma, A, B}{\vdash \Gamma, A \cdot B} \;\mathtt{par}$$
The tensor rule is obsolete as it can be derived from the mix and par rules:
$$ \frac{\vdash \Gamma_1, A\quad \vdash \Gamma_2, B}{\vdash \Gamma_1, \Gamma_2, A \cdot B} \;\mathtt{tensor} $$

My intuition is that not all proof-structures are valid i.e. some variant of Danos-Regnier criterion for this system still is necessary. The intuition is that it admits cycles but only the trivial ones, not 'real' deadlocks. But I don't know how to formalize it, so I'll move to cut elimination formalization.

The above, might be considered a type system for an interaction net with a single self-annihilating node $ \mu $ (notation defined in the footnote):
$$ \{\ldots, e \frown \mu (a_1, a_2), e \frown \mu (b_1, b_2), \ldots, \} \rightsquigarrow \{\ldots, a_1 \frown b_1, a_2 \frown b_2, \ldots \}$$

Let's extend standard cut-elimination procedure with one more rule:
the trivial cycle, made from identity and cut only, disappears:

$$
\{\ldots, a \frown b, b \frown a, \ldots, \} \rightsquigarrow
\{\ldots, a \frown a, \ldots \} \rightsquigarrow
\{\ldots, \ldots \}
$$

Example of a deadlock: $a \frown \mu(a,b)$.

Questions:

Does the described type system, when applied in an obvious way to the interaction net, eliminates the possibility of deadlocks?
Does the type system enjoy cut elimination?
Are these two questions equivalent?
Are there any publications about it?

Footnote

Notation for the nets:

Net is a set of links.
Variables denote edges.
$ e \frown \mu(a,b)$ represents an a node $\mu$  with two auxiliary edges $a, b$ and a principal edge $e$.
Each variable is present in the set exactly 1 or 2 times, 1 means it is a 'free edge',
$\frown$ is commutative.
Two connected edges are just an edge: $\{\ldots, a \frown b, b\frown c, \ldots \} \rightsquigarrow \{\ldots, a \frown c, \ldots \}$


texts: directed or bidirected in relation to mssp (Multiple source shortest path)

texts:
Firstly I wanted to ask. If I have a undirected graph and split all the edges into two directed edges is it still called directed or does it become bi-directed?

The main question is i have a graph with n sources all in the same graph until now I thought I could use the mssp method provided by Klein in this paper but it says that the graph must be a directed graph. Yet if I have an undirected graph and split each edges into two components with same weight I don't think it will be able to solve the problem or it does not matter?

Due the bidirection of the graph,  will it have the first source visit each and every node without the other sources implying that I can't adapt the graph such that I can have a Shortest path tree as if I ran a dijkstra on the other sources does it?

Also I wanted to make sure does this method gets all the shortest path trees? because i was getting confused.

Klein algorithm is able to compute all the shortest path trees for specific starting nodes found on a single face (lets agree on that). Its secret is that it will do adaptations of specific darts found in the dual graph. if it is an undirected graph turning it into directed graph will become a bi directed graph by the following:
can you still state that such graph is directed and also bi directed?

A directed graph is called bi-directed if the there is a mapping reversal() that maps each edge e=(v,w) to a reversal edge (denoted as reversal(e)) such that the following holds:

reversal(e)=(w,v), that is, the reversal edge of e indeed is reversely directed, so reversal() deserves its name.

reversal(reversal(e))=e, that is, also in the presence of multiedges always two edges correspond to one another.

e is different from reversal(e), that is, also in the presence of self-loops each self-loop edge has a different self-loop edge as its reversal edge. (don't have self loops)

Each edge e occurs as the reversal edge reversal(e') of a different edge e', that is, the mapping is bijective.

would you still be able to state that a I directed graph is also a directed graph?


texts: Interpolating the Tutte polynomial at the values of two hyperbolas

texts:
In a MO question
basically I asked when the Tutte polynomial of planar graph
can be uniquely determined by the polynomially computable values at the special points
and at the two hyperbolas. The solution is the unique solution
of certain integer program $L$. Possibly misleading experimental
data suggests this is possible sometimes.

Computing the Tutte polynomial at non-trivial points
is $\#P$-complete. In case the integer program $L$
has unique solution, one call to a $NP$-complete
oracle would solve $\#P$-complete problem.

  In case this happens, what are the complexity
  implications for the subclass of planar graphs
  satisfying this?

Suppose the integer program $L$ has polynomially many solutions corresponding
to polynomials $F_{G,i}(x,y)$. (The experimental data
suggest this).

  Given $G$ and a set of polynomials $F_{G,i}$ with
  the promise that one of them is the Tutte polynomial,
  what is the complexity of finding the Tutte polynomial?

AFAICT it is not harder than $\#P$ since we can compute
the Tutte polynomial at positive random $(x_i,y_i)$ and
see which of $F_{G,i}$ agree with the value.


texts:
I apologize in advance if this question is outside the scope of this Exchange community; if so, perhaps someone can point me in the right direction.

I am curious if there is a theoretical notion of "total work" of a problem, and possibly what kind of analyses could be done to explore the work required of a given problem. I realize this question is quite "soft", but any insight would sate my curiosity. Let me explain what I mean by "total work":

Suppose we have problem $X$ (e.g., sort a set of objects by some key, solve an initial/boundary value PDE, find all $4-$cycles in a graph, etc...), and we come up with some algorithm $Y$. We can do some asymptotic analysis to come up with some performance bounds, (e.g., $O(\log n)$ time but $\Omega(n^2)$ memory).

Now, algorithm $Y$ was just one of perhaps an infinite number of ways to solve problem $X$, making the performance of $Y$ a property of $Y$ rather than $X$. In my (limited) experience, there seems to almost always be a theme of "different $Y$'s for different guys": $Y_1$ will provide optimal time of an algorithm at the expense of memory, whereas $Y_2$ will solve $X$ with the absolute least amount of memory while forfeiting the time speed-up logic; a prototypical example being using adjacency lists vs adjacency matrices for graph representations (though in this example a priori knowledge of the use case informs the best approach).

This implies there is some inherent "total work" required to solve $X$, regardless of choice of $Y$, and paints the picture that for all solutions $Y$ to problem $X$, $Mem(Y)*Time(Y)\geq TotWork(X)$:

This is of course a gross simplification, as there are any number of things that contribute to the overall performance of an algorithm, whether it's machine architecture, parallelizability, language, etc., but it seems in all cases there is a set number of resources required to solve a problem, and the algorithm can be chosen to suit the respective availability of resources.

Is there any literature on this concept? (As I'm writing this, I'm thinking the concept is so fundamental to algorithm design and analysis that it's probably in any freshman text...)


texts: Satisfiability threshold and partially random formulas

texts:
My understanding is that if we have a totally random k-SAT formula, for a ratio $m < \alpha n$ far enough below the satisfiability threshold, we can solve for satisfiability in polynomial time (with a high probability of success as $n$ tends to infinity).

What I'm curious about, and which I guess is the beginner's question, is what happens if we increase $k$, $m$, and $n$.  To elaborate, we can suppose that the original formula is significantly above the threshold, and therefor no polynomial method is guaranteed.  However, the new increase in $k$ puts the formula significantly below the threshold, and so if the new formula was random, it could be solved in time polynomial in the new $n$.

However, the new formula is not random.  It's based on the old one.  So it seems that the polynomial methods don't apply.  My curiosity is, if we could generate several formulas with increased $k$, $m$, and $n$, below the threshold, they may in some way be considered random.  So perhaps the randomness criterion can be satisfied.  I'm wondering if there is any way to prove this...

ANOTHER APPROACH

Perhaps what I'm really after is finding out what constitutes randomness in satisfiability instances.  Of course it's a random formula with the proper parameters, but doesn't this mean that if we can repeatedly generate formulas with the same parameters, they can be considered random?

I'm really hoping that someone can give me a better perspective on things.  I keep wondering if there's some way to modify SAT formulas to take advantage of polynomial methods.


texts: Unary languages recognized by two-way deterministic counter automata

texts:
2dca's (two-way deterministic one-counter automata) (Petersen, 1994) can recognize the following unary language:
\begin{equation}
\mathtt{POWER} = \lbrace  0^{2^n} \mid n \geq 0 \rbrace.
\end{equation}

Is there any other nontrivial unary language recognized by 2dca's?

Remark that it is still unknown whether 2dca's can recognize $ \mathtt{SQUARE} = \lbrace  0^{n^2} \mid n \geq 0 \rbrace $?

DEFINITION: A 2dca is a two-way deterministic finite automaton with a counter. A 2dca can test whether the value of the counter is zero or not, and increment or decrement the value of the counter by 1 in each step.


texts: Algorithm to transform an arbitrary MIP problem into the corresponding formulation for PSO

texts: Is there an algorithm to transform an arbitrary Mixed Integer Programming problem into the corresponding formulation for Particle Swarm Optimization? I have found some information related to the use of penalty functions to avoid violation of constraints, but not a well defined procedure to convert the objective function and each of the constraints as required for a PSO solution.


texts: If I know pretty well '(a,b)', I know pretty well 'a', or 'b', or 'a xor b'

texts:
I've a quite simple problem: let's imagine I have a couple of bits $(a,b) \in \{0,1\}^2$ sampled uniformly at random. Then, I give a function of these bits $f(a,b)$ (it can be any function, including identity, or a constant function, or a random non deterministic function, or a function that encrypts a and b...) to an adversary $A$, that will give me back two bits $(a',b')$.

If by any chance, $A$ can guess correctly $(a,b)$ with a probability (taken over $a$, $b$, the randomness of $f$, and the randomness of the adversary) better than random, i.e:

$$\Pr[(a',b') = (a,b)] > 1/4$$
can I say that either:

he is good to guess $a$, i.e. $\Pr[a' = a] > 1/2$
or he is good to guess $b$, i.e. $\Pr[b' = b] > 1/2$
or he is good to guess the xor of $a$ and $b$, i.e. $\Pr[a' \oplus b' = a \oplus b] > 1/2$

?

NB: for sure the first two conditions are not enough, as if $f(a,b) = a \oplus b$, then the adversary that picks a random $a'$, and sets $b' := a' \oplus f(a,b)$ will guess $(a,b)$ with proba $1/2 > 1/4$, and still the proba for him to get $a' = a$ will be 1/2 (and same for $b'$). I have the feeling that adding the last line is enough, because it "makes sure" that $A$ cannot guess also the correlation between $a$ and $b$, but not sure how to prove it that it's enough.

Thanks!


texts: Prefix Probability in Stochastic Languages

texts:
I was reading the following paper (http://aclweb.org/anthology/W/W13/W13-1801.pdf) and they state that, given a Probabilistic Finite Automata $A$ and a string $w$, finding the probability $Pr_A(w\Sigma^*)$ is simple (section 3, property 3. Just before the start of section 4). However, this isn't immediately clear to me since, even using some dynamic programming approach, you may have to compute the probability of an infinite number of paths (since it is not acyclic) starting at all of the states that are the last state reached in a path, $\Theta$, that generates $w$.

I was not able to find an answer in the references of that paper or any relevant papers on the subject.

To summarize, I am looking for an algorithm that, given a PFA $A$ and a string $w \in \Sigma^*$, returns the probability $Pr_A(w\Sigma^*)$. in other words, the probability of any string having $w$ as a prefix.

Thanks in advance.


texts: Definition for MSO2 for arbitrary structures

texts:
I am not able to find a rigorous definition of MSO_2 logic for arbitrary structures (which I can cite). MSO_2 for graphs is often used and defined, i.e. in On the Parameterised Intractability of Monadic Second-Order Logic - Stephan Kreutzer. The only "definition" for MSO2 on structures I found was in A logical approach to multicut problems - Gottlob, Lee.

"The definition of MSO2 can be easily
generalized to arbitrary structures by allowing quantifi-
cation over subsets of the input relation (notice that in
the case of a graph, the input relation is just the edge re-
lation). Thus, for example, if a relational symbol R is
part of the signature, then a subformula (∃X ⊆ R)φ(X),
expressing that there exists a subset X of the relation R
such that φ(X) holds for some formula φ, could be part
of an MSO2 formula."

While this is enough explanation to know what MSO2 on arbitrary structures is, I really would appreciate if someone could give me a pointer to a formal, rigorous definition somewhere in the literature.


texts:
I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007.
The cliques should have exactly 17 vertices.

The algorithm should be fast, because of the size of the graph.

I had the following idea:

Delete all vertices with a degree of 16 or less.
Iterate over every vertex

try to add another vertex:

If the clique has exactly 17 vertices: Add it to a list
Else: Keep trying to add vertices

If no more vertices can be added: go back to the latest point where you had the choice to add some vertices and add one of those that could not be added before.

I didn't implement this algorithm, because I think it will be quite slow. Do you know better ones?


texts: Graph has several MST what does it mean combinatorically?

texts:
This question is not theoretical, it's about combinatorial meaning.

In graph theory there is a notion of complexity of a graph, which is equal to the number of spanning trees in a graph, which combinatorically simply means how much the graph is 'connected' (it is the way I understand it, is there any other combinatorial meaning? (there are different meanings of 'connectivity', including algebraic connectivity, which is second eigenvalue of Laplacian, but this one is more intuitive, as I think)). There is a fast algorithms to compute complexity of a given graph (look here for the discussion).

There is also a fast algorithm to compute the number of minimal spanning trees(MST) of a given  weighted graph (for more information read this paper).

The question is: what does having several MST's mean in terms of graph and distances?

P.S. It certainly means that not all distances are different, but, maybe there is some property, which provides more interesting consequences?

Thank you!


texts:
I need to show that there exists a polynomial time algorithm that inputs a deterministic automata $A$, and decides if $A$ accepts a word w if and only if it also accepts any word obtained by permuting the letters of w.

Would appreciate any help.


texts: Composition of regular expressions with lookahead into DFAs

texts:
Let's say we have a regular expression ("a" | "b"(~!"b"))*, written in Perl or other similar languages that support lookahead, which should match a list of a and b's where b's are not followed by b's.

The Perl regular expression engine is not based on Thompson DFAs and uses arbitrary backtracking, which I'm not looking for. Do you know of any known method for translating such a regular expression with lookahead into an NFA and then to DFA that accepts the described language? Any papers that describe the challenges of adding lookahead and lookbehind to DFAs and how to compose them?

I have done some trial and errors and it looks like composition in face of the Kleene star operator is problematic.


texts:
Let $A,B$ be two automata over the same alphabet $\Sigma$; they are supposed to be complete, strongly connected DFAs. We denote by $._A$ (resp. $._B$) the action induced by $\Sigma^*$ over $Q(A)$, i.e. $u ._A s$ designates the state reached from $s$ upon reading $u$ - note that this is more commonly denoted by $\delta_A(u,s)$ but we adopt the first notation for conciseness.  Say that an "automata relation" between $A$ and $B$ is a relation $R \subseteq Q(A) \times Q(B)$ such that:

(*) if $R(s,t)$ holds, then for any $u,v \in \Sigma^*$ we have: $u ._A s = v ._A s \Rightarrow u ._B t = v ._B t$.

Given $R$ and $t \in Q(B)$, we then define $R^{-1}(t) = \{ s \in Q(A) : R(s,t) \text{ holds} \}$.

Given such a relation, it is possible to define an action of $Q(A)$ over $Q(B)$ as follows: given $t \in Q(B)$ and $s \in Q(A)$, we define $s^{-1} t$ as the unique state $t' \in Q(B)$ such that for every $s' \in R^{-1}(t)$, $L_A(s',s).t = \{t'\}$. Note that the existence of $t'$ follows from the strong connectedness of $A$, and that the unicity follows by observing that if $u,v \in L_A(s',s)$, we have $u ._A s' = v ._A s' = s$ and thus $u ._B t = v ._B t = t'$.

Now, given the tuple $T = (A,B,R)$ and given two weight functions $f,g$ over $Q(B)$, let us define the "theta function" $\Theta_{T,f,g}(s) = \sum_{t \in Q(B)} f(t) g(s^{-1} t)$.

Question: what are the interesting questions to ask about this notion?

(Some examples and suggestions should follow, I'm still trying to clear my thoughts on this problem.)


texts: Is it possible to test if a computable number is rational or integer?

texts:
Is it possible to algorithmically test if a computable number is rational or integer?
In other words, would it be possible for a library that implements computable numbers to provide the functions isInteger or isRational?

I am guessing that it is not possible, and that this is somehow related to the fact that it is not possible to test if two numbers are equal, but I don't see how to prove it.

Edit: A computable number $x$ is given by a function $f_x(\epsilon)$ that can return a rational approximation of $x$ with precision $\epsilon$: $|x - f_x(\epsilon)| \leq \epsilon$, for any $\epsilon > 0$. Given such function, is it possible to test if $x \in \mathrm{Q}$ or $x \in \mathrm{Z}$?


texts: Are there any standard recent survey articles on quantum error correction (and may be including fault Tolerant computing)? The most standard ones that many people refer to are this and this. Both of them being relatively old, are missing some standard things such as Surface codes, codes comng from homology or LDPC codes. I am looking for survey paper giving indication of currently where do we stand.


texts: Sample complexity of distinguishing two Gaussian distributions?

texts:
Below is a description of the problem:

Suppose I have two $p$-dimensional Gaussian distributions with the same covariance matrix $\Sigma$ and means $\mu_1$, $\mu_0$.

And I can get $n$ samples $X_1^{(1)}, X_1^{(2)}, \dots, X_1^{(n)}$ from $\mathcal{N}(\mu_1, \Sigma)$, and another $n$ samples $X_0^{(1)}, X_0^{(2)}, \dots, X_0^{(n)}$ from $\mathcal{N}(\mu_0, \Sigma)$.

Then I flip an unbiased coin $b\in\{1,0\}$, and take a sample $s$ from $\mathcal{N}(\mu_b,\Sigma)$.

I then give the samples $X_1^{(1)}, X_1^{(2)}, \dots, X_1^{(n)}$ and $X_0^{(1)}, X_0^{(2)}, \dots, X_0^{(n)}$ to an algorithm with the sample $s$. The algorithm outputs a bit $b'$ to indicate that the algorithm thinks that $s$ is from $\mathcal{N}(\mu_{b'},\Sigma)$.

Note that the algorithm does not know $\Sigma$, $\mu_1$, $\mu_0$.

The question is: How large should $n$ be so that $\Pr[b=b'] \geq \frac{1}{2}+\epsilon$?

(The bound should be given in terms of $\epsilon$, $\Sigma$, $\mu_1$, $\mu_0$.)

Are there any papers that have solutions to this problem?


texts: It is common knowledge that a universal Turing machine can simulate any Turing machine with logarithmic overhead. Is it possible to make this overhead constant by constructing an analogous "Universal" multi head Turing machine?


texts: Counting distinct elements in a stream with expiration

texts:
Counting the number of distinct elements in a stream is a well-known and studied problem in computer science, for example Flajolet-Martin algorithm.
There are algorithms for calculating the number of 1s in a binary stream in a fixed-length window, such as the well-known Datar-Gionis-Indyk-Motwani algorithm.
Suppose we have a stream with expiration: every element in the stream is assumed to have expiration time. The question is to estimate the number of distinct elements in the stream which haven't yet expired.
Is there any known algorithm for this?


texts:
I have a profile hidden Markov model that I use to identify all instances of a user-defined pattern of symbols in a long sequence of symbols. I use the Viterbi algorithm to find the most probable path that generates that long sequence of symbols, and it all works very well to identify the user's pattern. But I'm now interested in extending this, and identifying the k-most probable paths through my model that would generate some long sequence. Is there an existing algorithm to do this? I've come across something called the "1-best" or "k-best" algorithm, but I can't find much of anything describing it.

I've also considered what I'm sure would be a heuristic, by finding the most probable path and then returning the neighbourhood around it. This would be found by iterating over each move between states in the most probable path, setting that particular step to 0, and resolving using Viterbi. This would obviously increase the run-time by a factor of (length of the path ~= length of pattern), which I suspect will be reasonable for my purposes.

Has anybody come across something like this, or can anybody see anything obviously wrong in my neighbourhood idea? I'd appreciate any feedback. As a note, this has been cross-posted to the Data Science forum.


texts: Hardness of approximation assuming the existence of one-way functions

texts:
This question is inspired by a question posed by Shiva Kintali, Hardness of approximation assuming NP != coNP
. Multiplication of two prime numbers of equal size is strong candidate for one-way function. We know the $P \ne NP$ does not imply the existence of one-way functions.

  Are there any hardness of approximation results assuming the existence of one-way functions?

Ideally, assuming $P \neq NP$ would not be sufficient to prove such hardness of approximation result and we must assume that existence of one-way functions to prove such hardness of approximation result.


texts: Is there an oracle that separates two complexity classes known to be equal?

texts:
We know that there exist two oracles $A$ and $B$ such that $P^A=NP^A$ and $P^B\neq NP^B$, this implies the obstacle of proving $P\neq NP$ using diagonalization.  I just wonder if there exist two complexity classes, say $A$ and $B$ and oracle $O$ such that $A=B$ but $A^O\neq B^O$?

I am not sure if it is a research-level problem. So don't hesitate to close it if not.

Thanks.


texts: What do you do when you cannot make progress on the problem you have been working on?

texts:
I am a 2nd year graduate student in theory.
I have been working on a problem for the last year (in graph theory/algorithms).
Until yesterday I thought I am doing well (I was extending a theorem from a paper).
Today I realized that I have made a simple mistake.
I realized that it will be much harder than I thought to do what I intended to do.
I feel disappointed so much I am thinking about leaving grad school.

Is this a common situation that a researchers notices that her idea is not going to work after considerable amount of work?

What do you do when you realized that an approach you had in mind is not going to work and
the problem seems too difficult to solve?

What advice would you give to a student in my situation?


texts: Error correction that adapts to different error rates

texts:
Say we have $N$ bits that we'd like to store in an $M$-bit error correcting code, where $M > N$.  Given $\epsilon > 0$, as long as $N > N_0(\epsilon)$ we can recover the original bits as long as any $N(1+\epsilon)$ of the $M$ bits are correct.

Now say the bits are ordered in decreasing order of importance.  Can we pick a single $M$-bit code so that if $K > K_0(\epsilon)$ out of the $M$ bits are uncorrupted, we can recover the first $K(1 - \epsilon)$ original bits correctly?  Here the difference is that the code is independent of $K$.


texts:
I'm reading Causal Memory:
Denitions, Implementation and
Programming and trying to get through the proof of liveliness of the algorithm around the middle of page 9, and I'm not really following it. There's almost certainly a typo/misprint when they refer to the $(s(q) \mathbin\bot 1)$st write. I assume they meant $(s(q) - 1)$st, but even then I'm not really following the reasoning of the proof.

Does anyone have a reference to this proof in the context of a causal multicast that I could look through instead? (or in any other context?)

Alternatively, can someone try to explain the proof. In particular I don't get:

"Let $\hat{w}$ be the $(s(q)\mathbin\bot1)$st write." Even assuming $s(q) - 1$, what if $s(q)$ is $0$ or $1$?
Why does lemma 1 say that $t(\hat{w}) \preceq t(w)$?
Even if we assume $t[j] \ge s[j] - 1$ (equivalently $s[j] \le t[j] + 1$), why is this sufficient? Don't we need to show $s[j] \mathbf{=} t[j] + 1$?

Sorry if this question isn't appropriate/is tagged incorrectly.


texts: What's the bias of random polynomials with low degree over GF(2)?

texts:
I have a question concerning low-degree polynomials and probability:
What is the (assyptotic behavior of the) probability that a
random* polynomial, $p$, over GF(2), with degree $\le d$ and n variables
has $bias(p) \triangleq |\Pr_{x\in\{0,1\}^n}(p(x)=0)-\Pr_{x\in\{0,1\}^n}(p(x)=1)| \gt \epsilon$.

*When I'm writing random polynomial with degree $\le d$ and n variables, you can think of each monomials of total degree $\le d$ picked with probability 1/2.

The only relevant thing I know is a variant of Schwartz-Zippel that states that if the polynomial is nonconstant then its bias is at most $1-2^{1-d}$. Hence, for $\epsilon=1-2^{1-d}$ the probaiblity is exactly $1/{2^{{n \choose 1}+\ldots+{n \choose d}}}$ where this is the probability that $p$ is a constant. Unfortunately, this $\epsilon$ is quite big.


texts: What are the inclusion relationships if any, between the classes Pspace, PLS, PPP, PPA and PPAD

texts:
I have been thinking about Pspace in conjunction with searching for a Natural Notion of Stablilty for Complex Dynamical Systems.

A natural question in this direction is the Nash equilibrium. Surprizingly, it appears that Games in Normal Form have Nash equilibria which is PPAD complete. This has led myself to wonder about the inclusion relationships of various associated Complexity Classes.

Thanks in advance.


texts: Matrix Coloring under Vertical and Horizontal Constraints

texts:
I'm searching for the correct name of the following NP-complete problem. I  would also appreciate answers pointing to problems with similar-looking variations.

The input consists of

A set of colors $\Sigma$ with $|\Sigma|=n^{O(1)}$.
An $nxn$ square matrix $M$ where each entry $M_{ij}$ is a subset of $\Sigma$
For each $i\in [n]$ and each $j\in [n-1]$, a set $H_{ij}\subseteq \Sigma\times \Sigma$ of horizontal constraints.
For each $i\in [n-1]$ and each $j\in [n]$, a set $V_{ij}\subseteq \Sigma\times \Sigma$ of vertical constraints.

A solution for the problem is an $n\times n$ matrix $N$ where each entry $N_{ij}$ belongs to $M_{ij}$, each pair horizontally consecutive entries $(N_{ij},N_{i(j+1)})$ belongs to $H_{ij}$ and each pair of vertically consecutive entries $(N_{ij},N_{(i+1)j})$ belongs to $V_{ij}$.


texts: Upperbound on the degree of a boolean function in terms of its sensitivity

texts:
A very interesting open problem in the study of complexity measures of Boolean function is the so called sensitivity vs block sensitivity conjecture. For background on sensitivity versus block sensitivity you can look at the following blogpost of S. Aaronson at http://www.scottaaronson.com/blog/?p=453.

To best of my knowledge, the best upper bound known on $bs(f)$ in terms of $s(f)$ is $bs(f)=O(e^{s(f)}\sqrt{s(f)})$. [Kenyon, Kutin paper] But of course maybe it is more convenient to relate $s(f)$ to some other complexity measure of $f$ say $\deg(f)$, the degree of $f$ as polynomial over $\mathbb{R}$, i.e. the size of its highest Fourier coefficient.

The question is what's the best upper bound known on $\deg(f)$ in terms of $s(f)$?


texts:
I would like to find examples of (unweighted) optimization problems $\Pi$ that satisfy 1) or 2):

1) $\Pi$ is NP-hard but polytime solvable in the class of graphs with diameter $\le k$, for all $k\ge 1$.

2) there is a $k_0\ge 1$ such that $\Pi$ is polytime tractable in the class of graph with diameter at most $k_0$ but NP-hard in the class of graphs with diameter at most $k_0+1$.

Any ideas ? What about DominatingSet for instance ?


texts: How to produce a random graph that does not have a Hamiltonian cycle?

texts:
Let class A denote all the graphs of size $n$ which have a Hamiltonian cycle. It is easy to produce a random graph from this class--take $n$ isolated nodes, add a random Hamiltonian cycle and then add edges randomly.

Let class B denote all the graphs of size $n$ which do not have a Hamiltonian cycle. How can we pick a random graph from this class? (or do something close to that)


texts: $\omega$-regular properties of a 2-state Markov Chain

texts:
Let $X$ be a Markov Chain on a state space $\{0,1\}$ with a transition matrix
$$
P =  \left(
\begin{align}
1-p & &p
\\
q & &1-q
\end{align}
\right)
$$
with both $p,q \in (0,1)$ so in particular it is irreducible. Define $p_\delta = p +\delta$, $q = q+\delta$ and let $P_\delta$ be the corresponding transition matrix defining a Markov Chain $X_\delta$. It is well-known that no matter how small $\delta$ is, for some tail event $A$ it holds that
$$
  \mathsf P(A) = 0,\quad \mathsf P_\delta(A) = 1 \tag{1}
$$
where $\mathsf P$ and $\mathsf P_\delta$ are corresponding probability measures over the paths. I wonder, however, whether $A$ can be always taken to be an $\omega$-regular event.

For a particular example, let $\pi$ and $\pi_\delta$ be invariant probability distributions for $X$ and $X_\delta$. Pick any vector $f$ such that $\pi f\neq \pi_\delta f$ and define
$$
  A_f :=\left\{\limsup_{n\to\infty}\frac1n\sum_{k=0}^n f(X_k) = \pi_\delta f\right\},
$$
then $(1)$ holds for $A_f$. Is $A_f$ $\omega$-regular?


texts: How quickly can we perform base extension in a residue number system?

texts:
Thinking about residue number systems, one major operation is to extend the set of primes that a given value is modulated by, also known as base extension.  For instance, a given number $N$ can be represented by a sequence of remainders or modulated values by another set of numbers, which are primes.  We then have:

$$N = (n_0, n_1, \dots, n_m)$$

where

$$n_0 \equiv N \bmod p_0$$
$$n_1 \equiv N \bmod p_1$$
$$\dots$$

$$n_m \equiv N \bmod p_m$$

Suppose we have a new sequence of additional primes, $(p_{m+1}, p_{m+2}, \dots p_{m+q})$.

How quickly can we get the new sequence of remainders (or modulated values), $(n_{m+1}, n_{m+2}, \dots n_{m+q})$ for the same number, $N$, in the worst case?


texts: Given a subset of of the hypercube and an affine transform of it, find the affine map

texts:
This is a follow up to this resolved question.
Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it
$$B=\{Mx + s\mid x\in A\}$$
for some full rank $M\in\mathbb{F}_2^{d\times d}$ and $s\in\mathbb{F}_2^d$.

Given $A$ and $B$ what are the randomized and quantum complexities of finding an $M$ and an $s$ so that $MA + s = B$ (let us assume SETH for the purposes of this post)?

Does this connect to any problems studied in tcs?