Tổng quan về luận án

Luận án tiến sĩ với tiêu đề "On the Design and Worst-Case Analysis of Certain Interactive and Approximation Algorithms" do tác giả Jia Mao thực hiện dưới sự hướng dẫn của Giáo sư Ronald L. Graham tại Khoa Khoa học Máy tính và Kỹ thuật, Đại học California, San Diego (UCSD, 2007). Nghiên cứu đặt trọng tâm vào việc xây dựng nền tảng lý thuyết và thiết kế thuật toán tối ưu cho các mô hình tính toán tương tác (interactive computations), tính toán động (dynamic computations) và bài toán xấp xỉ tổ hợp (combinatorial approximation). Như tác giả đã khẳng định: "With the speed of current technological changes, computation models are evolving to become more interactive and dynamic. These computation models often differ from traditional ones in that not every piece of the information needed for decision making is available a priori."

Khoảng trống nghiên cứu (research gap) trọng tâm mà luận án giải quyết xuất phát từ sự thiếu hụt các giới hạn cận chặt (tight bounds) và thuật toán hữu hiệu trong hai bài toán nền tảng:

  1. Bài toán Trò chơi Đa số và Đa số tương đối (Majority/Plurality Games): Đã được Moore (1982) đề xuất trong chẩn đoán hệ thống chịu lỗi (fault-tolerant diagnosis) và kiểm thử nhóm (group testing), nhưng độ phức tạp truy vấn trong môi trường không tương tác (oblivious setting) khi số lượng nhãn $k$ tùy ý vẫn tồn tại khoảng cách rất lớn giữa cận trên lũy thừa và cận dưới tam thức.
  2. Bài toán Đóng thùng với ràng buộc kiểu phần tử ($kBPS$ / $2BPS$): Bắt nguồn từ bài toán thực tế về phân bổ bộ nhớ động cho các bộ xử lý song song trong động cơ chuyển tiếp gói tin router tốc độ cao (pipelined router forwarding engines) do George Varghese, Fan Chung và Ron Graham khởi xướng.

Luận án giải quyết hệ thống 4 câu hỏi nghiên cứu (Research Questions - RQ) và kiểm chứng 4 giả thuyết cốt lõi (Hypotheses - H):

  • RQ1: Trong bài toán Majority Game với $k$ nhãn chưa biết ở chế độ oblivious, liệu có tồn tại chiến lược truy vấn tuyến tính $O(n)$ khi biết trước sự tồn tại của phần tử đa số hay không?

  • RQ2: Đối với Plurality Game với $k \ge 3$, việc mở rộng từ đa số tuyệt đối sang đa số tương đối làm thay đổi cấu trúc độ phức tạp như thế nào giữa hai chế độ tương tác thích ứng (adaptive) và không tương tác (oblivious)?

  • RQ3: Khi đối thủ (Adversary) được phép cung cấp thông tin sai lệch có giới hạn ($t$ lần nói dối trong trò chơi Rényi-Ulam Liar Game), số lượng câu hỏi tối thiểu tăng lên như thế nào để đảm bảo tính kháng lỗi tuyệt đối?

  • RQ4: Trong bài toán $2BPS$ (NP-hard), làm thế nào để phá vỡ rào cản tỷ số xấp xỉ cạnh tranh truyền thống thông qua kỹ thuật cải tiến sai số $\epsilon$ và kiểm soát chi phí tái đóng gói (repacking cost) trong môi trường động?

  • H1: Cấu trúc đồ thị mở rộng Ramanujan (Ramanujan expander graphs) với khoảng cách phổ (spectral gap) cực đại cho phép tạo ra chiến lược truy vấn oblivious tuyến tính $(1+o(1))21n$ cho Majority Game khi phần tử đa số tồn tại.

  • H2: Ngược lại với Majority Game, bài toán Plurality Game ở chế độ oblivious đòi hỏi độ phức tạp bậc hai $\Omega(n^2)$ ngay cả khi đã biết trước sự tồn tại của phần tử đa số tương đối.

  • H3: Trong bài toán Majority Game có lỗi sai ($t$ lies), chiến lược thích ứng có thể đạt giới hạn truy vấn tuyến tính đối với $t = o(n^{1/2})$.

  • H4: Kỹ thuật phân tích chuỗi $\epsilon$-improvement cho phép cải thiện tỷ số xấp xỉ cho thuật toán $2BPS$ và tham số tỷ số nén (compaction ratio) bị chặn giúp cân bằng tối ưu giữa việc sử dụng tài nguyên và chi phí di chuyển dữ liệu.

Phạm vi nghiên cứu (Scope) tập trung vào phân tích toán học thuần túy trong trường hợp xấu nhất (worst-case analysis), áp dụng cho không gian $n$ phần tử tùy ý, $k$ nhãn phân loại, hệ thống tham số mở rộng đồ thị $d$-regular bậc $p+1$, và dữ liệu cấu hình luồng mạng chuyển tiếp IP thực tế.

Literature Review và Positioning

Khung lý thuyết của luận án được xây dựng dựa trên sự giao thoa của ba nhánh học thuật lớn: lý thuyết thông tin - trò chơi tìm kiếm tổ hợp, lý thuyết phổ đồ thị (spectral graph theory), và lý thuyết thuật toán xấp xỉ trực tuyến (online approximation algorithms).

Trong nhánh trò chơi đa số, Saks và Werman (1991) đã đặt mốc lịch sử khi chứng minh cận dưới chặt cho trường hợp thích ứng với 2 nhãn là $M A_2(n) = n - \mu_2(n)$ (trong đó $\mu_2(n)$ biểu thị số lượng chữ số 1 trong biểu diễn nhị phân của $n$), được củng cố bằng các cách tiếp cận độc lập của Alonso et al. (1993) và Wiener (2002). Đối với trường hợp không biết số nhãn $k$, Fischer và Salzberg (1982) đã chứng minh giới hạn chặt $\lceil 3n/2 \rceil - 2$. Tuy nhiên, nhánh nghiên cứu về mô hình không tương tác (oblivious strategies) vẫn tồn tại những tranh luận sâu sắc:

  • Tranh luận giữa phân tích trường hợp trung bình (Average-case) và trường hợp xấu nhất (Worst-case): Aigner (2004) cùng Alonso et al. (1997) phân tích hành vi kỳ vọng dưới giả định phân phối ngẫu nhiên đều của các nhãn. Luận án của Jia Mao bảo vệ quan điểm phân tích cạnh tranh trường hợp xấu nhất có đối thủ (adversarial model), chỉ ra rằng phân tích trung bình đánh giá quá lạc quan khả năng phòng thủ của hệ thống trước các chuỗi đầu vào độc hại hoặc phân phối dị biệt.
  • Mâu thuẫn giữa tính khả thi của thuật toán ngẫu nhiên hóa và thuật toán xác định: Khác với các công trình dựa vào cấu trúc ngẫu nhiên hóa không tường minh (non-constructive random graphs), Jia Mao định vị nghiên cứu bằng cách kết hợp đồ thị mở rộng hiện thực hóa tường minh (explicit Ramanujan graphs $X_{p,q}$) của Lubotzky, Phillips và Sarnak (1988), thu hẹp khoảng cách giữa lý thuyết thuần túy và ứng dụng kỹ thuật mạng.

