Andrew Chi-Chih Yao

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

Collaborative distances:

• Dijkstra number of two.
• Erdős number of two.

2024

On the Diagram of Thought.

Yifan Zhang, Yang Yuan, Andrew Chi-Chih Yao

CoRR, 2024

A system capable of verifiably and privately screening global DNA synthesis.

Carsten Baum, Jens Berlips, Walther Chen, Hongrui Cui, Ivan Damgård, Jiangbin Dong, Kevin M. Esvelt, Mingyu Gao, Dana Gretton, Leonard Foner, Martin Kysel, Kaiyi Zhang, Juanru Li, Xiang Li, Omer Paneth, Ronald L. Rivest, Francesca Sage-Ling, Adi Shamir, Yue Shen, Meicen Sun, Vinod Vaikuntanathan, Lynn Van Hauwe, Theia Vogel, Benjamin Weinstein-Raun, Yun Wang, Daniel Wichs, Stephen Wooster, Andrew C. Yao, Yu Yu, Haoling Zhang

CoRR, 2024

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

Yifan Zhang, Yifan Luo, Yang Yuan, Andrew Chi-Chih Yao

CoRR, 2024

Augmenting Math Word Problems via Iterative Question Composing.

Haoxiong Liu, Yifan Zhang, Yifan Luo, Andrew Chi-Chih Yao

CoRR, 2024

Efficient Maliciously Secure Oblivious Exponentiations.

Carsten Baum, Jens Berlips, Walther Chen, Ivan Bjerre Damgård, Kevin M. Esvelt, Leonard Foner, Dana Gretton, Martin Kysel, Ronald L. Rivest, Lawrence Roy, Francesca Sage-Ling, Adi Shamir, Vinod Vaikuntanathan, Lynn Van Hauwe, Theia Vogel, Benjamin Weinstein-Raun, Daniel Wichs, Stephen Wooster, Andrew C. Yao, Yu Yu

IACR Commun. Cryptol., 2024

2023

Cumulative Reasoning with Large Language Models.

Yifan Zhang, Jingqin Yang, Yang Yuan, Andrew Chi-Chih Yao

CoRR, 2023

Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regression.

Jing Xu, Jiaye Teng, Yang Yuan, Andrew C. Yao

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.

Jing Xu, Jiaye Teng, Andrew Chi-Chih Yao

CoRR, 2022

Perspectives from the second Global Forum on Development of Computer Science.

Andrew Chi-Chih Yao, Xia Yin, Yinqun Liu, Guoliang Li

Sci. China Inf. Sci., 2022

2021

FedCM: Federated Learning with Client-level Momentum.

Jing Xu, Sen Wang, Liwei Wang, Andrew Chi-Chih Yao

CoRR, 2021

2020

An authenticated and secure accounting system for international emissions trading.

Chenxing Li, Yang Yu, Andrew Chi-Chih Yao, Da Zhang, Xiliang Zhang

CoRR, 2020

A Decentralized Blockchain with High Throughput and Fast Confirmation.

Chenxing Li, Peilun Li, Dong Zhou, Zhe Yang, Ming Wu, Guang Yang, Wei Xu, Fan Long, Andrew Chi-Chih Yao

Proceedings of the 2020 USENIX Annual Technical Conference, 2020

An Incentive Analysis of Some Bitcoin Fee Designs (Invited Talk).

Andrew Chi-Chih Yao

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2018

An Incentive Analysis of some Bitcoin Fee Designs.

Andrew Chi-Chih Yao

CoRR, 2018

Scaling Nakamoto Consensus to Thousands of Transactions per Second.

Chenxing Li, Peilun Li, Wei Xu, Fan Long, Andrew Chi-Chih Yao

CoRR, 2018

On Revenue Monotonicity in Combinatorial Auctions.

Andrew Chi-Chih Yao

Proceedings of the Algorithmic Game Theory - 11th International Symposium, 2018

2017

Dominant-Strategy versus Bayesian Multi-item Auctions: Maximum Revenue Determination and Comparison.

Andrew Chi-Chih Yao

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

