Timeline for Can addition be carried out in less than depth 5?
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 21, 2013 at 16:30 | vote | accept | Anonymous | ||
| Oct 21, 2013 at 1:16 | answer | added | SamiD | timeline score: 13 | |
| Mar 16, 2013 at 21:22 | vote | accept | Anonymous | ||
| Mar 16, 2013 at 21:23 | |||||
| S Aug 17, 2012 at 21:12 | history | bounty ended | Robin Kothari | ||
| S Aug 17, 2012 at 21:12 | history | notice removed | Robin Kothari | ||
| Aug 14, 2012 at 6:47 | answer | added | Noam | timeline score: 9 | |
| S Aug 12, 2012 at 1:57 | history | bounty started | Robin Kothari | ||
| S Aug 12, 2012 at 1:57 | history | notice added | Robin Kothari | Authoritative reference needed | |
| Aug 6, 2012 at 11:07 | comment | added | Emil Jeřábek | @mjqxxxx: Every Boolean function is computable by depth $2$ circuits. Now, suppose you find for your fixed $m$ a circuit of size $s$. How do you judge whether there are size $cn$ circuits for every $n$, where $c=s/m$, or whether there are only circuits of size $2^{\epsilon n}$, where $\epsilon=(\log s)/m$? There is simply no way to infer asymptotic information from a finite example. | |
| Aug 6, 2012 at 5:58 | comment | added | mjqxxxx | @RobinKothari: If there's no depth-$4$ circuit for a particular $m$, then there's no depth-$4$ circuit family for the general problem, polynomial-size or not. (The brute force approach can only prove the negative result here.) | |
| Aug 5, 2012 at 4:12 | comment | added | Robin Kothari | @mjqxxxx: How do you enforce the polynomial-size constraint on AC0 circuits when brute-forcing for a fixed m? @ OP: Is the current best circuit depth 4 or depth 5? | |
| S Aug 4, 2012 at 21:15 | history | suggested | CommunityBot | CC BY-SA 3.0 |
improving the question
|
| Aug 4, 2012 at 21:14 | review | Suggested edits | |||
| S Aug 4, 2012 at 21:15 | |||||
| Aug 2, 2012 at 19:09 | comment | added | mjqxxxx | This could be brute-forced by verifying that no depth-$4$ AC$^{0}$ circuit can compute the $(m+1)$-bit sum of two $m$-bit inputs for some fixed $m$; there are only finitely-many boolean functions of the input bits that can appear at each depth. | |
| Jul 31, 2012 at 6:42 | comment | added | Kaveh | @Geekster, generally people are not required to create an account or use their real names (however it is encouraged to do so for various reasons). If you have a general concern about something please use Theoretical Computer Science Meta to raise it. | |
| Jul 31, 2012 at 4:40 | history | tweeted | twitter.com/#!/StackCSTheory/status/230160963037458432 | ||
| Jul 30, 2012 at 22:08 | comment | added | Tayfun Pay | Can you tell us your name? Who you are? For the past month or so people are making a new username on here, asking a question and then deleting that user name! | |
| Jul 30, 2012 at 19:44 | history | edited | Robin Kothari |
edited tags
|
|
| Jul 30, 2012 at 17:27 | history | asked | Anonymous | CC BY-SA 3.0 |