Hasil Lipton yang paling berpengaruh

Richard J. Lipton telah terpilih sebagai pemenang Hadiah Knuth 2014 "untuk Pengenalan Gagasan dan Teknik Baru".

Menurut Anda, apa ide dan teknik baru utama yang dikembangkan Lipton?

Catatan. Pertanyaan ini akan menjadi wiki komunitas, harap cantumkan satu ide, teknik, atau hasil per jawaban.

The Planar Separator Teorema menyatakan bahwa dalam planar setiap -vertex graph G terdapat satu set O ( $n$$G$simpul-simpul yang pengangkatannya membuat grafik terputus menjadi setidaknya dua komponen yang kira-kira seimbang. Selain itu, himpunan tersebut dapat ditemukan dalam waktu linier. Hasil (ketat) ini,dibuktikan oleh Lipton dan Tarjan(meningkatkan hasil sebelumnya oleh Ungar) adalah alat yang kuat untuk merancang algoritma pada grafik planar. Ini memberikan banyak algoritma waktu subeksponensial yang tepat untuk masalah NP-hard dan meningkatkan algoritma perkiraan waktu polinomial. Melihathalaman wikipediamemberikan tempat awal yang baik untuk menjelajahi berbagai aplikasi. Sebuahsurvei awaldengan rincian sejumlah aplikasi ditulis oleh Lipton dan Tarjan pada 1980.$O(\sqrt{n})$

Karp-Lipton Teorema menyatakan bahwa tidak dapat memiliki polinomial-ukuran sirkuit boolean kecuali hirarki Polinomial runtuh ke level kedua.$\mathsf{NP}$

Dua implikasi teorema ini untuk teori kompleksitas:

• mungkin tidak memiliki polinomial-ukuran boolean sirkuit; membuktikan batas bawah pada ukuran sirkuit karena itu merupakan pendekatan yang mungkin untuk memisahkan kelas kompleksitas.$\mathsf{NP}$
• Beberapa hasil didasarkan pada teorema ini untuk membuktikan pemisahan kelas kompleksitas (misalnya Teorema Kannan).

Reducibilitas Diri Acak dari Permanen . Lipton menunjukkan bahwa jika ada suatu algoritma yang dengan benar menghitung permanen fraksi dari semua F n × n , di mana F adalah bidang ukuran terbatas setidaknya 3 n , maka algoritma ini dapat digunakan sebagai kotak hitam untuk menghitung permanen dari setiap matriks dengan probabilitas tinggi.$1-1/(3n)$$\mathbb{F}^{n\times n}$$\mathbb{F}$$3n$

Gagasan utamanya adalah bahwa permanen adalah polinomial derajat rendah, sehingga komposisinya dengan fungsi affine univariat adalah polinomial univariat derajat rendah (dalam x ) dan dapat dipelajari secara tepat dari sejumlah kecil nilai melalui interpolasi . Anda dapat memilih B acak sehingga komposisi didistribusikan sebagai permanen dari matriks acak untuk setiap x . Pada x = 0 polinomial univariat hanyalah permanen A . Rinciannya dapat ditemukan di Bab 8 Arora Barak .$A + xB$$x$$B$$x$$x = 0$$A$

Pendekatan aljabar ini sangat berpengaruh dalam teori kompleksitas. Ide-ide Lipton akhirnya mengarah pada bukti teorema IP = PSPACE, bukti teorema PCP, dan hasil pada kode koreksi kesalahan lokal.

Saya tidak 100% yakin apakah penjelasan di bawah ini secara historis akurat. Jika tidak, silakan mengedit atau menghapus.

Pengujian mutasi ditemukan oleh Lipton. Pengujian mutasi dapat dilihat sebagai cara untuk mengukur kualitas atau efektivitas suite uji. Gagasan utamanya adalah menyuntikkan kesalahan ke dalam program yang akan diuji (yaitu untuk memutasi program), lebih disukai jenis kesalahan yang mungkin dilakukan oleh programmer manusia, dan melihat apakah rangkaian uji menemukan kesalahan yang diperkenalkan. Contoh khas dari jenis pengujian mutasi kesalahan akan memperkenalkan bisa mengganti x> 0 dengan x <0, atau mengganti x dengan x + 1 atau x-1. Pecahan kesalahan yang ditangkap oleh test suite adalah "skor kecukupan mutasi" dari test suite. Berbicara dengan sangat longgar, orang dapat menganggap ini sebagai metode Monte-Carlo untuk menghitung skor kecukupan mutasi.

Secara lebih abstrak orang dapat mengatakan bahwa pengujian mutasi membawa ke depan sebuah simetri atau dualitas antara suatu program dan rangkaian pengujiannya: tidak hanya rangkaian uji dapat digunakan untuk menjadi lebih percaya diri tentang kebenaran suatu program, tetapi sebaliknya, suatu program dapat digunakan untuk mendapatkan kepercayaan tentang kualitas test suite.

Dalam terang dualitas ini, pengujian mutasi juga secara konseptual dekat dengan injeksi kesalahan . Keduanya secara teknis serupa tetapi memiliki tujuan yang berbeda. Pengujian mutasi bertujuan untuk mengukur kualitas suite pengujian, sementara injeksi kesalahan berupaya untuk menetapkan kualitas program, biasanya kualitas penanganan kesalahannya.

Baru-baru ini, ide dari pengujian mutasi telah digunakan untuk menguji (formalisasi) teori logis. Mengutip abstrak (4): Ketika mengembangkan formalisasi non-sepele dalam teorema teorema, sejumlah besar waktu dikhususkan untuk "men-debug" spesifikasi dan teorema. Biasanya, spesifikasi atau teorema yang salah ditemukan selama upaya pembuktian yang gagal. Ini adalah bentuk debugging yang mahal. Oleh karena itu sering berguna untuk menguji dugaan sebelum memulai suatu bukti. Cara yang mungkin untuk melakukan ini adalah dengan menetapkan nilai acak ke variabel bebas dari dugaan dan kemudian mengevaluasinya. (4) menggunakan mutasi untuk menguji kualitas generator kasus uji yang digunakan.

Sejarah . Dari (1): Sejarah pengujian mutasi dapat ditelusuri kembali ke tahun 1971 dalam sebuah makalah mahasiswa oleh Richard Lipton [...] Kelahiran bidang ini juga dapat diidentifikasi dalam makalah lain yang diterbitkan pada akhir tahun 1970 oleh Lipton et al. (2) serta Hamlet (3).

1. Gudang Pengujian Mutasi: Teori Pengujian Mutasi .

2. RA DeMillo, RJ Lipton, FG Sayward, Petunjuk Pemilihan Data Uji: Bantuan untuk Programmer yang Berlatih .

3. Ham RG, Program Pengujian dengan Bantuan Kompiler .

4. S. Berghofer, T. Nipkow, Pengujian acak dalam Isabelle / HOL. .

Schwartz - Zippel - DeMillo-Lipton Lemma adalah alat mendasar dalam kompleksitas aritmatika: Pada dasarnya menyatakan bahwa jika Anda ingin tahu apakah rangkaian aritmatika mewakili nol polinomial, yang Anda butuhkan hanyalah mengevaluasi rangkaian pada satu input. Maka Anda akan mendapatkan nilai bukan nol dengan probabilitas baik jika rangkaian tidak mewakili nol polinomial.

Ini adalah lemma yang sangat penting karena tidak ada algoritma deterministik waktu polinomial yang diketahui untuk masalah ini.

Lemma biasanya dikenal sebagai Schwartz-Zippel Lemma . Sejarah lemma ini dapat ditemukan di blog Lipton sendiri .

Cakupan dalam sistem penambahan vektor adalah EXPSPACE-hard : dalam RJ Lipton, Masalah keterjangkauan membutuhkan ruang eksponensial , laporan penelitian 63, Universitas Yale, 1976.

$d$$\langle v_0,A\rangle$$v_0$$\mathbb{N}^d$$A$$\mathbb{Z}^d$$\mathbb{N}^d$$v\to v'$$u$$A$$v'=v+u$$v'$$v$$\mathbb{N}^d$$v_0\to v_1\to\cdots\to v_n$$v_n\geq v$$\mathbb{N}^d$$v_n(i)\geq v(i)$$1\leq i\leq d$. Dikombinasikan dengan batas atas EXPSPACE yang dibuktikan oleh C. Rackoff pada tahun 1978 , hasil Lipton menunjukkan kelengkapan untuk EXPSPACE.

$v_n=v$

Kompleksitas komunikasi multipartai dan model Number-on-Forehead diperkenalkan oleh Ashok K. Chandra , Merrick L. Furst dan Richard J. Lipton dalam Protokol Multi-partai , STOC 1983, doi: 10.1145 / 800061.808737 .

Model multipartai adalah perpanjangan alami dari model kompleksitas komunikasi dua pihak Yao , di mana Alice dan Bob masing-masing memiliki bagian bit input yang tidak tumpang tindih, dan ingin berkomunikasi untuk menghitung fungsi yang telah ditentukan dari seluruh input. Namun, memperluas partisi bit input ke lebih banyak pihak seringkali tidak terlalu menarik (untuk batas bawah, orang biasanya hanya dapat mempertimbangkan dua pihak pertama).

$k$$k$$n$

$n$

$N$$k$$N$$k=3$$N$$O(\sqrt{\log N})$$N \le k(2^n-1)$$O(\sqrt{n})$

$^0$

$N$