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

Oct
17
comment Proof that circuit upper bounds for $E$ imply $P \neq NP$
good point, Andras! One of the quantifiers in the $\Sigma_3 E $ part can be seen as solving MCSP.
Oct
16
awarded  Nice Answer
Oct
16
answered Proof that circuit upper bounds for $E$ imply $P \neq NP$
Oct
14
awarded  Nice Answer
Oct
11
awarded  Good Answer
Oct
11
comment Nontrivial problems solvable in constant time?
I think David Eppstein's suggestion points to a more interesting direction: considering randomized O(1)-time algorithms. At least in that case, you can hope that every input bit is accessed in at least one possible run of the algorithm.
Oct
11
comment Nontrivial problems solvable in constant time?
Don't think your example is $O(1)$ time. Your input has length $m=O(\log n)$, in which case the typical word RAM would only allow $O(\log m)$-bit operations in one step. (The alternative is to allow wordsize proportional to the input length, but in that case one can name many "constant-time" algorithms...) You could try to add on a string of length $\geq n$ after those numbers, but then I don't see how checking that format would run in $O(1)$ time: seems you have to check (via binary search, say) that the total string length is indeed $\Omega(\log n)$, which requires $\log n$ time.
Oct
6
reviewed Close Log Rank Conjecture Collaborative Approach
Oct
6
reviewed Close Partitions on Integer Permutations
Oct
1
reviewed Close Is my language Turing-complete?
Sep
26
awarded  Custodian
Sep
26
reviewed Close Practical example: how to formally verify “file name” implementation from a spec?
Sep
26
reviewed Leave Open How Much Computing Power would be Required to Fully Simulate a Cubic Meter?
Sep
26
reviewed Close Complexity of QBF with Restrictions on Models
Sep
26
reviewed Close Computing the DAG of a program given source code or AST
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