texts:
I have a few questions about linear genetic programming. I'm struggling to find much information on them, hopefully someone here can help me, it would be much appreciated.

1) Initialisation: When initialising the population, does each individual point to the same set of registers or register values, or is a separate space allocated to each individual ?

2) Crossover / mutation: Are the registers crossed over and mutated as well as the program bodies, or just the program bodies ? I am guessing they're not, but then how would one go about optimising the values in the registers ?

3) Crossover cont: What, based on your experience, is the most efficient method of crossover ?  I have written a linear GP, and have applied to various datasets for time series forecasting. One being linear, a few trigonometric, and some economic data. It works fine when given anything except the economic data. Why could this be ? My guess is that is has something to do with crossover, which at present is two point. Although i have tested other methods such as one point and uniform but they have not in any way improved the performance? The first few generations are ok, and then the fitness of the population seems to fluctuate randomly with no improvement whatsoever :(

These may seem like very simple, or strange questions. I have only just begun learning about this so please be nice ! :)

Many Thanks


texts: Recent fundamental results in algorithms?

texts:
I dont know if this question belong to this forum, but I will ask it anyway

To your opinions, what are the most recent fundamental results in the field of algorithms ? [Results that can be taught in an advanced undergrad or graduate algorithms course]

In here, I am talking about results with high applicability to computer science, a continuation to what is usually taught in a general algorithm course. For instance, if we were in 1995 I would call skiplists and randomized rounding as new fundamental results in CS.

My main goal: build material for an advanced course on algorithms [that does not get into specific research areas and applications]

(Let's restrict recent to papers published in the late 1990's).


texts:
Let define the "Exactly $A$-SAT" problem : Given a CNF formula $F$ and a set $A$ of positive integers, is it true that the number of models of $F$ is in $A$?

  What is the complexity of Exactly $A$-SAT  ?

Edit --
Some different cases seem interesting:

Let $A_{MAJ}=\{m\in\mathbb{N},2^{n-1} < m\leq2^{n}\}$, then Exactly $A_{MAJ}$-SAT corresponds to the canonical $PP$-complete MAJ-SAT (Given a CNF formula $F$, is it true that $F$ is satisfied by more than half of the possible variable assignments?) - as long as $A_{MAJ}$ is not considered as part of the input, otherwise, as @Ryan's comment underlines it, the problem is in $P$.

Let $A_{SAT}=\{m\in\mathbb{N},1 \leq m\leq2^{n}\}$, then Exactly $A_{SAT}$-SAT is simply SAT.

($n$ is the number of variables of $F$).

Thank you for your answers and your comments.


texts: Understanding non-equivalence of proof lengths according to proof systems

texts:
Here, in section 4.3, Fortnow says:

But to prove P != NP we would need to show that tautologies
cannot have short proofs in an arbitrary proof system.

I am trying to understand the logic leading to this conclusion. Do I get it right when I say:

Haken showed that under a Frege proof system, solving the pigeonhole principle for $m=n+1$ is intractable.
However, with an extended Frege a proof system based on cutting planes, solving the pigeonhole principle for $m=n+1$ is always achievable in polynomial time.
Therefore, if one proves intractability of say k-SAT in a proof system, it does not imply that solving k-SAT would be intractable in another proof system.

Is that right? Else, what am I missing?


texts: FSM transducer sequential composition decidability

texts:
this is a followup/ sequel to this recent question which was answered, this one presumably significantly harder. consider a deterministic FSM transducer $F$ and its mapping $F(x)$ of an input word $x$. define a sequence/ composition of such mappings $x_n = F(\ldots F(x_1))$ where $F^n(x)$ is $n$ sequential mappings of $x$. the sequence terminates if/ "at the point" that $F(x_n)$ is unaccepted (by the FSM transducer).

now consider/ define a property of such sequences "descending". a FSM sequence $x_i$ is "descending" iff $|x_i| \geq |x_{i + 1}|$ where $|x|$ denotes word length, and for all $i,j$, $x_i \neq x_j$. (by defn all such sequences must be finite/ terminating.)

  question: given an input regular language $L$ and a FSM transducer $F$. is it decidable if all sequences $x_n = F^n(x) = F(\ldots F(x))$ for all $x \in L$ are descending?

a complete answer would be ideal but prefer partial answer(s) to none at all. looking for nontrivial analysis, reduction(s) to known problems, refs to related literature etc.

motivation/ background: a long story, but inspired/ related to investigation of a highly studied open number theory problem. the basic idea is to look for/ formulate a generalized loop invariant function applicable to automated theorem proving.


texts: Is semantic language complexity class UP Turing equivalent to syntactic language complexity class US?

texts: ${\sf UP}$ is defined in terms of unambiguous-SAT which asks if there exits at most one solution or no solution. On the other hand, ${\sf US}$ is defined in terms of unique-SAT which asks if there exists exactly one solution. I would like to know whether it is known that they are Turing equivalent, ${\sf P^{UP}}={\sf P^{US}}$. Any references would be appreciated.


texts: Does solving matrix multiplication in quadratic time imply that SETH is false?

texts:
I have a little conjecture that if you could perform matrix multiplication (or solve 3-clique) in $O(n^2 \log(n))$ time, then you could solve CNF-SAT in $O(2^{(1-\epsilon)n})$ time.

In other words, more efficient algorithms for matrix multiplication would imply more efficient algorithms for SAT refuting the strong exponential time hypothesis (SETH).

Questions:

Has anyone ever thought about connecting the hardness of matrix multiplication to SETH?  Secondly, does anyone think that there is or isn't a relationship?  Why or why not?


texts:
Is there an reverse Chernoff bound which bounds that the tail probability is at least so much.

i.e if $X_1,X_2,\ldots,X_n$ are independent binomial random variables and $\mu=\mathbb{E}[\sum_{i=1}^n X_i]$. Then can we prove $Pr[\sum_{i=1}^n X_i\geq (1+\delta)\mu]\geq f(\mu,\delta,n)$ for some function $f$.


texts: Any polynomial which is hard to count but easy to decide?

texts:
Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate
polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial
$f(x_1,\ldots,x_n)$, the circuit

 computes $f$ if $F(a)=f(a)$ holds for all $a\in \mathbb{N}^n$;
 counts $f$ if $F(a)=f(a)$ holds for all $a\in\{0,1\}^n$;
 decides $f$ if $F(a)>0$ exactly when $f(a)>0$ holds for all  $a\in\{0,1\}^n$.

I know explicit polynomials $f$ (even multilinear) showing that the circuit-size gap "computes/counts" can be exponential. My question concerns the gap "counts/decides".

Question 1: Does anybody know of any polynomial $f$ which is exponentially harder to count than to decide by $\{+,\times\}$-circuits?

As a possible candidate, one could take the PATH polynomial whose variables correspond to edges of the complete graph $K_n$ on $\{1,\ldots,n\}$, and each monomial corresponds to a simple path from node $1$ to node $n$ in $K_n$.
This polynomial can be decided by a circuit of size $O(n^3)$ implementing, say, the
Bellman-Ford dynamic programming algorithm, and it is relatively easy to show that every $\{+,\times\}$-circuit computing PATH must have size $2^{\Omega(n)}$.

 On the other hand, every circuit counting
PATH solves the $\#$PATH problem, i.e. counts the number of $1$-to-$n$ paths in the specified by the corresponding $0$-$1$ input subgraph of $K_n$. This is a so-called $\#$P-complete problem. So, we all "believe" that PATH cannot have any counting $\{+,\times\}$-circuits of polynomial size. The "only" problem is to prove this ...

I can show that every $\{+,\times\}$-circuit counting a related  Hamiltonian path polynomial HP requires exponential size. Monomials of this polynomial correspond to $1$-to-$n$ paths in $K_n$ containing
all nodes.
Unfortunately, the reduction of $\#$HP to $\#$PATH by Valiant requires to compute the inverse of the Vandermonde matrix, and hence cannot be implemented by a $\{+,\times\}$-circuit.

Question 2: Has anybody seen a monotone reduction of $\#$HP to $\#$PATH?

And finally:

Question 3: Was a "monotone version" of the class $\#$P considered at all?

N.B. Note that I am talking about a very restricted class of circuits: monotone arithmetic circuits! In the class of $\{+,-,\times\}$-circuits, Question 1 would be just unfair to ask at all:  no lower bounds larger than $\Omega(n\log n)$ for such circuits, even when required to compute a given polynomial on all inputs in $\mathbb{R}^n$, are known.
Also, in the class of such circuits, a "structural analogue" of Question 1 --
are there $\#$P-complete polynomials which can be decided by poly-size $\{+,-,\times\}$-circuits? --
has an affirmative answer. Such is, for example, the permanent polynomial PER$=\sum_{h\in S_n}\prod_{i=1}^n x_{i,h(i)}$.

ADDED:  Tsuyoshi Ito answered Question 1 with a very simple trick. Still, Questions 2 and 3 remain open. The counting status of PATH is interesting in its own both because it is a standard DP problem and because it is #P-complete.


texts: Finding an answer key given tests and scores

texts:
Consider multiple students taking a multiple-choice tests. The test has $q$ questions, and each question has $m$ choices. ($q$ can be large, but $m$ is rather small.) You are given $n$ tests, complete with all answer choices and their grades (number of questions correct). Find the set of answers keys which produce these scores.

I and a few friends had a go at it, but I was wondering if there was an efficient algorithm to solve this.


texts: If P = BQP, does this imply that PSPACE (= IP) = AM?

texts:
Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking...

I wondered what if Quantum Computers could be efficiently simulated by Classical Computers. Could this be SIMPLY related to the Divide between IP and AM? What I mean is that IP is characterized by Polynomial number of rounds of  classical interaction, while AM has 2 rounds of classical interaction. Could simulating a Quantum Computing reduced the amount of interaction for IP from polynomial to a constant value?


texts: question about concurrent ZK paper by Prabhakaran & Sahai

texts:
Concurrent Zero Knowledge Proofs with Logarithmic
Round-Complexity

Page numbers are from the paper itself, and not the pdf.

From page 3,

  "An interactive proof system is said to be black-box (computational) zero

  knowledge if there is a probabilistic polynomial time oracle machine $S$ such that

  for any probabilistic polynomial time verifier $V^*$ and for all $\:x \in L\:$, the distribution

  of the output produced by $S^{V^*}$  on input $x$ is computationally indistinguishable

  from the view of the verifier at the end of the interaction $(P,V)(x)$."

I assume they mean $\:\left(P,V^*\right)(x)\:$ at the end, otherwise this

just defines Honest Verifier Computational Zero Knowledge.

From page 7,

  "If the simulator does not abort till all the sessions are over (or the

  verifier terminates), it outputs the view of the verifier at that point."

From the third paragraph on page 8,

  "If the depth counter indicates that we are just one level above the leaves, then the

  simulator has to wait for the next two preamble messages, i.e., it has to move through

  the two leaves, and then return. For this the simulator keeps modifying the current view

  by letting the (modified) prover and the verifier run, until two preamble messages arrive."

It seems to me like this can't work, since the prover's message

at that stage is just a statistically binding commitment.

Let $\: p: \omega \to \omega \:$ be a polynomial that bounds the number of oracle queries $S$ makes when $V^*$ only requests one proof. $\:$ Suppose the statistically binding commitment scheme being used

is such that it is easy to compute a predicate which commitments have a probability of approximately $\: \frac1{2\cdot p(k)} \:$ of satisfying (for example, Naor commitments or commitment from an injective pseudo-random generator). $\:$ Have the cheating verifier $V_1$ request only one proof and then behave like the honest verifier except that, at one level above the leaves, it will terminate

