Mathematics includes the study of such topics as quantity, structure and change. Mathematicians use patterns to formulate new conjectures; when mathematical structures are good models of real phenomena mathematical reasoning can provide insight or predictions about nature. Through the use of abstraction and logic, mathematics developed from counting, calculation and the systematic study of the shapes and motions of physical objects. Practical mathematics has been a human activity from as far back; the research required to solve mathematical problems can take years or centuries of sustained inquiry. Rigorous arguments first appeared in Greek mathematics, most notably in Euclid's Elements. Since the pioneering work of Giuseppe Peano, David Hilbert, others on axiomatic systems in the late 19th century, it has become customary to view mathematical research as establishing truth by rigorous deduction from appropriately chosen axioms and definitions. Mathematics developed at a slow pace until the Renaissance, when mathematical innovations interacting with new scientific discoveries led to a rapid increase in the rate of mathematical discovery that has continued to the present day.
Mathematics is essential in many fields, including natural science, medicine and the social sciences. Applied mathematics has led to new mathematical disciplines, such as statistics and game theory. Mathematicians engage in pure mathematics without having any application in mind, but practical applications for what began as pure mathematics are discovered later; the history of mathematics can be seen as an ever-increasing series of abstractions. The first abstraction, shared by many animals, was that of numbers: the realization that a collection of two apples and a collection of two oranges have something in common, namely quantity of their members; as evidenced by tallies found on bone, in addition to recognizing how to count physical objects, prehistoric peoples may have recognized how to count abstract quantities, like time – days, years. Evidence for more complex mathematics does not appear until around 3000 BC, when the Babylonians and Egyptians began using arithmetic and geometry for taxation and other financial calculations, for building and construction, for astronomy.
The most ancient mathematical texts from Mesopotamia and Egypt are from 2000–1800 BC. Many early texts mention Pythagorean triples and so, by inference, the Pythagorean theorem seems to be the most ancient and widespread mathematical development after basic arithmetic and geometry, it is in Babylonian mathematics that elementary arithmetic first appear in the archaeological record. The Babylonians possessed a place-value system, used a sexagesimal numeral system, still in use today for measuring angles and time. Beginning in the 6th century BC with the Pythagoreans, the Ancient Greeks began a systematic study of mathematics as a subject in its own right with Greek mathematics. Around 300 BC, Euclid introduced the axiomatic method still used in mathematics today, consisting of definition, axiom and proof, his textbook Elements is considered the most successful and influential textbook of all time. The greatest mathematician of antiquity is held to be Archimedes of Syracuse, he developed formulas for calculating the surface area and volume of solids of revolution and used the method of exhaustion to calculate the area under the arc of a parabola with the summation of an infinite series, in a manner not too dissimilar from modern calculus.
Other notable achievements of Greek mathematics are conic sections, trigonometry (Hipparchus of Nicaea, the beginnings of algebra. The Hindu–Arabic numeral system and the rules for the use of its operations, in use throughout the world today, evolved over the course of the first millennium AD in India and were transmitted to the Western world via Islamic mathematics. Other notable developments of Indian mathematics include the modern definition of sine and cosine, an early form of infinite series. During the Golden Age of Islam during the 9th and 10th centuries, mathematics saw many important innovations building on Greek mathematics; the most notable achievement of Islamic mathematics was the development of algebra. Other notable achievements of the Islamic period are advances in spherical trigonometry and the addition of the decimal point to the Arabic numeral system. Many notable mathematicians from this period were Persian, such as Al-Khwarismi, Omar Khayyam and Sharaf al-Dīn al-Ṭūsī. During the early modern period, mathematics began to develop at an accelerating pace in Western Europe.
The development of calculus by Newton and Leibniz in the 17th century revolutionized mathematics. Leonhard Euler was the most notable mathematician of the 18th century, contributing numerous theorems and discoveries; the foremost mathematician of the 19th century was the German mathematician Carl Friedrich Gauss, who made numerous contributions to fields such as algebra, differential geometry, matrix theory, number theory, statistics. In the early 20th century, Kurt Gödel transformed mathematics by publishing his incompleteness theorems, which show that any axiomatic system, consistent will contain unprovable propositions. Mathematics has since been extended, there has been a fruitful interaction between mathematics and science, to
Gábor Tardos is a Hungarian mathematician a professor at Central European University and a Canada Research Chair at Simon Fraser University. He works in combinatorics and computer science, he is the younger brother of Éva Tardos. Tardos started with a result in universal algebra: he exhibited a maximal clone of monotone operations, not finitely generated, he obtained partial results concerning the Hanna Neumann conjecture. With his student, Adam Marcus, he proved a combinatorial conjecture of Zoltán Füredi and Péter Hajnal, known to imply the Stanley–Wilf conjecture. With topological methods he proved that if H is a finite set system consisting of the unions of intervals on two disjoint lines τ ≤ 2 ν holds, where τ is the least number of points covering all elements of H and ν is the size of the largest disjoint subsystem of H. Tardos worked out a method for optimal probabilistic fingerprint codes. Although the mathematical content is hard, the algorithm is easy to implement, he received the European Mathematical Society prize for young researchers at the European Congress of Mathematics in 1992 and the Erdős Prize from the Hungarian Academy of Sciences in 2000.
He received a Lendület Grant from the Hungarian Academy of Sciences. Devised to keep outstanding researchers in Hungary. ———, "Optimal probabilistic fingerprint codes", Journal of the ACM, 55: 116, CiteSeerX 10.1.1.8.8911, doi:10.1145/780542.780561, ISBN 978-1581136746. ———, "Transversals of 2-intervals, a topological approach", Combinatorica, 15: 123–134, doi:10.1007/bf01294464. ———. "On the power of randomization in on-line algorithms", Algorithmica, 11: 2–14, doi:10.1007/bf01294260. ———, "A maximal clone of monotone operations, not finitely generated", Order, 3: 211–218, doi:10.1007/bf00400284. Gábor Tardos at the Mathematics Genealogy Project
Joseph Yehuda Halpern is a professor of computer science at Cornell University. Most of his research is on reasoning about uncertainty. Halpern graduated in 1975 from University of Toronto with a B. S. in mathematics. He went on to earn a Ph. D. in mathematics from Harvard University in 1981 under the supervision of Albert R. Meyer and Gerald Sacks, he has written two books, Reasoning about Uncertainty and Reasoning About Knowledge and is a winner of the 1997 Gödel Prize in theoretical computer science and the 2009 Dijkstra Prize in distributed computing. From 1997 to 2003 he was editor-in-chief of the Journal of the ACM. In 2002 he was inducted as a Fellow of the Association for Computing Machinery and in 2012 he was selected as an IEEE Fellow. In 2011 he was awarded a Senior Fellowship of the Zukunftskolleg at the University of Konstanz.. In 2019, he was elected to the National Academy of Engineering. Halpern is the administrator for the Computing Research Repository, the computer science branch of arXiv.org, the moderator for the "general literature" and "other" subsections of the repository.
His students include Nir Friedman, Daphne Koller, Yoram Moses. Joe Halpern's homepage Google scholar profile
Computer science is the study of processes that interact with data and that can be represented as data in the form of programs. It enables the use of algorithms to manipulate and communicate digital information. A computer scientist studies the theory of computation and the practice of designing software systems, its fields can be divided into practical disciplines. Computational complexity theory is abstract, while computer graphics emphasizes real-world applications. Programming language theory considers approaches to the description of computational processes, while computer programming itself involves the use of programming languages and complex systems. Human–computer interaction considers the challenges in making computers useful and accessible; the earliest foundations of what would become computer science predate the invention of the modern digital computer. Machines for calculating fixed numerical tasks such as the abacus have existed since antiquity, aiding in computations such as multiplication and division.
Algorithms for performing computations have existed since antiquity before the development of sophisticated computing equipment. Wilhelm Schickard designed and constructed the first working mechanical calculator in 1623. In 1673, Gottfried Leibniz demonstrated a digital mechanical calculator, called the Stepped Reckoner, he may be considered the first computer scientist and information theorist, among other reasons, documenting the binary number system. In 1820, Thomas de Colmar launched the mechanical calculator industry when he released his simplified arithmometer, the first calculating machine strong enough and reliable enough to be used daily in an office environment. Charles Babbage started the design of the first automatic mechanical calculator, his Difference Engine, in 1822, which gave him the idea of the first programmable mechanical calculator, his Analytical Engine, he started developing this machine in 1834, "in less than two years, he had sketched out many of the salient features of the modern computer".
"A crucial step was the adoption of a punched card system derived from the Jacquard loom" making it infinitely programmable. In 1843, during the translation of a French article on the Analytical Engine, Ada Lovelace wrote, in one of the many notes she included, an algorithm to compute the Bernoulli numbers, considered to be the first computer program. Around 1885, Herman Hollerith invented the tabulator, which used punched cards to process statistical information. In 1937, one hundred years after Babbage's impossible dream, Howard Aiken convinced IBM, making all kinds of punched card equipment and was in the calculator business to develop his giant programmable calculator, the ASCC/Harvard Mark I, based on Babbage's Analytical Engine, which itself used cards and a central computing unit; when the machine was finished, some hailed it as "Babbage's dream come true". During the 1940s, as new and more powerful computing machines were developed, the term computer came to refer to the machines rather than their human predecessors.
As it became clear that computers could be used for more than just mathematical calculations, the field of computer science broadened to study computation in general. In 1945, IBM founded the Watson Scientific Computing Laboratory at Columbia University in New York City; the renovated fraternity house on Manhattan's West Side was IBM's first laboratory devoted to pure science. The lab is the forerunner of IBM's Research Division, which today operates research facilities around the world; the close relationship between IBM and the university was instrumental in the emergence of a new scientific discipline, with Columbia offering one of the first academic-credit courses in computer science in 1946. Computer science began to be established as a distinct academic discipline in the 1950s and early 1960s; the world's first computer science degree program, the Cambridge Diploma in Computer Science, began at the University of Cambridge Computer Laboratory in 1953. The first computer science degree program in the United States was formed at Purdue University in 1962.
Since practical computers became available, many applications of computing have become distinct areas of study in their own rights. Although many believed it was impossible that computers themselves could be a scientific field of study, in the late fifties it became accepted among the greater academic population, it is the now well-known IBM brand that formed part of the computer science revolution during this time. IBM released the IBM 704 and the IBM 709 computers, which were used during the exploration period of such devices. "Still, working with the IBM was frustrating if you had misplaced as much as one letter in one instruction, the program would crash, you would have to start the whole process over again". During the late 1950s, the computer science discipline was much in its developmental stages, such issues were commonplace. Time has seen significant improvements in the effectiveness of computing technology. Modern society has seen a significant shift in the users of computer technology, from usage only by experts and professionals, to a near-ubiquitous user base.
Computers were quite costly, some degree of humanitarian aid was needed for efficient use—in part from professional computer operators. As computer adoption became more widespread and affordable, less human assistance was needed for common usage. Despite its short history as a formal academic discipline, computer science has made a number of fundamental contributions to science and society—in fact, along with electronics, it is
Silvio Micali is an Italian computer scientist at MIT Computer Science and Artificial Intelligence Laboratory and a professor of computer science in's Department of Electrical Engineering and Computer Science since 1983. His research centers on the theory of information security. Silvio Micali won Turing Award together with Shafi Goldwasser in 2012. Silvio Micali has been on the faculty at MIT, Electrical Engineering and Computer Science Department, since 1983. Silvio’s research interests are cryptography, zero knowledge, pseudorandom generation, secure protocols, mechanism design. In 2017, Silvio founded Algorand, a decentralized and scalable blockchain which provides a common platform for building products and services for a decentralized economy. At Algorand, Silvio oversees all research, including theory and crypto finance. Silvio is the recipient of the Goedel Prize and the RSA prize, he is a member of the National Academy of Sciences, the National Academy of Engineering, the American Academy of Arts and Sciences.
Micali graduated in mathematics at La Sapienza University of Rome in 1978 and earned a Ph. D. degree in computer science from the University of California, Berkeley in 1982. Micali is best known for some of his fundamental early work on public-key cryptosystems, pseudorandom functions, digital signatures, oblivious transfer, secure multiparty computation, is one of the co-inventors of zero-knowledge proofs, his former doctoral students include Mihir Bellare, Bonnie Berger, Rafail Ostrovsky, Phillip Rogaway. Micali won the Gödel Prize in 1993. In 2007, he was selected to be a member of the National Academy of Sciences and a Fellow of the International Association for Cryptologic Research, he is a member of the National Academy of Engineering and the American Academy of Arts and Sciences. He received the Turing Award for the year 2012 along with Shafi Goldwasser for their work in the field of cryptography. In 2015 the University of Salerno acknowledges his studies giving him an honoris causa degree in Computer Science.
He was elected as an ACM Fellow in 2017
David Bernard Shmoys is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph. D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems. In particular, his work has highlighted the role of linear programming in the design of approximation algorithms for NP-hard problems, he is known for his pioneering research on providing first constant factor performance guarantee for several scheduling and clustering problems including the k-center and k-median problems and the generalized assignment problem. Polynomial-time approximation schemes that he developed for scheduling problems have found applications in many subsequent works, his current research includes stochastic optimization, computational sustainability and optimization techniques in computational biology. Shmoys is married to Éva Tardos, the Jacob Gould Schurman Professor of Computer Science at Cornell University.
Two of his key contributions are Constant factor approximation algorithm for the Generalized Assignment Problem and Unrelated Parallel Machine Scheduling. Constant factor approximation algorithm for k-Medians and Facility location problem; these contributions are described below: The paper is a joint work by David Shmoys and Eva Tardos. The generalized assignment problem can be viewed as the following problem of scheduling unrelated parallel machine with costs; each of n independent jobs have to be processed by one of m unrelated parallel machines. Unrelated implies. Job j takes p i, j time units when processed by machine i and incurs a cost c i, j, i = 1, 2.. M. N. Given C and T i, i = 1, 2.. M, we wish to decide if there exists a schedule with total cost at most C such that for each machine i its load, the total processing time required for the jobs assigned to it is at most T i, i = 1, 2.. M. By scaling the processing times, we can assume, without loss of generality, that the machine load bounds satisfy T 1 = T 2 =..
= T m = T. ``In other words, generalized assignment problem is to find a schedule of minimum cost subject to the constraint that the makespan, that the maximum machine load is at most T ". The work of Shmoys with Lenstra and Tardos cited here gives a 2 approximation algorithm for the unit cost case; the algorithm is based on a clever design of linear program using parametric pruning and rounding an extreme point solution of the linear program deterministically. Algorithm for the generalized assignment problem is based on a similar LP through parametric pruning and using a new rounding technique on a designed bipartite graph. We now state the LP formulation and describe the rounding technique. We guess the optimum value of makespan T and write the following LP; this technique is known as parametric pruning. L P:: ∑ i = 1 m ∑ j = 1 n c i j x i j ≤ C.
Sanjeev Arora is an Indian American theoretical computer scientist, best known for his work on probabilistically checkable proofs and, in particular, the PCP theorem. He is the Charles C. Fitzmorris Professor of Computer Science at Princeton University, his research interests include computational complexity theory, uses of randomness in computation, probabilistically checkable proofs, computing approximate solutions to NP-hard problems, geometric embeddings of metric spaces, he received a B. S. in Mathematics with Computer Science from MIT in 1990 and received a Ph. D. in Computer Science from the University of California, Berkeley in 1994 under Umesh Vazirani. Earlier, in 1986, Sanjeev Arora had topped the prestigious IIT JEE but transferred to MIT after 2 years at IIT Kanpur, he was a visiting scholar at the Institute for Advanced Study in 2002-03. He was awarded the Gödel Prize for his work on the PCP theorem in 2001 and again in 2010 for the discovery of a polynomial time approximation scheme for the Euclidean travelling salesman problem.
In 2008 he was inducted as a Fellow of the Association for Computing Machinery. In 2011 he was awarded the ACM Infosys Foundation Award, given to mid-career researchers in Computer Science. Arora has been awarded the Fulkerson Prize for 2012 for his work on improving the approximation ratio for graph separators and related problems. In 2012 he became a Simons Investigator. Arora was elected to the National Academy of Sciences on May 2, 2018, he is a coauthor of the book Computational Complexity: A Modern Approach and is a founder, on the Executive Board, of Princeton's Center for Computational Intractability. He and his coauthors have argued that certain financial products are associated with computational asymmetry which under certain conditions may lead to market instability. Sanjeev Arora's Homepage Sanjeev Arora at the Mathematics Genealogy Project