texts: When are two algorithms said to be "similar"?

texts:
I do not work in theory, but my work requires reading (and understanding) theory papers every once in a while. Once I understand a (set of) results, I discuss these results with people I work with, most of whom do not work in theory as well. During one of such discussions, the following question came up:

When does one say that two given algorithms are "similar"?

What do I mean by "similar"? Let us say that two algorithms are said to be similar if you can make either of the following claims in a paper without confusing/annoying any reviewer (better definitions welcomed):

Claim 1.  "Algorithm $A$, which is similar to algorithm $B$, also solves problem $X$"

Claim 2. "Our algorithm is similar to Algorithm $C$"

Let me make it slightly more specific. Suppose we are working with graph algorithms. First some necessary conditions for the two algorithms to be similar:

They must be solving the same problem.
They must have the same high level intuitive idea.

For instance, talking about graph traversal, breadth-first and depth-first traversal satisfy the above two conditions; for shortest-path computations, breadth-first and Dijkstra's algorithm satisfy the above two conditions (on unweighted graphs, of course); etc.

Are these also sufficient conditions? More specifically, suppose two algorithms satisfy the necessary conditions to be similar. Would you indeed call them similar, if

they have different asymptotic performance?
for a special class of graphs, one algorithm requires $\Omega(n)$ time while the other requires $O(n^{1/3})$ time?
they have different terminating conditions? (recall, they are solving the same problem)
the pre-processing step is different in the two algorithms?
the memory complexity is different in the two algorithms?

Edit: The question is clearly very context dependent and is subjective. I was hoping that the above five conditions, however, will allow getting some suggestions. I am happy to further modify the question and give more details, if needed to get an answer. Thanks!


texts: Results in Theoretical CS independent of ZFC

texts:
I'm going to ask a quite vague question, since the borderline between theoretical computer science and math is not always easy to distinguish.

QUESTION: Are you aware of any interesting result in CS which
is either independent of ZFC (i.e. standard set theory),
or that was originally proven in ZFC (+ some other axiom) and only later proven in ZFC alorne?

I'm asking because I'm close to finish my PhD thesis, and my main result (the determinacy of a class of games which are used to give "game semantics" to a probabilistic modal $\mu$-calculus) is at the moment proven in ZFC extended with other Axioms (namely the negation of the Continuum hypothesis $\neg CH $ and, Martin's Axiom $MA$).

So the setting is clearly Computer Science (the modal $\mu$-calculus is a temporal logic, and I'm extending it to work with probabilistic systems).

I would like to cite in my thesis other examples (if you are aware of any) of this kind.

Thank you in advance,

bye

Matteo


texts: hardness of approximating clique: how using FGLSS reduction with PCP verifier of hastad

texts:
I try to understand the $n^{1-\epsilon}$ hardness of approximating clique for any $\epsilon$ provided in [1]: www.nada.kth.se/~johanh/cliqueinap.ps

In fact, I only want to understand the proof of theorem 2.8 (page 10) of [1], which in fact is due to [7]: https://www.cs.utexas.edu/users/diz/pubs/approx.ps.

Theorem 2.8 (proved in [7]) says:
Suppose any language in NP admits a PCP with log random bit and f amortized free bits, then unless NP=ZPP for any $\epsilon$ max clique cannot be approximated within $n^{\frac{1}{1+f+\epsilon}}$

As [1] proves that "for any $f > 0$, there exists PCP verifier (for a L in NP) with f amoritzed free bits", I understand that the result follows immediatly.

To prove theorem 2.8, I want to be sure that I correctly understand the hypothesis, and hence my first question.

1) We are given "a PCP verifier with $f$ amortized free bits".
I know that $f$ amoritzed free bits implies that the number of free bits is
at most $f log(\frac{1}{s})$, where $s$ is the soundess of the verifier.
Thus, is it correct to say that
"there exists $s>0$ such that we are given a PCP verifier with soundess $s$ and that uses $f log(\frac{1}{s}))$ free bits ?
(i.e. we do not control the soundness and the number of free bits, but only the relation between these two numbers)

2) If this is true, how can we adapt the Lemma 2.11 of [7]?
Indeed, in Lemma 2.11, the verifier reads $c$ bits and has a soundess 1/2.
I understand that I can replace $c$ by $f log(\frac{1}{s}))$ in the number of vertices of the created graph, but how can we adapt the disperser to handle the soundess s ?

Thank you very much for your answer.

Best regards


texts: Non-hamiltonian Graphs with unique hamiltonian path between exactly 4 pair of vertices

texts: Need some example graphs which are not Hamiltonian, i.e, does not admit any Hamiltonian cycle,  but which have Hamiltonian path. It has Hamiltonian paths between exactly 4 pair of vertices. I have identified one such group of graphs. Would like to see more such examples.[Redundant information deleted; thanks to Sadeq Dousti for pointing it out]


texts: Can you diagnolize without mentioning simulation?

texts:
Are there any known diagonalization proofs, of a language not being in some complexity class, which do not explicitly mention simulation?
The standard diagnolization argument goes: here is a list of machines for all languages in a class $M...$, here is the list of all arguments $w...$, you create an onto map from $w$'s to $M$'s where a map between a $w$ and an $M$ means $w$ is in the diagonal language $L$ iff $w$ is not in $M$. Then, an assumption that $L$ is solved by one of the $M$s is not true. However, with this setup, inorder to decide if a particular $w$ is a member of $L$, you need to simulate the corresponding $M$.
Even with indirect diagnolization: (essentially) you assume two complexity classes are equal, you prove more and more equalities until you show two classes equal that you can separate via the ^ same ^ type of diagnolization. Although you are not simulating machines in the original class you want to separate, you are still relying on the construction of a language that requires simulation (of machines for languages in the class it is a diagonal of) to determine its members.
Can a language be defined, via some "passive" method of diagnolization, that doesn't require simulation of machines that solve the languages in the class you are diagnolizing against?


texts: Is the feedback vertex set problem on planar bounded degree graphs hard?

texts: Is it known whether the feedback vertex set problem on undirected planar graphs of bounded degree is $\mathsf{NP}$-hard?


texts: Category-theoretic treatment of diffs, patches and merging?

texts:
Is there a category of patches that looks roughly like this:

The objects are strings in some base alphabet
The morphisms are edit scripts ("diffs" or "patches") between the strings

I'm interested in these questions:

Is there a categorical notion of minimal edit script? Maybe the category of patches is enriched in PO-Sets?
Is merging of patches the categorical pushout?
How to generalise this from strings to trees (a file system, or an algebraic datatype)?


texts: Possible generalizations of associativity?

texts:
The well-known notion of associativity in algebra leads to structures with interesting properties, such as groups or semigroups. According to a paper by John Rhodes, some researchers in algebra and computational complexity are interested in extending this notion to obtain more general structures that retain certain properties of semigroups.

It seems that such a suggestion was made anonymously on this site, but I couldn't ascertain whether the definitition is well-founded and interesting. Therefore, I would like to know what other extensions of associativity are known, and which ones were successfully used in TCS, if any. I've heard about things like Moufang loops but couldn't wrap my mind around the defn, so any etra 'intuition' is welcome.


texts: Data structure for radial orderings of points on the plane

texts:
Assume points are always in general position.
For a set of $n$ points $S$ on the plane, a radial ordering with respect to $x\in S$ is a total ordering of the elements in $S-x$.

Consider shooting an upward vertical ray from $x$, and rotate the ray counterclockwise. The sequence of points in $S$ swept through by the ray is the radial ordering.

Given a set of $n$ points on the plane. Create a data structure, so it can answer the following query:

  Query($x$,$i$)

  Input: $x\in S$, $1\leq i\leq n-1$.

  Output: The $i$th element in the radial ordering with respect to $x\in S$.

Is there any study on such a data structure?
In my application, there will be around $\tilde{O}(n)$ queries.


texts: Re-packing of integers into fixed-size bins

texts:
We are given a constant $B \geq 3$, a set of positive integers $I$  s.t. $\forall i \in I, i \leq B$ and $\sum_{i \in I} = N$,
and 2) a packing of these numbers into $N/B > 1$ bins of size $B$.

An adversary replaces two numbers with their addition so that a packing exists. I.e.,
for some $i,j \in I, i+j \leq B$, the set
$I' = (I \setminus \{i,j\}) \cup \{i+j\}$ admits a packing into $N/B$ bins.

An optimal update minimizes the number of touched bins during the re-packing for $I'$.
We are interested in the maximum number of bins  an optimal update would touch.

Questions:
How many bins (at most) an optimal update has to touch in a worst case?

Does it depend on the number of bins or it is some function of only $B$?


texts:
Given an array of $n$ elements, $A[n]$ consider a data-structure which supports the following operations:

You are allowed a one time $\mathcal{O}(n)$ preprocessing step:

$\text{Init}(A)$

And the operations

$\text{Reverse}(i,j)$: Reverse the slice $A[i \dots j]$ i.e. swap $A[i]$ with $A[j]$, $A[i+1]$ with $A[j-1]$ etc.
$\text{Retreive}(i)$: Returns the element at position $i$ in the array.

Now I have heard that there is a data-structure which supports both $\text{Reverse}$ and $\text{Retrieve}$ in guaranteed $\mathcal{O}(P(\log n))$ time, where $P(x)$ is a polynomial (Assume $\mathcal{O}(1)$ array accesses).

I am guessing this was published somewhere. Does anyone know any reference?

Apologies if this is actually at the level of undergraduate homework. Please feel free to close/delete it in that case (but please do provide a reference to the appropriate text/website in comments before deleting).


texts: About counting the "total size" of non-zero Fourier coefficients of a Boolean function

texts:
Given a $f: \{-1,1\}^n \rightarrow \mathbb{R}$, I want to compute this quantity,

$\sum_{ \hat{f}(S) \neq 0, S \subseteq 2^{[n]}} \vert S \vert $

i.e the sum of the sizes of the subsets of $[n]$ corresponding to the non-zero Fourier coefficients of the function.

Is there a nice "analytic" form for this quantity? Anything is known about this?


texts:
Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called the rank-metric. This allows us to consider error-correcting codes in this space.

One example of codes in this metric are Gabidulin codes, which are analogues of Reed-Solomon codes. Essentially, we consider the rows of an $n \times m$ matrix as elements of the extension field $\mathbb{F}_{q^m}$. So now we consider the space of linearized polynomials over $\mathbb{F}_{q^m}$ of q-degree k-1 as the set of messages, and to get a codeword, we evaluate such a polynomial at $n$ evaluation points $g_1, g_2, \dots, g_n \in \mathbb{F}_{q^m}$ which are linearly independent as vectors over the base field $\mathbb{F}_q$, giving a vector in $\mathbb{F}_{q^m}^n$ which we can then interpret again as a matrix in $\mathbb{F}_q^{n \times m}$. This code, just like Reed-Solomon codes, has distance $n-k+1$.