2016

Concurrent Knowledge Extraction in Public-Key Models.

Andrew Chi-Chih Yao, Moti Yung, Yunlei Zhao

J. Cryptol., 2016

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

Andrew Chi-Chih Yao

CoRR, 2016

2015

An <i>n</i>-to-1 Bidder Reduction for Multi-item Auctions and its Applications.

Andrew Chi-Chih Yao

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Interdisciplinarity: A View from Theory of Computation.

Andrew Chi-Chih Yao

Proceedings of the Federated Computing Research Conference, 2015

2014

Privacy-Preserving Authenticated Key-Exchange Over Internet.

Andrew Chi-Chih Yao, Yunlei Zhao

IEEE Trans. Inf. Forensics Secur., 2014

An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications.

Andrew Chi-Chih Yao

CoRR, 2014

2013

Online/Offline Signatures for Low-Power Devices.

Andrew Chi-Chih Yao, Yunlei Zhao

IEEE Trans. Inf. Forensics Secur., 2013

On revenue maximization for selling multiple independently distributed items.

Xinye Li, Andrew Chi-Chih Yao

Proc. Natl. Acad. Sci. USA, 2013

OAKE: a new family of implicitly authenticated diffie-hellman protocols.

Andrew Chi-Chih Yao, Yunlei Zhao

Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security, 2013

2012

Graph Coloring Applied to Secure Computation in Non-Abelian Groups.

Yvo Desmedt, Josef Pieprzyk, Ron Steinfeld, Xiaoming Sun, Christophe Tartary, Huaxiong Wang, Andrew Chi-Chih Yao

J. Cryptol., 2012

Computationally-Fair Group and Identity-Based Key-Exchange.

Andrew C. Yao, Yunlei Zhao

IACR Cryptol. ePrint Arch., 2012

Digital Signatures from Challenge-Divided Sigma-Protocols.

Andrew C. Yao, Yunlei Zhao

IACR Cryptol. ePrint Arch., 2012

Quantum Computing: A Great Science in the Making.

Andrew Chi-Chih Yao

Proceedings of the Theory and Applications of Models of Computation, 2012

The Turing Computational Model.

Juris Hartmanis, Stephen Cook, William Kahan, Richard Edwin Stearns, Andrew C. Yao

Proceedings of the ACM Turing Centenary Celebration, 2012

2011

A New Family of Practical Non-Malleable Protocols.

Andrew C. Yao, Yunlei Zhao

IACR Cryptol. ePrint Arch., 2011

A New Family of Practical Non-Malleable Diffie-Hellman Protocols

Andrew C. Yao, Yunlei Zhao

CoRR, 2011

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum <i>k</i>-Way Cut Problem.

Mingyu Xiao, Leizhen Cai, Andrew Chi-Chih Yao

Algorithmica, 2011

2010

Adaptive Concurrent Non-Malleability with Bare Public-Keys.

Andrew C. Yao, Moti Yung, Yunlei Zhao

IACR Cryptol. ePrint Arch., 2010

Concurrent Knowledge Extraction in the Public-Key Model.

Andrew C. Yao, Moti Yung, Yunlei Zhao

IACR Cryptol. ePrint Arch., 2010

A New Framework for RFID Privacy.

Robert H. Deng, Yingjiu Li, Andrew C. Yao, Moti Yung, Yunlei Zhao

IACR Cryptol. ePrint Arch., 2010

Deniable Internet Key Exchange.

Andrew Chi-Chih Yao, Yunlei Zhao

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.

Andrew Chi-Chih Yao, Frances F. Yao, Yunlei Zhao

Theor. Comput. Sci., 2009

A note on the feasibility of generalised universal composability.

Andrew Chi-Chih Yao, Frances F. Yao, Yunlei Zhao

Math. Struct. Comput. Sci., 2009

On the Quantum Query Complexity of Local Search in Two and Three Dimensions.

Xiaoming Sun, Andrew Chi-Chih Yao

Algorithmica, 2009

Communication Complexity and Its Applications.

Andrew Chi-Chih Yao

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

