texts: Is there higher-dimensional generative grammar?

texts:
I'm interested in computer music, where there are approaches to treat pieces of music as sentences in generative grammars or L-systems. Instead of composing, one could then specify a grammar and let the computer generate the music. E.g. the Yale group around the late Paul Hudak are very strong in that.

It has struck me that we use seemingly one-dimensional representations of information to represent higher-dimensional things, like plant growth with L-systems. Music, to me, seems to have at least two dimensions: The obvious time dimension and the "instrument" dimension, i.e. the ability to have several different sounds at the same time. And indeed, music notation has exactly these two dimensions.

There are 2-dimensional programming languages like Befunge, which didn't strike me as very useful (yet), but I couldn't find anything about generative grammars, where the sentences are 2-dimensional.

By a 2-dimensional sentence I mean that the characters are spread on a 2-dimensional grid, e.g. like this:

ab cde
 aabce
dca  b

Production rules could have 2-dimensional sentences on either side of the rule as well:

a -> bc
     e

b -> cd
e    ab

Has something like this been studied before?

For example in computer music, this could be quite useful. Pieces like Ravel's Boléro could be generated by a 2-dimensional production rule like this:

t -> tt
      t

This should be read as "If in a piece, the theme t is played by instrument 1 at some time, then we can produce a new piece in which t is played by instrument 1 at the same time, and immediately after by instrument 1 and 2."


texts:
Suppose there is an oracle that returns a number $b \in \mathbb{Z}_{n}$ whenever I press the button.

We have $b = a + e$, where $a \in \mathbb{Z}_n$ is a fixed number and $e$ is sampled according to some distribution $\chi$ over $\mathbb{Z}_n$ (say, $\chi$ looks like normal distribution over $\{-(n-1)/2, ..., (n-1)/2\}$, so the mean is $0$).

Our goal is to learn (recover) the value of $a$, given as many samples from the oracle as you wish.

I know that if the random variables are over the real $\mathbb{R}$, we can take many samples and then compute the sample mean, and then we can upper-bound the probability of failure using Chebyshev's inequality.

However, this approach doesn't seem to work since we are working in $\mathbb{Z}_{n}$, I wonder whether anyone can suggest me an approach to remove $a$.

Thank you very much! :)


texts:
I'm a traveling salesman and I have n days to sell, I can start anywhere, I can sell once per city. I want to know where to start and what route to take.

It's likely NP-hard, I was just wondering if there's a name for this or similar variants on TSP.

EDIT

Here's a clarification of the problem:

Let $S$ be a clique with weighted edges that one could put onto a plane (Euclidian distances, etc.) and $k$ be a positive real number.
A solution $G$ is a subgraph of $S$ that is a simple path such that $\Sigma_{e \in E(G)} e < k$ and $|V(G)|$ is maximized.

Or, in terms of geometry:

Let $S$ be a set of points on the plane
A solution is a path through some of the points of length less than $k$ that maximizes the number of points hit.


texts: Recent insights on algorithms for 1D bin packing

texts:
This is just a general question on recent algorithms for the 1D bin packing problem. I just want to collect some information on this issue, so I’m grateful for any information. Especially heuristics solving the problem but also exact algorithms.

I know about the Bin Completion algorithm by Korf and the recent developments in Branch-and-Price algorithms. But is there anything else? As said before, I’m grateful for any information.


texts: I'm looking for an accepted, formal definition of a parser as function $f$ returning an AST, but I cannot find any reference in literature; all I can find is the definition of a recognizer as a function $f:\Sigma^*\to \{0,1\}$ with obviously $f(w)=1$ when $w\in L(G)$ and $0$ otherwise ($G$ being a grammar and $L(G)$ the generated language).


texts: What is the expected depth of a randomly generated tree?

texts:
I thought about this problem a long time ago, but have no ideas about it.

The generating algorithm is as follows. We assume there are $n$ discrete nodes numbered from $0$ to $n - 1$. Then for each $i$ in $\{1, \dotsc, n - 1\}$, we make the $i$th node's parent in the tree be a random node in $\{0, \dotsc, i - 1\}$. Iterate through each $i$ in order so that the result is a random tree with root node $0$. (Perhaps this is not random enough but this doesn't matter.)

What is the expected depth of this tree?


texts:
Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am looking in particular to find minimum distance of binary (codes over $\mathbb{F}_{2^l}$) quasi-cyclic  of rate q/q+1. Parity check matrix for such codes have a structure
$H=[I|C_1|C_2|...|C_m]$ where each $C_¡$ is a from class of circulant matrices. It may be useful that one can treat these codes as modules.
Or even if there are any approximate algoruihms for this ?


texts: Equivalent formula for LTL with and without past operators

texts:
I have recently been researching LTL with and without past operators.
From my understanding, both LTL and PLTL (LTL with Past) are equally expressive, however, PLTL is exponentially more succinct.

I have been searching for a list abbreviations between LTL and PLTL formulae but have found nothing, and I cant seem to figure them out myself.

If LTL allows the formulae

$\bigcirc\phi$ for  $\phi$ is true at the next moment in time,
$\Diamond\phi$ for  $\phi$ is true some time in the future,
$\Box\phi$ for  $\phi$ is true always in the future, and
$\phi\mathcal{U}\psi$ for  $\phi$ is true until $\psi$ is true,

and PLTL allows the additional formulae using the past versions of the temporal operators:

$\bigcirc^-\phi$ for  $\phi$ was true at the previous moment in time,
$\Diamond^-\phi$ for  $\phi$ was true some time in the past,
$\Box^-\phi$ for  $\phi$ was true always in the past,
$\phi\mathcal{S}\psi$ for  $\phi$ has been true since $\psi$ was true in the past,

then how are 1-4 expressed using only LTL?


texts:
In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric boolean (partial and total) functions in terms of a quantity denoted $\Gamma$:

  Theorem (Paturi): Let $f$ be any non-constant symmetric function, and denote $f_k=f(x)$ when $|x|=k$ (i.e. the hamming weight of $x$ is $k$). The approximate degree of $f$, denoted $\widetilde{deg}(f)$, is $\Theta(\sqrt{n(n-\Gamma(f))})$, where $\Gamma(f)=\min\{|2k-n+1|:f_k\neq f_{k+1}\text{ and } 0\leq k\leq n-1\}$

Now let $Thr_t(x)$ be the threshold function, i.e. $Thr_t(x)=1$ if $x\geq t$. In this paper (cf. section 8, page 15) says that $\widetilde{deg}(f)=\sqrt{(t+1)(N-t+1)}$.

Observe that for the threshold function we have $\Gamma(Thr_t)=|2(t-1)-n+1|$, because when $|x|=t-1$ the function changes from 0 to 1. Am I right?

If I apply directly Paturi's theorem to this value of $\Gamma$, I don't get the lower bound on the threshold function reported in other papers. Is the value of $\Gamma(Thr_t)$ above correct? What am I missing?

Edit: I also tried computing the quantum adversary lower bound for threshold. First, let's review the theorem.

  Theorem (Unweighted Quantum Adversary): Let $f$ be a partial boolean function, and let $A\subseteq f^{-1}(0)$ and $B\subseteq f^{-1}(1)$ be subset of (hard) inputs. Let $R\subseteq A\times B$ be a relation, and set $R_i=\{(x,y)\in R : x_i\neq y_i\}$ for each $1\leq i \leq n$. Let $m,m'$ denote the minimal number of 1s in any row and any column in relation $R$ respectively, and let $\ell,\ell'$ denote the maximal number of ones in any row and column in any of the relations $R_i$ respectively. Then $Q_2(f)=\Omega(\sqrt{\frac{m m'}{\ell \ell'}})$.

If I define $B$ as the set of all inputs with the number of 1s greater than or equal to $t$, and $A$ all the inputs with 1s strictly less than $t$, I get (after some algebra) that $\frac{mm'}{\ell\ell'}=n^2 \ln(\frac{n}{t}) \ln(\frac{n}{n-t})$.

So still I'm not getting the same lower bounds reported in other papers. Now, let's compare these bounds. The figure below shows for $n=200$ and without the square roots, a comparison between Paturi's theorem bound (blue), adversary bound (red), and the reported bound from other papers (green).

My questions are:

1- How do I get the bound reported in other papers?

2- You can see from the figure, that the reported lower bound (green) also lower bounds Paturi's bound and the adversary bound. Isn't that weakening the "real" lower bound? For example, if Paturi says that for all symmetric functions we have this bound, then how can you get a matching upper bound for quantum counting ($\sqrt{(t+1)(n-t+1)}$)? Isn't that upper bound violating Paturi's theorem?


texts:
Is there an inequality to relate the KL divergence of two joint distribution and the sum of the KL divergence of their marginals? Or in particular, is there a proof or a counter example for the following:

$D(q(x,y)\|p(x,y)) \geq D(q(x)\|p(x)) + D(q(y)\|p(y))$.


texts: Faculty hiring differences between US and UK/Germany

