texts: Uniquely 4-colorable Planar Graph Conjecture?

texts:
My question is on Uniquely 4-colorable Planar Graph Conjecture mentioned in
On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and Coloring of Maximal Planar Graphs", etc.).
I find this paper a bit misleading.

Uniquely 4-colorable Planar Graph "Conjecture"
(in their paper, this is called "uniquely 4-colorable graph conjecture: vertex version")

To my knowledge, Fowler's characterization closed the case: he proved that a planar graph is uniquely 4-colourable iff it is a maximal planar chordal graph (also called planar 3-trees or Apollonian network). In the paper above, they give this as a conjecture(they call maximal planar chordal graphs as recursive maximal planar graphs) and cite Fisk. But, I do not see this conjecture in Fisk.

They state that according to Fisk another known conjecture (If G is a uniquely 3-edge-colorable cubic graph,
then G is a planar graph that contains a triangle) is equivalent to Uniquely 4-colorable Maximal Planar Graph Conjecture.

I don't think they are equivalent (or at least the equivalence is not obvious). The conjecture that uniquely 3-edge colourable graphs contain a triangle is still open. The other as we saw is closed.
Is there something I am missing?


texts:
The gossiping problem in distributed systems is the following. We have a graph $G$ with $n$ vertices. Each vertex $v$ has a message $m_v$ that must be send to all nodes.

Now, my question is in the context of the ad-hoc network model (we assume that a node does not have any prior knowledge about the topology of the network, its in and out degrees, and the set of its neighbours. In fact the only knowledge of each node is its own identifier and the total number of nodes).

I also assume that all nodes have access to a global clock and work synchronously in discrete time steps called rounds.

The complexity of an algorithm in this context is the number of rounds needed for completion.

I remember that there exists an algorithm that solves the gossiping problem in $O(n \log ^2 n)$ rounds with high probability. But I cannot find the reference anymore, and I am wondering if there are more recent results on that matter.

edit following the judicious comment: at each round a node can transmit the message to all its neighbours and can receive the messages from them. A node will receive a message at a given round if and only if exactly one of its neighbours transmits at that round. Otherwise a collision occurs and none of the messages is received by the node.


texts: log(OPT) approximation for directed balanced vertex separator

texts:
Leighton, Rao presented an $O(\log n)$ approximation algorithm for directed and undirected balanced vertex separator. Agarwal, Charikar, Makarychev, Makarychev improved this approximation factor of directed balanced vertex separator to $O(\sqrt{\log n})$.

Is there an $O(\log \mathsf{opt})$ approximation algorithm for directed balanced vertex separator, where $\mathsf{opt}$ is the optimal size of the directed balanced vertex separator ?

I would appreciate any references/pointers.


texts: Is there a standard name for this way of modifying graphs?

texts:
Let $G = (V, E)$ be an undirected graph. Let me take an edge $\{x, y\}$ (in blue in the drawing) such that $x$ and $y$ have other incident edges. Among the incident edges we choose one edge $e_x = \{u_1, x\}$ for $x$ and one edge $e_y = \{y, v_m\}$ for $y$ (in red in the drawing).

Now, I modify $G$ by adding a copy $x'$ occurring in the same edges as $x$ except $e$ and $e_x$, adding a copy $y'$ occurring in the same edges as $y$ except $e$ and $e_y$, and replacing the edge $e$ by two copies $\{x, y'\}$ and $\{x', y\}$.

Does this operation have an established name, and is anything known about it?

One question for instance is to understand for which graphs there is a sequence of such operations that will terminate (the operation is no longer applicable to any edge, i.e., each edge has one vertex which is a leaf, or equivalently the graph is a union of stars), for which graph all sequences terminate, and is there confluence (do all terminating sequences on an input graph give the same result up to isomorphism). There are fairly simple graphs where applying sequences of this operation will never terminate, e.g., $\{a, b\}, \{b, c\}, \{c, d_1\}, \{c, d_2\}$.


texts: There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, computational complexity $F(n) $ is correlated to the average consumption of energy, hope I can get some answer here.


texts: What is the space complexity of calculating Eigenvalues?

texts:
I am looking for a survey paper or a book covering results
about the space complexity of common linear algebra operations
such as matrix rank, eigenvalues calculation, etc.
I stress the "space complexity" part meaning work space complexity,
rather than time complexity since it is easier to trace time results.
I appreciate any reference in the matter.

Thanks.


texts: Is there a polynomial time algorithm for creating a set of vectors in general position?

texts:
It seems to be possible to create a set of vectors in $\mathbb{R}^n$ such that any subset of $n$ vectors forms a basis.

For example, in $\mathbb{R}^3$, here is such a set with 21 vectors:

$$
\left\{
  [1,2,3], [2,3,1], [3,1,2], \\
  [1,4,5], [4,5,1], [5,1,4], \\
  [1,6,8], [6,8,1], [8,1,6], \\
  [1,8,12], [8,12,1], [12,1,8], \\
  [1,10,17], [10,17,1], [17,1,10], \\
  [1,12,23], [12,23,1], [23,1,12], \\
  [1,14,30], [14,30,1], [30,1,14]
\right\}
$$

Any combination of 3 of these vectors is linearly independent.

Is it possible to create a set satisfying this property with arbitrarily many vectors? I think so, but the specific pattern used in the set above breaks down around 50 vectors; I think some more complicated pattern should work.

Is it possible to create this set in time polynomial in the number of vectors in the set?


texts: Eigenvalues of Random Regular Bipartite Graphs

texts:
I am looking for a way of getting a good estimate of the eigenvalues of random bipartite d-regular graphs. The literature has very precise values the proofs of which are very involved and since I am looking to extend the estimates to a more general scenario I dont want to get into very involved techniques. The kind of bounds I am looking for can have constant (or even log factors) thrown around.

One way I have in my mind is to use the matrix Bernstein inequality by expressing a random bipartite d-regular graph as a sum of d independent random matchings and then black box the Matrix Bernstein Inequality result. This gives satisfactory answers for me with the caveat that summing up d random matchings does not necessarily produce simple graphs (edges can get repeated), however I feel that the estimate that we get from Matrix Bernstein should hold for the random regular graph case too. Is there an easy way to get around this difficulty?

Thanks in advance


texts: In a cryptosystem, why does the message space need to be finite?

texts:
I am learning cryptography through Douglas Stinson's book: Cryptography -- Theory and Practice (3rd ed.).  The first definition in the text is

A cryptosystem is a five tuple (M,C,K,E,D) where
 - M is a finite set ...

That is the set of "plaintexts" or unencrypted messages must be finite.  My question is: how reasonable of a definition is this?  For any natural language, there are an infinite number of messages that one can send.  It seems this is incomplete to me.  It seems that M is the alphabet we are encrypting, and to encrypt a string in M* (what I would call the message space) we encrypt by
   $$e_k(m_1 \cdots m_j) = e_k(m_1) \cdots e_k(m_j)$$
(where $e_k \in E$ is an encryption function -- note that elements of $E$ can be viewed as functions $e : K \to M \to C$).
But I feel this is a bad idea because we are reusing a key.


texts:
Is it possible to translate a boolean formula B into an equivalent conjunction of Horn clauses? The Wikipedia article about HornSAT seems to imply that it is, but I have not been able to chase down any reference.

Note that I do not mean "in polynomial time", but rather "at all".


texts: Minimize The Number of Connected Components in Hit-map of A Boolean Matrix

texts:
Suppose there is a matrix with the value of 0 and 1. The hit-map of the matrix (0 is blue and 1 is red) create some connected component (see the following figure as an instance):

Is there any efficient algorithm to minimize the number of connected components (constructed from red cells) by swapping rows and columns of the matrix with this constraint that "As row and column of this matrix comes from the same property set, if we swapping row $i$ with row $j$, we must swapping the column $i$ with column $j$ too.".


texts: Is it still open to determine the complexity of computing the treewidth of planar graphs?

texts:
For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-hard. (Source).

However, when the input graph is planar, much less seems to be known about the complexity. The problem was apparently open in 2010, a claim that also appeared in this survey in 2007 and on the Wikipedia page for branch decompositions. Conversely, the problem is claimed NP-hard (without proof of reference) in an earlier version of the previously mentioned survey, but I assume this is an error.

Is it still open to determine the complexity of the problem, given $k \in \mathbb{N}$ and a planar graph $G$, of determining $G$ has treewidth $\leq k$? If it is, was this claimed in a recent paper? Are any partial results known? If it isn't, who solved it?


texts:
I am an engineer and looking for a reference to find k-shortest path's in a large sparse graph. In the search for it, I came acorss Yen's ranking loopless algorithm and an improved implementation of it.
And did read about other implementations with the help of http://liinwww.ira.uka.de/bibliography/Theory/k-path.html

But in every paper there is a reference to multiple others citing improved performance in a different scenario. Ultimately too many options and tough to choose one.
Hence can some one please provide the reference to most optimized sequential version of finding k-shortest path.

Thanks.

EDIT: Another problem with improved implementation of yen's algorithm is that one cant work with it in parallel. i.e. if I am finding kth shortest path from node 1 to node 100, then in mean time I cannot use it to find from a node to some other node. This is because it removes some nodes and arcs from graph in midst of computation.

The problem with eppstein again is that it uses its own data structure. There are many issues with it. Firstly I will have to construct it to use and the graph in my case is a large graph. The data structure is different for the start and terminal nodes respectively and same data structure cannot be used for other pair. Ultimately resulting in high memory utilization when using multiple instances of the algorithm.

EDIT2: Sorry, this is my fault for lack of clarity, What I basically meant was that One should be able to run multiple instances of the algorithm in parallel. With improvised version of Yen algorithm one cannot do that. Basically a sequential algorithm that can have multiple instances (instances and not parallelism in the algorithm) of it running in parallel.

Secondly, in EDIT1, both of the comments are not a comparison but rather a small discussion. Due to inability to find satisfactory loopless shortest paths, I came across Prof.Eppstein paper compromising on loops for performance. What I am basically looking for is a loopless k-shortest path sequential algorithm with less memory utilization (in my case I am dealing with large road networks) which can scale for very large graphs (over 50k nodes).

Thanks a lot.


texts: Functions that typed lambda calculus cannot compute

texts:
I just want to know some examples of the functions that can be computed by the untyped lambda calculus but not by typed lambda calculi.

As I am a beginner, some reiteration of background information would be appreciated.

Thanks.

Edit: by typed lambda calculi, I was intending to know about System F and the simply-typed lambda calculus. By function, I mean any Turing-computable function.


texts: What's the correlation between treewidth and instance hardness for random 3-SAT?

texts:
This recent paper from FOCS2013, Strong Backdoors to Bounded Treewidth SAT by Gaspers and Szeider talks about the link between the treewidth of the SAT clause graph and instance hardness.

  For random 3-SAT, i.e. 3-SAT instances chosen at random, what is the correlation between treewidth of the clause graph and instance hardness?

"Instance hardness" can be taken as "hard for a typical SAT solver", i.e. running time.

I am looking for either theoretical or empirical style answers or references. To my knowledge, there do not seem to be empirical studies on this. I am aware there are somewhat different ways to build SAT clause graphs, but this question is not focused on the distinction.

