texts: Optimal additive basis for decomposing/partitioning an integer as a sum of two integers

texts:
I'm going to be given a positive integer $z$, and I want to find an optimal basis $B$ that is good for $z$.

A basis $B$ is a multiset of positive integers.  The basis $B$ is considered good for $z$ if, for all non-negative integers $x,y$ such that $x+y=z$, we have the following: there exist multisets $B_x,B_y$ such that $x=\sum_{i \in B_x} i$, $y=\sum_{j \in B_y} j$, and $B_x \cup B_y \subseteq B$ (counting multiplicities: since these are multisets, the union operation adds up multiplicities of common elements, and the subset operation checks that multiplicities are pointwise smaller).  In other words, for every possible way of decomposing $z$ into a sum of two non-negative integers, each of those integers has to be expressible as a sum of elements from the basis, and there have to be enough basis elements in $B$ that you don't "run out" of elements.  When you use a basis element from $B$ to help express $x$, then it gets used up and you can't use that basis element for expressing $y$ (but if there's another copy in $B$, you're free to use the second copy for $y$).  I hope this makes sense.

The size of a basis $B$ is the number of elements in the multiset $B$ (counting multiplicities).  Smaller is better.  An optimal basis is one that is as small as possible.

My question: is there a feasible algorithm that, given $z$, computes an optimal basis $B$ that's good for $z$?  Or, an approximation algorithm that computes a basis that's reasonably close to optimal?  How small can we make the basis, on average?

A naive algorithm: one simple approach is to use the basis $B=\{1,1,2,2,4,4,8,8,\dots,2^k,2^k\}$ (for $k=\lfloor \lg z \rfloor$), so the basis contains two copies of each power of 2 smaller than $z$.  This is certainly good for $z$: we can express $x$ in binary, express $y$ in binary, and since we have two copies of each power of two, we won't run out of basis elements (even if some power of two is common to both binary expressions, that's OK, since we have two copies, one for $x$ and one for $y$).  Its size is approximately $2 \lg z$, so it is pretty small.  However, it is not optimal in general: this basis could be up to a factor of two larger than optimal, depending upon $z$.  Can you do better?

If it helps, in my application I would expect $z$ to be no larger than 1000 or so.


texts:
Polar decoding, according to Arikan's paper, can be decoded using a successive cancellation (SC) decoder, which is based on calculating the likelihood ratio, as seen in the image below.

How can I calculate equations 2 and 3 in the above image?
For example, assuming that $N=4$ and that we are using an AWGN channel with $\sigma=0.987$.


texts:
Solve for $\alpha$ if solution exists:
$\min(r_1, s_1 \alpha_1) + \min(r_2, s_2\alpha_1) = d_1$,
where $r_1,r_2,s_1,s_2,d_1$ are integer constants.

One way seems to be enumerate all possible outcomes, e.g.,
$r_1 + s_2\alpha_1 = d_1$. However, for a larger problem ($\sum_{i=1}^{k} \min(r_i,s_i\alpha)$), enumerating all options becomes exponential. Is there a better way to reformulate this problem?


texts: I'd like to know some good starting points (such as books, papers, lecture notes, etc.) on EXPTIME and EXPSPACE.  I'd like to learn more about these two topics, but I'm not sure what the best approach is....


texts: Maximum fractional packing of spanning trees.

texts:
Given a graph $G$, let $\{T_1,\ldots,T_k\}$ be a set of spanning trees with associated nonnegative weights $\{w_1,\ldots,w_k\}$ such that for every edge $e$, $\sum_{e\in T_i}w_i \leq 1$.  This is a fractional packing of spanning trees.

What is the maximum total weight of such a fractional packing, i.e. the maximum possible value of $\sum_{i=1}^kw_i$?

Can this be done in polynomial time?  If so, how?

(Note that the dual linear program asks for the minimum total edge weight such that every spanning tree receives weight at least one, so the dual is a minimum fractional edge cut problem.)


texts:
Consider the problem:
Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$.

This problem has a stunning solution running in $O(n)$ time and using 2 words of space only, attributed to Bob Floyd (at least by Knuth). The crux is to see this as a cycle finding problem (even though there is zero mention of a cycle let alone a graph), and employ the so called Tortoise and Hare algorithm (again, by Floyd).

This Tortoise and Hare algorithm was later used by Pollard in his factoring algorithm and somewhat recently extended here to solve the element distinctness problem using small space.

What are some other uses of this algorithm or extensions of it in TCS?


texts: A few questions about KSVD algorithm (dictionary learning) in a paper

texts:
To learn more about dictionary learning, I am currently trying to understand the concept in detail and to do so, I've found the following paper quite informative:

KSVD: an algorithm for designing overcomplete dictionaries for sparse representation

I have a few questions:

does the jth column of D (the overcomplete dictionary) correspond to the jth row of X or its transpose? (where $Y=DX$, Y is our data/signals; D is the dictionary; X is the sparse represenation of signals) So we do work on the transpose of X and not the matrix X itself? Why the notation $x_T ^K$ is used and not $x_K ^T$ ?
somewhere in the middle, they suggest to initialize $w_k$ which defines as follows:
$$w_k=\{i|1 \leq k \leq K: w_k(i) \neq 0\}$$
is defining this variable necessary in spite of the fact that we will
define another variable afterwards. $\Omega _k$ is a matrix of size
$N$ (number of signals (Y)) $\times |w_k|$ where it is one for
$w_k(i)$ and zero otherwise. why do  we need to define $w_k$?


texts: Looking for reference proving polynomial-time bounds for A* search under specific conditions