texts:
This question contains some great answers on how to get a job. I wonder whether there are some significant differences if I will be looking for a position in Europe (in particular, UK and Germany) as opposed to in the US. As a PhD student in the US (who's neither a US nor an EU citizen, if that matters), should I do something differently? Some aspects:

Is there more/less weight placed in UK/Germany on professional services such as journal/conference reviewing?
Is there more/less weight placed in UK/Germany on publishing in journals as opposed to conferences?
Should I try to get to know more professors in UK/Germany through conferences? What about doing an internship or a research visit in UK/Germany?

Other differences are also very welcome.


texts:
Let $t(G)$ denote the number of spanning trees in a graph $G$ with $n$ vertices.  There is an algorithm that computes $t(G)$ in $O(n^3)$ arithmetic operations. This algorithm is to compute $\frac{1}{n^2} \det(J + Q)$, where $Q$ is the Laplacian of of $G$ and $J$ is the matrix consisting solely of $1$'s. For more information on this algorithm see Biggs - Algebraic graph theory or this Math SE question.

I wonder if there is some way to compute $t(G)$ faster. (Yes, there is faster than $O(n^3)$ algorithms for computing determinant but I am interested in some new approach.)

It's also interested in considering special families of graphs (planar, maybe?).

For example, for circulant graphs, $t(G)$ can be computed in $O(n \lg n)$ arithmetic operations via the identity $t(G) = \frac{1}{n} \lambda_1 \dotsm \lambda_{n-1}$, where $\lambda_i$ are nonzero eigenvalues of Laplacian matrix of $G$, which can be computed quickly for circulant graphs. (Represent the first row as a polynomial and then compute it on $n$-th roots of unity - this step uses the Discrete Fourier transformation and can be done in $O(n \lg n)$ arithmetic operations.)

Thank you very much!


texts:
This question is somewhat related to this one. There are many results in statistics where convergence rates (including minimax ones) are given in terms of the smoothness properties of the underlying function class: Lipschitz, Hölder, etc. The problem with these is that they're quite pessimistic: a function with a high oscillation on a tiny region of the space is penalized the same as a function with high oscillation everywhere. Are there generalization bounds that take into account average-case smoothness? The one classic example is functions of bounded variation at most $V$ on $[0,1]$, whose $\gamma$-shattering dimension is $1+\lfloor\frac{V}{2\gamma}\rfloor$ (see the Anthony-Bartlett book). For differentiable $f:[0,1]\to\mathbb{R}$, the bounded variation is given by $\int_0^1|f'(x)|dx$, and thus corresponds to an average measure of smoothness.

Can anyone point me to other results along these lines for more general spaces?


texts: Hereditary substitution with a universe hierarchy

texts:
I've read about hereditary substitution for the Simple Lambda Calculus and for The Logical Framework with distinct terms and types.

I'm wondering, are there any examples of hereditary substitution in a dependently typed system with a universe hierarchy? i.e. where $ True : Set_0 : Set_1:Set_2$ etc.

I'm wondering in particular how to establish an induction measure in such a system. The simply typed version is structurally decreasing in the type of the variable being replaced. This doesn't work work with dependent types, to for LF the paper I linked uses the simply-typed erasure of the terms, performing induction on the shape of the type.

However, erasing to simple types doesn't work with a universe hierarchy, since if you have something like this:

$ f : (x : Set_1)\to x \to True$ implies that
$ f\ ((y : True) \to True \to True ): True \to True \to True$

i.e. applying a function resulted in a structurally larger type.

I'm assuming the solution has something to do with the universe indexes, but if there's an existing technique for establishing that the induction is well founded, I'd prefer to cite it rather than coming up with something up on my own.


texts:
Let $G(V,E)$ be a simple undirected graph, let $k\in \mathbb{N}$, and let $I(G)=\{(v,e)\ :\ e\in E, v\in e \}$ (here, $v\in e$ means $v$ is incident on $e$). A $k$-incidence colouring of $G$ is a function $c:I(G)\to \{1,2,\dots,k\}$ such that the following hold for all $u,v\in V$ and $e,f\in E$ :
(i) $c(\,(v,e)\,)\neq c(\,(v,f)\,)$,
(ii) $c(\,(u,e)\,)\neq c(\,(v,e)\,)$, and
(iii) if $e=\{u,v\}$, then $c(\,(u,e)\,)\neq c(\,(v,f)\,)$.
I am interested in the weak variant where we drop condition (iii). Let us call it weak incidence colouring. That is, a $k$-weak incidence colouring of $G$ is a function $c:I(G)\to \{1,2,\dots,k\}$ such that $c(\,(v,e)\,)\neq c(\,(v,f)\,)$,  and $c(\,(u,e)\,)\neq c(\,(v,e)\,)$ for all $u,v\in V$ and $e,f\in E$. This seems to be a very natural relaxation to me.
I couldn't find any paper that study weak incidence colouring.
Is this because this is equivalent to some known notion?
We know that incidence colouring has several equivalent characterizations, for instance, in terms of strong edge colouring (or directed star arboricity). See "Links with other notions" in The Incidence Coloring Page maintained by Éric Sopena.
If it matters, I am particularly interested in the complexity of $k$-weak incidence colouring of $k$-regular graphs. Thank you, in advance.


texts: Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known

texts: Given a $k>0$ and a graph $G(V,E)$ with known independence number $\sqrt{|V|}\leq\alpha(G)\leq\alpha\sqrt{|V|}$ and chromatic number $\frac1\beta\sqrt{|V|}\leq\chi(G)\leq\sqrt{|V|}$ for some fixed $\alpha,\beta\geq2$ and given an optimum vertex coloring is it $\mathsf{NP}$-complete to decide if clique number $\omega(G)>k$?


texts:
I'm looking for an algorithm that will take a sorted array of numbers and generate a random permutation of this array in such a way that the probability of finding a larger element earlier in a sequence than a smaller element is proportional to the ratio of these elements' values.

For instance if we have a sorted sequence of elements: 1, 2, 3, then I'd like this algorithm to generate a permutation of this sequence in such a way that the probability of finding element 3 earlier in a sequence than the element 1 is 3 times smaller than the other way around. This property should hold for all pairs of the elements.

Is this possible?  If so, can you suggest an algorithm for this?


texts:
It is known that given an $n$-point subset of $\ell_2^d$ (that is, given $n$ points in ${\mathbb R}^d$ with Euclidean distance) it is possible to embed them isometrically in $\ell^{n\choose 2}_1$.

Is the isometry computable in (possibly, randomized) polynomial time?

Since there are finite-precision issues, the precise question is

Given a set $X$ of $n$ points in ${\mathbb R}^d$ and $\epsilon >0$, is there a mapping $f: X \to {\mathbb R}^{n\choose 2}$ computable (possibly, using randomness) in time polynomial in $n$ and logarithmic in $1/\epsilon$ such that for every $x,y\in X$ we have
$|| f(x)-f(y)||_1 \leq ||x-y||_2 \leq (1+ \epsilon) \cdot || f(x)-f(y) ||_1$

(Note: I am aware that a mapping with distortion $(1+\epsilon)$ can be found with high probability in time polynomial in $n$ and $1/\epsilon$ by projecting on $O(\epsilon^{-2} \cdot \log n)$ random lines, but I am not sure if the number of dimensions can be constructively reduced to $n\choose 2$ or even $O(n^2)$ when $1/\epsilon$ is much larger than $n$, and I don't know if there is a polynomial time method to handle the case in which $1/\epsilon$ is exponential in $n$.)


texts: Hardness of LWE on not-uniform vector samples

texts:
The "usual decisional LWE":
The challenger and the adversary get a common random matrix $A \in F_{q}^{m \times n}$. The challenger chooses a secret $s \in F_{q}^{n}$ and generates random (small) secret noise vector $\chi \in F_{q}^{m}$, and the claim is that the adversary can't distinguish efficiently between $(A, As + \chi)$ and $(A, U_{m})$ (where $U$ is the uniform distribution over $F_{q}$).

My question:
Assume that the challenger and adversary do not get $A$ at random, but rather create $A$ via some deterministic reduction from some common input $x$. All the rest is the same, i.e., the challenger chooses the secret  $s \in F_{q}^{n}$ and generates random (small) noise vector $\chi \in F_{q}^{m}$ and then sends to the adversary either $As + \chi$, or a true random vector. What conditions does $A$ have to fulfill to ensure that the challenger can't distinguish between  $(A, As + \chi)$ and   $(A, U_{m})$?

I'm currently more interested in the case of $q=2$, i.e., the LPN problem, but even a conclusion on the non-binary scenario may be useful.

I realize this question might be tricky and without an answer, so my hope is to at least get references to articles that either tried to tackle this issue directly or at the very least articles that will be a good entry point for me in the case I'll have to try and solve it myself.


texts:
Consider a collection of sets $F=\{F_1,F_2,\dotsc,F_n\}$ over a base set $U=\{e_1,e_2,\dotsc,e_n\}$ where $|F_i|$ $\ll$ $n$ and $e_i \in F_i$, and let $k$ be a positive integer.

The goal is to find another collection of sets $C=\{C_1,C_2,\dotsc,C_m\}$ over $U$ such that each $F_i$ can be written as a union of at most $k$ $(k<<|C|)$ mutually disjoint sets in $C$ and also we want $\sum_1^m |C_j|$ to be minimal (i.e., the aggregate number of elements in all sets of $C$ should be as small as possible) .

Note that $F$ has the same size with $U$, but the size of $C$ is uncertain.

Can anyone tell whether the above problem is NP-hard? (set covering？packing？perfect covering）

Thanks for your time.


texts:
In the course of trying to give a more natural answer to a previous question of mine involving the complexity classes $$SUBLOG=\{L\mid L \text{ is recognizable by a sublogarithmic-space TM} \}$$ and $DTIME(n)$ I need a language in $SUBLOG$ that is not in $DTIME(n)$ (I already know the other direction).
However, I'm not very familiar with sublogarithmic space and Liskiewicz and Reischuk's paper overviewing the topic deals more with alternating machines than it does with deterministic ones, which I was more interested in. Is it known whether there is a sublogarithmic language requiring super-linear time?


texts: Complexity of counting codeword length distribution

texts:
Suppose I have a code $C$ over $GF(2)$. I would like to count exactly the number of codewords of $C$ of weight $k$. Here $k$ should be thought of as small compared to the dimensions of the code.

What is the best algorithm for this? Even exponential algorithms could be useful.


texts: Reasons to believe $P \ne NP \cap coNP$ (or not)

texts:
It seems that many people believe that $P \ne NP \cap coNP$, in part because they believe that factoring is not polytime solvable. (Shiva Kintali has listed a few other candidate problems here).

On the other hand, Grötschel, Lovász, and Schrijver have written that "many people believe that $P=NP\cap coNP$." This quote can be found in Geometric Algorithms and Combinatorial Optimization, and Schrijver makes similar statements in Combinatorial Optimization: Polyhedra and Efficiency. This picture makes it clear where Jack Edmonds stands on the issue.

What evidence supports a belief in $P\ne NP\cap coNP$? Or to support $P=NP\cap coNP$?


texts: what is a model of computation, mathematically?

texts: Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't treat it as a maths object, it states it in English. Contrast this to clear maths definition for formal language: subset of finite set of symbols together with Kleene star


texts: Random functions of low degree as a real polynomial

texts:
Is there a (reasonable) way to sample a uniformly random boolean function $f:\{0,1\}^n \to \{0,1\}$ whose degree as a real polynomial is at most $d$?

EDIT: Nisan and Szegedy have shown that a function of degree $d$ depends on at most $d2^d$ coordinates, so we may assume that $n \leq d2^d$. The problems as i see are the following:
1) On one hand if we pick a random boolean function on $d2^d$ coordinates, then its degree will be close to $d2^d$, much higher than $d$.
2) On the other hand, if we pick each coefficient of degree at most $d$ at random, then the function will not be boolean.

So the question is: is there a way to sample a low degree boolean function that avoids these two problems?


texts: What's the approximation factor of this Max k-Cut approximation?

texts:
I'm thinking about an approximation algorithm for Max k-Cut. One simple and more involved approximation algorithms can be found here. The Max k-Cut problem is defined as follows.

Input is a graph G = (V, E) and an integer k, n = |V|, the question asks for partitioning G
into k disjoint sets such that the total number of edges between disjoint parts is maximized.

My algorithm is a greedy strategy and works as follow (maybe someone else already had a similar idea but I'm not aware of):

Start with each vertex in a group by
itself, and at each step, combine the
two groups that have a minimum number
of edges between them. Repeat this until the number of groups shrinks to $k$.

Is there a known approximation guarantee for this algorithm?


texts: Curry Howard Isomorphism and cut elimination

texts:
I am currently reading about the proof for the isomorphism between Gentzen's sequent calculus $G$ and the simply typed lambda calculus $\lambda(\rightarrow,\times)$. The proof assumes the cut-free representation of proofs in $G$. I fail to see the necessity for this assumption (besides that it may shorten the proof).
What am I missing?
Best,
David


texts: Is there any research on approximation of reals with computable numbers

texts:
I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential height functions.

The basic premise of Diophantine approximation is that you take a dense countable set(traditionally the rationals or the algebraic numbers), $A$ in some range(generally $(0,1)$) and a function $H: A \to \mathbb N$, the height function. You then see how given $N \in \mathbb N$ close you can get a member of $A$, usually referred to as $\alpha$ with $H(\alpha) < N$. The most famous result from this field is Dirichlet's Approximation Theorem which states that for any real in $(0,1)$ there exist infinitely many rationals $\frac{p}{q}$ such that $|x-\frac{p}{q}| \le \frac{1}{q^2}$. This has been shown to be optimal up to a constant.

Some height functions I imagined for the computable numbers would be

1) $H_c(\alpha)$ This is a restricted version of the above when the Turing machine is restricted to having $c$-characters not counting blank.

2) Same as 1 just counting transitions instead of states.

