texts: Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?

texts: Consider an connected undirected graph $G$ with $n$ vertices and maximum degree $\Delta$. Assume $G$ contains a maximum independent set of size $k$. Is there any relation between the chromatic number $\chi(G)$ and $k$? Say of the form $\chi(G)\le f(\Delta)\frac{n}{k}$ for some function $f$?


texts: Validity of exponentiation in a polynomial time reduction

texts:
I asked this question 10 days ago on cs.stackexchange here but I didn'y have any answer.

In a very famous paper (in the networking community), Wang & Crowcroft present some $\mathsf{NP}$-completeness results of path computation under several additive/multiplicative constraints. The first problem is the following :

Given a directed graph $G=(V,A)$ and two weight metrics $w_1$ and $w_2$ over the edges, define, for a path $P$, $w_i(P)=\sum_{a\in P}w_i(a)$ ($i=1,2$). Given two nodes $s$ and $t$, the problem is to find a path $P$ from $s$ to $t$ s.t. $w_i(P)\leq W_i$, where the $W_i$ are given positive numbers (example: Delay constraint and cost in a network).

The authors prove that this problem is $\mathsf{NP}$-complete by providing a polynomial reduction from PARTITION.

Then they present the same problem except that the metrics are multiplicative, i.e., $w'_i(P)=\prod_{a\in P}w'_i(a)$. In order to prove the multiplicative version is $\mathsf{NP}$-complete, they provide a "polynomial" reduction from the additive version just by putting $w'_i(a)=e^{w_i(a)}$ and $W'_i=e^{W_i}$.

I am very puzzled by this reduction. Since $W'_i$ and $w'_i(a)$ are part of the input (in binary, I guess), then the $|w'_i(a)|$ and $|W'_i|$ are not polynomial in $|w_i(a)|$ and $|W_i|$. Thus the reduction is not polynomial.

Am I missing something trivial or is there a flaw in the proof? My doubt is about the validity of the proof, even if the result is clearly true.

Paper reference : Zheng Wang, Jon Crowcroft. Quality-of-Service Routing for Supporting Multimedia Applications. IEEE Journal on Selected Areas in Communications 14(7): 1228-1234 (1996).


texts: Implementable algorithm for Voronoi regions with obstacles

texts: I'm looking for an algorithm that computes the Voronoi regions of a set of points contained in a polygonal region with obstacles.  What would be the most simple, straightforward way to implement this?  For each region, I need an explicit description of the boundary, that is, the union of line segments and hyperbolic arcs that compose it.  I'm aware that there are fast algorithms for this problem in the sense of running time (e.g. http://dl.acm.org/citation.cfm?id=161156 ) but I'm more interested in one that's easy to implement.  To be honest, I'm not even sure how to find an easy algorithm for finding the shortest path map for this problem.


texts: The average number of compressible strings in a random set of random strings

texts:
In the book Elements of Information Theory (p.446), it is stated:

...although there are some simple sequences, most sequences do not have simple descriptions. Similarly, most integers are not simple. Hence, if we draw a sequence at random, we are likely to draw a complex sequence. The next theorem shows that the probability that a sequence can be compressed by more than k bits is no greater than 2−k.

[snip latex Theorem and Proof]

Thus, most sequences have a complexity close to their length. For example, the fraction of sequences of length n that have complexity less than n − 5 is less than 1/32.

So, the answer I'm looking for looks something like:

For some given set and string length, for a random set of random strings, the number of compressible strings in that set will be on average X percent of that set.

Where X may be 0.0001% or 0.00002193487% or 0.000000009% or something more specific.


texts: Terminology for complete k-partite graph where k is not fixed

texts:
Is there a better term for "complete k-partite graph" in the case where k is not fixed?  If I say "complete k-partite graph", people tend to assume "for some particular k".

In other words, what's a term for any graph for whom each connected component in the complement graph is a clique?

I asked this before, but it was as part of another question, so it was ignored.


texts: Is there an efficient program for generating a Sidon sequence?

texts:
I would need a Sidon sequence of about $10^9$ elements.
I found math papers like [1] that explain how to generate Sidon sequences but it seems a lot of pain to write the corresponding program.

Are you aware of any existing program that generates a dense enough and large enough Sidon sequence ?

Extra: my real constraint for the sequence is $a+a′ , a \lt a′ ,~ a,a′ ∈ A$ instead of the true Sidon sequence property $a+a ′ , a ≤ a ′ , a, a ′ ∈ A$.
So a Sidon sequence would do the job but I could hope for a denser sequence by tuning the program.

[1] Javier Cilleruelo, "Infinite Sidon sequences", eprint on arXiv: http://arxiv.org/abs/1209.0326


texts: Star seperators to explain computational complexity of algorithms on a class of graphs?

texts:
A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be easily shown to be imperfect yet the mathematical programming implementation of several supposedly np-hard problems return optimal solutions in near instant time for problems with very large size (millions of nodes, millions of edges). Does there exist some explanation in terms of graph decomposition to explain this?

Tarjan in his paper "decomposition by clique separators", various methodologies in using clique separators for combinatorial optimization problems. This is done using the divide and conquer paradigm. Clique separator decomposition seems to allow easy calculation of conventionally hard problems for certain graph classes which yield a clique separation tree with atoms of basic structure. Another decomposition, the tree decomposition where we map a graph to a tree that follows a set of 3 properties, is one for which certain NP-hard optimization problems become more easily solvable (in the complexity sense) and basically linear time for a bounded width on the bags of the decomposition tree.

The class of graphs for which I am working with do not yield clique separators nor do they seem to have an easy tree representation.  I wanted to ask if there existed some methodology (in terms of decomposition maybe?) to explain the behaviour that I have encountered in the same vein of those above. For graphs that possess some other type of special structure to those previously mentioned. For context, I am neither a graph theorist or computer scientist so have very little competence in this stuff, I am actually an engineer working on a complex design problem which can, in a sense, be reduced down to maximum independent set on the class of graphs explained below:

The most I have been able to achieve is that if we let $G = (V,E)$ be a graph of the class, there always exists a partition with a star cut-set/separator which lets call $S$ whose deletion $G/S$ results in 2 disconnected sub-components $A$ and $B$ where $A$ is a clique and $B$ $U$ $S$ is either connected and possesses a star separator or is a clique. Basically, the graphs can always be represented in a way by a binary decomposition tree where the leaf atoms/nodes are all cliques and the articulation vertices are star separators. $K$ is a clique


texts:
A problem instance is a finite list of 4-tuples $(\alpha_1, u_1, v_1, \beta_1), ..., (\alpha_N, u_N, v_N, \beta_N)$, where $\alpha_i, \beta_i \in X$ come from a finite set, and each $u_i,v_i \in A^*$ are words over a finite alphabet $A$.

A solution to the problem is a sequence of indices $i_1, i_2, ..., i_K$ such that

For all $1 \leq k \leq K-1$, we have $\alpha_{i_k} = \beta_{i_{k+1}}$.
The words $u' = u_{i_1} u_{i_2} \cdots u_{i_K}$ and $v' = v_{i_1} v_{i_2} \cdots v_{i_K}$ are not prefixes of each other

That is, an instance is like an instance of PCP, but with restrictions on how "dominoes" can be composed, and instead of finding strings that are equal, we need strings that differ by at least one symbol.

It is not immediately obvious to me how to decide this problem, and I have not been able to find an example of it in the literature.

Update: Origin of the problem

Given a finite state transducer over input/output alphabets $\Sigma, \Gamma$ and with initial state $p^{-}$, two states $q_1, q_2$ are said to be twinned iff for all $u,v \in \Sigma^*$ and $y_1,y_2,z_1,z_2 \in \Gamma^*$ if

$$ p^{-} \stackrel{u/y_1}{\to} q_1 \stackrel{v/z_1}{\to} q_1 \text{ and } p^{-} \stackrel{u/y_2}{\to} q_2 \stackrel{v/z_2}{\to} q_2$$

then either $z_1=z_2=\varepsilon$ or $|z_1|=|z_2| \neq 0$ and one of $y_1, y_2$ is a prefix of the other. [Weber & Klemm, Economy of description for single-valued transducers, 1995]. This is equivalent to the "algebraic" definition given in [Berstel, Transductions and Context-free languages, 1979].

There are effective procedures for deciding whether all states are twinned or not. I am interested in computing all pairs of states that are not twinned. Applying the method of squaring transducers [Beal, Carton, Prieur, Sakarovitch, 2000], this reduces to deciding the problem in my question for all pairs of states.


texts: Is this multiprocessor scheduling problem with overlaps NP-Hard?

texts:
The problem statement is: "Given a set $J$ of jobs where job $J_i$ has length $L_i$ and a number of processors $m$, jobs have inter-overlapping (For example, if job $J_i$ and $J_k$ are assigned to the same processor, then the length of $J_i$ and $J_k$ is less than $L_i+L_k$), what is the minimum possible time required to schedule all jobs in $J$ on $m$ processors."

Is the above problem NP_hard? I'd be happy to get a reference or a description of a reduction.

Thanks!


texts: Can programming help one understand constructive mathematics?

texts: I have read about the principles of constructive mathematics, for example, the principle of excluded middle is not allowed, and now I want to do some exercises to increase my understanding of the subject. As a student in computer science, I have a background in programming, and I was wondering if programming in a language like Haskell would help in this endeavor? If not Haskell, then which programming language is best suited for learning constructive math?


texts: Does it help for clique if the vertices are partitioned into 3 cliques?

texts:
A graph is $(p,q)$-colorable if its vertices can be partitioned
into $p$ cliques and $q$ independent sets.
For $(2,0)$-colorable graphs clique is polynomial.
I am interested how easier (if any) is clique in $(3,0)$-colorable,
when the partitions are given.
Given graph $G$ and 3 partitions of its vertices
$A,B,C : A \cup B \cup C=V(G)$ such
that $A,B,C$ induce cliques in G.

Q1 Is clique faster in this case?
Q2 If it is faster what is the complexity?
Q3 How good can we approximate clique in this case?

We have a clique $\frac{V(G)}{3}$ for free.


texts: Reference request: reducing rank computations to characteristic polynomials over arbitrary rings

texts:
Question. I'm looking into certain algorithms for linear algebra which lie in NC2. Does anyone know of alternative references for the proof of the proposition just below, relating rank of matrices over R to characteristic polynomials over R(x)?

  Proposition. Let A be an m×n matrix in a ring R, and let R(x) be the extension by a formal indeterminate x. Define the matrices
  $$\begin{align*} A' &= \begin{bmatrix} 0 & A \\ A^{\mathsf T} & 0 \end{bmatrix}, & X &= \mathrm{Diag}(1,x,x^2,\ldots,x^{m+n-1}), & B &= XA'\,.\end{align*}$$
  Then rank(A) ≤ r for some integer r ≥ 0 if and only if the characteristic polynomial det(B − t I) of B is divisible by t 2(m+n−r).

Context. The proposition above is a standard result which allows decision problems about the rank of a matrix A to be reduced to those about the characteristic polynomial of B. A convincing proof of the proposition for the case that R is a finite field can be found in Mulmuley's article A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Because the degree of the formal indeterminate x can be bounded in det(B − t I), we can reduce this problem to a problem of polynomials over R alone.

While Mulmuley's proof breaks down for any ring that has nilpotent elements (such as 2 in the rings ℤ2k ), Allender + Beals + Ogihara claim (in their article The complexity of matrix rank and feasible systems of linear equations) that this proposition (or rather a result which I've paraphrased in the result above) holds generally for any ring, and is shown in the book chapter

  J. von zur Gathen. "Parallel linear algebra". In J. H. Reif, editor,
  Synthesis of parallel algorithms, (pp. 573–617). Morgan Kaufmann,
  1993.

