# Tagged Questions

92 views

### reference on aperiodicity and cluster [closed]

From this image: I believe there is a message relating those clusters drawn in picture and aperiodic tiling. Does anyone have some reference on this? Thank you :)
49 views

### A possible minimal aperiodic set of corner Wang Tile

From one of my previous question Aperiodic set of corner Wang Tile (although it is put on hold), I realize there is a systematic way to construct aperiodic corner type of Wang tile from edge type ...
101 views

### Aperiodic set of corner Wang Tile [closed]

There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...
41 views

561 views

### Polynomial-time algorithm to compare numbers in Conway chained arrow notation

I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...
1k views

### Non-constructive proofs vs. efficient algorithms

My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity. The wikipedia article on constructive proof begins, "a constructive ...
145 views

### Functions That Can Be Computed Faster Simultaneously Than Expected

The following is an elementary question about circuit complexity. It is different from the kind of thing I have seen discussed, so I would be interested in any work that has been done on this kind of ...
93 views

236 views

### Algorithm for vector space

I have $n$ vectors $e_1 \in (\mathbb Z/2 \mathbb Z)^m,\dots,e_n \in (\mathbb Z/2 \mathbb Z)^m$ and a vector $v \in (\mathbb Z/2 \mathbb Z)^m$ I need to find the better algorithm which answers ...
635 views

### Complexity of convex polytope volume calculation ? (Volume of Voronoi cell) (Error probability)

Assume I have polytope in R^k given by N (k<< N) linear inequalities (A_i x < b_i). I guess complexity of its volume calculate is higher than linear in "N", am I right ? (Is the complexity ...
1k views

### How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}} Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise. Example: Input ...
2k views

### Möbius Randomness of the Rudin-Shapiro Sequence

The Rudin-Shapiro sequence (also known as the Golay-Rudin-Shapiro sequence) is defined as follows. Let $a_n = \sum \epsilon_i\epsilon_{i+1}$ where $\epsilon_1,\epsilon_2,\dots$ are the digits in the ...
486 views

### k-uniform k-partite hypergraph matching in polynomial time

I have what seems like an elementary question, but google didn't throw up any answers for it. I would appreciate any pointers that MO users may provide. It is well known that for $k\geq 3$ finding ...
357 views

### Vertex transitive graphs

Does having vertex transitivity make the problem of calculating independence and chromatic numbers easier?
Let $C$ be size $n \times n^{2}$. Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$. There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$. $B$ is ...