Andrew Yao

Q: What Schools Are Affiliated With Andrew Yao

Andrew Yao is affiliated with the following schools: University of California, Berkeley, University of California, San Diego, Tsinghua University, Princeton University, Stanford University, University of Illinois Urbana-Champaign, National Taiwan University, Peking University, Harvard University

Andrew Yao's AcademicInfluence.com Rankings

Andrew Yao

Computer Science

#501

World Rank

#520

Historical Rank

Database

#293

World Rank

#307

Historical Rank

computer-science Degrees

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.

(See a Problem?)

Andrew Yao's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

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:

Andrew Yao's Academic­Influence.com Rankings