3) Some function on the time complexity to generate the number

4) Some function on the space complexity to generate the number

The first 2 are basically variants on Kolmogorov complexity I believe. The last two I'm not even sure how to map to the Naturals.

Here are some preliminary results I believe are true.

For 1 Using just rationals and an $x \in (0,1)$ you get an approximation of the following form
$$|x-\alpha| \le Cc^{-H_c(\alpha)}$$
For some $C>0$. I believe I can prove this. If it is true that using algebraic numbers of degree at most $d$ gives an approximation function of $|x-\alpha| \le cH^{-d-1}(\alpha)$ for some $c>0$ then I believe the same approximation function holds even if you use all algebraic numbers. The basic reasoning behind this is that it takes $O((d+1)\log_c(\max(a_1,\dots,a_{d+1})))$ states to output all the coefficients to the tape and then you should be able to do Newton's algorithm with a constant number of states. In the last equation $a_1,\dots,a_{d+1}$ is the set of coefficients of the minimal polynomial specifying $\alpha$.

Noting that the number of transitions is approximately equal to $c+1$ times the number of states you get an equivalent statement for 2 that for $x \in (0,1)$ you get
$$|x-\alpha| \le Cc^\frac{-H_c(\alpha)}{c+1}$$

For some constant $C > 0$. Due to these results I'd say 2 is probably the nicest approximation function since $c^\frac{n}{c+1}$ when restricted to integer inputs is bounded by $\sqrt[5]{4}^n$ or roughly $1.3195^n$.

A result I'd like to have and I believe is true is that the bounds on the approximation function for $3$ are optimal, that is that there exists $x \in (0,1)$ such that
$$|x-\alpha| \ge Cc^\frac{-H_c(\alpha)}{c+1}$$
For some constant $C>0$ and all but finitely many computable $\alpha$.

This is a cross-post from math.stackexchange. It was suggested to me that this site would be more likely to answer my question if there is any research or if this is worth pursuing any farther.


texts: Using Indicator Functions as Transfer Functions for Neural Networks

texts:
Does there exist any theory (other than Cybenko's proof of the Universal Approximation Theorem with sigmoids) advocating the use of indicator functions as transfer functions for machine learning with neural networks?

After having read matus's beautiful answer in this thread explaining (among other things) Cybenko's proof, I wonder: if it weakens the approximation to use sigmoid transfer functions instead of indicator functions, what are the theoretical reasons for not using indicator functions?

As suggested here, perhaps it's because indicator functions have negative implications for generalization.

However, indicator functions are computationally far cheaper to implement than sigmoid functions, and also more closely resemble biological neural networks (ie the brain). Therefore, does there exist any other theory advocating the use of indicator functions as transfer functions for machine learning with neural networks?


texts: Does anyone know (or can anyone think of) a simple reduction from (for example) PARTITION, 0-1-KNAPSACK, BIN-PACKING or SUBSET-SUM (or even 3SAT) to the UBK problem (integral knapsack with unlimited number of objects of each type)? I'm writing an introduction to a few of these problems, and noticed that I hadn't really heard of a standard reduction here. Shouldn't be that hard (it's a relatively expressive problem), but I can't think of anything right now… Thoughts/references?


texts: Algorithms for graph generation given parameters

texts:
I guess there may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g. clustering coefficient, average path length, degree distribution, etc). I am new to this field, and some google search didn't find me a thorough review of the literature.

My question concerns a specific case: I want to generate a few undirected regular graphs (i.e. each node of each graph has the same number of edges) with different clustering coefficients and average path lengths. More generally, while fixing a degree distribution, generate graphs by varying clustering coefficient and average path length.

I wonder what are the well-known algorithms for doing this (or links to relevant literature reviews would be great too!), and what are the recommended software for generating such graphs?


texts:
My question refers to the expansion of constant size sets of an expander graph.
Suppose we are given an expander graph with Cheeger constant $\alpha$.
What can be said about the edge expansion of sets of size, say 100?

Is it true, that the relative expansion of a set, w.r.t. the set size always has a
decaying profile - so that constant size sets expand much more rapidly than the overall graph expansion?

While there is nothing to stop constant-size sets from having just poor overall expansion value (equal to the minimal expansion over all sets) by definition, is it possible to show such a property?


texts: Remove unneeded atoms in CNF minimalization (SAT preprocessing)

texts:
This might be a very basic question.

I am interested in all atoms of a propositional formula that can be removed from a particular formula, while the derived formula has the same satisfiability characteristics.

Consider:

$(\lnot a\lor b) \land (a \lor b)$

Here the atom a can be removed, as the formula can be reduced to simply b.

Is there a name for atoms that can be removed from a formula? I.e., atoms like a that can be removed from a formula? (Informally I would call them "don't care" atoms.)

There are certain tools like lingeling and minisat2 that can simplify or preprocess a SAT problem, given a CNF formula (see another answer).
Do this approaches reliably remove all atoms (like aabove) from the formula that can be removed? My rough guess would be that finding a minified formula is as complex as finding all the prime implicants of a formula? (Minification in my sense would be a formula with the least number of atoms.)


texts: What is the complexity of estimating the number of paths between two vertices of a large graph?

texts:
Consider an $N\times N$ adjacency matrix $A$ of some large, $b$-sparse undirected graph $G$.  The $(i,j)$ entry of $A^m$ counts the number of $m$-length paths between vertex $i$ and vertex $j$.
We let $A$ be strongly explicit.  For example, the number of vertices $N$ is large, e.g. exponential in $m$, $b$.  We have an efficient algorithm to $A_{ij}$ - e.g. given vertices $i,j$ we can efficiently determine whether they are adjacent, and for all vertices $i$ we can efficiently generate all other $b$ vertices adjacent to $i$.  For example we can generalize Cayley graphs of the 15-puzzle ($b=4$ and $N=6.5e10$), or the Rubik's cube ($b=18$ and $N=4.3e19$).  Each $m$-length word corresponds to an $m$-length walk on the Cayley graph.
In a series of papers, Janzing and Wocjan investigated quantum algorithms to estimate various powers of $A$.  For example, they rescaled $A$ and simulated $U=e^{-iAt}$, and executed a quantum phase estimation on $U\vert \psi\rangle$ to perform an $A$-measurement on qubits prepared in various simple states $\vert\psi\rangle$. The phase estimation algorithm gives enough eigenvalues $\lambda$ of the spectral decomposition of $A$ with probabilities given by the decomposition of $\vert\psi\rangle$ into $A$-eigenstates, to estimate $\langle\psi\vert A^m\vert\psi\rangle$. Given three vertices $i,j,k$, they were then able to control errors in the Hamiltonian simulation and in the phase estimation, and showed:

Estimating the number of $m$-length walks that start at $i$ and end back at $i$ is in (promise) $\mathsf{BQP}$;
Estimating the number of $m$-length walks that start at $i$ and end at $j$ is in $\mathsf{BQP}$;
Estimating a difference in the number of $m$-length walks that start at $i$ and end at $i$, versus those that start at $i$ and end at $j$, is $\mathsf{BQP\:Complete}$; and
Estimating a difference in the number of paths from $i$ to $j$, versus a number of paths from $i$ to $k$, is likewise $\mathsf{BQP\:Complete}$.

