texts: Algorithms with multiple right answers --- complexity theory terminology

texts:
In standard complexity theory terminology, one wants to find Turing machines which decide membership in a language. For any given string, there is only one right answer --- either "yes" or "no."

But suppose we want a Turing machine $f$, which computes a function of its input $x$. We want to ensure that, for any $x$, we satisfy $A(x, f(x))$ where $A$ is some predicate. For example, given a graph $G$, we want to find some proper vertex-coloring of $G$. We don't care which one.

Many of the standard complexity theory notions have analogues in this model. For example, we may want $f$ to be a deterministic polytime algorithm succeeding with certainty (corresponding to complexity class $P$), we may want $f$ to run in expected polynomial time and succeed with probability $1$ (corresponding to class $ZPP$), we may want $f$ to run polynomial time and succeed with high probability (corresponding to $BPP$), or we may want $f$ to run in deterministic polylog time on polynomial-many parallel processors (corresponding to $NC$). And so forth.

What is the terminology for this type of algorithm? In many cases, we know that there exists some $y$ satisfying $A(x,y)$, so $f$ can't really be said to decide anything. I could just refer to saying that $f$ is an "NC algorithm", which is really an analogy and not proper nomenclature.

Thanks!


texts: Nearest Common Ancestor on DFS Tree (with Addition of Leaves in DFS Order) on Pointer Machines

texts:
What is the complexity status for the Nearest Common Ancestor Problem on Trees in which the leaves are attached to the tree in DFS order ?
i.e. Suppose one is visiting a tree T in DFS, and at any time one wants to answers NCA queries as NCA(x,y) for any already visited vertices (x,y).

This can be done in constant time $O(1)$ per NCA query and leaf insertion on RAM machines (Gabow, Tarjan '83, Gabow '90), my question is:

what is currently known concerning this problem on Pointer-Machines ?


texts: Ruzzo-Simon-Tompa oracle access mechanism

texts:
In a paper on relativizing logspace computations, Ladner and Lynch construct an oracle relative to which $\mathsf{NL} \nsubseteq \mathsf{P}$. There are some
more pathological examples in this vein in the literature. I have been reading some papers on relativized small space classes, and one of the primary tools in this area is the Ruzzo-Simon-Tompa(RST) oracle access mechanism which demands that a non-deterministic space-bounded turing machine act deterministically while making queries to the oracle.

Now consider circuit families with oracle gates - say, $A^B$, where $A$ is a circuit complexity class containing logspace with oracle access to another class $B$, via oracle gates appended to the basis of $A$. Are there any pathological examples similar in spirit to the Ladner-Lynch paper, known for such classes? What would be a RST-like restriction necessary for such classes?
In case there are indeed such examples, am I right in guessing that a RST analogue would be to insist that $A$ be a logspace-uniform circuit family?


texts: Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?

texts:
This is intended as a follow up question to Robin Kothari's previous post on polynomial time hardness results.

Specifically, I'm interested in seeing some hardness proofs for problems that are believed to have roughly $\Omega(n^3)$ lower bounds, and I say roughly to allow for slightly subcubic improvements by playing with the word size (such as that for 3SUM by Barab et al. [via Springer]). I would be happy to keep problems in the decision tree model if it simplifies the responses.

From Robin's post, I learned about Jeff Erikson's paper which gives a $\Omega(n^3)$ lower bound for 5SUM (more accurately, he shows that $k$-SUM runs in $\Omega (n^{\lceil k/2 \rceil})$ time in general).

Do papers or other references exist using such reductions to conjecture cubic lower bounds for problems in computational geometry or graph theory?


texts:
I'd appreciate any pointers or terms that could get me started in the right direction.

We have a directed graph $G=(V,E)$ and lengths $l_{ij}$ for each edge $ij$ that can be assumed positive.  There is a special start node $s$ and end node $t$.

For each edge $ij$, we'd like to compute the length of the shortest path from $s$ to $t$ that does not use edge $ij$.

A simple brute force algorithm is to run a shortest path algorithm for each edge, each time removing a different edge from the original graph.  Is there a more efficient algorithm that takes advantage of the fact that there is a lot of repeated computation happening in this brute force algorithm?

Thanks in advance.


texts: Graph (Forest) representation that supports edge deletion and efficient traversal

texts:
I am trying to write a data structure that given a general tree (or forest) will support the following operations:

Edge deletion
Connected(u,v) queries

