Ryan Williams
Reputation
20,223
Next privilege 25,000 Rep.
 Sep 26 comment Matrix vector multiplication algorithm using minimal number of additions It is NP-hard, see cstheory.stackexchange.com/a/32272/225 Sep 16 comment Alternative proofs of Schwartz–Zippel lemma Thanks, looks interesting Sep 1 comment Complexity of k-clique for hypergraphs As far as we know, 3-cycle is harder. The odd case in general takes about O(n^{2.373}) time, the even case takes O(n^2) for fixed length cycles. See for example, Yuster and Zwick, Finding even cycles even faster. Aug 22 comment Bit complexity of modulo operations? Perhaps he would be OK with a preprocessing model: you give me a $b$-bit $B$. I run some algorithm for $poly(B)$ steps, creating some data structure of $O(B)$ size. Finally you give me any $A$ of $O(B)$ bits and I can compute $A ~mod~ B$ in $O(B)$ time, using the data stucture. Aug 17 awarded Yearling Aug 16 reviewed Close “How much diagonal” a matrix is Aug 16 reviewed Close Is there an algorithm to generate proof in Coq? Aug 16 reviewed Close applications of institution-independent model theory Aug 16 reviewed Close Longest path in a DAG that's not too long Aug 16 reviewed Close Computational tractability Aug 15 awarded Enlightened Aug 15 awarded Nice Answer Aug 15 comment To what extent, computational ability for hard tasks helps in solving easy tasks I guess you want to be careful about what $n$ is: in SETH it denotes the number of variables, in the above it seems to denote the input length. If you allow gates that can "compute SAT on $.1n$ variable instances" it is trivial to get a depth-2 $2^{.9n}$ size circuit for $n$ variable SAT: take an OR over all possible assignments to $.9n$ variables, and use your SAT gates to solve SAT on the remaining $.1n$ variables. But this is probably not what you're looking for.... Is it? Aug 14 comment What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$? Exactly... So, lower bounds for the uniformity you mentioned above are already known. Aug 13 answered smallest circuit size using XOR gates Aug 13 comment What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$? @Ricky Demer, that is already known. See for example Chen and Kabanets eccc.hpi-web.de/report/2012/007/download Aug 12 comment To what extent, computational ability for hard tasks helps in solving easy tasks Actually the Strong ETH is not that strong: it just says you can't have a uniform algorithm running in $O(1.9999^n)$ time for SAT with $cn$ clauses, for all $c$. Allowing arbitrary Boolean functions on small sets of variables puts you in nonuniform circuit land. The "nonuniform SETH" is an interesting variant but I don't think it's been studied too closely yet. Aug 12 answered Complexity of k-clique for hypergraphs Aug 12 awarded complexity-classes Aug 11 answered What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?