Their proofs that the last two problems are $\mathsf{BQP\:hard}$ are quite clever (although I don't understand them fully).  But they emphasize that quantum computers show their power for interference when asking for a difference in the number of paths.  This I believe is similar to the context of Regan's comment on GLL.
But as to my question:

Can the first two problems be bounded any lower than $\mathsf{BQP}$?  For example, are they amenable to Stockmeyer approximation?  Or even better, is there any other $\mathsf{NP}$ certificate that can be used to estimate $\langle i\vert A^m\vert j\rangle$ for various $i,j$?

If $m$ is much greater than the mixing time, then each of the four questions might be straightforward to bound.  The last two should approach $0$ as $m$ increases, I think.


texts:
Primality was a nice problem that was in ZPP but was not known to be in P. Is there a (preferably simple to state) problem of which we can prove that it is in ZPP but we do not know whether it is in P or not?

I know ZPP=EXP might hold and so on, I want a problem surely in ZPP that is not surely in P.


texts: Is there a name for approximation algorithms with $f(OPT)$ approximation factor?

texts:
I have read that there are approximation algorithms with two different kinds of approximation factors:

$c$ . A constant approximation factor.
$f(n)$ . An approximation factor that is function of the input size.

However, right know I'm dealing with an approximation factor of the following nature:

$f(OPT)$ . Namely, an approximation factor that is a function of the optimal solution size.

Is there an special name for this kind of approximation algorithms?


texts:
Given $n$ vectors $v_1,\dots,v_n\in\Bbb R^N$ with $\|v_i\|_2^2\leq1$ at every $i\in\{1,\dots,n\}$, Komlos conjecture states that, there is a $c\in\Bbb R$ (independent of $n,N$) such that at some $\epsilon\in\{-1,+1\}^n$, $$\Big\|\sum_{i=1}^n\epsilon_iv_i\Big\|_\infty<c.$$ What is best lower bound known for $c$?

Best upper bound is $c=O(\sqrt{\log n})$.

Is there a set of examples for $c=1+\delta$ for any $\delta>0$ where Komlos conjecture fails?


texts:
How can we express "$P=PSPACE$" as a first-order formula?
Which level of the arithmetic hierarchy contains this formula (and what is the currently known minimum level of the hierarchy that contains it)?

For reference, see this blog post by Lipton.


texts: Educational Source or Survey on Analysis of Semidefinite Program?

texts:
When designing approximation algorithms one sometimes solves a semidefinite program followed by a rounding step. An often used example to illustrate this is Max-Cut. (See e.g. Approximation Algorithms by Vijay Vazirani.)

Are there good educational sources or surveys going beyond the Max-Cut problem to explain more complex rounding algorithms and techniques used for their analysis? I'm thinking of cases when the vectors of the SDP-solution aren't distributed uniformly on a hypersphere, they have different lengths, or have other properties making the analysis harder.


texts: Reference for context-free grammar for Martin-Löf type theory

texts: Are the terms and the types of Martin-Löf type theory described by context-free grammars? Have such grammars been written down somewhere?


texts: Examples of non-CSLs not created through diagonalization

texts:
Hopcroft & Ullman 1979, Intro to Automata Theory, Languages, & Computation states (p. 224) that "almost any language one can think of is CSL; the only known proofs that certain languages are not CSLs are ultimately based on diagonalization." They give for example the universal Turing machine. I presume this statement is still true today more than three decades later but wonder anyway.

Are there any non-CSLs known that are not "ultimately based on diagonalization"?

I agree that this question is not necessarily strictly defined. I would also be willing to accept examples in the form where an algorithm was initially/originally built or constructed for some purpose and had unknown complexity and later the algorithm was proved to be non-CSL.

Note non CSLs are also the Exp-space hard problems. Wikipedia mentions without reference "An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation."  I would like to know a reference for this if anyone has it.


texts: In APSP, the input is an $n$-node directed weighted graph $G$, and the output is an $n \times n$ matrix holding pairwise shortest path distances between nodes in $G$.  Define "APSP-Verification" as the problem where we get a graph $G$ and a matrix $D$, and the goal is to decide whether or not $D$ is the correct output of APSP on $G$.  Is there an algorithm that solves this problem in $O(n^{3-c})$ time, for any absolute constant $c>0$?  Alternately, taking the standard conjecture in fine-grained complexity that no algorithm solves APSP in $O(n^{3-c})$ time, can we prove that there is no such algorithm for APSP-Verification?


texts:
For all constants $\epsilon,\delta>0$, let $k=\epsilon^{-2}\log1/\delta$. We know there exists a linear transformation $M : \mathbb R^{k^2}\to \mathbb R^{\tilde O(k)}$, such that for all $x\in\mathbb R^{k^2}$ we have $|\|Mx\|_2-\|x\|_2|\le \epsilon\|x\|_2$ with probability $1-\delta$.

The question is whether there is such a transformation which can be computed in time $\tilde O(k)$ for vectors the form $y_1\otimes y_2=[y_1^2,y_1 y_2,\dots,y_k^2]\in\mathbb R^{k^2}$, $y_1,y_2\in\mathbb R^k$.

(We define $\tilde O(x) = x(\log x)^{O(1)}$.)

That is, the embedding should work for any vector in $\mathbb R^{k^2}$, but we care about the embedding time of vectors that are known to be simple tensor products.
This is known as a Tensor Sketch and has been studied extensively.
However, as far as I know, it is still open how fast this can be accomplished, even in the simple case sketched above.

What is known:

(1) Using the Fast JL method on the product, we can compute it in $\tilde O(k^2)\approx \epsilon^{-4}(\log1/\delta)^2$ time.
(Note that we allow the target dimension to be $\tilde O(k)$, slightly bigger than the optimal $k$, which is necessary for the best known Fast JL methods.)

(2) Using Sparse JL on the product, we can sketch the vector in time $\epsilon k^3 = \epsilon^{-5}(\log1/\delta)^3$.

(3) The analysis in here or here lets us first map the individual vectors with Fast JL into $\epsilon^{-2}(\log1/\delta)^3$ dimensions and then take the Hadamard product.

(4) Alternatively, the initial mapping can be done using Sparse JL, in which case we map into $m=\epsilon^{-2}\log1/\delta+\epsilon^{-1}(\log1/\delta)^2$ dimensions (again using the analysis of Ahle et al.) using time $\sim\epsilon m k=\epsilon^{-3}(\log1/\delta)^2+\epsilon^{-2}(\log1/\delta)^3$. However this is strictly worse than the above method.

In both case (3) and (4), we can make a terminal dimension reduction to the target dimension of $\tilde O(k)$ using Fast JL.

Hence the best we know how to do is time $\approx \epsilon^{-2}(\log1/\delta)^3$ or $\epsilon^{-4}(\log1/\delta)^2$.

I wonder if anyone has an idea for how we can get rid of one or both of the factors $(\log1/\delta)$?
(Or in the case of method (1), of one or both of the factors $\epsilon^{-1}$?)

Even $\epsilon^{-10}(\log1/\delta)$ would be quite interesting.

Alternatively we might hope to show that they are necessary?
Though, since this would be a time lower bound, rather than an embedding dimension lower bound, it is not clear which model one should choose.

Notes:

In the case of vectors $y_1,y_2\in\{-1,1\}^k$, simply sampling $\epsilon^{-2}\log1/\delta$ entries from the tensor product $y_1\otimes y_2$ suffices.
The loss of $(\log1/\delta)^3)$ in method (3) seems to have at least one $(\log1/\delta)$ more than we would expect from RIP methods.
However, the strongest RIP based analysis I know is Jin et al., which gets the same $\epsilon^{-2}(\log1/\delta)^3$ dependency.
The Tensor Sketches mentioned are all "oblivious" in that they apply the same linear transformation to any $x\in\mathbb R^{k^2}$, even if it computes it more efficiently for tensor products. There are Tensor Sketch methods which are non-oblivious (such as Wang et al.), but their embedding guarantees are no better.


texts:
We are considering a connected weighted graph G. 1-tree is a tree with one extra edge added (so it contains exactly one cycle). The task is to find minimum spanning 1-tree of G.
I was thinking of first using any of well-known MST algorithms and then adding an edge of smallest weight to the MST (which is not in the MST). Will something like this work (I am having trouble proving it would)?


texts:
A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which are decided by deterministic or nondeterministic log-space Turing machines, respectively. The two-way Turing machines may move their head on the input tape into two-way (left and right directions) while the one-way Turing machines are not allowed to move the input head on the input tape to the left.

Hartmanis and Mahaney have investigated the classes $1L$ and $1NL$ of languages recognizable by deterministic one-way log-space Turing machine and nondeterministic one-way log-space Turing machine, respectively. They have shown that $1NL \subseteq L$ if and only if $L=NL$.

See the paper here(it is free to download):

https://ecommons.cornell.edu/handle/1813/6253

I wonder this question:

Is $L \subset 1NL$ when $L \neq NL$?

Moreover, I wonder this another question:

Is there any reference that shows whether at least one of the options $L \subset 1NL$ or $1NL \subset L$ or $L = 1NL$ should be true?

Thanks in advance!!!


texts: Choosing random permutations in "strict" polynomial time

texts:
This question compares "strict" polynomial time, as opposed to "expected" polynomial time.

Let $S = \{1,2,…,n\}$, and let $O$ be an ordering on elements of $S$ (the number of orderings is $n!$).

A probabilistic algorithm can easily select a random ordering in "strict" polynomial time (in $1^n$), as follows:

Let O = {}, T = S
For i = 1 To n
    Let e be a random element from T
    Let T = T - {e}
    Let O = O ∪ {(i,e)}

The algorithm assumes that sampling a random element from $T$ can be performed in strict polynomial time. (More precisely, we assume that in strict polynomial time, we can uniformly sample from any set whose size is polynomial in $n$.)

Now let's consider the following problem:

  Choose $m$ distinct random permutations over $S$, where $m$ = poly($n$) < $n!$.

One naive way of doing this is to repeat the above algorithm, keep a record of permutations selected thus far. If the algorithm returns a "redundant" permutation, throw it away, and start over.

The above approach works in "expected" polynomial time, rather than "strict" polynomial time.

  Is there a strict polynomial time which does the job?

Edit: Here's a reference for those who want to know more on "strict vs. expected" issue:
On Expected Probabilistic Polynomial-Time Adversaries: A Suggestion for Restricted Definitions and Their Benefits.


texts: Guessing a low entropy value in multiple attempts

texts:
Suppose Alice has a distribution $\mu$ over a finite (but possibly very large) domain, such that the (Shannon) entropy of $\mu$ is upper bounded by an arbitrarily small constant $\varepsilon$. Alice draws a value $x$ from $\mu$, and then asks Bob (who knows $\mu$) to guess $x$.

What is the success probability for Bob? If he is only allowed one guess, then one can lower bound this probability as follows: the entropy upper bounds the min-entropy, so there is an element that has probability of at least $2^{-\varepsilon}$. If Bob chooses this element as his guess, his success probability will be $2^{-\varepsilon}$.

Now, suppose that Bob is allowed to make multiple guesses, say $t$ guesses, and Bob wins if one of his guesses is correct. Is there a guessing scheme that improves Bob's success probability? In particular, is it possible to show that Bob's failure probability decreases exponentially with $t$?


texts: Finding a ranking which minimizes the number of conflicts

texts:
Suppose that $k$ different voters have each produced a partial ordering of candidates $1,\ldots,n$. For example, if $k=3$ and $n=4$, the voters may have produced the partial orders

$1<2$
$2<1<3<4$
$2<3<1$

Our goal is to fuse all these into a single ranking of the candidates in a way that minimizes conflicts. The following seems like a natural way to do this. Given a total order $L$, let $C(i,j)$ be the number of the partial orders which rank $i$ and $j$ in the opposite way from $L$ (i.e., if $L$ ranks $i$ before $j$, $C(i,j)$ equals the number among the $k$ partial orders that rank $j$ before $i$).  We seek to find a total order $L$ which minimizes $\sum_{i<j} C(i,j)$.

This seems like it would be a well-studied problem, but I have been unable to find any references, likely because I'm not aware of the right keywords. Can any one point me towards papers where algorithms for this problem were considered?


texts: Circuity complexity: monotone circuit of Majority function

texts:
As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 log(n)+ O(1).

  http://link.springer.com/chapter/10.1007/11830924_38

My question is, what is the time-complexity of such constrution? (i.e., the time needed to construct the circuit, given n in unary)


texts: Has there been any research on $k$-SAT above the satisfiability threshold?

texts:
A well known characteristic of $k$-SAT instances is the ratio of the number of clauses $m$ over the number of variables $n$, i.e., the quotient $\rho = m/n$.  For every $k$, there is a threshold value $\alpha$ s.t.\ for $\rho \ll \alpha$, most instances are satisfiable, and for $\rho \gg \alpha$ most instances are unsatisfiable. There has been a lot of research done for problems where $\rho \ll \alpha$, and for problems with sufficiently small $\rho$, $k$-SAT becomes solvable in polynomial time.  See, for instance, Dimitris Achlioptas's survey article from the Handbook of Satisfiability (PDF).

I am wondering if any work has been done in the other direction (where $\rho \gg \alpha$), e.g., if we can somehow transform the problem from CNF to DNF in this case to solve it quickly.