So sánh với hai nghiên cứu quốc tế tiêu biểu:

  1. So sánh với Aigner et al. (2005) về bài toán Plurality 3 màu: Aigner đưa ra cận trên tuyến tính cho thuật toán thích ứng nhưng chưa giải quyết được cấu trúc cận dưới oblivious. Mao chứng minh cận dưới $P O_3(n) > (\frac{1}{6} - o(1))n^2$, vạch rõ ranh giới phân tách thông tin giữa Majority và Plurality.
  2. So sánh với Pelc (2002) và Cicalese et al. (2005) về Rényi-Ulam Liar Game: Các nghiên cứu trước chủ yếu xử lý câu hỏi tập hợp "x có thuộc tập con S không?". Luận án mở rộng thành công mô hình này sang câu hỏi so sánh cặp tương đối "nhãn của $a$ có bằng nhãn của $b$ không?" dưới sự can thiệp của $t$ lỗi sai, tạo bước đột phá trong lý thuyết kiểm thử chịu lỗi.

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án mang lại những đóng góp nền tảng cho lý thuyết khoa học máy tính thông qua việc thiết lập các định lý mới, mở rộng lý thuyết trò chơi tìm kiếm và lý thuyết xấp xỉ tổ hợp:

  1. Đột phá về cận trên tuyến tính trong Majority Game không tương tác (Oblivious Setting): Khi $k$ tùy ý và biết trước sự tồn tại của đa số tuyệt đối, luận án chứng minh định lý bước ngoặt: $$M O^*(n) \le (1 + o(1))21n$$ Hệ số 21 được chứng minh thông qua đồ thị Ramanujan xác định bậc $p+1 \ge 39$, và có thể giảm xuống $19.5n$ nếu sử dụng đồ thị ngẫu nhiên $G(n,p)$. Đây là bằng chứng lý thuyết chứng minh rằng việc thiếu tương tác từng bước không làm bùng nổ độ phức tạp truy vấn từ tuyến tính lên bậc hai đối với bài toán Majority.
  2. Xác lập rào cản thông tin giữa Majority và Plurality: Chứng minh định lý cận dưới bậc hai cho Plurality Game ở chế độ oblivious ngay cả khi biết trước sự tồn tại của đa số tương đối: $$P O_k(n) \ge \left(\frac{1}{6} - o(1)\right)n^2 \quad (\forall k \ge 3)$$ Phát hiện này tái định hình hiểu biết lý thuyết: biết trước sự tồn tại của đa số tuyệt đối ($> n/2$) cung cấp lượng thông tin cấu trúc mạnh hơn vượt trội so với đa số tương đối.
  3. Mở rộng lý thuyết trò chơi nói dối (Liar Games): Luận án thiết lập khung đánh giá chính xác số lượng truy vấn khi đối thủ được phép nói dối $t$ lần. Với $t=1$, cận trên thích ứng đạt chính xác $n+1$ ($n$ lẻ) và $n+2$ ($n$ chẵn). Với $t > 1$, cận trên đạt: $$\frac{t+1}{2}n + 6t + 2^{t+1} + 3\log n$$
  4. Hình thành lý thuyết đóng thùng có ràng buộc kiểu phần tử ($kBPS$): Chứng minh tính chất NP-hard của $2BPS$, thiết lập cận dưới tỷ số cạnh tranh và xây dựng kỹ thuật $\epsilon$-improvement phá vỡ ngưỡng xấp xỉ $(2 - 1/k)$ truyền thống.

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp ba trụ cột phương pháp luận toán học:

  • Đồ thị phụ trợ tiến hóa (Auxiliary Evolving Graph $H$): Biểu diễn trạng thái tính toán trong đó mỗi truy vấn là một cạnh vô hướng kết nối hai đỉnh, màu sắc cạnh đại diện cho câu trả lời (Xanh: bằng nhau; Đỏ: khác nhau). Độ lệch của thành phần liên thông được lượng hóa bằng hàm sai phân: $$\delta(D) = \left| |V_1(D)| - |V_2(D)| \right|$$
  • Bất đẳng thức sai phân đồ thị mở rộng (Expander Mixing Lemma): Áp dụng trên đồ thị $d$-regular $H$ có $n$ đỉnh với giá trị riêng thứ hai $\lambda \le \delta$: $$\left| e(X, Y) - \frac{d}{n}|X||Y| \right| \le \frac{\delta}{n} \sqrt{|X|(n-|X|)|Y|(n-|Y|)}$$ cho phép khống chế số cạnh giữa hai tập đỉnh bất kỳ, loại bỏ hoàn toàn khả năng đối thủ tạo ra hai thành phần đa số giả mạo.
  • Khung phân tích tỷ số nén (Compaction Ratio Framework): Định nghĩa chỉ số đo lường sự đánh đổi giữa dung lượng bộ nhớ lãng phí và số thao tác di chuyển dữ liệu trong bài toán động, làm cầu nối giữa lý thuyết xấp xỉ và kiến trúc phần cứng.

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Luận án tuân thủ triết lý thực chứng (positivism) nghiêm ngặt của toán học rời rạc và khoa học máy tính lý thuyết. Thiết kế nghiên cứu sử dụng phương pháp phân tích trường hợp xấu nhất đối kháng (adversarial worst-case design):

Mô hình hóa toàn bộ quá trình tính toán thành trò chơi 2 người giữa Người truy vấn (Questioner - Q) và Đối thủ (Adversary - A):

  • $Q$ tìm cách tối thiểu hóa số lượng câu hỏi truy vấn $q$.
  • $A$ tìm cách tối đa hóa $q$ bằng cách gán nhãn hoặc cung cấp câu trả lời hợp lệ trì hoãn tối đa việc xác định kết quả.

Quy trình nghiên cứu rigorous

