texts: Why does there always need to be a direct crossover between parents and children in real valued GAs?

texts:
I have just been thinking about the simulated binary crossover (SBX) operator used in the NSGA-II algorithm and other real-valued genetic algorithms; and i am wondering if there is any reason that there always needs to be a crossover from both parents to both children? do both children need to be the "opposite" of each other in order to preserve diversity? or is it something that is just assumed?

As far as i can tell, the SBX operator seems to basically work by flipping a coin for each indexed element along a pair of strings to decide if the operator is called, and if the coin flip is successful, it generates a pair of values that are close to the original parent values in accordance with some probability distribution, and either swaps them between the children (p1_i->c2_i | p2_i->c1_i), or inserts them into their respective children (p1_i->c1_i | p2_i->c2_i).. but the key being, that the two offspring are always the "inverse" of eachother..

eg:
p1 = [4 6 2 0 3]     p2 = [7 1 9 8 5]
c1 = [4 1 9 0 3]     c2 = [7 6 2 8 5]

(to make my point easier to explain, i have omitted the fact that the child values are usually perturbed slightly from their original parent values when using SBX - ie. I am taking a child value of 2.2 to mean the same as a parent value of 2)

You can see, in this way, c1 is the "inverse" of c2. Is there any reason why both children can't take on the characteristics of the same parent (p1_i->c1_i | p1_i->c2_i)?

eg:
p1 = [4 6 2 0 3]     p2 = [7 1 9 8 5]
c1' = [4 6 9 0 5]     c2' = [4 1 2 0 5]

I think I understand why this isn't the case with standard binary crossover, as you are dealing with blocks of values, but with real valued crossover you are taking each individual element in the string separately, so why can't both children take on the same value with a certain probability?

The only reason that I can think of is that it might be in order to maintain a higher diversity among the child solutions; and if a solution such as c2' was required, then it must come from a different crossover event in the future.

Is my thinking on the right track? or is there another reason?

EDIT:
I suppose the solution to this would be to generate two potential child values per crossover but only one child, which tosses a coin to see which of the potential values it gets; however this would require twice the number of crossover operations.


texts: Is there a "common" name for this type of combinatorial optimization problem?

texts:
I'm trying to find papers that discuss approaches (in particular, any Deep Learning or Deep Reinforcement Learning techniques) that could be used used to solve the problem described in the next paragraph. My question is whether such problem has a an equivalent problem with a "famous" name (similarly to what happens with problems like the Knapsack problem or the Job Shop Scheduling problem), since that would make my search much easier.
The problem in question is: given n tasks T1, T2, ..., Tn of varying cost $c_{i}$, and m nodes N1, ..., Nm with varying capacity $r_{i}$, what is the task allocation that minimizes the number of used nodes as priority 1, and the total quantity of free resources in the used nodes as priority 2.
So for example, if I have tasks {T1, T2} with costs {3, 7}, and nodes {N1, N2, N3} with capacity {5, 11, 12}. The optimal alocation would be assigning T1 and T2 to N2, since it would require only one node, and the number of free resources is $11 - 7 - 3 = 1$.
Any tips on what sort of terminology I could use on my search are also welcome! Same applies to suggestions on similar "famous" problems that, even if not equivalent, could be interesting to look at (as per my comments above, I am already familiar with the Knapsack and the JSS problems).
Thank you very much!


texts:
We know that #SAT is #P-complete. We also know that problems with polynomial decision versions like PERMANENT are #P-complete. Is it true that finding the number of simple cycles in a graph, i.e. #CYCLE is also #P-complete? This is also a problem with decision version solved in polynomial time.

I suppose that it is either not-known or false, because it might be used a a popular example in textbooks like Arora and Barak's book, etc.


texts: Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

texts:
I was reading a paper of Buhrman and Homer “Superpolynomial Circuits, Almost Sparse Oracles and the Exponential Hierarchy”.