So, essentially, What is known regarding SAT where $\rho = m/n \gg \alpha$?


texts: Algorithms on graphs represented using BDDs

texts:
The simplest representations for graphs use adjacency matrices/lists, meaning that each node and edge is explicitly represented. The importance of implicit representations for graphs exhibiting strong regularities has long been recognized. For instance, Galperin & Wigderson (1983), Papadimitriou & Yannakakis (A Note on Succinct Representations of Graphs, 1986) explored the question of graphs whose adjacency matrix is represented by a Boolean formula answering whether or not (i,j) is an edge given the binary representation of the node numbers i and j. Under some commonly satisfied constraints on reductions, P-complete problems for explicit graphs become PSPACE-complete for this representation, NP-complete problems become NEXPTIME-complete, etc.

A natural approach to such regular graphs is to represent the Boolean formula using a ROBDD; the difficulty is that classical algorithms tend to enumerate nodes one by one, which incurs exponential cost on such a representation and thus is to be avoided. There have been papers published on classical problems being solved using such a representation, e.g. Gentilini et al. (Computing strongly connected components in a linear number of symbolic steps), Woelfel (Symbolic topological sorting with OBDDs).

I'm wondering whether there is some survey of such techniques, because it's inconvenient to dredge the literature in such of the state of the art...


texts: Why is HAMILTONIAN CYCLE so different from PERMANENT?

texts:
A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a
polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment
$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$  such that $f(x_1,\ldots,x_n)=g(\pi(y_1),\ldots,\pi(y_m))$. That is, it is possible to
replace each variable $y_j$ of $g$ by a variable $x_i$ or a constant $0$ or $1$ so that
the resulting polynomial coincides with $f$.

I am interested in (the reasons for) the difference between the permanent polynomial PER and the Hamiltonian cycle polynomial HAM:
$$
\mbox{PER}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}\ \ \ \  \mbox{and} \ \ \ \
\mbox{HAM}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}
$$
where the first summation is over  all permutations $h:[n]\to[n]$,
and the second is only over all cyclic permutations $h:[n]\to[n]$.

Question: Why HAM is not a monotone projection PER? Or it still is?

I am not asking for proofs, just for intuitive reasons.

Motivation: the largest known monotone circuit lower bound for PER (proved by Razborov) remains "only" $n^{\Omega(\log n)}$. On the other hand, results of
Valiant imply that
$$
\mbox{CLIQUE$_n$ is a monotone projection of HAM$_{m}$}
$$
where
$$
\mbox{CLIQUE}_n(x)=\sum_{S}\prod_{i < j\in S}x_{i,j}
$$
with the summation is over all subsets $S\subseteq [n]$ of size $|S|=\sqrt{n}$. I myself couldn't get a "simple, direct" reduction form these general results, but Alon and Boppana claim (in Sect. 5) that already $m=25n^2$ is sufficient for this reduction.

