Circuit complexity: Revision history

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
• curprev 14:5614:56, 1 August 2019‎ 134.59.11.233 talk‎ 15,379 bytes 0‎ →‎History undo

31 May 2019

• curprev 23:4023:40, 31 May 2019‎ Geckop talk contribs‎ m 15,379 bytes 0‎ →‎Relation to time complexity: fix ref location undo

14 May 2019

• curprev 05:5905:59, 14 May 2019‎ Daviddwd talk contribs‎ 15,379 bytes +57‎ short description undo Tag: Visual edit

5 May 2019

• curprev 12:2112:21, 5 May 2019‎ Matthiaspaul talk contribs‎ 15,322 bytes +44‎ refined date undo

17 February 2019

• curprev 16:0816:08, 17 February 2019‎ Citation bot talk contribs‎ m 15,278 bytes +35‎ Alter: journal, isbn, template type. Add: citeseerx. | You can use this bot yourself. Report bugs here. | User-activated. undo

19 October 2018

• curprev 07:2607:26, 19 October 2018‎ Daydreamer302000 talk contribs‎ 15,243 bytes +22‎ Intro was too big and descriptive. Just moving the information around to be more generic and organized. undo

16 May 2018

• curprev 17:4217:42, 16 May 2018‎ Nemo bis talk contribs‎ 15,221 bytes +25‎ Added free to read link in citations with OAbot #oabot undo Tag: OAbot [1.0]

28 March 2018

• curprev 17:0017:00, 28 March 2018‎ 67.198.30.234 talk‎ 15,196 bytes +19‎ Added latex math for some complexity classes. undo Tags: Mobile edit Mobile app edit

12 January 2018

• curprev 22:2422:24, 12 January 2018‎ Chaikens talk contribs‎ m 15,177 bytes +666‎ Incorrect use of "recursive" in the explanation of circuit families was corrected, and the equivalence of decidable by a uniform family to recursive or decidable by Turing machine was added. undo Tag: Visual edit: Switched

22 October 2017

• curprev 07:0307:03, 22 October 2017‎ 121.44.9.193 talk‎ 14,511 bytes +5‎ No edit summary undo