texts: Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$?

texts: My understanding of the Presburger arithmetic decision problem is that it requires doubly-exponential time, but only singly-exponential space, meaning that it is in $EXPSPACE \setminus EXP$.  Obviously, if this set is not empty, then $P \subsetneq PSPACE$, solving a major open problem, so my understanding is probably wrong.  Where did my reasoning fail?


texts: Vertex Disjoint Path Covers of Hypercube-Like Graphs

texts:
This is a followup question relating to an older question I posted, namely: https://cs.stackexchange.com/questions/55213/decomposing-the-n-cube-into-vertex-disjoint-paths.

Given a graph $G = (V, E)$ and sets of distinct vertices $S = \{s_1, \ldots s_k \}$ and $T = \{t_1, \ldots t_k\}$, I am interested in finding a vertex disjoint path cover $P = \{P_1, \ldots P_k\}$ of $G$ such that each $P_i$ begins with $s_i$ and ends with $t_i$. Moreover, for $P$ to be a path cover of $G$, every vertex $v \in V$ must be part of a unique path $P_i \in P$.

In my previous question, I was interested in the case when $G = \mathcal{Q}_n$ where $\mathcal{Q}_n$ denotes the $n$ dimensional hypercube graph. It was shown by Gregor and Dvorak that such a cover exists when $P$ is balanced (in the sense that they contain the same amount of vertices from both bi-partitions of the $n$-cube), then such paths exists whenever $2k-e < n$, where $e$ is the number of pairs $(s_i, t_i)$ that form edges in $\mathcal{Q}_n$.

Now I am interested in the same problem for a graph $G = \mathcal{Q}_n - \mathcal{Q}_d$ (i.e a single copy of $\mathcal{Q}_d$ is deleted from $\mathcal{Q}_n$), for $1 \leq d \leq n$. Results were shown for the existence of Hamiltonian cycles in graphs for graphs $\mathcal{Q}_n - G$ when $G$ is an isometric tree or cycle (http://davpe.net/download/mff/bc_revised.pdf), but nothing for the problem of path covers in the desired graph class $G = \mathcal{Q}_n - \mathcal{Q}_d$. Is anyone familiar with such results?

I am primarily interested in results for $1 \leq k \leq 2$, though I would appreciate results for any $k$.


texts:
I am trying to understand to which complexity class the following problem belongs:

Exponentiating Polynomial Root Problem (EPRP)

Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients drawn from a finite field $GF(q)$ with $q$ a prime number, and $r$ a primitive root for that field. Determine the solutions of:
$$p(x) = r^x $$
(or equivalently, the zeros of $p(x) - r^x$) where $r^x$ means exponentiating $r$.

Note that, when $\deg(p)=0$ (the polynomial is a constant), this problem reverts to the Discrete Logarithm Problem, which is believed to be NP-Intermediate, i.e. it is in NP but neither in P nor NP-complete.

To the best of my knowledge, efficient (polynomial) algorithms to solve this problem  do not exist (Berlekamp and Cantor–Zassenhaus algorithms require exponential time). Finding roots to such equation can be done in two ways:

Try all possible items $x$ in the field, and check whether they
satisfy the equation or not. Clearly, this requires exponential time in the bitsize of the field
modulus;
The exponential $r^x$ can be rewritten in polynomial form, by using
Lagrange interpolation to interpolate the points
$\{(0,r^0),(1,r^1),\ldots,({q-1},r^{q-1})\}$, determining a
polynomial $f(x)$. This polynomial is identical to $r^{x}$ precisely because we are working on a finite field. Then, the difference $p(x) - f(x)$, can be
factored in order to find the roots of the given equation (using
Berlekamp or Cantor–Zassenhaus algorithms) and the roots read off the factors. However, this approach is
even worse than exhaustive search: since, on average, a polynomial
passing by $n$ given points will have $n$ non-null coefficients, even
only the input to Lagrange interpolation will require exponential
space in the field bit size.

Does anyone know if this problem is believed to be NP-intermediate as well or belonging to any other complexity class ? A reference will be greatly appreciated. Thanks.


texts: Resource-bounded variant of Kolmogorov complexity

texts:
Consider the variant of Kolmogorov complexity, where the program is only allowed to use a bounded amount of resources.  This more closely resembles the practical situation, where decompression needs to be fast.

Clearly this is decidable, since determining whether a program halts while using only a bounded amount of time or space is decidable by direct simulation.  So it seems that this problem is also decidable (by exhaustive search of all possible programs).

If the bound is to a fixed (non-constant) polynomial, then it appears that the problem is in $\text{fNP}$.  Is it NP-hard?

More generally, what is the complexity of this problem?  What properties does it have?


texts: Is it in NP to check if the convex hull contains the unit ball?

texts:
Given a set of $n$ points in $d$ dimensional Euclidean space, the problem is to determine if the convex hull contains the unit ball centered at the origin.

  Is this problem in NP?

It is in co-NP as one can give a point in the ball outside the convex hull as a witness and verify this fact using linear programming.

My focus here is not in computer precision relating to square roots although this may also be interesting.

(Related to https://mathoverflow.net/questions/141782/efficiently-determine-if-convex-hull-contains-the-unit-ball .)


texts: What's the Impact if proven NP/co-NP=PSPACE on settling P=NP? The future directions it opens to settle/attack P=NP? Remaining classes left outside?

texts:
The primary Impact i know would be that:

Polynomial Hierarchy collapses to Level 1.
NP=co-NP
NP=BPP
NP=PSPACE
BQP=NP
and so on..

What are the attack directions it will open for settling P=NP (in the sense that suppose X=Y or X!=Y is proven P=NP or P!=NP). ?


texts: Co-Partition Problem: Why is this proof for it being in NP wrong?

texts:
So I have this wrong proof that the problem "Co-Partition" is in NP. I know the proof is wrong because I've encountered it in an educational environment and was told that it's not working. I don't, however, know why.

We are given a set of natural numbers $A := \{a_{1}, a_{2}, ..., {a_{n} \}}$. The "Co-Partition"-Problem is supposed to answer the following question: Does $\sum_{a \in S} a \neq \sum_{a \in A \backslash S}$ hold true for all $S \subseteq A$?

Now suppose $PARTITION$ is a non-deterministic, polynomial algorithm that decides the Partition-Problem, which should be the complement of the "Co-Partition"-Problem as defined above.

Shouldn't this be a non-deterministic, polynomial algorithm that decides "Co-Partition"?

NON_PARTITION(J)
    bool result = PARTITION(J);
    return !result;

Why isn't this algorithm valid, therefore proving that "Co-Partition" is in NP?

Thanks for your help!


texts: Difference between time-bounded and memory-bounded Kolmogorov complexity

texts:
Let $x$ be a finite string of length $n$.

Denote by $C^t(x)$ the Kolmogorov complexity of $x$ bounded by time $t$ (i.e. the length of a minimal program that outputs $x$ and running at most $t$ steps).

Denote by $C_m(x)$ the Kolmogorov complexity of $x$ bounded by memory $m$.

Can $C^{\mathsf{poly}(n)}(x)$ be much greater than $C_{\mathsf{poly}(n)}(x)$?
It seems that the answer is "yes" but how to prove it under natural assumptions?

More accurately: let $(x_i)$ be a sequence of finite strings. Is it true that for every polynomial $p$ there exist a polynomial $q$ and a constant $c$ such that for every $x_i$ of length $n$ the following inequality holds: $$C^{q(n)}(x_i) <  C_{p(n)}(x_i) + c\log n ?$$
Does it contradict to some natural assumptions of Computational complexity theory?


texts: Recovery of preimage of hash function given part of it

texts: Suppose $m = m_1 \| m_2$ (concatenation, with $|m_1| = |m_2|$) and $h(m) = s$ (hash). Is it possible to recover the whole preimage $m$ in feasible time with non-negligible probability given $m_1$ (or $m_2$) and $s$? Is there such a guarantee that this can't be done theoretically or provided by concrete schemes such as SHA1/SHA256/SHA512, etc.?


texts: Reference request: An algebraic characterisation of LTL[XF]-definable word languages

texts:
I'm looking for a reference to the fact that LTL[XF]-definable languages (LTL where only the (strict) finally/future modality is allowed) correspond to the variety $\mathbf{R}$ (see: 1).
A similar characterisation is available for LTL[XF,XP], namely the variety $\mathbf{DA}$, see: Theorem 11 from 2.
1 Brzowoski, Fich: Languages of R-Trivial Monoids LINK
2 Tesson, P., Thérien, D.: Diamonds are forever: the variety DA LINK
PS: I have an idea how to prove it (by employing the correspondence that R = partially-ordered DFA), but before writing the result it would make sense to check whether this is already known in the literature (although I do not claim any breakthrough).


texts: automorphism in Cai-Furer-Immerman gadgets

texts:
In the famous counter example for graph isomorphism via Weisfeiler-Lehman (WL) method the following gadget was constructed in this paper by Cai, Furer and Immerman.
They construct a graph $X_k = (V_k, E_k)$ given by

$V_k = A_k \cup B_k \cup M_k \\ \text{ where } \\
\quad A_k = \{a_i \mid 1 \leq i \leq k\}, \\
\quad B_k =\{b_i \mid 1 \leq i \leq k\}, \mbox{ and } \\
\quad  M_k = \{ m_S \mid S \subseteq \{1,2,\ldots, k\},\ |S| \text{ is even} \}\\
E_k =\{(m_S,a_i) \mid  i \in S\} \cup  \{(m_S, b_i)\mid i \notin S\}$

One of the lemmas in the paper (lemma 3.1 page 6 )  states that if we color the vertices $a_i$ and $b_i$ with color $i$ then $|Aut(X_k)| = 2^{k-1}$ (color has to be preserved by the automorphism) where each automorphism corresponds to interchanging $a_i$ and $b_i$ for each $i$ in some subsets $S$ of $\{1,2,\ldots, k\}$ of even cardinality. They say that the proof is immediate. But I fail to see how even in the case of $k= 2$. In $X_2 \ (a_1, m_{\{1,2\}})$ is an edge but if we have automorphism which interchanges $a_1, b_1$ and $a_2, b_2$ the above edge gets transformed to $(b_1, m_{\{1,2\}})$ which is not an edge. So that should not be an automorphism.

I would like to understand what is my misunderstanding.


texts: Oracle separation between coNP and QMA implies oracle separation between NP and QMA

texts:
In [this] paper, Aaronson remarks (page 2, footnote) that:

  From the BBBV lower bound for quantum search [6], one immediately
  obtains an oracle $A$ such that $coNP^{A} \not\subseteq QMA^{A}$ for if there exists a
  witness state $|φ⟩$ that causes a $QMA$ verifier to accept the all-0
  oracle string, then that same $|φ⟩$ must also cause the verifier to
  accept some string of Hamming weight 1.

What stops us from modifying this argument to get a oracle separation between $NP$ and $QMA$ (using diagonalization etc)? For example, one can have an argument like the following:

  From the BBBV lower bound for quantum search [6], one immediately
  obtains an oracle $A$ such that $NP^{A} \not\subseteq QMA^{A}$ for if there exists a
  witness state $|φ⟩$ that causes a $QMA$ verifier to reject the all-0
  oracle string, then that same $|φ⟩$ must also cause the verifier to
  reject some string of Hamming weight 1.

In other words, during diagonalization, if the machine rejects with high probability in the presence of a proof for a no instance, then the machine will reject with high probability in the presence of the same proof if the oracle is changed to make it a yes instance. This is true for any proof that the prover might send (if there were a proof making the verifier accept for some string with Hamming weight 1, the same proof would also have made him accept the all 0 string: which is a contradiction as he rejects the all 0 string. Hence, no proof can make him accept some string with Hamming weight 1).

However, the second argument is nonsense as $NP^{A} \subseteq QMA^{A}$ for any oracle $A$ (and the prover can just send the verifier the right string to query when we change the oracle to a yes instance). But I cannot put a finger on where the argument is going wrong when stated as above.


texts: Support Vector Machines and privacy-preservation

texts:
suppose we have data matrix A m-by-n (m observations and n features) which I want to Apply SVM on it achieving privacy (Privacy-Preserving SVM)

the questions are:-

1 - Is applying kernel trick considered as Privacy-Preserving SVM?

2 - Is converting the data matrix into D = A.Transpose[A] and learning from *D m-by-m * considered as Applying a kernel?

thnq .. :)


texts: Can we construct a k-wise independent permutation on [n] using only constant time and space?

texts:
Let $k>0$ be a fixed constant.
Given an integer $n$, we want to construct a permutation $\sigma \in S_n$ such that:

The construction uses constant time and space (i.e. preprocessing takes constant time and space). We can use randomization.

Given $i\in[n]$, $\sigma(i)$ can be computed in constant time and space.

The permutation $\sigma$ is $k$-wise independent,
i.e., for all $i_1, \ldots, i_k$,
the random variables $\sigma(i_1), \ldots, \sigma(i_k)$ are independent and
uniformly distributed over $[n]$.

The only thing I currently know uses logarithmic space and polynomial computation time per value of $\sigma(i)$ using pseudo-random generators.

Background
I needed something like the above for some recent work, and
I ended up using something weaker:
I allowed repeated entries and verified that all the numbers that I needed
were covered (i.e., a mess).
Specifically, I got a $k$-wise independent sequence
that can be computed in $O(1)$ time and
using constant space.
It would be nice to have something simpler, or just know what is known.
Assumptions
I am assuming the unit-cost RAM model. Every word in memory/register is of size $O(\log n)$, and every basic arithmetic operation takes $O(1)$ time. I am willing to assume any reasonable cryptographic assumption (one way function, discrete log, etc).
Current thingy
As suggested by Kaveh, here is the "easy" hack that I currently have (this is quite standard): Let $\sigma(x) = \sum_{i=0}^{k+2} a_i x^i \bmod p$ be a polynomial over a prime $p$ (think about $p$ as being $n$). Here, each $a_i$ is uniformly and randomly sampled from $[p]$. It is easy to see that $\sigma(1), \sigma(2), \ldots, \sigma(n)$ is a sequence that has repetitions, but it is $k$-wise independent, and roughly $n(1-1/e)$ of the numbers of $[n]$ appear in this sequence. Note, however, that since numbers repeat in this sequence, it is not a permutation.


texts: Does a pair of disjoint homotopic cycles in the dual separate the graph?

texts: Let $G$ be a graph embedded on an orientable compact surface of genus $g$ so that the embedding is cellular. Consider the dual of the graph $G^*$. Let $C_1$ and $C_2$ be disjoint cycles in $G^*$ that are homotopic to each other and let $E_1$ and $E_2$ be their corresponding edge sets in $G$ respectively. Is $G \setminus (E_1 \cup E_2)$ a disconnected graph?


texts: Constructing FOL formula for which counting is easy?

texts:
Given a function free First Order Logic language $\mathcal{L}$ are there ways to write formulas for which counting the number of models for a given cardinality of the domain is easy (preferably exists a closed-form formula)?
An Example:
Let the language consist of a binary predicate $T$ and variables $\{x,y,z\}$, and a domain $\mathcal{D}$ consisting of $n$ elements. Are there ways to write formulas in this language such that counting the number of models for these formulas is computationally easy? A trivial example would be $\forall x, y,z  T(x,x)\land T(y,y) \land T(z,z)$, for which the number of models would be $2^{n^2 - n}$, are there more intricate ways to generate such formulas?
Additional Information:

Counting the number of models for a language with only two variables is known to be in complexity class P, whereas for more than two variables, it is known to be in #P, these results have been proven in the link below.
https://arxiv.org/abs/1412.1505
Closed forms formulas for counting any formula in FOL with 2 variables exist as well.
https://arxiv.org/abs/1804.10185


texts: Graph transformation according to some utility function

texts:
Consider an undirected graph that models a social network. Each vertex is a person, each arch represents a friendship relation between two persons.
Each arc is decorated by its average 'usage': how much, on average, the arc is used to read/send some information (ie: send my status update to my friends).

By default, the graph structure models the friendship relationship between people; but as we all know not all friends are the same: some are more important than others, and we want to receive news more reliable/faster than from others (ie: on facebook, some friends can be ignored).
An arc would be more 'used' if we receive more often news by the person associated with it.

So, from the social graph made by the 'who-knows-who' relationship, we can infer a subgraph of the 'who-ignores-who' with its dual 'who-cares_about-who'.

The problem that I'd like to solve is how to split/transform the original 'who-knows-who' graph into the two described sub-graphs as clusters, such as the arcs between these 2 clusters is minimal.

Is this problem tractable ?
Can it be reduced to the 'min-bisection' (or similar NP-hard) problems ?

thanks,
valerio


texts: Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space?

texts:
Consider language $ \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} $.

