Andrew Chi-Chih Yao
According to our database1, Andrew Chi-Chih Yao
Awards
Turing Prize recipient
Turing Prize 2000, "In recognition of his fundamental contributions to the theory of computation, including the complexity-based theory of pseudorandom number generator|pseudorandom number generation, cryptography, and communication complexity.".
ACM Fellow
ACM Fellow 1995, "For significant research contributions in Computational Complexity, Analysis of Algorithms, Data Structures, Communication Complexity, and Cryptographic Protocols.".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:
-
at viaf.org
-
at isni.org
-
at id.loc.gov
-
at dl.acm.org
On csauthors.net:
Bibliography
2017
On Revenue Monotonicity in Combinatorial Auctions.
CoRR, 2017
Dominant-Strategy versus Bayesian Multi-item Auctions: Maximum Revenue Determination and Comparison.
Proceedings of the 2017 ACM Conference on Economics and Computation, 2017
2016
Concurrent Knowledge Extraction in Public-Key Models.
J. Cryptology, 2016
On Solutions for the Maximum Revenue Multi-item Auction under Dominant-Strategy and Bayesian Implementations.
CoRR, 2016
2015
An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015
Interdisciplinarity: A View from Theory of Computation.
Proceedings of the Federated Computing Research Conference, 2015
2014
Privacy-Preserving Authenticated Key-Exchange Over Internet.
IEEE Trans. Information Forensics and Security, 2014
An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications.
CoRR, 2014
2013
Online/Offline Signatures for Low-Power Devices.
IEEE Trans. Information Forensics and Security, 2013
OAKE: a new family of implicitly authenticated diffie-hellman protocols.
Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security, 2013
2012
Graph Coloring Applied to Secure Computation in Non-Abelian Groups.
J. Cryptology, 2012
Computationally-Fair Group and Identity-Based Key-Exchange.
IACR Cryptology ePrint Archive, 2012
Digital Signatures from Challenge-Divided Sigma-Protocols.
IACR Cryptology ePrint Archive, 2012
Computationally-Fair Group and Identity-Based Key-Exchange.
Proceedings of the Theory and Applications of Models of Computation, 2012
Quantum Computing: A Great Science in the Making.
Proceedings of the Theory and Applications of Models of Computation, 2012
The Turing Computational Model.
Proceedings of the ACM Turing Centenary Celebration, 2012
2011
A New Family of Practical Non-Malleable Protocols.
IACR Cryptology ePrint Archive, 2011
A New Family of Practical Non-Malleable Diffie-Hellman Protocols
CoRR, 2011
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem.
Algorithmica, 2011
2010
Adaptive Concurrent Non-Malleability with Bare Public-Keys.
IACR Cryptology ePrint Archive, 2010
Concurrent Knowledge Extraction in the Public-Key Model.
IACR Cryptology ePrint Archive, 2010
A New Framework for RFID Privacy.
IACR Cryptology ePrint Archive, 2010
Concurrent Knowledge Extraction in the Public-Key Model.
Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010
Deniable Internet Key Exchange.
Proceedings of the Applied Cryptography and Network Security, 8th International Conference, 2010
2009
A note on universal composable zero-knowledge in the common reference string model.
Theor. Comput. Sci., 2009
A note on the feasibility of generalised universal composability.
Mathematical Structures in Computer Science, 2009
Adaptive Concurrent Non-Malleability with Bare Public-Keys
CoRR, 2009
Concurrent Knowledge-Extraction in the Public-Key Model
CoRR, 2009
On the Quantum Query Complexity of Local Search in Two and Three Dimensions.
Algorithmica, 2009
Communication Complexity and Its Applications.
Proceedings of the Frontiers in Algorithmics, Third International Workshop, 2009
2008
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem
CoRR, 2008
Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems.
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008
Some Perspectives on Complexity-Based Cryptography.
Proceedings of the Advances in Cryptology, 2008
Graph Design for Secure Multiparty Computation over Non-Abelian Groups.
Proceedings of the Advances in Cryptology, 2008
2007
Deniable Internet Key-Exchange.
IACR Cryptology ePrint Archive, 2007
Oblivious and Adaptive Strategies for the Majority and Plurality Problems.
Algorithmica, 2007
A Note on the Feasibility of Generalized Universal Composability.
Proceedings of the Theory and Applications of Models of Computation, 2007
A Note on Universal Composable Zero Knowledge in Common Reference String Model.
Proceedings of the Theory and Applications of Models of Computation, 2007
2006
Recent Progress in Quantum Computational Complexity.
Proceedings of the Theory and Applications of Models of Computation, 2006
On the Quantum Query Complexity of Local Search in Two and Three Dimensions.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
2005
On the Communication Complexity of Co-linearity Problems.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005
Oblivious and Adaptive Strategies for the Majority and Plurality Problems.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005
2004
Self testing quantum apparatus.
Quantum Information & Computation, 2004
Graph entropy and quantum sorting problems.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004
Dynamic Price Sequence and Incentive Compatibility (Extended Abstract).
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004
Fisher Equilibrium Price with a Class of Concave Utility Functions.
Proceedings of the Algorithms, 2004
Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go?
Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004
2003
Classical physics and the Church-Turing Thesis.
J. ACM, 2003
Finding Favorites
Electronic Colloquium on Computational Complexity (ECCC), 2003
On the power of quantum fingerprinting.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003
Interactive Proofs for Quantum Computation.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003
2002
On the Power of Quantum Fingerprinting
Electronic Colloquium on Computational Complexity (ECCC), 2002
Classical Physics and the Church-Turing Thesis
Electronic Colloquium on Computational Complexity (ECCC), 2002
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
Combinatorica, 2002
2001
Some perspective on computational complexity (abstract).
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
2000
Quantum bit escrow.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000
1999
NQPC = co-C=P.
Inf. Process. Lett., 1999
1998
NQP = co-C=P
Electronic Colloquium on Computational Complexity (ECCC), 1998
NQPC = co-C=P
CoRR, 1998
RAPID: Randomized pharmacophore identification for drug design.
Comput. Geom., 1998
An exponential lower bound on the size of algebraic decision trees for Max.
Computational Complexity, 1998
Quantum Cryptography with Imperfect Apparatus.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998
1997
Decision Tree Complexity and Betti Numbers.
J. Comput. Syst. Sci., 1997
Dictionary Look-Up with One Error.
J. Algorithms, 1997
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
RAPID: Randomized Pharmacophore Identification for Drug Design.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997
1996
Hypergraphs and Decision Trees (Abstract).
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1996
1995
Algebraic Decision Trees and Euler Characteristics.
Theor. Comput. Sci., 1995
On the Shrinkage Exponent for Read-Once Formulae.
Theor. Comput. Sci., 1995
On Computing Algebraic Functions Using Logarithms and Exponentials.
SIAM J. Comput., 1995
An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX
Electronic Colloquium on Computational Complexity (ECCC), 1995
Minimean Optimal Key Arrangements in Hash Tables.
Algorithmica, 1995
Security of quantum protocols against coherent measurements.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995
Dictionary Loop-Up with Small Errors.
CPM, 1995
1994
Near-Optimal Time-Space Tradeoff for Element Distinctness.
SIAM J. Comput., 1994
A Randomized Algorithm for Finding Maximum with O((log n)²) Polynomial Tests.
Inf. Process. Lett., 1994
Decision tree complexity and Betti numbers.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994
A Lower Bound for the Monotone Depth of Connectivity
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994
1993
A Circuit-Based Proof of Toda's Theorem
Inf. Comput., June, 1993
Groups and Algebraic Complexity (Abstract).
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993
Quantum Circuit Complexity
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993
Towards Uncheatable benchmarks.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993
1992
Linear Decision Trees: Volume Estimates and Topological Bounds
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992
Algebraic Decision Trees and Euler Characteristics
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
1991
Lower Bounds for Algebraic Computation Trees with Integer Inputs.
SIAM J. Comput., 1991
Lower Bounds to Randomized Algorithms for Graph Properties.
J. Comput. Syst. Sci., 1991
Weighted Random Assignments with Application to Hashing.
Proceedings of the ISA '91 Algorithms, 1991
Program Checkers for Probability Generation.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991
Recent Progress in Circuit and Communication Complexity (Abstract).
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991
1990
On Evaluating Boolean Functions with Unreliable Tests.
Int. J. Found. Comput. Sci., 1990
Coherent Functions and Program Checkers (Extended Abstract)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990
On ACC and Threshold Circuits
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
1989
On the Complexity of Partial Order Productions.
SIAM J. Comput., 1989
On Selecting the k Largest with Median Tests.
Algorithmica, 1989
Circuits and Local Computation
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
On the Improbability of Reaching Byzantine Agreements (Preliminary Version)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
Lower Bounds for Algebraic Computation Trees with Integer Inputs
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989
1988
Monotone Bipartite Graph Properties are Evasive.
SIAM J. Comput., 1988
Near-Optimal Time-Space Tradeoff for Element Distinctness
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988
1987
Lower Bounds to Randomized Algorithms for Graph Properties (Extended Abstract)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987
1986
How to Generate and Exchange Secrets (Extended Abstract)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986
1985
Uniform Hashing Is Optimal
J. ACM, July, 1985
On Fault-Tolerant Networks for Sorting.
SIAM J. Comput., 1985
On the Complexity of Maintaining Partial Sums.
SIAM J. Comput., 1985
On the Expected Performance of Path Compression Algorithms.
SIAM J. Comput., 1985
On Optimal Arrangements of Keys with Double Hashing.
J. Algorithms, 1985
A General Approach to d-Dimensional Geometric Queries (Extended Abstract)
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
1983
On the security of public key protocols.
IEEE Trans. Information Theory, 1983
Strong Signature Schemes
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983
Lower Bounds by Probabilistic Arguments (Extended Abstract)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
1982
On the Time-Space Tradeoff for Sorting with Linear Queries.
Theor. Comput. Sci., 1982
On the Average-Case Complexity of Selecting the kth Best.
SIAM J. Comput., 1982
On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems.
SIAM J. Comput., 1982
The Complexity of Finding Cycles in Periodic Functions.
SIAM J. Comput., 1982
Lower Bounds for Algebraic Decision Trees.
J. Algorithms, 1982
On Parallel Computation for the Knapsack Problem.
J. ACM, 1982
Space-Time Tradeoff for Answering Range Queries (Extended Abstract)
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982
Protocols for Secure Computations (Extended Abstract)
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982
Theory and Applications of Trapdoor Functions (Extended Abstract)
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982
On Signatures and Authentication.
Proceedings of the Advances in Cryptology: Proceedings of CRYPTO '82, 1982
1981
An Analysis of a Memory Allocation Scheme for Implementing Stacks.
SIAM J. Comput., 1981
A Lower Bound to Finding Convex Hulls.
J. ACM, 1981
Should Tables Be Sorted?
J. ACM, 1981
Efficient Searching Using Partial Ordering.
Inf. Process. Lett., 1981
The Entropic Limitations on VLSI Computations (Extended Abstract)
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981
On the Parallel Computation for the Knapsack Problem
Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981
On the Security of Public Key Protocols (Extended Abstract)
Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981
1980
A Stochastic Model of Bin-Packing
Information and Control, February, 1980
Optimal Expected-Time Algorithms for Closest Point Problems.
ACM Trans. Math. Softw., 1980
Some Monotonicity Properties of Partial Orders.
SIAM J. Matrix Analysis Applications, 1980
On the Polyhedral Decision Problem.
SIAM J. Comput., 1980
Bounds on Selection Networks.
SIAM J. Comput., 1980
An Analysis of (h, k, 1)-Shellsort.
J. Algorithms, 1980
New Algorithms for Bin Packing.
J. ACM, 1980
External Hashing Schemes for Collections of Data Structures.
J. ACM, 1980
Information Bounds Are Weak in the Shortest Distance Problem.
J. ACM, 1980
A Note on the Analysis of Extendible Hashing.
Inf. Process. Lett., 1980
1979
The Complexity of Pattern Matching for a Random String.
SIAM J. Comput., 1979
A Note on a Conjecture of Kam and Ullman Concerning Statistical Databases.
Inf. Process. Lett., 1979
Storing a Sparse Table.
Commun. ACM, 1979
Some Complexity Questions Related to Distributive Computing (Preliminary Report)
Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979
1978
On the Loop Switching Addressing Problem.
SIAM J. Comput., 1978
k+1 Heads Are Better than k.
J. ACM, 1978
Addition chains with multiplicative cost.
Discrete Mathematics, 1978
On Random 2-3 Trees.
Acta Inf., 1978
On the Average-case Complexity of Selecting k-th Best
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978
Should Tables Be Sorted? (Extended Abstract)
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978
1977
An Omega(n^2 log n) Lower Bound to the Shortest Paths Problem
Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977
Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract)
Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977
1976
On the Evaluation of Powers.
SIAM J. Comput., 1976
Resource Constrained Scheduling as Generalized Bin Packing.
J. Comb. Theory, Ser. A, 1976
Lower Bounds on Merging Networks.
J. ACM, 1976
An Almost Optimal Algorithm for Unbounded Searching.
Inf. Process. Lett., 1976
On a problem of Katona on minimal separating systems.
Discrete Mathematics, 1976
Analysis of the subtractive algorithm for greatest common divisors.
ACM SIGSAM Bulletin, 1976
On the Average Behavior of Set Merging Algorithms (Extended Abstract)
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976
The Complexity of Searching an Ordered Random Table (Extended Abstract)
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976
k+1 Heads Are Better than k
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976
1975
An O(|E| log log |V|) Algorithm for Finding Minimum Spanning Trees.
Inf. Process. Lett., 1975
On Computing the Minima of Quadratic Forms (Preliminary Report)
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975
On the Complexity of Comparison Problems using Linear Functions (Preliminary Report)
Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975
1974
Scheduling Unit-Time Tasks with Limited Resources.
Proceedings of the Parallel Processing, 1974
Bounds on Selection Networks
Proceedings of the 15th Annual Symposium on Switching and Automata Theory, 1974