Maybe a natural closely related question is how treewidth of the clause graph relates to the 3-SAT phase transition.


texts: Variability of gradient estimates and convergence rate in stochastic gradient descent/ascent

texts:
I am aware that convergence in stochastic gradient problems is very sensitive to the variance of your gradient estimator. One issue I'm running into is that the gradient is a random vector and so would require a different metric to comparing the variance of univariate estimators.

I've seen a paper (https://arxiv.org/pdf/1705.07880.pdf) where variance reduction techniques are applied to minimise the trace of the estimator covariance matrix, however there are usually dependencies between gradient components which is not accounted for when taking the trace.

I have heard that it is standard in the optimisation community to compare the relative efficiency of two gradient estimators by using the expected value of the squared norm of the gradient (apparently convergence is dependent on this). Is this correct? If so, can anyone share a reference?

Thanks!


texts: Treewidth of two complete binary trees joined at their leaves

texts:
Let $T$ be a complete binary trees on $n$ nodes. Let $G'$ be the graph that consists of two disjoint copies of $T$. For a leaf $x \in T$, let $x_1, x_2$ be the two copies of it in $G'$. Then, let $G$ be the graph obtained from $G'$ where for every leaf $x$, an edge between $x_1, x_2$ is introduced.

I am interested in the treewidth of $G$. I conjecture that it is $O(\log(n))$ (start at the root of one copy of a tree, then first visit the left subtree and recurse until the root node of the other tree is reached, we always need to keep track of a path of length at most $\log(n)$). First, is this correct? Second, how can I prove a LB on the treewidth of this graph?

Thanks in advance.


texts: Interesting PCP characterization of classes smaller than P?

texts:
The PCP theorem, $\mathsf{NP} = \mathsf{PCP}(\mathsf{log}\, n, 1)$, involves probabilistically checkable proofs with polynomial time verifiers, so the smallest class that can be characterized in this way (that is, $\mathsf{PCP}(0, 0)$) must be $\mathsf{P}$. There are also PCP characterizations of larger complexity classes (for example, $\mathsf{NEXP} = \mathsf{PCP}(\mathsf{poly}, \mathsf{poly})$), also using polynomial time verifiers.

Can we achieve an interesting (that is, not immediately following from the definitions) PCP characterization of smaller complexity classes by restricting the time or space used by the verifier? For example, by using a logarithmic space verifier, or an $\mathsf{NC}$ circuit verifier?


texts: What are some methods for representing a weighted directed graph with a non-weighted directed graph while preserving some properties?

texts:
More specifically, I'm looking at the problem of applying an algorithm for computing the permanent of a sparse matrix of binary entries (0s and 1s) to a matrix that has entries of positive and negative integers (but still sparsely).

I am not sure how hard this is. Clearly the permanent of a general matrix can be negative so it cannot be written as the permanent of a matrix with non-negative entries.

However, there may be some kind of way to re-represent the permanent of the general matrix in terms of other permanents.

That is, Per(A) = Per(A1) +/- Per(A2) +/- Per(A3) +/-... for some matrices A1,A2,A3, or something like that.

This is related to the problem of rerepresenting weighted graphs as non-weighted graphs through the connection of the permanent and cycle covers on the adjacency graph.


texts: Occam razor for exact learning with membership/equivalence queries

texts:
In PAC learning, there is the "Occam razor" principle, which says that learning is qualitatively equivalent finding a succinct hypothesis that is consistent with the training samples.

My question is whether there is a similar principle in Angluin's model in exact learning with membership and equivalence queries. In this model, the learner can either ask for the label of a sample of her choice, or ask for a counterexample for a hypothesis of her choice (if no counter-example exists, the verifier is told that the hypothesis is correct).

I am not sure how an "Occam razor" for Angluin's model could even be defined, but ideally it would say that learning is equivalent to the ability to find a succinct hypothesis that is consistent with training samples, in some sense.


texts: Results in computer science via the Stepanov method

texts:
I recently attended a Workshop on Pseudorandomness in Chennai Mathematical Institute on Pseudorandomness. Venkat Guruswami made the following beautiful statement in passing during his talk (on coding theory):

  It is remarkable how much one can prove using the simple fact that a
  degree $d$ polynomial over a field can have at most $d$ roots.

I believe this is also called the Stepanov Method (in those applications, typically roots occur with large multiplicity as well). One place where I've seen this is in a paper on square root bounds for the smallest non-residue by Michael Forbes, Neeraj Kayal, Rajat Mittal and Chandan Saha .

This principal was highlighted in the workshop with the unique and list decoding of Reed-Solomon code (which can be found in this course, for example) in Venkat's talk. In Neeraj Kayal's talk, he gave two other examples -- the proofs of the Finite Field Kakeya Conjecture and the Joints Conjecture (both of which can be found in this  very nice survey by Zeev Dvir). Other examples that I can think of is Dana Moshkovitz's proof of the Schwartz-Zippel Lemma, and another favourite of mine is the AKS Primality test which (if I'm allowed to make a stretch) uses only this fact essentially.

I was wondering if there are other examples of elegant results using (essentially) just this simple fact.

This post is closely related to the earlier question "Polynomial methods for complexity results" but that was for a more general 'polynomial method'.


texts: Anagrams, Prime numbers and prime coding

texts:
I am from math.stackexchange, here is my original post.

https://math.stackexchange.com/questions/2354828/anagrams-prime-numbers-and-prime-number-coding

The only comment I received was too technical for me, so I've decided to repost here in hope of a more mathematician friendly answer. Thanks in advance!

A while back I realised that I could find all anagrams in a language by assigning each letter to a prime number (I call this prime coding, though it probably has a proper name) then multiply the letters in a word to create some value. Then words that are anagrams will have the same value.

for example, if we let:
$$a=2, \;\; b=3, \;\; c=5, \;\; d=7, \;\; \cdots , \;\; t=71, \;\; \cdots$$
then $cat = 2\times 5 \times 71$ and $tac = 71 \times 2 \times 5$

Due to the fundamental theorem of arithmetic two words will have the same value if and only if they are anagrams.

When I thought about this practically, the numbers started getting pretty big. A 10 letter word is likely to be over 1 trillion. In an attempt to reduce these values I turned to Gaussian Integers. So that I could use smaller numbers as my primes.

Are there any more types of prime numbers I could use to further reduce values?

I suspect Quarternions and Octonians(?) and further powers of 2 down that route could potentially reduce the value at a cost of the number of numbers needed. So presumably there would be an optimal pay off here. But I'm more interested in a different approach.

Thank you in advance


texts:
I am a computer scientist taking a course on Topology (a sprinkling of point-set topology heavily flavored with continuum theory). I have become interested in decision problems testing a description of a space (by simplices) for topological properties; those preserved up to homeomorphism.

It is known, for example, that determining the genus of a knot is in PSPACE and is NP-Hard. (Agol 2006; Hass, Lagarias, Pippenger 1999)

Other results have more a more general feel: A. A. Markov (the son of the Markov) showed in 1958 that testing two spaces for a homeomorphism in dimensions $5$ or higher is undecidable (by showing the undecidability for 4-manifolds). Unfortunately, this last example is not a perfect exemplar of my question, as it deals with the homeomorphy problem itself rather than properties preserved under homeomorphism.

There seems to be a large amount of work in "low dimensional topology": knot and graph theory. I am definitely interested in results from low dimensional topology, but am more interested in generalized results (these seem to be rare).

I am most interested in problems which are NP-Hard on average, but feel encouraged to list problems not known to be so.

  What results are known about the computational complexity of topological properties?


texts: If $PIT$ has been derandomized then still how far would we be from showing $P=BPP$? What additional barriers need to be climbed?


texts: The minimum entropy of a proper coloring of a graph

texts:
The chromatic number $\chi(G)$ of an undirected graph $G$ is the minimum number of colors in a proper coloring of the vertices of $G$ (where a proper coloring uses different colors for two vertices connected by an edge). I am interested in a related quantity. In my problem, I am given a probability distribution $P$ on the vertices of $G$ and I am interested in minimizing the (Shannon) entropy of the induced probability distribution on the colors over all proper colorings of the vertices of $G.$ Let this quantity be denoted by $\rho(G,P).$ We have trivially,

$$\rho(G,P)\leq \log_2\chi(G).$$

Note that the entropy minimizing coloring need not use the minimum possible number of colors. Eg. Consider a 6-cycle with probabilities 0.48,0.01,0.01,0.48,0.01,0.01 in that order. The three-coloring that pairs the two heavy diametrically opposite points will have a lower entropy than any two-coloring.