It is known that $ \mathtt{EQUALITY} $ cannot be recognized by any sublogarithmic-space alternating Turing machine (ATM) (Szepietowski, 1994). (There is an ATM using sublogarithmic space for members but not for all non-members!)

On the other hand,  Freivalds (1981) showed that bounded-error constant-space probabilistic Turing machines (PTMs) can recognize $ \mathtt{EQUALITY} $ but only in exponential expected time (Greenberg and Weiss, 1986). Later, it was shown that no bounded-error $ o(\log\log n) $-space PTM can recognize a non-regular language in polynomial expected time (Dwork and Stockmeyer, 1990). My question is

  whether poly-time sublogarithmic-space PTMs recognize $ \mathtt{EQUALITY} $ with bounded-error.


texts:
Is there a way to prove the following theorem in Coq?

Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2.

EDIT: An attempt to give a brief explanation for "what proof irrelevance is" (correct me someone if I am wrong or inaccurate)

The basic idea is that in the proposition world (or the Prop sort in Coq), what you (and you should) really care about is the provability of a proposition, not the proofs of it, there may be many (or none). In case you have multiple proofs, from the provability point of view, they are equal in the sense that they prove the same proposition. So their distinction is just irrelevant. This differs from the computational point of view where you really care about the distinction of two terms, e.g., basically, you don't want the two inhabitants of the bool type (or Set in Coq's words), namely true and false to be equal. But if you put them in Prop, they are treated equal.


texts:
This is inspired by this question. Let $\mathcal{C}$ be the collection of all combinators which only have two bound variables. Is $\mathcal{C}$ combinatorially complete?

I believe the answer is negative, however I was not able to find a reference for this. I would also be interested in references for proofs of combinatorial incompleteness of sets of combinators (I can see why the set $\mathcal{D}$ consisting of combinators with only one bound variable is incomplete, so these sets ought to contain more than just elements of $\mathcal{D}$).


texts:
Motivation: In standard augmenting path maxflow algorithms, the inner loop requires finding paths from source to sink in a directed, weighted graph.  Theoretically, it is well-known that in order for the algorithm to even terminate when there are irrational edge capacities, we need to put restrictions on the paths that we find.  The Edmonds-Karp algorithm, for example, tells us to find shortest paths.

Empirically, it has been observed that we might also want to find fat (is there a better term for this?) paths.  For example, when using capacity scaling, we find shortest paths that can bear at least $\epsilon$ amount of flow.  There is no restriction on how long the path can be.  When we can no longer find any paths, we decrease $\epsilon$ and repeat.

I am interested in optimizing the choice of augmenting paths for a very specific application of max-flow, and I want to explore this tradeoff between short and fat paths.  (Note: it is not necessary for me to always solve the problem.  I am most interested in finding the largest lower bound on flow in the shortest amount of wall time.)

  Question: Is there a standard way to
  interpolate between the shortest path
  approach and the capacity-scaling
  approach?  That is, is there an
  algorithm for finding paths that are
  both short and fat, where ideally some
  parameter would control how much
  length in the path we are willing to
  trade off for fatness?  At the extremes, I'd like to be able to recover
  shortest paths on one end and capacity scaling-style paths on the other.


texts: More elementary proof of coloring theorem for d x d^2 rectangles

texts:
The following is known: For all $c$, for all $c$-colorings of $N\times N$ there exists a $d \times d^2$ rectangle ($d \ge 2$) such that all four corners are the same color.

The proof uses the Poly-Hales-Jewitt theorem.

I seek an easier proof. Okay to use Van der Waerden's theorem (VDW) or poly VDW or Gallai-Witt theorem.


texts: Is contextual equivalence of a language with `quote`-`eval` trivial or not?