Quy trình chứng minh và giải thuật được thực hiện qua 4 giai đoạn chuẩn hóa:

  1. Giai đoạn 1 - Mô hình hóa đồ thị phụ trợ: Chuyển đổi trạng thái tri thức về hệ thống thành cấu hình đồ thị $H=(V,E)$.
  2. Giai đoạn 2 - Rút gọn phổ và thiết kế cấu trúc Expander:
    • Sử dụng họ đồ thị Ramanujan $X_{p,q}$ xây dựng trên trường hữu hạn với số đỉnh $n = \frac{1}{2}q(q^2 - 1)$ ($p, q$ là các số nguyên tố đồng dư $1 \pmod 4$).
    • Bậc đồ thị $d = p + 1$, thỏa mãn chặn phổ Alon-Boppana tối ưu: $$\lambda_1 \le 2\sqrt{p}$$
  3. Giai đoạn 3 - Phân lập thành phần liên thông cực đại: Sử dụng bất đẳng thức phân tán chứng minh rằng nếu $p \ge 38$, mọi phép gán nhãn hợp lệ buộc phải tạo ra một thành phần liên thông màu xanh duy nhất có kích thước vượt ngưỡng $c_0 n > \frac{1}{3}n$.
  4. Giai đoạn 4 - Bù trừ số học giải tích: Bổ sung kỹ thuật làm đầy đỉnh $\delta(n) = o(n^{3/5})$ từ lý thuyết số giải tích để mở rộng kết quả từ tập số nguyên tố sang mọi số tự nhiên $n$.

Data và phân tích

Toàn bộ dữ liệu trong luận án được phân tích định lượng chính xác dựa trên cấu trúc tổ hợp và giải tích toán học:

  • Tính toán tiệm cận và hằng số mở rộng: Xác định chính xác ngưỡng bậc đồ thị $p \ge 38$ thông qua bất đẳng thức bậc hai liên kết bán kính phổ và kích thước thành phần: $$\beta \ge \frac{1}{2}\left(\alpha + \sqrt{\alpha^2 - \frac{16(1-\alpha)p}{(p-1)^2}}\right) > \frac{1}{3}$$
  • Phân tích độ nhạy (Robustness checks): Kiểm chứng khả năng chịu lỗi trước $t$ câu trả lời nghịch đảo mà không làm mất tính đúng đắn của phần tử đa số được nhận diện.

Phát hiện đột phá và implications

Những phát hiện then chốt

  1. Khám phá tính chất tuyến tính của Oblivious Majority: Trái ngược với giả định truyền thống cho rằng thiếu phản hồi tương tác sẽ dẫn đến bùng nổ số câu hỏi bậc hai, luận án chứng minh rằng chỉ cần $O(n)$ câu hỏi dạng khối (one-batch queries) là đủ để định danh phần tử đa số tuyệt đối khi biết trước sự tồn tại của nó.
  2. Sự sụp đổ của tính khả thi tuyến tính trong Plurality Game: Phát hiện mang tính phản trực giác sâu sắc (counter-intuitive result): dù bài toán Plurality chỉ là sự nới lỏng tự nhiên của Majority, ở chế độ oblivious nó chuyển pha đột ngột từ độ phức tạp $O(n)$ sang $\Theta(n^2)$. Cận dưới $(\frac{1}{6} - o(1))n^2$ được bảo toàn ngay cả khi biết trước chắc chắn phần tử đa số tương đối tồn tại.
  3. Cơ chế phòng thủ tối ưu trước kẻ nói dối (Liar Error-Tolerance): Xác lập công thức chính xác cho số truy vấn trong Majority Game có $t=1$ lỗi dối trá, chứng minh rằng hệ thống chỉ phải trả giá thêm đúng 1 đến 2 câu hỏi so với bài toán không có lỗi để đảm bảo tính an toàn 100%.
  4. Giải thuật $\epsilon$-Improvement cho bài toán phân bổ bộ nhớ $2BPS$: Phá vỡ giới hạn xấp xỉ $(2 - 1/k)$ bằng giải thuật $INC$ và $INC_k$, mở ra phương pháp tiếp cận mới trong tối ưu hóa việc phân chia tài nguyên có ràng buộc loại phần tử.

