# Andrew Yao

#3,312

Most Influential Person Now

Computer scientist and computational theorist

## Andrew Yao's AcademicInfluence.com Rankings

Andrew Yaocomputer-science Degrees

Computer Science

#501

World Rank

#520

Historical Rank

Database

#293

World Rank

#307

Historical Rank

## Download Badge

Computer Science

## Andrew Yao's Degrees

- Bachelors Physics National Taiwan University

## Why Is Andrew Yao Influential?

(Suggest an Edit or Addition)According to Wikipedia, Andrew Chi-Chih Yao is a Chinese computer scientist and computational theorist. He is currently a professor and the dean of Institute for Interdisciplinary Information Sciences at Tsinghua University. Yao used the minimax theorem to prove what is now known as Yao's Principle.

## Andrew Yao's Published Works

### Published Works

- On the security of public key protocols (1983) (5114)
- Protocols for secure computations (1982) (3721)
- How to generate and exchange secrets (1986) (2514)
- How to Generate and Exchange Secrets (Extended Abstract) (1986) (1512)
- Some complexity questions related to distributive computing(Preliminary Report) (1979) (1243)
- Theory and application of trapdoor functions (1982) (1083)
- Probabilistic computations: Toward a unified measure of complexity (1977) (1079)
- Protocols for Secure Computations (Extended Abstract) (1982) (1003)
- Theory and Applications of Trapdoor Functions (Extended Abstract) (1982) (814)
- Quantum Circuit Complexity (1993) (732)
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems (1977) (635)
- Quantum cryptography with imperfect apparatus (1998) (409)
- Separating the polynomial-time hierarchy by oracles (1985) (409)
- Should tables be sorted? (1981) (354)
- Optimal Expected-Time Algorithms for Closest Point Problems (1980) (343)
- Resource Constrained Scheduling as Generalized Bin Packing (1976) (340)
- Self testing quantum apparatus (2003) (322)
- The complexity of nonuniform random number generation (1976) (314)
- An Almost Optimal Algorithm for Unbounded Searching (1976) (307)
- New Algorithms for Bin Packing (1978) (302)
- Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version) (1985) (291)
- Informational complexity and the direct sum problem for simultaneous message complexity (2001) (259)
- Storing a sparse table (1979) (241)
- ON ACC and threshold circuits (1990) (230)
- Lower bounds by probabilistic arguments (1983) (220)
- A Lower Bound to Finding Convex Hulls (1981) (167)
- Lower Bounds for Algebraic Decision Trees (1982) (166)
- The Complexity of Pattern Matching for a Random String (1977) (164)
- A general approach to d-dimensional geometric queries (1985) (164)
- An O(|E| log log |V|) Algorithm for Finding Minimum Spanning Trees (1975) (155)
- On the Evaluation of Powers (1976) (153)
- Scaling Nakamoto Consensus to Thousands of Transactions per Second (2018) (151)
- On the Security of Public Key Protocols (Extended Abstract) (1981) (150)
- Security of quantum protocols against coherent measurements (1995) (142)
- An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications (2014) (133)
- Quantum bit escrow (2000) (122)
- On revenue maximization for selling multiple independently distributed items (2013) (121)
- Linear decision trees: volume estimates and topological bounds (1992) (119)
- K + 1 heads are better than K (1976) (118)
- Space-time tradeoff for answering range queries (Extended Abstract) (1982) (111)
- A Stochastic Model of Bin-Packing (1980) (103)
- On the Complexity of Maintaining Partial Sums (1985) (98)
- Lower bounds for algebraic computation trees with integer inputs (1989) (97)
- Decision tree complexity and Betti numbers (1994) (88)
- On random 2–3 trees (1978) (82)
- The entropic limitations on VLSI computations(Extended Abstract) (1981) (79)
- Coherent functions and program checkers (1990) (76)
- Classical physics and the Church--Turing Thesis (2003) (73)
- Discrete and continuous min-energy schedules for variable voltage processors (2006) (71)
- Near-optimal time-space tradeoff for element distinctness (1988) (68)
- The complexity of searching an ordered random table (1976) (65)
- On Fault-Tolerant Networks for Sorting (1979) (64)
- The Complexity of Finding Cycles in Periodic Functions (1982) (63)
- RAPID: randomized pharmacophore identification for drug design (1997) (62)
- Circuits and local computation (1989) (60)
- Analysis of the subtractive algorithm for greatest common divisors (1975) (59)
- Monotone Bipartite Graph Properties are Evasive (1988) (58)
- Towards uncheatable benchmarks (1993) (57)
- A Decentralized Blockchain with High Throughput and Fast Confirmation (2020) (56)
- Strong signature schemes (1983) (55)
- On the power of quantum fingerprinting (2003) (53)
- Rearrangeable Networks with Limited Depth (1982) (50)
- OAKE: a new family of implicitly authenticated diffie-hellman protocols (2013) (49)
- Algebraic Decision Trees and Euler Characteristics (1992) (45)
- Lower bounds to randomized algorithms for graph properties (1987) (45)
- Information Bounds Are Weak in the Shortest Distance Problem (1980) (44)
- Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus (1997) (43)
- On the Polyhedral Decision Problem (1980) (42)
- Lower Bounds by Probabilistic Arguments (Extended Abstract) (1983) (40)
- Some Monotonicity Properties of Partial Orders (1979) (38)
- Dictionary Look-Up with One Error (1997) (37)
- On the average behavior of set merging algorithms (Extended Abstract) (1976) (36)
- A Note on the Analysis of Extendible Hashing (1980) (36)
- NQPC = co-C=P (1999) (35)
- Uniform hashing is optimal (1985) (34)
- Deniable Internet Key Exchange (2010) (34)
- Efficient Searching Using Partial Ordering (1981) (34)
- Privacy-Preserving Authenticated Key-Exchange Over Internet (2014) (33)
- Online/Offline Signatures for Low-Power Devices (2013) (33)
- Quantum replication at the Heisenberg limit (2013) (33)
- Dominant-Strategy versus Bayesian Multi-item Auctions: Maximum Revenue Determination and Comparison (2017) (32)
- On the complexity of comparison problems using linear functions (1975) (31)
- Fisher Equilibrium Price with a Class of Concave Utility Functions (2004) (30)
- Bounds on Selection Networks (1974) (30)
- Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems (2007) (29)
- An Analysis of a Memory Allocation Scheme for Implementing Stacks (1981) (28)
- An Incentive Analysis of some Bitcoin Fee Designs (2018) (25)
- Graph properties and circular functions: how low can quantum query complexity go? (2004) (25)
- On the parallel computation for the knapsack problem (1981) (23)
- A Circuit-Based Proof of Toda's Theorem (1993) (23)
- An Analysis of (h, k, 1)-Shellsort (1979) (22)
- Lower Bounds on Merging Networks (1974) (21)
- Coherent Functions and Program Checkers (Extended Abstract) (1990) (21)
- On the improbability of reaching Byzantine agreements (1989) (21)
- A lower bound for the monotone depth of connectivity (1994) (19)
- On Evaluating Boolean Functions with Unreliable Tests (1990) (19)
- FedCM: Federated Learning with Client-level Momentum (2021) (18)
- On the Expected Performance of Path Compression Algorithms (1985) (17)
- Oblivious and Adaptive Strategies for the Majority and Plurality Problems (2005) (17)
- On Parallel Computation for the Knapsack Problem (1982) (15)
- A lower bound to palindrome recognition by probabilistic Turing machines (1977) (15)
- An exponential lower bound on the size of algebraic decision trees for Max (1998) (13)
- On the Quantum Query Complexity of Local Search in Two and Three Dimensions (2006) (13)
- Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem (2008) (13)
- Dictionary Loop-Up with Small Errors (1995) (13)
- On the Shrinkage Exponent for Read-Once Formulae (1995) (13)
- Addition chains with multiplicative cost (1978) (12)
- Graph Coloring Applied to Secure Computation in Non-Abelian Groups (2012) (12)
- On the Time-Space Tradeoff for Sorting with Linear Queries (1979) (11)
- Interactive Proofs for Quantum Computation (2003) (11)
- Scheduling Unit-Time Tasks with Limited Resources (1974) (11)
- A note on universal composable zero-knowledge in the common reference string model (2007) (11)
- Computational information theory (1988) (10)
- External Hashing Schemes for Collections of Data Structures (1980) (10)
- On a problem of Katona on minimal separating systems (1976) (9)
- Divergences of Massive Yang-Mills Theories: Higher Groups (1971) (9)
- On the Complexity of Partial Order Productions (1989) (9)
- Adaptive Concurrent Non-Malleability with Bare Public-Keys (2009) (8)
- An Ω(n2 log n) lower bound to the shortest paths problem (1977) (8)
- A Randomized Algorithm for Finding Maximum with O((log n)²) Polynomial Tests (1994) (7)
- Program Checkers for Probability Generation (1991) (7)
- On computing the minima of quadratic forms (Preliminary Report) (1975) (7)
- On the average-case complexity of selecting k-th best (1978) (7)
- On the Average-Case Complexity of Selecting the kth Best (1982) (7)
- On Computing Algebraic Functions Using Logarithms and Exponentials (1995) (6)
- On the Loop Switching Addressing Problem (1978) (6)
- Graph entropy and quantum sorting problems (2004) (6)
- Concurrent Knowledge Extraction in the Public-Key Model (2009) (6)
- Standing pion waves in superdense matter (1973) (5)
- A New Family of Practical Non-Malleable Protocols (2011) (5)
- Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus (2002) (5)
- Concurrent Knowledge Extraction in Public-Key Models (2010) (5)
- On the Improbability of Reaching Byzantine Agreements (Preliminary Version) (1989) (5)
- On Solutions for the Maximum Revenue Multi-item Auction under Dominant-Strategy and Bayesian Implementations (2016) (5)
- A Note on the Feasibility of Generalized Universal Composability (2007) (5)
- On Revenue Monotonicity in Combinatorial Auctions (2017) (5)
- A note on the feasibility of generalised universal composability† (2009) (5)
- Context-Free Grammars and Random Number Generation (1985) (5)
- Should Tables Be Sorted? (Extended Abstract) (1978) (4)
- Digital Signatures from Challenge-Divided Sigma-Protocols (2012) (4)
- A Note on a Conjecture of Kam and Ullman Concerning Statistical Databases (1979) (4)
- Graph Design for Secure Multiparty Computation over Non-Abelian Groups (2008) (4)
- On Signatures and Authentication (1982) (4)
- Dynamic Price Sequence and Incentive Compatibility (Extended Abstract) (2004) (4)
- Finding Favorites (2003) (4)
- NQP_{C} = co-C_{=}P (1998) (4)
- New quantum algorithms and quantum lower bounds (2006) (3)
- On Optimal Arrangements of Keys with Double Hashing (1985) (3)
- Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings (2010) (3)
- On selecting thek largest with median tests (1989) (2)
- Computationally-Fair Group and Identity-Based Key-Exchange (2012) (2)
- Communication Complexity and Its Applications (2009) (2)
- A New Family of Practical Non-Malleable Diffie-Hellman Protocols (2011) (2)
- A Comparative Study of Available Protocols during Privacy Preservation in Secure Multiparty Computation (2011) (2)
- A Note on Universal Composable Zero Knowledge in Common Reference String Model (2007) (2)
- NQP = co-C = P (1998) (1)
- Concurrent Knowledge Extraction in Public-Key Models (2014) (1)
- NQP = co-C=P (1998) (1)
- A study of concrete computational complexity. (1975) (1)
- Some perspectives on computational complexity (2001) (1)
- Relaxing the Feature Covariance Assumption: Time-Variant Bounds for Benign Overfitting in Linear Regression (2022) (1)
- When do Models Generalize? A Perspective from Data-Algorithm Compatibility (2022) (1)
- Should Tables Be Sorted? Should Tables Be Sorted? * (1979) (1)
- Fast, accurate, and secure DNA synthesis screening with random adversarial thresholds (1)
- Groups and Algebraic Complexity (Abstract) (1993) (0)
- A fundamental quantity which arises in the sorting of n numbers app * * (0)
- Some Perspectives on Complexity-Based Cryptography (2008) (0)
- Minimean optimal key arrangements in hash tables (1995) (0)
- SYMMETRY EFFECTS IN COMPUTATION (2008) (0)
- Proceedings Twenty-Second Annual IEEE Conference on Computational Complexity: Preface (2007) (0)
- An authenticated and secure accounting system for international emissions trading (2020) (0)
- Digital Signatures from Challenge-Divided Σ-Protocols (2012) (0)
- AN ALMOST OPTIMAL ALGORTTHM FOR UNBOUNDED SIZARCHING (1975) (0)
- On the Power of Quantum Fingerprinting 1 (0)
- Recent Progress in Circuit and Communication Complexity (Abstract) (1991) (0)
- Hypergraphs and Decision Trees (Abstract) (1996) (0)
- The Turing Computational Model (2012) (0)
- An Analysis of (h,k,l) -shellsort By (1998) (0)
- A Lower Bound on the Size of Algebraic Decision Trees for the MAX Problem (1995) (0)
- Some perspectives on computational and communication complexity (2006) (0)
- Weighted Random Assignments with Application to Hashing (1991) (0)
- On the Communication Complexity of Co-linearity Problems (2005) (0)
- A an Alternative Private Protocol (1996) (0)
- A SURVEY ON NEW CRYPTOGRAPHIC SYSTEM TECHNIQUES FOR DATA SHARING IN CLOUD STORAGE (2014) (0)
- Interdisciplinarity: A View from Theory of Computation (2015) (0)
- Theoretical foundations of the “ x 2 mod N ” generator (2004) (0)
- Multiparty Communication Complexity of Regular Languages (2007) (0)
- Quantum Computing: A Great Science in the Making (2012) (0)
- Recent Progress in Quantum Computational Complexity (2006) (0)
- Preliminary Version - to Be Improved Soon (2007) (0)
- Some perspective on computational complexity (abstract). (2001) (0)
- Khachian's Algorithm Modified (1979) (0)

This paper list is powered by the following services:

## Other Resources About Andrew Yao

## What Schools Are Affiliated With Andrew Yao?

Andrew Yao is affiliated with the following schools: