Andrew Chi-Chih Yao

According to our database1, Andrew Chi-Chih Yao
  • authored at least 165 papers between 1974 and 2017.
  • has a "Dijkstra number"2 of three.

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 
Other 

Links

Homepages:

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


  Loading...