texts:
In [1], Mitchell Wand demonstrated that adding fexprs to the pure lambda calculus trivializes the theory of contextual equivalence, meaning two terms are contextually equivalent iff they are $\alpha$-congruent.  When exploring related work, he went "our result extends an old observation of Albert Meyer [2] that evaland quote render contextual equivalence trivial".  But referring to [2], what could be found is only the following statement by Meyer:

  I ﬁrst thought that in languages with a quote-eval feature such as LISP [3] there was no type distinction between syntactic and executable objects.  In fact quote-eval seems safe enough in LISP because, although quote syntactically looks like a bona ﬁde operator, like say cond, it really doesn’t behave like one (it only has behavior at parse time, not run time, e.g., one can't pass quote as a parameter to a procedure).  Still, I have yet to see convincing examples where the quote-eval feature was worthwhile.

Regardless of one minor flaw in these comments that may mislead the reader to infer that cond could be passed as a parameter to a procedure.  If I understand correctly, what Meyer said "quote-eval seems safe enough" means that quote-eval may not trivialize the equational theory, although he did not offer a proof.

EDIT:

As suggested by Martin, since all the three papers cited dealing with LISP family languages, let's put the question under this same setting.  Is contextual equivalence of a language with quote-eval, in particular LISP, on earth trivial or not?

[1] Mitchell Wand, The Theory of Fexprs Is Trivial.  Lisp and Symbolic Computation 10(3): 189-199 (1998).

[2] Albert Meyer, Puzzles in Programming Logic  Workshop on Formal
Software Development. 1984

[3] John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Communications of the ACM in April 1960.


texts:
There are quite a lot papers describing near-linear algorithms. They are usually iterative, with linear complexity of one iteration. Others have $O(n\log^k n)$ time compexity.

I'm failed to find a decent source with the definition of "near-linear" time, which covers both types. Please, help me find one.


texts: Are there families of formal languages known to be truly PAC learnable?

texts:
I specifically mean language families that admit arbitrarily long strings -- not conjunctions over n bits or decision lists or any other "simple" language contained in {0,1}^n.

I am asking about "automata-theoretic" regular languages as opposed to "logic-theoretic" ones: something like the piecewise testable languages, start-height-zero languages, locally testable languages, that sort of thing. The relevant complexity parameter n is the size of the minimal accepting DFA. So, succinctly put: is there an interesting family of n-state DFAs that is known to be efficiently PAC learnable?


texts: Approximating $\textrm{AC}^{0}$ by sparse polynomials

texts:
Let $f$ be a Boolean function from $\{0,1\}^{n}$ to $\{0,1\}$.
We say that $f$ is randomly approximated with error probability $\epsilon$
by a family of polynomials $P$ if
\begin{equation}
\forall x\in\{0,1\}^{n}\Pr_{p\in P}[p(x)=f(x)]\geq1-\epsilon
\end{equation}

It is known that if $f:\{0,1\}^{n}\rightarrow\{0,1\}$ is computed
by an $s$ size bounded and $d$ depth bounded circuit of unbounded
fan-in, then $f$ can be randomly approximated with error probability
$\epsilon$ by a family of polynomials of degree $O(\log^{d}(\frac{s}{\epsilon})\cdot\log^{d}(s))$.

If $f$ can be computed by an $\textrm{AC}^{0}$ circuit then $s$ is polynomially
bounded by $n$ and $d$ is constant, hence $f$ can be randomly approximated
with constant error probability by a family of polynomials of degree
$\textrm{poly}(\log(n))$, which is low degree.

The number of monomials in these approximating polynomials may still be quasi-polynomial though.

What
if we want to approximate such $f\in\textrm{AC}^{0}$ by not low degree polynomials
but by family of polynomials which are sparse? Here, by sparse we would ideally
mean that number of monomial is something like $\textrm{poly}(n)$.

  Can we find a family
  of sparse polynomials $P$ such that such $f$ is randomly approximated
  with error probability $\epsilon$ by $P$ ?

  If not for $\textrm{AC}^{0}$,
  what are other non trivial class of functions which can be approximated
  by families of sparse polynomials.


texts: Complexity of approximating a real function using queries

texts:
Consider the following computational problem, where $I$ is the real interval $[-1,1]$:

There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of the kind: "Given $x\in I$, what is $f(x)$?". Let $x_0$ be an element of $I$ such that $f(x_0)=0$ (if it exists). Your goal is to find a value $x$ such that $|x-x_0|<\epsilon$. How many queries do you need, as a function of $\epsilon$?

All real numbers have infinite precision, as in the Real RAM model. It is allowed to do arbitrary computaitons on such real numbers - the only costly operations are the queries.
Here, the solution is simple: using binary search, the interval in which $x$ can lie shrinks by 2 after each query, so $\log_2(1/\epsilon)$ queries are sufficient. This is also an upper bound, since an adversary can always answer in such a way that the possible interval for $x$ shrinks by at most 2 after each query.
However, one can think of more complicated problems of this kind, with several different functions and possibly different kinds of queries.
What is a term, and some references, for this kind of computational problems?
Related posts in other sites:

First posted on cs.stackexchange.
This MathOverflow post is related, but there it is required to use a finite number of registers with a finite precision.


texts: Which version of KAKUTANI does lie in PPAD?

texts:
The seminal paper of Papadimitriou [1] claims that the computational search problem KAKUTANI is $\mathbf{PPAD}$-complete. Unfortunately, there are very few details. Many other papers and surveys cite this claim but I never found a formal proof. I think that there is a caveat in the "in $\mathbf{PPAD}$" part.

Recall the formulation of the Kakutani theorem: Let $S$ be a non-empty, compact and convex subset of Euclidean space and $F$ be an upper hemicontinuous set-valued function from $S$ to $2^S$ with non-empty and convex values. Then there exists a fixed point, i.e., $x$ such that $x\subset F(x)$.

When we deal with a computational version, first of all, $F$ must be somehow succinctly defined. But also we may hope to find only an approximate solution. And here comes the caveat.

We may try to find a strong approximation, i.e., a point $x$ in $\epsilon$ vicinity of some fixed point $x^*$. Such a problem would be complete in $\mathbf{FIXP}$ (see [2]) and thus is believed to be harder than $\mathbf{PPAD}$.
We may try to find a weak approximation, i.e., a point $x$ such that $|F(x)-x|<\epsilon$. This kind of approximation is typical for $\mathbf{PPAD}$ and is used in problems like BROUWER, NASH, EXCHANGE EQUILIBRIUM etc. The caveat is that in Kakutani theorem sometimes there are no such points besides the exact solution. (A trivial example: $F\colon [0,1]\to [0,1]$, $F(x)=1$ for $x<a$, $F(x)=0$ for $x>a$, $F(x)=[0,1]$ for $x=a$).

So, my question is the following: does the search for a weakly approximate fixed point lie in $\mathbf{PPAD}$ when $F$ is a general succinctly defined set-valued function? (And thus if an $\epsilon$-fixed point is single then it must be simple). Or must we narrow the domain to something like partially linear functions? I believe, this is sufficient for applications but does not have the specified issue.

[1] C. H. Papadimitriou. “On the Complexity of the Parity Argument and Other
Inefficient Proofs of Existence”. In: J. Comput. Syst. Sci. 48.3 (1994),
pp. 498–532.

[2] K. Etessami and M. Yannakakis. “On the complexity of Nash equilibria and
other fixed points”. In: SIAM Journal on Computing 39.6 (2010), pp. 2531–
2597.


texts: Applications of topology to computer science

texts:
I'd like to write a survey on the applications of Topology in Computer
Science. I plan to cover the history of topological ideas in Computer
Science and also highlight a few current developments.  It would be
extremely helpful if anyone could give input regarding any of the
questions below.

Are there any papers or notes that describe the chronology of the
use of topology in Computer Science?
What are the most important application of results in Topology to
Computer Science?
What are the most interesting areas of current work that use
topology to gain insight into computation?

Thanks!


texts:
I've been reading Nielson & Nielson's "Semantics with Applications", and I really like the subject. I'd like to have one more book on programming language semantics -- but I really can get only one.

I took a look at the Turbak/Gifford book, but it's too long-winded; I thought Winskel would be fine, but I have no access to it (it's not in our University library, and I'm short on money), and I'm not even sure if it's not dated. Slonneger seems OK, but the practical part makes it somewhat too long, and I'm not very comfortable with his style.

So my question is -- is Winskel a good book? And is it dated?

Also, are there other concise books on the subject?


texts: What is the fastest deterministic algorithm for incremental DAG reachability?

texts:
As the title. The incremental algorithm maintains the reachability information  of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if node u reaches node v) time.

It takes amortized O(n) time for each edge insertion (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) on general directed graphs. Is it possible to do it faster on DAGs?


texts: Lower bound for NFA accepting 3 letter language

texts:
Related to a recent question (Bounds on the size of the smallest NFA for L_k-distinct) Noam Nisan asked for a method to give a better lower bound for the size of an NFA than what we get from communication complexity bounds. What follows is a special version of that problem.

Suppose $L$ is a language over some $n$ letter alphabet whose words all have length $3$. Denote the size of the smallest NFA accepting $L$ by $NFA(L)$. Define an $n\times n^2$ matrix $M$ as $M(a;bc)=1$ if $abc\in L$ and otherwise $0$. Denote the minimal number of $1$-submatrices (submatrix that contains only $1$'s) covering all the $1$'s in matrix $M$ by $COV(M)$. (So $\log(COV(M))$ is the non-deterministic communication complexity of $M$.)
It is easy to see that $NFA(L)\ge COV(M)$. If we similarly define a matrix $N$ as $N(ab;c)=1$ if $abc\in L$ and otherwise $0$, then we also have $NFA(L)\ge COV(N)$.

Is there an $L$ for which $NFA(L)>COV(M)+COV(N)?$

By what function of $COV(M)$ and $COV(N)$ can we upper bound $NFA(L)?$


texts: How "hard" is it to maximize a polynomial function subject to linear constraints?

texts:
General Problem

Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following optimization problem?

\begin{align*}
 \text{Maximize} & \;\; f(\mathbf{x}) \\
  \text{Subject to: } & \;\, \ell_i(\mathbf{x}) \le 0\text{ for all } i
\end{align*}

We can assume that the region determined by the constraints is bounded.

Related, but More Specific, Problem

Suppose we have a bounded polytope (represented as the intersection of a set of linear inequalities).
I want to compute the maximum volume of an (axis parallel) hyperrectangle completely contained in the polytope. What is the complexity of solving this problem?

Help on either of these problems is greatly appreciated.


texts: Partition planar graph into connected subgraphs of equal size

texts:
Work

Jünger, Michael, Gerhard Reinelt, and William R. Pulleyblank. "On partitioning the edges of graphs into connected subgraphs." Journal of graph theory 9.4 (1985): 539-549.

states that for 4-edge-connected graph one can partition its edges into disjoint subsets of size $r$, such that each subset form a connected subgraph.

I wonder if the same kind of statement could be formulated for partition of vertices.
For what kind of graphs one find partition of vertices into disjoint subsets of size $\approx r$, such that each subset form a connected subgraph (for each r)? I'm particularly interested in planar graphs, but would be happy with any class.

I can soften some conditions (it will still meet my needs): for what graph classes existence of partition into less than $\frac{\alpha n}{r}$ connected subgraphs of size less than $r$ is guaranteed (for some $\alpha$)?


texts: Minimising the root-set of a spanning hyperforest of a hypergraph

texts:
I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a $k$-hypergraph. I describe the relevant definitions for hypergraphs below, but the following is the problem on

  SPANNING HYPERFOREST ROOT SET. For a directed hypergraph $D$ and an integer $k \geqslant 1$, determine whether there exists a spanning hyperforest for $D$ which has a root-set of size at most $k$.

Remarks.

It is not difficult to show that SPANNING HYPERFOREST ROOT SET is in NP: in particular, if a root-set of the suitable size is provided, then a spanning hyperforest with that root-set can be found in polynomial time.
It is also trivial to find a value of $k$ for which $(D,k)$ is a YES instance: for instance $k = \lvert V(D) \rvert$ (in which case the empty hypergraph is a spanning hyperforest with root set $k$).
Considered as an optimisation problem, it is usually easy to find values $k < \lvert V(D) \rvert$ for which $(D,k)$ remain YES instances, though it is not clear how easily one can find the optimum.

Question.

Is SPANNING HYPERFOREST ROOT SET also NP-hard? Is this true in the special case where the input hypergraph is "symmetric", in the sense that for any edge $e = (t(e), h(e))$ and for any $v \in s(e) := t(e) \cup h(e)$, there is also an edge $e' = (s(e) {\,\smallsetminus\,} \{v\}, v)$?

Relevant definitions.

In the following, I am broadly following the definitions of "Flows on hypergraphs" [free PDF link] by Cambini, Gallo, and Scutellà.

A hypergraph is a pair $G = (V,E)$, where $E \subseteq \mathcal P(V)$. If each $e\in E$ has the same cardinality $k$, we call $G$ a $k$-uniform hypergraph (or $k$-hypergraph).
A directed hypergraph is a pair $D = (V,E)$, where in our setting we let $E \subseteq \mathcal P(V) \times V$ be the set of hyper-edges. For each edge $e \in E$, we let $t(e) = \pi_1(e) \subseteq V$ be the "tail" of the edge, and $h(e) = \pi_2(e) \in V \smallsetminus t(e)$ be the "head" of the edge. Thus we consider hypergraphs where each edge has exactly one head (more general definitions are common).
We may associate a "symmetric" directed hypergraph $D_G = (V,E')$ of this sort to any hypergraph $G = (V,E)$, by replacing each undirected edge $e \in E$ with a collection of directed variants $E'_e = \{ (e{\,\smallsetminus\,} v, v) \,\vert\, v \in e \}$ and letting $E' = \bigcup_{e \in E} E'_e$.
A directed cycle in a directed hypergraph $D = (V,E)$ is just a vertex sequence $(v_0,v_1,\ldots,v_\ell)$ for which $v_{i+1} \ne v_i$ for $0 \leqslant i < \ell$, $v_0 = v_\ell$, and for which for each $0 \leqslant i < \ell$ there is an edge $e_\ell$ for which $v_i \in t(e_i)$ and $v_{i+1} = h(e_i)$.
A hyperforest is a directed hypergraph in which all vertices have in-degree either zero or one, and which has no cycles in the above sense. (N.B. I am diverging here from the terminology in my reference above, which does not explicitly consider whether the hypergraph is connected; but this cannot be taken for granted in my setting.) The set of nodes of in-degree zero we call the "root set" of the hyperforest.
A spanning hyperforest $T$ for a directed hypergraph $D = (V,E)$, is simply a subgraph $T \subseteq D$ of the hypergraph which contains all of the vertices $V$ and which is a hyperfohrest.


texts: Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?

texts:
If we can prove that  $\mathsf{L}=\mathsf{P}$, does it imply that $\mathsf{NL}=\mathsf{NP}$ ?

I thought it is the case, but I cannot prove it (also for the converse).


texts: Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures

texts:
I've been trying to understand Bits-back coding (Frey, B. J., and G. E. Hinton. 1997.) a bit more (pun intended), which can be used to encode data with latent variable models. This tutorial by Pieter Abbeel et al. sums up the procedure with an example which I present below, but with an explicit auxiliary variable (i.e. I added the variable $k$).
Consider a mixture of Gaussians where $i$ indexes the Gaussian from which the data $x$ is sampled; $p(x\vert i) = \mathcal{N}(x|\mu_i, \sigma^2_i)$. Assume, although possibly intractable, the true posterior $p(i \vert x, k)$ is available from which it is possible to sample and encode values $i$, where $k \sim p(k)$ is some auxiliary information used to sample $i$. Note that $k$ is used solely in the process of selecting $i$, therefore $k \rightarrow i \rightarrow x$ forms a Markov chain and $p(x \vert i, k) = p(x \vert i)$
Given a data point $x$ to compress, bits-back coding then proceeds to

Sample $k$ from $p(k)$
Sample $i$ from $p(i \vert x, k)$
Encode $i$ with a prior $p(i)$, resulting in code-length $\log_2(1/p(i))$
Encode $x$ with $p(x \vert i)$, resulting in code-length $\log_2(1/p(x \vert i))$
Although $i$ was encoded with $p(i)$, given that we know $p(i \vert x, k)$, it is possible to get "bits back" (hence the name) by reconstructing $k$.

My goal is to understand this concretely, since most tutorials I've found stop here and never actually give an example. Hence, consider the following:
Say there are 4 modes (Gaussians) of the mixture represented by $i \in \{0, 1, 2, 3\}$ and $k \in \{0, 1\}$. For a given point $x_o$, assume the given values for $p(i \vert x_o, k)$ and $p(i)$, as well as the code used to represent them from a binary alphabet, are the following:
$$\begin{array}{c|c|c}
i & p(i) & \text{code-word} \\ \hline
0 & 1/4  & 00 \\
1 & 1/4  & 01 \\
2 & 1/4  & 10 \\
3 & 1/4  & 11 \\
\end{array}$$
$$\begin{array}{c|c|c}
k &i & p(i \vert x_o, k) \\ \hline
0 & 0 & 1/2 \\
0 & 1 & 1/4 \\
0 & 2 & 1/4 \\
0 & 3 &   0 \\
1 & 0 &   0 \\
1 & 1 & 1/2 \\
1 & 2 & 1/4 \\
1 & 3 & 1/4
\end{array}$$
I've conveniently made the symbols I.I.D. with dyadic probability mass functions, therefore making traditional Huffman Coding optimal.
On the receiving end, if $i=0$, surely $k=0$ since $p(i=0 | x_o, k=1) = 0$. Similarly, $i=3$ implies $k=1$. In general:
$$\begin{array}{c|c|c}
i & p(k=0 \vert x_o, i) & p(k=1 \vert x_o, i) \\ \hline
0 &   1 &   0 \\
1 & 1/3 & 2/3 \\
2 & 1/2 & 1/2 \\
3 & 0 & 1
\end{array}$$
Therefore, we are able to recover $k$ to some extent.
I have 2 questions:

is this the bits-back coding scheme or am I missing something?
For $i=0$ and $i=3$ we can recover $k$, but for $i \in \{1, 2\}$ all we have are the probabilities over $k$. How do we get these bits-back?


texts: Prior work on finding domain-theoretic suprema of equivalent total functions?

texts:
In slightly more down-to-earth terms, this question is sort of about lazy evaluation in functional programming - except that it's more ambitious in general than just seeking what a typical Haskell programmer would consider "least-strict". If the previous sentence made no sense to you, don't worry, ignore it.

In domain theory, we examine posets, and for the purposes of this question we will consider a poset to represent the set of possible partially-specified values of a type in a non-strict programming language, such that two partial values $x$ and $y$ are ordered as $x \sqsubseteq y$ iff $y$ is $x$ "plus zero or more extra bits of information". In other words, $x \sqsubseteq y$ iff y is a version of $x$ where zero or more of the "holes" or "thunks" (if any) have been filled in.

We can (and do) extend this partial order to Scott-continuous functions, by stipulating that $f \sqsubseteq g$ iff for all $x$, $f(x) \sqsubseteq g(x)$.

However, note that in the case of Scott-continuous functions, $f$ can be $\sqsubseteq$ $g$ even if $g$ is distinguishable from $f$ but does not provide any extra information. This can be the case if $g$ provides the same information "more parsimoniously" (or "more lazily", depending on how you want to look at it).

My question is this: If $f$ is a Scott-continuous computable function, and is "total" (i.e. the elements of its domain are all finite, and it takes "fully-defined" values to "fully-defined" values), have techniques been developed for computing a maximal $h$ such that $f \sqsubseteq h$?

Of course, if the domain of $f$ is a finite set, one can just represent $f$ as a lookup table and then use elementary deduction to compute $h$. It's not necessarily efficient in practice, but it yields the correct answer. But what about functions over infinite domains?


texts: Is uniform RNC contained in polylog space?

texts:
Log-space-uniform NC is contained in deterministic polylog space (sometimes written PolyL).  Is log-space-uniform RNC also in this class?  The standard randomized version of PolyL should be in PolyL, but I don't see that (uniform) RNC is in randomized-PolyL.

The difficulty I see is that in RNC, the circuit can "look at the random bits" as much as it wants; i.e., the random inputs can have arbitrary fanout.  But in the randomized version of PolyL, it's not like you get a tape of random bits you get to look at as much as you want; rather, you are only allowed to flip a coin at each time step.

Thanks!


texts: Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$

texts:
1) What classes contain $\textbf{PSPACE}$, are contained in $\textbf{EXP}$ and (presumably) are not equal to $\textbf{PSPACE}$ nor to $\textbf{EXP}$?

A possible class satisfying this requirement: the class of languages that can be recognized in exponential time and subexponential memory.

2) Which of these classes are provably strictly larger than $\textbf{P}$?


texts: What are the most effective algorithms to find random number?

texts: I was reading the Ramsey's Theory stating "complete disorder is impossible". Is there any algorithm to generate random numbers for a long period of time without there being any relation from one set of random numbers to any other set?


texts: Palindrome language and Finite Automata Machines

texts:
I'm a grad student in math. I'm unaware of available literature in theoretical computer science, so require suggestions for books. Here are the two topics I'm interested in exploring.

1) A complete treatment of palindrome language with reference to finite automata, particularly interested in how a probabilistic finite automate would recognize palindrome language.

2) A thorough treatment of context-sensitive languages. Introductory books don't discuss it in details as it is perhaps not a topic to be studied in a first course.

it appears that introductory books have rather sketchy discussions of the topics, mostly end of chapter problems. Any suggestion is greatly appreciated.


texts: Monotone supermodular function minimization under partition matroid constraints

texts:
Is there a known approximation algorithm for the problem of minimizing
a monotone (non increasing) supermodular function under partition matroid constraints ?


texts: Number of simple paths between two vertices in a DAG

texts:
Let $G = (N, A)$ be a connected acyclic digraph (DAG). Furthermore, let $s \in N$ and $t \in N$ be two vertices on this graph, such that $t$ is reachable from $s$.

My problem is: how many simple $s-t$ paths exist on this DAG?
Most precisely, how can we write a function on the number of nodes $|N|$ which is an upper bound for the number of simple $s-t$ paths in $G$?

I'm aware that exists a polynomial-time dynamic programming algorithm that counts the number of such paths (see here) and that is an enumeration problem. This algorithm is #P-Complete on general digraphs, but is in $P$ for DAGs, as pointed out by @Joshua Grochow in the comments.

I'm also aware that this number is exponential on the size of the longest $s-t$ path.
However, I don't see a relation between this function and the number of nodes in the graph.

Thanks in advance :)


texts: Polynomial evaluation at all different points

texts:
I have a polynomial $f(x_1,\ldots,x_{50})$ of 50 variables over binary field $GF(2)$. I want
to evaluate at all $2^{50}$ points and check how many of them are 0.  Ofcourse we can evaluate at all points and check them. Can we do faster than this using some memory?


texts:
The topic says it all - I've been seeing this referenced a few times in information theory literature (Feedback in the non-asymptotic regime, Y. Polyanskiy et. al. among others), oftentimes making mentions to an article by a guy called Goppa. I've not seen it defined in any of the referencing articles and the article is nowhere to be found online.

So, can anyone tell me what it is? A reasonable guess would be that it relates to information density, i.e. $i(x;y) = \log \frac{p(x,y)}{p(x)p(y)}$, but it's hard to say.

