<p>Are there circuits with <span class="math-container">$o(\log^2 n)$</span> many gates and <span class="math-container">$2\log n$</span> designated output gates computing the following:</p>
<p>INPUT: An input <span class="math-container">$x=x_1\dots x_n\in\{0,1\}^n$</span>, where for precisely two indices <span class="math-container">$1\leq i&lt;j\leq n$</span> we have <span class="math-container">$x_i=x_j=1$</span>.</p>
<p>OUTPUT: The binary presentation of <span class="math-container">$i$</span> and <span class="math-container">$j$</span>, respectively.</p>
<p>Remark 1. One may assume that the circuits have unbounded fan-in and input gates appear both positively and negatively.</p>
<p>Remark 2. The circuit need not to test if the input contains precisely two ones, so the problem is formulated as a promise problem. However, this is not a restriction, since for fixed <span class="math-container">$k$</span> the threshold <span class="math-container">$k$</span> function is computable by <span class="math-container">$O(\log n)$</span> sized circuits due to: Friedman, Joel. &quot;Constructing <span class="math-container">$O(n\log n)$</span> Size Monotone Formulae for the k th Threshold Function of n Boolean Variables.&quot; SIAM Journal on Computing 15.3 (1986): 641-654.</p>
<p>A related question is whether there are circuits of size <span class="math-container">$o(\log^2 n)$</span> for the following decision problem.</p>
<p>INPUT: An input <span class="math-container">$x=x_1\dots x_n\in\{0,1\}^n$</span>, where for precisely three indices <span class="math-container">$1\leq i&lt;j&lt;k\leq n$</span> we have <span class="math-container">$x_i=x_j=x_k=1$</span>.</p>
<p>QUESTION: <span class="math-container">$i+j=k$</span>?</p>
<p><strong>Further remarks.</strong></p>
<p>Let us assume for simplicity that <span class="math-container">$n$</span> is a power of <span class="math-container">$2$</span>. When assuming that there is precisely one index <span class="math-container">$$</span> with <span class="math-container">$_=1$</span>, one can use the OR gates <span class="math-container">$_{,0}$</span> and <span class="math-container">$_{,1}$</span>, where <span class="math-container">$$</span> ranges from <span class="math-container">$1$</span> to <span class="math-container">$\log n$</span> to compute the binary presentation of <span class="math-container">$i$</span> as follows: <span class="math-container">$g_{k,}=\bigvee_{∈[1,]:\text{bit}_k(p)=}x_p$</span>. Here, <span class="math-container">$\text{bit}_()$</span> denotes the <span class="math-container">$$</span>th least significant bit of the binary presentation of <span class="math-container">$$</span>.</p>
<p>There is an <span class="math-container">$O(\log^2 n)$</span> upper bound to first question from above by applying a construction of Friedman. He shows that for every fixed <span class="math-container">$$</span> there is an injective function <span class="math-container">$f$</span> from <span class="math-container">$[1,]$</span> to <span class="math-container">$[1,]^\ell$</span> satisfying the following: 1) <span class="math-container">$$</span> only depends on <span class="math-container">$$</span>, (2) <span class="math-container">$\ell=O(\log n)$</span>, and (3) when applying <span class="math-container">$f$</span> to any <span class="math-container">$k$</span> distinct elements <span class="math-container">$i_1,\ldots,i_k$</span> from <span class="math-container">$[1,]$</span> there is a component <span class="math-container">$j\in[1,\ell]$</span> in which <span class="math-container">$f(i_1),\ldots,f(i_k)$</span> pairwise differ. This component <span class="math-container">$j$</span> can then be used as a witness to compute the binary presentation of these <span class="math-container">$$</span> distinct elements. This yields an <span class="math-container">$(\log^2 n)$</span> sized circuit.</p>
<p>There is an <span class="math-container">$\Omega(\log n)$</span> lower bound for deciding whether <span class="math-container">$i+j=k$</span> by using a pigeonhole argument. I am not aware of an <span class="math-container">$\omega(\log n)$</span> lower bound for this question, nor for the first problem I mentioned.</p>

