PCP theorem: Revision history

20 June 2024

• curprev 06:1806:18, 20 June 2024 Cedar101 talk contribs 15,710 bytes +21 →Quantum analog: replace {{nowrap}} with {{math}} undo
• curprev 06:1406:14, 20 June 2024 Cedar101 talk contribs m 15,689 bytes +33 →Quantum analog: {{sup|∗}} undo
• curprev 06:1206:12, 20 June 2024 Cedar101 talk contribs 15,656 bytes +24 →Proof: fix math italic undo

19 May 2024

• curprev 10:5910:59, 19 May 2024 AukusRuckus talk contribs 15,632 bytes +25 Disambiguated Query complexity → Computational complexity undo

21 March 2024

• curprev 05:5905:59, 21 March 2024 David Eppstein talk contribs 15,607 bytes −32 →First theorem [in 1990]: the citations are fine for text that basically says "other people published extensions of this work" undo

26 December 2023

• curprev 08:5308:53, 26 December 2023 Ctjk talk contribs 15,639 bytes +75 No edit summary undo Tag: Visual edit

23 December 2023

• curprev 14:4314:43, 23 December 2023 Ctjk talk contribs 15,564 bytes +8 No edit summary undo Tag: Visual edit
• curprev 14:4214:42, 23 December 2023 Ctjk talk contribs 15,556 bytes +460 Adding NLTS conjecture proof in 2022 undo Tag: Visual edit

13 December 2023

• curprev 19:1719:17, 13 December 2023 David Eppstein talk contribs 15,096 bytes −20 Undid revision 1189689537 by Onel5969 (talk) Bad dab. Decision trees are not a part of the query model here. Just queries. No tree. undo Tags: Undo Disambiguation links added
• curprev 10:5710:57, 13 December 2023 Onel5969 talk contribs m 15,116 bytes +20 Disambiguating links to Query complexity (link changed to Decision tree model) using DisamAssist. undo Tag: Reverted

10 October 2023

• curprev 15:4715:47, 10 October 2023 Tc14Hd talk contribs 15,096 bytes +65 No edit summary undo Tags: Mobile edit Mobile app edit Android app edit

14 August 2023

• curprev 20:5020:50, 14 August 2023 OAbot talk contribs m 15,031 bytes +16 Open access bot: doi updated in citation with #oabot. undo

22 July 2023

• curprev 04:4304:43, 22 July 2023 Citation bot talk contribs 15,015 bytes −1 Alter: title, template type. Add: chapter. Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine undo

9 April 2023

• curprev 16:2416:24, 9 April 2023 Aquohn talk contribs 15,016 bytes +286 →PCP and hardness of approximation: Further elaboration on connection to NP hardness undo
• curprev 16:1816:18, 9 April 2023 Aquohn talk contribs 14,730 bytes +1,148 →PCP and hardness of approximation: Explain connection between PCP class and CSP formulation undo
• curprev 15:4215:42, 9 April 2023 Aquohn talk contribs 13,582 bytes +287 →Formal statement: Clarify that verification is non-adaptive, and provide definition of ''n'' undo
• curprev 14:5914:59, 9 April 2023 Aquohn talk contribs m 13,295 bytes +32 →Formal statement: Tweak phrasing undo
• curprev 14:4514:45, 9 April 2023 Aquohn talk contribs 13,263 bytes +361 →Formal statement: Briefly elaborate on the formal definition undo

8 April 2023

• curprev 19:5019:50, 8 April 2023 Shreevatsa talk contribs m 12,902 bytes −27 →Quantum analog: remove wikilink that leads right back here undo

28 March 2023

• curprev 06:4506:45, 28 March 2023 David Eppstein talk contribs 12,929 bytes +209 conference version, not preprint undo

18 February 2023

• curprev 01:3401:34, 18 February 2023 Mikhail Ryazanov talk contribs m 12,720 bytes 0 →Quantum analog: MOS:LQ, MOS:CAPS, fmt. undo

10 February 2023

• curprev 19:4119:41, 10 February 2023 Henry Glunz talk contribs m 12,720 bytes +2 →Proof: Edited the statement so that they fit the result referenced undo Tag: 2017 wikitext editor

20 January 2023

• curprev 00:5900:59, 20 January 2023 Fragrant Peony talk contribs 12,718 bytes −121 Reverting edit(s) by 130.44.137.5 (talk) to rev. 1116511291 by Fixmaster: non-constructive (RW 16.1) undo Tags: RW Undo
• curprev 00:5800:58, 20 January 2023 130.44.137.5 talk 12,839 bytes +121 →Quantum analog undo Tag: Reverted

16 October 2022

• curprev 23:3723:37, 16 October 2022 Fixmaster talk contribs 12,718 bytes +27 →Quantum analog undo Tags: Mobile edit Mobile web edit Advanced mobile edit

8 August 2022

