Andrei Zary Broder (born April 12, 1953) is a distinguished scientist at

Google Google LLC (, ) is an American multinational corporation and technology company focusing on online advertising, search engine technology, cloud computing, computer software, quantum computing, e-commerce, consumer electronics, and artificial ...

. Previously, he was a

research fellow A research fellow is an academic research position at a university or a similar research institution, usually for academic staff or faculty members. A research fellow may act either as an independent investigator or under the supervision of a p ...

and

vice president A vice president or vice-president, also director in British English, is an officer in government or business who is below the president (chief executive officer) in rank. It can also refer to executive vice presidents, signifying that the vi ...

of computational advertising for

Yahoo! Yahoo (, styled yahoo''!'' in its logo) is an American web portal that provides the search engine Yahoo Search and related services including My Yahoo, Yahoo Mail, Yahoo News, Yahoo Finance, Yahoo Sports, y!entertainment, yahoo!life, and its a ...

, and before that, the vice president of research for

AltaVista AltaVista was a web search engine established in 1995. It became one of the most-used early search engines, but lost ground to Google and was purchased by Yahoo! in 2003, which retained the brand, but based all AltaVista searches on its own sear ...

. He has also worked for

IBM Research IBM Research is the research and development division for IBM, an American Multinational corporation, multinational information technology company. IBM Research is headquartered at the Thomas J. Watson Research Center in Yorktown Heights, New York ...

as a distinguished

engineer Engineers, as practitioners of engineering, are professionals who Invention, invent, design, build, maintain and test machines, complex systems, structures, gadgets and materials. They aim to fulfill functional objectives and requirements while ...

and was CTO of IBM's Institute for Search and Text Analysis.

Education and career

Broder was born in

Bucharest Bucharest ( , ; ) is the capital and largest city of Romania. The metropolis stands on the River Dâmbovița (river), Dâmbovița in south-eastern Romania. Its population is officially estimated at 1.76 million residents within a greater Buc ...

, Romania, in 1953. His parents were medical doctors, his father a noted oncological surgeon. They emigrated to

Israel Israel, officially the State of Israel, is a country in West Asia. It Borders of Israel, shares borders with Lebanon to the north, Syria to the north-east, Jordan to the east, Egypt to the south-west, and the Mediterranean Sea to the west. Isr ...

in 1973, when Broder was in the second year of college in Romania, in the Electronics department at the

Politehnica University of Bucharest Politehnica University of Bucharest () is a technical university in Bucharest, Romania founded in 1818.Technion – Israel Institute of Technology The Technion – Israel Institute of Technology is a public university, public research university located in Haifa, Israel. Established in 1912 by Jews under the dominion of the Ottoman Empire, the Technion is the oldest university in the coun ...

, in the EE Department. Broder graduated from Technion in 1977, with a B.Sc. summa cum laude. He was then admitted to the PhD program at Stanford, where he initially planned to work in the systems area. His first adviser was John L. Hennessy. After receiving a "high pass" at the reputedly hard algorithms qual,

Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...

, already a Turing Award and National Medal winner, offered him the opportunity to become his advisee. Broder finished his PhD under Knuth in 1985. He then joined the newly founded

DEC Systems Research Center The Systems Research Center (SRC) was a research laboratory created by Digital Equipment Corporation (DEC) in 1984, in Palo Alto, California. DEC SRC was founded by a group of computer scientists, led by Robert Taylor, who left the Computer ...

Palo Alto Palo Alto ( ; Spanish language, Spanish for ) is a charter city in northwestern Santa Clara County, California, United States, in the San Francisco Bay Area, named after a Sequoia sempervirens, coastal redwood tree known as El Palo Alto. Th ...

. At DEC SRC, Andrei was involved with

from the very beginning, helping it deal with duplicate documents and spam. When AltaVista split from

Compaq Compaq Computer Corporation was an American information technology, information technology company founded in 1982 that developed, sold, and supported computers and related products and services. Compaq produced some of the first IBM PC compati ...

that bought DEC, Andrei became its CTO and then chief scientist and VP of research. In 2002, he joined