Now consider the decoding of such codes. We shall consider the analogue of the Berlekamp-Welch decoder for Reed-Solomon codes.
We are given a word $(y_1,y_2,\dots,y_n)^T$ within a distance (according to the rank-metric) of $t$ from a codeword corresponding to the linearized polynomial $f$ say, and our aim is to algorithmically find $f$ when $t$ is less than half of the distance.
This is worked out in the following paper:
http://perso.univ-rennes1.fr/pierre.loidreau/articles/wcc_2005/Welch_Berlekamp.pdf
If you are familiar with the Berlekamp-Welch decoder, this paper should be easy enough to read through quickly.
In the paper, consider proof of proposition 2 in section 4.
There, it claims that

"Now let us consider a non-zero solution $(V_0,P_0)$ of 1), then any solution $(V,N)$ of 2) satisfies the following system of equations:

$$V_0[N(g_i)-V(P_0(g_i))]=0 $$
$\forall i=1,\dots,n$"

How is this equation obtained? The paper states it as if its obvious, but I am unable to prove this.
Any help would be appreciated.
Thanks.


texts: Multi prover, verifier games and PCP theorem

texts:
This question came up while I was going through Siu On Chan's paper on Approximation Resistance. My question is not really related to the paper though.  I also guess that this is more of a reference request kind of question (preferably some lecture notes or surveys). I hope what follows helps putting the question in perspective, so please bear with me.

I recently started studying up the literature on PCPs and inapproximability and my knowledge is small. I know the proof of PCP theorem. The proof I read is Dinur's proof as presented in Arora Barak. All the while, I saw the two contrasting views of the PCP theorem

(i) the prover, verifier view and,
(ii) the view related to a deciding a gap instance of a CSP (for some constant gap).

Now, my question is the following. While going through Siu's paper, I got the impression that 2 prover 1-verifier games are relevant to PCP literature. My current knowledge base is so shamelessly small that I do not really understand this. I just know the 2 views I described above and am not comfortable with the multiple provers view.

I mean, why is the value of a game with multiple provers even related to the PCP theorem where you have a single prover and a single verifier? Does the value of a game help you somehow argue about the soundness part?

Thanks


texts: Splay trees as dynamic weight-balanced trees?

texts:
Given a collection of keys $x_1 < x_2 < \dots < x_n$ with associated weights $w_1, w_2, \dots, w_n$, a weight-balanced tree for the keys $x_i$ with weights $w_i$ is defined as follows:

The root is chosen so that, intuitively, the weights in the left and right subtrees are as close as possible. Formally speaking, we pick the root node to be the key $x_k$ such that $$|\left ( \sum_{i = 1}^{k - 1} w_i \right ) - \left ( \sum_{i=k+1}^n w_i \right )|$$ is minimized.
The left and right subtrees are constructed recursively.

Weight-balanced trees have a number of surprising properties. One property in particular is that the cost of looking up a key $x_i$ in a weight-balanced tree of total weight $W$ is $O(\log {W \over w_i})$. (One way to show this is to prove that if the tree itself has total weight $W$, each subtree can have weight at most $\frac{2W}{3}$, giving a geometric decay on the remaining total weight from one level to the next.)

When I first learned this property, it reminded me of the access lemma for splay trees, which says that (assuming keys are assigned weights as given above), the amortized cost of looking up key $x_i$ in a splay tree is also $O(\log {W \over w_i})$. In the context of splay trees, this access lemma is used to prove the balance theorem, static finger theorem, and static optimality theorem by using a set of fixed weights. This exact same reasoning can be used to show that by assigning weights in the same way, a weight-balanced tree can give worst-case $O(\log n)$-time lookups (if all weights are the same), are within a constant factor of statically optimal (if weights are access probabilities), and can be used to mimic static finger trees (assigning weights based on the log of the distance to the static finger). Moreover, in Sleator and Tarjan's original paper on splay trees, they mention an application of splay trees to lexicographical search trees (basically, tries with child pointers stored in BSTs). They show that the cost of looking up a word, assuming each word has some associated weight $w_i$ and the total word weights are $W$, is amortized $O(\log{W \over w_i})$. This same behavior can be guaranteed in the worst-case by using weight-balanced trees, since they satisfy the same key requirements. On the other hand, some other results about splay trees (for example, the working set theorem) that follow from the access lemma work by dynamically changing the weights on the keys from one access to the next, something a weight-balanced tree can't do.

My question is whether there's some deeper connection between this style of weight-balanced tree and splay trees. Can splay trees, in some sense, be said to model what a weight-balanced tree would be doing in response to a series of accesses? Or perhaps in reverse - are weight-balanced trees tapping into some sort of structural property that's also shared with splay trees that guarantees these behaviors?


texts: Is there research on "minimal" Turing-universal Markov algorithms?

texts:
The Markov algorithm is a simple model of computation. For other models of computation, such as Turing machines, cellular automata, tag systems, etc., there is research on the "minimal" instances of the model that are Turing-universal. Here "minimal" is defined differently depending on the formal system in question, but it tends to mean things along the lines of a small number of states. For example, there is a 2-state, 3-symbol Turing machine that's arguably Turing-complete. Or rule 110 is an (arguably) Turing-universal cellular automaton with two states and a neighbourhood of three.

My question is whether this kind of research has been done in the context of Markov algorithms - are there "minimal" Turing-complete sets of transition rules for a Markov algorithm in the literature?

Note that I'm being deliberately vague about what "minimal" should mean in this context, since I don't want to overly constrain the answers, but I would guess that minimal would mean a small alphabet, a small number of rules, and short search/replace strings within the rules. Similarly, there is leeway in precisely how one would define Turing-universality for a Markov algorithm, but I'd be happy to see results for any half-way reasonable definition.

Note: there is a similar question over on CS.SE, but I thought it would be worth asking here and spelling out more carefully what I'm looking for.


texts: Are regular languages closed under addition?

texts:
Specifically what I mean by addition is, we define $\Sigma_i$ to be the alphabet $\{0, 1, 2, ..., i\}$. Given regular languages $A$ and $B$ under some alphabet $\Sigma_i$, look at $A\times B$.

For every ordered pair $(a, b) \in A\times B$, define the "sum" of this ordered pair as $a+b$, where $a$ and $b$ are numbers in base i. Leading 0's are ignored, so $0^*$is in front of every accepted string. This implies $\epsilon$ is defined as 0.

The language $A+B$ is the set of strings representing all such possible sums.

So far, I know:

This is true in unary ($\Sigma_1$).
This is true for any finite regular languages $A$ and $B$, because any finite language is regular and $A+B$ is finite.
The language $C_n$ = $\{$s $|$ s is a multiple of n in base b$\}$ under $\Sigma_b$ is regular for any $b >= 1$. This means any languages of the form $C_n$ can also be added, as $C_i+C_j=C_{i + j}$, which is also regular. However there are languages like $D$=$\{$s $|$ s starts and ends with a 1} which don't fit this criteria, so this doesn't describe all regular languages.


texts:
I was wondering if anybody had any pointers to:

 1. References for the problem of vertex counting on convex polytopes
 2. Possible implementations of known algorithms for such problem

So far I found:

cdd (by Komei Fukuda)
lrs (by David Avis)
azove (by Markus Behle)

The references to the corresponding methods can be found on the authors websites and the corresponding documentation.

The first two focus more on vertex enumeration and not just counting, while the third one focuses on the problem of counting 0/1 vertices on polytopes with coefficients in $\mathbb{Z}$.

A second question motivated by the last method:

Assuming that it's possible, are there any known methods for computing a combinatorially isomorphic polytope $A$ with coefficients in $\mathbb{R}$ from a polytope $A$ with coefficients in $\mathbb{Z}$?

Update: The answer to this last question seems to be no (see Tsuyoshi Ito's comment below)

A third related question:

Not sure if the answer to the previous question answers this one, but are there  any known transformations that preserve vertex cardinality from polytopes with coefficients in $\mathbb{R}$ to polytopes with coefficients in $\mathbb{Z}$?


texts: Orlicz norm of random variable and variance

texts:
In probability and statistics Orlicz norms are frequently used in concentration inequalities. For example, for Bernstein's inequality, we have versions for sub-exponential random variables using $\psi_1$-norm and for bounded random variables using variance.

My first thought is that the $\psi_1$-norm version is more general, and includes the case of bounded random variables as a special case. However, an example of Bernoulli random variable with probability $1/n$ being $1$ and $1-1/n$ being $0$ suggests this is not true. For $n$ very large, the variance is roughly of the order $1/n$. However, its $\psi_1$-norm is roughly of the order  ${1}/{\log n}$.

This suggests that $\psi_1$-norm (or similarly, $\psi_2$-norm) is actually very loose for very biased Bernoulli random variables. Is there any other notions like $\psi_1$-norm that can accommodate biased Bernoulli random variables?


texts: What is the proof that the existence of one-way-functions implies $P \neq NP$?

texts:
I am not an expert in this field, but I have read that the existence of one-way functions implies $P \neq NP$. Since there seem to be so many different definitions of one-way-functions and I have not seen a proof  I wanted to ask if someone knows where to read this, or knows the proof.
Please if you give a proof, also give a precise definition of which version of "one-way-function" you use. The proof can of course be detailed, the detailed, the better! :)
Thanks!


texts: Does diagonalization captures the essence of class separation ?

texts:
I don't remember having seen a class separation not based on diagonalization and relativization results.  Diagonalization could still be used to separate remaining known classes, because non-relativizing arguments might still be used in the diagonalization conclusion, or in the diagonalized Turing machine construction.  Here are some related questions:

  Are there class separation proofs not based on diagonalization?

And if so

  Can we find a self-reference mechanism behind them ?

Further,

  does every class separation have a "canonical natural" proof (in an informal sense)?

If so, we should try to find non-relativizing arguments, rather than other proof schemes for open questions.

  Can every non-diagonal proof be rewritten into a diagonal one ?


texts:
Show that in any graph $G$ with min-degree $k$ ($k \geq 1$ duh!) you can find as its subgraph any tree on $k+1$ vertices.