which in any case is (or was) widely referenced in the literature. Unfortunately, I can't seem to locate a copy of it (physically embodied or otherwise) that does not require an investment of about $50, and a couple of weeks for shipping and handling, for the entire textbook.

Can anyone provide an alternative reference, or possibly show me where to find an inexpensive electronic copy of the one book chapter? I would be satisfied with any widely available standard text on abstract algebra which proved this proposition, for example.


texts: Can the Hungarian method be used with real edge weights?

texts:
I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method but all of them expect a cost matrix of non-negative integers as input.

Moreover, I even looked at the pseudo code given in Figure 11-2 of Combinatorial Optimization: Algorithms and Complexity by Papadimitriou & Steiglitz. Even there, the pseudo code expects as input, cost matrix of non-negative integers. From what I understand of the algorithm, there shouldn't be any such restriction. Am I missing something here?


texts: Category theory, computational complexity, and combinatorics connections?

texts:
I have been trying to read “Pearls of Functional Algorithm design”, and subsequently “The Algebra of Programming”, and there is an obvious correspondence between recursively (and polynomially) defined data types and combinatorial objects, having the same recursive definition and subsequently leading to the same formal power series (or generating functions), as shown in the introductions to combinatorial species (I read “Species and Functors and Types, Oh My!”).

  So, for the first question, is there a way to recover the generating (recursive) equation from the power series? That’s an afterthought though.

I was more interested in the notion of initial algebras and final co-algebras as kind of “defining procedures about the data structure”. There are some practical rules in functional programming, concerning composition, products of mapping between algebras and similar, described for example in this tutorial. It seems to me that this could be quite powerful way to approach complexity and for example, it looks fairly straightforward to recover Master’s theorem in such context (I mean, you have to do the same argument, so not much gain in this instance), and the unique catamorphism from the initial algebra and the fact (am I mistaken?) that the algebras between A and FA for F-polynomial functor are isomorphic, makes it look to me that such approach could have a lot of benefits in analysing complexity of operations over data structures.

From practical standpoint, looks like fusion rules (basically, ways to compose algebra morphisms with one another, coalgebra morphisms, and general morphisms) are very powerful optimization technique for program transformation and refactoring. Am I right in thinking that full utilization of these rules can produce optimal program (no unnecessary intermediate data structures or other extra operations).

  Am I onto something (and what) here? Is it beneficiary (from learning standpoint) to try to look about computational complexity in this way? Are the structures, for which we can have "nice" initial algebras somehow too limited for some problems?

I’m mostly trying to find a way to think about complexity in terms of the structure of the search space and the way the "search space" and "search algorithm" interact through some "nice" object like the initial algebra of the functor and to understand if it's useful to try to view things this way, when looking at more complicated structures.


texts: Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion Question

texts:
I am reading the paper "Kernelizations for Parameterized Counting Problems", and had a question regarding some of the notation in the paper (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8295&rep=rep1&type=pdf).

In section 4, the author begins by defining the notion of a crown as follows:

Let $\mathcal{G} := (V, E)$ be a graph. A crown in $\mathcal{G}$ is a bipartite subgraph $\mathcal{C} = (I, N(I), F)$ of $\mathcal{G}$ satisfying the following three conditions.

$I$ is an independent set in $\mathcal{G}$ and $N(I)$ is the set of all neighbours of vertices from $I$ in $\mathcal{G}$.
$F$ contains all of the edges of $E$ that connect vertices from $I$ to $N(I)$.
$\mathcal{C}$ has a matching of cardinality $|N(I)|$.

In then goes on to define a few other pieces of notation. Let $\mathcal{G} - \mathcal{C}$ be the graph obtained from $\mathcal{G}$  by deleting all of the vertices in $\mathcal{C}$ and all edges incident to vertices in $\mathcal{C}$. Also, let $S_\mathcal{C}$ be a vertex cover of $\mathcal{C}$ and let $\mathcal{G}' := (V', E')$ be the graph obtained from $\mathcal{G} - \mathcal{C}$ by deleting all edges covered by vertices in $S_\mathcal{C}$.

What confuses me here is the difference between $\mathcal{G} - \mathcal{C}$ and $\mathcal{G}'$. Since the vertex cover contains only vertices in $I$ or $N(I)$, when removing $\mathcal{C}$ from $\mathcal{G}$, haven't we already removed all of the edges that can be covered by vertices in $S_\mathcal{C}$? It would seem to me that the edges in $\mathcal{G} - \mathcal{C}$ do not have any vertices that are incident, making it identical to $\mathcal{G}'$. Where is the error in my reasoning/understanding?

Thanks!!


texts: Describing a grammar and associated parser

texts:
In the process of writing a Turing machine simulator, I decided on a machine representation in ASCII that closely mirrors Turing's original machine tables. I am interested in the formal categorization of the grammar and the simplest type of parser required to implement it, and in a more formal description of same. The grammar is as follows:

<instruction> ::= <ident> "," <symbol> "," <operation> "," <ident> <EOL>
      <ident> ::= <char>
      <symbol ::= <char> | 'None'
  <operation> ::= <movement> | <write> <movement>
      <write> ::= 'P' <char> | 'E'
    <movement ::= 'R' | 'L'

An example Turing machine table written in this grammar is as follows:

b, None, P0R, c
c, None, R,   e
e, None, P1R, f
f, None, R,   b

It is clear to me that since this grammar is expressible in BNF, it must then be at most context-free, but is there a more accurate (more strict) categorization? The lack of left-recursion implies that it could be parsed with a recursive descent parser, but is there a simpler parser that would be capable of this grammar? How would one describe this grammar and its (simplest) associated parser?


texts: Hardness of additive approximation to Graph Coloring problem.

texts:
In paper Approximation Algorithms for the Chromatic Sum, page 18, authors state that based on the fact that the Graph Coloring problem is hard to approximate with a ratio less than 2 (under the assumption of $P \neq NP$), it's easy to show that for any constant $k$, there is no approximate algorithm $A$ to Graph Coloring such that $\chi(G) \leq A(G) \leq \chi(G) + k$.

But i can't see how to show/prove this.

As i see, it isn't so direct, because for any $k$, there are graphs such that $\chi(G) \leq k$, so for them $\chi(G) + k \geq 2 \cdot \chi(G)$ and it would be $(2 + \epsilon)$-approximative, for some $\epsilon \geq 0$, for these graphs.

So i'm asking for some help/advice on how to show/prove this.


texts: Factoriality testing algorithms and their efficiency

texts: How efficiently can we decide that a number $P$ is the result of the factorial of another number $N$ (i.e. $P = N!$)? Notice that $P$ and $N$ are both integers and we are only given $P$.


texts: Threshold Fully Homomorphic Cryptosystems

texts:
recently, Craig Gentry published the first public key encryption scheme (over plaintext space {0,1}) which is fully homomorphic, meaning that one can efficiently and compactly evaluate AND and XOR on encrypted plaintexts without knowledge of the secret decryption key.

I am wondering if there is any obvious way to turn this public key cryptosystem into a threshold public key cryptosystem such that everybody can encrypt, AND and XOR, but decryption is only possible if some (all) people sharing the key team up.

I would be interested in any ideas about that subject.

Thanks in advance

fw


texts:
I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real solution of the relaxation of the problem. Lets consider vertex cover (VC) as an example. VC can be stated as finding an optimal integer solution of the following set of linear equations:

We have zero/one valued variables $x_v$s for each vertex $v \in V(G)$ of the graph $G$. The equations are: $0 \leq x_v \leq 1$ for $v\in V(G)$, and $1 \leq x_v+x_u$ for each edge $uv \in E(G)$. We are looking for values which will minimize $\sum_{v \in V(G)} x_v$.

The relaxation of this problem allows real values between $0$ and $1$ so the space of solutions is larger and an optimal real solution can be smaller than an optimal integer solution we want to find. Therefore we need to perform a "rounding" process on the optimal real answer obtained from linear programming to find an integer solution. The optimal integer solution will be between the optimal real solution and the result of the rounding process. IG is the ratio of an optimal integer solution to an optimal real solution and does not say anything about the rounding process. The rounding process can (in theory) completely ignore the real solution and compute the optimal integer solution directly.

  Why are people interested in proving bounds on IG?


texts: Number of solutions to the biclique cover problem

texts: Given a bipartite graph and the number bicliques K, how many ways exist to solve the biclique cover problem using K (possibly empty) bicliques?


texts: Distinguishing permanent from false value

texts:
We are given a matrix $M$ with $0/1$ entries and the matrix is square of $n$ dimensions. We are given two integers $a$ and $b$ with promise one of the values is the permanent.
Is there a faster than $2^{\Omega(n)}$ algorithm to identify the correct permanent of the two values of $a$ and $b$ (output $0$ means $a$ is correct and putput $1$ means $b$ is correct) and is there a complexity class for this problem?
We might assume the lower $n-n^\alpha$ bits of $a$ and $b$ are identical at an $\alpha\in(0,1)$.


texts: What are different definitions of Universal Turing-machine?

texts:
I am not sure what is the appropriate way for this, but I would like to collect different possible definitions/variants of Universal Turing-machines.
Here are the ones I know, post below if you know other definitions/comments/don't agree.
For simplicity, I assume that we talk about two-tape machines with alphabet {0,1,*}, but let me know if in some definition this might make a difference.
I denote by T(x,..,z) the output of Turing-machine T when the inputs on its tapes are x,..,z, if it halts, and "running forever" otherwise.

Exists. U is universal if for every T there is a p such that for every x we have U(p,x)=T(x).

Computable. U is universal if there is a computable encoding E of Turing-machines (labeled directed graphs) into strings such that for every T and x we have U(E(T),x)=T(x).

Fix. Fix a (computable) encoding E of Turing-machines into strings. U is universal if for every T and x we have U(E(T),x)=T(x).

Strict. In both the Computable and the Fix definition, we can also demand that for every input that is not of the above format, U does nothing useful (halts without output, outputs the empty string, or runs forever).


texts: Required delta between proceedings and journal versions

texts:
I am recently getting my papers rejected from journals (i.e., TALG) on the mere basis of not having a significant difference between the journal and proceedings (i.e., SODA) version.

