texts: Approximations for the Stable Fixtures Problem

texts:
I have a set of N items, each with a subset of those items they can be paired with; each pair has a weight.  I'd like to choose pairs to maximize the total weight, subject to each item being in at most M pairs.

I believe this can be seen as an instance of the Stable Fixtures Problem (itself a generalization of the Stable Roommates Problem), which seeks to find a stable matching if one exists.  However, I don't really care if the matching is stable, and I want to find a high-weight matching in every case.  It doesn't need to be optimal, approximate is fine.

Are there any approximate solutions for this problem, or does this problem go by another name in another field?  Approaches I can think of would be to randomly perturb the ranks (weights) until a stable matching is found, or perhaps treat it as a linear programming problem.


texts: Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?

texts:
A decade ago I observed what I dub "Murphy's Law of Complexity Theory": whenever a new separation or collapse is discovered, the question is answered in the direction that makes $P\overset?=NP$ most challenging to determine. I do not believe this rule has failed once in the intervening years. This leads me to wonder what the implications would be if the Law were actually true.

What questions could be answered using this conjecture? Are the answers consistent, or is there some set of questions such that they can't all be answered in the way that makes proving $P\overset?=NP$ most challenging without causing inconsistencies?


texts: Solving "all-marginals" problem for independent sets on grid

texts:
Suppose I have a distribution over independent sets on an $n\times n$ grid where the probability of independent set occupying nodes $(i_1,j_1),\ldots,(i_k,j_k)$ is proportional to $\lambda_{i_1,j_1}\cdot \lambda_{i_2,j_2} \cdots\lambda_{i_k,j_k}$. Let $p_v$ be the probability that vertex $v$ in this grid is occupied, how do I compute $p_v$ for every vertex $v$ in the grid?

For instance, when $n=2$, the four probabilities are the ratios below

Motivation: comparing accuracy of "correlation decay" based approximate counting with exact for some not-too-large graphs

Clarification 11/6: This is the same $p_v$ as in the first formula of page 3 of [Weitz, 2006]


texts: 0-1 Linear Programming: computing the Optimal Formulation

texts:
Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in \{0,1\}$ and $k \in \mathbb{R}$.

Clearly, $c$ has the effect of splitting $\{0,1\}^n$ in two subsets $S_c$ and $S_{\lnot c}$. $S_c$ contains all and only those points satisfying $c$, whereas $S_{\lnot c}$ contains all and only those points falsifying $c$.

Assume that $|S_c| \geq n$. Now, let $O$ be a subset of $S_c$ such that all the following three statements hold:

$O$ contains exactly $n$ points.
Such $n$ points are linearly independent.
Such $n$ points are those at minimum distance from the hyperplane represented by $c$. More precisely, let $d( x, c )$ be the distance of a point $x \in \{0,1\}^n$ from the hyperplane $c$. Then, $\forall B \subseteq S_c$ such that $B$ satisfies 1 and 2 it is the case that $\sum_{x \in B} d(x, c) \geq \sum_{x \in O} d(x, c)$. In other words $O$ is, among all the subsets of $S_c$ satisfying both conditions 1 and 2, the one that minimizes the sum of the distances of its points from the hyperplane $c$.

  Questions

  Given $c$, is it possible to compute $O$ efficiently?
  Which is the best known algorithm to compute it?

$\ $

Example with $n = 3$

$S_{\lnot c} = \{ ( 1, 0, 1 ) \}$, $O = \{ ( 0, 0, 1 ), ( 1, 1, 1 ), ( 1, 0, 0 ) \}$.

$\ $

Update 05/12/2012

  Motivation

  The motivation is that using $O$ it should be possible to determine the optimal constraint $c^*$, as it should be the hyperplane defined by the $n$ points in $O$.

  The optimal constraint $c^*$ is the one that leads to the optimal polytope $P^*$.

  The optimal polytope $P^*$ is the one whose vertices are all and only the integer vertices of the initial polytope $P$ (an integer vertex is a vertex whose coordinates are all integer).

The process can be iterated for each constraint $c$ of a 0-1 $LP$ instance $I$, each time substituting $c$ with its corresponding optimal constraint $c^*$. At the end, this will lead to the optimal polytope $P^*$ of $I$. Then, since the vertices of $P^*$ are all and only the integer vertices of the initial polytope $P$ of $I$, any algorithm for $LP$ can be used to compute the optimal integer solution. I know that being able to compute $P^*$ efficiently would imply $P = NP$, however the following additional question still stands:

  Additional Question

  Is there any previous work along these lines? Did anyone already investigated the task of computing, given a polytope $P$, its corresponding optimal polytope $P^*$? Which is the best known algorithm to do that?


texts:
EDIT: The Wikipedia article mentioned here was incorrect and has since been updated.  Comb sort's worst-case behavior is $\Omega(n^2)$, not $O(n \log n)$ as was claimed.

Yesterday I stumbled on the comb sort algorithm, a modification of bubble sort similar in spirit to Shell sort.  The idea is to maintain a gap of some size, then use a bubble-sort pass over the array using that gap size to roughly position the elements into their proper positions.  Each iteration decreases the gap size, until eventually the algorithm degrades into bubble sort.

The Wikipedia article claims that the algorithm runs in O(n log n) time worst-case, but the citation for this claim is a paper on GPU processing that mentions this result offhand without providing any analysis or citation.  One of the original papers on comb sort doesn't even attempt to prove a worst-case bound, and in fact not a single source I've found has attempted to analyze the worst-case or even average-case complexity of comb sort.  This concerns me, since I've found a lot of sites that are clearly getting their information from the Wikipedia article, and I would hate for a single bad source to propagate the O(n log n) claim if it is incorrect.

My question is this: is there a reliable source that proves the O(n log n) worst-case behavior of comb sort?

Thanks!


texts:
I wanted to know whether Greedy approximation algorithms can outperform LP relaxation and rounding based algorithms. Specifically, can it beat the integrality gap of a 'reasonable' LP relaxation, (e.g. the natural relaxation of the ILP by relaxing variables $x_i\in\{1,0\}$ to $x\geq 0$).

For an example, if we consider the Setcover problem with universe set $U$ s.t. $|U|=n$ with max frequency of an element $f$, the greedy algorithm gives an $O(\mathrm{log}~n)$ approximation. Whereas LP relaxation can give an $f$ approximation with deterministic rounding. But we know that the integrality gap is $\Omega(\mathrm{log}~n)$ for the general LP formulation. Indeed through a randomized rounding technique we can achieve a $O(\mathrm{log}~n)$ approximation w.h.p. So the greedy is almost as good as the LP relaxation.

Does anyone know of an instance of NP Hard problem having approximations using greedy algorithm which is better than the integrality gap? Please point out the references if known. It will be great if the problem is well studied.


texts: Counting length-k increasing subsequences in a permutation

texts:
(Originally posted on Math.SE.)

Let $f$ be a permutation on $n$ letters. I want to count the number of $k$-long increasing subsequences quickly.

One approach is to first use divide and conquer to split the problem into finding increasing subsequences in pairs of numbers. The resulting 'tree' then has height $\log n$. I'm wondering how the subproblems could be combined in an efficient way. I thought about prefix sums and using mergesort, but I can't see how to effectively implement them.

One idea to save time when combining two subproblems is to compare elements at the end of the increasing subsequences in the first subproblem with values in the second subproblem.

My goal is to get to $O(k n \log n)$ time but this doesn't do it.


texts: Good Survey paper for k-means/k-median/k-center/facility-location

texts:
I have stated 4 problems in the Question title.
All these problems are closely related and are studied in various variations. For example:

Space: Euclidean/metric/discrete/continuous/non-metric/2-D_plane...

Parameters: when $k$ or $d$ is fixed or some sort of bi-critera relaxation ...

Settings: Streaming/Online/parallel/Fault-tolerant/query/...

Constrained models: capacitated/outlier/fairness-constraints/...

Special models: $\beta$-separation/ORSS-separability/BBG-condition/...

Techniques: coreset-based/primal-dual/local-search/distance-sampling/tree-decomposition/...

...many more

There are several hardness results, approximation algorithm and parameterized algorithms known for the problem and its variants; and many are not known yet and are open.
Sometimes it happens that the research papers mention imprecise/incomplete/incorrect results, that have been previously discovered. This causes a lot of confusion. Moreover, it is difficult to go through every paper and check their results. I am looking for a (survey) paper that might give a brief idea of what all has been done in the field over the years and what are the open questions remaining in the field. It would be a great help if somebody could share such a paper.


texts: Sending people to lunch together with minimal repetition

texts:
We have n people and split them up in groups of size x. Each group of x people goes to lunch together. Next time around when the groups are set up people who were in a group last time should not end up in a group together if avoidable. Ideally they also should go out with as few people from the time before that.

I thought about modelling this as a graph problem:
People are vertices $v \in V$ and going to lunch together creates a edge between those vertices. The edge has a weight on it that's higher the more recent the lunch happened. Now we want to create $\frac{|V|}{x}$ subgraphs with x vertices each and minimize the sum of the edges connecting the vertices in each subgraph.

Is there a name (lunching programmers ? ;-) ) and associated research for this problem? Or is there a way to map this to another known problem?


texts:
Suppose that you have a multiset of positive integers $I$.

$I$ is not given, but it is known that the sum over all elements of $I$ = $k$.

(e.g. if $I$={2,5,7} then k=14 is given, but I is unknown).

We are also given another integer $r$.

$S\subseteq I$ will be called $r-minimal-subset$, if $sum(S)>r$,

and for every $x\in S$, $sum(S$\{x}$) \leq r$.

For example, if $I$={1,3,3,5,7,8} and r=10,