I have not been able to solve the question so far. However, I would like if someone can invoke the probabilistic method to prove the above statement (as in if someone can show that the probability of not finding some tree on $k+1$ vertices as some subgraph of $G$ is less than $1$. My earlier efforts aimed at trying to show that we can somehow show that this graph contains $K_{k+1}$ which was obviously false. Next, I tried showing that a sequence of edge contractions can give a $K_{k+1}$. Though I have not shown it so far, I was wondering what good that result might have been. So far, sadly, I have gotten nowhere :(

Sorry, if the question is too dumb.
)


texts: Is an NP-hardness proof of an NP-hard problem considered a contribution?

texts:
I am solving a problem that is claimed to be NP-hard elsewhere, say in the paper [XYZ]. The NP-hardness provided in [XYZ] is complicated and uses advanced techniques. After some research and work, I succeeded to give a simple and clear proof of the NP-hardness. I am wondering if this is considered as a contribution or not? I am trying to motivate my work but I didn't find a similar path.

I don't know if this is the right place to ask or should I go to academia?


texts: Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

texts:
There are assumptions that are known to imply that $P = BPP$. For example, if there exists a function in $E = DTIME(2^{O(n)})$ that has circuit complexity $2^{\Omega(n)}$, then $P = BPP$ [1]. Clearly, such a result would also imply that $P = ZPP$.

Is there an assumption that is known to imply $P = ZPP$ but is not known to imply that $P = BPP$? Alternatively, is there a reason to believe that such a result is unlikely to exist?

[1] Impagliazzo, Russell, and Avi Wigderson. "P= BPP if E requires exponential circuits: Derandomizing the XOR lemma." Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. 1997.


texts: Simple version of Wang's tessellation problem

texts:
I'm reading about Wang's tessellation problem and the text mentions
a simpler version: If we consider a finite set of tiles $W_{n}=\{w_{1},...,w_{n}\}$
where $n$ is bounded then the claim is that now the problem
is in $R$.

Of course, after writing this claim the text adds the comment
$$
\text{(Why ? )}
$$

which left me thinking about it.

I fail to see how $n$ being bounded helps, since $\mathbb{R}^{2}$
is still infinite and so this doesn't seem like a finite problem to
me. Moreover, given some specific $n$ (not bounded a priory) it seems
that we could of solved the 'easy' problem with that $n$ thinking
of it as a constant (/bounded).

Can someone help me understand the reasoning ?


texts: Papers on Prolog-like languages without closed world assumption (CWA)

texts:
Prolog execution process may be seen as a search that model scientific search for a proof of a proposition. At the same time, real world scientific search greatly differs from Prolog search in the following way:

As we know, Prolog is based on closed world assumption (CWA) -- that is, if a proposition is not in the fact database and not derivable from the fact database, then it is not true. So Prolog search may yield 2 results:

proposition is proved; here is the proof: ...
proposition is false or it can not be proved using fact database

At the same time, scientific search is not limited by CWA and may be seen in at least 4 states:

proposition is proved; here is the proof: ...
proposition is disproved by counter-example; here is the counter-example: ...
proposition is neither proved, nor disproved to the specified (current) time
proposition is proved to be independent from the axiom set; here is the proof: ...

I suspect that, because of popularity of Prolog in the end of the XX century, there were successful attempts to improve it by removing CWA in order to better model scientific search in resulting language. CWA removing seems to open possibility to use 3 or even all the 4 above-mentioned states in programming language execution process.

So, I suspect, there are papers that describe such attempts and explore theoretic foundations of such a prolog-like languages. If so, please point out a survey or a bunch of most significant of such a papers.


texts: Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds?

texts: By counting arguments, one can show that there exist polynomials of degree n in 1 variable (i.e., something of the form $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ which have circuit complexity n.  Also, one can show that a polynomial like $x^n$ requires at least $\log_2 n$ multiplications (you need that just to get a high enough degree).  Are there any explicit examples of polynomials in 1 variable with a superlogarithmic lower bound on complexity? (results over any field would be interesting)


texts: Counting sum of parities of cycle covers in cubic, planar, bipartite graphs

texts:
Let $G$ be a cubic (i.e. every degree exactly three), planar, bipartite graph. By Hall's theorem its edges can be partitioned into three perfect matchings. Take any such partition $M_0,M_1,M_2$ and let $c_0,c_1,c_2$ be respectively the number of cycles in $M_1\cup M_2, M_2\cup M_0, M_0\cup M_1$ respectively.

Is $c_0 + c_1 + c_2 \equiv 0 \bmod{2}$? If yes, what is the proof? If not, a counterexample?

Small examples such as a cube or two concentric hexagons with $6$ cross edges etc. seem to point towards the first possibility but I am not sure either way.

Any references will be greatly appreciated!


texts: Factoring semiprimes whose factors very close to a power of two

texts: Are there any factorization algorithms that run well on numbers $N = pq$ where $p,q$ are prime and $p = 2^b - k_p, q = 2^b - k_q$ for very small $k_p,k_q$? What about $p = 2^b + k_p, q = 2^b + k_q$ for very small $k_p,k_q$?


texts: Euclidean Capacitated Facility Location Problem

texts:
In the Capacitated Facility Location Problem (CFLP), we are given a
set of clients $C$ and a set of potential facilities $F$. Each client $j \in C$ has a demand $d_j$ that must be served by one or more open facilities. Each facility $i \in F$ has an opening cost $f_i$ and has a capacity $u_i$, which is the maximum demand that facility $i$ can serve. The cost of serving one unit demand of client $j$ in facility $i$ is $c_{ij}$. We want to open a subset of facilities and assign demand of clients to open facilities such that the demands of all the clients are met, no capacity constraint violated and the total cost of opening facilities and servicing clients is minimized. Service costs are nonnegative, symmetric, and satisfy the triangle inequality.

Arora in [1, page 21] states that "Arora, Raghavan and Rao [2] give a PTAS for the geometric case. They extend the algorithm to the capacitated case but the final solution may violate capacity constraints by small amount." What does he mean by "small amount"? I guess it means they give a PTAS that violates capacity constraints within factor $(1+\epsilon)$ for an arbitrary $\epsilon > 0$. Is this right?

When I looked in [2], the only related result that I found was a $n^{O(\log^2 (n / \epsilon))}$ time algorithm for finding a $(1+\epsilon)$-approximate solution for the Capacitated $k$-median problem when we have uniform capacities. Does Arora refer to above result in [1]?

[1] S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey. In Math. Programming, Ser. B, vol. 97, pp 43-69, 2003.

[2] S. Arora, P. Raghavan, and S. Rao. Approximation schemes for the Euclidean
k-medians and related problems. In Proc. 30th ACM Symposium on Theory
of Computing, pp 106–113, 1998.


texts: Bouziane’s transformation of the Petri net reachability problem and incorrectness

texts:
This paper seems to point out that Bouziane’s solution is incorrect.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.143.9009&rep=rep1&type=pdf

In the conclusion:

  This false claim served for deriving a bound on the number of states
  of the constructed automaton – which in reality can have infinitely
  many states.

I think I understand this point as it relates to the general reachibility problem, However The Petri-Net used as an illustration contains 'loops' at transitions: t3 and t1 - transitions that have both incoming and outgoing arcs.

If Petri-Net being examined were composed of only elementary paths, the resulting witness sequence / state machine language would not be susceptible to the pumping lemma.

Does this seem accurate? why or why not?


texts: Regaining decidability by adding axioms that model real world situation

texts:
It is known that first order logic is too general to be decidable. Adding axioms with special meaning (e.g. expressing notions such as necessity/obligation, provability, etc.) leads us to modal logics but some of them (especially multidimensional fusions or products of them) are undecidable too.

As I understand, then undecidability generally is created by quantifiers - it is quite hard to prove of refute formula, that should be valid in all worlds (if accessibility relation allow them).

The undecidability can be handled by several approaches:
1) lowering the expressivity of the logic or considering the less expressive fragments;
2) following ideas of max-SAT problems;
3) moving to approximate reasoning (probabilistic, fuzzy-logic, etc.).

All these approaches has this drawback: they tries to reformulate or make less relevant the original problem that was created as conscise and clear model of the real world problem.

Maybe there is better way how to approach such undecidable situations - simply by adding additional axioms that reflect the real-world situation. E.g. axiom can be added that the number of variables is bounded in the logic (there can be different axioms depending on how we model the reason why there are only finite number of instances of some class in the world - e.g. bounded resources, restricion by law, etc.).

So - the question is - is there some research trend that investigates the modal logics with aim - what axioms should be added to them the regain the decidability of logics (and according - the suitability for them for automated reasoning tasks, for use in autonomous systems)?


texts: Can a non-competitive deterministic algorithm be k-competitive if randomized?

texts:
Let's say there is a problem in which all possible deterministic online algorithms tha solve this problem are not-competitive.

Does this mean that a randomized online algorithm for the same problem will also be not-competitive, or is there a case that it can be k-competitive (k is a constant)?


texts: Problems still "hard" in the SMP/Referee model with shared randomness?

texts:
In the referee (SMP: Simultaneous Message Passing) model introduced by Yao (see e.g. [1]), Alice and Bob have respectively inputs $x\in X$ and $y\in Y$, and wish to communicate with a third-party, the Referee, to compute $f(x,y)$ where $f\colon X\times Y\to\{0,1\}$ is a function known to the three parties.

The restriction, however, is that the communication is one-way: Alice and Bob can only send a message to the referee, who then must output the answer ($A\leadsto R$ and $B\leadsto R$). (This differs from the one-way CC setting as the referee does not hold any input.)

While the deterministic communication complexity in this model seems well-understood, and lower bounds (tight for $\sf EQ_n$) for the private-coin setting are known [1], I could not find examples of cases (preferably for promise problems, i.e. with a gap between $\sf yes$ and $\sf no$-instances) for which there was a strong separation between one-way public-coin communication complexity and SMP public-coin communication complexity.

  What are problems $\Pi$ for which there is a gap between $\operatorname{ow-CC}_{\rm pub}(\Pi)$ and $\operatorname{smp-CC}_{\rm pub}(\Pi)$?

For instance, ${\sf EQ}_n$ is $\Theta(\sqrt{n})$ for SMP private-coin, and $O(\log {n})$ for one-way private-coin; but in the public-coin setting, it is $O(1)$ for both. On the other end of the spectrum, ${\sf DISJ}_n$ is $\Theta({n})$ for both models, and so is ${\sf GAPHAMMING}_n$.

(As a side note, one can derive a separation between one-way "imperfectly-shared"-coin communication complexity and SMP "imperfectly-shared"-coin communication from the work of Bavarian et al. [2] on communication with correlated random bits, from their ${\sf GAPIP}_n$ problem, but this separation does not hold for perfectly shared randomness (public coins)).

[1] Randomized simultaneous messages: solution of a problem of Yao in communication complexity, L. Babai. 1997.
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=612319&tag=1

[2] On the Role of Shared Randomness in Simultaneous Communication, M. Bavarian, D. Gavinsky, T. Ito, 2014.
http://arxiv.org/abs/1508.06395


texts: Trade off between width and depth of free BDDs for total functions

texts:
Terminology
A binary decision diagram is a directed acyclic graph with one source (root), and two sinks ($A$ and $B$). Each non-sink nodes is labeled by an integer $i \in \{1,...,n\}$ and has out-degree 2 (one edge labeled '0', the other '1'). Visiting a node with label $i$ corresponds to queering the bit $x_i$ of the input and following the $0$-edge if $x_i = 0$ and the $1$-edge otherwise. When you arrive at a sink, you output its value $A$ or $B$ as the solution to the function represented by the BDD.