texts:
In the textbook "Artificial Intelligence - A Modern Approach" (Russel, Norvig), it mentions that a sufficient criteria for the A* search algorithm to complete in polynomial time is for the heuristic estimate h(n) and actual cost h*(n) to never be different by more than O(log(h*(n)), i.e.:

|h(n) - h*(n)| <= O(log(h*(n)))

The textbook mentions this result without proof. I am looking for the proof. Does anyone know where I can find this result proven?

Edit: I discovered that the proof is most likely available in Judea Pearl's textbook "Heuristics: Intelligent Search Strategies for Computer Problem Solving" (http://www.amazon.com/exec/obidos/ASIN/0201055945/acmorg-20) (I should have guessed that this was by Pearl). It appears that the textbook is not available except through pay walls.

I do not want anyone to violate copyright laws and post the content, but if someone can validate that the proof is in this text, I will happily go out and buy the textbook (or get it from the university library).


texts: Heuristic with worst-case exponential complexity

texts:
I have been working with some colleagues on a metaheuristic for an NP-Hard optimization problem. It is a genetic algorithm using a steady-state population replacement strategy (at each iteration a single new chromosome is created and used to replace an older one). The algorithm iterates until it fails to find a solution which is better than the current incumbent optimum for a pre-set number of consecutive iterations.
The algorithm has been tested on benchmark instances and proved empirically to be fast and effective, outperforming previous approaches.

We submitted our work to a journal and received rather favorable reviews. Among the modification requests, we were asked to state the time complexity of the procedure. While we have no difficulty to evaluate the (polynomial) complexity of a single iteration, we realized that, given the exponentially large solution space and our termination criterion, our algorithm could theoretically iterate an exponential number of times. Is this considered acceptable for a heuristic? After all, I was thinking, the same conclusion may even apply to a simple local search scheme, should it keep finding marginal improvements in its neighborhoods indefinitely without getting trapped in a local optimum.

Should we look into complexity analysis different from worst-case? Do you have references to works we may look into? Apologies if the question is too trivial, we are not "pure" computer scientists (although we submitted this work to a CS journal since we thought it was the right outlet for it).


texts: Any references for techniques in FPT reductions?

texts:
As everyone knows, Garey and Johnson's famous book (and many others) provides an excellent reference for reduction technique in classical setting. Are there any surveys or books on the
topic of reduction technique in parameterized algorithm, say the fpt reduction?


texts: What are bounded-treewidth circuits good for?

texts:
One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output of a gate having $a$ as input (or vice-versa); connect wires $a$ and $b$ whenever they are used as inputs to the same gate. Edit: one can equivalently define the treewidth of the circuit as that of the graph representing it; if we use associativity to rewite all AND and OR gates to have fan-in at most two, the treewidth according to either definition is the same up to a factor $3$.

There is at least one problem that is known to be untractable in general but tractable on Boolean circuits of bounded treewidth: given a probability for each of the input wires to be set to 0 or 1 (independently from the others), compute the probability that a certain output gate is 0 or 1. This is generally #P-hard by a reduction from e.g. #2SAT, but it can be solved in PTIME on circuits whose treewidth is assumed to be less than a constant, using the junction tree algorithm.

My question is to know whether there are other problems, beyond probabilistic computation, that are known to be intractable in general but tractable for bounded-treewidth circuts, or whose complexity can be described as a function of the circuit size and also of its treewidth. My question is not specific to the Boolean case; I am also interested in arithmetic circuits over other semirings. Do you see any such problems?


texts: Recent progress on the next-to-shortest-path problem for directed graphs?

texts:
In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem:

Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be vertices in $V(G)$. Let $p_1$ be a path of minimum weight from $u$ to $v$. Compute a simple path $p_2$ from $u$ to $v$ with $w(p_2) > w(p_1)$ and such that for any other path $p$ from $u$ to $v$ with $w(p) > w(p_1)$, we have $w(p) \ge w(p_2)$.

They prove that this problem is NP-hard. Their proof involves choosing a weight function that takes value $1$ on a certain edge and $0$ elsewhere, so it relies in a fundamental way on the possibility of there being edges of weight $0$.

Is anything known about whether the problem remains NP-hard when one restricts to unit-weight graphs, that is graphs for which $w(e) = 1$ for each $e \in E(G)$?


texts: Reference for fast algorithm for bottleneck shortest paths

texts:
I am looking for a good reference for bottleneck shortest paths.  Specifically, given vertices s and t in an undirected graph with edge weights, you want the shortest path from s to t, where the length of a path is the maximum edge on that path.  This can be solved in O(n+m) time by finding the median edge weight and (carefully) recursively deleting half the edges.

  Does anyone know a reference for
  this?


texts: Computing log of sum of positive integers

texts: As input, we are give $k$-bit approximation (after the decimal point) of $\log(a)$ and $\log(b)$ for positive integers $a$ and $b$, i.e, we are given $\alpha$ and $\beta$ (as binary strings) as input such that $(\log(a)-\alpha)\leq \frac{1}{2^k}$ and $(\log(b)-\beta)\leq \frac{1}{2^k}$. We need to compute $(k-c)$-bit approximation of $\log(a+b)$, i.e, we want to compute $\gamma$(as binary string) such that  $(\log(a+b)-\gamma)\leq \frac{1}{2^{k-c}}$. Here $c$ is some constant integer, you can choose it to be anything as long as running time complexity bound is satisfied. Required time complexity is $\mathrm{poly}(|\alpha|, |\beta|, k)$, here time complexity is defined as number of bit operations.  $|\alpha|, |\beta|$ denote the bit length of $\alpha$ and $\beta$ respectively.


texts: Solve a simple system of linear inequalities in natural numbers

texts:
I want to find a solution to a system of linear inequalities of the following form

\begin{aligned}
a_1 + b &\ge a_2 \\\
\vdots \\\
a_4 + c &\ge a_1
\end{aligned}

where $a_i \in \mathbb N \setminus \{0\}$ and $b,c \in \mathbb Z$. All inequalities consist of exactly two variables and one free factor. All $a_i$ appear as they are, and have no coefficient other than $1$.

The goal is to find a solution (perhaps more than one, but not necessarily), or declare the system as not having one. Such a solution would be vastly preferable to any linear programming ones.

I do remember some algorithm based on constructing a graph and then launching Floyd-Warshall algorithm could solve a similar problem, but I'm not sure.

EDIT: Problem expansion - how can I find such a solution that the number of distinct integers in the solution is maximized (the default Bellman-Ford behavior minimizes it)


texts: Is it possible to create an arbitrary $\textsf{NP}$-complete statement of chosen size $n$ and witness in polynomial time?

texts:
This questions came in my mind as I was reading the concept of hidden-bits of Feige, Lapidot and Shamir in "Multiple non-interactive zero knowledge proofs based on a single random string". There is one part about the construction of zero knowledge proofs of Hamiltonicity of directed graphs.

  Let $H$ be a randomly chosen Hamiltonian cycle on $n$ nodes. ... Assume now that P wants to prove $V$ the Hamiltonicity of some graph with $n$ nodes. ... Let $\pi$ be a permutation that maps H onto the Hamiltonian cycle of $G$.

I know that $\textsf{NP}$ is the class of problems, where its membership can be verified in polynomial-time. However, the sentence that $H$ is a randomly chosen Hamiltonian cycle on $n$ nodes looks very "easy". Either the computation of such a graph is easy, therefore it is in polynomial time or their idea was to choose some familiar instance of it.

Since, Hamiltonicity is NP-complete and assume it is easy to compute an arbritary instance of size $n$ with an associated witness, it is possible to create for every $\textsf{NP}$-complete problem an example instance in polynomial-time?

Another question which follows from this: If we rely on such a generated instances $s$ of a problem to prove some other statement, wouldn't the soundness of the proof be violated if $s$ is choosen "bad"?


texts: Counting the number of thick regions which overlap a square

texts:
Let $S$ be a unit square.
As a function of $\beta$, what is the maximum number of $\beta$-fat pairwise-disjoint regions with diameter at least 1 which can intersect $S$?

Below, we give a figure showing that for $\beta=1$, the maximum number is 7. What about for $\beta = 2, 3, \ldots, n$?

Recall the definition of fat for regions in the plane. Given a region $R$, let circle $C_1$ of radius $r_1$ be the largest circle contained in $R$, and let circle $C_2$ of radius $r_2$ be the smallest circle that contains $R$. The fatness of $R$ is given by $\frac{r_2}{r_1}$, and we say that $R$ is $\beta$-fat, for $\beta = \frac{r_2}{r_1}$.

For example, if $r_2 = r_1=\frac{1}{2}$, then the regions are unit circles, and there are at 7 circles with diameter at least 1 which can overlap $S$ without overlapping each other.
In the figure below, we have depicted a unit square and 7 unit circles which overlap the square.


texts: Edge and vertex fault tolerance in graphs

texts:
Suppose we are given two graphs $G$ and $H$, where $H$ is a subgraph of $G$. What is the maximum number $k$ such that if any $k$ edges are removed from $G$, $H$ still remains a subgraph of $G$? What about the same question when edges are replaced by vertices? A generalization is to consider weights on edges/vertices and ask for maximum weight edges/vertices. I want both a bound as well as an algorithm. This problem is NP-hard as subgraph isomorphism is a special case of it.

Any papers on this problem will be helpful.


texts: Difference between Stencil -structures and Cellular Automata Category-theoretically?

texts:
Definitions

  Stencil =
  "For a given point, a stencil is a pre-determined set of nearest
  neighbors (possibly including itself)."
  (source)

  Wikipedia's definition (source) =

It looks like CA (cellular automata) is a broader (and perhaps more sexy fuzzy populist) concept while the stencil (S) is more rigorous. Suppose a torus -topology in a grid and a simple structure where each state depends only on the next state (some transition rule, 4 neighbors but only next state matters). This I think is a Stencil, Cellular automaton, a grid, a mesh, easily described with Markov Chain -- and a structure. Now I am confused! So many different words for the same thing? Please, add references to quantify this concept, many authors seem to use different words for the same thing -- not sure what it is, some structure with function -definitions -- perhaps there exists some easy category-theoretic description for them?

If this is too elementary question, I would be happy about some reference covering definitions rigorously and doing some comparisons.

Perhaps related

Automatic Stencil Code Generation Ph.D. Thesis Proposal here. The author behind the last paper here, researching something about stencil things and a lot of perhaps related publications here, related to the last author.
Fey, Dietmar et al. (2010) Grid-Computing: Eine Basistechnologie für Computational Science. Page 439. (Source)
Complex Systems from the Perspective of Category
Theory: I. Functioning of the Adjunction Concept here


texts: How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

texts:
The exact phrasing of the title is due to Anand Kulkarni (who proposed this site be created). This question was asked as an example question, but I’m insanely curious. I know very little about algebraic geometry, and in fact also only have a cursory, undergraduate understanding of the obstacles at play in the P/poly versus NP question (non-relativizing, non-algebrazing, likely won’t be a natural proof).

What makes algebraic geometry seem like it can bypass these sorts of obstacles? Is it just field expert intuition or do we have a really good reason to believe the approach is fundamentally more powerful than previous approachs? What weaker results have this approach been able to achieve?


texts: Game semantics for coinductive predicates

texts:
Does anyone know of any work on game semantics for coinductive predicates?

A coinductive predicate is one where the predicate itself is called in the body of the predicate, and we are taking the meaning of the predicate to be the greatest fixed point of the underlying definition. Such a predicate will be defined over an infinite data structure, such as a stream or infinite tree or labelled transition system and so forth.

An overly simple example is the following (in Haskell):

data Cat = BlackCat | WhiteCat
data Stream a = Stream a (Stream a)

allBlacks :: Stream Cat -> Bool
allBlacks (Stream cat rest) = cat == BlackCat && allBlacks rest

I can define the stream of all black cats as:

blackCats :: Stream Cat
blackCats = Stream BlackCat blackCats

and use coinduction to prove:

allBlacks blackCats

One could think of a coinductive predicate as an infinite conjunction or disjunction, simply by imagining that it is unrolled completely. Game semantics in this setting would be straightforward: for an infinite conjunction, the Falsifier needs to select which conjunct to falsify in order to win the game; for an infinite disjunction, the Verifier needs to select which disjunct to satisfy in order to win the game.

There is, however, a natural order in 'evaluating' the coinductive predicate which is ignored when considering it as an infinite conjunction or disjunction, and I would like this ordering to be captured in the game semantics, namely that the game proceeds by playing each disjunct/conjunct in turn.

One additional problem I have is understanding which winning condition to use to capture the infinite nature of the predicate. Or to put it in lay persons terms: how do I know that there is no white cat in this supposed infinite stream of black cats––it could merely be after the point I stop looking?

additional example

Consider the following data type (again in Haskell):

data Tree a = Tree (a -> Maybe (Tree a))

Tree A corresponds to the greatest fixed point of the functor $F(X) = (X+1)^A$.

Now assume that there is some relation $R:\subseteq A\times A$. This has no intrinsic meaning, and is just used to formulate the following coinductive predicate. Thinking of $R$ as $\le$ is sufficient.

Consider the following coinductive predicate $covers\subseteq$Tree A$\times$Tree A (defined corecursively):

  $\mathit{covers}(\alpha,\beta) = $
  $\qquad \forall a\in A\mbox{ if } \alpha(a)\neq\bot \mbox{ then } \exists b\in B
  \mbox{ such that } a R b \mbox{ and } \beta(b)\neq\bot \mbox{ and } \mathit{covers}(\alpha(a),\beta(b))$.

I'm looking for a formalism for expressing such predicates in terms of game-theoretic semantics. A link to existing work would be greatly appreciated. The main thing I'm having trouble getting my head around is the winning condition (as discussed in some of the comments below). Even though the game goes forever, infinite plays do not constitute a draw.


texts: On aB-trees and its practical implementation

texts:
I'm reading the paper Succincter by M. Patrascu (link).

It introduces on page 7 the aB-tree. This is a regular B-ary tree that represents an array of values. It stores the element of the array in the leaves. Every node is augmented with a value from some alphabet. The value of a leaf is a function of its array element, and the value of an internal node is a function A of the values of its B children, and the size of the subtree.

The query algorithm examines the values of the root’s children, decides which child to recurse to, examines all values of that node’s children, recurses to one of them, etc. When a leaf is examined, the algorithm outputs the query answer. We assume the query algorithm spends constant time per node, if all values of the children are given packed in a word.

The part I'm having difficulties with is the following: The queries can be solved in constant time per node if the values of all children are given packed in a word. This uses very standard ideas from word-level parallelism that we omit.

Could somebody please point how does word-level parallelism achieve this ?

Also, is there a practical implementation of this structure (and its application to succinct rank/select bitvectors) ?

Thanks in advance.


texts: Are there "small" machines which can efficiently match regular expressions?

texts:
It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially exponentially larger. Furthermore, given a string $s$ and a regular expression $r$, the NFA can test membership in time proportional to $|s| \cdot |r|$, and the DFA can test membership in time proportional to $|s|$. The slowdown for the NFA arises from the fact that essentially we need to track the sets of possible states the automaton could be in, and the exponentially blowup for the DFA arises from the fact that its states are elements of the powerset of the states of the NFA.

Is it possible to efficiently (ie, in time better than $O(|r| \cdot |s|)$, and space better than $O(2^{|r|})$) recognize regular expressions, if we allow using more powerful machines than finite automata? (For example, are there succinctness gains to recognizing regular languages with pushdown automata, or counter machines?)


texts:
I asked this question on SO  on April 7 and added a bounty which has now expired but no poly time solution has been found yet.

I am trying to write code to detect if a matrix is a permutation of a Hankel matrix.  Here is the spec.

Input: An n by n matrix M whose entries are 1 or 0.

Output: A permutation of the rows and columns of M so that M is a Hankel matrix if that is possible. A Hankel matrix has constant skew-diagonals (positive sloping diagonals).

When I say a permutation, I mean we can apply one permutation to the order of the rows and a possibly different one to the columns.

A very nice $O(n^2)$ time algorithm is known for this problem if we only allow permutation of the order of rows.

Peter de Rivaz pointed out this paper as a possible route to proving NP-hardness but I haven't managed to get that to work.


texts:
Background: Transaction processing has been a traditional research topic in database theory.
Nowadays distributed transactions are popularized by the large-scale distributed storage systems which typically involve data partition (also called sharding) and data replication.

What are the major research issues in distributed transactions?
Are there well-known theories and solutions which need (theoretical) improvement?

Any references are appreciated.


texts: Is it to solid to conclude APX-complete after showing a problem cannot be approximated better than 1.5 and also develop a 2-approximation algorithm

texts: I know the canonical way to show APX-Complete is to give an L-reduction from an already-known APX-complete problem. If I have used gap-preserving reduction to show a problem cannot be approximated better than 1.5 unless P=NP. On the other hand, I have also developed an algorithm to approximate this problem by 2. Actually, I use the relaxed LP to solve the problem, and a rounding method could lead to a 2-approximation. I'd like to know if it is enough to conclude this problem is APX-hard and APX-complete. Because gap-preserving reduction shows it is at least APX-hard, which does not allow PTAS, and meanwhile, my 2-approximation proves it can be approximated by a constant.  Is it enough to draw an APX-complete conclusion directly without additional giving an L-reduction? Thanks a lot for your explanation


texts: Exercises of polynomial and turing reductions

texts:
I'm following a graduated course in theoretical computer sicence. A good part the theory we see in this course has to do with polynomial and Turing reductions of NP problem (to prove NP-completeness), mostly including gadgets. However the course has very few exercises to practice ourselves and the teacher is reluctant to give us some more. Is there any resources, web or books, that could fill this gap for me? I'm talking about problems and possibly their solutions and some explanation about the process of finding the reduction.

Thanks.


texts: Is the following optimization problem NP-hard?

texts:
Set S, which is an non-empty finite subset of $\{ (i,j) : i, j \in N \land i \neq j \}$, is given. E.g. $S=\{(1,3), (2,3), (1,4), (2,4), (3,1), (3,4)\}$ . For each element $(i,j)$, we have weight $w_{ij}=c(i)>0$, where $c$ is some benefit function, and a binary decision variable $x_{ij}$. The optimization problem is defined as follows:

$$\text{maximize} \sum_{(i,j)\in S} w_{ij}x_{ij} $$
$$\text{s.t.} x_{ij}+x_{ik} \le 1 $$
$$x_{ij}+x_{jk} \le 1 $$

Note this problem is not the Maximum Weighted  Matching problem as edges that share the same end point are allowed.


texts: Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

texts:
I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix.

If any one knows if this problem is of a different complexity class, that would be just as helpful.

EDIT: I've tagged this question with Linear Programming, because I have a strong suspicion that if such a solution existed, it would be a kind of linear programming algorithm. The reason I believe this is because the extreme points of the Birkhoff polytope are precisely the permutation matrices. If you could then find an objective function which is either maximized or minimized only on the vertices of the Birkhoff polytope, you could constrain your function to the intersection of the polytope and your vector subspace, then maximize it in polynomial time. If this value were a permutation matrix, you'd know the set contained a permutation. Those are my thoughts on the subject.

EDIT 2: After some more thought, it seems to me that the permutation matrices are precisely the elements of the Birkhoff Polytope with Euclidean norm $\sqrt{n}$, the we consider the Birkhoff polytope to be the convex hull of the $n \times n$ permutation matrices. Perhaps that could also be significant.

EDIT 3: I added the semidefinite programming tag, because after my previous comment, I'm beginning to think that a semidefinite programming solution may be possible since it is now a linearly constrained quadratic optimization algorithm.


texts: An oracle relative to which EXP(NP) = BPP

texts:
Whether or not $\mathbf{BPP} = \mathbf{EXP}^{\mathbf{NP}}$ is an open problem, although we believe the former is strictly contained in the other.  I guess, from the absence of the proof of the separation, that there should have been  a relativized result on this problem, namely, the existence of an oracle relative to which $\mathbf{BPP} = \mathbf{EXP}^{\mathbf{NP}}$.

Is there such a result in the literature indeed?


texts: When designing an explicitly parallel language, what built in functions should be parallelized?

texts: As stated by the title. Some examples that I would include would be map and conditionals. What other functions should be built in already parallel for users to expand on it?


texts: Graph isomorphism with equivalence relation on the vertex set

texts:
A colored graph can be described as tuple $(G,c)$ where $G$ is a graph and $c : V(G) \rightarrow \mathbb{N}$ is the coloring. Two colored graphs $(G,c)$ and $(H,d)$ are said to be isomorphic if there exists an isomorphism $\pi : V(G) \rightarrow V(H)$ such that the coloring is obeyed, i.e. $c(v) = d(\pi(v))$ for all $v \in V(G)$.

This notion captures the isomorphism of colored graphs in a very strict sense. Consider the case where you have two political maps of the same region but they use different color sets. If one asks if they are colored in the same fashion one would assume this to mean whether there exists a bijective mapping between the two color sets such that the colors of both maps coincide via this mapping. This notion can be formalized by describing colored graphs as tuple $(G,\sim)$ where $\sim$ is an equivalence relation on the vertex set of $G$. We can then say two such graphs $(G,\sim_1)$ and $(H,\sim_2)$ are isomorphic if there exists an isomorphism $\pi : V(G) \rightarrow V(H)$ such that for all pairs $v_1,v_2 \in V(G)$ it holds that
$$v_1 \sim_1 v_2 \text{ iff } \pi(v_1) \sim_2 \pi(v_2)$$

My question is whether this concept has been studied previously w.r.t. finding canonical forms etc. and if so under what name it is known?


texts: Reducing the bandwidth of non-symmetric matrix

texts: Is there an efficient algorithm to reduce the bandwidth of a directed graph's adjacency matrix? Something like the reverse Cuthill-McKee, but for non-symmetric matrices.


texts: Why do TCS papers have author names in alphabetical order of their surnames?

texts:
I am currently doing a Ph.D. in Theoretical Computer Science, and any research paper I encountered so far has the author's names in alphabetical order of their surnames.
For example consider the most fundamental book on algorithms: "Introduction to algorithms" by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein.
Also consider the book: "Parameterized Algorithms" by Marek Cygan, Fedor V. Fomin,
Lukasz Kowalik, Daniel Lokshtanov,
Dániel Marx, Marcin Pilipczuk,
Michal Pilipczuk and Saket Saurabh
Basically take any paper in the TCS domain, all follow this pattern. This pattern is not followed in other domains where the authorship is decided based on the individual contribution of the authors. In other words, a person having the most contribution to the paper is given the first authorship. Likewise, a person with less contribution would have his/her name appear later in the list of authors.
I consider this norm, fundamentally flawed. Can somebody provide a good reason as to why such a norm is followed in the TCS domain?


texts:
I have this confusion related to L1 and L2 svm. It is given in this paper that

The dual problem is given by

$$
min(\alpha) = 1/2*\alpha^T\hat Q\alpha - e^T\alpha
$$
subject to

$$
0 <= \alpha_i <= U
$$

$$
\hat Q = Q+D
$$
D is a diagonal matrix  and $Q_{ij}=y_iy_jx_i^Tx_j$. For L1 SVM U=C and $D_{ii}=0$. For L2 SVM U=inf and $D_{ii}=1/2C$

I didn't get what this U term is and why is in the case of L2 SVM U=inf and $D_{ii}=1/2C$. How was it derived?

This is how I tried to derive it but I think I am making certain mistake

$L(w,b,\zeta,\alpha,\gamma) = \frac{1}{2}||w||^2 + C\sum_i\zeta^2 - \sum_{i}\alpha_i(y^{(i)}(w^Tx^{(i) } +b)-1+\zeta_i) - \sum_{i}\gamma_i\zeta_i
$

Differentiating with respect to $w,\zeta$ and b

$w=\sum_i\alpha^{(i)}y^{(i)}x^{(i)}$

$\sum_i\alpha_iy^{(i)} = 0$

$2C\zeta_i = \alpha_i + \gamma_i$

Now when I substitute these values into the objective function I get

$-\frac{1}{2}||w||^2 + \sum_i\alpha_i-C\sum_i\zeta^2)$

I don't get the expression as given in the paper. I know I am pretty close but I think I am screwing up somewhere. Can anyone give some suggestion where I am wrong?


texts:
I was reading an abstract for a paper that gives a minimum number M of good agents that guarantees f-Byzantine gathering, if there are f Byzantine agents. It gives a lower bound of f+1 for strongly byzantine agents. It also says that:

"...we give deterministic gathering algorithms for at least 2f+1 good agents when the size of the network is known...".

There are two lower bounds to the number of good agents. What do those two lower bounds mean? If it was only one lower bound, it would have been clear.

The abstract is: Gathering Despite Mischief


texts: Maximize number of edges covered by an independent set of vertices

texts:
Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to finding if the graph is bipartite.

I am wondering if the following follow-up problem has a name, or has been studied.

If the graph does not have an independent vertex cover (i.e., all edges cannot be covered by an independent set), what is the maximum number of edges that can be covered by an independent subset of vertices, and how does one find such a subset? (an edge is counted if and only if it has (exactly) one endpoint connected to a vertex in the subset).

Thanks!


texts:
I'm wondering if there are some known sources of open TCS problems? I'm a junior studying math/CS and would like to know of some accessible problems that I could start thinking about!

Thanks so much!


texts: Is there any problem which is in AWPP but conjectured to be not in BQP?

texts:
Is there any known problem which is in $\mathsf{AWPP}$ but conjectured to be not in $\mathsf{BQP}$? What about relative to an oracle?

Is there any known problem in $\mathsf{MQ^2}$ which is conjectured to be not in $\mathsf{BQP}$?


texts: Are there any results on the following "generalized matching" problems?

texts:
Given a graph $G = (V, E)$, one can view a matching $M$ on the graph as a partition of $V$ into vertex sets $S_{i, j}$ for $j \in \{1, 2\}$, where each $S_{i, j}$ induces a subgraph in $G$ isomorphic to $K_{j}$. That is, the edges in $M$ correspond to subgraphs isomorphic to $K_{2}$ and the leftover (unmatched) vertices correspond to subgraphs isomorphic to $K_{1}$. A matching algorithm can then be viewed as partitioning the vertex set into subsets which induce complete graphs, where we try to include as many $K_{2}$s as possible before resorting to $K_{1}$.

I'm interested in a generalization of this problem where $j$ is as large as possible (or perhaps some fixed j > 2, if there are nice results). In particular, I'd like an algorithm which first tries to find subsets of $V$ which induce subgraphs isomorphic to $K_{l}$, for $l$ as large as possible, and then $K_{l-1}$, etc.

Is there any work on problems like this?


texts: "Planar graph coloring is not self-reducible" is this about all $p$-relations encoding that problem?

texts:
I have a question about the paper "Planar graph coloring is not self-reducible" by Samir Khuller and Vijay Vazirani.