Mingyu Xiao, Leizhen Cai, Andrew C. Yao

CoRR, 2008

Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems.

Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, Andrew Chi-Chih Yao

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Some Perspectives on Complexity-Based Cryptography.

Andrew Chi-Chih Yao

Proceedings of the Advances in Cryptology, 2008

Graph Design for Secure Multiparty Computation over Non-Abelian Groups.

Xiaoming Sun, Andrew Chi-Chih Yao, Christophe Tartary

Proceedings of the Advances in Cryptology, 2008

2007

Deniable Internet Key-Exchange.

Andrew Chi-Chih Yao, Frances F. Yao, Yunlei Zhao, Bin B. Zhu

IACR Cryptol. ePrint Arch., 2007

Oblivious and Adaptive Strategies for the Majority and Plurality Problems.

Fan R. K. Chung, Ronald L. Graham, Jia Mao, Andrew Chi-Chih Yao

Algorithmica, 2007

A Note on the Feasibility of Generalized Universal Composability.

Andrew Chi-Chih Yao, Frances F. Yao, Yunlei Zhao

Proceedings of the Theory and Applications of Models of Computation, 2007

2006

Discrete and continuous min-energy schedules for variable voltage processors.

Minming Li, Andrew C. Yao, Frances F. Yao

Proc. Natl. Acad. Sci. USA, 2006

Recent Progress in Quantum Computational Complexity.

Andrew Chi-Chih Yao

Proceedings of the Theory and Applications of Models of Computation, 2006

Some perspectives on computational and communication complexity.

Andrew C. Yao

Proceedings of the Proceedings 2006 IEEE International Symposium on Information Theory, 2006

2005

On the Communication Complexity of Co-linearity Problems.

Andrew Chi-Chih Yao

Proceedings of the Mathematical Foundations of Computer Science 2005, 2005

2004

Self testing quantum apparatus.

Dominic Mayers, Andrew Chi-Chih Yao

Quantum Inf. Comput., 2004

Graph entropy and quantum sorting problems.

Andrew Chi-Chih Yao

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Dynamic Price Sequence and Incentive Compatibility (Extended Abstract).

Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Fisher Equilibrium Price with a Class of Concave Utility Functions.

Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao

Proceedings of the Algorithms, 2004

Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go?

Xiaoming Sun, Andrew Chi-Chih Yao, Shengyu Zhang

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Finding Favorites

Fan R. K. Chung, Ronald L. Graham, Jia Mao, Andrew Chi-Chih Yao

Electron. Colloquium Comput. Complex., 2003

Interactive Proofs for Quantum Computation.

Andrew Chi-Chih Yao

Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2002

On the Power of Quantum Fingerprinting

Andrew Chi-Chih Yao

Electron. Colloquium Comput. Complex., 2002

Classical Physics and the Church-Turing Thesis

Andrew Chi-Chih Yao

Electron. Colloquium Comput. Complex., 2002

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.

Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao

Comb., 2002

2001

Some perspective on computational complexity (abstract).

Andrew Chi-Chih Yao

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.

Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Quantum bit escrow.

Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999

NQP_C = co-C₌P.

Tomoyuki Yamakami, Andrew Chi-Chih Yao

Inf. Process. Lett., 1999

1998

NQP = co-C₌P

Tomoyuki Yamakami, Andrew Chi-Chih Yao

Electron. Colloquium Comput. Complex., 1998

RAPID: Randomized pharmacophore identification for drug design.

Paul W. Finn, Lydia E. Kavraki, Jean-Claude Latombe, Rajeev Motwani, Christian R. Shelton, Suresh Venkatasubramanian, Andrew Chi-Chih Yao

Comput. Geom., 1998

An exponential lower bound on the size of algebraic decision trees for Max.

Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao

Comput. Complex., 1998

Quantum Cryptography with Imperfect Apparatus.

Dominic Mayers, Andrew Chi-Chih Yao

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Decision Tree Complexity and Betti Numbers.

Andrew Chi-Chih Yao

J. Comput. Syst. Sci., 1997

Dictionary Look-Up with One Error.