More generally, I want to understand what happens when one considers tensor powers of the graph. Consider the AND product of graphs where an edge exists between $(v_1,v_2)$ and $(w_1,w_2)$ if and only if there exist edges $(v_1,w_1)$ and $(v_2,w_2)$ or if $v_1=w_1$ and $(v_2,w_2)$ is an edge or if $v_2=w_2$ and $(v_1,w_1)$ is an edge. It is easy to show that the sequence $\chi(G^{\otimes n})$ is sub-multiplicative and so the limit $\lim_{n\to\infty}\chi(G^{\otimes n})^{\frac{1}{n}}$ exists (sometimes called Witsenhausen's rate of $G$). An analogous quantity for $\rho$ may be defined as below and existence of the limit follows from subadditivity again:

$$\lim_{n\to\infty} \frac{\rho(G^{\otimes n},P^{\otimes n})}{n}.$$

Note here we also take the tensor product of the specified probability distribution $P$. Do we know anything about these quantities? Any related references would be useful. Thanks!


texts: Probabilistic sorting given pairwise comparison probability

texts:
Let $X = \{x_1, \dots, x_n\}$ be a set, and $f:[1..n]^2 \to [0, 1]$ be a function, such that

$$f(i, j) \cdot f(j, k) \le f(i, k)$$

For all $1 \le i, j, k \le n$.

Does there exist a randomized algorithm $A(X, f)$ that outputs permutations of $X$, such that if $\le_A$ is the total order defined by one such output permutation, we have $P(x_i \le_A x_j) = f(i, j)$? ($\le_A$ here is a random variable.)

That is, the permutations that $A$ outputs have a probability proportional to the pairwise probabilities defined by $f$. I believe this implies the probability of a permutation is, in fact, the product of these pairwise probabilities.

We have a special case, where $X$ is already a totally ordered set, and $f(i, j) = \delta_{x_i \le x_j}$, then $A$ is any sorting algorithm. Can this be done for any such $f$ as described? If not, what other requirements does one need? Finally, is there an efficient such $A$?


texts:
I'm trying to build a Turing machine diagram for the language w#w^R, where w^R is the reverse of w, and w is a word made up of 0's and 1's. I'm trying to think of an algorithm but I can't think of something not extremely complicated that goes over all combinations of the alphabet for a given word length, then type # onto the print tape and copies it back in reverse.

Is there something I'm missing here? Could there be a simpler algorithm here?

Thanks in advance.


texts: Is it possible to derive induction by extending CoC with recursion?

texts:
Suppose we extended the CoC with primitive recursion; that is, we added a term µ x . t such that equality allowed unrolling recursive terms:

Γ |- µ x . a : *    Γ |- b : *    Γ |- a [a/x] == b
---------------------------------------------------
Γ |- a == b

And such that applying a recursive term to an argument unrolled it:

((µ x . a : T) q) ~> (a[a/x] q)

It seems that even that way, deriving induction wouldn't be possible. I've attempted the following (using Morteish syntax):

NAT =
  ∀ (P : *) ->
  ∀ (Zero : P) ->
  ∀ (Succ : NAT -> P) ->
  P

Zero =
  λ (P : *) ->
  λ (Zero : P) ->
  λ (Succ : NAT -> P) ->
  Zero

Succ =
  λ (n : NAT) ->
  λ (P : *) ->
  λ (Zero : P) ->
  λ (Succ : NAT -> P) ->
  Succ n

induction =
  λ (P : NAT -> *) ->
  λ (Z : P Zero) ->
  λ (S : ∀ (n : NAT) -> P n -> P (Succ n)) ->
  λ (n : NAT) ->
  n (P n) Z (λ (pred : NAT) -> S n (induction P Z S pred))

The problem here is that, when pattern-matching n on the definition of induction, we need to specify a return type. By specifying it to be P n, we get an error because, on the first case,

Z : P Zero

But should be:

Z : P n

And, on the second case,

(λ (p : NAT) -> S p (induction P Z S p)) : ∀ (p : NAT) -> P (Succ p)

But should be:

(λ (p : NAT) -> S p (induction P Z S p)) : ∀ (x : NAT) -> P n

The source of the problem seems to be that the system doesn't recognize that the following holds:

case n of
  Zero   -> ... here, n == Zero   ...
  Succ p -> ... here, n == Succ p ...

Or, in other words, after pattern matching a variable n : NAT as Zero, the system doesn't understand that n equals Zero. Similarly, it doesn't understand that Succ (pred n) == n. Is there any inherent reason for that, and is there any further extension that would allow this to check?


texts: What is the minimum required depth of reductions for NP-hardness of SAT?

texts:
As everyone knows,
SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions.
It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions.

My questions is what is the minimum required depth for the reductions?
More formally,

  What is the least $d$ such that
  SAT is $\mathsf{NP}$-hard w.r.t $\mathsf{AC^0_d}$ many-one reductions?

It seems to me that $\mathsf{AC^0_2}$ should be sufficient? Does anyone know a reference?


texts: Decision version of matrix multiplication problem

texts:
Is there any known decision version of matrix multiplication problem such that the time complexity of the best known algorithm for this decision problem is $O(n^k)$ for $n \times n$-dimensional matrices, where $k$ is bigger than 2 and preferable very close to $ \omega $ or the best known candidate of $\omega$ ($\omega$ is the optimal matrix-product constant)?

P.S. I am aware of matrix product verification problem (e.g. this post).


texts: Lower bound on the number of "short" paths in a rooted tree with polynomial size

texts:
Let $T$ be a rooted binary tree. Every path from the root of $T$ to a leaf has length $n$. Every node of $T$ has always a left and a right child node but it is possible that they are the same (So there are always $2^n$ paths possible). The size of $T$ is bounded by $O(poly(n))$. A node with different child nodes is called branching node.

We say that two paths are different iff there is one shared branching node and one path goes to the left child node and the other path goes to the right child node.
It is clear that there is at least one path in $T$ with $O(\log n)$ branching nodes. Otherwise there would be too much nodes in $T$.

Is there a better lower bound on the number of paths with $O(\log n)$ branching nodes if I know there are $\omega(\log n)$ branching nodes in the tree?


texts: Find the number of vertices that belong to all the maximum matchings of a general connected graph

texts:
The given graph is connected but not necessarily bipartite. Please describe the complete approach with useful links , I read stuff related to augmenting paths but could not comprehend well.
An O(VE) approach will be good for me .
Though i would prefer O(V^2) approach (if it is known)


texts:
I'm looking for the original paper where Hoare (or someone else I suppose) discusses termination (Total Correctness). Or any other early work on termination for "vanilla" Hoare logic (I suppose by that I mean a HL for a C-like toy language).

I've had a look at Axiomatic basis for Computer Programs (PDF) (which seems to be essentially Hoare logic of the partial correctness flavour) and
A note on the for rule, which mentions proof of a while rule, but can't seem to find the missing link; a paper on termination/the while rule/Total correctness.


texts:
Is there a polynomial-time algorithm to find—if one exists—a spanning spider
of a given graph $G$?  A spider is a tree with at most one node with degree greater than 2:

I know that various degree conditions on $G$ (essentially, sufficiently large node degrees) guarantee the existence of a spanning spider.  But I am wondering if there is an algorithm for arbitrary $G$.  Thanks!


texts: How hard is it to count the number of local optima for a problem in PLS?

texts:
For a polynomial local search problem, we know that at least one solution (local optimum) must exist. However, many more solutions could exist, how hard is it to count the number of solutions for a PLS-complete problem? I am particularly interested in the decision problem: does this PLS-complete problem's instance have two or more solutions?
Does the complexity depend on which PLS-complete problem we choose? If so then I would be particularly interested in weighted 2SAT (as defined in [SY91] and [Rou10]). I know that counting the number of satisfying solutions for 2SAT is #P-complete, but at first glance it seems like local optima of weighted 2SAT and solutions for 2SAT don't have all that much in common.
I also know that for PLS's cousin PPAD, [CS02] shows that counting the number of Nash equilibria is #P-hard. This suggests that similar PLS problems like counting the number of pure-strategy equilibria in congestion games, would also be hard.
References
[CS02] Conitzer, V., and Sandholm, T. (2002). Complexity results about Nash equilibria. IJCAI-03. cs/0205074.
[Rou10] T. Roughgarden. (2010). Computing equilibria: A computational complexity perspective. Economic Theory, 42:193-236.
[SY91] A.A. Schaeffer and M. Yannakakis. (1991). Simple local search problems that are hard to
solve. SIAM Journal on Computing, 20(1):56-87.


texts: Complexity of distributively verifying that the diameter is small

texts:
Consider a graph $G=(V,E)$ and an integer parameter $k$.

I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than $k$.

Formally, assume that we need (all vertices) to report "small" if the diameter is at most $k$ and "large" if it is larger than $f(k)$ for some function $f$ (e.g., $f(k)=100k^2$).

A closely related problem asks to approximate the diameter. In this paper, it was shown that deciding whether the diameter is at most $2\ell+1$ or larger than  $3\ell+1$ requires $\widetilde \Omega(n)$ rounds for any $1\le \ell\le \text{polylog}(n)$. However, this just shows that a (small) constant factor approximation is hard.

On the algorithmic front, it is possible to compute a $3/2$-approximation in $O(\sqrt{n\log n}+D)$ rounds.

  Does the round complexity depends on $n$ for any function $f(k)$? Are there functions $f$ for which this dependency is reduced, say, to logarithmic?

  If we allow super-linear functions $f$, is it possible to reduce the dependency on the diameter (e.g., to $f^{-1}(D)$)? (e.g., can we get a round complexity of $O(k^2 \sqrt{n})$ for $f(k)=k^2$?)


texts:
sorry for bad formatting earlier

We are given Cx,i, Cy,i, Cz,i ∈ ℕ and Px,i, Py,i, Pz,i > 0 for i=1,2,3 such that Px,1 < Px,2 < Px,3, Py,1 < Py,2 < Py,3, and Pz,1 < Pz,2 < Pz,3. We are also given K∈ℕ.

The values Cx,i and Px,i describe the content of a stack named x. From top to bottom, the stack x contains Cx,1 items each of profit Px,1, Cx,2 items each of profit Px,2, and Cx,3 items each of profit Px,3. The contents of stacks y and z are defined in the same way.

We are allowed to pop K items in total from the three stacks. How can I maximize the total profit?


texts: upper bound on the size of a DFA for A|B given the DFAs for A and B?

texts:
Given RegEx A and B where the size of the compiled DFAs are m and n respectively, what is the upper bound on the size of the compile DFA for A|B? It shouldn't be hard to show that it can't be more than n*m but can a lower upper bound be shown?

What about other related case:

What is the expected case for real world examples? Is it less than n+m?
What about the three part case with A, B and C?


texts:
Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum_{i=1}^4 p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ with $p_1$, goes to $(0,1)$ with $p_2$ etc.

I am interested in the probability $x$ of going back to (0,0), starting from (0,0). In general, this probability is not 1 (I guess that $x$ is not rational in general). The question is, given a probability threshold $r$, is it decidable that $x\geq r$?


texts: Other kinds of running time analysis besides worst-case, average-case, etc?

texts:
Here are some ways to analyze the running time of an algorithm:

1) Worst-case analysis: Running time on the worst instance.

2) Average-case analysis: Expected running time on a random instance.

3) Amortized analysis: Average running time on the worst sequence of instances.

4) Smoothed analysis: Expected running time on the worst randomly perturbed instance.

5) Generic-case analysis: Running time on the worst of all but a small subset of instances.

My question: Is this a complete list?


texts: Research papers regarding disinterval analysis

texts:
I'm trying to implement a disinterval analysis similiar to what is described in Clousot: Static Contract Checking with Abstract Interpretation (under section 5.2) - and I'm trying to find some papers describing the abstract operators (+, -, join, meet - etc) - however I have been unable to dig these up.

Are any of you aware of such papers and could you please link me to them?


texts: $NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$

texts:
Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$  be constants. Are there disjoint subsets $V_1, V_2$ with $V = V_1 \cup V_2$ and $|V_i| \leq (1+\epsilon)|V|/2$ such that at most $M$ edges have an endpoint in both sets?

In Computers and Intractability (1979), Garey and Johnson claim this problem is $NP$-Complete (label: ND17) (they use an upperbound $B \geq 0$ requiring $|V_i| \leq B$, but for us that just means setting $\epsilon= 2B/|V|-1$).

Is anything known about the $NP$-Completeness of this problem for fixed values of $\epsilon$? For $\epsilon = 0$ we get the standard perfectly balanced bisection problem. For $\epsilon  = 1$ the problem is vacuously trivial. What if $\epsilon$ is some fixed constant in $(0, 1)$ (that is, not part of the input, but part of the problem definition).


texts: Natural NP-complete problems with "large" witnesses

texts:
The question on cstheory "What is NP restricted to linear size witnesses?" asks about the class NP restricted to linear size $O(n)$ witnesses, but

  Are there natural NP-complete problems in which (yes) instances
  of size $n$ require witnesses of size greater than $n$?

Clearly we can build artificial problems like:

$L = \{ 1^nw \mid w \text{ encodes a satisfiable formula and } |w|=n \}$
$L = \{ \varphi \mid \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$

After a quick look at G&J, every natural NPC problem seems to have witnesses (strictly) smaller than $n$.

  Is there a "reason/explanation" for it ?


texts: What is an equivalent definition of mP/poly in terms of a Turing machine?

texts:
P/poly is the class of decision problems solvable by a family of polynomial-size Boolean circuits. It can alternatively be defined as a polynomial-time Turing machine that receives an advice string that is size polynomial in n and that is based solely on the size of n.

mP/poly is the class of decision problems solvable by a family of polynomial-size monotone Boolean circuits, but is there a natural alternative definition of mP/poly in terms of a polynomial-time Turing machine?


texts: Question on deduction that a certain problem requires exponential space

texts:
My question concern's a statement from the classic paper The equivalence problem for regular expressions with squaring requires exponential space.

Regular expressions with squaring are like ordinary regular expression but with a squaring operation. Let $RSQ(\Sigma) = \{ E \mbox{ is a regex with squaring} : L(E) \ne \Sigma^{\ast} \}$ be the test if some RegEx with squaring describes every word. In the paper the following is shown:

  Theorem 2.1: There is a finite set $\Sigma$ such that if $M$ is any machine which recognizes $RSQ(\Sigma)$, then there is a constant $c > 1$ such that $M$ requires space (and hence time) $c^n$ on some input of length $n$ for infinitely many $n$.

By coding accepting computations by such regular expressions they continue to show that if $L \subseteq \{0,1\}^*$ is any language with a space bound of $2^n$, then we can reduce the membership problem of $L$ to $RSQ(\Sigma)$ for some $\Sigma$ (the alphabet needs to be enlarged to account for describing sequences of instantaneous descriptions of Turing machines).

Then the argument for the above Theorem relies on the following fact (Fact 2 in the paper) taken from another paper:

  Let $S_1(n)$, $S_2(n)$ be tape constructable functions such that
  $$
 \inf_{n\to \infty} \frac{S_1(n)}{S_2(n)} = 0
\qquad \mbox{ and } S_2(n) \ge \log(n).
$$
  Then there is a language $L \subseteq \{0,1\}^*$ accepted by some space $S_2(n)$ machine but by no space $S_1(n)$ machine.

It is used in the following manner:

  Proof of Theorem 2.1: let $L$ be as in Fact 2 [the statement above] with $S_2(n) = 2^n$. Let $\Sigma$ be such that $L$ reduces to $RSQ(\Sigma)$.

  If $RSQ(\Sigma)$ is accepted by some space $S(n)$ machine, then $L$ is accepted by some space $S(cn) + cn$ machine for some constant $c$ [this is a general property of reductions as stated earlier].
  $$
 \inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0
$$
  implies that $S(n) \ge d^n$ for some constant $d > 1$ and all $n$ which are multiples of $c$.

How do they know that $\inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0$? Somehow the order of quantifiers in the statement of the fact seem not to match that kind of deduction. It does not say that if we have any machine with $S'(n)$ which also accepts $L$ then we must have
$$
 \inf_{n\to \infty} \frac{S'(n)}{S(n)} > 0.
$$
It just says that if this equals zero, then we can choose some language accepted in space bound $S(n)$ but not in space bound $S'(n)$, so it depends on the firstly choosen $S'(n)$. But the argument of the proof does not seem to use it that way. Also the introduction "Let $L$ be as in Fact 2 [...]" seems problematic, for what space bound function $S'(n)$ in the numerator is $L$ choosen?

So how do this argument works? What am I missing here? Can someone please explain?

EDIT: Just let me add that if I accept $\inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0$ then $S(n) \ge d^n$ for some $d > 1$ and all multiplies of $c$ is clear to me. For then we know for some $\varepsilon > 0$ we have
$$
 S(cn) > 2^n\varepsilon - cn
$$
for all $n > N$ for some $N$. Write with $d > 1$ then $2^n = (d + \delta)^n \ge d^n + n d^{n-1}\delta \ge d^n +
 d^{n-1}\delta$ and as $\lim_{n\to \infty} \frac{c\varepsilon^{-1}n}{d^{n-1}} = 0$ we have $c\varepsilon^{-1}n \le d^{n-1}\delta$ for all $n$ sufficiently large, which gives $S(cn) \ge \varepsilon d^n$. Now choose $1 < \hat d < d$ and we find $\lim_{n\to \infty} \frac{\hat d^n}{\varepsilon d^n} = 0$, hence $\varepsilon d^n \ge \hat d^n$ for sufficiently large $n$. So understanding the following conclusions is not the problem.


texts: Algorithm for multiplying multivariate polynomials in a commutative ring

texts:
Let $R$ be a commutative ring. Let $f(x_1, \dots, x_n), g(x_1, \dots, x_n)$ be two multivariate polynomials with the same $x_i$-terms with maximal total degree $\delta$, but with different coefficients in $R$.
How fast can we compute the product of $f$ and $g$, i.e. the resulting coefficients of each term?

For univariate multiplication in a general setting like this, one can use variants of schonhage-strassen to achieve $O(\delta \log \delta \log\log \delta)$ (e.g. Theorem 8.23 in von zur Gathen & Gerhard, Modern Computer Algebra).

I have only been able to find a non-trivial algorithm for when $R$ is a field of characteristic 0, but not for $R$ being a general commutative ring.


texts: How do you compute the fixed point of a best-response function efficiently?

texts:
I have a polynomial time best-response function that has the same properties as a game-theory game (convexity, compactness, set-valued).  I don't know that much topology, but my understanding is that the Kakutani fixed-point theorem confirms that this function has a fixed point, i.e., there exists a strategy profile whose best response is itself.

The "game" I have is not really a game, in the sense that there are no payoffs; there is only a best-response function.

My question is:  Given such a function, can one find a fixed-point quickly?  Ordinarily, there are polytime approximation algorithms for this task (finding a Nash equilibrium), but here I do not have the game in normal form, or an easy way to put it in normal form given the lack of payoffs specified.

Edit:  More specific information:  Given a fixed input, find a polytime machine bounded by n^8+8 s.t. the machine outputs its description on the input.  (There are ways of making this convex by allowing mixing over the edges of the machine.)


texts: Number of rounds of iterative one-round distributed color reduction

texts:
We are talking about one-round coloring algorithms for distributed graphs.

In "On the complexity of distributed graph coloring" (theorem 5.1) Kuhn and Wattenhoffer presented a one-round algorithm to transform an $m$-coloring to a $q$-coloring, where $q = m(d+1)/(d+2)$ ($d$ is the max degree).
We can show that if $m >= d+2$, then $q <= m-1$. [Therefore the algorithm returns a smaller coloring, as long as $m >= d+2$]

They mention that by applying this one-round algorithm over and over, we can transform an $m$-coloring to a $(d+1)$-coloring in $O(d \log(m/d))$ rounds.
I don't understand how they reached this number.

I thought that the number of rounds n needed to fulfill the equation:

$m((d+1)/(d+2))^n = d+1$

Because $m$ is the starting coloring, and each round we get a lower coloring by a factor of $(d+1)/(d+2)$.
But this doesn't yield the proper result for $n$. Why is it wrong? We want to get $n = O(d\log(m/d))$.

The algorithm itself isn't very complicated and I don't think will contribute to the question; basically for every color that is larger than $q$, we choose for him a color from $\{ 1,\ldots,q \}$ in a way that ensures it is a legal coloring.

Anybody has any insights about the number of rounds needed to achieve a $(d+1)$-coloring?


texts: Data Structure to calculate which interval a point lies in?

texts:
I have a list of $n$ non-overlapping intervals, namely $[a_1,a_2],[a_2,a_3],...,[a_n,n_{n+1}], a_i \in \mathbb{N}$.

Each of these intervals has a corresponding value $v_i$ corresponding to it.

Now I have another interval $[x,y], a_1 \leq x < y \leq a_{n+1}$. I want to query the $n$ intervals and find the sum of values of the overlapping intervals with it in $O(\log n)$ time.

To make it clearer, I'll give an example.

Suppose the intervals are $[0,2],[2,4],[4,10]$ with values corresponding to $1,3,5$.

For the interval $[0,3]$, the first and second intervals overlap with it so a total value of 1+3=4.

For the interval $[0,5]$, all three overlap with it so a total value of 1+3+5=9.

For the interval $[5,9]$ only the last one overlaps it so the total value is 5.

I know that I can use a segment tree and query the point based on my interval $[a,b]$. However, how would I calculate the sum of all the values of all the intervals in between also in $O(\log n)$?


texts: Constructing vectors in general position

texts:
Let a real $k\times n$  ($k\le n$) matrix ${\bf A}$ with the property that any collection of $k$ columns is full rank.

Q: Is there an efficient way to deterministically find a vector ${\bf a}$ such that the augmented matrix ${\bf A}' = [{\bf A}\;{\bf a}]$ preserves the same property as ${\bf A}$: any $k$ columns are full rank.

Relevant Sidenote: A matrix that has this property is the generator of an $(n,k)$ Reed-Solomon Code: adding columns that preserve its Vandermonde structure preserves the rank property.


texts: Generalizing Parsing Expression Grammar for Context Sensitive Grammars

texts:
One of the things I like about parsing expression grammars is that they're automatically unambiguous, and unambiguity is a very important property to have. However, context-free grammars are somewhat weak. Is there a generalization of parsing expression grammars that works for context-sensitive grammars? What I mean by that is whether there exist a generalization such that

the generalization allows for nonterminal symbols to be on both sides of the production rule.
the generalization preserves the property that an unambiguous parse is always produced.


texts: Completing a matrix (over the reals) to be singular

texts:
Consider the following problem: you are given a matrix (say, with rational entries) some of whose entries are actually left blank; can these blanks be filled in with real numbers so that the resulting matrix is singular?

It seems like deciding this should be NP-hard. Is this so and has this problem ever been studied before?


texts: Structural equivalence of two context-free grammars

texts: I understand that determining if two context-free grammars are structurally equivalent is decidable (according to the 1968 paper by Paull, M.C. and Unger, S.H., "Structural equivalence of context-free grammars"). I wonder what the best algorithm for this problem is, and what the computational complexity of the algorithm is. Thank you.


texts: Is there a theoretical guarantee that an autoencoder $g$ has $I(x;g(x)) \approx H(x)$?

texts:
I know that in general, a function $g$ can be a good auto-encoder (i.e., $g(x) \approx x$ for $x \sim D$) and on the same time $I(g(x);x)$ is small. This is the case when $g$ forms a good correlation but no compression of the data.

I'm curious if there is any work that suggests that the training process or some regularization tends to implicitly select an auto-encoder that maximizes the mutual information $I(x;g(x))$.

Please let me know if there are some missing mathematical technicalities and if the question needs further clarifications.

Thanks!!


texts:
First of all, my understanding on Gödel's incompleteness theorem (and formal logic in general) is very naive, also is my knowledge on theoretical computer science (meaning only one graduate course taken while I'm still an undergraduate), so this question may be very naive.

As far as I could find, the provability of P versus NP is an open problem.

Now:

Gödel's first incompleness theorem states that there may be statements that are true but not provable nor disprovable.
If a polynomial solution is found for an NP-complete problem, it proves that P = NP.

So, suppose that P=NP is not provable:
This means that no example of a polynomial solution for an NP-complete problem can be found (otherwise, this would be a proof).
But if no example of a polynomial solution for an NP-complete problem can be found, this means that P=NP is false (proving it, meaning the statement is provable), which leads to a contradiction, therefore P=NP should be provable.

This sounds like a proof of the provability of P=NP to me, but I think it's extremely likely that it is due to my lack of understanding of the logic topics involved. Could anyone please help me understand what is wrong with this?


texts: Is there a tight lower bound on the complexity of SSSP on a graph?

texts: I'm an undergrad and I'm not sure if this is the right way to ask this question. I want to know the lower bound on single-source shortest path computation in a general graph. The graph is allowed to have negative weight edges.


texts: Is there a fast algorithm for inverting a sparse matrix?

texts:
I am doing research on a random-walk like problem. As a critical part of my solution, I need to invert a non-singular sparse matrix of size $n \times n$ and with $O(n)$ non-empty entries. I'm working over a sufficiently large field.

I'm looking for a fast algorithm to invert it (say, $O(n^2polylog(n))$). Is this achievable?


texts: Computability of infinite-dimensional vector space

texts:
So there is a talk about infinite-dimensional vector space being computable. But then I find it hard to understand. Apparently, dimension is infinite, so how would the operations of the space be computable?

Is it something like $\pi$ being computable, although it has infinite number of digits?


texts: Does small circuits for a NP-complete problem contradict ETH?

texts:
The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ size, then ETH fails. However, there are no references and proofs for this statement in the paper, and it is hard for me to get proof of this statement.

In fact, I have tried to prove the following weaker statement but failed. "If $SAT \in P/poly$, then ETH fails."

QUESTION: How to prove that: if Circuit Satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ size, then ETH fails?


texts: NP-hardness of a winner determination auction

texts:
We would need some suggestions for the proof of NP-hardness of an optimization problem.

The problem

$$
\max_{x_{a,s}}
\sum_s \sum_a x_{a,s} q_a \lambda_s \prod_{s' < s} \prod_{a' \neq a} (1 + x_{a',s'} (c_{a'}-1) )
$$

\begin{align}
\sum_{s \in S} x_{a,s} \leq 1 & \quad \forall a \in A \\
\sum_{a \in A} x_{a,s} \leq 1 & \quad \forall s \in S \\
x_{a,s} \in \{0,1\} &  \quad  \forall a \in A, s \in S
\end{align}

The parameters have the following structure:

\begin{align*}
c_a  \in [0,1]     & \quad  \forall a \in A\\
\lambda_s \in [0,1]   & \quad \forall s \in S\\
\lambda_s >\lambda_{s'}  & \quad \forall s,s' \in S:s<s'\\
q_{a} \in[0,+\infty)   & \quad  \forall a \in A
\end{align*}

In words: the problem requires one to assign the elements of $A$ to the elements of $S$ such that the value of each assignment is determined as follows

if an element $a$ is assigned to $s=1$, then the value of the assignment of this element is: $q_{a}\lambda_1$;
if an element $a$ is assigned to $s=2$, then the value of the assignment of this element is: $q_{a}\lambda_2 c_{a'}$ where $a'$ is assigned to $s=1$;
if an element $a$ is assigned to $s=3$, then the value of the assignment of this element is: $q_{a}\lambda_3 c_{a'} c_{a''}$ where $a'$ is assigned to $s=1$ and $a''$ is assigned to $s=2$;
and so on.

The total value of the assignment is given by the sum of the values of all the element assignments. So, with $|S|=3$, the total value is: $q_{a}\lambda_1 +q_{a}\lambda_2 c_{a'} + q_{a}\lambda_3 c_{a'} c_{a''}$.

The problem is easy (but we do not know whether it is hard in general) when:

$\lambda_s = 1$: the algorithm is based on dynamic programming starting from the last $s$ and going backward to the first
$c_a=1$: the algorithm is simple, being a greedy optimizer.

Question: any idea on how to find a reduction for proving the NP-hardness of the problem?


texts: Extensional characterization of non-deterministic finite state transductions

texts:
I recently became aware of the rather appealing characterization of deterministic word-to-word transductions as word functions with bounded variation (see e.g. [1]). This coincides with the set of functions that can be realized by subsequential transducers, which are deterministic finite state transducers with an output function defined on accepting states.

Not every function defined by a non-deterministic FST is subsequential, that is, even if the FST is single-valued, it might not be determinizable. I wondered if there are any extensional characterizations of the set of functions definable by (single-valued) FSTs?

Thanks!

[1] Bruyère, Véronique and Reutenauer, Christophe.  A proof of choffrut's theorem on subsequential functions. Theoretical Computer Science, 1999.


texts: 'Uniqueing' an unsorted list of integers

texts:
let $A = [ a_1 \dots a_n ]$ be a sorted list of integers of length $n$. By a simple algorithm that works in-place and in linear time we can remove all duplicates and output a sorted list of unique integers that are precisely the integers which appear .

More generally, it suffices to have a list with the promise that all identical integers are merely grouped to apply the same idea.

Now let $A$ be a list of integers, neither sorted nor even grouped as above. Let us call the problem of outputting a not-necessesarily sorted list of integers that are precisely the integers appearing $A$ by the term "uniquing problem".

An algorithm to solve the "uniqueing problem" might sort the list and remove multiple entries in the obvious way, thus requireing a running time of O( n log(n) ). Can we do better? I don't think so, although there might be a speed up because we actually do not require any sorting on the output list, so this algorithm performs actually too much.

Best,
Martin


texts: How many words of length $k$ on $l$ letters avoid a partial word?

texts:
EDITED TO ADD: This question is now essentially answered; please see this blog entry for more details.  Thanks to everyone who posted comments and answers here.

ORIGINAL QUESTION

This is a hopefully smarter and better-informed version of a question I asked on MathOverflow.  When I asked that question, I did not even know the name of the area of mathematics my problem was in.  Now I am pretty sure it lies in Algorithmic Combinatorics on Partial Words.  (Recent book on the subject here.)

I want to make a list of words on $l$ letters.  Each word has length exactly $k$.  The deal is, if $a \lozenge ^j b$ is in the list, where $\lozenge$ is a wildcard/don't-care symbol, then $a \lozenge ^j b$ can never appear again in the list.  (The same holds true if $a=b$, or if $j=0$ and hence the prohibited subword is $ab$.)

Example where $k=4$ and $l=5$:

$abcd$
$bdce$
$dcba$ <-- prohibited because $dc$ appeared in the line above
$aeed$ <-- prohibited because $a \lozenge \lozenge d$ appeared on the first line

The literature on "avoidable partial words" that I have found has all been infinitary -- eventually some word pattern is unavoidable if the word size is large enough.  I would like to find finitary versions of such theorems.  So, question:

  Given a partial word of form $a \lozenge^j b$ in an alphabet of $l$ letters, how many words of length $k$ avoid it, and can they be explicitly produced in polynomial time?

I don't expect the above question to be difficult, and, unless there is a subtlety I am missing, I could calculate it myself.  The real reason I am posting on this site is because I need to know a lot more about the properties of such word lists for my application, so I am hoping someone can answer the followup question:

  Has this been studied in generality?  What are some papers that consider, not just whether a partial word is eventually unavoidable, but "how long it takes" before it becomes unavoidable?

Thanks.


texts: How to find the "best vectors" in a given matrix whose sum of products is as small as possible?

texts:
The input is a matrix $\mathbf{A}=[a_{ij}]$ of real numbers $a_{ij}>0$ for all $i\in\{1,\ldots,k\}$ and $j\in\{1,\ldots,n\}$ and a real number $v$. The coefficient of the matrix are not all greater than $1$ nor all less than one.

The question is to find a subset $S$ of $\{1,\ldots,n\}$ and $S\neq \emptyset$ such that $$\sum_{i=1}^k\prod_{j\in S}a_{ij}\leqslant v.$$

In fact, in the optimization settings, I would like to find a subset $S$ whose sum of products is minimum.

Example: Take $v=0.55$ and $$\mathbf{A}=\begin{bmatrix} 0.1&2&3\\2&0.2&0.1\end{bmatrix}.$$ This has the solution $S=\{1,3\}$. Its value (its sum of products) is $0.5$.

How to solve this problem?  Is this problem known (or is there any similar problem in the literature)?

Besides enumerating all subsets of $\{1,\ldots,n\}$, I cannot find a good way to solve the problem.


texts:
I want to use use Agda to help me write proofs, but I am getting contradictory feedback about the value of proof relevance.
Jacques Carette wrote a Proof-relevant Category Theory in Agda library. But some seem to think (perhaps here, but I was told elsewhere) that proof relevance can be problematic. 1-Category Theory is supposed to be proof irrelevant (and I guess above two categories, this is no longer the case?) I even heard that one may not get the same results if one uses proof relevant category theory.
At the same time I believe the Category Theory in the HoTT book and the implementation in Cubical Agda are proof irrelevant (as the HomSets are Sets, i.e., have only one way of being equal).
When should I be happy to have proof relevance? When should I rather choose a proof irrelevant library or proof assistant? What are the advantages of each? Would proof irrelevance be problematic as I move to two categories?


texts: "forward-secure" zero knowledge protocols

texts:
Has anything been done on the modification of the zero knowledge condition

where the distinguisher has access to the witness used by the prover and

the random bits used by the algorithm that generated the auxiliary input?

(Or is that, in fact, how the zero knowledge condition is usually defined?)

This seems like it would be important for using ZK protocols as pieces of larger protocols,

since whether or not an adversary succeeds could depend on that information.


texts: Characterising invisible equivalences by confluent rewrite rules

texts:
In response to another question, Extensions of beta theory of lambda calculus, Evgenij offered the answer:

beta + the rule {s = t | s and t are closed unsolvable terms}

where a term M is solvable if we can find a sequence of terms such that M's application to them is equal to I.

Evgenij's answer gives an equational theory over the lambda calculus, but not one characterised by a reduction system, i.e., a confluent, recursive set of rewrite rules.

Let's call an invisible equivalence over a theory of the lambda calculus, a reduction system that equates some nontrivial set of closed unsolvable lambda terms, but doesn't add any new equations involving solvable terms.

Are there any invisible equivalences over the beta theory of the lambda calculus?

Postscript An example that characterises an invisible equivalence, but is not confluent.  Let M=(λx.x x) and N=(λx.x x x), two unsolvable terms.  Adding the rule rewriting N N to M M induces an invisible equivalence containing M M = N N, but has the bad critical pair where N N reduces to both M M and M M N, each of which has one rewrite available, which rewrites to itself.


texts:
I was reading through Gunter's Semantics of Programming Languages: Structure and Techniques and in the second chapter on simply typed $\lambda$ calculus he introduces an equational theory with $\beta\eta\xi$ equality $T \vdash (H \triangleright M = N : \tau)$

What are the references for different equational theories for standard type systems such as Hindley-Milner, System F, substructural logics such as linear logic, etc.


texts: Is there any algorithm to find just the largest eigenvalue with subquadratic time complexity?

texts:
SVD or PCA can be used find the largest eigenvalue, but at a cost of $O(n^3)$ complexity. Lanczos algorithm runs much faster on a sparse matrix with complexity $O(dn^2)$ where $d$ is the average number of non-zeros in a row. It is better, but still quadratic.

My question is does anyone know any sub quadratic algorithm to find just the largest eigenvalue. It can be a very approximate algorithm that just capture the magnitude of the largest eigenvalue.


texts: Complexity of counting spanning subgraphs that have cycle properties

texts:
Let $G = (V, E)$ be a connected undirected graph. I am interesting in counting the number of connected spanning subgraphs having:

$\ge 1$ cycle each (but can have any number of cycles),
Exactly $k \ge 1$ cycles each.

The subgraphs that have $k=1$ are called unicyclic subgraphs. So essentially, I want to count the number of unicyclic spanning subgraphs.

For the first case, it seems that we can just count the number of connected subgraphs (which seems to be #P-complete), then use Kirchhoff's matrix tree theorem to find the number of spanning trees, and find the difference of the two to get the number of connected subgraphs with $\ge 1$ cycle each.

The second problem seems like a special case of the first, but I haven't been able to find any resources of its complexity. I'm not even sure how to do this for a fixed value of $k$.

The application of this would be on better approximating coefficients of the reliability polynomial.

Edit: another interesting direction would be to investigate $k$-regular graphs for $k \ge 3$ (the $k=2$ case is known, of course).

Edit 2: for planar graphs, counting unicyclic subgraphs is poly-time computable (and due to Myrvold, this is reducible to matrix multiplication): http://link.springer.com/article/10.1007%2FBF01994058


texts: Is it sufficient to only check on the vertices? Greedy algorithm

texts:
Suppose that I have a downwards closed Polyhedron and a vector $\omega$ and a greedy algorithm that goes as follows:

Given an initial $x_0$, order the indices of $\omega$. Then for each $i$, solve $\max_{a\in \mathbb{Z}}\left(\omega^T(x_i + ae_i) \right)$.
Let $x_{i+1} = x_i + ae_i$ and repeat for $i+1$.

Output $x_n$

If I am looking for the worst-case performance of this algorithm, i.e.
$$
\sup_{\omega}\frac{\omega^Tx : x \in P}{\min Greedy(P, \omega)}
$$

Is it sufficient to verify the above for $\omega \in \{0, 1\}^n$? That is does the following equality hold:
$$
\sup_{\omega}\frac{\omega^Tx : x \in P}{\min Greedy(P, \omega)}
= \sup_{\omega \in \{0, 1\}^n}\frac{\omega^Tx : x \in P}{\min Greedy(P, \omega)}
$$


texts: Continuity vs Uniformity when designing Hash functions

texts:
Reading available literature (yep, including wikipedia), I see that hash functions should have (continuity) and map values that differ very little to similar/same hash codes, in particular for (hash tables that use linear search) ... if that makes any sense. Supposedly, this would help linear search benefits from locality of reference.

OTH, a hash function should be uniform, in the sense that hash values are uniformly distributed. Unless I'm misunderstanding something, it looks to me as if these two properties are in conflict.

Let's say we have a sequence $S$ of input values $(s_1, ..., s_n)$ such that the delta between any two value pairs is small and similar across the set.

That is

$$\forall s_i, s_j \in S\,\,|\,\varepsilon_{min} < \delta(s_i, s_j) < \varepsilon_{max}$$

and with the differences between any two values ($\delta(s_i,s_j)$) being uniformly distributed. In such a case the values in the sequence have a uniform distribution.

Let's suppose we aim to store these values in a hash table with open addressing (linear probing) and a hash function $h$. Obviously, we assume that the hash table is large enough to accommodate all input values (and to be below an initial load factor.)

If the hash function $h$ exhibits continuity, then it will map all the values in $S$ very close to one another (if not, to the same hash code) ergo increasing collisions. That is, it would exhibit clustering.

Wouldn't that then, deteriorate the search performance (via liner probing) as a result of the resulting collisions. If continuity is desirable when using linear probing, then how does one cope with the collisions when a large part of the values are close to one another?

--- EDIT ---

Sorry, I left some things out. $\delta(s_i,s_j)$ represents the number of symbols by which the strings $s_i$ and $s_j$ differ (or the number of changes that need to occur to convert $s_i$ into $s_j$.)

For a better example, let $\Sigma = {\sigma_1, \sigma_2, ... , \sigma_n}$ be an alphabet, and $L(i, n)$ be a language over $\Sigma$ such that

$$
L(i,n)\,\triangleq \{s| (s=\sigma_i^*\sigma_k\sigma_i)\wedge (|s| = n) \wedge (\{\sigma_i,\sigma_k\} \subset \Sigma)\}
$$

So, if we were to consider input strings, all of length $n$ such as
$$aaa..., baaa..., abaa..., ....aaab, caaa..., acaa$$

that only differ on one character, the value and position of which is uniformly distributed among the input strings, then a hash function $h$ that possess continuity will cluster them all on top or near the same hash value.

-- ADDITIONAL EDIT --

The only place I've read so far that mentions continuity as a desirable property has been in the Wikipedia article for hash functions. I've consulted all the other books I have on Algorithms (CLRS, Sedgewick's, Berman and Paul's and others), and I've not found any such assertion on hash functions.

So it seems to me that continuity is not a desirable trait despite what the Wiki entry says. Or am I missing something????


texts: Reducing the Height of Context-Free Grammars

texts:
Let $G$ be a context free grammar in Chomsky normal form (CNF) with language $L(G)\subseteq \Sigma^n$. In other words, all strings generate by $G$ have size $n$.

Say that a string $w\in L(G)$ has height $h$ if $w$ has a parse-tree of height at most $h$. Say that $G$ has height $h$ if each string $w\in L(G)$ has height $h$. Let $|G|$ be the number of production rules in $G$. I have the following problem, which I believe it is well studied in the field of parallel parsing, but with a somewhat distinct terminology.

Problem: Given a context free grammar $G$ in CNF accepting a language $L(G)\subseteq \Sigma^n$, construct a context free grammar $G'$ in CNF such that

$L(G') = L(G)$,
$h(G') = O(\log n)$,
$|G'| = |G|^{O(1)}\cdot n^{O(1)}$.

Does the problem given above has always a solution?
In other words, from $G$ we want to construct a context free grammar $G'$ accepting the same language as $G$ but such that every string in this language has a parse tree of logarithmic height. The size of the obtained grammar $G'$ is allowed to blow up polynomially in $n$ and in the size of the original CFG $G$.

I'm mostly interested in references dealing with the problem above or similar problems.

Obs 1: Without the requirement that $|G'|=|G|^{O(1)}\cdot n^{O(1)}$, we can construct a grammar $G'$ with size $2^{O(n)}$ by considering a distinct set of production rules for each string in $L(G)$.

Obs 2: I don't care about the time necessary to construct $G'$. The only important thing is its size $|G'|$.

Obs 3: Both grammars are required to be in Chomsky normal form. Also both are allowed to be ambiguous.


texts: Von Neumann architectures and quantum computing

texts:
Can you do quantum computing in a von neuman architecture? If not, why? What is the constraint? If you control a qbit, can a quantum computer use the von neuman architecture?

Thanks.


texts: Are resource savings for the evaluation of $k$ dependent instances in parallel possible?

texts:
Let $\phi(x_1,\dots,x_n)$ be a CNF. It is satisfiable if $\exists X=(x_1,\dots,x_n): \phi(X)=1$. Assume $\phi$ has a unique satisfying assignment. Then, by allowing only black-box queries to $\phi$, essentially $\Theta(2^n)$ queries will be required to find the satisfying $X$, i.e. to solve this NP-complete problem.

Now let us construct a circuit $C(X) = \bigvee_{\sigma_i \in S_n} \phi(\sigma_i(X))$, where $\bigvee$ is over all $n!$ many permutations $\sigma_i$ in the symmetric group $S_n$ of of $n$ elements. Thus, if evaluated in the trivial black-box way, $C(X)$ requires exponential time. But let us ignore this problem for a moment.

$C(X)$ has the nice property, that $C(X)$ has $n!$ satisfying assignment, if $\phi(x)$ has a unique one, and $C(X)$ remains unsatisfiable if $\phi(x)$ is. Essentially inputs to $C(X)$ are equivalent up to the number of $1$'s in the input. Thus testing $n+1$ different assignments with $0 \dots n$ bits set suffices to decide satisfiability of $\phi(x)$.

Let us now come back to the resources required to evaluate $C(X)$. Essentially $C(X)$ is solving $n!$ instances of the same problem (CNF evaluation) in parallel. There are (strong) direct product theorems which essentially say that solving $k$ independent instances of the same problem in parallel require essentially $k$ times the resources of solving a single instance (with non-neglible probability). But, crucially, the $n!$ instances of CNF evaluation we are solving are not indepent. We can walk over all permutations from one $\sigma_i$ to another $\sigma_j$ which differ only in the mapping of two variables. Thus, many clauses in $\phi(\sigma_i(X))$ and $\phi(\sigma_j(X))$ refer to the same variables and will evaluate to the same value. Thus evaluation of (large?) sets of clauses may be shared and reused while evaluating $\phi(\sigma_i(X))$ for various $i$.

The question I have is: are there any results on the resources required for dependent evaluation of $k$ instances of a problem (like direct product theorems, but maybe with contrary conclusion)? What impossibility result would an approach like the above run into as it implies a (novel?) approach for solving $NP$-complete problems? Would assuming $P \neq NP$ already imply a lower-bound on the dependent evaluation problem of $k$-instances, i.e. a generalization of direct product theorems?

EDIT: The problem appears to be a special case of the OR(SAT)-problem where one is given a set of SAT-instances $\psi_1, \dots, \psi_t$ and is aked to decide $\psi = \bigvee_{i=1}^t \psi_t$. The related instance compression problem asks for a reduction of $\psi$ to a much smaller instance $\psi'$. See this paper by Drucker for details and (references to) negative results on the problem. Thus, the minimized circuit $C'(X)$ in the answer below is an exponentially compressed instance of an OR(SAT)-problem, where the $\psi_i$ are equivalent to a single CNF $\phi$ up to relabeling of the input variables and the complete set of all possible relablings.


texts: Maximum clique algorithm on undirected graph

texts:
Recently I learned about maximum cliques. For fun I came up with an algorithm (described below) to find the maximum cliques in an undirected graph. I'd just like some help constructing a graph s.t. the algorithm returns an incorrect result.

Consider an undirected graph $G$ represented by an adjacency matrix $A$. If there exists an edge directly connecting node $i$ and node $j$ then $A[i][j] = 1$, $A[i][j] = 0$ otherwise.

Construct a hashtable $H$ where the keys are nodes in $G$ and the values are lists of nodes directly connected to the given node. For example a simple triangle graph with nodes $a$, $b$ and $c$ would have $H$ with key-values pairs $(a, [b, c])$, $(b, [a, c])$ and $(c, [b, a])$.
Traverse all keys in $H$. For each key traverse the corresponding value and check if every node in the list is connected to every other node in the list. If a node $i$ is not connected to any single node $j$ then remove $i$ from the list.
Traverse the keys in $H$ again. Keep track of the maximum count $m$ of all values. $m$ will be the size of the maximum clique(s) in $G$.
Traverse the keys in $H$ again. This time print the contents of the value for a given key if value.count equals $m$.

I've tried a variety of graphs as inputs and so far I haven't found a good counter example.

Regarding the algorithm's runtime:

step one can be done in $O(N^2)$ time. This requires visiting every entry of the $NxN$ adjacency matrix $A$. Inserting an entry into $H$ can be done in amortized constant time.
step two takes $O(N^3)$ time. Traverse every key in $O(N)$ time. For a given key $k$ checking all the directly connected nodes takes $O(N^2)$ time.
step three runs in linear time
step four runs in $O(N^2)$ time (when accounting for printing the nodes)

So the overall runtime is $O(N^3)$ where $N$ is the number of nodes in $G$.

From some research it doesn't sound like finding maximum cliques in an undirected graph (without any constraints on the graph) can be done in polynomial time. Hence there's probably some nice corner cases for the above algorithm. Please help find some.


texts: Simple randomized priority queue matching the Fibonacci heap time bounds?

texts:
Since the Fibonacci heap was developed, many other priority queues have been invented with equivalent time bounds and a simpler design (e.g. hollow heaps, quake heaps, etc.).
Many classical worst-case efficient data structures have related randomized data structures that meet the same time bounds on expectation (e.g treaps and zip trees for sorted dictionaries, randomized incremental trapezoids for point location, cutset structures for dynamic connectivity, etc.). However, the only randomized priority queue I’ve encountered is the randomized meldable heap, which doesn’t meet the same time bounds as the Fibonacci heap (particularly for decrease-key).
Are there any known randomized data structures that meet the Fibonacci heap time bounds with a “simpler” implementation, for some subjective definition of “simpler?”


texts: When does a bipartite graph have bounded treewidth?

texts:
As the title says, I want to know when the treewidth of a bipartite graph is bounded by a constant. What families of graphs are both bipartite and bounded treewidth?
More generally, I would like to find a property $P$ such that for any bipartite graph $G$ the following statement is true: "the treewidth of $G$ is bound by a constant if and only if $G$ satisfies property $P$."


texts: Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?

texts:
In this question, a 3CNF formula means a CNF formula where each clause involves exactly three distinct variables.  For a constant 0<s<1, Gap-3SATs is the following promise problem:

Gap-3SATs
Instance: A 3CNF formula φ.
Yes-promise: φ is satisfiable.
No-promise: No truth assignments satisfy more than s fraction of the clauses of φ.

One of the equivalent ways to state the celebrated PCP theorem [AS98, ALMSS98] is that there exists a constant 0<s<1 such that Gap-3SATs is NP-complete.

We say that a 3CNF formula is pairwise B-bounded if every pair of distinct variables appears in at most B clauses.  For example, a 3CNF formula (x1∨x2∨x4)∧(￢x1∨￢x3∨x4)∧(x1∨x3∨￢x5) is pairwise 2-bounded but not pairwise 1-bounded because e.g. the pair (x1, x4) appears in more than one clause.

  Question.  Do there exist constants B∈ℕ, a>0, and 0<s<1 such that Gap-3SATs is NP-complete even for a 3CNF formula which is pairwise B-bounded and consists of at least an2 clauses, where n is the number of variables?

The pairwise boundedness clearly implies that there are only O(n2) clauses.  Together with the quadratic lower bound on the number of clauses, it roughly says that no pair of distinct variables appears in significantly more clauses than the average.

For Gap-3SAT, it is known that the sparse case is hard: there exists a constant 0<s<1 such that Gap-3SATs is NP-complete even for a 3CNF formula where each variable occurs exactly five times [Fei98].  On the other hand, the dense case is easy: Max-3SAT admits a PTAS for a 3CNF formula with Ω(n3) distinct clauses [AKK99], and therefore Gap-3SATs in this case is in P for every constant 0<s<1.  The question asks about the middle of these two cases.

The above question arose originally in a study of quantum computational complexity, more specifically two-prover one-round interactive proof systems with entangled provers (MIP*(2,1) systems).  But I think that the question may be interesting in its own right.

References

[AKK99] Sanjeev Arora, David Karger, and Marek Karpinski.  Polynomial time approximation schemes for dense instance of NP-hard problems.  Journal of Computer and System Sciences, 58(1):193–210, Feb. 1999.  http://dx.doi.org/10.1006/jcss.1998.1605

[ALMSS98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  Journal of the ACM, 45(3):501–555, May 1998.  http://doi.acm.org/10.1145/278298.278306

[AS98] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs: A new characterization of NP.  Journal of the ACM, 45(1):70–122, Jan. 1998.  http://doi.acm.org/10.1145/273865.273901

[Fei98] Uriel Feige.  A threshold of ln n for approximating set cover.  Journal of the ACM, 45(4):634–652, July 1998.  http://doi.acm.org/10.1145/285055.285059


texts: Is it beneficial to regularly read papers outside your field?

texts:
What do you think about regularly reading papers outside one's own field, even those which are not related to one's area? My intuition is that it can give a totally different perspective or technique that may help someone in solving his or her own problems. But at the same time I am a bit skeptical about it as it will be a waste of time if the new knowledge doesn't help him in his own work.
What are your thoughts on this? Is there any other way one can look for results unrelated to his own work? What about TCS+ series?


texts: FL with polynomial number of log-space "reductions" still in FL?

texts: Suppose that $f: X \rightarrow X$ is computable in log-space. Given an input $x \in X$ where $x$ is encoded within $n$ bits, is $f^n(x)$ computable in log-space?


texts: Why is the security of lattice cryptosystems not provable from $P \neq NP$?

texts:
My understanding is that the Shortest Vector Problem ($\text{SVP}$) is $\text{NP}$-hard.  Therefore, $\text{LWE}$ is also $\text{NP}$-hard.  But $\text{LWE}$ is hard on average if it is hard in the worst case, so breaking certain cryptosystems based on it is also $\text{NP}$-hard, which means that secure asymmetric encryption is not only possible but known, unless $\text{P} = \text{NP}$!

That would be a rather striking result, and to my knowledge it has not been clamed in a serious paper.  What is the flaw in my reasoning?


texts: Connectivity of a random regular graph of degree $d$

texts: An Erdos-Renyi graph over $n$ vertices and average degree $d$ is not connected whp iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be connected? In particular will this be connected for some degree less than $\log n$?


texts: Parse structure of a range concatenation grammar (RCG)

texts:
I know that with a context-free grammar, one can represent the results of a parse as a parse-tree. Specifically, each node represents one application of a production rule, is usually named for the LHS nonterminal, and its children are the nonterminals on the RHS.

For a context sensitive grammar, it's arguably possible to do the same thing, and to just decorate each node with its production rule's left and right context (non)terminals (or even ignore them entirely).

I've been staring at range concatenation grammars for a few hours now and am slightly boggled with respect to their parse representation. They're weaker than CSGs, stronger than CFGs, and yet I can't seem to digest how their parses are represented. Yes, I could say, "Oh, for this grammar it's clearly a tree because you can construct a tree of the production rules!" But that seems unsatisfactory to me because with CSGs and with CFGs one can trivially recreate the string by infix walking the parse tree. With an RCG, I don't see that being possible without an excess of bookkeeping due to rules like

$A(xay) \rightarrow B(by)$

(where ASCII symbols $\leq d$ are terminals and $\geq x$ are variables).

Here to recreate the string one would need to crawl back up the parse tree from any unary production rule $B$ just to figure out that some other production rule $A$ added a symbol $b$ (a new instance non-existent in the original string) to what had been 'produced' in $B$.

It makes me uncomfortable in a, "This seems oddly inelegant," sort of way. The feeling is of course unfounded and arbitrary, but it's there.

What's up with range concatenation grammars' parse representations? Is there a more elegant/useful way of representing their parse results than the trivial [production-rule $=$ subtree] intuition?

EDIT

As I read more into Earley parser designs for RCGs, it seems that there's the shared 'forest' way of representing them in papers by Boullier and Kallmeyer, but that doesn't give a particularly clear intuition for what an individual parse is; they may call it a 'forest' but that doesn't seem to imply the existence of nice and clean 'trees'. :-/

EDIT 2

I might be conflating features of literal movement grammars with range concatenation grammars. The interpretation I gave of the predicate clause above may be entirely incorrect...

EDIT 3

Okay, a key point to all of this is that a terminal appearing in a predicate on the RHS of a clause is actually just a range that is defined to span a part of the input string that is exactly that terminal. This lends credence to the equivalence of these two clauses in the presence of $C(c) \rightarrow \epsilon$:

$A(x) \rightarrow B(xc)$
$A(x) \rightarrow B(xy)C(y)$

Navigating the parse tree still requires bookkeeping, but the rationale behind that bookkeeping makes more sense.

Also, I might still very well be writing invalid rules in this example. I don't know if it's a requirement that the ranges present on the RHS be within the ranges of the LHS or if they may both span anywhere within the original string. If the former, maybe the tree makes a whole lot of sense and that's why I've been misunderstanding this.

EDIT 4

If I'm understanding Kallmeyer in 'Parsing Beyond Context-Free Grammars' correctly, the ranges appear to be able to span anywhere in the original string. Maybe. I'm still feeling that's a bit ambiguous.

EDIT 5

It is necessarily the case that the ranges are allowed to span anywhere in the input string being recognized by the grammar regardless of the ranges spanned by the arguments on the LHS of a clause, otherwise Boullier's remarks at the top of page 274 in "Recent Developments in Parsing Technology" (doi:10.1007/1-4020-2295-6_13) would make jack little sense.

Which correspondingly means that my original question still stands.


texts: Fitting minimum number of rectangles of width/height 1 into a 2D grid

texts:
Consider a problem in which you are given a 2D grid (e.g. a chessboard) where certain squares are occupied
and you need to put the minimum number of non-overlapping rectangles of any size w x h where w = 1 or h = 1 (i.e. "square segments") such that all unoccupied squares are covered and each rectangle covers only unoccupied squares.

For example, for the grid

..###
.....
..###
.#...

the solution would be 4, since you can cover all the unoccupied squares (denoted by '.') with 4 such rectangles as follows:

12###
12333
12###
1#444

I tried to come up with a polynomial algorithm or prove that this problem is NP-hard, but without success. Can anyone help me to prove / disprove that this is problem is in P, or point me to some related work / problems?


texts: Minimal DFA satisfying a finite view of a language

texts:
Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq L$ that are known to be in the language, and a finite set of strings $B \subseteq (\Sigma^* \setminus L)$ that are known to not be in the language.

For example, let's say I have the $A = \{ab, aaab, aaaaabb\}$ and $B = \{b, aab, aaaba\}$. I might have the language $L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$, since $A$ and $B$ are consistent with $L$, or I might have a completely different language.

My question is: is there a known way to create a DFA (deterministic finite automata) that accepts the strings in $A$ and rejects the strings in $B$, with a minimal or almost-minimal number of states? What's the complexity of this problem? How good is it at approximating $L$ (assuming $L$ has a fairly low descriptive complexity, and $A$ and $B$ are large)?

Original question on math.stackexchange.com. I decided to repost here after getting no answers on the original question, and having no idea where to look for them. If someone could point me toward research in this area, it would be greatly appreciated.


texts: Infinite $\beta \eta$-reduction sequence implies infinite $\beta$-reduction sequence

texts:
In Sorensen and Urzyczyn's book there is a lemma (1.3.11) which I am having a hard time proving.

1.3.11 Lemma:
If there is an infinite $\beta \eta$-reduction sequence starting with a term $M$ then there is an infinite $\beta$-reduction seqeunce from $M$.

Now the proof is sketched in the book but I am having trouble realising it:

Proof.
First observe that in an infinite $\beta\eta$-reduction sequence there must be infinitely many $\beta$-reduction steps (cf. Exercise 1.6). These $\beta$-reduction steps can be "permuted forward", yielding an infinite $\beta$-reduction. Indeed, by induction with respect to $M \to_{\eta} N$, one can show that $M \to_{\eta}N \to_{\beta}L$ implies $M \to_\beta P \twoheadrightarrow_{\beta \eta} L$, for some $P$.

So $\to_\eta$ is defined as the least compatible relation satisfying $\lambda x . f x \to_\eta f$. Where compatible means works with the syntax, i.e. $A \to B$ imples $M A \to M B$, $A M \to B M$ and $\lambda x . A \to \lambda x .B$.
The definition is similar for $\beta$ with the obvious reduction. The relation $\to_{\beta \eta}$ is the union of both. And $\twoheadrightarrow$ is the transitive-relfexive closure of said relation.
Exercise 1.6 was to prove that $\to_\eta$ is strongly normalising, which can be shown by considering a "depth" function on terms, and showing that this strictly decreases on $\eta$-reduction.
The problem I am having is I can't seem to understand how $\beta$ and $\eta$ interact.
Take for example $\lambda t. (\lambda  x . y) t$. Clearly we can $\beta$-reduce this to get $\lambda t . y$ or $\eta$-reduce it to get $\lambda x . y$ which are clearly equal but its not obvious to me in general.

How can this be proven? And better yet, are there any references for this? I can't seem to find much on $\eta$-reduction in lambda calculus.


texts: Fast high-dimensional K-nearest neighbors

texts:
I'm aware of this question
https://stackoverflow.com/questions/4350215/fastest-nearest-neighbor-algorithm
But it's not the same question as I'm asking. Because, Octree and its generalization are only applicable to very small $D$, and they increase exponentially with regard to it. But I'm interested in very high dimensional cases, like $D>1000$. Assume we have a cloud of $N$ points in a $D$ dimensional space. But they might have a lower inherent dimension $d$, i.e., they lie on a $d$ dimensional manifold. Now, what is the most efficient way to compute K-nearest neighbors for each point? I've researched this topic a little bit, but most of the literature focuses on KNN clustering which is slightly different from what I'm asking. First, I don't have any labels here and those methods which rely on labels to reduce complexity are not of any interest. Second, many methods focus on reducing query processing time, which means they pre-process the data, build a database, and quickly process new queries. But I'm interested in reducing the overall time complexity rather than queries. What is the state-of-the-art method and its time complexity?

UPDATE:
One might assume that these points are uniformly spread in a hyper-cube. I suppose anything which holds for uniform distribution, to a lesser extent will hold for a smoothly changing distribution.


texts: Finding divisors of an interval of integers

texts:
This numerical problem arose in one of my projects. It seems simple at first sight, but I can't seem to find a good approach. Maybe someone else has an idea:

We have two integers, $n$ and $N$. Let's say that $n \approx 10^6$ and $N>10^{18}$.

I need to create a list of all numbers between n and $\sqrt N$ that divide some number in the interval $[N,N+n-1]$.

Obviously, each number can divide at most one, and the total number of answers is approximately $n \ln{\sqrt N  \over n}$; $6.9*10^6$ for $10^{18}$.

The most straightforward approach is to enumerate all integers from $n$ to $\sqrt N$ and to try each one, and that takes $O(\sqrt N)$ operations. Surely we can do much better?


texts:
Suppose $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$ is some some continuous function

$x_1 \ldots x_n$ is a set of real values, and we'd like to compute

$\text{argmin}_a \sum_i f(a,x_i)$ to prescribed accuracy

Are there some results on difficulty of this problem for various f?

For instance, suppose $f(m,x)=(m-x)^2$. The minimum of our problem is now the mean of x's, easy to compute. On other hand, suppose $f(m,x)=\log (1+\exp(-m x))$, there's no closed form solution, so it seems argmin is harder to compute...or is it?

Motivation: this minimization problem comes up when fitting models to data. First example of f is least-squares fit and second f is logistic regression.

Edit: I just saw a related question, and it is in the spirit of what I was asking, for a particular choice of f


texts:
If one restricts Turing Machines to a finite tape (i.e., to use bounded space $S$),
then the halting problem is decidable, essentially because after a number of steps (which can be calculated from the number of states $Q$, and $S$, and the alphabet
size), a configuration must be repeated.

  Are there other natural Turing Machine restrictions that render halting decidable?

Certainly if the state-transition graph has no loops or cycles, halting is decidable. Any others?


texts:
I have a card game that I am analyzing with Maple. Actually, it's a series of card games, one for every parameter k, where k is a natural number (representing the number of ranks of cards used in the game). For small k, it is feasible to completely solve the game by reverse induction. I am trying to create an AI that will play optimally from this.

Given a winning position (and it being the computer's turn) the computer can answer easily with any move that takes the position to a losing one for the player. However, what to do with a losing position? Of course, picking a random move is a terrible strategy. Is there some way to make life very difficult for the human player? One idea I had was to make it choose a move that maximizes the length of the minimum path needed for the player to win the game. That would seem to avoid getting into all the psychology of what human weaknesses are in the game etc.

I am aware that this problem is completely general (does not depend on the game). However, I had difficulty finding good references. Does anyone have any references for someone interested in learning about AI in this setting?


texts: On the notion of positive rank of a matrix

texts:
The positive rank of a square matrix is defined in Theorem $3$ of "Expressing Combinatorial Optimization Problems by Linear Programs" by Mihalis Yannakakis as follows: given a $n\times n$ matrix $A$, the positive rank $rank_{\Bbb R}^+(A)$ is the smallest $m$ such that $A=LR$ for a non-negative $n\times m$ matrix $L$, and non-negative $m\times n$ matrix $R$.

This concept is valuable in communication complexity, since it was shown that if $rank_{\Bbb R}^+(A)$ and $rank_{\Bbb R}(A)$ could be subexponentially related for a $0/1$ matrix $A$, then the log-rank conjecture holds.

Is there an exponential separation between $rank_{\Bbb R}^+(A)$ and $rank_{\Bbb R}(A)$ for a general non-negative real matrix $A$ (as opposed to just $0/1$) or is this problem also open?

I checked the references in Jukna's book, but I am still unable to clarify the above question.


texts: Is there a geometrical picture for adiabatic quantum computation?

texts:
In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily coolable initial (ground) state with Hamiltonian $H_i$ and "anneal" (adiabatically perturb) towards $H_p$, i.e.

$$
H(s) = s H_i + (1-s) H_p
$$

where $s \in [0,1]$. Details about AQC: http://arxiv.org/abs/quant-ph/0001106v1

The interesting thing about this problem is to try to understand the gap between the ground state eigenvalue and the first excited state, as this determines the problem complexity. One interesting thing to do would be to try and say something about the behavior of certain types of Hamiltonians. One can analyze the energy spectrum of small qubit cases by simulation to understand the problem complexity, but this becomes infeasible very quickly.

What I'd like to know is if there is a geometrical or topological way of looking at how certain Hamiltonians behave. Someone mentioned that the above form could be looked at as a homotopy (if the scalar functions were generalized to operators), but I'm not well-versed in higher level mathematics so I'm not sure what this implies or what I could do with it.

It might help to mention that the Hamiltonians are usually Ising spin-glass Hamiltonians (at least, that is what $H_p$ is). I'm not well-read on advanced statistical mechanics literature either, so this may be another avenue.

I wondered if anyone could provide some explanation on this, or at least provide some interesting references, keywords, etc.


texts: Is there a proof that addition is faster than multiplication?

texts: The best upper bound known on the time complexity of multiplication is Martin Fürer's bound $n\log n2^{O(\log^* n)}$, which is more than linear time complexity of addition.  Do we have a proof that addition is inherently easier than multiplication?


texts: Games on Turing machines that are AH-hard

texts:
I'm interested in proving that finding optimal play in a particular two-player game is harder than the arithmetic hierarchy. I suspect this to be true, because even carrying out a deterministic end-game to it's conclusion is Turing complete. I was hoping to complete my proof via encoding in it the following game:

  The Polynomial Equation Game: Let $n$ be any positive integer and let $P$ be a multivariate polynomial with $n$ variables and integer coefficients. We define a two-player game by letting each player pick an integer of their choice, alternating picks until $n$ integers (not necessarily distinct) have been picked. The first player wins if $P(x_1,\ldots , x_n)=0$.

It follows from Matiyasevich's theorem (plus a little algebra work) that optimal play for every $P$ and every $n$ harder than the arithmetic hierarchy. Unfortunately, this has turned out to be quite difficult to encode due to the rules of my game.

As I have been able to model a universal Turing machine in a deterministic version of my game, I am considering if that can be extended to the proof I am after. One idea I've had is the following:

  The Monotonic Turing Machine Game: Let $\Phi$ be a universal Turing machine and let $n$ be an integer. We define a two-player game by letting each player pick a non-blank symbol (out of those that $\Phi$ reads) of their choice and set any blank cell of the input tape to that symbol. Players take turns picking symbols and writing to cells until $n$ symbols (not necessarily distinct) have been picked. The first player wins if $\Phi$ halts on the input constructed in this fashion.

Suppose that we have a globally-fixed $\Phi$ and encoding for the tape. Is it the case that optimal play for every $n$ is AH-hard? This intuitively feels like it should be the case, but the monotonicty of the input is tripping me up. Additionally, it is not the case that this game is $\Delta^0_n$-complete for each $n$, in stark contrast to the Polynomial Equation Game. It seems reasonable that, for infinitely many $n$, this game for a given $n$ is $\Delta^0_n$-complete (or $\Delta^0_{f(n)}$-complete for some unbounded $f:\mathbb N\to\mathbb N$) but I don’t see how to prove it because previous proofs along these lines I’ve done have all been inductive.

If the answer depends on the Turing machine in question, let's say it is the $(2, 18)$ universal Turing machine.


texts: Finding balanced disjoint cycles in bridgeless cubic graphs

texts:
Petersen's theorem states that a bridgeless cubic graph contains a perfect matching (1-factor). Motivated by this question, Complexity of finding 2 vertex-disjoint (|V|/2)-cycles in cubic graphs? I am interested in the problem of deciding the existence of perfect matching $M$ such that removing the edges of $M$ leaves two node-disjoint cycles of equal cardinality  (each cycle has size $|V|/2$).

  Is this problem solvable in P-time? Is it $NP$-complete?

The input is connected bridgeless cubic graph.