The main reasons for me to submit to a journal is its thorough review process.
Other than that, SODA's 20 page limit is more than enough for all that I want to say. In fact, David Johnson has repeatedly asked the SODA crowd to not "save stuff for the journal version".

Any advice?


texts: Consensus on P = NP in a world where RP = NP

texts:
$RP = NP$ is widely conjectured to be false.

But imagine for a moment that it is true. In such case, how likely would be that $P = NP$?

Put in other words: in a world where $RP = NP$, what might still be seen as an obstacle for us to believe $P = NP$?


texts:
I'm trying to under stand the paper On p-Optimal Proof Systems and Logic for PTIME. There is a notion called proof systems in the paper and I do not get the intution:

  $\Sigma = \{0,1\}$ ... We identify problems with subsets of $Q$ in $\Sigma^*$.

I think the intution is that we encode a certain structure in $\Sigma^*$ (e.g. undirected graphs) and subsets of these structures are problems (e.g. planar graphs).

  A proof system  for a problem $Q \subset \Sigma^*$ is a surjective
  function $P:\Sigma^* \to Q$ computable in polynomial time.

Now one possibilty is to say $\Sigma^*$ is the set of all possible models in a certain structure (e.g. all the undirected graphs). But that does not make sense because why should a undirected graphs be mapped on a subset? It could be encoded turing machines but this does not make sense either ...

Any ideas?


texts: NP-hardness of minimizing sum of complicated objective function

texts:
In our research, we faced the following problem optimization problem:

Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$;
an integer $m$.
Output: $P$, a partition of the pairs into $m$ nonempty classes,

such that the following objective function is minimized:

$$\sum_{C \in P}\left(
\left(\sum_{i \in C} d_i\hspace{-0.08 in}\right) \cdot
\left(\sqrt{\frac{ 2\log(4\sum_{i\in C} d_i)}{\sum_{i \in C}n_i}} +
 \sqrt{\frac{  \log(2\sum_{i\in C} d_i)}{\sum_{i \in C}n_i}}\hspace{.04 in}\right)\hspace{-0.04 in}
\right)$$
We think that the problem is NP-hard,
but we have not been able to prove this.

We tried to prove that it is NP-hard by reducing it to 3-Partition,
but we couldn't.

Is this problem NP-hard?


texts:
$(n + 1)$ points are required to uniquely determine a polynomial of degree $n$; for instance, two points in a plane determine exactly one line.

How many points are required to uniquely determine a computable function $f : N \rightarrow N$, given the length of a program that computes $f$ in a fixed language? (i.e. a bound on the Kolmogorov complexity of $f$).

The idea is that, at least theoretically, one could prove the correctness of a program by making enough tests.

If one has a program $P$ of length $L$ that computes $f$, there is a bound on the number of functions that can be computed with a source length of at most $L$.

Therefore one would "only" need to prove that:

$f$ can be computed with a source length $\leq L$
$P$ does not compute any other function computable in $L$ bytes or less (by testing)

This idea has probably no practical consequences (the bounds are surely bound to be exponential).


texts:
Definitions:

Let $n\in \mathbb N$ be an integer, and consider the field $\mathbb K=GF(2^n)$.

For $c\in \mathbb N$, let $S_c$ be a set of $n$ elements from $\mathbb K$ such that:

Every element $e$ from $S$ is balanced: its weight $|e|=n/2$ (there are as many $1$s as $0$s).
Every pair of distinct elements $e,e'\in S, e\neq e'$ are at distance a multiple of $c$. That is:
$$\forall (e,e')\in S^2, e\neq e', \exists k \in \mathbb N, |e\oplus e'|=k\cdot c$$

Observations:

If the set $S_c$ could contain 0, 1, or 2 elements, its construction is trivial.
For some values of $c$, there are no solutions.

Questions:

Does this set structure has a name?
Are there algorithms to construct $S_c$?
For fixed $(n,c)$, how many sets $S_c$ exist?
This question seems related to binary coding theory where the minimal distance is replaced by codewords evenly located in the space. Is there a way to express the problem into a code problem?


texts: About a random walk with constant spectral gap

texts:
The existence of a graph with certain strange-looking properties will imply a counterexample to something I am playing with. I'm stuck on figuring out whether such a graph can exist and so I thought I'd post it here as question.

Specifically, for any integer $n$, is it always possible to construct an undirected graph on $n$ nodes such that:

(i) the simple random walk on it has constant spectral gap?

(ii) there exist two vertices $i,j$ such that the stationary distribution at both of them is lower bounded by a constant and the hitting time from $i$ to $j$ is at least linear in $n$?

More formally, the question is as follows. Given an undirected graph $G$, the simple random walk is the Markov chain which  transitions to a uniformly random out-neighbor at each step. Let $P$ be its probability transition matrix and $\pi$ be its stationary distribution, i.e, $\pi^T P = \pi^T$.

Do there exist positive constants $\alpha, \beta, c$ such that:

i) For each $n$, there exists an undirected graph on $n$ vertices for which the corresponding matrix $P$ satisfies $\lambda_2(P) \leq 1-\alpha$.

ii) In the same graph, there exist nodes $i,j$ such that $\pi_i \geq \beta$, $\pi_j \geq \beta$ and the hitting time from $i$ to $j$ is at least $cn$?

I suspect that this is not possible.


texts:
Wondering if we can prove the following or if it is already proved where can I get the proof.

Let $v_1, v_2, v_3, \ldots, v_n$ and $t$ be $n+1$ vertexes in a directed graph. $v_1, v_2, v_3, \ldots, v_n$ form directed acyclic graph. $t$ is connected to each and everyone of $v_1, v_2, v_3, \ldots, v_n$. Now since $v_1, v_2, v_3, \ldots, v_n$ are connected in an acyclic manner, if there is a cycle then it will involve $t$. Can we show that all cycles of length more then 3 will always involve a cycle of length 3? Remember $t$ is connected to every $v_1, v_2, v_3, \ldots, v_n$ and there is no pair wise cycle.

Are there any other similar problems with different wordings?
Thanks

I have probably not worded the question more clearly.

Say the acyclic directed graph of vertices $v_1, v_2, v_3, \ldots, v_n$ is $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow \cdots \rightarrow v_n$. Each $v$ has an edge to $t$. Say there is a cycle $t \rightarrow v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow t$. Such a cycle seems to surely involve a cycle of length 3 i.t either $t \rightarrow v_1 \rightarrow v_2 \rightarrow t$ or $t \rightarrow v_2 \rightarrow v_3 \rightarrow t$. But an not being able to proof this.


texts: Is $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?

texts: Is it known that $\textbf{BPP} \subseteq \textbf{P}^{\textbf{NP}}$?


texts: Time complexity with irrational exponent?

texts: Is there any natural problem in P for which the best known running time bound is of the form $O(n^\alpha)$, where $\alpha$ is an irrational constant?


texts: Complexity class associated with exhaustive search

texts:
What is the complexity class associated with exhaustive search algorithms? (if there is one)

Is it NP or PSPACE?

Are there restricted models of computation capturing the class of exhaustive search algorithms similar to models for greedy and dynamic programming?


texts: Minimal directed circles partition cover of a directed graph

texts:
We are given a $G(V,E)$ digraph and a $c:E \rightarrow \mathbb{R}$ weight function. We are searching for a set of $C_{1}(V_{1},E_{1}),C_{2}(V_{2},E_{2}),\ldots,C_{k}(V_{k},E_{k})$ directed circles such that $V_{1},\ldots,V_{k}$ form a partition of $V$ and $\sum_{i = 1}^{k}\sum_{e \in E_{i}}c(e)$ is minimal among all such covers.

I know there is a polynomial algorithm which solves this problem. I just don't know what that algorithm is. Anyone knows this problem and can give a hint or a solution?(hint preferred)


texts: Is it possible to convert a Max heap to a Min heap in place?

texts:
I was just wondering if this was possible?

Surely there maybe some naive methods of doing so, but I was just wondering if someone can suggest efficient ways to do so.


texts: Request for references on multicommodity flow-cut results

texts:
This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to cut (say, within a factor that is constant or polylogarithmic in the number of flows). Examples are:

1) Flow polytope (also called demand polytope) for multicommodity flow in undirected graphs is within O(log k) of cut as shown in

F. Leighton and S. Rao,“An approximate max-flow min-cut theoremfor uniform multicommodity flow problems with applications to approximation algorithms,” in Proc. of 28th Annual Symposium on Foundations of Computer Science, (Los Alamitos, California), 1988.

N. Linial, E. London, and Y. Rabinovich, “The geometry of graphs and some of its algorithmic applications,” Combinatorica, vol. 15, no. 2, pp. 215–245, 1995.

2) Demand polytope of multicommodity flow in directed graphs with symmetric demands is within O(log^2 k) of cut as shown in

P. Klein, S. Plotkin, S. Rao, and E. Tardos, “Bounds on the max-flow min-cut ratio for directed multicommodity flows,” J. Algorithms, no. 22, pp. 241–269, 1997.

