Jakie artykuły każdy powinien przeczytać?

To pytanie jest (zainspirowane) / (wstydliwie skradzione) podobnym pytaniem w MathOverflow , ale spodziewam się, że odpowiedzi tutaj będą zupełnie inne.

Wszyscy mamy ulubione artykuły z naszych własnych obszarów teorii. Od czasu do czasu pojawia się artykuł tak zdumiewający (np. Ważny, przekonujący, zwodniczo prosty itp.), Że chce się nim dzielić ze wszystkimi. Wymień te papiery tutaj! Nie muszą pochodzić z informatyki teoretycznej - wszystko, co Twoim zdaniem może spodobać się społeczności, jest dobrą odpowiedzią.

Możesz udzielić tyle odpowiedzi, ile chcesz; proszę umieścić jeden artykuł na odpowiedź ! Zauważ też, że jest to wiki społeczności, więc głosuj na wszystko, co lubisz!

(Uwaga: poprzednie pytanie dotyczyło artykułów w teorii złożoności rekurencyjnej, ale jest to dość wyspecjalizowane).

„Matematyczna teoria komunikacji” Claude'a Shannona, klasyka teorii informacji. Bardzo czytelny.

( Lustro )

Artykuł z 1936 r., Który prawdopodobnie rozpoczął samą informatykę:

• Alan Turing, „O liczbach obliczalnych z wnioskiem do Entscheidungsproblem”, Proceedings of the London Mathematical Society s2-42, 230–265, 1937. doi: 10.1112 / plms / s2-42.1.230

Na zaledwie 36 stronach Turing formułuje (ale nie wymienia) Maszynę Turinga, przekształca słynne Twierdzenie Pierwszej Niekompletności Gödela pod względem obliczeń, opisuje pojęcie uniwersalności, a w dodatku pokazuje, że obliczalność przez maszyny Turinga jest równoważna obliczalności przez -definiowalne funkcje (badane przez Churcha i Kleene).$\lambda$

„ Refleksje na temat zaufania ” Kena Thompsona . Krótki, słodki i oszałamiający.

Co każdy informatyk powinien wiedzieć o arytmetyki zmiennoprzecinkowej

Ten artykuł wyjaśnia i wzmacnia pogląd, że zmiennoprzecinkowa nie jest magią. Wyjaśnia przepełnienie, niedopełnienie, jakie są liczby zdormalizowane, czym są NaN, czym jest inf i wszystkie rzeczy, które to implikuje. Po przeczytaniu tego artykułu dowiesz się, dlaczego a == a + 1.0 może być prawdziwe, dlaczego a == a może być fałszywe, dlaczego uruchomienie kodu na dwóch różnych maszynach może dać dwie różne odpowiedzi, dlaczego sumowanie liczb w innym Porządek może dać ci różnicę wielkości rzędu i wszystkie zwariowane rzeczy, które zdarzają się w świecie mapowania niezliczonych nieskończonych liczb na zbiór skończony.

Wersja edytowana jest również dostępna w Internecie.

Jak Keshav czytać gazetę . Możesz również pobrać papier tutaj .

Ścieżki, drzewa i kwiaty J. Edmondsa. Ten artykuł na temat klasycznego problemu optymalizacji kombinatorycznej jest nie tylko dobrze napisany, ale także stwierdza, że ​​pojęcie „algorytmów czasu wielomianowego” jest w zasadzie synonimem wydajności.

Redukowalność wśród problemów kombinatorycznych autorstwa Richarda Karpa. Artykuł zawiera coś, co często określa się jako „oryginalne problemy 21 kompletnych NP” Karpa. Pod wieloma względami ten dokument naprawdę zmotywował badanie kompletności NP, pokazując jego zastosowanie do szerszej dziedziny. Bardzo czytelny.

Hartmanis i Stearns, „O złożoności obliczeniowej algorytmów” , Transactions of the American Mathematical Society 117: 285–306 (1965)

Był to pierwszy artykuł, który poważnie podjął się badania złożoności czasu, i z pewnością był głównym impulsem do przyznania wspólnej nagrody Turinga przez Hartmanisa i Stearnsa. Choć ich początkowe definicje nie są dokładnie tym, czego używamy dzisiaj, artykuł pozostaje niezwykle czytelny. Naprawdę masz wrażenie, jak było na starej granicy „Dzikiego Zachodu” lat 60-tych.

Komputery mechaniki kwantowej (PDF) autorstwa Richarda Feynmana.

Wprowadza ideę obliczeń kwantowych, opisuje obwody kwantowe, wyjaśnia, w jaki sposób można symulować obwody klasyczne za pomocą obwodów kwantowych, a także pokazuje, w jaki sposób obwody kwantowe mogą obliczać funkcje bez dużej ilości śmieciowych kubitów (przy użyciu obliczeń nieobliczalnych).

Następnie pokazuje, jak każdy klasyczny obwód można zakodować w niezależnym od czasu hamiltonianie! Jego dowód dotyczy również obwodów kwantowych, dlatego też pokazuje, że ewolucja czasu Hamiltonianów jest trudna w BQP! Jego konstrukcja hamiltonowska jest również używana w dowodzie kwantowej wersji twierdzenia Cooka-Levina, udowodnionego przez Kitaeva, który pokazuje, że k-lokalny hamiltonian jest kompletny QMA.

Wykresy ekspanderów i ich zastosowania, S. Hoory, N. Linial i A. Wigderson to niezwykle ładne badanie dotyczące wykresów ekspanderów. Nic dziwnego, że zdobył nagrodę AMS Conant w 2008 roku.

Chcę przypomnieć, że wykresy ekspanderów są kluczowym składnikiem ostatnich przełomów w TCS, np.

• algorytm przestrzeni logów dla łączności bezkierunkowej (Reingold, STOC, 2005)
• alternatywny dowód twierdzenia PCP (autor: Dinur, ECCC, TR05-046, 2005)

i nie tak niedawno:

• Sieć sortująca AKS, która osiąga głębokość $O(\log n)$ i rozmiar $O(n \log n)$ do sortowania $n$ danych wejściowych (autor: Ajtai, Komlós i Szemerédi, STOC, 1983)
• Kodowane w czasie liniowym i dekodowalne kody korygujące błędy (autor: Spielman, STOC, 1995)

Setki wyników niemożliwości dla rozproszonego przetwarzania danych przez Ficha i Rupperta. Czytelna, obrazowa ankieta, która naprawdę przedstawia setki wyników niemożliwości, w tym podstawowe pytania w tej dziedzinie. Niezwykły kawałek pisania w Expository.

Dziwi mnie, że nikt nie wymyślił „Some Optimal Inapproximability Results” Hastada (JACM 2001; pierwotnie STOC 1997). Ten przełomowy artykuł został napisany tak dobrze, że możesz do niego dojść z niewielką dojrzałością matematyczną i sprawi, że będziesz chciał dobrze nauczyć się kilku rzeczy, takich jak techniki Fouriera, równoległe powtarzanie, gadżety i tak dalej.

$O((log N)^3)$$O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} b\right)^{1\over3} (\log b)^{2\over3}\right)\right)$

Les Valiant's Theory of the Learnable (1984) ustalił program teorii uczenia się na dziesięciolecia i jest to miły i czytelny artykuł!

W artykule znajduje się również dość intuicyjne wyjaśnienie, które sprawia, że ​​jest zabawny i atrakcyjny. Różne części tego artykułu są nadal rutynowo cytowane w rozmowach COLT / ALT.

Być może zbyt podstawowe, ale jestem zszokowany, że nikt nie wspomniał o oryginalnych artykułach Lambdy Steele i Sussman: SCHEME: Interpreter for Extended Lambda Calculus , Lambda: The Ultimate Imperative , Lambda: The Ultimate Declarative .

Rekurencyjne funkcje Johna McCarthy'ego wyrażeń symbolicznych i ich obliczanie przez maszynę, część I.

To podstawowa praca na temat Lisp. Tutaj znajduje się pierwszy ewaluator metakrążenia, mieszczący się na jednej stronie. Jego wpływu nie można przecenić, a mimo to jest niezwykle czytelny.

Złożoność procedur dowodzących twierdzeń Stephena A. Cooka. Artykuł ten dowodzi, że wszystkie języki ustalone przez niedeterministyczne maszyny Turinga z okresu polityczno-politycznego można (Cook-) zredukować do zestawu tautologii zdań.

Znaczenie tego wyniku jest (przynajmniej) dwojakie: po pierwsze pokazuje, że istnieją problemy w NP, które są co najmniej tak trudne jak cała klasa, problemy NP ; ponadto stanowi konkretny przykład takiego problemu, który można następnie sprowadzić do innych w celu udowodnienia, że ​​są kompletne.

Obecnie redukcje Karp są częściej stosowane niż redukcje Cooka, ale główny dowód tego dokumentu można łatwo dostosować, aby wykazać, że SAT jest NP- kompletny w odniesieniu do redukcji Karp.

