Rekor baru pengemasan bola lama muncul dari sumber yang tak terduga

• Boaz Klartag memperkenalkan alat dari geometri konveks ke masalah pengemasan bola berdimensi sangat tinggi, berbeda dari pendekatan yang ada
• Metode acak baru Klartag menghasilkan elipsoid dengan volume lebih besar, sehingga secara signifikan memperbarui rekor sebelumnya
• Pendekatan ini memungkinkan pengemasan jauh lebih banyak bola dalam ruang berdimensi tinggi
• Hasil ini menghidupkan kembali perdebatan tentang pentingnya keteraturan dan simetri dalam pengemasan
• Penelitian ini mendapat perhatian karena potensi penerapannya di berbagai bidang seperti kriptografi dan komunikasi

---

Riset pengemasan bola sebelumnya dan keterbatasannya

• Di masa lalu, keunggulan metode Rogers adalah bahwa kisi awal tidak harus efisien; cukup memilih elipsoid yang sesuai
• Namun, karena sumbu elipsoid dapat berubah dalam banyak cara di dimensi tinggi, pilihan bentuk yang akan diperbesar menjadi terlalu banyak
• Setelah itu para matematikawan kembali ke pendekatan Minkowski dan berfokus pada kisi itu sendiri, terspesialisasi dalam teori kisi, serta menjauh dari pendekatan Rogers yang berpusat pada geometri
• Strategi ini menunjukkan perbaikan bertahap dalam pengemasan bola berdimensi tinggi, tetapi hanya memberikan peningkatan efisiensi yang tipis dibanding metode Rogers
• Selama beberapa dekade tidak ada lompatan besar, dan stagnasi terus berlanjut

Inovasi yang bermula dari sudut pandang luar

• Boaz Klartag dari Weizmann Institute of Science pada dasarnya adalah spesialis geometri konveks, bukan teori kisi
• Ia sudah lama tertarik pada masalah pengemasan bola, tetapi belum mendapat kesempatan untuk menelitinya
• Pada 2023, ketika memiliki lebih banyak waktu, ia mengadakan seminar bersama Barak Weiss dari Tel Aviv University dan mendalami literatur klasik (Minkowski, Rogers)
• Klartag menilai bahwa metode elipsoid Rogers tidak efisien karena kurangnya keahlian dalam memanipulasi bangun konveks
• Ia pun yakin bahwa jika bisa membuat elipsoid yang lebih efisien, ia dapat menulis ulang rekor pengemasan bola

Penerapan algoritme pertumbuhan acak

• Klartag menerapkan metodenya sendiri yang memperluas/menyusutkan batas elipsoid secara acak untuk setiap arah sumbu
• Saat batas menyentuh titik kisi, pertumbuhan pada arah tersebut dihentikan, sementara arah lain terus berkembang
• Dalam proses ini, elipsoid menjelajahi ruang dengan bentuk yang tidak beraturan sambil terus membesar
• Karena sifat acaknya membuat volume elipsoid yang dihasilkan berbeda-beda, ia mengulangi percobaan berkali-kali untuk menilai kemungkinan menemukan elipsoid dengan volume lebih besar
• Dalam beberapa minggu, ia membuktikan bahwa elipsoid yang lebih besar daripada milik Rogers dapat dihasilkan

Pemecahan rekor dan dampaknya

• Metode elipsoid baru ini mencapai peningkatan efisiensi pengemasan bola terbesar sejak Rogers (1947)
• Saat dimensinya adalah d, metode ini memungkinkan pengemasan d kali lebih banyak bola dibanding pendekatan sebelumnya
  • 100 dimensi → sekitar 100 kali lipat, 1.000.000 dimensi → sekitar 1 juta kali lipat pengemasan bola
• Dengan wawasan dari geometri konveks, Klartag menembus beberapa masalah inti lama tentang kisi dan pengemasan bola hanya dalam hitungan bulan
• Pencapaiannya kembali menonjolkan pandangan bahwa pengemasan berbasis keteraturan dan simetri dapat menghasilkan pengemasan paling rapat
• Di sisi lain, belakangan ini juga ada riset yang bersaing dan berpendapat bahwa ketakteraturan tanpa kisi teratur perlu dimanfaatkan

Penilaian dan prospek ke depan

