texts: Regrouping a collection of sets based on constraint

texts:
(Pardon me for any unrefined usage/terminology for I do not have a math/CS background.)
Consider a collection of $N$ balls with subsets of $n_1, n_2, ..., n_L$ balls of different $L$ colors. The problem is to partition the $N$ balls into $M$ equal-sized groups (given $(N\mod M)=0$) such that the color subsets are preserved within new groups as much as possible. In the scenarios I'm concerned with, you could assume that for all $L$ original subsets, $n_l < (N/M)$.

Here's an example to make the problem clear:
For a collection of $12$ balls with $4$ color-subsets - $\{1111\}$, $\{222\}$, $\{33\}$, $\{444\}$ - that needs to be split into 2 groups, the best way to do so is $\{111133\}$ and $\{222444\}$

Is this problem well-defined?
Is there an algorithm to solve this problem exactly in polynomial time?
If not, is there an approximate algorithm?


texts: The minimum number of arithmetic operations to compute the determinant

texts: Has there been any work on finding the minimum number of elementary arithmetic operations needed to compute the determinant of an $n$ by $n$ matrix for small and fixed $n$?  For example, $n=5$.


texts:
We know that there are many families of matrices over $\Bbb F_q$, $\Bbb R$ etc are rigid.
See http://mahdi.cheraghchi.info/talks/rigidity_talk.pdf

Do we know there are many families of rigid REAL matrices with alphabet $\{0,1\}$ or $\{-1,+1\}$ (note not same as $\Bbb F_2$)?


texts: Complexity of generically inverting a class of near linear monotonic functions

texts:
Given a monotonic increasing function $f(\mathbb{N}) \rightarrow \mathbb{N}$ and a slack function  $a(\mathbb{N})\rightarrow \mathbb{N}$, where $f(n) = n \pm O(a(n))$;  how many calls to $f$ do we need to brute force $f^{-1}$ as a function of $a$ and $n$?

This problem comes up regularly when you have a near linear monotonic increasing sequence on OEIS which you have a good complexity algorithm to compute it, and need a generic algorithm to get an upper bound on the complexity of computing the inverse.


texts: The length of non perfect binary 1 error correcting codes

texts: I am interested in the best known number of code words in binary 1 error correcting codes of length $n$. I am aware of the Hamming code when $n=2^r-1$, but i would like to get lower bounds for other $n$ too. My motivation is completely theoretical and is related to graph theory.


texts: Why must QMA complete problems be promise problems?

texts:
I'm reading Watrous's excellent survey paper on paper on quantum complexity theory. In it he states that it would be surprising if a QMA -complete problem were found to have a vacuous promise (I.e. Be a language). Why is this so?

Does it have to do with the fact that the k-local Hamiltonian problem is a promise problem?

Also, this leads me to a related question: are there QMA-complete problems that aren't inherently "quantum" in nature?


texts: Lighting up all elements of a poset by toggling upsets

texts:
I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. Each move of the game consists of choosing one element $x$ of the poset; then I consider its upset $U_x = \{y \in P \mid x \leq y\}$ and:

If all elements of $U_x$ are off, then I can play an on-move on $x$, which turns all of $U_x$ on, so $S$ becomes $S \cup U_x$ (with the union being disjoint).
If all elements of $U_x$ are on, I can play an off-move on $x$ and turn all of $U_x$ off, so $S$ becomes $S \setminus U_x$ (with $U_x \subseteq S$).
Otherwise I cannot currently play on this $x$.

My goal is to switch on all elements of the poset, i.e., find a sequence of moves that reaches $S = P$, from the initial configuration $S = \emptyset$. However, I impose that for each element $x$, all my plays on $x$ in the sequence are of the same type, i.e., if I play an on-move on $x$ then I am not allowed to play an off-move on $x$ at any point of the sequence -- but I can play other on-moves on $x$ if I want. (If we don't impose this, then it's not too hard to show by induction that we can always win.)

My question is: What are the posets on which there is a way to win the game? In particular, can we always win when $P$ is a join-semilattice, i.e., any nonempty subset of elements has a least upper bound?

For a simple example of the game, consider $P$ with the following Hasse diagram:

I have animated a winning strategy on the picture. Initially all vertices are off (=white). Then we do the following:

first play an on-move on $A$ (and $S$ becomes $\{A, D, E\}$),
then play an off-move on $D$ (and $S$ becomes $\{A\}$),
then play an on-move on $B$ (and $S$ becomes $\{A, B, D, E\}$),
then play an off-move on $D$ again (and $S$ becomes $\{A, B\}$),
last play an on-move on $C$ (and $S$ becomes $P$ and I have won).

For a more complicated example, consider the following:

I have animated the steps on a winning sequence: on-move on $A$, off-move on $D$, on-move on $B$, off-move on $E$, on-move on $G$, off-move on $F$, on-move on $C$. Note that this is a bit tricky to find, e.g., starting a play with $G$ cannot win.

There is a relationship between the game and the Möbius inversion formula on posets. Specifically, if I define $\mu(x) = 1 - \sum_{y < x} \mu(y)$, in particular $\mu(x) = 1$ if $x$ has no ancestors, then the sign and absolute value of $\mu(x)$ tells me which types of move I should play on $x$, and how many. In particular when $\mu(x) = 0$, we should never play on $x$, as with the vertex $H$ in the example above. Another way to see this is about a restricted way to compute the inclusion-exclusion formula with no cancellations.

I already know that we cannot win on every poset, as a computer search by Louis Jachiet turned out the following poset, where there is no winning strategy (checked by exhaustive search). There is no counterexample with less than 9 elements:

For our purposes we are interested in knowing whether the game can always be won on join-semilattices, i.e., every nonempty set of elements has a least upper bound (i.e., a unique descendant which is as high as possible). This is not the case above (consider $A$ and $B$), and this requirement seems to constrain the structure of the graph, but we don't know how to prove the claim (or whether it is true). We have been running a computer search for join-semilattices on which the game cannot be won, but we haven't found a counterexample yet.

As for the motivation of the problem, it was originally about expressing certain kinds of Boolean functions using restricted classes of circuits, with connections to safe queries over probabilistic databases.


texts: Are any of the state of the art Maximum Flow algorithms practical?

texts:
For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year.  Orlin's Max flows in O(mn) time or better gives an algorithm that runs in O(VE).