On the bottom of page 2 they remark that the results of Kannan imply that $NEXPTIME^{NP}$ does not have polynomial size circuits. I know that in the exponential time hierarchy, $NEXPTIME^{NP}$ is just $\Sigma_2EXP$, and I also know that Kannan's result is that $\forall c\mbox{   }\exists L\in\Sigma_2P$ such that $L \not\in Size(n^c)$. Of course, Kannan's theorem is NOT saying $\Sigma_2P \not\subset P/poly$ (in order for that to be the case we would need to show that $\exists L\in\Sigma_2P$ such that $\forall c$, $L \not\in Size(n^c)$. However, I don't see how Kannan's result implies that $NEXPTIME^{NP} \not\subset P/poly$?


texts: logic in the presence of doubt, uncertainty, lies

texts:
I was reading Harry Frankfurt's On Bulls*t, a 1986 philosophical essay about this blurry notion between truth and falsity.

This is not a gratuitous exercise.  This may have applications to computer science, since we are always piping data-sets into each other.  Some of these data sources may be specious, the piping process can break down, or the conclusions we draw from them can be wrong as well.

One way of approaching Frankfurt's theory may be to express in terms of logical circuits, where the integrity of the gates or the inputs may be in question.

On pencil and paper, we mostly use boolean logic with values $T,F$ and gates $\mathbf{not},\vee,\wedge$.  Maybe it is possible to perturb boolean logic slightly to model how circuits are robus or break down with respect to noise.

Do logical theories exist accounting for doubt and uncertainty? Can we measure how much a lie hurts the integrity of a conclusion?

I'm sure that even with a collection of verifiably true or false statements, it's possible to write arguments (and conclusions) whose values are in the middle.  Or even to decide if one argument is "more" valid than another.

I apologize ahead of time, if there's no single question here.

COMMENTS

Logic is a very broad subject, but I'm not a logician so I'm not sure how to be more specific.  Ease of use is a priority, which is why I consider just bootstrapping Boolean logic.

I think that when we "call out" a proposition... the conclusion may be true, but the thought process may be wrong, as VijayD suggests in the comments.

It's not clear if bulls**t is the same as uncertainty -- we may be quite sure the proof is wrong.

I think it would be nice to see an extension of boolean logic, which assigns a value to proofs rather than statements.  A proof where all the steps are valid gets assigned a value of T, if steps are faulty, we'd like to measure to what extent the conclusion doesn't follow from the premises.

This idea must have been tried before.  A Google search comes up with the notions like heyting algebra, topos, multi-valued logic and even more sources in the comments and answer.


texts: Is this language recognizable by a 3 symbols TM in O(n log n)?

texts:
I was playing with the very interesting and still open question "Alphabet of single-tape Turing machine" (by Emanuele Viola) and came up with the following language :

$L = \{ x \in \{0,1\}^n \text{ s.t. } |x| = n = 2^m \text{ and } count1(x) = k * m; \; n,m,k \geq 1 \}$

where $count1(x)$ is the number of $1$s in the string x.

For example, if x = 01101111 then n = 8, m = 3, k = 2; so $x \in L$

Can L be recognized by a Turing Machine with a single tape and a 3 symbols alphabet $\{ \epsilon, 0, 1 \}$ in $O(n \log{n})$ steps ?

If we use 4 symbols the answer is yes:

check if $|x|=2^m$ replacing $0$s with $\epsilon$ and $1$s with $2$ and at the same time store $m$ $1$s on the right;
then count the number of $2$s modulo $m$ in $O(n \log{n})$.

For example:

....01101111....... input x  (|x| = 8 = 2^3)
000.021.1212.0001.. div 2, first sweep (000. can safely be used as a delimiter)
000.022.1222.00011. div 2, second sweep
000.022.2222.000111 div 2, third sweep --> m = 3 (= log(n) )
000..22.2222....111 cleanup (original 1s are preserved as 2)
000..22.2221102.... start modulo m=3 calculation
000..22.2210022.... mod 3 = 2
000..22.2000222.... mod 3 = 0
000..22.0012222.... mod 3 = 1
000..20112.2222.... mod 3 = 2
000..11122.2222.... ACCEPT


texts: Application of weak determinantal identities to GCT?

texts: In general determinants have many identities. Would it help the $GCT$ program by invoking the paradigm of identities such as to state that if the permanent is converted to determinant then it has to satisfy certain identities and therefore by reason $x,y,z$ we get lower bound on permanent or does it reduce to the symmetry characterization also (simply because determinantal identities follow from symmetries)? I am asking this because may be there are identities (I cannot think of one) that need only fewer essential symmetries (other symmetries just follow as consequence) making it easier to prove lower bounds (any superpolynomial lower bound on weaker assumptions can only be good).


texts: How expensive may it be to destroy all long s-t paths in a DAG?

texts:
We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-cut is a set of edges whose removal destroys all $s$-$t$ paths longer than $k$; shorter $s$-$t$ paths as well as long "inner" paths (those not between $s$ and $t$) may survive!

Question:
Is it enough to remove at most about a $1/k$ portion of edges from a DAG
 in order to destroy all $s$-$t$ paths longer than $k$?

That is, if $e(G)$ denotes the total number of edges in $G$, does then every DAG $G$ have
a $k$-cut with at most about $e(G)/k$ edges?  Two examples:

 If all $s$-$t$ paths have length $> k$, then a $k$-cut with $\leq e(G)/k$ edges exists.
 This holds because then
there must be $k$ disjoint $k$-cuts: just layer the nodes of $G$ according to their
distance from the source node $s$.

 If $G=T_n$ is a transitive tournament (a complete DAG), then also a $k$-cut with
$\leq k\binom{n/k}{2} \approx e(G)/k$ edges exists: fix a
topological ordering of nodes, split the nodes into
$k$ consecutive intervals of length $n/k$, and remove all edges joining the nodes of the same interval; this will destroy all $s$-$t$ paths longer than $k$.

Remark 1: A naive attempt to give a positive answer (which I also tried as first) would be to try to show that every DAG
must have about $k$ disjoint $k$-cuts. Unfortunately, Example 2 shows that this attempt can badly fail: via a nice argument, David Eppstein has shown that, for $k$ about $\sqrt{n}$, the graph $T_n$ cannot have more than four disjoint $k$-cuts!

Remark 2: It is important that a $k$-cut needs only to destroy all long $s$-$t$ paths, and not necessarily all long paths. Namely, there exist1 DAGs in which every
"pure" $k$-cut (avoiding edges incident to $s$ or $t$) must contain almost all edges.
 So, my question actually is: can the possibility to remove also edges incident with $s$ or $t$ substantially reduce the size of a $k$-cut? Most probably, the answer is negative, but I could not find
a counterexample as yet.

Motivation: My question is motivated by proving lower bounds for monotone switching-and-rectifier networks. Such a network is just a DAG, some of whose edges are labeled by tests "is $x_i=1$?" (there are no tests $x_i=0$).  The size of a network is the number of labeled edges. An input
vector is accepted, if there is an $s$-$t$ path all whose tests are consistent with this vector. Markov has proved that, if
a monotone boolean function $f$ has no minterms shorter than $l$ and no maxterms shorter than $w$, then size  $l\cdot w$ is necessary.  A positive answer to my question would imply that
networks of size about $k\cdot w_k$ are necessary, if at least $w_k$ variables must be set to $0$ in order to destroy all minterms longer than $k$.

1The construction is given in this paper.
Take a complete binary tree $T$ of depth $\log n$. Remove all edges. For every inner node $v$, draw an edge to $v$ from every leaf of the left subtree of $T_v$, and an edge from $v$ to every leaf of the right subtree of $T_v$. Thus, every two leaves of $T$ are connected by a path of length $2$ in the DAG. The DAG itself has $\sim n$ nodes and $\sim n\log n$ edges, but $\Omega(n\log n)$ edges must be removed in order to destroy all paths longer than $\sqrt{n}$.


texts: Reference request: algorithm meta-analyses

texts: Could you direct me to papers that survey families of algorithms? The ideal paper would focus on a single family of algorithms, would show how the improvements in each algorithm work, and ideally would perform this meta-analysis within a single paradigm. This paper comes close to this ideal.


texts:
In computational complexity there is an important distinction between monotone and general computations and a famous theorem by Razborov asserts that 3-SAT and even MATCHING are not polynomial in the monotone Boolean circuits model.

My question is simple: Is there a quantum analog for monotone circuits (or more than one)? Is there a quantum Razborov's theorem?


texts: Grover's search algorithm for 3 coloring

texts:
According to Arora & Barak (pdf), pg. 186, for a polynomial-time computable function $f: \{0,1\}^n \to \{0,1\}$ (represented as a circuit computing $f$), Grover's algorithm finds in $O(\text{poly}(n)2^{n/2})$ time a string $a$ such that $f(a) = 1$ (if such a string exists).

My question is an application of Grover's algorithm to 3 coloring. How can you show, using Grover's algorithm, that 3-coloring can be solved on a quantum computer in time $O(\text{poly}(n)2^{n/2})$, where $n$ is the number of vertices?

This is not a direct application of the algorithm, since although you can easily encode each of the $3^n$ (valid and invalid) colorings of the $n$ vertices using $\log_2(3^n) = n\log_2(3) = O(n)$ bits, this means that Grover's algorithm gives a run time of $O(\text{poly}(n)2^{n\log_2(3)/2}) = O(\text{poly}(n)3^{n/2})$.

So maybe, you would need to show that a coloring (possibly valid) can be encoded using only $n + O(1)$ bits? How would you show that?


texts: Maximizing a convex function where the objective function is separable but the search space is not

texts:
The problem statement is

  Given convex functions $f_i$ over $X$, find  $$\arg\max_{x\in X} \sum_i f_i(x)$$

Does this kind of problem structure allow one to use specific strategies to solve the problem?

Does it help if I also know the lower bound and upper bound of each $\max_x f_i(x)$ and the corresponding $x$?

For example, is there any algorithm like the objective function analogy of branch and bound method ?


texts: On the complexity of a "list" datastructure in the RAM model

texts:
I am interested in the complexity of a data-structure equipped with the following operations (similar to a list):

insertion of an element at a given position within the list
deletion of an element at a given position within the list
get the value of an element at a given position within the list

For instance "insert $v_3$ at position 3"; modifies the list $e_1 e_2 e_3 e_4$
into $e_1 e_2 v_3 e_3 e_4$ and "delete at position 4" would produce the list $e_1 e_2 v_3 e_4$.

Obviously a list can be used to answer all these questions but with a $O(n)$ complexity for all three operations. We can also use an array to have 3. with $O(1)$ complexity but with $O(n)$ complexity for 1. and 2. Finally we can use a balanced tree structure to get all three operations in $O(\ln(n))$. Is there any other known structure that achieves an interesting compromise?

A second but related question: If the operation 3. is limited to retrieve the value of the first element, can we do any better than this? Of course for this a list achieves $O(n)$ for 1. and 2. but $O(1)$ for the first element. With a bit of modification I think we can make the array-based solution work in $O(n)$ for deletion of the first element but $O(1)$ for everything else. With the balanced tree approach we can make $O(\ln(n))$ for 2. and 3. and $O(1)$ for 1. Are there any structure with a better compromise here?

Finally a third (and last) question, when 3. is limited to ask for the first element, what is the best that can be achieved for the sum of the complexities of 1., 2. and 3.? Are there any known lower bounds for this? Is there a better upper bound than $O(\ln(n))$?


texts: How can I find the distribution of a recursive relation with two parameters?

texts:
Suppose we have a recursive relation, e.g. $G(n,m) = G(n-1,m) + G(n, m-1)$, with some initial points where $n,m \in \mathbb{Z}^{+}$ and $F$ is a finite-field, e.g. $\mathbb{Z}_p$ for a prime $p$. Also $G: \mathbb{Z}_p \times \mathbb{Z}_p \rightarrow F$. There are enough initial points such that $G(n,m)$ terminates finitely for finite $m$ and $n$.

I want to compute the distribution of this relation over the field $F$ and then compare it to some other distribution, e.g. uniform or Gaussian distribution. The question is how can I do that? I have searched a lot, but could not find an answer. Even search terms are appreciated.

The reason I want to do this is proving hardness of the problem whose solution is finding $n$ and $m$ when $F(n,m)$ is given.

Thanks in advance.


texts: Clarification for argument in proof of search in N^1/3 queries with hidden variables/non-collapsing measurements

texts:
Let $N=2^n$. In Aaronson's Quantum Computing and Hidden Variables (1) and the recent follow up by Aaronson, Bouland, Fitzsimons, and Lee The space "just above" BQP (2), we consider models of computation involving hidden variables or non-collapsing measurements, and prove that this model of computation is able to simulate Grover's algorithm in time $O(N^{1/3})$.

The proof — Theorem 10 of (1) or Theorem 4.1 of (2); both go the same way for my question — starts with applying $N^{1/3}$ Grover iterations.
After this we should have the state:

$$\alpha \lvert x\rangle+\beta \!\!\!\sum_{y \in \{0,1\}^n} \!\!\lvert y\rangle$$

where $\alpha = \dfrac{1}{\sqrt{2^{n/3} + 2^{-n/3 + 1} + 1}}$ and $\beta = 2^{-n/3}\alpha$.

My questions:

From where do we follow this? The original paper from Grover is referenced, but he provides only the recurrence (in later versions he added a reference to the explicit sin/cos solution).
In my opinion, the state should be something like $\alpha \lvert x\rangle+\beta \sum_{y \in \{0,1\}^n \:\! \setminus\{x\}} \lvert y\rangle$, otherwise we would have for $n=3$ a superposition of $1 + 2^3 = 9$ states. I guess this is only a lazy notation for convenience?
Is this state normalized? If I try e.g. $n=3$, then I will have:
$$\begin{aligned}[b]
      \alpha &= \frac{1}{\sqrt{2^{1} + 2^{-1 + 1} + 1}}
      = \frac{1}{2}
    \\[1ex]
       \beta &= 2^{-n/3}\alpha = 2^{-1} \cdot \frac{1}{2} = \frac{1}{4}
    \end{aligned}$$
If we assume a factor $k$ from the sum, we can try to check the normalization with:
$$\begin{aligned}[b]
   1 = \alpha^2 + (k\beta)^2
= \bigl(\frac{1}{2}\bigr)^2 + \bigl(\frac{k}{4}\bigr)^2
={}& \frac{4 + k^2}{16}
\\[1ex]\implies{}& k^2 = 12
\end{aligned}$$
which is not solvable in integer. (If I take the $n$ general, substitute by $2^{n/3} = s$, and solve for $\alpha^2 + (k\beta)^2 = 1$, I get a polynomial in 3. degree. The general case does not give any insight for me)

The statement from (1) that "one can check that this state is normalized" does not provide a good feeling for my question. Scott Aaronson published a "list" of some errata on his blog for this paper, but the list did not include this. What am I missing?


texts: I am looking for websites or articles where can I find a data with test graphs for domination set problem. In my heuristic algorithms I use undirected and unweighted graphs. So I search for some graphs which already have been tested from other people.


texts: Automatically Adapting Forgetting Factor for Online EM

texts:
I've been reading some interesting papers recently on methods for automatically and adaptively setting the learning rate in stochastic gradient descent (SGD).  In particular, "No more pesky learning rate" and "Adaptive learning rates and parallelization for stochastic, sparse, non-smooth gradients" --- which are a pair of related papers that deal with a method for automatically adjusting the learning rate during stochastic gradient descent.  The first paper introduces the basic method and the second paper talks mostly about how to apply it in practical settings where one typically uses mini-batches and may have a sparse gradient etc.

I was wondering if a similar approach exists for the "online EM algorithm", where one would be learning an adaptive forgetting factor rather than an adaptive learning rate.  Clearly, there is a relationship between the two learning approaches, but it seems like more effort has been put into (and thus more results obtained) SGD.  Are there similar methods to rid the online EM of it's meta-parameter?  Where could I find some publications on this topic?

Thanks!


texts: Understanding the "gap theorem" in geometric spanners

texts:
I am reading the book "Geometric Spanner Networks" by G. Narasimhan and M. Smid. At page 109, there is the following definition:

  Intuitively: A set of directed edges satisfies the gap property, if the sources of any two distinct edges are "far" apart (relative to the shorter of the two edges)
  The gap property: Let $w \geq 0$ be a real number, and let $E$ be a set of directed edges in $\mathbb{R}^{d}$.
  We way that $E$ satisfies the $w-gap\ property$ if for any two distinct edges $(p,q)$ and $(r, s)$ in $E$, we have : $|pr| > w \cdot min(|pq|, |rs|)$

Then (at the same page) comes the following Theorem:

  Let $S$ be a set of $n$ points in $\mathbb{R}^{d}$, and let $E \in S \times S$ be a set of directed edges that satisfies the $w-gap\ property$.
  1. If $w \geq 0$, then each points of $S$ is the source of at most one edge if $E$.
  2. if $w>0$, then $wt(E)<(1+2/w) \cdot wt(MST(S))\log n$ (where $MST(S)$ denotes a minimum spanning tree of $S$.
  3. [not relevant for the question]

Background and context

In the proof of the second claim, there is inner claim that there exists a set $E' \subseteq E$ that is of size $m/2$ such that $wt(E')<(1+2/w) \cdot wt(MST(S))$.
Then comes an induction on $m$ in which the claim  $wt(E)<(1+2/w) \cdot wt(MST(S))\log m$ for any set $E$ that has less that $m$ edges. (Note: $n$ can be replaced by $m$ because $m \leq n$ in every graph that satisfies the $w-gap\ property$). The main point of the induction is relaying on the existence of an subset $E'$ of $E$ which has at least $m/2$ edges, and weight $(1+2/w) \cdot wt(MST(S))$. Then any set $E$ can be partitioned into 2 sets

$E'$ of weight $<(1+2/w) \cdot wt(MST(S))$. (whose existence was proofed before)
$E \setminus E'$ of weight $<(1+2/w) \cdot wt(MST(S)) \cdot \log m$. (according to the induction claim)

My question

Why is there the $\log m$? It seems to me that if the induction claim was "For every $E$ with less that $m$ edges $wt(E)<(1+2/w) \cdot wt(MST(S))$". The same proof would get a better bound (without the $\log m$)


texts: What are some efficient algorithms for finding the solutions to a quadratic multivariate polynomial?

texts:
Based on this question, there's an efficient algorithm to determine whether a quadratic multivariate polynomial has a root.

What are some algorithms to enumerate these solutions?  I'm interested in rational roots (working in $\mathbb{Q}$), if possible, or roots over the real numbers or some subfield of the real numbers if not.  I'd like algorithms that are as efficient as possible.

In the case of a large set of solutions (e.g. exponentially or infinitely large), an algorithm whose running time is polynomial in the number of roots would be ideal.


texts: The complexity of Area-lawed Hamiltonians

texts:
I have recently thought about "importing" some physics-related question into quantum CS:

The notion of the area-law phenomenon in Hamiltonian systems usually stands for a local Hamiltonian on some lattice, whose groundstate exhibits a property in which entanglement of any closed region is proportional to the surface of the region, and not its volume (as it would for a general state).
A famous conjecture is whether all constant-gapped Hamiltonians exhibit this area-law property.
For 1-dimensional systems, this question was answered in the positive by Hastings (arXiv:0705.2024).

Yet, the connection between such systems and complexity theory is very vague: while Hastings' result implies that 1-D area-law-abiding systems can be classically simulated, for general systems this is unknown.
So my question is, is the quest to solve the area-law conjecture worthwhile?
Or adversarially put, can one come up with a QMA-complete local Hamiltonian which is also area-law-abiding.
A small glance at the known QMA-complete local Hamiltonians, which are essentially all based on Kitaev's quantum Cook-Levin theorem yields that these Hamiltonians do not have the area law property.


texts:
I know the following variants of SUBSETSUM problems: $ \mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L} $ (Elberfeld at. al., 2010), NP-complete $ \mathtt{SUBSETSUM} $, and NEXP-complete $ \mathtt{SUCCINCT\mbox{-}SUBSETSUM} $ (link).