The depth of a BDD is the length of the longest path from source to sink.
A slice at depth $k$ is the set of all nodes that are a distance $k$ from the root. The width of a BDD is the size of the largest slice.
The size of a BDD is the total number of nodes.

A BDD is free, if there is no constraints on the labeling of the nodes. This is in contrast to the more commonly studied restriction of Ordered BDD that does not allow you to label a vertex $i \geq j$ if an ancestor is labeled $j$.
Question
Given a total boolean function $f$ is there a trade off between the depth and width (or depth and size) of the BDDs representing it?
Let $D(f)$ be the query complexity of $f$, and let BDD mean BDD representing $f$. Are there cases that every BDD of depth $D(f)$ has a strictly larger width than a BDD of larger depth?

Motivation
This question is a follow up to:
Trade off between time and query complexity
The hope is that by looking at a more rigid model such as BDDs we might be able to build intuition for that question in the interesting case of total functions. For a free BDD the depth corresponds directly to query complexity. The width is usually seen as a measure of space not time, so this question is also a restriction of time-space trade offs. However, the hope is that learning some trade offs between depth and width/size can help build similar things for query-vs-time in the circuit model.
Note that the case of partial functions is not interesting, since the Kothari-Fitzsimons construction from the previous question can be modified to give a separation for BDDs (although not an arbitrary one; at most exponential). The case of the better studied ordered BDDs is also less interesting, because it is easy to show that the depth of an ordered BDD does not correspond to query complexity. You can give examples of total functions where any ordered BDD has exponentially higher depth than the function's query complexity.


texts: On Courcelle's question about Monadic second-order logic with cardinality predicates

texts:
I have found the following question at openproblemgarden.org:

The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:

$\text{``}\,\mathrm{Card}(X) = \mathrm{Card}(Y)\,\text{''} $
$ \text{``}\,\mathrm{Card}(X) \text{ belongs to } A\,\text{''} $

where $ A $ is a fixed recursive set of integers.

Let us fix $ k $ and a closed formula $ F $ in this language.

Conjecture   Is it true that the validity of $ F $ for a graph $ G $ of tree-width at most $ k $ can be tested in polynomial time in the size of $ G $?

I think that this conjecture of course false:

Consider some set $A$ such that $A$ recursive but $A$ is EEXP-hard.
Consider the formula $ \text{``}\,\mathrm{Card}(V) \text{ belongs to } A\,\text{''} $, where $V$ is the set of vertices.

Now assume that the conjecture is true. I claim that in this case $A$ belongs to  EXP that contradict to Time-hierarchy theorem. Consider the following algorithm deciding $A$:

On input $n$ construct a tree with $n$ vertices. By the conjecture we can decides does $n$ belongs to $A$ in time $\text{poly}(n)$ that is $2^{\text{poly}(\text{the size of the input})}$.

Am I wrong?


texts: What are the widely used notations for quickly referring to a single component of a multi-component object?

texts:
I have the need to define a multi-component object type for which I provide numerous definitions throughout the text.
However, in most of these definitions, I only need to refer to one or two of the components constituting the object type.
Therefore, I am looking for a widely used notation that allows to quickly refer to only a single component of the object type without having to introduce the entire object.

I have identified four possible notations for defining multi-component objects. which I do introduce below using the object type transition system as an example.
The first notation is the classical one where the object type is defined as a tuple. The drawback of this definition is that anytime that I want to express properties on the object type I need to re-introduce the entire tuple.
The other three notations (2-4) avoid this issue, but I am not sure whether they are widely used and accepted.

Here are a few options

  A transition system $TS$ is a tuple $(S,\Sigma,\delta, s_0)$ where

  $S$ is a set of states
  $\Sigma$ is a set of Actions
  $\delta \subseteq S \times \Sigma \times S$ is the state transition relation
  $s_0 \in S$ is the initial state

Usage example

  A transition systems $TS = (S,\Sigma,\delta, q_0)$ is finite if $S$ is finite

  A transition system $TS$ is consists of

  a set of states $S(TS)$
  a set of actions $\Sigma(TS)$
  a transittion relation $\delta(TS) \subseteq S(TS) \times \Sigma(TS) \times S(TS)$
  the initial state $s_0(TS) \in S(TS)$

Usage example

  A transition systems $TS$ is finite if $S(TS)$ is finite

  A transition system $TS$ is consists of

  a set of state $S^{TS}$
  a set of action $\Sigma^{TS}$
  the transition relation $\delta^{TS} \subseteq S^{TS} \times \Sigma^{TS} \times S^{TS}$
  the initial state $s_0^{TS} \in S^{TS}$

Usage example

  A transition systems $TS$ is finite if $S^{TS}$ is finite

  A transition system $TS$ is consists of

  a set of states $TS.S$
  a set of actions $TS.\Sigma$
  a transittion relation $TS.\delta \subseteq TS.S \times TS.\Sigma \times TS.S$
  the initial state $TS.s_0 \in TS.S$

Usage example

  A transition systems $TS$ is finite if $TS.S$ is finite


texts: Check if graph stays connected after edge swap

texts: Checking whether a (simple, undirected) graph is connected can be done in linear time in the number of edges. What I am looking for is a more efficient way of checking whether it stays connected after repeated modifications, specifically: repeated edge swaps. An edge swap removes two edges $\{a - b, c-d\}$ and adds $\{a-c, b-d\}$ instead.  Is there a way to do better than a full linear-time check after each and every modification?


texts: Theoretically, can everyday computing tasks be broken down into ones solvable by a neural network?

texts:
MIT Review recently published this article about a chip from IBM, which is more or less a Artificial neural network. Why IBM’s New Brainlike Chip May Be “Historic” | MIT Technology Review

The article suggests that the chip might have borrowed a page from the future. It might be the beginning of an era of new and evolved computation power. And also talks about programming for the chip.

  One downside is that IBM’s chip requires an entirely new approach to
  programming. Although the company announced a suite of tools geared
  toward writing code for its forthcoming chip last year (see “IBM
  Scientists Show Blueprints for Brainlike Computing”), even the best
  programmers find learning to work with the chip bruising, says Modha:
  “It’s almost always a frustrating experience.” His team is working to
  create a library of ready-made blocks of code to make the process
  easier.

Which brings me to the question, can everyday computing tasks be broken down into ones solvable by a neural network (theoretically and/or practically)?


texts: Typing inference as a map on abstract syntax trees

texts:
Is there a reference that explains typing inference for Martin-Löf type theory as a computable map from abstract syntax trees of terms to abstract syntax trees of types? I don't want to identify non-identical judgmentally equal things.
The terms and the types are all defined in the empty context and we also include annotations for the variable types in lambda abstractions.
If there is such a map then is it true if a type is not in beta normal form then it has no terms in beta normal form map to it?


texts:
I was looking at some heuristics for coloring and found this book on Google books: Graph
Colorings By Marek Kubale

They describe the Greedy algorithm as follows:

While there is an uncolored vertex v
    choose a color not used by its neighbors and assign it to v

Then they describe a sequential algorithm:

order the vertices in a random way
execute the greedy algorithm

They claim that this algorithm is $O(m+n)$.

Its seems to me that the greedy algorithm is in fact $O(n^2)$.
Am I missing something here? Or is the greedy method $O(m)$?
($m$ = edges, $n$ = vertices)


texts: Why would one ever use an Octree over a KD-tree?

texts:
I have some experience in scientific computing, and have extensively used kd-trees for BSP (binary space partitioning) applications. I have recently become rather more familiar with octrees, a similar data structure for partitioning 3-D Euclidean spaces, but one that works at fixed regular intervals, from what I gather.

A bit of independence research seems to indicate that kd-trees are typically superior in performance for most datasets -- quicker to construct and to query. My question is, what are the advantages of octrees in spatial/temporal performance or otherwise, and in what situations are they most applicable (I've heard 3D graphics programming)? A summary of the advantages and problems of both types would me most appreciated.

As an extra, if anyone could elaborate on the usage of the R-tree data structure and its advantages, I would be grateful for that too. R-trees (more so than octrees) seem to be applied quite similarly to kd-trees for k-nearest-neighbour or range searches.


texts: I am about to choose a project regarding "Reversible logic circuit synthesis". I've studied well about "Switching circuits and Logic design" and I found it very intriguing but I've got no idea about the other topic. Can someone please elaborate it and explain what it refers or point some sources. Thank you guys in advance. :)


texts:
I was reading Scott Aaronson's blog, and one of the comments sparked a question.

"if P!=NP, this would be a general, conceptual result, so you’d expect the proof to be explanatory and in particular human-scaled. If P=NP, it could be 'an accident' and the reason is simply that there is some astronomic but polynomial time algorithm for SAT, an algorithm which humans might never grasp."

Problems with this specific argument aside, it seems that many proofs are best made by counterexamples, and often these counterexamples are simple enough that it's possible they could be semi-randomly generated by a computer, then automatically checked (say with an Interactive Proof).

