texts: Reinforcement Learning and Optimistic Decisions

texts:
Sutton recommended using an optimistic heuristic on decision making by considering the upper bound of the confidence range of an action-value.  From my testing, it seems to work.  I find this fascinating and wonder if it could be proven that optimistic thinking (within these limits) is actually a sound policy for life in general.  This may sound a bit off-topic, but I don't think so.  I universal truth that can actually be codified would be a real discovery, imho.

Question: is it a universally sound policy to use the "high" confidence probability in the formula:

$ActionValue = P(X) \cdot Value(X)$ <- utility theory, reinforcement learning

So, $P(X)$ will have a confidence interval based on the number of samples.  You can optimistically just use $P(X) + confInterval / 2$ to get $Popt(X)$.  This seems to work well in practice.  Is this a universal truth?


texts: Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to require?


texts: Hierarchy theorem for approximation ratios?

texts:
As is well known, NP-hard optimization problems can have many different approximation ratios, ranging all the way from having a PTAS to not being approximable within any factor. In between, we have various constants, $O(\log n)$, $poly(n)$, etc.

What is known about the set of possible ratios? Can we prove any sort of "approximation hierarchy"? Formally, for what functions $f(n)$ and $g(n)$ can we prove that there exists a problem with approximation ratio $f(n)\leq \alpha < g(n)$?

In the case that $\alpha=O(1)$, does there exist a problem with approximation ratio exactly $\alpha$?


texts: Any existing Reeds-Shepp implementations?

texts:
Does anyone know of any open source implementations for finding the optimal path of a Reeds-Shepp car?

I'm trying to implement the formulas myself, but I'm having trouble with one of them. I think it's a typo in their paper; their formula just doesn't spit out the expected result.

The specific formula is found in Section 8.3 in Reeds and Shepp's 1990 paper, found here. I'm trying to find the optimal path from (x = 0, y = 0, theta = 0) to (x = 0, y = 0, theta = -pi), or put differently: the car goes back to the starting position, but pointed in the opposite direction. The correct solution is shown in Figure D of Section 1. The formula in Section 8.3 should give the same turn lengths, but it doesn't. The three turn lengths should all be pi / 3, but working it out by hand gives me completely different values.


texts: Are there any natural hard problems where it is required that the number of solutions are always more than one?

texts: If there are no accepting paths or only one accepting path, it outputs zero. And If there are more than one accepting paths it outputs Yes. I am looking for a natural problem that requires this.


texts: Two paper appear to imply collapse via coloring $P_5$-free graphs

texts:
Found this from graphclasses.org.

Two papers give conflicting results for coloring $P_5$-free
graphs  which appear to imply $P=NP$.

From Polynomial-time algorithm for vertex k-colorability of P_5-free graphs

  Abstract. We give the first polynomial-time algorithm for coloring vertices of P5 -free graphs with k colors. This settles an open problem and generalizes several previously known results.

From Some new hereditary classes where graph coloring remains NP-hard, p 5

  ... Coloring is NP-hard in $2K_2$-free ... and $\{C_5,P_5\} \cup \ldots$-free

$2K_2-free \subset P_5-free$ and the other class contains $P_5$.

According to graphclasses, another reason for hardness is
clique cover on the complement (another paper), click +Details
for references.

Question:

  What is wrong with this seeming contradiction?


texts: Using partial functions to prove correctness

texts:
I'm interested in proving that a program (which may or may not terminate) will give the correct answer if it terminates.  Given:

$P$ is a family of programs, parameterized by a function $f$. Write $P_f$ for a particular program from this family.
We know that $P_f$ is correct.
$g$ is partial function from the same domain to the same range as $f$.
Moreover, $g$ is a subset of $f$; that is, for all $x$ where $g(x)$ is defined, $g(x) = f(x)$.

I'd like to show that $P_g$, wherever it terminates, gives the correct answer.  This seems intuitively obvious.  However, I'm struggling to find the appropriate math for it.

Most importantly, if we use functions instead of programs the claim is not correct.  For example, if $Q$ is a multivariable function, $Q(f,n)$ does not in general equal $Q(g,n)$, even if they're both defined.  However, if we think of $Q$ not as a function but as a program, which gets to use $f$ and $g$ as oracles, then they are.  What is the proper way to show that mathematically? Or, even simpler: What is the correct mathematical term for $Q$? If it's not a function, what is it?

By program, I mean "algorithm which makes use of an other algorithm"; I'm not referring to any particular language or implementation.  Note that even in functional languages like Haskell, due to the Halting Problem, a program is not truly a function: a program isn't guaranteed to terminate, whereas the concept of terminating doesn't apply to functions.  A function of $f$ can depend on whether $f$ terminates, but no program which uses $f$ as a subroutine can.

Indeed, this is the essence of waht I'm struggling with: What is the appropriate mathematical formalism for a program which uses other programs as subroutines?


texts: Maximal non-reducible vertex cover of a graph

texts:
Let $G=(V,E)$ be a graph (i.e. an undirected simple finite graph).
We say that a vertex cover $V'$ of $G$ is non-reducible if any $V''$ with $V''\subsetneq V'$ is not a vertex cover of $G$. We say that a non-reducible vertex cover $V'$ of $G$ is maximal if for all non-reducible vertex cover $V''$ of $G$ we have $|V''|\le |V'|$. Note that the minimum vertex cover is non-reducible, but of course not necessarily maximal.

What is know about the (time)-complexity of finding a maximal non-reducible vertex cover?

Is there anything known for hypergraphs with multiple edges?


texts:
I am searching for the VC-dimension of the following set system.

Universe $U=\{p_1,p_2,\ldots,p_m\}$ such that $U\subseteq \mathbb{R}^3$. In the set system $\mathcal{R}$ each set $S\in \mathcal{R}$ corresponds to a sphere in $\mathbb{R}^3$ such that the set $S$ contains an element in $U$ if and only if the corresponding sphere contains it in $\mathbb{R}^3$.

Details which I already know.

The VC-dimension is atleast 4. This is because if $p_1,p_2,p_3,p_4$ are 4 corners of a tetrahedron then it can be shattered by $\mathcal{R}$
The VC-dimension is atmost 5. This is because the set system can be embedded in $\mathcal{R}^4$ with spheres in $\mathcal{R}^3$ corresponding to hyperplanes in $\mathcal{R}^4$. It is known that hyperplanes in $\mathcal{R}^d$ have VC-dimension $d+1$.


texts: How to quantify the complexity of vectors whose components are real numbers?

texts: I started to study Kolmogorov complexity today, and  this question came to mind. Is there any way to use LZW to do this? I'm looking for a guidance to my studies


texts: On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?

texts:
Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which for people like me is more well grounded than basing on some other unknown and pure beliefs.

Is there a reference on P=BPP possibility earlier than this that goes into considerable depth?
On page 406 they state 'It should be clearly realized however that we have not seen a randomized algorithm which works faster than a deterministic one'. Now FPTAS for permanent came after this in 1988 and Toda's theorem came in 1991. Is there a philosophical take on what Kolmogorov would have thought if he had seen these before he passed away in 1987?

Note that our view of P=BPP is framed from circuit lower bounds. Kolmogorov's view was likely different and could not have come from circuit lower bounds.


texts: Is the running time of Boyer-Moore linear?

texts:
With pattern length $M$, text length $N$, and alphabet $\Sigma$,
is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$
(even when $M$ grows larger than $|\Sigma|$)?

Are there any sublinear expected-time string matching algorithms (on all alphabet sizes)?


texts: major applied focuses of different proof assistants

texts:
Currently, what are the major applied focuses (if any applications can be deserved such a distinction) of different proof assistants, such as the following? If there are significant differences between each of these assistants, why?

Coq
Isabelle
Mizar
Agda
NuPRL
any other assistants you have a lot of experience with.