On the other hand, the algorithms I most commonly see implemented are (I don't claim to have done an exhaustive search; this is just from casual observation):

Edmonds-Karp: $O(VE^2)$,
Push-relabel: $O(V^2 E)$ or $O(V^3)$ using FIFO vertex selection,
Dinic's Algorithm: $O(V^2 E)$.

Are the algorithms with better asymptotic running time just not practical for the problem sizes in the real world?  Also, I see "Dynamic Trees" are involved in quite a few algorithms; are these ever used in practice?

Note: this question was originally asked on stack overflow, here, but I was told it would be a better fit here.

EDIT: I asked a related question on cs.stackexchange, specifically about the algorithms that use dynamic trees (aka link-cut trees), which may be of interest for people following this question.


texts: Reference Request: Error correction code for a random projection

texts:
I'm interested in a variant of the Binary Channel, where the bits aren't flipped with some probability, but rather they are completely erased. Output words therefore vary in length.

I'm quite sure that this subject is well researched, and all I need is the correct search term.


texts: Single-pass streaming quantile estimation using moments

texts:
Is it possible to estimate within $\epsilon$ the quantiles of a set of integers $\{x_1, x_2, \dots, x_n\}$ given only the values $\sum x_i^0,\sum x_i^1, \sum x_i^2, \dots, \sum x_i^{f(n)}$ where $f \in o(n)$? If so, what is the most slowly growing $f$ that will suffice?

By "estimate the quantiles", I mean:

  ... for any given rank $r$, an $\epsilon$-approximate quantile summary returns a value whose rank $r'$ is guaranteed to be within the interval $[r - \epsilon n, r + \epsilon n]$.

following "Space-Efficient Online Computation of Quantile
Summaries", by Greenwald and Khanna.

I'm also interested in whether this is possible with non-integer, non-consecutive moments, so sets of values like $\sum x_i^{-1/2}, \sum x_i^\pi$ are also of interest.

I am more interested in deterministic algorithms than randomized ones.


texts: Lower bounds for quantum circuits using the geodesic framework

texts:
(this question is a crosspost from cstheory. I've incorporated the one answer there into the question)

Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum lower bounds (in brief, the construction of a Finsler metric on $SU(2^n)$ such that the geodesic distance from $I$ to an element $U$ is a lower bound on the number of gates in a quantum circuit that computes $U$).

I was wondering if there were concrete examples of problems where this program led to a lower bound that came close to, matched or beat prior lower bounds obtained by other means ?

One example that Joe Fitzsimmons provided is this paper on optimal transfer rates in spin chains. While it's a good example of the "spirit" of the original idea, I'm specifically looking for methods that use Nielsen's program to provide lower bounds.


texts: Extending the sequential calculus (logic over words) to allow a hierarchy of languages like the arithmetical hierarchy

texts:
Let $\Sigma$ be some finite alphabet. Then consider the logical language $\mathcal L = \{ R_a : a \in \Sigma \} \cup \{ <,= \}$ and first order formulas. For a given first order formula $\varphi$ a word $w \in \Sigma^*$ is a structure for it in the sense that the variables range over $\{ 1, \ldots, |w| \}$, where $|w|$ denotes the length of $w$ and
$R_a = \{ 1 \le i \le |w| : \mbox{ the word $w$ has symbol $a$ at position $i$ } \}$. For example for $a \in \Sigma$
$$
 \exists x ( R_ax)
$$
describes the language of all words with at least one $a$ in it.

This is the usual approach to logic on words which goes back to Büchi, see this survey, or this survey, or these slides.

This generalizes the logic over $\mathbb N$ (special case of $|\Sigma|=1$) with $<$ and $=$.

But this logic does not allow me to describe languages (sets of words) similar as the Arithmetical Hierarchy allows me to describe subsets of $\mathbb N$, the problem is that the variables are over the positions of a word, not the words itself. Hence I can just use them to define subsets of $\mathbb N$.

Is there any logic or variation such that the variables run over words and I can us formulas to built up a hierarchy like the Arithmetical Hierarchy? I somehow think about a multi-sorted logic where I can quantify over words and positions, such that the above set could be defined by $\varphi(w) = \exists x R_a(w,x)$ with free word variable $w$, i.e. we have
$$
 w \in \Sigma^* a \Sigma^* \Leftrightarrow \varphi(w).
$$
Is there anything done in that direction? Or are there other approaches with similar goals?


texts:
Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs.

  Given a graph $G$ and a collection $C$ of subsets of nodes.  One need
  to compute for each $S \in C$ the number of triangles in $G[S]$ -
  subgraph induced on $S$.

Do we know any efficient way to do this?

Clearly one can do it in $|C| n^{\omega}$. But I was hoping for something better.

The only relevant result I'm aware of is "Clustered integer 3SUM via additive combinatorics" by TM Chan and M Lewenstein. They were able to provide an algorithm with running time $O(n^{\frac{13}{7}} |C|)$ for sufficiently large $|C|$ for $3$-Sum in the same setting: given $n$ numbers and collection $C$ of subsets of this numbers, one needs to solve $3$-Sum on each subset.


texts: Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

texts:
Given a finite (deterministic or nondeterministic, I don't think this has much importance) automaton A and a threshold n, does A accept a word containing at most n distinct letters?

(By k different letters I mean that aabaa has two distinct letters, a and b.)

I showed this problem to be NP-complete, but my reduction produces automata in which the same letter appears on many transitions.

I'm rather interested in the cases where each letter appears at most k times in A, where k is a fixed parameter. Is the problem still NP-complete?

For k=1 the problem is just shortest path, so is P. For k=2 I've neither been able to show membership in P nor to find a proof of NP-hardness.

Any idea, at least for k=2 ?


texts: What are the relations between Alternative, MonadPlus(LeftCatch) and MonadPlus(LeftDistributive)?

texts:
Following up What’s an example of a Monad which is an Alternative but not a MonadPlus?:

Assume $m$ is a monad. What are the relations betweem $m$ being an Alternative, a MonadPlusCatch and a MonadPlusDistr? For each of the six possible pairs, I'd like to have either a proof that one implies another, or a counter-example that it doesn't.

(I'm using

MonadPlusCatch to distinguish a MonadPlus that satisfies the Left-Catch rule:

mplus (return a) b = return a

MonadPlusDistr to distinguish a MonadPlus that satifies Left-Distribution rule:

mplus a b >>= k = mplus (a >>= k) (b >>= k)

see MonadPlus on HaskellWiki.)

My current knowledge + intuition is that:

MonadPlusDist $\rightarrow$ Alternative - likely true - it seems straightforward, I believe I have sketch of a proof, I'll check it and if it's correct, I'll post it AndrewC answered this part.
Alternative $\rightarrow$ MonadPlusDist - false - as AndrewC showed in his answer: Maybe is an Alternative, but it's known it's not MonadPlusDist (it's MonadPlusCatch).
MonadPlusCatch $\rightarrow$ Alternative - likely false - I believe that MaybeT (Either e) (or basically anything MaybeT m') should serve as a counterexample. The reason is that

((pure x) <|> g) <*> a =    -- LeftCatch
    (pure x) <*> a
-- which in general cannot be equal to
((pure x) <*> a) <|> (g <*> a)

again I'll check and post. (Interestingly, for just Maybe it's provable, because we can analyze if a is Just something or Nothing - see the aforementioned AndrewC's answer.)
Alternative $\rightarrow$ MonadPlusCatch - likely false - if we prove that MonadPlusDist $\rightarrow$ Alternative then [] will server as a counter-example. (Or we could explicitly prove Alternative laws for [].)
MonadPlusDist $\rightarrow$ MonadPlusCatch - false - [] is a known counter-example.
MonadPlusCatch $\rightarrow$ MonadPlusDist - false - Maybe is a known counter-example.


texts: Awards, grants and fellowships for PhD students in TCS

texts:
I think that a PhD student that received some awards and fellowships has better chance to get a good postdoc position. I was wondering what awards/grants/fellowships should one consider to apply for?

Here are three that I know of:

Microsoft Research
IBM
Simons Foundation. Although this one seems obsolete.

I'm mostly interested in grants and awards in the US, but I think it's good to have an international list here too.


texts: Sampling distinct values with probability proportional to their frequency

texts:
This is a variant of my previous question (Reservoir sampling of distinct values)

I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass through the data is possible.

In my case, the stream contains many duplicate values, and I need to make sure that my sample set won't include any duplicate values. It is important to note the the number of distinct values in the stream is huge as well (to big to fit memory).

I need to make sure that the probability of any value being sampled is proportional (or about proportional) to its frequency in the stream.

Is there any way to achieve this?


texts: Hamiltonian cycle on graphs without small cycles

texts:
While answering this question on cstheory, I (informally) proved on the fly the following theorem:

Theorem: For any fixed $l \geq 3$ the Hamiltonian cycle probem remains NP-complete even if restricted to planar bipartite undirected graphs of maximum degree 3 that don't contain cycles of length $\leq l$.

It seems very unlikely that it has not already appeared somewhere.
But it allows to settle many Hamiltonian cycle/path problems on graphclasses.org that are marked as "Unknown to ISGCI" (see for example this one); indeed a direct corollary is that Hamiltonian cycle and path problems are still NP-complete if restricted to $(H_1,...,H_k)\text{-free}$ graphs, where each of the $H_i$ contains at least one cycle.

  Can you give me a reference of the paper/book where it appeared?

(then I'll contact people at graphclasses.org)


texts:
Where can I find graphs relevant to real-life problems?

Two repositories I know of are:

University of Florida's Sparse Matrix Collection
Bodlaender's TreewidthLib


texts: How hard is this combinatorial optimisation problem?

texts:
Suppose we have multiple intervals $R_1,R_2,...,R_i$ of non-negative integers. These intervals may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th interval $R_h$, and $x_R$ to denote the interval that the integer $x$ comes from. It is possible that two integers $x$ and $y$ are equal but they come from different intervals (i.e., $x=y$ but $x_R\neq y_R$).
Suppose we have a threshold $T$, a positive integer $N$, and a function $f(x)$ whose input is an integer $x$ and it is defined as: $f(x)=x$, if $x \leq N$. $f(x)=max(0,2N-x)$, if $x>N$.
I want to choose integers from intervals $R_1,R_2,...,R_i$ to maximise the cumulative scores $f()$ without exceeding the threshold $T$.
There are two constraints

Chosen integers must come from different intervals

Given two chosen integers $x$ and $y$, if $x_R(\mathrm{median}) \leq y_R(\mathrm{median})$, then
$$
\frac{x_R(\mathrm{median})}{x} \leq \frac{y_R(\mathrm{median})}{y}.
$$

The objective is maximising the following:
$$
\sum_{x \in R_1,R_2,...,R_i} p_x f(x)
$$
subject to:

$p_x=\{0,1\}$,
$\sum_{x \in R_1,R_2,...,R_i} xp_x \leq T$,
$\forall (x, y)$, if $p_x=p_y=1$, then $x_R \neq y_R$,
$\forall (x, y)$, if $p_x=p_y=1$ and $x_R(\mathrm{median}) \leq
    y_R(\mathrm{median})$, then  $$ \frac{x_R(\mathrm{median})}{x} \leq
    \frac{y_R(\mathrm{median})}{y}. $$

I have proved that this problem is weakly NP-hard by reduction from knapsack problem when each range contains exactly one integer. But I think the my problem should not be just weakly NP-hard. I know this problem can be reduced to the Knapsack Problem with conflict graphs, but not vice versa. Is it possible to perform reduction from existing strongly NP-hard problems to the one described above?


texts: Tail bounds for sum of weighted Poisson random variables

texts: Let $X_1,X_2,\ldots,X_n$ be $n$ independent Poisson random variables with $\mu(X_i) = \lambda_i$. I am interested in upper tail bounds for the random variable $Z = \sum_{i} a_i X_i$ where $a_i \in [0,1]$ for $1\le i \le n$. For instance if each $a_i =  1$ then $Z$ is simply a Poisson rv with mean $\sum_i \lambda_i$ and one would get tail inequalities such as the one I found in a note here. For the general weighted case Chernoff style tail bounds should apply but I am not finding an easy reference. Any help would be appreciated.


texts: A approximation version of the Goldreich-Levin Theorem

texts:
A little introduction
The Goldreich-Levin Theorem says that

let $f$ a one-way function and set $f'(x,r)=(f(x),r)$ where $|r|=|x|$ then $\langle x, r \rangle = \sum_{i}x_ir_i \mod 2$ is an hard-core predicate of the function $f'$.

With hardcore predicate we mean that if there exists a algorithm $D$ that given $f(x),r$ can predict the value $\langle x, r \rangle$ with probability at least $1/2+\epsilon$ then there exists a inverter algorithm $I$ that with probability $O(\epsilon)$ inverts the fuction $f'$ (using $D$ as subrutine).
From my point of view this is an amazing result in TCS that use simple probabilistic arguments in a really elegant way. Furthermore it's a very good tool for many applications!
For example,the theorem can be rephrased as a coding theory task.
(In the hadamard code we code the message $m \in \{0,1\}^n$ with a codeword $c \in \{0,1\}^{2^n}$ where $c_i= \langle x, \bar{i} \rangle$ and $\bar{i}$ is a binary rappresentation of the number $i$.)
Let $C = Enc(m)\in \{0,1\}^N$ a codeword of hadamard code, we send $C$ over a noise channel and then the receiver obtains $D= C + Error$. If the (normalized) distance between $D$ and $C$ is $1/2-1/p(\log N)$ for some polynomial $p$ then we can reconstruct the message $m$ only by looking few random location of $D$.
In this case $C$ is the binary rappresentation of the function $\langle m,\cdot \rangle$ , $D$ is the binary rappresentation of the predictor.
Goldreich,Rubinfeld and Sudan generalized the theorem: let $\mathbb{F}$ a field such that $|\mathbb{F}|=poly(n)$ and let $f: \mathbb{F}^n\rightarrow\mathbb{F}^m$ a one-way function define $f'(x,r)=(f(x),r)$ as above then $\langle x, r\rangle$ is a hard-core predicate of the fuction $f'$ where now all the operation are over $\mathbb{F}$.
This means that if $D$ is such that $$\Pr[D(f(x),r) = \langle x,r \rangle ] \geq 1/|\mathbb{F}|+p(n)$$ for some polynomial $p$ then we can invert the function $f'$ using $D$.
My question
Suppose there exists a function $D$ that, given $f(x)$, approximate $\langle x,\cdot \rangle$ with a additive factor $\delta$.

Given a algorithm $D$ such that $\forall r:|D(f(x),r)-\langle x,r \rangle| \leq \delta$ can we construct an Inverter for the function $f'$ from $D$?

A dummy example, suppose there exists $D$ such that, given $f(x)$, it calculates the function $\langle x,\cdot \rangle+1$, obviusly the probability that $D$ predicts $f'$ is 0 but it seem simple to invert the fuction $f'$ given $D$. However in the approximation setting we don't assume that for all input we can know the approximation factor.


texts:
What is the time complexity (not query complexity) of Grover's algorithm?  It seems clear to me that it is $\Omega(\log(N) \sqrt{N})$ since there are $\Omega(\sqrt{N})$ iterations and each iteration requires use of the reflection operation which in turn takes time $\Omega(\log(N))$ using any standard set of universal gates.

The problem is, I can't find even a single reference which says the time complexity of Grover's algorithm is $\Omega(\log(N) \sqrt{N})$.  Wikipedia, and several other web pages, say $O(\sqrt{N})$ time complexity.  Grover's paper claims $O(\sqrt{N})$ "steps".

Am I missing something?  Perhaps people define the reflection operation to take unit time.  But that doesn't make sense to me because if we can play the game of allowing arbitrary unitaries to take unit time then there would be no difference between query complexity and time complexity.


texts: What is the recognition complexity of k-uniform k-partite hypergraphs?

texts:
We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied.
It's also in P, right? What about larger $k$?


texts: Lower bound for orienting an asynchronous ring?

texts:
We require a lower message complexity bound of an asynchronous distributed algorithm that do the following:
Given a undirected ring, with $n$ vertices, we want to let each node direct its edges to form a directed cycle in the ring.

That is: if our ring is : a-b-c-d-a ---> then we want our result to be a->b->c->d->a

Note that the nodes in the ring do not have a common definition of left and right .. that is, the left of node a may be the right of node b etc .. (this is why the problem is difficult)

I think that the lower bound is $\Omega(n\log n)$ - similar to the election problem. But I cannot prove it until now.
I was trying to prove it by contradiction with other known lower bounds. That is, if we can solve this problem, then we can solve problem A with a complexity lower than its known lower bound. I tried it with the election problem, it did not work obviously.
Any suggestions ?


texts: Direct Proof that the Pigeonhole Principle is Hard for Regular Resolution

texts:
It is well known that the pigeonhole principle $PHP_n^{n+1}$ is hard for general resolution. The original proof due to Haken is elegant. One first defines a complexity measure for derived clauses, in which axioms have low complexity, and the final empty clause has high complexity. Then one shows that clauses of medium complexity must have many literals. Finally, one shows that if $\Pi$ is a refutation of small size, then one can restrict the values of some variables in such a way that the resulting formula $PHP_{n-k}^{n-k+1}$ has a corresponding refutation $\Pi'$ of width smaller than what it should be. Contradiction.

Regular resolution is the special case of resolution where variables are not allowed to be resolved more than once in any path from an axiom to the final empty clause. It is well known that regular resolution refutations are essentially read-once branching programs.

Is there a well known way of proving that $PHP_n^{n+1}$ is hard for regular resolution directly, without using Haken's arguments? I would imagine that since regular resolution proofs correspond to read-once branching programs, one could actually use a more direct approach based on rectangle covers and so on. Is this intuition right? Are there any discussions of this technique in the literature?

Ps: I'm aware of a paper due to Pitassi and Raz, which shows that the weak pigeonhole principle is hard for regular resolution. But now this proof is probably much more complicated than a proof for the original $PHP_n^{n+1}$ tautologies due to the weak modification.


texts: Finding all solutions by Grover search(not superposition)

texts:
When there are multiple marked elements, grover search provides only superposition of them. If I want to find all the marked elements, not superposition, I could try this:

1) Do Grover search, get superposition of t marked element,

2) observe ele space, get one marked element,

3) remove that element,

4) goto 1)

This takes time step $O(\sqrt{\frac{N}{t}}+\sqrt{\frac{N-1}{t-1}}+\dots+\sqrt{\frac{N-t+1}{1}})$.

My question is, can i do better?


texts: A reduction between small cliques problems

texts:
I'm looking for a reduction that gets a graph $G=(V_G,E_G)$ and outputs a graph $H$ that satisfies the following requirements.

If $G$ contains a triangle, then $H$ contains a clique of size 9.
If $G$ contains no triangles, then $\mathrm{maxclique}(H) \leq 4$.
The reduction runs in time $O(|G|) = O(|V_G|+|E_G|)$.

A simple attempt would be to take $H=G\boxtimes K_3$, that is the strong direct product of $G$ with $K_3$. This will give 9-vs-6, and not the required 9-vs-4.

Another attempt would be to try taking $H=G\boxtimes G$ to be the strong direct product of $G$ with itself. This satisfies the first two requirements, but the running time is quadratic. On the other hand, this construction gives something stronger, namely, if $\mathrm{maxclique}(G)=k$, then $\mathrm{maxclique}(H) = k^2$ regardless of the value of $k$. So maybe there is hope to change this product so that it works only for $k=2,3$ in linear time.

Remark 1: Note that we don't expect to have a linear time algorithm for finding a triangle, so I want a "real" reduction, and not an algorithm that looks for triangles in $G$.

Remark 2: Alternatively, I'd be happy with an explanation why such reduction is unlikely to exist (e.g., because the 9-vs-4 problem can be solved in linear time).


texts: Clarification: Are runtime bounds in P decidable?

texts:
In Emanuele Viola's much upvoted answer to the question, "Are runtime bounds in P decidable?" he uses the following proof:

The problem is undecidable. Specifically, you can reduce the halting problem to it as follows. Given an instance $(M,x)$ of the halting problem, construct a new machine $M'$ that works as follows: on inputs of length $n$, it simulates $M$ on $x$ for $n$ steps. If $M$ accepts, loop for $n^2$ steps and stop; otherwise loop for $n^3$ steps and stop.
If $M$ halts on $x$ it does so in $t=O(1)$ steps, so the run time of $M'$ would be $O(n^2)$. If $M$ never halts then the run time of $M'$ is at least $n^3$.
Hence you can decide if $M$ accepts $x$ by deciding if the run time of $M'$ is $O(n^2)$ or $O(n^3)$.

I have a significant problem with this proof, but as it is well accepted by theoreticians much smarter than me I am sure that I must be misunderstanding.
Here is my issue:

$M'$ simulates $M$ on $x$ for $n$ steps.

If $M$ accepts, then $M$ certainly halts on $x$. However, if $M$ does not accept, this does not mean that $M$ does not halt on $x$; it only means that $M$ does not halt on $x$ in the first $n$ steps. In a comment, Emanuele clarifies that $M$ and $x$ are selected independently of $n$; however, this does not negate the fact that $M$ is only simulated on $x$ for $n$ steps.
So either this is a reduction from, "Does $(M,x)$ halt in $n$ steps?" which is a decidable problem, or I am missing some major component of this proof. Could someone please clarify?


texts:
The PCP theorem (NP= PCP(log n, O(1)) )is a major result in complexity theory with many applications such as proving hardness of approximate results. However, it seems to me that it does not offer any insight that leads to separating P from NP or NP from coNP. My intuition is that P=NP would imply that coNP = PCP( log n, O(1)). That means Tautology instance has a proof that can be verified by an efficient probabilistic verifier using logarithmic random bits and reading only constant number of bits from a proposed proof. It seems that PCP theorem can not shed a light on why Tautology can not have such proof system.

  Why is the PCP characterization of NP not helpful in separating NP from coNP ( or from P)? Is there any known barrier?

** EDIT**: Provided context and motivation.


texts: Algorithm for testing if a point belongs to a sequence of convex set or not

texts:
I have a sequence of convex sets $C_\lambda$ for $\lambda \in \mathbb{R}$ such that for $\lambda_1 > \lambda_2$, we have $C_{\lambda_1} \subset C_{\lambda_2}$ (essentially a nested sequence of convex sets in $d$ dimensions). For a given point $x \in \mathbb{R}^d$, define:
\begin{align*}
f(x) = \sup \{ \lambda: x \in C_{\lambda} \}
\end{align*}

Is there an efficient algorithm for computing $f(x)$ given $x$.


texts: Find Shortest Pairwise Distance of Points in o(n log n)?

texts:
The following exercise has been handed out to students I supervise:

  Given $n$ points in the plane, devise an algorithm that finds a pair of points which distance is minimal among all pairs of points. The algorithm should run in time $o(n^2)$.

There is a (relatively) simple divide and conquer algorithm that solves the task in time $\Theta(n \log n)$.

Question 1: Is there an algorithm that solves the given problem exactly in worst-case time $\mathcal{o}(n \log n)$?

What made me suspect  that this might be possible is a result I remember to have seen in some talk (reference appreciated). It stated something along the lines of that not more than a constant number $c \in \mathbb{N}$ of points can be arranged in the plane around some point $p$ inside a circle of radius $r \in \mathbb{R}$, with $r$ the minimal distance between any two of the involved points. I think $c=7$, the points forming a equilateral hexagon with $p$ in the center (in the extreme case).

In that case, the following algorithm should solve them problem in $n$ steps.

fun mindist [] | p::[] = INFINITY
|   mindist p1::p1::[] = dist(P[0], P[1])
|   mindist p::r = let m = mindist(r) in
                     min(m, nextNeighbour(p, r, m))
                   end

Note that this is (claimed to be) in linear time because only a constant number of points in r can be no farer away than m from p (assuming above statement); only these points have to be investigated for finding a new minimum. There is a catch, of course; how do you implement nextNeighbour (maybe with preprocessing in linear time)?

Question 2: Let a set of points $R$ and a point $p \notin R$. Let $m \in \mathbb{R}$ with

$\qquad m \leq \min\{\mathrm{dist}(p_1, p_2) \mid p_1, p_2 \in R\}$

and

$\qquad R_{p,m} := \{p' \mid p' \in R \wedge \mathrm{dist}(p, p') \leq m\}$.

Assume $R_{p,m}$ is finite. Is it possible to find $p' \in R_{p,m}$ with minimal distance from $p$ in (amortised) time $\mathcal{O}(1)$? (You may assume $R$ to be constructed by adding investigated points $p$ one by one.)


texts: NP completeness of classes of spanning trees

texts:
I am teaching a complexity course, and I want to give some examples of similar looking problems such that one is in P, and the other is NP complete.

This made me think of the following problem: does a given graph contain a spanning tree with a given degree sequence? This is obviously easy for the sequence $n-1,1,...,1$ and hard for $2,...,2,1,1$.  Is there a general answer?


texts: How to approach the "traveling salesman problem" with cost changing every time salesman reaches a new city

texts:
Let's say instead of finding the shortest path we have to maximize the profit in a year of the salesman under the following constraints.

Salesman can go to a different city only on weekends, all weekdays of a week he will sell in the same city
The salesman has limited fuel, so he can visit only cities which are in 300(or any other constant) mile radius
Every time a salesman travels to a different city he gets new prices for each city for his inventory based on demand and supply in each city. For simplicity, you can assume you have prices for each city for each week are pre-decided. i.e. you have Nx52 matrix where N is the number of cities. The more the price the more will be the profit.

To simplify further we can assume a Graph(G) will contain N nodes and each node will point to all cities within a 300-mile radius.

class GraphNode:
    def __init__(self, locID, prices, close_locations)
        self.locID = locID
        self.prices = prices #List of prices in 52 weeks
        self.close_locations = close_locations #List of locations in 300 mile radius

How to approach this problem. I could not find any resources to get started to solve this.
Here is a similar kind of question but this is as far I could find a similarity:
https://stackoverflow.com/questions/24396976/what-is-the-name-for-this-special-case-of-the-travelling-salesman-involving-dyna


texts: Learning function with a few low-order Fourier coefficients, from uniformly random samples

texts:
Let $f:\{-1,+1\}^n \to \{-1,+1\}$ be a boolean function where all of the energy of the Fourier transform of $f$ is concentrated in a small number of low-order coefficients, say $k$ coefficients each having degree at most $d$.  Can we efficiently learn $f$ given samples of the value of $f$ on uniformly random inputs?

In other words, $f$ has the form

$$f(x) = \sum_{i=1}^k \alpha_i g_i(x),$$

where each $g_i$ is a low-order square-free monomial: $g_i(x) = \prod_{j \in S_i} x_j$ for some set $S_i$ of size at most $d$, where $\sum \alpha_i^2 = 1$.  Also assume that each $\alpha_i$ is either zero or bounded away from zero.  Crucially, I'm interested in the case where $k$ is small.

Is there a way to learn $f$ given the value of $f$ on many random inputs?  We are given $(x_1,y_1),\dots,(x_m,y_m)$ where each $x_i$ is drawn uniformly at random from $\{-1,+1\}^n$ and $y_i = f(x_i)$.  I'd like to approximately learn $f$ from these values.  One approach is to enumerate all ${n\choose 0} + \cdots + {n \choose d} = \Theta(n^d)$ possibilities for $g$, and estimate the Fourier coefficient for each by computing the average of $g(x_i) \cdot y_i$ over all samples.  However, this requires enumerating $\Theta(n^d)$ choices of $g$, even if $k$ is much smaller than $\Theta(n^d)$.

Is there a method faster than estimating all $\Theta(n^d)$ low-order Fourier coefficients, when $k$ is small?


texts: Consequences of bipartite perfect matching not in NL?

texts:
Are any significant consequences known of $\text{BPM} \not\in \textsf{NL}$?

I'm interested in the status of the following well-studied decision problem, in particular whether it is known to be in $\textsf{NL}$:

  Bipartite Perfect Matching (BPM)
  Input: bipartite $2n$-vertex graph $G$
  Question: does $G$ contain a matching with $n$ edges?

Maximum Bipartite Matching is the version where the required size of a matching is given as part of the input.
By Chandra-Stockmeyer-Vishkin, this is equivalent to BPM via $\textsf{AC}^0$-reductions, and these problems are hard for $\textsf{NL}$ via $\textsf{AC}^0$-reductions.

Recall the following sequence of inclusions (see the Zoo):
$$\textsf{L} \subseteq \textsf{UL} \subseteq \textsf{NL} \subseteq \textsf{NC}^2 \subseteq \textsf{RNC}^2.$$

Looking at a more general problem, maximum matching for general graphs is in $\textsf{RNC}^2$, by Mulmuley-Vazirani-Vazirani (preprint), and according to Allender-Reinhardt-Zhou this problem was (in 1999) not known to be in NL.
The latter paper also shows that BPM is in a nonuniform version of $\textsf{SPL}$, but $\textsf{SPL}$ is not known to be comparable to $\textsf{NL}$.
(The Zoo also claims that BPM is in $\textsf{coRNC}$ by Karloff, although it is not obvious to me how this follows from the results in Karloff's paper.)

All of the usual approaches to finding a maximum bipartite matching are polynomial-time.
Moreover, these algorithms have polynomial time bounds of quite low degree.
In particular, an $O(n^{2.5})$ time upper bound follows from the reduction of Hopcroft-Karp and Karzanov to maximum flow.
So it is not impossible that BPM (and perhaps even maximum matching) is in $\textsf{NL}$.

However, all the approaches I've looked at seem to be rather space-intensive.
The usual algorithms essentially keep track of subsets of the vertices, and therefore seem to require something like $\Omega(n)$ bits (although proving such a bound rigorously seems likely to be difficult).

Looking at a more specific problem, if the input graphs are further restricted to be planar as well as bipartite, then Planar BPM is in $\textsf{UL}$ and hence $\textsf{NL}$, by Datta-Gopalan-Kulkarni-Tewari.

So BPM is $\textsf{NL}$-hard, but is in some complexity classes "not much larger than" $\textsf{NL}$, and is in $\textsf{NL}$ for restricted classes of bipartite graphs.
It therefore seems reasonable to ask: if $\text{BPM} \not\in\textsf{NL}$, would anything interesting follow?


texts: Are there interesting graph classes where the treewidth is hard (easy) to compute?

texts:
Treewith is an important graph parameter that indicates how close a graph is from being a tree (although not in a strict topological sense).

It is well known that computing the treewidth is NP-hard.

  Are there any natural classes of graphs where the treewidth is hard to compute?

Similarly:

  Are there interesting graph classes where the computation of the treewidth is easy? If yes, is there any structural property/test that can be exploited? I.e., Graph $G$ has property $X$ $\Rightarrow$ computing the treewidth of $G \in \mathbf{P}$.


texts:
While studying a problem in algorithmic game theory I got interested
in the complexity of the following optimization question:
Problem
Given:

ground set $U = [n] = \{1,\ldots,n\}$ given by $n$,
$m$ rankings given as total orders $\langle S_i, \sigma_i \rangle$
where $S_i \subseteq U$ ($1 \leq i \leq m$),
weight vector for $U$ given by $w \in \mathbb{R}^n$.

Goal:
find a subset $L \subseteq U$ maximizing the following sum:
$$r(L) = \sum_{i \in [m],\  S_i \cap L \neq \emptyset} w(t_i(L))$$
where $t_i(L)$ is the highest ranked item in $L\cap S_i$ according to
$\sigma_i$.
I suspect that the problem is $\mathsf{NP}$-hard. In fact the problem
seems to be hard even when all the $S_i$'s are of size $2$. However I
haven't been able to prove this.
What I know
It easy to see that the following restrictions make the problem easy:

all of the weights are uniform: selecting all of the elements is
clearly optimal.
all of the rankings are complete rankings over $U$: the best
solution is obtained by taking the element with the maximal weight.
the weights are just binary ($w \in \{0,1\}^n$), then selecting all
of the $1$-weighing elements is optimal.

However I haven't been able to find a polynomial time algorithm for
the general case (for example using LP).
On the other hand proving the problem to be $\mathsf{NP}$-hard doesn't
look easy. The structure of the problem instances doesn't allow easy
encoding of other problems. (Note that the hardness of the problem
will come from using the same $L$ for all partial orders, however
using the same weight vector for all of them makes proving hardness
not straight forward). I have unsuccessfully tried reducing some
$\mathsf{NP}$-hard problems like Subset-Sum, NAND-Circuit-SAT, etc. to
the decision version of this problem (is there a subset such that
$r(L) \geq k$).
A matching IP can be constructed quiet easily for a given instance of
the problem, but I don't see any sufficient resemblance to any problem
that I know of.
Question
Do you know the complexity of this problem?
Are there any references studying the complexity of similar optimization problems?
How would you prove that this optimization problem is $\mathsf{NP}$-hard? (if it is indeed hard).


texts: Initial paper of the Moore Neighborhood algorithm

texts: I don't exactly know if this is the place to ask it, but I'm looking for the original paper of the Moore Neighborhood algorithm. I need to make a reference to it (or whoever came up with it). I can't seem to find the origin, just other people using it. Does anyone have an idea what I need to cite for this ?


texts: Interactive proofs for levels of the polynomial hierarchy

texts:
We know that if you have a PSPACE machine, it's powerful enough to give an interactive proof of any level the polynomial hierarchy. (And if I remember right, all you need is #P.) But suppose you want to give an interactive proof of membership in a $\Sigma_2$ language. Is it enough to be able to solve problems in $\Sigma_2$? Is solving problems in $\Sigma_5$ adequate? More generally, if you can solve $\Sigma_k$ or $\Pi_k$ problems, for what $\Sigma_\ell$ is this sufficient to generate interactive proofs of all languates in $\Sigma_\ell$?

This question was inspired by this cstheory stackexchange question.


texts: Nontrivial problems solvable in constant time?

texts:
Constant time is the absolute low end of time complexity. One may wonder: is there anything nontrivial that can be computed in constant time? If we stick to the Turing machine model, then not much can be done, since the answer can only depend on a constant length initial segment of the input, as farther parts of the input cannot even be reached in constant time.

On the other hand, if we adopt the somewhat more powerful (and more realistic) unit-cost RAM model, in which elementary operations on $O(\log n)$-bit numbers are counted as single steps, then we may be able to solve nontrivial tasks, even in constant time. Here is an example:

  Instance: Integers $n, k, l, d$, each given in binary format by $O(\log n)$ bits.

  Question: Does there exist an $n$-vertex graph, such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$?

Note that from the definition it is not even obvious that the problem is in NP. The reason is that the natural witness (the graph) may need $\Omega(n^2)$-bit long description, while the input is given by only $O(\log n)$ bits. On the other hand, the following theorem (see  Extremal Graph Theory  by B. Bollobas) comes to the rescue.

  Theorem:  Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree  $d$, if and only if one of the following conditions is satisfied:
    $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$,
   $1\leq 2d+2-n\leq k\leq l = d< n-1$
   $k=l=d=n-1.$

Since these conditions can be checked in constant time (in the unit-cost RAM model), the Theorem leads to a constant time algorithm in this model.

Question: What are some other nontrivial examples of constant time algorithms?


texts: Applications of computer science in biology

texts:
Is there a survey or tutorial article which talks about application of theoretical computer science to emerging fields of applications of computer science in biology, bioinformatics and nanotechnology?

Are there any problems from these fields that are unsolved and are of intrinsic merit to theoretical computer science?

Are there any algorithms that are already useful or potentially useful in current or future real-world applications and products in these fields? Is there any article which talks about real-world applications and products?


texts: I am studying the complexity of Portal 2 and I would like to know if the problem has been studied before. In particular, I would be interested any reference discussing the complexity of Portal 2 and it being NP-hard/PSPACE-hard and approaches to prove such results.


texts:
I'm trying to find any material on this problem. It extends the Asymmetric Travelling Salesman Problem (ATSP) in that it requires for some destinations that they are approached in the specified direction (but not for all). I couldn't find anything about this problem on the internet. Can anybody point me to some paper or the correct name for this problem? Or maybe similar problem from graph theory?

UPDATE

In my current design each node has a property of direction in which it is being approached. This direction can be restricted or unrestricted. When unrestricted, then I think all possible combinations of directions should be tried to the combination which minimizes the cost function.
Also I have 4 distance matrices corresponding to different direction combinations: 0-0, 0-1, 1-0 and 1-1. Where 0 is positive direction and 1 is negative direction.

UPDATE 2

The calculations are performed on a real street network data. Direction mean street direction (or side of the street). Each point on the street can be aproached from two different directions. Some points are restricted to be approached in a particular direction, some are not.


texts:
let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is

$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$
where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges between S and $\bar{S}$.
Expansion of graph G is
$$\alpha(G)=\min_{\emptyset\neq S\subsetneq {V}}\alpha(S)$$
Sparsity $\mathcal S_G$ of graph G is
$$\mathcal S_G=\min_{\emptyset\neq S\subsetneq {V}}\frac{|E(S,\overline S)|}{|S||\overline S|} $$
It is easy to see, that
$$\frac{n}{2} \mathcal{S}_G\leq \alpha(G) \leq (n-1)\mathcal{S}_G$$
where $n=|V|$.
Solution for Expansion Problem is to find set $S\subsetneq V$ such that $\alpha(S)=\alpha(G)$
Solution for Uniform Sparsest Cut Problem is to find set $S\subsetneq V$ such that
$$\frac{|E(S,\overline S)|}{|S||\overline S|}=\mathcal S_G$$.
My question is, is there a graph for which there are different solution for Expansion Problem and for Uniform Sparsest Cut Problem?
Thank you for any ideas ..


texts: How many minimal $k$-cycles can you put in a graph?

texts:
I wish to construct an unweighted, undirected graph on $n$ nodes that maximizes the number of minimal cycles of size $\ge k$.  What is known about this problem?  How many cycles can I squeeze in?

Additionally, how does the problem change if I require that my graph has $\ge m$ edges?

Clarification: I care purely about the existence of a many-cycled graph; it doesn't need to be efficiently constructable.


texts: A question regarding Improved Algorithm for Degree Bounded Survivable Network Design Problem

texts:
In the paper "Improved Algorithm for Degree Bounded Survivable Network Design Problem", by N. Vishnoi and A Louis,  have used the iterated rounding approach in a similar as by Jain in designing the approximation algorithm for the steiner network and recently by Mohit Singh et al for the degree bounded case steiner network. The paper improves on the result by Mohit Singh and may however be not optimal.

My query is very specific to the paper i have referred above:

1) In the proof of the main lemma: base case where we have a tight vertex $v$. If we say that degree of vertex $v$ is at least $4$, then it seems to me that the arguments still hold as follows. If there are no heavy edge then everything is good. In case we have a heavy edge e which the paper considers, then since $x_e$ is strictly less than $1$, we again will have at least $4$ other edges(including one light edge) and can get $4$ tokens.

I am interpreting that a tight vertex of degree $4$ has to have edges incident on it whose sum of $x_e$ is $4$.

2) In the induction part, the fact used is that we are maintaining $b(v)$ greater than or equal to $3/2$. Where else are we using this fact? Why cant be $2$ if we are not using anywhere else. (and accordingly changing the algorithm)

I am quite new to approximation algorithm and particularly to this technique. In order to find the underlying hardness, i was playing with the proof and ended up with above 2 things. I am sorry for the fact that the question is heavily dependent on the paper (both the context and notations). Any other suggestion or comment is appreciated.


texts: Would a proof assuming a physical law be considered sufficient?

texts:
I've always wondered if proofs in computer science would be considered sufficient proofs of the proposition if they needed to assume physical laws?
For example, I'm wondering what would happen if someone someday proved P != NP under the assumption of the second law of thermodynamics. Would this settle the debate of P != NP?
Or would the problem be still considered unsolved if it rests on physical assumptions?


texts: Showing hardness of maximizing stochastic objective function over graph

texts:
Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$.

The challenge is to assign weights $w_e$ to each edge to maximize the
objective function $E = \sum_{e = \{i,j\}} w_e \Pr[X_i + X_j \geq w_e]$ where $\Pr[X_i + X_j \geq w_e]$ denotes the probability that that the sum of values taken by vertex $i$ and $j$ is greater than $w_e$. This is linear time to solve since there are only $3$ candidate values for $w_e$ which are $a_i, a_j, a_i + a_j$, so I can pick the one that maximizes $w_e \Pr[X_i + X_j \geq w_e]$ for each edge.

The additional constraint is that the weights $w_e$ need to be sub-additive, i.e., for any two edges $e'$ and $e''$ that "cover" edge $e$ meaning $e'$ and $e''$ include the vertices that make $e$, it holds that $w_e \leq w_{e'} + w_{e''}$.

Observe that the deterministic version of this stochastic problem where $p_i = 1$ is trivial since then I can just assign $w_e = a_i + a_j$ and the sub-additivity constraint is free since the function assigning the weights is exactly additive.

I strongly believe that this problem is NP-Hard (or #P-Hard?). I can show that for some special graphs like path graphs where each edge has degree at most $2$, this can be done in polynomial time because the number of sub-additive constraints is linear in the size of the graph but in general, even if there was an oracle that tells me the set of edges that participate in the optimal solution, there would be exponential constraints in the linear program that finds the optimal weights. It is also easy to solve if $p_i = p$ for each vertex $i$. Any pointers on potential approaches to show the hardness (or PTIME) would be greatly appreciated!

Edit : For people interested in the background of the problem, this is related to database query execution. Each vertex is a view that is materialized and each edge represents a query that can be answered using two views. The $w_e$ and $a_i$ are set up to represent the cost vs benefit of materializing the view to speed up query execution.

Edit 2 : I have realized a mistake in my supposed "proof" for path graphs of degree 2. I will ask that as a separate question and link this post there in order to leave the general problem.


texts: Advantages and specific applications of massively parallel programming thesis idea

texts:
I'm nearly graduated in computer science engineering and my thesis should discuss the massively parallel computational model of CUDA and its advantages/applications.

I'm searching for an application field (an idea) to show off some of CUDA capabilities and (definitely) also my skills as programmer and engineer.

I'm up for a bit of challenge to integrate an interesting work into my thesis project and discussion so I'm asking for advices or ideas


texts: Fast extraction of the edges of an induced subgraph

texts:
Let $G = (V, E)$ be an arbitrary undirected graph and $W \subseteq V$ a subset of its vertices. What is the complexity of the best algorithms for obtaining the edges $F$ of the induced subgraph $H = (W, F)$?

We can iterate over all the pairs of vertices taken from $W$ and test whether they're in $E$ using a hash table. This has a complexity of $O(|W|^2)$.

Another algorithm is to iterate over all the neighbors of all the vertices in $W$, and keep the pairs that are in $W\times W$. If the average number of neighbors is $d$, the complexity of this algorithm is $O(|W|d)$.

Can we do better than either $O(|W|^2)$ or $O(|W|d)$?


texts:
In the paper Fast LTL to Buchi Automata Translation (2001, Gastin and Oddoux)  the authors, while defining co-Buchi alternating automata define  $\Sigma’= 2^\Sigma$ where $\Sigma$ is the alphabet.
They say that because of this the transitions that differ only by action can be gathered.

What does this statement exactly mean? Any pointers will be helpful.

thanks


texts: Different definitions of optimal decompressors

texts:
Let $B^{<\omega}$ be the set of finite binary strings. I will only consider functions from $B^{<\omega}$ to $B^{<\omega}$.

I recall the definition of the algorithmic complexity of a string relative to a partial recursive function $F$:
$C_{F}\left(x\right)=\min\left\{ \left|y\right|\in B^{<\omega}\mid F\left(y\right)=x\right\} $.

In algorithmic complexity theory, we often use what is called an optimal decompressor. An optimal decompressor is a partial recursive function $U$ from $B^{<\omega}$ to $B^{<\omega}$ which verifies « For any partial recursive function F, $C_{U}\left(F\left(x\right)\right)\leq\left|x\right|+O\left(1\right)$ ».

Now, this is purely an information-related concept, and it tells us nothing about whether $U$ can be seen as a usable « programming language ». We can define a stronger concept: an effectively optimal decompressor is a partial recursive function $U$ such as we can find a recursive and length-preserving translation from any other partial recursive function into $U$. Formally, $U$ is a partial function such that for any partial recursive function $F$, there exists a total recursive function $h$ such as $U\left(h\left(x\right)\right)=F\left(x\right)$ for all $x$, and such that $\left|h\left(x\right)\right|\leq\left|x\right|+O\left(1\right)$.

It is easy to show that those two definitions are not equivalent. But one of my colleagues asked the question: what if, in the definition of effective optimality, we only ask that $h$ verifies « If $F(x)$ is defined, then $U(h(x))=F(x)$ »? In other terms, what if we allow $h$ to output a program which halts when the input is a program which doesn't halt? Note that $h$ still has to be a total recursive function. It gives a definition which is stronger than the first definition (non-effective optimality), but I can't prove that it is equivalent, or strictly weaker, than the second definition.

It sounds like a question which is too simple not to have an easy answer, but I've been stuck on it for the last few days. If someone has an idea, I'm all ears =)

Thank you in advance!


texts:
Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix?

This question is motivated by this problem:
Positive topological ordering

The original decision problem is at least as hard as this one, so an NP-completeness result would solve that too.

Edit:
Laszlo Vegh and Andras Frank called my attention to an equivalent problem asked by Gunter Rote:
http://lemon.cs.elte.hu/egres/open/Graphs_extendable_to_a_uniquely_matchable_bipartite_graph

Edit:
The reduction to the original problem is as follows. Suppose that the DAG has only two levels, these will correspond to the rows and columns of the matrix. Also, we have one single node with weight +1. Everyone else in the lower level has weight -1 and on the upper level +1.


texts: Does it make sense to consider a category of all NP-complete problems, with morphisms as poly-time reductions between different instances? Has anyone ever published a paper about this, and if so, where can I find it?


texts: Functions that are Not Efficiently Computable but Learnable

texts:
We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable") can be expressed by polynomial neural networks with reasonable sizes, and thus can be learned with polynomial sample complexity ("learnable") under any input distributions.

Here "learnable" only concerns the sample complexity, regardless of the computational complexity.

I am wondering about a very closely related problem: does there exist a function that can not be efficiently computed by Turing machine in polynomial time ("not efficiently computable"), but meanwhile, can be learned with polynomial sample complexity ("learnable") under any input distributions?

[1] Roi Livni, Shai Shalev-Shwartz, Ohad Shamir, "On the Computational Efficiency of Training Neural Networks", 2014


texts:
The recent establishment of the relation $bs(f)=O(s(f)^4)$ goes through Gotsman,Linial .

  Can the same approach get to $O(s(f)^2)$ or is there an essential limitation to the approach?


texts: A PAC-like analogue for 1-class classification?

texts:
This is more of a philosophical question -- I am looking for a reasonable mathematical formulation of 1-class learning.

In the PAC model, it's very natural to formulate our demand on the learner: produce a hypothesis with low generalization error.

What might be a reasonable formalization of 1-class learning? This may also be called "anomaly detection": in the training phase, the learner only gets to see positive ("normal") examples, but in the test phase he needs to predict whether a given new example is positive ("normal") or negative (an anomaly). The formal details are quite open-ended -- what's a reasonable assumption on the training sample (generated from some distribution, etc)? What's a reasonable success criterion?


texts: Borel-Cantelli Lemma and Derandomization

texts:
I was reading a paper titled Random Oracles with(out) Programmability. The last paragraph of section 2.3 reads:

  [Using our novel approach] there is no
  need to apply well-known classical asymptotic (and uniform) derandomization
  techniques based on the Borel-Cantelli lemma. To the best of our knowledge,
  this approach is novel to this paper.

I took a look at Wikipedia's entry for Borel–Cantelli lemma, and almost grasped the idea. However, I couldn't still figure out how it relates to derandomization. In addition, I don't understand the meaning of "asymptotic" and "uniform" in the aforementioned paragraph.

PS: Googling for Borel-Cantelli and derandomization will show several interesting results, but I don't have enough background to understand them well.


texts:
I would like to compute the treewidth of a graph. There are really good heuristics for other NP-hard graph problems such as VF2 for subgraph isomorphism, with code available in igraph for example.   I have tried them on my graphs and I find they run very fast for my data.

Are there any fast algorithms for treewidth calculation in a similar vein?


texts: Complexity of finding the most likely edge

texts:
Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes.
Now consider the following random process. First sample a uniformly random spanning tree of $G$ and then pick an edge from this spanning tree uniformly at random. Our process returns the edge.
There is a probability distribution on edges implied by this process.  https://math.stackexchange.com/a/3781031/678546 points out that if $T$ is a uniform sampled spanning tree then
$$P(e \in T) = \mathscr{R}(e_- \leftrightarrow e_+)$$
where $e = \{e_-, e_+\}$ and $\mathscr{R}(a \leftrightarrow b)$ is the effective resistance between $a$ and $b$ when each edge is given resistance $1$.
Marcus M goes on to give a complexity of $O(mn^3)$ for computing the probabilities for every edge.  This is much too slow to run in practice for all but the smallest graphs.
If I only want to find an edge with the maximal probability, is there a faster algorithm? How about if I am happy with an approximation?


texts:
Is there an extension or translation of Brent's theorem into asymptotics aside from big-$O$?

Brent's Theorem: source

Running time of a parallel algorithm with $p$ processors (say, $f(n,p)$), $W(n)$ Work complexity, and $S(n)$ Step complexity takes $\leq \frac{W(n)}{p} + S(n)$ time.  The $\leq$ lets me use $O$ directly, but not $\Omega$.  If it's also true, I'd be able to say something like:

$f(n,p) \in \frac{\Theta(W(n))}{p} + \Theta(S(n))$

It seems like it is true.  Is it?  I'd love to have a reference.


texts: Have the proofs in Buss's "On Goedel’s Theorems on Lengths of Proofs" been formalized (mechanically checked)?

texts:
The paper On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics contains quite interesting results on proof length. But some of the details are still, to me, a bit fuzzy [I now find a lot of non-formalized mathematics a bit fuzzy, an occupational hazard it seems].

There is a somewhat related thread on here, but it doesn't link to machine-checked formalizations.


texts: Functional abbreviation for Inst expression in Turing's 1936 paper

texts:
In Turing's 1936 paper "On Computable Numbers",
For a Turing Machine $M$, $Inst(q_i  S_j  S_k  L  q_l ) $ means that if $M$ scans symbol $S_j $ under $m-configuration$ $q_i$, then the symbol on the  square under scanner (with symbol $S_j $ ) is to be replaced by symbol $S_k$, and the scanner/header moves one unit $Left$, and its new $m-configuration$ becomes $q_l$.
If:
${R_S}_j(x,y)$ means "In the complete configuration $x$ (of $M$) the symbol on the square $y$ is $S_j$.
$I(x,y)$ means that "In the complete configuration $x$ (of $M$) the square $y$ is scanned".
${K_q}_m(x)$ means that "In the complete configuration $x$ (of $M$) the m-configuration is $q_m$".
$F(x,y)$ means that "$y$ is the immediate successor of $x$".
Then $Inst(q_i  S_j  S_k  L  q_l ) $ is to be an abbreviation for:

$(x,y,x',y')$ {
($ {R_S}_j(x,y) \,\&\, I(x,y)\,\&\, {K_q}_i(x) \,\&\,  F(x,x') \,\&\, F(y',y)) \to   $ $( I(x',y') \,\&\, {R_S}_k(x',y) \,\&\, {K_q}_l(x') \,\&\, F(y',z)  ∨  [(
 {R_S}_0(x,z) \to {R_S}_0(x',z))  \,\&\, ({R_S}_1(x,z) \to {R_S}_1(x',z))  \,\&\, ... \,\&\, ({R_S}_M(x,z) \to {R_S}_M(x',z))])$

$ S_0, S_1, ..., S_M $ being the symbols $M$ can print.
I am unable to convince myself of the exact correctness of the above formulae w.r.t. to the meaning of $Inst(q_i  S_j  S_k  L  q_l ) $. More specifically, why do we have the following expression included? What is he trying to "cover" by including it?

$ ... \,\&\, F(y',z) ∨ [({R_S}_0(x,z) \to {R_S}_0(x',z))  \,\&\, ({R_S}_1(x,z) \to {R_S}_1(x',z))  \,\&\, ... \,\&\, ({R_S}_M(x,z) \to {R_S}_M(x',z))] $


texts: Gate definitions for quantum random access codes

texts:
I would like to know how the gates are defined in quantum random access codes? Consider the $2 \to 1$ code described in Lemma 3.1 of this paper.
The section defines the encoding and decoding circuits. But it is not clear to me how to define gates. Say, I want to apply an $Rz(\theta)$ on the first qubit or a CNOT gate on both qubits.
I was able to make some progress. For single qubit gates, applying it directly means applying on the first encoded qubit. To apply it on the second qubit, you have to conjugate it with the H gate. I am still not sure how to apply the CNOT gate.


texts: What is the best way to get a close-to-fair coin toss from identical biased coins?

texts:
(Von Neumann gave an algorithm that simulates a fair coin given access to identical biased coins. The algorithm potentially requires an infinite number of coins (although in expectation, finitely many suffice). This question concerns the case when the number of coin tosses allowed is bounded.)

Suppose we have $n$ identical coins with bias $\delta=P[Head]-P[Tail]$. The aim is to simulate a single coin toss while minimizing bias.

The simulation must be efficient in the following sense: An algorithm running in polynomial time looks at $n$ random bits and outputs a single bit. The bias of the algorithm is defined as $Bias(A)=|E[A=0]-E[A=1]|$ where the expectation is taken over the distribution defined by $n$ i.i.d bits ${x_1,\ldots,x_n}$ such that $Prob[x_i=1]-Prob[x_i=0]=\delta$.

  Which algorithm $A$ running in polynomial time has the least bias $Bias(A)$?

This question seems very natural to me and it is very likely that it has been considered before.

What is known about this problem? Is anything known when a weaker class (in $AC_0$, etc.) of algorithms is considered?


texts: Is finding an optimal solution to this Knapsack-like problem NP-hard?

texts:
Suppose our inputs are a set of objects with weights $w_1,...,w_n$. We have two separate sets of profits: $p_1,...,p_n$ and $v_1,...,v_n$. We wish to maximize $ \sum_{i=1}^{n} p_i(1-x_i)+\alpha_i v_iw_ix_i$ such that $x_i \in \{0,1\}$ subject to:

$\sum_{i=1}^{n} \alpha_iw_ix_i\leq W$
$0 \leq \alpha _i \leq 1$
$\alpha_iv_iw_ix_i \geq p_i x_i $

In other words, we can sell any amount of whole objects at profit $p_i$, and some subset of object fractions whose weight does not exceed $W$ at price $v_i$ (but then we can't sell the remaining fractions of those objects).

Is this problem NP-hard?

(Credit for this question goes to the author of the reddit post at https://www.reddit.com/r/compsci/comments/4e7q9t/polynomialtime_algorithm_for_modified_knapsack/).


texts: Transforming a DAG-like resolution proof to a tree like resolution proof

texts:
How can a DAG-like resolution proof be transformed to a tree-like resolution proof?

Is such a transformation possible in polynomial time?


texts:
Net (known also as FreeNet, or as NetWalk) is a puzzle game played on a $n \times n$ grid with the following objects:

there are $m$ computers ; each computer occupies one cell and has one link cable;
each computer must be connected to the central unit which occupies one cell and has  1, 2 or 3 link cables;
the rest of the grid is filled with wires (there are no empty cells); a wire cell can be of three types: straight line, corner, or T-connection.

The aim of the game is to rotate each cell in order to connect all computers to the central unit without making loops (i.e. the final configuration must be a tree) and without wires with dead ends (the leaves of the final configuration are the computers).

* Has the complexity of this game been studied?
* And/or do you see a quick reduction from a known similar NP-complete problem?

Eric Goles and Ivan Rapaport in "Complexity of tile rotation problems" prove that a similar problem is NP-complete but they use 5 tiles (we can assume that the Net game uses 4 tiles, because we can replace the central unit with a T-connector without changing the game structure), and in their proof loops are not forbidden.


texts:
I am currently looking at relations that are both transitive and Euclidean, but not necessarily symmetric, hence not necessarily equivalence relations. I have found nothing about this kind of relations. Does anyone know of some work concerning these relations? And first of all do they have a name?

Thanks!


texts: Bit complexity of integer factorization?

texts:
Integer Factorization problem: Given integers $N, M$, find an integer $d< M < N$ that divides $N$. Is it easier to find the value of a single bit? This problem is at least as hard as integer factorization.

  What is the best known upper bound on the complexity of finding the value of $i^{th}$ bit of $d$ ?

I'm interested in algorithms that are asymptotically better than the best known integer factorization algorithm.


texts: Purely Functional Representations of Catenable Sorted Lists question

texts:
Good day.

I'm currently reading the paper "Purely Functional Representations of Catenable Sorted Lists" by Tarjan and Kaplan[link to the paper]. But I have a question
about the modified 2-3 finger search trees in Section 3(nodes of degrees 1 to 4 are allowed on left and right spines).
Below I briefly describe the problem and where I have the question.

More precisely, I interest in how they maintain the Invariant 3.1 during the insertion.

Invariant 3.1:

There are no two 4-nodes with a 3-list between them.
There are no two 1-nodes with a 2-list between them.

They denote the node on the right spine where they insert the element as
$v$. If $v$ is node of degree 2 or 3 then $y$ denotes the {2-3}-list where $v$ is.
The insertion operation inserts a key into the regular 2-3 tree $T$ to which $v$ points to.

There are two possible cases:

The height of the tree does not increase.
The height of the tree increases by one. Then the inserting algorithm instead
of splitting the root returns two trees $T_1$ and $T_2$ of the same height as $T$,
and a key $k$.

If the case 2 occurs the the degree of $v$ increases by one since it has to point to
$T_1$ and $T_2$.
We use the operations Fix&Push and Fix&Concatenate(defined in the paper) to maintain the Invariants 3.1.
There are four cases according to the change in the degree of $v$.

I have a question about the case 2: degree of $v$ changes from $3$ to $4$.
We perform Fix&Push(v, $S_u$) and Fix&Catenate($S_u$, $S_l$), where
$S_u$ and $S_l$ are the list containing elements of the spine list(I did not give exact definitions here because I count on the help of the researchers how have read the paper). Consider the following example. Let right spine's list $R$ = {{2}, {3, 3, 3, 3, 3}, 4}. Then $v$ is bolded element(third element) and $y$ = {3, 3, 3, 3, 3}. After the split of $R$ we have: $S_u$ = {2, {3, 3}} and $S_l$ = {{3, 3}, 4}.
The degree of $v$ is 4 after the insertion. Then the result of Fix&Push(v, $S_u$) is $S_u$ = {2, {3, 3}}, 4}. And the result of  Fix&Catenate($S_u$, $S_l$) is {{2}, {3, 3}, 4, {3, 3}, 4}. This violates the Invariant 3.1(bolded elements).
This is due to the fact that Fix&Catenate does not fix the cases like
Fix&Catenate({{3, 3}, 4}, {{3, 3}, 4}). It's very easy to fix it: just add the necessary operations in the Fix&Catenate. But I do not understand why did not the authors do this? May be I'm missing something?

Thank you for help. I understand that the description of the problem is vague, but I hope the researches which have read this paper will understand my question.


texts: Alternate proofs of Immerman-Szelepcsenyi theorem

texts: Immerman and Szelepcsenyi independently proved that $NL=coNL$. Using their technique of inductive counting, Borodin et al proved that $SAC^i$ is closed under complementation, for $i > 0$. Prior to Reingold's theorem ($SL=L$), Nisan and Ta-Shma proved $SL=coSL$, using logspace uniform projection reductions. A 1996 paper of Alvarez and Greenlaw states "A proof of $NL=coNL$ using techniques similar to Nisan and Ta-Shma's has not been achieved although such a proof would be very interesting". I am wondering if such a proof is found in the last 14 years. Are there any other alternate proofs of $NL=coNL$ ?


texts: Justifying simplifying assumption about message distributions for perfectly secret encryption?

texts:
I am currently reviewing my way through Katz and Lindell's Intro to Modern Cryptography, and have found the following question early in the book (exercise 2.6) surprisingly difficult to answer cleanly:

  Say encryption scheme (Gen,Enc,Dec) satisﬁes Deﬁnition 2.1 for all distributions over
  $\mathcal{M}$ that assign non-zero probability to each $m\in \mathcal{M}$ (as per the simplifying convention used in this
  chapter). Show that the scheme satisﬁes the definition for all distributions over $\mathcal{M}$ (i.e. including those
  that assign zero probability to some messages in $\mathcal{M}$). Conclude that the scheme is also perfectly secret
  for any message space $\mathcal{M}' \subset \mathcal{M}$

Where $\mathcal{M}$ is the message space the encryption scheme is defined over, and def 2.1 is

  An encryption scheme (Gen,Enc,Dec) over a message space $\mathcal{M}$ is perfectly secret if for
  every probability distribution over $\mathcal{M}$, every message $m \in \mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ for which
  $\Pr[C = c] > 0$ :
  $\Pr[M = m \mid C = c] = Pr[M = m]$

Maybe I am just missing something really basic, does anyone have a simple solution?


texts: What is this variant of set cover problem known as?

texts:
Input is a universe $U$ and a family of subsets of $U$, say, ${\cal F} \subseteq 2^U$. We assume that the subsets in ${\cal F}$ can cover $U$, i.e., $\bigcup_{E\in {\cal F}}E=U$.

An incremental covering sequence is a sequence of subsets in ${\cal F}$, say, ${\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\}$, that satisfies

1) $\forall E\in {\cal A}, E\in {\cal F}$,

2) every newcomer has new contribution, i.e., $\forall i>1$, $\bigcup_{j=1}^{i-1}E_i \subsetneq \bigcup_{j=1}^{i}E_i$;

The problem is to find an incremental covering sequence of maximum length (i.e., with maximum $|{\cal A}|$). Note that a maximum length sequence must eventually cover $U$, i.e., $\bigcup_{E\in {\cal A}}E=U$.

I have attempted to find an algorithm or an approximate algorithm to find the longest incremental covering sequence. I was just wondering what this variant of set cover problem known as. Thank you!


texts: Find the maximum subset contained by a ball of radius R

texts:
I am searching for the name of / literature to the algorithmic problem as follows:

  Given a metric space $(M,d)$, a finite Subset $X = \{ x_1, \dots, x_n \} \subset M$ and a fixed Radius $R > 0$, find the maximum amount of points being enclosed by a ball of radius $R$. Alternatively, find $N$, such that
  $ N = \max_{x \in M} |X \cap B_R(x)| $

I only know of the 1-center problem so far. But this tries to solve the problem for minimizing the radius of a ball containing all points within a set. I also found one paper discussing a $\mathcal{O}(|X|^2)$ solution for the euclidean plane. There it has been called Maximum-Enclosing-Disk-Problem. Any information regarding generalizations for $\mathbb{R}^D, D > 2$ or different metrics, would be helpful.

I am not very experienced with computational geometry and the theory of algorithms, but I need to find current literature on this problem. Having a name, or a similar problem, on which this problem can be reduced, would be help me a lot. Also, if you know literature or keywords regarding approximation attempts.

Thank you for your answers.

Edit: As discussed in the comments, an arbitrary metric space might not even computable. However, as I didn't want to restrict the solution on real euclidean spaces (e.g. the space of strings provided with the edit-distance should be an option), I decided for the very general formulation of the problem.


texts: Is there any reference on the hardness of approximation for 2-partition problem?

texts: I tried to look for some references but could not find any. I knew it is proved to be NP-complete via a transformation from Knapsack or 3DM problem. But I couldn't find a way to apply PCP theorem to get the hardness of approximation for this problem. Thank you.


texts: Environment-assisted quantum transport computation

texts:
The paper below and the news story based on it describe a new form of computation based on what they call environment-assisted quantum transport (ENAQT).

ENAQT involves a combination of quantum and classical effects at room temperature.

The paper says:"Current computers operate with about 4 GHz processors, where the cycle time of logical operations is 250 picoseconds. Computers based on articial light harvesting complexes could have units with 100-1000 times larger eciency at room temperature. But, it is also possible to realize such systems on excitons of organic molecules or on Hamiltonians arising in nuclear matter, which would provide a virtually endless source of improvement both in time and miniaturization below the atomic scale."

http://www.technologyreview.com/view/522016/quantum-light-harvesting-hints-at-entirely-new-form-of-computing/
Evolutionary Design in Biological Quantum Computing,
Gabor Vattay, Stuart A. Kauffman
http://arxiv.org/abs/1311.4688

I know next to nothing about quantum computers or complexity-theory. Am I right in thinking that ENAQT computation is theoretically slower than quantum computers as heretofore conceived but faster than classical computers?

Will terms such a qubit, quantum-information and quantum complexity-classes need new ENAQT counterparts (ENAQTbit, B-ENAQT-P instead of BQP etc) or will the existing quantum versions be sufficient for describing ENAQT computation?


texts:
Vertex Cover can be easily reduced to Independent Set and vice versa.

However, in the context of parameterized complexity, Independent set is harder than Vertex Cover. A kernel with $2k$ vertices exists for Vertex Cover, but Independent Set is W1 hard.

  How does the nature of Independent Set change in
  the context of FPT and why?


texts: Computing Minima of the Projection of a Binary Cube

texts:
The problem is as follows: I want to compute the minima (with respect to the canonical partial order on vectors "$\leq$") of the linear projection of the extreme points of an $n$-dimensional $\{0,1\}$-cube into the plane. Thus, I am given a $2\times n$-matrix $C$ with integer entries which encodes my projection. Let's call it the cube projection problem.

Note that the result of the projection is a set of isolated points and that these points do not lie in convex position in general.

Is it possible to compute these points in an output-sensitive way? Is this a (well-)known problem? What are problems which might be related to this one?

EDIT NOTE: W.l.o.g. we can assume that each column of $C$ consists of a negative and a positive value. Assume that both values of column $i$ are non-negative (non-positive), then $Cx \leq Cx'$ for every $x\in\{0,1\}^n$ with $x_i = 0$ ($=1$) and $x'_j := x_j$ for $j\neq i$ and $x'_i = 1$ ($=0$).

The problem is related to the knapsack problem in the following sense: For a knapsack instance
\begin{equation}
\max\ c_1^Tx\\
\text{s.t.}\ c_2^Tx \leq W\\
x\in \{0,1\}^n,
\end{equation}

an optimal knapsack value is the negation of the first component of one of the vectors in

$$\mathcal{Y}:=\min\{\begin{pmatrix}-c_1^T\\c_2^T\end{pmatrix}x \mid x \in \{0,1\}^n\} \subseteq \mathbb{Z}^2.$$

This is well-known and used by the Nemhauser-Ullmann algorithm, cf. [1]. Though, output-sensitivity of the Nemhauser-Ullmann algorithm for the cube projection problem is open, as far as I known.

An interesting question which arises in this knapsack context is: Is there an $\mathbf{NP}$-hard set of knapsack instances with $\mathcal{Y}$ of polynomial size? If there is then the cube projection problem cannot be output-sensitively solved unless $\mathbf{P}=\mathbf{NP}$.

The relation to the Nemhauser-Ullmann algorithm also shows that the problem can be solved in pseudo-polynomial time.

EDIT NOTE2: To prove that the cube projection problem cannot be solved in ouput-polynomial time, we can prove that the following decision problem is hard:

Given $C$ and a subset $M\subseteq \min \{ Cx \mid x\in\{0,1\}^n\}$. Decide if $M=\min \{ Cx \mid x\in\{0,1\}^n\}$.

Lawler, Lenstra and Rinnooy Kan proved in [2] (for the case of finding maximal independent sets) that if the cube projection problem can be solved in output-polynomial time then the above decision problem can be solved in polynomial time. This technique is often used to prove the hardness of an enumeration problem.

References

[1] Kellerer, H., Pferschy, U., and Pisinger, D. Knapsack Problems. Springer Berlin Heidelberg New York, 2004.

[2] Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. Generating all maximal independent sets: $\mathbf{NP}$-hardness and polynomial-time algorithms. SIAM Journal on Computing 9, 3 (1980), 558–565.


texts: Best known joint containments for/by NP and Parity-P?

texts:
Parity-P is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero number of acceptance paths). Thus Parity-P is basically PP's stunted younger sibling: while PP counts whether or not the number of accepting paths of an NP-machine is a majority or not (i.e. the most-significant bit of that quantity), Parity-P indicates the least-significant bit of the number of accepting paths.

Like NP, Parity-P contains UP (which contains P, "probably" strictly so); and like NP, Parity-P is contained in PSPACE.

Question. What are the best known joint upper and lower bounds for NP and Parity-P?


texts: Does the System F with pairs have the strong normalisation and subject reduction properties?

texts: It is easy to look in a lot of textbooks the proofs of subject reduction and strong normalisation for System F, also, sometimes there are definitions of System F with pairs, where (t,r) is a term, not only an encoding. The question is, what would be the reference for this system?


texts: Wikipedia-style explanation of Geometric Complexity Theory

texts:
Can someone provide a concise explanation of Mulmuley's GCT approach understandable by non-experts? An explanation that would be suitable for a Wikipedia page on the topic (which is stub at the moment).

Motivation: I am "co-reading" Scott Aaronson's book Quantum Computing since Democritus with a friend of mine who is a researcher in string theory. In the preface of the book, Aaronson calls GCT "the string theory of computer science".
Being a string theorist, my friend got excited about this claim and asked me what GCT is. At that point I shamefully realized I didn't have a Wikipedia-ready answer for his question.


texts: What category are Tagless Final Algebras final In?

texts:
The Haskell and Scala community have been very enamored recently with what they call tagless final 'pattern' of programming. These are referenced as dual to initial free algebras, so I was wondering what Tagless Final was final of. On ncatlab one only finds talk of final coalgebras, not final algebras.

A few references:

The influential Haskell Typed Tagless Final Interpreters lecture notes
A translation of that article for Scala (Dotty) Revisiting Tagless Final Interpreters
A blog post From Object Algebras to Finally Tagless Interpreters makes the case that Object algebras are equivalent to Tagless Final.
It cites the paper Extensibility for the Masses, practical extensibility with Object Algebras.

The example used by these are clearly Algebras, which in category theory are expressed with endofunctors F as maps of the form F(X) -> X. Coalgebras are dual maps X -> F(X), and represent processes.

The follow up question is more about use of final tagless in programming circles which seems to be more related to final coalgebras.
See the question on stackoverflow here.


texts: Reconstructing labeled poset from linear extensions

texts:
Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is a finite sequence $L$ of elements of $\Sigma$ (formally $L$ maps every position $i \in \{1, \ldots, |L|\}$ to a label $L[i] \in \Sigma$, where $|L|$ is the length of $L$). We say that $L$ is a linear extension of $P$ if there is an order- and value-preserving bijection $f$ from $P$ to $L$: formally, $f$ is a bijection from $P$ to $\{1, \ldots, |L|\}$, we have $\forall x, y \in P$, if $x < y$ then $f(x) < f(y)$, and $\forall x \in P$, $\mu(x) = L[f(x)]$.

My question is to determine the complexity of the following problem: I am given as input a set $S$ of label lists, and I want to know if there exists a labeled poset $P_S$ such that $S$ is exactly the set of the linear extensions of $P_S$. (Also, if possible, compute $P_S$.)

For instance, for the input $S = \{(A, B, A), (A, A, B)\}$, a choice of labeled poset would be $P_S = (\{a_1, a_2, b\}, <_S, \mu_S)$, where $<_S = \{a_1 < a_2, a_1 < b\}$ and $\mu_S$ maps $a_1$ and $a_2$ to $A$ and $b$ to $B$.

Of course, the answer is trivially "no" if all lists of $S$ do not have the same length, or actually if they do not have the same domain of values (seen as a multiset). Conversely, if they do, I can easily construct a labeled poset (e.g., the empty order relation on the domain) such that all label lists of $S$ are linear extensions of the poset. However, can I do this and avoid that other label lists not in $S$ are also extensions?

Other remarks:

The problem can alternatively be phrased in terms of directed labeled graphs and topological sorts: a label list $L$ is a linear extension of a labeled poset $P$ iff it is the label of some topological sort of a labeled transitive DAG $G_P$ that represents $P$ (i.e., its Hasse diagram). So my problem can be equivalently phrased as follows: given $S$, determine if there is a labeled DAG $G_S$ such that $S$ is exactly the set of the labels of the topological sorts of $G_S$.
For the case of ordinary posets (not labeled posets), or equivalently of unlabeled DAGs, the problem is in PTIME. The argument is to construct a candidate poset $P_S$ by intersecting the comparability relations implied by $S$ (which you cannot do in the labeled case because of the ambiguity of labels), and then check that $P_S$ realizes no other linear extensions by enumerating them (you cannot tractably do this with labels because there may be a lot of "linear extensions" that end up being the same label set). This implies that the problem is in PTIME if the list $L$ contains no duplicate values, or if $\mu$ is injective.
Other related results are the fact that counting the number of linear extensions of an input labeled poset (actually, even when there are no labels), is #P-hard. This does not imply hardness of my problem, though, because enumeration approaches could conceivably work though they do not directly adapt (see above). Also, from an answer to a previous question I know that it is NP-hard, given a labeled poset $P$ and label list $L$, to determine whether $L$ is a linear extension of $P$; yet I see no easy reduction between that problem and the question asked here.
I am not even sure that my problem is in NP. Of course we can try to guess the poset $P_S$ and bijections that realize the linear extensions of $S$, but then we need to verify the absence of other linear extensions, so this only gives a $\Sigma_2^P$ upper bound.


texts:
Suppose I'm given a CNF formula with $m$ clauses (and $k$ literals in each clause), with a total of $n$ variables in the formula, where each variable is in at most $c$ clauses, along with a satisfying assignment to this formula. I change the value of each variable to the other possible value (from the one in the given assignment) with constant probability $p \leq \frac{1}{2}$ independently of the other variables. I want to show that with probability at least $1-exp\left(-\frac{p^2n}{2c^2}\right)$, the new assignment satisfies at least $\left(1-\left(c+1\right)p\right)m$ clauses.

It seems I should use here martingales (Azuma's inequality) or large deviation inequalities, however I didn't manage to get any meaningful results using these methods, so that may not be the case.


texts: Extension to the Stable Marriage Problem ?

texts:
This may sound more like a social sciences question more than a TCS one, but it is not. When reading "Randomized Algorithms" which describes the Stable Marriage Problem, one can read the following (p54)

" It can be shown that for every choice of preference lists there exist at least one stable marriage. (Curiously enough, this is not the case in a homosexual monogamous society with even number of inhabitants)...."

Are there any very simple extensions of the Stable Marriage Problem that allows some type of steady state that includes a homosexual monogamous society, or a society in which a certain subset of the population follow a different set of rules than the larger set ?

In the affirmative, are there algorithms that perform such a matching ?


texts: Ramsey's theorem for collections of sets

texts:
While exploring different techniques of proving lower bounds for distributed algorithms, it occurred to me that the following variant of Ramsey's theorem might have applications – if it happens to be true.

Parameters: $k$, $K$, $n$ are given, and then $N$ is chosen to be sufficiently large. Terminology: an $m$-subset is a subset of size $m$.

Let $A = \{1,2,...,N\}$.
Let $B$ consist of all $k$-subsets of $A$.
Let $C$ consist of all $K$-subsets of $B$.
Assign a colouring $f\colon C \to \{0,1\}$ of $C$.

Now Ramsey's theorem (the hypergraph version) says that no matter how we choose $f$, there is a monochromatic $n$-subset $B'$ of $B$: all $K$-subsets of $B'$ have the same colour.

I would like to go one step further and find a monochromatic $n$-subset $A'$ of $A$: if $B' \subset B$ consists of all $k$-subsets of $A'$, then all $K$-subsets of $B'$ have the same colour.

Is this true or false? Does it have a name? Do you happen to know any references?

If it is false for some trivial reasons, is there a weaker variant that resembles this claim?


texts: Notion of "quotient" or "inverse" for recognizable tree languages?

texts:
Related to my previous question but this time I have a better idea of what I'm actually asking.

I'm looking at the following operation on recognizable tree languages (i.e. regular tree grammars, bottom-up automata etc.):

$f^{-i}(L) = \{ t  \mid \exists s_1 \ldots s_n \ldotp f(s_1, \ldots, s_{i-1}, t, s_{i+1} \ldots, s_n) \in L \}$.

That is, if $f$ is a symbol in our ranked alphabet, we take the $i$th component of all trees in $L$ that have $f$ as their root.

This seems reminiscent of the notion of quotient in formal language theory, or of projections in the set-constraint literature. Notably, it's not a homomorphism, since we're only applying it at the root, not over the entire tree.

I'm wondering:

Does this operation have a name already? Has it been studied?
If so, are recognizable tree languages closed under this operation?

It seems like a simple-enough property, but I'd rather not have to figure out all the theory myself if it's already been studied. I've found some things about projection in the TATA book, but they seem to be more about projecting out the nth tuple of a relation, not about projecting to the $i$th argument of a symbol.


texts: My question is straightforward: Is an empty sudoku grid (not partially completed) still NP-complete?


texts: What is an unambiguous language in the sense of Schützenberger?

texts:
I'm reading Thomas Wilke's survey on the connections between Temporal Logic and finite automata, finite semigroups and first-order logic.

In Theorem 6 (by Kamp), the fragment $\mathrm{TL}[\mathsf{F},\mathsf{P}]$ (Temporal Logic with  modalities $\mathsf{F}$ (eventually) and $\mathsf{P}$ (eventually in the past)) is said to be equivalent to first-order logic with two variables.

After the statement of the theorem, Wilke mentions another connection from TL to formal languages:

  (...) the languages expressible in $\mathrm{TL}[\mathsf{F},\mathsf{P}]$ are exactly the unambiguous languages in the sense of Schützenberger [13]

where [13] cites Sur le produit de concatenation non ambigu. I can't pay for the paper and I can't find it anywhere else for download. What's more, I can't read French, even though I'd gladly try if I had the paper.

I've searched online for a while but I can't find a definition of "unambiguous in the sense of Schützenberger", and I guess it's not the same as in an "unambiguous context-free language", since $\mathrm{TL}[\mathsf{F},\mathsf{P}]$ is strictly less expressive than $\mathrm{TL}$, which is strictly less expressive than regular languages (unless it's the same definition, restricted to regular languages instead of context-free).

Does anybody have the definition, the paper, or know of a survey or book with this information?

An additional and related question: is there a (known) restriction to the syntax of regular expressions such that this class of unambiguous language is equivalent to the fragment of regular languages defined by those regular expressions? (as in the equivalence of star-free languages with first-order logic, for example).

Thanks in advance for your help!


texts: Is there a reduction to "door and pressure plate" games that doesn't explode solution length?

texts:
This paper gives a proof that in a game with doors and pressure plates, it is PSPACE-hard to determine whether or not the (player's) avatar can reach a given location. This is proven by a reduction from TQBF, and the length of the resulting solutions depends exponentially on the number of universal quantifiers in the formula.

Is there a reduction from an NPSPACE machine to such a game for which the length of the game's solutions are polynomially related to the length of the machine's accepting paths?


texts:
It seems that Geometric Complexity Theory requires much knowledge of pure maths such as algebraic geometry, representation theory.

While I am a CS student and do NOT have classes of very abstract and pure mathematics, I am interested in this program.

Is there a list of "minimum knowledge" for learning this theory ?

This list includes lecture notes of CS or math departments, surveys of any journal or conferences, and text books of pure math.

[EDIT: Added later] Thank you for your comments.

General theory of computing: I read Sipser's book with the title "Introduction to the Theory of Computation"

Complexity Theory :In particular, I am interested in concrete models for lower bounds of complexity. Thus I read the part of the "concrete lower bounds" in Arora-Barak's text book. I also have basic knowlede in the several chapers of the communication complexity book written by Nisan.

Basic Mathematics : I have learnt about proof-based linear algebra such as general definition of the vector space etc and precicely argument of calculas based on epsilon-delta argument.

Algebra: I have learned about definition and examples of group, ring, and field. I had a class for cs students, and have not learned about general thoery of this algebraic systems.


texts: On Vertex Coloring of Permutation Graph and Comparability Graph and 2-SAT

texts:
I have 2 questions.

Firstly, I am not sure about differences between Permutaion Graphs and Comparability Graphs. The latter graph class includes the other class. Is there a specific example of graph which is is in Comparability Class but is not in Permutation Class ?

Secondly, There are several fast algorithm for vertex coloring of permutaion graph like poly time algorithms using dynamic way or NC parralel algorithms. Can we solve vertex colroing via converting instances of coloring to instances of 2-SAT? I think this solution is plausible, because any permutaion can be represented by several transpositions and we may be able to construct clause whose length is 2 using such transpositions.


texts:
Suppose we're training a linear separator in the realizable PAC setting. Given $m$ labeled examples $(x_i,y_i)$ in $\mathbb R^d\times\{-1,1\}$, a (consistent) linear separator is a vector $w\in\mathbb R^d$ with $||w||=1$, such that
$$ y_i(w\cdot x_i)=:\gamma_i>0
$$
for all $1\le i\le m$. Putting $R_i=||x_i||$, we can define the margin of the $i$th example as $R_i/\gamma_i$ and the sample margin as
$$ \min_{1\le i\le m} R_i/\gamma_i.$$
This quantity is known to control the generalization error, see e.g. here
https://www.cs.bgu.ac.il/~karyeh/opt-svm.pdf
for the precise statements.

Question: are there any generalization bounds for the above setting in terms of the average margin, $\frac1m\sum_{i=1}^m R_i/\gamma_i$ --- as opposed to the worst-case one, as above?


texts: Complexity class of approximating perfect match count

texts:
We know we can approximate perfect matching count of bipartite and approximate volume of convex bodies in randomized polynomial time.

Is there any evidence these approximations could be in Nick's class or in quantum Nick's class?


texts:
Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS.

It is quite clear that most of us might be attracted to read (or at least glance at) a paper with an interesting title (at least I do so every time I go over a list of papers in a conference), or avoid reading poorly named articles.

  Which papers do you remember because of their titles (and, not-necessarily, the contents)?

My favorite, while not a proper TCS paper, is "The relational model is dead, SQL is dead, and I don’t feel so good myself." .