in New York to build its enterprise search product. In 2005, he returned to Silicon Valley and the Web Industry, as a Yahoo Fellow and vice president. There, he put the bases of a new discipline, Computational advertising, the science of matching ads to users and contexts. At Yahoo, Broder also helped build Yahoo! Research into one of the leading Web research organizations. Broder was elected a member of the

National Academy of Engineering The National Academy of Engineering (NAE) is an American Nonprofit organization, nonprofit, NGO, non-governmental organization. It is part of the National Academies of Sciences, Engineering, and Medicine (NASEM), along with the National Academ ...

in 2010 for his contributions to the science and engineering of the World Wide Web. In 2012, Broder joined

as a distinguished scientist, where he switched focus to another aspect of the WWW experience, large-scale personalization.

Contributions

In 1989, he discovered (independently from David Aldous) an algorithm for generating a

uniform spanning tree A uniform is a variety of costume worn by members of an organization while usually participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency serv ...

of a given graph. Over the last fifteen years, Broder pioneered several algorithms systems and concepts fundamental to the science and technology of the

World Wide Web The World Wide Web (WWW or simply the Web) is an information system that enables Content (media), content sharing over the Internet through user-friendly ways meant to appeal to users beyond Information technology, IT specialists and hobbyis ...

. Some of the highlights include: In 1997, Broder led the development of the first practical solution for finding near-duplicate documents on web-scale using " shingling" to reduce the problem to a set-intersection problem and "min-hashing" or to construct "sketches" of sets. This was a pioneering effort in the area of

locality-sensitive hashing In computer science, locality-sensitive hashing (LSH) is a fuzzy hashing technique that hashes similar input items into the same "buckets" with high probability. (The number of buckets is much smaller than the universe of possible input items.) Si ...

. In 1998, he co-invented the first practical test to prevent robots from masquerading as human and access web sites, often referred to as

CAPTCHA Completely Automated Public Turing Test to tell Computers and Humans Apart (CAPTCHA) ( ) is a type of challenge–response authentication, challenge–response turing test used in computing to determine whether the user is human in order to de ...

. In 2000, Broder, then at AltaVista, together with colleagues from IBM and DEC SRC, conducted the first large-scale analysis of the Web graph, and identified the bow-tie model of the web graph. Around 2001–2002, Broder published an opinion piece where he qualified the differences between classical information retrieval and Web search and introduced a now widely accepted classification of web queries into navigational, information, and transactional.

Awards and honors

He is a fellow of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membe ...

, and the

IEEE The Institute of Electrical and Electronics Engineers (IEEE) is an American 501(c)(3) organization, 501(c)(3) public charity professional organization for electrical engineering, electronics engineering, and other related disciplines. The IEEE ...

. He was one of the recipients of the 2012 ACM

Paris Kanellakis Award The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery (ACM) to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". It wa ...

for his work on

w-shingling In natural language processing a ''w''-shingling is a set of ''unique'' ''shingles'' (therefore ''n-grams'') each of which is composed of contiguous subsequences of tokens within a document, which can then be used to ascertain the similarity b ...

and min-hashing, and he won this award again in 2020, together with Yossi Azar,

Anna Karlin Anna R. Karlin is an American computer scientist, the Microsoft Professor of Computer Science & Engineering at the University of Washington. Biography Karlin was born into an academic family. Her father, Samuel Karlin, was a mathematician at S ...

Michael Mitzenmacher Michael David Mitzenmacher is an American computer scientist working in algorithms. He is Professor of Computer Science at the Harvard John A. Paulson School of Engineering and Applied Sciences and was area dean of computer science July 2010 to ...

, and

Eli Upfal __NOTOC__ Eli Upfal () is a computer science researcher, currently the Rush C. Hawkins Professor of Computer Science at Brown University. He completed his undergraduate studies in mathematics and statistics at the Hebrew University of Jerusalem i ...

for their work on the power of two choices.

References

External links

* * * {{DEFAULTSORT:Broder, Andrei 1953 births Living people Scientists from Bucharest Yahoo! employees IBM employees American technology chief executives American computer businesspeople American computer scientists American people of Romanian-Jewish descent Israeli computer scientists Israeli emigrants to the United States Stanford University alumni Technion – Israel Institute of Technology alumni 2007 fellows of the Association for Computing Machinery Romanian emigrants to Israel