This may be an overly broad question for this site; in that case, this more specific question may work better: what are the strengths and weaknesses of these proof assistants for formal verification? (for example, to me intuitively the set theoretic foundation of Mizar seems like a misfit for verification, but I really don't know if this intuition is correct)

(I can't quite justify the broadness of the question, but here's some context: I am the most familiar with Coq and its usage in verification and formalization of mathematics, but much less so with the other assistants. So I guess I want to know what is out there. It's kind of like categorical thinking (as opposed to set theoretic thinking): an object should be characterized by how it's used rather than its extensions. Currently I know some scattered facts about each of these assistants but I really don't have an idea how they are used in practice, other than Coq.)


texts: Algorithm for inverting a bijective function.

texts:
Does there exist a generalized algorithm for finding the inverse function of an arbitrary bijective function?

In order for this algorithm to be
useful, it must eventually halt once
the correct answer is found.
Beyond the requirement that it must find the solution eventually, there is no time constraints on the time it takes to find or run the inverse function (with that in mind, something better than bruteforce guess-and-check, would be more interesting).

For example, if such a generalized algorithm existed it could solve for a decompression algorithm for a lossless compression algorithm.

EDIT:

I really liked Evgenij Thorstensen assumptions as they summed up my question fairly well.

Assumptions

Computable bijective functions over a fixed alphabet (say {0, 1})
Represented by a deterministic Turing machine (DTM) that computes it
The proposed algorithm would be able to solve for a DTM that would invert the original bijective function output.

Another shot at explaining it:

Given: Bijective function F that maps X from domain A onto Y from domain B.

Proposed algorithm should be able to solve for a Bijective function G that maps Y from domain B onto X from domain A, such that G(F(X))=X and F * G = I where I is the identity function.


texts: Actual practical example of a prefix-free Turing-complete language

texts:
A theoretical construct that comes up a lot in algorithmic computability theory is a universal prefix-free language. For my purposes, this is a language with the following properties:

its syntax is defined by a binary prefix code. That is, concatenating extra digits to the end of a valid program will never result in another valid program, and if you keep choosing 0s and 1s at random indefinitely, you will eventually end up with a valid program.
it is Turing complete
its output is a stream of binary digits

I have a slightly crazy idea that would require me to play around with an actual implementation of such a language - I want to be able to generate arbitrary (self-terminating) binary strings, have them interpreted as programs, and get binary strings as output.

Of course, in principle I could just invent some kind of trivial prefix-free encoding of ASCII, run it through an interpreter for my favourite language, and convert STDOUT to binary. However, if I do this, the chances of it doing anything other than terminate immediately (with a syntax error) are vanishingly small. Thus, I also have the following requirement:

The language is such that a (uniformly) randomly generated program has a reasonable chance of doing something non-trivial and returning output

My question is whether such a language exists - either as a formal definition in the literature that wouldn't be too time-consuming to implement, or as a command line tool or (better) a library that can be called from C++ or Python. Given the amount that has been written about this construct, I would find it mildly surprising if no-one had constructed a concrete example, but I haven't been able to track one down.


texts: I would like to know how is theoretical computer science helping to understand mathematics, physics and biology better in our universe. How is it all merging out and how is theoretical computer science helping us to get a better understanding of nature around us? Perhaps some physical problem solved by some unconventional way of using computer science to help understand something in nature that wasn't previously understood well enough/or not understood at all. I don't mean just the application of part of something like the internet for sharing data, but something like theoretical computer science offered a new insight into, for example like quantum mechanics/string theory, some theorem of mathematics or cure for a disease. links to some research papers might be helpful.


texts: NP-completeness of the Dominating set problem for planar graphs of maximum degree 3?

texts:
I am trying to learn about some techniques that are used for proving the NP-completeness of domination related problems. One of the problems that is known to be NP-complete is the domination number of planar graphs with maximum degree 3 (Garey and Johnson). Everybody in any paper and book, they refer to Garey and Johnson book, but there is no proof there, cause Garey and Johnson book refer to a reference at the end of the book which is unpublished.

Does any body know what is a proof for this problem, or any reference for it?

Thanks,
Elham


texts:
I've read in Lemma 2 of the paper 1 that if every square region of the plane admits a tiling, then the whole plain admits a tiling, but the proof is omitted.  This sounds like a compactness property, but I don't see how easy can be proven.

I added the tag "automata theory" because there is a correspondence between Wang tilings and finite state transducers.


texts: Generating a Diffie Hellman tuple without "being able to know" one of the discrete logs involved

texts:
Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, and including cases in which Decisional Diffie Hellman is easy) to generate tuples of the form $(g, g^a, g^b, g^{ab})$ without in a sense "knowing" either a or b?

More formally, if there is a polynomial-time Turing machine $T(G, c)$ such that $T$ maps any input into such a tuple in the group described by $G$ ($G$ could just be a modulus if this is a modular multiplicative group, and $c$ could be thought of as random bits), must there exist a polynomial-time $T'$ such that $T'$, with the same input as $T$, outputs $(g, g^a, g^b, g^{ab}, a)$ or $(g, g^a, g^b, g^{ab}, b)$?

Clearly, the answer to this question is not known since there is always such a $T'$ if discrete log is easy and there is is a $T$ without such a $T'$ if Diffie Hellman is easy and discrete log is hard.  I'm particular interested in whether there is some existence result that says there must be a $T$ with no such $T'$ (under an assumption like hardness of discrete log), or whether there is a general conjecture that such a $T'$ always exists (or better yet, that this is implied by some other, widely believed, conjecture).

For further context, I'm essentially curious about whether the assumption that such a $T'$ always exists would be considered reasonable in an analysis of a cryptographic protocol.

Now cross-posted on mathoverflow: https://mathoverflow.net/questions/76302/is-it-believed-to-be-possible-to-algorithmically-generate-diffie-hellman-tuples


texts: proving speedup phenomenon does not apply to any open complexity class separations

texts:
Aaronson recently wrote a blog refuting the idea that there could be some "glitch" in the formulation of the P vs NP conjecture[1] which reminds me of this following question.

the Blum speedup theorem has been characterized by Goldreich [3] (p149)

  A conceptually related phenomenon is of problems that have no
  optimal algorithm (not even in a very mild sense); that is, every algorithm for
  these "pathological" problems can be drastically sped-up. It follows that the
  complexity of these problems can not be defined (i.e., as the complexity of the best
  algorithm solving this problem).

in math, it is not unprecedented that major conjectures have been shown to have "glitches" eg discovery that they are independent of axiomatic systems, etc.
also Goldreich reference to "pathological" languages is reminscent of historical consternations in math eg the counterintuitive discovery of functions that are continuous but nowhere differentiable eg the Weierstrauss function.

another angle is that at least one complexity theorist expert Lipton speculates that program size is underanalyzed in TCS and may have surprising aspects,[2] and the Blum speedup theorem seems to fit in with this line of thinking, because the proof construction basically relies on improving the language recognition time based on increasing the size of the TM program (ie like a tradeoff).

so:

  how does one show/ prove that no such "pathological" languages are/can be involved in open complexity class separation questions eg P=?NP etc?

am interested in more technical/ mathematical perspectives that avoid handwaving. (eg something more detailed/ substantial than an assertion that the Blum speedup construction is "contrived" etc.)

[1] Is the P vs. NP problem ill-posed? (Answer: no.) Aaronson blog
[2] Does program size matter? RJLipton blog
[3] Computational complexity: a conceptual perspective / Goldreich


texts: What functions can read-once branching programs compute?

texts: Barrington's Theorem gives us that polynomial size and bounded width Branching programs can compute exactly functions in $NC_1$, are there any results known about read-once BPs - bounded width and polynomial size?


texts: Equivalence of deterministic finite transducers over finite/infinite words

texts:
Equivalence of deterministic finite transducers - a special case of single-valued finite transducers - is decidable because it is decidable whether a transducer is single-valued. Note that two deterministic finite transducers $T_1$, $T_2$ are equivalent iff $T_1 \cup T_2$ is single-valued and their domains are equivalent which reduces to a DFA equivalence check on $T_1$, $T_2$ without output.

Can you point to a reference of an efficient algorithm to decide equivalence of deterministic finite transducers over finite words?

I am also interested in a decision procedure for infinite words assuming that all states are final. The latter transducer variant is also known as generalized sequential machine (GSM). Equivalence is also decidable for GSMs.


texts: Is it possible to formalize the notion of 'semi-greediness'?

texts:
It is commonly accepted that matroids provide an abstract setting for which greedy optimization works (although there are more general structures known as 'greedoids').

I was wondering whether there had been attempts to formalize a notion of 'semi-greediness'. Intuitively, it means that we would still construct a solution iteratively, but going from a solution $S$ of cost $i$ to a solution $S'$ of cost $i+1$ would work differently: instead of having $S'$ of the form $S \cup \{x\}$, we could for example have $S'$ of the form $(S \Delta T) \cup \{x\}$ i.e. we would replace $r$ elements present in $S$ by $r+1$ elements exterior to $S$.

This could possibly model interesting problems such as bipartite maximum matching, optimizations in $\Delta$-matroids or 2-polymatroids.


texts: Does the Category of CPOs have omega^op limits?

texts:
In "Domains and Lambdi Calculi" by Amadio and Curien, in the section on solving recursive domain equations (section 7), they give sufficient conditions on a cpo-enriched category so that the category of embedding-projection pairs has $\omega$-colimits. Specifically they say it is sufficient for the category to have $\omega^{op}$-limits.

They then have a theorem that the category of CPOs has all $\omega^{op}$ limits, but the proof is incomplete and I don't see how it could be completed.

To be clear in their book the category CPO has as objects directed complete partial orders with a least element and as maps continuous (not neccesarily strict!) functions.

Their proof proceeds as follows. Given a diagram ${D_n,f_n}_{n\in\omega}$ ($f_n : D_{n+1} \to D_n)$, their proposed limit is
$$D = \{ \alpha : \Pi_{n\in\omega} D_n | \forall n, f_n(\alpha_{n+1}) = \alpha_{n} \}$$

with the pointwise ordering.
This is definitely the product of that diagram in DCPO, but I don't see why $D$ must have a least element. In particular, you can't pick $\alpha_n = \bot_n \in D_n$ since the functions $f_n$ are not assumed to be strict.

However, restricting to strict continuous functions is all they need anyway because embedding-projection pairs of CPOs are strict anyway (embedding because it's a left adjoint, projection because it's a retract of the embedding). However this doesn't seem quite right either because for example a right adjoint wouldn't necessarily have to be strict, so it seems less general.

So to summarize

Is there a way to prove $D$ is a CPO or a concrete counterexample?
If it's not, what is the right way to "fix" to their formula for solving recursive domain equations? Specifically, we do want to limit the construction to a category of CPOs since they have the bottom elements needed for recursive domain equations, but restricting to limits of strict functions seems stronger than necessary (though sufficient for my needs for now).

I know I could go back through Wand and Plotkin and Pitts and probably find the answers to (3) there, but it would be nice to have a succinct general construction like in their book chapter. Specifically I would like a reference that includes Pitt's minimal invariants work (otherwise Abramsky-Jung is probably sufficient).


texts: Long-Standing Conjectures later trivially proved by an implication

texts: I'd like to know if there have been conjectures that have long been unproven in TCS, that were later proven by an implication from another theorem, that may have been easier to prove.


texts:
Consider $S_1, ...,S_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S_i \cap S_j$ is empty or not. We would like to asnwer this in constant time. Under this setting, the conjecture is that any data structure that allows constant query time requires $\tilde{\Omega}(n^2)$ space.

This problem has very tight connection to distance oracles and range diameter queries. Work by Patrascu regarding distance oracle mentions that the $\tilde{\Omega}(n^2)$ bound is a folklore conjecture. Range diameter query work also gives good intuition about the lower bounds and conjectures that space requirement for supporting the above queries is quadratic in $n$ is required.

I am looking for additional results of this form for set intersection queries with multiple sets i.e what is the space requirement for answering queries of the form $S_i \cap S_j \cap S_k$. Are there any results for multi set query lower bounds? Or is it trivial to show bounds using the conjecture for $2$ set intersection queries. Any leads in this direction appreciated!


texts:
Given parameters $n,k\in \mathbb N^+$, I'm interested in finding a set of binary vectors $V_{n,k}=\{v_1,\ldots,v_n\}$ of length that satisfies:

$\forall i: v_i\in\{0,1\}^{z_{n,k}}$.
The bitwise xor of any subset of $V_{n,k}$ that consists up to $k$ elements is unique. That is, if $V_1,V_2\subseteq V_{n,k}$ and $|V_1|,|V_2|\le k$, then $V_1$ and $V_2$ have different bitwise xors.

What is the smallest $z_{n,k}$ that allows such a construction?

Can we give an explicit construction of such a set $V_{n,k}$?

It seems that using the probabilistic method, it's possible to get an upper bound on $z_{n,k}$. Can we do better?

For example, $\{0001, 0011, 0110, 1011, 1111\}$ is an optimal construction for $n=5,k=2$.


texts: All pair shortest path problem for large number of nodes

texts:
I am having a small problem. I have the complete city's data which has over 100,000 nodes and 40,000 paths in my database. Now I need to calculate the all pair shortest path between all of them.

Obviously running them all together will take a long long time to compute as the complexity being $\Theta(n^3)$. So what I have decided is that to divide all the nodes into 20 different circles. I will compute for each different circle and then merge all the table's using a small dynamic programming approach which has the complexity of $\Theta(n_1n_2)$

where $n_1$ i the number of nodes in 1st and $n_2$ in the 2nd circle. In my case $n_1$=$n_2$.

So this way I am running it in $O(n^3)$, but practically its much faster than before. Yet overall it still is taking a long long time to compute. Is there any better approach?
Or are there any better well known algorithms which can solve such problems faster?

Quite helpless


texts: Graph embedding which maximizes minimum angle

texts:
Given a planar graph, one can   embed it in linear time crossing free into an $n \times n$ grid.
I am interested whether any efficient algorithms are known to straight line embed a planar graph crossing free into a $n^c \times n^c$ grid, for some small $c$, such that the minimum angle between two edges is maximized?


texts: Tree search guided by a probabilistic oracle

texts:
I'm trying to find a solution for the following problem.

I have a tree $T$ of branching factor $b$ and depth $d$. For the moment, I only care about the case where I restrict $b=2$, but I would be interested in the general case as well.

I am looking for an element in $T$ guaranteed to be somewhere at depth $d$, but I can't directly compare with the nodes in $T$. Instead, I must consult a probabilistic oracle $O$. Given a set of nodes, $S=\{n_0,n_1,\dotsc\}$, the oracle $O$ gives me the correct subtree with some probability $p$, where $0 \le p \le 1$, and a random subtree from the set with probability $1-p$. Furthermore, the oracle always gives the same answer when comparing two nodes, even if that answer might be wrong.

Given $\{b,d,p\}$, what might b the most efficient search technique to find the desired element at depth $d$? The cases where $p = 0$ (random search, since the oracle provides no information) and $p = 1$ (the oracle is perfect - just follow the directions from the oracle) are straight-forward, so I'm interested in $0 < p < 1$.

My first thought was at each branch, consult the oracle with all frontier nodes seen thus far and choose the one the oracle rated as best as my current optim the cases where the oracle provides some information, but not perfect knowledge.um subtree, remove it from the list of frontier nodes, and examine its children to see if they match. I wasn't sure if this is optimal or not. Obviously, for $p = 1$ this algorithm is optimal, and reduces to a $b$-ary search, but for $p = 0$, I think it might spend more time opening up the frontier than checking nodes at depth $d$.

edit: I've updated the oracle's probabilities to be more correct in the behavior where it is truly random and provides no information content.

update: To clarify the desired problem soluion, what I am looking for is an algorithm for, say $p = 0.5$ where I can locate a desired element a known depth $d$ with a greater than $0.5$ probability by examining as few nodes as possible. For now, the running time of the oracle isn't that important compared to exploring the tree, but I believe the oracle gives me a solution in $O(m)$ where $m$ is the size of the set given to the oracle.


texts: Is every countable, finite-branching LTS bisimilar to a tree?

texts:
Let $L$ be a finite set of labels, and let $\mathcal{C}$ be the set of finitely-branching transition systems labeled by $L$ and with a countable set of states.  Let $\sim$ denote the bisimulation relation, and let $\mathcal{C} / \sim$ denote the set of bisimulation equivalence classes of LTS's in $\mathcal{C}$.

Q1:  Does every bisimilarity equivalence class $\alpha \in \mathcal{C} / \sim$ have a tree model?

Let $L\mu$ denote the set of closed formulas in modal $\mu$-calculus.

Q2:  True or false:  $\forall \alpha \in \mathcal{C} / \sim$, $\exists F \in L\mu$ such that models$(F) \cap \mathcal{C} = \alpha$.  Or in plain English, every bisimilarity class of countable and finitely-branching LTS's over $L$ is exactly the set of countable and finitely-branching models of some modal $\mu$-calculus formula.

An answer to either would be helpful, and answers to both would be sublime :)