then {3,3,5} and {1,3,7} are r-minimal-subset, but {5,7,8} is not (as the subset {7,8} 's sum is 15. {7,8} is a r-minimal-subset).

What is the the best upper bound we can give on the number of $r-minimal-subsets$ of I?

(In this setting, we get is $(r,k)$, while $I$ is being chosen by an adversary).

~~~~~~~~~~~~~~~~~~~~~~~~~~

Edit:
Hmm, sorry for the question.

Obviously the answer is $k \choose r+1$, for I={1,1,..,1}, $|I|=k$.
It doesn't let me answer the question, so you could go ahead :/.


texts: Counterexample to max-flow algorithms with irrational weights?

texts:
It is known that Ford-Fulkerson or Edmonds-Karp with the fat pipe heuristic (two algorithms for max-flow) need not halt if some of the weights are irrational. In fact, they can even converge on the wrong value! However, all the examples I could find in the literature [references below, plus references therein] use just a single irrational value: the conjugate golden ratio $\phi' = (\sqrt{5}-1)/2$, and other values that are either rational, or are rational multiples of $\phi'$. My main question is:

General Question: What happens with other irrational values?

For example (but don't feel like you have to answer all of these to post - I'd find interesting an answer to any one, or to other questions that fall under the above general question):

Given any $\alpha \in \mathbb{R}$, can one construct (or even show existence of) such counterexamples?

More weakly: are there examples known that use an irrational value essentially different from $\phi'$? That is, is there some $\alpha$ which is not a rational multiple of $\phi'$ (or more strongly not in $\mathbb{Q}(\phi')$) and such that there are counterexamples to Ford-Fulkerson and/or Edmonds-Karp where all the weights lie in $\mathbb{Q}(\alpha)$?

In the other direction, does there exist an irrational $\alpha$ such that Ford-Fulkerson (resp., Edmonds-Karp) halts with the correct value on all graphs whose weights are all from $\mathbb{Q} \cup \{q\alpha : q \in \mathbb{Q}\}$? (Or more strongly, from $\mathbb{Q}(\alpha)$?)

In all cases, I want to assume something like the real RAM model, so that exact arithmetic and exact comparisons of real numbers are done in constant time.
(There are other max-flow algorithms that are known to run in strongly polynomial time, even with arbitrary real weights, which is perhaps why this type of question may not have been further explored. But having just taught these algorithms in my undergrad algorithms class, I'm still curious about this.)
References

A minimal counterexample for Ford-Fulkerson was given by Zwick TCS 1999

A counterexample for Edmonds-Karp was given by Queyranne or Queyranne Math. Oper. Res. 1980, though I don't know if that one's minimal.

These can both be found in Jeff Erickson's lecture notes, with the first in Section 23.5 and the second as Exercise 14 of Lecture 23.


texts: extracting/ exploiting similarity of SAT instances by solver

texts:
suppose that two SAT formulas on different variables $F_1, F_2$ are given on the input that are known to be true and the problem is to build an algorithm that finds a solution to each. the formulas actually are generated by another algorithm which creates/ generates instances $F_n$ for any $n$. the solving algorithm can find/ exploit "similar structures" contained in each by analyzing eg the clause-variable graph, eg looking for graph isomorphisms etc.

  has this problem of finding "similarities" between two SAT formulas by a solver been studied?

there is some rough connection of this eg implications of worst case bounds in this paper A simple proof that AND-compression of NP-complete problems is hard (Dell), but am looking for more direct algorithm(s) and possibly more empirical approaches/ analysis, eg somewhat similar to strategies/ heuristics used in SAT solver implementations. (this problem has applications in eg automated theorem proving.)


texts: Why is it difficult to develop a subexponential functoral approach to discrete log

texts:
Call a discrete logarithm algorithm functoral if the commutative algebraic object that the algorithm acts on can be changed with another commutative object in the same category and the algorithm does not asymptotically slowdown.

Why is it difficult to develop a single functoral discrete logarithm (classical) algorithm that works on all commutative groups?


texts: Is it known that $NEXP = \Sigma_2 \implies NEXP = MA$?

texts:
Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds?

(The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} \Leftrightarrow \mathsf{NEXP} = \mathsf{MA}$.)


texts: Using rejection sampling, it is trivial to construct a Las Vegas algorithm for sampling a uniformly random prime number less than a given $N$. What is known about sampling algorithms that run in worst-case polynomial time and produce the exact uniform distribution on primes? More generally, when an efficient testing for a property is available, is there a method better than rejection sampling that would achieve worst case polynomial time exactly-uniform sampling? This seems like a classical problem (related to sampling vs counting) but I'm not sure where to look up.


texts: Computing integer points on the circumference of a given circle

texts: Is there a known algorithm that efficiently outputs the set of lattice points on the circumference of a given circle? The input circle is specified using its center $(a,b)$ and its radius $r$. The inputs $a, b, $ and $r$ are not necessarily integers.


texts: What upper bound can we get under 3-wise independence? (comparable edition)

texts:
Here is the original question: What bound can we get using $k$-th moment inequality under 3-wise independence? .Yury has given a 3-wise independent example that shows the upper bound is no better than $O(1/t)$.

There is another way to constructing 3-wise independent variables (see more details in http://www.wisdom.weizmann.ac.il/~oded/PS/RND/l03.ps). Are they essentially equal to each other, particularly on deriving the upper bound of $\Pr(|\sum_i(X_i)-\mu|\geq t)$?

Here is the main idea of the construction:
We sample 3 random variables ${r_1,r_2,r_3}$ from $[m]$ uniformly and independently ($m$ is a prime). Then we construct a set $\Omega = \{r_1+r_2*i+r_3*i^2\mod m:i \in [m]\}$. The elements are 3-wise independent. Does the sum of these variables get a similar upper bound?


texts: A boolean function $f: \{0,1\}^n \rightarrow \{0,1\}$ is chosen at random from all $2^{2^n}$ such $f$. What do the Fourier coefficients look like?

texts:
As in the title.

I'm not sure where to start here. My guess is that in expectation at least a constant fraction are non zero, and as a result there would exist some "large" coefs. and some "small" coefs..

Any further intuition would be appreciated.

Thanks.


texts:
Is there a class of hash algorithms, whether theoretical or practical, such that an algorithm in the class might be considered 'reflexive' according a definition given below:

hash1 = algo1 ( "input text 1" )
hash1 = algo1 ( "input text 1" + hash1 )

The + operator might be concatenation or any other specified operation to combine the output (hash1) back into the input ("input text 1") so that the algorithm (algo1) will produce exactly the same result. i.e. collision on input and input+output. The + operator must combine the entirety of both inputs and the algo may not discard part of the input.

The algorithm must produce high entropy in the output. It may, but need not, be cryptographically hard to reverse the output back to one or both possible inputs.

I am not a mathematician, but a good answer might include a proof of why such a class of algorithms cannot exist. This is not an abstract question, however. I am genuinely interested in using such an algorithm in my system, if one does exist.

This is a duplicate of a question that was first posted at https://stackoverflow.com/questions/4823680/reflexive-hash


texts: Appilicability of Theoritical Computer Science in Malware research

texts:
I would like to know the importance of TCS in Malware research. Due to the large volume of new malware variants received per day (~50,000 samples/day according to McAfee), malware researchers are heavily dependent on dynamic analysis (i.e. running the samples in a sandbox and monitoring their behavior) and moving away from static analysis and Reverse engineering as these approaches are very time consuming and sometimes becomes very challenging due to  obfuscation/encryption.

I found a very useful talk (BlackHat 2010) by Greg Hoglund on Malware attribution where the speaker talks about the importance of bringing in the malware authors and their networks into the picture which gives valuable information than just analyzing the binary itself.

I have two questions:

If malware researchers move towards analyzing the behavior of malware authors and their network, in the future does TCS has any importance in malware research.
As I am not strong in TCS, I would like to know where exactly TCS fits
in malware research.

Thank you.


texts: What are the limits of total functional programming?

texts:
What are the limitations of total functional programming? It is not Turing-complete, but still supports a large subset of the possible programs. Are there important constructs that you could write in a Turing-complete language, but not in a total functional language?

And is it correct to say that programs written in total functional languages can be completely statically analysed, while static analysis in Turing-complete languages is limited by things like the halting problem? With that I do not mean that in total functional languages everything can be staticaly determined, because some things are only known at runtime, but I mean that in theory, programs written in an ideal total functional programming language, can be analysed so that everything that could in theory be determined statically can be determined statically. Or are there still undecidable problems inherit in total functional languages that make static analysis incomplete? Some problems will always be undecidable, no matter in which language they are written, but I am interested in such problems that are inherit to the language, like the halting problem in Turing-complete languages.


texts: Integral k-multicommodity flow with demands on acyclic digraphs wirh maximum outdegree two

texts:
It is well-known that different variants of Multicommodity flow problem are NP-complete. What is the complexity of the following variant, that is, the integral k-multicommodity flow problem with demands on acyclic digraphs with maximum outdegree two:

  INSTANCE: An acyclic directed graph
  $G=\left(V,E\right)$ with maximum
  outdegree two, a capacity function $c: E \rightarrow N$, $k$ pairs of
  vertices $(s_i,t_i)$ and a demand
  function $d:\{1,\ldots, k\} \rightarrow N$.

  SOLUTION: A flow $f_i\geq d_i$ for
  each pair $(s_i,t_i)$ with $f_i \in N$
  such that for each $e\in E$,
  $$\sum_{i=1}^k f_i(e) \leq c(e) \text.$$


texts: Rademacher complexity for piecewise-linear convex function

texts: Consider a function family $$\ell(x)=\max_{1\leq k\leq K} a_k^\top x + b_k,$$ where $a_k,b_k \in \mathbb{R}^d$ are bounded in the sense of some norm and $K\geq 2$. What is the best upper bound on the capacity (e.g., Rademacher complexity, etc) of such a family, in terms of dependence on dimension $d$, number of pieces $K$ and sample size $n$?


texts: What is known about reduction by "$P_1$ interprets $P_2$" for generalized programming languages?

texts:
Inspired by this answer, let's say that a programming language is given by the data $L=(P,ev)$ where $P$ (the set of "valid programs") is a computable subset of $\Sigma^*$ and $ev$ (the "evaluator") is a partial computable function $ev:P \times \Sigma^* \to \Sigma^*$, where $\Sigma$ is a finite alphabet. Let's also require that a programming language contains the successor functions $x \mapsto xa$ for each $a \in \Sigma$, the diagonal function $x \mapsto \langle x, x \rangle$, and is closed under composition. (As usual, $\langle a, b \rangle$ is a computable and computably-invertible-in-both-arguments pairing function $\Sigma^* \times \Sigma^* \to \Sigma^*$).

If you want to add some other natural/obvious ones (e.g. the projections $\pi_i(\langle x_1, x_2 \rangle) = x_i$) that should be okay, but nothing too powerful (e.g. don't require that every programming language has a universal interpreter).

  Definition:  $L_1=(P_1, ev_1)$ interprets $L_2=(P_2, ev_2)$ if there is a program $p_{12} \in P_1$ that is universal for $L_2$, i.e. $ev_1(p_{12}, \langle p, x \rangle) \simeq ev_2(p, x)$ for all $p,x$.

  Definition: $L_1$ and $L_2$ have the same "interpretability degree" if each interprets the other.

  Definition: $(P,ev)$ is total if for all $p \in P$, the function $x \mapsto ev(p,x)$ is total.

My question is:

  Question: What is known about the poset of interpretability degrees?

  For example, is it a lattice (probably not)? Are there minimal degrees strictly above the bottom? Are there maximal degrees strictly below Turing-universal? Is every finite/countable/blah poset a sub-poset of this one? Is there a non-Turing-universal (and, necessarily, non-total) least upper bound on the total languages? etc.

  I'd also be interested in the same questions but where we now require the interpreters to be efficient - that is, to preserve the Turing-machine time and space complexity up to polynomial factors.

Results, references, and keywords are all appreciated. (If there end up being lots of answer this may become a community wiki, but I don't anticipate that.)

Answers I already know: Turing-universal is the unique top element of this poset. The smallest set of functions containing successor, diagonal, and closed under composition is the unique bottom element (one can easily cook up a programming language according to the above definition which only computes such functions). Andrej Bauer's answer to another question shows that no total language interprets all total languages, and further that there are strictly increasing infinite chains, even amongst the total languages.


texts: Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?

texts:
Getting Started

Consider a parameterized problem $F$.  We use $n$ to denote the input size and $k$ to denote the parameter.  Consider the fixed levels of $F$ which we denote by $\{F_k\}_{k\in\mathbb{N}}$.

Definitions

We say that $F$ is in non-uniform $FPT$ if there exists a constant $c$, a function $f(k)$, and a family of algorithms $\{A_k\}_{k\in\mathbb{N}}$ such that for every $k$, $A_k$ solves $F_k$ in $O(f(k) * n^c)$ time.

We say that $F$ is in uniform $FPT$ if there exists a constant $c$ and a function $f(k)$ such that there exists a parameterized algorithm that solves $F$ in $O(f(k) * n^c)$ time.

Remark: One could construct unnatural examples of paramterized problems that are in non-uniform $FPT$, but are not in uniform $FPT$.  For example, take an undecidable language and define the parameter $k$ to be the input length.

Question

Does there exist a natural parameterized problem $F$ that is proven to be non-uniform $FPT$ and suspected (yet not proven) to be uniform $FPT$?

A More High-level Question

Does uniform vs non-uniform parameterized complexity have any relationship to uniform vs non-uniform circuit complexity?


texts: Generating a random connected bipartite graph

texts:
A (n, m, k)-bipartite graph is a bipartite graphs with:

independent sets of size $\{n, m\}$
a total of $k \geq n+m-1$ edges

We want an algorithm to generate a (n, m, k)-bipartite selected uniformly at random in the set of all (n, m, k)-bipartite graphs. Ideally the algorithm should be in O(k) but any suggestion is welcome (other than picking a random bipartite with {n,m} nodes and k edges graph until its connected).

For now the only algorithm I have in mind doesn't achieve uniform sampling:

The idea is to first create a connected bipartite graph with the minimum number of edges by iteratively picking isolated nodes and connected them to the other independent set of the bipartite graph. For that we will create two sets N and M and create a first random edge connecting N to M. Then we will pick a random isolated node (from either N or M) and connected it to a random non-isolated node from the other set. Once we don't have any more isolated node we will have exactly n+m-1 edges, we will thus need to add k-(n+m-1) additional edges to the graph to match the original constraints. To add these last edges we simply pick random pairs of nodes from NxM.

Here is the (python) code corresponding to that algorithm

import networkx as nx
import random

random.seed(0)

def biased_random_connected_bipartite(n, m, k):
  G = nx.Graph()

  # These will be the two components of the bipartite graph
  N = set(range(n))
  M = set(range(n, n+m))
  G.add_nodes_from(N)
  G.add_nodes_from(M)

  # Create a first random edge
  u0 = random.choice(tuple(N))
  v0 = random.choice(tuple(M))
  G.add_edge(u0, v0)

  isolated_N = set(N-{u0})
  isolated_M = set(M-{v0})
  while isolated_N and isolated_M:
    # Pick any isolated node:
    isolated_nodes = isolated_N|isolated_M
    u = random.choice(tuple(isolated_nodes))

    # And connected it to the existing connected graph:
    if u in isolated_N:
      v = random.choice(tuple(M-isolated_M))
      G.add_edge(u, v)
      isolated_N.remove(u)
    else:
      v = random.choice(tuple(N-isolated_N))
      G.add_edge(u, v)
      isolated_M.remove(u)

  # Add missing edges
  for i in range(k-len(G.edges())):
    u = random.choice(tuple(N))
    v = random.choice(tuple(M))
    G.add_edge(u, v)

  return G

B = biased_random_connected_bipartite(5, 6, 11)

The bias comes from the correlation between the node degrees and the time at which they have been added to the connected component. For example both nodes u0 and v0 will tend to have higher degree as they will be potential candidates for the $n+m-2$ remaining edges we will add to make the graph connected. The last node added in this same process will always have degree 1 before we start adding the $k-(n+m-1)$ additional edges.

Is there a know result for that? Or any existing result that may help?

edit I found a slightly better solution (smaller bias):

Generate a random (n, m, k)-bipartite graph (picking k random pairs)
While the graph is not connected:

pick a random edge (u, v) outside the largest connected component
connect u and v to the main connected component

This is a simpler algorithm, and my gut feeling is that it's better than the other as we only have a bias on the redirected edges (which is at most n+m-2). Which means that in the worst case the bias is still slightly less important than in the first solution.


texts: Probabilistic (randomized) algorithms before "modern" computer science appeared

texts:
Edit: I choice the answer with highest score by December 06, 2012.

This is a soft question.

The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?

In this wiki entry, Rabin's algorithm for the closest pair problem in computational geometry was given as the first randomized algorithm (year???). Lipton introduced Rabin's algorithm as the start of the modern era of random algorithms here, but not as the first one. I also know many algorithms for probabilistic finite automata (a very simple computational model) discovered during 1960s.

Do you know any probabilistic/randomized algorithms (or method) even before 1960s?

or

Which finding can be seen as the first probabilistic/randomized algorithm?


texts: Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?

texts:
There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum algorithm. I understand that the advantage of quantum annealing as opposed to classical simulated annealing is that quantum annealing allows the particle/search point to tunnel through high barriers with probability as a function of barrier width, instead of having to climb all the way over the barrier (which in some cases wouldn't be possible because there wouldn't be enough energy). This is my understanding from here: http://en.wikipedia.org/wiki/Quantum_annealing

If quantum annealing is better than simulated annealing in this fundamental way, would it not be faster to implement QA instead of SA or GA's for solving optimization problems on a classical computer? If so, why aren't people using it? Or are they, and I'm just unaware (in which case I'd love to see references)?

D-Wave seems to be banking on the practicality of their quantum computer, not so much insane accuracy or other more "scientific" pursuits. If it just so happens that D-Wave's computers aren't really quantum, shouldn't we be able to find a fast classically implemented quantum annealing algorithm to compete with the quantumly implemented version also?


texts: Multiplication of circulant matrices with a diagonal matrix

texts:
Let $A_{i}$, $B_{i}$ be a sequence of circulant matrices of size $n \times n$.
We know that $\sum_{i=1}^{n}A_{i}B_{i}$ can be calculated in quadratic time (use FFT to diagonalize and add the diagonal matrices and apply IFFT).
Supposing $D$ is an arbitrary diagonal matrix (for simplicity, let $r$ be $n$th root of unity and consider the diagonal elements as all distinct powers less than $n$ of $r$).
What is the complexity of $\sum_{i=1}^{n}A_{i}DB_{i}$? I suspect it to be quadratic since I am including the same diagonal matrix($O(n)$ terms) in each term.
Consider $R$ a circulant matrix of size $n \times n$ with first row made of distinct powers less than $n$ of $r$. Let $X_{i}$ and $Y_{i}$ for $i=1\rightarrow n$ be full-rank diagonal matrices.
What is the complexity of $\sum_{i=1}^{n}X_{i}RY_{i}$? Again I suspect this to be quadratic.
The matrices $D$ and $R$ that are defined with respect to $r$ is artificial. I am looking for the case of general diagonal $D$ and general full-rank circulant $R$.


texts: Is there a gap amplification type of result for the Graph Isomorphism Problem?

texts:
Suppose $G_1$ and $G_2$ are two undirected graphs on vertex set $\{1, \dotsc, n\}$. The graphs are isomorphic if and only if there is a permutation $\Pi$ such that $G_1 = \Pi(G_2)$, or more formally, if there is a permutation $\Pi$ such that $(i,j)$ is an edge in $G_1$ if and only if $(\Pi(i),\Pi(j))$ is an edge in $G_2$. The Graph Isomorphism Problem is the problem of deciding whether two given graphs are isomorphic.

Is there an operation on graphs that produces "gap amplification" in the style of Dinur's proof of the PCP Theorem? In other words, is there a polynomial time computable transformation from $(G_1,G_2)$ to $(G'_1,G'_2)$ such that

if $G_1$ and $G_2$ are isomorphic, then $G'_1$ and $G'_2$ are also isomorphic, and
if $G_1$ and $G_2$ are not isomorphic, then for each permutation $\Pi$, the graph $G'_1$ is "$\epsilon$-far" from $\Pi(G'_2)$ for some small constant $\epsilon$, where $\epsilon$-far means that if we choose $(i,j)$ uniformly at random, then with probability $\epsilon$ either

$(i,j)$ is an edge of $G'_1$ and $(\Pi(i),\Pi(j))$ is not an edge of $G'_2$, or
$(i,j)$ is not an edge of $G'_1$ and $(\Pi(i),\Pi(j))$ is an edge of $G'_2$.


texts: Bound for the spectral norm of a boolean function

texts:
As we know that the upper bound for the spectral norm of a Boolean function on $n$ variables is $2^{n/2}$.
Is it possible to improve this bound..?

Can somebody provide me an example of a Boolean function whose spectral norm is more than the degree of the Fourier expansion of $f$


texts:
Consider Context-Free Grammars with rules of the form $S\to\epsilon$
or $A\to aB | Ba|a$,
meaning that any nonterminal other than $S$ can be replaced by a terminal, or by a pair of letters exactly one of which is nonterminal (and the other one terminal). What class of languages do such grammars generate? Certainly the regular ones, but also $a^n b^n$, via the rules $S\to\epsilon|aB$, $B\to b|Ab$, $A\to a|aB$. Short of a full characterization, I conjecture that these grammars do not generate the full CFL language family, and would be curious to see a proof.


texts:
I have been working on a new approach for a subset sum exact solver, and the current state provides an algorithm operating on $O{n/2 \choose n/4}$, demonstrating as well the hardest target value is not $\approx \frac{sum(S)}{2}$ but $\approx\frac{sum(S)}{4}$ for dense instances ($d \approx 1$) in all cases.

I asked several people about their opinion and I got mixed feedback, some people though it was worth it to keep pushing the approach before publishing (to try to obtain an improved result, given this is likely possible, then publish), while other people encouraged me to publish right away given the improvement over the $O(2^{\frac{n}{2}})$ approach and the new characterization for the hardest target values not demonstrated before in the available literature, then continue working looking to improve these results.

What are your suggestions/opinions?


texts:
An independence system is a pair $(I,\mathcal{I})$ where $I$ is a (usually finite) ground set and $\mathcal{I}$ is a collection of subsets of $I$ such that:

$\emptyset \in \mathcal{I}$, and
$I_1 \subset I_2 \in \mathcal{I}$ implies $I_1 \in \mathcal{I}$.

I am interested a related, dual notion, where we replace conditions 1 and 2 with:

$I \in \mathcal{I}$, and
$I_1 \supset I_2 \in \mathcal{I}$ implies $I_1 \in \mathcal{I}$.

It is clear that the pair $M=(I,\mathcal{I})$ is an independence system if and only if $\overline{M}=(I,\overline{\mathcal{I}})$ obeys the new conditions, where $\overline{\mathcal{I}} = \{ I\setminus I_0 : I_0 \in \mathcal{I} \}$. However, in my application it is much easier to work with the new conditions. Does this have a name?


texts: 3-color a cubic graph such that a MIS receives only two colors

texts:
According to Brooks'_theorem, a cubic graph (3-regular graph) containing no $K_4$ can be properly colored by three colors.  (Such a color can actually be found in linear time, which is not our primary concern.)

The questions are:

  Does there always exist a $3$-coloring that uses at most two colors for some maximum independent set of this graph?
  If the answer to question 1 is yes, can such a coloring be found in polynomial time?


texts: Does every NO instance of this promise problem have a local refutation?

texts:
For the following equivalent questions, you choose

whether-or-not the 3 variables in a clause must be distinct.

  Is there an integer $k$ such that for all 3-SAT formulas $\mathcal{F}$ without negations,

  if every  $(\leq k)$-clause sub-formula of $\mathcal{F}$ is 1-in-3 satisfiable then $\mathcal{F}$ is NAE-satisfiable?

  Equivalently, is there an integer $k$ such that for all

  3-SAT formulas $\mathcal{F}$ without negations, if $\mathcal{F}$ is not NAE-satisfiable then

  $\mathcal{F}$ has a  $(\leq k)$-clause sub-formula which is not 1-in-3 satisfiable?

(The Fano plane shows that $k$ can't be less than $7$.)

Motivation:    That is the "low end" of my question

on cs.stackexchange which was inspired by the

possibility of generalizing Schaefer's dichotomy theorem

to constraint satisfaction promise problems.

Specifically, for the simplest non-trivial promise-constraint,

with m being the size of the input set, I have neither managed to

find evidence for it being in  promisecoQIP[2]TIME$\hspace{-0.02 in}\big(\hspace{-0.04 in}$2o(m)$\hspace{-0.03 in}\big)\hspace{-0.04 in}\big/\hspace{-0.04 in}$q2o(m)

for infinitely many m, nor find evidence that it's not solvable

in coNTIME(O(1)) on essentially the most basic word RAM.

The former applies even when each variable occurs exactly twice

and "many m" gets replaced with "many even m" (since 3 is odd),

and the latter applies even when negative literals are allowed.


texts: Cutting edge of quantum error correction

texts:
Often I find myself needing to know the best error correcting code for a certain quantum scenario. For example, suppose my logical systems are 3-dimensional; then what's the most efficient encoding to resist at most 4 single-system errors? Of, suppose my logical systems are qubits; then what's the most efficient encoding to resist 5 single-qubit phase errors?

Presumably for many questions like this, the answers are known. Is there a good survey that gives the state-of-the-art?


texts: What is the best approximation for majority vote?

texts:
The majority vote operation comes up fairly often in fault-tolerance (and no doubt other places), where the function outputs a bit equal to which ever value appears most frequently in the value of the input bits. For simplicity, let's assume that whenever the input contains an equal number of bits in state 0 and state 1, it outputs 0.

This can be generalized to dits where there are more than 2 possibilities for each input by returning the value which occurs most frequently in the input, and in the case of a tie, returning the most frequent value which comes first lexicographically. Let's call this function "plurality vote".

I am interested in the output of such a function when each input has a fixed probability distribution (and the distribution is the same for each dit in the input). Specifically I care about the following question.

  Given a set $S=\{S_1, S_2,... ,S_n\}$, if the set is independently
  randomly sampled $N$ times, with probability $p_i$ of choosing the
  $i^{th}$ element of $S$ each time, for a fixed choice of $v$ what
  is the probability that the plurality vote of these outputs $S_v$?

Now, it is straight forward to calculate the exact answer to the above question as a sum over multinomial distributions. However, for my purposes, this is less than ideal, and a closed for approximation would be better. So my question is:

  What closed form approximation to the above probability has the
  tightest bound on the maximum distance from the exact value?


texts: I would like to ask if any one is aware of any results related to graph sparsification with bounded degrees? What I mean is anyone aware of graph sparsification results such that the resultant graph has bounded degree or at least an expected bounded degree?


texts: Humanifying computer-generated or computer assisted proofs

texts:
I remember reading a blog post displaying two versions of the same proof, one written by a human and the other by a machine, and asked the readers to tell which is which. Trying to google the post again, I can't seem to find the right keywords; most things just direct me to pages on computer generated or computer assisted proofs.

So I'm wondering if anyone else remembers such a post, or better yet, can direct me to some surveys or other materials on this subject.


texts:
I am a physicist  getting acquainted with one of the typical constructs for formulation and analysis of quantum algorithms (such as search problems or query complexity models), namely the "oracle function". As far as I understand, the oracle is a quantum black-box entity which computes the quantity to be analyzed. For example, in a qubit circuit formulation of a universal quantum computer the oracle is a deterministically computed Boolean function (correct me here if I'm wrong).

My question is:

Is quantum oracle implementation overhead counted when the
computational complexity of specific/well-known algorithms is compared to
alternatives?

Examples: deterministic Deutsch-Jozsa algorithm algorithm is exponentially faster than a classical counterpart only if the implementation of the unknown function $f$ requires less than $2^n$ classical "steps'' (including obtaining the guarantee that $f$ is either partial or constant). A stochastic example: collapse of the Grover algorithm speedup by a faulty oracle with an arbitrary small but constant failure probability.

Why do one care: Of course, one can alsways say that we look just at the non-oracle part or count only the number of queries etc. But any talk of quantum speedup has any chance of empirical relevance only if the overhead for implementation of all of the quantum parts of the construction is taken into account (if it is trivial/constant - no problem). In other words, I find it meaningful to compare quantum algorithms only after they are "fully compiled'' onto (at least hypothetically) realizable classically-driven hardware (e.g., universal set of gates plus as many qubits as one needs - but we'll count all the time & memory required).

My question is probably fairly typical for a non-expert, perhaps I just got confused by some less sophisticated introductions to quantum computation. Please deconfuse me.


texts: Cheap online selection with weighted comparisons

texts:
Suppose we want to find the smallest element of a set $S$, whose elements are indexed from $1$ to $n$.  We do not have access to the values of these elements, but we can compare any two elements of $S$ to see which one is smaller.  For any indices $i$ and $j$, there is an associated cost $C_{i,j}$ to compare the $i$th and $j$th elements of $S$.  The complete cost matrix $C_{i,j}$ is given to us in advance.

It is well known that $n-1$ comparisons are necessary and sufficient to find the smallest element of $S$.  However, since each comparison may have a different cost, we also want to keep the total cost of the comparisons as small as possible.

Is there an online algorithm that finds a sequence of comparisons of small total cost that finds the smallest element of $S$?  There is no online algorithm that finds the set of comparisons with minimum total cost, even when $n=3$, but perhaps there is an online algorithm with small competitive ratio.

In particular, does allowing the online algorithm to perform more than $n-1$ comparisons help?  Is it better to make several "extra" cheap comparisons instead of a few expensive comparisons?

I am especially interested in the case $C_{i,j} = 4^{d(i,j)}$, where $d$ is a discrete metric over the set $S$, and $0 \le d(i,j) \le k$, for all $i,j$.  An optimal online algorithm is still impossible in this setting.

Any references to similar problems are appreciated. I'm not searching for someone to solve my problem (although some ideas may help and are appreciated).  I just want to know if this problem is known. (I couldn't find anything.)


texts: Efficiently generate list of lightest intervals of a vector

texts:
Suppose a vector of size $n$ is given. The goal is to compute, $\forall i \in [n]$ the lightest interval of size $i$ (i.e. the interval whose sum is minimal).

For example, if we have the array:

1 1 0 0 1 2 1 0 0 0 1

For any length n, the minimal weight of $i$ length interval is:

interval size:              1  2  3  4  5  6  7  8  9  10 11
interval weight:            0  0  0  1  2  4  4  4  5  6  7

A naive algorithm would compute the shortest interval for each $i$ by itself, which results in a $O(n^2)$ time algorithm (keeping a sliding window of size $i$).

If we attempt a greedy "triangle" algorithm (start from the smallest number, expand by 1 each time), it fails, no matter if we try it botom-up or top-down:

A triangle algorithm would fail at 1 1 1 4 0 1 4

1 1 1 4 0 1 4 -> 0
1:0 :         0
2:1 :       4 0 > 0 1
3:5 :       4 0 1 = 0 1 4     BUT: 1 1 1 would be cheaper
4:6 :     1 4 0 1 < 4 0 1 4
5:7 :   1 1 4 0 1 < 1 4 0 1 4
6:8 : 1 1 1 4 0 1 < 1 1 4 0 1 4
7:12: 1 1 1 4 0 1 4

A reverse triangle algorithm would fail at 0 3 0 0 1 1

6:5: 0 3 0 0 1 1
5:4: 0 3 0 0 1 < 3 0 0 1 1
4:3: 0 3 0 0 < 3 0 0 1     BUT: 0 0 1 1 would be cheaper!
3:3: 0 3 0 == 3 0 0        BUT: 0 0 1 would be cheaper!
2:3: 0 3 == 3 0            BUT: 0 0 would be cheaper!
1:0: 0 < 3

Is it possible to find the interval weights in time $o(n^2)$? Is it possible to approximate them with lower runtime?


texts: Is there a way to extract the mean from a quantum superposition?

texts:
Given the superposed output of some quantum computation, suppose I want to know the mean state, i.e. the mean probability of each qubit sampled over all states.

The most obvious way to get this is repeated sampling. Obviously the more samples I take, the more accurately I will be able to estimate the mean.

Can this performance be improved upon? For example, if we take a Quantum Fourier Transform then the probability of state |0> is presumably the mean quantity we're after. Of course we can't guarantee measuring it, can we use something like Grover's algorithm to make its measurement extremely likely in $\sqrt{n}$ steps? And if we do, does that give better performance than the repeated sampling approach?


texts: Cheeger's inequality for directed graphs?

texts:
Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to directed graphs.

I state a possible generalization of Cheeger's inequality next. I am asking first about its correctness and secondly about whether any results along these lines are known or possible.

Let $G=(V,E)$ be a strongly connected directed graph. Consider the lazy random walk on $G$: this is the Markov chain whose transition probability matrix is $P_{ii} = 1/2$, $P_{ij}=1/d(i)$ if $(i,j) \in E$, where $d(i)$ is the out-degree of node $i$, and $P_{ij}=0$ otherwise.

Let $\pi$ be the unique left eigenvector corresponding to the eigenvalue $1$. Naturally, define $\pi(S) = \sum_{i \in S} \pi(i)$. Then the Cheeger constant of $P$ may be defined as  $$ h(P) = \min_{S \subset V} \frac{\sum_{i \in S, j \in S^c} \pi(i) P_{ij}}{\pi(S) \pi(S^c)}$$

Now if $G$ is undirected, the part of Cheeger's inequality I am interested in says that
$$ 1 - \lambda_1 \geq \Omega(h(P)^2)$$ where $\lambda_1$ is the largest eigenvalue of $P$ not equal to $1$.

In the directed case, the eigenvalues are no longer real. Nevertheless, one can define $\lambda$ to be the largest absolute value of any eigenvalue of $P$ not equal to $1$. Then, is it true that

$$ 1 - \lambda \geq \Omega (h(P)^2)$$
Alternatively, is any sort of result along these lines possible, perhaps with different definition of Cheeger constant?

The only reference I was able to find was Laplacians and the Cheeger inequality
for directed graphs, F. Chung, Annals of Combinatorics, 2005 (see also these lecture notes). However, the main results of that paper appear to be different than what I'm asking about. In particular, this paper seems to prove a form of Cheeger's inequality for a certain symmetric matrix, though the symmetric matrix is derived from a directed graph.


texts: Is it possible to unambiguously read back λ terms from interaction nets without node types?

texts:
A class of lambda terms can be evaluated using Lamping's abstract algorithm - that is, converting them to interaction nets and applying a set of rules. In order to get the result, you have to read back lambda terms from normalized interaction nets. For example, this net:

Reads back as λλ(1 0), that is, the church-number 1. This net:

Reads back as λλ(1 (1 (1 (1 0)))), the church-number 4. This net:

Reads back as λλ((1 λλ(1 0)) ((1 λλ(1 (1 0))) ((1 λλ(1 (1 (1 0)))) 0))), the church list of the numbres 1, 2 and 3. The readback procedure is trivial, but it uses the tag annotations: λ for a lambda node, @ for an application, R for root, e for garbage, D for fan (duplication). Now, suppose that we erased those tags:

Is it possible, from the configuration of the net alone, to infer the tags and thus readback the same lambda term without them?


texts: Is there an algorithm which gets incrementally "smarter" as it runs?

texts:
Mind the following program:

n = 0
best = 0
while (true):
  if (hash(n) > best):
     best = hash(n)
  ++n

If you leave this program running for 10 years, when you come back you'll have a n : N such that hash(n) is really, really big. If someone ever needed a proof of ∃ n : ℕ . hash(n) > K, you could probably sell/provide it to him. In a way, as time passed, that program became incrementally smarter at proving statements of this specific shape. In a way, you could say it was generating knowledge. Obviously, the knowledge generated by that program is very specific and probably useless.

What I want to know is: is there any "generic" way to convert "computing power" in "knowledge"? In other words, is there an algorithm that, as it evolves, becomes incrementally more efficient at proving arbitrary statements?

More formally, given a function A : {0,1}* -> Theorem -> Maybe Proof (which attempts to prove a theorem given some knowledge), and an heuristic H : {0,1}* -> A -> Number (which estimates the efficiency of A at proving arbitrary statements given a specific knowledge), does there exist a P : {0,1}* -> {0,1}* such that ∀ n : ℕ . ∀ m : ℕ . n > m ⇒ H(P^n(∅)) > H(P^m(∅))?


texts:
UP class is defined as such:

  The class of decision problems solvable by an NP machine such that

  If the answer is 'yes,' exactly one computation path accepts.

  If the answer is 'no,' all computation paths reject.

I'm trying to develop intuition for this definition.

Can one say that UP problems are the problems with unique solutions (e.g. prime factorisation)?

That seems close to the truth to me; but I can't help thinking that that would mean, since UP contains P and is contained in NP, that in case P = NP we'd get that P = UP = NP, so all problems in NP have unique solutions as well, which seems like something provably not true: P != NP by reductio ad absurdum. I hope there's not too much conjectures and hand-wavery in this paragraph for your taste.


texts: Shortest paths with structured dependence on earlier path

texts:
Perhaps this problem has been studied under a different guise. If so, I'd appreciate any pointers or terms that could help my search for related work.

Suppose we have an undirected simple graph $G=(V,E)$.  Given as input, we associate with each vertex $i$ a binary vector $\boldsymbol m_i$, where $|\boldsymbol m_i| = K$.  $\boldsymbol m_i[k]$ denotes the presence or absence of the $k$-th "marker" for $k \in \{1, ..., K\}$.  Each edge $(i,j)$ is associated with a function $e_{ij} : \{0,1\}^K \to \{0,1\}^K$.  $e_{ij}$ can be arbitrary, except that it must obey a sort of monotonicity property, where

If $m_B[k] \ge m_A[k]$ for all $k$, then $e_{ij}(\boldsymbol m_B)[k] \ge e_{ij}(\boldsymbol m_A)[k]$ for all $k$.

($e_{ij}$ can be different from $e_{ji}$.)

Starting at any vertex, I am interested in efficiently finding a short (or even any) simple path that collects all possible markers (or reporting that one does not exist), where the rules for collecting markers are as follows.  We maintain binary vector $\boldsymbol m$ denoting which markers that we hold (initially none, i.e. all 0), which is updated as we arrive at vertices and traverse edges.

When arriving at vertex $i$, collect all markers present at $i$ that we don't currently hold, i.e. $\boldsymbol m[k] := \max(\boldsymbol m[k], \boldsymbol m_i[k])$ for all $k$.
When traversing edge from $i$ to $j$, $\boldsymbol m := e_{ij}(\boldsymbol m)$.

For $K=1$, I believe this is a standard shortest paths problem.  How efficiently can it be solved for larger $K$?  (In practice, $K$ is around 2 to 100, $|V|$ is several hundred thousand, $|E|$ is 5 to 10 times $|V|$, and if paths exist, we expect them to be fairly short -- if it helps to fix a parameter $L$, which is the maximum path length, I'd be interested as well.)


texts: What are the general classes of measured systems

texts:
Imagine there is a class of system such that a measurement can be performed on an exemplar of this class, each measurement producing 1 bit of information. There are no limitation on how many times the experiment can invoke new instance of a class, and there are no limitations on how many times measurement can be performed. However there are only N types of measurements that can be done.

To clarify, here are some examples:

The measured systems are fixed 4-bit strings, all equal to “0100”; N = 4 and corresponds to measurements of each one of these bits
The measured system is 4 independent random bits. N = 4 and correspond to measurements of these random bits.
Measured system is a pair of entangled photons. N = 4 (there are 2 ways of measuring polarization of the first photon, and 2 ways of measurement the polarization of the second photon).

It’s clear that system as a black box looks the same, and whatever its inner workings, it can be judged by results obtained from the string of 0s and 1s obtained by the measurements. For example, in 1'st case 3 of 4 types of measurements would produce 0s for every instance of the system. In 2nd case all measurements would produce independent random bits. In the 3rd case there would also be random bits, however their distribution will violate Bell's inequality.

My question is – what are the most general classes of systems that can be described by this definition and discriminated by a limited pre-set amount of kinds of measurements?


texts: Remove edges from bipartite graph subject to degree restrictions

texts:
I have a bipartite graph $G$ with two sets of vertices $X$ and $Y$, where the degree of each vertex in $X$ is exactly $M$.

I now must remove some of the edges to ensure that, after removal, no vertex in $Y$ will have a degree larger than $1$.  I want to choose a way to remove the edges so that as many vertices in $X$ have degree at least $N$ (where $N$ is given to me, $N \le M$).

How can I find the maximum number of vertices in $X$ whose degree will be at least $N$ after removal, subject to the restriction that after removal no vertex in $Y$ should have degree larger than $1$?


texts: Existing technique to detect the clique and biclique cover the edges in a graph?

texts:
I wonder if there is any existing method to find the clique and biclique structures in a graph that can cover all the edges in it, and every edge belongs to exactly one of the cliques or bicliques found? I try to illustrate the idea in the figure above where the red edges belong to a biclique and the blue edges belong to a clique. All the edges in the graph are covered by the structures found.

The bicliques and cliques may have overlapping nodes.

The motivation of doing this is that in social networks, the biclique structure often corresponds to an influential group of persons that reach a common group of audiences, and such structural feature cannot be described by clique ...

As noted by Tom van der Zanden, a trivial solution would be to return all the edges of the graph.  I am trying to look for non trivial solutions such as those with minimum numbers of cliques and bicliques.

I wonder if anybody could point to some research in this area?


texts:
Suppose I have a list $\cal X$ of subsets of $\{1, ..., n\}$. I can do preprocessing on this list if necessary.  After this preprocessing, I am presented with another set $A \subseteq \{1, ..., n \}$. I want to identify any sets $B \in \mathcal X$ with $B \subseteq A$.

The obvious algorithm (without any preprocessing) takes time $O(n |\cal X|)$ -- you simply test $A$ against each $B \in \mathcal X$ separately. Is there anything better than this?

If it helps, you can assume that, for any $A$, the total number of matches $B \in \mathcal X$ is bounded by something like $O(1)$.


texts: From Extractors to Pseudorandom Generators?

texts:
Luca Trevisan showed how many constructions of pseudorandom generators can in fact be thought of as extractor constructions:

http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf

Is there a meaningful converse? I.e., can "natural" constructions of extractors be thought of as pseudorandom generators (PRG) constructions?

Extractor constructions seem to correspond to distributions over PRGs (such that any distinguisher won't succeed in distinguishing for almost all of them). Are there known applications for this?


texts: What can be the upper bound on the number of edges in a graph of $n$ vertices such that the graph does not have $K_4$ as a minor? Is there some relevant paper/book that I can look into it or it would be kind if some one can give intuition or some proof of some kind along with the bound.


texts: Complexity of finding vectors with optimal projection?

texts:
Input: a set $T$ of vectors $v_i=(x_i,y_i,z_i)$. Where $x_i,y_i,z_i$ are integers.

Output: a subset of vectors $v_1,v_2,...,v_n$ with vector addition $m=\sum v_i$ such that the projection of $m$ on each axis is maximized. (maximize the absolute value of the minimum projection along any axis)

  Is this problem efficiently solvable or is it NP-hard?

I'm not aware of results related to the 2D case.


texts: Why is Metric TSP's best possible achieved approximation ratio believed to be 4/3?

texts: Is it just that integrality gaps (LP/IP) for specific instances do not give more than 4/3? Thanks in priori.


texts: Complexity of reachability in Markov Chains

texts: Is anything known about the complexity of the following problem beyond membership in PTIME: Given a finite Markov chain $M$, an initial state $q_0$ and a set $F$ of (absorbing) states, is the probability of eventually reaching $F$ from $q_0$ greater than (or equal to) $\frac{1}{2}$?


texts: How can I find all numbers for which the XOR-sum is 0?

texts:
Given a list of integers $[a_1, a_2, \dots a_n]$, I want to find the number of $n$-tuples $(x_1,\dots,x_n)$ of integers such that the following three conditions are satisfied:

$x_1 \oplus x_2 \oplus \dots \oplus x_n = 0$.
$x_k \in [0,a_k]$ for each $k$.
$x_k=a_k$ for at least one $k$.

For instance, if the given list is [1,2,3], the answer is 4, and the specific solutions are

[0,2,2],
[1,0,1],
[1,1,0], and
[1,2,3].

A brute-force approach would just compute the Cartesian product of all $x_k$s or simply count through the whole number space starting with [0,0,0]. But how can I tackle this problem with a more sophisticated algorithm? What paradigm is a good choice? Dynamic programming? If I only consider condition 2, then I could think of denoting the sub-problem by

$$E[n,i]$$

Where $n$ defines the number of integers and $i$ the current slot. Also given the caps $[m_1, m_2, \dots,m_n]$ then the number of combinations could be computed with:

$$
\begin{align*}
  E[0,0] & = 0 \\
  E[0,i] & = 1 + m_i \\
  E[n,i] & = (1 + m_i) \cdot E[n, i-1] \\
  E[n,i] & = \text{invalid if } i + 1 > n
\end{align*}
$$

But how can I integrate the XOR constraint here?

On the other hand it seems this is a classical Constraint Satisfaction Problem which could be backtracked.


texts: Proving liveness-like property on an infinite tree

texts:
(Context: this is a problem from the middle of my dissertation work, abstracted into a more general problem. It's related to showing that some liveness properties hold, so perhaps work from something like CTL could apply.)

Say you have some tree of possibly infinite depth with root node $n_0$. (EDIT: the number of children per node is bounded, in case that helps.) There exists a special set $G$ of "good" nodes in the tree such that for every path from $n_0$ through the tree, that path contains a node in $G$ (although that node can be at any arbitrary depth).

Now, say there is some property $P$ on nodes of the tree such that $P(n)$ holds if and only if:

$n \in G$, or
for every child node $n'$ of $n$, $P(n')$ holds.

To prove: $P(n_0)$ holds

$P$ is practically another way of saying "every path has a node in $G$", so this seems almost trivial. However, I can't seem to formally prove it. An inductive proof seems like the way to go ("I expect my children to all be in P if I'm not in $G$ myself, so $P$ should hold for me"), but what to induct on? Something like "distance until the farthest "good" node" seems natural, but I'm not sure such a bound exists.

I'm reasonably sure this statement can be proved, so how to prove it? Is there indeed a bound on the farthest "good node", and if so, what is the argument that such a bound exists?


texts:
In this question - XOR-SAT to Horn-SAT reduction, two algorithms are described for reducing any XOR-SAT formula to a HORN-SAT formula.

My question is: say I limit the clauses of an XOR-SAT formula to exactly three variables per clause, is there a specific HORN-SAT formula that is equisatisfiable with each clause? If so, why not just replace all of the XOR clauses using that formula and instead go through the algorithms described in the question above?

As an example of what I mean, it is possible to reduce any 3SAT clause to an equisatisfiable XSAT clause as described here: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Exactly-1_3-satisfiability. Is the same possible for 3-XOR-SAT and HORN-SAT?


texts: Why is it difficult for $GCT$ to prove super quadratic lower bound?

texts:
We have a quadratic lower bound for the Permanent versus Determinant problem.
Why is it difficult for $GCT$ to improve it?


texts: Expected vs actual amount of information leaked by an $l$-bits message

texts:
Say we have a random variable $X$ that contains $k$ bits of information, and a  message $M = f(X)$ ($M$ is deterministic given $X$) that is $l$ bits long, where $l<k$. This implies $H(X) = k$ and $H(M) \le l$. Hence, we know on average $M$ leaks at most $l$ bits of information about $X$:

$H(X \mid M) = H(X) - I(X;M) \geq H(X) - H(M) \geq k - l$.

Now, can we get an upper bound to the probability (over $X$) that $M$ leaks $l + t$ bits of information about $X$, or $\Pr_{M}[H(X) - H(X \mid M = m) \geq l + t]$?

Obviously, we can use Markov inequality to bound the probability down to $\epsilon$ when $t = (1/\epsilon - 1)l$. But can we get something better, or even something as good as $2^{-t}$?

This sounds like something really basic when you want to talk about deterministic protocol on random input, but I cannot find material that talks about this... Many thanks in advance.


texts: Accomplished autodidact theoretical computer scientists

texts:
While it is very common to see successful autodidact musicians, painters, authors and architects - I am not familiar with any famous autodidacts in the field of TCS.
Are there any examples of an accomplished autodidact theoretical computer scientist (i.e., someone who published a significant paper, without ever going to grad school) ?


texts: What are some example problems for integer programming that are *not binary*

texts:
I'm interested in NP-hard problems that have a "nice" integer-programming formulation (quadratic or linear, with quadratic or linear constraints) that is not binary.

Of course it is always possible to replace integer-valued variables with a set of binary variables, but that's okay; I'm still interested in optimization problems whose "natural" formulation would be as an integer problem with more-than-binary integers.

Classical examples that come up when searching for integer programming are Set Cover and Max Cut, but those have a very straight-forward binary formulation... any pointers?

EDIT: Let me clarify natural through an example. Let's say we have some integer optimization problem where variables $x_i$ refer to how many units of product $i$ a factory should produce. This would be naturally formulated with integers other than 0 and 1. On the other hand, a knapsack combinatorial optimization problem would have an integer formulation where $x_i = 0, 1$ indicating whether or not item $i$ is chosen.

EDIT:
In the integer programming literature, binary does not refer to the overall representation of integers. It refers to the additional constraint that all variables be either 0 or 1, instead of arbitrary integers.


texts:
I am unable to prove whether the following problem is NP-Hard. It seems like a bin-packing or a partition problem, without being close enough to either of them (at least I do not see the reduction to them).

  Pooling-aware bin packing

  Consider 2 sets of non-negative numbers
  $$a=\{a_1,a_2,...,a_n\}\\b=\{b_1,b_2,...,b_n\}.$$ Which is the size of the smallest
  partition $P$ for the values $1$ to $n$ such that for every subset
  $S=\{ (a_i,b_i), (a_j,b_j),\ldots\}$ in the partition $$\max_{i\in S}a_i+\max_{j\in S}b_j\le1,\qquad \forall S\in P?$$  (I inherently
  assume feasibility, i.e.,  $ a_i+b_i\le1, i=1,...,n$)

  Simple instance:
  $$a=[0.3,0.5,0.4,0.9,0.7]\\ b=[0.6,0.3,0.6,0.1,0.2]$$

  Solution: we need 3 bins

  $[(0.9,0.1)]$
  $[(0.7,0.2),(0.5,0.3)]$
  $[(0.3,0.6),(0.4,0.6)]$

Note that maybe the most similar problem is the one in
Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-3 and discussed in
bin packing with overlapping objects.

Thoughts / similar problems / pointers?

PD: I want to apologize in advance if there is some issue with my question that I am unaware of, I am new here :)


texts: Why does predecessor(zero) need to be zero in Church numerals?

texts:
My question may be similar to: Why naturals instead of integers?, but it is more specific.

I am trying to learn lambda calculus. All the books make a big deal about how it was necessary that predecessor(zero) == zero and it was very tricky to get it right.

Why was that necessary? Can someone point me to some literature, or, better yet, give me a 30 sec explanation?

The only thing I can figure out is that this resulted in the naturals being closed under subtraction, but at a cost of having subtraction being a non one-to-one mapping from the natural numbers to themselves.

Thanks,

Charlie


texts:
Is it known if $\mathsf{NC^1}$ circuit evaluation problem is in $\mathsf{NC^1}$?
  How about $\mathsf{ALogTime}$ (uniform  $\mathsf{NC^1}$)?

We know that circuits of depth $k$ can be evaluated with circuits of depth $k+c$
where $c$ is a universal constant.
This means circuits of depth $k\lg n + o(\lg n)$ can be evaluated by
a circuit of depth $O(\lg n)$.
However $O(\lg n)$ doesn't contain a function that eventually dominates all functions in $O(\lg n)$.

We know that formula evaluation problem is in $\mathsf{ALogTime}$. Every $\mathsf{NC^1}$ circuit is equivalent to a Boolean formula. Can't we compute the extended connection representation of an equivalent Boolean formula from that of a given $\mathsf{NC^1}$ circuit in $\mathsf{ALogTime}$?

The extended connection representation of a circuit includes

the number of gates in the circuit,
the type of each gate, and
for every gate $g$ and every path $\pi$ in the DAG of the circuit the gate reached from $g$ following path $\pi$.

A path is given by a 0/1 sequence where 0 represents moving to the left parent and 1 represents moving to the right parent. Note that the number of paths is polynomial: the length of the paths is bounded by the depth of the circuit.


texts: First-order methods for solving SDP with geometric convergence or better

texts: Is there any first-order method that can solve general SDP in a geometric (linear) rate? or super-geometric (super-linear) rate?


texts: Alternative criterion for approximate maximum-weight perfect matching algorithms

texts:
I have asked this question in cs.stackeschange, and it was recommended to me that I asked it here.

Is there any literature on approximate maximum-weight perfect matchings where the approximation criterion is not a factor between the weight sum of the approximate and the optimal solutions, but instead the cardinality of the intersection of the edge sets of the approximate and the optimal solutions to the original maximum-weight perfect matching? The relevant graphs $G(V_1\cup V_2,E)$, $V_1\cap V_2=\varnothing$, are bipartite with non-negative possibly non-uniform edge weights and assumed to have perfect matchings. In particular, $|V_1| = |V_2|$.

To be clear:

Let $\mathcal{G}$ the the class of graphs $G$ as above, and let $\mathcal{E}_{G}$ be the set of maximum-weight perfect matchings of a $G\in\mathcal{G}$ with $|V_1| = N$. I seek an approximation algorithm which outputs a perfect matching $E''$ of $G$ satisfying $\max_{E'\in\mathcal{E}_{G}}|E''\cap E'|\geq(1-\epsilon)N$.

If it helps, I am willing to restrict the problem to the class of graphs for which $|\mathcal{E}_{G}|=1$, and therefore the potentially complicating term "$\max_{E'\in\mathcal{E}_{G}}$" can be removed from the problem definition. Randomized algorithms, in the sense that their output satisfies the required inequality with probability $1 - \delta$, for some $\delta > 0$, are also welcome.

I am familiar with Duan and Pettie's work, and most references therein.


texts:
Suppose that $G$ is a group with $|G|=n$. Suppose that $G$ is generated by elements $g_{1},\dots,g_{k}$. Let $\iota:G\rightarrow S_{2^{N}}$ be an injective group homomorphism such that $\iota(g_{i}):\{0,1\}^{N}\rightarrow\{0,1\}^{N}$ is computed by a reversible circuit consisting of $t_{i}$ reversible gates and where $t=t_{1}+\dots+t_{k}$ (for definiteness, assume that we can use any reversible gate on three bits). Then we shall say that $G$ has action complexity at most $t$.

Let $\delta_{n}$ be the maximum action complexity of a group $G$ with $|G|\leq n$. What are some bounds on $\delta_{n}$?

To obtain a trivial lower bound, we observe that if $|G|=n$, then
$|G|\leq|S_{2^{N}}|=(2^{N})!$ and without loss of generality, $t\geq N/3$, so
$t\geq\sqrt[1+\epsilon]{\log_{2}(\log_{2}(n))}$.

For a trivial upper bound, we can set $k\leq\log_{2}(n)$ and by Cayley's theorem, $G$ embeds into $S_{2^{N}}$ where $N=\lceil\log_{2}(n)\rceil$. Let $\iota:G\rightarrow S_{2^{N}}$ be an embedding. Now, the functions $\iota(g_{1}),...,\iota(g_{k})$ along with their inverses can each by computed by circuits of size $O(2^{N})=O(n)$ which gives an upper bound of
$\delta_{n}\leq O(n\cdot\log_{2}(n))$.

There is a large gap between the lower bounds and the upper bounds which I gave, so I am looking for better bounds for $\delta_{n}$.

Since this is CSTheory and not MathOverflow, I am interested in upper bounds which are not be obtained simply by finding smaller $r$ such that $G$ embeds in $S_{2^{r}}$ or by finding a smaller generating set for $G$.

Note: I could have formulated this question in terms of conventional Boolean circuits since if $f$ is a bijective function and both $f,f^{-1}$ can be computed by conventional circuits on $n$ gates, then $f$ can be computed by a reversible circuit on $O(n)$ gates.


texts:
I'm currently doing research in pseudorandomness, which involves a zoo of wonderful objects such as pseudorandom generators, randomness extractors, expander graphs, etc. I find it a fascinating topic, but one thing that drives me crazy is the glut of parameters that are involved. I understand that these objects are very complex, but I cannot help but break out into a sweat when I see "Let $G$ be a standard $(\alpha,V,\epsilon^2,k,\delta)$-pseudorandom widget...". Then I have to flip back in the paper or find another paper (which probably uses a different parameterization) and try to remember what all $\alpha,V,\epsilon,k$ and $\delta$ all meant.

It takes me quite a while to acquire a feeling for "good" parameter settings versus "bad" parameter settings, versus "natural" settings versus "easy" settings.

There's probably no magic bullet for this issue - but I was wondering if other people had some method of managing the "parameter explosion" so that it's easier to retain in memory for a longer period of time?

Thanks!


texts: Shortest distance/path between two households

texts:
If you wanted to know the shortest distance/path between two household addresses, which data structure(s) would you use to return the answer efficiently?

Say you are considering the set of all households in the United States (~100 million).

I am struggling to come up with a practical data structure considering the input size is so big. Dijkstra's seems too inefficient, but I'm guessing there is a way to preprocess the paths to make such a query possible.


texts: How to shrink a very large sparse matrix

texts:
Let $A$ be a matrix where $A \in \mathbb{F}^{n^s \times n^s}$ and $s>2$.
Assume $A$ is a sparse matrix where its rank  $\leq n$ and that there is only constant number of non-zero elements in each row.
The positions of the non-zero elements are predefined.

My question:  How can I fill a matrix of size $n \times n$ with an equal rank that each value is computed from the original matrix, where the complexity of that building would be $O(n^2)$?
(randomized algorithms can also be considered)


texts: Fast algorithm for linear context finding

texts:
I am trying to figure out a quick algorithm which solves the following problem.

For the rest of this question, assume $0\in\mathbb{N}$.

Denote by $\mathbb{R}^\mathbb{N}$ the set of all real sequences and by $\mathbb{N}^\mathbb{N}$ the set of all natural sequences. The algorithm should emulate a function $F:\mathbb{R}^\mathbb{N}\to\mathbb{N}^\mathbb{N}$ which can be defined as follows: given a real sequence $\{x_n\}$, $F(\{x_n\}) = \{y_n\}$, where $y_n$ is the maximum natural number for which both $y_n\le n$ and $x_{n-i} < x_n$ for all $0<i\le y_n$.

The emulation is of the following sense: the algorithm should receive floats, one by one, and for the float $x_n$ return the integer $y_n$. By quick I mean of linear speed. The naive algorithm is $O(n^2)$.

Note: there is a similar (?) algorithm which for a given positive integer $n$, receives a sequence of floats and returns for each the maximal value among the last $n$ received values, which is linear.


texts: Symmetry of optimal solutions to discrete optimization problems

texts:
Given a graph, say one wants to find the clique number, independence number, chromatic number, vertex cover number etc., one knows that a solution exists. However if the solution space has more than one solution, it is possible to talk about the symmetry of the solution space. For instance if there is only one solution, we have only the identity. However, if we have $n!$ solutions, the solution space has $S_n$ as symmetry group ($n$ is number of vertices on the graph).

Has there been any study on the symmetry of solution spaces to NP-complete problems atleast for classes of graphs?


texts: Efficient Shamir secret sharing reconstruction

texts:
Shamir's secret sharing scheme is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the original polynomial and subsequently the secret.

The regrouping process can be summarized as finding $p(0)$ in a polynomial knowing only the degree and pairs $(x_i, y_i)$ such that $p(x_i) = y_i$.

My question is: how do I do this efficiently? All implementations I've seen so far are $O(n^2)$ because they recompute the polynomial using Lagrange, with a few optimizations. Are there known faster ways?


texts:
Lately I have been looking around for a formal definition of a what a data structure is. I cannot find neither a paper, nor a book with such a definition. Even the famous "The Art of Computer Programming" is missing one. Even for just a linked data structure, e.g., binary search tree, I couldn't find one.

So, is there one? Perhaps a paper that is talking about it?

By formal definition I'm thinking of something like "A data structure is a tuple (Op, El, ..) where ...".


texts: Computing Size of Set with Particular Jacobi Symbol in Poly-Time

texts:
Background

Let $(\tfrac{a}{p})$ denote the Legendre symbol, defined for all integers $a$ and all odd primes $p$ by:

$(\tfrac{a}{p}) = \begin{cases}
\;\;\,0\mbox{ if } a \equiv 0 \pmod{p}
\\+1\mbox{ if }a \not\equiv 0\pmod{p} \mbox{ and for some integer }x, \;a\equiv x^2\pmod{p}
\\-1\mbox{ if there is no such } x. \end{cases}$

For any integer $a$ and any positive odd integer $n$ the Jacobi symbol is defined as the product of the Legendre symbols corresponding to the prime factors of $n$:

$(\frac{a}{n}) = (\frac{a}{p_1})^{\alpha_1}(\frac{a}{p_2})^{\alpha_2}\cdots (\frac{a}{p_k})^{\alpha_k}\mbox{ where } n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$

Fortunately, computing Jacobi symbol can be performed efficiently, without having to know the factorization of $n$.

Let $J_n^{+1} = \{a \in \mathbb{Z}_n^* \mid (\frac{a}{n}) = +1 \}$. Deciding membership in $J_n^{+1}$ is easy. The question is,

  Given an odd $n$, can we compute $\left|J_n^{+1}\right|$ in polynomial time?


texts: Finding out a set by intersection comparison

texts:
The following problem recently emerged from my research and I would like to ask if anyone knows if this problem was considered before or has heard of anything that might be related.

The general setting is the following. We are given $F$, a family of $t$-subsets of $\{1, 2, ..., n\}$, for some parameter $t$ (I am most interested in the case where $t=\lfloor n/2\rfloor$). There is an adversary who picks one set in $F$, denoted by $S$. Our job is to find what $S$ is. To do this, we are allowed to send any two sets in $F$ to the adversary, say $A$ and $B$ and the adversary will output $A$ if $|A\cap S|\geq |B\cap S|$ and $B$ if $|B\cap S|\geq |A\cap S|$. Note that if $|A\cap S|=|B\cap S|$ then the adversary can output either $A$ or $B$.

This problem can be solved trivially if we do not care how many queries we can ask since if we compare all pairs of sets, $S$ will be the only set that is always returned back from the adversary when we send a query $(S, B)$, for any $B\neq S$. However, our goal is to minimize the number of queries.

My goal is to show either that this problem can be solved using $O(poly(n))$ queries or that super-polynomial number of queries are required. I'm particularly interested in the case where $F$ is the set of all $\lfloor n/2\rfloor$-subsets of $\{1, ..., n\}$.

Any pointers to anything related would be appreciated.


texts: What are TCS conjectures that were proved for primes and small values but then turned out to be false?

texts:
Are there any conjectures in theoretical computer science that involve some parameter n and were proved for small values of n AND for primes but later turned out to be false?

In number theory such problems do exist, eg. as Aaron Meyerowitz points out the one about the coefficients of the cyclotomic polynomials. From TCS I only know examples like the Evasiveness Conjecture that are still unsettled.


texts: Algorithms for Interval Coloring with Capacities and Demands

texts:
We are given a graph $G = (V,E)$, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $I_i = [s_i,t_i]$ associated with it, where $s_i$ is the source and $t_i$ is the destination vertex. A set of requests $\mathcal{R}$ is called feasible, if the total demand of all requests in $\mathcal{R}$ passing through any edge $e$ does not exceed it's capacity, i.e., $\sum_{i:e \in R_i} d_i \le c_e$ for all $e \in E$. The goal is to partition the requests $R_1,\ldots,R_k$ into a number of sets such that each set is feasible and the total number of sets is minimized. This problem is called Interval Coloring with Capacities and Demands. This is because we can think of this as coloring the requests in such a manner so that requests in each color class are feasible and we want to minimize the number of colors. This can also be thought of as routing the requests in a feasible manner in a number of rounds. We consider the special case where $G$ is a path $(v_1,e_1,v_2,e_2,\ldots,e_{n-1},v_n)$.

What is the best approximation algorithm and hardness result known for this problem?


texts: Is there any known nontrivial result on QIP systems having a space-bounded verifier?

texts:
Is there any known nontrivial result on quantum interactive proof (QIP) systems having a space-bounded verifier?

The only paper I know is An application of quantum finite automata to interactive proof systems by Nishimura and Yamakami, in which a restricted 2QFA (two-way quantum finite automaton) model is used as a verifier and the following result is given:
$ \mathsf{QIP(2qfa,polytime)} \subseteq \mathsf{NP} $.

The motivation: I am preparing a paper containing some new results on space-bounded QIP systems and I want to be sure not missing any related known result!


texts: Relation between static Nash equlibria and dynamic equlibria

texts:
I am working on Normal form continuous games. I am not very familiar with dynamic game theory. I would like to know if there is any relation between static Nash equilibria and dynamic equilibria. If players play a certain game repeatedly or learn about the strategies of the players or if they follow certain dynamics, will they always converge to static Nash equilibria?

Is there any result between set of static Nash equilibria and dynamic equlibria (under some conditions)? Thanks in advance!


texts: count number of i such that ( (a*i+b) mod p) mod k == l

texts:
How to determine the number of $i$'s as fast as possible such that
$$1\le i \le L$ and $((ai+b)\mod p) \mod k = l$$
where $p$ is a prime number, $1\lt a, b\lt p-1$, and $l \lt k \lt L \lt p$.

This problem is related with the simple hash function
$$h(i) = ((ai+b)\mod p) \mod k$$

It seems that no related topics are discussed.


texts:
Consider the following undirected unweighted graph:

The green nodes separate the graph from the "external environment". Let's call them the graph hull. Now, a graph may have several hulls. Consider the following graph, where the green nodes constitute the hull:

If we rearrange the drawing in the following way (stretching the blue nodes to the outside) then the blue nodes become the hull:

Questions

Which is the fastest known algorithm to determine, given an undirected unweighted graph $G$, one of its hulls?
Is it possible that the number of hulls of a graph is superpolynomial in $|V|$?
Which is the fastest known algorithm to determine, given an undirected unweighted graph $G$, its minimum hull (i.e. the hull having the minimum number of vertices)?
Which is the fastest known algorithm to determine, given an undirected unweighted graph $G$, its maximum hull (i.e. the hull having the maximum number of vertices)?


texts: Who proved that a triangulation is 3-colourable implies its dual is bipartite

texts:
Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent:
(i) $G$ is 3-colourable
(ii) dual graph $G^*$ of $G$ is bipartite
and (iii) $G$ is Eulerian (i.e., every vertex has even degree).
I am interested in direct constructive proof of (i) $\iff$ (iii).
I would like to know who came up with this proof; esp. the proof of (i)$\implies$ (ii) given below
(i) $\implies$ (ii):
Suppose $G^*$ has a 3-face colouring $f$ with colours 1,2,3. Then, one can obtain a 2-colouring $f^*$ of $G^*$ by assigning colour +1 at a vertex $v$ if colours 1,2,3 appear clockwise on faces around $v$, and colour -1 at $v$ if 1,2,3 appear counterclockwise around $v$. So, $G^*$ is bipartite.
David Gale wrote to Shen giving a proof for (i) $\iff$ (iii) using homology theory (for triangulations of the sphere). In that letter, he proves that the mapping $f\to f^*$ given in the proof above is in fact a bijection (answer to this question explains why). Shen explains these in Mathematical Entertainments 20(3). I think that Gale's proof is different for the direction (i)$\implies (ii)$ (I am not sure, homology theory is Greek to me). I guess this proof should be known already because it is easier than the other direction. So, like I said, I would like to know who came up with this proof of (i)$\implies (ii)$ first.
Tsai and West's paper A new proof of 3-colorability of Eulerian triangulations refer to Lovász (Combinatorial Problems and Exercises, Problem number is 9.52 I suppose) and to Shen (reference given above).
Thank you.


texts: Nonlocal Games and Quantum Communication

texts:
I'm currently on the look out for some good reference material relating non-local games with beneficial aspects in quantum communication. For instance, I am aware that non-local games are good at lower bounding communication complexity as well as ensuring the security of QKD protocols.

What I'd like to know is, what are some of the big papers in regard to non-local games in quantum communication? Have there been any recent advancements in this field that have been exceptionally important? Are there any good video abstracts/lectures/presentations on the web that parallel this material?

Specifically finding some material that relates quantum communication and the CHSH game would be of specific interest to myself as well.

Any feedback on this for any one of my questions would be very much appreciated. Thanks!


texts: Number of "3-edge" triangles in a planar triangulation

texts:
I'm working on a triangle partitioning problem, and I'm trying to find and prove some properties of specific triangulations. The triangulations I'm dealing with are constrained delaunay triangulations in which every constraint is at least an edge (there are no single vertex constraints). Here is an example of such a triangulation:

The red lines represent edge constraints and the blue lines represent the unconstrained edges produced to create the triangulation. Notice how all vertices are in some edge constraint and that there will never be a vertex that is not connected to a constrained edge.

Now let us create a graph from this triangulation. Every triangle is a vertex, and edges are defined by $(v_1,v_2)$ where $v_1$ and $v_2$ are triangles that share an unconstrained edge. Notice that every vertex in this graph has degree at most 3.

My problem is that I want to say something about the number of 3 degree vertices in such a graph. I believe that at least half the vertices have less than degree 3 (just from a hunch) but I have no idea how to go about proving such a thing. What I'm asking is, what is the upper bound of the ratio degree 3 vertices to total vertices in a triangulation with these properties.

EDIT: I found this on the delaunay triangulation wikipedia page. Delaunay triangulations have $O(n^{d/2})$ simplicies, so a planar DT would have $O(n)$ triangles where $n$ is the number of vertices. This isn't the same as the set of constrained delaunay triangulations we're working with, but it seems to suggest that there could be a relationship degree-3 triangles and the total number of triangles.

http://www.sciencedirect.com/science/article/pii/092577219500013Y


texts: Lower bounds for noncommutative arithmetic circuits with exact division?

texts:
It is known that for general arithmetic circuits there is not much of a difference between standard model and one with division: any circuit with divisions that computes a polynomial can be simulated by a circuit without divisions with only polynomial blow-up.

However, in the non-commutative world, such a reduction is unknown. In fact, although exponential lower bounds are known for noncommutative formulas without division, proving lower bounds for noncommutative formulas with division is a big open question.

  Are we aware of lower bounds for noncommutative circuits with division, but where every gate computes a polynomial (and not just a rational function)?


texts: Fast approximation of (vertex) clique cover

texts:
I'm looking for a fast algorithm to find a clique cover on an undirected unweighted graph.

I'm not looking for an optimal solution (ie minimal number of cliques). Obviously I'm also not looking for a maximal solution (ie 1 clique per edge on an edge cover).

Any pointer towards a nice algorithm?


texts: Why are sub-normalized states studied in quantum computation?

texts: By basic postulates of QM, any state of a system is described by a normalised density operator. Now i fail to see why people study sub-normalized states ( e.g.: In  generalised fidelity etc). I'd be glad to know any physical interpretations of the same.


texts: Expected length of a self-avoiding random walk

texts:
We're given an arbitrary graph $G=(V,E)$. A self-avoiding random walk is a random walk such that in each step, a random neighbour which was not previously visited is chosen, if such one exists.
Clearly, this random walk can get stuck very quickly.

Now, the questions are 1) How can one compute (or even approximate) the expected walk time?
2) How can one choose the initial node that maximizes the walk time? For example, the lollipop graph
composed of a $3$-cycle over the set $\{1,2,3\}$ with a fourth node $4$ attached to node $1$.
The ratio of the expected walk times corresponding to choosing nodes $4$ and $1$ is $8/5$.

In trees the problem is trivial (average depth of leaves), but I don't see how to generalize that.

A sampling approach may do trick, as the naive bound on each sampled walk would be $n$. However, I suspect that some graph classes might be amenable to more efficient analyses.


texts:
I have a quick question that I'm stumped on. This is about constructing a decision tree using information gain (entropy). Let's say we have a dataset with two input attributes such that the information gain at the root of the tree for both attributes is zero, but this tree is still a decision tree of depth two (so two questions must be asked) that is consistent with the data.

How would this be constructed? I don't understand how I can get to a deeper depth without knowing have any information gain...


texts:
Consider the language $A=\{0^{k}1^{k}|k\geq0\}$ . On Sipser's book "Introduction to the Theory of Computation" an algorithm with running time $O(n\log n)$ is given, on single-tape TM. We also know that the set of languages that run in time $o(n\log n)$ is exactly the set of regular languages. Since $A$ is not a regular language, we can be sure that this is a strict lower bound, on a single-tape TM.

Therefore, if $f(x) = n\log n$ and $g(x) = o(f(x))$ , the existence of this language allows us to say that
$DTIME(g(x)) \subset DTIME(f(x))$ . Therefore:

By using the padding argument, couldn't we argue that for any time function $h(x) = \Omega(n\log n) $ the same result applies, i.e. that if $g(x) = o(h(x))$ then $DTIME(g(x)) \subset DTIME(h(x))$


texts:
CFL is the class of context-free languages; co-CFL the languages whose complements are context-free.  So CFL $\neq$ co-CFL.

Are there any nice characterizations or other basic facts about CFL $\cap$ co-CFL?

Two easy examples of the kind of fact I have in mind (but one would like more precise information):

DCFL $\subseteq$ CFL $\cap$ co-CFL.
pCFL $\subseteq$ CFL $\cap$ co-CFL, where pCFL is the class of CFLs that are permutation-closed.  It's closed under complement by Parikh's theorem and the fact that semilinear sets are definable in Presburger arithmetic.

Another related question: given a CFL $L$, it's undecidable whether $L \in$ DCFL.  Is the same true for pCFL?


texts: Is there any second-order logic finite satisfiability checker?

texts:
I know that there are implementations of first-order (finite) satisfiability checking that, given a finite set of axioms, searches for a finite model that satisfies them all.
I would like to ask whether there is a second-order logic (finite) satisfiability checker. Although, we can always write a (naive) algorithm that enumerates all possible finite interpretations and check whether they are a model or not, I would like to know if there is some implementation/research doing something more intelligent (instead of a blind search).


texts:
$1)$Can a $NP$-hard problem can have short certificates that can be verified in deterministic polynomial time for ALL but $\frac{1}{n}$ of the NO instances$?

$2)$ Can one concoct versions of NP complete problems $\Pi_1$ and $\Pi_2$ where probability $p=P(\Pi_2=NO|\Pi_1=YES)=P(\Pi_1=NO|\Pi_2=YES)$ is between $\frac{1}{2}+\epsilon$ and $1-\epsilon$? Then almost all the time short certificates are possible as in $1)$ if $p$ is closer to $1-\epsilon$.


texts: Finding a prime greater than a given bound

texts:
Is a deterministic polynomial-time algorithm known for the following problem:

Input: a natural number $n$ (in binary encoding)

Output: a prime number $p > n$.

(According to a list of open problems by Leonard Adleman, the problem was open in 1995.)


texts:
Usually to check password validity we used to create over given password it hash value and compare it with stored one. So password protection relies on strength of hashing function.

Could it be used another approach?

Let's say we have encryption algorithm (doesn't matter which one).
Let assume we have some array of predefined chars (for instance just digits)
Then generate random sequence of chars consisting predefined array (for instance just random sequence of digits)
Encrypt sequence with our algorithm with given password and store it somewhere in safe place (let's call it as saved value)
EDIT Also presumed that channel between client and server provides confidentiality and integrity

Now time to check password validity

Trying to decrypt saved value with probe password
If decryption successfull (meaning mathematically correct) check decrypted value to presence of predefined chars array. For instance if value consists only digits - we assume that password is correct. If decrypted value contains extra chars (except digits) - we would assume that password is incorrect.

Now question: what do you think about crypto-strength of this method?


texts: What are practically computable properties of Labelled Transition Systems?

texts: I found labelled transition systems to be a good model for my application, namely there is a paper about modeling use cases using LTSs. The question is, what can be easily proven about LTSs? I would like to re-use existing solutions to see if they are useful for my appication. I would like to know what properties of LTSs (and use cases) can be easily automatically proved, so I can decide, if there is a practical counterpart to the problem for use cases.


texts: The logic in derivation of virtual welfare

texts:
I am learning algorithmic game theory with the lecture notes posted by Tim Roughgarden. In lecture 5 it is proved that the problem of revenue (or profit) maximization in single-parameter environment is equivalent to maximizing something called "virtual welfare". I find it hard to understand the logic of the proof.

The very first step of the proof assumes that the payment rule is exactly in the form given by Myerson's lemma:
$$p_i(b_i,\mathbf{b}_{-i})=\int_0^{b_i}z\cdot x'_i(z,\mathbf{b}_i)\mathrm{dz}$$
where $x'_i(z,\mathbf{b}_i)$ is the derivative of the allocation rule $x'_i(z,\mathbf{b}_i)$. Then substitute the formula of payment into the profit object
$$\mathbb{E}\left[\sum_{i=1}^n\mathbf{p}(\mathbf{v})\right]$$
with some calculus the "virtual-welfare" magically shows up.

Then the author claims that maximizing the virtual welfare is equivalent to maximizing revenue, and if the corresponding allocation rule is monotone then we get a optimal DSIC mechanism. I have two questions about this:

The result relies on the assumption that the payment rule is given in the previous form. Why does it must be in that form? The proof feels like some circular reasoning. Is this because that we are restricted on searching only for DSIC mechanism?
Furthermore, sometimes there exists no monotone allocation rule to optimize the deduced virtual welfare, but does this also mean that there exists no monotone rule to optimize the original profit?


texts: What is the current state of the art in black-box grammar induction?

texts:
Grammar induction of Context Free Languages seems to be a very well researched field. I would like to know the current state of the art in inducing a Context Free Grammar (I am reading up Higuera's Grammatical Inference book, and looking through previous papers). What is the current bound on inducing a Context Free Grammar given unstructured (non parenthesized) input?

In particular, I would like to know the community's opinion on the paper by Bastani et al. Synthesizing Program Input Grammars. How it compares to existing work. Does it improve the algorithmic bounds?