if the prover's commitment does not satisfy the predicate. $\;\;$ The probability of $\:\left(P,V_1\right)(x)\:$ succeeding is obviously approximately $\: \frac1{2\cdot p(k)} \:$, $\:$ whereas by the union bound, but by the

union bound and the independence of the simulator's, the probability that $S^{V_1}$ outputs a

succeeding view is not non-negligibly more than $\: \frac1{4\cdot p(k)} \:$. $\;\;$ This means that for sufficiently

large $k$, the probability of $\:\left(P,V_1\right)(x)\:$ succeeding will be more than $\: \frac1{5\cdot p(k)} \:$ greater than

the probability $S^{V_1}$ has of outputting a succeeding view. $\;\;$ That means the distribution

of $S^{V_1}$ is computationally distinguishable from the distribution of $\:\left(P,V_1\right)(x)\:$.

Is this an error in the paper? $\:$ If no, what am I missing?


texts:
The definition of Book Embedding on Wikipedia: "A book embedding is a generalization of planar embedding of a graph to embeddings into a book, a collection of half-planes all having the same line as their boundary. The vertices of the graph are required to lie on this boundary line, and the edges are required to stay within a single half-plane". Full definition is at (http://en.wikipedia.org/wiki/Book_embedding)

Planar embeddings have geometric duals, that has numerous algorithmic application. One of the very nice property of duality of planar graphs is that if $T$ is a spanning tree of a planar grpah $G$, then the set of edges not in $T$ in the dual is a spanning tree of the dual $G^*$. Is there any kind of similar geometric dual for book embeddings? Is there a similar property between the spanning tree of primal and dual graphs as in the planar case?


texts: Is the problem of finding operators to satisfy a list of boolean variables NP complete?

texts:
This is similar to SAT, except that we know the assignment of each variable, but do not know the assignment of any boolean operator. In that case, is finding the assignment of each operator so the expression evaluates to a given boolean value a NPC problem?

Actually, I was wondering if finding assignment of arithmetic operators to satisfy an integer arithmetic expression(e.g., $1$ $op_1$ $3$ $op_2$ $7$ $op_3$ $op_4$ = 10) is NP complete?


texts: minimal languages that "cover" grammar productions

texts:
this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site cs.se (now with more questions than this one!) and which seems theoretically significant yet maybe not studied much in the literature. consider a grammar as a set of production rules, terminal and nonterminal symbols.

  what is the smallest language that "covers" all the grammar production rules/symbols?

by "covering" what is meant that every grammar production rule is invoked at least once in a derivation of the acceptance of the word, and including all the terminals. the smallest language is necessarily finite, ie a set of words/strings. the question arose (roughly) in the context of DFAs[2] and CFLs[1]. the problem becomes more complex in the case of CFLs, ambiguous languages & nondeterminism. looking for eg ref(s), thms, complexity, theory, connections, applications, insight etc.

[1] Generating a set of minimal-length strings that, together, invoke every production of a context free language / D.W., cs.se
[2] Transition coverage for a DFA / Patrick Collins, cs.se


texts: A variant of hitting set: finding a matching to hit all edge sets

texts:
In general, the hitting set problem is given a family $\cal S$ of sub-sets, $\{S_1, \cdots, S_h\}$, and a universal set $U = \bigcup_{i\in [1,h]} S_i$. It asks for a minimum set $H \subseteq U$ hitting all sub-sets of $\cal S$, and as we know, it is NP-hard. Now the problem is defined as following.

Let $K$ be a clique, and $\{K_1, \cdots, K_h\}$ be a collection of sub-cliques of $K$. A matching is a set of pairwise disjoint edges. The question now is to find a matching $M$ of $K$ that hits every $E(K_i)$ for $i \in [1,h]$, where $E(K_i)$ is the edge-set of $K_i$, and $M$ hits every $E(K_i)$ if for any $E(K_i)$ (with $i \in [1,h]$), there is an edge $uv\in M$ that is an edge of $E(K_i)$ as well.

For now, I can show that if what we want is a minimum matching, then the problem is NP-hard. So is it still hard to find a minimal matching hitting every $E(K_i)$?


texts: On optimality of Grover algorithm with high success probability

texts:
It is well-known that bounded error quantum query complexity of the function $OR(x_1,x_2,\ldots, x_n)$ is $\Theta(\sqrt{n})$. Now the question is what if we want our quantum algorithm to succeed for every input with probability $1-\epsilon$ rather than the usual $2/3$. Now in terms of $\epsilon$ what would be the appropriate upper and lower bounds?

It is immediate that $O(\sqrt{n} \log(1/\epsilon))$ queries suffices for this task by repeating the Grover algorithm. But from what I recall this is not at all optimal as even plain Grover algorithm if run carefully, i.e. for appropriate number of iterations, can achieve something like $\epsilon=O(1/n)$ with just $O(\sqrt{n})$ iterations. And hence using that one can get an improvement for all $\epsilon$'s. On the other hand, I don't expect that $\Omega(\sqrt{n})$ be the right answer for very small $\epsilon$'s.

But I am interested to see what one can show in terms of $\epsilon$-dependent upper and lower bounds for different ranges of $\epsilon$ especially when $\epsilon$ is very small say $\epsilon= \exp(-\Omega(n))$ or $\epsilon=1/n^k$ for large $k$'s.

(To give some context, the general phenomenon I am getting at is the amplification in context of quantum query complexity. )


texts: Hardness of Computing Weisfeiler-Lehman labels

texts:
The 1-dim Weisfeiler-Lehman algorithm (WL) is commonly known as canonical labeling or color refinement algorithm. It works as follows :

The initial coloring $C_0$ is uniform, $C_0(v) = 1$ for all vertices $v \in V (G) \cup V (H)$.
In the $(i + 1)$ st round, the color $C_{i+1}(v)$ is defined to be a pair consisting of the preceding color $C_{i−1}(v)$ and the multiset of colors $C_{i−1}(u)$ for all $u$ adjacent to $v$. For example, $C_1(v) = C_1(w)$ iff $v$ and $w$ have the same degree.
To keep the color encoding short, after each round the colors are renamed.

Given two undirected graphs $G$ and $H$, if the multiset of colors (aka labels) of the vertices of $G$ is distinct from the multiset of colors of the vertices of $H$, the algorithm reports that the graphs are not isomorphic; otherwise, it declares them to be isomorphic.

It is well-known that the 1-dim WL works correctly for all trees and requires only $O({\log}n)$ rounds.

My question is :

  What is the hardness of computing 1-dim WL labels of a tree ? Is a lower bound better than logspace known ?


texts:
In the article Levenshtein distance Wikipedia says about the proof of invariant that:

  This proof fails to validate that the number placed in d[i,j] is in
  fact minimal; this is more difficult to show, and involves an argument
  by contradiction in which we assume d[i,j] is smaller than the minimum
  of the three, and use this to show one of the three is not minimal.

So how can I show that d[i,j] is actually minimal? (informal proof is ok)


texts: Decomposing Single Crossing Minor Free graphs

texts:
We know that for a single-crossing graph H of size h, there exists a constant ch whose value depends only on h, such that every four-connected component of an H-minor-free graph is either a planar graph or of treewidth at most ch.
I would like to know if some sort of the reverse of this also holds. That is, can we say for every such graph G whose four-connected components are of treewidth is at most w or a planar graph, there exists a constant cw whose value depends only on w and single-crossing graphs H1, H2, ..., Hl each of size at most cw, such that G belongs to the union of H_i-minor free-graphs for each i in 1, 2, ..., l?


texts: Calculate sum of reciprocal rank in arbitrary large graph

texts: For arbitrary graph of n node, can I approximate $\sum_{v\neq u}\frac{1}{Rank_u(v)^a\times Rank_v(u)^b}$ with $\sum_{v\neq u}\frac{1}{Rank_u(v)^{a+b}}$ or not when n is large enough? $a,b>0$, $Rank_u(v)=k$ if v is the $k$th nearest node to u. For example, $Rank_u(u)=1$, $Rank_u(u')=2$ where u' is the nearest node to u. Here approximation means something like $\Theta(n)$. Thanks a lot!


texts:
I thought something fancy can be done with number-theory or memoization, but neither worked for me. Being limited in knowledge I decided to ask experts.
Does there exist a deterministic polynomial-space algorithm
for the following decision problem?

Instance: Two positive integers $k$ and $m$ in decimal representation.
Question: Is $2^k+m$ a prime number?

Some comments:

By polynomial-space I mean that the space complexity of the algorithm should be bounded by a polynomial in the input length $\log k+\log m$.

The naive approach to this problem determines the decimal representation of $2^k+m$ and then applies a fast primality testing algorithm.
It is easy to see that this naive approach requires exponential space,
just for writing down the decimal representation of $2^k+m$.

This is related to another question of mine.


texts:
(I posted this question to MathOverflow two weeks ago, but so far without a rigorous answer)

I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (graphs which can be built by the operations of disjoint union and complementation, starting from isolated vertices) have cliquewidth at most 2. (Courcelle et al, Upper bounds to the clique width of graphs). Now consider some fixed non-negative integer k, and consider the class of graphs $\mathcal{G} _k$ of graphs such that for every $G = (V,E) \in \mathcal{G} _k$ there is a set $S$ of at most k vertices such that $G[V - S]$ is a cograph. Since the graph class $\mathcal{G} _k$ can also be seen as the class of graphs that can be built out of cographs by adding at most $k$ vertices, this class has also been called cographs + $kv$.

My question is: what is a tight bound on the cliquewidth of graphs in $\mathcal{G}_k$, i.e. the graphs which can be turned into a cograph by deleting k vertices?

It is known that if a graph $G$ is obtained from $H$ by deleting $k$ vertices then $cw(H) \leq 2^k (cw(G) + 1)$. This shows that if a cograph $G$ can be obtained from a graph $H$ by deleting $k$ vertices, then $cw(H) \leq 2^k (3 + 1)$, and hence the cliquewidth of a graph in $\mathcal{G}_k$ is at most $4*2^k$. I am unsure whether this exponential dependency on $k$ is necessary. In this context I would also be interested in the maximum decrease in the cliquewidth by deleting a vertex; i.e. if we delete a single vertex from a graph, how much can the cliquewidth decrease?


texts: Inapproximability of set cover: can I assume m=poly(n)?

texts: I am trying to show that a certain problem is inapproximable by a reduction from set cover. My reduction transforms an instance with ground set of size $n$ and $m$ sets into an instance of my problem where a certain parameter $r$ is of size $O(n+m)$. I can then show that an instance of set cover where the cover size is s corresponds to an instance of my problem where the size of the optimal solution is $2s$ (or something like this), and vice versa. I would like to invoke Raz-Safra to conclude that my problem is inapproximable up to a factor of $c  \log{r}$, for some constant $c$. This would work fine if I could assume that $m$ is bounded by a fixed polynomial of $n$. Does anyone know if it is kosher to assume this? This is certainly true for the family of instances used in the standard NP-hardness proof for set cover, but I am not sure if this remains the case for the kind of PCP reductions employed by Raz and Safra.


texts: Does P/poly $\neq$ NP/poly have any interesting implications?

texts:
$P/poly = NP/poly$ implies $NP \subseteq P/poly$, which in turn has interesting consequences like the collapse of the polynomial hierarchy.

Are there interesting implications for $P/poly \neq NP/poly$?


texts: Sufficient conditions for the regularity of a context-free language

texts:
It would be nice to collect a list of conditions that imply that a context-free language L
is regular, i.e. conditions of the form:
"if a given CFG/PDA has property P, then its languages is regular"

The property P does not have to characterize
the CFGs generating regular languages. Furthermore, P does not have to be decidable, and P should "somehow depend" on the language being
context-free ("the syntactic monoid of L is finite",
"L is decidable in space o(log log n)" and so on, are not what I am looking for).


texts: Does the NP-hardness of finding any valid solution imply NPO-hardness?

texts:
Suppose we have an NP optimization problem $A$ such that the problem of finding any valid solution, regardless of whether it is good or bad, is NP-hard (as it happens in NPO-complete problems such as Max-W-Sat, Max Ones, Max $\{0,1\}$ Integer Programming, and their corresponding Min versions). Does this imply $A$ is NPO-hard? If so: why? Can we write some general PTAS-reduction from some NPO-hard problem into $A$? If the answer is no: any known counterexample?

EDIT: Alternatively, I would appreciate to see an NP optimization problem which does not belong to Exp-APX (as long as $P\neq NP$) but is not NPO-hard.


texts: What is the problem of finding a largest subset of smallest Kolmogorov complexity?

texts:
What do you call the problem of finding a largest possible subset of strings with smallest possible information content? I'm studying a particular instantiation of this problem in a different setting and would like to know about this more abstract problem. In terms of Kolmogorov complexity, this would be the following decision problem.

  Given: a finite set of binary strings S and positive integers c and d.

  Question: is there a subset S' of S such that |S'| is at least c and the resource-bounded Kolmogorov complexity of S' is at most d?

Edit: consider the complexity measure to be one of the resource-bounded Kolmogorov complexity measures (for example, the length of the shortest program that outputs a given string, with an additive penalty of the logarithm of the running time of the program) to make the problem computable, as suggested in the comments.


texts:
If BPP=BQP then there is a polynomial time randomized factoring algorithm.  A lot of other quantum algorithms that appeared to have an exponential speedup have recently been dequantized. For examples, see https://arxiv.org/abs/1910.06151 and references therein.

What other significant practical consequences would BPP = BQP be likely to lead to?


texts: (co-)Horn formulation of Frankl's union-closed sets conjecture

texts:
Based on comments on MO
there is simple forumlation of Frankl's union-closed sets conjecture in terms of (co-)Horn.

In co-Horn CNF at most one literal is negated in every clause
(Horn CNF where every literal is negated).

Frankl's union-closed sets conjecture is equivalent
to the following:

(A) Let $\phi$ be Horn (resp co-Horn) formula in CNF
in variables $x_1 \ldots x_n$ with more than one
solution. There is a variable $x_i$ which is False
(resp True) in at least half the solutions.

Are there sufficient conditions $\phi$ to satisfy (A)?
How would a minimal counterexample look like?

My guess about (2) is that one must maximize
the positive (resp negative) literals and
all clauses will be binary of the form $x \lor \lnot y$.


texts: How to approximate minimum clique edge cover

texts:
I'd like to take an undirected graph and express it (meaning all of its edges) using only cliques (ideally minimizing their sum cardinality).

It's clear that actually finding the minimum solution is at least as hard as the set-cover problem, but set-cover has good approximation algorithms.
Does anyone know a good approximation algorithm for this?

Particularly, if I start with each edge as its own clique and then arbitrarily choose two cliques from my list (whose union also forms a clique) and merge them and do this over and over until I can't merge any more, what's the worst case (as a ratio / the minimal solution)? Is there some heuristic I should use to determine what to merge next?


texts: Can Canetti's composition theorem be used to prove composition of Nash equilibrium?

texts:
This might be a very simple doubt, but I am not able to prove or disprove it rigorously.

Canetti's work on "Security and Composition of Multiparty Cryptographic Protocols: JoC 2000" allows us to prove results of the following form: Let $g, f_1, f_2, \cdots, f_m$ be $n$-party functions and $\pi$ can securely compute $g$ in $(f_1, \cdots , f_m)$ hybrid model. Let $\rho_i$ computes $f_i$ securely, then the composed protocol $\Pi$ by replacing the ideal call to $f_i$ by a subroutine call to $\rho_i$ securely evaluates $g$.

Does this result translate equally well if we consider Nash equilibrium or any game-theoretic equilibrium instead of secure computation? To be more precise, suppose instead of securely evaluating the function, we have a protocol that is Nash equilibrium in $(f_1, \cdots , f_m)$hybrid model, then can we construct a protocol that is Nash equilibrium in the real world?

What I mean by that a protocol is a Nash equilibrium in a setting X (X=ideal, hybrid, or real world) is the following. Suppose the strategy profile of player $i$ be $\Sigma_i$ for $i \in [n]$. Running the protocol is a (strict) Nash equilibrium with a strategy ($\sigma_1, \sigma_2, \cdots, \sigma_n) \in \Sigma_1 \times \cdots \times \Sigma_n$ in the setting X if any deviation of the players from the strategy prescribed in the protocol leads to a (strict) decrease in their utility.


texts: Reachability on DAG (best-known algorithm)

texts:
Task: To answer several reachability queries on large DAGs (millions or billions of vertices and edges) using a data structure that takes up as little space as possible, is not expensive to construct, and subsequently allows for "near-constant time" responses to reachability queries.

Question: Is there a state-of-the-art data structure that has the following features:
(1). Pre-processing time or time to build data structure is linear in number of edges or vertices. This can also be quadratic, as its a once-off process.
(2). Has linear space complexity
(3). Can answer reachability queries in O(1) time (or even logarithmic time)?

The paper I found which mentioned some structures --> http://www.vldb.org/pvldb/vol7/p1191-wei.pdf

The trade-off between properties (1)-(3), would be that we want to optimize (3), then (2) to the best possible, while (1) is still important but can be rated lowest. So, optimize (3) > (2) > (1).

The worst case would be to do a BFS/DFS for every single query. The other extreme is to pre-compute reachability for every pair of vertices, but then storage would be O(n^2) in a matrix.


texts: Does this pairwise independent random process have expected max load $\sqrt{n}$?

texts:
This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load $\sqrt{n}$ .  There the following question is asked and answered in the affirmative:

  Can we give an explicit uniform but only pairwise independent random process for selecting the next bin to put a ball into which gives the
  expected max load to be $\Theta(\sqrt{n})$ asymptotically?

Imagine we choose the explicit pairwise independent hash function family $h((ax+b) \bmod p) \bmod n)$. It is a straightforward standard exercise to show an upper bound of the following form:

$$P(\text{max number of values hashed to the same value} \geq 1 + \sqrt{2n}) \leq \frac{1}{2}$$

However, can a matching or near matching lower bound be found for the expected max load for this specific hash function family?


texts: Solving a system of sums-of-powers polynomials

texts:
What is the complexity of calculating the values of the integers $x_i$, where $0 \leq x_1 < x_2 < \dots < x_k < n$, given only the values $s_m = \sum_{i=1}^k x_i^m$? for $1 \leq m \leq k$?

If this can be solved in $f(n,k)$ space, it can be used to solve the following problem:

Given $S \subset \mathbb{Z}_n$ where $|S| = n-k$, determine $\mathbb{Z}_n \backslash S$ in $\tilde O(f(n,k))$ space.

This is done by calculating $\sum_{s \in S} s^i$ for $1 \leq i \leq k$ and $\sum_{s \in \mathbb{Z}_n} s^i$ for $1 \leq i \leq k$.


texts: How fast can we sort a list if we know how it was written?

texts:
Let $G$ be a linear time (deterministic) turing machine that takes positive integers $n$ in unary to lists of length $n.$ For any fixed such $G$, define sparse-sort(G,n) as the problem of sorting the list that $G$ outputs for input size $n$.

In general, can we compute sparse-sort(G,n) asymptotically faster than $O(n \log n)$?

It's easy to generate examples where we can manage linear time, for example any $G$ that runs $G(n-1)$, then appends some predictable value to the list. Likewise, it seems plausible that one could use the function $G$ in the algorithm to get a good runtime in general.


texts: Many-one reductions vs. Turing reductions to define NPC

texts: Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?


texts: When does automaton stay unchanged after string homomorphism?

texts:
Suppose we have a string homomorphism $\varphi: \Sigma \rightarrow \Sigma^*$.
Consider the languages in $\varphi(\Sigma^*)$ whose letters are elements of $\varphi(\Sigma)$, so here I do not want to expand each $\varphi(\Sigma)$, but leave them in this abstract form, e.g., $\varphi(a)\varphi(b)\varphi(a)$ would be a word.
So in fact for any language $L$, the language $\varphi(L)$ is the same as $L$, over a different alphabet.
If $M$ was an automaton over $\Sigma$, then there is a natural automaton, $\varphi(M)$, over $\varphi(\Sigma)$ with the same number of states: from any given state after reading $\varphi(a)$, $\varphi(M)$ goes to whatever state $M$ would go after reading all letters of $\varphi(a)$.

For example, suppose that $M$ was counting the parity of $b$'s, that is, from state 0 it goes to state 1 iff the read letter is $b$, and vica versa.
Let $\varphi$ map $a$ to $\varphi(a)=ab$ and $b$ to $\varphi(b)=bab$.
Then $\varphi(M)$ goes from state 0 to state 1 iff the read letter is $\varphi(a)$.
Therefore, $M$ and $\varphi(M)$ are isomorphic.
In fact, for the above $M$, we get an isomorphic automaton if and only if exactly one of $\varphi(a)$ and $\varphi(b)$ have an odd number of $b$'s.

  In general, for what $M$ and $\varphi$ will be $\varphi(M)$ isomorphic to $M$?

If it makes the question simpler, we can ignore which states are accepting and which is the start state.
I am interested in any type of conditions, as I could not find anything on the subject.
I am also curious when $\varphi(M)$ will be minimal for the language it recognizes.


texts:
I have a plane graph $G$ and a set of $k$ vertex pairs $\{s_1,t_1\}, \dots, \{s_k, t_k\}$. The goal is to find $k$ non-crossing paths connecting the pairs of terminals $s_i$ with $t_i$ in the graph so that the sum of path lengths is minimized. Note that the paths may "touch" each other, that is, share graph vertices and edges; the only requirement is that they do not cross.

It is easy to see that a solution always exists. Is finding an optimal solution NP-hard? I'm interested in the variant when $k$ is arbitrary and $G$ is a planar graph. However, the problem seems non-trivial even when $k=O(1)$ and/or $G$ is restricted. Say, is it possible to efficiently find such paths on a tree or a star?

An example of an input instance and a (possibly non-optimal) solution follows.

Most of the existing works (e.g., Shortest Non-Crossing Walks in the Plane) consider a similar problem in which the paths are not restricted to a graph and can be routed arbitrarily in the plane. In this setting, the terminals lie on obstacles and a solution might not exist. I'm not aware of a paper considering my variant of the problem.


texts: How to exploit knowledge of the sampling distribution for better generalization bounds?

texts:
In the PAC learning model, suppose the learner actually knows the sampling distribution $P$. Surely this knowledge can be exploited to yield better generalization bounds -- but how? One idea is using PAC-Bayesian techniques to convert the distribution over $X$ into a distribution over hypotheses, which is what I think this paper is doing:
http://www0.cs.ucl.ac.uk/staff/G.Lever/pubs/ALTfinal.pdf

Any other methods for making clever use of $P$?

[Edit 25.03.2015: In light of Vitaly's answer, let me sharpen the question. Suppose that I know the sampling distribution only approximately as $Q$. Can we formulate a generalization bound in terms of $D(Q||P)$ or $||P=Q||_{TV}$?]


texts: A direct-sum theorem for the non-deterministic communication complexity of inequality?

texts:
A non-deterministic protocol for the inequality function is a protocol that behaves as follows: Alice and Bob get strings $x,y\in\{0,1\}^n$ respectively, and an untrusted prover is trying to convince them that $x \ne y$ by sending them some proof string $\pi$. The protocol accepts if both Alice and Bob accept $\pi$, and rejects otherwise. The prover should succeed in making the protocol accept if and only if indeed $x \ne y$.

It is well-known that in every such protocol, the string $\pi$ must be of length at least $\log n$. The easiest way to see it is to observe that if this lower bound did not hold, then there would be a deterministic protocol for the equality function that transmits less than $n$ bits. This lower bound is tight, since the prover can choose $\pi$ to be a coordinate $i\in [n]$ suh that $x_i \ne y_i$.

My question is whether the non-deterministic complexity of solving $k$ independent instances of inequality is at least $k\cdot\log(n)$? In other words, is there a direct-sum theorem for the non-deterministic communication complexity of inequality?

Relevant work:
Feder et. al. [FKNN95] proved a general direct-sum theorem for non-deterministic communication complexity. Unfortunately, this theorem only applies to functions whose complexity is $\gg log(n)$, and therefore does not apply to the inequality function. Karchmer et. al. [KKN95] gave an alternative proof for this theorem, which suffers from the same limitation.

References:

[FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor, Noam Nisan, "Amortized Communication Complexity". SIAM J. Comput. 24(4): 736-750 (1995)

[KKN95] Mauricio Karchmer, Eyal Kushilevitz, Noam Nisan, "Fractional Covers and Communication Complexity". SIAM J. Discrete Math. 8(1): 76-92 (1995)


texts: Complexity relative to the graph of the Busy-Beaver function

texts:
This question is inspired by the comments made on this other question that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree $\mathbf{0}$.  (And like the former question, I'm not sure whether this is more appropriate here or on MathOverflow.)
Let $\Gamma_{\mathrm{BB}}$ be the graph of the Busy-Beaver function, i.e., $\Gamma_{\mathrm{BB}}$ is the set of $(n,v)$ such that $v = \mathrm{BB}(n)$ (I hope the exact details of how the Busy-Beaver function is defined aren't relevant for the question I'm about to ask!  but let's say that $\mathrm{BB}(n)$ is the maximal number of execution steps that a Turing machine with $n$ states can take and eventually halt).  Now consider Turing machines with $\Gamma_{\mathrm{BB}}$ as an oracle: i.e., they are allowed to ask the question “is $v = \mathrm{BB}(n)$?” at any point in their computation.
Since $\mathrm{BB}$ is in the same Turing degree $\mathbf{0}'$ as the halting problem $H$, such machines can indeed solve the halting problem (given a machine $e$ having $n$ states, simulate its execution while, at each step $v$, asking $\Gamma_{\mathrm{BB}}$ whether $v = \mathrm{BB}(n)$, and stop whenever either the machine stops or we know we've run more steps than a machine with $n$ steps can possibly go through).
Now I am interested in the time complexity for such machines with $\Gamma_{\mathrm{BB}}$ as an oracle: clearly the algorithm I described has an enormous complexity (comparable to $\mathrm{BB}$ itself!).  So I am inclined to ask whether one can do better.
Specifically:

Question 1: Does the halting problem $H$ belong to any standard complexity class relativized to the $\Gamma_{\mathrm{BB}}$ oracle, like $\mathbf{P}^{\Gamma_{\mathrm{BB}}}$ (polynomial time), $\mathbf{EXP}^{\Gamma_{\mathrm{BB}}}$ (exponential time) or $\mathbf{PR}^{\Gamma_{\mathrm{BB}}}$ (primitive recursive in $\Gamma_{\mathrm{BB}}$)?

Note in particular that, if such is the case, once we can compute the halting problem, we can compute all computable sets in the same complexity (I mean, if $H$ is the halting problem, and $\mathbf{R}$ is the class of all computable sets, we have $\mathbf{R} \subseteq \mathbf{P}^H$ by letting the oracle do all the computational work, so a positive answer to question 1, say, for $\mathbf{P}$, would imply that $\mathbf{R} \subseteq \mathbf{P}^{\Gamma_{\mathrm{BB}}}$).

Question 2: Or, at the other extreme, is it perhaps true that $\mathbf{P}^{\Gamma_{\mathrm{BB}}} \cap \mathbf{R}$ (functions computable in polynomial time with $\Gamma_{\mathrm{BB}}$ as oracle, and which happen to also be computable without oracle) equals $\mathbf{P}$, i.e., that having access to $\Gamma_{\mathrm{BB}}$ as an oracle won't speed up the computation of any problem that's already computable?  (Or replace $\mathbf{P}$ by any standard complexity class like the ones mentioned in the previous question.)


texts: How can I understand the Coppersmith–Winograd algorithm?

texts:
I want to do research on matrix multiplication algorithms. I glanced at the Coppersmith-Winograd algorithm paper, but I didn't understand anything. How can I complete the background to read this paper?

I am an undergraduate student with senior math maturity.


texts: Which invertible linear transformations can be computed reversibly without ancilla/garbage bits just as easily as they can be computed irreversibly?

texts:
Suppose that $L:F_{2}^{n}\rightarrow F_{2}^{n}$ is an invertible linear transformation. Then define $w(L)$ to be the gate count of the smallest reversible circuit on $n$ bits without ancilla/garbage bits consisting solely of CNOT gates $(x,y)\mapsto(x,x\oplus y)$ and SWAP gates $(x,y)\mapsto(y,x)$ and that computes the linear transformation $L$. Said differently, let $w(L)$ be the least number of elementary row operations on $F_{2}^{n}$ needed to produce the linear transformation $L$.

Let $w^{\sharp}(L)$ be the gate count of the smallest reversible circuit with an arbitrary amount of ancilla/garbage bits that computes the linear transformation $L$. Let $\iota_{+m}:F_{2}^{n}\rightarrow F_{2}^{n}\oplus F_{2}^{m}$ be the function where $\iota_{+m}(x)=(x,0)$ and let $\pi_{-m}:F_{2}^{n}\oplus F_{2}^{m}\rightarrow F_{2}^{n}$ be the projection mapping where $\pi_{-m}(x,y)=x$ whenever $x\in F_{2}^{n},y\in F_{2}^{m}$. Define
$w^{\sharp}(L)=\min\{w(M)\mid M:F_{2}^{n}\oplus F_{2}^{m}\rightarrow F_{2}^{n}\oplus F_{2}^{m},L=\pi_{-m}M\iota_{+m}\}.$ We say that $L$ is strongly reversible if $w(L)=w^{\sharp}(L)$.

For each $n$, let $t_{n}$ be $\max(w(L):L:F_{2}^{n}\rightarrow F_{2}^{n},w(L)=w^{\sharp}(L)\}$.

What are some lower and upper bounds on the constants $t_{n}$?
Does there exist an efficient (probabilistic) algorithm such that on an input $n$ the algorithm returns a linear transformation $L:F_{2}^{n}\rightarrow F_{2}^{n}$ such that either

a. $L$ is strongly reversible and $w(L)=t_{n}$,

b. $L$ is strongly reversible and $W(L)$ is near $t_{n}$, or

c. (with probability at least $1-o(2^{-n})$) $w^{\sharp}(L)$ is near $w(L)$ (by near, I will accept
$w(L)-w^{\sharp}(L)\leq n$) and $w(L)$ is large (here we shall informally call $L$, nearly reversible).

Can a linear transformation obtained by iterating a linear cellular automata over $F_{2}$ of dimension $1$ or $2$ be reversible or nearly reversible (I do not care if you have special boundary conditions or if the cellular automata is on a torus)?

The motivation for this question is that I want to know if and when reversible computation produces a significant computational overhead when computing invertible linear transformations over a vector space over $F_{2}$.


texts: On "The Power of the Prover" in Arora and Barak

texts:
In section 8.4 of Arora and Barak, after describing the public coin protocol for $\mathsf{GNI}$ and $\mathrm{IP=PSPACE}$, the authors state:

A curious feature of many known interactive proof systems is that in order to prove membership in language $L$ the prover needs to do more powerful computation than just deciding membership in $L$.  We give some examples.

The public coin system for graph nonisomorphism in Theorem 8.13 requires the prover to produce, for some randomly chosen hash function $h$ and a random element $y$ in the range of $h$, a graph $H$ such that $h(H)$ is isomorphic to either $G_1$ or $G_2$ and $h(x)=y$. This seems harder than just solving graph non-isomorphism (though we do not know of any proof that it is).

I believe the intent was:

...a graph $H$ such that $H$ is isomorphic to either $G_1$or $G_2$ and $h(H)=y$...

although I can't find it in any errata.
But more importantly, I believe the comment was to the effect of "finding preimages of hashes can be challenging, and the only obvious way for Merlin to execute the public coin $\mathsf{GNI}$ protocol is to go through each and every permutation $\pi$ of $G_1$ or $G_2$ and calculate $h(\pi(G_i))$ until he finds an $h(\pi(G_i))=y$."
But is it the case that all such public-coin protocols put a heavy burden on the prover?  For example, the hash $h$ is not required to be difficult to invert; it just needs to be strongly universal, which, as I understand, is not the same as being one-way.  So if Arthur were to give Merlin an image $y$ for some "easy-to-invert" hash function $h$, then it might not be so difficult for Merlin to find the preimage.

Is that the right interpretation of Arora and Barak?  Has there been any progress on Arora and Barak's statement?

Answers to this question suggests that it is an open question as to whether an interactive proof for a problem in $\mathrm{coNP}$ requires the prover to do as much work as a $\mathrm{\#P}$ machine.


texts: Defining finite sets inductively in a proof assistant?

texts:
To represent finite sets within coq, we either use something like ListSet, which are just definitions on top of list, or we build something like Compcert.Map, and then we define a set A as a map from A to ().

However, neither of these approaches manage to define sets inductively. What I want to know is a way to define a set type in the form of:

Inductive set (A: Type) : Type :=
 nil: set A | add: A -> set A -> <fill in the blanks> -> set A

Is it possible to have such an "inductive definition" for finite sets? If not, can I be supplied with a proof of why not?

My intuition is that such a thing is not possible, because an inductive type allows for equational reasoning, while sets cannot be equationally reasoned with:

$$
\texttt{add}~(1, \emptyset) = \texttt{add}(1, \texttt{add}(1, \emptyset)) \quad \text{(union is idempotent.)}
$$

however:

add 1 (add 1 nil) <> add 1 nil

So we will always have to go through some "extensional interface". Unfortunately, I don't know how to prove such a thing!


texts:
This problem came out of my recent blog post, suppose you are given a TSP tour, is it co-NP-complete to determine if it is a minimal one?

More precisely is the following problem NP-complete:

Instance: Given a complete graph G with edges weighted with positive integers and a simple cycle C that visits all the nodes of G.

Question: Is there a simple cycle D that visits all the nodes of G such that the total weight of all the edges of D in G is strictly less than the total weight of all the edges of C in G?


texts:
A DFA has a synchronizing word if there is a string that sends any state of the DFA to a single state. In ‘The Cerny Conjecture for Aperiodic Automata” by A. N. Trahtman (Discrete Mathematics and Theoretical Computer Science vol. 9:2, 2007, pp.3-10), he wrote,

  Cerny conjectured in 1964 that every
  n-state synchronizable DFA possesses a
  synchronizing word of length at most
  $(n-1)^2$.

He also wrote, "in the case when the underlying graph of the aperiodic DFA is strongly connected, this upper bound has been recently improved by Volkov who has reduced the estimation to $n(n + 1)/6$.

Does anybody know the current status of Cerny conjecture?
And in which paper Volkov obtained the result n(n+1)/6 ?

Thanks for any pointer or link.


texts: Implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model

texts:
What are implications of $\mathsf{P}\neq\mathsf{NP}$ in $\mathsf{BSS}$ model to $\mathsf{Turing}$ model and $\mathsf{Valiant's}$ counting complexity model?

In opposite direction what are implications of $\mathsf{P}=\mathsf{NP}$ in $\mathsf{BSS}$ model to $\mathsf{Turing}$ model and $\mathsf{Valiant's}$ counting complexity model?


texts: Is there a computer science equivalent page for this: "How to become a GOOD Theoretical Physicist"?

texts:
http://www.staff.science.uu.nl/~gadda001/goodtheorist/

I was wondering if any one has come across a page similar to the above but for CS.


texts: Good codes decodable by linear-sized circuits?

texts:
I'm looking for error-correcting codes of the following type:

binary codes with constant rate,
decodable from some constant fraction of errors, by a decoder implementable as a Boolean circuit of size $O(N)$, where $N$ is the encoding length.

Some background:

Spielman, in Linear-Time Encodable and Decodable Error-Correcting Codes, gave codes decodable in $O(N)$ time in the logarithmic-cost RAM model, and also decodable by $O(N \log N)$-sized circuits.
Guruswami and Indyk gave an improved construction in Linear Time Encodable/Decodable Codes with Near-Optimal Rate.  They don't analyze the resulting circuit complexity, although I believe it is also $\Theta(N \log N)$.

Thanks in advance!


texts: The distribution on the solution space induced by randomized rounding

texts:
Consider the Goemans-Williamson algorithm for the MAX-CUT problem.
It is known, that if $maxcut(G) \geq 1-\epsilon$, then
the algorithm returns a cut $S$ of fractional size at least $1-\sqrt{\epsilon}$.

What is known about the distribution on such cuts, as induced by the hyperplane
randomized rounding procedure?

For example, is it known whether or not $S$ is distributed uniformly over the
cuts of size at least $1-\sqrt{\epsilon}$.

To place in context, it is known for example, that if one allows $\Omega(n)$ levels of SDP / Lasserre relaxations, then one can force the output distribution to be uniformly random on the set of exact MAX-CUTS, so essentially the question is whether or not such behavior holds in a similar way for lower-level (and efficiently-computable) levels of SDP.


texts:
I am looking for an extension for Levenshtein distance (Edit distance) for multi dimensional strings (2D and 3D). I am not sure if there is a formal definition for multi dimensional or not, but here is what I am talking about:

1-D string: is the regular string

2-D string: is something like a list of 1-D strings like

dfdsfdsfdsf
dsffgdfdgfdsdaf
dsfdsf
fdgfdgfdg

N-D string: is list of (N-1)-D strings


texts: Tardos Function Counterexample to Blum's $P\neq NP$ Claim

texts:
In this thread, Norbet Blum's attempted $P \neq NP$ proof is succinctly disproved by noting that the Tardos function is a counterexample to Theorem 6.

Theorem 6: Let $f \in \mathcal{B}_n$ be any monotone Boolean function. Assume that there is a CNF-DNF-approximator $\mathcal{A}$ which can be used to prove a lower bound for $C_m(f)$. Then $\mathcal{A}$ can also be used to prove the same lower bound for $C_{st}(f)$.

Here's my problem: the Tardos function is not a Boolean function, so how does it satisfy the hypotheses of Theorem 6?

In this paper, they discuss the complexity of the function $\varphi(X) \leq f(v)$, which is not in general a monotone Boolean function, since increasing edges can make $\varphi(X)$ larger to make $\varphi(X) \leq f(v)$ false when it was true with fewer $1$'s in the input. The function $\varphi(X) \geq f(v)$ does not, in general, compute $1$ on $T_1$ and $0$ on $T_0$.

In fact, the test sets $T_1$ and $T_0$ are chosen precisely so that computing $1$ on $T_1$ and $0$ on $T_0$ with monotonicity means your function in precisely computing CLIQUE (they define the boundary of the $1$'s and $0$'s in the lattice of inputs), so these remarks imply that the Tardos function is the same as CLIQUE, which is clearly not true.

Yet, so many people -- and such knowledgeable people -- claim that the Tardos function provides an immediate counterexample, so there must be something I'm missing. Could you please provide a detailed explanation or proof for those of us who are interested parties but not quite on your level?


texts:
The subgradient algorithm for minimizing a convex function $f(x)$ is the update rule
$$ x(t+1) = x(t) - \alpha(t) d(t)$$ where $d(t)$ is any subgradient of $f(x)$ at $x(t)$ and
$\alpha(t)$ is a decaying stepsize. Choosing $\alpha(t) = 1/\sqrt{t}$, one usually
obtains the bound
$$ f \left( \frac{\sum_{j=1}^t \alpha(j) x(j)}{\sum_{j=1}^t \alpha(j)}\right) - f^* \leq O \left( \frac{||x(0) - x^*||_2^2 + L \ln t}{ \sqrt{t}} \right)$$ where $L$ is an upper bound on the norm of all the subgradients that appear by time $t$, and we assume that the optimal value is $f^*$.

There are a number of puzzling things about the subgradient method that I don't feel I have a good handle on.

Why is the bound for a convex combination for $x(1), \ldots, x(t)$ instead of for $f(x(t))$? Is it possible to derive a similar bound for $f(x(t))$? Specifically is it true that $f(x(t))-f^* = O( \log t/t)$ (taking $L$ and $||x(0)-x^*||^2$ as constants in the O-notation)?If not, is there a clear reason why this is unreasonable?
I think I understand why the bound is on $f(\cdot) - f^* $ rather than on the distance $||x(t)-x^*||_2^2$ - it has to do with functions that are nearly flat. For example, if $f(x)$ is a tiny perturbation of the zero function, it may take a while for the subgradient algorithm to find the optimal point. So, suppose we assume that every subgradient that enters the method has norm at least $l>0$. Does that allow us to derive a similar bound on $||x(t) - x^*||_2^2$?

Note: I asked this question on mathoverflow a week ago where it attracted no responses.


texts: Automatic proofs or model checking in an extremely simplified functional language

texts:
Imagine a stripped down functional programming language, that has the following properties

The only value type is an integer
There are no side effects
Functions are defined as a single expression, value of which becomes the return value of the function.
Program consists of zero or more function definitions and an expression. The expression can be defined in terms of the previously defined functions. Value of that evaluated expression is the result of the program.
Aside from simple arithmetic, there is only an if then else fi expression
The only way to do looping is through recursion

A program can then look like

f(x) = r(x+1,1)
r(x,y) = if x-(y*y) then r(x,y+1) else y*y fi

f(2)

so f() computes the second power of the given argument.

My question is, whether it is possible with current automated tools to prove theorems about such programs without human assistance. And what exactly?

Is it for example possible to automatically say for sure that for two functions f and g for every x: f(x) = g(x) ?


texts: How to design concurrent data structures?

texts:
I previously asked this question on Programmers.SE, without success.

I'm looking for written learning resources on how to design concurrent data structures. I'm more interested in the design process (e.g., identifying the right invariants) than in the final product (a full code listing).

For a concrete example: I really enjoyed Chris Okasaki's book “Purely Functional Data Structures”, because it's more than just a reference - it guides the reader through the design of its data structures and algorithms. Often, the book motivates a tricky or non-obvious design by first giving a more naïve version, and only then refining it until the desired time complexity (either worst-case or amortized) is achieved. This is the kind of thing I'm looking for.

So:

What techniques or heuristics exist for designing concurrent data structures?
Are there any books, papers, blog posts, tutorials, etc. explaining these techniques and heuristics?


texts: Any results on binary boolean CSP beyond the fixed-parameter tractability of almost 2SAT problem?

texts: Let $\varphi$ be a 2CNF formula and $k$ a nonnegative integer. It is proved in this paper that the problem of deciding whether one can delete at most $k$ clauses to make $\varphi$ satisfable, is fixed-parameter tractable, where $k$ is the parameter. My question is whether there are some work that generalize this result to other binary boolean CSP? (That is, to decide whether one can delete at most $k$ constraints to make some CSP instance satisfiable, parameterized by $k$) Or any negative results?


texts: Upper bound on the number of vertex-transitive graphs

texts: Is there a known upper bound on the number of vertex transitive graphs on $n$ vertices?


texts: Can a measurement commuting with the stabilizer of a state disturb the state?

texts:
In Nielsen and Chuang's "Quantum Computation and Quantum Information", Section 10.5.3, the authors claim the following:

  With a system in state $|\psi\rangle$ with stabilizer $g_1,...,g_n$, if a measurement $g$ that is commute with all $g_i$ is applied to the state, then either $g$ or $-g$ is a stabilizer of the system and the measurement doesn't disturb the state.

However, it seems to me that there is a simple counterexample:

  Let $g$ be the $Z_1$ operator in the system, thus it commutes with all stabilizers as $g|\psi\rangle$ is still a valid state in the system. However neither $g$ nor $-g$ is a stabilizer of the code.

Am I missing anything or the quoted claim is indeed false?


texts:
A linear extension $x_1 x_2 \ldots x_n$ of a partially ordered set (poset) is said to have $k$ jumps if there are $k$ occurrences of consecutive elements that are incomparable with each other -- i.e., $x_i \parallel x_{i+1}$.  The jump number of a poset $P$ is the minimum number of jumps in any of its linear extensions.  Finding the jump number of a general poset has long been known to be NP-hard [Pulleyblank 1981].  It remains NP-hard for interval posets (posets that admit a representation of elements by intervals in one dimension; an interval that is wholly before another is less than it in the poset).
There are 3/2 approximation algorithms for interval posets [Syslo 1995], and an improvement to 89/60-approximation [Krysztowiak 2013] for the same class of posets.
My question is: what is known about approximating the jump number in the general case?  Are there approximation algorithms for the general case, and what approximation ratio do they achieve?


texts:
You are given N points on 2-D plane. How can I find out minimal radius of a circle which contains at least M of these points?

algorithm for code

I searched for smallest enclosing circle problem but that was not for at least m?


texts: Counting the number of connected components in a dynamic plane graph

texts:
I'm working on the following problem: let $G = (V, E)$ be a connected, planar graph. Our goal is to find a $d$-partition of $G$, $P = \{V_1, \ldots, V_d\}$, such that $G[V_i]$ is connected, and $\min_{V_i \in P} |V_i|$ is maximized. (That is, the partitions are as balanced in size as possible.) This is the balanced connected partition problem on planar graphs, and is known to be NP-complete.

I'm trying to use hill-climbing to solve this problem. Let $C$ be a $|V|$-length array, such that $C[i] = j$ implies that vertex $i$ is in $V_j$. This represents a partition $P_C$ of $V$, such that $V_k = \{i \in V \mid C[i] = k\}$. Let $G_C = (V, E_C)$ be the corresponding graph $\bigcup_{V_i \in P_C} G[V_i]$. Thus, $E \setminus E_C$ is the set of all edges $(u, v)$ such that $u$ and $v$ are in different vertex subsets.

A "move" in this space (for the purposes of hill-climbing) is performed as follows. Let $N(v) = \{w \in V \mid (w, v) \in E\}$ be the neighbors of a vertex $v$ in the original graph. Let $(u, v)$ be an edge in $E \setminus E_C$. For all $w \in N(v)$, if $C[w] = C[v]$, remove $(w, v)$ from $E_C$; otherwise, if $C[w] = C[u]$, add $(w, v)$ to $E_C$. This induces a different partition, one where $v$ is in $u$'s subset.

It's of course possible that the graph induced by these partitions contains more than $d$ connected components. I want to penalize these, proportional to the absolute difference between the number of connected components in the graph and $d$. The problem is that finding these connected components is expensive—$O(|V| + |E|)$ time per step—and I'd like to reduce that.

I did some snooping around in the space of fully dynamic graph connectivity algorithms. For general graphs, Holm et al. (see [1]) achieve $O(\log^2 n/\log \log n)$ insert/delete and $O(\log n/\log \log n)$ connectivity queries (i.e., are $u$ and $v$ connected?) by using Henzinger and King's Euler-tour trees (see [2]). For planar graphs, Eppstein et al. (see [3]) achieve $O(\log n)$ insert/delete/connectivity.

The problem is that I'm not sure that it's trivial to adapt any of these results to my problem, since I'm not sure that transforming connectivity queries into connected-component counts is easy or possible. The other thing is that those results support general edge insertion and deletion, which is good, but I want to know if I can exploit the fact that I know all of the edges that can ever be inserted or deleted ahead of time to do some precomputation and speed up connected component counting.

I've also had the following insight. Let's say we move $v$ to $u$'s subset as described above. Call the original graph $G_1$ and the new graph $G_2$. Then the number of connected components in $G_2$ is the number of connected components in $G_1$, minus the number of vertices $w$ in $N(v)$ that weren't connected to $u$ before but are now (i.e., every path from $u$ to $w$ goes through $v$), plus the number of bridge edges $(w, v)$ for $w \in N(v)$ and $C[w] = C[v]$ (i.e., the number of $v$'s neighboring edges that, upon removal break connectedness of $v$'s original subset).

Does anyone know of any kind of solution to this problem? Or does anyone have any suggestions for papers to read?


texts:
A linear PRAM model is a PRAM model without bit operations and at least one operand of the $\times$ instruction is a constant. If in addition we require that the running time does not depend on the bit length of the input then the resulting model is called the arithmetic linear PRAM model.

This 1999 paper (ps file) of Ketan Mulmuley says "we do not know a natural example that is in the linear PRAM model but not in the arithmetic linear PRAM model". I am wondering if such an example is found in the last decade. Are there any potential candidates ?


texts: Is the "Fewest Discriminating Bits" problem NP-complete?

texts:
That is a name I have made up for this problem.  I have not seen it described anywhere before.  I have not been able to find a proof of NP-completeness nor a polynomial time algorithm for this problem yet.  It is not a homework problem -- it is related to a problem I have come across in my work.

FEWEST DISCRIMINATING BITS

INSTANCE: A set T containing bit vectors, where each bit vector is exactly N bits long.  Every element of T is unique, as one would expect from a set in math.  An integer K < N.

QUESTION: Is there a set B of at most K bit positions (i.e. integers in the range [0,N-1]) such that when we remove all bits except those in B from every vector in T, the remaining shorter vectors are all still unique?

Example 1: For the instance N=5, T={00010, 11010, 01101, 00011}, K=2, the answer is yes, because we can select the bit positions B={0,3}.  Using the convention that bit position 0 is the rightmost, and the bit position numbers increase right-to-left, removing all bit positions except those in B from the vectors in T leaves T'={00, 10, 11, 01}, and those are all unique.

Example 2: N=5, T={00000, 00001, 00010, 00100}, K=2.  The answer is no, because no matter which two bit positions we select, none of the 2-bit vectors will be equal to 11, so at least two of the 2-bit vectors will be equal to each other.

We can of course solve this problem by enumerating all (N choose K) subsets with size K of the N bit positions, and determining which satisfy the condition of the question.  However, that is exponential in the input size.


texts:
The mean of a positive random variable $X$ is either finite or infinite; define $J(X)$ to be $0$ in the former case and $1$ in the latter case. Claim: there does not exist a function $J_n$ from the iid sample of size $n$ to $\{0,1\}$ such that
$J_n\to J(X)$ in probability.
This claim (which is undoubtedly true) appears to be folklore knowledge among statisticians, but I have not been able to find a formal proof in the literature. The closest result I could find is the one by
Hawkins, which proves the impossibility of a sequential test with finite stopping time.
Can anyone give a pointer to a book/paper where the folklore claim is formally proven?


texts:
Let's try to generalize the $VC$-dimension (of the class of hyperplanes) to include accuracy/error.  Let $S$ be a set of points in $R^d$ and $t$ in $[0,1]$.  We say that the class of hyperplanes $t$-shatters $S$ if for every binary labeling of the points in $S$, there exists some hyperplane which separates $S$ with accuracy at least $t$ (i.e., at least $t*|S|$ of the points in $S$ are classified correctly by the hyperplane).  We then define the $VC(t)$-dimension of the class of hyperplanes (in a feature space of dimension $d$) to be the size of the largest set $S$ which the hyperplanes $t$-shatter, i.e.,

$VC(t) = max_{S \subset R^d}{|S|}$, subject to the constraint that the hyperplanes $t$-shatter $S$.

For example, the usual VC-dimension is $VC(1)$.  So $VC(1)=d+1$.  $VC(t)$ is clearly nonincreasing in $t$.  $VC(0)=\infty$ (in fact, I think $VC(0.5)=\infty$).

Question:  Have people studied this generalization of VC-dimension, or something similar?  If so, what is it called, and can you point me to resources about it?  What is the best lower bound on $VC(t)$?  Thanks!

Edit: Here's the motivation for my question.  For any set of non-coplanar $d+1$ points in $R^d$, and any binary labeling of these points, there is a linear classifier (a hyperplane) which classifies these points with 100% accuracy.  More generally, given $n>d+1$ points (satisfying some "weak" condition like non-coplanarity) and a binary labeling of them, what can we say about the accuracy of a linear classifier for these points?  If $t \in [0,1]$ and $VC(t) \geq n$, then we know that for any $n$ points in $R^d$ (satisfying some "weak" condition) and any labeling of these points, there is a linear classifier which has accuracy at least $t$ on these points.


texts: Problems with exponential lower computational complexity bound

texts:
I am looking for problems which have an algorithm with asymptotically optimal exponential computational complexity or the problem has a lower bound of exponential computational complexity for algorithms to solve the problem.

I am not looking for problems, where this is implied because the solution can be exponential in size.

If you know any, it would be very kind if you can share it with me.


texts: Finding odd holes in circulant Paley graphs

texts:
The Paley graphs Pq are those whose vertex-set is given by the finite field GF(q), for prime powers q≡1 (mod 4), and where two vertices are adjacent if and only if they differ by a2 for some a ∈ GF(q). In the case that q is prime, the finite field GF(q) is just the set of integers modulo q.

In a recent paper, Maistrelli and Penman show that the only Paley graph which is perfect (having a chromatic number equal to the size of its largest clique) is the one on nine vertices. This implies, in particular, that none of the Paley graphs Pq are perfect for q prime.

The Strong Perfect Graph Theorem asserts that a graph G is perfect if and only if both G and its complement lacks odd holes (an induced subgraph which is a cycle of odd length, and size at least 5.) The Paley graphs of prime order are self-complementary, and imperfect; therefore they must contain odd holes.

Question. For q≡1 (mod 4) prime, is there a poly(q) algorithm for finding an odd hole in Pq? Is there a polylog(q) algorithm? Randomness and popular number-theoretic conjectures are allowed.


texts: Graph planar drawing, with each edge's length is known

texts:
Assuming I have a graph $G$, with edges $E$ and vertices $V$, and the length of each edge is known, but the coordinates of vertices are not.

Further assume that this is a graph that can be embedded on a 2D plane, what is the algorithm that can create a "nice" drawing with no edge intersection?

Obviously there are many ways the graph can be drawn, and the definition of nice is a bit fuzzy (for practical purpose I would define it as something that is pleasing to the human eyes), but I would only need a good enough algorithm for this.

Note there could be many graphs with its embedding and I frankly don't care the algorithm gives me which, as long as it is pleasant looking enough and it has all the above constraint satisfied.

The motivation for this question is this: imagine that you have to design a circuit layout, the path that connects between two electronic components is $E$, and the vertex of each component is $V$, as a part of your engineering design you know that the distance between each component is pre-specified. As a designer, you would have to arrange the components on the board so that it looks nice. How can you design the circuit layout?


texts: Lower bounds for nonuniform circuits and oracles separating complexity classes

texts:
I have read that Furst, Sax, and Sipser came up with their lower bound for nonuniform AC0 while trying to prove an oracle separation.

Can someone explain how proving lower bounds for circuits and constructing oracles separating complexity classes are related?
Are there other circuit lower bounds related to separating oracles?
Is there a general theme connecting nonuniform lower bounds for circuits and  separating oracles?


texts: Impagliazzo lemma, unclear detail in its proof

texts: In Arora-Barak's book on page 378 in the proof of Impagliazzo's Hard Core lemma why did they choose the number 50 in this line: Set $t = \frac{50n}{\epsilon^2}$ ? How this choice then yields the size of $S'=\frac{\epsilon^2 S}{100n}$ from the top line on that page $378$ ?


texts:
Alice has a vector $x \in [r]^d$ and Bob has $y \in [r]^d$, where $[r] \stackrel{\rm def}{=} \{0,1,\dots,r\}$. Alice send a message $M(x)$ to Bob and Bob wants to estimate the inner product $\left<x,y\right>$ with multiplicative error $\epsilon$ with probability $1 - \delta$.

My question is. Is there any known lower bound on $|M(x)|$? My intuition tells me that Alice pretty much has to estimate each coordinate of $x$ up to $\epsilon$ precision since Bob can have an input that zeros out all but one of the entry. Does that give you something like $\Omega(d \log 1/\epsilon)$?


texts: Head variables of terms after application

texts:
We work in the Church-style simply typed lambda calculus. All terms shall be considered in long normal form. Any term of type $A_1\rightarrow A_2\ldots\rightarrow A_n \rightarrow 0$ is of the form $\lambda y_1 y_2 \ldots y_n . y_i u_1 u_2 \ldots u_m$. In this case, we shall say that $i$ is the index of this term.

My question is, does every term of a type with multiple components (that is, $n$ is greater than $1$ in the example above) behave as a function with respect to indices? Namely, given two terms of the same index of type $A_1$ above, would both return terms of type $A_2\ldots\rightarrow A_n \rightarrow 0$ with the same index?


texts: Existence of $opt^c$-approximation of Dominating Set with $c < 1$?

texts:
Consider the Dominating Set problem in general graphs, and let $n$ be the number of vertices in a graph. A greedy approximation algorithm gives an approximation guarantee of factor $1 + \log n$, i.e. it's possible to find in polynomial-time a solution $S$ such that $|S| \leq (1 + \log n) opt$, where $opt$ is the size of a minimum dominating set. There are bounds showing that we cannot improve the dependency on $\log n$ much http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf.

My question: is there an approximation algorithm which has a guarantee in terms of $opt$ instead of $n$? In graphs where $n$ is very large with respect to the optimum, a factor-$\log n$ approximation would be much worse than a factor $\log opt$ approximation. Is something like that known, or are there reasons why this cannot exist? I am happy with any polynomial-time algorithm which produces a solution $S$ such that $|S| \in O(opt^c)$ for some constant $c$.


texts:
I have a doubt regarding the "effects" in Program Graph. Below is the image from the book Principle of Model Checking from Christel Baier and Joost-Pieter Katoen
(The MIT Press Cambridge, Massachusetts London, England)

I know what interleaving means and also I know what Effects are. As per my knowledge, effects are nothing but the result of the action on your variable (correct me if I am wrong). What does the Greek letter "η" mean?
In the book, it states that η is the evaluation, but can somebody please elaborate it me with respect to the below example?

Example 2.14. Beverage Vending Machine
The graph described in Example 2.12 (page 29) is a program graph. The set of variables is
Var = { nsoda, nbeer }
where both variables have the domain { 0, 1, . . . , max }. The set Loc of locations equals {start, select} with Loc0 = {start}, and
Act = { bget , sget, coin, ret coin, refill }.
The effect of the actions is defined by:
Effect(coin, η) = η
Effect(ret_coin, η) = η
Effect(sget, η) = η[nsoda := nsoda−1]
Effect(bget, η) = η[nbeer := nbeer−1]
Effect(refill, η) = [nsoda := max, nbeer := max]

Why is the Effect(coin, η) = η and Effect(ret_coin, η) = η?
Thank you very much.


texts: Looking for papers and articles on the Tarskian Möglichkeit

texts:
Some background: Łukasiewicz many-valued logics were intended as modal logics, and Łukasiewicz gave an extensional definition of the modal operator:
$\Diamond A =_{def} \neg A \to A$ (which he attributes to Tarski).

This gives a weird modal logic, with some paradoxical, if not seemingly absurd theorems, notably $(\Diamond A\land \Diamond B) \to \Diamond (A\land B)$. Substitute $\neg A$ for $B$ to see why it's been relegated to a footnote in the history of modal logic.

However, I've realised that it's less absurd when that definition of a possibility operator is applied to Linear Logic and other substructural logics.
I have an informal talk about this earlier in the month. A link to the talk is at http://www.cs.st-andrews.ac.uk/~rr/pubs/lablunch-20110308.pdf

(One of the reasons that I asked about substructural modal logics was to compare the expressiveness of those logics with the use of this operator.)

Anyhow, the only non-critical work that I found a reference to is a talk by A. Turquette, "A generalization of Tarski's Möglichkeit" at the Australasian Association for Logic 1997 Annual Conference. The abstract is in the BSL 4 (4),
http://www.math.ucla.edu/~asl/bsl/0404/0404-006.ps Basically Turquette suggested applications in $m$-valued logics for $m$-state systems. (I've not been able to obtain any notes, slides or other content of this talk, so I would appreciate hearing from anyone who has more information.)

Is anyone here aware of other articles or papers on this?

(I don't have any applications for it, but I find the properties to be interesting enough to merit a paper.)


texts: Oracle complexity of a problem in the Counting Hierarchy

texts:
In "On The Complexity of Numerical Analysis" (SIAM J. Comp. Vol. 38, 2009), Allender et al. introduce the problem of PosSLP and show that its complexity lies in the counting hierarchy, and more precisely in
$P^{\mathit{PP}^{\mathit{PP}^{\mathit{PP}}}}$.

I have a problem, call it $X$, that I have shown can be solved in
$\mathit{NP}^{\mathit{PosSLP}}$. Can I correctly conclude that $X$ lies in
$\mathit{NP}^{\mathit{PP}^{\mathit{PP}^{\mathit{PP}}}}$?


texts:
Possible Duplicate:
  Producing more functional dependencies (FDs) from a list of functional dependencies (FDs)

I am currently trying to understand functional dependencies and their properties. I am looking at an example, but when I try to apply the rules I can't see to get the same answers. The question is:

  Question: Given a relation T(A,B, C,D)
  and functional dependencies AB -> C,
  BC -> D,CD -> A AD -> B What FD’s
  follow from the given FD’s?

  Answer: AD -> CD,AD -> BC,CD -> AB.

When applying the properties of functional dependencies I can't even see how they get the first answer (AD -> CD). If anyone could give me an idea of how we get to the first answer, maybe I can solve the rest myself.

PS: This is NOT homework (as I already have the answer!), but I am revising for an important exam and I need to understand these concepts.

Thanks!


texts: Computational complexity problem book with solution recommendation?

texts:
I will be taking complexity class next quarter and we will use the book "B. Barak, S. Arora, Computational Complexity: A Modern Approach". However, I have little exposure to complexity before and I think the most efficient way to learn anything is to read a bunch of example problems with solutions.
This book has no solution and I wonder if there are books that cover similar topics have solutions to their exercise.


texts: Known and described subclasses of Context-Free Grammars class

texts:
I'm looking for various researches which consider specific subclasses of Context-Free Grammar class, i.e. some specific described cases, which differ from well-known:

deterministic/non-deterministic
ambiguous/unambiguous
regular/non-regular

As an example of such "non-standard" subclasses are Visibly pushdown grammar described here. Any additional examples will be much appreciated.

More specifically, I'm wondering, are any described subclasses which can help distinguish this two very similar cases?

$G_1$:

$S\rightarrow aD$, $S\rightarrow cD$

$D\rightarrow abc$, $D\rightarrow abDc$

$G_2$:

$S\rightarrow aD$, $S\rightarrow cD$

$D\rightarrow abc$, $D\rightarrow abDc$, $D\rightarrow aDb$, $D\rightarrow aDc$

It is clear that both of them are unambiguous non-determ. CFG, and $\mathcal{L}(G_1)\subset\mathcal{L}(G_2)$. But these are common properties, I'm looking for specific differences.


texts: Approximate matching in table of integer vectors

texts:
Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving.

I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain 0-N sorted numbers from range [0,N-1].

Now I have a query vector Q, that - similarly to vectors in the list - can contain 0-N sorted numbers from range [0,N-1]. I have to find time efficient way of finding all vectors in the table that have Jaccard similarity coefficient (T) of k or more.

In this particular case, Jaccard similarity coefficient between two vectors a and b is defined as:

Tqb = Nqb / (Nq + Nb - Nqb)

where Nq and Nb are lengths of vectors and Nqb is the number of common elements.
The naive solution is to compute Tqb between Q and every vector from the table and discard those for which Tqb < k. A little bit better solution is to precompute vectors lengths and consider only vectors of length L such that:

T * Nq <= L <= Nq / T

where Nq is the length of the query vector Q.

Another trick is to notice that out of any

Nq − T * Nq + 1

elements chosen at random from the query vector Q, at least one must be present in any other vector to achieve a similarity above the threshold k.

After applying those two constraints the algorithm is still too slow. The lower the threshold k is, the more vectors pass constraint filtering and the longer it takes to compute coefficient. But unfortunately 'longer' means here exponentially longer not linearly longer, probably due to exponentially larger number of vectors passing filtering phase. Ideally, I would like to achieve constant time of finding similar vectors, regardless of k or Q. I'm not sure if this is possible, thought.


texts: Language in $PSPACE$ and not necessarily in $P$ if $P=PP$?

texts:
If $P=PP$ then the counting hierarchy collapses to $CH=P$. Because so many complexity classes are contained in $CH$, this causes most classes to now be contained in $P$. My question is whether this is true for all languages in $PSPACE$, or not.

  What is a candidate language $L\in PSPACE$ such that we do not know that $P=PP$ implies that $L\in P$?


texts:
I would like to practice on some problems for using LTL formulae but besides the foundations and theory there are only every few examples. I know that having understood theory is not enough. Where can I go looking for interesting applications, examples including discussions about it. Is it possible to open a thread with examples here?

E.g.

$(P\to \Diamond Q)$ is intriguing. One would think "On a path $\pi$ starting at state $s$ when P holds, eventually Q will hold." But of course given LTL formula does also hold for any other path which does not satisfy $P$ but $\Diamond Q$ (def. $\rightarrow$ or $\neg P \vee  Q$).

Now, this is not covered in theory in general. It is experience knowledge. I want to practice LTL formulae, where can I go looking for them?


texts: Classes with oracles forcing the caller to immediately accept (or reject)?

texts:
Usually an oracle operates as a black box, simply returning an yes or no answer to the machine calling it; once it has the result, the caller is free to proceed as it sees fit.

However, what happens if the caller must accept or reject (exactly one of the two) immediately as a function of the oracle's output? Say, for example, the caller has access to a SAT oracle, but must always accept (unconditionally) whenever the oracle answers with "yes"; this means the caller can continue its operation if and only if the query formula is unsatisfiable.

This imposes a restriction, obviously; are there cases in which this yields — or there is reason or evidence enough to suspect it yields — a strict subset of decision problems when compared to the "usual" behavior?

I am particularly interested in the case of $\mathsf{P}^{\mathsf{NP}}$ or similar classes in the polynomial hierarchy, but other classes and oracles are relevant too.


texts: Are there other computer architectures apart fom the von neumann /turing architectures?

texts: Are there other computer architectures apart from the Von Neumann /Turing architecture?


texts:
Given a matrix $A$ with distinct eigenvalues, can I find a sparsest eigenvector of it in polynomial time?

It is tempting to say that one can simply compute the eigenvectors and pick the sparsest among them. However, I believe methods for computing eigenvectors do so with additive error. Indeed, since the eigenvectors may have irrational entries, computing them exactly is hopeless. And knowing the eigenvector with any fixed additive error may not give a definitive answer about whether a particular entry is zero or not.

Of course, this gives rise to the question of what, exactly, I mean by finding a sparsest eigenvector. I'm fairly flexible here - but for the sake of definiteness, let us say that if $v$ is some sparsest eigenvector, then I am happy with  an $\epsilon$ additive approximation $v^{\epsilon}$ to $v$ which has the further property that if $v_i=0$ then $v_i^{\epsilon}=0$.


texts:
The Minkowski sum of two sets of vectors $A, B \in R^d$ is given by

$$ A \oplus B  = \{ a + b \mid a \in A, b \in B \}$$

I just heard an interesting problem (attributed to Dan Halperin): Given a shape $B$, does there exist a shape $A$ such that $A \oplus A = B$ ?

But that's not my question (it appears to be an open problem). Observe that in the above problem, if $B$ is a convex set, then there exists a solution $A = (1/2)B$ since convex sets are closed under the taking of Minkowski sums.

Fix a class of shapes ${\cal S}$. We say that ${\cal S}$ is closed under Minkowski sums if for any $A, B \in {\cal S}, A \oplus B \in {\cal S}$.

So my question is:

  Is there a nice characterization of
  classes of shapes ${\cal S}$ that are
  closed under Minkowski sums ?


texts: Is it preferable to write $O(n2^n)$ or $O((2 + \epsilon)^n)$? If neither, what is the best way? Since I see a lot of papers with $O(1.42^n)$ instead of $O(2^{\frac{n}{2}})$ and similar transformations, I was wondering what people prefer.


texts: Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis

texts:
The Berman Hartmanis conjecture which formally states that there is an isomorphism for two $NP$ complete languages $L_{1}$, and $L_{2}$, the isomorphism is a bijective function $f()$ such that $f()$ maps strings from $L_{1}$ to $L_{2}$, such that $x \in L_{1}$ iff $f(x) \in L_{2}$. The isomorphism holds for all $NP$-complete languages under polynomial time assumptions(p-isomorphisms). Special conditions are: p-isomorphisms, polynomial run time $f()$, and so also the inverse of $f()$ is computable in polynomial time. The conjecture if true, would imply no $NP$-complete language is sparse. What are the analogues to the conjecture in various types of reductions, for example under $AC^{0}$ reductions the conjecture is true: Under $AC^{0}$ many-one reductions, all $NP$ complete languages do show an $AC^{0}$ isomorphism.

This leads one to the creativity conjecture, which is: Are all NP-creative sets  languages the same as NP-complete sets under $\leq^{m}_{p}$ reductions. Formally, creativity for a set is defined as: A set $A$ is creative if its complement is "productive". By "productivity" of a set $A$, over a class of languages $C$, we mean there is a function(not necessarily polynomial), that witnesses $A \notin C$. So, it is natural to think of problems to be creative under different conditions, eg, a polynomial time function $f$, or even under log time, or oracular function restrictions. So, while $AC^{0}$ many-one reductions give a resolution to the Berman-Hartmanis conjecture, is there resolution to the creativity conjecture under $AC^{0}$ reductions(or any other reasonable assumptions)?

Creativity(k-creativity), like the Berman-Hartmanis conjecture(truth of which shows that there are no sparse $NP$-complete languages), shows us another fine grained level nature of $NP$ complete problems. Are there $NP$ complete problems that show creative(k-creativity, for one) properties, and some don't. Are there natural problems that
that one would consider creativity, such that the $NP$-complete language is known to be creative (any variants of SAT)?


texts: What is a probabilistic function and where can I learn more about them?

texts:
I am reading a paper on privacy that says we can model something as an arbitrary probabilistic function from $X^M \to X^M$.  I'm trying to figure out what exactly that means.  I saw another paper that defined a probabilistic function as a function $\mathcal{F}:X \times Y \to [0, 1]$ that satisfied the condition $$\forall x \in X: \sum_{y \in Y} \mathcal{F}(x, y) \leq 1.$$  But that definition doesn't seem to make sense if the function can take on values in the space $X^M$ where $X$ is an arbitrary set of objects.  So what exactly are probabilistic functions?

Thanks so much!


texts:
This interesting paper http://www.math.hmc.edu/~su/papers.dir/leitzel.pdf is about how to motivate students during a course.

One of the idea is to add some "fun facts" during the course for some reasons explained in the paper. The author give the address of the following website:
http://www.math.hmc.edu/funfacts/
which is only for maths.

Are you aware of a similar website for TCS?


texts:
The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time.

You can do $O(n \log^2 n)$ time by applying FFT in a tree fashion. Can you do $O(n \log n)$?


texts: 1-D set cover optimisation with connected subsets

texts:
Given a 1-D universe $U$ (e.g. $\mathbb{Z}$) and a set-of-sets $\pmb{S}$, where each element of $\pmb{S}$ is a closed, connected subset of $U$ (e.g. $[a .. b]$ given $ a,b\in\mathbb{Z}$) and $\bigcup\pmb{S}=U$, what is the quickest way to find $\pmb{S}^*\subseteq \pmb{S}$ with the smallest cardinality such that $\bigcup \pmb{S}^* = U$?

In other words, is there a fast 1-D set cover optimisation algorithm given that the sets you're working from are closed-connected?

It seems to me that the naive greedy set cover will in fact be optimal here, but I'm not expert enough to prove it. Can anyone think of a counter-example?


texts: Is a "complete" symmetric cipher possible?  By this I mean a symmetric cipher that is provably secure under the assumption that a secure symmetric cipher exists.


texts: Edge-weight updates in all pair shortest path problem

texts:
I want to calculate all-pairs shortest paths on a graph with roughly 50,000 nodes representing a city-wide road network.  An answer to my previous question led me to Hiroki Yanagisawa's paper "A multi-source label-correcting algorithm for the all-pairs shortest paths problem" [IPDPS 2010] which is performing really well.

But what about updates?  I couldn't produce a technique which can update the shortest paths quickly when the weight of an edge changes.  On researching, I came across a paper "On Dynamic Shortest Path problems", which states that

  Reductions that show that the incremental and decremental single-source
  shortest-paths problems, for weighted directed or undirected
  graphs, are, in a strong sense, at least as hard as the static all-pairs
  shortest-paths problem.

So the question is: Are there useful heuristic approaches to solve this problem?


texts: Is NP-complete the existence of paths of a given length in a directed graph?

texts: Given a directed graph G= (V,E), a pair of vertices s and t, a natural number K encoded in binary, whether the problem to decide there exists a path (not necessarily simple) from s to t of length K is NP-complete ?


texts: Is there a notion of "inevitable reduction?"

texts:
I was just working on a semantics paper and realized I needed a notion of inevitable reduction. I came up with this definition:

  Let $\rightarrow$ be a binary relation. We say that $a$ inevitably reduces to $b$, or $a \rightarrow^{\forall *} b$, if either $a=b$ or, for all derivations $a \rightarrow x_1 \rightarrow x_2 \rightarrow \dots$ (where the $x_i$ are either infinite or terminate in a normal form), there is some $i$ such that $x_i = b$.

This seems way too simple and fundamental to not already exist, but I've never encountered it before. (I've read "Term Rewriting and All That" in full, and just took a skim through "Advanced Topics in Term Rewriting".) It's clearly related to confluence, and can also be stated in terms of dominators. Still, I have no leads for finding prior uses.

So, anyone know prior work on this?


texts: Fully Homomorphic Encryption over Integers

texts:
On the section 3 of the paper  Fully Homomorphic Encryption over the Integers, there is a construction of a somewhat encryption scheme, as follow:
key generation
Choose an odd η-bit integer $p$ in $(2Z + 1) ∩ [2^{η−1} , 2^η)$ to be the secret key.
For the public key, sample $x_i ← pq_i + r_i$ for $i = 0, ..., τ$, where $q_i \in Z∩[0, \frac{2^γ}{p})$ and $r_i \in Z∩(−2^ρ, 2^ρ)$.
Relabel so that $x_0$ is the largest. Restart unless $x_0$ is odd and $r_p(x_0)$ is even. The public key is $pk = \{x_0, x_1, ... , x_τ\}$ .
encryption
Choose a random subset $S ⊆ \{1,2, ..., τ \}$ and a random integer $r$ in $(−2^{2\lambda}, 2^{2\lambda})$, and output $c ← (m + 2r + 2 \sum_{i \in S} x_i) \mod x_0$
decryption
Output $m ← (c \mod p) \mod 2$
You can find more information on the paper (it's linked above).
So, I have some questions:
1 - Why we have to make $\mod p$ in decryption step? Since the sum is multiplied by two, we could just apply the $\mod 2$ to recovery the message $m$, couldn't?
----- BEGIN EDIT
There is a lemma that shows that $c$ is of the form $ap + (2b + m)$ for some integers $a$ and $b$, then, since $2b + m$ is smaller than $p$, we have $c \mod p$ equal to $2b + m$, then, $(c \mod p) \mod 2$ is equal to $m$.
Therefore, I consider this question 1 answered.
----- END EDIT
2 - What is the maximum number of adding and multiplications operations that we can do over the ciphertexts?
Any help will be appreciated.
Thank you very much.


texts: Sorted dictionary structure supporting efficient merges?

texts:
Many balanced tree structures (red/black trees, splay trees, etc.) and some other sorted dictionary structures (skiplists) support a join operation that takes in two dictionaries where all keys in the first structure are less than all keys in the second, then combines the two dictionaries into a single sorted dictionary in time $O(\log n)$, where $n$ is the total number of keys. However, this only works if there is no overlap in the ranges of keys stored in those trees.

Similarly, many priority queues (binomial heaps, Fibonacci heaps, etc.) support $O(\log n)$-time merges. These merges work regardless of what keys are stored, but given that the data structures are priority queues we can't do lookups for random elements in the resulting structure.

Is there a sorted dictionary structure that supports merges of arbitrary dictionaries in time $O(\log n)$ while simultaneously supporting normal sorted dictionary operations (insertions, deletions, lookups, successor/predecessor queries, etc.) in time $O(\log n)$, or a lower-bound proof that such structures can't exist?


texts:
Major edit on June 6, 2019: Replaced the target problem with a simpler (but equivalent) one.

Is the following problem NP-complete?

  Planar Exact Cover by even-size sets

  Input: A set $U$, a subset family $\mathcal{F} = \{F_1, \dots, F_{m}\} \subseteq 2^{U}$ with the two restrictions below.
  Question: Is there $\mathcal{F}' \subseteq \mathcal{F}$ such that each element of $U$ is included in exactly one set in $\mathcal{F}'$?

  Restriction 1: The bipartite graph $B = (U, \mathcal{F}; \{\{u, F_{i}\} \mid u \in F_{i}\})$ is planar.
  Restriction 2: $|F_{i}|$ is even for every $i$.

If we forget the 1st restriction, then the problem is NP-complete because of 4-dimensional matching.
If we replace the 2nd restriction with "$|F_{i}| = 3$ for every $i$", then the problem is NP-complete as Planar Exact Cover by 3-sets is NP-complete (1).

Martin E. Dyer, Alan M. Frieze.
Planar 3DM is NP-Complete. Journal of Algorithms 7(2) 174-184 (1986).
doi:10.1016/0196-6774(86)90002-7

Motivation: Such a restriction would be useful when subset gadgets can have only an even number of connections to the rest.

The old version of the problem is as follows:

  Planar Exact Cover by 2- and 4-sets (with at most three occurrences)

  Input: A set $U$, a subset family $\mathcal{F} = \{F_1, \dots, F_{m}\} \subseteq 2^{U}$ with all three restrictions below.
  Question: Is there $\mathcal{F}' \subseteq \mathcal{F}$ such that each element of $U$ is included in exactly one set in $\mathcal{F}'$?

  Restriction 1: The bipartite graph $B = (U, \mathcal{F}; \{\{u, F_{i}\} \mid u \in F_{i}\})$ is planar.
  Old restriction 2: Each element of $U$ appears in at most three sets in $\mathcal{F}$.
  Old restriction 3: $|F_{i}| \in \{2,4\}$ for every $i$.

The new problem can be reduced to the old one as follows.

Reducing the number of occurrences:
Assume that there is an element $u$ that appears in sets $F_{1}, F_{2}, \dots, F_{k}$ with $k \ge 4$.
We replace $u$ with three new element $x, u_{1}, u_{2}$ and then replace $F_{1}, \dots, F_{k}$ with $D_{1} = \{u_{1}, x\}$, $D_{2} = \{x, u_{2}\}$, and $F_{i}'$ for $1 \le i \le k$ such that
$F_{i}' = F_{i} \cup \{u_{1}\} \setminus \{u\}$ for $1 \le i \le 2$ and
$F_{i}' = F_{i} \cup \{u_{2}\} \setminus \{u\}$ for $3 \le i \le k$.
We can see that $u_{2}$ appears in $k-1$ sets.

Reducing set size:
Assume that there is a set $F_{i} = \{u_{1}, u_{2}, \dots, u_{2k}\}$ with $k \ge 3$.
We add two new elements $x, y$ to $U$ and then replace $F_{i}$ with three sets
$F_{i}^{(1)} = \{u_{1}, u_{2}, u_{3}\} \cup \{x\}$,
$F_{i}^{(2)} = \{x,y\}$, and
$F_{i}^{(3)} = \{u_{4}, \dots, u_{2k}\} \cup \{y\}$.
Observe that $|F_{i}^{(3)}| = 2k-2$.

Correctness: The reductions preserve the answer and the planarity. See the figure below.


texts: Shrinkage Exponent of Formulas over the Full Binary Basis

texts:
Håstad has shown that the shrinkage exponent of boolean formulas over the De Morgan basis is 2. In other words, if one keeps each variable of the formula alive with probability $p$ and restricts it with a uniform random bit otherwise, then the resulting formula can be shrunk by a factor of roughly $p^2$ in such a way that it computes the same function. This fact can be used to prove a $\Omega(n^2)$ lower obund for the parity on $n$ bits, and a
$\Omega(n^{3-o(1)})$ lower bound for Andreev's function.

I have the following questions:

The shrinkage exponent of a formula over the full binary basis is 1 (consider for instance the parity function). Is there some relaxation of the notion of shrinkage exponent which is greater than 1 for formulas over the full binary basis?
Has such a relaxation of the notion of shrinkage exponent been used to obtain lower bounds?


texts: Is it sometimes better to not publish at all?

texts: I hope this is not a politically incorrect question to ask, but for a PhD student who usually publishes at CCC/ITCS/ICALP (and occasionally at FOCS/STOC), could it be harmful (career-wise) to publish less significant works in less prestigious conferences (e.g. MFCS, FCT, STACS, IPL)? Could it be better to just leave such papers laying at ECCC/arXiv?