texts:
It is well known that general satisfiability (of polynomially many clauses) is NP-hard, and in fact, it is conjectured that an algorithm deciding instances of SAT takes time nearly $2^n$ on $n$ variables.

I was wondering what, if anything, is known about the hardness of promise variants of the problem, GAP-SAT. Here the promise is that each such Boolean formula $\phi$ is guaranteed to lie in the union of

$$\Pi_{no} = \{\phi: |\{x:\phi(x) = 1 \}| \leq a\} $$
and
$$ \Pi_{yes} = \{\phi: |\{x:\phi(x) = 1 \}| \geq b\}$$

for different $0 \leq a = f(n) < b = g(n) \leq 2^n$ fixed functions of $n$. Any references would be appreciated, thanks!


texts: To what extent MSO = WS1S, when adding relations?

texts:
[This question has been asked on MathOverflow with no luck a month ago.]

Let me first clarify my definitions.  For a word $w \in \Sigma^*$, with $\Sigma =\{a_1,
\ldots, a_n\}$, I define two structures:

$\mathbb{N}(w) = \langle \mathbb{N}, <, Q_{a_1}, \ldots, Q_{a_n} \rangle$,

and the more usual word model:

$\mathbb{N}^r(w) = \langle \{0, \ldots, |w|-1\}, <, Q_{a_1}, \ldots, Q_{a_n} \rangle$,

where $Q_{a_i} = \{p \mid w_p = a_i\}$.

Then WS1S is the set of second order formulas with models of the form
$\mathbb{N}(w)$, with order, and for which second order quantification is
limited to finite subsets of the domain.  MSO is the set of second order
formulas with models of the form $\mathbb{N}^r(w)$, with order.

The usual proof that REG = WS1S proves at the same time that MSO = WS1S.  My
question is then, for which first or second order relations can we keep this
to be true?

For instance, if we add a unary predicate $E(X)$ which says that a
(monadic) second order variable contains an even number of objects, we add no
power, as $E(X)$ is expressible as "there exists $X_1$ and
$X_2$ that partition $X$, in such a way that if an element is in
$X_i$ the next one in $X$ is in $X_j$, $i \neq j$, and
the first element of $X$ is in $X_1$ and the last is in
$X_2$."

Now, if we add a predicate $|X| < |Y|$, then WS1S becomes undecidable
(see Klaedtke & Ruess, 10.1.1.7.3029), while MSO stays trivially decidable.

Thank you.

Edit: As a side question, ... is this question of interest?  I mean, I'm no expert in the field, so I'm not sure this question is relevant.


texts:
I am interested to study Graph Isomorphism (GI) complete problems.

In the Paper " Problems Polynomially Equivalent to Graph Isomorphism" by Kellogg S. Booth, (1979), proved that many basic problems are GI complete by using Edge replacement techniques, Composition techniques etc.

I would like to learn some more techniques which are used in recent papers.

Can some one suggest me some recent papers which are more concentrated in proving some graph class is GI complete.


texts: What are the prospects of research in database field?

texts:
I have been working with database management systems, and would like to focus on research in this very area some day.

I was having a look at the various research labs around the world,

http://www-07.ibm.com/in/research/
http://research.microsoft.com
http://research.google.com/

but did not find any dedicated Database research groups, or any exciting activity in this area.

How do the research prospects in the Database field look like?


texts: Minimum weights needed to derandomize weight assignment by isolation lemma

texts:
Under isolation lemma if you have a graph with $2n$ vertices and $m$ edges an isolating weight assignment can be obtained by assigning edges weights randomly from $\{1,2,\dots,2m-1,2m\}$. A weight assignment is isolating if there is an unique perfect matching with minimum sum weight.

Is $\Omega(m)$ weight necessary or would it be possible that there is a (deterministic) scheme that can get the job done in $O(\sqrt m)$?

Note that the best weights we know uses $O(2^m)$.


texts:
The question is:  can exist a parallel or serial neural network or someone talked about this?
For explanation, in the network a single record in a data set enter in the input layer as a value between 0 and 1, but, could i interpretate the value parallely as an array of bits (so i need an input layer as large as the number of bits composing the value) or even serially? or this is a bad technic?

Imagine a number (es. 5) that is interpretated as an n-bits values (101) in a 3-way input layer instead of a degree (0,?) in a 1-way input layer.

I'm a novice in neural network and the question could be stupid. Sorry if it is.


texts: Complexity of a problem over acyclic context-free grammars

texts:
Let $G$ be an acyclic, context-free grammar over a fixed alphabet $\Sigma=\{a_1,\dots,a_k\}$ with the restriction (without loss of generality) that $|w|=2$ for each rule $A\to w$ in the grammar. Acyclic means that if $N$ is the set of nonterminals, then
$$\{(A,B)\in N^2\mid A\to xBy\text{ is a rule in }G\text{; }x,y\in(\Sigma\cup N)^*\}$$
is an acyclic relation. So $L(G)$ is finite. Let in this setting the size of a grammar be defined as the number of nonterminals
My question
Let $\#_w(i,j)$ be the number of different subsequences of $a_ia_j$ in $w$. For example $w=a_1a_1a_2a_2a_1$ yields $\#_w(1,2)=4$, $\#_w(2,1)=2$, $\#_w(1,1)=3$ and $\#_w(2,2)=1$. Now I am looking for the complexity of:

Given: Acyclic, context-free grammar $G$ and numbers $n_{i,j}$ with $i,j\in\{1,\cdots,k\}$
Problem: Is there a word $w\in L(G)$ with $\#_w(i,j)=n_{i,j}$ for all $i,j\in\{1,\cdots,k\}$ ?

Background / Well-studied, related problem
The following problem is one step behind my question. In my question, the number of occurences of all subsequences of length $2$ are given. We could first ask, what is the complexity, if the given numbers are the occurences of subsequences of length $1$, i.e. the given numbers are the occurences of the alphabet symbols. So, let $\#_w(i)$ denote the number of occurences of $a_i$ in $w\in\Sigma^*$. The following problem is known to be $\mathsf{NP-complete}$:
Given: Acyclic, context-free grammar $G$ and numbers $n_1,\dots ,n_k$
Problem: Is there a word $w\in L(G)$ with $\#_w(i)=n_i$ for all $i\in\{1,\cdots,k\}$ ?
McKenzie and Wagner ("THE COMPLEXITY OF MEMBERSHIP PROBLEMS FOR CIRCUITS OVER SETS OF NATURAL NUMBERS") provide an $\mathsf{NP}$ algorithm to solve the membership problem of circuits over the natural numbers with $\cup$ and $+$. A slightly modified algorithm solves our problem. The algorithm in short: In addition to the given numbers, we guess for each nonterminal how often it occurs in a derivation tree and for each rule how often it is applied in a derivation tree. Afterwards, we check whether there is a derivation tree of $G$ satisfying the guessed numbers by checking some relations between those numbers. The problem should also be $\mathsf{NP-hard}$, e.g. as a conclusion of Kopczyński and Widjaja To ("Complexity of Problems for Parikh Images of Automata").
Still $\mathsf{NP}$ ?
Is the problem for subsequences of length $2$ still solvable in $\mathsf{NP}$ ? Of course it is at least as hard as the related problem for subsequences of length $1$, because
$$\#_w(i,i)=\frac {\#_w(i)\cdot(\#_w(i)-1)}{2}.$$
Unfortunately, I am neither able to extend the algorithm of McKenzie and Wagner to get an $\mathsf{NP}$ algorithm, nor can I show another hardness result like $\mathsf{coNP}$ hardness.
Thanks for any help.


texts:
I've been struggling with understanding of the proofs showing that implementation statements are extensional.

Basically I am referring to material described in Abstraction Classes in Software Design paper.

As an example, let us take the following proof for class diagram Figure 13:

  Proposition 11. The class diagram in Figure 13 is extensional.

  Proof: Let us show that Figure 13 is preserved under expansion. Let M designate a structure that satisfies Figure 13. Any such structure shall include,
  among others, the following entities and relations:

  Class entities, such as Creator and ConcreteCreator, as well as
  Method entities, such as Creator::FactoryMethod and
  ConcreteCreator::FactoryMethod.
  The binary relation Member, which associates every method with one
  class, such as the pair (Creator::FactoryMethod, Creator)
  The binary relation Inherit, which includes the pairs
  (ConcreteCreator, Creator) and (ConcreteProduct, Product)

  Additional information in Figure 13 is represented informally. For
  example, the  relation Invoke(AnOperation,FactoryMethod) is
  represented by the note product=FactoryMethod() at the top right
  corner of the diagram.

  Note that every element in the diagram
  explicitly represents a specific entity (e.g., class Creator) or a
  specific relation (e.g., Inherit(ConcreteCreator, Creator)). Thus,
  expanding M with any number of Class entities cannot violate Figure
  13.

  Let us show that Figure 13 is preserved under reduction. There are two types of entities that can be removed from M:

  Entities that are explicitly mentioned in Figure 13.
  Entities that are not explicitly mentioned in Figure 13.

  By the Intension criterion, we
  only consider reductions removing entities  that are not explicitly
  mentioned in Figure 13 from the universe of M. Obviously, any such
  reduction will continue to satisfy Figure 13.

