texts: Polynomial time approximation algorithms for machine scheduling: how many open problems are left?

texts: In 1999, Petra Schuurman and Gerhard J. Woeginger published the paper "Polynomial time approximation algorithms for machine scheduling: Ten open problems". Since then, to the best of my knowledge, reviews which would concern very the same list of problems haven't appeared. Thus it would be great and useful if each of us could make such summary on some of the ten open problems and contribute it here.


texts: Why does the Placid Platypus function grow faster than any computable function?

texts:
I came across the Placid Platypus function $PP(n)$ today, defined as the minimal number of states needed for a turing machine that prints a string of $n$ ones and halts. This function is claimed to (eventually) grow faster than any computable function, similar to the busy beaver function.

However, it is trivial to upper bound this function: consider the turing machine with $n+1$ states. It's transition function is simply (have it start in state 1):

If in state $k \leq n$, go to state $k+1$, write $1$ on the tape, then move left
If in state $n+1$, halt

This will write a string of $n$ ones, thus, $PP(n) \leq n+1$, disproving the claim that the Placid Platypus function grows faster than any computable function.

What am I missing?


texts:
There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important topic and whether it still has applications in practice. Therefore undergraduate students might have trouble in understanding the importance of automata theory and might think it is not of any practical use anymore.

Is automata theory still useful in practice?

Should it be part of undergraduate CS curriculum?


texts: equivalent way(s) of expressing P=?NP problem in linear programming?

texts:
the paper "In defense of the Simplex Algorithm's worst-case behavior" Disser/Skutella [1] was recently cited on this tcs.se site by saeed on another interesting question. the paper introduces the idea of "NP mighty" algorithms (p3 def2). it follows a fruitful/continuing line of research analyzing P$\stackrel{?}{=}$NP wrt the simplex algorithm and linear programming of which there have been other major recent advances, eg results by Pokutta et al in [2] showing that the P-time TSP polytope must have an "unlikely/restrictive" form (commentaries in Barriers to P/NP proofs, RJLipton, also Stating P$\stackrel{?}{=}$NP without TMs). question (possibly with multiple leading answers):

  the Disser/Skutella paper has closely related ideas but does not seem to explicitly reformulate the P$\stackrel{?}{=}$NP question. what is an equivalent way to state/study it in their introduced schema/framework of "NP Mighty" algorithms? what is a/the basic open problem in simplex/linear programming complexity theory that is equivalent to P$\stackrel{?}{=}$NP?

(somewhat related question: the Disser/Skutella paper also refers to Klee-Minty cubes, long used to show worst-case behavior on the simplex algorithm. are there any results relating lower bounds on them to general algorithmic lower bounds and/or complexity class separations eg P$\stackrel{?}{=}$NP etc?)

[1] "In defense of the Simplex Algorithm's worst-case behavior" Dissker/Skutella
[2] Exponential Lower Bounds for Polytopes in Combinatorial Optimization Fiorini et al


texts: Protocol partition number and deterministic communication complexity

texts:
Besides (deterministic) communication complexity $cc(R)$ of a relation $R$, another basic measure for the amount of communication needed is the protocol partition number $pp(R)$. The relation between these two measures is known up to a constant factor. The monograph by Kushilevitz and Nisan (1997) gives

$$cc(R)/3 \le  \log_2(pp(R)) \le cc(R).$$

Regarding the second inequality, it is easy to give (an infinite family of) relations $R$ with $\log_2(pp(R)) = cc(R)$.

Regarding the first inequality, Doerr (1999) showed that we can replace the factor $c=3$ in the first bound by $c=2.223$. By how much can the first bound be improved, if at all?

Additional motivation from descriptional complexity: Improving the constant $2.223$ will result in an improved lower bound on the minimum size of regular expressions equivalent to a given DFA describing some finite language, see Gruber and Johannsen (2008).

Although not directly related to this question, Kushilevitz, Linial and Ostrovsky (1999) gave relations $R$ with $cc(R)/(2-o(1)) \ge  \log_2(rp(R))$, where $rp(R)$ is the rectangle partition number.

EDIT: Notice that the above question is equivalent to the following question in Boolean circuit complexity: What is the optimum constant $c$ such that every boolean DeMorgan formula of leafsize L can be transformed into an equivalent formula of depth at most $c \log_2L$?

References:

Kushilevitz, Eyal; Nisan, Noam: Communication Complexity. Cambridge University Press, 1997.
Kushilevitz, Eyal; Linial, Nathan; Ostrovsky, Rafail: The Linear-Array Conjecture in Communication Complexity is False, Combinatorica 19(2):241-254, 1999.
Doerr, Benjamin: Communication Complexity and the Protocol Partition Number, Technical Report 99-28, Berichtsreihe des Mathematischen Seminars der Universität Kiel, 1999.
Gruber, Hermann; Johannsen, Jan: Optimal Lower Bounds on Regular Expression Size using Communication Complexity. In: Foundations of Software Science and Computation Structures 2008 (FoSSaCS 2008), LNCS 4962, 273-286. Springer.


texts: Complexity of algorithm to test if a graph is asymmetric

texts: Counting the order of automorphism group of a graph is polynomial-time equivalent to graph isomorphism problem. But if we just want to know if the order is greater than 1, what is the complexity of this problem? Graphs which have no automorphism except for the trivial one, that is identity permutation, are called asymmetric graphs. So the problem is to check if the graph is asymmetric.


texts:
Definition. Given an undirected graph $G = (V,E)$, a $k$-plex is a subgraph $G'$ of $G$ such that each vertex in $G'$ is connected to at least $s - k$ other vertices in $G'$, where $s$ is the # of vertices in $G'$.

Computing the maximum $k$-plex is NP-hard since a clique is just a $1$-plex. In my understanding, such a reduction only shows the hardness of computing the maximum $1$-plex. Moreover, when $k=|V|$, the problem becomes trivial because any subgraph of $G$ is a $k$-plex then.

  Question. Is the maximum $2$-plex still NP-hard to be computed? Or more generally, given a graph $G = (V,E)$, what is the maximum $k$ such that the maximum $1$-plex, the maximum $2$-plex, $\cdots$ and the maximum $k$-plex are all NP-hard to be computed?

This question seems interesting but I did not come up with a reduction from any other NP-complete problem, even from the MaxClique.


texts: Approximating Independent Dominating set on bipartite graphs

texts:
I'm interested in the following problem: given a bipartite graph, find the smallest independent set of vertices which dominate all other vertices.
My question is: are there any positive results in the litterature regarding polynomial time guarenteed approximations for this problem?
On the negative side, we know that no constant factor approximation exists unless $\mathrm{P}=\mathrm{NP}$. Moreover there is some constant $\delta>0$ for which there is no $\delta B$ factor approximation on bipartite graphs with maximum degree bounded by $B$ (for large enough $B$, assuming $\mathrm{P}\neq\mathrm{NP}$). See [M. Chlebík and J. Chlebíková, Approximation Hardness of Dominating Set Problems in Bounded Degree Graphs]. The problem is also more or less inaproximable when not restricted to bipartite graphs.
I was however unable to find anything implying a positive result about polynomial time approximations on bipartite graphs.


texts: Indexing over all possible functions in better than linear time

texts:
Given two sets X and Y, the number of functions mapping X to Y is $\vert Y\vert^{\vert X \vert}$.

In particular I am interested in binary strings of relatively small length, e.g. 8.  There are $2^8$ (comprising set $B$) possible bit strings and $2^{2048}$ functions that map onto the same set (let's call the set of these $F$ ).  So I need 2048 bits to represent these functions uniquely.

My goal is to find a function, that given an arbitrary an arbitrary 2048 length bit string, will return the appropriate function from  the $F$.  I can imagine doing this with space on order $2^8$, and average time linear in $|F|$, using a hash table mapping $B\rightarrow B$ and some enumeration over mappings.

The question is, can I do better than this, especially with regard to the linear time (without of course just storing all functions)?


texts:
I've been reading about sketches for processing streaming data (the CountMin sketch, the Count sketch, the tug-of-war sketch, FM sketches, etc.).  They use hash functions that are required to be 2-independent or 4-independent or $k$-independent for some small $k$.

However from cryptography we have fast hash functions that are very good candidates to essentially perfect: $k$-independent for every value of $k$ you could ever wish for, and so on.  We can essentially treat them as uniformly chosen from the set of all functions: as far as we know, no polynomial-time computation can tell that this is not the case.  I suspect many practitioners might be happy to use these cryptographic hash functions, if it led to improved performance or better parameters for the sketches.

Does it change anything about the design and analysis of sketches, if we assume we have perfect hash functions like this?  Can we get asymptotically better parameters if we assumed our hash function was perfect?  Or, can we get simpler sketch constructions?

(For instance, I've noticed that the analysis of existing sketches is often somewhat conservative: e.g., it uses the Markov bound or Chebyshev bound.  If we had a perfect hash function we could use a Chernoff-style bound.  Are there any sketches where this makes a significant difference, or is it just a small constant factor in the bound?)


texts: What are the current best upper bounds of #P?

texts:
#P is the class of counting problems for problems in NP.  In other words, a solution to #P returns the number of solutions to a particular problem in NP.

I'm wondering if there have been any studies on the worst-case behaviors of current best solutions to problems in NP.  My focus in the past has been on 3-SAT, so I am particularly interested in the time it takes to count 3-SAT solutions in the worst case.  However, I ask in general, What are the current best upper bounds for any (#P-complete) problem in #P?


texts: The complexity of determining if a fixed graph is a minor of another

texts:
The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic:

1) It appears that there have been improvements to this algorithm since. What is the best-known algorithm at present?

2a) What do people conjecture to be the optimal bound?

Mohar's algorithm for embedding on a fixed surface and Kawarabayashi's algorithm for recognizing $k$-apex graphs decide membership of graphs characterizable by forbidden minors in linear time, motivating the last question:

2b) Is there any reason to suspect that we can do this in linear time?

Of course, if someone already came up with a linear-time algorithm, the last two questions are silly. :)


texts:
An instance of the SET-PACKING problem is given by a list of sets $\mathcal{S} = \{S_1,\dots,S_m\} \subseteq 2^U$. It is a ``yes'' instance iff there exists some subset $\mathcal S'$ of $\mathcal S$ of size $\ge k$ such that for every $S,T \in \mathcal S'$, $S\cap T = \emptyset$.

Now, I propose the "promise variant" of this problem: I am telling you that your instance is a yes instance; that is, there exists some $\mathcal T'\subseteq \mathcal S$ such that all elements of $\mathcal T'$ are disjoint and it is of size $\ge k$. Can you find some $\mathcal S'$ that is of size $\ge k$ with all disjoint elements?

This seems to be an obviously NP-hard problem, but one needs to be slightly careful in the proof: intuitively, simply taking an instance of SET-PACKING and appending k arbitrary disjoint sets will work (informally, if finding them is in P, then SET-PACKING is also in P).

This relates to a similar question that appeared in cs.stackexchange. I am aware that promise variants of NP hard problems are generally hard (that is, given an NP hard problem X, define promise-X to be the problem X when a yes instance is guaranteed).


texts: Is anyone aware of any games/algebraic structures that provide lower-bounding methodologies for $FO(TC)$ formulae? I am aware of EF games as they apply to first-order and second-order statements, but would like to be able to determine lower bounds for $FO(TC)$ queries on finite models. Any help in this direction would be appreciated!


texts: The probability by which Bloom filters preserves the order relation given a similarity measure on sets

texts:
A Bloom filter is a data structure for probabilistic set-membership. When adding an item to the set, $k$ bits (whose indices are determined by $k$ different hash functions) are set to 1. To check if an item is a member of the set, those $k$ bits are checked to be equal to 1. Deletions are no supported and there is a probability of false positives.

Bloom filters are usually used make digests of big sets. In our case they are used to represent a set of items a certain user are interested in. Our clustering algorithm uses the similarity between the sets of two users (Cosine Similarity usually). However for the cryptographic version, we use the similarity between the corresponding Bloom filters of the sets instead.

  What I am seeking as whether there is
  any references regarding the
  conditional probability that the
  similarity between two Bloom filters
  will tell us something about the
  similarity between the corresponding
  sets, and to which degree Bloom
  filters preserve the order relation on
  Cosine Similarity (or other similarity
  measures).

I have been doing some work on that, and it gets pretty deep, lots of combinatorics and multi-set coefficients. I've posted a related question here. I tried to search for papers studying these properties as well and I did not manage to find something of much use.


texts: Deciding whether a metric is a tree metric

texts:
An n-point metric space is a tree metric if it isometrically embeds into the shortest path metric of a tree (with nonnegative edge weights). Tree metrics can be characterized by the 4 point property, i.e. a metric is a tree metric iff every 4 point subspace is a tree metric. In particular this implies that one can decide in polynomial time whether a given metric is a tree metric by examining all quadruples of points in the space.
My question now is what other (than the trivial) algorithms are there? Can one check in linear (in the number of points) time whether a metric is a tree metric?


texts: Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

texts:
This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below:

The original algorithms, despite being hopelessly intractable (e.g. exponential or high-degree polynomial), were considered breakthroughs at the time by the TCS community;
Since then, extremely efficient (e.g. provably linear or sublinear, maybe sub-quadratic) algorithms have been developed and are used in practice.

So, 1) precludes algorithms which have inefficient solutions (e.g. brute-force), but also have efficient solutions. The idea is that these are problems that were initially considered so difficult that even inefficient algorithms were considered a breakthrough by the research community. 2) is meant exclude problems that have shown incremental progress, even if those incremental developments are/were considered theoretically significant (e.g. exponential to high-degree polynomial).
In other words, have we gone from problems that were considered theoretical curiosities to practical, usable algorithms that are widely adopted in practice?


texts: Can every efficiently computable permutation be written as the composition of two efficiently computable involutions?

texts:
It is well-known that every permutation can be written as the composition of two involutions.

Suppose that $p$ is a polynomial. Then does there exist a polynomial $q$ such that if $f:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ and its inverse are permutations which are computable by combinatorial circuits with at most $p(n)$ gates, then there exists involutions $g,h:\{0,1\}^{n}\rightarrow\{0,1\}^{n}$ such that $f=g\circ h$ and where $g,h$ are computable by a combinatorial circuit with at most $q(n)$ gates?


texts: Densest k subgraph problem for outerplanar graphs?

texts:
The densest k subgraph problem aims to find a subgraph $H$ of a graph $G$ with exactly $k$ vertices that maximizes the number of edges $|E(H)|$.

Does anyone know if there exists a polynomial-time algorithm for this problem under the restriction that $G$ is outerplanar? (Note: I am specifically asking for an algorithm, not a PTAS, and I want $G$ to be outerplanar, not $b$-outerplanar for some $b > 1$).


texts:
Is there a tractable way to define an approximate distribution over small vertex separators of the graph? I'm looking for something along the lines of [Bayati,2008], a way to turn a single "this is a separator" constraint into a product of several constraints that are easier to enforce. Small true separators may be impossible, in which case approximate separators would do (any cycle that goes through approximate separator must have length >k).

Motivation is constructing a message-passing scheme without short feedback loops.


texts: Compared growth of the number of syntactic classes and Nerode classes.

texts:
For a language L ⊆ Σ^*, define the syntactic congruence ≡ of L as the least congruence on Σ^* that saturates L, i.e. :

u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L].

Now define the Nerode equivalence as the following right congruence :

u ∼ v ⇔ (∀ x)[ux ∈ L ↔ vx ∈ L].

Let [u] be the equivalence class of u with respect to ≡ and 〈u〉 with respect to ∼.
Now define i(n) to be the number of different [u]  for u of size n, and define j(n) in a similar fashion for ∼.

Now the question is, how do the two functions relate ?

For instance, a standard theorem (Kleene-Schützenberger, I believe) says that i(n) is bounded by a constant whenever j(n) is, and reciprocally.

Question: Is there any other result in this trend?  What if one of them is polynomial, for instance?


texts: What are some good references for mathematical optimization for the layman?

texts:
I've been getting myself involved with this topic and would like to read more to gain a conceptual understanding of the various techniques and what each one is trying to achieve and their 'idea' behind achieving it. Basically the 'big-picture' view of things excluding the complicated math if possible.

I've read numerous articles on the web and TCS too :) but still would like to know some good references for the layman (i.e. if you were to explain the various concepts/ideas to your wife/mother/child what you recommend them?) I know they wouldn't all be listed in one book but even if they are spread out across books that's fine.

I'm quite interested in learning about nonlinear programming, semi-definite programming, convex optimization, I'm fairly well versed with linear/integer programming and do have a decent background in algorithms and a strong CS background too :)

I may not have a strong mathematical background as probably required by these topics and before I develop it I'd like to have some 'fun' understanding the 'what, why and how' at a more humane level before diving into the math :)

What would be some good references for the above? Good books/links covering other aspects of optimization but not listed above would be welcome to.


texts: Mathematical explanation of recursion and lambda (referenced in The Little Schemer)

texts:
In the preface of Friedman and Felleisen's book The Little Schemer it states:

  We could, for example, describe the entire technical content of this book in less than a page of mathematics, but a reader who understands that page has little need for that book.

Has anyone got an online link to the equivalent of this mathematical summary of The Little Schemer in a single page? Presumably this would cover recursion,  lambda and the y-combinator.