This is also true with algorithms - there are many procedures for checking if an algorithm works for solving a problem (IE: Blum and Kannan's procedure for the Graph Isomorphism Problem) efficiently, without providing the algorithm itself.

I recognize you have many approximation algorithms that use this very principle to give near/if not optimal answers, but I'm asking about the case where typically such a search isn't academically productive because of how uncommon a randomly generated correct result occurs.

Are there any significant proofs/efficient algorithms that have been randomly generated, potentially far ahead of the theoretical understanding for why those counterexamples exist? Or provided a helpful background that created motivation for building the knowledge-base for that understanding?

The main reason I'm asking is because I've never head of such a result, and am wondering how commonly this occurs (thus if it's a viable assumption it can occur).


texts: Is Hartmanis-Stearns conjecture settled by this article?

texts:
The paper

  "On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited"
  by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec
  https://arxiv.org/abs/1601.02771

claims in Theorem 2.3: "
An algebraic irrational real number cannot be generated by a one-stack machine, or equivalently, by a determistic push down automaton."

I have read and checked the article, have not found any gap in it, and thus the Hartmanis-Stearns conjecture is closed by the theorem? Since the conjecture is hard to prove, I suspect that I misunderstood the article or some fault in it.


texts:
Parameterized Higher Order Abstract Syntax (PHOAS) is a representation of syntax trees that allows the host language's binding to be used to represent binding in the language being modelled, while fulfilling the strict positivity requirements that most dependently typed languages impose . This is done by modelling the type of variables as a type parameter: $term : (V : Set) \to Set$.

The original PHOAS paper describes a way to model System F using intrinsic typing: the syntax tree of a term is indexed by its type, so only well typed terms can be constructed.

The problem I have is that, I would like to use PHOAS to model a dependently typed calculus. Having terms and types be in the same syntactic category means that (as far as I can see) the extrinsic approach is not feasible: we can't have $term\ (V : Set) :  term \to Set$.

I'm wondering if there has been any work done on using PHOAS to model extrinsically typed languages: that is, where our syntax allows ill-typed terms to be formed, and we have a separately defined relation between telescopes, terms and types, i.e. traditional $\Gamma \vdash t : T$ typing rules.

In particular, I'm unsure how to model a term whose free variables all come from the given telescope. PHOAS uses $Term_0 = \forall V . term\ V$ to model closed terms, and $Term_1 = \forall V . (V \to term\ V)$ to model terms with one open variable. How can I generalize this to arbitrary telescopes? Should my typing rules refer to $term$s or $Terms$?


texts: Optimal scheduling with delay constraints

texts:
Suppose you have $K$ servers numbered $\{1,2,...,K\}$. Playing server $i$ provides a value of $v_i > 0$. However, once you play server $i$, you are not allowed to play it for the next $n_i$ time-slots. Assuming you have a time-horizon of $T \gg K$ time-slots, what is the optimal scheduling strategy to play the servers in terms of collecting the maximum total value.

There is a chance that this problem is well-studied but I cannot find any references, nor can I solve it trivially.  Any help would be appreciated. I know that the greedy strategy of playing the available server with the highest value is not optimal.


texts: Typed Lambda Calculus models and denotations

texts:
I'm trying to draw a general mental picture about the models and the
denotational semantics of the typed lambda calculus, in its different
variants.

I'm particularly interested in how the semantics changes according to:

which forms of recursion are allowed, and
which forms of polymorphism are allowed.

I understand that, even if one makes a precise choice about these
options, there are many possible models.  Still, I would like to pick
a few concrete examples (or even one) for each option, and draw them
in my mental picture. Of course, the simplest the better.  I feel
that, at my current stage, I do not benefit much (yet) from abstract
descriptions such as "take any such-and-such category" when I do not
have any idea about how to craft at least one of those.

Since the topic is quite broad, let me ask a specific question:

What would you study next? References are welcome.

Here's what I have seen so far:

The STLC has a very simple set-theoretic model. Just interpret basic
types with sets, products with cartesian products, etc. Boring but
simple. Can be generalized to arbitrary CCCs.
STLC + term-level recursion / fixed points. This is essentially
PCF. We can build models using CPOs ($\omega$CPOs or DCPOs or
...). They are not fully abstract, but I'm not concerned with that.
To compute fixed points, Kleene's fixed point theorem saves the day.
PCF + type-level recursion. Here things start getting
non-trivial. To solve type-level recursive equations, we can
translate these to recursive domain equations, and solve them by
lifting the Kleene $\omega$-CPO machinery at the domain level.
Essentially, monotonic functions become functors, continuous
functions become continuous functors, and suprema become colimits.
Some issues arise since $\rightarrow$ is contravariant on its first
argument, but restricting the categories at hand to
embedding-projections pairs (which to me look like a special case of
Galois connections) one can make everything covariant.
Adding predicative polymorphism. By this, I mean allowing types like
$\prod_{\tau:\sf Mono} T(\tau)$ where $\sf Mono$ is the set of monomorphic
types, which do not contain such products. In such way, the product
is a countable one, hence a small one, so we can take the related
product on the CPOs for monotypes without any size issues. Shallow,
but simple.
Adding impredicative polymorphism, as in System F. Here
$\prod_{\tau:*}$ ranges over all the types, including polymorphic
ones. I'm not sure about how to proceed here. Types are still
countable, but we can't simply relate to a polymorphic type $\tau'$
the product of some selected CPOs as before, since such product would also involve
the CPO of $\tau'$ itself, which we are defining.
Adding dependent types. Ultimately I'd like to understand how a
dependently typed semantics can be given for a language featuring
unrestricted term-level recursion, and possibly type-level recursion
as well. I tried to read about fibered categories, but I think I'm not yet ready to tackle those, so I'm looking for some smaller steps, first. I will try again in the future, though.


texts:
In compressed sensing, the goal is to find linear compression schemes for huge input signals that are known to have a sparse representation, so that the input signal can be recovered efficiently from the compression (the "sketch").  More formally, the standard setup is that there is a signal vector $x \in \mathbb{R}^n$ for which $\|x\|_0 < k$, and the compressed representation equals $Ax$ where $A$ is a $R$-by-$n$ real matrix where we want $R \ll n$.  The magic of compressed sensing is that one can explicitly construct $A$ such that it allows fast (near-linear time) exact recovery of any $k$-sparse $x$ with $R$ as small as $O(k n^{o(1)})$. I might not have the parameters best known but this is the general idea.

My question is: are there similar phenomena in other settings?  What I mean is that the input signal could come from some "low complexity family" according to a measure of complexity that is not necessarily sparsity.  We then want compression and decompression algorithms, not necessarily linear maps, that are efficient and correct.  Are such results known in a different context?  What would your guess be for a more "general" theory of compressed sensing?

(Of course, in applications of compressed sensing, linearity and sparsity are important issues. The question I ask here is more "philosophical".)


texts:
I have an undirected graph $G = (E,V)$, $|V|=n$,
where each node $v_i$ has a natural number weight.
Think of these weights as heights $h_i$.
Given two nodes $s$ and $t$, I'd like to find a lowest simple path between $s$ and $t$,
a path whose average height is minimal among all simple paths.
If $\rho = (s{=}v_1, v_2, \ldots, v_{k-1}, v_k{=}t)$ is a path,
its average height is $(h_1 + \cdots + h_k)/k$.
The path $\rho$ must be simple, i.e., no vertex repeated.

I am not seeing an efficient algorithm. If it helps, assume $G$ is planar.


texts: Is there any good literature on the computational complexity of function problems?

texts:
There are some cstheory questions that touches function-problems. Like this:
Complexity class corresponding to sorting

So here is the question: Is there good literature about the computational complexity of functions problems? Especially, but not limited to that, about functions-problems with polynomial space bound.


texts: I was looking into multigraphs recently and I couldn't find a simple "goto" model for generating random multigraphs along the lines of the ER model of simple graphs. Specifically, I was hoping to find a model where some type of probabilistic sampling is repeated, generating a binomial degree distribution. I assume one would extend the ER process in some way but I can not seem to find any results around it. To be clear, I am not interested in extending the configuration model into a multigraph model, which has been done and is straightforward. Does anyone have any pointers? Thank you


texts:
Suppose we have a regular language specified by a regex, for example, (ab|ac)* and we wish to find an equivalent regex with the minimal number of symbols, (a(b|c))*. Is there any efficient way to do this? From what I've read, minimizing the number of states in a DFA is easy, but minimizing a NFA is PSPACE-Complete, and I'm not sure which if either of these it falls under. If it's not tractable, are there any good approximation algorithms or special cases under which it can be done efficiently?

Note: By minimizing the number of symbols, I mean the number of times symbols in the alphabet (a,b,c in the example) appear in the regular expression. The number of parenthesis, | and *s don't matter.

Motivation - this idea comes from the challenge of minimizing program code size, given that if and while statements are the only allowable control flow. The possible paths through the control flow graph correspond to a regular language, with if being union, while being the Kleene star, and symbols representing primitive statements that don't transfer control.


texts: Set data structure for efficient repeated insertions

texts:
I'm looking for a space-efficient data structure that holds sets (no repetition) of wordsize elements and supports fast insertion (amortized O(1)).  By "space-efficient" I mean, ideally, $n + o(n)$ words to store $n$ elements.

Being a set is an important part of the question: if each element is added $\log n$ times the space used can't be $n\log n$.

The structure should also support listing its elements (reasonable efficiently); any sane structure should have no trouble here.  (Fast membership queries are a plus.)


texts:
Are type theories with equality reflection (i.e. having a term of an identity type between two objects allows us to freely swap them) but not the $\eta$-rule for $\Pi$-types interesting?
Does function extensionality have to hold in such a type theory?


texts: Is there an algorithm for minimizing an NFA with respect to bisimilarity rather than language equivalence?

texts:
DFA minimization is the problem of transforming a given automaton to an equivalent one with the minimum number of states.
Equivalence is taken to be language equivalence.

Milner introduced the notion of bisimilarity, and in his book on the $\pi$-calculus, he motivates bisimilarity by first studying it as an equivalence relation on (states of) finite automata (interestingly non-deterministic ones).

So, has there been any study of the problem of minimizing an NFA with respect to this equivalence relation, bisimilarity (say of initial states), instead of equivalence of the recognized language?


texts: Determinant of a generalized Vandermonde matrix

texts:
Moore matrix is similar to Vandermonde matrix but has a slightly modified definition.
http://en.wikipedia.org/wiki/Moore_matrix

What is the complexity of computing the determinant of a given $n \times n$ full rank Moore matrix modulo some integer?

Can Moore determinant be reduced from $O(n^{3})$ using FFT techniques to $O(n\log^{a}n)$ for some $a \in \mathbb{R}_{+} \cup \{0\}$?

Is complexity of Moore det modulo an integer and Vandermonde det the same?
Complexity of Vandermonde determinant is $O(n\log^{2}n)$ (Page 644 in Handbook of Theoretical Computer Science: Algorithms and complexity By Jan Leeuwen)

Post similar to the current one: Determinant modulo m


texts: Confidentiality of "partial private keys" in certificateless public key crypto

texts:
I'm looking at alternatives to PKI and I'm having trouble understanding exactly how certificateless public key algorithms (e.g. Al-Riyami and Paterson, Liu et al) work in practice.  It seems like the "partial private key" generated by the KGC in these systems is not actually confidential information (which would be awfully convenient for practical use of the system), but if it isn't, then I don't understand why the KGC and its master secret are necessary.

(I hope this isn't too "practical" a question for this site.)


texts: $\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More generally, a standard one-way function can be viewed as an average-case-hard (search) problem in $\mathbf{NP}$ relative to $\mathbf{P}$. Can this notion be extended to two arbitrary complexity classes?


texts: Strategies for preventing isolated nodes in a dynamically changing undirected cyclic graph

texts:
I'm building a mesh network where i need to detect the unexpected disappearance of a peer.

Each node attempts to stay in communication with at least X peers. A node refuses connection from another peer if it already has at least Y neighbours. Nodes communicate the IP addresses of their peers on every connection attempt. If a peer disconnects, it will be noted by keep-alives from its neighbours and the disconnection message will make its way around the network.

I'm a little worried about the case where there are two large clusters of nodes with a single node in the middle. If the sole 'bridge' node between two clusters disappears, the clusters will retain out-of-date information about peers in the other cluster.

Are there values of X and Y i can choose, or replacement strategies for choosing peers to connect to, such that this behaviour is made impossible or very unlikely? i.e. There are always at least two paths between any pair nodes.

I expect the network to grow to such a size where walking every edge is infeasible..


texts: What is the difference between System F and Hindley-Milner type system?

texts:
Hindley-Milner type system is some restriction of System F, which allows type inference.

But from simple descriptions I cannot see, what is the difference between them?


texts: What is the computational complexity of Acyclic Joins?

texts:
I am quite new to relational algebra, but I realize that there are efficiency proofs for processing Acyclic joins. I have not been able to understand these results, but this particular problem is quite interesting to me. Given the following table, say $R_i$, $i \in \{1..n\}$

\begin{array}{|c|c|c|}
\hline
A_{i}& A_{i+1} \\ \hline
0 & 0 \\ \hline
0 & 1 \\ \hline
1 & 0 \\ \hline
1 & 1 \\ \hline
\end{array}
Now, I want to evaluate $R_{1}\bowtie_{A_2}R_{2}\bowtie_{A_3} ... R_{n-2}\bowtie_{A_{n-1}}R_{n-1}$, which is going to be a table with attributes $A_{1} .. A_{n}$ and $2^{n}$ rows(Basically resembling a Truth table). What is going to be the computational complexity of evaluating this join, given that it is an acyclic, K-uniform join ? Also, are there any gaurentees for cyclic joins which are of the form as I mentioned above (i.e same the column names keep changing but the table attribute remain the same for ex. AB,BA,AC)


texts: Major conjectures used to prove complexity lower bounds?

texts: Complexity theory uses a large number of unproven conjectures. There are several hardness conjectures in David Johnson's NP-Completeness Column 25. What are the other major conjectures not mentioned in the above article? Did we achieve some progress towards proving one of these conjectures? Which conjecture do you think would require completely different techniques from the currently known ones?


texts: Is clique-width preserved under edge contractions?

texts:
Let $G$ be class of graphs with bounded clique-width. In each graph in $G$ some edges are contracted (e.g. randomly). Is now the clique-width still bounded?

In case it is (in general) no longer bounded, I would be very interested in a counter-example.


texts: Formalizing the theory of finite sets in type theory

texts:
Most proof assistants have a formalization of the concept of "finite set".  These formalizations, however, differ wildly (although one hopes that they are all essentially equivalent!).  What I don't understand at this point is the design space involved, and what are the pros and cons of each formalization.

In particular, I would like to understand the following:

Can I axiomatize finite sets (i.e. types inhabited by a finite number of inhabitants) in simple type theory?  System F?  What are the drawbacks of doing it this way?
I know it can be done 'elegantly' in a dependently typed system.  But, from a classical point of view, the resulting definitions seem extremely alien.  [I am not saying they are wrong, far from it!].  But I do not understand why they are 'right' either.  I understand that they pick out the correct concept, but the deeper reason for 'saying it that way' is what I do not fully grasp.

Basically, I would like a reasoned introduction to the design space of formalizations of the concept of 'finite set' in type theory.


texts: The existence of planar distance preserver?

texts:
Let G be an n-node undirected graph, and let T be a node subset of V(G) called terminals.  A distance preserver of (G,T) is a graph H satisfying the property

$$d_H(u,v) = d_G(u,v)$$

for all nodes u, v in T. (Note that H is NOT necessarily a subgraph of G.)

For example, let G be the following graph (a) and T be the nodes on the external face. Then graph (b) is a distance preserver of (G,T).

Distance preserver with various parameters are known to exist. I'm particularly interested in the one with the following properties:

G is planar and unweighted (that is, all edges of G has weight one),
T has size $O(n^{0.5})$, and
H has size (the number of nodes and edges) $o(n)$. (It would be nice if we have $O(\frac{n}{\log\log n})$.)

  Does such a distance preserver exist?

If one cannot meet the above properties, any kind of relaxations are welcomed.

References:

Sparse Source-wise and Pair-wise Distance Preservers, Don Coppersmith and Michael Elkin, SIDMA, 2006.
Sparse Distance Preservers and Additive Spanners, Béla Bollobás, Don Coppersmith, and Michael Elkin, SIDMA, 2005.
Spanners and emulators with sublinear distance errors, Mikkel Thorup and Uri Zwick, SODA, 2006.
Lower Bounds for Additive Spanners, Emulators, and More, David P. Woodruff, FOCS, 2006.

Distance preserver is also known as an emulator; many related work can be found on internet by searching the term spanner, which requires H to be a subgraph of G. But in my applications we can use other graphs as well, as long as H preserves the distances between T in G.


texts: Satisfiability problems with restricted (not bounded) number of occurrences per variable

texts:
Intro

It is known that SAT is hard even when restricted to, e.g., formulas with exactly 3 literals per clause and at most 4 occurrences per variable. On the other hand it is easy if there are exactly 3 literals per clause and at most 3 occurrences per variable. I am interested in other restrictions on the number of occurrences per variable.

For a set $S$ of positive integers, define $(k,S)$-SAT to be the satisfiability problem restricted to boolean formulas with exactly $k$ literals per clause, and the number of occurrences of each variable is in the set $S$. For example $(3,\{1,2,3,4\})$-SAT is hard, $(3,\{1,2,3\})$-SAT is easy.

Sub-questions

If $k=3$ and $S$ is the even numbers, then you can easily pad an instance of $3$-SAT to get an equivalent instance of $(3,S)$-SAT. Is there anything known more generally? Is it always hard if $S$ is infinite? Are there any easy cases for $k=3$ besides $S\subseteq \{1,2,3\}$?

Main Question

I am really interested in 1-in-3-SAT restricted to the case where each variable appears an even number of times - the standard reduction from 3-SAT introduces new variables some of which occur an odd number of times. My feeling is that the problem should be NP-hard. Is there a suitable reduction from SAT? Or from normal 1-in-3-SAT? Or perhaps some sort of dichotomy theorem I don't know about that can be applied?

Edit

The answer to my question as stated is that the problem is indeed hard, because you can simply copy all clauses of a 1-in-3-SAT instance. I now insist that the clauses should not be repeated (we can efficiently preprocess an instance of SAT so that there are no repeat clauses after all)


texts: Proof that circuit upper bounds for $E$ imply $P \neq NP$

texts:
In the official Clay problem description for P versus NP it's stated that $P \neq NP$ would follow from showing that "every language in $E$ [the class of languages recognizable in exponential time with a deterministic Turing machine] can be computed by a Boolean circuit family $<B_n>$ such that for at least one $n$, $B_n$ has fewer gates than the maximum needed to
compute any Boolean function $f: \{0,1\}^n \longrightarrow \{0,1\}$." However, the only reference is that this "is an intriguing observation by V. Kabanets." Could someone please point me to a published version of this implication with the proof?


texts: Computing input length on a one-tape Turing machine

texts:
In connection with this question it occurred to me to wonder: what is the time complexity
for a single-tape single-head Turing machine to compute the length of its input? To be specific, let's say that the tape alphabet is $\{0,1,b\}$, the input is a string in $(0+1)^*$ surrounded by blanks, the machine starts at the leftmost input symbol, and it must terminate at the leftmost symbol of a string in $(0+1)^*$ (again surrounded by blanks) that gives the binary representation of the input length. This can also be thought of as the problem of converting a number from unary to binary.

It's easy to solve this on a two-tape machine or two-head machine in linear time (just scan the input with one head while using the other head to repeatedly increment a counter; incrementing is a constant amortized time operation). But the single-head solutions I can come up with are only $O(n\log n)$ (e.g. repeatedly increment a counter and then shift it by one position along the tape). Is there a matching lower bound?

I tried some searches but phrases like "one head" and "input length" are so common as to make it difficult to search the literature for known results on this problem.


texts: Is there an analysis of red-black trees using amortized analysis? I saw it mentioned somewhere as an example of amortized analysis but all the proofs that I know use a global approach ("black height") to demonstrate the O(log n) runtime of individual operations.


texts: Number of vertices at distance $k$ for each vertex of restricted sparse graph

texts:
My graphs has following restriction: undirected, connected, simple, unweighted,
and maximum degree of any vertex is 8. These are actually molecular graphs. Almost always maximum degree will be 4 but in some cases I have seen it to be 5 or 6, so I am keeping the limit as 8.Usually I will have around 100 vertices.

I want to compute for each verticex $v$, the number of vertices at distance $i$ from $v$. I found several reference to algorithm for all-pair-shortest-path problem of Floyd-Warshall type. However, i do not need the exact paths, and not even the distances.  These algorithms, can solve my problem, but they do more than what I want. For me time is very critical ( computation over millions molecules), so I want an algorithm which is optimal for above restrictions possibly at the cost of not being generalizable. Solution should be exact and deterministic. I would worry not just about the order of complexity but also of the constants.


texts: What's the relation between OOP and category theory?  Is there some related work on this topic one can read?


texts: A stronger multiplexing rule for soft linear logic?

texts:
In (intuitionistic) linear logic the usual rules for the storage modality $!$ are promotion, dereliction, contraction, and weakening:

$$\frac{!\Gamma\vdash A}{!\Gamma\vdash !A}(prom) \qquad \frac{\Gamma,A \vdash C}{\Gamma,!A\vdash C}(der) \qquad \frac{\Gamma,!A,!A\vdash C}{\Gamma,!A\vdash C}(ctr) \qquad \frac{\Gamma\vdash C}{\Gamma,!A\vdash C}(wk)$$

Lafont's soft linear logic is obtained by observing that these rules are equivalent to soft promotion, multiplexing, and digging:

$$\frac{\Gamma\vdash A}{!\Gamma\vdash !A}(sp) \qquad \frac{\Gamma,\overbrace{A,\dots,A}^n\vdash C}{\Gamma,!A\vdash C}(mpx) \qquad \frac{\Gamma,!!A\vdash C}{\Gamma,!A\vdash C}(dig)$$

and then removing the digging rule.  Soft linear logic (SLL) is interesting because it corresponds closely to polynomial-time computation in various precise senses.  For instance, Lafont showed that polytime functions are precisely those representable in second-order SLL in a certain sense, while  McKinley showed that they are also those representable in a naive set theory based on SLL, and lambda calculi based on SLL can also characterize polytime computation (plus other complexity classes when augmented with additional features).

My question is what happens if in SLL we replace the multiplexing rule (which is actually a rule schema consisting of one rule for each external natural number $n$) with the following "strong multiplexing" or "weak contraction" rule?

$$\frac{\Gamma,!A,A\vdash C}{\Gamma,!A \vdash C}\qquad (*)$$

(and also weakening, which is a special case of ordinary multiplexing but not of $(*)$)

Ordinary contraction says that we can use $!A$ as two $!A$'s — hence any number of $!A$'s, and hence any number of $A$'s — while ordinary multiplexing says that we can use $!A$ as any number of $A$'s as long as we do it all at once.  So, for instance, if we have $!A$ and two branches of a derivation both need some $A$'s, then ordinary contraction says we can give them both a whole $!A$, while ordinary multiplexing says we need to decide right away before doing the branch how many $A$'s each branch needs.

The rule $(*)$ seems to be in between: it says that from $!A$ we can extract any number of $A$'s and keep the $!A$ around, but we can't get more than one $!A$.  So if we have $!A$ and two branches of a derivation both need some $A$'s, then we can give one of them a whole $!A$ but we need to decide right away how many $A$'s the other branch needs.

The question "what happens" is admittedly a bit vague, but it could be made precise in various ways.  Is rule $(*)$ conservative over ordinary multiplexing?  Is contraction conservative over rule $(*)$?  Does SLL+$(*)$ still correspond to polytime computation, in any or all of the ways that ordinary SLL does?  Or does it correspond to some larger complexity class?  I would be interested in answers to any of these questions.

(My reason for asking is partly curiosity, but also partly practical: it could be inconvenient for some purposes that ordinary multiplexing is a rule schema indexed by external natural numbers, whereas $(*)$ is a single rule.)


texts: Using Kolmogorov complexity to establish proof complexity lower bounds?

texts:
The motivation for this question is the fact that most n-bit strings are incompressible. Intuitively, we can propose by analogy that most proofs for Tautologies are incompressible to polynomial size. Basically, my intuition is that some proofs are inherently random and can't be compressed.

  Is there a good reference on research effort related to using Kolmogorov complexity results to establish super-polynomial lower bounds on the proof size of Tautologies?

In this Ph.D. dissertation
On the Complexity of Propositional Proof Systems

  the Incompressibility method from Kolmogorov Complexity is used to obtain Urquhart's $\Omega(n/\log n)$ lower bound for a class of Tautologies. I wonder if there are stronger results using the Incompressibility method or other results from Kolmogorov complexity?


texts:
Let $s\in\Sigma^*$ be a string, for some alphabet $\Sigma$.
We want to find the most frequent repeated substring $q$ of $s$ such that its first character equals its last one, i.e. the most frequent repeated substring of type $q=aXa$ for $a\in\Sigma, X\in \Sigma^*$.

Can we solve this problem with standard techniques ? I'm thinking about suffix-trees here. What is the most efficient algorithm for this problem ?


texts: Closure properties of deterministic context-sensitive languages

texts:
There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages.

However, the literature is almost mute on the subject of the closure properties of deterministic context-sensitive languages. In fact, I have spend days looking for it on the internet and in the standard reference books about formal languages and theoretical computer science and didn't find anything complete or related enough to bother using and I wasn't able to find results let alone proofs for most properties myself either.

So, let $\mathbf{DCSL}$ denote the class of deterministic context-sensitive languages, then given two arbitrary languages $L_1, L_2 \in \mathbf{DCSL}$ and a regular language $L_R$, what are its closure properties under

union, $L_1 \cup L_2 \in \mathbf{DCSL}$
intersection, $L_1 \cap L_2 \in \mathbf{DCSL}$
set difference, $L_1 \setminus L_2 \in \mathbf{DCSL}$ (or $L_1 - L_2 \in \mathbf{DCSL}$ to remove ambiguities with left quotient)
complementation, $L_1^c \in \mathbf{DCSL}$
concatenation, $L_1 L_2 \in \mathbf{DCSL}$
Kleene star, $L_1^* \in \mathbf{DCSL}$
intersection with a regular language, $L_1 \cap L_R \in \mathbf{DCSL}$ (bonus)
left/right quotient with a regular language, $L_1 / L_R \in \mathbf{DCSL}$ and $L_R \backslash L_1 \in \mathbf{DCSL}$ (bonus)
reversal (bonus)
homomorphism, maybe $\lambda$-free homomorphism (bonus)
inverse homomorphism (bonus)
substitution, maybe $\lambda$-free substitution (bonus)

These are probably not all interesting closure properties of languages, but for now, I think they are enough.

Posting only results is acceptable, but providing proofs or counterexamples is definitely preferred.

To clarify the notion of deterministic context-free language: a language $L$ is deterministically context-sensitive, if there exist a formal grammar $G$ such that $L_G = L$ and all production rules of $G$ are unambiguous and consist of either growing[1] or strictly growing[2] context-sensitive substitution patterns.

Note: There are two slightly different kinds of unambiguous context-sensitive grammar classes and probably two slightly different kinds of deterministic context-sensitive language classes as well (unless they coincide, which I highly doubt since their nondeterministic counterparts don't), namely [1] and [2]. For the questions posed above, both are relevant and may yield different answers.

Note: AFAIK A (strictly) growing grammar/language is also called a (strictly) monotonic grammar/language by some authors

This question moved over from Computer Science beta


texts: Vertices adjacent to Exterior region of a Planar Graph(Algorithm)

texts:
Problem:
I am looking for an algorithm which finds all vertices that are adjacent to exterior region of a planar graph(For a planar graph, any region=face can be considered as the  exterior region /face).

Attempt:
Using the planarity check algorithm, an algorithm can be constructed with polynomial bound.

Questions:
My questions are-

Are there any literature /algorithms regarding the problem?
Can the problem have a log-space time algorithm (without using planarity check algorithm)?

Motivation: Trying to find the outer cycle of a  planar graph quickly to reduce the complexity of Hamiltonian circuit problem.


texts: How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts?

texts:
I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring nodes have. I would like to run this algorithm in parallel in the public cloud. Unfortunately, I cannot find a way to split my graph for maximum computation efficiency. All of my workers end up hitting the network to access neighbouring nodes. I need a way to split my graph to minimise network I/O between workers.

Ideally I want to split my graph into (approximately) balanced parts and minimize the number of edges crossing the parts.

I thought that ordering all nodes in some kind of 'locality-preserving' order is an option since I might not know upfront how many workers I have.


texts: Satisfiability for various branching programs

texts:
Clearly, SAT for CNF, formula, or many classes of boolean circuits have strong significance on the entire theory community.
Branching program, or BDD is one of the most basic and popular computational models for boolean functions. For instance, arbitrary space bounded TM with space $S(n)$ are simulated by  branching program of size $2^{S(n)}$.
My question is about  classification of hardness of $satisfiability$ problem for $branching$ $programs$.
More concretely,

Q1. SAT for branching programs corresponding natural complexity classes like $L/poly$, $NL/poly$, or $\oplus L/poly$ can be computed polynomial time ?
Q2. Is there some $threshold$ $condition$ for BP-SAT problem ? For example, I hope some results as follows: for some two classes of branching programs $\mathcal{C},\mathcal{D}$, one of two is polytime computable and the other one is NP hard.


texts: Sub-exponential algorithm for Hamiltonian cycle problem on cubic planar graphs?

texts:
There are several graph $NP$-complete problems that have sub-exponential time algorithm on planar graph instances.

What is the fastest algorithm for HC problem on cubic planar graphs? Is there a sub-exponential algorithm for this class of graphs?


texts: Deciding DDH based in partial information

texts:
Decisional Diffie–Hellman assumption, or DDH in short, is a famous problem in cryptography.
The DDH assumption holds on a cyclic group $(G,*)$ of (prime) order $q$, if for a generator $g \in G$, and for randomly chosen $a,b,c \in $\mathbb{Z}_q$$, the following pairs are indistinguishable (for probabilistic poly-time algorithms):

Type 1: $(g,g^a,g^b,g^{ab})$
Type 2: $(g,g^a,g^b,g^{c})$

Now, assume that $G$ is a group on which DDH is hard, and consider the following informal question:

  Do we know of a probabilistic poly-time (PPT) algorithm, which gets a Diffie-Hellman pair, along with some partial information about $a$ (say, $a$ is odd), and can correctly output whether the input pair is "Type 1" or "Type 2" (with non-negligible probability)?

By partial information, I mean a string $z$, such that given $z$ and a Diffie-Hellman pair, no PPT algorithm can compute $a$, with non-negligible probability.

It's possible to formalize the above question. However, since the amount of notation required is tedious, I try to use an analogy.

A famous, non-standard cryptographic assumption is called Knowledge-of-Exponent (KEA).

  For any adversary A that takes input $q$, $g$, $g^a$ and returns $(C,C^a)$, there exists
  an "extractor" B, which given the same inputs as $A$ returns $c$ such that $g^c = C$.

Intuitively, it states that, since the adversary cannot solve discrete log to obtain $a$, the only way to output a pair $(C,C^a)$ is to "know" the exponent $c$ where $g^c = C$.

Now, I'm asking a similar question, based on DDH (rather than discrete log): to distinguish "Type 1" and "Type 2" Diffie-Hellman pairs, should we "know" either $a$ or $b$?

A bit more formally (but still not fully formal):

  Let $(G,*)$ be a group of prime order $q$, and let $f(\cdot)$ be an arbitrary function whose output length is polynomial in the length of its input.
  Pick $a$, $b$, and $c$ randomly from $\mathbb{Z}_q$, and let $z=f(a)$.
  Toss a coin, and let $X = ab$ if the result is heads. Otherwise let $X=c$.

  For any PPT adversary A that takes input $(q,g,g^a,g^b,g^X,z)$, and correctly decides between Type 1 and Type 2 with non-negligible probability, there exists
  a PPT "extractor" B, which takes the same input as A, outputs either $a$ or $b$ (with non-negligible probability).


texts: What are the open ended questions for an CS Undergraduate to think about?

texts:
What can be a possible open ended research topics in Computational Complexity (or something equally fun), for an undergraduate to think about?

[I am planning to take up something fun, however my objective is not to publish a paper, but just to think about it for the joy of the subject :) , but of course, if a paper comes along, that might be fun as well...

P.S. I have taken basic courses in Theory of Computing, Algorithms, Advanced Algorithms, Advanced DS and Discrete Mathematics among others.]


texts:
Consider the following problem:

Input: the vertices of two $n$ dimensional axis-parallel cubes:
$\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and
$\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$.

Let

$P = \{ \vec{p} \in \times_{i=1}^{n} [a_i,b_i] : ||\vec{p}||_1 = 1\}$,
$X = \{ \vec{x} \in \times_{i=1}^{n} [l_i,u_i] : ||\vec{x}||_1 = 1\}$,
$W = \{ \vec{w} \in [0,1]^n : ||\vec{w}||_1 = 1\}$,

where $||\vec{v}||_1 = \sum_{i=1}^n v_i$.

Query: for all $\vec{p} \in P$
there are $\vec{x} \in X$ and $\vec{w} \in W$ such that
$x_iw_i=p_i$ for all $i = 1, \ldots, n$?

What is the complexity of this problem?


texts: What is the complexity of computing optimal prefix free codes, when the frequencies are similar?

texts:
It is well known that there is a worst case optimal algorithm to compute the Huffman code in time $\theta(n\lg n)$. This is improved in two orthogonal ways:

Optimal prefix free codes can be computed faster if the set of distinct frequencies is small (e.g. of size $\sigma$): sort the frequencies using [Munro and Spira, 1976] so that to take advantage of the small value of $\sigma$, and compute the Huffman tree in linear time from the sorted frequencies. This yields a solution in $O(n\lg\sigma)$
There is an $O(n 16^k)$ algorithm to compute equivalent codes where $k$ is the number of distinct codewords lengths [Belal and Elmasry].

Is there a way to combine those techniques, in order to improve on the current best complexity of $O(n\min\{16^k,\lg\sigma\})$?

THE $O(nk)$ RESULT FROM STACS 2006 SEEM TO BE WRONG, Elmasry published on ARXIV in 2010 (http://arxiv.org/abs/cs/0509015) a version announcing
     - $O(16^kn)$ operations on unsorted input and
     - $O(9^k \log^{2k-1} n)$ operations on sorted input

I see an analogy with the complexity of computing the planar convex hull, where algorithms in $O(n\lg n)$ (sorting based, as the $O(n\lg n)$ algorithm for Huffman's code) and in $O(nh)$ (gift wrapping) were superseded by Kirkpatrick and Seidel's algorithm in $O(n\lg h)$ (later proved to be instance optimal with complexity of the form $O(nH(n_1,\ldots,n_k)$). In the case of Prefix Free codes, $O(n\lg n)$ versus $O(nk)$ suggests the possibility of an algorithm with complexity $O(n\lg k)$, or even $O(nH(n_1,\ldots,n_k)$ where $n_i$ is the number of codewords of length $i$, using the analogy of an edge of the convex hull covering $n_i$ points to a code length covering $n_i$ symbols.
A simple example shows that sorting the (rounded) logarithmic values of the frequencies (in linear time in the $\theta(\lg n)$ word RAM model) does not give an optimal prefix free code in linear time:

For $n=3$, $f_1=1/2-\varepsilon$ and $f_2=f_3=1/4+\varepsilon$
$\lceil\lg f_i\rceil=2$ so log sorting does not change order
yet two codes out of three cost $n/4$ bits more than optimal.

Another interesting question would be to reduce the complexity when $k$ is large, i.e. all codes have distinct lengths:

for instance when $k=n$ the frequencies are all of distinct log value. In this case one can sort the frequencies in linear time in the $\theta(\lg n)$ word RAM, and compute the Huffman code in linear time (because sorting their log values is enough to sort the values), resulting in overall linear time, much better than the $n^2$ from the algorithm from Belal and Elmasry.


texts:
In 1978 Willem H. Haemmers published "An upper bound on the Shannon capacity of a graph".

Tims has a survey of more recent results his thesis.

What is the computational complexity of computing Haemmer's minimum rank function?


texts: Distributed file storage system - theoretical approaches

texts: What are the main theoretical approaches to a distributed file storage system that allows files to be stored across a network of nodes, assuring their availability in case a node randomly loses connection, but without replicating the entire tree in each node (as in git)?


texts: Total flow using minimum number of edges on a bipartite network

texts:
If I have a set of sources $S$ with total capacity $C$ and a set of sinks $T$ with the same capacity $C$, but not necessarily the same cardinality, is there an efficient way to find the minimum number of direct edges between sources and sinks and their required capacity, assuming $flow=C$?

TIA, Luis


texts: Resource listing models with known VC dimension

texts:
Is there any reference resource gathering models with known VC dimension? I am looking for an exhaustive list of models with their VC dimension (and ideally the associated proof or a pointer to it).

It would be in the same spirit as the Complexity Zoo, which gathers most of the known complexity classes, or the textbook Computers and Intractability, which catalogues many NP-Complete problems.


texts: Convergence of Q-learning with non-linear function approximation

texts:
Q-learning is a well-known algorithm in Reinforcement learning which enjoys great empirical success but with insufficient theoretical understanding. In the tabular setting, it is known that if each state-action pair $(s, a), \forall s \in \mathcal{S}, \forall a \in \mathcal{A}$ is visited for infinite number of times.

In the function approximation setting, however, the algorithm is not known to be convergent. There are some counterexamples where it diverges, under various assumptions. I was wondering if Q-learning with nonlinear function approximation could converge if each state-action pair is visited for infinite times. If not,  I wonder if there is any convergent variation of Q-learning algorithm that uses nonlinear function approximation.


texts: Regular expressions: Finding "negation" of regular expression?

texts:
Given regular expressions containing only (,),|,* and characters of an Alphabet A, how can I find the "negation" of a regular expression i.e.:

<R1> is a regular expression
<R2> = A*\<R1>

where A* are all the words you can produce with A and <Ri> the words accepted by the regular expression Ri.

Given R1, how can I find R2? Is there any algorithm to do that?

Thank you!


texts:
Suppose we have a string stream over alphabet $[n]$. At each step, we would like to compute a sketch of the last $k$ elements, such that from the sketch we can approximate their relative order. For simplicity, we can assume that the previous $k$ elements are unique. Moreover, we want the time complexity of the sketch to logarithmically depend on $n$ and sublinearly on $k$. (with linear dependency on $k$ means we can just compute and store the ranks)

More formally, let $s_1, s_2, ...$ be the stream of integers $s_i\in[n]$. At time step $t$ we want to sketch order statistics of $S_t:=[s_{t-k+1},...,s_{t-1},s_{t}]$. Because the elmenets are unique we can uniquely view them through their rank $[r_1,...r_k]$ such that $r_i\in[k]$ is the rank of element $s_i$ in $S_t$. Now let $\tilde{S}$ be the sketch of $S$ which we use to recover approximate rank vector $[\tilde{r}_1,...\tilde{r}_k]$. Let $\sum_{r_i<r_j} 1_{\{\tilde{r}_i>\tilde{r}_j\}}$ be the error function, which counts pairs that their order is reversed. There are other ways to measure sketching error, namely $\sum_i |r_i-\tilde{r}_i|$. As long as an error function captures how close two rank vectors are it is acceptable.

What is the lowest sketching error (average or worst case) we can achieve while maintaining complexity constraints on $n$ and $k$? Ideally, the method would demonstrate a trade-off between the error and dependency on $k$.
Is there any link between this problem and frequency moment sketching?


texts:
What does it mean that some problem is undecidable?

For instance the halting problem.

Does it mean that humans can never invent a new technique that always decides whether a turing machine will halt?

If not, what techniques are allowed such that halting problem is still undecidable?

For instance induction is a good technique, why cant one discover some new technique?

I have trouble understanding how some new invention cannot solve the halting problem.

Given some computer and a program, is there really insufficient information stored in it to determine if it will halt?

It seems like a purely mechanical problem


texts: Lower bound of real valued bounded function

texts:
Is well known that the lower bound on number of example necessary to reach a given error for concept classes $\Omega(d/\varepsilon)$ (cf. also
Agnostic PAC sampling lower bound
)
I am looking for the lower bound of example necessary to define a real value bound function as PAC learnable, given a VC dimension, bound and precision.
I have found in this '92 paper by Haussler some bounds for finite and infinite sets some bounds. E.g. for a finite set of $|F|$ bounded function $0 \leq f \leq M$, theorem 1 states that
$$ m \geq \frac{M^2}{2\epsilon^2} \left( \textrm{ln}|F| + \frac{2}{\delta}\right),$$
with probability $\delta$. Where $m$ is the number of training examples needed, and $\epsilon$ is defined as the "regret", that is the difference between the optimal and empirical risks.
I was wondering:

if there is a result regarding the optimal risk as well and evaluate the total risk, like for the concept classes bounds
if there are new results regarding these bounds for real-valued functions.


texts: The quantum capacity of a trace-decreasing CP map

texts:
Assume a qubit quantum channel (trace-preserving CP (==completely positive) map) $\mathcal{N}:C^2\to C^2$ whose quantum capacity is known. Now I construct a new channel $\mathcal{M}:C^2\to C^{2+n}$ where $n>0$:
$$
\mathcal{M}=p\mathcal{N}\oplus(1-p)\mathcal{C},
$$
where $\mathcal{C}$ is an arbitrary channel $C^2\to C^n$, whose form I don't need to know, and $0\leq p\leq1$. Assume that I have access just to the two-dim output subspace of $\mathcal{M}$ given by the image of $\mathcal{N}$. So effectively, I constructed a new CP map $\mathcal{M'}:C^2\to C^{2}$ that is trace-decreasing (since $p\leq1$).

Here is my question:
What si the quantum capacity of $\mathcal{M'}$ ?

Here is my answer:
Irrespective of $n$, I can assume that $\mathcal{M'}$ can be written as
$$
\mathcal{M'}=\mathcal{E}\circ\mathcal{N},
$$
where $\mathcal{E}:C^2\to C^3$ is a qubit erasure channel
$$
\mathcal{E}(\rho)=p{\rho}\oplus(1-p)\rho_{fixed},
$$
where  $\rho_{fixed}$ is an input-independent positive operator (density matrix) spanning a one-dimensional subspace. Hence, the quantum capacity of $\mathcal{M'}$ is the minimum of the quantum capacities of $\mathcal{N}$ and $\mathcal{E}$ (known as the bottleneck inequality).

EDIT
Following Shor's comment I wanted to say that the quantum capacity of $\mathcal{M'}$ will be bounded from above by the quantum capacities of $\mathcal{N}$ and $\mathcal{E}$.

Do you agree?


texts: Non-interesting numbers via resource-bounded properties?

texts:
There is an old joke about the smallest non-interesting number being interesting in itself (I have heard it attributed to Richard Hamming).  This is then used to justify the argument that every number must be interesting.  I have always found this induction unsatisfactory.

Here is an attempt at a more precise argument.  Consider a set of rules, represented as sentences of some logic.  The interesting numbers are then the smallest numbers that are models of some set of sentences.  In first-order logic each natural number can be distinguished from every other one, so the sentences true for any natural number will differ from those true for any other, and every number will be interesting.

Now suppose our rules are given in terms of a bounded model of computation, so that only finite sets of properties can be associated with each number, and so that every property can be checked with a bounded amount of some resource (for instance, time or space).

  Is every number still interesting with resource-bounded properties?

Edit: to clarify, resource bounds is my focus here.  With unbounded resources this devolves into a question about definability and large ordinals, as discussed by Aaron and Kaveh.  The idea is that each interesting number should be definable by a sentence that can be checked given a bounded amount of resources.  (It might also make sense to allow some finite set of sentences as separate building blocks instead of making them into single sentences via conjunction.)


texts: Type inference with subtype constraints and polymorphism using Trifonov and Smith's constraint maps

texts:
Trifonov and Smith's Subtyping Constrained Types (1996) introduces constraint maps to represent consistent closed constraint sets (such maps providing sets of lower and upper bounds to each variable in their domain), and canonical constraint maps for which each variable has exactly one constructed upper and one constructed lower bound. They note that constraint maps and canonical constraint maps have potential as an implementation technique.

However, the work I am familiar with on algorithms for polymorphic type inference in the presence of constraints (essentially, Pottier and Rémy's The essence of ML type inference, and the range of research cited therein -- also see Simonet's Type inference with structural subtyping, and Odersky, Sulzmann and Wehr's Type inference with constrained types) does not appear to use the constraint map representation.

Have Trifonov and Smith's constraint maps been put to use in any published works (or actual implementations in the wild)? Were there any obstacles to doing so, or was this line of research simply not pursued?