EDIT: There seems to be consensus as to what it SHOULD mean at least, i.e. basically the average information density, i.e. $\sum \log \frac{p(x_i,y_i)}{p(x_i)p(y_i)}$ where we're summing over observations. Not going to accept however as I am looking for a definite statement.


texts:
Consider the following problem: given a CNF formula and an assignment that satisfies this formula, is there another satisfying assignment for this formula ?

What is the complexity of this problem ? (It most surely is in NP, but is it also NP-hard ?)

What if you are not given the assignment and you just want do decide whether the formula has a unique satisfying assignment ?

Thanks.


texts:
Sudoku is a well-known puzzle that is NP-complete. Binary Sudoku is a variant that only allows the numbers $0$ and $1$. The rules are as follows.

Each row and each column must contain an equal number of zeros and ones.
Each row and each column is unique.
No row or column contains consecutive triples of zeros or ones ($1 1 1$ is a consecutive triple of ones).

The input is a $N \times N$ square partially filled with zeros and ones. To solve the puzzle, each cell in the $N \times N$ square must be filled by either $0$ or $1$ while respecting the above rules. I was not able to find any intractability result for solving the Binary Sudoku puzzle.

  How hard is solving the Binary Sudoku puzzle? Is it NP-complete?

Also, I'm interested in the complexity of a related problem.

Given a fully filled $N \times N$ square that respects only rules 1 and 2 above,

  how hard is it to find a permutation of rows and columns such that the resulting square respects rule 3?


texts:
We all know that the minimal complexity of a comparison-based sorting algorithm is $\Omega(n \log n)$ comparisons. I'm trying to do a blind sort, i.e. given a number $n$ output a circuit (with boolean, arithmetic and "comparison" gates) that sorts a list of $n$ items.

Precomputing all ${n \choose 2}$ comparisons and then doing arithmetic on the resulting bits gets me an $\Theta(n^3)$ algorithm, however by some crazy "pointer arithmetic" I think I can get a $\Theta(n^2)$ version.

Is there a known lower bound for comparison-based sorting circuits along similar lines to the $n \log n$ one for comparison-based sorting algorithm? Might it even be possible to blind sort in $n \log n$ time?


texts: Is there any notion of sensitivity for probabilistic Boolean functions?

texts:
Sensitivity is defined here. Denoting the neighbors of $x$ in the Boolean cube as $N(x)$, we define the sensitivity to be $s(f, x) = \sum_{y \in N(x)} I(f(x) \neq f(y))$, where $I$ is $1$ if the statement inside is true, $0$ otherwise. I'd imagine that you could do the same thing but instead of the indicator function use the probability and a lot of the results from that paper could still go through but in a probabilistic way.

I'm mostly just curious if anyone has looked at this before, as I think the notion I stated works just fine, but if anybody has an alternative notion or a problem with my candidate I'd be interested in that.


texts: Is there a better than brute-force solution to the shortest simple path problem?

texts:
Given as input graph which can possibly contain negative weight cycles, we can still ask for the weight of the shortest simple path between two vertices (i.e., a path that does not visit any vertex more than once)

As explained in Finding the shortest path in the presence of negative cycles, this problem is NP-hard. But I couldn't find any concrete upper bound anywhere.

Is there an algorithm that improves over the brute-force way of enumerating all simple paths and keeping the one with the minimum weight?


texts: Probability that a random sorting network works

texts:
Given $n$ inputs $x_0, \ldots, x_{n-1}$, we construct a random sorting network with $m$ gates by iteratively picking two variables $x_i, x_j$ with $i < j$ and adding a comparator gate that swaps them if $x_i > x_j$.

Question 1: For fixed $n$, how large must $m$ be for the network to correctly sort with probability $> \frac{1}{2}$?

We have at least the lower bound $m = \Omega(n^2 \log n)$ since an input that is correctly sorted except that each consecutive pair is swapped will take $\Theta(n^2 \log n^2)$ time for each pair to be chosen as a comparator.  Is that also the upper bound, possibly with more $\log n$ factors?

Question 2: Is there a distribution of comparator gates that achieves $m = \tilde{O}(n)$, perhaps by choosing close comparators with higher probability?


texts: min hitting set of every base of a matroid

texts:
We are given a matroid. Our goal is to find a set of elements of minimum size that has non-empty intersection with every base of the matroid.
Is the problem studied before? Is it in P?
For example, in a spanning tree matroid, the minimum hitting set should be a minimum cut. Thanks.


texts: Meaning of program as solution of a recursive equation

texts:
I would like to ask you a question about (denotational?) semantic of program. After defining program as a transition system, and the semantics as a transition function: $$next: States \rightarrow States$$
the author stated that the meaning of program is the solution of the equation:
$$ P = next \circ P $$
which is given by:
$$ fix(\lambda f.next \circ f) $$
I could not get the idea here, what is the "meaning"? and why it is the solution of that equation? How it is related to Tarski's fixpoint theorem?

Could anyone explain for me or give me some references to read about it?
Thanks in advance.


texts: What's the nature of hypercomputing and relativity?

texts: Somewhere I read something like "a hypercomputer rotating around a rotating black hole" would have some esoteric properties e.g. would produce other answers than other hypercomputers and other computing. Is there any support for this, do I remember incorrectly, or is this claim known to be nonsense?


texts: Is there a way to detect search engine bias?

texts:
Search engines are increasingly being relied on as information gatekeepers, yet the criteria used by search engines to rank results is opaque to users. How can users be sure their results aren't biased or tampered with in some way to benefit some interest at the expense of search result quality?

Governments routinely demand that search providers remove or lower the ranking of websites deemed politically undesirable. Businesses may pay providers to boost certain results over others to increase their revenues. Firewalls may meddle with results before they're transmitted back to users.

Even seemingly innocuous changes to ranking algorithms that might not on the surface appear to be biased, could actually be deviously designed to harm websites that share some common attribute (unrelated to actual quality).

Is it possible to detect search engine bias, by say monitoring results over a period of time and evaluating whether some "hidden variable" (perhaps a political affiliation) is a driving factor in the change in website rankings?

A sneaky provider may gradually over time lower the ranking of targeted websites (and perhaps random websites as well to distract users). What are the limits on how much bias a provider can introduce without detection? Or is it possible to always conceal such interference by deviously selecting weighted ranking criteria that incidentally produce the intended result (by way of "data snooping").

Does any of this change if the ranking criteria is made public? Do we need to open-source the criteria search engines use?

This reminds me of the result that detecting whether or not a complex financial instrument such as a CDO has been tampered with by the seller is equivalent to solving the densest-subgraph problem:

http://www.cs.princeton.edu/~rongge/derivative.pdf

Thanks!


texts: Is it decidable that a computable analytic function over $\mathbb{R,C} ,$ equals $0$

texts:
Is it decidable whether a computable analytic function $f(x_1,x_2,\dots,x_n)$ over $\mathbb{R}$, $\mathbb{C}$  in a semi-algebraic or semi-analytic domain is identically zero? Is there any algorithm?

Also, I am wondering under what condition regarding the domain of the function, can it be decidable that $f$ is identically zero?


texts:
The subset sum problem is NP Complete. I was wondering if the following variation can be proved to be NP Complete :

The cardinality of set of integers is $m$.
And each element of the set is between $1$ and $m^2$. Repetitions are allowed.
The objective is to find a subset that would sum up to a given sum.

This seems to be as hard as the subset sum itself, but i cant come up with a reduction that would prove my conjecture.


texts: On the properties of a family of submatrices