The final theorem in that paper states that "Planar Graph k-coloring is not self reducible, assuming NP!=P." In reading the proof of this (with $k =4$), it seems they actually prove a statement about a particular way to encode $(\text{Plane graph }G,\text{proper } 4\text{-coloring of }G)$ as a $p$-relation. In particular it's crucial to the reduction (Theorem 3.1) that the encoding is one where the vertices of the graph are given an ordering, and colorings are stored as a string of letters, with each letter describing the color of the $i$th vertex. I can imagine that most reasonable encodings look this way, but maybe there are some that don't.

Questions: Is there a way to interpret their theorem as proving that all encodings of the plane graph $4$-coloring problem as a $p$-relation are not self-reducible (assuming $P \not = NP$)? Is there a way to formalize the class of $p$-relations that they prove are not self-reducible? Maybe I'm misunderstanding something?


texts: Quantum Hardness of Finding Nash Equilibria

texts:
This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen.

Their main result is that the existence of indistinguishability obfuscation ($i\mathcal{O}$) and subexponentially-secure one-way functions implies that the $\mathsf{PPAD}$-complete search problem $\mathsf{End}$-$\mathsf{Of}$-$\mathsf{Line}$ (see for example, my old, old question) is worst-case hard for polynomial-time algorithms. Recall, of course, that the search problem of finding a Nash equilibrium in a normal form game of three or more players with specified utilities is (correct me if I'm wrong) known to be $\mathsf{PPAD}$-complete from a sequence of works beginning with the breakthrough of Daskalakis, Goldberg, and Papadimitriou. [Update: Finding two-player Nash equilibria is PPAD-complete -- Thanks Akshayaram Srinivasan for pointing this out.]

Independently, a (the?) major question in theoretical cryptography is to construct cryptographically-secure multilinear maps from $\underline{\rm standard}$ assumptions, in particular from the Learning with Errors ($\mathsf{LWE}$) assumption [Regev05]. (Any secure multilinear map, in turn, implies efficient indistinguishability obfuscation for $\mathsf{P/poly}$, landing us firmly far, far into the land of Cryptomania.)

However, this goal raises an interesting question: Suppose the Crypto community (sometime in the next year or few) jointly produces an appropriate reduction from the standard Learning with Errors assumption to the security of some indistinguishability obfuscation scheme for all circuits. Note that $\mathsf{LWE}$ is believed to be hard for quantum adversaries, formally by quantum reduction from approximating $\mathsf{GapSVP}$ to polynomial approximation ratios. In turn, $\mathsf{GapSVP}$ is "believed hard" for quantum computers itself, intuitively by $\mathsf{GapSVP}$'s "relation" to the Non-Abelian Hidden Subgroup Problem ($\mathsf{HSP}$) -- whereas Shor's algorithm solves the Abelian variant of $\mathsf{HSP}$. (If someone wants to independently fill me in more on the history/relationship between $\mathsf{GapSVP}$ and the Non-Abelian $\mathsf{HSP}$, great and thank you!)

The point is this: If indistinguishability obfuscation can be constructed for all circuits from $\mathsf{LWE}$ alone, then the resulting obfuscator will be quantum-secure. Intuitively, this seems to yield the following, simple and natural consequence of BPR's result/proof + the conjectured security of $i\mathcal{O}$ from $\mathsf{LWE}$ + the quantum-hardness of $\mathsf{LWE}$:

$\bullet$ Quantum computers cannot efficiently find Nash equilibria in the worst-case.

$\underline{\rm Question}:$ What, if any, consequence would the quantum hardness of finding Nash equilibria have? Is this an expected or unexpected outcome? Does anything overly weird occur, which we did not already observe simply from our implicit settling of $\mathsf{P}\ne\mathsf{NP}$ in order to allow a cryptographic assumption like $\mathsf{LWE}$ in the first place?


texts: Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

texts:
Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$.
For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic exptime oracle machine $M_2$ with access $M_2^{L_2}$ such that (a) $M_2$ may only make poly(n) length queries to $L_2$ (b) $M_2^{L_2}$ accepts iff $M_1^{L_1}$ accepts? (Note $M_1$ is capable of making exp(n) length queries to $L_1$ as it is an exponential time TM).
If the above is not true for a particular $L_2$, is it possible to find an $M_2$ and an $L_2\in$NEXP such that the above is true?
Obviously, there is always a polytime reduction from $L_1$ to $L_2$ as $L_2$ is NEXP-hard and $NP\subseteq NEXP$. However if the queries to $L_1$ have $exp(n)$ length, then under the polytime reduction the corresponding $L_2$ instances will now also have $exp(n)$ length. Hence, if $M_2$ is restricted to only $poly(n)$ length queries it's not clear $M_2^{L_2}$ can always make the necessary queries.
It does not seem unreasonable that given an $(M_1, L_1)$ pair, that $M_2^{L_2}$ can simulate $M_1^{L_1}$ and return the same output. If we have an NP language with $exp(n)$ input, a non-deterministic TM of runtime $O(exp(n))$ is capable of solving it. A NEXP machine also has an $exp(n)$ runtime but on an input of length $poly(n)$ and so might be capable of solving the exponential length NP instance.
Edit: I suppose this boils down to the question, if $EXP_{poly}^A$ is an exponential time oracle machine which is only allowed to make polynomial length queries to $A$, does the following hold: $EXP_{poly}^{NEXP} = EXP^{NP}$? The containment $EXP_{poly}^{NEXP} \subseteq EXP^{NP}$ seems to be straightforward to prove.


texts: Length bounded minimum cardinality cut in DAGs

texts:
Suppose I have a DAG with non-negative edge lengths. The problem is to compute the minimum number of edges which disconnects all paths of length L or less. We call this L-length bounded minimum cardinality cut problem on DAGs. It can naturally be extended to all directed graphs.

There can be a further generalization where removing an edge has some associated cost. The L-length bounded min cut problem is finding the set of edges with minimum total weight that gives a L-length bounded min-cut.

The L-length bounded min-cut problem is known to be NP hard. In fact for a given budget it is NP hard to decide if there exists a length bounded cut which does not exceed the budget for series parallel graphs [1]. So it holds for DAGs.

In this paper [1] it is showed that for directed graphs L-length bounded minimum cardinality cut itself is NP hard to have an 1.1377 approximation.

1) Does there exist NP hardness result for L-length bounded minimum cardinality cut on DAGs?

Or,

2) Is there any polynomial time, w.r.t. the number of edges and vertices, algorithm to construct the L-length bounded minimum cardinality cut on DAGs?

References:

1: Baier, Georg, et al. "Length-bounded cuts and flows." Automata, languages and programming. Springer Berlin Heidelberg, 2006. 679-690.


texts: Difference between PRAM and machine model in dynamic multithreading

texts:
In the first edition of Introduction to Algorithms (Cormen et al., MIT Press, 1990), the discussion of parallel algorithms is based on the PRAM model. In the second edition, paralellism has been eliminated, but in the third edition (Cormen et al., MIT Press, 2009), the topic is reintroduced, but with a dynamic threading model (based on Cilk). The chapters are very different, for sure, and the models seem to be, as well, at least superficially. But I'm wondering: What are the differences in the underlying computational model or abstract machine here?

Their underlying model is still a shared-memory RAM machine with multiple processors. How is this different from the PRAM? Is it the case, perhaps, that they are in fact using the same underlying model, but approaching it differently? The threading is certainly handled differently in the classic PRAM algorithms – more in line with static threading, where you manually schedule which threads/processes are to run on which processors, rather than simply express concurrency/potential parallelism and have some automatic scheduler use the processors available. But still: Are there more fundamental differences?

In their chapter notes (3rd ed., Chapter 27), Cormen et al. write, “Prior editions of this book included material on […] the PRAM (Parallel Random Access Machine) model.” This seems to indicate that they do not view their dynamic multithreading as being built on this model. Is this so? If so, what differences am I missing?


texts: Algorithms to synthesize optimal plans satisfying temporal logic constraints

texts:
I know how NuSMV can be applied on a model to check if certain temporal logic statements are satisfied, particularly LTL. I also know of the LTL to BA conversion routines available online.

I am concerned with specific types of temporal logic constraints such as:

this task can begin after this task
this task can happen only in this time interval

I think this falls in LTL, STL domain. I am mostly interested in generating motion and task plans based on temporal logic constraints. NuSMV only seems to check the validity of certain statements on a model. I am more interested in software tool or codes that can lead to optimal plan synthesis based on my specification of LTL etc.?

I know there are research papers that solve this problem. But i do not know the theory of LTL, BA, etc. in depth so it is difficult to understand what these papers are doing and then recreate the process. Can someone tell some seminal papers or simply written paper easy to understand that explain how to build such algorithms. Even relevant sections of book are useful. Most books on model checking solve the inverse that is given a model does it satisfy this LTL constraint? I am interested in creating a model that satisfies a given LTL, STL constraint etc.? This technology is lying around so if someone can even suggest me some source codes that tackle such problems that will be even more helpful. I am not keen on understanding the theory if possible and would be happy to use someone else's software to develop plans and test them.


texts: Would an optimal sorting network ever have to swap two numbers the "wrong" way

texts:
Intuitively it seems like an optimal (either minimum depth or minimum gates) sorting network should never have to compare-swap two numbers the "wrong" way (such that the larger one goes into the smaller-indexed position and vice versa).

Is this true?

If so, how do you prove it?


texts:
I was thinking about the old question regarding the existence of fixed points in hash functions (for instance, if we restrict the domain of MD5 to $S = \{0, 1\}^{128}$, making it a mapping $S \to S$, then is there an element $s \in S.~MD5(s) = s$?). Of course, a simple probabilistic argument indicates that the existence of such an element is likely, but as far as I know, there is no clear proof of the existence of such a fixed point.

Then I recalled Poincare's recurrence theorem in ergodic theory, which basically states that iterations of a well-behaving transformation brings almost every point in the space to near where it started, given sufficient time. So I'm just wondering whether there has ever been some connections between results along that branch of math and the study of hash functions? For instance, something saying that "a certain hash function, given enough time, will always bring any $s$ to $\{s': d(s, s') < \delta\}$ where $d$ is some metric on the value space"? Of course, Poincare's theorem would probably not directly apply here, but some weaker version, with additional simplifications on the hash functions, may bring about something interesting?

Additional thoughts on this and/or reference to related literature would be much appreciated. Thanks.


texts:
Given points $x_1, x_2, \cdots, x_n \in \mathbb{R}^d$. What is the complexity of computing
$$
argmin_{x}\left(\sum_{i=1}^n ||x_i-x||_2\right)
$$


texts: Identifying sub graph in connected digraph

texts:
Hello
I need some idea for a quick algorithm.
Given a strongly connected undirected graph G with weighted edges, I would like to identify induced sub graph(it is required to be weakly connected) of size n vertices ,such that its weight is minimum.
Thank you.


texts: Maximum subset of words with Hamming distance ≥ D

