- SOSA: viết tắt của Symposium on Simplicity in Algorithms là hội nghị lần đầu tiên được tổ chức với mục tiêu publish những paper đơn giản mà "đẹp". Tập các accepted papers đã được công bố (https://simplicityalgorithms.wixsite.com/sosa/program). Một số paper mà mình yêu thích:
- A Naive Algorithm for Feedback Vertex Set by Yixin Cao. Bài báo đề xuất một giải thuật FPT đơn giản dựa trên greedy branching cho bài toán Feedback Vertex Set trong thời gian $O(8^k n^2)$.
- Một super-star với hơn 2 triệu Citation trên Google Scholar: Et Al. https://scholar.google.nl/citations?user=qGuYgMsAAAAJ&hl=en
- Svensson, Tarnawski, và Végh tìm ra giải thuật với độ xấp xỉ (approximation factor) O(1) cho bài toán Asymmetric TSP (ATSP); một biến thể của bài toán TSP trên đồ thị có hướng. Trên đồ thị vô hướng, ta có thể xấp xỉ TSP với mức độ xấp xỉ O(1) khá đơn giản như sau: tìm một cây khung nhỏ nhất, sau đó double các cạnh và short cut. Xấp xỉ ATSP với mức độ O(1) khó hơn TSP rất nhiều; và đây là một bài toán mở mấy chục năm nay.
- Paper: https://arxiv.org/abs/1708.04215 đang được submit vào STOC 2018.
- Bài vết dễ hiểu hơn, không bao gồm các ngôn ngữ kĩ thuật, trên Quanta Magazine: https://www.quantamagazine.org/one-way-salesman-finds-fast-path-home-20171005/
- Bài viết trên rjlipton blog, có bao gồm mô tả sâu hơn về kĩ thuật và một số bài toán liên quan:
https://rjlipton.wordpress.com/2017/09/11/a-tsp-breakthrough/
- Càng ngày Nature càng tệ. Còn nhớ mấy năm trước Nature xuất bản một bài về Cryptography mà các chuyên gia cho là vô cùng tệ (thậm chí một người còn cho rằng các tác giả chả biết gì về Crypto cả). Fuck Nature! http://retractionwatch.com/2017/11/07/17-johns-hopkins-researchers-resign-protest-ed-board-nature-journal/.
- Tham khảo thêm ở đây về Nature với ngành KHMT: http://www.procul.org/blog/2005/12/10/t%E1%BA%A1p-chi-nature-va-khmt/
- Tranh cãi xung quanh ranking ngành CS. https://cra.org/cra-statement-us-news-world-report-rankings-computer-science-universities/
- Đọc thêm post của Lance Fortnow: http://blog.computationalcomplexity.org/2017/11/a-tale-of-three-rankings.html
- Đôi khi sử dụng floating-point division nhanh hơn sử dụng integer division: https://lemire.me/blog/2017/11/16/fast-exact-integer-divisions-using-floating-point-operations/. Mình thấy kĩ thuật này khá counter-intuitive.
- Đọc sách in đôi khi tốt hơn đọc bản mềm: http://www.businessinsider.com/students-learning-education-print-textbooks-screens-study-2017-10. Mỗi khi gặp paper mà mình thực sự muốn nghiên cứu kĩ lưỡng thì bước đầu tiên mình làm là in nó ra.
- Bài viết về Ryan Williams (có lần mình đã linked trong blog) và những đóng góp trong lý thuyết khoa học máy tính: http://news.mit.edu/2017/faculty-profile-ryan-williams-1122
- Cái gì mang Deep Learning tới cộng đồng Computer Vision? Theo Malik, có 2 nhân tố quan trọng: dữ liệu lớn và tính toán với dữ liệu lớn (big data and big computation) mà hai đại diện tương ứng là ImageNet và GPU. Link: https://dl.acm.org/citation.cfm?id=3065384.
- Bài này phải trả tiền. Nếu bạn nào không down lậu được thì email mình gửi cho một bản.
- Sách mới của Oded Goldreich về Property Testing, một nhánh mới nổi của lý thuyết khoa học máy tính: http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html. Oded có thể nói là một great writer. Các textbook của ông đều khá đầy đủ với phong cách viết dễ đọc. Các bạn có thể tìm được thông tin về các sách của ông trong trang cá nhân.
- Survey của Boaz Barak về nền tảng lý thuyết của mật mã khóa công khai (public key cryptography). https://eccc.weizmann.ac.il/report/2017/065/
cs-ranking
You are currently browsing articles tagged cs-ranking.
Theory News 11/2017
November 27, 2017 in News | No comments
Tags: Boaz Barak, cs-ranking, deep-learning, feedback-vertex-set, nature, oded, property-testing, Ryan Williams, theory-news, tsp
Recent Posts
Categories
Igor Park
- Two constructions April 19, 2024 igorpak
Terry Tao
- Two announcements: AI for Math resources, and erdosproblems.com April 19, 2024 Terence Tao
David Eppstein
- Linkage David Eppstein
Luca Trevisan
- The Moore Bound for Irregular Graphs February 24, 2024 luca
Vũ Hà Văn
- Bắc Kinh, thủ đô bất đắc dĩ December 1, 2023 vuhavan
Đàm Thanh Sơn
- Aron Pinczuk March 30, 2024 damtson
PhD Comics
- 08/31/23 PHD comic: 'New Book! Oliver's Great Big Universe!' December 14, 2021
XKCD
- Pub Trivia April 19, 2024
ACM-XRDS
- How to Change a Career XRDS Staff
Peter Cameron
- Ischia group theory conference 2024 Peter Cameron
Jacob Steinhardt
- New new blog location October 13, 2021 jsteinhardt
Rigor+Relevance
- Another book chapter is up! September 26, 2017 Adam Wierman
Recent Comments