3) Max sum-rate in groupcast is within a factor 2 of the multicut. (I don't know a reference for this result. Could someone help me with this? Thanks.)

I would like to know more such positive results affirming flow being close to cut assuming certain structure of the problem (such as undirectedness of graph or symmetric demands, as in above). It would be great if you can give me a one-line summary of the result(s) and a reference of the paper. Thanks.


texts: To what extent is anonymity through a Chaum mix compromised by using trusted mixes in the cascade?

texts:
As I understand it, a fundamental of Chaum's mix-net is that, absent an external adversary who can analyse traffic on links within the network, no mix can link the source and destination of any message unless it collaborates with every other mix participating in the cascade through which that message passes.

Most of the mix-net projects about which I have read (both those that have been implemented and those that remain theoretical) mitigate such a "collaboration attack" by introducing randomness into path selection: thus an adversary must collaborate with a significant proportion of all mixes throughout the network in order to achieve a high probability that those in any given cascade will all be collaborators.  Various techniques have been suggested to further frustrate an adversary who attempts to so bias the network, such as viewing all mixes on a single subnet as potential collaborators.

If one is certain (at least, as much as one can ever be) that some particular mixes are honest (i.e. not collaborating with an adversary), it would at first glance appear desirable to ensure that at least one such honest mix is included in every cascade used for one's messages so as to significantly reduce (if not completely eliminate) the threat of such "collaboration attacks".

However, forcing all one's messages to pass through a subset of the network that is defined by one's trust relationships leaks information about those relationships.  Over time, an adversary might be able to use such information to link together all one's messages or even identify oneself.

My question is: how can one measure this trade-off?  Is there existing research that already has considered it (I have not been able to find any yet)?

Where senders are themselves also acting as mixes in the presence of sufficient inbound cover traffic, does the inclusion of known honest mixes in downstream cascades for their own messages actually provide any additional anonymity given that those messages could arguably have been forwarded for another party?


texts:
I am looking for tutorial material that covers compiler correctness proofs, preferably using denotational methods, at the level of a beginning grad student.

Alternatively, do you know of some simple compiler examples that I could use to illustrate the issues?  (The first example that occurred to me was a translator from infix to postfix expressions.  But it failed to show anything interesting other than how to do induction on syntax.)


texts: Everyday encounters with NP-complete problems

texts:
Mark Dominus collected a few examples of polynomial-time reductions from various NP-hard problems to “regular expression” matching. Envisioning polynomial-time verifications isn't an enormous leap.

How do you illustrate the class NP-complete to undergraduates or to friends in other fields who wanted to understand the recent fuss over Deolalikar's paper?


texts: Checking whether two quadratic equations have a common zero

texts:
Given two quadratic equations (with integer coefficients):

$x^T A_1 x+ b^T_1 x + c_1=0$ and $x^T A_2 x+ b^T_2 x + c_2=0$

The problem is to decide whether they have a common zero.  Here $x$ is a vector of real numbers, i.e., we are looking for real solutions.

Q: what is the complexity of this problem?

What we know is that checking whether a family of quadratic equations has a common zero is $\exists R$-complete. However, the current question restricts the family size to be 2. A natural question arises: is this problem simpler, or remains to be $\exists R$-complete?

A related question is here: Zero of a multivariate cubic equation


texts: An explicit separation between time-constructibility and space-constructibility?

texts:
Show a function $f(n)$ which is space-constructible but not time-constuctible.

Is this problem related to a possible separation between complexity classes DTIME(f(n)) and SPACE(f(n))?


texts: Proving properties about a compilation from one problem into another

texts:
Say I have two problems A and B.

A is the shortest path problem with positive weights

B is the shortest path problem (with potentially negative weights)

I would like to show: There is no mapping m, from B to A such that for every instance I_B of B the exact solutions for m(I_B) is the same as for I_B.

What I would like to know is where can I find proofs of this kind?
How would you approach something like this?


texts: Worlds Relative to Which "Invulnerable Generators" Do Not Exist

texts:
Invulnerable generators are defined as follows:

Let $R$ be an NP relation, and $M$ be a machine which accepts $L(R)$. Informally, a program is an invulnerable generator if, on input $1^n$, it produces instance-witness pairs $(x, w) \in R$, with $|x| = n$, according to a distribution under which any polynomial-time adversary who is given $x$ fails to find a witness that $x \in S$, with noticeable probability, for infinitely many lengths $n$.

Invulnerable generators, first defined by Abadi et al., found many applications in cryptography.

Existence of the invulnerable generators is based on the assumption that $\mathbf{P} \neq \mathbf{NP}$, yet this is possibly not sufficient (see also the related topic).

Theorem 3 of Abadi et al. paper, cited above, shows that any proof of the existence of invulnerable generators does not relativize:

Theorem 3. There is an oracle $B$ such that $\mathbf{P}^B \neq \mathbf{NP}^B$, and invulnerable generators do not exist relative to B.

I don't understand a part of the proof of this theorem.
Let $\sqcup$ denote the disjoint union operation.
Let $QBF$ be the PSPACE-complete language of satisfiable quantified Boolean formulas, and let $K$ be an extremely sparse
set of strings of maximum Kolmogorov complexity. Specifically, $K$ contains one string of each length $n_i$, where the sequence $n_1, n_2, \ldots$ is defined by: $n_1 = 2$, $n_i$ is triply exponential in $n_{i-1}$, for $i > 1$; if $x \in K$ and $|x| = n$, then $x$ has Kolmogorov complexity $n$.

  The paper states that relative to $B = QBF \sqcup K$, it holds that $\mathbf{P} \neq \mathbf{NP}$. Can you explain? (Also, please clarify whether $B$ is recursive.)


texts: We have recently covered linear programming and I am comfortable with the weak and strong duality theorems.  However, I don't understand what the applications of duality are that are specific to TCS.  Mike Spivey's blog post gives some interesting examples of some nice properties of duality but I was wondering if there are algorithmic advances, for example,  that come from understanding duality or anything more CS related.


texts: Computation space of Nisan's generator for space bounded machines

texts:
This is probably a very trivial question. Suppose a space($S$) machine uses $R$ random bits. Then Nisan's PRG for space bounded machines can fool it using a seed of length $O(S\log (R/S))$. Theorem 1 in section 4 also mentions that this PRG can be computed in space $O(S\log R)$. This is due to the fact that we need to store $\log R$ many hash functions, each of $O(S)$ space. My questions is, can we say that the PRG can be computed in space $O(S\log (R/S))$ (to produce $R$ bits as above) as well in stead of $O(S\log R)$? That is, can we use just $\log (R/S)$ hash functions?

Reference paper: N. Nisan, Pseudorandom generators for space-bounded computation, Combinatorica, vol. 12, no. 4, pp. 449-461, Dec. 1992.


texts:
In the paper "On the complexity of some coloring games", Bodlaender gives some open questions about the complexity of deciding if player 1 or 2 has a winning strategy in some graph coloring games. Does anyone know if they have been solved?

1) In one game, two players take turns selecting one vertex in a graph and coloring it properly with a color from a fixed finite set. The loser is the first player who is unable to color a vertex. In Schaefer's paper it is shown to be pspace-complete with 1 color and Bodlaender shows it to be pspace-complete with 2 colors but gives no answer with more color. Is it still open?

2) In another variation, the vertices have numbers 1..n. On a player's turn he must properly color the vertex with the lowest number that has not yet been colored. Again, they are using colors from a fixed set and the loser is the first player who is unable to color his vertex. Bodlaender shows it to be pspace-complete for general graphs. He asks who wins on trees, is it known?

Thanks


texts: Ajtai's Proof of Theorem 1 in 'Generating Hard Instances of Lattice Problems'

texts:
My question pertains to the proof of Ajtai's main theorem in his groundbreaking 1996 paper, Generating hard instances of lattice problems, which indicates a connection between worst-case hard and average-case hard lattice problems.
This proof is  difficult for me to understand. Is there a clear exposition of this proof in the literature?


texts: Is modal $\mu$-calculus "equivalent" to bisimulation?

texts:
I know that propositional modal $\mu$-calculus $L\mu$ is bisimulation-invariant.  However, I'm curious to what degree it captures bisimulation.

Q1:  Given two labeled transition systems $T_1$, $T_2$ that are not bisimilar, is there an $L\mu$ formula which has $T_1$ as a model but not $T_2$?

Q2 (stronger):  What is a maximal class $\mathcal{C}$ of labeled transition systems such that given any $T \in \mathcal{C}$, there exists an $L\mu$ formula which has $T$ as its unique model in $\mathcal{C}$?

I hope this makes sense!  Basically I'm wondering to what degree I could replace discussion of transition systems with modal mu calculus formulas.  Thanks! :)


texts: reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs?

texts:
This is a question about the correct reference for a result that seems to appear frequently in the literature on planar graph isomorphism. In "A $V \log V$ Algorithm for Isomorphism of Triconnected Planar Graphs",
Hopcraft and Tarjan mention that a 3-connected planar graph has an essentially unique embedding into the plane (up to mirror symmetry), and attribute this result to Whitney (1933) "A set of topological invariants for graphs". I've noticed this citation reappearing in various places (for example here, here, and here), but I couldn't find the result in Whitney's article itself -- am I just overlooking something? The paper is dense, and builds on a series of other articles he published in succession... Still, this result sounds a lot like Theorem 11 of Whitney (1932) "Congruent Graphs and the Connectivity of Graphs", which states that a 3-connected planar graph has a unique dual. Was that the intended reference?


texts: How to iterate over vectors in order of probability in small space

texts:
Consider an $n$ dimensional vector $v$ where $v_i \in \{0,1\}$.  For each $i$ we know $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent.  Using these probabilities, is there an efficient way to iterate over binary $n$ dimensional vectors in order from most likely to least likely (with arbitrary choices for ties) using space sublinear in the output size?

Take for example $p = \{0.8, 0.3, 0.6\}$. The most likely vector is $(1,0,1)$ and the least likely is $\{0,1,0\}$.

For very small $n$ we could label each of the $2^n$ vectors with its probability and simply sort but this would of course still not use sublinear space.

A close variant of this question was previously asked at https://cs.stackexchange.com/questions/24123/how-to-iterate-over-vectors-in-order-of-probability .


texts:
The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not more than $B$ The goal is to minimize $s(S) - \sum_{k=1}^{m} s(S_k)$, i.e. the total value of leftover elements.

This is obviously strongly NP-complete as well. I am asking if anyone is aware of approximation/inapproximability results (other than the obvious nonexistence of FPTAS). I tried searching, but maybe I am not using the correct keywords.

EDIT: As pointed out in the comment below, there is no constant-factor approximation. Are there any (non-constant) approximation results?


texts:
Let $M=(\Sigma,S,s_0,\delta)$ be an (unknown) deterministic finite-state automaton (DFA), with alphabet $\Sigma$, statespace $S$, start state $s_0 \in S$, and transition relation $\delta$.  I want to explore $M$, i.e., visit every state of $M$, or as many states as possible.  Unfortunately, I'm not given $M$; I only have the ability to send inputs to $M$.

In particular, what I can do is specify some input strings $x,y,\dots \in \Sigma^*$.  The string $x$ will drive $M$ down some path, namely, down the sequence of states $s_0,s_1,s_2,\dots$ where $s_{i+1} = \delta(s_i,x_i)$.  I can specify as many input strings as I want.

The cost to me is the sum of the lengths of the input strings.  In other words, each transition costs me \$1.

The benefit to me is the fraction of $M$'s states that are visited at least once in response to at least one of these input strings.

I have complete freedom to choose the set of input strings, but I am not given any feedback (I can't see the sequence of states that $M$ follows, I don't learn when I've visited a new state, etc.).  I'm hoping to get as much coverage of $M$'s statespace as possible.

How should I choose the set of input strings to maximize the coverage while minimizing the cost?  For instance, given a fixed budget, what's the best set of input strings that will give the best benefit?  Is there a reasonable strategy, or any theory to help guide the choice of input strings?

Of course, I realize that the worst-case coverage, taken over all possible DFAs, might be very poor.  But I would be satisfied with any approach that one can argue is close to optimal, in any meaningful sense.  For instance, maybe one metric might be to use a regret ratio, where the regret of strategy 1 compared to strategy 2 is the maximum, over all DFA's $M$, of the benefit of strategy 2 on $M$ divided by the benefit of strategy 1 on $M$.  Or maybe you can suggest some other way to formulate this in a principled way that admits an interesting solution.  I'm open to suggestions about how to formulate the problem in a way that permits analysis.

If it's helpful, I'll promise that the alphabet is small (say, $|\Sigma| \le 10$), the number of states is not too large (say, $|S| \le 1000$), and the diameter of the graph is small (say, at most 10).

I'm also interested in the variant where $M$ is a NFA instead of a DFA, but I thought I'd start with the simpler case.

This is an attempt at an application of theory to practice.  The application is randomized testing of UI-driven applications, where we think of the application as a DFA and the inputs represent user actions (e.g., tapping on a particular portion of the screen).  The problem above is an idealization of the problem where we don't get any feedback as we go (which is motivated by the fact that it's not trivial to observe anything reliable about the state of the application).