texts:
For all words of fixed length L over a given alphabet, I am interested in a practical algorithm that can give me a subset of maximal cardinality such that the Hamming distance between any two words in the subset equals D.
(The following variation is also of great interest: ... Hamming distance between any two words in the subset is at least D.)

Is there a mathematical result about the cardinality of such sets, depending on the alphabet, the length L of the words, and the minimum distance D?

Thank you very much.


texts: Which (almost) balanced Boolean function has smallest "total" influence

texts:
The well known Kahn–Kalai–Linial (KKL) Theorem says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$
$$
\max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot \Omega\Bigl(\frac{\log n}{n}\Bigr).
$$
The lower bound on maximum influence is achieved by the $\mathsf{Tribes}_n$ function. I have two questions in this regard:

What is a lower bound on total influence (as opposed to maximum influence) of Boolean functions? For a meaningful answer, it is necessary to consider functions that are (almost) balanced like $\mathsf{Tribes}_n$. For instance, a constant function has $0$ total influence.
Which almost balanced Boolean function achieves the lower bound on total influence? i.e., which balanced function has the smallest total influence? This question is a natural follow-up to the first question.

Thanks in advance!

Edit:

As Clement C. pointed out, there is a simple solution to the question for the Dictator function. Perhaps more interesting is to have the constraint that all variables $x_1, \dots , x_n$ have non-zero influence.

Questions:

What is a lower bound on total influence (as opposed to maximum influence) of Boolean functions where each coordinate $i \in [n]$ is influential?
Which almost balanced Boolean function, whose every coordinate has non-zero influence has the smallest total influence?


texts: Is there any research on the complexity of producing given a problem description?

texts: It is straightforward enough to analyze the complexity of a particular algorithm as a function of input size or other variables in terms of runtime or space used or whatever else. I am wondering if anyone has researched the complexity of producing the algorithm itself. For example, if I have implemented a merge sort, I can quickly say that the run time is O(n log n), but suppose my input were actually something like "Your input will be a list of elements and a transitive, antisymmetric comparison operator. Output a list of those same elements in sorted order." Without already knowing a sorting algorithm, what is the complexity of producing an algorithm that meets those requirements and runs in O(n log n) time?


texts: Are there upper bounds on the worst case complexity of NP-complete problems?

texts: I have proven some problem to be (weakly) NP-complete and try to find out some algorithm to solve it exactly. Except for some pseudo-polynomial stuff, I would be happy with an algorithm running in $O(c^n)$ for a constant $c$, but the best algorithm I can imagine runs in $O(n!)$, so much worse. Since all other NP-complete problems, where I know an exact algorithm, can be solved in exponential time, the question that comes to my mind is if there is some upper bound on the complexity of NP-complete problems like $O(c^n)$ or if there are problems with a proven lower bound of something like $O(n!)$, too (unless P = NP). At least everything is reducible to SAT, which in turn can be solved in $O(2^n)$.


texts: Best Asymptotic Complexity for Persistent Union Find

texts:
In this paper https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf, they claim to have a practically fast persistent union-find data structure for most use-cases, but it's still not polylogarithmic in the worst case (the worst case being, I have two variants which I alternately update between); only in a backtracking search.

Are there any implementations of a persistent union find datastructure which guarantee amortized polylogarithmic time complexity per operation regardless of how it's used?


texts:
I'm thinking about some properties of the empirical entropy for binary strings of length $n$ when the following question crosses my way:

$\underbrace{\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize nH_{0}(w)}_{\large\#}\;\overset{?}{=}\;n-\varepsilon_{n}\;\;\;$
with $\;\;\lim\limits_{n\rightarrow\infty}\varepsilon_{n}=c\;\;\;$ and $\;\;\;\forall n:\;\varepsilon_{n}>0$
where $c$ is a constant.
Is that equation true? For which function $\varepsilon_{n}$ respectively which constant $c$?
$ $
$n=2\;\;\;\;\;\;\;\rightarrow\;\#=1 $
$n=3\;\;\;\;\;\;\;\rightarrow\;\#\approx 2.066 $
$n=6\;\;\;\;\;\;\;\rightarrow\;\#\approx 5.189 $
$n=100\;\;\;\rightarrow\;\#\approx 99.275 $
$n=5000\;\rightarrow\;\#\approx 4999.278580 $
$n=6000\;\rightarrow\;\#\approx 5999.278592 $

$ $
Backround
$ $
$H_{0}(w)$ is the zeroth-order empircal entropy for strings over $\Sigma=\left\{0,1\right\}$:

$H_{0}(w)=\frac{|w|_{0}}{n}\log\frac{n}{|w|_{0}}+\frac{n-|w|_{0}}{n}\log\frac{n}{n-|w|_{0}}$

where $|w|_{0}$ is the number of occurences of $0$ in $w\in\Sigma^{n}$.
The term $nH_{0}(w)$ corresponds to the Shannon-entropy of the empirical distribution of binary words  with respect to the number of occurences of $0$ respectively $1$ in $w\in\Sigma^{n}$.
More precise:
Let the words in $\left\{0,1\right\}^{n}$ be possible outcomes of a Bernoulli process. If the probability of $0$ is equal to the relative frequency of $0$ in a word $w\in\left\{0,1\right\}^{n}$, then the Shannon-entropy of this Bernoulli process is equal to $nH_{0}(w)$.
At this point, my question should be more reasonable since the first term normalizes the Shannon-entropies for all empirical distributions of words $w\in\left\{0,1\right\}^{n}$.
Intuitively I thought about getting something close to the Shannon-entropy of the uniform distribution of $\left\{0,1\right\}^{n}$, which is $n$.
By computing and observing some values I've got the conjecture above, but I'm not able to prove it or to get the exact term $\varepsilon_{n}$.
It is easy to get the following equalities:
$\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize nH_{0}(w)\;\;=\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\left\{0,1\right\}^{n}}\normalsize |w|_{0}\log\frac{n}{|w|_{0}}+(n-|w|_{0})\log\frac{n}{n-|w|_{0}}$
$=\large\frac{1}{2^{n}}\normalsize\sum\limits_{k=1}^{n-1}$ $n\choose k$ $\left(k\log\frac{n}{k}+(n-k)\log\frac{n}{n-k}\right)$
and it is possible to apply some logarithmic identities but I'm still in a dead point.
(the words $0^{n}$ and $1^{n}$ are ignored, because the Shannon-entropy of their empirical distributions is zero)
Any help is welcome.


texts:
It is well known that minimizing an NFA for a fixed regular language is $PSPACE-Complete$.

As far as I know, there are no better than trivial algorithms for minimizing such NFA, but there's a little improvement if you consider symmetries.

I've a specific regular language I'd like to compute a minimal automaton for:

$$
L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]: \sigma_i\in\Sigma ~\text{ and }~ \forall j\ne i: \sigma_j\ne\sigma_i \}$$

But at the moment I can't seem to close the gap between the automaton I know to build for it and the lower bound I can prove for it.

I thought it might be fruitful to use some tool that given a language (it is finite for all $k,n$), searches (exhaustively if needed) for the smallest automaton which accept it, and see what the automaton looks like for small values of $k,n$.

Does anyone know a tool which builds a minimal automaton for a given language?


texts: Reduction of a language to a shorter equivalent

texts:
I'm new to Theoretical Computer Science, and my textbook says that it is easy to verify that the following language
\begin{array}{l}
L_{1}=A^{*} \cdot\{b\}-\left(A^{*} \cdot(A-\{a\}) \cdot A^{*} \cdot\{b\}\right) \\
L_{2}=A^{*}-\left(A^{*} \cdot(A-\{b\}) \cdot A^{*}\right) \\
L_{3}=L_{1} \cdot L_{2}
\end{array}
is equivalent to $L_{1}=a^{*} \cdot b$, $L_{2}=b^{*}$, and $L_{3}=a^{*} \cdot b^{+}$.
However, I don't seem to understand the process of reducing the languages. Can someone easily explain it to me?


texts: Identifying ambiguities in inductively learned concepts

texts:
I'm looking at ways in which "ambiguities" can be identified in labeled training data by a system undergoing some sort of inductive learning process. Do you know if there is any literature on this topic, and if so, where I could find that literature / what keywords to search for?

To better illustrate what I'm looking for, there is a classic parable of machine learning told by e.g. Dreyfus and Dreyfus (What Artificial Experts Can and Cannot Do, 1992) of an algorithm intended to classify whether or not pictures of woods contained a tank concealed between the trees. Pictures of empty woods were taken one day; pictures with concealed tanks were taken the next. The classifier identified the latter set with great accuracy, and tested extremely well on the portion of the data that had been withheld from training. However, the system performed poorly on new images. The first set of pictures were taken on a sunny day, whereas the latter were taken on a cloudy day. The classifier was not identifying tanks, it was identifying image brightness.

This leads to a question of how, in principle, one could take labeled training data and generate "ambiguities" that could be raised to user attention. The goal is not to generate "borderline" cases (e.g. images with medium brightness), the goal is to identify additional features in the data that could explain the training labels so that these can be turned into queries (e.g. "these labels can be explained both by brightness and by tanks").

I can think of a number of ways to approach this problem, but I'm sure it's already been tackled in various different ways. Can anyone point me towards the literature on this question?