CC BY-SA 4.0
2024-10-03T14:02:36.513Z
What "close" positive results do you know?  E.g. do you know whether there are such circuits of size, say, $O(\log^2 n)$?  Do you know anything about the simpler problem of, given $x$ that has just one index $i$ with $x_i=1$, computing the binary representation of $i$?  Do you know any relevant lower bounds?
Neal Young
CC BY-SA 4.0
2024-10-03T19:20:34.963Z
Yes to all of your questions. Let us assume for simplicity that $n$ is a power of $2$. When assuming that there is precisely one index $i$ with $x_i=1$, one can use the OR gates $g_{k,0}$ and  $g_{k,1}$, where $k$ ranges from $1$ to $\log n$ to compute the binary presentation of $i$: $g_{k,b}=\bigvee_{p\in[1,n]:\text{bit}_k(p)=b} x_p$. Here $\text{bit}_k(p)$ denotes the $k$th least significant bit of the binary presentation of $p$.
Buggo
CC BY-SA 4.0
2024-10-03T19:29:49.387Z
There is an $O(\log^2 n)$ upper bound to my problem by applying a construction of Friedman. He shows that for every fixed $k$ there is an injective function from $[1,n]$ to $[1,b]^\ell$ satisfying the following: 1) $b$ only depends on $k$, (2) $\ell=O(\log n)$, and (3) when applying $f$ to any $k$ distinct elements $i_1,\ldots,i_k$ from $[1,n]$ there is a component $j\in[1,\ell]$ in which $f(i_1),\ldots,f(i_k)$ pairwise differ. This component $j$ can then be used as a witness to compute the binary presentation of these $k$ distinct elements. This yields an $O(\log^2 n)$ sized circuit.
Buggo
CC BY-SA 4.0
2024-10-03T19:37:06.700Z
I am aware of an $\Omega(\log n)$ lower bound for deciding whether $i+j=k$ by using a pigeonhole argument. I am not aware of an $\omega(\log n)$ lower bound for this question, nor for the first problem I mentioned.
Buggo
CC BY-SA 4.0
2024-10-04T14:49:35.570Z
Thanks, that's informative.  Might be worth editing those into the post somehow for background.
Neal Young
CC BY-SA 4.0
2024-11-20T20:30:33.633Z
I expect that the answer is yes even with $O(k \log n)$ gates and $≤k$ non-zero indices.  $O(k \log n)$ random $≈n/k$-fanin OR gates on the input should suffice to distinguish all possibilities, but the difficulty is doing it pseudorandomly such that the results can be processed efficiently.
Dmytro Taranovsky
<cc.complexity-theory><circuit-complexity>
Computing the address of two ones in a binary string with small circuits
Buggo
# Computing the address of two ones in a binary string with small circuits

(Asked by: username_0 on 2024-09-27)

Are there circuits with $o(\log^2 n)$ many gates and $2\log n$ designated output gates computing the following:

INPUT: An input $x=x\_1\dots x\_n\in\{0,1\}^n$, where for precisely two indices $1\leq i we have $x\_i=x\_j=1$.

OUTPUT: The binary presentation of $i$ and $j$, respectively.

Remark 1. One may assume that the circuits have unbounded fan-in and input gates appear both positively and negatively.

Remark 2. The circuit need not to test if the input contains precisely two ones, so the problem is formulated as a promise problem. However, this is not a restriction, since for fixed $k$ the threshold $k$ function is computable by $O(\log n)$ sized circuits due to: Friedman, Joel. "Constructing $O(n\log n)$ Size Monotone Formulae for the k th Threshold Function of n Boolean Variables." SIAM Journal on Computing 15.3 (1986): 641-654.