Andrew Chi-Chih Yao, Frances F. Yao

J. Algorithms, 1997

1996

Hypergraphs and Decision Trees (Abstract).

Andrew Chi-Chih Yao

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1996

1995

Algebraic Decision Trees and Euler Characteristics.

Andrew Chi-Chih Yao

Theor. Comput. Sci., 1995

On the Shrinkage Exponent for Read-Once Formulae.

Johan Håstad, Alexander A. Razborov, Andrew Chi-Chih Yao

Theor. Comput. Sci., 1995

On Computing Algebraic Functions Using Logarithms and Exponentials.

Dima Grigoriev, Michael F. Singer, Andrew Chi-Chih Yao

SIAM J. Comput., 1995

Minimean Optimal Key Arrangements in Hash Tables.

Andrew Chi-Chih Yao

Algorithmica, 1995

Security of quantum protocols against coherent measurements.

Andrew Chi-Chih Yao

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Dictionary Loop-Up with Small Errors.

Andrew Chi-Chih Yao, F. Frances Yao

Proceedings of the Combinatorial Pattern Matching, 6th Annual Symposium, 1995

1994

Near-Optimal Time-Space Tradeoff for Element Distinctness.

Andrew Chi-Chih Yao

SIAM J. Comput., 1994

A Randomized Algorithm for Finding Maximum with O((log n)²) Polynomial Tests.

Hing-Fung Ting, Andrew Chi-Chih Yao

Inf. Process. Lett., 1994

A Lower Bound for the Monotone Depth of Connectivity

Andrew Chi-Chih Yao

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

A Circuit-Based Proof of Toda's Theorem

Ravi Kannan, H. Venkateswaran, V. Vinay, Andrew Chi-Chih Yao

Inf. Comput., June, 1993

Groups and Algebraic Complexity (Abstract).

Andrew Chi-Chih Yao

Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Quantum Circuit Complexity

Andrew Chi-Chih Yao

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

Towards Uncheatable benchmarks.

Jin-yi Cai, Richard J. Lipton, Robert Sedgewick, Andrew Chi-Chih Yao

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

Linear Decision Trees: Volume Estimates and Topological Bounds

Anders Björner, László Lovász, Andrew Chi-Chih Yao

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

1991

Lower Bounds for Algebraic Computation Trees with Integer Inputs.

Andrew Chi-Chih Yao

SIAM J. Comput., 1991

Lower Bounds to Randomized Algorithms for Graph Properties.

Andrew Chi-Chih Yao

J. Comput. Syst. Sci., 1991

Weighted Random Assignments with Application to Hashing.

Andrew Chi-Chih Yao

Proceedings of the ISA '91 Algorithms, 1991

Program Checkers for Probability Generation.

Sampath Kannan, Andrew Chi-Chih Yao

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Recent Progress in Circuit and Communication Complexity (Abstract).

Andrew Chi-Chih Yao

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990

On Evaluating Boolean Functions with Unreliable Tests.

Claire Kenyon, Andrew Chi-Chih Yao

Int. J. Found. Comput. Sci., 1990

Coherent Functions and Program Checkers (Extended Abstract)

Andrew Chi-Chih Yao

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

On ACC and Threshold Circuits

Andrew Chi-Chih Yao

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

On the Complexity of Partial Order Productions.

Andrew Chi-Chih Yao

SIAM J. Comput., 1989

On Selecting the k Largest with Median Tests.

Andrew Chi-Chih Yao

Algorithmica, 1989

Circuits and Local Computation

Andrew Chi-Chih Yao

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

On the Improbability of Reaching Byzantine Agreements (Preliminary Version)

Ronald L. Graham, Andrew Chi-Chih Yao

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988

Monotone Bipartite Graph Properties are Evasive.

Andrew Chi-Chih Yao

SIAM J. Comput., 1988

1987

Lower Bounds to Randomized Algorithms for Graph Properties (Extended Abstract)

Andrew Chi-Chih Yao

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986

How to Generate and Exchange Secrets (Extended Abstract)