texts:
Are there any known exact algorithms for Euclidean TSP that take advantage of the inherent structure of the problem?  Do any of these algorithms have better asymptotics than $O(2^n n^2)$ of a DP solution via Held-Karp?  I am also interested in simplicity of implementation (I've seen a 10-line implementation of Held-Karp in Python).

Is this still the current state of the art?


texts: Why can machine learning not recognize prime numbers?

texts:
Say we have a vector representation of any integer of magnitude n, V_n

This vector is the input to a machine learning algorithm.

First question : For what type of representations is it possible to learn the primality/compositeness of n using a neural network or some other vector-to-bit ML mapping. This is purely theoretical -- the neural network could be possibly unbounded in size.

Let's ignore representations that are already related to primality testing such as : the null separated list of factors of n, or the existence of a compositeness witness such as in Miller Rabin. Let's instead focus on representations in different radices, or representations as coefficient vectors of (possibly multivariate) polynomials. Or other exotic ones as are posited.

Second question : for what, if any, types of ML algorithm will learning this be impossible regardless of the specifics of the representation vector? Again, let's leave out 'forbidden by triviality' representations of which examples are given above.

The output of the machine learning algorithm is a single bit, 0 for prime, 1 for composite.

The title of this question reflects my assessment that the consensus for question 1 is 'unknown' and the consensus for question 2 is 'probably most ML algorithms'. I'm asking this as I don't know any more than this and I am hoping someone can point the way.

The main motivation, if there is one, of this question is : is there an 'information theoretic' limit to the structure of the set of primes that can be captured in a neural network of a particular size? As I'm not expert in this kind of terminology let me rephrase this idea a few times and see if I get a Monte-Carlo approximation to the concept : what is the algorithmic complexity of the set of primes? Can the fact that the primes are Diophantine recursively enumerable (and can satisfy a particular large diophantine equation) be used to capture the same structure in a neural network with the inputs and outputs described above.


texts: Algorithms for Maximum weight connected subgraph in planar graphs

texts:
I wonder what is known about the two following maximisation problems.

Maximum weight connected subgraph :

Input : A graph $G$, with weights $w_v\in \mathbb{R}$ for each vertex $v \in V(G)$

Output : A connected subgraph $H$ in $G$

Objective : Maximise the weight of $H$

and Maximum weight connected $k$-subgraph :

Input : A graph $G$, with positive weights $w_v\ge 0$ for each vertex

Output : A connected subgraph $H$ in $G$ of size $k$

Objective : Maximise the weight of $H$

I would very much appreciate any relevant related references.

I am particulary interested in the case when $G$ is a planar graph : Are there any constant aproximation algorithms known ? Any PTAS ?


texts: Splitting a graph into size constrained clusters

texts:
I ran across a problem while working on an algorithm for a game I'm making on the side. It's basically a clustering problem where we have a graph G and want to split it into clusters of equal size where each cluster is a connected subgraph of G. I also wanted to minimize the number of clusters and keep some guarantees about their size. The graph will also change over time so I want some quick way to add and remove vertices and maintain the clustering properties I created for the original clusters.

I'm working on this myself at the moment but I don't want to waste time if there already exists some sort of solution for this problem or if I'm overlooking an easy solution. If y'all have any helpful algorithms or papers you could refer me to, that would be amazing. Also, if you straight up solve this, that would be great as well.

Here's a formalization of the problems:

Cluster Property: given undirected graph G = (V, E) with vertices V and edges E and a set of clusters $C=\{C_1, ..., C_n\}$ where each $C_k=(E_k, V_k)$, $C$ holds the following properties:

$|C_k| \le a*ceil(\sqrt{|V|})$ where ceil is the ceiling function that rounds to up
$n$ is minimized for graph $G$
$C_k$ is connected
$V_k \subseteq V$ and $E_k \subseteq E$
the sets $V_1,\ldots,V_n$ are disjoint
$V_1 \cup V_2 ...\cup V_n = V$

Problem 1

Input: an undirected graph $G = (V,E)$

Output: a set of clusters $C={C_1,...,C_n}$ where $C$ has the Cluster Property

Problem 2

Input: an undirected graph $G = (V, E)$, a set of clusters $C={C_1,...,C_n}$, and a set of valid edges and vertices to remove $R=(E_R,V_R)$

Output: a set of clusters $C'={C'_1,...C'_n}$  for graph $G_R=(V-V_R,E-(E_R\cup E_{V_R}))$ where $C'$ maintains the Cluster Property. $E_{V_R}$ is the set of all edges that have an endpoint in $V_R$.

Problem 3

Input: an undirected graph $G = (V, E)$, a set of clusters $C={C_1,...,C_n}$, and a set of valid edges and vertices to add $R=(E_A,V_A)$

Output: a set of clusters $C'={C'_1,...C'_n}$  for graph $G_A=(V \cup V_R,E \cup E_A)$ where $C'$ maintains the Cluster Property.

Note: when adding or removing edges to the graph, assume that valid edges have endpoints in vertices that exist in the final graph.

Edit: There are a couple extra constraints I have that on the graph that I haven't provided. I'd like to be able to solve this problem for undirected graphs in general but if that's not possible or it's too difficult, I'll be forced to solve it for the specific set of graphs I'm working on. These graphs are Constrained Delaunay Triangulations, I can go into this more if you'd like.


texts: How to find interesting algorithms to implement?

texts:
I am not a researcher in algorithms (I am a college freshman).
I would like to implement an interesting recent algorithm from
a data structure/algorithms paper.

How can find a good algorithms paper to implement?


texts: The complexity of checking whether two DAG have the same number of topological sorts

texts:
This problem is highly related to the CNF one.

Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".

Intuitively, the complexity of this problem is $C_=P$-complete, just as the CNF one. It is easy to see it is in $C_=P$, but is it $C_=P$-hard?


texts:
There is an increasing number of scientific articles which I look through and somehow I feel a lack of a tool to keep track of the already read ones and my summary notes on it. Or another usage scenario would be to search by an author and see which articles of the given author I have already read.

The question is: Do you use or know of any freeware tools for organizing articles?


texts: Reference for a class of graphs that preserve subgraph distances when ordered

texts:
Let us say that a graph $G$ has the property $M$ if its vertices can be ordered $v_1, v_2, \ldots v_n$ in such a way that the graph $H_i$ induced by the vertices $\{v_1, \ldots, v_i\}$ has $dist_{H_i} (v_j, v_k) = dist_G(v_j, v_k)$ for all $j,k \leq i$. In other words adding the next vertex in our ordering does not affect the distance metric of the current graph.

An example of such a graph is the regular $n \times n$ grid.

Does this property or class of graphs have a name? Have they been studied?


texts:
Termination is the following problem.
Input: a Petri Net with initial marking
Output: "yes" iff there exists an infinite firing sequence. The naive algorithm in the case of bounded nets for example consists in running the net until either all configurations have been reached or a repeating one is found. Is there any clever way to solve the problem? What is the lower bound complexity?


texts: Finding invariant elements of binary matrix from row and column sums

texts:
Consider a m-by-n binary matrix A. Given only an m-dimensional vector of its row sums (R) and an n-dimensional vector of its column sums (C), is there an efficient (ie. polynomial time) algorithm that determines which elements of A must be 1 and which elements of A must be 0?

A trivial example: if R = {2,1,2} and C = {1,1,3}, then

$$
 A =
 \begin{bmatrix}
  ? & ? & 1 \\
  0 & 0 & 1 \\
  ? & ? & 1 \\
 \end{bmatrix}
$$


texts: Complexity of Turing self-reducibility of Clique problem?

texts:
I'm interested in the complexity of self reducibility of a variant clique problem. Namely, the NP-complete problem HALF Clique: given a graph on $N$ nodes, Is there a clique of size $N/2$ in the graph?

How hard is it to reduce an instance of HALF CLIQUE of input size $2N$ to an instance of size $N$ using Turing reduction? Is there a Cook reduction? I'm looking for references for upper bounds and lower bounds on the complexity of Turing reductions of this type.


texts: Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

texts:
I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part of the input). Note that this is different from the problems of MINCUT and MAXCUT which simply ask to find the minimum and maximum sized cutsets.

For general graphs, the MINCUT problem can be solved in polynomial time while the MAXCUT problem is NP-Hard. It follows that deciding if a cutset of a particular size exists in a general graph is also NP-Hard since we could use it to find the maximum sized cutset.

For bipartite graphs however, the MAXCUT problem is trivial -- all the edges in the graph constitute the MAXCUT. Moreover, if it helps, I think I can show that for bipartite graphs, the edge - complement of a cutset is also a cutset. That is if $E_c\subseteq E$ is a cutset of a bipartite graph $G=(U\cup V,E)$ then $E−E_c$ is also a cutset of $G$.

However, I have not been able to determine if deciding if a cutset of some size $k$ exists is in P or is NP-Complete or something else. If it is Np-Complete, is there a family of graphs for which it is in P? Any pointers will be helpful.


texts:
I noticed that dual decomposition methods tend to be preferred over primal ones in the large scale optimization literature (here are some examples: (1), (2)). The reason seems to be, from what I understand, that dual decomposition methods often lead to more efficient algorithms.

After reading about decomposition methods on various sources (e.g. see these notes by Stephen Boyd), I don't get the intuition of why this would be the case.

Perhaps an important difference is that, as S. Boyd notes in his slides, in primal decomposition methods:

  the master problem manipulates the primal (complicating) variables

while in the dual decomposition methods, this would not be the case. However, when S. Boyd describes the procedures for primal vs dual methods, the decomposition looks essentially the same:

repeat
   solve the subproblems (presumably on the slaves)
   update complicating variable (presumably on the master)

So my questions are:

Is it true that dual decomposition methods tend to be more efficient in practice than primal methods?  If so, why?
Why does S. Boyd say that in primal decomposition methods, "the master problem manipulates the complicating variables" ? How is this different from the way these variables are handled in a dual decomposition?

Update: Additional background:

Statistical machine learning problems, such as MAP-MRF estimation, arise often in bioinformatics, computer vision and NLP, and are usually formulated as quadratic pseudoboolean problems (i.e. mathematical programming problems with binary and quadratic cost functions) (e.g. (3)).

There seems to be a growing trend in the literature to solve these problems via dual decomposition (as pointed out by the two articles I linked to above: (1), (2)). Moreover, some of these authors have pointed out that there are connections between an important class of inference algorithms, such as belief propagation and other general message passing methods, to dual decomposition (4).