• Saat ini masih ada perdebatan di kalangan akademik tentang apakah metode pengemasan Klartag benar-benar mendekati optimum, atau masih ada ruang untuk perbaikan lebih lanjut
• Jawaban atas masalah ini sangat penting juga untuk penerapan nyata seperti kriptografi dan teknik komunikasi
• Walau belum masuk tahap penerapan praktis, temuan ini sudah menarik perhatian sebagai teknologi baru di kalangan rekayasa dan bidang lain
• Klartag berharap momentum ini akan memperkuat keterkaitan antara geometri konveks dan teori kisi
• Ia berharap keterputusan antara dua bidang itu bisa diatasi dan perpaduannya dapat meluas ke pemecahan masalah kisi selain pengemasan

[GN⁺]

Komentar Hacker News

• Pengakuan bahwa selalu sulit menjelaskan kepada orang tua bahwa pekerjaan saya benar-benar ada, dan membayangkan situasi yang jadi makin canggung ketika harus berkata, “Saya meneliti bentuk, tetapi hanya bentuk yang tidak punya bagian cekung ke dalam”
  • Dari pengalaman saya, kesimpulannya adalah paling baik menjelaskan pekerjaan dengan istilah teknis yang sulit; pilihannya menyempit jadi tiga: kalau memberi penjelasan yang relatif mudah dipahami orang tua, pekerjaan itu terlihat terlalu gampang sehingga reaksinya jadi, “Masa ini bisa menghasilkan uang?”; kalau menjelaskan dengan benar kenapa itu penting, penjelasannya jadi terlalu panjang sampai orang tua bosan dan menyesal sudah bertanya; atau kalau diceritakan singkat dengan jargon rumit, mereka memang tidak paham, tetapi entah kenapa terdengar hebat; itu pilihan terbaik
  • Saya menjalankan micro-business yang membuat komponen untuk peralatan fisika energi tinggi, dan saat menjelaskan pekerjaan saya kepada orang lain, topiknya begitu asing, sangat niche, nyaris tak pernah ditemui publik, dan beberapa tingkat terlepas dari kehidupan sehari-hari, sehingga sampai sekarang saya masih belum menemukan cara menjelaskannya agar dipahami
  • Saya biasanya cuma bilang, “Saya kerja dengan komputer,” lalu responsnya, “Oh, ya, bagus juga pekerjaannya,” dan percakapan pun selesai dengan praktis
  • Bagi saya, yang lebih sulit daripada pertanyaan “kerja apa?” justru pertanyaan lanjutan seperti “itu gunanya apa/ dipakai di mana?”; saya selalu kesulitan menjelaskan secara singkat dan efektif rantai panjang yang menghubungkan riset fundamental dengan penerapan nyata
  • Setidaknya sphere packing berkaitan erat dengan masalah inti dalam teori informasi, dan dari sana ada konteks sejarah serta makna penting yang terhubung dengan meningkatnya keandalan Bell Telephone System (untuk bangun cembung saya kurang tahu)
• Pengalaman memikirkan algoritme kompresi data vektor dengan menggunakan sphere packing; pendekatan teoretisnya hanya efektif ketika data sangat seragam dan sulit diterapkan pada data dunia nyata
  • Untuk mengubah data tak beraturan (tidak seragam) menjadi seragam, trik yang umum adalah memanfaatkan pengetahuan domain untuk mengurangi asimetri; misalnya, walaupun data punya struktur berdimensi tinggi, secara lokal data sering menjadi cukup seragam karena noise; jika centroid dihitung dan disimpan, centroid menjadi lebih seragam, lalu setiap vektor disimpan terpisah menjadi indeks centroid dan offset vektor; indeks cocok untuk kompresi entropi yang efisien, dan offset kini hampir seragam sehingga lebih mudah menerapkan strategi sphere packing yang sudah ada
  • Mungkin ini juga sudah pernah dicoba, tetapi bisa diuji apakah precompression dapat mengurangi sparsity vektor dan meningkatkan keseragaman
  • Candaan bahwa saat benar-benar menyentuh vektor, harus berhati-hati (grope berarti “meraba-raba”, typo dari group)
  • Perluasan cakupan teori ke persoalan yang lebih praktis, yaitu data yang tidak homogen; kalau ragam penerapan dunia nyata terlalu banyak, pendekatan umum mungkin memang sulit, tetapi tetap perlu ada perhatian pada perluasan riset ini
  • Penunjukan bahwa pada bidang lama yang penting secara komersial, sebagian besar hasil yang mudah diraih mungkin sudah lama dipanen
