texts:
Say I have a finite $n$-ary tree where each node contains state. For the sake of argument, let's say a key-value store. If we are interested in the aggregation of some key(s) at some node, then we fold over the subtree at that node with the appropriate function. However, this doesn't scale well.

An option would be to always fold whenever a node is inserted/removed, keeping a cache of each node's subtree aggregation and updating that. However, if a node were inserted deep in the structure, the resulting cascade up to the root would still be quite expensive.

Is there a known data-structure that makes this aggregation cheap? Specifically, it needs to have cheap access and insert to nodes, their state and their aggregated subtree; while being happy to sacrifice space. (Ideally the aggregation should be precise, but if an estimate is possible, then that will suffice.)

The best I've come up with is keeping the tree with a projection of its nodes onto a list, where each subtree occupies a contiguous region thereof, then folding over that to get the aggregate date. However, a fold over a flat bit of memory isn't going to be much better than the same thing over a subtree (i.e., it's still $O(n)$, modulo pointer lookups)... I'm just wondering if there's some clever trick.


texts: Is computing the dual optimum of a degenerate LP equivalent in complexity to solving LP?

texts:
Given a primal LP and an optimum solution thereof, it is well-known that complementary slackness conditions [1] can be used in non-degenerate cases to produce a dual optimum solution.

For instance, if we have an LP of the form $\max c^Tx, Ax\le b, x \ge 0$ with $m$ constraints and $n$ variables, and we are given a vertex optimum solution such that at least $m$ primal slack values and primal optimum coordinates are strictly positive, then it is easy to use Gaussian elimination to produce the optimum solution of the dual.

However, many degenerate cases can happen: an optimum vertex can be placed on many more constraints, or many variables can be set to 0, meaning that in such degenerate cases, complementary slackness does not seem to lead to a fast way of getting a dual optimum solution.

Is there an argument showing that the problem of computing any dual solution in such degenerate cases, while knowing the optimum, is equivalent (in complexity) to solving LP from scratch?


texts: Is it possible to solve perfect matching in linear time

texts:
As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft.

  Is it possible to solve perfect matching problem in linear time for given $G=(V,E)$? Here, we say linear time as $O(|V|+|E|)$. I think it is impossible to solve it in linear time.  Are there plausible evidence such as complexity lower bounds for some limited computation models or conditional results indicating the linear time intractablity of matching problems?


texts: Permanents - Approximation and connection to integer factorization

texts:
Given a non-negative integer matrix of size $n \times n$. If the permanent can be calculated in $n^{2}$ arithmetic operations but each operation is on word size $n^{k}$ bits for some constant $k$, does that imply calculating permanent is in  $P$?

We assume the maximum integer size $M$ is bound and only let $n$ grow for complexity estimates.

Actually an observation is that even if if one can calculate permanent of $n \times n$ matrix in $O(n^{k})$, then $n!$ is easy to calculate. But even then it wont bother RSA since for RSA $n ~ O(2^{256})$ and $n^k$ even for $k=1$ would be formidable. Is this correct?

Ryan Williams Answer:
"the permanent is #P-complete, due to Valiant's theorem in my answer below. It is possible in principle to reduce the factorization of a 256-bit number (which is computable in TFNP) to the Permanent on a matrix of dimension N×N where $N≤c⋅256^{c}+c$ for some hopefully small constant c. However the computation of a nice upper bound on c would probably take substantial effort. It's possible c is no more than 2 or 3."

" computing the permanent is much harder than integer factoring (to my knowledge), so I doubt someone would try to reduce factoring to permanent."

How about via approximations?

If an $\epsilon$-approximation to permanent can be found in polynomial time, then I don't think it will be not worthwhile to study such an algorithm. One can take $\epsilon$ small enough so that one has to try $O(\epsilon)$ different choices for permanents. In that case factoring should have an efficient probabilistic algorithm


texts: What are the equational laws for zero types?

texts:
Disclaimer: while I care about type theory, I don't consider myself an expert on type theory.

In the simply typed lambda calculus, the zero type has no constructors and a unique eliminator:

$$\frac{\Gamma \vdash M \colon 0}{\Gamma \vdash initial (M) \colon A}$$

From a denotational point of view, the equation
$initial (M_1) = initial(M_2)$ is obvious (when the types make sense).

However, from that perspective I can also deduce that, when $M,M' \colon 0$, then : $M = M'$. This deduction seems stronger, although a particular model that shows it eludes me.

(I have some proof-theoretic intuition though: it doesn't matter which contradiction you use to obtain an inhabitant, but there might be different contradiction proofs.)

So my questions are:

What are the standard equational laws for zero types?
Are any of them classified as $\eta$ or $\beta$ laws?


texts: Efficient Algorithm for bilinear pairing on ECC

texts:
Bilinear Pairing in the elliptic curves is a wonderful mathematical mapping which is usually defined by the map $e:G_{1} \times G_{1} \rightarrow G_2$ for some groups of $G_{1}$ and $G_{2}$. For better understanding of pairing and its properties see the wikipedia.

Question1: Are there any efficient bilinear pairing or efficient pairing algorithms? If so, is this algorithm applicable to all kind of pairings, I mean is it a general approach for efficiently computing any pairing or just an algorithm specific pairing? Meanwhile, I am familiar with Weil and Tate pairing, but efficiency of implementation and performance is my concern.
Question2: Is there any article in which the efficient computability of pairing-based approaches are discussed? Or may be an article in which a comparison between pairing based approaches and discrete logarithm based approaches is discussed.

I have read some pairing-based approaches for group key exchange in which there is no clue on how efficient they are and also there is no comparison of this kind with their previous algorithms. So I doubted may be there is a nice article on this which has paved the way.


texts: Topological sort with constraints on the relative difference between the vertex labels

texts:
A topological sort of a graph $G(V,E)$ consisting of $n$ vertices assigns a label $L(v_x)$ to a vertex $v_x$ where $L$ is defined as $L:V \rightarrow \{1,\dots,n\}$.

Let additional constraints over the labels that the topological sort will assign to be defined as follows.  For every vertex pair $(v_x,v_y)$ let $d(v_x,v_y)$ be the permitted difference between $L(v_x)$ and $L(v_y)$ i.e. $L(v_x) - L(v_y) \leq d(v_x,v_y)$. $d$ is defined as $d:V \times V \rightarrow \{0,\dots,n-1\}$. A solution to this variant of Constrained Topological Sort (CTS) will compute a tolopological sort satisfying the difference constraints for all possible pairs of vertices in $G$.

Is a linear time solution to CTS possible?
Is there an existing work where I can refer to?


texts: Comparing two products of lists of integers?

texts:
Suppose I have two lists of positive integers of bounded manitude, and I take the product of all elements of each list. What's the best way to determine which product is larger?

Of course I can simply compute each product, but I'm hoping there's a more efficient approach, as the number of digits in the products will increase linearly with the number of terms, so that the whole computation is quadratic.

If I were adding instead of multiplying, I could use a "zippering strategy" of incrementally adding entries from the first list and subtracting from the second, circumventing the need to compute the (large) overall sums. The analogous techniques for products would be to sum the logarithms of the entries, but the problem now is that computing the logs requires use of inexact arithmetic. Unless there's some way to prove the numerical error is irrelevant?


texts: Complexity of counting poset automorphisms

texts:
A (finite) poset $P = (X, <)$, or partially ordered set, is a (finite) set $X$ equipped with a transitive antisymmetric relation $<$; it can be equivalently seen as a DAG $G = (X, E)$ that is transitive (whenever $(x, y) \in E$ and $(y, z) \in E$ then $(x, z) \in E$).

An automorphism of $P$ is a bijection $f$ from $X$ to $X$ such that $x < y$ iff $f(x) < f(y)$, in other words, both $f$ and $f^{-1}$ are order-preserving. The automorphism is fixed-point-free if there is no $x$ such that $f(x) = x$. Of course, the identity is always an automorphism (which is not fixed-point-free); other automorphisms are said to be non-trivial. Both automorphisms and fixed-point-free automorphisms are well-studied natural notions for posets; intuitively, posets that have non-trivial (fixed-point-free) automorphisms have a certain symmetry.

Is anything known about the complexity of determining if a poset has a non-trivial automorphism, or fixed-point-free automorphism? Or the complexity of counting the number of automorphisms, or fixed-point-free automorphisms?

For DAGs that are not transitive, determining if a DAG has a non-trivial automorphism is in NP and its complexity is unknown, like that of graph isomorphism (source). So, while the problem for transitive DAGs is still in NP, it should not be realistic to prove hardness as that would imply hardness of that open problem; but maybe the graph being transitive makes the problem easier (solvable in polynomial time)?

For other natural counting problems about posets, the problems of antichain counting (antichains are subsets of elements that are all pairwise incomparable), or of linear extension counting (linear extensions are the way to extend the partial order to a total order by adding more comparability relations), are all #P-complete to compute. (source and source). Is it also hard to count automorphisms, then?


texts: Relative Two-Function Hypercontractive Inequality $\langle T_{\rho\sigma} f,g \rangle \le \langle T_{\sigma} f,g \rangle^q$

texts:
The hypercontractive theorem (or Bonami Beckner inequality) says (Ryan O'Donnell):

This of course also directly gives the 'intermediate' inequality $\|T_{\rho\sigma}f\|_q  \le \|T_\sigma f\|_{1+(q-1)\rho^2}$.

The theorem also has a 'two function' version, which can be proven, for example using Holders inequality and then the standard theorem:

I'm wondering if anyone has studied 'intermediate' inequalities of this two-function version of the inequality? That would mean something like

$$\langle T_{\rho\sigma} f,g \rangle \le \langle T_{\sigma} f,g \rangle^q$$

for some value of $q$ depending on $\rho$ and $\sigma$.
It doesn't appear to follow easily from any of the individual theorems.

One thing we might try is to look at the normalized case, where we write:

$\langle T_{\rho\sigma} f,g \rangle
= \sum_{S\subseteq[n]}\rho^{|S|}\hat f(S)\hat g(S)$ and divide both sides by $\|f\|\|g\|$. Then we can use the means inequality to show

$$
\left(\frac{\langle T_{\rho} f,g \rangle}{\|f\|\|g\|}\right)^{1/\log\rho}
=
\left(\sum_{S\subseteq[n]}e^{|S|\log\rho}\frac{\hat f(S)\hat g(S)}{\|f\|\|g\|}\right)^{1/\log\rho}
\le
\left(\sum_{S\subseteq[n]}e^{|S|\log\sigma}\frac{\hat f(S)\hat g(S)}{\|f\|\|g\|}\right)^{1/\log\sigma}
=
\left(\frac{\langle T_{\sigma} f,g \rangle}{\|f\|\|g\|}\right)^{1/\log\sigma}
$$

whenever $\log\rho\le\log\sigma$.
However to be valid, this requires the values
$p_k = \sum_{|S|=k}\hat f(S)\hat g(S)$ to be non-negative for all $k$, which is certainly not the case for general functions $f,g:\{-1,1\}^n\to\mathbb R$.

It also doesn't appear to be very sharp, since it becomes equality when all the fourier mass is on level 1, which the hypercontractive inequalities usually tell us isn't possible for many (smaller) functions.


texts: Why is the circuit class AC0 unavoidable?

texts:
Take AC0.
What is a natural thought process that leads to the definition of AC0?
Does this class arise intrinsically anywhere?

My problem is that in the case of unbounded fan-in, AND and OR gates behave very differently. Why do we take these gates along with NOT to define a circuit class?


texts: Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$

texts:
Question

Given the language $L_n = \{ a^n \}$ for a natural number $n \geq 2$. Is there a symbol minimal context-free grammar $G$ that generates $L_n$ and contains a rule of the form $A \rightarrow aB$ where $A$ and $B$ are non-terminals?

Remark

Symbol minimal means that there is no other context-free grammar that generates $L_n$ with fewer characters (symbols) for all rules. For instance, the number of symbols of the rules in $\{ S \rightarrow a, S \rightarrow aS \}$ is 7 (these rules are also minimal for $\{ a \}^+$).

Known Results

Facts about G (a symbol minimal context-free language for $L_n$) that I have already proved:

The right hand side of the rules of $G$ consist of at least 2 characters (non-terminals and/or terminals) (otherwise it’s easy to find a grammar that has fewer symbols).
For each non-terminal of $G$ there exists exactly one rule (can be shown by contradiction).
There are no loops in the derivations of $G$ (because $L_n$ is finite).
There is an upper bound for the number of symbols: we can trivially generate $L_n$ with the rules $\{ S \rightarrow a^n \}$. We count the number of symbols and get $n + 2$ – that’s an upper bound.

I wrote a program that finds symbol minimal grammars for a specific $n$ by creating all possible grammars generating $L_n$ (there are only a finite number because we have an upper bound). Here are the results for some small $n$:

$n = 2$: $\{ S \rightarrow aa \}$, $4$ symbols
$n = 3$: $\{ S \rightarrow aaa \}$, $5$ symbols
…
$n = 7$: $\{ S \rightarrow aaaaaaa \}$, $9$ symbols
$n = 8$: $\{ S \rightarrow a^8\}$, $\{ S \rightarrow AA, A \rightarrow a^4 \}$, $\{ S \rightarrow AAAA, A \rightarrow aa \}$, $10$ symbols
$n = 9$: $\{ S \rightarrow AAA, A \rightarrow a^3 \}$, $10$ symbols
$n = 10$: $\{ S \rightarrow AA, A \rightarrow a^5 \}$, $\{ S \rightarrow A^5, A \rightarrow aa \}$, $\{ S \rightarrow aA^3, A \rightarrow a^3 \}$, $11$ symbols
$n = 11$: $\{ S \rightarrow aAA, A \rightarrow a^5 \}$, $\{ S \rightarrow aA^5, A \rightarrow aa \}$, $\{ S \rightarrow aaA^3, A \rightarrow a^3 \}$, $12$ symbols
$n = 12$: $\{ S \rightarrow AAA, A \rightarrow a^4 \}$, $\{ S \rightarrow A^4, A \rightarrow aaa \}$, $11$ symbols
$n = 13$: …,  $12$ symbols
$n = 14$: …,  $13$ symbols
$n = 15$: …,  $12$ symbols
$n = 16$: …,  $12$ symbols

There are nice „ups and downs“ in the number of symbols, right? I have seen grammars that contain rules like $A \rightarrow aB$ but they were not symbol minimal …


texts:
What machine learning classifiers are the most parallelizeable? If you had a difficult classification problem, limited time, but a decent LAN of computers to work with, what classifiers would you try?

Off hand it looks to me like some standard classifiers I know of stack up as follows but I could be totally wrong:

Random Forests - Very parallelizeable as long as each machine can hold all the data (i.e. can't divide up the training data per se, but otherwise parallelizeable).

Boosting - ?

Support Vector Machine - Not very parallelizable.

Decision trees - Can be divided up in part, but not very efficiently.


texts: Set:Set or Negative Inductives in a Total Language?

texts:
In total dependently typed languages, general recursion is forbidden, since this can allow for non-terimination. However, dependently typed language can still describe Turing-complete computations (without running them), using free monads (see also here).

However, recursion is not the only source of non-termination in dependently typed languages. Having $Set : Set$ allows for Girard's paradox, inductive data types must be strictly positive, since otherwise we can write an interpreter for the untyped lambda calculus.

I'm wondering, is there an equivalent of the General Recursion monad for describing (but not running) computations involving $Set : Set$ or non-strictly positive data types? Or is there a way that we can express these in terms of a general-recursion monad?


texts: Lambda: The Ultimate Imperative - who is Jensen?

texts:
One of the notes in the classical paper LAMBDA: The Ultimate Imperative says:

  {Jensensdevice}

  The technique of repeatedly modifying a variable passed call-by-name in order to produce side effects on another call-by-name parameter is commonly known as Jensen's device, particularly in the case where call-by-name parameters are j and a[j]. We cannot find any reference to Jensen or who he was, and offer a reward for any information leading to the identification, arrest, and conviction of said Jensen.

Today, after almost 40 years since the memo was published, do we know the identity of Jensen? I'm not hoping for the reward, just curious.


texts: What is the computational complexity of this SAT Variant

texts:
Given a 3SAT problem. The question being: 'This Problem has exactly K Solutions'?

Now, lets say K=1 (without loss of generality).

If the problem has a exactly 1 solution and the answer is True. So, the partial certificate is that 1 solution. the certificate is partial as it shows there is a solution but without guarantee of exactly 1.
If the answer is False. Then either it has 0 or more than 1 solution.

(a) In case of more than 1 solution, the certificate is any of the 2 or more solutions. This is a complete certificate.

(b) In case of 0 solution, the problem is same as asking does the given SAT have a solution. The certificate being same in 1.

Thus, the problem seems to require a certificate from both NP and co-NP versions. It seems to mean problem lies in NP and co-NP. But then it also is NP-hard. So doesn't that imply NP=co-NP?! What am I missing.


texts: What are some applications of computational geometry towards computer vision?

texts: I'm interested in both of these topics independently, and wondering some good applications of comp geom within the domain of vision.  What are some nice applications and potential projects of comp geom applied to vision?


texts: A good Library for testing whether a minors exists in a graph?

texts: I would like to know if there are any free graph libraries for testing whether a specific set of minors exists in a given graph?


texts:
Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a
structure as  $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; j=1,...,n$   and   $\sum_j x_{ij}=1$.
We define $P= CH (\cup_i  P_i)$ where $CH$ stands for the convex hull.

On the other side, we have another set of polytopes $Q_t: t=1,2,..., r$
each of which defined similarly as $Q_t:= \{(y_{t1},y_{t2},..., y_{tn})\; |\; y_{tj} \in
[c_{tj}, d_{tj}] \subseteq [0,1]\; \text{for all}\; j=1,...,n \;   \text{and}   \sum_j y_{tj}=1\}$.
Then we define $Q= CH (\cup_t  Q_t)$.

Please note that the number of polytopes $P_i$, i.e., k and the number of
polytopes $Q_t$, i.e., r are not necessarily equal. However, both polytopes
$P_i$ and $Q_t$ are defined in $\mathbb{R}^n$ as above.

Query: Is checking if $P=Q$ computationally hard?


texts:
In considering an answer to this question, I once again wondered how quickly we could find a digit in multiplication.

We may first consider previous results.  Finding the least significant digits is fairly obvious.  I was intrigued by this question, on Math.SE, which has several answers that show a mathematical series solution to obtaining the most significant digit to a division, albeit one with little necessary information.

This brings up a few questions.

(1) How quickly can we find the most significant digit in a multiplication (between two $n$-bit integers)?  (Just to clarify, I intended this to mean knowing the position of the digit itself.)  Can we find other most significant digits in approximately the same time?

(2)  How quickly can we find an arbitrary digit in multiplication?

(3) Is finding an arbitrary digit in multiplication as hard as multiplication itself?


texts:
Consider a 2D grid, and a given planar graph $G$ with $\Delta<4$ (max node degree) and without odd cycles. What conditions should $G$ satisfy so that when it is mapped (or embedded) into the 2D grid, the adjacency of the nodes is maintained (i.e., all adjacent nodes in $G$ remain adjacent in the 2D grid). Accordingly, after embedding of $G$ in the 2D grid, the shortest path distance between adjacent nodes is still 1.

The alternative question is what is the condition for a given planar graph (with $\Delta<4$ and w/o odd cycles) to be a 2D grid?

Thanks!


texts: Exactly solvable but non-trivial integrality gap

texts:
Are there interesting polynomial time solvable problems that we know of for which the natural convex relaxation has a non-trivial integrality gap?

Note: Maximum matching doesn't qualify because I consider natural the exponential-sized poly-time solvable LP.


texts:
Is there some example of a PSPACE problem that we can show PSPACE-hard under NP reduction, but we do not know a proof of PSPACE-hardness under P reduction ?
To be more precise, the NP reduction I am referring to is of the following kind: take your problem A that you want to show PSPACE-complete. You show that given an oracle for A, and an oracle for an NP-complete problem (the oracles are used separately, not nested in any way), you can solve a PSPACE-complete problem in polynomial time.
A related question is there, but it is not answered.


texts: Dividing users with certain files into 2 equal groups

texts:
I am framing a particular combinatorial question using users and files for better understanding.

Let there be a universe of files $F$ = $\{f_1, f_2,\ldots,f_n\}$ and $2k$ users $\{u_1, u_2,\ldots, u_{2k}\}$. Each user $u_i$ has a set of files denoted by $F(u_i) \subseteq F$.

Can the users be divided (whenever possible) into two equal sized group $G_1$ and $G_2$ in polynomial time in $n$, such that   $\mathcal{F}(G_1) = \bigcup_{u_i \in G_1} F(u_i)$ and similarly let
$\mathcal{F}(G_2) = \bigcup_{u_j \in G_2} F(u_j)$ satisfy the following conditions:

$$\mathcal{F}(G_1)\not\subset \mathcal{F}(G_2) \text{ and } \mathcal{F}(G_2)\not\subset \mathcal{F}(G_1), $$
where $\not \subset$ means "not a strict subset".

EDIT 1: The algorithm must to be polynomial time in $k$ and $n$.

Thanks in advance.


texts: Degree distribution of certain subgraphs of a biregular graph

texts:
Consider a bipartite graph $G=(X,Y)$, such that the degree of a left node $x \in X$ is $l$, and the degree of a right node $y \in Y$ is $r$. The number of edges is $|E|=|X|l=|Y|r$.

Pick $w$ nodes in $X$ in random. We take a subgraph of $G$ by connecting at random the $wl$ sockets of the chosen $w$ nodes to distinct right nodes $Y' \subseteq Y$. That is, the sample space is all the permutations from the $wl$ sockets to sockets in $Y$. In a valid subgraph, at least two sockets of each $y' \in Y'$  is connected.

I want to calculate the probability of a valid subgraph with a particular right-degree distribution. That is, what is the probability of a valid subgraph that has $c_1$ right-nodes of degree $r_1$, $c_2$ right-nodes of degree $r_2$ and so on.

I know how to calculate the probability that a subgraph is valid, which is

$$\frac{{{\rm{coef}}\left( {{{\left( {{{\left( {1 + y} \right)}^r} - 1 - ry} \right)}^{\left| Y \right|}},{y^{wl}}} \right)}}{{{|X|l \choose wl}}},$$
where ${{\rm{coef}}\left( {f\left( x \right),{x^i}} \right)}$ is the $i$th coefficient $f_i$ of $f\left( x \right) = \sum\limits_{i \ge 0} {{f_i}{x^i}}$. However, I am not sure how to proceed.


texts: When can a convex function induce submodularity?

texts:
Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$. Let $f'$ be the induced function on the discrete hypercube $\{-1,1\}^n$. Now I want to find a vertex on $\{-1,1\}^n$ on which either  (1) $f' < c$ for some given constant $c$ or (2) $f'$ minimizes.

Is either of these questions for any class of $f$ known to be solvable in $poly(n)$ time?
For any class of $f$ is $f'$ known to become submodular?

Typically I am dealing with a $f(\vec{x}) = SpectralNorm ( A + \vec{x}.\vec{M} )$ where the matrices are $2n$ dimensional real symmetric matrices with entries in $\{0,1,-1 \}$ , $\vec{x} \in [-1,1]^n$ and the matrices in the coordinates of the vector (in matrix space) $\vec{M}$ being simultaneously diagonalizable. Any advice specific to this class would be most helpful.


texts: What is the complexity of checking equivalence of two boolean formulae without NOT symbol?

texts:
Suppose I have two boolean formulae (propositions) $P_1$, and $P_2$ (can be assumed to be in CNF) over the same variables and such that there are no "NOT" symbols used.  I.e. only conjunction and disjunction are used but not negation.  Then what is the complexity of checking if $P_1$ and $P_2$ are equivalent (they are equivalent iff they agree on all inputs)?

By This answer, I know that if negation is allowed, this problem is co-NP complete.  It is also easy to see that if I simply wanted to check satisifiability for either proposition when negation is disallowed, I would have a linear time algorithm by simply setting all variables to true and checking if the proposition is true.

However, I am not sure what the complexity of checking equivalence in this case would be.  I could say that the two propositions are equivalent iff ($P_1 \wedge \neg P_2$) and ($P_2 \wedge \neg P_1$) are both unsatisfiable, but I can't use the linear time SAT algorithm above because now I have negation in these new propositions.

Can anyone help me figure out what the complexity of this problem is?

Much obliged!


texts: Is there an algorithm that, given a point cloud, infers an optimal wireframe (surface) structure?

texts:
I have a point cloud that I would like to convert to a surface, in the form of a wireframe lattice structure.

This means, from a sequence of 3D points (x,y,z), obtaining three 2D matrices X,Y,Z of the same size. In this way the points should be topologically related with a neighborhood of 4 (North, South, East, West). Such an organization of the points might, then, be plotted with functions such as matplotlib's Axes3D.plot_wireframe or Axes3D.plot_surface

From what I understood, the relationship of a point with the neighboring points is characterized by having minimal distance. I think that this is a combinatorial optimization problem, and NP-hard.

Now the question: are there algorithms that, given a list of 3D points, return the three aforementioned matrices X,Y,Z ?

Thank you very much. I also hope this is the correct stack exchange forum for this kind of question.


texts: Algorithms for finding unique solutions of NP-complete problems

texts:
The complexity of algorithms that find unique solution for an NP-complete problem (the input is guaranteed to have a unique solution) seems to shed light on the hardness character of different NP search problems. Two well known examples are the unique k-SAT search problem and solving Sudoku puzzle. As far as I know, the best algorithms for both are still exponential. I am interested in large gaps (if any exists) between the complexity of search algorithms for different NP-complete problems.
What complexity class does represent such search problems? Is there a survey paper of algorithms for such search problems?
This is motivated by two posts, NP-Complete problems that admit an efficient algorithm under the promise of a unique solution, and Examples where the uniqueness of the solution makes it easier to find.


texts: If we have an infinite string of 0's and 1's, such that no finite Turing-machine can output it. What can we say about the string? Must it be normal, ie. must every finite sequence appear infinite times as a subsequence at approriate rates etc?


texts: Efficiently picking free position from array with uniform probability.

texts:
For each array position it is known if position filled or not.

How efficiently pick one free position with uniform probability?

That task happen during implementation of AI by Monter-Carlo method for board game.

I have in mind:

uniformly pick random index of array and check position, repeat until success - this method is extremely bad for mostly filled arrays
count free positions, uniformly pick random number from 1 to count and scan for that free position - this method require 2 arrays scans

Is it possible uniformly pick free position with only one scan?

From my intuition this algorithm produce biased solution toward clustered arrays:

uniformly select index and scal to one side until find free position

What if for each free position picking generate random permutation without cycles and travel across all elements by uniformly choosing index and recursively applying permutation until free position was found? I don't know if this algorithm leads to uniform picking. I don't know how to represent computationally efficient subset of permutations. This way may produce one pass solution...


texts:
I am new to machine learning and I am considering the following problem:

Suppose you have clusters of points in $\mathbb{R}^N$ with $N$ large. The Johnson-Lindenstrauss lemma specifies how distances between points are preserved when reducing dimensionality. But what if I don't care about distances and I am only interested in keeping the clusters separate when projecting to one single dimension. Which condition should hold on the clusters for a random projections from $\mathbb{R}^N$ to $\mathbb{R}$ to be able to avoid the points in the cluster to overlap? Is there a result defining these conditions?


texts: Logic programming with integer or even floating point domains

texts:
I am reading a lot about logic programming - ASP (Answer Set Programming) is one example or this. They (logic programs) are usually in the form:

[Program 1]
Rule1: a <- a1, a2, ..., not am, am+1;
Rule2: ...

This set of rules is called the logic program and the s.c. model is the result of such computation - some kind of assignment of True/False values to each of a1, a2, ...
There is lot of research going on - e.g. how such kind of programs (rules) can be integrated with the (semantic web) ontologies to build knowledge bases that contain both - rules and ontologies (some kind of constraints/behaviour and data); there is lot of research about ASP itself - like parallel extensions, extensions for probabilistic logic, for temporal logic and so on.

My question is - is there some kind of research and maybe some proof-of-concept projects where this analysis is extended from Boolean variables to variables with integer and maybe even float domains? Currently I have not found any research that could address the following programs:

[Program 2]
Rule1 a1:=5 <- a2=5, a3=7, a4<8, ...
Rule2 ...
...
[the final assignment of values to a1, a2, etc., is the solution of this program]

Currently - as I understand - if one could like to perform some kind of analysis on Program-2 (e.g. to find if this program is correct in some sense - e.g. if it satisfies some properties, if it terminates, what domains are allowed not to violate some kind of properties and so on), then he or she must restate Program-2 in terms of Program-1 and then proceed in way which seems to be completely unexplored - to my knowledge (and I don't believe that is it unexplored, simply - I don't know some sources or trend). There is constraint logic programming that allow the use of statements with inequalities in Program-1, but it is too focused on Boolean variables as well. Actually - Programm-2 is of kind that can be fairly common in business rules systems, that was the cause of my interest in logic programming.

SO - my question has some history - my practical experience has led me to appreciate business rules systems/engines, especially - JBoss project Drools and it was my intention to do some kind of research of theory underlying s.c. production rules systems (I was and I am planning to do my thesis about them - if I would spot what can be done here), but I can say that there is little to do - after going over the literature (e.g. http://www.computer.org/csdl/trans/tk/2010/11/index.html was excellent IEEE TKDE special issues with some articles about them, one of them was writter by Drools leader) one can see that there is some kind of technical improvements of the decades old Rete algorithm but there is no theory of Drools or other production rule systems that could help with to do some formal analysis about them. So - the other question is - is there theory of production rule systems (for rule engines like Drools, Jess, CLIPS and so on) and is there practical need for such theory and what are the practical issues of using Drools and other systems that can be addressed by the theory of production rule systems.

p.s. I know - all these are questions that should be directed to thesis advisor, but my current position is that there is no (up to my knowledge) person in department where I am enrolled with who could fit to answer them, so - I am reading journals and also conference proceedings (there are nice conference series series of Lecture Notes in Computer Science - RuleML and RR)...

Thanks for any hint in advance!


texts: Can a result of (any) hash algorithm contain the hash result itself?

texts:
Suppose you have a file of 240 lines. Any lines, any content.
You then calculate the hash of that file, let's say MD5, and the result is something in the following structure:

f8dbe310c1f61066d766071b07503ce8

Now, you take this hexadecimal digest, and add it to the file as line 241.

Rehashing the file (with additional hash line) will result with a new hash value obiously.

My questoin is whether it is even theoretically possible for a hash value to contain itself, meaning, can there be a file, with some content that its hashed value is identical to a string already presented in the file (e.g. line 241 in this example)


texts:
An integer partition of $n$, $A$, is a multiset of positive integers such that $\sum_{a \in A} a= n$. We say that $B \leq A$, if there exists a map $\phi: |B| \to |A|$, such that for $a \in A$, we have $\sum_{b| \phi(b) = a} b = a$.

Given two integer partitions of $n$, $A$, $B$, I was wondering how hard is it to find the smallest $C$ satisfying both $C \leq A$, $C \leq B$. (by smallest, I mean minimizing $|C|$)

Are any polynomial time algorithms known for this problem?

Considering very simple approximations, I know that $|C| \leq n-\min_{X \in \{A,B\}} \sum_{x \in X} \left\lfloor \frac{x}{2}\right\rfloor$. I got this by considering splitting each $x$ into 2's and 1's. More generally we could say:

$$ |C| \leq n -\max_{k} \left((k-1)\min_{X\in\{A,B\}} \sum_{x\in X}\left\lfloor\frac{x}{k}\right\rfloor\right)$$


texts: Longest edge length of the greedy spanner on uniformly distributed pointsets in $[0,1]^d$

texts:
Let $P$ be a set of $N$ points in $\mathbb{R}^d$. For any $t \geq 1$, a $t$-spanner is an undirected graph $G=(P, E)$ weighted under the Euclidian measure, such that for any two points $v$, $u$, the shortest distance in $G$, $d(v, u)$, is at most $t$ times the Euclidian distance between $v$ and $u$, $|v u|$ (note that this definition can easily be extended to arbitrary measure spaces).

Consider the following algorithm with $P$ and $t$ as input:

E = empty
for every pair of points (v, u) in ascending order under |vu|
    if the shortest path in (P, E) is more than t times |vu|
        add (v, u) to E
return E

This algorithm computes the so-called greedy spanner (or path-greedy spanner). This graph has been subject to considerable research: it produces extremely good spanners, both in practice and in theory.

I'm interested in the length of the longest edge in the greedy spanner if $P$ is uniformly distributed in $[0,1]^d$ (the case that d=2 is fine as well). I conjecture this maximal length is at most about $1 / \sqrt{N}$, potentially with some log factors and factors $d$. This conjecture is motivated by experimental data.

The reason for my interest is that I have an algorithm that computes the greedy spanner quickly if the length of the longest edge is relatively short. If the above is correct, then it would mean my algorithm is applicable to the above scenario, and therefore potentially useful in practice.

I have found some papers analyzing the number of edges and the degree of other types of spanners on randomly distributed pointsets, but none on the length of the longest edge. The probability theory involved seemed rather complicated, so I was hoping something was known before attempting a proof myself.


texts: How to go from a DAG model to bounded treewidth?

texts:
I am cross posting this question from CS.SE since I believe it is research-related question.

Given a Bayesian Network DAG $G$, we can transform it into a junction tree $T_G$ by performing two steps:

moralisation (connect variables that have the same child, drop directions)
triangulation (fill-in edges) i.e chordal graphs.

Are there known conditions/assumptions over $G$ under which for any junction tree $T_G$, $T_G$ will have tree width at most $k$? In other words, bounded treewidth for the triangulated graph of $G$?


texts: Intermediate problems between PSPACE and EXPTIME

texts:
Intermediate problems between P and NP are quite famous, and are sometimes considered as complexity classes by themselves.

Do you know of any problem that is known to be PSPACE-hard and in EXPTIME, and resisting all efforts to be proved complete for one of these classes ?

Lifted (succinct) versions of problems between LOGSPACE and PTIME are accepted, but even more interesting would be problems that are not of this form.

Here are some I found, this area of complexity theory seems to be the realm of games:

Phutball: https://arxiv.org/abs/0804.1777
Go (with Chinese rules): D. Lichtenstein and M. Sipser, Go is polynomial-space hard


texts: Is there a better explanation of Hellman's paper on rainbow tables than the paper itself?

texts: I'm reading through Hellman's A Cryptanalytic Time-Memory Trade-off [PDF], and I was wondering if there is code out there that implements this or if there are better explanations of how a password could be decrypted using rainbow table method mentioned in this paper?


texts:
Are there any problems that are solvable in polynomial time only if P!=NP, and otherwise solvable in (say) $O(2^n)$ time?

A simple example would be: If P!=NP, compute a primality test for a random n-bit number, otherwise, evaluate a random worst-case position in generalized chess of a nxn board with 2n pieces on each side. That seems kinda hacky though. Are there any more natural examples?


texts:
How is the Property testing  is related to PAC model of learning?

More precisely,

Let we have given a property tester, $\mathcal{A}$, for the (concept) class of function $\mathcal{F_n}$  which receives as input a size parameter $n$ (labeled input $(x_1,f(x_1)), (x_2,f(x_2)),...,(x_n,f(x_n))$), distance parameter $0<\epsilon<1$,  confidence interval $0<\delta<1/2$, and does the following:

-if $f\in \mathcal{F_n}$, then with probability probability $(1-\delta)$ (over the choice of $x_i$'s) $\mathcal{A}$ accepts $f$.

-if $f$ is $\epsilon$-far from $\mathcal{F_n}$, then with probability probability $(1-\delta)$ (over the choice of $x_i$'s) $\mathcal{A}$ rejects $f$.

Now, I have following two questions:

1) Now, how this tester $\mathcal{A}$ can be used to generate learning algorithm (under PAC learning model) for the concept class $\mathcal{F_n}$, and vice versa. And how does VC-dim of $\mathcal{F_n}$ plays role in the reduction.

2) Can we give some sort of characterization (for example, on the basis of VC-dim) over the concept class for which  testing is easier/harder than  learning?

Pls let me know if I am not able to put the question clearly.

Thanks.


texts:
Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to select a minimum number of intervals $[l_i,r_i]$ such that for every $i=1,…,2n$, at least $d_i$ intervals containing the integer $i$ are selected.

It is not hard to see that $Q$ can be solved in polynomial time (see below).

Now consider the following slightly modified problem $Q’$: The input of the problem is the same as before. However, the task now is to select a minimum number of intervals such that for every $i=1,…,n$, at least $d_{2i-1}$ intervals containing the integer $2i-1$ or at least $d_{2i}$ intervals containing the integer $2i$ are selected (with “or” we mean the usual logical or).

My question: Can $Q’$ be solved in polynomial time?

Here are two ways to solve $Q$ efficiently:

A simple greedy algorithm: Sweep through the intervals from left-to-right and select only as few intervals as are necessary to “satisfy” the numbers $d_i$. Whenever there is a choice between different intervals, choose the one(s) with maximal right endpoint.

An integer program: For each interval $[l_i,r_i]$ introduce a decision variable $x_i\in\{0,1\}$ with $x_i=1$ iff the interval is selected. The objective is to minimize $ x_1+…+x_k$, subject to the constraints $\sum_{j:i\in[l_j,r_j]} x_j\geq d_i$. The constraint matrix of this integer program has the consecutive ones property and therefore the linear programming relaxation of this program has an integer optimal solution.

Thanks for any hints, and also for references!


texts: Are there subexponential algorithms for PLANAR SAT known?

texts:
Some NP-hard problems which are exponential on general
graphs are subexponential on planar graphs because the
treewidth is at most $4.9 \sqrt{|V(G)|}$ and they are exponential
in the treewidth.

Basically I am interested if there are subexponential
algorithms for PLANAR SAT which is NP-complete.

Let $\phi$ be a CNF formula on variables $x_i$ and the
$i$-th clause is $c_i$.

The incidence graph p. 5
$G$ of $\phi$ is on vertices $V(G)=\{x_i\} \cup \{c_i\}$
and edges $(x_i,c_i)$ iff $x_i \in c_i$ or $\lnot x_i \in c_i$.

$\phi$ is in PLANAR SAT if the incidence graph is planar.

  Are there subexponential algorithms for PLANAR SAT in terms of $\phi$?

I don't exclude the possibility reduction SAT to PLANAR SAT
to make this possible, though SAT still to be exponential
and $\phi$ is subexponential because of the increase in the size.


texts: Computational complexity of counting induced subgraphs which admit perfect matchings

texts:
Given an undirected and unweighted graph $G=(V,E)$ and an even integer $k$, what is the computational complexity of counting sets of vertices $S\subseteq V$ such that $|S|=k$ and the subgraph of $G$ restricted to the vertex set $S$ admits a perfect matching? Is the complexity #P-complete? Is there a reference for this problem?

Note that the problem is of course easy for a constant $k$ because then all the subgraphs of size $k$ can be enumerated in time ${|V| \choose k}$. Also note that the problem is different from counting the number of perfect matchings. The reason is that a set of vertices which admits a perfect matching may have multiple number of perfect matchings.

Another way to state the problem is as follows.
A matching is called a $k$-matching if it matches $k$ vertices.
Two matchings $M$ and $M'$ are ``vertex-set-non-invariant'' if the sets of vertices matched by $M$ and $M'$ are not identical. We want to count the total number of vertex-set-non-invariant $k$-matchings.


texts: What persistent data structure for a set of partially ordered elements?

texts:
I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable.

One problem with hashtables is that two equal elements can be represented differently, and I do not have access to a hashing function consistent with equality.

Comparing two elements can be a lengthy process so it would be interesting to minimize comparisons. If needed, it is possible to memoize calls to the comparison operator. I realize now that I will only need to store antichains (or let's assume so).
More precisely, the operations I will need to perform are as follows:

Remove an element from the antichain;
Try to add an element. If the element is smaller than a member, do not add it, otherwise, add it and remove every element smaller than it.

I can also bound every element by two integers, so that if I know that $i_1 < a < i_2$ and $i_3 < b < i_4$, then knowing $i_2 < i_3$ instantly gives me $a < b$. Of course, $i_2 \not< i_3$ does not mean $a \not < b$... Finding integer bounds is a relatively cheap operation in comparison to a full blown element comparison.


texts: Is the complexity of this covering problem known?

texts:
Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex set $S\subseteq V$ of minimum size such that $S\cap X\neq\emptyset$ for every critical set $X$.

The problem has the following rumour-spreading interpretation: Vertex $i$ spreads the rumour to its neighbour $j$ if and only if all other neighbours of $i$ are already informed. The question is then how many vertices do I have to inform initially to make sure that everybody is informed in the end.


texts: Randomness and small circuits complexity classes

texts:
Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined as $\textrm{BPP}$ with respect to $\textrm{P}$. More formally we provide polynomially many random bit and we accept an input iff the probability to accept is over $\frac{2}{3}$.

It is known that for non-uniform circuits class we have $\textrm{BPAC}^0=\textrm{AC}^0$:

  Miklós Ajtai, Michael Ben-Or: A Theorem on Probabilistic Constant Depth Computations STOC 1984: 471-474

Are generalizations of this theorem known ? For instance, do we know if $\mathrm{BPNC}^1=\mathrm{NC}^1$ (still in the non-uniform setting)? This last question seems somehow non trivial to me since it seems plausible that for instance $s,t\textrm{-Connectivity}$ is in $\textrm{BPNC}^1$.

A relevant post on the subject: https://mathoverflow.net/questions/35184/use-of-randomness-in-constant-parallel-time


texts: Reasonable estimate of an asymptotic limit notion of Kolmogorov complexity

texts:
Let $$f(c)=\min_{x \ge c} K(x)$$ where $K(x)$ is the kolmogorov complexity of $x$. Since $K(x)$ is always a natural number, there will always be a minimum. My question is, what is the growth rate of $f$? We know that $$f \in \mathcal O(1) + \log c$$ since $f(c)\le K(c) \in \mathcal O(1) + \log c$. We also know $f$ is increasing, since if $c_1 \ge c_2$, then $\min_{x \ge c_1} K(x) \ge \min_{x \ge c_2} K(x)$. We also know that $$\lim_{c\to\infty}f(c)=\infty$$ since otherwise a finite number of programs would be able to generate arbitrarily large outputs.

Can we get a tigher bounds on $f$? What is $f$'s growth rate?


texts:
After reading the literature on type theory (especially the constructive kind - CTT) I'm left wondering "why" should one study type theory, specifically within the confines of "computing" in general?

I understand how type systems (loosely speaking) were created to avoid various paradoxes and the correspondence between philosophy, logic, lambda-calculus and the how it comes together for CTT to serve as a foundation of mathematics. Fair enough.

Now, functional programming (FP) languages like Haskell, Scala that can be used in large projects are based on an inconsistent logic - making any kind of (automated) formal reasoning about them nearly impossible - but that seems to be the very need/power of TT! E.g., theorem proving and proof assistants and the notion of programs as proofs. But none of this carries over to FP languages.

So my question is trying to understand the bigger role i.e., interplay of TT and computing taken together. Most FP languages have just "good enough" type systems (e.g., Haskell > Java). The problem of "type inference" is in some way similar to "logical inference" and doesn't seem all that complicated for simple types. I'm guessing things become undecidable after a particular threshold. Fair enough. I understand its need till this level. But is that it? It seems one can understand type systems/inference without really diving into the details of TT per se.

Since FP languages don't really borrow much from TT other than "type systems/inference", why bother studying the theory in depth especially within computation theory? It seems that after studying a good deal of TT, for fun, I'm still left wondering "what did I gain" - both as a theoretician and a software practitioner? What "is" the aha understanding that one gains at a deeper level - since very little of TT's power/awesomeness actually gets carried over to commercially viable FP languages (and not Agda, Epigram etc.,)?

(PS: Here's a similar question on Math.SE- but that's from a mathematical POV and I get that from that perspective. I'm struggling to see TT's importance when concerned about computing and software engineering in general)


texts: Efficiently modeling Turing machines in Peano Arithmetic

texts:
The (undecidable) Peano Arithmetic (PA) is powerful enough to model Turing machines.
Consider a standard first order axiomatization of Peano Arithmetic and a standard Hilbert-style proof system $\mathcal F$.

Is it true that every first order informal proposition $P$ about computation and Turing machines has a corresponding formal formula $\varphi$ in Peano Arithmetic which is equal in size up to a polynomial blow-up: $|\varphi| = O(|P|^k)$ for some fixed $k$ which is independent of $P$?

Furthermore if $P$ has an informal short proof (polynomial in $|P|$), is it true that the corresponding $\varphi$ in PA has a polynomial length proof with respect to $|\varphi|$

As a trivial example consider the following Turing machine (in pseudocode):
M:
n=100
while n > 0 do n = n - 1

and the informal proposition: $P \equiv \text{ M doesn't halt in less than 90 steps}$
$P$ can be converted to a formula $\varphi$ in PA; and this $\varphi$ must "embed" a symbolic representation of M and some kind of operational semantic. But can the conversion be done efficiently (polynomial time and space)?
Furthermore there is a trivial "informal" short proof of $P$, but does the corresponding formal proof in PA ($\mathcal F \vdash \varphi$) have a polynomial length size with respect to $|\varphi|$?
Edit: as noted by Kaveh the "informal" term above is confusing.
I could restate the two questions above in this way: if $P$ is a true mathematical statement that is expressible both in ZFC (as $\varphi'$) and PA (as $\varphi$). Is it always true that $| \varphi | \in O(|\varphi'|^k)$ for some fixed $k$ independent of $P$? What about the size of the corresponding proofs in the two axiomatizations (assuming that $\varphi'$ is provable in ZFC and $\varphi$ is provable in PA)?
But this lead to another question:

Is it true that every "human written proof" that is expressible in ZFC has indeed an "efficient" representation in ZFC? i.e. a (rather informal) proof of $\#p$ pages in my favourite paper cannot become a $O(2^{\#p})$ long formal proof in ZFC ? :-)


texts: Is it possible to compute whether two functions are extensional equal?

texts:
If you have two functions implementing a different sorting algorithm, is it then possible to infer by source code that they both have the same external properties? Meaning that they both will have a possible unsorted sequence as their input and have a sorted sequence as their output? In what way could these external properties be determined by the source code? And how would you describe these external properties? What notation would be used?

The external properties could be made known by defining them explicitly, for example within a type system, but I am wondering whether this could be done implicitly. Or is it somehow theoretically impossible to infer this kind of semantics? I am interested in whether this is possible for arbitrary functions, not just for sorting algorithms, assuming things like functions will always halt and have no side-effects.

Should I look at denotational semantics, or is unrelated?

I'm interested in pointers to research in this area and to different terms used to describe the subject that might help my literature search.


texts: Efficient recalculation of the maximum flow when edge capacities are reduced

texts:
Assume that we have a (directed) graph $G(V \cup \{s, t\}, E)$ and an (integer) capacity function $c : E \mapsto \mathbb{N}$. Let $f : E \mapsto \mathbb{N}$ be a maximum $s-t$ flow on this graph. Suppose that some edge capacities are suddenly reduced; i.e. we now have to work with a capacity function $c_R : E \mapsto \mathbb{N}$ such that $c_R(e) \leq c(e)$ for all $e \in E$.

Can we efficiently "adjust" our old optimal flow $f$ to find the new optimal flow $f_R$ instead of recomputing the latter from scratch?

Note 1: Assume that the reduction is consequential; i.e. $c_R(e) < f(e)$ for at least one $e \in E$. Also, for the sake of simplicity, you can assume that the capacity is reduced for only one edge.

Note 2: One approach would be to treat the problem as an LP. In this case, capacity reductions will simply change variable bounds. Thus, we can use a warm-start capable LP solving method to get from $f$ to $f_R$. For example, if we used the dual simplex method (DSM), we can compute $f_R$ from $f$ via a (hopefully) small number of pivots, each of which involves $O(|V| \cdot |E|)$ arithmetic operations.

Note 3: This discussion tries to tackle the related (harder?) problem of adding/removing vertices and modifying the maximum flow.


texts: Is algorithmic information theory still evolving?

texts:
I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory.
The field seems very interesting for me, but it seems everything is the field was done before many years.

So my question is:
Is the field “alive” or is it pretty much closed?
Does it have open questions?

Thanks


texts: Is the 2016 implementation of Shor's algorithm really scalable?

texts:
In the 2016 Science paper "Realization of a scalable Shor algorithm" [1], the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of [2] and Table 5 of [3]. The 8-qubit requirement comes from the end of [4] which states that the number of qubits needed for factoring an $n$-bit number is $1.5n+2$ which for 15 is $1.5\cdot 4 + 2=8$.

The paper that uses only 5 qubits states that their algorithm "replaces a QFT acting on M qubits with a semiclassical QFT acting repeatedly on a single qubit", but the consequences of this on the complexity of the  algorithm was never mentioned in the paper.

Now there has been harsh criticism of the paper claiming to factor 15 in a "scalable" way, as they say in Section 2 that the complexity argument for Shor's algorithm no longer holds. However, this criticism has not been corroborated anywhere, and the Science paper keeps getting celebrated as a "scalable" version of Shor's algorithm. What is the complexity of the "scalable" Shor algorithm?

[1] Monz et al. (2016) Science. Vol. 351, Issue 6277, pp. 1068-1070
[2] Smolin et al. (2013) Nature. 499, 163–165
[3] Dattani & Bryans (2014) arXiv:1411.6758
[4] Zalka (2008) arXiv:quant-ph/0601097
[5] Cao & Luo "Comment on: Realization of a scalable Shor algorithm"


texts:
I am looking for a simple rejection-free algorithm to uniformly sample random labelled trees (i.e. to generate each of them with the same probability).

One possibility is to generate Prüfer sequences and convert them to trees, but this is not very simple when thought of as a construction procedure.  I was wondering is there was a simpler, more direct construction that still guarantees uniform sampling?


texts: All Pairs Shortest Path - Directed graph with integer weights

texts:
I don't understand how Distance Product works (or Min Plus Product). If we replace each argument in $A$ from $a_{i,j}$ to $x^{a_{i,j}}$ and each argument in $B$ from $b_{i,j}$ to $x^{b_{i,j}}$ and each and make the polinomial product on each row and column we'll get a matrix $C$ such $c_{i,j}= \sum_{\substack{1<k<n \\}} cx^{a_{i,k}+b_{k,j}})$.

We want the path, not only the distance, and for the path we must know $k$ which gives us the minimum $x^{a_{i,k}+b_{k,j}}$. So how do we extract k from it?
Why does the time of Distance Product is $O(n^{\omega}M)$? (where $\omega$ is the present lowest exponent for matrix multiplication and $M$ is the maximum value in the matrices).


texts: Is any related work to this m-trails problem ?

texts:
Yesterday, I discussed with one of my EE friends. She asked me an interesting problem and I simplify it by ignoring the bandwidth cost and model as following:
Given a graph $G=(V,E)$ with its path set $P=\{P_1,P_2,\ldots, P_m\}$ where $P_i$ is a path
between two points in $V$. A path $P_i$ is colored by red if only and only if one of it's edges is colored by red, i.e. $P^c=red$; otherwise $P_i$ is colored by blue, i.e. $P^c=blue$. Find a subset $P_s\subseteq P$ s.t. 1) If for every $j$ color all edges in $G$ by blue except only one $e_j\in E$ by red,
there is a subset $P_s' =\{P_1,P_2,\ldots,P_t\}$ in $P_s$ such that $f(P_1^c,\ldots,P_t^c)=e_j$ where f() is one-to-one mapping; 2) minimize the size of the result set $P_s$.

My questions are:
1) is there any similar work done in TCS?
2) is there any similar work done in graph theory?
3)2) is there any similar work done in networks?
3) any discussions about this problem are welcome.


texts:
I'm wondering what the best method obtained for the Valiant-Vazirani theorem is.  We can state the following criteria:

(1) First and foremost, has anyone been able to derandomize it?

(2) If not, what is the best running time for converting a SAT instances?  And how does this method work?  Can we somehow do better than the technique mentioned here?

(3) Out of curiosity, I'd also like to know the size bounds of the converted SAT formula.

The reason I ask is that I'm studying an algorithm that makes use of this, so I'd like to have the best technique available.


texts: Constructing a small (n,k)-Covering Matrices family

texts:
Let ${\cal A}$ be a set of $k\times n $ matrices over ${\mathbb F}_2$.
We call ${\cal A}$ a (n,k)-covering, if for every subset of columns
$I=(i_1,\ldots,i_k)\subseteq [n]$, there is a matrix $A \in {\cal A}$
such that the columns $(i_1,\ldots,i_k)$ in $A$ are linearly independent.
It is known that when choosing a random $k\times k$ matrix over ${\mathbb F}_2$
the probability that it is non-singular is at least half.
This means that if we pick at random a set of $r$ such matrices, the probability that for some $I=(i_1,\ldots,i_k)\subseteq [n]$ won't be covered (by any matrix $A \in {\cal A}$) is at most $2^{-r}$.
Since there are $n \choose k$ such $I$'s, the probability that one of them will not be covered is at most (union bound):
$${n \choose k} \cdot 2^{-r}.$$
If we force this probability to be strictly lower than 1 (which ensures such family of size $r$ exists), we get:
$${n \choose k} \cdot 2^{-r}<1 \Rightarrow r > k \log n.$$
Is there a deterministic build of such family of size $O(k \log n)$, or at least of size $\text{poly}(k,\log n)$?
Motivation for this problem:
I have an algorithm that searches for subgraphs of a given graph $G$ which are similar to a smaller graph $H$ on $k$ vertices.
As part of the algorithm it gets a $k\times n$ matrix (each vertex in the graph is associated with a binary vector of length k) and then it checks that all of the vertices which are matched to $H$ are different by checking that the induced $k \times k$ matrix is not singular.
On the one hand, if two vertices of $H$ were mapped to the same vertex, their vectors are the same and the matrix's rank will surely be less than $k$.
On the other, I'm not guaranteed that if the vertices were distinct the resulting matrix will be of full rank, so I run the algorithm for every matrix in my $(n,k)$-covering family.
Currently I can draw random matrices and get the result with high probability, but an explicit build will allow me to derandomize the algorithm.


texts: On algorithms that minimizes maximal load of bins

texts: There are $n$ bins and $m$ balls, $b_i$ where $0<i\le m$. Balls are with different weights $w_i$ and have dependency between them. ball $b_1$ depends on $b_2$, $b_2$ depends on $b_3$, and so on. It means that $b_1$ can be assigned with $b_3$ only when $b_2$ is assigned to the same bin. Is there an algorithm that assigns balls into $x<n$ bins so that maximal load of these bins is minimized.


texts: Lower bound for Yao's algorithm on general addition chains?

texts:
An addition chain of size $n$ for given integers $n_1,n_2\dots ,n_p$ is a sequence of integers $k_1,k_2\dots ,k_n$ such that

$k_1=1$,
for all $i$ $(2\le i\le m)$ we have $k_i=k_j+k_m$ for some $1\le j,m<i$
and $\{n_1,n_2\dots ,n_p\}\subseteq \{k_1,k_2\dots k_n\}$.

The general addition chain problem is the following:

Given: Numbers $n_1,n_2,\dots,n_p$
Problem: Compute a smallest addition chain for $n_1,n_2,\dots,n_p$.

This problem is known to be $\mathsf{NP}$-hard by [Dow81]. However, Yao [Yao76] presented an algorithm which on any input produces an addition chain of size
$$ \log N +c\cdot\sum_{i=1}^p\frac{\log n_i}{\log \log (n_i+2)}\le \log N +\frac{cp\log N}{\log \log (N+2)},$$
where $N=\max_i(n_i)$ and $c$ is a constant.
In [Cha05] it is now claimed that this is an approximation algorithm for the general addition chain problem of ratio
$$O\left(\frac{\log\left(\sum_i n_i\right)}{\log\log\left(\sum_i n_i\right)}\right),$$
i.e., Yao's algorithm produces for each input a chain which is at most by this factor larger than a smallest addition chain.
Now my question: Is there a lower bound on the approximation ratio of Yao's algorithm, e.g. is there a family of inputs such that Yao's algorithm produces addition chains which are by the described factor larger than a shortest addition chain?
$ $
$ $
[Dow81]: P. Downey, B. Leony, and P. Sethi, "Computing Sequences with
Addition Chains", SIAM J. Computing, vol. 11, pp. 638-696, 1981
[Yao76]: A. C.-C. Yao, “On the evaluation of powers”, SIAM J. Comput., vol. 5, no. 1, pp. 100–103, 1976
[Cha05]: M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, A. Shelat, "The Smallest Grammar Problem", IEEE Transactions on Information Theory. 51 (7): 2554–2576, 2005


texts: Assessing the unavoidability of a set kof structures?

texts:
Consider a family of structures equipped with a "sub-structure" relation - e.g. subwords, subpermutations or induced subgraphs. Given a set of structures $\cal{K}$, we denote by $Av(\cal{K})$ the family of structures $S$ that do not contain any element of $\cal{K}$ as a sub-structure. We say that $\cal{K}$ is unavoidable if $Av(\cal{K})$ is finite, i.e. every sufficiently large structure contains an element of $\cal{K}$.

I'm not knowledgeable on this subject but it seems to have interesting aspects. In particular I'm interested in the following problem: given a set $\cal{K}$, what is the complexity of deciding if $\cal{K}$ is unavoidable? Without a single glance at the literature I'm pretty sure that this is easy for words, but the kinds of objects I'm interested in seem to lie at the border (mainly permutations / languages / trees) and it's not clear to me on what side they fall ($\sf{P}$ or $\sf{NP}$-hard).


texts: Efficient algorithm for finding directed cycle with smallest average weight

texts: Suppose we have a strongly connected directed graph with non-negative weights on its edges. Is there an efficient algorithm to find the directed cycle with the smallest average weight in the graph? (Here, smallest average weight of a directed cycle is the sum of the weights of all edges in the cycle divided by the number of edges.)


texts: What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?

texts:
What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates?
What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates can be solved in $2^{(n-n^\alpha)}poly(nm)$ time?


texts: Origins and applications of Theory A vs Theory B?

texts:
In a couple recent questions (q1 q2), there has been discussion of "Theory A" vs "Theory B", seemingly to capture the divide between the study of logic and programming languages and the study of algorithms and complexity.

This terminology was new to me, and a quick web search didn't come up with any obvious references explaining it.

Does anyone know of a reference or references that explain the origin of this terminology, and what, if any, substantive benefit is intended to be derived from making this distinction?


texts: Distributed Elections using Logical Clocks (hints and tips)

texts:
I need to implement one of the logical clock algorithms (described here), to allow me to coordinate an election protocol for a distributed system. I'm struggling to work out how I might go about using the clock to enforce a total ordering on a sequence of events in practice. i.e. I don't see a problem in implementing the data structures in practice, but I can't work out how to ensure that my election is not being duplicated elsewhere in the network.
For example, if my 'master' machine goes down, I expect several machines to notice at round about the same time. There will be contention for the 'master' position as several machines try to take it over. My plan is for each machine to broadcast a 'grab the master position' message. Using a logical clock, I should be able to decide what was the globally first machine that sent the message. It will then be acclaimed the master. What I can't work out is how (and where) I will be able to create that ordering over the network messages.
Has anyone out there implemented this sort of algorithm and can offer me some guidance on how I should go about solving the problem?
Thanks in Advance.


texts: Complexity of #PP2DNF where we also count on the number of clauses

texts:
The #PP2DNF problem is the following: we have variables $X = \{x_1, \ldots, x_n\}$, $Y = \{y_1, \ldots, y_n\}$, and a positive partitioned 2-DNF formula, i.e., a Boolean formula of the form $\phi = \bigvee_{1\leq i \leq l} x_{p_i} \land y_{q_i}$, and we want to count its number of satisfying assignments, i.e., the number of Boolean functions from $X \cup Y$ such that $\phi$ evaluates to true under this valuation. This problem is well-known to be #P-hard by the work of Provan and Ball (sorry, no open-access version).

I'm interested in a variant of the problem where we also want to count on the clauses. Specifically, seeing $\phi$ as a set of clauses, I want to count the number of pairs $(\phi', \nu)$ of a subset of the clauses $\phi' \subseteq \phi$ and of a valuation $\nu$ of $X \cup Y$ such that $\phi'$ evaluates to true under $\nu$. For instance, if $\phi$ has two clauses, i.e., $\phi = C_1 \lor C_2$, I will count the number of satisfying valuations of $\phi$, plus the number of satisfying valuations of $C_1$, plus the number of satisfying valuations of $C_2$, plus 0 (the empty disjunction is always false). Equivalently I want to compute $2 n_1 + 2 n_2 + 3 n_{12}$ where $n_1$ is the number of valuations satisfying $C_1$ but not $C_2$, $n_2$ is the number of valuations satisfying $C_2$ but not $C_1$, and $n_{12}$ is the number of valuations satisfying both.

Is this version of the problem also #P-hard?

Another equivalent way to phrase the problem is in terms of bipartite graphs: we can see $\phi$ as a bipartite graph between $X$ and $Y$ (each clause being an edge, and #PP2DNF asks about the number of subsets of $X \cup Y$ that contain some pair of vertices that are connected by an edge (i.e., how many subsets are not independent sets). My version of the problem asks how many subsets of the vertex and edge sets there are such that we kept two vertices and an edge between these two vertices.


texts:
Let $f_i \in FP$ and $g_i \in \#P$ for $i \in \mathbb{N}$.
It is known that: $f_1(f_2(x)) \in FP$ and that $g_1(f_1(x)) \in \#P$.
Is it known whether or not $f_1(g_1(x)) \in \#P$ or maybe $f_1(g_1(x)) \in GapP$?


texts:
Suppose you have a sequence generated by an i.i.d. process (such as repeatedly rolling a die and recording the values in order) parameterized by some K-dimensional vector $\vec{\gamma}$ (the probabilities associated with each side of the die), which is unknown. But, if you assume some distribution $Q$ on $\vec{\gamma}$, you can calculate the probability of a sequence (where $n(k)$ is the number of times symbol $k$ appears in the sequence): $$P(seq) = \int P(seq|\vec{\gamma}')Q(\vec{\gamma}')d\vec{\gamma}' = \int \prod_{k=1}^K \gamma_k' ^{n(k)}Q(\vec{\gamma}')d\vec{\gamma}' $$
Then $-\log P(seq)$ is the code length. I believe this code length is equal to $$-n\sum_{k=1}^K \vec{\gamma}\log \vec{\gamma}+\frac{K-1}{2}\log n +O(1),$$ where the $O(1)$ term approaches a constant as $n \rightarrow \infty$. Can someone help me find the $O(1)$ term, or its value as $n\rightarrow  \infty$ in terms of $\vec{\gamma}$, $n$ and $k$ (Or, even just proving that this limit exists would be good too.)?


texts: In the context of regular languages, must the alphabet be finite?

texts:
In The Theory of Parsing, Translation, and Compiling, Volume I, Section 0.2.1 (p.15 / 1972), Aho and Ullman casually write that "[a]n alphabet need not be finite or even countable, but for all practical applications alphabets will be finite."

However, in Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Section 1.5.1 (p.28 / 2007), Hopcroft, Motwani and Ullman state that "[a]n alphabet is a finite, nonempty set of symbols." Further, Sipser "define[s] an alphabet to be any nonempty finite set." (Introduction to the Theory of Computation, 3rd Edition, Section 0.2 (p.13 / 2013).)

Is it correct that an alphabet may be infinite, even uncountably so? If so, are there any resources that discuss infinite alphabets?


texts: parametrized logspace algorithm for k-dominating set for planar graphs

texts:
$k$-Dominating set:

Given a graph $G=(V,E)$ where $V$ is a set of vertices and $E$ a set of edges, and an integer $k$, the $k$-Dominating set problem determines if there exists a subset of vertices $V′$ of $V$ of size at most $k$, such that for every Vertex $u \in V$, there is an edge $uv \in E$ for some vertex $ v \in V'$.

It is easy to see $k$-Dominating set problem for planar graphs in $O(f(k)\log n)$ space.

Can we solve the $k$-Dominating set problem for planar graphs in $f(k)+c \log n$ space where $c$ is some constant.

Answer to this question is yes[link] Page 11 theorem 2.4.

Their proof based on the FPT algorithm for finding the $k$-Dominating set problem for planar graphs [link] page 11 theorem 2.4.

Can we get the simple proof or process for finding the $k$-Dominating set problem for planar graphs in $f(k)+c \log n$ space where $c$ is some constant?


texts: Implication of lower bounds in Boolean circuit to other models of computation

texts:
Suppose that one can prove that some hard function $f$ with $n$ bit input does not admit any Boolean circuit of size at most $n^t$.

Then, how strong can we say about how hard $f$ is in other models? The other models are, for example, pointer machine or Word RAM model, or decision tree.

Can we get a lower bound of $n^{t-1}$ or even $\tilde{\Omega}(n^t)$ for instance ?


texts: Can two strings be matched as disjoint subsequences of a string?

texts:
Consider a fixed finite alphabet $A$. I am given as input two strings $S_1$ and $S_2$ on $A$, and a string $S$ on $A$. It is of course possible in PTIME to determine whether $S_1$ is a (non-contiguous) subsequence of $S$, and likewise for $S_2$. But now I ask whether I can have matches $m_1$ and $m_2$ of $S_1$ and $S_2$ as subsequences of $S$ ($m_k$ for $k \in \{1, 2\}$ is a strictly increasing function from $\{1, \ldots, |S_k|\}$ to $\{1, \ldots, |S|\}$ such that, for all $i$, $S_k[i]$ and $S[m_k(i)]$ are the same letter) such that $m_1$ and $m_2$ are disjoint (that is, their images are disjoint). Intuitively, no character of $S$ matches $S_1$ and $S_2$ simultaneously.

Is there a PTIME algorithm to determine this (in the size of the input $S_1, S_2, S$), or can it be shown to be NP-hard? I would suspect it is NP-hard but I cannot see a reduction.

In case it is in PTIME, what about the straightforward generalization, for a constant $k$, where $k$ strings are given as input and I ask for the existence of pairwise disjoint matches of all $k$ strings?

(This problem is a bit related to How hard is unshuffling a string? except the candidate strings can be different, are provided as input, and are not required to cover the entire string $S$.)


texts: Some good Theoretical Computer Science Journals

texts: I have been doing some work in Theoretical Computer Science(especially related to algorithms), and I wanted the publish some of my findings. Can someone please suggest some good journals or publications in the same area.


texts: Can Suffix trees be used to find all common substrings?

texts:
I am trying to use suffix trees to compare string sequences. I have found implementations/theory for the longest common sub string problem using suffix trees.
However, What i am looking for is a discussion of the related problem - "all common substrings".
Specifically, I have a problem in which i need to first find the longest common substring, then find the next longest common substring that does not include the already found lcs indices, and so on until a minimum length. Is this problem solvable by constructing the Generalized suffix tree (GST) only once for the two sequences. I know it can be solved by repeatedly constructing a GST after every iteration of finding and removing the LCS. But, I am wondering if i am missing a neat trick where in the GST is constructed only once.


texts: Problems between NC and P: How many have been resolved from this list?

texts:
In the paper "A Compendium of Problems Complete for P" by Greenlaw, Hoover and Ruzzo (PS) (PDF), there is a list of problems in P that are not known to be in NC and not known to be P-complete either. (This list subsumes all the open problems in the excellent survey by Karp and Ramachandran.) The open problems list starts on page 89.

How many problems from this list have been resolved (i.e., shown to be P-complete or in NC)? I'm guessing not too many have been solved in the last 19 years, so this (hopefully) shouldn't turn into a big-list.

That's the most recent list I could find. Pointers to a more up-to-date list would also be appreciated!

EDIT: András Salamon points out that there is a textbook by the same authors which has a slightly longer list. This is a PDF of the book. The open problems start on page 237.


texts: Semantic equivalence using a model of computation of two languages

texts:
I am relatively new to the field of language semantics. However i had a question pertaining to language equivalence (i did read about the question, however my approach is slightly different and hence this question).

If i have two languages $A$ and $B$ and both languages can be expressed using a model a computation like $\pi$-Calculus. If i have to prove that the 2 languages are equivalent, then would it be need to show that the 2 $\pi$-Calculus constructs (starting from the most atomic elements of the language to then the composition of the elements etc) of the two languages are equivalent, is this correct?

How do we prove equivalence between two $\pi$-Calculus representation of the languages?. Can i use bisimulation in $\pi$-Calculus to prove the same or have i missed something and is there another formal proof to do the same?


texts:
In the the standard library of Coq, there is the axiom:

Axiom JMeq_eq : forall (A:Type) (x y:A), JMeq x y -> x = y.

Why isn't it provable? Can it be reduced to more elementary axioms? Is it consistent with impredicative Set? Is there the same axiom in Agda?


texts: Functions and Counting Problems in Streaming Computation

texts:
I have read a stream computation paper in STOC07(Paul Beame, T. S. Jayram, and Atri Rudra. Lower bounds for randomized read/write stream algorithms.) and FOCS08（Paul Beame and Trinh Huynh. On the value of multiple read/write streams for approximating frequency moments).
I am interested in this topic with design of algorithms and analysis of limitations.

I want a list of natural counting functions, which stream algorithm theorists often consider like NPcomplete problems list by Garey and Johnson .

Is there such a list ?


texts: The relationship between completeness and strength of reductions

texts:
Ladner theorem can be stated as:

$P \ne NP$ if and only if there exists an incomplete set in $NP-P$.

Here an incomplete set is a set that is not complete for $NP$ under many-one polynomial time reductions (Karp reduction). Therefore, existence of any incomplete problem in $NP$ would immediately imply $P \ne NP$.

  Is there a many-one reduction weaker than Karp reduction for which we can prove the existence of incomplete sets in $NP$?

An example of weak reductions is $NC^0$ many-one reduction (using circuits of polynomial size, constant depth, and bounded fan-in). In an $NC^0$ reduction, each output bit of the reduction can depend only on a constant number of input bits. Many $NP$-complete problems remain complete under $NC^0$ reductions.

  Does there exist an incomplete $NP$ set under $NC^0$ reductions?


texts:
A quick Google search didn't turn up anything obvious, so I'm asking here.

Converting direct style programs to continuation-passing style is a well-studied program transformation. However, I'm interested in the reverse transformation -- I'd like to take a program in CPS, and convert it to direct-style. Obviously the identity trasnformation works, in a vacuous sense, but I'm interested in transformations that are "as direct-style as possible".


texts: Distributive expansion of CNF and implicants

texts:
I am looking for references for the following theorems.

Theorem 1: Distributive expansion of a CNF formula $P_c$ (product of sums)
results in a DNF formula (sum of products) consisting of all prime
implicants for $P_c$. $P_c$ is called a Blake canonical form BCF.

Theorem 2: If we transform a disjunctive clause $C_d$ with $k$ literals to a
disjunctive clause of conjunctions $C_m$ by replacing each literal
$l_i, i = (1, ..., k)$ with the conjunction $(\neg l_1 \wedge
... \wedge \neg l_{i-1} \wedge l_i)$, then $C_m$ will be logically equivalent to $C_d$. The clause $C_m$ is called a
clause with maximized conflicts.

Distributive expansion of $C_m$ shows that it is logically
equivalent to the unmaximized clause $C_d$, $C_m = C_d$.

Theorem 3: Distributive expansion of a CNF formula with maximized conflicts
$P_m$ (product of sums of products), with simplification of
outermost clauses before innermost clauses, results in a DNF
formula $P_u$ (sum of products) defining a set of (not
necessarily prime) implicants $I_u$ for $P_m$. The
implicants from $I_u$ cover all possible solutions for
$P_m$.  The implicants $I_u$ are unique, in that no
implicant $M_i \in I_u$ covers the solutions of any other
implicant $M_j \in I_u, i \ne j$.

Motivation:

With the discussion in [BROWN] I have finally found the last
piece of the puzzle.

Obviously, the restrictions for syllogistic formulae --- namely
removal of duplicate literals and elimination of clauses with
contradictory literals --- have been loosened over time. However, this
seems to have been a process of ad hoc reasoning.

I am missing an exhaustive formal discussion of the
consequences. I.e., the set of logically equivalent DNFs
represented by their minimal form of a disjunction of "atomic"
literals and the influence on the resulting DNFs of partial
assignments, which always cover all possible solutions, albeit in
different ways.

In order to find out, whether I have to do all of that on my own,
I use theorem 3 to show, that besides the well-known Blake canonical
form BCF, other non-trivial DNFs of implicants with different
properties appear, when the input clauses are generalized from
CNF to allow non-syllogistic representations, namely the DNFs
from theorem 2. Since that also requires a different order of
evaluation which is highly non-intuitive to simplification
junkies, I assume that I am out of luck.

It can especially be shown that for selection problems in "direct
encoding" (Chapter 2, Handbook of Satisfiability), the input based on theorem 2 alone allows a CDCL solver to solve the problem with
significantly less decisions than with plain CNF. Small problems
(currently 40 variables, 171 clauses) are even solved earlier with the
generally less effective "direct encoding" than with the original CNF
encoding. Note, that there is actually never a set of implicants
generated in that case.

I have prepared a PDF with examples to illustrate the effects.


texts: Sensitivity and Low-Degree Approximation under Non-Uniform Distribution

texts:
I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between the different input bits. I know of $p$-biased analysis, but I'm facing the setting where there can be correlations between the different input bits $x_i$.

Specifically, I have the following question.

Background: The average sensitivity of a Boolean function $f : \{-1,1\}^n \rightarrow \{-1,1\}$ is $as(f) := \mathbb{E}_x[s(f,x)]$, where $s(f,x)$ is the number of Hamming neighbors $x'$ of $x$ such that $f(x) \neq f(x')$. Here, the expectation $\mathbb{E}_x$ is over the uniform distribution over $\{-1,1\}^n$.
In this setting, low average sensitivity guarantees approximation by low-degree polynomials:
If $\hat{f}(S)$ is the Fourier coefficient associated to the set $S \subset \{X_1, \dots, X_n\}$, then $as(f) = \sum_{S} |\hat{f}(S)|^2 |S|$ (e.g. shown in Section 3.3 of Ryan O'Donnell's tutorial https://www.cs.cmu.edu/~odonnell/papers/analysis-survey.pdf).
Therefore, by Markov's inequality and the Parseval theorem, a polynomial of degree $as(f)/\epsilon^2$ is sufficient to approximate $f$ up to $\ell_2$ error $\epsilon$.

My question is: Is there any known way to generalize this to the setting where the distribution of $x \in \{-1,1\}^n$ is not uniform?
That is, is there an average-sensitivity-like measure that bounds the degree of a polynomial approximating the function in $\ell_2$, where all expectations over input strings $x$ are taken w.r.t. the given non-uniform distribution? (Complexity measures other than polynomial degree are also welcome.)

I can think of a couple of generalizations of average sensitivity that appear reasonable to me. To give a specific example, take the following averaged version of block sensitivity:
$$\max_{d} \sum_{i=1}^{|d|} Var[f|X_i : X_i \not\in d_i]$$
where $d$ runs over all partitions of $\{X_1, ..., X_n\}$ into disjoint subsets.
This measure evaluates, for each subset $d_i$, how sensitive $f$ is to that specific subset, on average across the input strings $x$ distributed according to the given nonuniform distribution. For the uniform distribution, it is equal to the ordinary average sensitivity $as(f)$.
Can this, or a similar, sensitivity measure tell us something about the polynomial degree (or decision tree depth, ...) needed to approximate $f$ in $\ell_2$ (or some other metric)?

Any pointers, ideas, or thoughts would be extremely appreciated! Thanks for your help!

Addition: Why is the `standard' definition $as(f) := \mathbb{E}_x[s(f,x)]$ not a sufficient answer? (Responding to question asked by Stella Biderman): First, I don't know how to prove in the non-uniform setting that low average sensitivity entails approximability with low-degree polynomials, as is known in the uniform setting.
Second, it seems to provide answers that do not match the polynomial degree necessary for approximation: Consider the distribution $P_0$ putting almost all ($1-\epsilon$) of its mass on $1^n$, and let $f$ be the PARITY function. Then $\mathbb{E}_{x\sim{P_0}}[s(f,x)] = n$, even though $f$ is almost a constant function.
If low average sensitivity corresponds to low-degree approximability (as is the case for the unifrm distribution), then this is undesirable, as a constant is sufficient to approximate $f$ up to $\ell_2$ error $\epsilon$, under the given distribution.
In contrast, the proposed sensitivity metric $\max_{d} \sum_{i=1}^{|d|} Var[f|X_i : X_i \not\in d_i]$ gives a value of about $\epsilon$.


texts: Exhibiting an adversary to prove a boolean function is evasive

texts: I'm trying to collect examples of exhibiting an adversary to prove that a Boolean function is evasive. I know of several examples of graph properties for which adversary methods have been used, i.e. graph connectedness and containing a triangle, however I'm hoping to find other interesting examples.


texts: Reference request: Shortest homotopic curve via vertex releases

texts:
Let $C$ be a piecewise-linear path (or closed curve) in the plane, in the presence of polygonal obstacles. We would like to find the shortest path (or curve) homotopic to $C$. (A path $D$ is homotopic to $C$ if it has the same endpoints as $C$ and can be obtained from $C$ by modifying it continuously, without crossing any obstacle and without moving the endpoints. For curves the definition is the same except that there is no endpoint requirement.)

Here is a simple algorithm for finding $D$. Is there any reference to it in the literature?

Call a path vertex $v$ "unstable" if it does not touch any obstacle, or if it touches an obstacle but the obstacle lies on the side of $v$ at which the angle is larger than 180 degrees.

An unstable vertex can be "released" resulting in a shorter path, as follows: Let $v$ be an unstable vertex, and let $u$, $w$ be the previous and next vertices of $C$. Let $\Delta$ be the triangle $uvw$, and let $S$ be the set of obstacle vertices contained in $\Delta$. Let $u, z_1, \ldots, z_k, w$ be the sequence of vertices of the convex hull of $S\setminus\{v\}$ in order. Then we replace $v$ by $z_1, \ldots, z_k$. The new vertices $z_i$ will necessarily be stable, but $u$ and $w$ might change from stable to unstable or vice versa.

So then the algorithm is: As long as there is an unstable vertex, pick an arbitrary unstable vertex and release it.

This works also for self-intersecting paths or curves with no problem.

If we allow point obstacles, then we also need to keep information of the "wrap" angle of the curve around each obstacle point. Then the curve is unstable if and only if the wrap angle is between -180 and 180 degrees.

Is there any mention in the literature of this simple algorithm?

The standard approach (which might be more efficient, though perhaps more cumbersome) uses a "funnel", and involves triangulating the empty space. See for example these course notes by Jeff Erickson: http://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf

[Added: For the record, this algorithm was found in joint work with Sergey Avvakumov.]


texts: Minimum Degree Spanning Tree Without Restricting Vertices Searched

texts:
This is reposted from cs.stackexchange. I asked the question more than two weeks ago and got no answers, so I thought to repost here.
I am currently self studying approximation algorithms from The Design of Approximation Algorithms (Williamson and Schmoys; page 50 here), specifically the minimum-degree spanning trees (MDST) problem. Given a graph $G$, we need to find a spanning tree $T$ that minimizes the maximum degree of any vertex in $T$.
I understand that the local search algorithm attempts to look at vertices with degree at least $\Delta(T)-\lceil \log_2(n)\rceil $ and try to improve it, and only stops when one cannot improve any such vertex. I understand that this restriction is done to polynomially bound the run time of the algorithm.
My question is, what approximation ratio can we get if we try to improve any vertex? I understand that we cannot show that it runs in polynomial time, but what approximation ratio would hold? Obviously the $2OPT+\lceil \log_2(n)\rceil$ still holds, but can we improve the ratio by trying all vertices? I tried to read the original paper which had another local search algorithm with cost $OPT+1$, but I am not able to prove that this locally optimal tree for all vertices is also an $OPT+1$ algorithm.


texts:
Looking at models of parametric polymorphism, I am curious why are
reflexive graph categories are used?

In particular, why do they not include relational composition?
In looking at the models, they all seem to support a natural notion of
relational composition:

$$ x(R;S)z \iff \exists y. xRy \wedge y S z$$

Most recent papers that use reflexive graphs seem to take this for
granted, and the only older paper I could find that discussed it was
"Relational Parametricity and Local Variables" by O'Hearn and Tennent
who say:

  One reason for not requiring composability is that, as is well known,
  composition is not preserved by logical relations at higher types.

And I'm not quite sure what this means, so my first question is what
is meant by this and hopefully a better reference on this question.

What I think this means is that for instance the exponential doesn't
necessarily preserve relational composition on the nose. In particular
we can't show $(R;R') \to (S;S') \equiv ((R \to S);(R' \to S'))$.
This means that the exponential doesn't extend to a functor on a
category of relations.

However, while I can't show the equivalence between the above
relations, I can certainly prove an inclusion $((R \to S);(R' \to
S')) \subset ((R;R') \to (S;S'))$, right?

Given $f((R \to S);(R' \to S')) h$, then there exists a $g$ of
appropriate type with $f(R\to S)g(R'\to S')h$, so given an $xRyR'z$, I
can show $f(x) S g(y) S' h(z)$.
Doesn't this means that the exponential does give me a lax functor,
which seems like a bad property to throw away?
So my second question is are there examples where the inclusion in
this direction is not provable, either?


texts: Results regarding Bounded Diameter Minimum Spanning Tree

texts:
Given edge weighted undirected graph the problem asks to output a spanning tree $T$ of minimum weight such that the path between any two vertices in the tree $T$ is bounded by the input $k$. One of the related paper is at http://www.sciencedirect.com/science/article/pii/S0166218X99001110 .

However i could not find other relevant results which improvised over it in general case. Can anyone please refer me the state of the art in this problem. I am also looking for results on unweighted undirected graphs which i couldn't get. I tried to google out and follow the citations but couldn't get what i wanted.


texts: Exponential-time factorization of polynomials

texts:
Let an explicit field be a field for which equality is decidable (in some standard model of computation). I am interested in the factorization of univariate polynomials over an explicit field.

It is known that over some explicit fields, testing irreducibility of polynomials is undecidable [1]. Though, over many fields, the irreducible factorization of polynomials is known to be computable in polynomial time, either deterministically (over $\mathbb Q$ [2] or any number field) or probabilistically (over finite fields [3]). Here the size of the input is the size of the dense representation of the polynomial, that is the list of all its coefficients.

  Is there an explicit field for which

  either the best known algorithm has an exponential running time,
  or (better) there exists an exponential lower bound for irreducibility testing?

Quick clarification: There may be very different explicit fields, depending on the complexity (for instance) on the equality test or of the standard operations (addition, multiplication). Actually, I am not aware of any result about polynomial factorization which is not a polynomial time upper bound, or undecidability. So I am interested in any kind of different result (exponential time is just an example). Conditional lower bounds are of interest too.

References.

[1] A. Fröhlich et J. C. Shepherdson (1955): On the factorisation of polynomials in a finite number of steps.
[2] A. K. Lenstra, H. W. Lenstra Jr., L. Lovász (1982): Factoring polynomials with rational coefficients.
[3] E.R. Berlekamp (1967): Factoring Polynomials Over Finite Fields.


texts:
Is $⊕2SAT$ - the parity of the number of solutions of $2$-$CNF$ formulae $\oplus P$ complete?

This is listed as an open problem in Valiant's 2005 paper https://link.springer.com/content/pdf/10.1007%2F11533719.pdf. Has this been resolved?

Is there any consequence if $⊕2SAT\in P$?


texts: What is the communication complexity of approximating addition?

texts:
In my circuit complexity research, I came across the need to find the communication complexity of approximating addition. Specifically, the class of problems I am interested in is parametrized by four numbers $a,b,k,m$, and given these I want to find the $k$-party number-in-hand deterministic communication complexity of the following problem:

  Each player is given an $m$-bit number $x_i$ with the guarantee that $\Sigma_ix_i$ is either less than $a$ or greater than $b$ and they must decide which of these two conditions hold (i.e. whether $\Sigma_ix_i$ is less than $a$ or greater than $b$).

The settings of parameters that are most interesting to me are where $b=Ca=Ckl$ ($C$ is just some constant), $m=\Theta(\log a)$, and I want to choose $k$ as large as possible for given values of $l$ so that the complexity remains linear in $l$. That is, I want $k$ to be a function in $l$ that grows as quickly as possible (ideally it would be linear growth) which still results in linear complexity.

So far, I think I can make $k$ at least $\Omega(\frac{l}{\log\log l})$, but I am still a pesky $\log\log l$ factor away from optimal. In fact, my protocol is even symmetric and simultaneous and works by having each player specify the number of bits in their number. Thus, each player outputs a number in the range $[0,m]$, and so each player outputs about $\log m=O(\log\log l)$ bits of communication. In total, this protocol uses $k\log\log l$ bits of communication, allowing us to choose $k\sim \frac{l}{\log\log l}$. Using these players' messages we can then approximate each of their numbers by a factor of two, and thus approximate the sum by a factor of two.

Can we do any better? Are there any lower bounds to the complexity of approximating addition? I found this paper, but it only studies the communication complexity of exactly computing addition, and I haven't been able to reduce that to an approximate calculation. I have a hunch there's some way to make this work, though, since they also get a similar tight $k\log\log k$ lower bound for the exact computation of addition by one-way protocols. Any help, references, tips, or opinions would be greatly appreciated!


texts: Check the match of the maximum of each subset

texts:
Given a number of vectors with $n$ elements, i.e., $S=(a_1, \cdots, a_n)$, $T_j=(b_1^j, \cdots, b_n^j)$ for $j=1,\cdots, m$ where each $a_i$ or $b^i_j$ is a natural number.

Question: determine whether, for all subset $I\subseteq \{1, \cdots, n\}$, there is some $T_j$ ($1\leq j\leq m$) such that $\max\{a_i\mid i\in I\}=\max\{b_i^j\mid i\in I\}$.

Obviously there is an exponential time algorithm to do this (one can just enumerate all $I$), but can we do better to have a polynomial-time algorithm? or is it NP-hard?

Example: $S=(1,2,0)$, $T_1=(2,1,0)$, $T_2=(2,0,1)$, $T_3=(1,0,2)$, $T_4=(0,2,1)$ gives an affirmtive answer.

Motivation: this question is from database research, the background of which is a bit hard to describe precisely here.


texts:
Given a rectangular region $R$ and a set $D$ of $n$ disks such that the union of all disks in $D$ cover the entire rectangular region $R$, the objective is to find the minimum cardinality set $D'$ subset of $D$ such that the union of all disks in $D'$ cover the entire $R$.
I believe that this problem is NP-hard, but did not find any reference. can somebody help me to find the one or reduction from an NP-hard problem.


texts: What about apply maxplus algebra for all-pairs shortest paths?

texts:
I didn't find deep informations on Wikipedia about all-pairs shortest path, in particular I do not know what is the best algorithm to solve this problem beyond Floyd-Warshall's one, then I do not know if the following observation is too irrelevant or trivial.

In maxplus algebra we revisited linear algebra substituting the usual operations with the max-operation and plus-operation instead of addition and multiplication respectively. In particular we obtain an equivalent theory by taking minimum instead of maximum, then having a minplus algebra (with the obvious changing in the associated semiring, i.e. taking $+\infty$ instead of $-\infty$ as neutral element for the first operation).

Trying to see what the usual graph-theoretic-interpretation of matrix multiplication become in the minplus algebra (with $+\infty$ in the entries corresponding to non-existing edge and $0$s on the diagonal), I see that the $k$-th power of the adjacency matrix gives the shortest paths of length at most $k$. Then, all-pairs shortest path could be solved in $n^\omega \log n$ (where $\omega$ is the present lowest exponent for matrix multiplication) instead of $n^3$ like FW-alg.

Did I made big mistakes about all that?

I consider that maybe the lower bounds on matrix multiplication are not valid changing operations... but then seems plausible that it could be possible to have an exponent less than $3$ also for minplus algebraic matrix multiplication; among other things, the multiplication is far more computationally expensive than addition, and so is taking minimum respect to addition.