My specific question is about preserving Figure 13 under reduction. How can we remove entities that are not explicitly mentioned in Figure 13? What are these entities that are not explicitly mentioned in Figure 13? Just don't get how can we remove something that is not present on the diagram.


texts: Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs

texts:
Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ancestors of every vertex in $V'$ in $O(|V'|A + m)$ time? In other words, I want sets $B_i$ consisting of all ancestors of $v_i \in V'$ for all $v_i$.
The trivial algorithm does this in $O(|V'|A^2)$ time (for very dense graphs) but I would like to do this in $O(|V'|A + m)$ time or even better $O(|V'|A + E(V', B(V')))$. (Here $E(V', B(V'))$ indicates time proportional to the induced subgraph consisting of $V'$ and all ancestors of vertices in $V'$.)
If we cannot do this, are there any known lower bounds for this runtime?


texts:
Let $F$ be a large finite field, where the elements are strings of length $n$. We require, addition, multiplication, and division to be efficient (polynomial in $n$).

We say that $F$ is searchable if for any $u \in F$ and string $x$, we can find efficiently find a string $s \in F$ such that

$x$ is a substring of $s \cdot u$
The number of lexicographically earlier strings $s' \in F$ with this property is $\mathcal o(n)$

We say that $F$ is regex-searchable if instead of requiring $x$ to be a substring of $s \cdot u$, we require $s \cdot u$ to satisfy the $x$ when interpreted as a regular expression.

For any $n$, can find a searchable field with strings of length $>n$? What about a regex-searchable field?


texts:
What is the relationship between the expressiveness of LTL, Büchi/QPTL, CTL and CTL*?

Can you give some references that cover as many of these temporal logics as possible (especially between linear- and branching-time)?

A Venn diagram with those temporal logics and some practical properties as examples would be perfect.

For instance:

Is it true that there are properties specifiable in Büchi but not in CTL*? Do you have a good example?
How about in Büchi and CTL but not in LTL?

Details:

The expressiveness of the logics is more relevant for me than the examples. The latter is just helpful for understanding and motivation.

I already know of the expressibility theorem between CTL* and LTL from [Clarke and Draghicescu, 1988], but do not like the usual example of fairness being in CTL and not in LTL since there are a plethora of fairness variants, some of which are expressible in LTL.

I also do not like the usual example of the evenness Büchi-property, given, e.g., in [Wolper83] about the restrictions of LTL, since adding another propositional variable would solve the problem ($even(p) \equiv q \wedge \Box ( q \implies X \neg q ) \wedge \Box ( \neg q \implies X q ) \wedge \Box ( q \implies p )$).

I do like the example of the evenness Büchi-property, given, e.g., in [Wolper83] about the restrictions of LTL, since it is simple and shows the necessity of PQTL for evenness (thanks for the note below).

Update:

I think the expressibility theorem between CTL* and LTL from [Clarke and Draghicescu, 1988] can be lifted to Büchi automata, resulting in:

Let $\phi$ be a CTL* state formula.
Then $\phi$ is expressible via Büchi automaton
         iff $\phi$ is equivalent to $A\phi^d$.

With this, Büchi $\cap$ CTL* = LTL, answering my questions above:

Is it true that there are properties specifiable in Büchi but not in CTL*? Yes, e.g. evenness.
How about in Büchi and CTL but not in LTL? No.

Has anyone lifted Clarke and Draghicescu's theorem already to Büchi automata, or stated a similar theorem? Or is this too trivial to be mentioned in a paper, since CTL*'s path quantifiers are obviously "orthogonal" to the criteria on accepted paths states by Büchi automata?


texts: Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?

texts:
Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi.

In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have countably many quantum Turing machine.

Is this choice of angle arbitrary?


texts: Deciding transitivity of a directed acyclic graph

texts: Is there any algorithm that decides whether a given directed acyclic graph is transitive or not, in time-complexity asymptotically better than boolean matrix multiplication?


texts: Has this formulation of pursuit evasion been researched? Similar to Helicopter Cops and Robbers Game

texts:
There are pursuers and evaders in the vertices of a directed graph G with one component.  Each vertex must have atleast one outgoing edge (can be a loop).

At each time t:

The evaders must move along an edge to another vertex (may use loop)
Each pursuer must check one vertex (it can be any vertex in G).

A vertex is considered contaminated at time t if an evader can be there without having been caught by the pursuers. A vertex v is decontaminated at time t if:

A pursuer is checking v.
All edges to v originate from vertices which were decontaminated at time t-1.

At time t=0 all vertices are contaminated. The goal is that all vertices are decontaminated. This translates to the evaders being guaranteed to be caught.
A search strategy for k pursuers is a sequence of k-tuples referencing k vertices i.e. "check these k vertices at time t=0, then these k vertices at time t=1" and so on.

What is the minimum amount of pursuers needed to decontaminate all vertices in G?

What is the optimal (shortest sequence) search strategy given a graph G and k pursuers?

So, where can I find this problem definition or an equal one? Is this problem NP-complete and if it is, how can that be shown?


texts: Fast convolution over small finite fields

texts:
What are the best known methods for cyclic convolution of length $n$ over a small field, i.e. when $|\mathbb{F}| \ll n$?  I'm particularly interested in constant-sized fields, or even $\mathbb{F} = \mathbb{F}_2$.  General asymptotic-efficiency statements and references are much appreciated.

Background:  Let $\mathbb{F}$ be a field, and $n > 0$.  We think of vectors $u \in \mathbb{F}^n$ as having coordinates indexed by $\mathbb{Z}_n$.

The (cyclic) convolution of length $n$ over $\mathbb{F}$ is the transformation taking $u, v \in \mathbb{F}^n$ and outputting $u * v \in \mathbb{F}^n$, defined by
$$
(u * v)_i :=  \sum_{j \in \mathbb{Z}_n} v_j u_{i - j},
$$
with index arithmetic over $\mathbb{Z}_n$.

To perform cyclic convolution over large fields, a popular method is to use the Convolution Theorem to reduce our problem to performing Discrete Fourier Transforms (DFTs), and using an FFT algorithm.

For small finite fields, the DFT is undefined because there's no primitive $n$-th root of unity.  One can get around this by embedding$^*$ the problem in a larger finite field, but it's not clear that this is the best way to proceed.  Even if we take this route, it'd be nice to know if someone has already worked out the details (for example, choosing which larger field to use and which FFT algorithm to apply).

Added:

$^*$ By 'embedding' our convolution in, I mean one of two things.  First option: one could pass to an extension field in which the desired primitive roots of unity are adjoined, and do the convolution there.

Second option: if our starting field is cyclic, one could pass to a cyclic field $\mathbb{F}_{p'}$ of larger characteristic--large enough that if we consider our vectors as lying in $\mathbb{F}_{p'}$, no "wraparound" occurs.
(I'm being informal, but just think about how, to compute a convolution over $\mathbb{F}_2$, we can clearly just do the same convolution over $\mathbb{Z}$, and then take the answers mod 2.)

Also added:

Many algorithms for FFT and related problems work especially well for 'nice' values of $n$ (and I would like to understand the situation with this better).

But if one doesn't attempt to take advantage of special values of $n$, the cyclic convolution problem is basically equivalent (by easy reductions involving linear blow-up in $n$) to ordinary convolution; this in turn is equivalent to multiplication of polynomials with coefficients over $\mathbb{F}_p$.

By this equivalence, one can use results in, e.g., this paper of von zur Gathen and Gerhard (building on work of Cantor), who use an extension-field approach to get a circuit complexity bound of $\tilde{O}_p(n)$.  They don't state their bounds in an especially clear way IMO, but the bound is worse than $n \cdot \log^2 n$ even for $\mathbb{F}_2$.  Can one do better?


texts:
Is anyone aware of a max flow algorithm where the edges are conditioned upon one another?

Meaning if I send f units of flow from vertex a --> b, then I have to send .5*f* unit from a --> c.


texts: Variance of bounded functions with rapidly decaying Fourier coefficients

texts:
I have the following conjecture about bounded functions on the hypercube. Any help resolving it (proof, counterexample, some ideas) is much appreciated.

Conjecture. Let $f : \{ -1, +1 \}^n \to [-1, +1]$ and $p \in [0,1/2]$. Suppose $\left| \widehat{f}(S) \right| \leq p^{|S|+1}$ for all $S \subseteq [n]$. Then $\mathrm{Var}\left[ f \right] \leq p^{\Omega(1)}$.

Here $f(x) = \sum_{S \subseteq [n]} \widehat{f}(S) \prod_{i \in S} x_i$ for all $x \in \{ \pm 1\}^n$ defines the usual Fourier transform. It's clear that $$\mathrm{Var}\left[ f \right] = \sum_{S \ne \emptyset} \widehat{f}(S)^2 \leq \sum_S p^{2|S|+2} = p^2 (1+p^2)^n,$$ but, unless $p \leq \tilde{O}(1/\sqrt{n})$, this is worse than the trivial $\mathrm{Var}\left[ f \right] \leq 1$. I'm interested in $p = (1/\log n)^{O(1)}$. I don't know exactly what the right bound on the variance of $f$ should be.

My motivation comes from the area of pseudorandomness, but this seems to be an interesting question about discrete Fourier analysis in its own right. In particular, this seems related to the majority is stablest theorem: Suppose $f = T_p(g)$ for some balanced $g : \{\pm 1\}^n \to \{\pm 1\}$ with $\mathrm{Inf}_i(g) \leq p^2$ for all $i$, where $T_p$ is the noise operator. Then $f$ satisfies the hypotheses of the conjecture and the variance of $f$ is the noise stability of $g$, which is bounded by $O(p)$ as a consequence of majority is stablest.


texts: What is the most Accurate way of Determining an Object's Color?

texts:
I have written a computer program that can detect coins in a static image (.jpeg, .png, etc.) using some standard techniques for computer vision (Gaussian Blur, thresholding, Hough-Transform etc.). Using the ratios of the coins picked up from a given image, I can establish with good certainty which coins are which. However, I wish to add to my confidence levels and also determine if a coin that I deduce to be of type-A (from radius ratios) is also of the correct colo[u]r. The problem is that for British coins et al. (copper, silver, gold), the respective colors (esp. of copper to gold) are very similar.

I have a routine that extracts the mean color of a given coin in terms of the RedGreenBlue (RGB) 'color-space' and routines to convert this color into HueSaturationBrightness (HSB or HSV) 'color-space'.

RGB is not very nice to work with in attempting to differentiating between the three coin colors (see attached [basic] image for an example). I have the following ranges and typical values for the colours of the different coin types:

Note: the typical value here is one selected using a 'pixel-wise' mean of a real image.

Copper RGB/HSB: typicalRGB = (153, 117, 89)/(26, 0.42, 0.60).

Silver RGB: typicalRGB = (174, 176, 180)/(220, 0.03, 0.71).

Gold RGB: typicalRGB = (220, 205, 160)/(45, 0.27, 0.86)

I first tried to use the 'Euclidian distance' between a given mean coin color (using RGB) and the typical values for each coin type given above treating the RGB values as a vector; for copper we would have:

$$D_{copper} = \sqrt((R_{type} - R_{copper})^{2} + (G_{type} - G_{copper})^{2} + (B_{type} - B_{copper})^{2})$$

where the smallest value of the difference ($D$) would tell us which type the given coin is most likely to be. This method has shown itself to be very inaccurate.

I have also tried just comparing the hue of the coins with the typical values of the types provided above. Although theoretically this provides a much better 'color-space' to deal with varying brightness and saturation levels of the images, it too was not accurate enough.

Question: What is the best method to determine a coins type based on color (from a static image)?

Thanks very much for your time.


texts: Elementary bounds on parameter in fixed-parameter tractability?

texts:
In the definition of (strong) fixed-parameter tractability, the time bound is an expression of the form $$f(k).p(|x|),$$ where the input instance is $(x,k)$ with parameter $k$, $p$ is a polynomial, and $f$ is a computable function.

It is possible to replace the computability requirement for $f$ with other classes of functions, as long as the notion of reduction is similarly restricted.  (For instance, Flum and Grohe cover exponential and subexponential families in chapters 15–16 of their textbook, with the associated erf and serf reductions.)

  Has anyone studied the family of elementary functions for the parameter bound $f$?

An elementary function can be bounded above by a fixed tower of exponentials, so this class is closed under composition.  The growth in the parameter in a reduction must then be bounded above by an elementary function as well.

There do exist interesting problems from automata theory which are fixed-parameter tractable, but where the parameter bound is non-elementary (unless P = NP, see Frick and Grohe, doi: 10.1016/j.apal.2004.01.007).  I am wondering if anyone has looked at the fixed-parameter tractable problems which exclude fixed values of the parameter leading to such "galactic" constants (to use Richard Lipton and Ken Regan's term).  Speculating wildly, such a restriction might have useful connections with finite model theory, such as being characterized by a fragment of monadic second-order logic that doesn't lead to the non-elementary constants that can arise from applying Courcelle's Theorem to a fragment with unbounded quantifier alternation.


texts: What logic do refinement types correspond to?

texts:
I'm interested in applicability of refinement types to theorem-proving hence the questions about their logical expressiveness. Let's say, we have a type system which corresponds to some logic according to Curry-Howard isomorphism.

How is the expressiveness of the logic affected by refining the system with predicates? If refinement predicates can belong to a different logic than that of the underlying system, what influence may it have on the original logic?
How is the choice of the logic for refinement predicates motivated in real systems such as LiquidHaskell?
How close can we get to higher order logic with refinement types?


texts:
I'm reading Ankur Moitra's excellent lectures notes at http://people.csail.mit.edu/moitra/docs/bookex.pdf .

In Chapter4, the notes claim that a certain circulant matrix of fourier coefficients is invertible [left as exercise to reader, and I can't find the footnote]. I can not prove it. I'm also not convinced it's true. The pages are attached. Any pointers as to what I should read up on would be helpful.

Thanks!

EDIT: Images are high resolution. Click "open image in new tab".


texts:
I'm looking to calculate the approximate intersection (proximity under a certain distance) of two sets of points in a discrete metric space. In other words, given a metric space $(M, d)$, subsets $A, B \subseteq M$, and maximum distance $k$, find $A' \subseteq A, B' \subseteq B$ where $A' = \{ x \in A | (\exists y \in B)[ d(x,y) \le k ]  \} $, and same for $B'$.

One obvious way to do this is to put one set in a BK-tree, then simply iterate through each point in the second set and look up its neighbors in the first set's BK-tree. However, this becomes slow (and, I suspect, wasteful) when both sets are large.

Is there a faster way (such as calculating the intersection of two BK-trees directly)?


texts: Collatz Conjecture & Grammars / Automata

texts: I was wondering if there is a good bibliography of attempts to investigate the Collatz conjecture as a formal grammar?  (or any other attempts in the CS community to deal with this class of generative phenomena & their "halting" properties).


texts: Does anybody know a NP-hardness proof of Weapon-target assignment problem (http://en.wikipedia.org/wiki/Weapon_target_assignment_problem)? Lloyd and Witsenhausen produced a reduction from 3-EXACT-COVER, but it seems that there is no chance to get their paper titled "Weapons allocation is NP-complete".


texts: Does a weighted graph have a path with weight zero?

texts:
Given a weighted digraph $G=(V,E)$, where each edge is associated with a weight (could be positive, negative, or zero). We define the weight of a path to be the sum of the weights along this path.

The question: given two vertices $s,t$, decide whether there is a (not necessarily simple) path from $s$ to $t$ such that the weight of the path is 0.

It is not very difficult to see that this problem is in NP. I am wondering whether there is a polynomial time algorithm, or it is NP-hard.


texts: Has compressed sensing been generalized to convex optimization problems?

texts:
Has the theory of "compressed sensing" been generalized to any classes of convex optimization problems? I need to analyze a problem of the type
$$\min ||x||_0, ~~~~ \mbox{ subject to } ~~~g(x) \leq 0$$ where $g(x)$ is some convex function and the $0$-norm counts the number of nonzero entries of the vector. A natural approach is to instead solve
$$\min ||x||_1, ~~~~ \mbox{ subject to } ~~~g(x) \leq 0$$ which is now a convex problem. The theory of compressed sensing consider the case when the constraint is of the form $Ax = b$, and identifies conditions on the matrix $A$ which often hold and which force the solution of the two problems to coincide. Has anyone studied cases of general convex (possibly nonlinear) constraints? That is, are there papers studying nonlinear convex constraints, and identifying conditions on them which hold often or generically, such that the solutions of the above two problems are the same?

In my case, the constraint $g(x) \leq 0$ happens to be an SDP constraint  $A(x) \succeq 0$ where $A(x)$ is a symmetric matrix whose entries depend linearly on the vector $x$, and I'm especially interested in this case.


texts: Why does this cut elimination procedure terminate (contraction case)?

texts:
In Melliès’ survey Categorical Semantics of Linear Logic, a cut elimination procedure for intuitionistic linear logic is given which includes the following case:

3.9.3 Promotion vs. contraction
The proof
$$
\displaystyle\frac{
\displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion}
\qquad
\displaystyle\frac{\displaystyle\frac{\pi_2\\\vdots}{\Upsilon_1 , !A , !A , \Upsilon_2 \vdash B}}{\Upsilon_1 , !A , \Upsilon_2 \vdash B} \text{ Contraction}
}{
\Upsilon_1 , !\Gamma , \Upsilon_2 \vdash B
} \text{ Cut}
$$
is transformed into the proof
$$
\displaystyle\frac{
\displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion}
\qquad
\displaystyle\frac{
\displaystyle\frac{\displaystyle\frac{\pi_1\\\vdots}{!\Gamma \vdash A}}{!\Gamma \vdash !A} \text{ Promotion}
\qquad
\displaystyle\frac{\pi_2\\\vdots}{\Upsilon_1 , !A , !A , \Upsilon_2 \vdash B}
}{
\Upsilon_1 , !A , !\Gamma , \Upsilon_2 \vdash B
} \text{ Cut}
}{
\displaystyle\frac{\Upsilon_1 , !\Gamma , !\Gamma , \Upsilon_2 \vdash B}{\Upsilon_1 , !\Gamma , \Upsilon_2 \vdash B} \rlap{\;\text{ Series of Contractions and Exchanges}}
} \text{ Cut}
$$

Why is this a valid inductive step? Neither the size of the cut formula nor the sizes of the derivations are decreasing. (In the transformed proof, the right branch of the lower cut is potentially larger after inductively eliminating the upper cut.) So it's not clear why this procedure should terminate.


texts: Understanding bounded-diameter decomposition of graphs for PTAS

texts:
While trying to understand Baker's approach (also explained in this article by Eppstein) to designing PTAS's for planar graphs, I came across a difficulty.

The idea is, given an integer $k$, decompose the graph into subgraphs of tree-width bounded by $O(k)$ (which for planar graphs happens if $diameter = O(k)$), then solve the problem on the subgraphs in polynomial-time, and finally glue the solutions together to get a polynomial-time $(1 + O(1/k))$-approx.

The decomposition method described in the part $8$ of the article, amounts to, as far as I understood, pick any vertex, get a BFS tree from that vertex, and remove every $k$-th level of the tree (potentially starting at level $0 \leq i < k$, but I do not think it matters for this part).

The author then argues that the obtained subgraphs (consisting each of at most $k-1$ levels of the BFS tree), have bounded diameter (i.e. depending only on $k$).

This is the part I do not understand. For instance, what happens if some layer of the tree is a long path ? How is the diameter of a subgraph containing this layer bounded ?

Thank you for any help,

Lucas


texts: Geometric / Visual explanation that the average height of a random binary tree of given size $n$ is asymptotically $2\sqrt{\pi n}$

texts:
I just finished reading the proof that the average height of a random binary of given size $n$ is asymptotically $2\sqrt{\pi n}$.

I'm now searching for an intuitive, or geometric, or visual proof of this asymptotic equivalence. In other words, I'm trying to find an intuitive arguments that shows that this number grows like $\sqrt{n}$.

Any ideas?
Thanks!

Note: This is a duplicate of https://math.stackexchange.com/questions/16457 , but I couldn't find how to move it to this website. Sorry!


texts: reset and shift only one level deep (delimited continuations)?

texts:
I'm looking at the following tutorial on delimited (or composable) continuations:

http://community.schemewiki.org/?composable-continuations-tutorial

The author(s) propose the following "rewrite rule"

 (reset (...A... (shift K E) ...B...))
 ; -->
 (let ((K (lambda (x) (reset (...A... x ...B...)))))
   (reset E))

 (reset E)
 ; -->
 E

This is vastly smaller than anything else I've been able to find on delimited continuations, and doesn't rely on Haskell's Cont monad or on Scheme's call/cc and unique macro system. Therefore, it looks like I can implement this myself to play with outside of Haskell or Scheme / Racket, and that would be grand (see my Mathematica version below).  Problem is that I don't think it's right.

If I fire up Racket, do (require racket/control) and then

(reset (+ 1 (shift k (k 42)))  ~~>  43

as expected and as consistent with the above.  If I do

(reset (+ 1 (* 2 (shift k (k 42)))))  ~~>  85

this looks right, but doesn't match the prescription above.  That prescription, if I read it correctly, should lead to the second rewrite rule and just produce (+ 1 (* 2 (shift k (k 42)))) because it can't "see" the shift at the second level, "inside" the (* 2 (shift ...)) subexpression.

My straight transcription into Mathematica confirms this behavior,

reset[h_[As___, shift[k_, E_], Bs___]] :=
  Block[{K = Function[x, reset[h[As, x, Bs]]]},
   reset[E /. {k -> K}]]
reset[E_] := E

One level deep (like almost all the concrete examples I've found in papers! so the wiki authors are exonerated), and everything is fine:

reset[1 + shift[k, k[42]]] ~~>
reset[Plus[1, shift[k, k[42]]]] ~~>
(* h -> Plus, As -> {1}, E -> k[42], Bs -> {} *)
reset[Plus[1, 42]] ~~>
43

But then I try this:

reset[1 + (2 * shift[k, k[42]])] ~~>
reset[Plus[1, Times[2, shift[k, k[42]]]]] ~~>
1 + (2 * shift[k, k[42]])

This fires the second, transparent rewrite rule because shift is too far down; the first pattern h[As___, shift[k_, E_], Bs___] can't see it -- it's inside Bs, which matches the second-level AST Times[2, shift[...]].

So the final question is:

Can I just patch the rewrite rule above, perhaps like this:

 (reset (...A... (shift K E) ...B...))
 ; -->
 (let ((K (lambda (x) (reset ( (reset ...A...) x (reset ...B...))))))
   (reset E))

 (reset E)
 ; -->
 E

or am I doomed to take the long, scenic tour through vast landscapes of Haskell and OchaCaml and call/cc and denotational semantics just so I can create a small, but correct, toy implementation?


texts: A promise problem to decide whether two given pure quantum states are close or far apart

texts:
Consider this problem in quantum cryptography:

We have two pure states $\phi_1,\phi_2$ as input and constants $0 \leq \alpha <\beta \leq 1 $, where "Yes instances" are those for which $$\left|\left<\phi_1,\phi_2\right>\right| \leq \alpha$$ and "No instances" are those for which $$\left|\left<\phi_1,\phi_2\right>\right|\geq \beta$$

I need to devise a quantum circuit that accepts "Yes instances" with probability at least $p$, and "No instances" with at most probability $q$ for some $q<p$.

How can I do this? Is there a reference in which this problem is solved?

Thanks in advance.


texts: Can the rendezvous problem be solved without exploration in synchronous rings?

texts:
Problem Definitions:
Rendezvous: A number of agents, in this case two, that start from distinct nodes of a ring need to meet in some node that is not known in advance.
(Collaborative) Exploration: A team of agents (say again two) need to visit each node of a ring within finite time. Each nodes needs to be visited by at least one agent.
I do not specify communication methods between agents, knowledge of initial distance, knowledge of the size of the ring and memory becasue I am interested in finding an answer for any scenario.
I have been reading this book that (among other things) gives lower bounds for the time needed for agents to rendezvous under various assumptions and after most time bounds an algorithm that satisfies these asumptions is given. The given algorithms also explore the ring but it is not stated if exploration is necessary or just convenient. Intuitively, I would expect that at least in the cases where the agents do not have much information about the network (such as initial distance to each other or knowledge of size) the ring will need to be explored, but I haven't been able to find a proof of that.
One (easy) result that I have been able to find is that if each node has a numerical ID and the agents have enough memory to read the label then rendezvous is reduced to exploration (e.g., by having the agents check all IDs and then move to the node with the smallest one). However, I am more interested in the necessity (or lack of necessity) of exploration for solving rendezvous and not of a reduction.
Are there any more general known results that connect collaborative exploration to rendezvous in a deterministic context?


texts: Computing 3D viewpoint of a set of non-intersecting segments

texts:
Consider the following problem: we are given a finite set of bounded line-segments in ${\mathbb R}^3$, and we want to decide whether there exists a point $p\in {\mathbb R}^3$ from which no two segments obscure one another.

Can this be done efficiently?

Problem statement:

More precisely and formally: we are given $n$ line segments $\ell_1,\ldots,\ell_n$, where each segment is defined as $\ell_i=\{tu_i+(1-t) v_i: t\in [0,1]\}$ with $u_i,v_i\in {\mathbb Q}^3$ (we assume rational coordinates).

We wish to decide whether there exists a point $p\in {\mathbb R}^3$ such the lines connecting $p$ with each point on the lines are distinct, and if so, compute it.

Is there an efficient solution? Is there a hardness lower bound?

UPDATE: Given the lack of answers so far, what about the case where the line segments connect two adjacent point in a 3D $k\times k\times k$ grid ? Then, they are all parallel to some axis, they are all of length 1, etc. Does this make it significantly easier?

Inefficient solution:

Observe that for each pair of lines $\ell_1,\ell_2$, the points from which the lines do obscure each other can be described as a polyhedron defined as the intersection of 4 half-spaces: for every 3 points in {u_1,v_1,u_2,v_2}, the hyperplane defined by them is a boundary such that on one side of it, the lines do not obscure each other.

Thus, we can represent the set of "bad points" (those from which at least one pair obscure each other) as a union of $n^2$ polyhedra (not necessarily disjoint). Then, all we need is to test it's complement for emptiness. This can be done e.g. using Fourier-Motzkin quantifier elimination, whose complexity is quite bad. On top of this, we first need to convert a CNF representation to DNF, which may involve an exponential blowup.


texts: Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem

texts:
I've difficulty in understanding the last steps of the AHSP algorithm. Let $G$ be an abelian group and $f$ be the function which hides the subgroup $H$. Let $G^*$ represent the dual group of $G$.

Here are the steps of the algorithm

First prepare the state,

$\qquad \displaystyle I=\frac{1}{|G|} \sum_{g \in G} |g\rangle|0\rangle$.
Then apply the quantum oracle which evaluates $f$ on $I$, we get

$\qquad \displaystyle I'=\sum_{g \in G} |g\rangle|f(g)\rangle$.
Now measure the the second qubit of $I'$, we get

$\qquad\displaystyle I'= \left(\frac{1}{|H|}\Sigma_{g \in H} |rh\rangle\right) \otimes |f(rh)\rangle$

for some $r \in G$.
Now we  apply the quantum fourier transform on the first qubit, we get

$\qquad \displaystyle I_m = \frac{1}{|H^*|}\sum_{\chi \in H^*} |\chi\rangle$,

where $H^*= \{\chi \in G^*: \chi(h)=1 ,\forall h \in H\}$.

Now from the state $I_m$ how can we get generators of the group $H$?


texts: Simple and practical deterministic algorithm, complicated running time

texts:
Very often, if the running time of an algorithm is a complicated expression, the algorithm itself is also complicated and impractical. Each of the cube roots and $\log \log n$ factors in the asymptotic running time tends to add complexity to the algorithm and also hidden constant factors to the running time.

Do we have striking examples in which this rule of thumb fails?

Of course it is easy to find examples of algorithms that are very difficult to implement even though they happen to have a very simple worst-case running time. But what about the converse?

  Do we have examples of very simple and practical deterministic algorithms that are easy to implement but happen to have a very complicated expression as its worst-case asymptotic running time?

Please note the keywords "deterministic" and "worst-case"; the analysis of simple randomised algorithms fairly easily leads to complicated expressions.

Of course what is "complicated" is a matter of taste. Anyway, I would prefer to see an expression that is far too ugly to put in the title of your paper. And I would prefer a complicated function of one natural parameter (input size, number of nodes, etc.).

PS. I thought I would not make this a "big-list question", and not CW. I'd like to find a single excellent example (if it exists at all). Hence please post another answer only if you think that it is "better" than any of the answers so far.


texts: Justification for the Hungarian method (Kuhn-Munkres)

texts: I wrote an implementation of the Kuhn-Munkres algorithm for the minimum-weight bipartite perfect matching problem based on lecture notes I found here and there on the web. It works really well, even on thousands of vertices. And I agree that the theory behind it is truly beautiful. And yet I still wonder why I had to go to such lengths. I find that these lecture notes don't explain why we can't simply take the primal linear program and pass it to the simplex method. Of course I suspect that it's a question of predictable performance, but since I haven't seen it explicitly stated, I'm not too sure. The polytope's extreme points of the primal are proven to be in 0-1, so it seems that we can feed it directly to a simplex implementation without even formulating the dual. Or am I being simplistic?


texts: Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?

texts:
In Feldman-Gopalan-Khot-Ponnuswami 06 the authors show that agnostically learning parities reduces to learning parities with random classification noise. They also remark (among other things) that learning conjunctions in this model is NP-hard.

Though I can't remember the source right now, I also recall that a random projection argument gives a reduction from learning parities with malicious noise to learning parities with uniform random noise.

Is there a reduction from learning conjunctions with malicious noise to learning conjunctions with random noise?


texts: What is the Turing degree of Kleene's O?

texts: It's not computable whether a number is a member of Kleene's ${\mathcal {O}}$. What is that set's Turing degree? I can almost see an argument that ${\mathcal {O}} \leq_T \emptyset^{(2)}$ but I can't see how to be sure that the set I'm thinking of is the smallest that meets the criteria. It also seems plausible that ${\mathcal {O}} =_T \emptyset^{(\omega_{CK})}$. Is this known?


texts:
I've found this webapp which lets you generate a free theorem for a given type.
The generated theorems quantify over types and relations on these types. These theorems (formulas) are theorems of which theory/logical system? How does this system relate to the equational theory of the language?


texts:
I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the graph you can get to all others.

This is similar to the rooted MST digraph problem, which the chu-liu algorithm solves quite nicely. My intuition is to calculate the rooted MST for all nodes using chu-liu and then merge each, removing redundancies along the way. However, I don't believe that that would be optimal.

Has anybody been working on this? Can you point me towards some papers that I should read?

Thanks.


texts:
Here is a brief summary of the experts framework: Given $n$ experts who either give correct or wrong advice for each round $t\in [T]$, an algorithm is required to give a best prediction for each round based on the advice from experts.

We define the difference of total loss (either 0 or 1 for each round) incurred and that of the best expert as regret. We call the regret as a function of $n$ and $T$ the zero-order regret, as a function of $L^*$ (loss of the best expert) the first-order expert, and so on.

The upper bound on the zero-order regret is known as $O(\sqrt{T\ln n})$. I was wondering if there is also a positive lower bound on this?

I guess this is true, since I could find it in Exercise 5 in the survey Learning, Regret minimization, and Equilibria by A. Blum and Y. Mansour. I would appreciate it if anyone can give me a pointer to the proof. Thanks.


texts:
background

Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no satisfactory result came up. I remember the course TA insisted on something he couldn't prove, and said he forgot the proof, and ... [you know what].

Today, I recalled the problem. I was still eager to know, so here it is...

The Question

  Is it possible to implement a stack using two queues, so that both PUSH
  and POP operations run in amortized time O(1)? If yes, could you tell
  me how?

Note: The situation is quite easy if we want to implement a queue with two stacks (with corresponding operations ENQUEUE & DEQUEUE). Please observe the difference.

PS: The above problem is not the homework itself. The homework did not require any lower bounds; just an implementation and the running time analysis.


texts: Optimal $\ell^1$ sketching, including the coefficient

texts:
Let us define the sketch as mapping $\varphi:R^D\to R^d$, such that for arbitrary $x\in\mathbb{R}^D$, its $\ell^1$ norm is preserved up to $\epsilon$ error, with $1-\delta$ success probability:
$$\mathbb{P}\left(1-\epsilon\le \frac{\|\varphi(x)\|_1}{\|x\|_1}< 1+\epsilon\right) > 1-\delta \qquad \forall x\in\mathbb{R}^D,x\neq 0$$
Clearly, the design of $\varphi$ must be agnostic to $x$, or otherwise the problem becomes trivial. I believe $d=\mathcal{O}(\epsilon^{-2}\log(1/\delta))$ can be achieved by defining $\varphi(x)=M x,$ where $M\in\mathbb{R}^{d\times D}$ is a random matrix with elements drawn from the Cauchy distribution, and use a median estimator to approximate its norm. My question is two folds:

can we generate $\varphi$ such that the norm can be assessed using
$\ell^1$ norm, rather than the median (or some other simple
geometry, like $\ell^2$ or on Hamming cube)
for a given $\delta,\epsilon$, what is the lowest possible $d$,
including the optimal constants and not just the asymptotic optimal
relationship? I am also interested the answer to the same question
for $\ell^2$ embedding/sketching


texts:
When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in $O(n^2)$ time, and I wondered if it is possible to do better:

  Can all unambiguous grammars be parsed in linear time?

I'm quite sure I read somewhere that this is the case, but it doesn't come up when searching the internet. The same question was asked here, but no answer was given as far as I know.


texts: Upper and lower bound of binomial summation

texts: For $n>1$ and $~0<p \leq 1$,   can we upper and lower bound the following   binomial series in terms of $n$ and $p$ $$\Sigma_{i=\lceil p n \rceil}^n {n \choose i} (p )^i(1-p)^{(n-i)}$$


texts:
Consider the following problem from TFNP that is somewhere between End-of-the-Line (PPAD) and End-of-Metered-Line (CLS).

Input (via polynomial circuit): Graph on vertex set $0$ to $2^n-1$ such that querying any vertex returns its neighbors (at most two), and $deg(0)=1$.

Output: Either a $v\ne 0$ for which $deg(v)=1$, OR {four vertices, $a<b<c<d$, such that $ac$ and $bd$ are edges OR $ad$ and $bc$ are edges} OR {three vertices, $a<b<c$, such that $ab$ and $ac$ are edges} OR {three vertices, $a<b<c$, such that $ac$ and $bc$ are edges}.
(So this practically says that the graph when drawn naturally behaves like a 'graph of a function', i.e., it intersects every vertical line at most once.)

How hard is this problem?


texts:
I was going through the description of NIST Randomness Beacon. I would like to know the meaning of the term

  full-entropy bit-strings

used in the third paragraph.


texts: Minimizing a general submodular pseudo boolean function

texts: Are there algorithms that minimize a general submodular pseudo boolean function (PBF) without first transforming it to a quadratic pseudo boolean function (QPBF)?


texts: Is there a quantum NC algorithm for computing GCD?

texts:
From the comments on one of my questions on MathOverflow
I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer Factorization being in $\mathsf{P}$ vs. $\mathsf{NP}$.

Is there something like a "quantum $\mathsf{NC}$" algorithm for GCD as there is a quantum polynomial time ($\mathsf{BQP}$) algorithm for Integer Factorization?

Related question: complexity of greatest common divisor (gcd)


texts: What is the Complexity Status of Arbitarily Weighted Planar Max Cut?

texts:
If you search on the internet for the Complexity Status of Arbitarily Weighted Planar Max Cut you seem to get conflicting answers.

On one hand, there are references that Barahona solved this problem in the 1980's.

On the other there is this paper:
NP-completeness of maximum-cut and cycle-covering problems for planar graphs
http://www.springerlink.com/content/xj7238374871347j/

My question is what is the Complexity Status of Arbitarily Weighted Planar Max Cut?


texts: Are the `ArrowApply` and `Monad` typeclasses equivalent?

texts:
It is stated e.g. on Hackage, that the ArrowApply and the Monad typeclasses are equivalent. I have my doubts about this.

It is obvious that there are morphisms from ArrowApply to Monad and back, and one can check that one can prove the Monad laws and the ArrowApply laws in each case. What I doubt is that these morphisms are inverses.

They are defined this way:

Let $\leadsto: \operatorname{Type} \times \operatorname{Type} \to \operatorname{Type}$ be an instance of ArrowApply, so there is $arr: (a \to b) \to (a \leadsto b)$, $first: (a \leadsto b) \to (a \times c \leadsto b \times c)$ and $app: ((b \leadsto c) \times b) \leadsto c$, and $\leadsto$ is the hom of some category. I'm leaving out the universal quantifiers on lower-case letters, like in Haskell-style.
We define a monad $m: \operatorname{Type} \to \operatorname{Type}$ by $m a = 1 \leadsto a$. For example, $\operatorname{return}: a \to m a$ is defined as $\operatorname{return} x = arr (\lambda y. x)$, and $\operatorname{join}$ and the monad laws are not very hard.
Or the other way: Given a monad $m$, define $a \leadsto b = a \to m b$. This defines obviously a category and also gives rise to an ArrowApply.

I cannot see at all that these constructions are inverse to each other. Here is what I believe to be a counter-example:

Define your arrow type as the fixpoint of $a \leadsto b = a \to (b \times (a \leadsto b))$. This is the terminal coalgebra of the functor $x \mapsto A \to (b \times x)$. It represents a stateful, causal stream function. Constructions like this are used in functional reactive programming, e.g. Yampa.

We then define the monad $m$ in terms of $\leadsto$.
Intuitively, $m a$ is the type of stream functions from unit to $a$, in other words, streams in $a$.
But Kleisli arrows of this monad aren't stream functions:
$$m a = 1 \to a \times (1 \leadsto a) \cong a \times (m a)$$
$$\implies a \to m b \simeq a \to b \times (m b) \not\simeq a \to b \times (a \leadsto b) \simeq a \leadsto b$$
So in this case, the constructions are not equivalent, if I haven't made a mistake somewhere.

Are ArrowApply and Monad inequivalent then, since the constructions aren't inverses of each other? Or is there another construction that makes them equivalent?


texts: Polynomial time construction of families of pairwise nonhomomorphic graphs

texts:
Is it true that for all $n$
there are $n$ pairwise nonhomomorphic graphs with $poly(n)$ vertices?

Is there a polynomial time algorithm for constructing such families of graphs?


texts: Dark Integers: General Purpose Computations on Internet Routers

texts:
Greg Egan in his fiction "Dark Integers" (story about two universes with two different mathematics communicating by means of proving theorems around of inconsistence in arithmetic) claims that it is possible to build general purpose computer solely on existing internet routers using only its basic functionality of packet switching (and checksum correction, to be precise).

Is this possible, in principle?

Update.

To make the question more precise:

What is an absolutely minimal set(s) of properties the router network must have that it will be possible to build general purpose computer on top of it?


texts:
In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT."

I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time complexity of the most efficient SAT solver?

In particular, is it conceivable to find a sub-exponential (yet super-polynomial) algorithm for SAT?


texts: Is there a diagonal matrix D such that DMD is SDD, where M is SPD matrix

texts:
Let $M$ be symmetric and positive definite matrix (SPD). It is known [1] that

if $M$ is SPD and
in addition satisfies $M_{ij}\leq 0$, for $i\neq j$ (called M-matrix)
then there is a positive diagonal matrix $D$ such that
$DMD$ is symmetric, diagonally dominant and $M_{ij}\leq 0$ (called SDDM matrix).

Q1: Let $M$ be SPD. Is there a diagonal matrix $D^{\prime}$ with $D^{\prime}_{ii} \neq 0~~ \forall i$ such that
$D^{\prime}MD^{\prime}$ is symmetric and diagonally dominant matrix?

Q2: Let $M$ be SPD and $[M\mathbf{1}]_i\leq[\mathrm{diag}(M)\mathbf{1}]_i~~\forall i$ (a weaker condition than $M_{ij}\leq 0$).
Is there a diagonal matrix $D^{\prime}$ with $D^{\prime}_{ii} \neq 0~~ \forall i$ such that
$D^{\prime}MD^{\prime}$ is symmetric and diagonally dominant matrix?

Q3: Is there a matrix $D^\prime$ from above such that all entries $D^{\prime}_{ii} \neq 0$ belong to  a bounded range, say $[-1,1]\backslash{\{0\}}$.

[1]: Topics in Matrix Analysis
http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511840371


texts: why are the constraints in the following paper tight?

texts:
My question is about the following paper:

http://webdocs.cs.ualberta.ca/~maz/publications/ratliff_nathan_2007_3.pdf

In section 2 they show Equation 3 (which is just an optimization problem), which they transform into the optimization problem right before section 3. Everything is very easy to read and self-contained. However, I do not understand how they can tell so easily that the constraints in the convex program are tight (which allows them to transform the program to the one before section 3). Are they relying on some result that they are not saying, or is this a very simple argument coming from optimization?

An edit, following a request to rewrite the question in a self-contained way.
Let $w \in R^d$ and $y_i \in R^d$ and $A_i$ be a finite set of vectors in $R^d$.
Consider the following optimization problem:

$\min_{w,\xi} ||w||_2^2 + \sum_i \xi_i$

under the constraints that $\forall i$ we have $w^T y_i + \xi_i \ge \max_{y \in A_i} \left( w^T y \right)$

why in any solution of this optimization problem, the constraints are tight, so that we can reformulate the optimization problem by replacing $\xi_i$ with $\max_{y \in A_i} \left(w^T y \right) - w^T y_i$ and get rid of the constraints?


texts: Is $\mathsf{P} = \mathsf{NP}$ relative to a universal predictor?

texts:
Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula

$$s(L)_n=\chi_L(s(L)_{<n})$$

Here $\chi_L$ is the characteristic function of $L$ i.e. $\chi_L(w)=1$ for $w \in L$, $\chi_L(w)=0$ for $w \notin L$

A language $U$ is called a "universal (closed) predictor" when

$$\forall L \in \mathsf{P} \, \forall n>>0:s(L)_n=\chi_U(s(L)_{<n})$$

It is easy to see $U \notin \mathsf{P}$ by considering $L = U^c$. However, $U$ can be recursive. To give an example, consider the language decided by the following algorithm $A$. Given input $w$, $A$ runs all possible programs in shortlex order, allowing each to execute for time $t(|w|)$ where $t$ is a function of superpolynomial growth. Once it reaches a program $R$ that outputs $w$ plus one or more bits and doesn't halt, $A$ outputs the first bit $R$ outputted after $w$. It easy easy to see that (under mild conditions on $t$) $A$ always halts and the language it decides is a universal predictor. $A's$ time complexity is approximately $2^nt(n)$

Given $a \in {\lbrace 0, 1 \rbrace}^\omega$, define $s(L, a)$ by

$$s(L, a)_{2n} = \chi_L(s(L, a)_{<2n})$$
$$s(L, a)_{2n + 1} = a_n$$

A language $V$ is called a "universal open predictor" when

$\forall w \in V : |w|$ is even
$\forall L \in \mathsf{P}, a \in {\lbrace 0, 1 \rbrace}^\omega \, \forall n>>0:s(L, a)_{2n}=\chi_V(s(L, a)_{<2n})$

[I am using 0-based indices so $|s_{<2n}| = 2n$]

Again it is easy to see $V \notin \mathsf{P}$ but $V$ can be in $\mathsf{E}$

  Is there $V$ a universal open predictor s.t. $\mathsf{P}^V=\mathsf{NP}^V$?

I'm especially interested in having either a specific example of such $V$ or a proof such $V$ doesn't exist under reasonable assumptions such as $\mathsf{P} \ne \mathsf{NP}$

The question might seem strange, so I'll briefly outline my motivation for it. I'm interested in AIXI-like models of aritifical intelligence. Here $L$ plays the role of the environment, which I assume to be efficiently computable, and $a$ plays the role of the actions of the agent itself. Given a positive answer for my question, it is possible to construct an agent efficiently computable relative to $V$ which optimizes a given efficiently computable utility function $u$ by choosing its future actions s.t. $u$ is maximized assuming the environment behaves according to the prediction of $V$


texts: The edit distance of BWT of two strings with one difference

texts:
Let $BWT$ stand for the Burrows-Wheeler transform on strings.
What is the maximal edit distance of $BWT(w)$ and $BWT(u)$, if $w$ and $u$ differ only in one character.


texts: Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?

texts:
I've learned from several sources that an LL(1) grammar is:

unambiguous,
not left-recursive,
and, deterministic (left-factorized).

What I can't fully understand is why the above is true for any LL(1) grammar. I know the LL(1) parsing table will have multiple entries at some cells, but what I really want to get is a formal and general (not with an example) proof to the following proposition(s):

A left-recursive (1), non-deterministic (2), or ambiguous (3) grammar is not LL(1).


texts: Assuming $\mathsf{P} \ne \mathsf{NP}$ can we show $\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$? Obviously this would be the case if $\mathsf{P} \ne \mathsf{NP}$ and $\mathsf{P/poly} \supset \mathsf{NP}$ but this is unlikely. This is also true under the assumption $\mathsf{P} \ne \mathsf{BPP}$, however AFAIK it is commonly believed $\mathsf{P} = \mathsf{BPP}$. Can we prove $\mathsf{P} \ne \mathsf{P/poly} \cap \mathsf{NP}$ under a weaker assumption? What evidence can be provided for/against? Is there a specific language which is believed to be in $\mathsf{P/poly} \cap \mathsf{NP}$ but not in $\mathsf{P}$?


texts: NFA to DFA Powerset Construction : A Partial determinization algorithm with trade-off between running time and size for the resulting automata?

texts:
Given a NFA $N$ and its equivalent DFA $D$ resulting from the total determinization of $N$ (using powerset construction, for example), the following properties hold for $N$, $D$ and for any word $w$ :

$N$ reads $w$ in running time at most $O(|w|.|N|^2)$.
$D$ reads $w$ in running time at most $O(|w|)$ and its size may be $O(2^{|N|})$ (in number of states needed to represent $D$).

I wonder if there exists some partial determinization algorithm that guarantees a trade-off between the size of the result and the running time ?

For example, this partial determinization algorithm could turn an NFA into a partially deterministic automata $D'$ such that $D'$ guarantees that the word $w$ is read in $O(|w|.|N|^x)$ where $0 \leq x \leq 2$ without exceeding the size $|D'| \leq 2^{f(x)}$ where $f(x)$ is a continuous decreasing function defined on the range $[0, 2]$ such that $f(0)=|N|$ and $f(2)=log |N|$.

I did not find any method to partially determinize a NFA in such a way. In all papers : either determinization is avoided because the NFA is too large, either determinization is full and the NFA is turned into a DFA (with a possible exponential blowup). There is no compromise...

I would really appreciate any references or any answers regarding this problem. Thank you very much, Luz.


texts: Quantum algorithms for determining whether two sets intersect

texts: Grover's algorithm is a quantum algorithm that is able to locate a special record in an $N$ element unsorted database in $\Theta(\sqrt{N})$ time. What quantum algorithms are known to determine whether two sets of size $\sqrt{N}$ intersect (so there are $N$ ordered pairs with one element from each set)? Do they beat the $\Theta(\sqrt{N})$ time of Grover's algorithm?


texts: Is there software for graph product calculation and visualization?

texts:
I am interested in finding a program which can calculate and preferably also visualize various products of not huge graphs.

More specifically, I work with labeled, directed multigraphs, and would like to be able to calculate and visualize especially the lexicographic product of such graphs.

Further, as it more precisely is a close variant of the lexicographic product I am interested in, it would be preferable if modifying the predefined operation is possible.

Specifically, I am interested in the following: where L(sG) constitute the set of labels on node s in graph G, and pre(tH) is one of two sets of labels for t in H, the product is one such that 1) the set of nodes is (s,t) such that pre(tH) is a subset of L(sG), 2) (s,t) and (s',t') are related in GxH as specified by the lexicographic product, and 3) the labels L(sGxH) are [those from L(sG) plus those from the second set of labels of t in H called post(t,H)] minus [those from L(sG) inconsistent with the new post(t,H)].

I do not assume that the program in question has the specified operation pre-programmed, but it would be very nice if it was implementable with some tampering.

Does any one know of a package that would allow this?


texts: Free books (or course materials) on undergraduate algorithms

texts:
What free books (or course materials) are there that cover undergraduate algorithms material?  I added "course materials" in case there exist comprehensive sets of lecture notes/video/other that are not quite organized in a book format but that are at least as effective as a book.

A similar question about Language and Automata.


texts: Razborov-Smolensky polynomial argument on $\textrm{ACC}[q]$ where $q$ is a prime power

texts:
It seems to be a folklore that we can "handle" $\textrm{ACC}[q]$ circuits not only for prime $q$ but prime power $q$.
For example, authors of this paper say that

  ... any constant
  depth circuit consisting of only $MOD_q$ gates, $q=p^k$
  , is
  equivalent to a constant degree polynomial over $\mathbb{Z}_p$ and
  therefore cannot compute the $AND$ function at all regardless
  of its size.

However, the original Razborov-Smolensky polynomial argument seems to consider only the case where $q$ is a prime.
How can we extend this to cover the case where $q$ is a prime power?
I'm a bit embarrassed that I was not able to follow the quote above, although it appears to give the answer already...

Or in brief:

  How to prove that $MOD_p \notin \mathrm{ACC}[q]$, where $(p,q)=1$ and $q$ is a prime power?


texts: Formalizing the "no formula for primes" intuition

texts:
I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt:

Conjecture: There is no $O(n^2)$ expected time randomized algorithm to generate $\ge n$-bit primes.

Currently I believe the best algorithm has conjectured complexity $\tilde{O}(n^3)$: run the $\tilde{O}(n^2)$ Lucas-Lehmer test on $O(n)$ Mersenne numbers.  We could go from $n^3$ to $n^2$ using the same sample-and-check strategy if a faster $\tilde{O}(n)$ checking algorithm is found.  (This argument for the choice of 2 as exponent due to Paul Christiano.)

However, if a "formula for primes" existed, and was sufficiently simple, the fact that arithmetic is quasilinear means that we might get a quasilinear time prime generation algorithm, or $\tilde{O}(n)$.  Conjecturing that the minimum exponent is 2 roughly approximates "the best strategy is sample-and-check".

Two questions:

Is there any heuristic evidence beyond the algorithms discovered so far about the optimum primality testing exponent, or the optimal exponent for generating primes?
Are there other attempts at formalizing the "no formula for primes" intuition?

I should clarify that of course I know that settling the conjecture is hopeless: I’m looking for heuristics only.


texts: Monotonic and bounded sequences throughout computer science

texts:
When I refer to the Monotone Convergence Theorem below, I refer to the very simple claim that if a non-decreasing sequence has an upper bound then it converges. I don't refer to the claim from Measure Theory.

One application I know of for this result is to recurrence relations. One shows that a recurrence relation like $a_{n+1} = \sqrt{2 + a_n}, a_0 = 0$ is non-decreasing and bounded, from which one concludes that it has a limit as $n$ approaches $\infty$.

Are there any other applications of the theorem?

I ask because I'm curious about the possibility of systematically "constructivising" applications of this theorem. Obviously in general this isn't possible. But surely there are lots of situations in which it may be possible.

By constructivise, I mean derive convergence bounds, and compute what the limit is explicitly.

I tried constructivising Herschfeld's Convergence Theorem, I believe successfully. The resulting argument is a great deal less straightforward than Herschfeld's original one.


texts:
Given an array of $n$ pairwise-different positive integers, the problem is to find the longest subsequence that is stack-sortable, i.e. avoiding the permutation pattern $231$.

How fast can this problem be solved? Can it be solved in polynomial time and linear space?


texts:
The BLR linearity test and the low degree test are two common tools in PCPs. By my understanding these tests ensure bounds such that (self-) correctors can be applied. I have two questions regarding the use of both parts:

In the literature those tests are always used to check if e.g. a function is 0.99-'close' to a linear function. What is now exactly meant by 'checking'? Is that approximating the closeness by repeating the test and evaluating the approximation (using Chernoff bounds)?
Are correctors always used in a constructive way? Would it make a difference using them to reject a function that needs to be corrected?


texts: Computing a frontier set for some Boolean-valued function in a lattice?

texts:
Assume that we have a non-empty finite lattice $(L,\leq)$ and a monotone Boolean-valued function $f : L \rightarrow \mathbb{B}$ (i.e, for every $x,y \in L$, if $f(x)=\mathbf{true}$ and $x \leq y$, then $f(y) = \mathbf{true}$).

What is an efficient algorithm to compute the frontier set of $f$, i.e., the elements $x \in L$ such that $f(x) = \mathbf{true}$ for but no element $y \leq x$, we have $f(y) = \mathbf{true}$? Alternatively, what is an efficient algorithm to compute the co-frontier set of $f$, i.e., the elements $x \in L$ such that $f(x) = \mathbf{false}$ but for all elements element $y \geq x$, we have $f(y) = \mathbf{true}$?

The algorithm can use the following operations:

Get the least element of $L$
Get the maximum element of $L$
For some element $x \in L$, compute the direct predecessors of $x$, i.e., the elements $y \in X$ with $y \leq x$, but for no $z \in L$, there is $y \leq z \leq x$).
For some element $x \in L$, compute the direct successors of $x$, i.e., the elements $y \in X$ with $y \geq x$, but for no $z \in L$, there is $y \geq z \geq x$).
Evaluate $f$ on some element of the lattice

The algorithm should minimize the number of calls to the oracle $f$. It can be assumed that the number of direct successors or predecessors of some element is constant and "small".

Some remarks that shall not be seen as part of the problem formulation:

I did a search on algorithms for this already and found a few papers that are not fully irrelevant for this problem. However, they either do not answer the problem, or they are tied to certain application domains, which makes it hard to even find out with certainty if they are related or not. An example is "Maximal Antichain Lattice Algorithms for Distributed Computations" by Vijay K. Garg.

The types of lattices that I am actually interested in are direct products of subsets of $\mathbb{N}$ and $\mathbb{B}$. The problem is is kind of an optimization problem, where $f$ tells us if some "quality requirement" vector is feasible or not.

Thanks!