Most Popular
1500 questions
19
votes
1 answer
Can we count in depth $\frac{\lg n}{\lg \lg n}$?
Can we compute an $n$-bit threshold gate by polynomial size (unbounded fan-in) circuits of depth $\frac{\lg n}{\lg \lg n}$? Alternatively, can we count the number of 1s in the input bits using these circuits?
Is $\mathsf{TC^0} \subseteq…
Kaveh
- 21,577
- 8
- 82
- 183
19
votes
2 answers
Are all the functions whose fourier weight is concentrated on the small sized sets computed by AC0 circuits?
Are all the functions whose fourier weight is concentrated on the small sized sets(or terms with low degree) computed by $\mathsf{AC}^0$ circuits ?
Stattrav
- 523
- 2
- 8
19
votes
2 answers
A mathematical (categorical) description of type classes
A functional language can be viewed as a category where its objects are types and morphisms functions between them.
How do type classes fit in this model?
I assume we should only consider those implementations that satisfy the constraint that most…
Petr
- 2,601
- 15
- 28
19
votes
1 answer
Visualizing Unique Games
How would you design a picture to illustrate the unique games conjecture?
This is for a "Current Events" presentation on unique games at the next AMS Joint Meeting and for the booklet that will be produced.
Example of the kind of illustrations…
Luca Trevisan
- 4,912
- 28
- 34
19
votes
2 answers
Linearly independent Fourier coefficients
A basic property of vector spaces is that a vector space $V \subseteq \mathbb{F}_2^n$ of dimension $n-d$ can be characterized by $d$ linearly independent linear constraints - that is, there exist $d$ linearly independent vectors $w_1, \ldots, w_d…
Or Meir
- 5,380
- 22
- 33
19
votes
2 answers
What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?
I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ripe for such problems"). It has been proven that a class of "Collatz-like"…
vzn
- 11,014
- 2
- 31
- 64
19
votes
2 answers
How hard is Mafia?
Mafia is a popular role-playing game at parties, a detailed description is available at wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29.
Basically, it works as follows:
At the beginning, each of the $N$ players is secretly assigned a role,…
Syzygy
- 291
- 1
- 5
19
votes
1 answer
Looking for a nice problem inside SC but not in the first two levels
The complexity zoo doesn't have much about the $\mathsf{SC}$. I am looking for a nice$^\dagger$ problem that is in higher levels of the hierarchy, i.e. a problem in $\mathsf{DTimeSpace}(n^{O(1)},\lg^{O(1)} n)$ but not known to be in…
Kaveh
- 21,577
- 8
- 82
- 183
19
votes
3 answers
Complexity of deciding whether a matrix is totally regular
A matrix is called totally regular if all its square submatrices have full rank. Such matrices were used to construct superconcentrators. What is the complexity of deciding whether a given matrix is totally regular over the rationals? Over finite…
Markus Bläser
- 2,938
- 18
- 19
19
votes
3 answers
graphs where vertex coloring is in P but independent set is NP complete
Is there an example of a class of graphs for which the vertex coloring problem is in P but the independent set is problem is NP complete?
Ankur
- 779
- 4
- 14
19
votes
1 answer
What is the counting complexity of random 2-SAT?
Has any work been done on how the complexity of random instances of #2-SAT varies with the clause density? That is: how does the difficulty of counting satisfying solutions to a randomly generated instance of 2-SAT vary, as the clause density…
Niel de Beaudrap
- 8,821
- 31
- 70
19
votes
3 answers
Running a BPP algorithm with a half-random, half-adversarial string
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…
Scott Aaronson
- 13,733
- 2
- 62
- 68
19
votes
3 answers
Determinant modulo m
What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but composite (so computations are performed in ring, not…
Valeriy Sokolov
- 353
- 1
- 8
19
votes
1 answer
Finding good induced subgraph
You are given a graph $G = (V,E)$ with $n$ vertices. It might be bipartite if you want. There are $m$ sets of edges $E_1,\ldots, E_m \subseteq E$ (say disjoint). I am interested in the problem of finding a subset $S \subseteq V$, as small as…
Sariel Har-Peled
- 9,626
- 31
- 53
19
votes
3 answers
Is the concept of the Turing Machine derived from automata?
I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"?
I didn't know the answer of course, but I'm curious to find out. The Turing Machine is…
Emmanuel M. Smith
- 293
- 1
- 6