Implications đa chiều

  • Về mặt lý thuyết (Theoretical Advances): Kết nối thành công lý thuyết đồ thị phổ sâu sắc (Ramanujan expanders) với lý thuyết trò chơi tìm kiếm thông tin và chẩn đoán hệ thống phân tán.
  • Về mặt phương pháp luận (Methodological Innovations): Khung phân tích đồ thị tiến hóa (Auxiliary Evolving Graph) cùng hàm sai phân $\delta(D)$ cung cấp công cụ chuẩn tắc để giải quyết các bài toán tìm kiếm tổ hợp tương tác phức tạp.
  • Về ứng dụng thực tiễn (Practical Applications):
    • Ứng dụng trực tiếp vào cấu trúc bảng định tuyến router tốc độ cao (BGP/IP lookup engines), giảm thiểu chi phí bộ nhớ đệm SRAM/DRAM đắt đỏ.
    • Tối ưu hóa giao thức truyền thông trong mạng cảm biến không dây (wireless sensor networks), cho phép định vị cảm biến bị lỗi hoặc bị chiếm quyền điều khiển với số lượng gói tin trao đổi tối thiểu.
  • Về chính sách và tiêu chuẩn công nghệ (Policy & Standards): Cung cấp cơ sở định lượng để xây dựng các tiêu chuẩn an toàn cho hệ thống mạng chuyển mạch lõi viễn thông thế hệ mới.

Limitations và Future Research

Luận án thẳng thắn thừa nhận các giới hạn lý thuyết và điều kiện biên:

  1. Tính kiến tạo của đồ thị Ramanujan: Cận trên $(1+o(1))21n$ phụ thuộc vào việc xây dựng tường minh đồ thị Ramanujan với các số nguyên tố $p, q \equiv 1 \pmod 4$. Mặc dù hệ số có thể giảm xuống $19.5$ với đồ thị ngẫu nhiên, cấu trúc ngẫu nhiên lại không có tính chất xác định (non-deterministic).
  2. Khoảng cách cận trong Plurality Game: Vẫn tồn tại khoảng cách giữa cận dưới $(\frac{1}{6} - o(1))n^2$ và cận trên xác suất $(1 - \frac{1}{k} + \epsilon)\binom{n}{2}$ trong mô hình oblivious tổng quát.
  3. Giới hạn tham số lỗi dối trá $t$: Cận trên thích ứng cho Majority Game với $t$ lỗi dối trá chỉ áp dụng tối ưu khi $t = o(n^{1/2})$. Khi $t$ tỷ lệ thuận với $n$ ($t = \alpha n$), lời giải thích ứng tối ưu vẫn là bài toán mở.

Chương trình nghiên cứu 5-10 năm tiếp theo tập trung vào 4 định hướng:

  • Thu hẹp khoảng cách hằng số trong bài toán Oblivious Majority (tiến gần về cận dưới lý thuyết).
  • Khám phá mô hình lỗi ngẫu nhiên (probabilistic/noisy errors) thay vì mô hình lỗi đối kháng hoàn toàn (adversarial liars).
  • Mở rộng bài toán $kBPS$ sang không gian bộ nhớ phân cấp đa tầng (multi-tier hierarchical storage architectures).
  • Phát triển các thuật toán xấp xỉ phân tán (distributed approximation algorithms) hoàn toàn không tập trung.

Tác động và ảnh hưởng

Đối tượng hưởng lợi

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và nó mở rộng lý thuyết nào?

Đóng góp độc đáo nhất là việc chứng minh sự tồn tại của chiến lược truy vấn không tương tác (oblivious strategy) tuyến tính $O(n)$ cho bài toán Majority Game thông qua việc ứng dụng đồ thị mở rộng Ramanujan $X_{p,q}$. Nghiên cứu đã mở rộng trực tiếp lý thuyết trò chơi tìm kiếm tổ hợp (Combinatorial Search Games) và lý thuyết phổ đồ thị của Margulis (1973), Lubotzky-Phillips-Sarnak (1988), chứng minh rằng tính chất mở rộng phổ cực đại ($\lambda \le 2\sqrt{p}$) có thể triệt tiêu sự thiếu hụt thông tin tương tác từng bước.

2. Sự đổi mới về phương pháp luận so với các nghiên cứu trước đây?