texts:
Background

  We know that $P^{\#P} \subseteq PSPACE$.

  In addition, we known from
  Toda's theorem that $PH \subseteq P^{\#P}$.

  For more background on $\#P$, see here:
  https://en.wikipedia.org/wiki/Sharp-P

Question

  Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?


texts: Any Hypothesis Classes Other than Parity in Noisy PAC but not in SQ?

texts:
Angluin and Laird ('88) formalized learning with randomly corrupted data in the model "PAC with random classification noise" (or noisy PAC). This model is similar to PAC learning, except for the labels of the examples given to the learner are corrupted (flipped), independently at random, with probability $\eta < 1/2$.

To help characterize what is learnable in the noisy PAC model, Kearns ('93) introduced the Statistical Query model (SQ) for learning.  In this model, a learner can query a statistical oracle for properties of the target distribution, and he showed that any class that is SQ learnable is learnable in noisy PAC.  Kearns also proved that parities on $n$ variables cannot be learned in time faster than $2^{n/c}$ for some constant $c$.

Then Blum et al. ('00) separated noisy PAC from SQ by showing that parities on the first $(\log(n) \log\log(n))$ are polynomial-time learnable in the noisy PAC model but not in the SQ model.

My question is this:

  Parities (on the first $(\log(n) \log\log(n))$ variables) are learnable in the noisy PAC model but not in the SQ model.  Are there any other specific classes, sufficiently different from parity, that are known to be learnable in noisy PAC but not in SQ?


texts: Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?


texts: Classification of Saturated LL(1) Grammars

texts:
By saturated I mean that the grammar accepts every possible string
that can be constructed from the terminal set. So the parse table would
be full of valid entries, no error entries at all. Can such a grammar
be known to also be included in a more restrictive class, such as
regular for example?

The following grammar is what motivates this question.

A1 --> A2 a
A1 --> A2 b
A2 --> A3 a
A2 --> A3 b
A3 --> A4 a
A3 --> A4 b
    .
    .
    .
Ak --> a
Ak --> b

Clearly since the grammar is left-linear we know that it is LL(k) as
well. Can anything be deduced from the other direction. That is, by
knowing that the grammar is saturated LL(k), can we say that it is
also regular? Does the saturated property imply anything useful about
the grammar?


texts: Dependence of decidability on the encoding of Turing machines

texts:
Let $f : \{0, 1\}^* \to \{0, 1\}^*$ be a computable function. Given any encoding $\left<M\right>$ of Turing machines over binary (i.e., a function from the set of Turing machines to the set of strings over $\{0, 1\}^*$), consider the following language:
$$ L_f = \{\left<M\right> \mid M \mathrm{\ accepts\ } f(\left<M\right>)\} $$
Question: Does there exist a function $f$ for which the decidability/recognizability of this  language depends upon the particular encoding used?


texts: NP-hard problems on the class of caterpillars

texts:
My question is whether there exist an NP-hard problem that has only a caterpillar as input.

By saying only caterpillar as input, I wanted to emphasize that no function (eg: weights on vertices or edges) or specially chosen vertex (or edge) or anything like that is part of the input.

Instance: a caterpillar $T$
Question: __________

There are two similar question in the site: NP-hard problems on trees, NP-hard problems on paths. Note that all answers for the latter problem needs more than one path in input and/or additional structures (edges weights, for instance). In fact, so are most (but not all) answers of the former problem (on trees) as well.

I feel that it is implausible to have an NP-hard problem that take only a path as input. But, it is possible to have an NP-complete problem that take only a caterpillar as input (isn't it?).

Update: I am interested in problems that are naturally defined on caterpillars. True, we cannot define naturality: but we can sense it when we see it.

Thank you


texts: Complexity of counting when there is no parsimonious reduction

texts:
Let $\#A$ be a counting problem in $FP$ and let $\#B$ a counting problem with unknown complexity.  Suppose there is a polynomial-time, one-to-many reduction from $B$ to $A$, but there is no specific relation between the solutions of $A$ and those of $B$.

For example, $i$ solutions of $A$ could be related to one solution of $B$, and $j$ other solutions of $A$ could be related to a different solution of $B$ and so on. I only know that I can cover all solutions of $B$ via the reduction, and nothing more about solutions of $B$.

Is it possible to conclude that $\#B$ is in $FP$? Or do I have to find a strict parsimonious reduction or weak parsimonious reduction in a way that I could obtain the exact number of solutions of $B$ (possibly with help from the reduction)?


texts:
This question is related to one of my previous questions, NP-hard problems on trees.

  I am looking for problems that are P-complete on trees.


texts: Problems in $\mathsf{BPP}$ not known to be in $\mathsf P$?

texts:
What problems are known to belong to $\mathsf{BPP}$ but not known to belong to $\mathsf P$?

More precisely, I am interested in independent problems, that is whose derandomizations are not known to be equivalent. For instance, it is known that derandomizing PIT and multivariate polynomial factorization are equivalent and I would count them as only one problem.

The motivation of my question is that it is common to say that "there are few problems in $\mathsf{BPP}$ not known to be in $\mathsf{P}$", but I was not able to find a list of them. In particular, if I have to cite problems in this category, I usually cite the factorization of univariate polynomials over finite fields, or the factorization of multivariate polynomials. I suppose that there exist examples that are not related to polynomial factorization, for instance in other domains such as graph theory or formal language theory.

P.S.: I find curious that a similar question does not exist on this website yet. My apologies if I simply did not find it (or them)!


texts:
MCS problem: Given a set $\phi$ of Boolean clauses. Find a minimal correction subset (MCS) $M\subseteq\phi$ such that: $\phi\setminus M$ is satisfiable and for all $c\in M$ holds $\phi\setminus (M\setminus\{c\})$ is unsatisfiable.

I would like to know the complexity hardness of this problem, but I just could not find a clear answer to this question:

Is the computation of a minimal correction subset (MCS) $FP^{NP}$-hard?

A similiar question would be 'Is the computation of a maximal satisfiable subset (MSS) $FP^{NP}$-hard?', since the complement of an MCS is an MSS.

Obviously, the MCS/MSS problem is in the class $FP^{NP}$, since we can iterate over all clauses and check for satisfiability. If satisfiable, add clause to the MSS, otherwise add clause to the MCS.  See for example [Marques-Silva, On Computing Minimal Correction Subsets, 2013]

If this question is an open research topic, I would be happy, if someone could confirm it (and possibly give a reference to a recent paper).

I just found a paper 'On the Query Complexity of Selecting Few Minimal Sets' by Marques-Silva and Janota (2014). In the introduction it states:
"For example, it is not known what is the best worst-case number of calls to a SAT solver for computing [..] a maximally satisable subset [..]".

Unfortunately, the paper shows no further references to underline this statement. But, if I interpret 'best worst-case' correctly, it says that there is no known hardness result for MSS (and therefore for MCS, too) in terms of SAT solver calls. Anyone agree or disagree?


texts: Magic constant to solve NP-complete problem in polynomial time

texts:
Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C_n$ that has a polynomial length $P(n)$?
Clearly, if $P\ne NP$ this constant can be only calculated in exponential time and the calculation must be done for each $n$.

Thanks


texts: What's the state of the art for matrix nuclear/trace norm optimization

texts:
I am interested in simple matrix optimizations with nuclear/trace norm:

$\min_X \left(f(X) + \|X\|_*\right)$

where $\|X\|_*$ stands for the trace norm of the matrix $X$, and $f$ is a convex smooth function.

What is the largest size of the matrix that the state-of-the-art solvers can handle?  In particular, I am interested in the case where both the number of rows and columns are large.


texts: What type of automaton is Google's Turing Doodle?

texts:
In celebration of Alan Turing's birthday, Google published a doodle showing a machine. What kind of machine is the doodle? Can it express a Turing Complete
language?

There are obvious differences to the classical turing machine: a finite tape, constraints in how state can be connected,...

The doodle is still be available here

(The display on the top right shows the expected output.)

The  tape in the middle is divided into squares that can hold a blank, a zero or a one. The head is positioned above one of the squares and is used for reading and writing.

Below the tape you can see a green arrow which you can click on to start the machine. There are two lines of circles next to it, some of which are connected. I will call them "states".

After the machine starts, the first state to the right of the green button lights up, then the next one to the right, and so on... Each state contains one of the following commands:

blank = do nothing (just move to the next state)
1 = write a one to the tape at the current position of the head
0 = write a zero to the tape at the current position of the head
arrow to the left = move the head one step to the left
arrow to the right = move the head one step to the right
condition: if the value under the head is equal to the value shown in the square go down to the second line of states. if not, move to the next state to the right
left jump: return to a (fixed) previous state but only on the upper row [I originally forgot that one, thanks  @Marzio!]

There is no way to "overlap" two jumps (one over another).
The machine stops when there it leaves a state and there is no next state to the right of it.

(After the machine stops the contents of the tape are compared to the contents of the display, but I don't consider that to be part of the intended functionality of the machine.)


texts:
I've got a specific problem, but I'm not sure where to look to solve it:

In the context of my application, there are critical services, non-critical services, and agents which provide exactly one critical service and one or more non-critical services. I must choose from the collection of all agents (with replacement) a finite number of agents, such that each critical service is provided by a certain number of agents. This is straightforward. However, I have the secondary objective that I would like the set I choose to also provide as many different non-critical services as possible.

I'm sure this can be done via SAT, but I don't really want to mess around with NP-complete solvers. The goal for either kind (critical or not) of the services could be constructed as a network flow problem and solved in a straightforward way, but I can't seem to merge them, even as a multi-commodity network flow.

Has anyone seen this problem before, or something embarrassingly similar? I'd really appreciate a pointer to where I could start looking for solutions.

-- David


texts: Does k-PATH admit a constant approximation?

texts:
In the $k$-PATH problem, we receive as input a graph $G$ and an integer $k$. The goal is to decide whether there exists a simple path of length $k$ in $G$.

A $\alpha$-approximation for $k$-PATH is an algorithm which given an input $\langle G,k\rangle$ either confirms that a path of length $k/\alpha$ exists in $G$, or denies the existence of a $k$-path. It may act arbitrarily if the longest simple path in $G$ is at least of size $k/\alpha$ and at most of size $k$.

Is there a constant $\alpha>0$ for which $k$-PATH is $\alpha$-approximable in poly time?


texts: off-policy and offline policy reinforcement learning

texts:
What's the difference between

  off-policy reinforcement learning
  algorithms

and

  offline policy reinforcement learning
  algorithms ?

Or do they mean the same thing ?
thanks


texts: centralized deterministic Spanner construction with low degree and low stretch

texts: Does there exist a centralized deterministic spanner construction with low degree and low stretch both independent of the graph diameter (no log D factor), but can be dependent on the number of nodes. There exists distributed spanner construction algorithms that satisfy this property, so I believe there should exist a simpler centralized counterpart.


texts:
Theorem 2.2 in "Nondeterministic circuits, space complexity and quasigroups", by Wolf, 1994 (a technical report version is available here without fee), proves that NP = NNC, where NNC is the class of languages decidable by an L-uniform family of nondeterministic NC circuits. A nondeterministic NC circuit is an NC circuit with a polynomial number of nondeterministic input bits. The simulation essentially guesses a tableau of an arbitrary NP machine then verifies that each configuration proceeds from the previous one according to the transition function of the machine. My interpretation of this proof is that the NC circuit is in fact an NC1 circuit, since it simply takes the conjunction of a polynomial number of subcircuits, each of which checks that a local "window" in the tableau is valid.

Assuming that interpretation is correct, it should follow that NP = NL, since NC1 is in L, so the same argument will apply. What is the error in my interpretation of this result? Why doesn't the strategy "guess a tableau, verify that each configuration follows from the previous" work?


texts: Decide if a given sequence is regular or context-free

texts:
Given a sequence s (or a finite set of sequences) I would like to know if this was generated by a regular or by a context-free (supposes these are the only options) grammar.

Of course, this is an ill-posed problem because any finite language is regular. So I am more interested in work which tried to discover context-free, non-regular structures inside a given sequence. I could think of two possible ways of doing it:

is a smallest CF grammar "much smaller" than a smallest regular grammar? If yes, this would be a good indicator that the generative grammar should be CF
try to find specific context-free structures (in the sense of the pumping lemma).

Any work out there I should know about?


texts: Indexing structure for all-pairs min-cuts in a huge DAG

texts:
I have a huge DAG - e.g., the dependency graph of all packages in a linux distribution.

Suppose I'd like to make a user-friendly tool that makes it very easy to understand how to break the transitive dependency between package A and package B, and do other related queries/algorithms.

The question "how to break a transitive dependency" is answered by a min-cut.

Is there a practical indexing structure for answering all-pairs min-cut that works for large DAGs (non-ridiculous time and space complexity)? I am aware of Gomory-Hu trees (though I have not yet grasped them), but they seem to work only for undirected graphs.


texts: Finding a cell in an arrangement of simplices

texts:
My question is n-dimensional, but I will begin by dropping the problem down to two dimensions for clarity's sake. It regards defining what is a solution by defining one or more data points that are known to be solutions and a set of linear bounds.
Lets say you have a two-dimensional grid of discrete units that exists within a limited domain, say 1000 x 1000. I'll refer to that domain as D, and reference units within that domain via zero relative c-style array operators (e.g. D[0][0] and D[999][999]).
We also have a function L describing a line segment defined by two points in ℝ2 and within the bounds of D. D[5,5] and D[10.4, 2.6] would be valid points, whereas D[1020, 40] and D[503, 2000.7] would not.
We then create some random set of line segments S{L1, L2,...,Ln} that may or may not intersect with other line segments in the set and define some point P in ℝ2, like (5, 6.7), that is bounded by D and does not intersect with any line segment in S.
If we imagine P as a water source, and S as a set of barriers, the water would spread out and fill some solution area that could be bounded by a set of lines B such that each line connects to the beginning of the next in a loop. Each line is infinitely thin, so lines that project into the water could have the option of not influencing the solution region:

You would then use the point to define the solution area, and determine the set of units in D that are part of that solution area.
If you take this scenario to three-dimensions, you could imagine water filling a volume in a similar manner, generating a three-dimensional bounds object. This can then expand to four or more dimensions.
I suspect the problem would become easier if I split line segments into two line segments at the points of intersection.
I've looked at some isosurface algorithms and modified dilation (fill) algorithms for solving this problem, but they seem very inefficient, especially given extremely large domains, or domains whose resolution relative to the set of bounds functions can be arbitrarily set. The problem grows when the domain has more than three dimensions.
I'm certain that this sort of problem has been dealt with before, as restricting the domain of large data sets down to a solution set using a set of bounds in a time-efficient manner is fundamental to many big-data problems. I'm mainly looking for resources and algorithms related to this problem that I might be able to use?
EDIT
The solution set can also have holes. For example, a bounds with the appearance of a square inside a square, with the solution point between them, would produce a solution area that looked like a square with a square hole in it.
Edit
The more I think about it, the more I think this might actually be a graph-theory question.


texts: Subset of a vertex set with directed edge to all other vertices

texts:
I am posting the following question due to a lacking overview of relevant algorithms.

Given a directed graph $G=(V,E)$, how can you find a (minimal) subset $S$ of $V$ such that there for every vertex $u \in V-S$ is a (directed) edge from some vertex $v \in S$ to $u$?


texts: Reducing space usage of st-connectivity with multiple passes?

texts:
Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream.

Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar
Rajagopalan observed that $\Omega(n/k)$ space is necessary to determine whether there is a path between two given vertices in $G$, if $k$ passes are allowed over the data.  (See also the technical report version.)  However, they do not provide an algorithm to actually achieve this bound.  I assume that an optimal algorithm would actually take $O((n\, \log\, n)/k)$ space in a realistic computing model, since one has to distinguish the $n$ different vertices if one cannot index memory using constant size pointers.

  How can one decide graph connectivity with $k$ passes using $O((n\, \log\, n)/k)$ space?

If only one pass is allowed, the input data can be stored as a partition of the set of vertices, merging sets if an edge is seen between vertices in two different sets.  This clearly requires at most $O(n\, \log\, n)$ space.  My question is about $k > 1$: how can one use more passes to reduce the required space?

(For avoidance of triviality, $k$ is a parameter that cannot be bounded a priori by a constant, and the space bounds are expressions involving functions of both $n$ and $k$.)

Update: even for $k=2$ it would be really useful to have a way to store only $n/2$ vertices.  Or is there actually a stronger lower bound $cn$ for some constant $c$, regardless of $k$?


texts:
In quantum computing we are often interested in cases where group of special unitary operators, G, for some d-dimensional system gives either the whole group SU(d) exactly or even just an approximation provided by a dense cover of SU(d).

A group of finite order, such as the Clifford group for a d-dimensional system C(d), will not give a dense cover.  A group of infinite order will not give a dense cover if the group is Abelian. However, my rough intuition is that an infinite number of gates and basis changing operations of the Clifford group should suffice to provide a dense cover.

Formally, my question is:

I have a group G that is a subgroup of SU(d). G has infinite order and C(d) is a subgroup of G. Do all such G provide a dense cover of SU(d).

Note that I am particular interested in the case when d>2.

I take the Clifford group to be as defined here:
http://arxiv.org/abs/quant-ph/9802007


texts:
Consider a graph $G = (V,E)$ with $N$ edges. Consider two vertices $u_1, v_1 \in V$. We wish to find whether there exists a path of length $4$ between these two vertices or not. This is easy to do in $O(N)$ time by performing a BFS.

Clearly, there also exists a tradeoff between preprocessing space and answering time. I can use $N^2$ space by storing a bit for all possible vertex pairs to indicate whether there exists a path of length $4$ or not and answer each query in constant time. The other end of the spectrum is that BFS gives linear query time.

I am interested in using the least amount of space to answer the query for any pair of vertices $u_1$ and $v_1$. in sublinear time $N^{1-\epsilon}$. Any leads/papers/ideas appreciated!


texts: APx hardness of Multiterminal Cut Problem

texts:
In a Multiterminal Cut problem input is a graph G=(V,E) and a set of k terminals T which is a subset of vertex set V. There is a weight w(e) associated with each edge in the graph. The question is to find the minimum weight edge set whose removal will disconnect every terminal to every other terminal in T. The following things are known about the problem:

k = O(1), Degree of any vertex unbounded, edge weights = O(1)
APX hard
k = O(1), Degree of any vertex = O(1), edge weights unbounded
APX hard
k unbounded, Degree of any vertex = O(1), edge weights = O(1)
NP hard
k = O(1), Degree of any vertex = O(1), edge weights equal
Poly time.

Is there a result which says that the problem with " k unbounded, Degree of any vertex = O(1), edge weights = O(1)" is also APX-hard? Any ideas on proving this will be useful.


texts: Why does the log-rank conjecture use rank over the reals?

texts:
In communication complexity, the log-rank conjecture states that

$$cc(M) = (\log rk(M))^{O(1)}$$

Where $cc(M)$ is the communication complexity of $M(x,y)$ and $rk(M)$ is the rank of $M$ (as a matrix) over the reals.

However, when you are just using the rank-method to lower bound $cc(M)$ you can use $rk$ over any field that is convenient. Why does the log-rank conjecture restrict to rk over the reals? Is the conjecture resolved for $rk$ over fields of non-zero characteristic?  If not, is it of interest or is there something special about $rk$ over $\mathbb{R}$?


texts: Lower bound for the maximal vectors problem

texts:
I am studying the (worst-case) complexity $C(n,d)$ required to solve the maximal vector problem: given a finite set $V$ of $n$ $d$-dimensional vectors, compute the set of undominated (a.k.a. skyline, pareto) vectors:

$$\{v\in V\mid \forall v'\in V\;\exists i\leq d.\, v.i>v'.i\}$$

I am aware of the following upper bounds:

$O(dn^2)$ (trivial algorithm)
$O(n(\log n)^{d-2})$ when $d\geq3$, $O(n\log n)$ for $d\leq 3$. On Finding the Maxima of a Set of Vectors, Kung et al'75
$O(n^{2.684})$ when $d=n$ Efficient algorithms on sets of permutations, dominance, and real-weighted APSP, Yuster'08, which improves marginally a result of Matousek's IPL'91.

As for lower bounds, I am only aware of one bound (tight when $d=2$):

$C(n,2)\geq S(n)+n-1\approxeq n\log_2 n+n-1$ , where $S(n)$ is the number of comparisons required for sorting $n$ elements. On finding the maximal elements in a set of plane vectors, F.F. Yao, technical report UIUC'74

Are other non-trivial bounds known? In particular lower bounds that refine Yao's for $d>2$?

N.B.1 For the lower bound I am interested in a model where the only question available to access the data is "is vector $v$ greater than $v'$ along dimension $i$?".
Though I would still be curious about whether interesting bounds are known in other models (e.g. for integer valued vectors).

N.B.2 The above is about computational complexity, but I am also curious about results about the minimal number of comparisons required, apart from
Yao's lower bound and the trivial $dS(n)$ upper bound


texts: Stream fusion in total functional language

texts:
As I understand, stream fusion consists in converting operations on lists to operations on streams (colists), optimize redundant codata to data and back conversions, fuse operations on streams, and finally convert the resulting stream to a list again.

Data to codata conversion is a total operation, but the opposite is not. Is stream fusion optimization impossible in total functional programming languages?


texts:
Consider an acyclic directed graph in which a traversal from any node in the graph must eventually end at some terminal node R.  Borrowing from tree-based vocabulary, I would tend call this the "root" of the graph, since all traversals eventually terminate there.  However, the term "rooted graph" seems to already be in use for something else.

Is there a term I can use to describe this property?  The best way I can describe the graph at present is a "multi-parented directed tree" -- all nodes point toward the root, but, unlike a directed tree, nodes may have more than one parent. I don't like this terminology, though, as it seems like an abuse of the term "tree".

I considered "hierarchical graph", but a node can have more than one outgoing vertex, so I think that may disqualify it from being hierarchical.


texts:
Let a weighted graph $G(V,E)$, where the weights are real (positve and negative). Assume that $G$ has $\mathcal{O}(n\log n)$ edges.

How fast can we compute MAX-CUT on this graph?
Can we compute (approximate within $\epsilon$) MAXCUT faster on sparse graphs compared to dense ones?


texts: What is the relation of parametricity and function extensionality?

texts:
In Agda function extensionality can be defined like this:
funExt = {A : Set} {B : Set} {f1 f2 : A → B} → (∀ x1 x2 → x1 ≡ x2 -> f1 x1 ≡ f2 x2) → f1 ≡ f2
One may note a similarity in the definition of a (binary) logical relation
f1 [A -> B] f2 being:
∀ x1 x2 → x1 [A] x2 -> f1 x1 [B] f2 x2.
What is the relation of logical relations to function extensionality?
Is there perhaps a relation to eta-equality?


texts: What is the state-of-the-art asymptotics for convex optimization?

texts:
I've got a convex program of the form:

Choose $v \in \mathbb{R}^n$ to minimize $vAv^T$ subject to $O(n)$ linear contraints (including $v \ge 0$).  $A$ is a square binary matrix.

What algorithm gives me the best asymptotic solution?


texts:
[The assumption in this question is wrong. It is possible to enumerate exactly the decidable languages with semideciders.]

Lets say we have a TM $M_E$ enumerator that writes out codes of TM's on a tape. How does one show that it's not possible that every decidable language $L$ is represented, but no undecidable $L$ is represented?

If we demanded that $M_E$ write out every $M$ representing a decidable $L$, then this could be shown impossible by Rice's Theorem II (for r.e. index sets).

If we demanded that every $M$ $M_E$ writes out is a decider, then this could be shown impossible by diagonalizing out of the set.

In this setup $M_E$ writes out $M's$ that aren't necessary deciders but that represent decidable languages. Every decidable language $L$ is represented by some $M$ on the tape, and no undecidable $L$ is represented. How does one show that this is impossible?


texts: "Parity testing set" for disjoint pairs of sets

texts:
I'd like a construction of the following description.  Let $V$ be a set of $n$ elements.  I'd like a collection $X$ of subsets of $V$ such that for any pair $(P,Q)$ of disjoint subsets of $V$, there is an element $S \in X$ such that $|S \cap P|$ and $|S \cap Q|$ are both odd.
Probabilistic arguments indicate that there exists solutions with $|X|=O(n)$, but I'd like an explicit design.  I'd also like to know the best possible constant factor in the size $|X|$.
It sounded basic enough that I thought it should be solved, or easily attackable, but I'm drawing a blank. Any pointers?


texts:
Assume a framework in communication complexity where we have two players A(lice) and B(ob) and a R(eferee). A and B don't communicate directly with each other. In each round of communication, each of them sends a message ($m_A$, $m_B$) to the R. R computes two functions $f_A(m_A,m_B)$ and $f_B(m_A,m_B)$ and sends the results to them. The functions are fixed. The idea is that the communication between the players is restricted. Moreover the referee might do some processing on the messages.

Example:

A and B send two (arbitrary large) numbers to R, R checks which of them is greater and informs the players.

In this framework, we can design a simple protocol that easily computes the following function using a single round. A and B send $x$ and $y$ to R, R returns the answer to them, and they output the answer.

$$f(x,y)= \begin{cases}0 & x\leq y\\ 1 & ow \end{cases}$$

Obviously this is not an interesting case, since the function we are computing is the same as the referee functions. A more interesting case is when we have a fixed linear inequality $\vec{a} \cdot \vec{x} \leq \vec{b} \cdot \vec{y}$ and the values for the variables are partitioned between players (A has $\vec{x}$ and B has $\vec{y}$). The task is to decide if the inequality is correct. The protocol in this case is that players compute their part and then send them to the referee.

Question:

Has this kind of communication complexity been studied? If yes where can I find more about this?

note 1: on page 49 Kushilevitz and Nisan mention a framework which involves a referee but seems very different from what I am asking.

note 2: I am not sure if calling R a referee is the right thing, please comment if you have a better suggestion.


texts: Local Smoothness vs optimisation in combinatorial problems

texts:
Local smoothness is often mentioned in literature analysing different heuristics and meta-heuristics for combinatorial optimisation.  What is meant precisely by local smoothness is often left out, but one definition is "A landscape with small (average) fitness differences between neighboring points is called smooth". Additionally I have read of at least one measure (auto-correlation) that quantifies this.

I am interested however in the relationship between smoothness and optimisation processes.  The extent of the detail in literature seems to be local smoothness is good for optimisation and ruggedness is bad.  Could anyone further explain the relation between effective optimisation and local smoothness, and/or point to literature that delves into this more deeply.


texts:
Lipton asks for a physical proof of $P\neq NP$.

Can we even ask for a physical proof for understanding $P=BPP$ or $P\neq BPP$? Is there anything in physics that lets us avoid randomness?

Statistical mechanics and hence entropy is founded on randomness.

Entropy, information and randomness are all related and in this case can physical principles show $P=BPP$ or $P\neq BPP$ let alone the harder $P$ versus $NP$?

(Harder is relative here.. the guess here is that $P=BPP$ and $P\neq NP$ and showing classes that are hypothetically closer to be equal may be easier than showing classes that are hypothetically far-off to be separate).


texts:
Given a set of points $V \subset \mathbb{R}^d$, the Voronoi diagram divides $\mathbb{R}^d$ into $|V|$ parts such that for every $v \in V$, the part of $\mathbb{R}^d$ for which $v$ is closer than any other point in $V$ is exactly a part of the diagram. See also Wikipedia.

It is well known that for $d=2$, its complexity is $\Theta(n)$ and it can be computed in $O(n \log n)$ time. For $d=3$ however, there are families of pointsets for which the Voronoi diagram has complexity $\Theta(n^2)$, and for $d > 3$ there are even worse cases.

However, from what I've seen, all these bad cases seem to occur 'inside' the pointset, and for the purpose I have in mind, this inside is irrelevant.

Let $m = \max \{ |uv| \mid u, v \in V \}$. Suppose therefore we take a bounding box around our pointset $V$ and increase its size by some constant factor $c$ so that any point in $V$ is at least $m (c-1)/2$ away from this larger box. We take the Voronoi diagram for $V$ and remove the part that is inside the box. We name this new diagram the outer Voronoi diagram.

  What is the worst-case complexity of the outer Voronoi diagram for $d=3$? What if $d>3$? If this complexity is smaller than the normal Voronoi diagram, can we also compute it faster?


texts: Algorithms for finding all cliques of a given degree in a graph

texts:
Consider a graph with $n$ vertices and maximum degree $Δ$. I would like to obtain all $s$ cliques, where $s≤Δ$ and both of them are small compared to $n$.

Bron-Kerbosch algorithm gives all maximal cliques but that's not quite what I need. I want all s cliques (where $s≤Δ$), including not maximal ones.

Are there any efficient algorithms to do this? Even achieving an exponential speed-up would be good?


texts: parallel algorithms for the determinant of the Hessenberg matrix

texts:
I am interested in highly parallel algorithms for computing the determinant of matrices of a special form (over finite fields).

It is known that computing determinant of general matrices over finite fields is in NC2.
I've been wondering whether something better is known (hopefully NC1) for the (say, lower) Hessenberg matrix.

If it helps, it is further restricted so that its subdiagonal is all 1's, and all I care about is whether the determinant is 0 or not.


texts: Can recursion be replaced with a finite set of higher-order functions?

texts:
I am wondering if there is some proof that all recursive algorithms can be rewritten to use some known set of higher-order functions instead of recursion. I'm talking about functions like fold, map, filter, etc.

If recursion can always be replaced, I'm also interested in knowing whether there is some mechanical translation, or if it's something that can't be automated.

Apologies if this question is ill-formed. I'm no PLT expert.


texts:
The (uniform) directed sparsest cut problem asks for a cut $(S,\bar{S})$ in a directed graph $G=(V,E)$ which minimize the ratio $\frac{\delta_{out}(S) }{|S||\bar{S}|}$, where $\delta_{out}$ is the total capacity of edges coming out from $S$. The best approximation ratio for the problem is $O(\sqrt{\log n})$ via the paper $O(\sqrt{\log n})$ approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems.

The undirected version of the problem on planar graphs have a factor two approximation algorithm:  Finding separator cuts in planar graphs within twice the optimal !
Does anybody aware of a similar result for directed sparsest cut on planar graphs ? Can we apply the same technique for the undirected version to get a constant ratio?


texts: Cases of nearly linear time solvable linear systems

texts:
Let a square $n\times n$ real matrix ${\bf A}$ and two vectors ${\bf x}$ and ${\bf b}$ of length $n$, such that $${\bf A}{\bf x}={\bf b}.$$
Solving for ${\bf x}$ through standard Gaussian Elimination yields an aggregate complexity of almost $O(n^3)$.
However, there are cases where solving (or $\epsilon$-approximately solving) for ${\bf x}$ costs $O(n\log^\rho n)$, such as systems where ${\bf A}$ is a symmetric and diagonally dominant matrix (e.g., a Laplacian) [1].

Which other families of linear systems (i.e., matrices) admit linear (or nontrivial poly(n)) time solutions?
If we consider finite fields instead of real matrices, are there any families of matrices there that admit nearly linear time solutions?

[1] http://www.cs.yale.edu/homes/spielman/Research/linsolve.html


texts:
Suppose you have sets $S_1, \dots S_m$ such that $\sum_i |S_i| = n$. The goal is to arrange all the sets into a (possible unconnected) DAG such that $S_i$ is a parent (or ancestor) of $S_j$ iff $S_j \subseteq S_i$. The domain of the elements over which $S_i$ are constructed can have size as large as $O(n)$ (so no word packing tricks or orthogonal vector style lower bounds).

Note that any set $S_i$ that is not a subset of some other set will be an isolated vertex in the graph. I wish to know the time complexity of solving this problem and possible lower bounds.


texts:
I'm looking at page 28 of Lovasz "Semidefinite programs and combinatorial optimization" and it gives the following approximation of independence number of the graph

$$\max u' Z u$$
subject to
$$Z\succ 0$$
$$Z_{ij}=0 \ \forall ij\in E(G)$$
$$tr(Z)=1$$

Can I get independent set (or something close to an independent set) directly from the solution of SDP relaxation? Lovasz says that SDP is the only known way to solve this problem exactly for perfect graphs, is that still true?

Clarification: there's a similar SDP relaxation for the size of maximum cut, and I can get the full solution (the actual cut, rather than its size) by taking square root of Z and doing randomized rounding (Ch.6 of Williamson/Shmoys book). I'm wondering if there's a similar technique for this problem


texts: Multi-way spectral partitioning and higher-order Cheeger inequalities

texts:
I am reading the paper above by Lee, Gharan and Trevisan, and I am having trouble with lemma 4.8 on page 23. How do we form the set $T_1, \ldots, T_{r'}$ such that $r'>(1-\delta/2)k$ and each set $T_i$ satisfies both the upper bound and lower bound with respect to $\epsilon$ as in the paper ?
I am struggling with this for a while, so any help is greatly appreciated.


texts:
By $'$ I mean transpose. I gather the info here from  rjlipton.wordpress.com/2014/12/21/modulating-the-permanent.
We know that if $U\in\Bbb F_{3^t}^{n\times n}$ satisfies $UU'=I_n$ in $\Bbb F_{3^t}$ then we can compute $Perm(U)$ in $\Bbb F_{3^t}$ in $O(n^4)$ time.

This gives an $O(n^4)$ time algorithm for $Perm(U)\bmod 3$ for $U\in\Bbb Z^{n\times n}$ satisfying $UU'=I_n$ in $\Bbb Z$?

  Can it be modified to give an $O(n^{O(t)})$ time algorithm for $Perm(U)\bmod 3^t$ for $U\in\Bbb Z^{n\times n}$ satisfying $UU'=I_n\bmod 3^r$ in $\Bbb Z$ where $r\in\Bbb N$ is fixed?


texts: Name of this graph partitioning problem? (related to coloring)

texts:
Given a graph $G=(V,E)$ and an integer $k$, find a partition $P_1, P_2, \dots, P_k$ of $V$ into $k$ parts that minimize the total number of edges between two vertices in the same part, i.e. $\sum_i |(P_i\times P_i)\cap E|$.
May someone please provide the name of this problem and/or references?
If $k$ is larger than or equal to the chromatic number of $G$, then the number of edges under concern is $0$. But if $k$ is lower than the chromatic number, then it is strictly positive. Also, it is trivially bounded by $m=|E|$ (in the case $k=1$).


texts: Complexity for computing weighted number of paths on integer lattice

texts:
Our input is a $(n+1)\times (n+1)$ table filled with some value (integer) for each leftmost and bottom cell $l_i,b_i$ as in the figure.
We wish to compute the value of all upper and rightmost cells $u_i$ and $r_i$ ($1\leq i\leq n$)
when each cell of the table is filled recursively according
to the equation $T(x,y)=T(x,y-1)+T(x-1,y)$ for each $x,y\geq 1$.

If we compute naively the $u_i,r_i$ by filling the table, or summing corresponding binomial coefficients, the complexity is $\Theta(n^2)$.
Is this a lower bound for the problem or is there any way to compute all $u_i, r_i$ in $o(n^2)$?
If so, does the technique extend to rectangular tables?


texts: Approximately counting paths and cycles in a graph

texts: Counting cycles, and paths in graphs is a hard problem, see questions  here, and related question for cycles for a given length $k$,  here. The question is about the approximability of these graph problems, are they easily approximatable? Or do they have more fundamental implications for $NP$ complete problems, or #$P$ counting problems, hardness or otherwise. Any #$P$ hardness for approximately counting paths and cycles(from uniform distributions, or not) would imply, gaps between actually generating cycles paths(approximately) and enumerating the number of paths, and cycles. Also, what can be said about the  $APX$ hardness implications under reasonable hardness reduction assumptions($L$-hardness, others)?


texts: Spectrum of absorbing random walk for regular graphs

texts:
I have a symmetric Markov chain given by the matrix $P$. Let $M$ be a set of special states of the chain (called marked states, they correspond to solutions to some problem). We can write $P$ as

\begin{array}
[c]{cc}%
P_{UU} & P_{UM}\\
P_{MU} & P_{MM}%
\end{array}

Here $P_{UU}$ denotes transitions from unmarked to unmarked, $P_{UM}$ transitions from marked to unmarked and so on. From $P$ we form the absorbing walk $P'$, by turning all transitions from marked states to unmarked states into self-loops. Thus $P'$ has the form

\begin{array}
[c]{cc}%
P_{UU} & 0_{UM}\\
P_{MU} & I_{MM}%
\end{array}

Here $I_{MM}$ is the identity matrix.

Define $D(P')$ as

\begin{array}
[c]{cc}%
P_{UU} & 0_{UM}\\
0_{MU} & I_{MM}%
\end{array}

I know the spectrum of $P$. Actually, let's say that $P$ is very nice,
symmetric, corresponding to a regular graph. For instance, $P$ is the hypercube or the 2-D grid with periodic boundary conditions. Thus $P$ is diagonal in the Fourier basis.

How can I can find the spectrum of D(P')? I couldn't find any reference to this.

Of course, I could have formulated the question without introducing that $P'$, but I did so to provide the context where this situation
appears. In short, I have a random walk $P$, I remove from it lines $10$ and $12$
and columns $10$ and $12$ let's say. I want to find the spectrum of the remaining
matrix.

I used the notation $P_{xy}$ = the probability of jumping from $y$ to $x$. Thus, the eigevectors of $P$ are on the right.

Edit: if it is not possible to find the full spectrum, I'd be interested to find the eigenvector corresponding to the second-largest eigenvalue when $P$ is the 2-D grid and I have at least two marked vertices.

Edit 2: In the paper "Quantum speed-up of Markov chain based algorithms" by M. Szegedy, on page 9, the author states that "there are also several methods in store to estimate the spectral norm of $P_{UU}$." He gives the example $\left\lVert P_{UU} \right\rVert \le 1-\epsilon \delta /2$, where $\epsilon = |M|/N$ and $\delta$ is the spectral gap of $P$. Here $N$ is the number of states of $P$. Does anyone know and other methods to say something about $P_{UU}$?

Thanks!


texts: Parallel sorting: introduction and state of research

texts:
there seem to exist papers on parallel sorting, but I have not found a good introduction into this topic.

So, do you know a good summary or introduction into parallel sorting algorithms? In particular, I am looking for some good and handy examples that realize best lower bounds (e.g. like merge sort in the sequentiel case.), if available.


texts: Did "Where the really hard problems are" hold up? What are current ideas on the subject?

texts:
I found this paper to be very interesting. To summarize: it discusses why in practice you rarely find a worst-case instance of a NP-complete problem. The idea in the article is that instances usually are either very under- or very overconstrained, both of which are relatively easy to solve. It then proposes for a few problems a measure of 'constrainedness'. Those problems appear to have a 'phase transition' from 0 likelihood of a solution to 100% likelihood. It then hypothesizes:

That all NP-complete (or even all NP-problems) problems have a measure of 'constrainedness'.
That for each NP-complete problem, you can create a graph of the probability of a solution existing as a function of the 'constrainedness'. Moreover, that graph will contain a phase-transition where that probability quickly and dramatically increases.
The worst case examples of the NP-complete problems lie in that phase-transition.
The fact whether a problem lies on that phase-transition remains invariant under transformation of one NP-complete problem to another.

This paper was published in 1991. My question is was there any follow-up research on these ideas the last 25 years? And if so, what is the current mainstream thinking on them? Were they found correct, incorrect, irrelevant?


texts: Circuit games in extensive form with imperfect information

texts:
Consider $l,m,n,N \in \mathbb{N}$ and circuits $C: \{0,1\}^{l+m} \rightarrow \{0,1\}^l$, $D: \{0,1\}^{l+n} \rightarrow \{0,1\}^l$. Consider the following zero-sum two-layer extensive-form game with perfect information:

The positions of the game are $\{0,1\}^l$ and the initial position is $0^l$.
The 1st player's moves are $\{0,1\}^m$ and their effect on the position is defined by $C$.
The 2nd player's moves are $\{0,1\}^n$ and their effect on the position is defined by $D$.
After $N$ moves the game is over. The first bit of the resulting position determines whether the winner is the 1st player or the 2nd player (the game is zero-sum with pure payoffs $\pm 1$).

It is well-known that the value of such a game can be computed in space polynomial in $l, m, n, N$ and the size of $C$ and $D$ (or even just the depth of $C$ and $D$, assuming appropriate representation).

Now consider the same setting as above with additional parameters $k,j \in \mathbb{N}$ s.t. $k + j \leq l$. Consider the extensive-form game with imperfect information which is the same as above but positions are grouped into 1st player information sets by the first $k$ bits and into 2nd player information sets by the last $j$ bits. That is, the 1st player's pure strategies are functions $\{0,1\}^k \rightarrow \{0,1\}^m$ and the 2nd player's pure strategies are functions $\{0,1\}^j \rightarrow \{0,1\}^n$, which are evaluated on the first $k$ bits or the last $j$ bits of the position correspondingly.

  Is it true that for every $\epsilon > 0$ we can decide whether the value $v$ of the game is positive, in polynomial space, given the promise that $\lvert v \rvert > \epsilon$?

Also, consider the same question for the extensive-form game with perfect recall that results when we allow each player to remember history, i.e. each player's moves can depend both on the current observable part of the position and the history of observable positions and moves for the same player. Note that in this case the game is known to be solvable in time polynomial in $2^{(m+n)N}$ due to the result of Koller and Megiddo.


texts: Can we distinguish strictly syntactic and semantic methods in programming language?

texts:
While discussion strong normalization proofs, this comment contrasts the "normal forms model" with "purely syntactic methods".

This brings me back to a more basic question: can we still distinguish syntactic and semantic constructions strictly, in the face of syntax-based models? What about term models for algebras, Henkin models for first-order logics? What about structural operational semantics? Since term models can be isomorphic to syntax, it seems hard to make a firm distinction.

Until I studied the difference between proof theory and model theory in logic, I was even baffled by the idea that "static type systems are a syntactic method". After all, a type system reasons about types, which are an abstraction of program behavior (and with dependent types, an arbitrarily precise one).


texts: Popular average-case complexity assumptions

texts: Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?


texts: Sampling from the Voronoi cell of a point

texts:
Fix a set of $n$ points $P \subset \mathbb{R}^d$. Now a query point
  $q$ arrives, and the goal is produce a point $r$ sampled uniformly
  at random from the Voronoi cell of $q$ in the set $P \cup \{q\}$.

For the purpose of this question, you can assume that $q$'s Voronoi cell is always bounded (for example $q$ always lies in the convex hull of $P$).

Is there anything known about this problem ?

Some constraints:

I might want more than one sample from $q$'s Voronoi cell. These should be IID.
I am allowed to preprocess the points, but I cannot spend time exponential in $d$.
The sample should be generated in time sublinear in $n$ and polynomial in $d$ ideally.

Note that the above rule out computing the Voronoi cell explicitly. Also note that while a rejection sampling approach would yield a uniform sample, it's not clear how to do it efficiently.


texts: Sparsification Lemma for k-SAT and Exponential Time Hypothesis

texts:
According to R. Impagliazzo, R. Paturi and F. Zane, 2001 an instance of $k$-SAT is called sparse if $m = O(n)$ where $m$ denotes the number of clauses and $n$ the number of variables. The Sparsifiction Lemma, as mentioned in R. Impagliazzo, R. Paturi, 2001 says:

  [...] that an arbitrary $k$-CNF can be expressed (in subexponential time) as the disjunction of a subexponential number of linear size $k$-CNFs. More precisely [...]

  For all $\varepsilon > 0$, $k$-CNF $F$ can be written as the disjunction of at most $2^{\varepsilon n}$ $k$-CNF $F_i$ such that $F_i$ contains each variable in at most $c(k,\varepsilon)$ clauses for some function $c$. Moreover, this reduction takes at most $poly(n) 2^{\varepsilon n}$ time.

In the above reduction, each $k$-CNF $F_i$ has at most $c(k,\varepsilon)n$ many clauses, hence is sparse in the above sense. According to this talk, the Exponential Time Hypothesis (ETH) says:

  $3$-SAT instances (with $n$ variables and $m$ clauses) cannot be solved in time $O(poly(n) 2^{o(n)})$.

(the $O^{\ast}$-star notation just suppresses polynomials). And it says that the Sparsification Lemma is equivalent to:

  If ETH holds, then $3$-SAT instances cannot be solved in time $O(poly(n) 2^{o(n+m)})$.

I do not understand the second claim, so I am asking if anyone could please explain why this is a statement of the Sparsification Lemma, what has it to do with the Lemma as stated before?


texts: How can ORAMs be secure in the random oracle model with O(1) protected words of O(lg n) bits each?

texts:
This post assumes some knowledge about ORAMs on the reader's part. Very roughly, ORAMs are ways in which one can simulate a generic RAM program for $n$ steps in such a way that the memory access pattern reveals "almost nothing" about the nature of the program or its inputs -- this is orthogonal to hiding the actual contents of the memory itself.

As I was reviewing the related literature, I came into a problem. In many constructions, including the original one by Goldreich and Ostrovsky, security is achieved assuming a) a random oracle and b) O(1) words of memory storage that the adversary cannot access. Furthermore, in many recent constructions, it seems that a) words are assumed to be of size O(lg n) and b) the construction is claimed to fail with at most $1/n^{\omega(1)}$ probability.

But shouldn't this be impossible? In general, random oracles are supposed to be public, i.e. the adversary can query them to obtain your same result if he can guess your seed. Then, If you have O(1) protected words of O(lg n) bits each, an adversary should be able to guess your "protected" state with $1/2^{O(\lg n)}=1/n^{O(1)}$ probability. Am I missing something?


texts: How are proofs verified probabilistically in interactive proof systems?

texts:
I'm having a hard time understanding the way Arthur verifies proofs probabilistically with coin tosses in an intuitive manner.

Suppose Arthur is a logician equipped with paper, a pencil and an unbiased coin. Someone hands Arthur a proof that some string s is in some language L. How exactly does Arthur probabilistically check the proof? My interpretation is that he does the following:

Arthur tosses the coin. If it lands showing heads, he accepts the first statement without checking it. If it lands tails, he checks it. If, upon checking, he determines that the first statement is false, he rejects the proof. Otherwise, if he determines that the first statement is true, he continues this process with the next statement of the proof. If Arthur never rejects the proof during this process, then he accepts the proof if one of the statements is a concluding statement of the form "..., hence s is in L" and he rejects the proof otherwise.

Is this a correct interpretation?

Edit: I am not talking about probabilistically checkable proofs. The question above came about from thinking about the class MA.


texts: Damas-Milner-like subset of the calculus of constructions with global type inference

texts:
Damas-Milner is a subset of System Fω that gives up expressivity (type-level computation) for usability (type inference). The experience with Haskell and ML attests to the practical value of this tradeoff.

Does a similar Damas-Milner-like subset of the calculus of constructions exist, for which global type inference is possible? I expect the answer to be “yes” based on the following clues:

1ML's abstract syntax already unifies terms and types, in a way reminiscent of System Fω's definition as a pure type system, and then makes type inference work for a subset of the language.
AFAICT, Damas-Milner type inference only requires that the type language be first-order, pure, terminating and confluent. First-order unification doesn't require that all unification variables range over a single sort (namely, that of types). A first-order, pure, terminating language can be carved out of a higher-order, effectful, potentially nonterminating language, by means of syntactic restrictions on terms in the latter.

But is there a definitive answer?


texts: Complexity of computing the union of H-polytopes in three dimensions

texts:
Consider a set $P_1,\ldots,P_k$ of polytopes in $\mathbb{R}^3$, each given as an intersection of halfspaces with rational normals (in particular, they are all convex).
We are also given a target polytope $Q$, which we can assume is the box $[-1,1]^3$.

What is the complexity class of deciding whether $Q\subseteq \bigcup_{i=1}^k P_i$?

If I'm not mistaken, This paper by Aronov and Sharir shows that the problem can be solved in expected polynomial time.
Is it known whether the problem is in P?
If it simplifies things, in my setting the polytopes are each defined by 4 non-affine halfspaces, so they are infinite cones.


texts: What's the meaning of "input size" for 3-SAT?

texts:
In the computational complexity theory, we say that an algorithm have complexity $O(f(n))$ if the number of computations that solve a problem with input size $n$ is bounded by $cf(n)$, for all integer $n$, where $c$ is a positive constant non-depending on $n$, and $f(n)$ is an increasing function that goes to infinity as $n$ does.

The 3-SAT problem is stated as: given a CNF expression, whose clauses has exactly 3 literals, is there some assignment of TRUE and FALSE values to the variables that will make the entire expression true?

A CNF expression consists of, say, $k$ clauses involving m variables $x_1,x_2, ..., x_m$.
In order to decide if 3-SAT has polynomial complexity $p(n)$, or not, I need to understand something so simple as "what is n" in the problem.

My question is:

  Which is considered, in this particular 3-SAT problem, the input
  size n?

Is it the number k of clauses? Or is it the number m of variables?
Or n is some function of k and m? ( $n=f(k,m)$ ).

What exactly the theoretical computer scientits consider as the input size for this problem?

I did the estimate that $n \leq $constant $* m^3$. Is this correct for you?


texts: Cell probe model vs transdichotomous ram

texts:
can someone explain me the difference between those two (cell probe model and transdichotomous ram)?

In cpm I'm allowed to do computation for free, and complexity of algorithm is just a number of memory reads/writes. Can I use words as pointers in that model? Is the memory size fixed or unbounded?

In transdichotomous ram memory is a table of words indexed from 0 to S - 1 for given S. words have fixed size and serve as pointers. I can read/write constant number of cells at constant time. What about complexity of operations? Are computation free?

I don't feel the difference between them.

Thanks for help!


texts:
It is known that $\textbf{AM}[O(1)] = \textbf{AM}$.

Since $\textbf{IP}=\textbf{PSPACE}$ we have $\textbf{AM}[poly(n)] = \textbf{PSPACE}$.

Can we say something about $\textbf{AM}[ f(n)]$, where $f$ is a function between  $O(1)$ and $poly(n)$?

(For example, $f(n) = \log n$.)


texts: Is the proceedings of WG 2015 published?

texts:
Within theoretical computer science, the "Workshop on Graph-Theoretic Concepts in Computer Science (WG)" is one of the main specialized venues for publication of papers dealing with graph theory. It's 41st edition, WG 2015, happened in June 2015.

For several reasons I need to provide the full reference of a paper which appeared at WG 2015. However I could not find the proceedings online. It should have been published in LNCS. My questions are the following.

Were the proceedings already published?
If not, when will the proceedings be published?
What can I do to get the full reference information of the paper if the proceedings are not yet out?
Is it normal for a conference to take so long to publish the proceedings?


texts: Properties of the number of copies of an NFA in each state

texts:
For an NFA $A$ with $n$ states and a word $w$, we can associate an $n$-dimensional vector $v_w$ with entries in $\mathbb{N}\cup\{0\}$ denoting the number of copies of the NFA in each state after reading $w$.

For standard NFAs, this vector doesn't have much meaning, only it's support does (e.g. for the subset construction). However, when considering certain cumulative properties of NFAs, this vector is meaningful (see example at the end of the post).

It would make sense that in an NFA, the behavior of the possible reachable vectors will be fairly "regular". Or at least have some nice properties.

  I am looking for any results concerning these vectors.

Note that this problem has some resemblance to the matrix mortality problem. Thus, it may be the case that determining whether a certain vector is reachable is undecidable.

Example of when such vectors are meaningful: consider a semantics for a weighted NFA where there are weights on the edges, and the value of a word is the sum of the edges along all the runs of the NFA. In such NFAs, the state in the middle of a run is captured by such a vector and the accumulated sum along the run so far.


texts: What algorithms do you know for beltway reconstruction?

texts:
I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of non-identical integers between 0 and N, we only have pairwise distances of points of that set mod N, How can we reconstruct the original set using this?


texts:
Are there interesting examples of "collapsing hierarchies" in computer science?

The formal definition of a hierarchy here would be a class of languages/problems/objects which is parametrized by a partially ordered set. But I am of course looking for an at least somewhat "natural" hierachy, where the parameter represents some type of resource. I am particularly interested in hierarchies where the parameter space is $\mathbb{N}$ or the $\Sigma_i/\Pi_i$ ladder. Some examples are

the polynomial hierarchy (counting alternations),
the lightface hierarchy (same),
$NC^i$ and $AC^i$,
various ways to associate languages to $k$-headed finite-state automata (as $k$ grows).

I am also happy with more complicated parameter spaces such as polynomial time languages parametrized by their time-complexity or space-complexity, if you know interesting collapsing results for them.
By collapsing I simply mean that some level of the hierarchy already contains all elements of the hierarchy. In all natural cases I can think of, either we know hierarchy does not collapse or we don't know whether it collapses. I would like to know some examples of hierarchies that do collapse. The hierarchy should be "natural", and I would prefer an example where the collapse does not happen "on the first level".
I did not carefully check that none of the hierarchies listed in What hierarchies and/or hierarchy theorems do you know? collapse, but at least it is not known to collapse for any of the ones I was familiar with, or for which this was mentioned in the answers.


texts: Inapproximability Results for APX-hard Geometric Optimization Problems

texts:
A lot of Geometric Optimization problems are NP-hard and APX-hard to approximate (No PTAS unless P=NP). One example of the geometric set cover problem can be found here. However, it is not easy to prove the lower bound (or inapproximability results) even we know a constant approximation ratio exists.

Khot showed the connection of UGC and Certain problems in geometry, especially related to isoperimetry and embeddings between metric spaces and their inapproximability results.

Guruswami et al. showed bypassing UGC from Some Optimal Geometric Inapproximability Results.

The recent breakthroughs for UGC improve a lot of inapproximability results such as Set Cover. However, I didn't find their connections with geometric optimization problems.

What are the inapproximability results for APX-hard geometric optimization problems such as geometric set cover, geometric hitting set etc. ?


texts: What is the current state of research on the representation of boolean functions using wavelets

texts:
The harmonic representation of boolean functions such as XOR or AND has been studied in different course note lectures that can be found on Google.

http://cs.mcgill.ca/~hatami/comp760-2011/

http://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf

What is the state of research on the representation of boolean functions using wavelets?


texts: The language Critical SAT is defined as the set of $CNF$ boolean formulas $f$ such that $f \in UNSAT$ but removing any  clause from $f$ makes it satisfiable. It is known that Critical SAT is $DP$-complete. I wonder about the following variant: given a $CNF$ formula $f$, is it the case that $f$ is in $UNSAT$ and that there exists some clause $c$ such that $f \setminus c \in SAT$ (instead of for all clauses, there exists a clause). Is this variant $DP$-complete as well?


texts: Decidability of diophantine equations over {=, +, gcd}

texts:
It is well-known that polynomial diophantine equations are undecidable (Hilbert's 10th problem): that is, given a quantifier-free formula over the language $\{=, +, \cdot, 1\}$ (of equality, addition, multiplication, and the constant $1$), with free variables taking values in the integers, deciding whether the formula is satisfiable is undecidable.
If multiplication $\cdot$ is replaced by the binary greatest-common-divisor (gcd) function, defined appropriately for 0 and negative numbers, does the satisfiability problem remain undecidable?

For example, the input might be a formula like
$$
a + b = c \land \gcd(a, b) = 2 \land \gcd(a, c) = 1
$$
or
$$
\gcd(a, \gcd(b, c) + b) = a + c \land \lnot (\gcd(a, b) = a).
$$
I suspect this to be a basic result in the study of decidability results for integer theories, but this came up in another context and I am not entirely familiar. From a brief literature search (see On Decidability Within the Arithmetic of Addition and Divisibility, Marius Bozga and Radu Iosif) I know of the following classical results:

The theory of $\{=, +, |\}$ (where $|$ is divisibility) allowing quantifiers is undecidable (Julia Robinson 1949).

The satisfiability of quantifier-free formulas over $\{=, +, |\}$ (i.e. existential fragment of the above) is decidable. (The diophantine problem for addition and divisibility, Leonard Lipshitz 1976.)

Divisibility can be defined in terms of gcd ($a \mid b \iff \gcd(a, b) = a$), but vice versa requires existential quantification ($\gcd(a, b) = c \iff (c \mid a) \land (c \mid b) \land \exists x \exists y.\; c = ax + by$), which won't work in quantifier-free formulas in a negated context, so at least at first glance I am not sure that gcd is equivalent to divisibility for the purposes of decidability.


texts: Indistinguishability complexity of a subset

texts:
Given set $S = \{0,1\}^n$, consider a subset $S' \subseteq S$. By determine we mean there is a deterministic TM $A_{S'}$ which always halts and defines a mapping $\{0,1\}^n \rightarrow {0,1}$ such that $A_{S'}(x) = 1$ iff $x \in S'$.

If $S_1'$ contains all even numbers in $S$, $\forall x \in S$, we can determine whether $x \in S_1'$ in polynomial time.
If $S_2'$ contains all numbers in $S$ which are smaller than $2^{n-1}$, $\forall x \in S$, we can determine whether $x \in S_2'$ in polynomial time.
If $S_3'$ contains $2^{n-1}$ randomly chosen numbers in $S$, $\forall x \in S$, intuitively, it may not be possible to determine whether $x \in S_3'$ in polynomial time using a polynomial-size TM.

Note that the set $S'$ itself is not part of the input. In this way the running time of $A_{S'}$ doesn't depend on the size of $S'$.

Intuitively, the size and running time (which have some trade-off) of the most efficient TM $A_{S'}$ (that can determine whether $x \in S'$ correctly) can be viewed as the indistinguishability complexity (defined by me) of the subset $S'$.

Question:

Is there any formal theory that exactly defines this idea?
How to measure this trade-off between the size and the running time?
For $S = \{0,1\}^{n}$, what is the subset $S'$ that has the largest indistinguishability complexity?


texts: Understanding the Physical Church-Turing thesis and its implications

texts:
Question:
Most of the applied mathematicians I know have considered Wigner's essay [3] at some point in their lives. Over time my intuition for this empirical observation of the immense progress of the mathematical sciences in the last four hundred years has been influenced by the Physical Church-Turing thesis. In fact, I would argue that the Physical Church-Turing thesis is not only compatible with Wigner's observation it actually implies that the effectiveness of mathematics in the natural sciences is reasonable.
Might such a connection between Wigner's arguments and the Physical Church-Turing thesis have been developed by either a theoretical computer scientist or theoretical physicist? One approach I have found for comparing the distinct claims of these theses is by formulating a choice of thesis as a model-selection problem, as proposed below.
Choosing between theses as a model selection problem:
In my attempts to understand the Physical Church-Turing thesis I have managed to break it into two separate statements:

Every computational process is ultimately a mathematical description of a physical process in terms of (possibly coarse-grained) state transitions.

Every physical process has a mathematical description in terms of a sequence of mathematical operations such that it may be simulated by a Turing Machine. Therefore, every physical process may be simulated by a universal computing device.

I think most theoretical computer scientists and most scientists for that matter would accept the first point as it is consistent with the Church-Turing thesis and basic principles of computer engineering. However, the second point appears to be less universally accepted as it appears to have two possible interpretations: (a) The universe is computable and therefore we may identify such a device with the universe itself. (b) The universe is computable and so we may engineer a Planck-scale computer capable of simulating the universe itself.
If the vanilla Church-Turing thesis is identified with $H_0$, the first claim of the Physical Church-Turing thesis and (2a) is identified with $H_1$(modest thesis) and the first claim of the Physical Church-Turing thesis and (2b) is identified with $H_2$(strong thesis) then I think we may frame the problem of choosing between these distinct alternatives as follows:
\begin{equation}
X = \{\text{effectiveness of mathematics in the natural sciences} \} \tag{1}
\end{equation}
\begin{equation}
H = \min_{H \in \mathcal{H}} -\ln P(X|H) \tag{2}
\end{equation}
where $\mathcal{H} = \bigcup_{i=1}^3 H_i$.
My current intuition suggests that $H_1$ is more plausible than $H_2$ as there are probably epistemic limits to knowledge discovery via the scientific method.
References:

Michael Nielsen. Interesting problems: The Church-Turing-Deutsch Principle. 2004. https://michaelnielsen.org/blog/interesting-problems-the-church-turing-deutsch-principle/
David Deutsch. Quantum theory, the Church–Turing principle and the universal quantum computer. 1985.
Eugene Wigner. The Unreasonable Effectiveness of Mathematics in the Natural Sciences. 1960.


texts: Are vertex colourings--in a sense--edge colourings?

texts:
We know that edge colourings of a graph $G$ are vertex colourings of a special graph,
namely of the line graph $L(G)$ of $G$.

Is there a graph operator $\Phi$ such that vertex colourings of a graph $G$ are
edge colourings of the graph $\Phi(G)$ ?
I am interested in such a graph operator that can be constructed in polynomial time,
i.e. the graph  $\Phi(G)$ can be obtained from $G$ in polynomial time.

Remark:  Similar question can be asked for stable sets and matchings. A matching
in $G$ is a stable set in $L(G)$. Is there a graph operator $\Psi$ such that stable sets
in $G$ are matchings in $\Psi(G)$?
Since STABLE SET is $\mathsf{ NP}$-complete and MATCHING belongs to $ \mathsf{P}$, such a
graph operator $\Psi$ (if exists) cannot be constructed in polynomial time, assuming
$\mathsf{NP}\not=\mathsf{P}$.

EDIT: Inspired by @usul's answer and @Okamoto's and @King's comments, I found a weaker form for my problem: Vertex colourings of a graph $G$ are edge colourings of a hypergraph $\Phi(G)$ defined as follows. The vertex set of $\Phi(G)$ is the same
vertex set of $G$. For each vertex $v$ of $G$, the closed neighbourhood $N_G[v]= N_G(v) \cup\{v\}$ is an edge of the hypergraph $\Phi(G)$. Then $G$ is the line graph of the hypergraph $\Phi(G)$ and therefore vertex colourings of $G$ are edge colourings of $\Phi(G)$.

Again, I am grateful for all answers and comments showing that, with or without assuming $\mathsf{NP}\not=\mathsf{P}$, the operator I am looking for cannot exist. It would be nice if I could accept all the answers!


texts:
I hope somebody knows a ref to this, so I do not have to read the literature...

Consider a sequence of numbers $x_1, \ldots, x_n$. Think about the sequence as $n-1$ intervals $[x_1, x_2], [x_2, x_3], \ldots, [x_{n-1},x_n]$. Clearly, the original sequence is bitonic if any point on the real line stabs at most 2 intervals. We will refer to a sequence where a point stabs at most $k$ intervals as being $k$-idiotic. Visually, if you draw the graph of the sequence (i.e., connect the points $p_i =(i,x_i)$ in order), then the above corresponds to the condition that no horizontal line intersects the graph more than $k$ times.

It is not too hard (but not too easy, either) to see that $k$-idiotic sequences can be sorted in $O( n \log k )$ time, which is clearly optimal.

Question: This result should be known. Do you know any appropriate ref?


texts: How useful is program search in the field of programming-language theory?

texts:
I've been thinking: computing systems such as the Lambda Calculus and its variations are usually very simple and can be implemented in as few as ~80 lines of Haskell code. There is a self-interpreter for the Binary Lambda Calculus in 210 bits.

Considering PL research mostly consists of the search of similar systems with desirable characteristics (such as being supercompilable, or capable of expressing proofs), and taking in account how information-starved those systems are, wouldn't it be interesting to use automated search techniques such as genetic programming or just breadth-first search to find those?

Has that been tried already?


texts: Johnson and Lindenstrauss lemma for hamming space

texts:
A result of Johnson and Lindenstrauss shows that a set of $n$ points in high
dimensional Euclidean space can be mapped into an $O(\frac{\log n}{\epsilon^2})$- dimensional Euclidean space such that the distance between any two points changes by only a factor of $(1\pm \epsilon).$

I am looking for reference for a similar result for Hamming space- i.e.  a set of $n$ binary vectors  can be mapped into a very low dimensional  space such that the hamming distance between any pair of vectors is approximately preserved.


texts:
Given a Boolean formula $\varphi$ over the variables $\{x_1...x_n\}$ , an assignment $T_0$ for $\varphi$ and an integer $k$, I am interested in the following question:
Does $k$ is the minimal number of bits that we have to change with respect to $T_0$ to change the value of $\varphi$? I.e. there exists an assignment $T_1$ such that $T_1$ is different from $T_0$ in at least $k+1$ different places and $T_0(\varphi) \neq T_1(\varphi)$, and for all $T$ such that $T$ is different from $T_0$ in $k$ places or less, it holds that $T(\varphi)=T_0(\varphi)$.
Edit : I suspect that this problem is in dp, but can't prove its completeness. Ideas wil be welcome


texts: Compare similar N-Dimensional vector in a database

texts:
I want to compute Euclidian distance between similar vectors in a database (SQLite).
So each column in the database is a value from my vector.

The first problem appears, I have a large number of values that I first need to reduce to fit a reasonable number of rows (<50) since the original data have thousands of columns.
I have also thought of storing a blob, load it in memory and do my computations ?

Since I am trying to find the best matches (similarity mesure), I am currently filtering the database by applying a threshold for each value. Applying a filter for a small number of column is feasible, doing this for many columns is too time consuming.

Sqlite has a RTree module limited to 5 dimensions (11 columns). But it is not the filtering that I want.

What is the best compromise or technique/algorithm to sort and compare vectors using a database ?

Thank you


texts: Hidden Constants in Complexity of Algorithms

texts:
For many problems, the algorithm with the best asymptotic complexity has a very large constant factor that is hidden by big O notation. This occurs in matrix multiplication, integer multiplication (specifically, the recent O(n log n) integer multiplication algorithm of Harvey and van der Hoeven), low-depth sorting networks and finding graph minors, to make a few. Such algorithms are sometimes called Galactic algorithms.

Note that for other algorithms, such as general sorting and integer addition, algorithms are known with optimal asymptotic complexity and small constant factors.

What research has been done in separating the former algorithms from the latter algorithms, from a theoretical perspective?

I am aware that hidden constants are often omitted to hide the distinction between different models of computation. However, I am confident that under a wide variety of different models, these Galactic algorithms will be slower than asymptotically worse algorithms for inputs of size one billion, for instance. The distinction is not subtle, in some cases. Has it been made rigorous?

For instance, one could invent a very simple model of computation, such as a von Neumann machine with a very simple ISA, and then implement the algorithms and bound their running times with explicit constants. Has this been done for a variety of algorithms?


texts: Halt means the halting set. $PSPACE^{Halt}$ is the class of problems that can be solved with polynomial memory (possibly exponential time), given a halting oracle.


texts: Nonuniform circuit families - don't have to specify for arbitrarily large, but finite, input lengths?

texts:
This is a question about nonuniform circuit families that's kind of bothering me. Let $\lbrace C_n \rbrace$ be a family of circuits for a language $L$ such that for inputs $x$ of length $n$, $C_n(x) = L(x)$. This implies that $C_n$ has to answer correctly on all inputs of the form $0y$, where $|y| \leq n-1$, right? In that case, that implies that in specifying a circuit family $\lbrace C_n \rbrace$, you can leave out arbitrary long (but finite) sequences of circuits in this (infinitary) "description", and you wouldn't have lost any part of your description.

I'm sure this is not profound in the slightest, but it does seem strange to me - that for each $n$, the circuit $C_n$ subsumes all of the $C_k$ for $k < n$.


texts: hardness of approximating the chromatic number in graphs with bounded degree

texts:
I am looking for hardness results on vertex coloring of graphs with bounded degree.

Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor of $|V|^{1-\epsilon}$ unless $\textit{NP}=\textit{ZPP}$ [1]. But what if the maximum degree of $G$ is bounded by $d$? Are there any hardness ratios of the form $d^{1-\epsilon}$ (for some $\epsilon$) in this case?

An easier question is: Hardness of approximating the edge-chromatic-number of hypergraphs when their edge size is bounded by $d$. Can we hope for a $d^{1-\epsilon}$ hardness ratio in this case? (say, for any $\epsilon >0$)

Thanks for your attention!


texts: Are there languages that are not in RE nor CO-RE?

texts:
I am familiar with the theorem which states that some languages are not in the RE (Recursively Enumerable) class of languages, but that can mean either that they are all in CO-RE (or rather, the part of it that doesn't intersect with RE), or that they are partly in CO-RE and partly somewhere else.

Are there languages about which nothing can be decided, not even what words are not in them?