But wait: it is well known that CLIQUE requires monotone circuits of size $2^{n^{\Omega(1)}}$ (first proved by Alon and Boppana using Razborov's method).

So, were HAM a monotone projection of PER, we would have $2^{n^{\Omega(1)}}$ lower bound also for PER.

Actually, why HAM is not even a non-monotone projection  of PER? Over the boolean semiring, the former is NP-complete, while the latter is in P. But why? Where is a place where being cyclic for a permutation makes it so special?

P.S. One obvious difference could be: HAM covers [n] by just one (long) cycle, whereas PER can use may disjoint cycles for this. Thus, to project PER to HAM the hard direction seems to be: ensure that the absence of a Hamiltonian cycle implies the absence of any covering with disjoint cycles in the new graph. Is this the reason for HAM not being a projection of PER?

P.P.S. Actually, Valiant proved a more impressing result: every polynomial $f(x)=\sum_{u\subseteq [n]}c_u\prod_{i\in u}x_i$ with $c_u\in\{0,1\}$, whose coefficients $c_u$ are p-time computable, is a projection (not necessarily monotone if the algo is non-monotone) of HAM$_m$ for $m$ = poly$(n)$. PER also has this property, but only over fields of characteristic $\neq 2$. So, in this sense, HAM and PER are indeed "similar", unless we are not in GF(2) where, as Bruno remembered, PER turns to DETERMINANT, and is easy.


texts: Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains

texts:
Let ${\cal L}=\{Y_1,..., Y_k, X\}$ be a finite relational language such that $X$ is a unary relation name. Let $\phi(X,\bar{Y})\in{\cal L}$ be a first-order formula (the formula can have the equality relation). For a natural number $n$, we have $$([n],X')\models \exists \bar{Y}\phi(X,\bar{Y})$$ when $X$ is interpreted by $X'\subseteq [n]$ iff there exists an expansion $([n],X',\bar{Y'})$ of $([n],X')$ such that $$([n],X',\bar{Y'})\models \phi(X,\bar{Y}).$$
A language $L\subseteq \{0,1\}^*$ is $\Sigma^1_1$-definable using the relation names in $\cal L$ over finite domains iff there exists a formula $\phi(X,\bar{Y})\in{\cal L}$ such that for every $x\in \{0,1\}^*$,

$x\in L$

if and only if

$([|x|],S_x)\models \exists \bar{Y}\phi(X,\bar{Y})$ where $S_x=\{i\in [|x|]:x_i=1\}$.

So for example the majority language ${\bf Maj}=\{x\in\{0,1\}^*: x\text{ has at least }\lfloor\frac{|x|}{2}\rfloor \text{ ones.}\}$ is $\Sigma^1_1$-definable. Let ${\cal L}=\{X(.),Y(.,.)\}$ be our language, then $\phi_{Maj}(X,Y)$ is the conjunction of the following formulas:

$\forall i \exists j(\neg X(i)\to X(j)\land Y(i,j))$.
$\forall i,j,k(i\neq j\to \neg(Y(i,k)\land Y(j,k)))$.

Other interesting symmetric languages can be defined in this way. Moreover, it is possible to allow $X$ to have more arity to define more complicated languages.
My question is the following:

Does the class of languages that are $\Sigma^1_1$-definable in this terminology have a Computational complexity name?

The important property here is that we do not use interpreted relations such as linear order in $\phi(X,\bar{Y})$ (except the equality).


texts: Reduction of graph chromatic number to hypergraph 2-colorability

texts:
I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this paper, the author tries to reduce graph chromatic number to hypergraph 2-colorability (same as set splitting).

You can find the paper here: http://web.cs.elte.hu/~lovasz/old-papers.html

I'm reproducing the reduction below.

Let $G$ be a graph, $V(G) = \{x_1,\dots,x_n\}$. Let $G_i$ be an isomorphic copy of $G$, $(i=1,\dots,k)$, $V(G_i) = \{x_{i,1},\dots,x_{i,n}\}$ ($x_{iv}$ is a point corresponding to $x_v$). Take a new point $y$ and let $f_v = \{x_{1,v},\dots,x_{k,v},y\}$. Define hypergraph $H$ by
$$
  H = E(G_1) \cup \dots \cup E(G_k) \cup \{f_1,\dots,f_n\}.
$$
Then $H$ is 2-colorable if and only if $G$ is $k$-colorable. I don't understand this conclusion and the only example I've been able to come up with where this is true is $k = 1$.


texts: Are there "NP-Intermediate-Complete" problems?

texts:
Assume P $\ne$ NP.

Ladner's Theorem says that there are NP Intermediate problems (problems in NP that are neither in P nor NP-Complete).  I have found some veiled references online that suggest (I think) that there are many "levels" of mutually reducible languages within NPI that definitely do not all collapse into one.

I have some questions about the structure of these levels.

Are there "NP-Intermediate-Complete" problems - that is, NP-Intermediate problems to which every other NP-Intermediate problem is polytime reducible?
Sort NP - P into equivalence classes, where mutual reducibility is the equivalence relation.  Now impose an ordering on these equivalence classes: $A > B$ if the problems in $B$ reduce to problems in $A$ (so clearly the NP-Complete equivalence class is the maximum element).  Is this a total ordering (i.e. the problems are arranged in an infinite descending chain)?  If not, does the "tree structure" of the partial ordering have a finite branching factor?
Are there any other interesting known structural components of NP - P?  Are there any interesting open questions about the underlying structure?

If any of these are currently unknown, I would be interested to hear that as well.

Thanks!


texts: A data structure for minimum dot product queries

texts:
Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of the following format: given $x \in \mathbb{R}^n$ output $\min_i \langle x, v_i \rangle$. Is it possible to go beyond the trivial $O(nm)$ query time? For example if $n = 2$, then it is immediate to get $O(\log^2 m)$.

The only thing I can come up with is the following. It is an immediate consequence of Johnson-Lindenstrauss lemma that for every $\varepsilon > 0$ and a distribution $\mathcal{D}$ on $\mathbb{R}^n$ there is a linear mapping $f \colon \mathbb{R}^n \to \mathbb{R}^{O(\log m)}$ (which can be evaluated in $O(n \log m)$ time) such that $\mathrm{Pr}_{x \sim \mathcal{D}}\left[\forall i \quad \langle x, v_i \rangle - \varepsilon (\|x\| + \|v_i\|)^2 \leq \langle f(x), f(v_i)\rangle \leq \langle x, v_i \rangle + \varepsilon (\|x\| + \|v_i\|)^2 \right] \geq 1 - \varepsilon$. So, in time $O((n + m) \log m)$ we can compute something that is in some sense close to $\min_i \langle x, v_i \rangle$ for most $x$'s (at least if the norms $\|x\|$ and $\|v_i\|$ are small).

UPD The abovementioned bound can be somewhat sharpened to the query time $O(n + m)$ if we use locality-sensitive hashing. More precisely, we choose $k := O(\frac{1}{\varepsilon^2})$ independent Gaussian vectors $r_1, r_2, \ldots, r_k$. Then we map $\mathbb{R}^n$ to $\{0,1\}^k$ as follows: $v \mapsto (\langle r_1, v \rangle \geq 0, \langle r_2, v \rangle \geq 0, \ldots, \langle r_k, v \rangle \geq 0)$. Then we can estimate the angle between two vectors within an additive error $\varepsilon$ by computing $\ell_1$-distance in the image of this mapping. Thus, we can estimate dot products within an additive error $\varepsilon \|x\| \|v_i\|$ in $O(\frac{1}{\varepsilon^2})$ time.


texts: About lower bounding the sample complexity of a distribution

texts:
Given a joint probability distribution over a finite number of random variables (each with a finite range space) of which only a certain subset is observable, is there a notion of "sample complexity" as in the minimum number of samples required of the observables for the full joint distribution to be recoverable with some given accuracy? (when possible)

More precisely think of being given a distribution $D$ and constants $\epsilon, \delta >0$ and let there be some parameter say $p(D)$ that one is trying to learn.  Now lets say that by taking $N$ samples (denoted as $\{N\}$) from $D$ by using some algorithm $A$, one is able to estimate $p(D)$ as $p'(D,N,A)$. Now I would think that a natural notion of "sample complexity" would be to look for this number,

$$min_{N} [ \{ N \vert  Pr_{\{N\}} [ \vert p(D) - p'(D,N,A) \vert \leq \epsilon  ]  ] \geq 1- \delta \} ]$$

Has such a thing been defined or computed or studied? (...maybe one would very optimistically also want to put in a ``$min_A$" over the whole expression if in any restricted scenario that too is possible to account for and hence making the quantity truly intrinsic to $D$!..)

(..I can imagine such a question coming up with say "topic modelling" where one can sample only the "word" random variables (the "views") and under certain conditions one can recover the joint distribution of the topics and the views..)

I would be equally happy to know if there above kind of notion of "sample complexity" has been studied in situations when either all the random variables are observable or when few or all of the random variables have a continuum range.
Can someone kindly link me to some pedagogic reference about how one proves lower bounds on such a notion of sample complexity of learning a joint distribution?

The closest thing I have found in this regard are things like Theorem 1 (page 12) , Theorem 2 and Theorem 3 (page 14) in this paper, http://newport.eecs.uci.edu/anandkumar/pubs/AltTensorDecomp_Part2LVMs.pdf But then I am not understanding as to why these would be called "sample complexity" because these theorems don't seem to tell me any lower bounds on the number of samples needed to learn the tensors they are looking at. What one can do at best is to take the RHS of the equations proved in these three theorems and ask for that to be upper-bounded by some error tolerance and hence invert that to get a lower-bound on the number of samples needed.

But this is a-priori not the same thing as finding out the minimal number of samples needed to get that accuracy. Am I missing something?


texts: Some nuances on Group and Subgroup Isomorphism?

texts:
(1) Is it known Group Isomorphism is in $\mathsf{coNP}$ and is the conjecture so? Is there a good reference for $\mathsf{coNP}$-ness in similar situations?

(2) Is subgroup isomorphism $\mathsf{NP\text-complete}$?

(3) Is there an explicit relation between group cardinality and number of generators and bit size of generators that is used in the presentation of the group? For instance if the group has cardinality $2^{\log^cn}$ is there a bound on size and number of generators?


texts:
I'm trying to implement an approximation algorithm for the 0-extension problem

I found the following paper:

  Approximation Algorithms for the
  0-extension problem by Gruia
  Calinescu, Howard Karloff and Yuval
  rabani.

On page 5 they explain the algorithm
but I don't understand it (I'm not English and some words are difficult to understand)

so can someone explain the algorithm from an implementation standpoint?

As input data (numbers are for illustration), I have a graph with 64 vertexes and a number of connections (no info about the max degree)
every connection has a "distance" defined
I want to colour the vertices with 3 colours
some vertices already have a colour

How do I do this? I'm pretty advanced software designer so you can use high-level pseudo-code

EDIT

  $\delta(u,v) = d(f(u),f(v))$

What do they mean with $f(\cdot)$?
Aren't $d$ and $\delta$ the "distance" functions?

  minimize $\sum_{uv \in E} c(u,v) \delta(u,v)$

Where is the $c(\cdot)$ coming from?
Cost function?

Rounding procedure:

  set $f(t) = t$ for all terminals

Are the terminals the colors or the vertices or vertices with a color assigned?

  such that $\delta(u,\sigma_j) \leq \alpha A_u$

What is $A_u$?
What is $\sigma_j$?

edit2

ok so i need to compose the equasions and solve them with a LP solver

lets take this example:
http://i77.photobucket.com/albums/j74/bertyhell/Diagram1.png
I want to know what colour to give B and C
in this case the best solution is to give C the red colour and B a green colour (B and A are furthest from each other)

2 terminals already have a color
and every edge as a "distance"
my cost function is:

int c(u,v){
    if(u.color == undef || v.color == undef){
        return undef //unknown cost
    }else if(u.color == v.color){
        return 90 - "distance"
    }else{
        return 0 //no cost
    }
}

how do I put this in an equation?

and won't the equation system be undefined if there are to many terminals without a colour?

and if it isn't undefined, wont the first step solve the whole 0-extension problem?


texts: Are the minimal quantum and classical span programs the same?

texts:
A span program is a linear-algebraic way of specifying a boolean function introduced here which has found recent application in quantum query complexity.

A span program for a function $f: \{0,1\}^n \rightarrow \{0,1\}$ consists of an ambient vector space $V$, target vector $z \in V$, and $2n$ subspaces $U^0_1, U^1_1, ... , U^0_n, U^1_n$. With the condition that:

$$
f(x) = 1 \; \text{if and only if} \; z \in \text{span}\{U^{x_1}_1, ... , U^{x_n}_n\}
$$

The classical complexity measure on span programs is size: the sum of the dimensions of all $2n$ subspaces. The quantum complexity measure on span programs is witness size which (is slightly more subtle, but basically) the the norm of the vector that actual shows that $z$ is spanned or proves that it can't be (see here for a proper definition). In particular, we fix specific vectors to span the individual subspaces, and then a witness can be generated for each input by looking at the linear combination of vectors that match $z$, then we take max over all inputs.

To me, these two measures look very different. Are there known correspondences between the programs that minimize the measures? If we take the span program of minimal size, is it possible to pick a basis for the $2n$ subspaces to produce a span program of minimal witness size? Is the minimal span program measured by size the same as the minimal span program measured by witness size?

Related questions

Span programs, witness size, and certificate complexity


texts: Relationship between $O(\log n)$ (bounded) treewidth and H-minor-free

texts: What is the relationship between graphs which have $O(\log n)$ treewidth and $\mathcal{H}$-minor-free graphs? Are graphs which have $O(\log n)$ treewidth $\mathcal{H}$-minor-free? I know that graphs which are $\mathcal{H}$-minor-free have treewidth $O(\sqrt{n})$ but I am concerned more with the relationship between $O(\log n)$ treewidth graphs and $\mathcal{H}$-minor-free graphs.


texts:
What exactly is theoretical computer science? Is it learning to code in various language and making apps in platforms? Or is it just thinking about faster and faster algorithms so that you can achieve a task more efficiently by the computers? Or is it programming and thinking of new life situations which can be simulated on a computer? What exactly are we trying to do here ?

For example, physics is trying to find all the laws of nature that govern it; mathematics is a tautology based to model reality and used as a very precise language by other subjects.

What exactly is theoretical computer science? When computers were designed by us humans for application purposes, hence it must all drop down to mathematics and physics in the end? Then where is the "theory" in computer science itself.

Sorry for being too naive but I want to know what does a theoretical computer scientist do ?


texts:
We are working in distributed computers, and we came up with a complexity problem which reduces to a minimum path covering problem. We currently do not know how to solve it. The problem is the following:

Let $k$ be some integer, and let $Z_k$ be a graph containing $\frac{k(k+1)}{2}$ vertices.
We label each vertex with a couple $(i,j)$ such that $1 \leq i \leq j \leq k$.
Hereafter, we name vertices using their label.
The set of edges in $Z_k$ is defined as follows  :
$\{ ((i,j),(i',j')) | i' >i \land j' \geq i \}$.

What is the minimal path covering of $Z_k$ ?

Reading
"On Path Cover Problems in Digraphs and Applications to Program Testing"
by Ntafos et al. , we have seen that the minimal path covering equals
the cardinal of the greatest incomparable vertex set.
We were thinking about the following set:
$S= \{ (i,j) : i \geq k/2 \land j < k/2 \}$
which has a cardinal of $\frac{k^2}{4}-\frac{k}{2}$.

Sincerely,

Pierre


texts: How to benchmark #2-SAT counting algorithms?

texts:
Are there any libraries of #2-SAT instances that are hard to solve with state-of-the-art exact solvers (sharpSAT, cachet, ...)?

Alternatively: are there practical ways to generate hard #2-SAT instances?

I have only been able to find benchmark instances for #k-SAT for $k\ge3$.


texts:
I have a minimum cost path selection problem that is different from the usual shortest path in that each type of cost is accounted only once in the total cost of the path if multiple edges on the path have that type of cost. For example, in the example below, cost of the red path that goes from S to D is C(F1)+C(F2). Although both F1 and F2 appear multiple times along the path, each one of them is only counted once. This path also is the minimum cost path since any other path will have F3 as well and so its cost will be C(F1)+C(F2)+C(F3). Costs are positive real numbers and are known for each item.

I named it Union-Sum Cost since if we look at different edges, cost of a path is the sum of costs of the union of items associated with the edges on the path.

Has this problem been solved before? (like an approximation algorithm) Is there a well-known graph problem that resembles this? And do you think this is a hard problem?


texts:
I've read that this SE is for research-level CS questions; this is certainly research level, just not my field of research, so it is hard for me to assess how difficult the question really is. So in case this is well-known and easy, I'd still be grateful for a hint or a reference. Thanks!

So here is the question:
Given a multiset $S$ of integers (or rationals), does there exist a multi-subset $T\subsetneq S$ such that $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s|\le\sum_{s\in S}s$?

In case we replace the rhs with some constant $l\ge0$, this reduces to the subset sum decision variant, which is NP hard. But is this variant still NP-hard?

Thanks!
- Josely


texts:
Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths and the question of how it may be extended to the wider class of purely functional sequences based on trees.

The problem is the following: You want to test for almost certain structural equality in O(1) time by means of strong hashing. If the hash function is structurally recursive, i.e. hash (x:xs) = mix x (hash xs), then you can transparently cache hash values on lists and update them in O(1) time when an element is consed onto an existing list. Most algorithms for hashing lists are structurally recursive, so this approach is eminently usable in practice.

But suppose instead of singly-linked lists you have tree-based sequences that support concatenating two sequences of length O(n) in O(log n) time. For the hash caching to work here, the hash mixing function must be associative in order to respect the degrees of freedom a tree has in representing the same linear sequence. The mixer should take the hash values of the subtrees and calculate the hash value of the whole tree.

This is where I was six months ago when I spent a day mulling over and researching this problem. It seems to have received no attention in the literature on data structures. I did come across the Tillich-Zemor hashing algorithm from cryptography. It relies on 2x2 matrix multiplication (which is associative) where bits 0 and 1 correspond to the two generators of a subalgebra with entries in a Galois field.

My question is, what have I missed? There must be papers of relevance in both the literature on cryptography and data structures that I failed to find in my search. Any comments on this problem and possible venues to explore would be greatly appreciated.

Edit: I am interested in this question on both the soft and cryptographically strong ends of the spectrum. On the softer side it can be used for hash tables where collisions should be avoided but aren't catastrophic. On the stronger side it can be used for equality testing.


texts: Does Dinur's proof of PCP Theorem imply a procedure for reconstructing a witness?

texts:
In Section 3.2 of On Syntactic versus Computational Views on Approximability by Khanna, et al., the authors state that an adaptation of the results from Proof Verification and Hardness of Approximation Problems by Arora, et al. proves that there is a polynomial time computable gap-introducing reduction from SAT to Max 3-SAT, and furthermore, that there is a polynomial time computable function that computes a satisfying assignment for an instance of SAT given an assignment satisfying strictly greater than $1 - \epsilon$ of the clauses of the transformed instance of Max 3-SAT, where $\epsilon$ is the gap. From what I understand, the authors claim that such a function exists because the proof by Arora, et al. utilizes an error-correcting code, so the original message (the assignment satisfying the instance of SAT) can be reconstructed from a corrupted message (the assignment satisfying greater than $1 - \epsilon$ of the clauses of Max 3-SAT). This function for reconstructing a satisfying assignment is critical for proving hardness results in classes of approximable optimization problems under approximation-preserving reductions.

Does The PCP Theorem by Gap Amplification by Dinur also imply the existence of such a function?


texts: Looking for Literature Source for Following idea

texts:
I am quite certain that I am not the first to entertain the idea that I am going to present.  However, it would be helpful if I can find any literature related to the idea.

The idea is to construct a Turing Machine M with the property that if P=NP then M will solve 3-SAT in polynomial time.  (The choice of 3-SAT is arbitrary.  It could be really any problem in NP).

Just to be clear, this is not a claim that P=NP.  In fact, I believe the opposite.  I merely state that if P=NP, then M will provide a polynomial-time solution.  If you are looking for an efficient solution, I should warn that this is far from efficient.

M is constructed as follows:
first, assume a canonical encoding for all Turing Machines, and apply a numbering to these machines.  So, there is a Turing Machine number 1, a number 2, etc.  The idea of a Universal Turing Machine that can read the format for a provided machine and then simulate that machine's running on separate input is pretty well known.  M will employ a Universal Turing Machine to construct and simulate each Turing Machine in turn.

It first simulates the running of Turing Machine 1 for a single step.
It then looks at the output of Turing Machine 1.
It the simulates the running of Turing Machine 1 for two steps and looks at output,
then proceeds to simulate Turing Machine 2 for 2 steps.
It continues and loops in this fashion, in turn running Turing Machine 1 for k steps then 2 for k steps ... then eventually machine k for k steps.

After each simulation run, it examines the output of the run.  If the output is an assignment of variables satisfying the 3-SAT problem instance, M halts in an accept state.  If on the other hand, the output is a proof-string in some verifiable proof-language with the proven result that the problem instance is not satisfiable, M halts in a reject state.  (For a proof-language, we could for example, use the Peano Axioms with Second-Order logic and the basic Hilbert-style logical axioms.  I leave it as an exercise for the reader to figure out that if P=NP, a valid proof-language exists and is polynomial-time verifiable).

I will claim here that M will solve 3-SAT in polynomial time if and only if P=NP.
Eventually, the algorithm will find some magical Turing Machine with number K, which just so happens to be an efficient solver for the 3-SAT problem, and is able to provide a proof of its results for either success or failure.  K will eventually be simulated running poly(strlen(input)) steps for some polynomial.  The polynomial for M is roughly the square of the polynomial for k in the largest factor, but with some terrible constants in the polynomial.

To reiterate my question here: I want to know if there is a literature source that employs this idea.  I am somewhat less interested in discussing the idea itself.


texts: Real-time countable vs fully time-constructible

texts:
Real-time countable functions were used in time hierarchy theorem in the papers of Hartmanis and Stearns (Theorem 9, 9.1 ...) and also of Hennie and Stearns (Theorems 3, 5, 7 ...). Now it is a "standard" to use the notion of time-constructible function instead. This question has the aim to compare these two notions.

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. See this question for more about (fully) time-constructible functions.

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is real-time countable, if

$f$ is monotone increasing
there exists a deterministic multi-tape Turing machine $M$ that on empty input, on $n$-th step outputs 1 if $\exists m: f(m)=n$ and else outputs 0.

The second condition sais that started on empty input, $M$ on each step outputs 0 or 1, depending on whether the number of the step is in the image of $f$.

It is easy to see that the function $(n-2)^2+5$ is fully time-constructible. But it is not real-time countable, since it is not monotone increasing. It is also easy to see that the function, given recursively by $f(0)=1$,
$$f(n)=\left\{\begin{array}{ll}
  f(n-1)  & \mbox{if the turing machine encoded by }n \mbox{ halts on empty input}\\
  f(n-1)+1 & \mbox{else}
 \end{array}
\right.$$
is not recursive, thus not fully time-constructible. But it is real-time countable (consider a Turing machine that on each step outputs one).

Thus, the discussed notions are in general incomparable. But the reason just given is in some sense "primitive". Thus it is interesting to consider an injective real-time countable function and a monotone fully time-constructible function (I think that the essence of both definitions remains).

It is easy to see that all injective real-time countable functions are fully time-constructible: just wait for the $n$-th one to be outputted (it will be in the $f(n)$-th step). And the question that remains is:

  Q: Is every monotone fully time-constructible function real-time countable?

I think that the answer to this question would somehow shed more light on which notion is "stronger". Note that fully time-constructibility of some function $f$ tells us that we can compute fast enough whether on the $f(n)$-th step we should output 1 or 0. But in the next step we need the information about $f(n+1)$ and then for $f(n+2)$ ...


texts: Planar graph via the intersection of fat thingies?

texts:
There is a beautiful theorem of Koebe (see here) that states that any planar graph can be drawn as kissing graph of disks (very romantic...). (Putting it somewhat differently, any planar graph can be drawn as the intersection graph of disks.)

Koebe theorem is not very easy to prove. My question: Is there an easier version of this theorem where instead of disks one is allowed to use any fat convex shapes (convexity might be open to negotiations, but not fatness). Note, that every vertex can be a different shape.

Thanks...

Clarification: For a shape $X$, let $R(X)$ be the radius of the smallest enclosing ball of $X$, and let $r(X)$ let me the radius of the largest enclosed ball in $S$. The shape $S$ is $\alpha$-fat if $R(x) /r(x) \leq \alpha$. (This is not the only definition for fatness, BTW.)


texts: Reference to "compressibility" of logarithmic space

texts: Is there a reference somewhere for the result SPACE($O(\log n)$) = SPACE($\log n$)? i.e. Big-O doesn't matter in logspace since you can compress the space. I feel like this is an elementary result but I can't figure out if it was stated somewhere, or if it's a corollary of something, or if it's just folklore.


texts:
Consider the following 2-player game:

Nature randomly picks a program
Each player plays a number in [0, infinity] inclusive in response to nature's move
Take the minimum of the players’ numbers, and run the program for (up to) that many steps (unless both players chose infinity)
If the program halts, the player who played the minimum number gains 1 point. If the program does not halt, that player loses 1 point. Any player who played a non-minimum number receives 0 points, and both players receive 0 if they both play infinity.

(Corner cases may be handled in whatever way best preserves the spirit of the problem - e.g. upper semicontinuity may be helpful.)

The question: does this game possess a computable Nash equilibrium?

Without the computability requirement, each player just plays the exact number of steps in which the program halts (or infinity, if it does not halt).

If you try the usual diagonalization argument for the halting problem, you'll find that an equilibrium exists in mixed strategies, so the obvious approach does not immediately work. Maybe there's some way to tweak it?

On the other hand, the equivalence of real closed fields means that finite games with computable payoffs have computable equilibria. This game is not finite, but the strategy space is closed and the payoffs computable, so maybe the same trick could be applied with Glicksberg's Theorem or something in that vein? The problem is, without the computability requirement, the equilibrium is in pure strategies, so any attempt to prove existence of a computable equilibrium using existence of a maybe-computable equilibrium has to explain why the equilibrium is downgraded from pure to mixed.

This seems like the sort of problem where people may not have addressed this exact question before, but might have looked at something similar. I haven't been able to turn up much, but if anyone knows of something in spirit, please let me know!

Motivation: there's a common intuition that self-reference is the main block to computability - i.e., that any uncomputable problem somehow embeds self-reference. If a game roughly like this has a computable Nash equilibrium, it would provide evidence for that intuition.

UPDATE: To clarify, the equilibrium should be "computable" in the sense of computable real numbers: the probabilities describing the mixed strategy distribution should be computable to arbitrary precision. (Note that only finitely many probabilities will be above any particular precision cutoff.) This also means that we can sample from an arbitrarily close approximation of the equilibrium strategy.


texts: Is there a history-independent rope data structure?

texts:
I'm experimenting with a toy (functional) programming language. One of my ideas is to aggressively hash cons everything, thus representing any data structure as a single integer. In that context, data structures are only efficient if they are history independent so I would switch out traditional RB/AVL/weight balanced trees for PATRICIA trees. For example, any set S would then be represented by the same underlying integer regardless of how it had been made.

A modern editor for my language (e.g. with throwback of inferred types) could benefit from "free" incremental updates to lexing, parsing and even type checking in the event of insertions and deletions of characters in the input program provided I can use a history-independent data structure supporting efficient enumeration, insertion and deletion.

Therefore, I am wondering if there is a history-independent rope?


texts: Finite Automata with succinct representation of chains of states

texts:
Consider a kind of automata similar to common DFAs or NFAs where it is possible to represent succinctly linear chains of states. In other words, an automaton like this:

could be represented in this way:

where the thick edge represent the chain of states, where each state is connected to the next by a single edge and all the edges are labeled in the same way, in this case by $a$.

So this is not really a counter or anything fancy, it is just a succinct representation of a very limited special case. By succinct, I mean that by representing the $k$ parameter in binary, the second automaton can be represented in logarithmically less space than the first. Let's call this kind of automata the "succinct automata", SA, so say DSA and NSA for short for the deterministic and nondeterministic variants.

Now, my question concerns the complexity of boolean operations over this kind of automata.

In details:

Given two NSAs $\mathcal{A}$ and $\mathcal{B}$, is it possible to build the NSAs for $\mathcal{L}(\mathcal{A})\cup\mathcal{L}(\mathcal{B})$ and $\mathcal{L}(\mathcal{A})\cap\mathcal{L}(\mathcal{B})$, of size still polynomial in the size of $\mathcal{A}$ and $\mathcal{B}$ (i.e. without paying for the unrolling of the chains before computing the results)?
Is it possible to compute those operations on DSAs (deterministic) guaranteeing that the resulting automata stay deterministic (and still polynomial size)?
Is it possible to determinize an NSA with only a singly-exponential blowup (i.e. without paying for the unrolling of the chains before paying for the classic determinization)?

My feeling on all of these after having though about it a bit is that an exponential increase in size is needed in most of the cases, or that the results must be nondeterministic.

So the question is really: is anybody aware of a place where this kind of problems have been addressed? Has this variant of finite automata being studied before?


texts: Can Lenstra's algorithm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k?

texts:
It is well-known that Lenstra's famous algorithm (presented in the paper
Integer programming with a fixed number of variables) can solve an ILP problem in $O^*(f(k))$ time where k is the number of variables occur in the ILP.

My question is that whether the algorithm or any of its improved versions can output all feasible solutions in $O^*(f(k))$ time?


texts: Placing points far away from each other in simple polygon

texts:
I am sure the following problem has been studied before, but I did not find any literature about it.

Place m points in a simple polygon such that
the minimum geodesic distance among those points is maximized.

Does anybody know the name of this problem, or has any references?

Maybe the problem corresponds to a known special case of the facility location problem?


texts:
Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?

This question came up while watching "Graduate Complexity at CMU - Lecture 2: Hierarchy Theorems (Time, Space, and Nondeterministic)" https://www.youtube.com/watch?v=HrJKTTJfweo

In time 00:53:30 - Prof. Ryan O'Donnell states that "there are languages decidable in $DTIME(2^{t(n)})$ that are undecidable in $NTIME(t(n))$".

Is this currently a known fact?

Your answers will be greatly appreciated!

Thanks,
Avi Tal


texts: Given the following set of LISP primitives, is it possible to extend the eval function to evaluate defmacro?

texts:
In this paper McCarthy sets out the following primitives: QUOTE, CAR, CDR, CONS, EQUAL, ATOM, COND, LAMBDA and LABEL.

He then sets up the following abbreviations: T, NIL, DEFUN, NULL, CADR, LIST, AND, ALT, and SUBST.

He rounds it up with an incredible definition of the EVAL function used in the reader.

Given the above set of LISP primitives, is it possible to extend the EVAL function to evaluate defmacro?


texts: Confusion with the proof of constraints for a particular adiabatic quantum evolution

texts:
[This might be related to one of my previous unanswered questions.]

This proof belongs to the paper, How to Make the Quantum Adiabatic Algorithm Fail by Edward Farhi, Jeffrey Goldstone, Sam Gutmann and Daniel Nagaj. It is the theorem 1 on page 3. The theorem is as follows.

  Let $H_P$ be diagonal in the $z$ basis with a ground state subspace of
  dimension $k$. Let

  $$ H(t) = \left(1 - \frac{t}{T} \right) E \left( \mathbb{I} -
> |s\rangle \langle s|  \right) + \left( \frac{t}{T} \right) H_P $$ .

  Let $P$ be the projector onto the ground state subspace of $H_P$ and
  let $b > 0$ be the success probability, that is, $b = \langle \Psi (T)
> | P | \Psi (T) \rangle $. Then

  $$ T \ge \frac{b}{E} \sqrt{\frac{N}{k}} - \frac{2 \sqrt{b}}{E} $$.

As the proof proceeds I can't really follow it completely.

For example, there are three equations at the bottom of page 3 which evaluates $S(t)s$. As per the paper $S(t)$ is the sum on $x$. But the expression looks to involve norms. I understand that there are more than one kind of norms. What kind of norm are we talking about here? Why? What is the physical significance of this quantity in this context?


texts:
I am looking for an algorithm that will split a set $A = \{ a_1, a_2, ..., a_N \}$ into (possibly) multiple subsets based on a given criterion. In my case, the criterion is spatial overlap of the elements in the set, but it could be any criterion really. Let's define a function $crit(a_1, a_2)$ which takes as input two elements of $A$ and outputs a boolean indicating whether those two elements overlap.

If $crit(a_i, a_j) = false$ for all $a_i, a_j \in A$, then the output of the algorithm should be a single set containing all of the elements of $A$. If $crit(a_i, a_j) = true$ for a single pair of elements $a_i, a_j \in A$, then the output of the algorithm should be two sets, one set containing all elements except for $a_i$, and one set containing all elements except for $a_j$. We continue this pattern until we reach the other extreme case, in which $crit(a_i, a_j) = true$ for all $a_i, a_j \in A$, in which case the output of the algorithm should be a partition of $A$: $N$ sets, each containing a single element from $A$.

I would be surprised if this problem has not been formalized before. Is there an efficient algorithm for solving this problem?

Edit: For clarification, it is ok if an element ends up in multiple sets in the output. In fact, an element should be in every set that does not contain an element that overlaps with it. For example, if $A = \{ w,x,y,z\}$, $crit(w, x) = true$, $crit(w, y) = false$, $crit(w, z) = true$, $crit(x, y) = false$, $crit(x, z) = false$, $crit(y, z) = false$, then the output should be $A' = \{ \{ w, y \}, \{ x, y, z \} \}$.

Another edit: based on bbejot's response, I did a bit more looking and it does appear that I can reduce my problem to enumerating all maximal cliques of the graph represented by the adjacency matrix bbejot describes in his response. In response to my original question, there is no efficient algorithm for solving this problem, but the Bron–Kerbosch algorithm seems to be pretty standard.


texts:
Barrington, Immerman, and Straubing state

  circuit complexity classes contain problems which are not computable at all in the ordinary sense (e.g., any unary language is in $\text{AC}^0$)

I'd appreciate clarification of this statement; it seems to imply that $\text{AC}^0$ contains even undecidable languages.

Could someone please point out my error, or explain what the authors might mean?

Barrington, D.A.M., Immerman, N., and Straubing, H., On Uniformity within $NC^1$, JCSS 41 274–306, 1990.  doi: 10.1016/0022-0000(90)90022-D


texts: For a given binary-search tree obtain an isomorphic splay tree

texts:
I will assume that the reader is familiar with some undergraduate algorithms and data structures. To people who are not familiar with splay trees I recommend to read through this link : https://en.wikipedia.org/wiki/Splay_tree

An interesting problem is :

  Given a binary search tree $T$ with $n$ nodes. Find the sequence $S$ of
  operations (find, insert, delete) to obtain a Splay tree
  $T_{Splay}$, such that $T_{Splay} = T$.

For example the splay tree equal to this one

could be generated by the following sequence:

Insert(3), Insert(2), Insert(1), Find(2)

My questions are:

Is it possible to obtain $T_{Splay}$ for every binary search tree $T$?
If the answer for the above question is positive, find an algorithm to solve this problem. What about its complexity?
If the answer for the above question is positive, how long need to be the sequence $S$?

Unfortunately I can't find any solutions to these problems which means that either it could be hard or simply uninteresting for most of us. I found also a few links about similar problems but none of them could be applied to this case. The full list of links below:

https://stackoverflow.com/questions/14564437/a-sequence-that-forms-the-same-avl-and-splay-trees
https://stackoverflow.com/questions/22413727/determining-if-a-binary-search-tree-can-be-constructed-by-a-sequence-of-splay-tr

Thanks for any answers,
Bartosz Bednarczyk


texts: A question on the Kolmogorov Complexity of Human I/O behaviour

texts:
Note: From my Twitter poll I managed to get feedback from AI researchers and neuroscientists so far and I think it would be interesting to get input from theoretical computer scientists on this question as well.

The specific question I am interested in is the following: What is the ratio of the Kolmogorov Complexity of Human I/O behaviour, let's call this K(H), relative to K(S), the Kolmogorov Complexity of Slime Mould I/O behaviour?

Here's how I understand the problem:

By I/O behaviour I am referring to the agent-environment interaction loop which may be represented by coarse-grained state-action sequences that are objective, as viewed by an external observer, and potentially countably infinite.
Symbolically, we may refer to these sequences as follows: $(a_i,s_i)_{i \in \mathbb{N}}$ where $s_i$ represents the state of the observable Universe at instant $i$.
If we compress this sequence we will probably end up with a short program which describes the agent-environment interaction as a coupled dynamical system. For clarification, this sequence is obtained by sampling from:

\begin{equation}
p(a_t|s_t)
\end{equation}

as well as from the state-transition probability distribution conditioned on the actions of our agent:

\begin{equation}
p(s_{t+1}|a_t,s_t)
\end{equation}

Given this formulation I think it's fair to say, intuitively, that the causal influence of an individual organism $\mathcal{A}$ on the observable Universe(which is responsible for all possible input signals) is negligible relative to the causal influence of the observable Universe(which includes many other organisms) on $\mathcal{A}$. Now, considering the previous argument it follows that the Kolmogorov Complexity of the organism's environment alone, without that particular organism, is approximately equivalent to the Kolmogorov Complexity of the environment plus an individual Human or Slime Mould so we surely have:

\begin{equation}
\frac{K(H)}{K(S)} \approx 1
\end{equation}

I must note that I don't think this question can be answered in a definitive manner but I'd like to know whether there are important conceptual arguments which I might have overlooked and whether the question
itself might be fundamentally flawed.

References:

Thirty eight things to do with live slime mould. Andrew Adamatzky. 2015.
A three minute introduction to the slime mould
A brief introduction to Kolmogorov Complexity by Marcus Hutter

Update: Just for clarification, an input signal can take many forms. Examples include electromagnetic waves in the form of sunlight, liquid in the form of rain and even extra-terrestrial comets that may cause extinction.


texts: Proof of SAT is complete for NP via first-order reductions

texts:
So I have been reading this: https://people.cs.umass.edu/~immerman/book/ch7.pdf

I do not understand the proof of theorem 7.16, which says that SAT is complete for NP via first-order reductions. My main problem is, that I do not understand the details of the construction of the boolean formula $\gamma(\mathcal{A})$.

Why is the mapping from $ \mathcal{A}$ to $\gamma(\mathcal{A})$ a $t+1$-ary first order query?

I feel like the construction of the first-order reduction isn't explained in much detail and wonder if someone could elaborate more on how the first-order reduction is constructed.


texts:
The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ such that for all $x, y \in S$:
$$(1-\epsilon)||f(x)-f(y)||_2 \leq ||x-y||_2 \leq (1+\epsilon)||f(x)-f(y)||_2$$
It is known that similar statements are not possible for the $\ell_1$ metric, but is it known if there is any way of getting around such lower bounds by offering weaker guarantees? For example, can there be a version of the above lemma for the $\ell_1$ metric that only promises to preserve the distances of most points, but might leave some arbitrarily distorted? One that makes no multiplicative guarantee for points that are "too close"?


texts: Using negative results to prove positive results in computability theory

texts:
Many results in cryptography depend on impossibility results/conjectures in complexity theory. For example, public-key cryptography using RSA is believed to be possible because of the conjecture about infeasibility of the factoring (and the modular root finding problems).

My question is :

  do we have similar results in computability theory? Are there interesting positive constructions using negative impossibility results?

E.g., does the undecidability of the halting problem allow us to perform tasks that we would not be able to do if the halting problem was decidable?


texts:
I have been working on a project that turns out to be a special case of the directed version of the survivable network problem.

Iterative rounding gives a 2-approximation of the undirected case. I'm wondering if the directed case has been studied at all and if so, what approximations can be guaranteed.