This problem is addressed in section two of the following ACM journal article: "An On-Line Edge-Deletion Problem". The idea given claims to be able to carry out q edge deletions in O(q + |V|log|V|) time, while allowing constant time Connected(u,v) queries. The idea being: to maintain a table mapping each vertex to a connected component. Upon each deletion, each of the new trees is scanned in parallel. Which ever tree is finished being scanned first - becomes a new component. Now my question is, which graph representation can I use to implement their idea? On one hand I need to be able to delete an edge without having to scan an O(|V|) adjacency list, on the other hand, I need to be able to run a traversal (DFS) in O(|E|) = O(|V| (tree) time which can't happen using a matrix.


texts: Sequential Consistency, cannot find a sufficient explanation

texts:
I am having a hard time understanding the SC memory model properly.
The sentence "the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program." is very ambiguous for me.

Does:
"having the operations in each processor appear in the sequence specified by the program" mean that all memory operations are updated system wide exactly after being run? Or can they reside in the cache, not known to the processors by the new value for a while.

Does the sentence also infer that no matter what sequential order i decide to order my commands between the threads (not order differently the commands in each individual thread), I will always get the same read's for all of my writes?

Lets take for example this:

X=Y=0
Thread 0         Thread 1           Thread 2
X=1              EAX=X              Y=1
                 EBX=Y              ECX = X

Output:
Thread 1: EAX=1
Thread 1: EBX=0
Thread 2: ECX=0

It is easily seen that Y=1 MUST be before EBX=Y, because otherwise, EAX cannot be 1 if ECX is 0 or vice versa. But is this still SC? because even though Y=1 was issued before EBX=Y, it could of updated all the threads only after EBX polled Y.


texts: Testing boolean vectors orthogonality with fast query-time

texts:
Consider the following problems,

Problem1:
INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$
TASK: preprocess INPUT in such a way that the following queries can be solved as fast as possible: given a query vector $x\in\{0,1\}^d$, find every $s\in S$ that is orthogonal (or non orthogonal, by complementarity) to $x$.

Problem2:
INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$
TASK: preprocess INPUT in such a way that the following queries can be solved as fast as possible: given a query vector $x\in\{0,1\}^d$, decide whether $S$ contains a vector orthogonal to $x$.

I'm in deep search of fast methods, i.e. faster than naive inspection! Also complexity lower bounds, or any other known reference ...

In particular, I was wondering whether we can adapt range searching techniques (I'm thinking about kd-trees or similar partitioning trees) to the problems above ...

Also, I wonder whether Random Projection or (Jaccard index, angle, cosine based) Similarity Search methods might provide good speed-up ...


texts:
When encoding a logic into a proof assistant such as Coq or Isabelle, a choice needs to be made between using a shallow and a deep embedding. In a shallow embedding logical formulas are written directly in the logic of the theorem prover, whereas in a deep embedding logical formulas are represented as a datatype.

What are the advantages and
limitations of the various
approaches?
Are there any guidelines available for determining which to use?
Is it possible to switch between the two representations in any systematic fashion?

As motivation, I would like to encode various security related logics into Coq and am wondering what the pros and cons of the different approaches are.


texts: Sorting a programs instructions until it works

texts:
Lets say I have a computer program below.

(define (factorial x)
   (if (= x 0)
       1
       (else (* x (factorial (- x 1)))))

I then take each line of the program and create a random permutation.

       1
   (if (= x 0)
       (else (* x (factorial (- x 1)))))
(define (factorial x)

Now I give you a set of valid values that the program must return.
    1,2,6,24

Your task is to sort the permutations of the program until it gives you the result.

Is this a new problem? I haven't found anything remotely like the problem I proposed above.

What is the runtime to solving this problem?


texts: formalizing a statement about the expressive power of programming languages wrt divergence

texts:
In the Coq'Art book the authors mention in passing that any language that can calculate all computable functions must also be able to express diverging computations.
Or in other words, there can be no Coq' that is Turing-complete that maintains the guarantee that all computations describable in that language terminate.

How would I go about formalizing this statement? I feel it's a simple corollary to the Halting problem, but I don't know enough about formal semantics of programming languages to express or prove this.


texts: How do computers check if two functions are the same?

texts:
To prove that two given functions are the same involves proving infinitely many statements. I wonder how to implement so that a computer can check such a statement?

An easy example is the following: how to check

$$ \frac{1}{1-x}\frac{1}{1+x} = \frac{1}{1-x^2} $$

where three of them are expressed in terms of infinite sums?

More precisely, define three functions $f, g, h: \mathbb{N_{\geq 0}} \to \mathbb{C}$ with

$$ f(n) = 1 \mbox{, }   g(n) = (-1)^n  \mbox{, }  h(2n) = 1 \mbox{, } h(2n+1) = 0.$$ Then

$$\frac{1}{1-x} = \Sigma_n f(n) x^n$$
$$\frac{1}{1+x} = \Sigma_n g(n) x^n$$
$$\frac{1}{1-x^2} = \Sigma_n h(n) x^n$$

Precise Question

How does a computer check if $h(n) = \Sigma_{k=0}^n f(k)g(n-k)$ for all $n$? Lets suppose we are not allowed to use theorems to transform the infinite sums back to their fractions form.

Disclaimer

I am a mathematician (sort of) who knows little about logic, functional programming, and proof assistants. I know how to argue the proof with mathematician standard, but I am very curious about how a computer checks proofs that involve infinity.


texts: Parametrized Algorithm for Finding Bicliques

texts:
Given an $n$ vertex undirected graph, what is the best known runtime bound for finding a subgraph which is a $k\times k$-biclique? Are there faster parametrized algorithms than the
$\binom{n}{k}\mbox{poly}(n)$ time algorithm of "guessing" one side of the biclique and see if there are at least $k$ other vertices incident to all of them?


texts: Characterization of problems for which sublinear time algorithms exist

texts:
I was wondering if problems for which sublinear time (in the input size) algorithms exist can be characterized as possessing specific properties. This includes sublinear time (e.g. property testing, an alternative notion of approximation for decision problems), sublinear space (e.g. sketching/streaming algorithms in which the Turing machine has a read-only tape, a sublinear working space, and a write-only output tape) and sublinear measurements (e.g. sparse recovery/compressive sensing). In particular, I am interested to such a characterization for both the framework of property testing algorithms and in the classical model of randomized and approximation algorithms.

For instance, the problems for which a dynamic programming solution exist exhibit optimal substructure and overlapping subproblems; those for which a greedy solution exists exhibit optimal substructure and the structure of a matroid. And so on.
Any reference dealing with this topic is welcome.

With the exception of a few problems that admit a deterministic sub linear algorithm, almost all of the sublinear algorithms I have seen are randomized. Is there any specific complexity class related to problems admitting sublinear time algorithms ? If yes, is this class included in BPP or PCP?


texts: Is finding the minimum regular expression an NP-complete problem?

texts:
I am thinking of the following problem:
I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses).

Suppose by regular expression we mean some well-defined finite state machine, I am not familiar with the exact terminology, but let's agree on some class of allowed expressions.

Instead of manually crafting the expression, I want to give it a set of positive and a set of negative examples.

It should then come up with an expression that matches the + ones, rejects the - ones and is minimal in some well-defined sense (number of states in the automata?).

My questions are:

Has this problem been considered, how can it be defined in some more concrete way and can it be solved efficiently? Can we solve it in polynomial time? Is it NP complete, can we approximate it somehow? For what classes of expressions would it work? I would appreciate any pointer to textbooks, articles or such that discuss this topic.
Is this related in any way to Kolmogorov complexity?
Is this related in any way to learning? If the regular expression is consistent with my examples, by virtue of it being minimal, can we say something about its generalization power on yet unseen examples? What criterion for minimality would be more suitable for this? Which one would be more efficient? Does this have any connections with machine learning? Again any pointers would be helpful...

Sorry for the messy question ... Point me in the right direction to figure this out. Thanks !


texts: Auction theory - Selling Multiple Items via Social Networks

texts:
I am trying to understand this paper.

The one thing that I cannot wrap my head around is the payment policy for the Generalized Information Diffusion Mechanism. It is explained on page 72 with examples on page 73.

I understand it as follows:

So for any node $i \in N$, the payment is: $\mathcal{SW}_{-D_{i}} - (\mathcal{SW}_{-C_{i}^{\mathcal{K}}}-v_{i}^{'})$

$D_{i}$ is the union of $i$ and its critical children,

$\mathcal{SW}_{-D_{i}}$ sums over all nodes except the nodes in $D_{i}$.

$\pi_{j}(\theta^{'})$ is 1 if $j$ receives an item, else 0.

Thus, $\mathcal{SW}_{-D_{i}}$ is the sum of the bids of the nodes that receive an item and are not $i$ and not a critical child of $i$.

So for node D (figure 5) I get: $\mathcal{SW}_{-D_{D}} = 19 + 17 + 20 = 56$

$C_{i}^{\mathcal{K}}$ is the set of the top $\mathcal{K}$ ranked critical children of $i$ according to their bid. When the set is smaller that 5, we just take all critical children.

For node D: $\mathcal{SW}_{-C_{i}^{\mathcal{K}}} = 19 + 17 + 20 + 14 = 70$ (all nodes that receive an item that are not D's critical children).

Finally, $v_{i}^{'}$ is just node $i$'s reported valuation (bid).

For node D:  $v_{D}^{'} = 14$.

Thus when I calculate D's payment:
$\mathcal{SW}_{-D_{D}} - (\mathcal{SW}_{-C_{D}^{\mathcal{K}}} - v_{D}^{'}) = 56 - (70 - 14) =  0$.

Of course this is wrong because it always comes out as 0 and in reality D has to pay 10.

Has anyone read this paper already and can help me?


texts: Nim-game variant - weird ending condition

texts:
the game is structured like this:

two players
the players alternate moves
4 heaps $h_1,h_2,h_3,h_4$ with sizes $n_1,n_2,n_3,n_4$
at each move, the player can either remove one or two elements from any of the heaps (meaning that if the player takes two elements, those two can either be from the same heap or from two different heaps, as long as the total number of removed elements per turn is 2).
the game stops when the player (who loses the game) is left with 3 heaps of size $0$ and one heap with size greater than $0$.

Can anyone suggest a winning strategy for this game?

ty.thank-you


texts: Randomized Reduction for Maximization Problem

texts:
I have two maximization problems $P_1$ and $P_2$ where the decision version $L_1 = \{(x, t) : \operatorname{Val}_1(x)\ge t\}$ of $P_1$ is $\mathsf{NP}$-complete. Let $f:P_1\to P_2$ be a randomized reduction such that it holds with high probability that $$|\operatorname{OPT}_1(x) - \operatorname{OPT}_2(f(x))|\le\varepsilon.$$ I would like to show that $L_2$ is also hard under some complexity theoretic assumption like $\mathsf{NP}\neq\mathsf{BPP}$.

The issue I am running into is that simply knowing $t^*:=\operatorname{OPT}_1(x)$ and $\hat{t}:=\operatorname{OPT}_2(f(x))$ are close does not seem to imply the usual requirements of a randomized reduction (though this closeness seems to me that "morally" $P_2$ should also be hard if $P_1$ is, since if we could solve the optimization problem for $P_2$, we pretty much are able to solve it for $P_1$ up to some small error). Is there a version of reduction that formalizes what I think to be morally true? Any help is appreciated.


texts: Is there an array structure that allows for O(1) complexity for reverse, zip, slice etc operations?

texts:
Many operations on arrays have $O(n)$ complexity.

If we represent arrays as accessors methods, many of them could be done in $O(1)$. For example, the $i$th item in the reverse of an array $A$ of size $n$ is given by $reverse(A).i = A[n-1-i]$. So we can define reverse as:

$$reverse := \lambda A:array \ \lambda i:int. \ A[n-1-i]$$

and similarly for other operations like
slicing, zipping, concatenation, and so on.
This technique allows us to implement these complicated operations in constant time without touching the original memory at all.

What is the formal name of this structure?
What are the negative aspects of using this structure compared to the standard structure?


texts: Is there a containment between $\mathsf{ZPP}$ and $\mathsf{UP}$?

texts: Do we know if $\mathsf{ZPP}\subseteq\mathsf{UP}$ known or is there oracles against the hypothesis?


texts:
This is a very basic doubt, something I've always swept under the carpet.

The definition of BPP allows a machine access to random bits, which are 0 and 1 with equal probability. Many a randomized algorithms need to sample points from a space/set of size $n$, where $n$ need not be a power of two, and sampling from such a space using random bits would typically yield Las Vegas sort of behaviour as far as running time is concerned i.e. at best, the expected running time can be bounded by polynomial.

Am I missing something here (like there being a way to sample from arbitrary sets using random bits without having to make the running time expected polynomial time), or is this something that is swept under the carpet for convenience sake i.e. BPP actually requires only expected running time being polynomial?


texts: Additive error approximations of GapP functions

texts:
Consider a GapP function $g(x)$ for $x \in \{0, 1\}^{*}$. Consider an approximation $\tilde g(x)$ such that
\begin{equation}
\left|g(x) - \tilde g(x)\right| \leq \epsilon.
\end{equation}
Consider a few cases.
Case 1: $\epsilon = 2^{n-1}$.
Case 2: $\epsilon = 2^{n-1} - \text{poly}(n)$.
Case 3: $\epsilon = 2^{n}/\text{poly}(n)$.
Case 4:  $\epsilon = 2^{cn - o(n)}$, $c < 1$.
From this answer, we know that if $g(x)$ is a #P function, then the first three cases are easy (have a BPP algorithm), and the fourth case is #P-hard.
Are all these cases #P-hard when $g(x)$ is a GapP function? If so, is there any value of $\epsilon$ for which approximating a GapP function is "easy" (doable in BPP/the polynomial hierarchy)?


texts: Efficiently Detecting "edges" in the time frequency plane

texts:
Given a signal $y(t)\in\mathbb{R}$ I wish to detect edge patterns.  $s(f,t)$ is a time-frequency decomposition of $y(t)$ in some window $(t-n,t+n)$ so that $f$ loosely corresponds to a local frequency. Edges are located where $||s(f,t)|-|s(f+ i,t+j||>\tau$ for some threshold $\tau$ and $i,j\in \{-1,0,1\}$.  I do not have a precise model or setting: at present I have been working with $s(f,t)$ being a short-time Fourier transform.  My assumption is that there should only be a few such edges locations.

What measurement efficient and time efficient algorithms exist to solve this sort of problem?  One can adapt methods of compressive sensing to the computed time frequency distribution but that seems wasteful: one should not have to compute an entire Fourier transform in order to discover these heavy hitters.


texts: In the Hott book, are the most of the type formers redundant? And if so, why?

texts:
In chapter 1 and Appendix A of the Hott book, several primitive type families are presented (universe types, dependent function types, dependent pair types, Coproduct types, Empty Type, Unit type, natural number type, and identity types) to form the foundation for Homotopy Type Theory.

However it seems that given universe types, and dependent function types you can construct all these other "primitive" types.  For instance the Empty type could instead be defined as

ΠT:U.T

I assume the other types could also be constructed similar to how they are in pure CC, (ie just derive the type from the inductive part of the definition).

Many of these types are explicitly made redundant by the Inductive/W types that are introduced in chapters 5 and 6.  But Inductive/W types appear to be an optional part of the theory since there are open questions on how they interact with HoTT (at least at the time the book came out).

So I am very confused about why these additional types are presented as primitive.  My intuition is that a foundational theory should be as minimal as possible, and redefining a redundant Empty type as a primitive into the theory seems very arbitrary.

Was this choice made

for some some metatheoretic reasons that I am unaware of?
for historical reasons, to make the type theory look like
past type theories (which were not necessarily trying to be
foundational)?
for "usability" of computer interfaces?
for some advantage in proof search that I am unaware of?

Similar to: Minimal specification of Martin-Löf type theory , https://cs.stackexchange.com/questions/82810/reducing-products-in-hott-to-church-scott-encodings/82891#82891


texts:
A matrix $M$ is sorted if $M_{i,j}\leq M_{i+1,j}$ and $M_{i,j}\leq M_{i,j+1}$.

Consider the following problem.

  Search in a sorted matrix

  Given a $n\times m$ sorted matrix $M$, where $n\leq m$.
  There is a hidden number $x$. We have access to an oracle $f$, where $f(y)$ returns if $y< x$, $y=x$ or $y>x$. Decide if $x$ is in $M$.

The native algorithm would be going through every element in the matrix, and call the oracle on the element. This takes $O(nm)$ time and $O(nm)$ oracle calls.

One can get much better in terms of oracle calls. A simple algorithm is to sort all elements in the matrix in $O(nm \log nm)$ time, and then use the oracle $O(\log nm)=O(\log m)$ times to do a binary search on the sorted list.

The best-known algorithm can achieve $O(\log m)$ oracle calls and $O(n\log \frac{m}{n})$ time. See here.
This is best possible, as one can show a $\Omega(\log m)$ lower bound on oracle calls and $\Omega(n\log \frac{m}{n})$ on running time.

The problem is about more refined running time.
The numbers that are no larger than $x$ form an (inverted) staircase shape that contains all elements no larger than $x$.
We measure the complexity of the problem by the $h$, the number of steps of the staircase, and $k$, the number of elements no larger than $x$.

  Example: Let $x=11$ and $M$ is the matrix below. The staircase shape
  is highlighted. The staircase shape has $h=3$ steps, and there are $k=11$
  elements in the staircase.

One can obtain a $O(h\log \frac{k}{h^2})$ time algorithm for the problem by using exponential search to find the boundary of the staircase. This never worse than $O(n\log \frac{m}{n})$, and significantly better when $h$ is small. However, the algorithm has to use the oracle $O(h\log \frac{k}{h^2})$ times.

One can show $\Omega(m)$ is the lower bound on the number of oracle calls.

Can we get the best of both worlds? A faster running time together with small number of oracle calls?

  Is it possible to use $O(h\log \frac{k}{h^2})$ time and $O(\log m)$ oracle calls to search in a sorted matrix?


texts:
Given: An undirected, unweighted graph

Looking for: A disjoint vertex cycle cover where every cycle has at least 3 edges

Is there any algorithm that solves this problem, possibly with some heuristics? Can the bipartite representation of the graph used for finding perfect matching be leveraged here?


texts: A version of bipartite graph turnpike problem

texts:
Given a set of "required" weights for edges of a bipartite graph, I am looking for assignments to the nodes so that there is at least an edge carrying a weight from that set. Each edge can have possibly four weights as a+b, a-b, b-a, -a-b where the values on its endpoints are a and b. The values are allowed to be any real number.

For example, given {2,3,-5,8,9,12}, I can choose V1 = {4,10} and V2 = {1,2} where, out of 24 possible values over 6 edges (each edge has 4 values), we get all the required edge weights by
 4 - 2 = 2 //
 4 - 1 = 3 //
-4 - 1 = -5 //
10 - 2 = 8 //
10 - 1 = 9 //
10 + 2 = 12 .

The reason that I stated the problem over a graph is that it seems to be similar to the Graph Turnpike problem studied by Feder and Motwani (On the graph turnpike problem, Information Processing Letters, 2009 - Elsevier).

I was wondering if this problem can be solved in polynomial time or reduced to another problem.


texts: Lower bound on the support size of an $\epsilon$-biased distribution

texts:
Let $D$ be an $\epsilon$-biased distribution we want to show that
$$\text{Supp}(D)\geq \Omega\bigg(\frac{n}{\epsilon^2\log(\frac{1}{\epsilon})}\bigg)$$
I know that there are some proofs for this but I am intrested in the following particular way.

Let $X,Y$ be two distributions over $\{0,1\}^n$. Consider the "convolution" of distributions $Z=X\circledast Y$ to be defined by sampling $x\sim X$ and $y\sim Y$ independently and outputting $x\oplus y$ where $\oplus$ is just bit-wise xor.

Now if we define a distribution $D^{(t)}=D\circledast\cdots\circledast D$ ($t$ times) we can use some Fourier analysis and combinatorics to show that

$D^{(t)}$ is $\epsilon^t$-biased.
$|\text{Supp}(D^{(t)})|\leq\binom{|\text{Supp}(D)|+t}{t}$

We can also show that for every $\delta$-biased distribution $Z$ we have $\lVert Z\rVert_2^2\leq\delta^2+2^{-n}$ when considering the distribution as a vector of probabilities. Now, I was told that I can use the latter to obtain a lower bound on $|\text{Supp}(D^{(t)})|$ and then choose $t$ accordingly to get the desired bound.

However, the only bound I can get for $|\text{Supp}(D^{(t)})|$ is
$$|\text{Supp}(D^{(t)})|\geq\sqrt{\frac{1}{\epsilon^{2t}+2^{-n}}}$$
And I don't see how that helps...


texts: Min Hamming distance of a given string from substrings of another string

texts:
Let $U$ be a small finite set.
Consider the following problem:
Input: two strings $u \in U^k$ and $v\in U^n$ with $k \leq n$.
Output: a (contiguous) substring of $v$ of length $k$
with the minimum Hamming distance from $u$.
In other words I want to compute the following function:
$$f(u,v) = \arg\min_{j < n-k} d_H(u, v[j,j+k])$$
where $n = |v|$ and $k = |u|$.

What is the fastest algorithm for this problem?
Can this problem be solved in time $O(n\log n)$?

I think I can solve the problem if I have a data structure as follows:
Let $B = \{0, 1 \}$ and $k \le n$ be fixed numbers.
We want a data structure $D$ with the following properties:

Build: for $v \in B^n$ and $u \in B^k$, $D.Build(v, u)$ builds an instance of $D$ in time $O(n \log n)$.

Query: for $1 \le q \le n - k + 1$, $D.Query(q)$ returns $\langle u, v[q, q + k - 1]\rangle$ in time $O(\log n)$.

Is there a data structure with these properties?

$\langle \cdot , \cdot \rangle $ is the dot product and
$v[i, j]$ = $(v_i,\ldots, v_{j})$ is the subsequence of $v$ from $i$ to $j$.


texts: Algorithm for ordering a list under a similarity function?

texts:
While thinking about the best way to display confusion matrices, and I came up with the following problem:

You have a set of objects $A$, and a similarity function $s: A,A \rightarrow \mathbb{R}$ defined on every pair of objects.  You want to find an ordering $i: A \rightarrow [1..|A|]$ on the objects that minimizes:

$\sum_{a,b \in A} s(a,b) * (i(a) - i(b))^2$

That is, the ordering is penalized by the similarity of each pair times the square of the distance.

Any ideas on an algorithm to solve this?  Any of: a polynomial-time algorithm, an idea for an NP-hard reduction, or search keywords for similar problems would be greatly appreciated.  Thanks!


texts: Number of distinct enclosing circles for N points

texts:
Several enclosing circles are possible for a given set of N 2D points. I am only talking about  enclosing circles having 3 or more points on the circumference. What is the asymptotic limit of the total number of distinct enclosing circles having 3 or more points on the circumference. The naive bound is $O(n^3)$ but tighter bound  should exist.

And also how to generate all such enclosing circles?


texts: Space complexity to compute the optimal string alignment for the Levenshtein edit distance

texts:
If we are given two strings of size $n_1$ and $n_2$, the standard Levenshtein edit distance computation is by a dynamic algorithm with time complexity $O(n_1 n_2)$ and space complexity $O(n_1 n_2)$. (Some improvements can be made as a function of the edit distance $d$, but we make no assumption on $d$ being especially small.) If you are only interested in the value of the edit distance (i.e., the minimal number of edits), a well-known improvement of the usual algorithm (where you only keep the previous and current row of the alignment table) reduces the space complexity to $O(\max(n_1, n_2))$.

However, if you want to get the actual edits of an optimal edit script, is it possible to do better than $O(n_1 n_2)$ memory usage, possibly at the expense of running time?


texts: The use of crossovers in Genetic Algorithm

texts:
My questions concern the use of crossovers in genetic algorithms. The three basic ingredients of genetic algorithms are:

selection
mutation
crossover

If we think of genetic algorithm acting on binary strings…

Crossover is the process by which two parent strings get mixed to give born to offspring strings. For example: 11000 and 00010 can create the offspring 11010 by crossover only.

In some genetic algorithm people authorize double-crossover. For example the two parents: 110011 and 001100 can give birth to 111111.

I don't fully understand the advantageous of crossovers! It seems to me that one can obtain similar results with algorithms that do not contain crossover.

My questions

Under what conditions is the use of crossover in genetic algorithm beneficial? why?
Under what conditions is the use of double-crossover more beneficial than single crossover? why? What about triple crossover?

When I say "Under what conditions", I mean "for what fitness landscape" or "for what problem type".

By fitness landscape, I mean a mapping of each possibility to fitness (reproductive success) in a hyperspace of $n+1$ dimensions where $n$ is the length of the string (the additional dimension being the fitness).


texts: With equirecursive types are there downsides to making all types potentially recursive?

texts:
By this I mean to ask, is it a bad idea to have all type constructor term expressions abstracted with $\mu$ just in case they need to be recursive? For example,

$Bool : Type;$

$Bool = (\mu Bool' . (Unit \lor Unit));$

The value constructors would still just be $(inj_0 unit)$ and $(inj_1 unit)$ in a system with equirecursive types, right? It seems like it would just be $O(x + 1)$ for an $O(x)$ type checking algorithm using unification, or maybe not even that.

I understand why $Bool$ is not written this way by default, especially considering recursive types are usually added to a theory after-the-fact and therefore the value constructors would differ depending on the variant of the recursive type theory. It's much less intuitive to read $(\mu X . \tau)$ than just $\tau$ when programming or proving theorems but are there any reasons of real consequence for not doing this? I can't find any.

The reason I ask this question is because I am writing a program to translate a functional programming language into a core dependent type theory with equirecursive types.


texts: Complexity of testing if a hypergraph has generalized hypertreewidth $2$

texts:
A hypergraph $H = (V, E)$ consists of a set of vertices $V$ and a set $E$ of hyperedges, i.e., subsets of $V$.

The generalized hypertreewidth (GHW) parameter is a measure of the cyclicity of a hypergraph which is a variant of its treewidth. Intuitively, it is like a tree decomposition but the width of each node is counted as the number of hyperedges required to cover it. Formally, a hypertree decomposition of a hypergraph is defined as a tree $T$ where each node $b \in T$ is labeled by some vertices $V(b) \subseteq V$ and $E(b) \subseteq E$. We that $T$ is a tree decomposition of $H$, namely, we impose the following on the vertex mapping:

for each hyperedge $e \in E$, there is a node $b \in T$ such that $e \subseteq V(b)$
for each vertex $v \in V$, the set $\{b \in T \mid v \in V(b)\}$ of the vertices where $b$ occurs is a connected subtree of $T$.

Further, we require the following on the edge mapping:

for each node $b \in T$, the hyperedges $E(b)$ cover $V(b)$, i.e., $V(b) \subseteq \bigcup_{e \in E(b)} e$.

The width of the decomposition $T$ is the maximum, over $b \in T$, of $|E(b)|$. The GHW of $H$ is the smallest $k$ such that $H$ has a generalized hypertree decomposition of size $k$.

My question is: Do we know the complexity of testing, given an input hypergraph $H$, whether it has GHW $\leq 2$?

It is known that testing whether an input hypergraph has GHW $\leq 3$ is NP-hard [GMS 2007] and having GHW $=1$ is tractable because it is equivalent to being $\alpha$-acyclic as mentioned in [GGS 2014] and this is testable in linear time. I did not find any reference about whether having GHW $\leq 2$ is also tractable, or if it is already hard.

Georg Gottlob, Zoltán Miklós, and Thomas Schwentick, "Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants", 2007
Georg Gottlob, Gianluigi Greco, and Francesco Scarcello, "Treewidth and Hypertree Width", 2014


texts: Fast algorithm for successively merging k-overlapping sets?

texts:
Consider the following algorithm for clustering sets: Begin with $n$ sets, $S_1, S_2, \ldots,S_n$, such that $$\sum_{i = 1}^n |S_i| = m \,,$$ and successively merge sets with at least $k$ elements in common. E.g., if $S_1 = \{1, 2, 3\}$, $S_2 = \{3, 4, 5\}$, and $S_3 = \{5, 6, 7\}$, and $k = 1$, then $S_1$ can be merged with $S_2$ to create $S_1' = \{1, 2, 3, 4, 5\}$, and $S_1'$ can be merged with $S_3$ to create $S_1'' = \{1,\ldots,7\}$.

Warmup question: Can this clustering algorithm be implemented efficiently for $k = 1$?

Answer to warmup question: If the sets only need to overlap by one element to be merged as in the example above, the clustering can be performed in $O(m)$ time using connected components if you are careful.

Harder question: Suppose the sets must overlap by at least 2 (or $k$) elements to be merged. Is there an efficient algorithm for this case (i.e., close to linear time)? The challenge here is that you can have cases like $S_1 = \{1, 2, 3\}$, $S_2 = \{2, 4, 5\}$, $S_3 = \{1, 4, 5\}$, with $k = 2$. Note that in this case $S_1$ can be merged with $S_2$ and $S_3$, but only after $S_2$ and $S_3$ are merged to create $S_2'$ so that $S_1$ and $S_2'$ share both elements 1 and 2.


texts: Advice for attending my first TCS conference

texts:
I will be attending my first computer science conference and after reading the advice for how to improve conferences I noticed the several suggestions were about grad students attending their first conference.

What advice do you have for a grad student attending his first conference and what should his focus be.


texts:
Let $\varphi$ be a CNF formula. Suppose that each of $\varphi$'s clauses consist of exactly $t$ literals (and, moreover, all literals within one particular clause correspond to different variables). It is well known that if every clause has less than $2^t / e$ clauses that share variables with it, then $\varphi$ is satisfiable (let us call such formulae easy). Satisfiability can be proved easily using Lovász local lemma. Moreover, using a recent result by Moser and Tardos one can show that one of the satisfying assignments can be found in polynomial expected time using the following very simple procedure:

Pick a random assignment
While there exists an unsatisfied clause, resample all its variables.

On the other hand, most of modern SAT solvers are DPLL-based. It means that they try to find a satisfying assignment using brute force with two simple prunings:

If a formula contains clause with one literal, then we can fix it.
If one variable occurs in a formula only with (or without) negation, then we can fix it.

The question: is it true that a version of DPLL that splits on random variables finds a satisfying assignment of any easy formula in polynomial expected time?


texts: Set query in a universe with overlapping sets

texts:
Suppose we have a universe $U$ of $n$ items $u_1,u_2,u_3,...,u_n$.
And a collection of sets (no restriction on being disjoint or exhaustive etc.)
which cover some items. Size of each set is bounded by some parameter $k<n$.
We need to perform the following update and query efficiently.

Update:
1- Add a new set to the collection having some elements of $U$.

2- Delete any existing set from collection.

Query:
Given two vertices, does there exist a set which has both these vertices.

A trivial way would be to maintain a 2D matrix with each $M(i,j)$ storing number of sets containing both $i$ and $j$. Update would be done in $O(k^2)$ by incrementing $M(i,j)$
for all pairs of vertices in set S_i. The query can be done in$ O(1)$ time.

I am looking for some solution with o(k^2) update time and poly log query time..


texts: Matching on bipartite graph - multiple edges

texts:
I have a weighted bipartite graph consisting of two sets $S$ and $P$. ($|S| > |P|$).
I need to find a matching so that every node $s$ in $S$ matches a node of $P$. But a node $p$ in $P$ can match multiple nodes of $S$. Each $p$ has an individual limit of how many nodes it can match. The total weight of the matching should be as small as possible.

My research ended quite quick because I do not know the right key words to search for. Does this kind of matching problem have a specific name?

Second question: Do you already know some algorithms I should have a glance at?


texts:
In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the dual is feasible in expectation (see Lemma 3 on page 5). My question is:

  Is it enough for linear program constraints to be satisfied in expectation?

It is one thing to show that the expected value of the objective function is something. But if feasibility constraints are satisfied in expectation, there is no guarantee that it will be satisfied on a given run. Moreover, there are many such constraints. So what is the guarantee that ALL of them will be satisfied on a given run?


texts: Typechecking liveness properties of coprograms

texts:
Clarification: in Total Functional Programming terminology, a program terminates with useful input, while a coprogram doesn't necessarily terminates, and repeatedly produces useful input.

I am investigating the relationship between model checking and type theory. It is straightforward to encode safety properties in the type of a program. It seems like typing coprograms would be the best way to check liveness properties, but where is the literature on the subject? I can't find any papers about the general case.


texts: Can we fast generate perfectly uniformly mod 3 or solve NP problem?

texts:
To be honest, I don't know that much about how random number are generated (comments are welcome!) but let's assume the following theoretical model:
We can get integers uniformly random from $[1,2^n]$ and our goal is to output an integer uniformly random from [1,3].

A simple solution whose expected running time is polynomial is the following. Discard $2^n$ (and possibly also $2^n-1$) from $[1,2^n]$ so that the number of remaining integers is divisible by $3$ so we can take $\bmod 3$ of the generated integer.
If we get a discarded number, we generate another number, until we get a non-discarded one.

But what if we want to terminate surely in polynomial time?
Because of divisibility issues, the problem becomes unsolvable.
However, I wonder if we can solve the following.

  Suppose we can generate integers uniformly random from $[1,2^n]$ and we are given a computationally hard problem.
  Our goal is to output an integer uniformly random from [1,3] or solve the hard problem.

Here the hard problem can be factoring an integer, solving a SAT instance or anything similar.
For example, we can decode a one-way permutation $f$ as follows, if we are given some $f(x)$ (and supposing $n$ is even):
If for our random string $f(r)<f(x)$, then take $f(r) \bmod 3$, if $f(r)>f(x)$, then take $f(r)-1\bmod 3$.
Finally, if $f(r)=f(x)$, then we are done, as $r=x$.
(If $n$ is odd, then something similar works, just we also have to check if $f(r+1)=f(x)$ and subtract $2$ if $f(r)>f(x)$.)

Summary of answers.
Emil Jeřábek has shown that unless we can generate perfectly uniformly, we can solve any single-valued search problem from TFNP, and also from PPA-3.
On the other hand, daniello has shown that we cannot solve NP-complete problems the above way, unless NP=co-NP.


texts:
Last year I attended Scott Aaronson's talk Hawking Quantum Wares at the Classical Complexity Bazaar. Being intrigued by his argument that "[e]ven if quantum mechanics hadn't existed, theoretical computer scientists would eventually have had to invent it", I have been thinking about how we can derive the first and second quantization in quantum mechanics from theoretical computer science.

First quantization is basically the quantization of properties of a unit quantum system and second quantization is the quantization of the electromagnetic field. Is there some way that theoretical computer science could entail these two ideas? I can recognize some "quantumnesses" in theoretical computer science, including

enumeration of set elements,
enumeration of interactions with oracles, and
discrete states of Turing machine,

but I am having a hard time relating them to first and second quantization.


texts: Greater-Than operator using an Arithmetic Circuit

texts:
How can I transform the term $x>C$ (i.e. the term assumes the value $1$ if $x>C$ and assumes the value $0$ otherwise) to an arithmetic circuit that computes it?

Where $x$ is the input to the circuit and $C$ is a known constant.


texts: Solving 0/1 integer programming and solving ACC-of-SYM circuits

texts:
I am referring to the proof of Theorem 1.4 in this STOC 2014 paper, https://arxiv.org/abs/1401.2444. In particular my question is about the argument that begins in the 8th line of page 9 where the author says the following,

"Following the strategy of Theorem 1.2 (and the author's ACC SAT algorithm https://www.cs.cmu.edu/~ryanw/acc-lbs.pdf), the satisfiability question of (a $AC^0[2]\circ SYM$) C with $n$ inputs and size $poly(s)$ can be efficiently converted into a problem of evaluating a larger $AC^0[2]\circ SYM$ circuit C' where C' has $(n-k)$ inputs, $2^k\times poly(s,M)$ size and $k < \frac{n}{2}$ is a parameter and the $AC^0$ part has depth $6$. More precisely C' is an OR of $2^k$ copies of the depth $5$ circuit $C$ and each copy has its first $k$ inputs assigned to a distinct string from $\{0,1\}^k$."

Now given how C' is defined given a circuit C it seems obvious to me that the circuit C' is satisfiable if and only if C is satisfiable.

(...EXCEPT that I dont see why $C$ is a depth $5$ circuit given that from whats on the top of page $9$ it follows that its a $AND \circ OR \circ AND \circ XOR \circ AND \circ OR \circ SYM$.
Then the $AC^0[2]$ part of $C'$ should be depth $6$ and that matches with the first part of the paragraph. I guess this "depth 5" part of the quoted paragraph is a typo!...)

Then to make this argument where is the need for the deeper theorems like Theorem 1.2 of this paper (which is about a fast algorithm to evaluate $ACC \circ THR$ circuits) and the big breakthrough paper thats cited? (At no later stage in this proof do I see these two big results being referred to either.) Am I missing something in this argument?


texts:
A frame rule, like the one given below, captures the idea that, given a program c with precondition p that holds before it runs and postcondition q that holds afterward, some disjoint condition r should hold both before and after c runs.  (The * connective requires that its arguments be disjoint.)  Often, the pre- and postconditions are states of a heap, and c is an effectful program that modifies the heap in some way.

    {p} c {q}
----------------- (where no free variable in r is modified by c)
{p * r} c {q * r}

Discussions of the frame rule that I've seen always seem to focus on how the disjoint part of the heap, r, is preserved.  This enables "local reasoning": when reasoning about the effect that c has, we can disregard the r part of the heap and only concern ourselves with the part that actually changes.  But another way to look at it is that the change from p to q is preserved, even though r is now sitting there.  In other words, it's important that we end up with the postcondition {q * r}, rather than {q' * r} for some other q'.

So, my question is whether there's any treatment of the frame rule that discusses or makes use of the preservation-of-change-from-p-to-q thing.


texts: Chernoff Bounds for settings with limited dependence

texts:
Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. By partially I mean the variables could be divided into subsets of size atmost k such that any variable from two different sets are independent.

Of course one possible technique is that we sum the variables in a set and treat the sums as my new random variables but now the bound of the value we would have on these variables would be k and that's unreasonable in the setting that we have. So could something better be said ?

If needed the corelation between variables belonging to a set could be better characterized.

Thanks


texts:
Why does one need valuations in order to define the semantics of first-order logic? Why not just define it for sentences and also define formula substitutions (in he expected way). That should be enough:

$$M \models \forall x. \phi \iff \text{for all }d\in \mathrm{dom}(M),\ M \models \phi[x\mapsto d]$$

instead of

$$M,v \models \forall x. \phi \iff \text{for all }d\in \mathrm{dom}(M),\ M, v[x\mapsto d] \models \phi$$


texts:
This question was asked by Jan Pax on the Foundations of Mathematics mailing list.
Certainly $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$
but I suspect from the answers to this question that it's not known whether $\oplus P \subseteq PP$ (otherwise, $PP$ would be one possible answer to that question).  If it's not known, is there an oracle separation?


texts:
The semantics of a large subset of OCaml, called OCamllight,  was formalized in HOL by Owens several years ago. More recently, a type theoretical semantics of a smaller subset of OCaml was implemented in Nuprl by Kreitz, Hayden and Hickey.

Is there any similar development in Coq?


texts:
Let us define:

$U = \left\{ u_j \right\}, 1 \leq j \leq N = 2^{L}$, the set of all different binary sequences of length $L$.
$V = \left\{ v_i \right\}, 1 \leq i \leq M = \binom{L}{k}2^{k}$, the set of all different gapped binary sequences with $k$ known bits and $L-k$ gaps.

We have a score function $f : V \rightarrow R$, that associates a real number $c_i$ to any of $v_i$'s; i.e. $c_i = f(v_i)$.

Given any pair of $u_j$ and $v_i$, we can count the number of mismatches, by counting the known bits of $v_i$ that are different in $u_j$.  For example given $L=7, k=4$:

$\text{diff}(\text{"0001100"}, \text{"01...01"}) = 2$,

because the second bit and the last bit are different (gaps can match to any value).

We have a weight associated to the number of mismatches. In general, the number of mismatches can be any number between $0$ and $k$. so we have $k+1$ such weights given by $\left \{ w[0],w[1],\ldots,w[k] \right \}$.

For a given sequence $S$ of $T$ bits, $S = s_0s_1 \ldots s_{T-1}$, we define the total score as the weighted sum of all the $c_i$'s for all the the contiguous $L$-bits subsequences of $S$ weighted by their distance:

$g(S)=\sum_{j=0}^{T-L}\sum_{i=1}^{M} c_i \times w[\text{diff}(v_i, s_js_{j+1} \ldots s_{j+L-1})]$.

the obvious algorithm is as follows:

g:=0;
for j:=0 to T-L
  for i:=0 to M
    g:=g+c[i]*calcDif(S,j,i)

where calcDif() takes $O(L)$ to count number of mismatches. so the overall time would be in the order of $T*M*L$.

What is a better approach to calculate the total score more efficiently? Typical values are: $L=20, k=10, T=2000$?


texts: Isomorphism between algebraic data-types

texts:
I have two types of trees in Haskell, defined as the least solution of the following equations:

$T_1(A) \cong 1 + A + T_1(A) \times T_1(A)$

$T_2(A) \cong 1 + A \times T_2(A) + T_2(A) \times T_2(A)$

In Haskell it would be something like

data T1 a = Leaf | Data a | Node (T1 a) (T1 a)

data T2 a = Leaf' | Data' a (T2 a) | Node' (T2 a) (T2 a)

How could I prove or disprove that $T_1$ and $T_2$ are isomorphic? I'd like to know which tools are used to prove the non-existence of isomorphisms.


texts: Nontrivial algorithm for computing a sliding window median

texts:
I need to calculate the running median:

Input: $n$, $k$, vector $(x_1, x_2, \dotsc, x_n)$.
Output: vector $(y_1, y_2, \dotsc, y_{n-k+1})$, where $y_i$ is the median of $(x_i, x_{i+1}, \dotsc, x_{i+k-1})$.

(No cheating with approximations; I would like to have exact solutions. Elements $x_i$ are large integers.)

There is a trivial algorithm that maintains a search tree of size $k$; the total running time is $O(n \log k)$. (Here a "search tree" refers to some efficient data structure that supports insertions, deletions, and median queries in logarithmic time.)

However, this seems a bit stupid to me. We will effectively learn all order statistics within all windows of size $k$, not just the medians. Moreover, this is not too attractive in practice, especially if $k$ is large (large search trees tend to be slow, overhead in memory consumption is non-trivial, cache-efficiency is often poor, etc.).

Can we do anything substantially better?

Are there any lower bounds (e.g., is the trivial algorithm asymptotically optimal for the comparison model)?

Edit: David Eppstein gave a nice lower bound for the comparison model! I wonder if it is nevertheless possible to do something slightly more clever than the trivial algorithm?

For example, could we do something along these lines: divide the input vector to parts of size $k$; sort each part (keeping track of the original positions of each element); and then use the piecewise sorted vector to find the running medians efficiently without any auxiliary data structures? Of course this would still be $O(n \log k)$, but in practice sorting arrays tends to be much faster than maintaining search trees.

Edit 2: Saeed wanted to see some reasons why I think sorting is faster than search tree operations. Here are very quick benchmarks, for $k = 10^7$, $n = 10^8$:

≈ 8s: sorting $n/k$ vectors with $k$ elements each
≈ 10s: sorting a vector with $n$ elements
≈ 80s: $n$ insertions & deletions in a hash table of size $k$
≈ 390s: $n$ insertions & deletions in a balanced search tree of size $k$

The hash table is there just for comparison; it is of no direct use in this application.

In summary, we have almost a factor 50 difference in the performance of sorting vs. balanced search tree operations. And things get much worse if we increase $k$.

(Technical details: Data = random 32-bit integers. Computer = a typical modern laptop. The test code was written in C++, using the standard library routines (std::sort) and data structures (std::multiset, std::unsorted_multiset). I used two different C++ compilers (GCC and Clang), and two different implementations of the standard library (libstdc++ and libc++). Traditionally, std::multiset has been implemented as a highly optimised red-black tree.)


texts: Complexity of finding a graph separator with a given property

texts:
Are there any known results on the complexity of finding a separator (of any size) satisfying a given property?

I know that a clique separator is easy (polynomial time) to find and also know that many papers consider the problem of finding small separators or separators that leave connected components of size at most a fraction of the size of the original graph. But what if one need a separator with other properties, say, a cubic, bipartite or 2-connected separator? It's also easy to create properties which are NP-hard to decide, hence it would be interesting to distinguish between the P and NPC cases.

Edit: Someone (which is not a user of this website) just told me that the problem is polynomial if the property is "has a universal vertex" and NP-complete if the property is "induces an independent set" or "induces a complete bipartite graph".


texts: Maximize quadratic function subject to linear constraints

texts:
Can one maximize $\sum_i c_i x_i^2$ where the $c_i$ are constants (possibly negative), subject to linear constraints over the $x_i$?

This paper seems to come close to answering "no."  They show it is NP-hard for target functions $x_1 - x^2_2$.  However they have $x_1$ which is not squared, and from the two pages I can access online I can't understand if that's critical or not.

Bonus question: Is there a free software that can be tried to solve these problems (possibly heuristically)?


texts: Is there any time efficient way of achieving the result of FKS hashing lemma?

texts:
FKS hashing lemma states.

  Given a set of $n-$bit numbers $\{x_1,x_2,\dots,x_k\}$ there exist a
  prime $p$ of $O(\log n + \log k)$-bit such that $x_i$ mod $p \neq $
  $x_j$ mod $p$ if $x_i \neq x_j$.

This follows from prime number theorem. But finding such a prime takes a lot of time. Are there more efficient hashing schemes which achieve the similar results?


texts: Quicksort: compute the expected number of comparisons as a function of $M$ and $t$

texts:
I stumbled upon this problem on a list of open problems in the analysis of algorithms dating back to 1997. Is it still open? Can anyone point to a reference with a full or partial solution, or at least discussion?

Problem description (see link for more context):

  Let $C_n$ be the number of comparisons made by quicksort to sort
  a random permutation of $\{1,\ldots,n\}$, when using the median of a
  sample of size $2t+1$ to perform the partitions and the recursive
  calls stop at subfiles of size $M\ge 2t+1$.  Both $M$ are $t$ are constants.
  Compute the expected value of $C_n$ [as a function of] $M$ and $t$.


texts: complexity of CSPs with 2-variable constraints and multi-valued variables

texts:
(CSP = "constraint satisfaction problem")

CSPs for which either the variables are restricted to less than two values or the constraints
take less than two inputs are obviously trivial, and Schaefer's dichotomy theorem

gives the complete situation for variables with two possible values.

How hard is it to solve CSPs with 2-variable constraints

but variables that can take more than two values?


texts: What are consequences of the collapse of CH?

texts: I don't grasp the full complexity of the counting hierarchy $CH$. I understand $CH$ is in $PSPACE$, and contains $PH$ within its second level, due to the Toda's theorem. But, what would be important consequences of the collapse of $CH$? I got a sort of intuition behind the conjecture the polynomial hierarchy $PH$ doesn't collapse. Nevertheless, since $PP^{PH}\subseteq P^{PP}=P^{\# P}\subseteq C_2^P$ due to the Toda's theorem, where $C_2^P$ is the second level of $CH$, the power of counting seems huge. Thus, what would be wrong or unexpected if $CH$ collapsed? And what if the stronger condition $CH=PSPACE$ held?


texts: Complexity of the Hamiltonian Subcycle problem

texts:
The problem is as follows:

  Given a graph $G$, find a (vertex)
  disjoint set of cycles $C$ on $G$ such
  that every vertex is visited by a
  cycle exactly once.

My question is then: what is the complexity of this problem? Is it NP-hard, in P or something else?

If we modify the problem to require $|C| = 1$, we end up with the standard Hamiltonian Cycle problem. It's easy to see that for any $k$, if we require $|C| = k$ or $|C| \leq k$, then the problem is NP-hard: given an instance for the Hamiltonian Cycle problem, we simply copy this graph $k$ times.

An equivalent definition of the problem is as follows:

  Given a graph $G$, have every vertex
  $v$ 'choose' some other vertex $u$
  such that $(u,v) \in E$, and that
  every vertex is chosen exactly once.

If you prove the above problem NP-hard, then for any $k$, if we modify the problem so that every vertex chooses $k$ vertices and every vertex is chosen exactly $k$ times, then the resulting problem is NP-hard as well: you can reduce the problem for any $k$ to the Hamiltonian Subcycle problem by 'eating up' the number of choices each vertex has by attaching certain gadgets to them.

I came across this problem when I believed a certain problem was in fact equivalent to the above problem. That later turned out to be wrong, but the problem interested me nonetheless.

I've developed an algorithm that sometimes finds the correct answer, but often doesn't end at all. It's based on using Lagrangian relaxation on the TSP variant of the above problem, which is simply TSP where more than one cycle is allowed (as long as the cycles are disjoint). I doubt it's possible to fix the algorithm so it works all the time, so I haven't included it in this question, though I could always do that if needed.


texts: Is there a Turing complete planetary system?

texts:
Seemingly simple things have turned out to be capable of computation - Conway's Game of Life, Wolfram's Rule 110, etc.

Has anyone devised a Turing complete system using suns, planets, moons, sub-moons, etc? Just inert chunks of matter in space behaving according to Newtonian physics that perform computation?


texts: Complexity of extending $P_4 $-partition of cubic graphs

texts:
This is a question I posted on MathOverflow before but never got an answer. I am cross-posting it here.

Surprising phenomena occurs when we want to extend a partial solution of some easy problems. We are given part of the solution and we want to decide whether we can extend it to a complete solution. Extendability problem can transform an easy problem to hard one.

For instance, Konig-Hall theorem states that all cubic bipartite graphs
are 3-edge colorable but the extendability version becomes $NP$-complete if we are given the colors of some edges.

It is a fact that the edges of any bridgeless cubic graph can be partitioned into edge-disjoint paths $P_4$ (follows from Petersen's theorem). Given a set of paths $P_4$ (of three edges), I suspect that it is hard to decide the existence of edge partition into $P_4$ paths that include the given paths.

  Is this extendibility problem NP-complete?

Extendibility problem

INPUT: Bridgeless cubic graph $G(V,E)$ and set of paths $P_4=(e_i,e_j,e_k)$ where $e_i,e_j,e_k \in E$

QUERY: Is there a partition of the edge set $E$ into edge-disjoint paths $P_4$ that include the input paths


texts: Is being fooled by limited independence preserved by products?

texts:
Question. Let $f,g : \{\pm 1\}^n \to \{\pm 1\}$ be $\varepsilon$-fooled by $k$-wise independence -- i.e. for any $k$-wise independent random variable $X$, $\left|\mathbb{E}[f(X)] - \mathbb{E}[f(U)]\right| \le \varepsilon$ (where $U$ is uniform) and likewise for $g$. Define $h(x,y) = f(x) \cdot g(y)$. Is $h$ necessarily $O(\varepsilon)$-fooled by $O(k)$-wise independence?

If $\varepsilon=0$, the answer is yes: The hypotheses imply that $f$ and $g$ are polynomials of degree at most $k$, which implies $h$ has degree at most $2k$ and is therefore fooled by $2k$-wise independence.

This feels like it shouldn't be too hard to answer. Any ideas?

There is an equivalent formulation in terms of sandwiching polynomials (see e.g. [Bazzi07] $\S 1.1$): Essentially, it asks is the product of two "almost" degree-$k$ functions "almost" degree $O(k)$?

 Equivalent Question.
Let $f,g : \{\pm 1\}^n \to \{\pm 1\}$. Suppose there exist polynomials $f_+,f_-,g_+,g_- : \{\pm 1\}^n \to \mathbb{R}$ of degree at most $k$ such that $$f_-(x) \le f(x) \le f_+(x) ~~~ \text{and} ~~~ g_-(x) \le g(x) \le g_+(x)$$ for all $x \in \{\pm 1\}^n$ and $$\mathbb{E}[f_+(U)-f_-(U)] \le \varepsilon ~~~\text{and}~~~ \mathbb{E}[g_+(U)-g_-(U)] \le \varepsilon.$$ Do there exist polynomials $h_+, h_- : \{\pm 1\}^{n} \times \{\pm 1\}^{n} \to \mathbb{R}$ of degree $O(k)$ such that $h_-(x,y) \le f(x) \cdot g(y) \le h_+(x,y)$ for all $x,y \in \{\pm 1\}^n$ and $\mathbb{E}[h_+(U,U')-h_-(U,U')] \le O(\varepsilon)$?

The obvious thing to try is setting $h_\pm(x,y)=f_\pm(x) \cdot g_\pm(y)$. Unfortunately, it doesn't seem to work out (essentially the signs and inequalities don't go the right way).

I'm also interested in generalisations of this question, where $X$ is, say, small-biased, rather than $k$-wise independent.


texts: Applications of Combinatorial Games in Computational Biology

texts:
I'm looking for general references in the literature about applications of games algorithmics in computational biology.

Q1. What are the notable cases of computational-biology or bioinformatics problems that can be modeled/analyzed by means of combinatorial games ?

Q2. What are the notable cases of computational-biology or bioinformatics problems that can be modeled/analyzed by means of economic games ?


texts: Ramsey number for path in a colored tournament

texts:
I am looking about the following Ramseyish theorem with additional structure on tournament (see [1]).

  For all number of colors $k$, there exists $n=T(k)$ such that all tournaments of size $n$ colored with $k$ colors, there exists necessary a path of length $2$ monochromatic.

It is a direct consequence of Ramsey theorem when applied to triangle on the underlying colored graph. Now, I am looking for estimate on $T(k)$, that is the minimum size such that we are certain that a path of length $2$ exists. Remarks that $T(k)$ has to be at least larger than $k$. Indeed, otherwise you can associate to each vertices a unique color that you use to label its outgoing edges.

Actually, I don't really need the  precise value but simply to know if it is polynomial or exponential. Note that the same question for coloring numbers in $[n]$ (i.e. the tournament is a full order) sounds already non trivial, or maybe I miss something?

[1]: Wikipedia page for tournament https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Ramsey_theory


texts: Are there applications of modular graph decomposition in TCS/complexity theory?

texts:
What are there some applications of modular graph decomposition in TCS/complexity theory?

I am especially interested in its use in proofs or upper/lower bounds if it occurs.

[1] Modular graph decomposition, Wikipedia.

[2] References for Modular Decomposition, TCS.SE.


texts: Open/unsolved problems in (computational) random matrix theory / matrix completion?

texts:
I was wondering what some open problems are in random matrix theory (especially those of interest to TCS people/so mainly non-asymptotic things, I imagine). Also, and relatedly, what are remaining/outstanding open problems in matrix completion?

In view of the questions above, I'd also be interested if people can point to research monographs/survey papers/texts that provide some background on the topics (RMT in computer science/matrix completion) above.


texts: Bounded-cardinality bounded-frequency set cover: hardness of approximation

texts:
Consider the minimum set cover problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets.

Example: the case $k = 4$ and $f = 2$ is equivalent to the minimum vertex cover problem in graphs with maximum degree 4.

Let $a(k,f) > 1$ be the largest value such that finding an $a(k,f)$-approximation of the minimum set cover problem with parameters $k$ and $f$ is NP-hard.

Example: $a(4,2) \ge 1.0128$ (Berman & Karpinski 1999).

Question: Do we have a reference that summarises the strongest known lower bounds on $a(k,f)$? In particular, I'm interested in concrete values in the case that both $k$ and $f$ are small but $f > 2$.

Restricted versions of the set cover problem are often convenient in reductions; typically there is some freedom in choosing the values of $k$ and $f$, and further information on $a(k,f)$ would help to choose the right values that provide the strongest hardness results. References here, here, and here provide a starting point, but the information is somewhat outdated and fragmentary. I was wondering if there is a more complete and up-to-date source?


texts: Did von Neumann answer to Gödel's letter?

texts:
On 20 March 1956, Kurt Gödel wrote a famous letter to John von Neumann, in which he formulated the P versus NP question.
Here is a link to that letter:  [pdf of letter]

I cant seem to find John von Neumann's answer to Gödel's letter online.
Was there one ?


texts: Is DNF-Equivalence Problem $\mathsf{NP\mbox{-Hard}}$?

texts:
I have the following Equivalent DNF problem:

Input:Two DNF formulas, $F_1$ and $F_2$,with variables $a_1,a_2,...a_n.$

Output: $1$ if $F_1$ and $F_2$ are equivalent, $0$ otherwise.

$F_1$ and $F_2$ are equivalent if for all $(a_1,a_2,...a_n)∈\{0,1\}^n,F_1(a_1,a_2,...a_n)= F_2(a_1,a_2,...a_n).$

Is the DNF-Equivalence problem polynomial or in $\mathsf{NP\mbox{-Hard}}$? If in $P$, how do we find an efficient algorithm and determine its complexity. How do we prove it if it's $\mathsf{NP\mbox{-Hard}}$.


texts:
The sign rank of a matrix A with +1,-1 entries is the least rank (over the reals) of a matrix B which has the same sign pattern as A (i.e., $A_{ij}B_{ij}>0$ for all $i,j$). This notion is important in communication complexity and learning theory.

My question is: Are there any known (subexponential time) algorithms that approximate the sign-rank of a matrix to within a factor $o(n)$?

(I am aware of Forster's lower bound on the sign rank in terms of spectral norm, but this does not yield an approximation ratio better than $\Omega(n)$ in general.)


texts: Theoretical Applications for Approximation Algorithms

texts:
Lately I've started looking into approximation algorithms for NP-hard problems and I was wondering about the theoretical reasons for studying them. (The question is not meant to be inflammatory - I'm merely curious).

Some truly beautiful theory has come out of the study of approximation algorithms - the connection between the PCP theorem and hardness of approximation, the UGC conjecture, the Goeman-Williamson approximation algorithm, etc.

I was wondering though about the point of studying approximation algorithms for problems like Traveling Salesman, Asymmetric Traveling Salesman and other variants, various problems in mechanism design (for instance in combinatorial auctions), etc.
Have such approximation algorithms been useful in other parts of theory in the past or are they studied purely for their own sake?

Note: I'm not asking about any practical applications since as far as I know, in the real world, it's mostly heuristics that are applied rather than approximation algorithms and the heuristics are rarely informed by any insight gained by studying the approximation algorithms for the problem.


texts: P-complete decision problems about integers

texts:
Are there any known examples of P-complete decision problems which take as input a single integer? (non-unary, as unary feels like un-naturally forcing the issue)

It feels like there are many inherently sequential questions I could ask about an integer, but I don't know of any examples that have been shown to be P-complete.


texts: Complexity of isotopy of embedded graphs

texts:
I am looking for previous work on the following problem: given two graphs embedded in the plane without crossing, determine if they are isotopic. By isotopic I mean that there is a continuous deformation of the plane tranforming one embedding to the other, without introducing any crossing between edges during the transformation.

This isotopy notion is stronger than the much studied isomorphism of (planar) graphs, for instance when a connected component is nested in another (the nesting is preserved by isotopy, not isomorphism).

Do we know anything about the complexity of this problem, or anything similar?

A similar question asks about how to define this isotopy notion in combinatorial terms:
Equivalent embeddings of a graph

Precision: I am primarily interested in the case where the embedded graph is not connected.


texts: Tuning Parameters of Locality Sensitive Hashing

texts:
We have given a set of $n$ binary vectors each of dimension $d$, i.e.  a binary matrix of $d*n$. Our goal is to group vectors which are almost similar,  $\forall v_i, v_j\in\{0,1\}^d$, we say $v_i$ and $v_j$ are almost similar, if $HammingDistance(v_i,v_j)<\epsilon$. Since comparing two $d$ bit vectors are expensive, and $n$ is large, we can't afford to do $O(n^2)$ comparisons, we use Locality Sensitive Hashing algorithm to computer similarity preserving matrix in subquadratic time.

Now, my question is that how to tune parameters of LSH, i.e. # of hash tables $m$, # of entries per hash table $l$, such that error is minimizes (the number of similar items which hashes to different bucket, and  the number of dissimilar items which hashes to same bucket is minimizes).

Pls let me know if I am missing something obvious.


texts: Use of Process Calculi and PL Theory for modern programming language development

texts: For a while now, I have been very interested in programming language theory and process calculi and have started to study them. To be honest, it something that I wouldn't mind going into for a career. I find the theory to be incredibly fascinating. One constant question I keep running into is if either PL Theory or Process Calculi have any importance at all in modern programming language development. I see so many variants on the Pi-calculus out there and there is a lot of active research, but will they ever be needed or have important applications? The reason why I ask is because I love developing programming languages and the true end goal would be to use the theory to actually build a PL. For the stuff I have written, there really has not been any correlation to theory at all.


texts: How would I prove that the chromatic number of a graph $G$ is smaller than or equal to the path-width of $G$ + 1? or $\chi(G) \leq pw(G) + 1$


texts: What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

texts:
Let $X$ be the universe of elements, $F$ a collection of subsets $S \subseteq X$, each with an associated cost. The goal is to find a subcollection $C \subseteq F$ of minimum total cost which covers $X$.
GreedySetCover(X,F)
1 C ← ∅
2 U ← X
3 while U ≠ ∅
4     Find set S ∈ F \ C that minimizes α = cost(S) / |S ∩ U|
5     C ← C ∪ {S}
6     U ← U \ S
7 end while
8 return C

Let $N = |U|$ and $M = |F|$. Then, in the worst-case, all subsets $S \subseteq X$ have to be searched. In the first iteration we search $M$ sets, in the second iteration we search $M - 1$ sets and so on. The cost of computing $|S \cap U|$ is $O(N)$.
$$T(n) = N (M + (M - 1) + (M - 2) + \cdots + 2 + 1) = N M(M+1)/2 = O(N M^2)$$
I think this is correct. I am not sure how to approach the average case time complexity however.


texts: A good exposition of the random restriction method

texts: I'm wondering if there are good references that describe the random restriction method as a lower bound technique ? I'm aware that it's linked to the switching lemma and shows up in many different proofs, but I'm looking for a more or less self-contained explanation of the idea.


texts: Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G

texts:
You are given two graphs G and H , and want to know if H is a subgraph of G.

You know that H has a max vertex degree K (constant integer).

What can you say about the complexity of this?

I know that
Isomorphism of Graphs of Bounded Valence Can Be tested in Polynomial Time - Luks 1982,
that's the best I currently have...


texts:
i am searching an heuristic algorithm for a weighted exact cover problem shown here: http://en.wikipedia.org/wiki/Exact_cover

On my research i only found algorithm which calculates all solutions without any cost function, like http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

Do you know some algorithm for that?

My problem has a Universe of size 200 and about 500 000 subsets, so it is not possible to calculate all solutions.

--------------EDIT--------------

Example:

Universe = { 1, 2 ,3 ,4 ,5 ,6 ,7}

Sets=[

{1,2,3,4}, Cost 10

{5,6,7}, Cost 20

{5}, Cost 5

{6,7}, Cost 10
]

On this example i have to possible solutions {1,2,3,4} and {5,6,7} with cost 30 and the second solution is {1,2,3,4}, {5} and {6,7} with cost 25.


texts: Is there a standard interpretation of this quantity?

texts:
Define an encoding scheme by a pair of functions:
$$\mathsf{encode} : \mathcal{M}\to\mathcal{X},\quad \mathsf{decode} : \mathcal{X}\to\mathcal{M}$$
Typical examples of encoding schemes are things like error-correcting codes, encryption schemes, etc.
Define the rate of an encoding scheme in the standard way:
$$R = \frac{\log_2|\mathcal{M}|}{\log_2|\mathcal{X}|}$$
Let $R_0, R_1$ be the rates of two encoding schemes.
Does the quantity:
$$\frac{1 - R_0}{1 - R_0R_1}$$
have a standard interpretation?

Context: I have a way of designing encryption schemes by "plugging in" certain error-correcting codes into some template. In this framework, any encryption scheme has a "formal dual" (essentially using the dual codes in the instantiation. This requires a linearity assumption of course).
If $R_0, R_1$ are the rates of my encryption scheme instantiated by some code and its dual, I can relate the above expression to some other quantity that I have some lower bounds on.
This all might be interesting if this quantity has some standard coding-theoretic interpretation.
It seems plausible that it does, but I am not a coding theorist, and in general Googling for formula is quite difficult.
That being said, I am not especially optimistic, as I have not been able to give it some reasonable interpretation.


texts: Covering a binary relation as a union of rectangles

texts:
Given finite sets $X$ and $Y$ and a subset $R\subset X\times Y$, I want to express $R$ as a union $R=\bigcup_{i=1}^n X_i\times Y_i$ with $n$ as small as possible. Here, each $X_i\subset X$ and $Y_i\subset Y$, and I don't care whether the $X_i$ are disjoint, whether the $Y_i$ are disjoint, or whether the $X_i\times Y_i$ are disjoint. (I'm calling each $X_i\times Y_i$ a "rectangle" but there's no geometry here, just sets.)
If I think of this as a generic set cover problem, then it looks like it might be NP-hard. (With respect to what variable though, $|R|$ maybe?)
But I'm really hoping that this version of the problem, using these really "nice" rectangular covering sets that intersect in predictable ways, might be easier. What is known about this problem? Does it have a standard name and a nice theory behind it? Maybe if we think of $R$ as a matrix or a bipartite graph...?
For what it's worth, in practice I'm interested in what I suspect are fairly easy problem instances, where $|X|\leq 15$, $|Y|\leq 15$, typically $|R|\leq 70$, and the optimal $n$ is probably $\leq 4$. I haven't tried greedy search yet, because I'm hoping for an even simpler solution.


texts: What's the fastest known algorithm for finding the diameter of a graph?

texts: Given a positively weighted graph what's the fastest algorithm for finding the diameter for that graph?


texts: Characterization of $L$ for which $\{ww : w \in L\}$ is not a CFL?

texts:
It is a standard proof in automata courses that for $L = \Sigma^\star$ and $|\Sigma| \ge 2$ that $S(L) = \{ww : w \in L\}$ is not a context-free language.

It is also true that for any finite $L$, $S(L)$ is finite (and therefore a CFL). I'm guessing that $L$ being infinite and regular are not "sufficient" for $S(L)$ being not a CFL. Edit: what about non-CFL $L$?

Is there any characterization of what $L$ have $S(L)$ not being a CFL?


texts: Bin packing upper bound: total size of items = k, bin size = r

texts:
Suppose you have items, whose total size (i.e. sum of sizes) is $k$.
The number of items and their individual sizes are unknown integers.
We need to pack the items into bins of size $r$.

I need to find a number of bins $X$, such that given a random distribution of the items into bins (every item goes to every bin w.p. $1/X$), all bins will satisfy the size limit
(i.e. no bin will contain items of size more than r) with as high as possible probability.

If, for a specific $X$, we denote the success probability by $P_X$, then my goal is to minimize $\frac{X + 1 \choose k + 1}{P_X}$ (for an adversarial selection of item number and sizes).

We have pretty much established that if $X < \frac{2k}{r+1}$, then $P_X=0$ (or $X < \frac{2k}{r}$, in case $r$ is even).

I believe that if we pick $X = \frac{2k}{r}$, then we get a probability bound of $P_X \geq X!/X^X > e^{-X}$, since it looks like the worst case is when all items are of size $(r/2 + \epsilon)$, where $\epsilon \in {0.5,1}$ depending on whether $r$ is odd or even.

If this is indeed the worst case, I have to get all of the items colored by different colors (packed into different random beans), so the bound $P_X \geq X!/X^X$ is tight.

The motivation for this problem comes from random coloring of graphs, where I want to color weighted vertices, such that no color will have vertices of weight more than $r$ colored by it.

~~~~~~~~~~

A try to formalize the question in a simpler manner:

Find a minimal number of colors $C$, such that if we randomly color an item set $I$, whose total size is $k$:

The probability of the event where there is a color in which an items of size $> r$ is only exponentially low in $k$.


texts: When is it hard to invert a sparse matrix?

texts:
Are cases where numeric inversion of a sparse matrix is known to be harder than sparse matrix multiplication?
In practice, sparse matrix inversion is done with methods like Jacobi or Gauss-Seidel, which  give a good estimate after a small number of sparse matrix multiplications, when they converge.
However such methods fail to converge when off-diagonal entries are large compared to diagonal entries. I'm curious if this is a limitation of those methods, or reflects a fundamental difficulty of the task.


texts:
Does there exist a w-bit word-RAM data structure with O(1) time per operation for the following problem?:  Maintain a set of w-bit non-negative integers that supports the operations

add(x) : add x to the set
remove(x) : remove x from the set
fingerprint() : return a fingerprint of the set.  This w-bit fingerprint has  the property that two sets that are identical have the same fingerprint while two sets that are different probably have different fingerprints

All operations should run in constant time.

The Rabin-Karp fingerprinting scheme, where $$f(S) = \left(\sum_{x\in S} 2^x\right) \bmod p$$ where p is a random w-bit prime almost works.  The problem is with the update time, since computing $$2^x \bmod p$$ takes more than constant time.  Using repeated squaring, this can be done in O(log w) time. The fastest modular exponentiation algorithm I could find does something like (log w)/(loglog w) arithmetic operations.


texts: Curriculum: Logical/Formal Methods in Security

texts:
At present I teach a small course (Four two hour lectures at the Masters level) on Logical Methods in Security, though the title Formal Methods in Security might be more apt. It covers briefly the following topics (with associated logical methods):

Digital Rights Management and Policy Enforcement (general formalisation, modal logic, enforcement via automata)
Proof-carrying code and proof-carrying authentication (proof theory, logical systems, Curry-Howard Isomorphism, verification)
Access Control (non-classical logics, proof theory)
Stack Inspection (programming language semantics, contextual equivalence, bisimulation)

Naturally, the course has multiple goals, where one of them is attracting potential graduate students.

In the coming years the course may be expanded to a regular course, which will need more content. Given that the background of people here is quite different from mine, I would like to know what content you would include in such a course.


texts: Teaching high school TCS - existing programs

texts:
I was offered to teach a novel TCS high school program, which requires constructing a curriculum. I would very much like to hear opinions and suggestions regarding this.

First, does anyone know of high schools where a TCS program has been taught successfully (or unsuccessfully)?

The idea is for a 3-year program (10th-12th grades, ages 16-18), about 8 weekly hours, for selected outstanding students, meaning that it can and should be demanding. Unlike the standard "computers" program, this program should not focus on programming, but rather on selected topics in CS, mostly in TCS. The topics we have in mind so far are, broadly:

Asymptotic analysis
Basic data structures and algorithms (lists, arrays)
Graph algorithms, also as a demonstration of greedy algorithms v.s. dynamic programming.
Other algorithms (e.g. probabilistic)
Computability - the concept of a TM, reduction, decidability.
Complexity - NP, P, perhaps PSPACE and NL. Completeness.
Automata theory

Basically, this covers the TCS part of the first two years of a B.Sc in CS. However, we must keep in mind that these students lack the mathematical foundation needed for most of this material. In particular, things like set theory, combinatorics, probability, and modular artihmetic are not taught in high school (unfortunately).

To sum up, and to give precise questions:

Does anyone know of a similar program anywhere?
Are there suggestions for concrete/general topics which you think can and should be taught in addition/instead of the topics above, while keeping the program interesting as well as important and directly relevant (e.g. group theory is important and interesting, but not relevant enough to justify the time it will take)
I would have been happy to introduce machine-learning in some form, as it is a really hot topic nowadays. Any ideas as to how machine learning can be presented without tools like measure-concentration theorems are welcome.


texts:
I was asked the following by a student, and couldn't come up with a complete answer:

Are there any closure properties for the class of languages that are not context free?

It's fairly easy to find examples that show that it is not closed under intersection and iteration (Kleene star operator), but how about union and concatenation? My guess is that it's not closed under either, so unless I'm way off, what I'm looking for are examples for two non-CFLs that their union or concatenation is a CFL.


texts: Data structure to report points in the intersection of two circles

texts:
The circular range reporting is defined as follow: preprocess $n$ points in the plane so that the points inside a query circle, of any radius, can be reported quickly.

This was solved beautifully and optimally in a paper by Afshani and Chan. Their solution uses $O(n)$ preprocessing time and $O(\log n + k)$ time to answer a query, where $k$ is the number of points reported.

Consider the following variant. We have $n$ points in the plane but now we query with 2 points $p_1$ and $p_2$ and a radius $r$.  A query should return the points that are within distance $r$ of both $p_1$ and $p_2$.

Clearly we could just run the algorithm of Afshani and Chan twice and return the intersection of the two given sets of points. However the intersection of the two sets may be much smaller than their union.

Is there a known data structure that takes $O(\log n + k')$ time per query where $k'$ is the number of points to be reported?


texts: Maximize the weight of MST + sum of vertex weights

texts: I am considering a problem where the goal is to choose a subset of size $k$ of the vertices in a graph, such that the weight of their minimum spanning tree + the sum of their vertex weights is maximized. Has this problem been studied before? It is submodular.


texts: Are equally weighted MSTs closely related?

texts:
Suppose we have an undirected connected graph $G=(V,E)$ that has several minimum spanning trees. We say two trees $T_1, T_2$ are connected if they share exactly $|V|-2$ edges(*).  In other words $T_1$ can be obtained from $T_2$ by removing exactly one edge $e_1$, and adding another edge $e_2$.

Now suppose we draw a new graph $H$ that its vertices are the MSTs of the graph $G$, and there is an edge between them if they share $|V|-2$ edges. The question is, is graph $H$ connected?

One can view the problem also this way: can we obtain other minimum spanning trees by greedily looking for edges that can be replaced with another edge, without increasing the total weight along the way?

(*) Given that trees have $|V|-1$ edges, two distinct trees cannot have more than $|V|-2$ in common. So this is the maximum number of edges in common they can have.


texts: Time complexity of derivative-based regex matchers

texts:
Regex matching using the Brzozowski derivative without any caching or expression-simplifying takes exponential time and space because of the product rule.

In Brzozowski's original paper, Brzozowski shows how to generate a DFA using the derivative operation. The upper bound he finds on the size of that DFA is an iterated exponential. So going on the upper bound alone, transforming a regex to a DFA via differentiation is less efficient than "running" the regex "directly".

In a later paper "Regular-expression derivatives reexamined", the authors show how to use automatic expression-simplifying to speed up Brzozowski's algorithm; but nothing is proven about the worst-case complexity.

Also, the theory of Brzozowski differentiations works just as well on ordinary regexes as it does on Extended Regexes, which feature intersection and complement. If deciding whether an Extended Regex expresses the Empty language were possible to do efficiently, then that would imply that derivative-based matching must be worst-case inefficient.

So what is the time-complexity of Brzozowski derivative-based matchers if automatic expression-simplifying is used?


texts: Lack of atomic propositions in the Calculus of Constructions from ATTAPL textbook

texts:
I am working through the Dependent Types chapter from Advanced Topics in Types and Programming Languages (ATTAPL) by Benjamin Pierce et al. I am confused with the calculus presented Fig 2-7 (Calculus of Constructions) that extends $\lambda LF$ to support Prop type. I have multiple questions.

Can a Prop term be $\beta$-reduced at all? The rule (BETA-ALL) on the next page suggests that only the body of a Prop can be reduced. That is, in the term forall x:T.t, only t is reduced.
There are no atomic propositions like True, False. So how can one build a term of type Prop (and Prf p). Any simple example suffices.
I am not sure I understand the type equivalence rule QT-ALL in Fig 2-7.
The encoding of nat (and zero later on) is confusing. For the sake of readability I am writing it down here.

nat = all a:Prop.all z:Prf a.all s:Prf a ->Prf a. a

What is the meaning? Specifically, what is a - any Prop? Why are proofs of z (zero) and s (succ) required?

I think these are lot of questions. I would appreciate answers to any of these questions.

EDIT: I was suggested to move this to cs.stackexchange.com. However, the question is about the meta-theory of Coq and I thought cstheory is an appropriate forum. But if multiple users suggest moving this, I can do that.


texts: Hardness of Approximation results for Special Set Packing Problem Wanted

texts:
Is there any inapproximability result for the following NP-hard problem, which is a special case of the weighted Set Packing Problem?

The general Set Packing Problem would be:
Given A Collection of Sets $S=\{S_1,\ldots,S_n\}$ over a base set $U$, find the subset $S'\subseteq S$ such that each element of $U$ is covered at most once (i.e. the sets in $S'$ are mutually disjoint) and $S'$ has the maximum total weight over all such subsets.

And my weight function assigns a set $S_i$ the weight $|S_i-1|$

Then, the IP would be

$\max \sum_{S_i \in S}|S_i-1|x_{S_i}$

s.t. $\sum_{S_i:c\in S_i}x_{S_i}\leq 1 \hspace{1 cm} \forall c\in U$

$x_{S_i}\in\{0,1\}$

It is easy to see that the problem is NP-complete, by reducing Exact Cover by 3-Sets on it.
All approximation algorithms from the classical weighted set packing problem obviously work here as well.

My Questions:

Can we do better on this special instances?
Is there a known inapproximability result for this kind of problem?
Does this problem has a name in the literature?
What about the following minimization version: Cover as many elements as possible with the least number of sets? More specific: We have that the sets in $S$ contain also the singleton sets $\{c\}$ for all $c\in U$. That is, we can easily generate a feasible solution. And we want to find the solution to the following IP:

$\min \sum_{S_i \in S}x_{S_i}$

s.t. $\sum_{S_i:c\in S_i}x_{S_i}= 1 \hspace{1 cm} \forall c\in U$

$x_{S_i}\in\{0,1\}$


texts:
This might sound like a trivial question. But since am starting out with my research in an area that is entirely new to me, I would really appreciate it if someone could kindly elucidate what Soft truth values mean.

I came across this in the context of PSL(Probabilistic Soft Logic).
This paper stated that;

  PSL uses first order logic rules as a template language for graphical models over random variables with soft truth values from the interval [0,1].

Any clarifications in this regard will be much appreciated.


texts: What algorithm is behind akinator or 20q?

texts:
The title speaks for itself. Here are Akinator and 20Q.

The principle of these games is to ask a user a number of questions relating to some entity chosen by the user. And then find out what is this entity. The core of the algorithm is to find the "most useful question" at each round, while dealing with a user who might not answer all questions correctly.

"most useful question" being defined as the question that give the most information, in the optimal case splitting the audience (or number?) of candidate entities into two equal halves.

I found a paper that described some algorithms (well the word "algorithm" was not used, but the proofs could be turned into algorithms). Unfortunately I cannot find this paper again :( . The paper described the problem with game theory concepts, with some levels of lying allowed to the user (it discussed  3 levels of lying). Please post if you think you know the paper.


texts:
In classical computing NAND is a complete set (functionally complete) of binary operations, namely any Boolean circuit can be expressed using NAND gates.

Is there an equivalent for quantum computing circuit? It should be possible imho to have such a complete set because any rotation ob Bloch sphere is reducible to Euler angles based rotation matrices: $R=X(\alpha)Y(\beta)Z(\gamma)$.


texts: Does every greedy algorithm have matroid structure?

texts: It is well established that for every matroid $M$ and any weight function $w$, there exits an algorithm $\mbox{GreedyBasis}(M,w)$ which returns a maximum weight basis of $M$. So, is the reverse direction also true? That is, if there is some greedy algorithm, then there must be some matroid structure also.


texts: Cut-elimination for calculus with nats or other inductive datatype?

texts:
Does anyone direct me to a paper detailing a cut-elimination theorem for propositional intuitionistic logic, including an inductive datatype such as the natural numbers (lists or trees would be fine, too)? An example of the kind of system I am interested in is Godel's T, which has types given by the grammar $A ::= \mathbb{N} \;\;|\;\; A \to A'$. I am not very interested in quantifiers over natural numbers or predicates indexed by natural numbers.

I know how to prove beta-normalization for natural deduction version of these systems using a logical relations argument (or related techniques such as NbE), but would like to know if there are standard references on how to adapt these methods to sequent calculi.

The reason I ask is that I am studying adding fixed point operators for guarded recursion to a language. The denotational idea is a rather old one -- interpret types as ultrametric spaces and fixed points via Banach's theorem -- but the purely syntactic techniques I know for proving cut-elimination don't seem to adapt that well.


texts: What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?

texts:
Background
The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore real numbers can not be faithfully represented by finite strings over a finite alphabet.
Unlike the classical computability over finite strings where different models of computation like: lambda calculus, Turing machines, recursive functions, ... turn out to be equivalent (at least for computability over functions on strings), there are various proposed models for computation over real numbers which are not compatible. For example, in the TTE model (see also [Wei00]) which is the closest one to the classical Turing machine model, the real numbers are represented using infinite input tapes (like Turing's oracles) and it is not possible to decide the comparison and equality relations between two given real numbers (in finite amount of time). On the other hand in the BBS/real-RAM models which are similar to RAM machine model, we have variables that can store arbitrary real numbers, and comparison and equality are among the atomic operations of the model. For this and similar reasons many experts say that the BSS/real-RAM models are not realistic (cannot be implemented, at least not on current digital computers), and they prefer the TTE or other equivalent models to TTE like effective domain theoretic model, Ko-Friedman model, etc.
If I understood correctly, the default model of computation which is used in Computational Geometry is the BSS (a.k.a. real-RAM, see [BCSS98]) model.
On the other hand, it seems to me that in the implementation of the algorithms in Computational Geometry (e.g. LEDA), we are only dealing with algebraic numbers and no higher-type infinite objects or computations are involved (is this correct?). So it appears to me (probably naively) that one can also use the classical model of computation over finite strings to deal with these numbers and use the usual model of computation (which is also used for implementation of the algorithms) to discuss correctness and complexity of algorithms.

Questions:

What are the reasons that researchers in Computational Geometry prefer to use the BSS/real-RAM model? (reasons specific Computational Geometry for using the BSS/real-RAM model)
What are the problems with the (probably naive) idea that I have mentioned in the previous paragraph? (using the classic model of computation and restricting the inputs to algebraic numbers in Computational Geometry)

Addendum:
There is also the complexity of algorithms issue, it is very easy to decide the following problem in the BSS/real-RAM model:

Given two sets $S$ and $T$ of positive integers,
is $\sum_{s\in S} \sqrt{s} > \sum_{t\in T}\sqrt{t}$?

While no efficient integer-RAM algorithm is known for solving it. Thanks to JeffE for the example.

References:

Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale, "Complexity and Real Computation", 1998
Klaus Weihrauch, "Computable Analysis, An Introduction", 2000


texts: Diameter of "almost" always connected Erdős-Renyi graphs

texts:
Let $G=(V,E)$ be a random Erdős-Renyi Graph, i.e., $G\in\mathcal{G}(n,p)$.
It is well known that if $p=(\log n +c +o(1))/n$ with $c\in\Re$ then
$$
P(G \text{ is connected})=e^{-e^{-c}}\ .
$$

However, I found no information about the expectation of the diameter if $G$ is connected.

  My question is: Let $G\in\mathcal{G}(n,p)$ with $p=(\log n +c +o(1))/n$ and $c\in\Re$. What is the value of
  $$
\mathbb{E}(diam\ G \mid G\text{ is connected})
$$

Is the result known? Or is it an open question? Any reference is welcome.

Motivation:

I'm performing simulations of several algorithms to compute the diameter of random graphs. Some of them are generated using the value of $p$ above. A graph is used only if it is connected. I would like to compare the results with the theoretical expectation.