20
$\begingroup$

Are there any references that provide details about circuit lower bounds for specific hard problems arising in cryptography such as integer factoring, prime/composite discrete logarithm problem and its variant over group of points of elliptic curves (and their higher dimensional abelian varieties) and the general hidden subgroup problem?

Specifically do any of these problems have more than a linear complexity lower bound?

Improve this question
$\endgroup$
9
  • 9
    $\begingroup$ You, of course, know that no lower bound better than 5n for circuit complexity is known, for <i>any</i> explicit function, not just for ones you mentioned. So, you should specify the question. Better bounds are only known for restricted circuits. You could, perhaps, find some partial answers on the home page of <a href="web.science.mq.edu.au/~igor" rel="nofollow"> Igor Sparlinski.</a> $\endgroup$
    – Stasys
    Jul 15, 2011 at 15:58
  • 8
    $\begingroup$ Well, I am not quite sure what do you mean under "this interesting fact". Anyway, the current state of art in circuit complexity is given in my upcoming book thi.informatik.uni-frankfurt.de/~jukna/BFC-book. User: friend Password: catchthecat $\endgroup$
    – Stasys
    Jul 15, 2011 at 17:24
  • 1
    $\begingroup$ @Stasys, I remember a student from Russia talked about their lowerbound of the form 7n+O(1) based on gate elimination in the Prague Fall School two years ago, but I cannot remember any more details. $\endgroup$
    – Kaveh
    Jul 16, 2011 at 22:42
  • 12
    $\begingroup$ Kaveh, this a (7/3)n-c lower bound, not 7n. It was proved by Arist Kojevnikov and Sasha Kulikov from Petersburg. The advantage of their proof is its simplicity, not numerical. Later they gave a simple proof of 3n-o(1) lower bound for general circuits (all fanin-2 gates are allowed). Albeit for very complicated functions - affine dispersers. Papers are online at: logic.pdmi.ras.ru/~kulikov/papers. Actually, tight bound 7n-7 were shown by Redkin (1973) for the parity function, but only if only NOT and AND gates are allowed. If also OR is allowed, then his bound is 4n-4 (also tight!). $\endgroup$
    – Stasys
    Jul 17, 2011 at 15:01
  • 5
    $\begingroup$ @StasysJukna: a combination of your comments is appropriate as an answer. $\endgroup$
    – Suresh Venkat
    Aug 29, 2011 at 6:43

1 Answer 1

Reset to default
27
+50
$\begingroup$

@Suresh: following your advice, here is my "answer". The status of circuit lower bounds is quite depressing. Here are the "current records":

  • $4n-4$ for circuits over $\{\land,\lor,\neg\}$, and $7n-7$ for circuits over $\{\land,\neg\}$ and $\{\lor,\neg\}$ computing $\oplus_n(x)=x_1\oplus x_2\oplus\cdots\oplus x_n$; Redkin (1973). These bounds are tight.
  • $5n-o(n)$ for circuits over the basis with all fanin-2 gates, except the parity and its negation; Iwama and Morizumi (2002).
  • $3n-o(n)$ for general circuits over the basis with all fanin-2 gates; Blum (1984). Arist Kojevnikov and Sasha Kulikov from Petersburg have found a simpler proof of a $(7/3)n-o(1)$ lower bound. The advantage of their proof is its simplicity, not numerical. Later they gave a simple proof of $3n-o(1)$ lower bound for general circuits (all fanin-2 gates are allowed). Albeit for very complicated functions - affine dispersers. Papers are online here.
  • $n^{3-o(1)}$ for formulas over $\{\land,\lor,\neg\}$; Hastad (1998).
  • $\Omega(n^2/\log n)$ for general fanin-$2$ formulas, $\Omega(n^2/\log^2 n)$ for deterministic branching programs, and $\Omega(n^{3/2}/\log n)$ for nondeterministic branching programs; Nechiporuk~(1966).

So, your question "Specifically do any of these problems have more than a linear complexity lower bound?" remains widely open (in the case of circuits). My appeal to all young researchers: go forward, these "barriers" are not unbreakable! But try to think in a "non-natural way", in the sense of Razborov and Rudich.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is this Hastad's 1998 paper? nada.kth.se/~johanh/monotoneconnect.pdf I do not think the bound involves 'not'. Plus the exponent is quadratic. $\endgroup$
    – Turbo
    Jul 2, 2013 at 16:35
  • $\begingroup$ @J.A.: No, this is in another his paper of the same year J. Håstad, The Shrinkage Exponent is 2, SIAM Journal on Computing, 1998, Vol 27, pp 48-64. $\endgroup$
    – Stasys
    May 21, 2014 at 15:27
  • $\begingroup$ It seems noone has updated this answer with the new results, so I'll do it here. The 2015 paper by Magnus Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov "A Better-than-3n Lower Bound for the Circuit Complexity of an Explicit Function." gives a $(3+\Omega(1))n$ lower bound. Maybe this makes things a little less depressing. $\endgroup$
    – Manu
    Nov 8, 2016 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.