texts: Paths and Probabilities for a Random Walk on a Graph

texts:
I'm working on a problem about $N$ nodes that are randomly positioned on a rectangular grid. I want to take a sample of $n\leq N$ nodes by randomly selecting the first node then visiting the nearest neighbour of the last selected node. Once a node is visited, it is excluded from future selctions. If a node has there multiple nearest neighbours, one is randomly picked among them.

I'm interested in the probability that a node is visited (I'm also interested in the probability that a pair of nodes appear in the same sample). I'm using the following population as an example: $$\{(-4,6),(0,5),(-3,4),(-2,4),(2,4),(3,4),(1,3),(5,3),(3,2),(2,1),(-1,0),(-3,1),(1,-1),(-4,-2),(-3,-2),(-1,-2),(3,-2),(4,-2),(2,-3),(4,-3),(2,-4),(4,-4),(5,-4),(-5,-5),(2,-5)\}$$

(Note: The numbers above the points are just identifying labels. They do not indicate anything about the order in which they are visited. A sample of three points would be something like $6 \rightarrow 5 \rightarrow 7$)

Here are my two approaches:

Enumerate all the possible paths of a specified length, calculate the probability of each path, then sum up the probabilities of the paths that include a particular node.
Repeatedly take samples then calculate the proportion of paths that include a particular node.

Is there a better way to solve my problem? By the way, I'm using R to do the computing.

I don't have any background in graph theory whatsoever. I'd like to look up terms and concepts that would be relevant to what I'm doing, but I'm not even sure where to begin. Do you have any ideas for a solution or do you know of any resources that can be understood by a novice?


texts: Problem dependent lower bound for stochastic bandits with full information

texts:
Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from that arm, but we get to observe a stochastic sample of the rewards of all arms.

This problem can be reduced to the stochastic expert setting, where the problem independent lower bound of $O(\sqrt{KT})$ is known, where $T$ is the time-horizon.

However, I am interested in a logarithmic regret lower bound that depends on the instance $\mu_1,...,\mu_K$ (similar to Lai and Robbins expression). Somehow I am not being able to find this in the literature. Any references would be helpful. It is known that the optimal algorithm is just following the highest estimated mean.


texts: Has this generalization of the vertex cover problem been researched?

texts:
I have the following problem, let's call it the $n$ vertex cover:

  Given a directed graph $G,$ find a minimum subset of vertices $S$ such that each trail of length $n$ has at least one vertex in $S$.

Has this problem been researched before? Is there a good way to approximate $S$?

A trail is a walk in which no edge appears twice, but vertices are allowed to repeat. I am also interested in variants where we consider paths or walks instead of trails.  Here $n$ is a small constant that is not part of the input; in my application, $n$ is probably something like 5.


texts: Is monotone 1-in-3 MAXSAT known to be APX hard?

texts:
Monotone 1-in-3 SAT is the problem where each clause of the SAT problem contains exactly 3 positive variables. The goal is to find an assignment such that exactly one variable is true in each clause and maximizes the number of clauses satisfied.

Is this problem APX hard? More importantly, is there a reference I can cite (or the result is folklore)?


texts: Is there a linear space lower bound for streaming set equality?

texts:
Consider two streams. In each stream one string arrives at a time.  A query asks: Is the set of strings that has arrived so far the same in both streams?

  Is there a linear space randomized lower bound for this problem?

If the sets of strings had been given in advance we could just sort them, remove duplicates, concatenate them in each set and then compute a random fingerprint of each of the two concatenated strings which can then be compared quickly using very little space (although there is of course no benefit as we first created something of linear size).

In the streaming case, we would need an updatable fingerprint it seems to do something similar.  I suspect this is not possible to do in sublinear space but I don't see a proof yet.


texts: Approximation factor when objective can be negative

texts:
In Williamson and Shmoys' textbook The Design of Approximation Algorithms they make the following assumption:

  We assume that there is some objective function mapping each possible solution of an optimization problem to some nonnegative value...

Vazirani makes the same assumption:

  Each valid instance...comes with a nonempty set of feasible solutions, each of which is assigned a nonnegative rational number called its objective function value.

What if my objective function can take negative values? Is there a standard way to deal with this? What if it is known that $-1$ is a lower bound?


texts: Speed-up of universal computation by caching

texts:
A universal computer is a program that can execute any other program. It is interesting to ask whether there are "booster" computers that execute programs faster than they execute "on their own". In the simplest sense of the question, the answer is negative, as can be seen by the following argument.

Suppose $V$ is a universal computer. Consider the following program $P$: "Run $V$ on my own source code. If it halts in less than $n$ steps, produce output which is different than the output of $V(P)$. Otherwise produce the output '0' (say)". It is clear that $V$ will take at least $n$ steps to execute $P$ and $P$ will execute in approximately $n$ steps on its own. So $P$ and $V(P)$ take approximately the same time.

However, what happens if we allow a pre-computed cache of arbitrary size? Formally, we consider a universal Turing machine with the addition of a special read-only tape on which an infinite computable bit-string $s$ is written in the initial state. Fix $U$ an "ordinary" universal computer program, i.e. $U$ doesn't use the special tape. The question is then

  Can we construct $V$ a program (using the special tape) and $s$ as above s.t. for any $U$-program $P$ if $U(P)$ halts in $t$ steps then $V(P)$ halts in at most $max(f(t), g(|P|))$ steps where $f \in o(t)$ and $g$ is computable?

Repeating the self-referential construction above only yields that the time complexity of $s$ has to be at least $f^{-1}$


texts: Complexity of transforming a balanced bipartite graph into regular graph?

texts:
I'm studying certain graph editing problems and I'd like to determine the complexity of this problem:

Input: Balanced bipartite graph $G(A \bigcup B, E)$, $|A|=|B|=n$, integer $k$

Problem: Is there $r$ edit operations that transform the input graph into balanced bipartite $n/2$-regular graph ($r \leq k$).

An edit operation can be an addition of one edge or a removal of one edge (between sets $A$ and $B$).

  Has anyone seen this problem in the literature? Is there a polynomial time algorithm or is it $NP$-complete?

My main interest is in the case where $k \leq cn$ for some constant $c \gt 0$.