Andrew Chi-Chih Yao

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

Uniform Hashing Is Optimal

Andrew Chi-Chih Yao

J. ACM, July, 1985

On Fault-Tolerant Networks for Sorting.

Andrew Chi-Chih Yao, F. Frances Yao

SIAM J. Comput., 1985

On the Complexity of Maintaining Partial Sums.

Andrew Chi-Chih Yao

SIAM J. Comput., 1985

On the Expected Performance of Path Compression Algorithms.

Andrew Chi-Chih Yao

SIAM J. Comput., 1985

On Optimal Arrangements of Keys with Double Hashing.

Andrew Chi-Chih Yao

J. Algorithms, 1985

A General Approach to d-Dimensional Geometric Queries (Extended Abstract)

Andrew Chi-Chih Yao, F. Frances Yao

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)

Andrew Chi-Chih Yao

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1983

On the security of public key protocols.

Danny Dolev, Andrew Chi-Chih Yao

IEEE Trans. Inf. Theory, 1983

Strong Signature Schemes

Shafi Goldwasser, Silvio Micali, Andrew Chi-Chih Yao

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

Lower Bounds by Probabilistic Arguments (Extended Abstract)

Andrew Chi-Chih Yao

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982

On the Time-Space Tradeoff for Sorting with Linear Queries.

Andrew Chi-Chih Yao

Theor. Comput. Sci., 1982

On the Average-Case Complexity of Selecting the kth Best.

Andrew Chi-Chih Yao, F. Frances Yao

SIAM J. Comput., 1982

On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems.

Andrew Chi-Chih Yao

SIAM J. Comput., 1982

The Complexity of Finding Cycles in Periodic Functions.

Robert Sedgewick, Thomas G. Szymanski, Andrew Chi-Chih Yao

SIAM J. Comput., 1982

Lower Bounds for Algebraic Decision Trees.

J. Michael Steele, Andrew Chi-Chih Yao

J. Algorithms, 1982

On Parallel Computation for the Knapsack Problem.

Andrew Chi-Chih Yao

J. ACM, 1982

Space-Time Tradeoff for Answering Range Queries (Extended Abstract)

Andrew Chi-Chih Yao

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

Protocols for Secure Computations (Extended Abstract)

Andrew Chi-Chih Yao

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

Theory and Applications of Trapdoor Functions (Extended Abstract)

Andrew Chi-Chih Yao

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

On Signatures and Authentication.

Shafi Goldwasser, Silvio Micali, Andrew Chi-Chih Yao

Proceedings of the Advances in Cryptology: Proceedings of CRYPTO '82, 1982

1981

An Analysis of a Memory Allocation Scheme for Implementing Stacks.

Andrew Chi-Chih Yao

SIAM J. Comput., 1981

A Lower Bound to Finding Convex Hulls.

Andrew Chi-Chih Yao

J. ACM, 1981

Should Tables Be Sorted?

Andrew Chi-Chih Yao

J. ACM, 1981

Efficient Searching Using Partial Ordering.

Allan Borodin, Leonidas J. Guibas, Nancy A. Lynch, Andrew Chi-Chih Yao

Inf. Process. Lett., 1981

The Entropic Limitations on VLSI Computations (Extended Abstract)

Andrew Chi-Chih Yao

Proceedings of the 13th Annual ACM Symposium on Theory of Computing, 1981

On the Security of Public Key Protocols (Extended Abstract)

Danny Dolev, Andrew Chi-Chih Yao

Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, 1981

1980

A Stochastic Model of Bin-Packing

Edward G. Coffman Jr., Kimming So, Micha Hofri, Andrew Chi-Chih Yao

Inf. Control., February, 1980

Optimal Expected-Time Algorithms for Closest Point Problems.

Jon Louis Bentley, Bruce W. Weide, Andrew Chi-Chih Yao

ACM Trans. Math. Softw., 1980

Some Monotonicity Properties of Partial Orders.

Ronald L. Graham, Andrew C. Yao, F. Frances Yao

SIAM J. Algebraic Discret. Methods, 1980

