Circuit complexity: Revision history

18 May 2025

• curprev 00:5700:57, 18 May 2025 Cosmia Nebula talk contribs 21,433 bytes +24 →Logspace uniform undo Tag: Visual edit

2 April 2025

• curprev 09:3809:38, 2 April 2025 Maxeto0910 talk contribs 21,409 bytes +1 period after sentence undo Tag: Visual edit

5 February 2025

• curprev 05:5905:59, 5 February 2025 Ringo62 talk contribs m 21,408 bytes +1 →Size and depth undo Tag: Visual edit

9 January 2025

• curprev 09:0609:06, 9 January 2025 Citation bot talk contribs 21,407 bytes +27 Added isbn. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Circuit complexity | #UCB_Category 1/19 undo

29 November 2024

• curprev 15:5515:55, 29 November 2024 Remsense talk contribs m 21,380 bytes −1 Reverted 1 edit by Termeh Tizravesh (talk) to last revision by EvilxFish undo Tags: Twinkle Undo
• curprev 15:5115:51, 29 November 2024 Termeh Tizravesh talk contribs m 21,381 bytes +1 No edit summary undo Tags: Reverted Visual edit

25 October 2024

• curprev 01:5701:57, 25 October 2024 EvilxFish talk contribs m 21,380 bytes +43 →Complexity classes: add unsourced section template undo Tag: Visual edit

27 September 2024

• curprev 15:2515:25, 27 September 2024 Sisima70 talk contribs 21,337 bytes +12 →Size and depth: Made the article easier to skim by bolding the definitions of circuit size and depth. undo
• curprev 15:2315:23, 27 September 2024 Sisima70 talk contribs 21,325 bytes −11 Undid own revision, due to it not being an *useful* clarification (and some might argue not a clarification at all) undo Tag: Undo
• curprev 15:2015:20, 27 September 2024 Sisima70 talk contribs 21,336 bytes +11 replaced "size" in definition of "circuit-size complexity" with "number of gates" since "size" is ambiguous and according to Boolean_circuit the size complexity is the number of gates. undo Tag: Reverted

28 February 2024

• curprev 22:0022:00, 28 February 2024 Hwzh0 talk contribs 21,325 bytes +48 The definition of logspace uniformity is not exactly correct; the definition in both Sipser and Arora & Barak use log-space transducers and not logarithmic space complexity which was implied undo Tag: 2017 wikitext editor

24 February 2024

• curprev 20:2520:25, 24 February 2024 David Eppstein talk contribs 21,277 bytes +189 fix two broken refs undo

13 February 2024

• curprev 17:4417:44, 13 February 2024 A3nm talk contribs m 21,088 bytes 0 use svg undo Tag: 2017 wikitext editor

28 January 2024

• curprev 16:2916:29, 28 January 2024 Horcrux talk contribs m 21,088 bytes +4 →Complexity classes: +wl undo

10 December 2023

• curprev 02:1102:11, 10 December 2023 InternetArchiveBot talk contribs 21,084 bytes +217 Rescuing 1 sources and tagging 1 as dead.) #IABot (v2.0.9.5 undo

7 November 2023

• curprev 05:0205:02, 7 November 2023 RobinK talk contribs m 20,867 bytes −1 No edit summary undo
• curprev 05:0205:02, 7 November 2023 RobinK talk contribs 20,868 bytes +432 Added a section on monotone circuits undo

18 August 2023

• curprev 11:4711:47, 18 August 2023 OAbot talk contribs m 20,436 bytes −4 Open access bot: doi updated in citation with #oabot. undo

13 August 2023

• curprev 13:5313:53, 13 August 2023 OAbot talk contribs m 20,440 bytes +16 Open access bot: doi added to citation with #oabot. undo

24 July 2023

• curprev 08:1608:16, 24 July 2023 Citation bot talk contribs 20,424 bytes +64 Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | #UCB_CommandLine 647/9214 undo

7 July 2023

• curprev 18:4718:47, 7 July 2023 David Eppstein talk contribs 20,360 bytes −55 let's not include Wikidata links in references undo
• curprev 18:4518:45, 7 July 2023 David Eppstein talk contribs 20,415 bytes +4 CS1 undo

29 January 2023

• curprev 17:1717:17, 29 January 2023 OAbot talk contribs m 20,411 bytes +17 Open access bot: doi added to citation with #oabot. undo

8 May 2022

• curprev 17:1017:10, 8 May 2022 Yuval Filmus talk contribs 20,394 bytes −116 →History: Superpolynomial lower bounds for general circuits on *explicit* functions are currently unknown undo

