Reputation
20,223
Next privilege 25,000 Rep.
Access to site analytics
Badges
5 80 144
Newest
 Good Answer
Impact
~259k people reached

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$?