Recently, I also ran into $ \Sigma_2^p $-complete $ \mathtt{GENERALIZED\mbox{-}SUBSETSUM} $ problem (Page 16: Schaefer and Umans, 2008).

Do you know some other (non-trivial) interesting variants of SUBSETSUM problems? Specifically, $ \Sigma_l^p $- or $ \Pi_l^p $- complete problems for some $ l > 1 $.

Some definitions:

$
\mathtt{UNARY\mbox{-}SUBSETSUM} = \{ 0^n \# 0^{i_1} \# \cdots\#0^{i_k} \mid \exists I \in \{1,\ldots,k\} \sum_{j \in I}i_j = n \}.
$

$ \mathtt{SUBSETSUM} = \{ S \# a_1 \# \cdots\# a_k \mid \exists I \in \{1,\ldots,k\} \sum_{j \in I}a_j = S \}, $ where $S$ and $a_j$'s are binary numbers.

$ \mathtt{GENERALIZED\mbox{-}SUBSETSUM} = \{ u \# v \# t \mid (\exists x) (\forall y) [ux+vy \neq t] \}, $ where $u$ and $v$ are integer vectors, $t$ is an integer, and $x$ and $y$ are binary vectors of the same length as $u$ and $v$, respectively.


texts:
Milner embedded $\lambda$-calculus into $\pi$-calculus, showing that the $\pi$-calculus is capable of Turing-complete, deterministic calculation. Since parallel compositions of processes in the $\pi$-calculus typically have several possible non-confluent reductions, so one can use the $\pi$-calculus to model non-deterministic concurrency.

Type systems are used to prove certain desirable behaviour of programs. For example, simply typed lambda terms always terminate to a lambda abstraction value (the calculus is strongly normalising). So it's just natural to wonder whether we can find a good type system for $\pi$-calculus such that some of its processes correspond to deterministic computations.

Is there a type system for the $\pi$-calculus probably with types for processes such that processes under certain types are always confluent? Even more, could there be certain types such that their values are processes coming from lambda expressions, e.g. encoded in one of Milner's encodings?


texts: What is the point of calling $\lambda$-calculus an algebra?

texts: What is the difference of calling $\lambda$-calculus an algebra instead of a calculus? I raise this question because I read somewhere the line "$\lambda$-calculus is not a calculus but an algebra" (iirc, attributed to Dana Scott). What is the point? Thanks.


texts: Max-weight connected subgraph problem in planar graphs

texts:
The maximum-weight connected subgraph problem is as follows:

Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$.
Output: a maximum-weight subset $S$ of vertices such that $G[S]$ is connected.

This problem is NP-hard. David S. Johnson mentions on pg. 149 of this column that the problem remains hard in planar graphs of maximum degree three with all weights either $+1$ or $-1$.
I cannot find the cited paper --  A. Vergis, manuscript (1983)
Any ideas as to where to find the paper? Or what the reduction was?


texts:
This problem is inspired by this MO question, which I thought was very interesting.

  What is the oldest open problem in TCS?

Clearly this question needs some clarification.

First, what is TCS?  I think the existence of odd perfect numbers is not TCS. I would say that Hilbert's tenth problem is TCS. I think problems like "Can we construct X with a ruler and compass" are also TCS, since they are asking for an algorithm in a restricted model of computation. There may be no rigorous way to define what a TCS problem is, but use your judgment. Perhaps one test is "If this gets solved, would it most likely appear in STOC/FOCS? Would the researcher who solved it most likely be a theoretical computer scientist?"

Second, what is "oldest"? I mean oldest by date. The stated date should also be verifiable, but I don't think this should be too hard.

Third, what is an "open problem"? By "open problem", I mean a problem that was specifically considered open at some time. Perhaps it appeared at the end of a paper in the open problems section, or maybe there is evidence that some people worked on it and failed, or maybe there are incorrect proofs in the literature, which suggest that it has been studied. An example of something that doesn't fit this criteria: "The greeks studied objects X and Y. Z is clearly an intermediate object, surely they wondered if it can be constructed." If there's no literature on Z from that time period, then it is not an open problem from that time period.

Fourth, what do I mean by "problem"? I mean a specific "yes/no" question, and not something like "Characterize all the objects X with property Y", because such questions often do not have a satisfactory answer. Quite often there will be disagreement as to whether the question has been resolved. Let's not get into such questions here. If it is not a yes/no question, but it is clear that it is really open, that's fine too. (In case this isn't clear, by "problem" I mean a formally stated problem. Please do not convert some folk legend about gambling in the 16th century to a question about BPP and PSPACE.)

Lastly, since this is not a big-list question, please post an answer only if you think it is older than the answers already posted (or if you think the answers posted do not satisfy some other condition -- like they are not TCS, or they are not open). This isn't an indiscriminate collection of old open problems.


texts: Are optimal evaluators actually optimal?

texts:
The following term (using bruijn-indexes):

BADTERM = λ((0 λλλλ((((3 λλ(((0 3) 4) (1 λλ0))) λλ(((0 4) 3) (1 0))) λ1) λλ1)) λλλ(2 (2 (2 (2 (2 (2 (2 (2 0)))))))))

When applied to a church number N evaluates to normal form quickly in several existing evaluators, including naive ones. Yet, if you encode that term to interaction nets and evaluate it using Lamping's Abstract Algorithm, it takes an exponential numbers of beta-reductions in relation to N. On Optlam, specifically:

N   interactions(betas)     (BADTERM N)
1   129(72)                 λλλ(1 (2 (2 (2 (2 (2 (2 (2 0))))))))
2   437(205)                λλλ(2 (1 (2 (2 (2 (2 (2 (2 0))))))))
3   976(510)                λλλ(1 (1 (2 (2 (2 (2 (2 (2 0))))))))
4   1836(1080)              λλλ(2 (2 (1 (2 (2 (2 (2 (2 0))))))))
5   3448(2241)              λλλ(1 (2 (1 (2 (2 (2 (2 (2 0))))))))
6   6355(4537)              λλλ(2 (1 (1 (2 (2 (2 (2 (2 0))))))))
7   11888(9181)             λλλ(1 (1 (1 (2 (2 (2 (2 (2 0))))))))
8   22590(18388)            λλλ(2 (2 (2 (1 (2 (2 (2 (2 0))))))))
9   43833(36830)            λλλ(1 (2 (2 (1 (2 (2 (2 (2 0))))))))
10  85799(73666)            λλλ(2 (1 (2 (1 (2 (2 (2 (2 0))))))))
11  169287(147420)          λλλ(1 (1 (2 (1 (2 (2 (2 (2 0))))))))
12  335692(294885)          λλλ(2 (2 (1 (1 (2 (2 (2 (2 0))))))))
13  668091(589821)          λλλ(1 (2 (1 (1 (2 (2 (2 (2 0))))))))
14  1332241(1179619)        λλλ(2 (1 (1 (1 (2 (2 (2 (2 0))))))))
15  2659977(2359329)        λλλ(1 (1 (1 (1 (2 (2 (2 (2 0))))))))

On similar evaluators such as BOHM, it takes much less beta steps, but more interactions. If optimal evaluators are optimal, how can they evaluate terms asymptotically slower than existing evaluators?

This link has an explanation about the origin of the term, as well as an implementation of the same function that behaves the opposite, almost bizarrely so: it should run in exponential time - it does run in exponential time in most evaluators - yet, optimal evaluators normalize it in linear time!


texts: What are considered to be the most canonical and important consequences of the recursion theorem?

texts:
The recursion theorem in computability states that, for any computable map $f : \mathbb{N} \to \mathbb{N}$ there exists $n \in \mathbb{N}$ such that $\varphi_{f(n)} = \varphi_n$, where $\varphi$ is a standard enumeration of partial computable functions. The one given here is due to Rogers, there is another by Kleene (but they can be derived from each other).

I am collecting typical uses of recursion theorem. I can think of the following:

existence of quines, for instance that there is $k \in \mathbb{N} \to \mathbb{N}$ such that $\phi_k = \lambda n . k$, or that there is $n$ such that $W_n = \{n\}$, where $W$ is a standard enumeration of c.e. sets.
it can be used to establish validity of various kinds of recursion schemata for defining computable functions,
the Kreisel-Lacombe-Shoenfield-Tseitin theorem stating that "all computable functionals are continuous".

What are some other typical uses of recursion theorem?


texts: A lottery that you can be convinced that it is fair

texts: (Sorry if this is well known.) I would like to give some item to one of $k$ agents, so that agent $j$ will get the item with probability $p_i$. Is there a cryptographic (or other) tool so that every agent (and even every observer) will be able to be convinced that the random drawing was indeed fair?


texts: Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?

texts:
I'm sure everybody knows of Buffon's needle experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$.

The implementation of the algorithm in computers usually calls for the use of $\pi$, or a trigonometric function, which, even if they are implemented as truncated series, sort of defeats the purpose.

To circumvent this issue, there is the well-known rejection-method algorithm: draw coordinates in the unit square, and see whether they belong to the unit quarter circle. This consists in drawing two uniform reals $x$ and $y$ in (0,1), and counting them only if $x^2+y^2 < 1$. In the end, the number of coordinates that have been kept divided by the total number of coordinates is an approximation of $\pi$.

This second algorithm is usually passed off as Buffon's needle, thought it is considerably different. Unfortunately, I have not been able to track down who originated it. Does anybody have any information (documented, or at worst undocumented) as to who/when this idea originated?


texts:
In finite model theory, Ehrenfeucht-Fraïssé games gives us tools to prove inexpressibility results for FOL. Pebble games do the same for infinitary logic with finitely many variables.

Do we have such a framework to deal with Second order logics ? At least with $\Sigma_1^1$ and $\Pi_1^1$ ?


texts: Highest lower bound on NP problems (TSP)

texts:
I'll try another question that I haven't been able to find almost any kind of information about, thanks a lot for any kind of pointers or explanations.

Is there a list of the proven lower bounds of NP algorithms (particularly for the TSP problems)?

Like one might imagine that someone already has proven 3SAT to run at at least 2n² for example.

Thanks again


texts: How do you argue a query is impossible in a query language like SPARQL or SQL?

texts:
I've been investigating the ability of the SPARQL query language to represent certain basic tasks in graph theory and machine learning, and have come to believe that it is not possible to do some. For example, I suspect that it is not possible to test (s,t)-connectivity without using Property Paths (but simple with them).  Also, I suspect that it is not possible to list the k nearest neighbors of a list of vectors with a single query.

Is there a proof technique or general approach to show, or at least provide some evidence, that a search or decision problem cannot be represented as a single query in a query language like SPARQL or SQL?


texts: A Quine is a computer program which produces a copy of its own source code as its only output. Is there any Quine program that could print itself out n times, with n specified some way in the program?


texts: Intersecting Complexity Classes with Advice

texts:
In on hiding information from an oracle, the authors (Abadi, Feigenbaum, and Kilian) wrote:

  $(\mathsf{NP/poly} \cap \mathsf{co\text-NP}{/poly})$ ...  is  not  known  to  be  equal  to  $(\mathsf{NP} ∩ \mathsf{co\text-NP}){/poly}$.

They highlighted that in the conference paper, they mistook the two classes. Apparently, the latter is a subset of the former, but we don't know if the containment is strict.

Assuming $X$ and $Y$ are complexity classes, and $F$ is a set of functions specifying the length of the advice strings, are there recent results comparing $(X_{/F} \cap Y_{/F})$ and $(X \cap Y)_{/F}$, resolving issues like the one pointed above?


texts: Chordal Graphs and maximum independent sets

texts:
For a chordal graph $G$ there is a clique tree such that its vertices corresponds to maximal cliques of $G$ and there is a edge between two vertices iff the intersection of the corresponding cliques are also their minimal vertex separator and for each vertex in the graph the cliques containing it, induces a subtree.

Now my questions are:-

  1.Take a subpath of the tree of length 5 with the property that no
  vertex has degree more that 2 and intersection of all the maximal
  cliques is non empty. Does there exist a independent set of
  atleast size 3 in the subgraph induced by that vertices present in the
  maximal cliques taken in the path?

  2.If yes, then is the bound of path length and independent set size tight?


texts: There are by now mountains of results on separators in graphs, from planar separator, tree separator, bounded tree width graphs, bounded genus graphs, etc, etc, etc. Is there any good updated survey about this, and their applications?


texts: How close can we get to linear multiply, add, and compare (on integers)?

texts:
Accoring to K. W. Regan's article "Connect the Stars", he mentions at the end that it is still an open problem to find a representation of integers such that the addition, multiplication, and comparision operations are computable in linear time:

  Does there exist a representation of integers so that addition, multiplication, and comparison are all doable in linear time? Basically, is there a linear time discretely ordered ring?

(1)  How close can we come to linear time multiplication and addition, without compares?  Here I assume that the problem sizes may vary, so that we may need a data structure/algorithm that allows for changing integer sizes.

(2)  For the complete problem, we can assume that we will find an optimum scheme for multiply, add, and compare on the integers.  How close can we get the slowest of these three operations (in the worst case) towards linear time?  And on that note, how fast would the other operations be?

FORMAL PROBLEM STATEMENT

As Emil Jeřábek mentions, we'd like to rule out trivial cases and concentrate on worst case behavior for this question.

So we ask, for non-negative integers $\forall x$ and $\forall y$ where $0 \le x < n$ and $0 \le y < n$, can we find a data structure/algorithm that can perform addition, multiplication, and compares with\between $x$ and $y$ in $O(n \log{(n)})$ time and $O(\log^2{(n)})$ space?


texts: String version of even-odd partition problem

texts:
Motivated by Hardness proof of EVEN-ODD PARTITION post I came up with a string version.

String even-odd partition

INPUT: $(x_{1,0},x_{1,1}),\dots,(x_{n,0},x_{n,1})$, i.e.,  $n$ pairs of strings over $\{0,1\}^*$

QUESTION: Does there exist $(b_1,\dots,b_n) \in \{0,1\}^n$ such that $x_{1,b_1} \cdots x_{n,b_n} = x_{1,1-b_1} \cdots x_{n,1-b_n}$?

Equivalently: for each pair, we can either swap the two strings or leave them alone; then we want to know if the concatenation of the left part of each pair can equal the concatenation of the right part of each pair.

Or, in other words, we are trying to partition every pair into two strings to obtain concatenated strings $W_{even} $ and $W_{odd}$  such that $W_{even}= W_{odd}$, where exactly one string from each pair goes to $W_{even}$  and the other goes to $W_{odd}$.  The selected strings have to stay in the same order they appear in the input.

It feels like this should be NP-complete by a reduction from even-partition problem but I can't find an explicit reduction; I am having difficulty in representing integers by appropriate strings.

  Is there a simple reduction to prove the NP-completeness of this string variant?

This was posted first on CS StackExchange.


texts: Data structures lower bounds on Turing machines

texts:
Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ?

I guess that people are mostly interested in models with random access, but I still wonder.


texts: A natural result that relativized to a random oracle is true with probability 1/2

texts:
There are several well known results regarding random oracles, e.g.

  $\mathsf{IP}^A \neq \mathsf{PSpace}^A$ for almost all oracles.

Are there any known natural examples where a similar statement is both true and false for significant fractions of the random oracles (e.g. it is true with probability $1/2$)?


texts:
Labelled Markov Processes (LMP) seem to be a generalization of Probabilistic Automata (PA) studied by Segala to the case of the general state space. Namely, any LMP is given by a be a finite set of labels $A$, a measurable state space $(X,\mathscr B(X))$ and substochastic kernels
$$
  \forall a\in A,\;\tau_a:X\times \mathscr B(X)\to [0,1].
$$
In case $X$ is finite and $\mathscr B(X) = 2^X$, we obtain simply a PA.

The behavior of the PA is clear to me: it is given by trace distributions over the sequences of labels - e.g. in Section 3 here. I would expect the very same definition of the behavior for LMP, but I have never seen it defined formally anywhere. I would appreciate if you can hint upon a source describing the behaviour of a LMP.

Updated: after a short discussion, I have to clarify some details. I am familiar with measure-theoretical approach to probability and stochastic processes, and I think that behavioral semantics of PA extends directly to LMP modulo dealing with Borel or universally measurable transition kernels to characterize an adversary. However, I am not sure whether this is a possible way to define a behavior of LMP, or it is the intended one. For example, it may perhaps be described in the PhD thesis of J. Desharnais (which I do not have an access to).


texts: Pi-type over a list in dependent type theory

texts:
In a formalization I need to create an inductive type which has a term for each element in a list, something like this (I'll use Agda in the following, but everything here is standard dependent type theory):
data DataType : Type where
  inj : (xs : List A) → (x : {! xs !}) → DataType

Of course, we cannot have a Pi type over x : xs in the middle since xs is a term and not a type, so we cannot quantify over it.
We can use singletons to get an n-tuple from a list as follows:
Singleton : (x : A) → Type
Singleton x = Σ[ y ∈ A ] (y ≡ x)

list→type : List A → Type
list→type [] = ⊥
list→type (x ∷ []) = Singleton x
list→type (x ∷ y ∷ xs) = Singleton x × list→type (y ∷ xs)

That way a list 1 ∷ 2 ∷ 3 ∷ [] is turned into the tuple (s1, s2, s3), from which can recover the numbers in the list. However, this tuple is still just one term, so we will only have a single inj (s1, s2, s3) in our data type above when using list→type xs in the Pi type above.
How can we get a different inhabitant in DataType for each element of the list? Is there a standard way to deal with that? Or do I fundamentally misunderstand something? It's of course a bit awkward to mix a data structure understanding of "collection" with the basic doctrine of regarding types as collections (with explicit term constructors), but it still should be possible to reconcile both understandings I hope.


texts: P vs. NP in a logic with a random oracle

texts:
Choose a random oracle $f : \{0,1\}^\ast \to \{0,1\}$, and define the logic $ZFC^f$ by adding a fresh symbol $g$, an axiom that $g$ has the correct type, and one axiom $g(s) = f(s)$ for each $s \in \{0,1\}^\ast$.  This is a countably infinite set of axioms since $f$ is not a symbol in $ZFC^f$.

Within $ZFC^f$ we can define $g$-oracle Turing machines in the standard way, for example by using a second tape for the input to $g$ and letting the machine branch on the value of $g$ on the second tape.  We then have the complexity classes $P^g$, $NP^g$, etc.  Since $f$ was chosen at random in the metalogic, $P^g \ne NP^g$ is true with probability 1.

Question 1: Is $P^g = NP^g$ independent over $ZFC^f$?

The proof seems immediate: any finite proof in $ZFC^f$ can interrogate at most finitely many values of $g$.  However, I am not confident the definitions are sensible.

Question 2: Is there a good reference exploring this type of logic + random oracle construction?


texts: Channel coding results using Kolmogorov complexity

texts: Usually Shannon entropy is used to prove channel coding results. Even for source-channel separation results shannon entropy is used. Given the equivalence between Shannon (global) vs Kolmogorov (local) notions of information, has there been a study to utilize Kolmogorov complexity for these results (or atleast to replace the source coding part in source channel separation results)?


texts:
Consider the following problem:

Input: An integer $n$ and a subset $S \subseteq \{0...n-1\}$ in some representation.

Output: The encoding of some kind of automaton (say, a Turing machine) which enumerates this set.

If you want the shortest machine, then this is a witness variant of determining the Kolmogorov complexity of the input. This is intractable of course.

But now suppose I make the following changes/relaxations to the problem:

It's sufficient to enumerate a set $S'$ such that $S \subseteq S' \subseteq \{0...n-1\}$, of size at most $\delta n$.
Instead of an enumeration, I want a machine which is given $i$ and outputs the $i$-th element in $S'$.
I don't really need the smallest machine. I only need its size to be independent on $n$, and I want it to be fast - taking $T(n)$ time.

So my parameters are $\delta$ and $T(n)$; I need to devise an algorithm which gives a good tradeoff between them, as a factor of $n$, in the worst-case (i.e. for all values of $S$). And - no asymptotics for that tradeoff! No  monstrous constants hidden in $O(\cdot)$ notations, this needs to work in the "real" world.

Now, of course I don't expect people here to solve this problem for me. What I was hoping is that this, or similar, problems have been studied in the TCS community, enough for people to provide suggested directions/pointers/inspirations for this.

Notes:

A variant of the above which is also of interest is when $S'$ can also discard some elements of $S$, say, $\varepsilon |S|$ of them.
If you want some motivation, think: "Dictionary-like compression scheme selection mechanism".


texts: What happens if we improve the time hierarchy theorems?

texts:
In a nutshell, the time hierarchy theorems say that a Turing machine can solve more problems if it has more time for computation. In detail for deterministic TM and time-constructable functions $f,g$ with $f(n) \log f(n) = o(g(n))$ it is
$$ DTIME(f(n)) \subsetneq DTIME(g(n))$$
and for nondeterministic TM and time-constructable functions $f,g$ with $f(n+1)=o(g(n))$ it is
$$ NTIME(f(n)) \subsetneq NTIME(g(n)).$$
There are a lot of (old and current) results which use the time hierarchy theorems to prove lower bounds. Here are my questions:

What happens if we can prove a better
result for the deterministic or nondeterministic case?
If we can prove that there is a gap
between the deterministic time
hierarchy and the nondeterministic
time hierarchy, does this imply $P \neq
   NP$?


texts: Unary parametricity vs. binary parametricity

texts:
I've recently become quite interested in parametricity after seeing Bernardy and Moulin's 2012 LICS paper ( https://dl.acm.org/citation.cfm?id=2359499). In this paper, they internalize unary parametricity in a pure type system with dependent types and hint at how you can extend the construction to arbitrary arities.

I've only seen binary parametricity defined before. My question is: what is an example of an interesting theorem that can be proved using binary parametricity, but not with unary parametricity? It would also be interesting to see an example of a theorem provable with tertiary parametricity, but not with binary (although I've seen evidence that n-parametricity is equivalent for n >= 2: see http://www.sato.kuis.kyoto-u.ac.jp/~takeuti/art/par-tlca.ps.gz)


texts: The largest connected component of a random subgraph

texts:
Let a graph on $|V|$ vertices and $|E|$ edges. We randomly sample $s= c \cdot \frac{|V|}{{d_{\text{av}}}}$ vertices, without replacement, where $d_{\text{av}}$ is the average degree of $G$ and $c$ is some big constant. Let $G'$ be the subgraph induced by these $s$ vertices.

What is the size of the largest connected component of $G'$?

I'm tempted to say $O(\log(s))$, under a mild assumption like |E| = o(|V|^2). Some intuition comes from the fact that the probability of 2 vertices in $G'$ being friends is $\sim \frac{E}{V^2} = \frac{{d_{\text{av}}}}{|V|}=1/s$; if $G'$ was an Erdős–Rényi then, it would be below the giant component threshold. Obviously, the edges in $G'$ are not independent, so the result does not immediately hold.

Examples where the O(log(s)) claim is true: star, cycle graph, union of cliques of size o(n).

Any ideas?


texts:
As a mild follow-up to this question on alphabet sizes, let me ask about the other part of the natural numbers, i.e. $\le 2$.

Clearly everyone knows about problems over a binary alphabet. Unary, on the other hand, is most commonly used in input encodings for a problem to a Turing machine (at least, that's the use I'm interested in). But, are there any good examples of problems where the input is encoded with an explicit mix of the two, perhaps in order to make a particular complexity argument? Admittedly, since many classes (like NP) are closed under concatenation, you could just append one such problem's input to another -- but I'm particularly interested in problems where the "natural" form of the problem requires a mix.

What are some problems where their standard input to a Turing machine is a mix of unary and binary encoding? (Bonus points if the only-unary or only-binary encoded versions are meaningful as well!)

P.S. I'm less interested in broad "classes of problems" (not to be confused with complexity classes), such as "any crypto problem" where there is frequently a security parameter of $1^n$ and the rest of the problem is in binary, or as Tsuyoshi points out, "any FPTAS". I'm very interested in specific computational problems that require both a unary and a binary component in the input for the problem to be meaningful (and perhaps, to be meaningful at all).


texts: At most how many satisfying assignments are there for a 2SAT with n variables?

texts:
It is not obvious but easy to see that, for some fixed set of satisfying assignments, there is no 2CNF that can satisfy the set of satisfying assignment exactly, when I discover this, I wonder at most how many satisfying assignments are there for a 2CNF with n variables.

Here, all variables must appear in the formula, the formulas I mean here doesn't include such kind of 2CNF:

there are n-r variables appearing in formula as positive or negative literals or both. (n>r)
there are r variables not appearing in formula as any form. (r>1)

If n = 1, that is trivially 1; like formula $(x_1 \vee x_1)$, if we don't allow such clause containing two same literals, just $(x_1 )$ is still a 2CNF, but not exact 2CNF.

else if n = 2, that is 3; like formula $(x_1 \vee x_2)$

else if n = 3, that is 5; like formula $(x_1 \vee x_2)\wedge({x}_1 \vee x_3)$

else if n = 4, that is 9; like formula $(x_1 \vee x_2)\wedge({x}_1 \vee x_3) \wedge({x}_1 \vee x_4)$

for other n?

well, for the form $(x_1 \vee x_2)\wedge({x}_1 \vee x_3) \wedge({x}_1 \vee x_4)...\wedge({x}_1 \vee x_n)$, it can be obtained that there are $(2^{n-1}+1)$ satisfying assignments.

Will the number be any larger?


texts:
It is known that $\textbf{MA}_{\textbf{EXP}} \not\subset \textbf{P/poly}$. Is it known any explicit language from $\textbf{MA}_{\textbf{EXP}}$ that does not belongs to $\textbf{P/poly}$?

(An example of explicit language is any EXPSPACE-complete language but presumably $\textbf{EXPSPACE} \not=\textbf{MA}_{\textbf{EXP}}$).


texts:
The SODA '15 submission rules state that "The submission, excluding title page, bibliography and appendix, must not exceed 10 pages."

However, the website does not define "title page." Does "title page" simply mean "the page with the title and abstract," or does it mean some sort of cover page?


texts: Efficient Enumeration and Parameterization of Graphs Deriving from Delaunay Tesselations in 3D

texts:
This is a repost from a question on Computational Science. No proper answer was found and it was suggested that TCS might be able to answer. So here it goes:

Is there an algorithm that enumerates the graphs that correspond to some Delaunay tesselation of points in 3D?

If so, is there an efficient parameterization of geometries that correspond to any "Delaunay graph"?

More precisely:
Let $G_N$ be the set of graphs with $N$ vertices.
Let $D: \mathbb{R}^{N\times 3} \to G_N$ be a map of $N$ points in $\mathbb{R}^3$ to a graph corresponding to a Delaunay tesselation of said points in 3D.

How do I enumerate $D(\mathbb{R}^{N\times 3})$ (efficiently)?

Further, given a graph $g\in D(\mathbb{R}^{N\times 3})$, how can I parameterize $D^{-1}(g)$ (efficiently)?

$D$ should be invariant under translations and rotations of $\mathbb{R}^3$, so I'm more interested in the remaining degrees of freedom.

For example in 2D, 4 points may generate 2 Delaunay graphs.

$$ \begin{matrix}
1 & - & 2 & - & 3 \\
&\diagdown &| & \diagup\\
&&4
\end{matrix}\mbox{ and }
\begin{matrix}
1 & - & 2\\
|& \times & |\\
3 & - & 4
\end{matrix}$$

The first of these graphs may be parameterized by any position of points 1, 2 and 4, i.e., $\mathbb{R}^{3\times 3}$, while point 3 would be any point $x_3(r,\theta)=c(x_1,x_2,x_4) + r\left(\begin{array}{c} \cos(\theta) \\ \sin(\theta)\end{array}\right)$ where $r$ is larger than the radius of the circle circumscribing points 1, 2, and 4 centered at $c(x_1,x_2,x_4)$ and $x_i$ is the position of point $i$.


texts: Linear Function Representation of Neural Network

texts:
I have trained a neural network using MATLAB and am ready to deploy it into my software. Right now, I include it in my software by programming the structure of the neural network and the connection weights and doing some matrix multiplication.

But there has to be a better way to do this: neural networks are basically linear separators. This means that it should be possible to model the outputs as some linear function of the inputs.

So here's the question: given the structure of a neural network and the connection weights after training, how would I come up with the correct linear function of the inputs that models the functionality of the network?


texts: Encoding of binary trees as a regular language?

texts:
There are many ways of representing binary trees as strings.  For example, I could encode a tree as either nil or a pair of trees, such as

(nil, ((nil, nil), nil))

This representation has a simple CFG:

S -> nil
S -> (S, S)

My question is whether there exists some representation of binary trees as a string such that the set of all binary tree encodings is a regular language.  I have a suspicion that this cannot be done due to some pumping-lemma-based argument, but I have no idea how to go about showing this.

Does such a representation exist?


texts: Constructive proof of the Halting Problem

texts:
Does there exist any constructive (indeed, computable) proof of the Halting Problem? All the ones I have encountered make use of proof by contradiction.

As an aside, some proofs I have encountered make use of Cantor's diagonal argument, but this seems to be purely extraneous (e.g. the proof in Sipser).


texts: $SAC^i$ is the class of decision problems solvable by a family of $O({\log}^i{n})$ depth circuits with unbounded-fanin OR and bounded-fanin AND gates. Negations are only allowed at the input level. It is known that $SAC^i$ for $i \geq 1$ is closed under complement and $SAC^0$ is not. Also, $SAC^1 = LogCFL$ and hence has a machine characterization, since LogCFL is the set of languages accepted by an $O({\log}n)$ space bounded and polynomial time bounded auxiliary PDA. Are there similar machine characterizations of $SAC^i$ for $i \geq 2$ ?


texts: Two extremely naive questions about the Kronecker problem from Geometric Complexity Theory

texts:
I was reading the GCT IV paper (http://arxiv.org/pdf/cs/0703110v4.pdf) and while the representation theory is clear enough (by which I do not mean to say 'easy'!) the relation to complexity theory as stated in the introduction confuses me.

I quote:

  The flip suggests that separating the classes P and NP will require solving difficult positivity problems in algebraic geometry and representation theory. A central positivity problem arising here is the following
  fundamental problem in the representation theory of the symmetric group.

  Let $S_r$ denote the symmetric group on $r$ letters and let $M_\nu$ denote the $S_r$-irreducible corresponding to the partition $\nu$. Given three partitions λ, µ, ν of r, the Kronecker coefficient $g_{\lambda \mu \nu}$ is defined to be the multiplicity of $M_\nu$ in the tensor product $M_\lambda \otimes M_\mu$. (...)

  Problem 1.1 (Kronecker problem). Find a positive combinatorial formula for the Kronecker coefficients $g_{\lambda \mu \nu}$.

  There are two precise related problems in complexity theory that arise in the flip: (1) find a (positive) #P formula for Kronecker coefficients, and harder, (2) find a polynomial time algorithm to determine whether a Kronecker coefficient is zero.

My questions are:

A) When they say polynomial time in question (2), what is the input size here? I found it easy to find a $O(d^3)$ algorithm where $d$ is the product of the dimensions of the vector spaces $M_\lambda, M_\mu, M_\nu$, so apparently they are thinking of something smaller than that. But what? The number $r$? How do we know that the dimensions are not polynomial in $r$? (It seems to me they are polynomial in $r$ but with an exponent that depends on the number of elements in the partition, so maybe that doesn't count as truly polynomial?)

B) How can question (2) be harder than question (1) when, obviously, any solution to question (1) gives you a solution to question (2). (At least I find it hard to imagine a world where an algorithm to compute a number doesn't give you an algortithm to tell if that number is zero.) The $P$ in $\#P$ also means 'polynomial time', right?

It looks like I am missing something really obvious here but what?


texts: Is finding Logspace reductions harder than P reductions?

texts: Motivated by Shor's answer related to different notions of NP-completeness, I am looking for a problem that is NP-complete under P reductions but not known to be NP-complete under Logspace reductions (preferably for a long time). Also, Is finding Logspace reductions between NP-complete problems harder than finding P reductions?


texts: Which problems in graph theory can be stated as quadratic programs?

texts:
There seem to be many very interesting problems in graph theory that can be written in the form of maximizing/minimizing a quadratic form on either the Adjacency ${\bf A}$ or the Laplacian matrix ${\bf L}$ of a graph. Examples are:

1) the max-cut problem is equivalent to finding a sign vector that maximizes a quadratic form
$$\max_{x_i\in\{\pm1\}} \sum_{i,j}A_{i,j}(1- x_ix_j),$$
2) The densest $k$-subgraph is equivalent to
$$\max_{x_i\in\{0,1/\sqrt{k}\},\;{\bf 1}^T{\bf x}=1} {\bf x}^T{\bf A}{\bf x}$$
3) The Grothendieck constant involves maximizing the adjacency's quadratic form over sign vectors
$$\max_{x_i\in\{\pm1\}} {\bf x}^T{\bf A}{\bf x},$$
4) The spectral profile of a graph
$$\Lambda(\delta) = \min_{d(\text{supp}({\bf x}))\le \delta} \frac{{\bf x}^T{\bf L}{\bf x}}{\sum_i \text{deg}(\text{vertex}_i) x_i^2},$$
where $d(\text{supp}(x))$ is the fraction of edges incident on vertices within the support of vector ${\bf x}$

( http://www.eecs.berkeley.edu/~prasad/Files/spectralprofile.pdf )

4+$\epsilon$) Anything involving the computation of an adjacency/laplacian eigenvalue.

${\bf Q}$: Which other problems in graph theory can be expressed as maximizing/minimizing a quadratic form?


texts: Eliminating clauses from a CNF formula based on their unsatisfying truth assignments being covered by some other clause

texts:
We are given a Boolean formula in Conjunctive Normal Form (CNF) with $n$ variables and $m$ clauses, where we do not allow repetition of clauses in a given formula and we do not allow repetition of variables in a given clause. Then it is well known that we can have up to $3^n-1$ distinct clauses.

What I would like to know is the complexity of eliminating clauses where their unsatisfying assignments are already covered by some other clause. For example, given the following CNF formula $ \{ (a,b,c,d), (a,b,c,\bar{d}), (a,\bar{b},c,d), (a,b,c), (a,b,d), (b,c,d), (c,d) \}.$ After we eliminate the clauses where their unsatisfying truth assignments are already covered by some other clause we get following CNF formula $\{ (a,b,c), (a,b,d), (c,d) \}.$ How fast can this be done for an arbitrary formula? Could it be done in polynomial time in terms of the length of the input?


texts: Subgraph containing all nodes and edges that are part of length-limited simple s-t paths in a digraph

texts:
Note: I posted a similar question regarding undirected graph.

Given

A digraph $G$ with no multiple-edges or loops
A source node $s$
A target node $t$
Maximal path length $l$

I am looking for $G'$ - A subgraph of $G$ that contains any node and any edge in $G$ (and only those), that are part of at least one simple path from $s$ to $t$ with length $\leq l$.

Note that I don't need to enumerate the paths.


texts: Boolean function with specific ОBDD representation

texts:
I am looking for a class of boolean functions on $n$ variables with the following property:

When represented by read twice palindromic ordered bdd (i.e. the order is 1..n n..1) the size of the OBDD is polynomial in $n$
Read once polynomial size OBDD doesn't exist for the boolean function.

I did some experiments with the CUDD package to no success.

Any ideas how to find an instance of such function?

(There is a chance such functions don't exist but I would not bet much money on this).


texts: Formalization of simulation for Turing machines

texts:
Right now I am trying to understand the concept of simulation in theoretical computer science, focussing on Universal Turing machines. All textbooks that I looked into only explain examples. They introduce one particular Universal Turing Machine and explain how it simulates other Turing Machines. But does there exist a rigorous theory/formalization behind simulations of Turing machines? Particular questions that I care about:

Given two Turing machines T and T', when can it be said that T simulates T'?
Is there a theory of "shortcuts" in simulations of Turing machines?
A random google search revealed the notion of Simulation preorder, see e.g.:
https://en.wikipedia.org/wiki/Simulation_preorder
Does something similar exist for Turing machines?


texts: Which definition of asymptotic growth-rate should we teach?

texts:
When we follow the standard textbooks, or tradition, most of us teach the following definition of big-Oh notation in the first few lectures of an algorithms class:
$$
f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n)).
$$
Perhaps we even give the whole list with all its quantifiers:

$f = o(g) \mbox{ iff } (\forall c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
$f = O(g) \mbox{ iff } (\exists c > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \leq c \cdot g(n))$
$f = \Theta(g) \mbox{ iff } (\exists c > 0)(\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(d \cdot g(n) \leq f(n) \leq c \cdot g(n))$
$f = \Omega(g) \mbox{ iff } (\exists d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$
$f = \omega(g) \mbox{ iff } (\forall d > 0)(\exists n_0 \geq 0)(\forall n \geq n_0)(f(n) \geq d \cdot g(n))$.

However, since these definitions are not so easy to work with when it comes to proving even simple things such as $5 n \log^4 n + \sqrt{n\log n} = o(n^{10/9})$, most of us quickly move to introduce the "trick of the limit":

$f = o(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is $0$,
$f = O(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is not $+\infty$,
$f = \Theta(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is neither $0$ nor $+\infty$,
$f = \Omega(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is not $0$,
$f = \omega(g)$ if $\lim_{n \rightarrow \infty} f(n)/g(n)$ exists and is $+\infty$.

My question is:

Would it be a big loss for teaching an undergraduate algorithms class to take the limit conditions as the definitions of $o$, $O$, $\Theta$, $\Omega$, and $\omega$? That's what we all end-up using anyway and it seems pretty clear to me that skipping the quantifier definitions makes everybody's life easier.

I would be interested to know if you have encountered some convincing natural case where the standard $c,n_0$-definitions are actually required, and if not, whether you have a convincing argument to keep the standard $c,n_0$-definitions upfront anyway.


texts: What is the class of the languages recognized by PCREs?

texts: I have been considering building a tool that would convert regexes between the various syntaxes (BRE, ERE, PCRE). It is obvious that PCREs are too strong for the is-regular problem to be decidable, which would make the PCRE -> BRE / ERE conversion impossible in the general case, but it is clearly possible to recognise a subclass of regular PCREs via static analysis. I am curious if any research has been conducted and published in this regard and whether the class of languages recognized by PCREs has been formally described in relation to an existing hierarchy (Chomsky od otherwise).


texts: Stable Marriage with incomplete lists and ties - NP-hardness

texts:
According to [1] finding a weakly stable matching in a stable marriage (or SM) instance with incomplete lists and ties is NP-Hard.

According to [2] a weakly stable matching in a hospital-residents (or HR) instance with ties always exists and one can be found by arbitrarily breaking the ties and applying one of the known algorithms for the HR problem.

Also HR with ties is a generalization of SM with incomplete lists and ties.

Isn't there a conflict here?

[1] K. Iwama, D. Manlove, S. Miyazaki and Y. Morita. Stable Marriage with Incomplete Lists and Ties. Automata, Languages and Programming, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 1999

[2] R. W. Irving, D. F. Manlove, and S. Scott. The Hospitals/Residents Problem with Ties. Algorithm Theory - SWAT 2000. Lecture Notes in Computer Science. Springer Berlin / Heidelberg

[3] V. Bansal , A. Agrawal , V. S. Malhotra. Polynomial time algorithm for an optimal stable assignment with multiple partners. Theoretical Computer Science 379 (2007) 317–328

[4] D.F. Manlove, R.W. Irving, K. Iwama, S. Miyazaki, and Y. Morita. Hard variants of stable marriage.Theoretical Computer Science 276(1-2):261-279.


texts: Universal approximation theorem of second order

texts:
The universal approximation theorem (https://en.wikipedia.org/wiki/Universal_approximation_theorem)
informally states that up to several conditions, any function can be approximated by a shallow neural network up to any degree.

I was wondering if there is a version of this theorem that states the same for the gradients of the functions, i.e, for any function there is a (shallow or not shallow) neural network that approximates it and its gradient approximates the gradient of the original function (up to any degree)?


texts: Finding number of cycles of length $k$ in a graph

texts:
We have $f(k) n^3$ time algorithm to determine whether a graph $G$ has a cycle of length exactly $k$.
How can we find how many such $k$-cycles are present in $G$ using the same or any other algorithm.


texts:
The SODA 2008 Ailon-Liberty paper on fast Johnson-Lindenstrauss transforms uses a "dual BCH code of design distance 5" as part of the construction. They cite the
MacWilliams-Sloane book on error-correcting codes as the source for how to construct these codes, but my initial wading through the book doesn't appear to yield the answer (there are dual codes and BCH codes, but...)

Is there an easy way to describe how to construct such a matrix, for general matrix dimensions $m \times d$ ?


texts:
I am reading the following paper

Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson ,"Proof Complexity Lower Bounds from Algebraic Circuit Complexity", 2016.

IPS is defined as follows:

  (Ideal Proof System (IPS), Grochow-Pitassi [GP14]). Let $f_1(x), \ldots , f_m(x) ∈ F[x_1, \ldots , x_n]$ be a system of polynomials. An IPS refutation for showing that the polynomials $\{f_j\}_j$ have no common solution in $\{0, 1\}^n$ is an algebraic circuit $C(x, y, z) ∈ F[x, y_1, \ldots , y_m, z_1, \ldots , z_n]$
  such that

  $C(x, 0, 0) = 0$.
  $C(x, f_1(x), \ldots , f_m(x), x^2_1 − x_1, . . . , x^2_n − x_n) = 1$.

Then:

  We then consider the subset-sum axioms, previously considered by Impagliazzo, Pudlak, and Sgall [IPS99], and show that they can be refuted in polynomial size by the C-IPS_LIN proof
  system where C is either the class of roABPs, or the class of multilinear formulas.

The subset-sum axiom is defined as follows:

  That is, we give such refutations for whenever the polynomial $\sum
_i α_ix_i − β$ is unsatisfiable over the boolean cube $\{0, 1\}^n$, where the size of the refutation is polynomial in the size of the set $A := \{\sum_i α_ix_i : x ∈\{0, 1\}^n\}$.

They have given a polynomial size refutation for the subset-sum axiom. Polynomial-size proofs for the complement of subset-sum should imply
NP=coNP, doesn't it? What am I missing?


texts: What is known about multi-prover interactive proofs with short messages?

texts:
Beigi, Shor and Watrous have a very nice paper on the power of quantum interactive proofs with short messages. They consider three variants of 'short messages', and the specific one I care about is their second variant where any number of messages can be sent, but the total message length must be logarithmic. In particular they show that such interactive proof systems have the expressive power of BQP.

What I want to know is whether there are analogous results for the multi-prover setting, either for classical or quantum verifiers. Are any non-trivial complexity results known for multi-prover interactive proofs where the total length of all messages is restricted to be logarithmic in the problem size?


texts: An upper bound over the number of bipolar orientations for a regular graph

texts:
Given a $k$-regular graph $G$, the number of acyclic orientations $Acy(G)$ is $\chi(-1)$ where $\chi$ is the chromatic polynomial of $G$. How many bipolar orientations does $G$ have?

Is there an upper bound for it? I assume it should be exponentially lower than $Acy(G)$ but didn't succeed in finding a known result connecting these two numbers.


texts: number of iterations of this algorithm (upper bound)

texts:
Let $(A, dist)$ be a finite metric space. Consider the following "$p$-center problem": given a positive integer $p$,
find a subset $B$of $A$ such that $|B| = p$ and which minimizes the number $\max_{a \in A}\min_{b \in B}{dist(a, b)}$.
Assume that we have an oracle $f$ for this problem, i.e., which finds such optimal subset $B = f((A, dist), p)$ for any given finite metric space $(A, dist)$ and positive integer $p$.

Consider now the following algorithm, which takes in input a finite metric space $(A, dist)$, a positive integer $p \geq 2$ and an element $a \in A$:

1) Set $B = f((A, dist), p))$;

2) If $a \in B$ then return. Otherwise goto 3;

3) Select an element $b_* \in B$ which is one of the closest to $a$ with respect to $dist$;

4) Set $A' = \{a \in A \mid \forall b \in B, dist(a, b_*) \leq dist(a, b)\} \setminus \{b_*\}$;

5) Set $A = A'$ and goto 1);

Intuitively, this algorithm seeks for a given point $a \in A$ by solving iteratively the $p$-center problem by reducing the search space $A$ at each step.
It is useful, e.g., in Product Configuration, when a user wants to reach her preferred product, but doesn't want to browse the (possibly large) catalog $A$.
Step 1 finds a "well-distributed" set $B$ of $p$ elements among the set $A$ (using $f$). If one of the points in $B$ is the preferred one, then the algorithm stops in Step 2.
Otherwise, the (rational) user just picks the element $b_*$ from $B$ which is the closest to her ideal one; this is automatically done in Step 3.
In Step 4 and Step 5, one removes the element $b_*$ from the set $A$, and one further reduces $A$ only to its elements which are closer to $b_*$ than to any other element from $B$. The algorithm iterates the process on the restricted set $A$.

It is easy to see that the algorithm terminates at most after $|A|$ iterations, since one element at least ($b_*$) is removed from it at each iteration.

The question is: can we have a tighter upper bound of number of iterations? Like, a logarithmic number of iterations in the size of $A$ or the diameter of $A$.

I know that in the case where for some constant number $\alpha$, if we have $\forall a_1, a_2 \in A$, $dist(a_1, a_2) = \alpha$, then the number of iterations is not logarithmic but linear in the size of $|A|$, but this is a very specific case. One can make some assumptions like, e.g., the number of elements in $A$ which have the same pairwise distance is bounded by some number $k$.


texts: Preprocessing Sparse, Directed Non-Planar Graphs for Faster Shortest Path

texts:
I'm trying to preprocess a very large and sparse directed graph in order to do faster shortest path searches.  The vertices have no natural distance function, and the edges are unweighted.

One thought I had was to try and use a force directed graph layout algorithm to project the graph into space.  This way I could use cartesian distance for ASTAR and maybe get some improvements.

Constraint: There are so many vertices that any solution requiring a data with $O(n^2)$ space isn't viable.  However $O(n)$ space is fine, which is what made me think about assigning spacial coordinates to each vertex and doing distance calculations.

Any thoughts on this idea or others?

Thanks,

- Dan

UPDATE: For anyone interested, here's a paper that discusses my initial idea exactly: http://www.siam.org/meetings/alenex05/papers/02d.wagner.pdf


texts: On approx-preserving P- and A-reducibilities

texts:
Let $X$ and $Y$ be two NPO problems.
Let $(f,g)$ be a reduction between $X$ and $Y$,
in particular, assume that $(f,g)$ is both P-reduction and A-reduction,
i.e.,

there exist two poly-time  computable functions $c_1,c_2 :(1, +\infty)\cap \mathbb{Q}\mapsto (1, +\infty)\cap \mathbb{Q}$ such that:

$R_B(f(x),y)\leq r \Rightarrow R_A(x, g(x,y))\leq c_2(r)$ (A-reduction)

and

$R_B(f(x),y)\leq c_1(r) \Rightarrow R_A(x, g(x,y))\leq r$ (P-reduction)

Then, can you prove that $c_1$ is invertible and that $c_1=c_2^{-1}$ is always the case ?

(I am reading a paper which asserts that this is always the case, but I don't see it true...)


texts: Why can't we have superlinear bounds on Boolean circuit size for an explicit function?

texts:
I am interested about the minimal size (number of gates) of a family of circuits (with negation) over a complete Boolean basis (with fanin 2) that computes some explicit Boolean function. (In other words, I want results that apply for a specific function, not diagonalization, counting, or non-constructive arguments). I call $n$ the number of inputs.

Section 1.5.2 of Boolean Function Complexity by Stasys Jukna (2011) says that the best such lower bound currently known is in $5n - \text{o}(n)$, from Iwama and Morizumi in 2002. This is very surprising, because, as Shannon proved in 1949 by a counting argument, most Boolean functions require exponential-size circuits.

Is the $5n - \text{o}(n)$ result still the best known? Is there any reason why proving a super-linear lower bound on the circuit size of an explicit function seems out of reach? In particular, do we know that solving this would close long-standing open problems in complexity theory as well?


texts:
There's a computability theory exercise that had me stuck for a long time. I have the language

L={ M | there exists a reduction from HP to L(M) }

I managed to prove it's not in R with a reduction from HP, but I can't figure out if it's in RE (or rather, I suspect it must not be in RE but can't prove it).

I'm not necessarily looking for an actual solution, but a clear enough hint, since it did elude me for a while now.

EDIT: M is a Turing machine. L(M)={x | M accepts x}. HP is the Halting Problem. RE is the Recursively Enumerable class of languages.


texts: Updating set of lists dependent upon a few indices

texts:
I'm curious about a data structure for a set of "valid lists", where you have a set of lists of length $i$ $S_i$, have a list $L$ of possible items to append, and a boolean function $f$, and wish to create a set $S_{i+1} = \{ l+a| l \in S_i a \in L \land f(l+a)=1 \} $. ($l+a$ represents appending the item $a$ to $l$) Specificlaly, I'm curious when $f(l+a)$ depends on a small number of indices, $I$, meaning $\forall l_1, l_2 \in S_i, l_1[k] = l_2[k] \forall k \in I \implies f(l_1+a) = f(l_2+a)$. I think it's better explained through an example like graph coloring.

Say you have a graph $G$ that you want to color. One way to do this is to make a list of its vertices $L = v_1,v_2 \dots v_n$, and keep track of set $S_i$ of valid ways to color the vertices $v_1, v_2 \dots v_i$, and update it sequentially to get $S_{i+1}$ until you reach $n$. If you had an oracle algorithm which could take a set $S$ of colorings and return the subset of $S$ of colorings $c$ such that $c(v_a) = k_1 \land c(v_b) = k_b \dots \land c(v_z) = k_z$ in polynomial time, then one could create an easy polynomial algorithm for any given $\Delta$ to determine if there exists a 3-coloring of any graph with maximal degree $\leq \Delta$. Specifically, you'd need at most $k^{deg(v_{i+1})}$ queries to check the $k$-colorings of $v_{i+1}$'s neighbors that have been colored before it.

Thus, since 3-coloring is NP-Complete, it stands to reason that no such data structure allows for such a query to be easily done in general. And this is true even with the information about which queries will be made, as it is trivial to get this information in the case of coloring. Yet, at the same time, there seems like a better way to do this than brute force, going through each list one by one.

For example, say we only made queries about the last $x$ items of our lists, $l \in S_i$, with each item having at most $y$ possible values. Then, we can make rooted tree, where the edges from the root represent the possible values of $l[-1]$, and the children represent the possible values of $l[-2]$ given the path to it, et cetera. Basically, to create the valid lists of length $i+1$, for each of the possible values we could append, we make a copy of this tree, prune according to which paths are compatible with this.

Is there a name for this kind of query? If we know $I_i$, the list of indices which matter at step $i$, can do queries with faster complexity than brute force ($O(|S|)$)? What about the case when $|I_i|$ is bounded, even by one?


texts: Intersection of N rectangles and M points

texts: There are N rectangles parallel to X and Y axis and they do not overlap, also there are M points. For each point find an enclosing rectangle (or absence of one). Total runtime complexity should be not more than O((N+M) * (log(N+M))2).


texts: Research on call-site based type inference?

texts:
I'm trying to learn more about whole-program type checking and type inferencing systems that use information from function call sites to compute type information (in addition to the standard approach of using the function body). For example, such an algorithm might use a function call like foo(1) to infer that the function in foo takes integer arguments. Obviously this would complicate inference a lot and make the check non-modular.

Anyway, I haven't had much luck finding any research on this approach, probably because I don't know the correct terminology to describe what I'm talking about. Any pointers?


texts: Is there an alternative technique to define computable functions other than their definition on natural numbers?

texts:
I am not completely sure that why computable functions is defined as a subset of all functions from/to Natural Numbers, but as far as I know, computation comes from real (physical) world so instructions, inputs and outputs should be finite (intuitively, because a human or machine can not complete a task which contains infinite amount of steps, with finite steps (or finite amount of time). I wonder that can I imagine a computing model which can accept real numbers as its inputs and outputs, and a program is again a real number (or equivalently all programs in this computational model is set theoretically isomorphic to real numbers).

For example, I imagine that a one dimensional empty space (physically) and a particle in that space which moves with a constant velocity. And I see that universe as a computing machine (it takes a real number which is bigger or equal than $0$ representing the time (I think that nonnegativeness is not a problem for this situation because again nonnegative real numbers set theoretically isomorphic to real number) and it gives anothor real number which represents position of the particle). Of course this universe computes only constant slope functions ($ax+b$). This example can be extended to much bigger subsets of the all functions from $\mathbb R$ to $\mathbb R$ (I guess that it should be a proper subset because of the cardinality issues). Although, this model is an abstract model (because of the measurement issues) theoretically it looks like that it is possible.

Lets call this computational model as $\mathbb R$-computable. How can I determine which functions is $\mathbb R$-computable?


texts: Hi I am taking an undergraduate taking a course in Probabilistic checkable Proofs. I will greatly appreciate if you can suggest some good research ideas and pertaining reading for someone who is just getting started. Thanks!


texts:
I've got an idea for indexing multidimensional data. I haven't been able to find anything equivalent and am wondering if it is indeed a novel approach.

The idea is a 'stacked' B+ tree implementation where the leaf nodes contain both the dimension data and a pointer to the next dimension. Each dimension is in itself a B+ tree. It is similar to how Range Trees link/point to the next dimension. However, it is different from a Range Tree by using a B+ tree instead of a straight binary search tree.

Also, the elements in each B+ tree layer are unique and are stored with the number of records belonging to each leaf value.

I believe the search complexity would be $(\sum_{i=0}^{d-1} \log _{B} \text{card}(n^{i})) + k$.

Where $\log _{B}$ comes from the branching factor of the B+ tree, $\text{card}(n^{i})$ is the number of unique elements stored for each dimension and $d$ is the number of dimensions stored. $k$ is simply the number of elements returned.

Has anyone written / designed a similar search algorithm before?


texts: Which computational framework lies behind the Chinese “Social Credit System”?

texts:
BACKGROUND

The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness score. One can only guess that Facebook implements similar systems, albeit for different goals. What these systems have in common is that they're based on an ontology, i.e., a finite set of entity-relations, which fix the constraints on the correlations between the various entities to be scored. One could think of similar ontologies in, say, cybersecurity, whereby various entities (domains, IP addresses, e-mails, etc.) can be seeded with beliefs or initial scores of maliciousness which will then propagate to their neighbors according to particular rules. The same could be done with fault prevention or forensics in mechanical systems of interacting entities.

QUESTION

Conceptually speaking, is there a common framework that best represents these systems? I initially thought of Bayesian propagation, but it seems that it doesn't easily account for

uncertainties in the scores,
loops in the ontology graphs (how does one avoid runaway "feedback"?),
non-linearities at the nodes (since scores can be generated at a node itself based on its attributes, regardless of its neighbors). For example: Bob is a successful surgeon, Bill is a drug addict. Therefore, Bob is less likely than Bill to commit a crime---and that's independently of any inference from their respective environments.


texts: Shortest Path Algorithm for large graph but short paths

texts:
I have a graph (say, about a million vertices) where the degree of every vertex is somewhat large (about 100 000). We want to find the shortest path between two vertices -- but we know the graph is such that there is a very small upper limit (say, 10) for the shortest path length. There are no edge weights (or consider them 1).

Edit: also, I probably need to run this several times on different pairs. What data structure could be used to speed this up?


texts:
I'm interested in an computational geometry problem that's sensibly expressed as an infinite dimensional 0-1 integer program.  I'm not worried about finding an actual minimum for the objective function, any solution with isn't stupidly big will do.  It thus seems natural to apply an approximation algorithm that starts by running simplex or similar restricted to $[0,1]$.

I'd expect the solutions usually require only a few hundred dimensions, but any naive restriction of the problem space yields millions of dimensions.  As I understand it, good implementations of a linear program solver should be polynomial time in both the dimension and constraints on average cases, but nevertheless this problem chokes GLPK.  Should GLPK really choke on a million dimensions?

I've therefore started looking for less naive restrictions of the problem space, which lead me to LP-type problems. In particular, there is a claim that Clarkson's algorithm applied to linear programs are equivalent to running the simplex algorithm on the dual problem.  In what sense is this true?

I find this claim highly dubious with respect to complexity for several reasons.  First, Clarkson's algorithm does not exploit any $[0,1]$ solutions with fast average case solutions, but merely randomly chooses pivots.  Second, Clarkson's algorithm has running time worse than exponential in the dimension $O(dn + d! d^k \log n)$, which doesn't rule out polynomial time for average cases, but I haven't found that fact yet.

As an aside, any nice examples of improving a restriction of an infinite dimensional linear program over time?


texts:
Are there positions for recently graduated bachelor or masters students with a record of research to work as a researcher before committing to their PhD?

TCS has a culture of post-doc positions for recent PhD graduates to do research before attempting to apply for a faculty position. Is there a similar mechanism in place for Bachelor or Masters students to do research before applying for a Ph.D? In particular, if they have a research record already (say a few published papers). I have heard of such positions, but usually they are through your current or future supervisor. Are there other options in industry or at universities/research-centers that are more formal than these personal connections?
The goal of such a position is to work within your field or at an institute you are considering for PhD before committing to it for a longer term.
Related questions:
What are some career options for someone with a computer scientist master degree?
Deciding between different PhD programs
Edit:
After a number of answers, I'd like to emphasize the interest is in having an analogue to a post-doc in that it is purely (or almost completely) a research position. Programs where you take courses to ready for a PhD application are not interesting, since the goal is not to prepare yourself for a PhD application as much as it is to do research to make sure research is what you want to do for the long term.


texts:
Say $L_1$ and $L_2$ are computable languages.  Let $f$ be a function $L_1 \rightarrow L_2$.  Let $C$ be the statement, "if $l \subseteq L_2$ and $l$ is a computable language, the preimage $f^{-1}(l)$ is a computable language."  Does $C$ imply that $f$ is necessarily a computable function?
$C$ is similar to the topological concept of continuity; a function $g$ between topological spaces is continuous if, for each open set $S$ in the codomain of $g$, $g^{-1}(S)$ is an open set in the domain.  Here "open sets" have been replaced with "computable languages."  (Computable languages can't actually be considered open sets here, because they aren't closed under infinite union.)
The converse, "$f$ is computable implies $C$," is easily proved.  If $f$ is computable, and $l$ is a computable language that's a subset of $L_2$, then let $l' = f^{-1}(l)$.  You can computably tell whether something is in $l'$ by first mapping it through $f$ and asking if the result is in $l$.  So $l'$ must be a computable language, proving $C$.


texts: Axioms necessary for theoretical computer science

texts:
This question is inspired by a similar question about applied mathematics on mathoverflow, and that nagging thought that important questions of TCS such as P vs. NP might be independent of ZFC (or other systems). As a little background, reverse mathematics is the project of finding the axioms necessary to prove certain important theorems. In other words, we start at a set of theorems we expect to be true and try to derive the minimal set of 'natural' axioms that make them so.

I was wondering if the reverse mathematics approach has been applied to any important theorems of TCS. In particular to complexity theory. With deadlock on many open questions in TCS it seems natural to ask "what axioms have we not tried using?". Alternatively, have any important questions in TCS been shown to be independent of certain simple subsystems of second-order arithmetic?


texts: What is the difference between unification and anti-unification?

texts: I understand that in Unification we try to find a general solution to an equation between two terms, but what is anti-unification, and how is it different?


texts:
This is a problem I ran across recently while trying to schedule classes which I thought might be interesting theoretically.

Given k golfers who want to play on m courts for n weeks, is it possible to arrange groups of golfers of fixed size s (where s can possibly be smaller than m/k) such that every golfer plays on every court, and every golfer plays every week?

I'm actually trying to solve this for k=24, m=n=7, s=6

Is there an equivalent or similar problem I should look at?  Is there a way to solve this for small n so I can get my personal version done in time for the classes?


texts: understanding programming monads through diagrams

texts:
I am trying to understand better how the category definition of monad is related to the computer science definition.  nlab has a rather terse definition of Monad in terms of a bicategory.

an object $a$
an endomorphism $t: a \to a$
$2$-cells $\mu, \eta$ (multiplication and unit).

For the case of programming languages, what are the objects (0-cells), morphisms (1-cells) and 2-morphisms (2-cells)? I am guessing the object is a type and multiplication is the >>= operator (some way of putting commands in succession).  I won' t know what the endomorphism $t$ could be.

I was told that list is a monad, so is maybe and IO but I don't see the category or endomorphisms there.

Alternatively they have another definition that kind of makes sense:

  Indeed, one can define a monad on an object a of a bicategory K as just a monoid in the endomorphism category K(a,a).

Are the endomorphism the lines of code preserving the type a?

nLab goes on to say, that monads can be represented as string diagrams.  Here are

The axioms for a monad - could be represented in terms of the >>= operator in a language like Haskell - are represented in terms of string diagrams.

Then, can a computer program be represented in terms of these diagrams?

This is a sequel to a previous question:  https://cs.stackexchange.com/questions/30757/how-is-io-a-monad and can be migrated at the discretion of the admins.


texts: Translation from basic While-language to $\lambda$-calculus

texts:
Is there a simple way to translate programs written in a basic "While" language (such as Winskels Imp)?

I know about Church numerals and booleans, and I can see how if and while statements can be translated as

$$\mbox{if}~t_c~\mbox{then}~t_t~\mbox{else}~t_f\qquad\rightarrow\qquad(t_c t_t)t_f$$ and $$\mbox{while}~t_c~\mbox{do}~t_l \qquad\rightarrow\qquad \omega(\lambda r.(t_c (t_l; \omega r) I))$$ (with suitable definitions for $\omega$ and $I$).

Assignment however puzzles me.

One example translation of the following program

x := foo;
if x then t_1 else t_2

would be

$$(\lambda x.(x t_1)t_2)~foo$$

But I can't seem to find a general rule for it. How would for instance this program translate:

x := true;
y := false;
while x do
    x := y


texts: How can you state how abstract interpretation gets around Rice's Theorem succinctly?

texts: At this question, abstract interpretation has a nice in-depth look. However, I'd like someone to clearly and very precisely state how abstract interpretation takes the result of Rice's Theorem over the Turing-complete programming languages/Turing machines, and uses abstract interpretation to get similar results for decidability for non-trivial program properties; or, rather, how does abstract interpretation get around Rice's Theorem/the Halting Problem?


texts: Cover a Concave Polygon with a minimum number of rectangles

texts:
I am trying to cover a simple concave polygon with a minimum rectangles. My rectangles can be any length, but they have maximum widths, and the polygon will never have an acute angle.

I thought about trying to decompose my concave polygon into triangles that produce a set of minimumally overlapping rectangles minimally bounding each triangle and then merging those rectangles into larger ones. However, I don't think this will work for small notches in the edges of the polygon. The triangles created by the reflex vertices on those notches will create the wrong rectangles. I am looking for rectangles that will span/ignore notches.

I don't really know anything about computational geometry, so I'm not really sure on how to begin asking the question.

I found other posts that were similar, but not what I need:

split polygon into minimum amount of rectangles and triangles
Covering an arbitrary polygon with minimum number of squares
Find $k$ rectangles so that they cover the maximum number of points
Algorithm for finding the fewest rectangles to cover a set of rectangles

Some examples: Black is the input. Red is the acceptable output.

Another exmaple: The second output is prefered. However, generating both outputs and using another factor to determine preference is probably necessary and not the responsibility of this algorithm.

Polygons that mimic curves are extremely rare. In this scenario much of the area of the rectangles is wasted. However, this is acceptable because each rectangle obeys the max width constraint.

Also, I found this article to be close to what I need:

Covering with rectangular pieces by Paul Iacob, Daniela Marinescu, and Cristina Luca

Maybe a better question is "How can I identify rectangular-like portions of a concave polygon?"

Here is an image showing the desired implementation:

The green is the actual material usage. The red rectangles are the layouts. The blue is the MBR of the entire polygon. I am thinking I should try to get little MBRs and fill them in. The 2-3 green rectangles in the upper left corner that terminate into the middle of the polygon are expensive. That is what I want to minimize. The green rectangles have a min and max width and height, but I can use as many rows and columns necessary to cover a region. Again, I must minimize the number of rectangles that do not span across the input. I can also modify the shape of the green rectangle to fit in small places that is also very expensive. In other words, getting as many rectangles as possible to span as much as possible is ideal.