Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation and are the interplay of randomness and computation, the foundations of cryptography, computational complexity theory, he won the Knuth Prize in 2017. Goldreich has contributed to the development of pseudorandomness,zero knowledge proofs, secure function evaluation, property testing, other areas in cryptography and computational complexity. Goldreich has authored several books including: Foundations of Cryptography which comes in two volumes, Computational Complexity: A Conceptual Perspective, Modern Cryptography, Probabilistic Proofs and Pseudorandomness, he is married to Dana Ron, a computer scientist at Tel Aviv University, has collaborated with Ron on approximation algorithms. Science and technology in Israel Home page of Oded Goldreich Oded Goldreich at the Mathematics Genealogy Project Interview with Oded Goldreich
Computational complexity theory
Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used; the theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying their computational complexity, i.e. the amount of resources needed to solve them, such as time and storage. Other measures of complexity are used, such as the amount of communication, the number of gates in a circuit and the number of processors. One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do; the P versus NP problem, one of the seven Millennium Prize Problems, is dedicated to the field of computational complexity.
Related fields in theoretical computer science are analysis of algorithms and computability theory. A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem. More computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources. In turn, imposing restrictions on the available resources is what distinguishes computational complexity from computability theory: the latter theory asks what kind of problems can, in principle, be solved algorithmically. A computational problem can be viewed as an infinite collection of instances together with a solution for every instance; the input string for a computational problem is referred to as a problem instance, should not be confused with the problem itself.
In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing; the instance is a number and the solution is "yes" if the number is prime and "no" otherwise. Stated another way, the instance is a particular input to the problem, the solution is the output corresponding to the given input. To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometres passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.
When considering computational problems, a problem instance is a string over an alphabet. The alphabet is taken to be the binary alphabet, thus the strings are bitstrings; as in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, graphs can be encoded directly via their adjacency matrices, or by encoding their adjacency lists in binary. Though some proofs of complexity-theoretic theorems assume some concrete choice of input encoding, one tries to keep the discussion abstract enough to be independent of the choice of encoding; this can be achieved by ensuring that different representations can be transformed into each other efficiently. Decision problems are one of the central objects of study in computational complexity theory. A decision problem is a special type of computational problem whose answer is either yes or no, or alternately either 1 or 0. A decision problem can be viewed as a formal language, where the members of the language are instances whose output is yes, the non-members are those instances whose output is no.
The objective is to decide, with the aid of an algorithm, whether a given input string is a member of the formal language under consideration. If the algorithm deciding this problem returns the answer yes, the algorithm is said to accept the input string, otherwise it is said to reject the input. An example of a decision problem is the following; the input is an arbitrary graph. The problem consists in deciding; the formal language associated with this decision problem is the set of all connected graphs — to obtain a precise definition of this language, one has to decide how graphs are encoded as binary strings. A function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem—that is, the output isn't just yes or no. Notable examples include the integer factorization problem, it is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not the case, since function problems can be recast as decision problems.
For example, the multiplication of two integers can be expressed as the set of triples such that the relation a × b = c holds. Deciding whether a given triple is a member of this set corresponds to solving
Cambridge University Press
Cambridge University Press is the publishing business of the University of Cambridge. Granted letters patent by King Henry VIII in 1534, it is the world's oldest publishing house and the second-largest university press in the world, it holds letters patent as the Queen's Printer. The press mission is "to further the University's mission by disseminating knowledge in the pursuit of education and research at the highest international levels of excellence". Cambridge University Press is a department of the University of Cambridge and is both an academic and educational publisher. With a global sales presence, publishing hubs, offices in more than 40 countries, it publishes over 50,000 titles by authors from over 100 countries, its publishing includes academic journals, reference works and English language teaching and learning publications. Cambridge University Press is a charitable enterprise that transfers part of its annual surplus back to the university. Cambridge University Press is both the oldest publishing house in the world and the oldest university press.
It originated from letters patent granted to the University of Cambridge by Henry VIII in 1534, has been producing books continuously since the first University Press book was printed. Cambridge is one of the two privileged presses. Authors published by Cambridge have included John Milton, William Harvey, Isaac Newton, Bertrand Russell, Stephen Hawking. University printing began in Cambridge when the first practising University Printer, Thomas Thomas, set up a printing house on the site of what became the Senate House lawn – a few yards from where the press's bookshop now stands. In those days, the Stationers' Company in London jealously guarded its monopoly of printing, which explains the delay between the date of the university's letters patent and the printing of the first book. In 1591, Thomas's successor, John Legate, printed the first Cambridge Bible, an octavo edition of the popular Geneva Bible; the London Stationers objected strenuously. The university's response was to point out the provision in its charter to print "all manner of books".
Thus began the press's tradition of publishing the Bible, a tradition that has endured for over four centuries, beginning with the Geneva Bible, continuing with the Authorized Version, the Revised Version, the New English Bible and the Revised English Bible. The restrictions and compromises forced upon Cambridge by the dispute with the London Stationers did not come to an end until the scholar Richard Bentley was given the power to set up a'new-style press' in 1696. In July 1697 the Duke of Somerset made a loan of £200 to the university "towards the printing house and presse" and James Halman, Registrary of the University, lent £100 for the same purpose, it was in Bentley's time, in 1698, that a body of senior scholars was appointed to be responsible to the university for the press's affairs. The Press Syndicate's publishing committee still meets and its role still includes the review and approval of the press's planned output. John Baskerville became University Printer in the mid-eighteenth century.
Baskerville's concern was the production of the finest possible books using his own type-design and printing techniques. Baskerville wrote, "The importance of the work demands all my attention. Caxton would have found nothing to surprise him if he had walked into the press's printing house in the eighteenth century: all the type was still being set by hand. A technological breakthrough was badly needed, it came when Lord Stanhope perfected the making of stereotype plates; this involved making a mould of the whole surface of a page of type and casting plates from that mould. The press was the first to use this technique, in 1805 produced the technically successful and much-reprinted Cambridge Stereotype Bible. By the 1850s the press was using steam-powered machine presses, employing two to three hundred people, occupying several buildings in the Silver Street and Mill Lane area, including the one that the press still occupies, the Pitt Building, built for the press and in honour of William Pitt the Younger.
Under the stewardship of C. J. Clay, University Printer from 1854 to 1882, the press increased the size and scale of its academic and educational publishing operation. An important factor in this increase was the inauguration of its list of schoolbooks. During Clay's administration, the press undertook a sizeable co-publishing venture with Oxford: the Revised Version of the Bible, begun in 1870 and completed in 1885, it was in this period as well that the Syndics of the press turned down what became the Oxford English Dictionary—a proposal for, brought to Cambridge by James Murray before he turned to Oxford. The appointment of R. T. Wright as Secretary of the Press Syndicate in 1892 marked the beginning of the press's development as a modern publishing business with a defined editorial policy and administrative structure, it was Wright who devised the plan for one of the most distinctive Cambridge contributions to publishing—the Cambridge Histories. The Cambridge Modern History was published
In computational complexity theory, CC is the complexity class containing decision problems which can be solved by comparator circuits of polynomial size. Comparator circuits are sorting networks in which each comparator gate is directed, each wire is initialized with an input variable, its negation, or a constant, one of the wires is distinguished as the output wire; the most important problem, complete for CC is a decision variant of the stable marriage problem. A comparator circuit is a network of gates; each comparator gate, a directed edge connecting two wires, takes its two inputs and outputs them in sorted order. The input to any wire can be its negation, or a constant. One of the wires is designated as the output wire; the function computed by the circuit is evaluated by initializing the wires according to the input variables, executing the comparator gates in order, outputting the value carried by the output wire. The comparator circuit value problem is the problem of evaluating a comparator circuit given an encoding of the circuit and the input to the circuit.
The complexity class CC is defined as the class of problems logspace reducible to CCVP. An equivalent definition is the class of problems AC0 reducible to CCVP; as an example, a sorting network can be used to compute majority by designating the middle wire as an output wire: If the middle wire is designated as output, the wires are annotated with 16 different input variables the resulting comparator circuit computes majority. Since there are sorting networks which can be constructed in AC0, this shows that the majority function is in CC. A problem in CC is CC-complete if every problem in CC can be reduced to it using a logspace reduction; the comparator circuit value problem is CC-complete. In the stable marriage problem, there is an equal number of women; each person ranks all members of the opposite sex. A matching between men and women is stable if there are no unpaired man and woman who prefer each other over their current partners. A stable matching always exists. Among the stable matchings, there is one in which each woman gets the best man that she gets in any stable matching.
The decision version of the stable matching problem is, given the rankings of all men and women, whether a given man and a given woman are matched in the woman-optimal stable matching. Although the classical Gale–Shapley algorithm cannot be implemented as a comparator circuit, Subramanian came up with a different algorithm showing that the problem is in CC; the problem is CC-complete. Another problem, CC-complete is lexicographically-first maximal matching. In this problem, we are given a bipartite graph with an order on the vertices, an edge; the lexicographically-first maximal matching is obtained by successively matching vertices from the first bipartition to the minimal available vertices from the second bipartition. The problem asks. Scott Aaronson showed. In this problem, we are given a starting number of pebbles and a description of a program which may contain only two types of instructions: combine two piles of sizes y and z to get a new pile of size y + z, or split a pile of size y into piles of size ⌈ y / 2 ⌉ and ⌊ y / 2 ⌋.
The problem is to decide whether any pebbles are present in a particular pile after executing the program. He used this to show that the problem of deciding whether any balls reach a designated sink vertex in a Digi-Comp II-like device is CC-complete; the comparator circuit evaluation problem can be solved in polynomial time, so CC is contained in P. On the other hand, comparator circuits can solve directed reachability, so CC contains NL. There is a relativized world in which CC and NC are incomparable, so both containments are strict. Complexity Zoo: CC