On the Polyhedral Decision Problem.

Andrew Chi-Chih Yao, Ronald L. Rivest

SIAM J. Comput., 1980

Bounds on Selection Networks.

Andrew Chi-Chih Yao

SIAM J. Comput., 1980

An Analysis of (h, k, 1)-Shellsort.

Andrew Chi-Chih Yao

J. Algorithms, 1980

New Algorithms for Bin Packing.

Andrew Chi-Chih Yao

J. ACM, 1980

External Hashing Schemes for Collections of Data Structures.

Richard J. Lipton, Arnold L. Rosenberg, Andrew Chi-Chih Yao

J. ACM, 1980

Information Bounds Are Weak in the Shortest Distance Problem.

Ronald L. Graham, Andrew Chi-Chih Yao, F. Frances Yao

J. ACM, 1980

A Note on the Analysis of Extendible Hashing.

Andrew Chi-Chih Yao

Inf. Process. Lett., 1980

1979

The Complexity of Pattern Matching for a Random String.

Andrew Chi-Chih Yao

SIAM J. Comput., 1979

A Note on a Conjecture of Kam and Ullman Concerning Statistical Databases.

Andrew Chi-Chih Yao

Inf. Process. Lett., 1979

Storing a Sparse Table.

Robert Endre Tarjan, Andrew Chi-Chih Yao

Commun. ACM, 1979

Some Complexity Questions Related to Distributive Computing (Preliminary Report)

Andrew Chi-Chih Yao

Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

1978

On the Loop Switching Addressing Problem.

Andrew Chi-Chih Yao

SIAM J. Comput., 1978

k+1 Heads Are Better than k.

Andrew Chi-Chih Yao, Ronald L. Rivest

J. ACM, 1978

Addition chains with multiplicative cost.

Ronald L. Graham, Andrew Chi-Chih Yao, F. Frances Yao

Discret. Math., 1978

On Random 2-3 Trees.

Andrew Chi-Chih Yao

Acta Informatica, 1978

On the Average-case Complexity of Selecting k-th Best

Andrew Chi-Chih Yao, F. Frances Yao

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

Should Tables Be Sorted? (Extended Abstract)

Andrew Chi-Chih Yao

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

Andrew Chi-Chih Yao, David Avis, Ronald L. Rivest

Proceedings of the 9th Annual ACM Symposium on Theory of Computing, 1977

Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract)

Andrew Chi-Chih Yao

Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October, 1977

1976

On the Evaluation of Powers.

Andrew Chi-Chih Yao

SIAM J. Comput., 1976

Resource Constrained Scheduling as Generalized Bin Packing.

M. R. Garey, Ronald L. Graham, David S. Johnson, Andrew Chi-Chih Yao

J. Comb. Theory A, 1976

Lower Bounds on Merging Networks.

Andrew Chi-Chih Yao, Foong Frances Yao

J. ACM, 1976

An Almost Optimal Algorithm for Unbounded Searching.

Jon Louis Bentley, Andrew Chi-Chih Yao

Inf. Process. Lett., 1976

On a problem of Katona on minimal separating systems.

Andrew Chi-Chih Yao

Discret. Math., 1976

Analysis of the subtractive algorithm for greatest common divisors.

Andrew Chi-Chih Yao, Donald E. Knuth

SIGSAM Bull., 1976

On the Average Behavior of Set Merging Algorithms (Extended Abstract)

Andrew Chi-Chih Yao

Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

The Complexity of Searching an Ordered Random Table (Extended Abstract)

Andrew Chi-Chih Yao, F. Frances Yao

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.

Andrew Chi-Chih Yao

Inf. Process. Lett., 1975

On Computing the Minima of Quadratic Forms (Preliminary Report)

Andrew Chi-Chih Yao

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

On the Complexity of Comparison Problems using Linear Functions (Preliminary Report)

Andrew Chi-Chih Yao

Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975

1974

Scheduling Unit-Time Tasks with Limited Resources.

Andrew Chi-Chih Yao

Proceedings of the Parallel Processing, Proceedings of the Sagamore Computer Conference, 1974