Call-by-value jest dwojakie niż call-by-name Philipa Wadlera to dobra lektura.

CAR Hoare, Aksjomatyczna podstawa programowania komputerowego .

Z streszczenia: W niniejszym artykule podjęto próbę zbadania logicznych podstaw programowania komputerowego za pomocą technik, które zostały po raz pierwszy zastosowane w badaniach geometrii, a następnie zostały rozszerzone na inne gałęzie matematyki.

Ma sześć stron, które można dość łatwo śledzić.

Alon, Matias i Szegedy, Złożoność przestrzenna aproksymacji momentów częstotliwości , JCSS 58 (1): 137-147, 1999.

Ten dość magiczny papier był pierwszym, który sformalizował algorytmy przesyłania strumieniowego i udowodnił rygorystyczne górne i dolne granice podstawowych zadań w modelu przesyłania strumieniowego. Jego techniki są proste, dowody są piękne, a ich wpływ był ogromny. Praca zdobyła nagrodę Gödela dla Alona, ​​Matiasa i Szegedy w 2005 roku.

Artykuł Immermana dowodzący twierdzenia znanego obecnie jako twierdzenie Immermana – Szelepcsényi jest doskonałym przykładem łatwego do odczytania, mądrego i krótkiego artykułu. Uwielbiam historię opowiedzianą we wstępie.

N. Immerman, Przestrzeń niedeterministyczna jest zamknięta pod uzupełnieniem, SIAM Journal on Computing 17, 1988, ss. 935–938.

$f(n) \ge \log(n)$

$\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right).$

$\text{NPSPACE} = \text{PSPACE}$$\text{P}$$\text{NP}$

Savitch, Walter J. (1970), „Relacje między niedeterministycznymi i deterministycznymi złożonościami taśm”, Journal of Computer and System Sciences 4 (2): 177–192.

Russell Impagliazzo Osobisty pogląd na złożoność średnich przypadków . Jest to świetny artykuł, ponieważ jest sprytnie napisany i podsumowuje stan rzeczy w pięciu „światach”, w których nasze domysły na temat złożoności są rozwiązywane na różne sposoby, dając w każdym przypadku rzeczywiste konsekwencje.

Ulepszone algorytmy aproksymacyjne dla problemów z maksymalnym cięciem i satysfakcją dzięki programowaniu półfinałowemu przez Goemansa i Williamsona.

Świetny przykład wprowadzenia nowej techniki w celu uzyskania wyników, które są znacznie lepsze niż te znane wcześniej.

Ekstraktory i generatory pseudolosowe Luca Trevisan. W tym artykule opracowano dobry ekstraktor losowości za pomocą kodów korygujących błędy i konstrukcji kombinatorycznych. Konstrukcja jest dość łatwa do zrozumienia, ale całkowicie oszałamiająca, ponieważ wcale nie jest oczywiste, jaki jest związek między ekstraktorami, kodami i projektami.

W końcu jest to dobry przykład wyniku w TCS, który wymaga wymyślnej kombinatoryki.

Jak napisać dowód , autorstwa Leslie Lamport.

Wpływ zmiennych na funkcje boolowskie, J. Kahna, G. Kalai i N. Linial

W tym artykule wprowadzono techniki Fouriera dla społeczności TCS i rozwiązano bardzo czysty otwarty problem.

Uważam ten artykuł za bardzo czytelny.

Jeśli mogę zacytować Sarah Palin w tej sprawie: „Wszyscy”.

Mówiąc poważniej, uważam, że większości artykułów nie należy czytać w oryginale. W miarę upływu czasu ludzie wymyślają lepszy sposób zrozumienia i przedstawienia oryginalnego problemu / rozwiązania. Z wyjątkiem oryginalnego papieru Turinga, który ma znaczenie historyczne, nie polecałbym czytania większości oryginalnych artykułów, jeśli zostały oczyszczone kolejne prace. W szczególności wiele rzeczy jest prezentowanych w książkach znacznie lepiej niż w oryginale.

• N. Chomsky. Trzy modele opisu języka. Transakcje IEEE dotyczące teorii informacji 3. 1956. doi: 10.1109 / TIT.1956.1056813

Chomsky analizuje, w jaki sposób można zastosować modele matematyczne do opisu języka naturalnego z językowego punktu widzenia.

Kurt Gödel's O formalnie nierozstrzygalnych propozycjach Principia Mathematica i powiązanych systemach .