texts: Let $n$ and $k \le n/2$ be positive integers, and consider a family $\mathcal{F}$ of $k\times k$ sub-matrices of an $n\times n$ matrix such that every two elements of $\mathcal{F}$ intersect. What non-trivial (I know I'm already annoying people by this term) properties of $\mathcal{F}$ one could claim? (in particular related to its cardinality).


texts: Is that particular case of the "minimum weight solution to linear equations" still NP-complete?

texts:
We in our research group are working in the application of heuristic methods to the inverse illumination problem (that is, given a set of constraints about the illumination conditions in a scene, find the places where the light sources have to be placed and their intensities in order to fulfill the constraints and minimize the cost). We would like to justify the use of heuristic methods by proving the problem to be NP-hard and we have found it to be closely related to the "minimum weight solution to linear equations" (MWSLE) NP-complete problem of Garey and Johnson's "Computers and intractability", with the particularity that, given that light source emittances can not be negative, the solution to the linear equations system has to be formed only by non-negative values.
Summarizing, the problem is the following:

MINIMUM WEIGHT POSITIVE SOLUTION TO LINEAR EQUATIONS.

INSTANCE: Finite set $X$ of pairs $(\vec{x},b)$, where  $\vec{x}$ is an m-tuple of non-negative integers and $b$ is a non-negative integer, and a positive integer $K \leq m$.

QUESTION: Is there an m-tuple $\vec{y}$ of non-negative rational entries such that $\vec{y}$ has at most $K$ non-zero entries and such that $\vec{x} \cdot \vec{y}=b$ for all $(\vec{x},b)\in X$?

Garvey and Johnson state that MWSLE's NP-completeness can be proved from the "exact covering by 3-sets" problem but don't give more details. Exact cover by 3-sets is a natural generalization of the perfect matching problem to hypergraphs G=(V,E) with all edges e∈E containing 3 vertices (instead of 2) and |V|  is divisible by 3. The problem is to find a subset of the hyperedges such that each vertex is incident to exactly one of the selected hyperedges.

We are trying to prove that the restricted problem is still NP-complete but we don't see the way to do it. Any clues?

Thanks in advance

Esteve


texts: Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?

texts:
Planar graphs are 4-colorable.
Determining if a planar graph is 3-colorable is NP-Complete.
A graph with a crossing number 1 (graph such that it can be drawn with $\le 1$ crossing) is 5-colorable.
What is the hardness of determining if a graph with crossing number 1 is 4-colorable? Is that NP-Complete?
One can also can ask similar question for crossing numbers 2,3,... and for genus 1,2,...


texts:
I know some schemes to compute power sums (I mean $1^k + 2^k + ... + n^k$) (here I assume that every integer multiplication can be done in $O(1)$ time for simplicity): one using just fast algorithm for computing $n^k$ in $O(\lg k)$ and it's overall time is $O(n \lg k)$, the other, using Bernoulli numbers, can be implemented in $O(k^2)$. And the most complicated works in $O(n \lg \lg n + n \lg k / \lg n)$ - it uses somewhat like sieve of Eratosthenes. (Don't know if it's well-known, I came up with this by myself, so if it not well-known, I can explain how to do it)

Every of this 3 algorithms, but the first, has it's own pros and cons, for example for every $k = n^{O(1)}$ the last algorithm works in $O(n \lg \lg n)$ time, while first in runs $O(n \lg n)$ and second is even worse. When $k = o(\sqrt{n \lg \lg n})$ second algorithm performs better than others.

So my question is: if there exists some more efficient algorithms? (Like in previous problems, I am not merely interested in asymptotics in $n$, but in $k$ too)

Thank you very much!


texts: Automated theorem proving via unsupervised approaches

texts:
This question Where and how did computers help prove a theorem? considers some automated theorem proving successes.
However they seem to be mostly supervised approaches, such as with the 4 color graph theorem, the researcher did/does the hard conceptual, non-automatable work of narrowing the conjecture to a finite (but large) set of computer-checkable cases.
Also, in other cases/examples the computer may have found an "infinite" type proof but have been obtained largely by the researcher closely intervening/guiding the overall theorem proving process.

Are there any significant examples of what could be called unsupervised theorem proving successes?

This would generally come in two forms:

only the theorem statement/conjecture, which refers to infinite cases, is given to the computer and the computer manages to find it (ie prove it) without any human intervention/assistance.
the computer searches all theorems and lists "interesting" ones based on some algorithmic criteria/rating, and later after browsing through the list, the researcher recognizes "mathematically significant" proof(s) that are standard or can be found in the literature.

(Note: I have some possible example(s) of the above & depending on response may answer with them.)


texts: Kolmogorov complexity with weak description languages

texts:
We can think of Kolmogorov complexity of a string $x$ as the length of the shortest program $P$ and input $y$ such that $x = P(y)$. Usually these programs are drawn from some Turing-complete set (like $P$ might be the description of a Turing machine, or it could be a program in LISP or C). Even when we look at resource-bounded Kolmogorov complexity, we still look at Turing machines but with some bounds on their runtime or space usage. One of the consequences of this, is that the complexity of a string is undecidable. This seems like an awkward feature.

  What happens if we use non-Turing complete models of computation to define Kolmogorov complexity?

If we pick a restrictive enough model (say our model can only implement the identity), then the complexity of a string becomes decidable, although we also lose the invariance theorem. Is it possible to have a model strong enough to have complexity equal (upto a constant offset, or even a multiplicative factor) to the Turing-complete model, but weak enough to still allow the complexity of a string to be decidable? Is there a standard name for Kolmogorov complexity with non-Turing complete models of computation? Where could I read more about this?


texts: A definition of computable numbers that requires to "wait an infinite amount of time" to get the correct result; how to make this precise

texts:
Consider the following definition:

  A number $x \in \mathbb R$ is computable, if there exists a (one-tape) Turing machine which (running infinitely long) writes the binary expansion of $x$ onto its tape.

But even allowing additional working tapes does not change the class of herey defined computable numbers. But does this definition makes sense? How can anybode read off one digit of $x$, as we cannot be sure that it is definite, i.e. it could be changed infinitely often in the run of the machine. So the result is just correct if we "wait an infinite amount" of time. But how to formalize this?


texts: Examples of Computer-Found Optimal Strategies in Games

texts: I am looking for examples in games such as Go, Chess, and Backgammon, where the believed-optimal move turned out to be suboptimal as a computer found better strategies.


texts: Does a chordal graph where the size of minimal separators is constrained have name?

texts:
An undirected graph $G$ is chordal if it has no induced cycles of length 4 or more. A set $S \subseteq V(G)$ disconnects a vertex $a$ from vertex $b$ if every path of $G$ between $a$ and $b$ contains a vertex from $S$. A non-empty set $S \subseteq V(G)$ is a minimal separator of $G$ if there exists $a$ and $b$ such that (i) $S$ disconnects $a$ from $b$ in $G$, and (ii) no proper subset of $S$ disconnects $a$ from $b$ in $G$.

A $k$-tree is a chordal graph where all maximal cliques are of size $k+1$ and all minimal separators of size $k$. A block graph is a chordal graph, where maximal cliques can be of any size, but the minimal separators are of size one. What about chordal graphs where the maximal cliques can be of any size, but there's a constraint on the size of the minimal separators? This feels like a rather natural variant, but I was unable to find a reference that captures this.

  Let $k$ be a positive integer. Consider a chordal graph such that the size of every minimal separator $|S| = k$. (Alternatively, replace $=$ with $\leq$). Have such graphs been studied before somewhere?

For $k=1$, such a graph is known as a block graph. What about $k \geq 2$?


texts: Ramsey theory through semidefinite programming

texts:
Could we realize good bounds on Ramsey theoretic problems using semidefinite programming? Example: Is there a good bound on Ramsey numbers $R(r,s)$ from semidefinite programming?

Does number of quantifiers matter in semidefinite programming? In maximizing independence number, we ask ∃ independent set of given size? In Ramsey number we ask ∀ graphs of given size ∃ clique or independent set of given sizes?


texts:
Everywhere that I read about the sparsest cut problem, it only says that the problem is known to be NP-hard. Where can I find a proof of this? Which known NP-hard problem reduces to the sparsest cut problem?

I could not find any proof in Vazirani's book - Approximation Algorithms, which presents the Leighton Rao algorithm, or the book "Computers and Intractability" - which summarizes many NP-complete problems. I could not find it by searching (with obvious search strings) on Google.  There is one paper by Chawla et al, which assumes Khot's UGC conjecture and proves the hardness of approximating the sparsest cut. I was hoping to see a proof that does not assume any conjecture.

The proof should just reduce a known NP-hard problem to sparsest cut.

Thank you,

Arpita Korwar.


texts: What would be the performance properties of a comb or shell sort where the gap sequence is the prime numbers?

texts:
In particular, the genesis of this idea was the notion that you could minimize the number of passes through the list in a comb sort by using the primes as a way to guarantee that every element gets sorted while having the largest gap be only slightly larger than the square root of the size of the list rather than just below the size of the list. Some quick experimentation showed that this was very wrong and that starting with the largest prime possible as the gap is always more efficient (for comb sort; I confess I don't really get shell sort and so didn't test it, though I expect similar results) unless the list is already extremely well-ordered, so that part of the idea is a bust, but I'm still curious about the relative merits of using primes over other gap-choosing strategies.
I assume that this is obvious enough of an idea that it's been studied and found inefficient in some key way, but I don't have any idea why exactly this might be so beyond an aversion to having a lookup table of primes in one's code (or needing to calculate a significant number of primes every time the sort is run); I couldn't begin to speculate as to how costly that kind of overhead would be considered to be however.


texts: P/poly vs NP separation based on circuit trees instead of DAGs

texts:
there are various theorems that relate major complexity class separations to circuit family DAGs sizes, in particular for P/poly vs NP. in contrast,

  are there theorems/conjectures that relate P/poly vs NP separation to the size of circuit trees (aka formulas)?

note of course that CNF/SAT is a boolean formula. an example in this form would be something like if a CNF circuit family $C_n$ requires size $\Omega(g(n))$ clauses to compute function $f$ (alternately, can compute $f'$ in $O(g'(n))$ clauses) then NP $\not\subset$ P/poly, but the question is not limited to CNF & is asking about formulas in general. ([1] is a somewhat related question)

[1] Complexity of converting a boolean circuit to a boolean formula


texts: Are the sets of executions of data-race free programs equal, when run on causal memory and on sequentially consistent memory respectively?

texts:
In the paper "Causal Memory: Definitions, Implementations, and Programming (Distributed Computing [DC] 1995)", the authors present a formal definition of causal memory, an abstraction of distributed shared memory that ensures that processes in a system agree on the relative ordering of operations that are causally related.

More interestingly, it is shown that data-race free (DRF, for short) programs, if written to run correctly on sequentially consistent memory, also run correctly in a system with causal memory. That is,

  DRF theorem: If program $\Pi$ is data-race free, then all histories of $\Pi$ when run on causal memory are sequentially consistent.

For completeness, the definition of data-race free is given as follows. For more details and discussions, you can refer to “Data-race free” programs at cs.se.

  DRF: Program $\Pi$ is data-race free if, for all histories $H$ of $\Pi$ and all causality orders $\leadsto$ of $H$, if $H$ has a serialization that respects $\leadsto$ (note that this implies that $H$ is sequentially consistent), then $H$ is data-race free with respect to $\leadsto$.

This theorem is important and beneficial to programmers because data-race free programs can be written assuming a sequentially consistent memory even for a system that provides causal memory.

Despite such "equivalence" DRF theorem, I am still curious about the detailed behaviors of data-race free programs when run on causal memory and on sequentially consistent memory. Formally,

  My problem: Let $\Pi$ be a data-race free program. When run on causal memory, $\Pi$ results in a set (denoted $E_{c}$) of (possibly infinite many) executions. When run on sequentially consistent memory, it results in a set (denoted $E_{s}$) of (possibly infinite many) executions. Though, according to DRF theorem, every execution in $E_{c}$ is sequentially consistent, are the two sets of executions equal, i.e., $E_c = E_s$?

