feedback-vertex-set

You are currently browsing articles tagged feedback-vertex-set.

Theory News 11/2017

  1. 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)$.
  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
  3. 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.
  4. 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/.
  5. Tranh cãi xung quanh ranking ngành CS. https://cra.org/cra-statement-us-news-world-report-rankings-computer-science-universities/
  6. Đô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.
  7. Đọ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.
  8. 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
  9. 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.
  10. 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.
  11. 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/

Tags: , , , , , , , , ,