For question borderline with, or having application to, computer science. Consider also posting http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ instead of here, if appropriate.

learn more… | top users | synonyms

1
vote
1answer
91 views

Total conditional complexity

By $C(|)$ denote conditional complexity. By $CT(|)$ denote total conditional complexity. For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$ but $CT(x|y) \ge n $. ...
25
votes
0answers
646 views

Computer calculations in A_infinity categories?

Is there a good computer program for doing calculations in A-infinity categories? Explicit calculations in A-infinity categories are an important, useful, yet very tedious task. One has to keep ...
11
votes
0answers
307 views

Splay trees and Thompson's group $F$

( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but: Question: Is there a reformulation of the Dynamic ...
9
votes
0answers
268 views

Various definitions of recursion from ordinal machines

Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...
9
votes
0answers
669 views

Finding a set with the maximum number of finite alphabet strings within a fixed Levenshtein distance of one-another

Please consider the set of all possible strings of some finite size $M$ alphabet $\Sigma$, $\alpha$ $= a_1, a_2, ..., a_k, ..., a_n$, of length $|\alpha| = L$. The Levenshtein distance (or 'edit ...
8
votes
0answers
1k views

Question on randomness extractors

Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$. The adversary doesn't ...
6
votes
0answers
729 views

How many 2L-bit numbers are the product of two L-bit numbers?

If I multiply two integers $x, y $ in $[0,2^L)$, I get an integer in $[0,2^{2L})$. Clearly, this map from $[0,2^L) \times [0,2^L) \to [0,2^{2L})$ is not bijective. I am interested in the size of ...
6
votes
0answers
148 views

Finding a database of representations as matrices

Sorry if this would be more appropriate as a stackoverflow and not a mathoverflow question, but I think it's more likely to be known in this community. There are plenty of places on the internet or ...
5
votes
0answers
107 views

Are there sampNP-intermediate problems?

This questions is approximately cross-posted from theoretical computer science stackexchange Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} ...
5
votes
0answers
198 views

Büchi automata with acceptance strategy

I have already asked this question on cstheory.stackexchange, but without success. Maybe it is too close to an "open problem", although it is not a famous one. Anyway I try here, I can always remove ...
5
votes
0answers
328 views

Chain/Hierarchy of Monoids

Let's assume that we have the following collection of structures: Some space $P$. Monoids $(M_{i+1},\circ_{i+1})$, and Actions $\bullet_{i+1}:M_{i+1}\times M_i\to M_i$, for $i\ge 0$ And ...
4
votes
0answers
239 views

About “natural proof” of Razborov and Rudich

The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , ‎of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...
4
votes
0answers
160 views

Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$. The graphs have a significant automorphism group (these are disconnected ...
4
votes
0answers
94 views

Question about constructing an admissible ideal of a quiver of an algebra with the aid of a computer

Let $k$ be an algebraically closed field and $A$ a finite-dimensional, basic, connected $k$-algebra. Then $A$ is Morita-equivalent to a quotient of a path algebra $kQ/I$ and $I$ is an admissible ...
3
votes
0answers
125 views

Correspondence between numerical semigroups and polynomials?

A numerical semigroup $A$ is defined as a subsemigroup of the semigroup $(\mathbb{N},+)$ of the positive integers such that the set $\mathbb{N}\setminus A$ is finite. Equivalently (for a subsemigroup) ...
3
votes
0answers
316 views

Groupoid interpretation of type theory

Hello, I read the paper on groupoid interpretation of type theory by Hofmann and Streicher and I have a question. According to the authors $Tm([[\text{Set}\:[\Gamma]\: ]])$ is the same as ...
3
votes
0answers
306 views

Inversion density: Have you seen this concept?

Let n > 1 be an integer. Let A be an array, indexed from 1 to n, of n values A(i) coming from the finite set {0,1}. (More generally, the values can come from any totally ordered set, but I only need ...
3
votes
0answers
365 views

Wolff's application of CS to analysis

In the foreword of Tom Wolff's "Lectures on Harmonic Analysis", C. Fefferman writes "[Wolff made] (as far as I know) the first serious application of theoretical computer science to analysis." What ...
2
votes
0answers
30 views

largest size for a randomness extractor

I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature. Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...
2
votes
0answers
50 views

Private Randomness extractor

Suppose we are given two random variables $X$ and $Y$ with fixed marginal and joint distribution. What is the maximum randomness that we can extract from $Y$ that is independent from $X$, that is, if ...
2
votes
0answers
54 views

Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
2
votes
0answers
151 views

Is it possible to implement η-reduction in interaction nets?

There are several ways to encode λ-terms in interaction nets; for instance, using the original optimal algorithm by Lamping, or compiling λ-calculus into interaction combinators. However, all the ...
2
votes
0answers
156 views

A primal-dual (double) circle packing (coin graph) question

I know that any 3-connected simple planar graph with a designated outside face (outer face) has a primal-dual (double) circle packing (Brightwell-Scheinerman Theorem). Q1- But I am not sure whether ...
2
votes
0answers
106 views

How to argue about state transitions?

Computing differs from math by its dependence on state changes, among other things. A program can be seen as a composition of state transitions, and it would be nice to have an inverse function to ...
2
votes
0answers
224 views

what is the largest gap between rank and approximate rank

$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} ...
2
votes
0answers
257 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
2
votes
0answers
183 views

Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed? More precisely, suppose that for any deterministic TM $M$ accepting $$ ...
1
vote
0answers
75 views

Is there any track for proving $D=NP$, besides showing that $D$ has polynomial-bounded universal quantifiers?

Background By the MRDP theorem, every for every recursively enumerable set $S$, there exists a Diophantine polynomial $p$ such that $$x \in S \iff \exists y_1, \dots, y_n \in \mathbb{N} \text{ such ...
1
vote
0answers
89 views

Indecomposability of image transformations (pure algebra). Open questions

W-transformations -- definitions We will consider a class called finite window transformations $\ T:C^\mathbb Z\rightarrow C^\mathbb Z\ $ defined a paragraph below; $\ \mathbb Z\ $ is the ring of ...
1
vote
0answers
79 views

Testing functional equivalence

We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...
1
vote
0answers
117 views

Is there an easy decision algorithm for the inhabitation problem for simple types?

Consider the basic system of simple types usually known as $TA_\lambda$. One can prove that (as a consequence of the Subject Reduction Property and the fact that any typable term is strongly ...
1
vote
0answers
92 views

Schönhage's SMM with only one instruction

It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...
1
vote
0answers
62 views

Optimal Reduction in Interaction Calculus

We work in interaction calculus. Let $\Sigma = \{\lambda, \psi, \delta, \epsilon\}$, $\text{Ar}(\lambda) = \text{Ar}(\psi) = \text{Ar}(\delta) = 2$, and $\text{Ar}(\epsilon) = 0$. For any $\alpha ...
1
vote
0answers
108 views

Turing-complete primitive interaction systems

Let us call primitive an interaction system with the signature $\Sigma = \{(\rho, 0), (\xi, n)\}, \quad n \geq 2;$ and the only rule being of the form $\rho \bowtie \xi[\rho, \xi(a_1, \dots , a_n), ...
1
vote
0answers
187 views

A Multiplicative version of McDiarmid's Inequality like the one of Chernoff-Hoeffding Bounds

McDiarmid's Inequality basically says the following: Let $X_1, X_2, X_3, \ldots, X_n$ denote independent random variables and $f$ is a function of $n$ real arguments. If changing the value of the ...
1
vote
0answers
309 views

The used symbols for equality and equivalence

Background: I am currently developing a general purpose programming language which allows formal verification (i.e. correctness proofs) of programs. During the development it came out that a lot of ...
1
vote
0answers
129 views

Optimizing for a unique outcome of a probabilistic marriage problem

Let's say I have some number of individuals who are single, $(b_1, ..., b_N) \in B$, and for every possible pairing of two individuals, $b_i$ and $b_j$, I happen to know the exact probability that the ...
1
vote
0answers
204 views

Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there) The following ...
1
vote
0answers
342 views

NP-complete variants of NPI problems

Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that ...
1
vote
0answers
366 views

Minimizing quadratic form over permutations

Let $Q$ be an $n \times n$ real symmetric matrix and $x$ an $n \times 1$ real vector. Consider the following minimization problem: $\min_{\pi \in S_n} ~(\pi x)^{\rm T} Q (\pi x)$, where $S_n$ ...
1
vote
0answers
399 views

Cluster-preserving and distance-maximizing embedding into Hamming Space?

I have a set of data, each instance in the real $[0,1]^{d}$. However, it's actually all in a relatively small range around 0.5, clustered into classes in even smaller ranges. The actual origin of the ...
0
votes
0answers
32 views

Any software that can symmetrize input sets?

Is there any software that contains symmetrization techniques ex. polarization, Steiner Symmetrization etc. I suppose not. Which software would you suggest for rigid transformations? Thank you
0
votes
0answers
72 views

Proof of conjecture that permutation-free automata restrict the possible states visitable from a stringset sharing prefixes and infixes

An automaton $\mathcal A = (X, Q, \delta, q_0)$ is called permutation-free iff no word $w \in X^*$ induces a nontrivial permutation of a subset of the states of $\mathcal A$. More formally for any $R ...
0
votes
0answers
226 views

Extended definition of unambiguous language and the existence of unambiguous grammar

Let's extend the unambiguity of language and grammar as follows: a language $L$ is unambiguous if there is a grammar that generates every word in $L$ in a unique way, the grammar may be of type 0 or ...
0
votes
0answers
194 views

An interesting version of the problem “balls into bins”

Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
0
votes
0answers
85 views

Exact Length Problem in a directed graph

I have a directed graph that consist of N^2 vertices (like a square) and each vertex is connected to at most 1 node (not bidirectional) and every connections have length 1. There are no cycles in the ...
0
votes
0answers
349 views

Examples of Hamiltonian Cycle Problem / Traveling Salesman Problem in general grid graph form

I understand that there is a polynomial algorithm to solve TSPs that are in solid grid graph form (grid graphs without holes). I am particularly interested in the non-solid grid graph form of the ...
0
votes
0answers
83 views

Does there exist an algorithm for computing reachability in dynamic directed forests with fast update?

I'm interested in an algorithm which is able to compute reachability between any two nodes in polylog update (add or remove a valid edge) and query. I know that such an algorithm does exist for all ...
0
votes
0answers
379 views

Applications of the property of Kendall-Mann numbers

I am looking for an application of the Kendall-Mann sequence (KM) which uses the property $M(n+1)/M(n) = n - 1/2 + O(1/n)$ ($n \to \infty$) in science ( computer science ( sorting), physics, biology ...