1
vote
0answers
32 views
Drawing a combinatorial 3-configuration of points and lines with pseudolines
This question is related to the question of drawing a combinatorial 3-configuration of points and lines with straight lines. We only relax the condition and admit drawings with pse …
3
votes
1answer
75 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 …
7
votes
2answers
149 views
Drawing 3-configurations of points and lines with straight lines
It is well-known that the black-and-white coloring of the Heawood graph on 14 vertices determines a combinatorial 3-configuration with 7 "points" and 7 "lines", known as Fano plane …
5
votes
4answers
245 views
Does there exist a general theory of “arithmetic complexity”/“arithmetic height”?
This question is hopelessly vague, but here goes:
Say I'm given some finite precision complex number, which I'm told is algebraic over $\mathbb{Q}$. Is there some well defined not …
7
votes
1answer
201 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 ro …
6
votes
1answer
111 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 Fi …
1
vote
0answers
60 views
Are weakly symmetric boolean functions evasive?
I was always fascinated by this nice and easy to state question. I wonder if any progress has been made on it (except for proving it for six). Do you know any related results?
For …
6
votes
4answers
246 views
Complexity of testing integer square-freeness
How fast can an algorithm tell if an integer is square-free?
I am interested in both deterministic and randomized algorithms. I also care about both unconditional results and one …
4
votes
1answer
131 views
Space Bounded Communication Complexity of Identity
$\bf Definition.$ We define the space bounded communication in the following way. A and B are
supernatural beings capable of computing anything but
they only have a limited amount …
12
votes
2answers
242 views
Simulating Turing machines with {O,P}DEs.
Qiaochu Yuan in his answer to this question recalls a blog post (specifically, comment 16 therein) by Terry Tao:
For instance, one cannot hope to find an algorithm to determine …
10
votes
1answer
325 views
Counting subgraphs of bipartite graphs
I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed!
Given a bipartite graph $G$ of $n$ vertices, how many …
11
votes
3answers
449 views
Is the theory of categories decidable?
There are a lot of theorems in basic homological algebra, such as the five lemma or the snake lemma, that seem like they'd be more easily proven by computer than by hand. This led …
5
votes
4answers
427 views
Solving NP problems in (usually) Polynomial time?
Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinari …
6
votes
2answers
379 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 fo …
0
votes
1answer
189 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)|.
The set of sa …
