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

<ul>
<li>  $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.

<li> $5n-o(n)$ for circuits over the basis with all
  fanin-2 gates, except the parity and its negation; Iwama and
  Morizumi (2002).

<li>  $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 <a href="http://logic.pdmi.ras.ru/~kulikov/papers"> here</a>.

<li> $n^{3-o(1)}$ for formulas over
  $\{\land,\lor,\neg\}$; Hastad (1998).

<li>  $\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).
</ul>

<p>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.  </p>

CC BY-SA 3.0
2013-07-02T16:35:59.487Z
Is this Hastad's 1998 paper? http://www.nada.kth.se/~johanh/monotoneconnect.pdf

I do not think the bound involves 'not'. Plus the exponent is quadratic.
Turbo
CC BY-SA 3.0
2014-05-21T15:27:34.133Z
@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.
Stasys
CC BY-SA 3.0
2016-11-08T15:58:48.213Z
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.
Manu
CC BY-SA 3.0
2011-08-29T18:29:19.167Z
2011-08-29T18:29:19.167Z
Stasys
<p>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?</p>

<p>Specifically do any of these problems have more than a linear complexity lower bound?</p>

CC BY-SA 3.0
2011-07-15T15:58:40.190Z
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="http://web.science.mq.edu.au/~igor/" rel="nofollow"> Igor Sparlinski.</a>
Stasys
CC BY-SA 3.0
2011-07-15T17:05:12.313Z
@Stasys, do you have a reference for this interesting fact?
Simd
CC BY-SA 3.0
2011-07-15T17:24:36.843Z
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 http://www.thi.informatik.uni-frankfurt.de/~jukna/BFC-book/. User: friend Password: catchthecat
Stasys
CC BY-SA 3.0
2011-07-15T20:47:12.710Z
@Stasys Great book. I am going to munch through it.

Also I am new to circuit complexity. So I did not know the $5n$ result. Is there a specific name for it? I am interested in the proof.

Also what kind of results are known for restricted circuits for these problems? Thankyou.
v s
CC BY-SA 3.0
2011-07-16T22:42:53.530Z
@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.
Kaveh
CC BY-SA 3.0
2011-07-17T15:01:50.497Z
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: http://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!).
Stasys
CC BY-SA 3.0
2011-08-29T06:43:33.957Z
@StasysJukna: a combination of your comments is appropriate as an answer.
Suresh Venkat
CC BY-SA 3.0
2011-08-29T07:35:28.613Z
I agree with suresh. But for discrete log anything helpful?
v s
CC BY-SA 3.0
2011-08-29T18:08:22.117Z
@Kaveh, search engines do get comments: https://encrypted.google.com/search?q=%22I+think+results+for+polytime+transfer+upwards+using+padding%2C+don%27t+they%3F%22
didest
<cc.complexity-theory><complexity-classes><cr.crypto-security><circuit-complexity>
Is there a better than linear lower bound for factoring and discrete log?
v s
# Is there a better than linear lower bound for factoring and discrete log?

(Asked by: username_0 on 2011-07-15)

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?

**Tags:** cc.complexity-theory, complexity-classes, cr.crypto-security, circuit-complexity
> **Comments:**
> **username_1**: 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="http://web.science.mq.edu.au/~igor/" rel="nofollow"> Igor Sparlinski.</a>  
> **username_2**: @Stasys, do you have a reference for this interesting fact?  
> **username_1**: 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 http://www.thi.informatik.uni-frankfurt.de/~jukna/BFC-book/. User: friend Password: catchthecat  
> **username_0**: @Stasys Great book. I am going to munch through it.  Also I am new to circuit complexity. So I did not know the $5n$ result. Is there a specific name for it? I am interested in the proof.  Also what kind of results are known for restricted circuits for these problems? Thankyou.  
> **username_3**: @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.  
> **username_1**: 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: http://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!).  
> **username_4**: @StasysJukna: a combination of your comments is appropriate as an answer.  
> **username_0**: I agree with suresh. But for discrete log anything helpful?  
> **username_5**: @Kaveh, search engines do get comments: https://encrypted.google.com/search?q=%22I+think+results+for+polytime+transfer+upwards+using+padding%2C+don%27t+they%3F%22  

---

## 1 answers

### Answer by username_1 on 2011-08-29. Score: 27 | Accepted answer

@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](http://logic.pdmi.ras.ru/~kulikov/papers).* $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.

> **Comments:**
> **username_6**: Is this Hastad's 1998 paper? http://www.nada.kth.se/~johanh/monotoneconnect.pdf  I do not think the bound involves 'not'. Plus the exponent is quadratic.  
> **username_1**: @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.  
> **username_7**: 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.  

---

