texts: Reference Material for Axiomatic Semantics

texts:
I'm looking for some kind of reference material that has a full treatment of axiomatic semantics with everything spelled out. If the material comments on or includes algebraic semantics and any other variations of axiomatic semantics, that would be great. A separate recommendation for variations is also welcomed.
Are there any such textbooks, lecture notes, survey papers, etc?


texts: Suffix array construction algorithms (SACAs)

texts: I am working on an efficient pattern-matching algorithm (using binary files as input) based on suffix arrays. I would like to ask you If you are familiar with any suffix array construction algorithm (SACA) except the one that was presented in the original paper. So far I have found quite a few: BPR2, DC3 RadixSA etc, however, as their source is not publicly available I do not want to implement them all and benchmark them afterward. Do you have any experience and which of them would you suggest if the operation time is critical? Additionally, I have found out that sometimes suboptimal algorithms (e.g. O(nlogn)) can work better in real-life scenarios than other counterparts which may have better asymptotic complexity( e.g. O(n)). Is this due to hidden constants that may dramatically increase the operation time of the latter algorithms? Does the poor locality that may come with these optimal algorithms also result to bad caching also affecting their performance? Thank you!


texts: Is the basis of parity functions the only orthonormal basis for Boolean functions?

texts:
Is there another orthonormal basis of functions for Boolean functions? Or, more specifically, besides the parity functions, is there another explicit function (which is common and has a name) that can form an orthonormal basis for Boolean functions?

If not, why not?


texts: Optimal reduction using token-passing nets

