Reputation
19,958
Next privilege 20,000 Rep.
Access 'trusted user' tools
Badges
5 79 143
Newest
 Enlightened
Impact
~253k people reached

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$?
Jun
8
awarded  Nice Answer
May
30
comment Undecidable Single Programs
For any finite collection of halting instances, there is a machine that can decide that collection in linear time, since that collection can be seen as a regular language. Any yes instance of the halting problem has a finite proof that it indeed halts, namely its computation history.
May
27
answered Counting the number of K4
May
23
comment Additive combinatorics applications in algorithm design
I don't think we could use this to solve $3SAT$ faster than known algorithms -- $3SAT$ can already be solved in $1.308^n$ time.
May
12
awarded  Nice Answer