28 February 2022

• curprev 12:4112:41, 28 February 2022 Oliphaunt talk contribs m 20,510 bytes 0 unhyphenate (not used adjectivally) undo

8 February 2022

• curprev 21:1721:17, 8 February 2022 Qwerfjkl (bot) talk contribs m 20,510 bytes 0 Capitalising short description "model of computational complexity" per WP:SDFORMAT (via Bandersnatch) undo

10 December 2021

• curprev 22:0122:01, 10 December 2021 184.64.112.238 talk 20,510 bytes +512 Add stronger Turing machine complexity by Pippenger-Fischer undo Tag: Visual edit: Switched

6 July 2021

• curprev 02:1302:13, 6 July 2021 OAbot talk contribs m 19,998 bytes +17 Open access bot: doi added to citation with #oabot. undo

5 July 2021

• curprev 13:2513:25, 5 July 2021 Cedar101 talk contribs m 19,981 bytes +4 →Circuit lower bounds: fix math italic undo
• curprev 13:2113:21, 5 July 2021 Cedar101 talk contribs m 19,977 bytes +18 →top: \mathsf undo

25 May 2021

• curprev 16:5716:57, 25 May 2021 Citation bot talk contribs 19,959 bytes −59 Removed parameters. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform undo

27 March 2021

• curprev 18:2118:21, 27 March 2021 Matthiaspaul talk contribs 20,018 bytes +10 →References: improved ref undo
• curprev 12:3412:34, 27 March 2021 Matthiaspaul talk contribs 20,008 bytes +15 →References: improved refs undo
• curprev 12:2412:24, 27 March 2021 Matthiaspaul talk contribs 19,993 bytes +20 →References: improved refs undo
• curprev 12:2312:23, 27 March 2021 Matthiaspaul talk contribs 19,973 bytes +63 →Further reading: improved ref undo
• curprev 12:1912:19, 27 March 2021 Matthiaspaul talk contribs 19,910 bytes +249 →References: improved refs undo
• curprev 12:0112:01, 27 March 2021 Matthiaspaul talk contribs 19,661 bytes +463 improved refs undo
• curprev 11:2211:22, 27 March 2021 Matthiaspaul talk contribs 19,198 bytes +265 →References: improved refs undo
• curprev 11:0211:02, 27 March 2021 Matthiaspaul talk contribs 18,933 bytes +75 improved refs undo
• curprev 10:4510:45, 27 March 2021 Matthiaspaul talk contribs 18,858 bytes +1,694 CE, improved refs undo

13 January 2021

• curprev 21:5221:52, 13 January 2021 Monkbot talk contribs m 17,164 bytes +9 Task 18 (cosmetic): eval 19 templates: hyphenate params (9×); undo Tag: AWB

22 June 2020

• curprev 09:3909:39, 22 June 2020 BHGbot talk contribs m 17,155 bytes −16 WP:BHGbot 6 (List 5): eponymous category first, per MOS:CATORDER; WP:GENFIXES undo Tag: AWB

21 June 2020

• curprev 17:4117:41, 21 June 2020 MCT-890220 talk contribs 17,171 bytes −24 →Circuit lower bounds undo
• curprev 17:3817:38, 21 June 2020 MCT-890220 talk contribs 17,195 bytes +1,559 No edit summary undo

7 April 2020

• curprev 22:2322:23, 7 April 2020 Jaydavidmartin talk contribs 15,636 bytes +229 added image undo

4 April 2020

• curprev 09:0409:04, 4 April 2020 Jaydavidmartin talk contribs 15,407 bytes −59 removed unnecessary sentence not in encyclopedic tone undo

2 April 2020

• curprev 11:2311:23, 2 April 2020 Jaydavidmartin talk contribs m 15,466 bytes +4 grammar undo

17 March 2020

• curprev 17:2817:28, 17 March 2020 73.92.106.85 talk 15,462 bytes +45 →History: The statement is inaccurate. See discussion at https://www.reddit.com/r/math/comments/dkka6g/superpolynomial_circuit_lower_bounds/ and survey paper at http://www.cs.columbia.edu/~rocco/Teaching/S17/6998/Boppana-Sipser.pdf . undo

4 October 2019

• curprev 20:0220:02, 4 October 2019 Hatifnatter talk contribs 15,417 bytes +27 →Complexity classes undo

1 August 2019

• curprev 15:0715:07, 1 August 2019 134.59.11.233 talk 15,390 bytes +11 →Circuit lower bounds undo