Bons exemplos de como escrever bem no TCS

46

Eu estava editando um manuscrito de estudante. O aluno comentou que seria bom ver exemplos de redação de qualidade em trabalhos publicados, e eu percebi que não conseguia realmente encontrar bons exemplos do alto da minha cabeça

Quais são os melhores exemplos de escrita matemática de qualidade que você já viu?

Regras:

  • Eu preferiria papéis TCS, tanto quanto possível. Nosso estilo é diferente o suficiente dos papéis matemáticos padrão, e acho melhor focar no TCS (também porque estou perguntando aqui e não no MO)
  • ajudaria se você mencionasse exatamente o que achou que o jornal fez bem. Nem toda exposição é boa em tudo - alguns trabalhos têm ótimos esboços de provas, alguns usam a notação com muita eficácia e outros transmitem intuição com maestria.
  • se possível, faça o link para o artigo.

Espero que isso possa se tornar um recurso, como muitas de nossas outras questões amplas. Estou marcando CW por esse motivo.

Suresh Venkat
fonte
2
Uma versão em PDF das notas do curso Knuth, Larrabee e Roberts sobre Escrita Matemática está flutuando na Internet. Por exemplo, aqui: jmlr.csail.mit.edu/reviewing-papers/…
Logan Mayfield
3
Além dos comentários de Kaveh e Logan, Don Knuth fez uma série de palestras em vídeo em Stanford, com base no currículo de "Mathematics Writing". Eu tenho os vídeos, mas não consigo encontrá-los hospedados em qualquer lugar on-line. Eu não me importaria de colocá-los em algum lugar, mas tenho certeza de que haveria algumas falhas de direitos autorais nos quais passar primeiro.
Vincent Russo
9
@VincentRusso eles estão aqui: scpd.stanford.edu/knuth/index.jsp
Suresh Venkat

Respostas:

6

Lembro-me de gostar muito do artigo de Luca, dando uma aproximação espectral a Max Cut: http://arxiv.org/pdf/0806.1978v5.pdf .

Exceto pela clara exposição, ele descreve bem o cenário geral: por que é difícil aproximar o MaxCut do fator 2 do melhor que o fator 2, por que esperar que as técnicas espectrais funcionem, como o algoritmo dele se relaciona com a desigualdade de Cheeger e o SDP de Goemans-Williamson. Além do algoritmo em si ser muito elegante.

Sasho Nikolov
fonte
6

O extrator de Luca Trevisan é lindamente escrito - a idéia, naquela época, era revolucionária, e a exposição da intuição por Luca era ótima.

D. S.
fonte
5
Link para o jornal?
Suresh Venkat
5

Não tenho certeza se ele se qualifica para o TCS, mas o artigo clássico de Kleinberg é um bom exemplo de boa redação. Pelo menos é isso que eu uso como exemplo quando me fazem essa pergunta.

Fontes Autorizadas em um Ambiente Hiperlinkado por Jon M. Kleinberg http://www.cs.cornell.edu/home/kleinber/auth.pdf

Também é bastante interessante contrastar este artigo com o "artigo do Google", publicado na WWW. O artigo de Kleinberg está muito melhor escrito.

Panos Ipeirotis
fonte
4

Oded Goldreich's In a World of P = BPP é um dos melhores artigos escritos que li. Isso se deve principalmente à clareza da exposição, à perspectiva conceitual e à escolha de incluir reflexões sobre o significado dos resultados no artigo.

user887
fonte