Timeline for Boolean formula balancing in $\mathsf{AC^0}$
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 1, 2020 at 16:50 | answer | added | Anupam Das | timeline score: 3 | |
| Jun 17, 2020 at 9:38 | history | edited | CommunityBot |
Commonmark migration
|
|
| Oct 23, 2013 at 20:57 | comment | added | vzn | agreed the defn of "balancing" should be made clear. is this similar to the concept of balancing in binary trees? eg "self balanced trees" | |
| Oct 23, 2013 at 19:47 | answer | added | SamiD | timeline score: 3 | |
| Jan 3, 2013 at 8:09 | comment | added | Kaveh | @Dana, we can use something like $Depth < 10\lg Size + 100 $ (i.e. $Depth = O(\lg Size)$ with specific constants). See also Bonnet and Buss's paper "Size-Depth Tradeoff for Boolean Formulae", 2002. | |
| Dec 31, 2012 at 17:24 | comment | added | Dana Moshkovitz | What definition of "balance" do you use? | |
| Dec 30, 2012 at 7:02 | history | tweeted | twitter.com/#!/StackCSTheory/status/285279757128589312 | ||
| Dec 30, 2012 at 6:24 | history | edited | Kaveh | CC BY-SA 3.0 |
deleted 1 characters in body
|
| Dec 30, 2012 at 5:33 | history | edited | Kaveh | CC BY-SA 3.0 |
deleted 1 characters in body; edited title
|
| Dec 30, 2012 at 3:08 | history | asked | Kaveh | CC BY-SA 3.0 |