Andrew Chi-Chih Yao

Affiliations:
  • Tsinghua University, Institute for Theoretical Computer Science


According to our database1, Andrew Chi-Chih Yao authored at least 160 papers between 1974 and 2024.

Collaborative distances:
  • Dijkstra number2 of two.
  • Erdős number3 of two.

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 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
AutoMathText: Autonomous Data Selection with Language Models for Mathematical Texts.
CoRR, 2024

Augmenting Math Word Problems via Iterative Question Composing.
CoRR, 2024

2023
Cumulative Reasoning with Large Language Models.
CoRR, 2023

Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

2022
Relaxing the Feature Covariance Assumption: Time-Variant Bounds for Benign Overfitting in Linear Regression.
CoRR, 2022

Perspectives from the second Global Forum on Development of Computer Science.
Sci. China Inf. Sci., 2022

2021
FedCM: Federated Learning with Client-level Momentum.
CoRR, 2021

2020
An authenticated and secure accounting system for international emissions trading.
CoRR, 2020

A Decentralized Blockchain with High Throughput and Fast Confirmation.
Proceedings of the 2020 USENIX Annual Technical Conference, 2020

An Incentive Analysis of Some Bitcoin Fee Designs (Invited Talk).
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2018
An Incentive Analysis of some Bitcoin Fee Designs.
CoRR, 2018

Scaling Nakamoto Consensus to Thousands of Transactions per Second.
CoRR, 2018

On Revenue Monotonicity in Combinatorial Auctions.
Proceedings of the Algorithmic Game Theory - 11th International Symposium, 2018

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. Cryptol., 2016

On Solutions for the Maximum Revenue Multi-item Auction under Dominant-Strategy and Bayesian Implementations.
CoRR, 2016

2015
An <i>n</i>-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. Inf. Forensics Secur., 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. Inf. Forensics Secur., 2013

On revenue maximization for selling multiple independently distributed items.
Proc. Natl. Acad. Sci. USA, 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. Cryptol., 2012

Computationally-Fair Group and Identity-Based Key-Exchange.
IACR Cryptol. ePrint Arch., 2012

Digital Signatures from Challenge-Divided Sigma-Protocols.
IACR Cryptol. ePrint Arch., 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 Cryptol. ePrint Arch., 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 <i>k</i>-Way Cut Problem.
Algorithmica, 2011

2010
Adaptive Concurrent Non-Malleability with Bare Public-Keys.
IACR Cryptol. ePrint Arch., 2010

Concurrent Knowledge Extraction in the Public-Key Model.
IACR Cryptol. ePrint Arch., 2010

A New Framework for RFID Privacy.
IACR Cryptol. ePrint Arch., 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.
Math. Struct. Comput. Sci., 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 Cryptol. ePrint Arch., 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

2006
Discrete and continuous min-energy schedules for variable voltage processors.
Proc. Natl. Acad. Sci. USA, 2006

Recent Progress in Quantum Computational Complexity.
Proceedings of the Theory and Applications of Models of Computation, 2006

Some perspectives on computational and communication complexity.
Proceedings of the Proceedings 2006 IEEE International Symposium on Information Theory, 2006

2005
On the Communication Complexity of Co-linearity Problems.
Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

2004
Self testing quantum apparatus.
Quantum Inf. Comput., 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
Electron. Colloquium Comput. Complex., 2003

Interactive Proofs for Quantum Computation.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2002
On the Power of Quantum Fingerprinting
Electron. Colloquium Comput. Complex., 2002

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
Comb., 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
NQP<sub>C</sub> = co-C<sub>=</sub>P.
Inf. Process. Lett., 1999

1998
NQP = co-C<sub>=</sub>P
Electron. Colloquium Comput. Complex., 1998

RAPID: Randomized pharmacophore identification for drug design.
Comput. Geom., 1998

An exponential lower bound on the size of algebraic decision trees for Max.
Comput. Complex., 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

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

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.
Proceedings of the Combinatorial Pattern Matching, 6th Annual Symposium, 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

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

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

1988
Monotone Bipartite Graph Properties are Evasive.
SIAM J. Comput., 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. Inf. 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 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
Inf. Control., February, 1980

Optimal Expected-Time Algorithms for Closest Point Problems.
ACM Trans. Math. Softw., 1980

Some Monotonicity Properties of Partial Orders.
SIAM J. Algebraic Discret. Methods, 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.
Discret. Math., 1978

On Random 2-3 Trees.
Acta Informatica, 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.
Discret. Math., 1976

Analysis of the subtractive algorithm for greatest common divisors.
SIGSAM Bull., 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

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, Proceedings of the Sagamore Computer Conference, 1974


  Loading...