Most Popular
1500 questions
24
votes
1 answer
What is known about the complexity of finding minimum circuits for SAT?
What is known about the complexity of finding minimal circuits that compute SAT up to length $n$?
More formally: what is the complexity of a function which, given $1^{n}$ as input outputs a minimal circuit $C$ such that for any formula $\varphi$…
Joshua Grochow
- 37,260
- 4
- 129
- 228
24
votes
2 answers
Balls and Bins analysis in the $m \gg n$ regime: gaps
Suppose we are throwing $m$ balls into $n$ bins, where $m \gg n$. Let $X_i$ be the number of balls ending up in bin $i$, $X_\max$ be the heaviest bin, $X_\min$ be the lightest bin, and $X_{\mathrm{sec-max}}$ be the second heaviest bin. Roughly…
Yuval Filmus
- 14,445
- 1
- 48
- 92
24
votes
5 answers
Approximation algorithms for Maximum Independent Set on special classes of graphs
We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon > 0$ unless P = NP. What are some special classes of graphs for which better approximation algorithms are known?
What are the…
Arindam Pal
- 1,591
- 12
- 23
24
votes
5 answers
What are some career options for someone with a computer scientist master degree?
Other than going fully academic and getting a doctorate/post-doc, or going for a more or less 'standard' job in software development, what are some other career options in the full or semi theoretical C.S field?
ripper234
- 873
- 10
- 15
24
votes
1 answer
Logspace algorithms on graphs with bounded tree width
Tree width measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known approximation algorithm achieves $O(\sqrt{{\log}n})$ factor.
Courcelle's theorem states that any property of graphs definable in monadic…
Shiva Kintali
- 10,578
- 41
- 74
24
votes
1 answer
Space complexity of Coppersmith–Winograd algorithm
Coppersmith–Winograd algorithm is the asymptotically fastest known algorithm for multiplying two $n \times n$ square matrices. The running time of their algorithm is $O(n^{2.376})$ which is the best known so far. What is the space complexity of…
Shiva Kintali
- 10,578
- 41
- 74
24
votes
3 answers
Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
Jason
- 241
- 1
- 3
24
votes
4 answers
Handbook of advanced data structures
I am looking for a book on advanced data structures that goes beyond what is covered in standard textbooks like Cormen, Leiserson, Rivest, and Stein's "Introduction to Algorithms".
A book that can be used for teaching a graduate level course on…
Kaveh
- 21,577
- 8
- 82
- 183
24
votes
2 answers
Implications of proof of abc conjecture for cs theory
What implications would a proof of the abc conjecture have for tcs?
http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/
vtt
- 357
- 1
- 5
24
votes
1 answer
What is UG-hardness, and how is it different from NP-hardness based on the unique games conjecture?
There are many inapproximability results which rely on the unique games conjecture. For example,
Assuming the unique games conjecture, it is NP-hard to approximate the maximum cut problem within a factor R for any constant R > RGW.
(Here RGW =…
Tsuyoshi Ito
- 16,466
- 2
- 55
- 106
24
votes
1 answer
What is the complexity of this covering problem?
Edit: I first misformulated my constraint (2), it is now corrected. I also added more information and examples.
With some colleagues, studying some other algorithmic question, we were able to reduce our problem down to the following interesting…
Florent Foucaud
- 2,153
- 12
- 27
24
votes
6 answers
Introduction to spectral graph theory
What are the basic references? Are there any good, high-level surveys of SGT and its applications to CS in general and machine learning more specifically?
Alexandre Passos
- 1,459
- 12
- 20
24
votes
2 answers
What is the best lower bound for the fault-tolerance threshold in quantum computing?
It is well established that there exists a noise threshold for quantum computation, such that below this threshold, the computation can be encoded in such a way that it yields the correct result with bounded probability (with at most polynomial…
Joe Fitzsimons
- 13,675
- 47
- 91
24
votes
1 answer
complexity of the half language
For any language $L$ over $\Sigma^*$, define
$$L_{1/2} = \{x \in \Sigma^* : xy\in L, y\in\Sigma^{|x|} \}.$$
In words, $L_{1/2}$ consists of all $x$ for which there is a $y$ of equal length such that $xy\in L$.
An exercise in Sipser's book asks to…
Aryeh
- 10,494
- 1
- 27
- 51
23
votes
3 answers
Convex Body with minimum expected l2 norm
Consider a convex body $K$ centered at origin and symmetric (i.e. if $x\in K$ then $-x\in K$). I desire to find a different convex body $L$ such that $K\subseteq L$ and the following measure is minimized:
$f(L)=\mathbb{E}(\sqrt{x^T \cdot x})$, where…
Ashwinkumar B V
- 1,584
- 12
- 20