texts:
I am looking for implementation of optimal reduction for λ-calculus based on interaction nets (McCarthy's amb allowed) in the spirit of "Token-Passing Nets: Call-by-Need for Free" by François-Régis Sinot. Implementations of optimal reduction that I am aware of either assume a specific strategy for the interaction net reduction, or involve non-pure graph reductions rather than just interaction rules.

The reason why I am interested in such implementation is that I already have a compiler for interaction nets which is based on interaction calculus, but is agnostic to any notion of interface, thus unable to follow any strategy while reducing a configuration simply represented as a queue of active pairs.


texts:
Suppose $L$ is a Boolean language, of finite strings over $\{0,1\}$.  Let $L_n$ be the number of strings in $L$ with length $n$.  For a function $d(n)$ from the positive integers to the positive real numbers, $L$ has upper density $d(n)$ if $L_n \le 2^n d(n)$ for all sufficiently large $n$.

  Do any P-complete Boolean languages have upper density $O(1/n)$?

Motivation

PARITY has upper density $1/2$.  YES (the language of all finite binary strings) has upper density 1.  Any finite language has upper density 0.
A sparse language $L$ has the property that there is a polynomial $p(n)$ such that $L_n - L_{n-1} \le p(n)$ for all $n$.  If $L$ is a sparse language, then $L_n \le p_1(n)$ for a polynomial $p_1$ of degree one greater than that of $p$, so the upper density of $L$ is zero.
Jin-Yi Cai and D. Sivakumar showed that a P-complete language cannot be sparse unless P = L (= LOGSPACE).  Since P=co-P, any language of which the complement is sparse cannot be P-complete either, unless P=L.
By a simple inequality (see e.g. Corollary 2 of Rosser and Schoenfeld 1962), PRIMES has upper density $(\log_2 e)/n$.  Question Are the problems PRIMES, FACTORING known to be P-hard? discusses whether PRIMES is P-hard (this seems to be open currently).
In some sense, the complete (or universal)languages for a complexity class contain all the structure of the class.  So my tentative hypothesis, based on a wild extrapolation of Cai and Sivakumar's result, would be that such languages cannot be too sparse.  The usual polynomial bound defining sparse languages seems too restrictive, so I'm asking about a bound that is a little less restrictive.

The work on lowness by Fortnow, Hemaspaandra, and others is also possibly related.

The question can be asked of classes other than P, but I can't recall any results that would allow establishing density of, say, $k$-SAT.  Pointers to relevant literature would be most welcome.

Acknowledgements

See also related question Conditional density of primes.  Thanks to @Tsuyoshi Ito and @Kaveh for helpful comments on an earlier version of this question, which was unfortunately ill-posed.


texts: Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?

texts:
Consider a permutation $\sigma$ of $[1..n]$. An inversion is defined as a pair $(i, j)$ of indices such that $i < j$ and $\sigma(i) > \sigma(j)$.

Define $A_k$ to be the number of permutations of $[1..n]$ with at most $k$ inversions.

Question: What's the tight asymptotic bound for $A_k$?

A related question was asked before: Number of permutations which have the same Kendall-Tau distance

But the question above was regarding computing $A_k$. It can be computed using dynamic programming, since it satisfies the recurrence relation shown here: https://stackoverflow.com/questions/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble-sort-swaps

The number of permutations with exactly $k$ inversions has also been studied and it can be expressed as a generating function: http://en.wikipedia.org/wiki/Permutation#Inversions

But I can't find a closed-form formula or an asymptotic bound.


texts: Algorithms for finding clique in bounded-degree graph

texts:
Consider a graph with $n$ vertices and maximum degree $\Delta$. I would like to find if the graph has any $s$ cliques, where $s \leq \Delta$ and both of them are small compared to $n$. I only need to find a single such clique (or certify that none exist)

There is a straightforward way to do this: for each vertex $v$, test all $s$-subsets of the neighbors of $v$. The work is thus $\approx n \binom{\Delta}{s-1}$.

Are there any more efficient algorithms than this? Even achieving an exponential speed-up would be good?


texts: A bicartesian closed category of strict complete partial orders (Hask)

texts:
It seems to be well-known that programming languages can't have sums, products and nontermination together.

Q1. Is this true? Below (or in the above link I gave) is a partial argument.

However, Hinze's Generic programming with Adjunctions ignores the issue, even after discussing somewhat precisely which is the involved category. In particular, he talks (seemingly without reservations) about Haskell being modeled by the category $\mathbf{SCpo}$ of strict continuous partial orders and having sums and products. But we know that Haskell does not have sums (right?).
(Part of the paper uses $\mathbf{Set}$ instead, but that doesn't allow for non-termination).

Q2
So, what am I missing? I see four options:

People often ignore non-termination on purpose when discussing Haskell. Perhaps this paper does it too. But why would one mention CPOs then?
The barrier I discuss can be avoided in clever ways. In particular, the paper models non-strict Haskell functions $f : A \to B$ by strict functions $f : A_{\bot} \to B$, for other reasons.
The paper does mention the limitation and I missed that. I've spent some effort looking for this mention and failed to find any.
This is an actual mistake, and as everybody keeps claiming Haskell indeed lacks categorical sums (as other people agree on), even though the paper claims Either is such a thing. Everything works out nicely instead in total languages with inductive and coinductive types.

Background

It's well known that, in a bicartesian closed category (BCCC), if the initial and final object coincide (that is, if the category has a zero object) the category collapses (with all types being isomorphic) by $A \cong  A \times 1 \cong A \times 0 \cong 0$ for all $A$.

This means, for instance, that the category of pointed sets, with its zero object, can't be bicartesian closed.

But the category SCpo also has a zero object for the same reason: all objects are structured sets (CPOs) with a bottom element $\bot$, and arrows are strict (and ($\omega$-)continuous) functions, so they preserve $\bot$. Indeed, this is attributed to Smyth and Plotkin (1982), who describe this category as $\mathbf{CPO}_{\bot}$ and state it lacks categorical products; other categories they consider lack other features of a BiCCC (e.g., their $\mathbf{CPO}$ lacks sums).

What is not clear to me is whether every way of handling $\bot$ falls into this trap. However, knowledgeable people on Reddit seem to repeat this claim without good sources (Filinski's master thesis was the best reference I got, and it doesn't lay out a generic categorical argument).


texts:
A language is in $L/poly$ if there exists a logspace Turing machine that decides the language with polynomial amount of advice.

See here for more info: https://en.wikipedia.org/wiki/L/poly

  Question

  What are the consequences of $P \subseteq L/poly$?


texts: Practical implementation of Hindley–Milner with typeclasses — matching vs most general unifier

texts:
I'm trying to get a deep understanding of a (great) paper "Typing Haskell in Haskell". I'm having difficulties understanding the implementation of two methods there — the mgu and match.

Let's talk about the TAp case (full implementation in the article):

-- Substitutions are from a type variable to a type
type Subst  = [(Tyvar, Type)]

-- Calculate most general unifier 's' so that:
-- prop> apply s t1 = apply s t2
mgu :: Monad m => Ty.Type -> Ty.Type -> m Subst
mgu (TAp l r) (TAp l' r') = do s1 <- mgu l l'
                               s2 <- mgu (apply s1 r) (apply s1 r')
                               return (s2 @@ s1)              -- <=== THIS
-- ...snip...

-- Matching of t1 and t2 finds a substitution 's' so that:
-- prop> apply s t1 = t2
match :: Monad m => Type -> Type -> m Subst
match (TAp l r) (TAp l' r') = do sl <- match l l'
                                 sr <- match r r'
                                 merge sl sr                  -- <=== THIS
-- ...snip...

-- Substitution composition such that:
-- prop> apply (s1 @@ s2) = apply s1 . apply s2
(@@)       :: Subst -> Subst -> Subst
s1 @@ s2    = [ (u, apply s1 t) | (u,t) <- s2 ] ++ s1

-- A `symmetric' composition of substitutions such that:
-- prop> apply (s1++s2) = apply (s2++s1)
merge :: Monad m => Subst -> Subst -> m Subst
merge s1 s2 = if agree then return (s1 ++ s2) else fail "merge fails"
  where agree = all (\v -> apply s1 (Ty.TVar v) == apply s2 (Ty.TVar v))
                    (map fst s1 `intersect` map fst s2)

match is used only for matching predicates, mgu is used more often e.g. for actual type inference.

I can't wrap my head on why in the mgu the substitution composition is sequential and in match a symmetric composition is used. Why's that?

Furthermore, would it make a difference if I'd change the ordering of unification, so mgu would read:

mgu (TAp l r) (TAp l' r') = do s1 <- mgu r r'
                               s2 <- mgu (apply s1 l) (apply s1 l')
                               return (s2 @@ s1)


texts: What is the intuitive meaning of the weakest precondition expression $\text{wp}(S,R)$ in refinement calculus with miracles?

texts:
What is the intuitive meaning of the expression $\text{wp}(S,R)$ ($\text{wp}$ = weakest precondition) in refinement calculus with miracles?
When the $\text{wp}$ function describes partial correctness (as in Hoare's calculus), $\text{wp}(S,R)$ means intuitively: if you start at a state satisfying $\text{wp}(S,R)$ and then proceed to execute the program $S$, then, if the computation terminates, the final state will satisfy $R$.
When the $\text{wp}$ function describes total correctness (as in Dijkstra's calculus), $\text{wp}(S,R)$ means intuitively: if you start at a state satisfying $\text{wp}(S,R)$ and then proceed to execute the program $S$, then the computation is guaranteed to terminate in a state satisfying $R$.
But what is the intuitive meaning of $\text{wp}(S,R)$ in refinement calculus with "miracles" (as in Carroll Morgan's textbook Programming from Specifications)? For instance, how should I understand the fact that $\text{wp}(S, \text{false}) = \text{true}$ when $S$ is the specification statement $x:[\text{true},\text{false}]$? Is it simply partial correctness? If so, then why introduce the concept of "miracles", and not just call it "partial correctness"?


texts: On the size of P4-transversals of graphs

texts:
A subset $T$ of vertices of a graph $G$ is called a $P_4$-transversal if $T$ intersects every $P_4$ of $G$. In the context of this question, we consider $P_4$ as an induced path on 4 vertices.

Conjecture :
Given a graph $G$ of $n$ vertices, the minimal $P_4$-transversal of G is of at most $\frac{n}{2}$ vertices.

We consider gneral simple graphs here. However, any results of subclasses of simple graphs are welcome.

Thoughts:
$P_4$-transversal can be seen as a special case of hitting set of sets of size 4. However, for general hitting set of 4-sets (i.e., 4-uniform hypergraph) on $n$ vertices, the minimum hitting set can be as large as $n-3$.

The original version of this question guessed the upperbound of the size of $P_4$-transversal as $\frac{n}{3}$. Thanks to the comments from R B and Jim Nastos, we have an example on 16 vertices and whose minimal transverval has 7 vertices.

Introduction and why I am interested in $P_4$-transversal of graphs.

Study of $P_4$-transversal is a part of study of $P_4$-structures of graphs, which plays an important role in the "Strong Perfect Graph Theorem". $P_4$-transversal of perfect graphs and chordal graphs were studied in perfect graph and chordal graph.

$P_4$ is a path of 4 vertices. A $P4$-free graphs is called a cograph, which is the minimal family of graphs generated from $K_1$ and complementation and disjoint union. Therefore, $P_4$ structures seems to be an interesting and important property of graphs.


texts: Karp-like reductions vs Cook-like reductions for Functional Complexity Classes.

texts:
Assume we have two counting (functional) complexity classes $A$ and $B$. Suppose that

Under Karp-like reductions $A$ is strictly inside $B$.
Under Cook-like reductions $P^A=P^B$.

  What does this tell us about the relationship between these two
  counting complexity classes?


texts: A non-trivial combinatorial optimization

texts:
So I stumble over this problem in which I couldn't find anything similar in the literature. I am not even sure if it is NP-hard or solvable in polynomial time. Any thought or suggestion would be greatly appreciated.

Suppose I give you a $d$ dimensional vector $x$, with rational entries in the range $[0,1]$. Similarly, I also give you $d$ dimensional $n^2$ vectors $y_{i,j}$ for $i,j \in \{1,...,n\}$ with entries in the range $[0,1]$.

I want to find a directed spanning tree with each vertex has exactly one parent (except the root) $T$ of $n$ vertices such that:

$\| x - \circ_{(i,j) \in edges(T) }y_{i,j}\|_1$  is minimized, where $\circ$ denotes the Hadamard product (entry-wise product) between the vectors. I'm also fine with $l_2$ norm. I.e,

$\| x - \circ_{(i,j) \in edges(T) }y_{i,j}\|_2$  is minimized.


texts: Upper bound on the pseudoentropy of any distribution

texts:
From here:

  The notion of pseudoentropy is only useful, however, as a lower bound on the computational entropy in a distribution. Indeed, it can be shown that every distribution on $\{0,1\}^n$ is computationally indistinguishable from a distribution of entropy at most $poly (\log n)$.

How is that any distribution on $n$-cube can be computationally indistinguishable from one with entropy at most $poly(\log n)$?


texts: Using compression to improve edit distance computation

texts:
I am doing a seminar on a paper titled "Unified Compression-Based Acceleration
of Edit-Distance Computation" that uses straight-line programs to improve edit distance computation. It is a common method to exploit repetitions for ED although I couldn't find the first article that used it and I thought it is important to mention it in the seminar.

Does anybody have a clue what it was?
Thanks!


texts: Aren't Monads F-Algebra's? And then if that could be said are Comonad's F-Coalgebra's?

texts:
So considering a Monad to be a Triple (T:C -> C, η, µ) with eta and mu as the Natural transformations with appropriate signatures, isn't this in essence an F-Algebra?

My thinking is that being both (Monad and F-Alg) centered around some particular action(s) on|of a given Endofunctor, what stops Monads NOT just being special cases of F-Algebra's? (Also for some context I've been reading a bit of Homotopy theory & Bart Jacobs so I like could just be you know not seeing clearly and making connections where there are none...) I'm seeing a Monad as an F-Algebra of some Monoidal category or Quasicategory with the action of the Endofunctor or alternatively the operations definable on the Algebra of the Endofunctor as the particular semantics of that F-Algebra (e.g. what makes a Monad the State Monad or the Identity Monad or what have you instead...)

Examples, Proofs etc. in Scala or Haskell are good, but I might need clarification if it's in Haskell.


texts: Optimal point placement on integer lattice

texts:
What is known about the following point placement problem?
For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute
\begin{eqnarray*}
\mu_1(N,n)\triangleq\min_{\mathcal{P}\subset \mathcal{G},\,|\mathcal{P}|=n}\sum_{g\in \mathcal{G} }d_1(g,\mathcal{P})
\end{eqnarray*}
where $d_1$ denotes Manhattan distance ($l_1$ distance).

Any known reasonably efficient algorithms to compute $\mu_1(N,n)$?
What (symmetry) properties one should expect from an optimal $\mathcal{P}$ or its convex
hull?
Is anything known about continuous versions of this problem? For instance, the grid $\mathcal{G}$ is replaced by a unit square $\mathcal{S}$, and $\mathcal{P}$ is measurable subset of $\mathcal{S}$ or area $\sigma<1$ - and of course a different definition of $\mu_1$

It looks related to computing some type of 'optimal' $l_1$-DVD (Discrete Voronoi Diagram) for $\mathcal{G}$.


texts: Is there any result on approximating an arbitrary tree metric by an HST metric?

texts: Is there any known result on approximating an arbitrary tree metric by an HST metric (or an Ultrametric)? What is the distortion? Thanks.


texts: How can I prove formally semantic equivalence of programming languages?

texts:
I would like to compare two languages which are from different programming paradigms. Both langauges are object oriented languages, but one of them a multiparadigm language because it supports functional programming style as well.

I wrote some example codes in imperative style and functional style which are absolutely different in syntax but equivalent in semantics.

I have some experiences about operational semantics, the WHILE language and so on from my university studies and I was wondering how I could give a formal definiton about semantic equivalence of an imperative and a functional language.

I was looking for a clear and nice article about this topic on google scholar but i have not found any useful yet.

Thanks for helping!


texts: Reduce $m$-clause 3SAT to PLANAR-3SAT in $O(m^{2-\varepsilon})$

texts:
The classic reduction from 3SAT to PLANAR-3SAT requires a removal of $O(m^2)$ crossings from a rectilinear representation of 3SAT with $m$ clauses. However, the crossing number inequality suggests that it may not be necessary to have that many crossings.

Is there a way to reduce 3SAT to PLANAR-3SAT in time $O(m^{2-\varepsilon})$ with $\varepsilon>0$ (or less) for subclasses of 3SAT (e.g., read-(at most)-$r$ 3SAT with bounded $r$)?


texts: Running a BPP algorithm with a half-random, half-adversarial string

texts:
Consider the following model: an n-bit string r=r1...rn is chosen uniformly at random.  Next, each index i∈{1,...,n} is put into a set A with independent probability 1/2.  Finally, an adversary is allowed, for each i∈A separately, to flip ri if it wants to.

My question is this: can the resulting string (call it r') be used by an RP or BPP algorithm as its only source of randomness?  Assume that the adversary knows in advance the entire BPP algorithm, the string r, and the set A, and that it has unlimited computation time.  Also assume (obviously) that the BPP algorithm knows neither the adversary's flip decisions nor A.

I'm well-aware that there's a long line of work on precisely this sort of question, from Umesh Vazirani's work on semi-random sources (a different but related model), to more recent work on extractors, mergers, and condensers.  So my question is simply whether any of that work yields the thing I want!  The literature on weak random sources is so large, with so many subtly-different models, that someone who knows that literature can probably save me a lot of time.  Thanks in advance!


texts: Question About Turing Machine Computability

texts:
If p is a Turing machine then L(p) = {x | p(x) = yes}.

Let A = {p | p is a Turing machine and L(p) is a finite set}.

Is A computable? Justify your answer.

So I'm trying to figure out how to solve this practice problem and was wondering if the following solution would be valid for this question.

Yes, A is computable, here is an algorithm that solves it.

If P is a turing machine then L(P) is the set of all strings so that, when you run P on input x, P eventually stops and accepts x.

is x in P?(P, x)

Run P(x)
if x is a member of P,
answer yes
else
answer no


texts: Polynomial-time distinguishability threshold of planted clique

texts:
I have a basic question regarding the best known polynomial-time "distinguishing advantage" for the planted clique problem. By this, I'm referring to the problem of distinguishing the distribution $G(n,\frac{1}{2})$ of Erdos Renyi Random graphs from $G_k(n,\frac{1}{2})$ -- the distribution of graphs formed by planting a clique of size $k$ in $G(n,\frac{1}{2})$. This problem (as well as its natural bipartite variant) is conjectured hard for $k=n^{\frac{1}{2} - \delta}$ when $\delta >0$ is an absolute constant. In this post, you can think of $k=n^{\frac{1}{4}}$.

It is often assumed as a hardness assumption that no polynomial time algorithm can distinguish $G(n,\frac{1}{2})$ from $G_k(n,\frac{1}{2})$ with "non-negligible" advantage. Formally, this means that for any "non-negligible" advantage $\epsilon>0$, there is no polynomial time algorithm $f$ from graphs to $\{0,1\}$ such that $|\Pr[ f(G)=1 ] - \Pr[f(G_k)=1] | > \epsilon$ for $G \sim G(n,\frac{1}{2})$ and $G_k \sim G_k(n,\frac{1}{2})$.

In applications of this hardness assumption which I have seen, "non-negligible" is often taken to mean an absolute constant. In other words, it is believed that no polynomial-time algorithm can distinguish between the two distributions with constant advantage. My question is whether this extends to sub-constant $\epsilon$ which are not too small? i.e., is it believed hard to distinguish the two distributions with advantage, say, $\epsilon = \frac{1}{n}$ or $\epsilon = \frac{1}{\sqrt{n}}$ ? Clearly, there is some advantage $\epsilon$ more than exponentially small in $n$ but less than a constant where this problem crosses from being easy to being hard, and I'm interested in what is known about this "threshold".

The only reference to sub-constant distinguishability I could find is in this paper, which (assuming I understand the paper correctly) seems to rule out polynomial-time distinguishability with $\epsilon > \frac{1}{o(n)}$ via "statistical algorithms." Anybody know what else is known / believed?


texts:
I am looking for blogs which contains recent progress on puzzles/games (Algebraic and Combinatorial) etc. like Soduko, latin square etc. I come across a list on TCS What CS blogs should everyone read?, but it does not seem to contain the type of blogs I am looking for. I am looking for blogs that contains content related to the complexity and algorithmic question of games/puzzles.

I have tried to try to search on the internet. I have got a few resources like FUN conference etc., that helps to some extent.

Are there any blogs or webpage which can serve the purpose I have given below?

What I am from them

Brief idea of the puzzle
Current status of the puzzle
Current open/interesting question on puzzle


texts: What effect would using different types of orders have on a binary search tree?

texts:
Recently, I was coding a comparator function for use in a set backed by a binary search tree, and the set kept saying that it didn't contain elements that I had previously added to it. I eventually realized that the ordering I had implemented in the comparator was to blame, which got me thinking:

How would a binary search tree change if its elements were ordered by different orders (partial, total, strict, etc...)?

Documentation on the C++ STL set says that the ordering must be strict and weak otherwise behavior is 'undefined', but I'd be interested to hear if anyone could give a more in-depth analysis.


texts: Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results

texts:
Are there any known results showing that existence (or non-existence) of finite graphs with specific computable properties imply certain complexity results (such as P = NP)?

Here's one completely hypothetical result: If a finite graph exists with distingushed edges A, B, C and D such that all maximum matchings either contain all of A, B, C, and D, or contain none of A, B, C and D, then P = NP.


texts:
For the longest time I was under the impression that PR contains NEXP.  Try as I might, I am unable to recall where I picked up this notion.  I've looked recently, but I have not been able to find anything about what is known about their relationship.

All that I can currently conclude about them is that it's almost certainly not the case that PR = NEXP, as there are known NEXP-complete problems, while the notion of completeness for PR is problematic.

  What is known about the relationship between PR and NEXP?


texts:
Is the flood fill algorithm the same as depth first search?

If not, how do they differ in complexity?


texts: What is the fastest algorithm for Weighted Planar Max Cut

texts:
In 1990's, the paper Unifying Maximum Cut and Minimum Cut of a Planar Graph described an
$O(n^{3/2}\log n)$-time algorithm for Weighted Planar Max Cut, a landmark in the field.

Recently, this paper appeared:

  Min st-Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
  http://arxiv.org/abs/1003.1320

I was wondering if the time for Weighted Planar Max Cut could be improved from $O(n^{3/2}\log n)$ to $O(n \log^c n)$ for some small constant $c$, using ideas from this paper?

In general, have any improvements in Weighted Planar Max Cut been published?


texts: What's the complexity of recognizing equivalence for the following relation?

texts:
Consider the set $\mathcal{M}_{m,n}(\mathbb{Z})$ of $m$-by-$n$ matrices over, e.g., integers.

We say that two matrices $A$, $B \in \mathcal{M}_{m,n}(\mathbb{Z})$ are equivalent if $A$ can be obtained from $B$ by

permuting (i.e., swapping) rows and
permuting integers (i.e., applying a bijection $\mathbb{Z} \to \mathbb{Z}$ to every element of $B$).

Example:
$\left(\begin{matrix}1 & 0\\ 1 & 1\end{matrix}\right)$ is equivalent to $\left(\begin{matrix}0 & 0\\ 0 & 1\end{matrix}\right)$.

What is the complexity of the recognition problem, i.e., given two matrices, decide whether they are equivalent?

What is the complexity of the invariant problem, i.e., given a matrix $A$, calculate a complete invariant $f(A)$, that is, a function such that $A$ and $B$ are equivalent only if $f(A) = f(B)$?


texts: Best algorithms for real linear programming

texts:
Linear Programming asks for $x\in\mathbb R^n$ such that $Ax\leq L$ holds where $A\in\mathbb R^{m\times n}$ and $L\in\mathbb R^m$ are given. Karmarkar has shown that $\ell$ is the number of bits of input to the algorithm then we can find $x$ in$O(n^{3.5} \ell)$ operations on $O(\ell)$ digit numbers, as compared to $O(n^6 \ell)$ such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus $(n^{3.5} \ell^2 \log \ell \log \log \ell)$ using fast integer multiplication.

What is the best algorithm and its complexity that is currently known and what is believed to be the optimal?
What is the best when $n$ or $m$ is fixed?


texts: Minimization of the maximal adjacent integer sums on a circle

texts: Arrange $\{1,2,\cdots,n\}$ on a circle. What are the arrangements that minimize the maximal sum of all adjacent $k$ integers? For specific and low $n$'s it has been pointed out in math.stackexchange.com this problem can be solved with the binary linear programming. I would like to know if there are general solution for arbitrary $(n,k)$. A random algorithm that gives a probabilistic bound would be great, too.


texts:
One way to prove NP$\neq$ coNP is to show that for every propositional proof system $f$ computable in polynomial time, there exists a family of tautologies for which $f$ requires super polynomial proof lengths (w.r.t the length of tautology being proven).
Results like that of Haken and Ajtai fix a propositional proof system and prove that a certain family (PHP in this case) requires super polynomial length proofs.

My Question:
Are there results which do not fix a proof system and show, possibly very weak, but non-trivial lower bounds on proof length?
For Example: Are there results showing that for every propositional proof system, there exists a family of tautologies which requires superlinear proof lengths?


texts: Is state splitting the LR equivalent of LL nonterminal replication

texts:
The grammar classes SLR and strong LL are similar in that they both use FOLLOW sets to resolve conflicts. For still unresolved conflicts, state splitting always works for SLR grammars, if the grammar is LR. Similarly, Aho/Ullman have shown that nonterminal replication can make any LL grammar strong. If the form of the LL grammar is EBNF, the replication is intrinsic if identical EBNF forms are implemented as different nonterminals at each occurrence in the grammar.

I wonder if the nonterminal replication provided by an EBNF formed SLR grammar would provide something equivalent to state splitting such that the grammar would have LR recognition power.

More specifically, for a fixed k, given any LR(k) grammar, if that grammar contains at most one occurrence of each nullable nonterminal on the right hand sides of all productions, must that grammar also be SLR(k)? What I am looking for is a counter example grammar.


texts: Calculus of constructions: Why forall when pi exists?

texts:
I'm studying the calculus of constructions from ATAPL, Chapter 2. I'm trying to understand the Type Equivalence rule, which describes the meaning of the new type family Prf a. The rule states:
Γ ⊢ T :: *         Γ, x:T ⊢ t: Prop
---------------------------------------[QT-ALL]
Γ ⊢ Prf (all x:T.t) ≡ Πx:T. Prf t :: *

This rule seems to state that types of the form of Prf(all ...) is equivalent to Π types. Combining this with the information that:

Prf: Πx:Prop.* [Prof needs Prop as input]
The only constructor of Prop is of the form all ...

implies that the only well-typed occurrence of Prf we can have is of the form Prf (all ...), which is equivalent to the Pi-type encoding (as given by QT-ALL).
Thus, I see no benefit gained by adding the Prf/Prop mechanism. I believe we gain something to do with impredicativity, as we can use all x:T.t : Prop to quantify over Prop itself. I don't know enough theory to judge whether this is possible or impossible just using Pi types.
Clearly, I am missing something. Could I please have an explanation of what we gain by introducing Prf/Prop that we did not already have with Pi types?
I've added a picture of the full definition here:


texts: k-testable languages with non-constant k?

texts:
Let $p_t(w)$ and $s_t(w)$ denote the prefix and suffix of length $t$ of the word $w$, respectively. If $|w| < t$, then $p_t(w) = s_t(w) = w$. Furthermore, let $i_t(w)$ be the set of infixes of length $t$ of $w$. (If $|w| < t$, then $i_t(w)$ is empty.)

For $k \in \mathbb{N}_0$, a language $L \subseteq \Sigma^\ast$ is said to be strictly $k$-testable if there is are sets $P, S \subseteq \Sigma^{\le k}$ and $I \subseteq \Sigma^k$ such that, for every word $w$, $w \in L$ if and only if $p_k(w) \in P$, $s_k(w) \in S$, and $I_k(w) \subseteq I$.

A language is strictly locally testable if it is strictly $k$-testable for some $k$. A language is locally testable if it can be expressed by the union, intersection, or complement of finitely many strictly locally testable languages. It is known that the locally testable languages are a strict subset of the regular languages.

(The above definitions are slightly adapted from here and  here.)

Are there any papers which analyse the case in which $k$ is no longer a constant? That is, when $k$ is allowed to scale with the length $|w|$ (but we still have $k \in o(|w|)$; e.g., $k = \log |w|$)? Clearly, the resulting languages will not necessarily be still regular, but they seem to be strongly related to parallel computing models such as cellular automata.

(My Google Scholar searches have been fruitless so far...)


texts: Fixed set of type constructors to simulate all intensional inductive families?

texts:
I'm wondering, are there small dependent calculi that can simulate a language with inductive families (that is, has a type isomorphic to each inductive family, at least as powerful of induction principles).

For example, I'm thinking:

You can use propositional equality to turn an inductive family into an inductive type with equality constraints on the indices
You can use Sigma types to encode sums-of-products
You can get inductive types with a fixed-point type:

data Fix : (Type -> Type) -> Type where
  Fold : (f : Type -> Type) -> f (Fix f) -> Fix f

which is fine as long as f is strictly positive.

But I'm not certain that these give you the full power of inductive families, particularly whether Fix gives you the full power of eliminators/structural recursion for inductive families.

Are there any references on what is sufficient to model inductive families?

I'm aware of:

W-types, which don't work well in an intensional setting.
Church-encodings, which aren't powerful enough to prove that (0 != 1), and also don't work well in a predicative setting
Levitation/datatype-generic-programming, which seems to give you all of inductive families, but at the expense of having to keep a runtime representation of every type, with a lot of complexity related to this representation. This seems like a chainsaw where I need a knife.


texts: Which algorithms are used most often in practice?

texts:
Which algorithms are used most often?

Please write a single algorithm per answer, try to keep your answer short (one or two lines).


texts: Site with collection of exercises in TCS?

texts: Is there a website with a large collection of exercises for theoretical computer science, sorted by topics? I know that many exercises can be found in different textbooks, I'm looking for an online database, preferably with hints/solutions included.


texts:
Is it known whether $Logspace$ is strictly contained in the polynomial time hierarchy ?
Are there oracles relative to which these classes are equal / distinct ?


texts:
This is a follow-up question to this one about infinite graphs.

Answers and comments to that question list objects and situations which are naturally modeled by infinite graphs. But there are also numerous theorems about infinite graphs (see chapter 8 in Diestel's book) of which, for example, Koenig's infinity lemma is a very famous one.

Now I have the following question: What can we prove with infinite graphs that we cannot prove without them? Or more specifically, what is an example where we model something as an infinite graph, then invoke a theorem about infinite graphs, and in the end have proved something about the original problem -- without knowing how to prove it otherwise?


texts:
I have read the paper by Anderson and Biham [0] describing the ciphers Bear and Lion, which combine a PRG and a hash function (each cipher does that in a different way). the authors proved that a key recovery attack on the ciphers would imply breaking the PRG and hash function used.
I also read the paper by Morin [1] in which he shows a man-in-the-middle attack on Bear and Lion, and also proposes a new cipher (Aardvark) of the same kind, immune to such attack.

Was there any attack on Aardvark?

And are there other block ciphers with proof of security?

The references are the following (sorry, I couldn't find exactly the publication years and conference names)

[0] Ross Anderson and Eli Biham. Two Practical and Provably Secure Block Ciphers: BEAR and LION.

[1] Pat Morin (1996). Provably Secure and Efficient Block Ciphers.


texts: How does communication complexity relate to time complexity in distributed algorithms?

texts:
Some distributed algorithms (e.g. Bracha broadcast) runs in a constant number of rounds. I'm interested on how you'd analyse the time complexity of such algorithm, especially when the message size changes.

Let the message be $m$. If the communication complexity is $O(n^2 |m|)$, then for every node it's $O(n |m|)$. Assuming every unit of communication has some fixed computational overhead (e.g. receiving/sending/parsing). Can I argue that the time complexity is also $O(n |m|)$? What would be the formal way to do this?


texts: Approximating transitive reduction of a transitive closure of a dag

texts:
Let's suppose a transitive closure $G^+$ of a dag $G$ is given and we want to compute an approximation of the transitive reduction $G^-$ such that the full transitive reduction is a subgraph of the approximation.

My idea is to compute a topological sort $TS$ of the dag and then for each edge $u \rightarrow v$ look at ~10 nodes $w$ such that $TS(w) > TS(v)$, $u \rightarrow w$ and $TS(w)$ are as large as possible. If $w \rightarrow v$ then edge $u \rightarrow v$ is redundant ($u \rightarrow w \rightarrow v$) and can be removed.

An implementation of this algorithm can be found here. The algorithm has complexity $O(m + n)$ and from my experiments the number of edges in the approximation is 3-5 times larger than in the full transitive reduction.

I have a couple of questions:

Can I prove any upper bound for the number of edges in the approximation?
How can I improve the algorithm (except looking at more $w$-s) in terms of time and/or number of edges left?


texts:
Can some one suggest a good source for VNP completeness of Permanent. I tried reading it from book on Algebraic complexity theory by Burgisser,clausen,shokrollahi,lickteig.
And What is the best known lower-bound on determinental complexity of $PERM_{n}$?


texts: Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard?

texts:
The usage of an $\mathrm{NP}$-oracles which delivers a witness has been proposed for example in [Buss1995]. I would like to see an example of an $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard problem. Can someone tell me?

Since I am not a complexity theory expert, I could not come up with an example nor could I find an example by searching through papers.

References:

[Buss1995] Buss, Krajíček, Takeuti, "Provably total functions in the bounded arithmetic theories $R_3^i$, $U_2^i$ and $V_2^i$" (1995)


texts:
I am reading
Leslie Lamport's Paxos Made Simple paper.

Can someone explain why $P2^c$ implies $P2^b$?

  $P2^b$ If a proposal with value $v$ is chosen,
  then every higher-numbered proposal issued by any proposer has value $v$.

  $P2^c$ For any $v$ and $n$,
  if a proposal with value $v$ and number $n$ is issued,
  then there is a set $S$
  consisting of a majority of acceptors such that either

  no acceptor in $S$ has accepted any proposal numbered less than $n$, or
  $v$ is the value of the highest-numbered proposal among
  all proposals numbered less than $n$ accepted by the acceptors in $S$.


texts: Sequences with sublogarithmic concat and approximate split

texts:
Is there a data structure for representing sequences that supports the operations:

concat takes two sequences of size $m$ and $n$ and produces a new sequence of size $m+n$ by joining them in time $o(\lg \min(n,m/n))$ (or $o(\lg \min(m,n/m))$ if $n>m$).
For some constants $c$ and $N$, approximate split takes a sequence of size $n > N$ and divides it into two contiguous non-overlapping sequences of sizes $p$ and $q$ such that $p+q = n$ and $1/c < p/q < c$ in time $o(\lg n)$
singleton takes a single element and produces a sequence containing only that element in $O(1)$ time.
linearize takes a sequence of size $n$ and produces an array of size $n$ containing the elements of the sequence in time $O(n)$.

I'm really looking for worst-case or expected bounds on the time, but amortized bounds would also be interesting. Results in the word RAM would be interesting as well.

Here are some results I am aware of. In this table, sloppy split is like approximate split, but the bounds are $1/c < (\lg p)/(\lg q) < c$.

   structure            |           concat           | approx split | sloppy split
==================================================================================
doubly-linked lists     |            O(1)            |     O(n)     |      *
arrays                  |           O(n+m)           |     O(1)     |      *
weight balanced trees   |         O(lg (n+m))        |     O(1)     |      *
treaps and skip lists   |       O(lg min(n,m)) **    |   O(1) **    |     *,**
functional finger trees |  O(min(lg lg m/n, lg lg n) |   O(lg n)    |     O(1)

*: same as approx split
**: expected

By functional finger trees I mean "Purely functional representations of catenable sorted lists" by Kaplan and Tarjan.


texts: Reference for a propositional proof system being equivalent to its soundness?

texts:
I am looking for the original reference for the following statement:

Let $P$ be a propositional proof system containing $EF$. Then $P$ is equivalent to $EF+Sound(P)$.

Background
A propositional proof system (pps) $Q$ can thought of as an nondeterministic algorithm for $TAUT$ (a certificate for a tautology is called a $Q$-proof for that formula).
A $Frege$ system is a pps similar to those used in the logic textbooks. It has lines which are formulas (using an adequate set of connectives, e.g. $\land, \lor, \lnot$) and a finite  complete set of deduction rules and axioms. Extended Frege, usually denoted by $EF$ or $EFrege$, is the pps resulting from adding the extension rule (which allows introducing new propositional variable as shorthand for formulas, i.e. it allows definitions). An equivalent system which might be easier conceptually to imagine is Circuit Frege (denoted by $CF$ and $CFrege$) and has circuits as its lines in place of formulas (refer to Emil Jeřábek's thesis for the definition of $CFrege$).
Soundness formula for a pps $Q$, denoted by $Sound(P)$ is the (family of) propositional tautologies that express the soundness of $Q$, i.e.

if $\varphi$ is provable in $Q$ then $\varphi$ is true.

More explicitly

if $\pi$ is a $Q$-proof of $\varphi$ and $\tau$ is a truth assignment then $\tau$ satisfies $\varphi$.

In symbols

$\pi : Q \vdash \varphi \implies \tau \vDash \varphi$.

The parameter for the family is the length of the proofs. Soundness is also known as the Reflection in the proof complexity literature.
We say two ppses are equivalent when the size of shortest proofs of tautologies in them are polynomially related, i.e. each one can simulate the other one with at most a polynomial proof size increase.
The choice of $EF$ is not essential for the equivalence in the question and one can take a weaker pps like Resolution (with some modifications). AFAIK this stronger version is first stated by Jan Krajicek.
The statement in the question is essentially saying that the soundness tautology for $Q$ is universal/complete for $Q$.


texts: Can any Calculus of Construction term be built up from application of a finite number of terms?

texts:
Can we form a finite set of well typed calculus of construction terms such that any closed term can be built up from them (plus the type of large types) using only application?

I conjecture that the following four combinators suffice:

P : T
∏ = λx:P. λy:(x→P). (∀a:x. ya)
S = λx:P. λy:P. λz:P. (λa:(z→y→x). λb:(z→y). λc:z. ac(bc))
K = λx:P. λy:P. (λa:x. λb:y. x)

(You would also need to have the above three combinators with P replaced by T, I think.)

For example, the type of m→n is ∏m(K P m n) (for closed terms m:P and n:P).


texts: Getting an automaton from set of words in and out of a language

texts:
Possible Duplicate:
  Is finding the minimum regular expression an NP-complete problem?

Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets of words $\mathcal I$ and $\mathcal O$ that are and aren't in the langueage, respectively. This means: $\mathcal I\subset\mathcal L$ and $\mathcal O\cap \mathcal L=\emptyset$.

Is there an algorithm that would try to generate the simplest possible automaton such that it accepts words in $\mathcal I$ and denies words in $\mathcal O$?

I know that there's no single automaton for any such case, but I believe my language is quite and the automaton should be simple as well.

My idea in the background is that I don't know the language, I have a program that enumerates it. I suppose the language is regular and I would like to prove it by proving that it's accepted by an automaton.

(NB: If this belongs to CS.SE, feel free to migrate it.)


texts: Given a subset of the hypercube and a copy translated by s, find s

texts:
Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible in randomized RAM model with say $d$-bit wide words. Here we think of bit strings as elements of $\mathbb{F}_2^d$ and addition is modulo 2, namely the xor operation. (Note that even though we receive both A and B, we are not told which element is a translated version of which.)

I have 3 4 questions regarding this problem. I have encountered this question in a competitive programming (practice) contest years back. Now revisiting this question, it really looks like it originated from some tcs related question.

  Has anyone seen this or a related problem in their research? Does this relate to any PCP or property testing related constructions? (Or Simon's problem in any way)

Naive solution

Fix an element $a_0\in A$ and for each element $x\in B$, guess that $s=x-a_0$ and verify this guess in linear time by computing $A+s$ and comparing it against $B$ (we can then compare $A+s$ and $B$ in linear time by, say, hashing as we are assuming $d$-bit wide words).
This gives us an $O(n^2)$ time algorithm.

A better solution:

Here is a solution that does much better for most inputs (which allowed me to pass the test cases during the contest). Pick a random subset of $S\in[d]$. Partition $A=\{x^1,x^2,\ldots,x^n\}$ into $2^{|S|}$ equivalence classes according to $x_S$. Here subscript means restricting $x$ to those coordinates in $S$. Denote for $v\in\{0,1\}^S$, the class of $v$ as $C_v = \{x\in A\mid x_S = v\}$. For $v\in\{0,1\}^S$, let $m_v = |C_v|$. Now let us partition $A$ into equivalence classes according to $m_{x_S}$ this time. Denote for an integer $i\in[n]$ the class of $i$ as

$$ D_i = \{x\in A\mid m_{x_S} = i\}.$$

Now take the smallest nonempty class $i^* = \arg\min_i |D_i|$. If we pick $a_0$ from this class, we just need to make $|D_{i^*}|$ guesses as to what element to pair $a_0$ with inside $B$. Therefore the runtime becomes $n|D_{i^*}|$.

An idea: What if we pick a random full rank matrix $M\in\mathbb{F}_2^{d\times d}$ and transform $A$ by $M$ first, does this ensure that $\mathbb{E}_{M,S} |D_{i^*}|$ is small for any $A$? Note that for $x^1, x^2\in A$ we have $(Mx^1)_S = (Mx^2)_S$ iff $(M(x^1+s))_S = (M(x^2+s))_S$

The above solution will not provide any improvements when $A$ is a subcube. Though, in this case we can easily solve it by other observations. In general I am unable to think of hard instances to this problem and suspect there should be a provably efficient solution for all inputs.

A Fourier theoretic approach:

Lets not try to learn $s$ all at once; that way we make no measurable progress up until we actually solve the problem. How about we try to learn s bit by bit. I will use A,B to denote the subsets of $\{0,1\}^d$ as well as the corresponding indicator functions. We have

$$\hat{A}(u) = \hat{B}(u)(-1)^{\langle u, s\rangle}$$

If we pick a random $u\in\{0,1\}^d$, by the above equation in linear time we will learn 1 bit of information about $s$, unless $\hat{A}(u) = 0$.

Note that this already solves the problem when $d\gg \log n$ due to the uncertainty principle in Fourier analysis: it will imply that at most $2^d/n$ Fourier coefficients are zero. Therefore the hardest case is when $d\approx \log n$.

What can we do in this case?

Question 2: What is the randomized RAM complexity of this problem?

Question 3: What is the quantum complexity?


texts: Online version of All pair shortest path when path weights are updated

texts:
Given

an undirected graph of $n$ nodes with weighted edges and
a sequence $S=((e,w),...)$ of updates, always decreasing, of the weight $w$ of edge $e$.

What is the online complexity of computing the shortest pair between each pair of nodes in the graph after each updates? Is there any solution better than solving the problem offline in time within $O(n^3)$ (using Floyd-Warshall's algorithm) after each update?


texts: What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?

texts:
What is the best deterministic result for maintaining the dynamic transitive closure in a directed graph with only edge insertion?

I read some papers on the dynamic transitive closure problem with both edge insertion and deletion. However, is there any better algorithms for that with only edge insertion?


texts:
A fractal maze is a maze which contains copies of itself. Eg, the following one by Mark J. P. Wolf from this article:

  Begin at the MINUS and make your way to the PLUS. When you enter a smaller copy of the maze, be sure to record the letter name of that copy, as you will have to leave this copy on the way out. You must exit out of each nested copy of the maze that you have entered into, leaving in the reverse order that you entered them in (for example: enter A, enter B, enter C, exit C, exit B, exit A). Think of it as a series of nested boxes. If there is no exit path leaving the nested copy, you have reached a dead end. Color has been added to make the pathways clearer, but it is only decorative.

If a solution exists, breadth-first-search should find a solution. However, suppose there is no solution to the maze - then our search program would run forever going deeper and deeper.

My question is: given a fractal maze, how can we determine if it has a solution or not?

Or alternatively, for a fractal maze of a given size (number of inputs/outputs per copy), is there a bound on the length of the shortest solution? (if there was such a bound, we could exaustively search only that deep)


texts: Asymptotic density of ambiguous context-free grammars (CFGs)

texts:
What is the ratio of ambiguous CFGs to all CFGs?

Since both sets are countably infinite the ratio is not well-defined.
But what about the asymptotic density:

$$\lim_{n \mapsto \infty}\frac
  {\# \text{ ambiguous CFG of size} < n}
  {\# \text{ CFG of size} < n}$$

where terminal and non-terminal symbols come from a fixed countable set.

The size of a grammar is any reasonable notion of size for grammars, e.g.

the total number of occurrences of variables and terminals in the production rules, or
the total number of occurrences of variable, or
the total number of production rules, or
the number of distinct variables.

(I am assuming the definition of size will not affect the answer.)


texts: Complexity of intersection of regular languages as context-free grammars

texts: Given regular expressions $R_1, \dots, R_n$, are there any non-trivial bounds on the size of the smallest context-free grammar for $R_1 \cap \cdots \cap R_n$?


texts: Applications of the monoidal closed structure in LTL?

texts:
A simple model of temporal logic is via time-indexed truth
functions. This lets us model the Boolean connectives, as well as the
next-step operator and modal always operator:

$$
\begin{array}{lclll}
  n & \models & P & \iff & \mbox{condition}\\\hline
  n & \models & \top & \iff & \mbox{always} \\
  n & \models & P \land Q & \iff & n \models P \mbox{ and } n \models Q \\
  n & \models & \lnot P & \iff & n \not\models P \\
  n & \models & X(P) & \iff & n+1 \models P \\
  n & \models & G(P) & \iff & \forall k.\; n + k \models P \\
\end{array}
$$

Thinking of this in terms of the Kripke-Joyal semantics for modal
logic leads us to observe that the natural numbers, viewed as a
discrete category, are monoidal with addition, and so the Day tensor
product
exists. Specializing the definitions gives us the following forcing clauses:

$$
\begin{array}{lclll}
  n & \models & P & \iff & \mbox{condition}\\\hline
  n & \models & P \otimes Q   & \iff & \exists j, k.\; j + k = n \mbox{ and } j \models P \mbox{ and } k \models Q \\
  n & \models & P \multimap Q & \iff & \forall k.\; k \models P \mbox{ implies } n + k \models Q \\
\end{array}
$$

So we have an adjunction between $\otimes$ and $\multimap$. Namely, we
can show that $P \otimes Q \vdash R$ if and only if $P \vdash Q
\multimap R$.

My questions are:

This structure is surely well-known to students of temporal logic. What is it called, and what is the standard temporal logic notation for it?
What is it used for? (I.e., what are some applications?)


texts:
Can first-order logic be modeled/simulated as linear programming or integer programming?
What about other forms of logic (say second order)?

Update:  am actually not a theory person, but more on the applied side in machine learning and AI. suppose you define a set of variables and some implication rules. Can we model this as an LP/ILP?

In the following, I define a a set of implication rules. Then I define a problem for fixed variables, and I ask some question. I also give the desired answer to each question(based on logical implication). The question is, can we model this problem as an LP/ILP?

Here is an example. Suppose I define the following types:

A = CHILD
B = PARENT
C = SIBLING

And I define the implication rule:

R1: For any $(x,y) \in A $ (meaning that $x$ is child of $y$) $\Rightarrow $ $(y, x) \in B$ (meaning that $y$ is parent of $x$).
R2: For any $(x,y) \in B $ (meaning that $x$ is parent of $y$) $\Rightarrow $ $(y, x) \in A$ (meaning that $y$ is child of $x$).
R3: For any $(x,y) \in C $ (meaning that $x$ is sibling of $y$) $\Rightarrow $ $(y, x) \in C$ (meaning that $y$ is sibling of $x$).
R4: or any $(x,y) \in C $ (meaning that $x$ is sibling of $y$) and $(y,z) \in A $ (meaning that $y$ is child of $z$) $\Rightarrow $ $(x, z) \in A$ (meaning that $x$ is child of $z$).

Now suppose we fix the variables (i.e. a problem is given).

Problem 1:
We know three variables $x, y, z$. We know the following facts

F1: $(x,y) \in A$ (i.e. $x$ is child of $y$).

And we want to be able to infer the answer to the following question(s):

 - Does it imply $(y,x) \in B$? (Answer: yes)
 - Does it imply $(y,z) \in C$? (Answer: unknown)
 - Does it imply $(z,y) \in C$? (Answer: unknown)

Problem 2:
We know three variables $x, y, z$. We know the following facts

F1: $(x,y) \in A$ (i.e. $x$ is child of $y$).
F2: $(x,z) \in C$ (i.e. $x$ is sibling of $z$).

And we want to be able to infer the answer to the following question(s):

 - Does it imply $(y,x) \in B$? (Answer: yes)
 - Does it imply $(y,z) \in C$? (Answer: yes)
 - Does it imply $(z,y) \in C$? (Answer: no)


texts: What is the optimal strategy for this 2 player game?

texts:
Let some finite array of integers is given initially.

There is a number k which is initially '0'.

In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]).

Also, the number chosen from the array(i.e a[i]) will be removed from that array.

CONSTRAINTS

A player who makes k=1 at any step loses.
A player who cannot move also loses.
2 players are playing the game optimally.

When will the player who moves first wins the game?


texts: Well Defined Ordering Relations in Object Oriented Type Systems

texts:
In any Object-Oriented type system the type relation of two objects A and B can be characterized in exactly one of the following ways:

A has the same type as B
A is a subtype of B
B is a subtype of A
A and B are not (directly) related.

My goal is to define an ordering relation which I can then use to demonstrate covariance and contravariance. The canonical ordering relation used for this in literature is a <: b, which is defined as "a is a subtype of b".

Since my math course at university (1st semester CS) has only covered partial orders so far, I tried starting with a simple partial order:

We can establish a well defined order relation between two types as "X is a subtype of or of the same type as Y", written as X <:= Y because it fullfils the three neccessary properties

Reflexitivity: For all types T, T<:= T.
Antisymmetry: For all types T and U, T <:= U and U <:= T implies U = T
Transitivity: For all types S, T and U S <:= U and U <:= T implies S <:= U

Now my problem is that I want to use this to show that covariant means (from wikipedia):

  a type operation is called covariant
  if it preserves the ordering, ≤, of
  types, which orders types from more
  specific to more generic;

I guess I'm in conflict with the definition if I substituted <: with my made up <:= relation here. However, this is just a gut feeling. So in order to arrive at <:, I'd need to make my partial ordering <:= a strict total ordering (if I understood correctly).

From a logical perspective this seems simple, however I struggle with the mathematically correct way of formulating this. Wikipedia seems to suggest that it should be possible:

  Contrast this [a total order] with a
  partial order, which has a weaker form
  of the third condition (it only
  requires reflexivity, not totality).

...

  For each (non-strict) total order ≤
  there is an associated asymmetric
  (hence irreflexive) relation <, called
  a strict total order

It seems I'm almost there, however this is completely new terrain for me and I'd like to how this could be done actually.


texts: Techniques for proving NP completeness for a specific sequence of instances

texts:
Most NP-completeness proofs I have seen pertain to proving that a problem on a class of instances is NP-complete. E.g., satisfiability is NP-complete on the class of instances with clauses having three literals. Usually these proofs exploit the room that the definition of the class allows to reduce every instance from a known NP-complete class to an instance in the class of interest.

The question I am interested in is somewhat nonstandard: suppose I have a sequence of instances $P_1,P_2,...$ with size of input $n_1,n_2,...$. The size  $n_k \rightarrow \infty$ as $k\rightarrow \infty$. I want to claim that this specific sequence of instances is NP-complete. I know the instances are in NP, only NP-hardness remains to be shown.

Here's the challenge. Because I have a specific instance for each $k$, I don't have adequate room in the definition to reduce the known broad classes to this class. Furthermore, the sizes of my instances are also fixed, which restricts me further. Conceptually, I think I will have to argue that for every instance in some NP-complete class, there exists a $k$ such that this instance reduces to $P_k$. But I am not aware of techniques that reduce known instances to instances of interest with such specificity.

So my question is: are there techniques for proving NP-completeness/NP-hardness type results for a specific sequence of instances?

In case it helps, the instances $P_k$ are 0-1 integer programming problems with specific constants; in fact the constraint matrix of $P_k$ contains that of $P_{k-1}$ as a submatrix for all $k$ and the number of variables $n_k = 2^k$. Notice also that the set of instances $P_k$ has cardinality of $\mathbb{N}$, which is also the cardinality of the number of SAT instances (or finite graphs, or integer programs etc); thus as far as I understand, there is nothing in principle preventing my sequence instances from being NP-complete.


texts: Do there exist x such that K(xx)<K(x), where K is Kolmogorov complextity.

texts: Let $K(x)$ denote the Kolmogorov complexity of a string $x$. Do there exist a string such that $K(xx)<K(x)$. (Here $xx$ is the concatenation of $x$ with itself). A similar but different question was asked here, but the counterexample given in the answer to that question doesn't work for this one.


texts: maximize edges minus vertices in a weighted graph

texts: for a given weighted vertices and edges graph, we want to find the maximum subgraph. the maximum subgraph is made of some vertices and some edges of the given graph which sum of the edges minus sum of the vertices is maximum. what is the algorithm for this problem? or any help with the code please.


texts: Is there an NP-complete language that contains precisely half of the n-bit instances?

texts:
Is there a (preferably natural) NP-complete language $L\subseteq \{0,1\}^*$, such that for every $n\geq 1$
$$|L\cap \{0,1\}^n|=2^{n-1}$$
holds? In other words, $L$ contains precisely half of all $n$-bit instances.


texts: Finding a 5-cycle in a sparse graph efficiently.

texts:
(crossposted from MathOverflow)

Hi,

I was reading this thread: https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length

I want to find a 5-cycle in a graph.  Actually, what I really want is a shortest odd cycle of length at least 5, but maybe that is a little beside the point.  For my purposes, I treat $m$ and $n$ the same in the complexity analysis.

Can we do better than colour coding for finding a 5-cycle in this case?  Let me give a specific formulation of my question:

  What is the minimum $\alpha$ such that there is an $O(m^\alpha)$-time algorithm for detecting a cycle of length 5?  What is the algorithm?  And what is this $\alpha$ if you forbid impractical methods like Coppersmith-Winograd fast matrix multiplication?


texts:
Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$".

This is the dual of the "near neighbour" problem studied by people like Andone and Indyk. I'm wondering if it has a name in the literature. Certainly "far neighbour" doesn't make much sense.

There are a few references on "farthest point queries", however nothing recent and nothing that works in high dimensions.

Are you aware of a name for the described problem in newer literature?


texts: Hyperspherical nature of K-means and similar clustering methods

texts:
Jain, Murty, and Flynn
state in their article Data Clustering: A Review
all squared error based clustering methods like K-means
tend to generate hyperspherical clusters.

However, they do not give a theoretical justification for this.

Is a theoretical justification for this observation?
Can we change the K-means algorithm to generate rectangular clusters?


texts: Properties of convex polytope of 0-1 matrices

texts:
Problem setting

Consider a set $ S = \big\{ 1,2,\cdots,n \big\}$. Now consider $k$ equal-sized subsets $S_i \subset S$ s.t of size $\big|S_i\big|=n' \;\forall i$.

Consider a $k\times k$  matrix $M$ s.t  $\;M_{ij} = \big|S_i\cap S_j\big|\big/n'$, size of the intersection of the $i^{th}, j^{th}$ subset divided by $n'$.

Question

Does $M_{ij}$ lie in the polytope of zero-one matrices? Paraphrasing the question - Can we express every $M_{ij}$ as a convex combination of zero-one matrices?


texts: Does hyper-computational power of infinite time Turing machines also require infinite memory?

texts: Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?


texts: Why is single authorship so common among breakthrough papers in computer science?

texts:
Looking at the list of important papers in computer science one notices that the majority are authored by a single author. Those include classic papers of Turing, Shannon, Karp and Cook. Cook's solo paper started the most important question of computer science.

How can we explain this? What are the implications to the creative process in theoretical computer science?

I am aware of paradigm shifts and paradigm blindness. However, I doubt they fully explain this phenomena.

Here is the list that includes important papers in TCS which motivated my question.


texts: Autoencoders and information compression

texts:
Disclaimer: I know very (very) little about deep nets, besides what an introductory course on machine learning would teach on neural networks, and skimming some paper abstracts and introductions.

If I understood correctly the concept, an autoencoder is a specific case of neural networks with as many input nodes than output nodes (say $d$), whose goal is to approximate the identity function
$$
\operatorname{id}\colon \mathbb{R}^d \to \mathbb{R}^d\,.
$$
The trick is that this net can be broken into two parts, "encoder" and "decoder" of the form $\Phi\colon \mathbb{R}^d \to \mathbb{R}^k$ and $\Psi\colon \mathbb{R}^k \to \mathbb{R}^d$, such that $k\ll d$. Therefore, there has to be something non-trivial going on for $\Psi\circ \Phi$ to approximate the identity, given the restricted width of the middle layers.

This struck me as begging the question:

  Can one (and has one already?) formalize and analyze this rigorously in terms of information theory, and specifically compression?

I realize the problem itself would need a more thorough and precise formulation to be tackled, as in the above we deal with full real numbers (so "hiding" information in a single real number, say the weight of a node in the middle layer, would give a very easy way out). But with this dealt with appropriately, hopefully there are non-trivial statements to be made with regard to what compression can be achieved, with respect to some distribution over the inputs?

Has this type of question been looked at from a theoretical viewpoint, in our community or another?


texts: How to find largest supergroup in polynomial time?

texts:
Let $G \le S_n$, and G acts on set $[n]$ via a map $\pi$:
$$\pi : G \times [n]\mapsto [n] $$

In Input generating set of $G$ is given.

Question : I need to find the largest supergroup $G^{'}$ (generating set) of $G$  in $S_n$ which has same blocks as $G$.

  For all $x \notin \langle G \rangle$

  check whether $\langle G,x\rangle$ has same blocks as $\langle G\rangle$

  If yes then add $x$ to the generating set of $G$
  Else do nothing

This is a brute force algorithm and running time of this algorithm is exponential many operations i.e. $O(n^n)$.

Question  : Is there an polynomial time algorithm for the above problem ?

Motivation : Isomorphism of hyper-graphs of low rank in moderately exponential time (see this)


texts:
I am faced with the following question on max. integer multiflow:

INSTANCE: An acyclic directed graph G=(V,E), a capacity function c:E→N, k pairs of vertices (si,ti) and a demand function d:{1,…,k}→N.
Objective: Find the integer flows satisfying maximum demand.

what is the hardness status of this problem?


texts: Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?

texts:
Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity.

Background/Motivation: Coming from information theory, I recently learned about a connection of entropy and Kolmogorov complexity: Loosely speaking, entropy of a random variable is the expected rate at which the Kolmogorov complexity of a long sample sequence increases per sample. [Elements of Information Theory, p. 154] Kolmogorov complexity can therefore capture the notion of entropy, but it is more general than that. Hereby, and in the following, whenever I write complexity, I implicitly refer to the complexity given the length of the output.

For non-zero entropy, the Kolmogorov complexity of initial segments of an infinite sequence of samples from a random variable is therefore unbounded. I was wondering whether this is equivalent to the fact that an infinite sequence of samples is uncomputable. This led me to the hypothesis in the title: Is a binary sequence computable if and only if the Kolmogorov complexity of its initial segments is bounded?

If the hypothesis was true, then computability could be understood as an indicator that the "amount of information" in a sequence is finite. In some sense, the initial segment complexities would allow a more finely graded characterization of infinite sequences than just "computable" and "uncomputable". We could get a notion of "information content" and "information rate" of infinite sequences by analyzing the size of the bound or, in the unbounded case, the rate/type of growth, as in the entropy case above. My question boils down to whether "computable" and "uncomputable" are regions on this scale.

If the hypothesis is true, I'd be interested in whether this perspective is useful for TCS research. If yes, are there references elaborating this idea? If not, why not?

What I found in literature: It is shown that a sequence is Martin-Löf random iff there is a constant $c$ so that there are infinitely many initial segments with complexity greater than $n - c$ where $n$ is the segment length. [Randomness, p. 18]

This means that random sequences have unbounded initial segment complexity. Since they are not computable, the hypothesis is true at least for this case. If I am not mistaken, a similar argument could even be made for a weaker form of randomness, since Mises-Wald-Church random sequences cannot have initial segment complexity of O(log n). [The complexity of stochastic sequences]

What's missing for a proof:

$\Leftarrow$:
Assume a sequence is computable. We know that a program generate_bit(n) exists that generates any bit of the sequence. Now, we can build a program generate_initial_segment(n) = concat(map(1..n, generate_bit)) that, given the segment length $n$, generates the initial segment up to position n by invoking generate_bit $n$ times and concatenating the results. The Kolmogorov complexity of this task is therefore bounded by the length of this program. ☐

$\Rightarrow$: I struggle to prove/disprove this direction, namely: If initial segment complexity is bounded, is a sequence always computable?

Update: The last two pages of A variant of the Kolmogorov concept of complexity prove this direction.


texts: What are "$\mu$-recursive functions" and $\mu$-calculus?

texts:
I saw in this question a reference to $\mu$-recursive functions or $\mu$-calculus as some computation model equivalent to Turing machines and $\lambda$-calculus. I know about these two but never heard of $\mu$-calculus. Can you briefly describe it and compare it with the other models? Bonus points for link references and books for beginners. Thanks in advance.

Edit: Ok, just for clarification i'm interested in both $\mu$-recursive functions and $\mu$-calculus.


texts: Is it possible to implement tail recursion inside a lambda calculus built on top of functions?

texts:
Inside a lambda calculus implementation for ECMASCript 6, we are trying to implement new constructs such as type tags for strong typing, and conditionals such as the if statement by wrapping in lambdas the branches of the conditional.

General recursion can also be implemented with the Y combinator. However, when trying to implement tail recursion we get an ever-expanding stack trace. Is it even possible to do so without resorting to while loops, which are not available in the primitives of lambda calculus? Is there a related impossibility result?


texts: Sample graph dataset for testing algorithms

texts:
I hope I'm addressing the right community. For a project for my students, I need to find some weighted graphs (oriented or not) to benchmark their algorithms (shortest paths, flows...).
There are a few samples on the companion site of the ALGS4 course from R. Sedgewick (Shortest Paths), but I would like some more datas, encoded in this simplest way (or easily convertible).
Maybe someone here is aware of some samples and could point me to it.
Thanks in advance.


texts: Expected length of longest construction path in Barabási–Albert Model

texts:
The Barabási-Albert Model is used for constructing scale-free networks using the preferential attachment technique. The essence, as I understand it, is that nodes are incrementally added to a graph by adding an edge to an existing node selected with probability proportional to the number of edges connecting the node. The algorithm starts on some initial clique, $G$.

Now let's assume that newly added nodes are labelled $0, 1, 2, \ldots$.
Define a construction path to be a path $l_0l_1l_2\ldots l_n o$ in the generated graph such that $o$ is a node from the initial clique $G$, $l_n<\cdots<l_2<l_1<l_0$ and $l_0$ is maximal.

Clearly, at one extreme, such paths will be of length $1$, when all newly added nodes connect to one of the initial nodes.
At the other extreme, the length of the path will be equal to the number of nodes added to the graph. Both of these cases are extremely unlikely.

I'm interested in the average case.  Are there any known results about the expected value of the lengths of construction paths?

NB. Construction path is a name I invented for this question: please let me know if such paths go by another name.


texts: Relationship between symmetry and computational intractability?

texts:
The $k$-fixed point free automorphism problem asks for  a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0.

However, If $k(n)=O(\log n)$ then the problem is polynomial time Turing reducible to Graph Isomorphism Problem. If $k(n)=O(\log n/\log \log n)$ then the problem is polynomial time Turing-equivalent to the Graph Automorphism problem which is in $NPI$ and is not known to be $NP$-complete. The Graph Automorphism problem is Turing reducible to the Graph Isomorphism problem.

On the Complexity of Counting the Number of Vertices Moved by Graph Automorphisms,
Antoni Lozano and Vijay Raghavan

Foundation of Software Technology, LNCS 1530, pp. 295–306

It appears that computational  hardness increases as we increase the symmetry of the object we are trying to find (as indicated by the number of nodes that must be moved by the automorphism) . It seems this may explain the lack of polynomial time Turing reduction from the NP-complete version to Graph Automorphism (GA)

  Is there another example of a hard problem which supports this relationship between symmetry and hardness?


texts: What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?

texts:
The question I am interested in is related to generating random permutations. Given a probabilistic pairwise swap gate as the basic building block, what is the most efficient way to produce a uniformly random permutation of $n$ elements? Here I take "probabilistic pairwise swap gate" to be the operation which implements a swap gate between to chosen elements $i$ and $j$ with some probability $p$ which can be freely chosen for each gate, and the identity otherwise.

I realise this is not usually the way one generates random permutations, where usually one might use something like a Fisher-Yates shuffle, however, this will not work for the application I have in mind as the allowed operations are different.

Clearly this can be done, the question is how efficiently. What is the least number of probabilistic swaps necessary to achieve this goal?

UPDATE:

Anthony Leverrier provides a method below which does indeed produce the correct distribution using $O(n^2)$ gates, with Tsuyoshi Ito providing another approach with the same scaling in the comments. However, the best lower bound I have so far seen is $\lceil \log_2(n!) \rceil$, which scales as $O(n\log n)$. So, the question still remains open: Is $O(n^2)$ the best that can be done (i.e. is there a better lower bound)? Or alternatively, is there a more efficient circuit family?

UPDATE:

Several of the answers and comments have proposed circuits which are comprised entirely of probabilistic swaps where the probability is fixed at $\frac{1}{2}$. Such a circuit cannot solve this problem for the following reason (lifted from the comments):

Imagine a circuit which uses $m$ such gates. Then there are $2^m$ equiprobable computational paths, and so any permutation must occur with probability $k 2^{−m}$ for some integer k. However, for a uniform distribution we require that $k 2^{−m}=\frac{1}{n!}$, which can be rewritten as $k n! = 2^m$. Clearly this can't be satisfied for an integer value of $k$ for $n\geq3$, since $3|n!$ (for $n\geq 3$, but $3\nmid 2^m$.

UPDATE (from mjqxxxx who is offering the bounty):

The bounty being offered is for (1) a proof that $\omega(n \log n)$ gates are required, or (2) a working circuit, for any $n$, that uses less than $n(n-1)/2$ gates.


texts:
First of all, I apologize in advance for any stupidity. I am by no means an expert on complexity theory (far from it! I am an undergraduate taking my first class in complexity theory) Here's my question. Now Savitch's Theorem states that
$$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right)$$
Now I'm curious if if this lower bound was tight, i.e that is something along the lines of
$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^{1.9}\right)$ is not achievable.

It seems like something there should be a straightforward combinatorial argument to be made here - each node in the configuration graph for a Deterministic Turing machine has only one outgoing edge, while each node in the configuration graph of a Non-Deterministic Turing machine can have more than one outgoing edge. What Savitch's algorithm is doing is converting configuration graphs with any number outgoing edge to configuration graphs with $<2$ outgoing edges.

Since the configuration graph defines a unique TM (not sure about this), the combinatorial size of the latter is almost certainly larger than the former. This "difference" is perhaps a factor of $n^2$, perhaps less - I don't know. Of course, there are lots of little technical issues to be worked out, like how you need to make sure there are no loops and so forth, but my question is if this is a reasonable way to begun proving a thing like this.


texts: Split or merge Binary Search Trees in O(log n)

texts:
We need to have an efficient operation of merging or splitting two binary search trees $S_1$ and $S_2$. There are given the following.

The element with the largest value in $S_1$ is smaller than the element with the smallest value in $S_2$. Abusing the notation $S_1 < S_2$.

We define as merge operation the operation which requires the two trees $S_1$ and $S_2$ and produces a valid binary search tree $S$ containing all of their elements.

Similarly, $S$ is split in two binary search trees $S_1$ and $S_2$ given an element $k$ for which (abusing the terminology again) $S_1 \le k < S_2$.

The best solution I have come up with in order to convince myself that this is possible, is by using splay trees. To merge we put the smallest element of $S_2$ as the root of the new tree with $S_1$ as the left subtree and $S_2$ as the right subtree (alternative we use the largest element of $S_1$ if it smaller). Amortized time $O(\log n)$. Similarly, we split by searching for the element $k$... Amortized time $O(\log n)$ again.

Is there anything better?

(Sorry for the lack of imagination in my question, this is my first post here.)


texts: Does a noisy version of Conway's game of life support universal computation?

texts:
Quoting Wikipedia, "[Conway's Game of Life] has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life."

Do such results extend to noisy versions of Conway's Game of Life?
The simplest version is that after every round every live cell dies with a small probability $t$ and every dead cell becomes alive with a small probability $s$ (independently).

Another possibility is to consider the following probabilistic variant of the rule of the game itself.

Any live cell with fewer than two live neighbours dies with probability $1-t$.
Any live cell with two or three live neighbours lives with probability $1-t$ on to the next generation.
Any live cell with more than three live neighbours dies with probability $1-t$.
Any dead cell with exactly three live neighbours becomes a live cell with probability $1-t$.

Question: Do these noisy versions of the Game of Life still support universal computations? If not, what can be said about their "computational power"?

Related information on the computational power of cellular automata and noisy versions of cellular automata will be also much appreciated.

(This question developed from this question on MathOverflow. Vincent Beffara's answer on MO gave interesting references for related results on computational aspects of noisy cellular automata.)


texts: NP-hardness proof: looking for some good restricted np-hard problems

texts:
To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can be used for the reduction, but in practice, some of the problems are more easily reduced than others.

For instance, 3-SAT is usually a better choice for constructing a reduction than SAT because the former one is more restricted than the latter one, 3-partition is usually an easier choice than bin packing, ...

One way to find such "good" problems for the reduction is to do a statistical analysis over the existing reductions. E.g., one can shape all the pairs of from -> to reductions of the book Computers and Intractability: A Guide to the Theory of NP-Completeness
(or other resources)
and draw a histogram of the problems in the from set.
Then we can find out which problems are more commonly used for reductions.

I wonder if such a statistical analysis makes sense at all. Has such a research been already conducted or not? If not, what is your guess about the most commonly used problems for
reductions.

The reason I am asking this question is that I have already done a few proofs of NP-hardness, but almost all of them rely on reduction from the same problem (3-partition).
I am looking for other options to use in my proofs.


texts: What is the asymptotic time complexity of the number of steps of "Half Or Triple Plus One" ( HOTPO)?

texts:
The "Half Or Triple Plus One" process goes as follows:

  start with $x=n$ for some value of $n$
  if ($x$ is odd)

  $x = 3x+1$

  else

  $x = \frac{x}{2}$
  if ($x$ > 1) goto (2)

Define $f(n) = $

total stopping time of $n$, i.e. The number of steps required for the procedure to halt.

The Collatz conjecture suggests that the process stops for every value of $n$, hence if the conjecture holds, $f$ is well defined.

The question is:

  What is the asymptotic time complexity of calculating $f(n)$?


texts: Book for self study of algorithms in group theory

texts:
I am a math major interested on TCS.

I want to self-study the algorithms, and complexity of them for solving the group theoretical problems like find order of elements, coset enumeration, find generator, test if a given subset generates the group.

What book should I read?


texts: For log-space machines, why do we care about PRGs?

texts:
Assumptions

I believe RL can be derandomized in polynomial time:

We need to store the following state:

The position of the head on the input.
The state of the TM

Both can be stored with O(log n) bits.
We use dynamic programming, building a table of poly(n) size encapsulating the state of the TM. Then, we march along the random bits, calculating the probability of each TM state after reading a given bit.

This should give us exact acceptance probability in $poly(n)$ time.

Observation

People care about prgs for log space machines.

Question:

Why? What can we do with a prg for RL that we can't do with an exact acceptance probability algo for RL ?

What is implied by a O(log n) seed length PRG for RL?

Thanks!


texts: On succinct $EXP$ and $NEXP$ complete problems?

texts:
We know succinct version of many $P$-complete problems are $EXP$-complete. There are standard ways to define $EXP$-complete graph problems from succinct representations of these $P$ complete problems.

What is the standard way to define $EXP$-complete problem from succinct representations of $P$ complete problems that do not come from graphs if there are any?

For example what is the succinct version of the $P$-complete iterated mod problem $$\mbox{given }a, b_1, b_2,\dots, b_n\in\Bbb Z,\mbox{ is }((\dots((a \bmod b_1) \bmod b_2) \dots) \bmod b_n) = 0$$ and would that be $EXP$-complete and what is the succinct version of linear programming and would that be $EXP$-complete?

Is there a higher version of $ETH$ (Exponential Time Hypothesis) that is applicable to the $EXP$ versus $NEXP$ problem for $NEXP$ complete problems that come from succinct version of $NP$ complete problems?


texts: What literature exists on Lévy flights for computational search?

texts: I just finished Albert-László Barabási's popular science book "Bursts: The Hidden Pattern Behind Everything We Do" which describes the Lévy flight as an ideal strategy for finding scarce resources in an environment. I immediately wondered whether anyone had studied them as a search algorithm. I could imagine them being more or less useful depending on the makeup of the search space. Have there been any papers on the subject?


texts:
Are there cases where extra publications can hurt your record?

This is avoiding the obvious cases where you publish incorrect, or controversial results. Also avoiding the case of finite-time: you only have so much time to think and write, so writing a paper might cause you to lose time on another project.

An example use-case might be: you are aiming for a position in theoretical computer science, but often publish in non-theoretical areas which might be under the broader CS canopy or maybe even completely unrelated to CS. On the one hand, this can show broad interests and breadth. On the other hand, this could show a lack of focus, opportunism, or lack of commitment to the field.

Can you avoid the problem by simply listing 'selected publications' on your CV that tailors to the specific position, or will the hiring committee always google scholar you? If so, when should you consider not publishing or publishing under pseudonym (or alternative spelling of name)?


texts:
You are given $n$ boxes and want to stack them to make a tallest possible tower, but you can only stack a box on top of another if the base is smaller in both dimensions.  This is a classic dynamic programming problem, and yet I can't easily find answers online to natural questions:

If the boxes cannot be rotated, what is the complexity of this problem?  A standard dynamic programming algorithm gives $O(n^2)$.  Can you do $O(n \log n)$?  Any conditional lower bounds?
If the boxes can be rotated, what is the complexity?  Note that I do not have $n$ types of boxes and infinite instances of each type, I have $n$ boxes.
What is the complexity in higher dimensions?
What is the complexity if the dimensions are integers from $1$ to $k$?


texts: Searching for name of equivalence property in hamiltonian paths

texts:
This one has been bugging me for a while. A long time ago in undergrad, I noticed this while learning about TSP. Nobody recognized it and I basically gave up.

Given a hamiltonian path, any subpath will consist of a start, end, and set of interior vertices. Any ordering of the interior vertices will possibly yield a path existing within the graph, that when substituted for the original will yield another valid hamiltonian path. These subpaths would therefore form an equivalence class.

Under this relation, two paths would be equivalent if they have the same start vertex, the same end vertex, and the same set of interior vertices.

Does this equivalence class have a name? If so, are there any TSP optimization algorithms that make use of this?


texts: Earliest forbidden subgraph characterisation

texts:
I wonder, what was the first non-trivial graph class for which there was a forbidden (induced) subgraph characterisation ?

Of course, bipartite graph is one example but I am considering it as trivial because of the simplicity of the proof of sufficiency.

Another example can be planar graphs, but does Kuratowski's Theorem qualify as a forbidden subgraph characterisation ?

Do you think that the Boland-Lekkerkerker characterisation of interval graph can qualify as the first instance of non-trivial forbidden induced subgraph characterisation? Or does there exist such an example which appeared before ?


texts: I have read in several papers it is well known that deterministically extracting even one bit from a weak source is impossible. Could someone explain why?


texts: Heyting algebra in simply typed lambda calculus

texts:
The Emil Jeřábek's comment in Can boolean algebra be expressed in simply typed lambda caclulus? give rise to the following question:

Can some non-trivial Heyting algebra be expressed in simply typed lambda calculus?

Consider, for example, the simplest Heyting algebra that is not already a Boolean algebra, that's the totally ordered set $\{0, \frac 12, 1\}$ described here.

More generally, I ask if is possible to build a type $H$ togheter with two terms $\mathrm{true},\mathrm{false}:H$ and functions $\wedge, \vee, \Rightarrow, \neg:H\to H$ satisfying the inference usual rules for intuitionistic logic, exception for the excluded middle.


texts: Trees that structure partially ordered data

texts:
Suppose we have a binary search tree $T$ built over keys from a totally ordered set, and we want to support the standard dictionary lookup $\mbox{Find}(x)$ which returns a pointer to the node containing key $x$, or reports that $x$ is not contained in $T$.

Normally, we start a query from the root of a binary search tree, but we don't have to.
From any node in the search tree, we can traverse the tree to find the location of any key in the search tree using only local information stored at each node. This takes $O(h)$ time, where $h$ is the height of the tree.

Now suppose we want to support that same $\mbox{Find()}$ query over keys drawn from a partial order.
A quadtree built over 2d points has these three interesting properties:

The data in the tree is partially ordered.
We can perform a $\mbox{Find()}$ query in $O(h)$ time using only local information at each node.
It is often used to answer more complex queries.

Question: are there other tree data structures that meet these three criteria?

Justification of the three criteria for the quadtree is included below:

1) Points in two dimensions are partially ordered. Sorting 2d points, or finding the successor of a point $(x,y)$ doesn't have meaning unless we first define a total order on the points, essentially projecting them down to one dimension. (Sort these points lexographically, find the successor of $(x,y)$ along this space-filling curve).

2) Each cell of a quadtree stores an axis-aligned rectangle, and the rectangle of a parent is the union of the rectangles of the children. We can navigate to the correct node in $O(h)$ time by comparing the point we are searching for with the rectangle stored at each node along our search path.

3) e.g. Approximate nearest neighbor or approximate range queries.


texts: Find negative cycle with vertex constraints

texts: Given a graph with weighted edges, how can we find a negative cycle that contains at least one vertex in a given vertex set $\{V_1, V_2, \ldots, V_k\}$? Thanks.


texts:
I'm doing a bit of research on doing social analysis between so called "hub" people.  Basically what I want to try to do is determine the shortest paths between two individuals.  The problem is that while there are relatively few individuals (a few hundred at most), there are a LOT more connections between the nodes (and several categories of connections).  So while a graph may have 100 nodes, there may be tens of thousands of connections (Some of which are redundant).

Now, what we want to try to do is show the relationships from each individual to each other.  So for example, if you pick person A, show all of their first degree relationships.  Then show all second degree relationships, etc until all the relationships are shown.

There may be as many as 1000 nodes and 100,000 connections, but I don't think too much more than that.  Are there any simple algorithms available for this, or would pre-computing unique permutations (via a Map-Reduce style system) be my best bet?

Am I right by thinking this problem is a NP problem (I don't think it's NP-Complete, but it might by NP-Hard)?

Thanks


texts: Tribes function vs (modified) polynomial threshold circuits

texts: Are there lowerbounds known for representing the Tribes function by a circuit consisting of a single layer of polynomial threshold gates feeding into maybe a trivial summing gate? (Even for degree $1$ polynomials?)


texts: PAC learning and computation over real numbers

texts:
I became familiar with the BSS model of computation recently.
I find it to be a better model of computation to study complexity of numerical analysis methods (cf. Complexity and Real Computation; Blum, Cucker, Shub, Smale.)

Most of the existing PAC learning theory is concerned with standard computation model. I was wondering,

  are there any research or literature regarding PAC learning in the BSS model?

The reason is that most of practical methods of computation over real numbers are based on numerical analysis which seem disconnected from the standard PAC learning developed in TCS community. Whereas the BSS model seems natural and well-suited for such studies.


texts: Importance of irrational numbers in computer science

texts: Computers can only deal with a few rational numbers. Why is it important as a computer scientist to deal with irrational numbers?


texts: Is `sort` typeable on elementary affine logic?

texts:
The following λ-term, here in normal form:

sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l))
       (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j
       (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c))

Implements a sorting algorithm for church-encoded lists. That is, the result of:

sort (λ c n . (c 3 (c 1 (c 2 n)))) β→ (λ c n . (c 1 (c 2 (c 3 n))))

Similarly,

sort_below = λabcd.a(λef.f(λghi.g(λj.h(λkl.kj(ikl)))(hi))e(λgh.h))
            (λe.d)(λe.b(λf.e(f(λghi.hg)(λgh.cfh))))

Also implements sorting for the same lists as above, except you must provide an additional argument with a limit for the numbers it will consider:

sort_below 4 [5,1,3,2,4] → [1,2,3]

I am trying to determine whether those terms are typeable on elementary affine logic. Since I don't know any EAL type-checker publicly available, this is proving a harder task than I expected. Is there a type for sort in elementary affine logic?


texts: What is this matrix column-selection problem, and how hard is it to approximate?

texts:
I ran across the following simple-to-state problem involving selection of a subset of columns simultaneously for a number of matrices. I suspect it might be well known, though I can't seem to place it.

The input is a set $A^1,\ldots,A^m \in {\mathbb R}^{n \times n}$ of $n\times n$ real-valued matrices. A feasible solution is a set of columns $S \subseteq \{1,\ldots,n\}$.  The value of $S$ is the sum, over all matrices $A^k$, of the maximum sum of a row of $A^k$ when restricted to columns $S$. Formally,

$ val(S) = \sum_{k=1}^m \max_{i=1}^n A^k_i \cdot 1_S,$

where $A^k_i$ denotes the i'th row of matrix $A^k$, $\cdot$ denotes dot product, and $1_S$ denotes the $\{0,1\}$ vector with a 1 in columns corresponding to S. The objective is to find a set of columns $S$ maximizing $val(S)$.

Is this problem well known? What is known about the polynomial-time solvability or approximability of this problem?

Here is what I know. Observe that this problem is trivial when the matrices all have nonnegative entries --- here picking S to be all columns is optimal. The problem is also trivial when the input consists of a single matrix --- simply try all rows and select all positive entries in the row. Therefore, this problem is interesting only when the input consists of many matrices, and the matrices have both positive and negative entries. A (simple though nontrivial) reduction from max-cut shows that this problem is NP-hard, and UGC-hard to (multiplicatively) approximate better than the Goemans-Williamson constant. Beyond that, I don't know much else.


texts: What is the difference between ${\bf P ^{\bf FewP}}$ and ${\bf UP ^{\bf FewP}}$?

texts: What is the difference between ${\bf P ^{\bf FewP}}$ and ${\bf UP ^{\bf FewP}}$ ? In other words, what is the language that can be decided by ${\bf UP ^{\bf FewP}}$, but cannot be decided by ${\bf P ^{\bf FewP}}$ assuming that ${\bf P} \not = {\bf UP} \not = {\bf FewP}$.


texts:
I'm currently reading through the tome "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield, and I find the proofs to be extremely case analysis heavy and full of finicky +-1s. This seems very error prone to program.

I was hoping for a more "conceptual" way to build string algorithms, where we first construct a toolkit of basic objects that we then use. I was hoping that prefixes, suffixes, and the Z algorithm would be those. But they seem too level to construct something like Boyer-Moore or Aho-Corasick.

As an analogy for some kind of abstract algebraic flavoured approach, like using matroids for greedy algorithms to capture the "hard" part of the analysis.

So my question is, are there nice algebraic structures that govern string algorithms which can be used to present and implement them more elegantly?