Brenda Sue Baker is an American computer scientist. She is known for Baker's technique for

approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...

s on planar graphs, for her early work on

duplicate code In computer programming, duplicate code is a sequence of source code that occurs more than once, either within a program or across different programs owned or maintained by the same entity. Duplicate code is generally considered undesirable for a n ...

detection, and for her research on two-dimensional

bin packing problem The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has ma ...

s. Baker did her undergraduate studies at Radcliffe College.. She earned a Ph.D. from

Harvard University Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of higher le ...

in 1973; her dissertation concerned

automata theory Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο� ...

and

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...

s, and was supervised by

Ronald V. Book Ronald Vernon Book (March 5 1937 – May 28, 1997 in Santa Barbara, California) was a theoretical computer scientist. He published more than 150 papers in scientific journals. His papers are of great impact for computational complexity theory In ...

. Early in her career she was an instructor and Vinton-Hayes Research Fellow at Harvard's Division of Engineering and Applied Physics, a visiting lecturer in the Department of Electrical Engineering and Computer Sciences at the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

, and an assistant professor in the Department of Computer and Communication Sciences at the

University of Michigan , mottoeng = "Arts, Knowledge, Truth" , former_names = Catholepistemiad, or University of Michigania (1817–1821) , budget = $10.3 billion (2021) , endowment = $17 billion (2021)As o ...

. Later she worked at

Bell Laboratories Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial research and scientific development company owned by mult ...

, becoming a Distinguished Member of Technical Staff there. Baker married another Bell Labs computer scientist, Eric Grosse, who would later become Google's Vice President for Security & Privacy Engineering. Their son, Roger Baker Grosse, is also a computer science researcher.

Research

Her research interests principally include algorithm and software tools. Specifically, she has worked on problems involving string pattern matching, combinatorial algorithms, and approximation algorithms for NP-hard problems. In the software tools domain, she designed tools to analyze and compare source code and compiled executables. These tools include ''Dup'' and ''Pdiff'', which compare regions of source code to determine if there are any repeated segments, as well as ''Exediff'', which enables the creation of small patches for executables without requiring access to the source code they were compiled from.

Selected publications

*. * *. *. *. *.

References

{{DEFAULTSORT:Baker, Brenda S. Year of birth missing (living people) Living people American computer scientists Radcliffe College alumni 20th-century American women scientists 21st-century American women scientists University of Michigan faculty Harvard University alumni UC Berkeley College of Engineering faculty American women computer scientists 20th-century American scientists 21st-century American scientists Theoretical computer scientists American women academics