This problem is essentially inspired by the paper "Linearizable Implementations Do Not Suﬃce for Randomized Distributed Computation" (arXiv for STOC'2011), which shows that linearizability does not suffice for randomized algorithms. Specifically, using well-known linearizable implementations of objects in place of atomic objects can change the probability distribution of the executions (and thus the outcomes).

I want to investigate whether such phenomenon happens in the context of data-race free programs on different memory models. Here the data-race free programs may be deterministic or randomized which permit local coin-flips.


texts: Under some assumptions, it is hard to approximate MAX-CLIQUE within a factor $n^{1-\epsilon}$ for any $\epsilon >0$. Are there any other problems that are known to be equally hard to approximate? I'm particularly interested in unweighted problems.


texts: Algorithms for creating a directed network with a given 3-node motifs distribution

texts:
I am looking for algorithms to create directed networks with an arbitrary distribution of 3-node network motifs (i.e. subgraphs of the order 3), see this picture from O. Sporns, R. Kotter, Motifs in Brain Networks, (2004).

It should work in a reasonable time for up to 10,000 nodes with total graph density of $p=0.1$ (probability of every connection + no self-connectivity). Of course, some distributions are impossible because motifs in the network overlap with each other. Thus, it should work for distributions relatively close to a random-network distribution  (let's say, it should give a result for input motif numbers of $50-200\%$ of mean numbers in random networks).


texts: Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?

texts:
The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in reasonable time is an approximate one (Synopsis diffusion), but increasing its precision is exponential in the number of bits (and I need a lot of bits).

Background: this task is done (several times with different 'weights') as part of the probability calculations in  BBChop (http://github.com/ealdwulf/bbchop) a program for finding intermittent bugs (ie, a bayesian version of 'git bisect'). The DAG in question is therefore a  revision history. That means that the number of edges is unlikely to approach the square of the number of nodes, it's likely to be less than k times the number of nodes for some smallish k.
Unfortunately I haven't found any other useful properties of revision DAGs. For example, I was hoping that the largest triconnected component would grow only as the square-root of the number of nodes, but sadly (at least in the history of the linux kernel) it grows linearly.


texts:
I've looked in the Zoo and it seems it is not true because $PH \subseteq P^{PP}$. Nonetheless I've passed by a paper that appears to have used a positive result. It was in the context that $f : \{0,1\}^* \mapsto \{0,1\}^*$ is a function, computable by probabilistic polynomial time oracle machine $M$ with access to an arbitrary oracle $A$. The authors say and I quote:

  Its also immediate that $G^f$ ≡
  $G^{M^A}$ is computable by a
  probabilistic polynomial time oracle
  machine with access to $A$.

where $G$ is a probabilistic polynomial time oracle machine.

They do it again also for $S^{N^A,M^A}$, $S,N$ being other probabilistic polynomial time oracle machine.

Update: the paper is "Notions of reducibility between cryptographic primitives" - 2004. It was in the proof of Lemma 1 of the part that "If there exists a fully-black-box reduction from a cryptographic primitive P to cryptographic primitive Q then there exists a relativizing reduction from P to Q as well." The definitions of fully-black-box and relativizing reduction is in the paper.

The question now, according to Lance Fortnow's answer that they are not equal, does that mean that this is a gap in the proof ?


texts: How to implement a functional programming language efficiently?

texts:
Thanks to Petr and Andrej for their feedback.
I'm rephrasing my question and give a bit of a context:

Functional programming languages are mostly based on lambda calculus.
Implementing a functional language straight forward is inefficient on today's hardware. For example:

\begin{eqnarray}
f &\equiv&\ \lambda x.\lambda y.\ x+y \\
g &\equiv&\ f\ v
\end{eqnarray}
Those functions will have the following types:
\begin{eqnarray}
f &\colon& a \rightarrow b \rightarrow c  \\
g &\colon& a \rightarrow b
\end{eqnarray}

Now the function $g$ needs to store the variable $v$ in an runtime environment, when the variable $v$ is only accessible in a specific context.
This concept is known as closure.

I'm looking for an method to eliminate all closures in a given program and avoid the allocation of environments at runtime.

Is this even possible?
What are the disadvantage of such an algorithm?

Thanks to Petr for mentioning the S-K basis.
As I understand, the combinator graph reduction will put any function in a point-free style. However by applicate arguments partially, there is still some form of environment necessary.

Original question:

Is a purely functional programming language like Haskell still turing
complete without the concept of closures?
Or the other way around: Is it possible to eliminate all closures in
a Haskell program in order to use no heap space?


texts: Stephen Hawking's impact on computer science

texts:
In light of Stephen Hawking passing away today, I was wondering whether any of his results have direct impact on cs?

The obvious candidate would be in quantum computing, or rather the construction of a physical quantum computer, but perhaps there are results that have other impact.

I am familiar with his work only on the popular-science level, so this is not really a research-level question, but perhaps it has research-level answers.

EDIT: following the answer, I don't mean his recent concerns about AI. That is not really a contribution to CS, more of a philosophical/sociological point. I aim more for mathematical results, or connections of physics to computing.


texts: Minimum number of columns making each row different

texts:
I'm curious whether this problem is NP-hard: suppose you are given an arbitrary $m\times n$ 0-1 matrix (each element is either 0 or 1, for the simplicity of the problem), and any pair of rows (i.e. a 0-1 vector of dimension-$n$) are different (in other words, there are no repetitive rows). I'd like to select a minimum number of columns such that each row within these columns are different.

To make sure you understand it correctly, there is a firm lower bound, $\log_2m$, of the number of columns to be selected, but you don't know whether a solution of size $\log_2m$ exists. In addition, there must be a feasible solution of size $n$ since each row is different.

Is there an efficient algorithm for solving this? Or I need to solve it in a brute-forth way by checking every possible combinations of columns from $\log_2m$ to $n$?


texts:
I'm dealing with the min-max regret 0-1 Integer Linear Programming problem (MMR-ILP, for short), which is formulated as below.

\begin{equation} \label{eq:nip_obj}
\min_{x \in \Phi} \sum_{i = 1}^n u_i x_i - \theta
\end{equation}

\begin{equation} \label{eq:nip_constraints}
\theta \leqslant \sum_{i = 1}^n \left(l_i + (u_i - l_i)x_i\right)y_i, \quad \forall~y \in \Phi
\end{equation}

where $\Phi$ is the set of all possible solutions for the problem, $x,y \in \Phi$, $\Theta \in \mathbb{R}_{>0}$, and $|\Phi|$ is exponential.

I strongly believe that MMR-ILP is EXPSPACE-Complete (or, at least, EXPSPACE) since $\Phi$ is an exponential set (and not given by the problem instance/benchmark).

I'm not a theoretical scientist, sadly. I'm studying the polynomial hierarchy and the time and space hierarchies, but I did not find any good literature regarding this topic.

I want to show that this problem does not belong to NP.
Thus, my questions are as follows.

Which technique I can use to show that it's in EXPSPACE?
If I show that MMR-ILP is in EXPSPACE, thus it implies that MMR-ILP does not belong to NP?
If I show that MMR-ILP is in EXPSPACE, what I can affirm regarding its time complexity (as far as I read, it's strongly believed that EXPTIME $\subseteq$ EXPSPACE)?

Thank you in advance :)


texts: Implications of proof of abc conjecture for cs theory

texts:
What implications would a proof of the abc conjecture have for tcs?

http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/


texts: polytime approximability of directed multicut

texts: Does anyone know how well directed multicut can be approximated in planar and minor free graphs?  Also any survey of approximability of directed multicut and multicut in various graph classes would be appreciated  Also if anyone can recommend


texts:
Can the divide and conquer nature of the FFT be generalized to other transforms (z Transform, chirp, etc) automatically?

Is there an algorithm that takes in a description of transform (I don't know what information would be needed) and can produce a fast FFT like function?


texts: Computational complexity of minimum distance of rate $\frac{1}{2}$ codes

texts:
We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing minimum distance of a (binary) code is hard. Later Dumer, Micciancio and Sudan showed that it is hard to approximate also. Both of them talk about hardness of the problem when all codes are considered.
My question is regarding a slightly more restricted class. Is there anything known for codes of half rate? Without loss of generality, parity check matrix of the code can be assumed to be of the form $(\mathbb{1 \vert }M)$ where $M$ is a square matrix.
I assume that none of the results above directly give NP-hardness (for exact or approximate answer) when class is restricted since the reductions don't end up landing in half rate codes.


texts: Learning k-parities with Membership Queries and Persistent Noise

texts:
Random independent misclassification error is an inappropriate noise model for a membership query (MQ) oracle because for any noise rate $\eta<1/2$ one can eliminate noise to an arbitrary extent by simply querying the oracle $p(1/(1-2\eta))$ times with the same input for some polynomial $p(\cdot)$ and taking the majority label returned.

The random persistent misclassification noise model of Goldman, Kearns, and Schapire, plugs this "loophole" by stipulating that an oracle that assigns a label $l$ to some sample $x$, always assigns label $l$ to sample $x$.

My question is: What are the known best upper bounds on the time and queries required to solve the learning parities problem with membership queries and random persistent misclassification noise for some constant value of $k$ (the number of relevant attributes)? Is the problem known to be solvable in $O(n \log (n/\delta))$ time and $O(\log (n/\delta))$ queries w.r.t. $n$, the number of attributes and $\delta$, the probability of error?


texts: Hierarchy theorem for NTIME intersect coNTIME?

texts:
$\newcommand{\cc}[1]{\mathsf{#1}}$Does a theorem along the following lines hold: If $g(n)$ is a little bigger than $f(n)$, then $\cc{NTIME}(g) \cap \cc{coNTIME}(g) \neq \cc{NTIME}(f) \cap \cc{coNTIME}(f)$?

It's easy to show that $\cc{NP} \cap \cc{coNP} \neq \cc{NEXP} \cap \cc{coNEXP}$, at least. Proof: Assume not. Then $$\cc{NEXP} \cap \cc{coNEXP} \subseteq \cc{NP} \cap \cc{coNP} \subseteq \cc{NP} \cup \cc{coNP} \subseteq \cc{NEXP} \cap \cc{coNEXP},$$ so $\cc{NP} = \cc{coNP}$, and hence (by padding) $\cc{NEXP} = \cc{coNEXP}$. But then our assumption implies that $\cc{NP} = \cc{NEXP}$, contradicting the nondeterministic time hierarchy theorem. QED.

But I don't even see how to separate $\cc{NP} \cap \cc{coNP}$ from $\cc{NSUBEXP} \cap \cc{coNSUBEXP}$, as diagonalization seems tricky in this setting.


texts: Is there an equivalent to derandomization for quantum algorithms?

texts: With some randomized algorithms you can derandomize the algorithm, removing (at a possible cost in run time) the use of random bits and maximizing some lower bound on the objective (usually computed using the fact that the theorems are about the expected performance of the random algorithm). Is there an equivalent for quantum algorithms? Are there any well-known results of "dequantization"? Or is the underlying state space too big for this sort of technique?


texts: Structural property of DFAs/NFAs accepting LTL-definable languages

texts:
I consider LTL on finite words. In this context, there are a couple of nice equivalence results for a language L:

L is LTL-definable (i.e., there exists an LTL formula phi such that L is the set of all words satisfying phi)
L is FO[<, Succ]-definable
L is star-free

However, I am looking for a simple (sufficient) condition on the structure of a DFA, let us call it A, that guarantees that the language L(A) accepted by A is indeed LTL-definable. I am aware that L(A) is LTL-definable if and only if the syntactic monoid of A is group-free, but this monoid is too large to compute in many cases.

Is there a "simpler", preferably structural property on DFAs/NFAs that guarantees that the accepted language is expressible by an LTL formula?


texts: Are there any approaches to the following scheduling problem?

texts:
Consider the following problem: we are given $K$ tasks $\langle n_1, n_2, ..., n_K \rangle$. Every task $n_i$ is qualified with two parameters:

The time it takes to be completed ($t_i$) and,
The utility of completing it, $u_i$. Let us assume that $u_i$ is a scalar value which represents a revenue that is obtained after completing task $n_i$ (so that we are rewarded $u_i$ after $t_i$).

All tasks are affordable and there are no constraints among them. Once one is started it has to be completed before permuting to a different one. It is clear that the total revenue is constant and it is equal to $U=\sum\limits_{i=1}^K u_i$. It is also obvious that this reward will be obtained in a total time equal to $T=\sum\limits_{i=1}^K t_i$.

We are interested, however, in computing the best arrangement (or permutation) of the $K$ tasks that anticipates the rewards as much as possible

Two quick questions:

What are the known approaches to this problem?
What if $u_i$ is defined as a function over time so that we are rewarded while we are completing the task?

What follows is a particular attempt to put the problem on a formal basis so that comments to this part would be also very welcome. Answers are not expected to necessarily go along the same lines:

For a particular arrangement $\pi:\langle n_1, n_2, ..., n_K \rangle$ let us $X$ denote the random variable that represents the utility over the interval $(0,T]$. Thus, let $f_{\pi, t} = p(X=x,t)$ denote the probability that the random variable $X$ is exactly equal to $x$ in the instant $t\leq T$. This reasoning suggests that the optimization metric should be the area inscribed by the density function: $F_{\pi, t}=p(X\leq x, t)$. Both $f$ and $F$ are subscripted with $\pi$ and $t$ because every problem defines different curves and different values of $t$ yield different results.

This would lead to the following formal definition of our problem:

Given $K$ tasks $\langle n_1, n_2, ..., n_K \rangle$ each qualified with the utility $u_i$ of completing it and the time required to complete it, $t_i$ find the optimal permutation $\pi^*$ among the $K!$ plausible permutations $\pi$ such that the following is maximized:

$\sum\limits_{t=1}^T F_{\pi,t}$

Thank you very much,


texts: Type of induction principle for fixpoint types

texts:
To the Calculus of Constructions we could add a general fixpoint type constructor (accepting inconsistencies or assuming F is a Functor):

Fix : (* -> *) -> *
in  : ∀F. F (Fix F) -> Fix F
out : ∀F. Fix F -> F (Fix F)

We can then write down the type of case discrimination and folding:

case : ∀F T. (F (Fix F) -> T) -> Fix F -> T
fold : ∀F T. (F T -> T) -> Fix F -> T

But what is the type of induction (if there is one)? I've gotten this far:

ind : ∀F T (P : Fix F -> *). (∀(h : Fix F). P h -> P ???) -> (x : Fix F) -> P x

Assuming the rest is correct, what should be in the place of ????
Alternatively, what is the type of dependent case discrimination?


texts: Is embedding a solution feasible for SAT?

texts:
I am interested in "hard" individual instances of NP-complete problems.

Ryan Williams discussed the SAT0 problem at Richard Lipton's blog.  SAT0 asks whether a SAT instance has the specific solution consisting of all 0's.  This got me thinking about constructing SAT instances that are likely to be "hard".

Consider a SAT instance $\phi$ with $m$ clauses and $n$ variables, where $\alpha = m/n$ is "large enough", in the sense that it falls into the region beyond the phase transition, where nearly all instances are unsatisfiable.  Let $x$ be a random assignment to the values of $\phi$.

  Is it possible to modify $\phi$ to obtain a new instance $\phi|x$, so that $\phi|x$ is "largely similar" to $\phi$, but so that $x$ is a satisfying assigment for $\phi|x$?

For instance, one could try to add to each clause a randomly chosen literal from the solution, that does not already occur in the clause.  This will guarantee that $x$ is a solution.

Or is this hopeless, leading to a fast algorithm for finding the "hidden" solution, along the lines of the following recent paper?

Uriel Feige and Dorit Ron, Finding hidden cliques in linear time, DMTCS proc. AM, 2010, 189–204.

I am aware of the discussion by Cook and Mitchell and work they reference.  However, I couldn't find anything about what happens to the structure of a formula when one tries to explicitly embed a satisfying assignment into it.  If this is folklore, pointers would be very welcome!

Stephen A. Cook and David G. Mitchell, Finding Hard Instances of the Satisfiability Problem: A Survey, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 35 1–17, AMS, ISBN 0-8218-0479-0, 1997. (PS)


texts: Careers for theoretical computer scientists

texts:
What are the typical careers for theoretical computer scientists (people with graduate degree in theoretical computer science)?

What kind of industries and institutions look for theoretical computer science knowledge?
What careers do theoretical computer scientists typically peruse?


texts:
I am wondering what is known about the complexity of the reversible Circuit Value Problem (rCVP) and the corresponding reversible Satisfiability problem (rSAT).

More precisely: a circuit $B^n\rightarrow B^n$ on $n$ boolean values is reversible if it computes an invertible function.

The rCVP problem is: given a reversible circuit on $n$ boolean values and $n$ inputs, what is the value of the output?

The rSAT problem is: given a reversible circuit, what is the input that yields the output $1,\dots,1$? (function problem, see comments)

As subcases of their non-reversible versions (CVP and SAT) these problem are respectively in Ptime and NP.

My question is rather about hardness: is rCVP Ptime-complete? Is rSAT NP-complete? I am no specialist of this and looked for a statement of the result, but found nothing so far. I read that one can encode any usual circuit by a reversible circuit using Toffoli's gates, but the is size of the reversible circuit one obtains doing so polynomial in the size of the initial circuit?


texts: Pseudo-Random Function families whose instances have full domain

texts:
The GGM construction gives (PRF) pseudo-random function families
whose instance's input's are binary strings of a single length.

I've convinced myself that one could get a PRF family whose instances have domain of all finite binary strings by taking a PRF for inputs of length $n$ and an independent PRNG seed,
using the PRNG seed to take a value that is indistinguishable
from being a primes chosen uniformly from $\; [2^{n-1},2^n) \;$,
interpreting the input as a non-negative integer,
reducing that integer mod the value from the PRNG,
expressing the result as a binary string, and feeding that to the PRF instance.

(The PRF instance and PRNG seed could instead be the output of the PRNG on the key.)

However, looking at the construction, I see what would be much simpler and more efficient,
and I think it would still be secure, although I don't understand the
proof well enough to figure out if that can be suitably modified.

  Does the following give a pseudo-random function family from
  a pseudo-random generator that stretches by a factor of 3?

Let $G$ be the generator, and define $H_0,H_\#,H_1$ to return the first,middle,last $n$ bits of $G$'s output. $\;\;$ For all non-negative integers $n$ such that $\: n\lt \text{len}(x) \:$, $\:$ let $b_n$ be the $n$th bit of $x$. $\;\;$ $F_s(x)$ is then defined to equal $\; H_\#(H_{b_{\text{len}(x)-1}}(...(H_{b_2}(H_{b_1}(H_{b_0}(s)))))) \;$.


texts: Does there exist a CAS for formal language theory?

texts: I need support for: grammars, equivalence classes, finite sets, and some smallest grammar approximation functions.


texts: Barriers to separating other complexity classes

texts:
Do Natural Proofs, Relativization and Algebrization also affect separation of other complexity classes like $L\neq NL\neq NP\neq coNP \neq PH\neq PSPACE$ etc?

For instance natural proofs barrier should affect any proof of $NP\neq CoNP$ since it will separate $P\neq NP$. However relation between $NP$ and $CoNP$ does not seem to have much with OWFs as compared to relation between $P$ and $NP$. So do natural proofs affect the stronger separation of $NP\neq CoNP$?


texts: Why/when do we ever need transfinite loop variants?

texts:
I do not understand why one would ever need a transfinite loop variant.

Why do natural-number-valued variants not suffice? My simple (but perhaps too naive) argument is: if a loop $L$ terminates from any initial state then there should be a trivial variant function $V$ which simply maps every state $s$ to the number of iterations needed for $L$ to terminate on $s$. Naturally, $V$ would be decreased by 1 with every iteration of $L$.

Can anyone provide an example of a simple deterministic while loop (no recursion, no reading of additional user provided input during runtime of the loop, no nondeterministic choices, etc.) that terminates on every initial state it is started from and yet requires a transfinite loop variant to prove its termination?


texts: How much independence is required for separate chaining?

texts:
If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In "The Power of Simple Tabulation Hashing", Pătraşcu and Thorup mention that "Chernoff-Hoeffding bounds for applications with limited independence" (mirror) shows that this bound on the population of the heaviest loaded bin also holds if the balls are distributed by an $\Omega(\lg n/\lg \lg n)$-independent hash function.

In "Balls and Bins: Smaller Hash Families and Faster Evaluation", Celis et al. note that it is not known if there is a family of hash functions where

Hash functions can be represented with $O(\lg n)$ bits of space
Hash functions can be evaluated in $O(1)$ time
The maximal load is $O(\lg n / \lg \lg n)$ with high probability.

If there is a constant $k$ such that any $k$-independent family suffices for #3, then it the polynomial construction of $k$-independent families would meet #1 and #2.

What bound do we have for the heaviest loaded bin with $k$-independent hashing?

Using Theorem 4.III of "Chernoff-Hoeffding bounds ..." and the union bound, I think I can get a bound of $O(n^{2/k})$ on the weight of the heaviest loaded bin w.h.p.

Can this be brought down to $O(\lg ^c n)$ using other techniques?


texts: Is there a notion of "sequential" idempotence?

texts:
TL;DR: I have a definition, and I'm wondering if it already has a name or has been studied.

Suppose we have a sequence of operations (or if we want to be mathematical, functions whose domains and ranges are all the same) $f_1, f_2, ..., f_n$.

I'll call the sequence idempotent if the composition $f_1f_2...f_n$ is idempotent.

But I call the sequence strongly idempotent if any initial subset of the operations $f_1...f_k$ is idempotent for all $1 \leq k \leq n$.

For example, if we take the domain of integers, set $f_1(x) = x + 1$ and $f_2(x) = 0$, then the sequence $(f_1, f_2)$ is idempotent but not strongly idempotent.

My question is, does this definition/idea already have a name? Are there any known useful properties of strong idempotency, or is it known to be useful in any particular areas?


texts: Complexity class corresponding to sorting

texts:
Two parts of TCS are algorithms and complexity. I'll simplistically say that algorithms is the study of upper bounds, showing that you can do something (with given restricted resources), and complexity is about showing that you cannot do it without some minimal resources.

So often an algorithmic problem is stated in a decision model in order to place it in a complexity class.

But something that's always bothered me is that some elementary algorithms are never mentioned outright as belonging to a particular class. One example is (comparison) sorting. Try as I might, a relevant class just seems too deficient (really, is it just checking in logspace that the result is sorted? That just seems too weak, or I'm not getting the decision version right).

What is the best/most appropriate/most useful complexity class that comparison sorting lies in?


texts: Regular languages and constant communication complexity

texts:
Let $L \subseteq A^*$ be a language, and define $f_L\colon A^* \times A^* \to \{0, 1\}$ by $f_L(x, y) = 1$ iff $x\cdot y \in L$.  I'm searching for a reference for:

Proposition. $L$ is regular iff the deterministic communication complexity of $f_L$ is constant.

In other words, $L$ is regular iff there exists a two-player protocol $P$ for $f_L$ such that the function $$n \mapsto \max\{\text{comm}(P, x, y) : |x\cdot y| = n\}$$  is bounded by a constant, where $\text{comm}(P, x, y)$ is the number of bits exchanged by Alice and Bob when Alice receives $x$ and Bob $y$, following the protocol $P$.

The only place I could find that is in George Hauser's PhD thesis, 1989, available here, where he also generalizes that to other distributions of the input $x\cdot y$ among Alice and Bob, such that the number of "cuts" is constant.


texts: Examples of successful derandomization from BPP to P

texts:
What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)?

The only example that comes to my mind is AKS deterministic polynomial time primality testing (even for this there was a methodology assuming GRH). So what specific evidence through example do we have for derandomization (again not the hardness or oracle connection)?

Please keep examples to only where time complexity improvement was shown from randomized poly to deterministic poly or something that is very close for specific problems.

Following is more of a comment and I do not know much it will help this query.

Chazelle has a very intriguing statement in http://www.cs.princeton.edu/~chazelle/linernotes.html under 'The Discrepancy Method: Randomness and Complexity   (Cambridge University Press, 2000)'.

'It's been an endless source of fascination for me that a deeper understanding of deterministic computation should require the mastery of randomization. I wrote this book to illustrate this powerful connection. From minimum spanning trees to linear programming to Delaunay triangulations, the most efficient algorithms are often derandomizations of probabilistic solutions. The discrepancy method puts the spotlight on one of the most fruitful questions in all of computer science: if you think you need random bits, please tell us why?'