texts: Consider a full-rank lattice in $\mathbb{R}^n$. Let $\lambda_1$ be the length of the shortest nonzero vector. Given a vector in $\mathbb{R}^n$ we wish to find the nearest lattice vector, as measured by Euclidean distance. In general this is NP-hard. However, we can add the promise that distance to the nearest lattice vector is at most $d$. I'll refer to this as the bounded distance decoding problem. My understanding is that Babai's nearest plane algorithm provably solves this for $d \leq 2^{-c n} \lambda_1$ for some specific value of $c$ (which I don't know but which I believe to be known, and which I think maybe originates from an LLL preprocessing step). My question is whether there is a known way to efficiently go beyond this by a polynomial factor. For example, is there a known polynomial-time algorithm to solve bounded distance decoding at $d = n 2^{-cn} \lambda_1$? The closest to this that I have managed to find in the literature is an algorithm by Klein and subsequent extension by Liu, Ling, and Stehle, which appears to extend beyond the radius of Babai's algorithm by a factor of $k$ at a complexity cost of $n^{k^2}$.


texts: Is there a constructive parallel repetition theorem for nice MIP protocols?

texts:
Theorem 1.1 of Ran Raz's paper is a non-constructive upper bound on the soundness error of parallel repetitions of a 2-prover minimally minimally interactive proof system with perfect completeness.

As far as I can see, despite the second sentence of that paper's abstract suggesting otherwise, that paper does not give a constructive upper bound on the relevant quantities.

  Is there a known constructive upper bound on the soundness error of parallel repetitions of a 2-prover minimally minimally interactive proof system with perfect completeness?


texts:
Wikipedia states that the advantages of smoothsort over heapsort is that at times it comes closer to O(n) time.

Now I was wondering what advantage does heapsort has over smoothsort?

Or to rephrase this question, is smoothsort always a better choice than heapsort (even if the input is not already sorted to any degree) ?


texts: How to design a scalable distributed consensus protocol that isn't vulnerable to long range attack

texts:
Research on distributed consensus has surged with the invention of Bitcoin and Blockchain.

In these special cases we are looking for a distributed consensus algorithm that can scale to a number of nodes comparable to the size of the internet. Nodes can crash or have byzantine failures at any given time. Messages are delivered asynchronously without knowing an upper bound of time one message delivery can take. And there are no exact synchronized clocks available.

The FLP impossibility result suggests that this is not possible.

The Bitcoin Whitepaper by Satoshi Nakamoto provides a solution to this problem by regarding consensus as something that is never definitive but the probability of a value being accepted by all members grows exponentially with the number of confirmations. However the proof-of-work algorithm provided in this paper requires lots of computational power and is very energy hungry.

That is why the PPCoin Paper suggests a new approach called proof-of-stake that solves consensus in a similar fashion, but distributing voting power according to the amount of "stake" someone has in the system instead of how much computing power someone has. However, Proof-of-Stake is vulnerable to the long-range-attack. An attacker can convince honest nodes that a long chain of confirmations he/she produced by themselves is the official chain. PPCoin solves this problem by introducing centralized checkpoints.

Does anyone know of a decentralized solution to the long-range-attack in consensus protocols that doesn't use proof-of-work?

I know of these other protocols: (but none of them have a real solution to this problem)

Tendermint expects 2/3rds of all bonded validators to sign a block confirmation before it is accepted. I believe that this will not scale to a node set as big as the internet.
Slasher / Casper: the ethereum developers have presented many ideas and found flaws in all of them. Currently there are two different versions of Casper around, but none of them are formally described completely.
Ripple uses unique node lists that have to fulfill certain properties of interconnectedness for the protocol to work. But they don't have an algorithm that supports creation of these unique node lists that way.

Do you know any other protocols that might be worth a look? Or have an idea of your own for solving this problem?


texts: Resources to get started on fractional graph coloring algorithms

texts:
I'm interested in using  fractional graph coloring algorithms/solvers to solve a problem, where is a good place to start? I'm looking to find basic/introductory to state-of-the-art algorithms more than theoretical results at this point.

Scheinerman's book looks great, but the focus seems to be more on theory than algorithms.


texts: Approximation algorithms for min vector subset-sum over GF(2)

texts:
In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum.

  Given a set of vectors $v_i$ over GF(2) and a target vector $y$, is there a subset of the $v_i$ summing to $y$?

In the answers, comments, and referenced papers I noted

The decision problem is in P.
The natural minimization problem (finding the smallest subset) is NP-hard.
It's related to the problem of finding sparse codewords in a linear code.

My question is: are there any known polynomial-time approximation algorithms for the minimization problem in (2)? I know very little about coding theory, so there may be some obvious or well-known approximation-preserving reductions to (3) that I have not seen.


texts: Collapses under the assumption that $NEXP\subseteq P/Poly$

texts:
It is known that if $NP\subseteq P/Poly$ then the polynomial hierarchy collapses to $\Sigma_2^{P}$ and $MA = AM$.

What are the strongest collapses known to happen if $NEXP\subseteq P/Poly$?


texts: $O(m+n)$ really necessary for graph algorithms?

texts:
It is standard to express the running time of linear-time graph algorithms as $O(m+n)$ (such as depth-first-search, etc.).

For nearly all such algorithms, vertices of degree zero have no effect on the underlying graph problem. So a solution to the graph problem can usually treat all these unsupported vertices jointly, and does not need to process them individually. For example, in depth-first-search, it suffices to list the dfs-tree for the supported vertices, along with an auxiliary record that all other vertices are unsupported.

If the graph is presented with any kind of intelligent data structure, it should be possible to process in time $O(m)$, and to generate a data structure that encodes the solution in time $O(m)$. This applies even in the case that $n \gg m$.

My question is, what is the reason for the notation $O(m+n)$? Are there really algorithms which require this running time $\Omega(n)$ in the regime $n \gg m$? Is this basically for pedagogical purposes only?


texts: Does XOR automata (NXA) for finite languages benefit from cycles?

texts:
A non-deterministic Xor automata (NXA) is syntactically an NFA, but a word is said to be accepted by NXA if it has an odd number of accepting paths (instead of at least one accepting path in the NFA case).

It is easy to see that for a finite regular language $L$, there exists a minimal NFA which doesn't contain any cycles (if a cycle was both reachable from the initial state and you get from it to an accepting state - your language is not finite).

This is not necessarily the case for NXAs.

Denote by $xsc(L)$ the xor-state complexity of a language $L$,

and by $axsc(L)$ the acyclic xor state complexity of $L$ (i.e. the size of a smallest acyclic NXA which accepts $L$).

  Is it true that for every finite language $L$: $$axsc(L)=xsc(L)\ ?$$


texts: Is there Zero Knowledge Proof of Knowledge protocol for Hash function? (If h(v)=w) without revealing v to the anyone can we prove that we know 'v')


texts: relations between the degrees of a boolean function and its absolute function

texts: Given a boolean function $f:\{0,1\}^n\rightarrow\mathbb{R}$ of degree $d$, is there any upper bound in terms of $d$ on the degree of the function $|f|$, where $|f|(x)=|f(x)|$. Here the degree of $f$ is the minimum degree of all polynomials over $\mathbb{R}^n$ that taking the same values of $f$ in $\{0,1\}^n$.


texts: Time complexity of polynomial regression with random coefficients

texts:
Suppose that I have
$$\lim_{k,l,m \rightarrow \infty}(f(x,l) ~~=~~ \sum_{n=1}^{m} g(a_{n,k})h(x,n)$$
where the $a_{n,k}$ are pseudo-random real numbers with $k$ digits generated in an arbitrary way, and $g,h$ are functions. At the limit, let the sum be equal to the function. Let's be interested in the approximations at $k$ digits and $l$-digit precision in the function $f$.

What would be an estimate of the time-complexity $O(u(m),v(k),z(l),f)$ to fit the function $f(x)$ by trial and error to a demanded precision $l$, as a function of the chosen number of finite terms $m$ in the sum, the $k$ digits of the random numbers $a_{n,k}$? For simplicity, assume that $f$ has a taylor series, and for concreteness, let $f$ be the sine function.


texts: Is there a result in computability theory that does not relativize?

texts:
I was reading Andrej Bauer's paper First Steps in Synthetic Computability Theory. In the conclusion he notes that

  Our axiomatization has its limit: it cannot prove any results in computability
  theory that fail to relativize to oracle computations. This is so because the
  theory can be interpreted in a variant of the effective topos built from partial
  recursive functions with access to an oracle.

This made me wonder about non-relativizing results in computability. All results I know from computability theory do relativize to computation with oracles.

Are there results in computability theory that do not relativize? I.e. results which hold for computability but do not hold for computability relative to some oracle?

By result I mean a known theorem in computability theory, not some cooked up statement. If the notion of relativization doesn't make sense for the result then it is not what I am looking for.

It is also interesting to know if the result can be stated in the language of Synthetic Computability Theory or not.


texts: Why doesn't computer science follow biology more closely in computer design?

texts:
Nature has proved with the brain that it can create complex computers with very little energy consumed and released, extremely low energy compared to a common computer.

However, I noticed the design is completely different, why hasn't anyone tried to or succeeded to create a similar one?

For example:

1) Computers use memory as the main building block. After that, a processor is used to manipulate it.

2) However, biological computers do not use memory as the main building block. This is a by-product. The main building block appears to be a combination of static geometry and design of the computer (DNA) which is combined with the energy generators (mitochondria, components of both DNA and energy transfer).


texts: Efficient Reduction from Min Cut to st-Min Cut

texts:
I am aware that many known algorithms for min cut problem is not by reducing the problem to $st$-min cut.

But the question of efficient reduction from min cut to $st$-min cut is still interesting to me.

I know the following trivial reductions:

Min cut is $st$-min cut for some $s,t$. So we can, for every pair  $s,t$, solve $st$-min cut and return the minimum. This takes $O(n^2)$ calls to $st$-min cut algorithm.
By the same reasoning, we can fix any vertex $s$, and return the minimum, among all $t$, of the $st$-min cut. That takes $O(n)$ calls.

  Is there any more efficient (randomized) reduction ?
  What if we only want the size of the minimum cut, not the cut itself ?


texts:
I have a (biological) computational system that outputs squared matrices. These matrices will sometimes have a tendency to be diagonal-like, with higher values at and around the diagonal.

I would like to have some summary measure on how "much diagonal" a matrix is, so that I can batch process hundreds of outputs and score them on how much the higher entries cluster in and around the diagonal.

Any ideas of some standard approach that I can generalise?

Thanks !
JL


texts: Why is "topological sorting" topological?

texts: Why is "topological sorting" called "topological"? Is it just because it determines an order without altering any vertices or edges -- like a doughnut and coffee cup are topologically equivalent? Why is it not called "dependency sort" or something else? Why "topological"? I admit I'm mystified.


texts: Maximizing a submodular function of two sets with different size constraints

texts:
I have two totally distinct domains (apples and oranges) and I have a function $f$ that takes a set of objects from the first domain and a set of objects from the second domain and returns a real number.

$f(S,T)$ has the following interesting properties:

fixing $T$, it is non-negative, submodular and monotone w.r.t. $S$;
fixing $S$, it is non-negative, submodular and monotone w.r.t. $T$.

I want to maximize $f(S,T)$ with two cardinality constraints $|S| = s$ and $|T| = t$.

How can I do that?
If I consider the product space, the function is monotone and submodular.
Thus I can apply the standard greedy algorithm.
Dealing with the two different size constraints, might not be an issue: adding $(a, x)$ and $(a, y)$ in sequence allows me to increase $|T|$ without increasing $|S|$.

The question is whether the $1-1/e$ approximation still holds.


texts: Is it known that $\mathsf{IP}\notin\mathsf{NP}^{cc}\cup\mathsf{coNP}^{cc}$ where $\mathsf{IP}$ is inner product communication complexity problem? Where is the classification of $\mathsf{IP}$ currently in?


texts: Anyone recognize this as a special type of multi-commodity flow problem?

texts:
Consider this problem:

$$
\begin{align}
\min_{y,z,l \geq 0} \quad & g(y,z,l) :=
\sum_{(i,j)\in E} \sum_p (-w_{ijp}) y_{ijp} &  \\
\textrm{s.t.} \quad & \left( \sum_{(i,j)\in E} y_{ijp} + l_{ip} \right)-
                      \left( \sum_{(j,i)\in E} y_{jip} + z_{ip} \right)=
                \begin{cases}
                 +1 \quad i=1 \\
                 -1 \quad i=n \\
                  0 \qquad i\neq 1,n
                \end{cases} & \forall i \in I, p\in P \\
               & \sum_p (z_{ip} - l_{ip}) = 0 & \forall i\in I
\end{align}
$$

Sets $I=\{1,\ldots,n\}$ and $P=\{1,\ldots,m\}$ correspond to $n$ nodes and $m$ commodities.
Set $E \subseteq I\times I$ corresponds to the arcs of a directed acyclic graph where node $1$ is the source (no predecessors) and node $n$ is the sink (no successors).
Sending $y_{ijp}$ units of commodity $p$ from node $i$ to $j$ costs $-w_{ijp}y_{ijp}$, with all $w_{ijp}$ positive.
Note that all commodities have $1$ as the source and $n$ as the sink.