EDIT: One way to look at the problem is to find the minimum number of edit operations that transform an input of balanced bipartite graph $G(A \bigcup B, E)$ into balanced bipartite $n/2$-regular graph $G(A \bigcup B, E^{'})$. Notice that $n$ must be even integer.


texts:
I recently got interested in data stream algorithms to the point that I'd like to study the topic and then teach it to someone.

I'd be thus grateful for pointers to really good sources on the topic, t.i. papers presenting major ideas in a particularly articulate way, papers with clever proofs of clever theorems, just good overviews of the state of the art, whatever.

My two cents:

Lecture notes from the Dartmouth University, 2009. This is the best source I've found so far.
Distributing Frequency-Dependent Data Stream Computations, described in my answer to a different (also mine) question.
The book "Data streams: algorithms and applications" (I haven't read it yet)


texts: Are there any applications of techniques in real analysis to theoretical computer science?

texts: I have looked far and wide for such applications and have mostly turned up short. I can find plenty of applications of topology and similar structures on countable (or uncountable) sets, but rarely do I actually find uncountable sets as the object of study by computer scientists, and therefore leading up to the need for techniques from analysis.


texts: It is well known that the complexity of distinguishing an $\epsilon$ biased coin from a fair one is $\theta(\epsilon^{-2})$. Are there results for distinguishing a $p$ coin from a $p+\epsilon$ coin? I can see that for the special case of $p=0$, the complexity will be $\epsilon^{-1}$. I have a hunch that the complexity will depend on whether $p$ is of the order of $\epsilon$, but can't prove so rigorously. Any hints/references?


texts: Parametrized Complexity of Counting Bicliques

texts:
In a previous question Parametrized Algorithm for Finding Bicliques, I inquired if there were fast parametrized algorithms for finding a $k\times k$-biclique in an $n$ vertex graph and learnt that it was open if it is FPT w.r.t. $k$. Is the same true for counting the $k\times k$-bicliques, or is it known that this is #$W\[1\]$-hard w.r.t. $k$ (or some other notion of hardness)?

I know that counting induced $k\times k$-bicliques are #$W\[1\]$-hard, expanding a simple reduction for finding an induced biclique in section 4.5 in Serge Gaspers' thesis.


texts:
Whenever I read a presentation of MLTT, especially in the context of the correspondence of MLTT with LCCCs (eg. Seely's paper), they say "the type constructors/formation rules are..." and then list a bunch of rules, and at least one of the rules will refer to terms. For example, in Seely, you have:

  If $F$ is a type-valued function constant, and $a_1, a_2, \dots a_n$
  are terms of the appropriate types, then $F(a_1, \dots , a_n)$ is a
  type.

And then after, you get the term formation rules, which refer to types. This is supposed to represent some sort of mutual induction, but if you naively interpret a paper as being a sort of short-hand for formal definitions and proofs in set theory + FOL, then the definition given is circular.

Later, you get,

  Let $C(M)$ be the category whose objects are all closed types of M, and morphisms $\mathrm{hom}(A,B)$ are closed terms of type $A \to B$.

A category consists of a set of objects (modulo size issues) and a set of morphisms between each object. Lets say for the sake of argument that I am skeptical that the mutual inductive definitions like Seely's actually give a well-defined set. How do you actually construct the sets of types and terms (more) formally in set theory, and convince me that these actually do form a set?

Not just for the sake of argument, I'm skeptical that the sort of dependent type theory that you can implement on a computer and program with is the same sort of dependent type theory that has this relationship with locally cartesian closed categories.


texts: Computing the most likely winner in elections : intermediate case between Kemeny and Borda?

texts:
Given

$n$ possible alternatives satisfying some unknown linear ordering,
a multiset of pairwise votes, i.e., a matrix $M\in\mathbb{N}^{n\times n}$:
$M_{i,j}$ counts the number of votes for which $i<j$.

I am interested in computing the most likely maximum when we assume that all linear orders have same prior probability, and that each vote reflects the true ordering with probability $p>1/2$ independently.

According to Young, APSR'88: Condorcet's Theory of Voting it has long been known that  for $p$ close to $1/2$ it is the Borda Winner (hence easy to compute), whereas for high enough $p$ it has been shown that the most likely maximum is a Kemeny Winner (hence computing a candidate is $P^{NP[log]}$ complete).

My main question is: what do we know for intermediate values of $p$? For instance, is there something like a dichotomy depending on $p$?

A side question is whether the complexity of the max-likelihood problem could for some $p$ be lower when the input vote matrix is restricted to those obtained by combining the votes of several rankings  (or whether there are results "of that kind" in some other natural settings).


texts: Is graph coloring complete for poly-APX?

texts:
Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for all vertices of the given graph.

The complexity class poly-APX contains all NP optimization problems that can be
approximated within a factor that is polynomial in the size of the
input. The notion of C-reducibility concerns approximation preserving
reductions, which keep the performance ratio of the feasible solutions
under consideration within a linear factor. For definitions regarding
approximation preserving reducibilities, see P. Crescenzi: A short guide to approximation preserving reducibilites, CCC '97.

EDIT (1.8.2014):
Somewhat related, I've found in the paper "on syntactic versus computational views of approximability" by Khanna, Motwani, Sudan and Vazirani (SICOMP 28(1):164-191) a remark stating that GRAPH COLORING and MAX CLIQUE are both in poly-APX-PB and interreducible (Remark 6 in that paper). I understand this is meant with respect to E-reducibility defined in that paper. Later, in the sketch of proof of Theorem 6 in that paper, I understand that they imply that MAX CLIQUE is complete for poly-APX-PB under E-reductions. I would also be grateful for a proof that GRAPH COLORING is complete for poly-APX-PB w.r.t. E-reducibility.


texts: Approximate 1d TSP with linear comparisons?

texts:
The one-dimensional traveling salesperson path problem is, obviously, the same thing as sorting, and so can be solved exactly by comparisons in $O(n\log n)$ time, but it is formulated in such a way that approximation as well as exact solution makes sense. In a model of computation in which the inputs are real numbers, and rounding to integers is possible, it's easy to approximate to within a $1+O(n^{-c})$ factor, for any constant $c$, in time $O(n)$: find the min and max, round everything to a number within distance $(\max-\min)n^{-(c+1)}$ of its original value, and then use radix sort. But models with rounding have problematic complexity theory and this led me to wonder, what about weaker models of computation?

So, how accurately can the one-dimensional TSP be approximated, in a linear comparison tree model of computation (each comparison node tests the sign of a linear function of the input values), by an algorithm whose time complexity is $o(n\log n)$? The same rounding method allows any approximation ratio of the form $n^{1-o(1)}$ to be achieved (by using binary searches to do the rounding, and rounding much more coarsely to make it fast enough). But is it possible to achieve even an approximation ratio like $O(n^{1-\epsilon})$ for some $\epsilon>0$?


texts: Generalizations of planar graphs that include hypercubes with large side length in $R^d$

texts:
A lot of people have asked about generalizations of planar graphs on other forums. Some topics include:

https://mathoverflow.net/questions/7650/generalizations-of-planar-graphs
https://math.stackexchange.com/questions/22714/higher-dimensional-analog-to-planar-graphs

Many have talked about minor-closed family generalizations of planar graphs, but they cannot possibly include even 3D n by n by n grids. If they did, then n by n by n grids would have to have balanced separators of size $n^{3/2}$, but in reality all of their balanced separators have size at least $n^2$. Qiaochu's definition focuses more on the direction that I am interested in. Ideally, I would like to look at graphs that are 1-skeleta of $(k-1)$-dimensional cell complexes that can be embedded in $\mathbb{R}^k$ injectively (which may be the same thing that Qiaochu is looking for). These are not minor closed for $k\ge 3$, but might be face-contraction closed.

Have these graphs been studied algorithmically? For example, can one generalize the planar separator theorem to these graphs? Or is there something particularly nasty about this definition that I am overlooking that prevents these objects from being algorithmically interesting?


texts: What is the background in algebraic geometry and representation theory needed for geometric complexity theory?

texts:
I'm a mathematics student in my junior year and I'm interested in computational complexity and specially geometric complexity theory. I'm going to learn algebraic geometry and representation theory but I want to consider the parts that are related to geometric complexity theory so I wonder What are the topics that should be mastered by someone who wants to understand geometric computational complexity?

Surely, a lot of algebraic geometry and representation theory are needed, but which topics? and representation theory of what? finite groups? lie algebras(probably not) etc? and which topics in algebraic geometry are needed? It would be great if it is possible to name some topics that are required to be well understood in algebraic geometry and representation theory to before tackling  geometric  complexity theory. naming good resources ( texts etc ) that cover this background will be highly appreciated too.

I have asked the same question on math stackexchange but got no answer, so I thought I should ask it here.


texts: Is there a Boolean formula that is resistant to bias from a polytime adversary?

texts:
I am studying Coin Flipping protocols in cryptography, and the complexity of problems related to this.

Here, a question has come to my mind: Does there exist a public coin, coin flipping protocol?. Usual coin flipping protocols (as invented by Manuel Blum) involve that one party hides its random value by a bit commitment, and later makes it public. The coin-function is then just an XOR of the two bits.

Is it possible to drop the bit commitment part, and instead put the "hardness" into the coin function (i.e. something much harder than XOR)?

In other words:

Does there exists a PPT uniform family of circuits $\phi(x_1,\ldots, x_k, y_1 \ldots, y_k)$ for $k\in \mathbb N$, such that there for any PPT adversary $\mathcal A$ exists a negligible function $\gamma(k)$,  such that the family of circuits (under certain computational assumptions) have the following properties:

$\Pr[\phi(U_X,U_Y) = 1] = \frac{1}{2}$, where $U_X, U_Y$ are uniform distributions on $\{0,1\}^k$
Consider the function as the output of the following protocol: Alice decides the $x_i$ bits, and Bob decides the $y_i$ bits, and Alice wants $\phi$ to be 1 and Bob wants 0, and the bits have to be published in order $(x_1, y_1, x_2, y_2 , \ldots, x_k, y_k)$. $\phi$ should be resistant to more than negligible bias, when applying $\mathcal A$ against opponent that choses its bits uniformly. In other words:

When the variables are chosen in the following manner: Let $x_1$ be chosen by $\mathcal A$. Let $y_1$ be chosen uniformly. Let $x_2$ be chosen by  $\mathcal A$ using the knowledge of $(x_1,y_1)$. Let $y_2$ be chosen uniformly, and so on. Then the expected outcome of $\phi$ should be within $\gamma(k)$ of $\frac{1}{2}$
The same should hold where the $x$'s are uniform and $y$'s are chosen by $\mathcal A$

As a remark, one can see that the truth of this statement:
$ \exists x_1 \forall y_1 \ldots \exists x_k \forall y_k : \phi(x_1, \ldots, x_k, y_1, \ldots, y_k)$
correspond to the fact, that there exists a strategy for Party 1 to bias completely by $\frac{1}{2}$.


texts: Algorithms for computing the minimal vertex separator of a graph

texts:
Background: Let $u,v$ be two vertices of an undirected graph $G=(V,E)$. A vertex set $S\subseteq V$ is a $u,v$-separator if $u$ and $v$ belong to different connected components of $G−S$. If no proper subset of a $u,v$-separator $S$ is a $u,v$-separator then S is a minimal u,v-separator. A vertex set $S \subseteq V$ is a (minimal) separator if there exist vertices $u,v$ such that $S$ is a (minimal) u,v-separator.

Is there some algorithm to compute the minimal vertex separator on a generic graph?

If I'm not interested in the smallest set but just in a set of separator vertices that disconnects $u$ from $v$ how can I do it?


texts: Gradient descent-like optimization on a convex landscape with noisy sampling

texts:
We have a strictly convex function $f(x,y)$ with a global minimum at $p_{min}$.
The goal is to approximate the minimum.
E.g.
$$f: [0,\pi]^2 \to \mathbb{R}$$
$$f(\theta,\phi) = t_1 \sin \theta + t_2 \sin \phi$$
where $t_1,t_2$ are constants in $\mathbb{R}^+$.

We want to find the best possible approximation for the minimum $p_{min}$,
but we only have noisy black-box access to the function $f$.

We can think of the setting as a game with two players Alice and Bob as follows:

Alice provides Bob a point $s$ such that $|s-p_{min}|<r$.
Bob provides Alice a point $p$.
Alice provides Bob information about the value of the function on $p$.
However, the information is noisy: Bob gets $v \sim f(p) + N(\mu,\sigma)$.

If Bob can pick $k$ points adoptively,
what would be an optimal strategy for choosing the points s.t.
the last one is as close as possible to the minimum?

On average, how well can Bob do?

What would be the dependency of the error on $k$?

If it simplifies things, we can use uniform distribution $U[a,b]$ in place of Gaussian distribution for noise.

The copy of the question on MathOverflow.


texts: Is the class NSC closed under complement?

texts:
The class $\mathsf{NSC}$ is defined as $\bigcup_{k\in\mathbb{N}}\mathsf{NSC}^k$, where $\mathsf{NSC}^k = \mathsf{NTIMESPACE}[\mathsf{poly},\mathsf{log}^k]$.
In a 1991 paper Mix Barrington and McKenzie ask the question of whether $\mathsf{NSC}^2$ is closed under complement.

Has there been any progress on that question for $\mathsf{NSC}$ in general or for particular values of $k$?


texts: Sorting array of distances by proximity to each other

texts:
I was playing with geolocation on maps and stumbled on an interesting problem:
I retrieve data from the db ordered by increasing distance from a user input, like a postcode or street, which makes sense as long as I don't use a combination of paging and map browsing, at which point the dataset no longer makes sense. Since the data on the map will be represented in concentric circles, if a user starts browsing the map needs to zoom out in order to accommodate for changing pages.
So I thought a better way of sorting data would be by elements' proximity to each other, rather than the user, which is a logical representation of a map I guess (in a geographical sense). But how then given any point on this map can we retrieve an equivalent 1D array that would convey this information?

EDIT: Thanks for your comments. I think it may be that my problem isn't as theoretical as you answers, it's been a few years since I had to cram for my algorithm exams and I've forgotten a whole lot. I'll to give some details, perhaps that will make it clearer:

In this particular case I am looking at around 350 points on the map, and page of around 10. (I think that makes k in Suresh's comment about 20, because on/after the second page distance from q - in this case position of user's query - is not the only relevant factor)

I had a, possibly a not so smart an idea, which I would like to try to explain with the of a crudely drawn diagram in paint:

So diagram A is what I have now, where concentric red circles represent paged results as points get further and further away from the centre red dot. I'd like to be able to drag the map, so that paged results get updated with what's currently closest to the centre of the screen (much like Google results) but with current sorting it's impossible without zooming out to accommodate all the points.
A possible solution is to apply some clustering to get a bunch of probably overlapping areas that represent pages as shown in diagram B. That would mean there is some duplication in the returned dataset, but the duplication factor could be tweaked. The green spiral in both diagram indicates roughly increase in distance.

Having said all that, I'm now beginning to think it would be much easier to just use viewport to determine what's currently visible to the user and simply show the results on the page as that. :S


texts: Computational complexity of modular power towers (tetration)

texts:
The complexity of modular addition is known: $g + p \mod N$ (for $|p| \approx |g| \approx |N|$) can be computed in $O(n = |N|)$.

The complexity of modular multiplication is open though some results are known: by Toom-Cook $g * p \mod N$ can be performed in $O(n^{1.465})$ and by Schönhage–Strassen in $O(n \log n \log \log n)$.

Modular exponentiation can be performed in $O(M(n) k)$ where $M(n)$ is the complexity of multiplication and $k$ is the length in bits of the exponent by the square-and-multiply algorithm.

I am looking for results about the modular arithmetic in general. Are there better complexity results for performing modular exponentiation (over the 'naive' square-and-multiply)? What results are known for modular exponentiation of power towers of height h?

(For $h = 3$: $g^{g^{g}} \mod N$ and for general $h$: $g^{g^{g^{g^{...^g}}}} \mod N$)


texts: Is it considered OK to email authors to inquire about their paper while subreviewing their paper for a conference?

texts: More generally, how do you reconcile questions that you may have about the paper's technical material?


texts: Derive logitboost using the logistic loss function

texts:
An additive model constructed using the exponential loss function

$$L(y, f (x)) = \exp(−yf (x))$$

gives   Adaboost. How can we derive the corresponding additive model (known as logitboost) using the logistic loss function

$$L(y, f (x)) = \log(1 + \exp(−yf (x)))$$

What steps I should take to do the above proof?


texts: Automata model with undecidable (or non-context-sensitive) languages and no $\varepsilon$-transitions.

texts:
Adding extensions to automata has always been a fruitful domain.  But usually, one wants to add weak capabilities, as undecidability comes quickly into the picture.

Take FSM with added stacks.  It is easily seen that two stacks can simulate a Turing machine's tape, and the state control of the TM is taken care of by the FSM.  Thus, such machines recognize Turing-recognizable languages.

The implicit assumption made here is that the FSM is not only non-deterministic but has $\varepsilon$-transitions, which are used to "wait" for the TM to halt.

My question is thus: what (minimal) capabilities should one add to $\varepsilon$-transition-free automata in order to make them recognize undecidable (or non-context-sensitive) languages.  I'm searching for something else than an oracle for a specific language, of course!

Nota: Requiring no-$\varepsilon$-transition means that a word of length $n$ is read taking $n$ transitions.  This may mean that the added power ought to be undecidable / of large space complexity by nature.


texts: Contradiction between Gödel's Second Incompleteness Theorem and the Church-Rosser's property of CIC?

texts:
On one hand, Gödel's Second Incompleteness Theorem states that any consistent formal theory that is strong enough to express any basic arithmetical statements can't prove its own consistency. On the other hand, the Church-Rosser's property of a formal (rewriting) system tells us that it is consistent, in the sense that not all equations are derivable, for example, K$\neq$I, since they don't have the same normal form.

Then the Calculus of Inductive Constructions (CIC) clearly statisfies both conditions. It is strong enough to represent arithmetical propositions (indeed, the $\lambda\beta\eta$-calculus alone is already able to encode the Church numerals and represent all primitive recursive functions). Moreover, CIC also has the confluence or Church-Rosser property. But:

  shouldn't CIC be unable to prove its own consistency by the Second Incompleteness theorem?

Or it just states that the CIC can't prove its own consistency inside the system, and somehow the confluence property is a meta-theorem? Or maybe the confluence property of CIC does not guarantee its consistency?

I would highly appreciate  if someone could shed some light on those issues!

Thanks!


texts: Mapping of entire balls using Locality Sensitive Hashing (LSH)

texts:
LSH functions are useful for approximate nearest neighbor search.
They are usually defined, for distance metric $d$ and $c>1$ as follows:

  A family of hash functions is $(r, cr, p_1, p_2)$-LSH with $p_1 \ge p_2$ and $c > 1$ if:

$\Pr[h(x) = h(y)] \ge p_1$ when $d(x, y) \le r$ (close points).
$\Pr[h(x) = h(y)] \le p_2$ when $d(x, y) \ge cr$ (distant points).

The family is interesting when $p_1>p_2$ and they are often compared using $\rho = \frac{\log 1/p_1}{\log 1/p_2}$ which directly affect the space and query time.

I am wondering what is known for mapping of balls using LSH functions.
Let's say that a ball $B_R(x)$ is mapped entirely if $h(x)=h(y)$ for any $y$ such that $d(x, y) \le R$.

Intuitively, if $R_1\ll r$, we may be able to expect that $B_{R_1}(x)$ will be mapped entirely with a reasonable probability.

  Question 1: Given $r, R_1, c, x$, how can we derive a lower bound on the probability that $B_{R_1}(x)$ is mapped entirely for known LSH families?

The other side is that if $cr\ll  R_2$, we may be able to expect that with decent probability no point $y$ for which $d(x,y)\ge R_2$ will have $h(x)=h(y)$.

  Question 2: Given $r, R_2, c, x$, can we derive a lower bound on the probability that no $y$ for which $d(x,y)\ge R_2$ has $h(x)=h(y)$?


texts: Load-balancing; Alternate methods of keeping track of nodes?

texts:
Reading various articles in the literature have given me only a few decent methods of keeping track of nodes before->after load-balancing them on a very large network.

One popular method uses virtual-servers and a DHT (Distributed Hash Table)[1]

The problem with DHTs is they are very difficult to maintain, and can result in single point of failure.

Recently I've been looking at implementing a tree of counting bloom filters for finding nodes once their position has been moved.

Can you recommend an alternate method of keeping track of nodes?

[1] Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. Wide-area cooperative storage with CFS. SIGOPS Oper. Syst. Rev., 35(5):202215, October 2001.


texts:
Where can I seek help when I cannot understand a research paper? Instead of emailing the author since the paper is long time ago, I am preferring some discussion forum that people exchange ideas on the paper.

I am not a student in university so I cannot ask my professor but a software engineer in the industry.


texts: What is the difference between PRAM and multi threading?

texts:
PRAM and multi-threading are somewhat part of the same model of the shared memory model, in which both can compute in parallel, and both can allow processors to communicate with each other since there data parallel.

So what is the difference between multithreading and PRAM?


texts: Number of Maximum Overlap in n-Dimensions

texts:
Given a list of compact axis-aligned intervals (in 1-D), rectangles (in 2-D), cuboids (3-D) etc, what is the maximum number that overlap at any point?

In 1-D there's a fairly simple solution that exploits the the ordering of R: assuming you have a set of pairs $\{[a_1,b_1],...,[a_n,b_n]\}$ sort all of the a's and b's (together) then scan from a_min to b_max adding one to the count of overlap whenever you encounter $a_i$ for any i and subtracting one whenever you see a $b_j$ for any j. Then just keep track of the maximum value of count that you see.

I'm not sure how to extend this to 2-D, let alone n-D. Any ideas?


texts:
What is the complexity of local satisfiability problem for modal logic $\mathit{IK5}$? Herein we denote by $IK5$ the modal logic over euclidean frames extended with inverse modality. Could you provide any references? Is it in $NP$?

What I know about the topic?

  It's easy to see that $IK5$ is in $ExpTime$, since there is a
  reduction from it to $GF^2$ (the two-variable guarded fragment of
  first-order logic) - see Deciding Regular Grammar Logics with
  Converse Through First-Order Logic.

  On the other hand, the ordinary $K5$ is $NP$-complete.

  We can write an equisatisfiable formula in $FO^1$ (the one-variable
  fragment of first-order logic), because the models can be devided into
  three parts: (1) starting world $w$, (2) sucessors of $w$ (3)
  sucessors of sucessors of $w$. The example reduction for even harder
  logic ($K5$ with graded modalities) is described in A Note on the
  Complexity of the Satisfiability Problem for Graded Modal Logics.
  However in the presence of inverse modality we cannot do the same
  trick - the brief idea is that inverse worlds could require the
  different number of successors.


texts: What is the best place to get BibTeX entries for ICLR and other machine learning papers?

texts:
dblp seems the best i found so far (as also mentioned in the comments and in What is the best place to get BibTeX entries for computer science articles ?) but even there some papers from NIPS workshops and ICLR in general are not listed as such and are listed simply as CoRR papers.

For example "Neural Machine Translation by Jointly Learning to Align and Translate"
https://dblp.uni-trier.de/rec/bibtex/journals/corr/BahdanauCB14
although after writing the question i'm finding that most papers are referencing the NMT paper also as CoRR/arXiv. I also didn't find proceedings of ICLR so maybe it's a general issue only with ICLR papers and some conference workshops.


texts: Decidability of regular partition construction given its existence

texts:
Let $G = (N,T,P,S)$ be a context-free grammar where $T,N$ are sets of terminals and nonterminals respectively, $P$ contains all the productions of the grammar, and $S \in N$.
If we know that $G$ is LL($k$) it is possible to construct a parser for $G$, since the construction of a LL($k$) parsing table is decidable, despite the problem of determining whether an arbitrary grammar is LL($k$) being undecidable. This is possible even if we don't know the exact value of $k$.
The problem of determining whether given arbitrary grammar is LL-regular is undecidable. Assume that we know that $G$ is LL-regular. Is the problem of constructing a regular partition $\pi$ for $G$ decidable?


texts: Can boolean algebra be expressed in simply typed lambda caclulus?

texts:
Boolean algebra can be expressed in untyped lambda calculus in (for example) this way.

true  = \t. \f. t;
false = \t. \f. t;
not   = \x. x false true;
and   = \x. \y. x y false;
or    = \x. \y. x true y;

Also boolean algebra can be encoded in System F in this way:

CBool = All X.X -> X -> X;
true  = \X. \t:X. \f:X. t;
false = \X. \t:X. \f:X. f;
not   = \x:CBool. x [CBool] false true;
and   = \x:CBool. \y:CBool. x [CBool] y false;
or    = \x:CBool. \y:CBool. x [CBool] true y;

Is there a way to express boolean algebra in simply typed lambda calculus? I assume that answer is NO. (For example, Predecessor and lists are not representable in simply typed lambda-calculus.) If the answer is NO indeed, is there a simple intuitive explanation, why it is impossible to encode booleans in simply typed lambda calculus?

UPDATE: We assume that there are base types.

UPDATE: The negative answer with explanation was found here (Comment "Here's a proof sketch to show that simply-typed lambda calculus with products and infinitely many base types does not have booleans.") This is what I was looking for.


texts: From Church-encoding to induction principle

texts:
I am looking for an algorithm to go from a Church-encoded datatype to their induction principle in the Calculus of Constructions. For example:

Unit = {t : *} -> t -> t
~>
(x : Unit) -> {P : Unit -> *} -> P (\{t} x. x) -> P x

Nat = {t : *} -> t -> (t -> t) -> t
~>
(x : Nat) -> {P : Nat -> *} -> P (\{t} z s. z) -> ({m : Nat} -> P m -> P (\{t} z s. s (m {t} z s))) -> P x

It seems like this should be possible for any Church-encoded datatype. Does anybody know such an algorithm/translation or resources on it?


texts: Minimum-area orthogonal rectangle coverage

texts:
Suppose there are N orthogonal rectangles on the planes, overlapping or not.

I want to cover them with exact K orthogonal rectangles, overlapping or not. Each input rectangle must be completely covered. More specifically:

An input rectangle can be covered by more than one covering rectangles.
An input rectangle may be partially covered by a covering rectangle.

The target is to minimize the sum of the area of the covering rectangles.

Here is an example:

http://i.stack.imgur.com/VLz63.png

The input consists of 3 rectangles as shown in the show. When k=1,2,3, the solutions are shown below. There are 2 possible solutions for K=3, depending on whose area is smaller. Note that an input rectangle can be partially covered by a covering rectangle.

I tried to google this, but not sure about the name of this problem. I got many results about the problem to decompose rectilinear polygons into rectangles, where the target is to minimize the number of covering rectangles used. That is not my case, I don't require that the covering rectangles are disjoint, and I want to minimize the area fixing the number of the covering rectangles instead of the opposite way.

I guess this is NP-Hard or similar, so I don't even expect a good approximation. Any heuristic idea would be appreciated.

Thanks!


texts: Relation between transcendental numbers and computational complexity?

texts: Regarding the relation, there is the Hartmanis-Stearns conjecture, but beyond Turing Machine of the realtime output, there is no further conjecture or theorem. Obviously irrational algebraic number can not be outputted by real time TM, and so are  infinite transcendental numbers. But beyond realtime TM and in the same complexity classes like P, are there irrational algebraic numbers and transcendental numbers? Or we can separate transcendental numbers from irrational algebraic numbers by the different complexity classes?


texts: A special class of languages: “circular” languages. Is it known?

texts:
Define the following class of "circular" languages over a finite alphabet Sigma. Actually, the name already exists to denote a different thing it seems, used in the field of DNA computing. AFAICT, that's a different class of languages.

A language L is circular iff for all words $w$ in $\Sigma^*$, we have:

$w$ belongs to L if and only if for all integers $k > 0$, $w^k$ belongs to L.

Is this class of languages known? I am interested in the circular languages which are also regular and in particular in:

a name for them, if they are already known
decidability of the problem, given an automaton (in particular: a
DFA), whether the accepted language obeys to the above definition


texts:
It is not difficult to show that sorting an array of numbers is hard for $\mathsf{TC^0}$.
If the input is an array of 1s and 0s then it is essentially the function $Count$ (given $n$ bits, output the number of 1s in binary) since $Count$ is complete for $\mathsf{TC^0}$ and it is possible to convert unary numbers to binary numbers and (logarithmicly) small binary numbers to unary numbers in $\mathsf{AC^0}$:

  $Count(\vec{x}) = Binary(Sort(\vec{x}))$
  $Sort(\vec{x}) = Unary(Count(\vec{x}))$

So the power of $\mathsf{TC^0}$ is essentially sorting a binary string (eg. 100011 to 000111).
This is true more generally when the numbers in the array are bounded. My question is what if the numbers are not bounded?

Is the problem of sorting an array of unbounded numbers still in $\mathsf{TC^0}$?  Is it  complete for a larger class like $\mathsf{NC^1}$?


texts:
I had done some search on this but I was not able to find an answer either way.
Huck answered it fully. Thanks :)


texts: Parallel (NC) replacements for Gaussian elimination?

texts:
Suppose one has an matrix $A$ with $c$ columns and $r$ rows with entries in the binary field $GF(2)$. One wants to determine

its rank, and
a basis for its null-space.

These can be computed easily in time $O(r^2 c)$ by Gauss elimination, but that is a very sequential algorithm.

Are there deterministic parallel (NC, polylogarithmic time, polynomial space) algorithms to compute these?

One may be able to assume that either $r$ or $c$ is small (maybe polylogarithmic) if it helps.


texts: Counting small terms in a determinant calculation over polynomials (counting spanning trees by weight)

texts:
I have a $n\times n$ matrix $A$. It's terms are $a_{ij}=-x^{w_{ij}}$ if $i\neq j$ and $a_{ii}=\sum_{j=0}^{n+1} x^{w_{ij}}$ on the diagonal. The matrix is symmetric as $w_{ij}=w_{ji}$. Numbers $w_{ij}$ are arbitrary. (The matrix is not singular as the sum on the diagonal runs up to $n+1$.)

How can I compute the $(1+\varepsilon)$-approximate number of terms in the determinant of $A$ with exponent smaller than some given exponent $W$, in time polynomial in $n$ and $\varepsilon^{-1}$ and independent of the largest value $w_{ij}$?

As a black box, I can use an algorithm that counts the number of paths on a DAG, shorter than some threshold $L$ with error $(1+\varepsilon)^{\pm 1}$. I planned to calculate some LU-decomposition of $A$. Then I could get the determinant as a product of a polynomial number
of polynomials with polynomial number of terms: $det(A)=\prod_i^N f_i(x)$ where $N\in O(poly(n))$ and each $f_i(x)$ has polynomially many terms.  Now I would construct a DAG that represents the determinant: a monomial $x^{w_{ij}}$ would be represented two vertices connected by an edge with weight $w_{ij}$. A summation of polynomials $f(x)$ and $g(x)$ would be represented by two vertices connected in parallel by the graph that represents $f(x)$ and the graph that represents $g(x)$. The product of polynomials $f(x)g(x)$ would be represented by the graphs corresponding to $f(x)$ and $g(x)$ in series. All is well so far, I would construct the graph and approximately count paths shorter than the threshold from one end to the other. But the problem is that some polynomials $f(x)$ will have negative terms. That means that I need to keep track of the parity of individual paths, effectively making 2 copies of the DAG and switching between them when parity changes. In the end I have to calculate the paths that end up with negative parity and subtract them from the paths that end up with positive parity. This can kill my approximation ratio since I do not know the relationship between the number of positive and negative parity paths.

Is there a different way how to represent the determinant as a product of polynomial number of polynomials, hopefully without negative terms and without division? I need to avoid any actual determinant calculation, since the expansion may generate a polynomial with number of terms exponential in $n$.

The original intent is probably obvious:
I am trying to count spanning trees shorter than some value $W$. The determinant of the matrix $A$ is a generating polynomial for these. Evaluating the polynomial fully would not give a FPTAS, since we can have at most $n^{n-2}$ distinct weight spanning trees (consider a complete graph with edges of lengths $2^i$ for edge $i$.)

In this case, it seems that applying some division-less LU decomposition and then counting paths with parity will not work: if we calculate the determinant according to the Leibniz formula
$\det(A)=\sum_{\sigma\in S_n}sgn(\sigma)\prod_{i=1}^n A_{i,\sigma_i}$, the expansion will contain cyclic subgraphs that will eventually cancel out. But there can be many cyclic subgraphs, shorter than the MST. So if we set counting
threshold to the value of the MST, we might make a large error in the subtraction, unless the LU decomposition somehow magically takes care of this.


texts:
Is there any known "nice" hierarchy $L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots$ (may be finite) inside the class of regular languages $L$? By nice here, the classes in each hierarchy capture different expressiveness / power / complexity. Also, the membership of each class is "nicely" demonstrated by some elements (unlike star height problem that may be problematic).

Thank you!


texts: Efficiently computing the exact union of 'N' intersecting circles on a plane

texts: I have a set of $N$ circles with a set of known radii $r_i$ on a plane of some surface area $A$.  If intersection is allowed between circles, how can I most efficiently compute the exact (not approximate) surface area of their union?


texts: In Strongly connected tournament T.Is it NP-hard to find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.

texts:
Given strongly connected tournament T.find a minimum number of vertices(V1) which make T\V1 as non strongly connected tournament.
I have doubt whether the problem mentioned can be solved in polynomial time,if so please give the idea
else please mention proof of NP-completeness


texts:
Consider any tree $T$ with $n>2$ vertices and $k$ leaves. Let's denote $G(T)$ a graph constructed from $T$ by connecting its leaves into $k$-cycle in such way that $G(T)$ is planar.

In case I wasn't clear enough I'll give an example:

Let T be a tree with edges E(T) = { {1,2}, {2,3}, {2,4}, {4,5} } and then E(G(T)) = sum of the sets: E(T) and { {1,5}, {5,3}, {3,1} }, since we are connecting leaves 1,5,3 into a cycle.

And I believe that if $T$ is not $K_{1,2r+1}$ then $G(T)$ is $3$-colorable, but my problem is I don't know how to prove it. I was trying to come up with an algorithm that starts with $2$-coloring of a tree and then with third color fix collisions on a cycle, but this led me to nowhere.


texts: Does a polynomial-time algorithm for factoring product of two primes imply a polynomial-time algorithm for factoring in general?

texts: Is it known if the existence of a polynomial-time algorithm for the promise problem of factoring of numbers with two prime factors implies that factoring in general has a polynomial-time algorithm?


texts: Where is relational parametricity in hyperdoctrine or topos models explored?

texts:
Reynolds originally proposed a relational semantics for the second order polymorphic lambda calculus[1].  However he later showed[2] that this approach was inconsistent with classical  set theory.  Pitts described the framework of hyperdoctrine models and topos models[3] which are consistent with constructive logic.

Presumably relational hyperdoctrine and topos models were then developed.  Where can I read about them?

[1] Types, abstraction and parametric polymorphism
[2] Polymorphism is not set-theoretic
[3] Polymorphism is set theoretic, constructively


texts: Complexity of a naive algorithm for finding the longest Fibonacci substring

texts:
I already posted this question here but I didn't receive an answer, so I'm posting it here as well :)

Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows:

$$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\
\text{a} &\mbox{if } k = 1 \\
F(k-1) \star F(k-2) &\mbox{else} \end{cases} $$

with $\star$ denoting string concatenation.

Thus we'll have:

$F(0) = \text{b}$
$F(1) = \text{a}$
$F(2) = F(1) \star F(0) = \text{ab}$
$F(3) = F(2) \star F(1) = \text{aba}$
$F(4) = F(3) \star F(2) = \text{abaab}$
...

Given a string $S$ formed by $n$ symbols, we define a Fibonacci substring as any substring of $S$ which is also a Fibonacci string for a suitable choice of $\text{a}$ and $\text{b}$.

The problem

Given $S$, we want to find its longest Fibonacci substring.

A trivial algorithm

For each position $i$ of the string $S$, suppose that $F(2)$ starts there (it's enough to check that the $i$-th and $(i+1)$-th symbols are distinct). If that's the case, check if it can be extended to $F(3)$, then $F(4)$, and so on. After that, start again from the position $i+1$. Repeat until you reach the position $n$.

We must look at each symbol at least once, so it's $\Omega(n)$. There are only two for loops involved, so we can furthermore say that it's $O(n^2)$.

However (somewhat unsurprisingly) this naive algorithm performs much better than usual quadratic algorithms (if it does a lot of work on the $i$-th position, it won't do a lot of work in the next positions).

How can I use Fibonacci properties to find tighter bounds for the execution time of this algorithm?