• Setuju dengan klaim Klartag bahwa “bangun cembung sangat kuat dan sangat berguna”; meski bukan matematikawan, saya sering melihat algoritme Convex Hull muncul di tempat tak terduga, terutama dalam berbagai persoalan seperti dekomposisi palet otomatis pada gambar; dibagikan tautan makalah rujukan Convex Hull and automatic palette decomposition
• Klartag mengatakan metode sphere packing barunya dapat memuat bola sebanyak d kali lebih banyak dibanding sebelumnya jika dimensinya adalah d; jadi 100 kali lipat di 100 dimensi dan sejuta kali lipat di sejuta dimensi terdengar luar biasa, sehingga muncul pertanyaan apakah dalam berbagai sistem komunikasi ini benar-benar berarti bandwidth bisa meningkat puluhan hingga ratusan kali lipat atau konsumsi daya bisa turun drastis
  • Dalam praktiknya, makin tinggi dimensinya, density justru memburuk secara eksponensial menjadi n^2/2^n, sehingga peningkatan linear dalam teori tidak langsung tercermin sepenuhnya pada performa nyata; artinya ini berguna untuk data yang secara alami punya struktur berdimensi tinggi, tetapi untuk data digital (yang panjangnya bisa dipilih) kita bisa memilih dimensi kecil; lihat detail sphere packing di wikipedia link
• Gagasan bahwa matematikawan seharusnya bisa mengambil gelar doktor kedua di bidang yang berdekatan, bukan bidang yang sama, beberapa tahun setelah doktor pertama
  • Tujuan mendasar gelar doktor adalah membuktikan kemampuan melakukan riset secara mandiri, sehingga pada praktiknya banyak peneliti yang setelah lulus doktor berpindah bidang atau mengubah topik minatnya, dan sejak saat itu yang menjadi pusat adalah “riset” itu sendiri
  • Sebagai contoh nyata bahwa ini mungkin, matematikawan terkenal Bela Bollobas memiliki dua gelar doktor di dua bidang, yaitu geometri diskret dan analisis fungsional; meskipun di dunia akademik modern akan sangat sulit mencoba hal yang sama lagi
  • Jika fleksibilitas institusional seperti ini ada di seluruh sains, keterampilan dan ide dari bidang yang berbeda bisa saling berpindah dengan cepat dan berpotensi mempercepat kemajuan sains; khususnya di bidang seperti matematika, yang koneksi antarcabangnya penting, manfaatnya diperkirakan makin besar
• Pertanyaan pemula: apakah sphere packing optimal selalu terkait dengan kisi reguler; di 2D dan 3D memang begitu, tetapi apakah itu juga berlaku di ND
  • Selain di dimensi 2 dan 3, ada juga kasus di dimensi 8 (kisi E₈) dan 24 (kisi Leech) di mana best packing terbukti berbentuk kisi reguler; ini dibuktikan oleh Maryna Viazovska dan rekan-rekannya pada 2017, dan dibagikan tautan ke paper1, paper2, dan pdf penjelasan; tetapi di dimensi lain mungkin ada contoh tandingan di mana packing optimal bukan kisi reguler, dan pada sebagian dimensi bentuk tak beraturan justru bisa lebih rapat
  • Tidak harus begitu; bahkan di 3D, selain menyusun dengan lattice (kisi reguler), ada tak terhitung banyaknya susunan non-kisi dengan menggeser horizontal tiap lapisan secara berbeda; dalam kasus ini densitasnya tetap sama dengan kisi FCC, dan di dimensi tinggi ada dugaan bahwa kurangnya simetri membuat packing optimal justru selalu non-kisi
• Rasa ingin tahu tentang dimensi minimum di mana struktur sphere packing baru ini mulai mengungguli dimensi-dimensi yang sebelumnya sudah terbukti memiliki densitas terbaik
• Usulan arah pengembangan apakah hasil riset ini bisa dimanfaatkan di bidang kriptografi dan komunikasi untuk mengembangkan sistem komunikasi yang secara nyata lebih aman, lebih andal, dan lebih hemat energi; bidang riset yang sangat menarik
• Perumpamaan jenaka bahwa dalam fisika nyata ada kemungkinan aplikasi praktis dari “Cow Packing” (misalnya studi teoretis tentang mengisi sapi pada densitas optimal)
• Menarik bahwa sphere packing benar-benar muncul dalam begitu banyak persoalan di bidang terapan; menantikan membaca makalahnya dengan saksama