• curprev 12:1112:11, 8 August 2022 The void century talk contribs 12,691 bytes +316 →Quantum analog: un-orphan orphan article undo Tag: Visual edit
• curprev 06:0406:04, 8 August 2022 David Eppstein talk contribs 12,375 bytes −22 Intended undo undo Tag: Manual revert
• curprev 06:0406:04, 8 August 2022 David Eppstein talk contribs 12,397 bytes +2 Undid revision 1103026618 by The void century (talk) still breaks up the WP:COMMONNAME in the lead, for no good reason as the same phrase "probabilistically checkable proof" is right there later in the same paragraph undo Tags: Undo Reverted
• curprev 02:1102:11, 8 August 2022 The void century talk contribs m 12,395 bytes −2 fix grammar undo Tags: Reverted Visual edit
• curprev 02:1102:11, 8 August 2022 The void century talk contribs m 12,397 bytes +22 See MOS:ACROTITLE and NASA undo Tags: Reverted Visual edit

7 August 2022

• curprev 21:1921:19, 7 August 2022 David Eppstein talk contribs 12,375 bytes −37 Undid revision 1102976363 by The void century (talk) you added your IN THE MIDDLE OF SOMETHING ELSE explanation, breaking the boldfaced copy of the main article's PUT IT SOMEWHERE ELSE, PLEASE title undo Tag: Undo
• curprev 21:1121:11, 7 August 2022 The void century talk contribs m 12,412 bytes +37 fixing acronym without explanation undo Tags: Reverted Visual edit

27 July 2022

• curprev 00:4100:41, 27 July 2022 Citation bot talk contribs 12,375 bytes +63 Add: s2cid, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Smasongarrison | Linked from User:Smasongarrison/sandbox | #UCB_webform_linked 1989/3850 undo

13 April 2022

• curprev 21:1721:17, 13 April 2022 ReyHahn talk contribs m 12,312 bytes 0 →History: wrong P undo
• curprev 21:1621:16, 13 April 2022 ReyHahn talk contribs 12,312 bytes −49 →History: the whole article is about the PCP no need to repeat it, also etymology is for words not abbreviations undo
• curprev 21:1521:15, 13 April 2022 ReyHahn talk contribs m 12,361 bytes 0 →History: wikistyle undo

31 January 2022

• curprev 14:5414:54, 31 January 2022 Shfkk talk contribs 12,361 bytes +16 No edit summary undo

6 May 2021

• curprev 14:3914:39, 6 May 2021 OAbot talk contribs m 12,345 bytes +18 Open access bot: doi added to citation with #oabot. undo

8 January 2021

• curprev 00:1600:16, 8 January 2021 WikiCleanerBot talk contribs m 12,327 bytes −16 v2.04b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation - Link equal to linktext) undo Tag: WPCleaner

28 February 2020

• curprev 16:1516:15, 28 February 2020 Citation bot talk contribs m 12,343 bytes +37 Alter: pages, journal. Add: isbn, bibcode, year, class, eprint. Removed URL that duplicated unique identifier. Removed parameters. Formatted dashes. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Activated by User:AManWithNoPlan | via #UCB_toolbar undo

20 December 2019

• curprev 16:1616:16, 20 December 2019 Michael Hardy talk contribs 12,306 bytes 0 →Quantum analog of the PCP Theorem undo
• curprev 16:1616:16, 20 December 2019 Michael Hardy talk contribs 12,306 bytes +26 →Quantum analog of the PCP Theorem undo

15 November 2019

• curprev 20:2120:21, 15 November 2019 Inavda talk contribs m 12,280 bytes +1 →Proof undo

1 October 2019

• curprev 12:5612:56, 1 October 2019 Shuiberts talk contribs 12,279 bytes +206 2019 Godel prize as citation for significance of Dinur's result. undo

27 September 2019

• curprev 07:5107:51, 27 September 2019 Monkbot talk contribs m 12,073 bytes +8 →Quantum analog of the PCP Theorem: Task 16: replaced (2×) / removed (0×) deprecated |dead-url= and |deadurl= with |url-status=; undo Tag: AWB

20 September 2019

• curprev 15:2715:27, 20 September 2019 Cephian talk contribs 12,065 bytes 0 →Proof: Fixed right parens which should have been right bracket undo Tags: Mobile edit Mobile web edit

27 July 2019

• curprev 07:0607:06, 27 July 2019 OAbot talk contribs m 12,065 bytes +17 Open access bot: add arxiv identifier to citation with #oabot. undo

10 July 2019

• curprev 06:4106:41, 10 July 2019 GreenC bot talk contribs 12,048 bytes +221 Rescued 2 archive links. Wayback Medic 2.5 undo

7 July 2019

• curprev 20:2020:20, 7 July 2019 Fschwarzentruber talk contribs 11,827 bytes +382 →History undo Tag: Visual edit

18 March 2019

• curprev 14:0514:05, 18 March 2019 Imbrifer talk contribs m 11,445 bytes −23 →PCP and hardness of approximation: link to Promise problem page undo