So với phương pháp quy nạp trạng thái truyền thống của Saks & Werman (1991) hay phương pháp đồ thị ngẫu nhiên không tường minh của Erdős-Rényi, luận án giới thiệu hai đổi mới mang tính bước ngoặt:

  • Sử dụng Đồ thị phụ trợ tiến hóa (Auxiliary Graph $H$) kết hợp hàm sai phân $\delta(D)$ để theo dõi cấu hình trò chơi.
  • Ứng dụng Bất đẳng thức sai phân đồ thị mở rộng (Expander Mixing Lemma) trên cấu trúc đồ thị đại số tường minh, tạo ra công cụ tất định (deterministic) để giải quyết các bài toán tối ưu đối kháng.

3. Phát hiện gây bất ngờ nhất được hỗ trợ bởi dữ liệu toán học?

Phát hiện bất ngờ nhất là sự tương phản gay gắt về độ phức tạp giữa Majority Game và Plurality Game ở chế độ oblivious:

  • Majority Game: Đạt cận trên tuyến tính $(1+o(1))21n$.
  • Plurality Game: Rơi vào cận dưới bậc hai chặt $(\frac{1}{6}-o(1))n^2$ ngay cả khi $k=3$ và biết trước sự tồn tại của phần tử đa số tương đối. Điều này chứng minh rằng việc sở hữu tỷ lệ áp đảo $> 50%$ tạo ra bước nhảy vọt về mặt cấu trúc thông tin so với việc chỉ sở hữu tỷ lệ tương đối lớn nhất.

4. Luận án có cung cấp quy trình tái lập (Replication Protocol) không?

Có. Toàn bộ các định lý đều đi kèm chứng minh toán học giải tích chi tiết, thuật toán xây dựng đồ thị Ramanujan tường minh $X_{p,q}$ dựa trên nghiệm phương trình Diophantine bậc bốn và nhóm ma trận xạ ảnh $PGL_2(\mathbb{Z}/q\mathbb{Z})$, cùng mã giả chi tiết của các thuật toán xấp xỉ ($A_k$, $INC$, $INC_k$, $DYN$) được xuất bản trên các tạp chí bình duyệt quốc tế.

5. Chương trình nghiên cứu 10 năm được vạch ra như thế nào?

Chương trình tập trung giải quyết bài toán tổng quát hóa:

  • Thiết lập ranh giới chính xác cho bài toán $k$-color Plurality với $k \ge 4$.
  • Giải quyết bài toán Majority với tỷ lệ lỗi dối trá tuyến tính $t = \alpha n$.
  • Tối ưu hóa tỷ số nén trong bài toán dynamic bin packing đa chiều trên các hệ thống tính toán đám mây và trung tâm dữ liệu quy mô lớn.

Kết luận

Luận án tiến sĩ của Jia Mao đã giải quyết xuất sắc những thách thức cốt lõi trong thiết kế và phân tích thuật toán tương tác và xấp xỉ, để lại 5 dấu ấn học thuật quan trọng:

  1. Xác lập chuẩn mực độ phức tạp cho Majority Game: Đưa ra cận trên tuyến tính $(1+o(1))21n$ trong chế độ oblivious thông qua đồ thị Ramanujan và cận chặt $n - \mu_2(n)$ trong chế độ thích ứng.
  2. Chứng minh ranh giới thông tin Plurality Game: Thiết lập cận dưới bậc hai $\Omega(n^2)$ cho chế độ oblivious, vạch rõ sự phân kỳ bản chất giữa đa số tuyệt đối và đa số tương đối.
  3. Tiên phong trong lý thuyết trò chơi chịu lỗi: Giải quyết bài toán Majority Game với $t$ lỗi dối trá, cung cấp cận truy vấn chính xác cho $t=1$ và cận tiệm cận cho $t > 1$.
  4. Khai phá bài toán đóng thùng $kBPS$: Chứng minh tính chất NP-hard của $2BPS$, thiết lập giải thuật $\epsilon$-improvement và giải thuật động $DYN$ với tỷ số nén bị chặn.
  5. Mở ra 3 nhánh nghiên cứu liên ngành mới: Ứng dụng lý thuyết phổ đồ thị vào an ninh mạng cảm biến, thuật toán xấp xỉ phân bổ bộ nhớ cho phần cứng mạng tốc độ cao, và lý thuyết trò chơi tìm kiếm chịu lỗi đối kháng.

Công trình khẳng định vị thế tiên phong của Đại học California, San Diego trong việc kết hợp toán học tổ hợp thuần túy với kỹ thuật máy tính ứng dụng, tạo nền tảng vững chắc cho sự phát triển của các hệ thống mạng và tính toán phân tán trong kỷ nguyên số.