Phòng "Cơ sở toán học của tin học" có tiền thân là Phòng "Toán rời rạc" (1975-1998), được xây dựng trên cơ sở Nhóm làm việc "Lý thuyết Ô tô mát và Ngôn ngữ hình thức", thuộc vào Bộ môn "Điều khiển học" do Giáo sư Phan Đình Diệu chủ nhiệm (1970-1975).

Các Trưởng phòng qua các thời kỳ (1975-2010): Đỗ Long Vân, Phạm Trà Ân, Ngô Đắc Tân và Lê Công Thành.

Các hướng nghiên cứu chính của Phòng: Lý thuyết đồ thị, hệ động lực rời rạc, tổ hợp đếm, thuật toán và độ phức tạp, lý thuyết ô tô mat.

Semina hàng tuần của Phòng vào mỗi sáng thứ năm là semina khoa học lâu đời nhất của Viện, được thành lập từ năm 1970, thu hút các cán bộ nghiên cứu và giảng viên từ  các Phòng chuyên môn của Viện và từ các Trường Đại học Tổng hợp, Đại học Bách khoa, Đại học Sư phạm Hà nội 2, Đại học Giao thông vận tải, vv.

Phòng thực hiện nhiều đề tài nghiên cứu cơ bản cấp nhà nước và các đề tại NAFOSTED.

Các cán bộ của Phòng tham gia công tác đào tạo NCS và thạc sỹ của Viện và của một số Trường Đại học.

Phòng có nhiều hợp tác quốc tế, đặc biệt là với các trường Đại học của Pháp.