All Questions
Tagged with co.combinatorics computational-complexity
216 questions
10
votes
3
answers
649
views
Efficiently getting bits of N! ?
Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?
i.e....
4
votes
0
answers
242
views
Domination in Nice Lattices
Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...
2
votes
0
answers
289
views
Finding globally minimal row subsets of an integer matrix which generate the full row span
Given a $n\times m$ integer matrix $A$, we can consider its row span $span(A)$, that is, the minimal sublattice of $\mathbb{Z}^m$ containing all rows of $A$.
Given a subset of the rows of $A$ it is ...
9
votes
0
answers
2k
views
Weighted Hamming distance
Basically my question is, what kind of geometry do we get if we use a "weighted" Hamming distance. This is combinatorics but similar things come up sometimes in theoretical computer science, ...
3
votes
1
answer
277
views
Theorems about the directed bandwidth of a rooted tree?
Let $T$ be a rooted tree with root $r$. Say an ordering $v_1,\ldots,v_n$ of the vertices of $T$ is a search order if $v_1=r$ and for all $2 \leq i \leq n$, there is $j < i$ such that $v_j$ is the ...
13
votes
0
answers
713
views
Regular languages of matrices and their generating functions
My question is somewhat related to this question.
Let us fix natural numbers $k$ and $C$. Let $A$ be an automaton whose alphabet consists of $k\times k$ matrices with integer coefficients of ...
1
vote
0
answers
576
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$ ...
11
votes
1
answer
860
views
Counting colored rook configurations in the cube - when is it even?
Informal Statement
In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,...
2
votes
2
answers
249
views
Indexing schemes of binary sequences
I am looking for "low-complexity" indexing methods to enumerate binary sequences of a given length and a given weight.
Formally, let $T_k^n = \{x_1^n \in \{0,1\}^n: \sum_{i=1}^n x_i = k\}$. How to ...
7
votes
1
answer
357
views
How long are the certificates produced by the Zeilberger and WZ methods for solving combinatorial sums (A=B)?
In the book "A = B" by Petkovesk, Wilf, and Zeilberger, (downloadable here), the authors provide several algorithmic methods for finding closed forms or recurrences for sums involving e.g. binomial ...
10
votes
1
answer
910
views
Finding Two Rainbow Spanning Trees
Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.
Is the following problem NP-...
2
votes
1
answer
353
views
poly-time algorithm to choose elements of sets
Let $A_1,A_2,\ldots,A_k$ be finite sets. Furthermore, for each $i\in\{1,2,\ldots,k\}$, let $B_i$ be a set whose elements are subsets of $A_i$.
Is there any polynomial-time algorithm that decides ...
7
votes
1
answer
805
views
Counting Eulerian Orientation in a 4-regular undirected graph
We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-...
6
votes
1
answer
1k
views
Finding a cycle of fixed length in a bipartite graph
Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Finding a cycle of ...
-2
votes
1
answer
519
views
cardinal equivalence: for each boolean formula, |quantifications| = |assignments|. [closed]
Cardinal Equivalence Theorem
For each boolean formula, |quantifications| = |assignments|.
The set of valid quantifications has some cardinality, call that |Q(B)...
7
votes
2
answers
1k
views
How unhelpful is graph minors theorem?
A very interesting Robertson-Seymour (graphs minors) theorem says:
Any infinite collection of graphs $C$ with the property that if $G\in C $ then its minors also are has the form $\{$graphs $G$ ...