A related question is whether there are circuits of size $o(\log^2 n)$ for the following decision problem.

INPUT: An input $x=x\_1\dots x\_n\in\{0,1\}^n$, where for precisely three indices $1\leq i we have $x\_i=x\_j=x\_k=1$.

QUESTION: $i+j=k$?

**Further remarks.**

Let us assume for simplicity that $n$ is a power of $2$. When assuming that there is precisely one index $$ with $\_=1$, one can use the OR gates $\_{,0}$ and $\_{,1}$, where $$ ranges from $1$ to $\log n$ to compute the binary presentation of $i$ as follows: $g\_{k,}=\bigvee\_{∈[1,]:\text{bit}\_k(p)=}x\_p$. Here, $\text{bit}\_()$ denotes the $$th least significant bit of the binary presentation of $$.

There is an $O(\log^2 n)$ upper bound to first question from above by applying a construction of Friedman. He shows that for every fixed $$ there is an injective function $f$ from $[1,]$ to $[1,]^\ell$ satisfying the following: 1) $$ only depends on $$, (2) $\ell=O(\log n)$, and (3) when applying $f$ to any $k$ distinct elements $i\_1,\ldots,i\_k$ from $[1,]$ there is a component $j\in[1,\ell]$ in which $f(i\_1),\ldots,f(i\_k)$ pairwise differ. This component $j$ can then be used as a witness to compute the binary presentation of these $$ distinct elements. This yields an $(\log^2 n)$ sized circuit.

There is an $\Omega(\log n)$ lower bound for deciding whether $i+j=k$ by using a pigeonhole argument. I am not aware of an $\omega(\log n)$ lower bound for this question, nor for the first problem I mentioned.

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: What "close" positive results do you know?  E.g. do you know whether there are such circuits of size, say, $O(\log^2 n)$?  Do you know anything about the simpler problem of, given $x$ that has just one index $i$ with $x_i=1$, computing the binary representation of $i$?  Do you know any relevant lower bounds?  
> **username_0**: Yes to all of your questions. Let us assume for simplicity that $n$ is a power of $2$. When assuming that there is precisely one index $i$ with $x_i=1$, one can use the OR gates $g_{k,0}$ and  $g_{k,1}$, where $k$ ranges from $1$ to $\log n$ to compute the binary presentation of $i$: $g_{k,b}=\bigvee_{p\in[1,n]:\text{bit}_k(p)=b} x_p$. Here $\text{bit}_k(p)$ denotes the $k$th least significant bit of the binary presentation of $p$.  
> **username_0**: There is an $O(\log^2 n)$ upper bound to my problem by applying a construction of Friedman. He shows that for every fixed $k$ there is an injective function from $[1,n]$ to $[1,b]^\ell$ satisfying the following: 1) $b$ only depends on $k$, (2) $\ell=O(\log n)$, and (3) when applying $f$ to any $k$ distinct elements $i_1,\ldots,i_k$ from $[1,n]$ there is a component $j\in[1,\ell]$ in which $f(i_1),\ldots,f(i_k)$ pairwise differ. This component $j$ can then be used as a witness to compute the binary presentation of these $k$ distinct elements. This yields an $O(\log^2 n)$ sized circuit.  
> **username_0**: I am aware of an $\Omega(\log n)$ lower bound for deciding whether $i+j=k$ by using a pigeonhole argument. I am not aware of an $\omega(\log n)$ lower bound for this question, nor for the first problem I mentioned.  
> **username_1**: Thanks, that's informative.  Might be worth editing those into the post somehow for background.  
> **username_2**: I expect that the answer is yes even with $O(k \log n)$ gates and $≤k$ non-zero indices.  $O(k \log n)$ random $≈n/k$-fanin OR gates on the input should suffice to distinguish all possibilities, but the difficulty is doing it pseudorandomly such that the results can be processed efficiently.  

---

## 0 answers