If you ignore the $z_{ip}$ and $l_{ip}$ variables the problem becomes a set of $m$ independent shortest-path problems.
Specifically, let $C = \{(y,z,l)\}$ denote the class of all solutions with $z_{ip} = l_{ip}$ for all $i, p$.
Then, the best $(y,z,l) \in C$ can be found by solving $m$ independent shortest-path problems, i.e. by assigning $y_{ijp} \in \{0,1\}$.

It is this remark that makes me hope that we are dealing with a special-case of multicommodity flow that can be solved more efficiently. But I haven't found anything in the literature.

Does anyone recognize this problem or have an idea for a clever heuristic?


texts: Most general setting for fine-grained exponential-time complexity classes?

texts:
Consider the class of functions computable in time $(b+o(1))^n = 2^{\log_2{(b)} \times n + o(n)}$ on a $2$-tape Turing machine.

By the Hennie-Stearns theorem, the same functions are computable in time $(b+o(1))^n$ on a $k$-tape Turing machine for any $k \geq 2$. And we can extend this equivalence to any model of computation that has an essentially linear time translation to and from $2$-tape machines. But this isn't a very natural class, even given that we believe in the extended Church-Turing thesis.

If we account for the space usage as well, more models are time-translatable with a blowup of the form $O(t \times s^k)$.  For example, when emulating a $2$-tape machine on a $1$-tape machine, it only has to scan the space used each time step, so the time blowup is $O(t \times s)$. Similarly, it seems like for RAM models there is a small $k$ that works: use one tape as an associative memory, a list of key-value pairs, which the emulator searches to find a key written on a different tape.

Now it seems sensible to say something like this: $F$ is computable in $(b+o(1))^n$ time and $2^{o(n)} = (1+o(1))^n$ space. I don't have to say what model I'm using because all the obvious ones work.  There is sort of a trade-off here, in exchange for a subexponential space restriction, we can specify a particular base $b$ for the time complexity of our function that's invariant in a larger context.

That's about as far as I understand this issue right now.  And I could be completely mistaken about something so partly I'm looking for some reassurance that the above is roughly correct. But I wonder if that's all there is to it? Is there some other set of assumptions under which the exponential time base of a function can be uniquely specified?

EXAMPLE: Rubinstein's theorem says that we can factor with base $2^\frac{1}{3}$. Since the algorithm uses subexponential space, this result is robust across models.

EXAMPLE: The square-root barrier for finding primes. If it were broken by exhibiting an algorithm that required exponential space on a Turing machine, would that really be a natural result, or possibly just an artifact of the machine model?

EXAMPLE: The Strong Exponential-Time Hypothesis. Might it be the case that a RAM program can solve general $\text{CNF-SAT}$ in exponential time with a base less than $2$, but also requiring exponential space, so that when translated to a TM the algorithm runs in exponential time with a base at least $2$ and (a slightly-weakened version of) SETH is true in the TM model only?  Is there a variant of SETH where only subexponential space algorithms are considered in order to make it applicable to more models?  Or is there some reason I'm not understanding that no generality is lost without this assumption?


texts: Embarrassingly Parallel: Formal Definition & Citation

texts:
I've been unable to find a good answer for this question: Formally, what makes a problem embarrassingly parallel? Intuitively, it would seem to me that an embarrassingly parallel problem is one where:

The full solution can be discretized.
It is efficiently decomposable into subproblems that are similar in structure.
Each subproblem is (more or less) independently soluble (i.e. without a large communication overhead required between the subproblems).
The solutions of each subproblem are independent such that there is an efficient method that can reassemble them into the larger solution.

I realize there's some overlap in the bullets above, hence the question – how is 'embarrassingly parallel' or its synonymous technical term clearly defined? Is there a reference in the literature where this definition was first formalized?

Note: I'm not trained in TCS (as you may have guessed) and am aware that my descriptions above may not be entirely correct or in keeping with established formalisms and terminology.


texts: MSOL optimization problems on graphs of bounded cliquewidth, with cardinality predicates

texts:
CMSOL is Counting Monadic Second Order Logic, i.e. a logic of graphs where the domain is the set of vertices and edges, there are predicates for vertex-vertex adjacency and edge-vertex incidence, there is quantification over edges, vertices, edge sets and vertex sets, and there is a predicate $\textrm{Card}_{n,p}(S)$ which expresses whether the size of $S$ is $n$ modulo $p$.

Courcelle's famous theorem states that if $\Pi$ is a property of graphs expressible in CMSOL, then for every graph $G$ of treewidth at most $k$ it can be decided in linear time whether $\Pi$ holds, provided that a tree decomposition of $G$ is given in the input.
Later versions of the theorem dropped the requirement that a tree decomposition is given in the input (because one can be computed with Bodlaender's algorithm), and also allowed optimization instead of merely decision; i.e. given a MSOL formula $\phi(S)$ we can also compute the largest or smallest set $S$ which satisfies $\phi(S)$.

My question concerns the adaptation of Courcelle's theorem to graphs of bounded cliquewidth. There is a similar theorem saying that if you have a MSOL1 which allows quantification over vertices, edges, vertex sets but not edge sets then given a graph $G$ of cliquewidth $k$ (with given clique-expression), for every fixed $k$ it can be decided in linear time whether graph $G$ satisfies some MSOL1 formula $\phi$; all references I have seen point to

  Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width by Courcelle, Makowsky and Rotics, Theory of Computing Systems, 2000.

I have tried to read the paper, but it is not self-contained with respect to the exact definition of MSOL1 and it is frankly hard to read. I have two questions with respect to what exactly is possible to optimize in FPT, parameterized by the cliquewidth of the graph, if a clique expression is given in the input.

Does MSOL1 allow the $\textrm{Card}_{n,p}(S)$ predicate for testing the size of a set modulo some number?
Is it possible to find a minimum / maximum size set $S$ which satisfies a MSOL1 formula $\phi(S)$ in FPT parameterized by cliquewidth, when the expression is given?

For both these questions I would also like to know what the correct references are to cite when claiming these results. Thanks in advance!


texts: Proof of decidability of type checking of calculus of (co)inductive constructions?

texts: I often see it asserted that type checking is decidable for CIC, but I haven't seen it proven. Is there a good paper (or simple demonstration) of this?


texts:
Treewidth has arguably pretty involved definition. Recently I was thinking about a problem and turns out it easy to solve it for graphs with small ``naive treewidth''.

Naive treewidth is defined as follows. Let $G=(V,E)$ be a graph. We say that $G$ has naive treewidth $k$ if there exists a partition $V_1 \sqcup V_2 \sqcup \ldots \sqcup V_m = V$ such that $|V_i| \le k$ and a tree $T = ([m], E_T)$ such that for every $(u,v) \in E$ either $u,v \in V_i$ for some $i \in [m]$ or $(u,v) \in V_i \times V_j$ such that $(i,j) \in E_T$.

If $T$ is a path than we say that $G$ has naive pathwidth $k$.

For naive pathwidth it is easy to see that it can be much larger than pathwidth. Consider a full binary tree with $2^k$ leaves. It has pathwidth $k-1$. On the other hand notice that if naive pathwidth of a graph is $\le t$ than the partition contains at least ${|V| \over t}$ blocks. Thus there exists a path in $G$ of length at least ${|V| \over t} - 1$. Since the longer path in the full binary tree of height $k$ is $2k$, naive pathwidth of the full binary tree is at least ${2^k \over 2k}$.

Notice that instead of the full binary tree it was possible to use a tree with one vertex connected to the remaining $|V|-1$ vertices which gives even better separation. The reason I've used the binary tree is that for my purposes all graphs have constant degree.

My questions are:

For a graph with small pathwidth (and constant degree if it is needed) can it be shown that it has small naive treewidth? If it is not true, how the counterexample looks like?
The same question for a graph with small treewidth.

Update: for arbitrary degrees there is a separation between treewidth and naive treewidth. The example is a path of length $n$ and a vertex connected to all vertices of the path. Treewidth of such graph is $2$ and naive treewidth is $\Omega(\sqrt{n})$. The proof goes like this: consider the block $B$ containing the vertex of degree $n$. Assume that this block contains at most $\sqrt{n} / 2$ vertices. Then there exists a path in $G - B$ containing at least $2 \sqrt{n}$. Notice that in $T$ all the blocks should be connected to $B$. Thus this path of length $2 \sqrt{n}$ must be contained in a single block.


texts: Low space computation and branching program

texts:
One of the most elemental result of relationship between boolean circuit size and polynomial uniform computation is Pippenger and Fishers simulation: $DTIME[T(n)]\subseteq SIZE[T(n)\log  T(n)]$.
I want to consider the small branching program family simulating low space  computation.

Question1: What is the best simulation bound $S_{1}(n)$ which is known at this moment such that $DSPACE [S(n)]\subseteq BP-SIZE[S_{1}(n)]$
Question2:What is the best time complexity bound as far as we know, for the function that $1^{n}\rightarrow $a branching program in the Question 1.


texts: Distribution of number of unique items in a sample

texts:
Suppose we're sampling a discrete random variable from a distribution f, n times. Is there a simple analytical formulation for the expected number of unique items we obtain, or for the distribution of this number? Is there a name for this characteristic?

This question came up in a practical task: I have a stream of items arriving, every item having several Zipf-distributed parameters, and I'd like to answer queries like "how many items had a parameter equal to x" - I was wondering how feasible it is to just count each parameter value's occurrences (obviously, the space required is exactly what I'm asking about).


texts: Are there non trivial 2-basis of a 2-connected planar graph?

texts:
Based on MacLane's planarity criterion, planar graphs are exactly those that admit a 2-basis. Such basis can be easily obtained considering $|E| - |V| + 1$ of its faces. Denoting those basis as trivial bases, my question is: are there examples of non-trivial 2-basis of a 2-connected planar graph?
A non-trivial basis should contain at least one cycle surrounding at least two faces. I could neither find an example nor prove their inexistence.
Any help would be highly appreciated.


texts: What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$ under the Kullback-Leibler divergence?

texts: If $D_{KL}$ is the Kullback-Leibler divergence, minimizing $D_{KL}(P_{data}||P_{parameters})$ performs maximum likelihood estimation of the parameters. What happens if you minimize $D_{KL}(P_{parameters} || P_{data})$?


texts: Two Questions on the paper Near-optimal Regret Bounds for Reinforcement Learning

texts:
I am reading the classic paper Near-optimal Regret Bounds for Reinforcement Learning. I have two questions:

How to combine all MDPs in $ \mathcal{M} $ to get a single MDP with extended action space?

Why value iteration on the MDP $\tilde{M}^{+}$ with continuous action is equivalent to value iteration on an MDP with finite action set?

These two steps are important for understanding the algorithm UCRL2. But I cannot see why they are true based on the concise explanations in the paper. Any comment is much appreciated!