 | 2009 |
|---|
| 130 |       | Andrew Chi-Chih Yao:
Communication Complexity and Its Applications.
FAW 2009: 2 |
| 129 | | Xiaoming Sun,
Andrew Chi-Chih Yao:
On the Quantum Query Complexity of Local Search in Two and Three Dimensions.
Algorithmica 55(3): 576-600 (2009) |
| 128 | | Andrew Chi-Chih Yao,
Moti Yung,
Yunlei Zhao:
Concurrent Knowledge-Extraction in the Public-Key Model
CoRR abs/0908.2476: (2009) |
| 127 | | Andrew Chi-Chih Yao,
Moti Yung,
Yunlei Zhao:
Adaptive Concurrent Non-Malleability with Bare Public-Keys
CoRR abs/0910.3282: (2009) |
| 126 | | Andrew Chi-Chih Yao,
Frances F. Yao,
Yunlei Zhao:
A note on the feasibility of generalised universal composability.
Mathematical Structures in Computer Science 19(1): 193-205 (2009) |
| 125 | | Andrew Chi-Chih Yao,
Frances F. Yao,
Yunlei Zhao:
A note on universal composable zero-knowledge in the common reference string model.
Theor. Comput. Sci. 410(11): 1099-1108 (2009) |
| 2008 |
|---|
| 124 | | Xiaoming Sun,
Andrew Chi-Chih Yao,
Christophe Tartary:
Graph Design for Secure Multiparty Computation over Non-Abelian Groups.
ASIACRYPT 2008: 37-53 |
| 123 | | Andrew Chi-Chih Yao:
Some Perspectives on Complexity-Based Cryptography.
ASIACRYPT 2008: 54 |
| 122 | | Tsuyoshi Ito,
Hirotada Kobayashi,
Daniel Preda,
Xiaoming Sun,
Andrew Chi-Chih Yao:
Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems.
IEEE Conference on Computational Complexity 2008: 187-198 |
| 2007 |
|---|
| 121 | | Andrew Chi-Chih Yao,
Frances F. Yao,
Yunlei Zhao:
A Note on Universal Composable Zero Knowledge in Common Reference String Model.
TAMC 2007: 462-473 |
| 120 | | Andrew Chi-Chih Yao,
Frances F. Yao,
Yunlei Zhao:
A Note on the Feasibility of Generalized Universal Composability.
TAMC 2007: 474-485 |
| 119 | | Fan R. K. Chung,
Ronald L. Graham,
Jia Mao,
Andrew Chi-Chih Yao:
Oblivious and Adaptive Strategies for the Majority and Plurality Problems.
Algorithmica 48(2): 147-157 (2007) |
| 2006 |
|---|
| 118 | | Xiaoming Sun,
Andrew Chi-Chih Yao:
On the Quantum Query Complexity of Local Search in Two and Three Dimensions.
FOCS 2006: 429-438 |
| 117 | | Andrew Chi-Chih Yao:
Recent Progress in Quantum Computational Complexity.
TAMC 2006: 89-89 |
| 2005 |
|---|
| 116 | | Fan R. K. Chung,
Ronald L. Graham,
Jia Mao,
Andrew Chi-Chih Yao:
Oblivious and Adaptive Strategies for the Majority and Plurality Problems.
COCOON 2005: 329-338 |
| 115 | | Andrew Chi-Chih Yao:
On the Communication Complexity of Co-linearity Problems.
MFCS 2005: 57 |
| 2004 |
|---|
| 114 | | Ning Chen,
Xiaotie Deng,
Xiaoming Sun,
Andrew Chi-Chih Yao:
Fisher Equilibrium Price with a Class of Concave Utility Functions.
ESA 2004: 169-179 |
| 113 | | Ning Chen,
Xiaotie Deng,
Xiaoming Sun,
Andrew Chi-Chih Yao:
Dynamic Price Sequence and Incentive Compatibility (Extended Abstract).
ICALP 2004: 320-331 |
| 112 | | Xiaoming Sun,
Andrew Chi-Chih Yao,
Shengyu Zhang:
Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go?
IEEE Conference on Computational Complexity 2004: 286-293 |
| 111 | | Andrew Chi-Chih Yao:
Graph entropy and quantum sorting problems.
STOC 2004: 112-117 |
| 2003 |
|---|
| 110 | | Andrew Chi-Chih Yao:
Interactive Proofs for Quantum Computation.
ISAAC 2003: 1 |
| 109 | | Fan R. K. Chung,
Ronald L. Graham,
Jia Mao,
Andrew Chi-Chih Yao:
Finding Favorites
Electronic Colloquium on Computational Complexity (ECCC)(078): (2003) |
| 108 | | Andrew Chi-Chih Yao:
Classical physics and the Church-Turing Thesis.
J. ACM 50(1): 100-105 (2003) |
| 2002 |
|---|
| 107 | | Alexander A. Razborov,
Avi Wigderson,
Andrew Chi-Chih Yao:
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
Combinatorica 22(4): 555-574 (2002) |
| 106 | | Andrew Chi-Chih Yao:
Classical Physics and the Church-Turing Thesis
Electronic Colloquium on Computational Complexity (ECCC)(062): (2002) |
| 105 | | Andrew Chi-Chih Yao:
On the Power of Quantum Fingerprinting
Electronic Colloquium on Computational Complexity (ECCC)(074): (2002) |
| 2001 |
|---|
| 104 |  | Amit Chakrabarti,
Yaoyun Shi,
Anthony Wirth,
Andrew Chi-Chih Yao:
Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity.
FOCS 2001: 270-278 |
| 103 | | Andrew Chi-Chih Yao:
Some perspective on computational complexity (abstract).
STOC 2001: 600 |
| 2000 |
|---|
| 102 | | Dorit Aharonov,
Amnon Ta-Shma,
Umesh V. Vazirani,
Andrew Chi-Chih Yao:
Quantum bit escrow.
STOC 2000: 705-714 |
| 1999 |
|---|
| 101 | | Tomoyuki Yamakami,
Andrew Chi-Chih Yao:
NQPC = co-C=P.
Inf. Process. Lett. 71(2): 63-69 (1999) |
| 1998 |
|---|
| 100 | | Dominic Mayers,
Andrew Chi-Chih Yao:
Quantum Cryptography with Imperfect Apparatus.
FOCS 1998: 503-509 |
| 99 | | Tomoyuki Yamakami,
Andrew Chi-Chih Yao:
NQPC = co-C=P
CoRR quant-ph/9812032: (1998) |
| 98 | | Dima Grigoriev,
Marek Karpinski,
Andrew Chi-Chih Yao:
An exponential lower bound on the size of algebraic decision trees for Max.
Computational Complexity 7(3): 193-203 (1998) |
| 97 | | Tomoyuki Yamakami,
Andrew Chi-Chih Yao:
NQP = co-C=P
Electronic Colloquium on Computational Complexity (ECCC) 5(73): (1998) |
| 1997 |
|---|
| 96 | | Alexander A. Razborov,
Avi Wigderson,
Andrew Chi-Chih Yao:
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
STOC 1997: 739-748 |
| 95 | | Andrew Chi-Chih Yao,
Frances F. Yao:
Dictionary Look-Up with One Error.
J. Algorithms 25(1): 194-202 (1997) |
| 94 | | Andrew Chi-Chih Yao:
Decision Tree Complexity and Betti Numbers.
J. Comput. Syst. Sci. 55(1): 36-43 (1997) |
| 1996 |
|---|
| 93 | | Andrew Chi-Chih Yao:
Hypergraphs and Decision Trees (Abstract).
WG 1996: 1 |
| 1995 |
|---|
| 92 | | Andrew Chi-Chih Yao,
F. Frances Yao:
Dictionary Loop-Up with Small Errors.
CPM 1995: 387-394 |
| 91 | | Andrew Chi-Chih Yao:
Security of quantum protocols against coherent measurements.
STOC 1995: 67-75 |
| 90 | | Andrew Chi-Chih Yao:
Minimean Optimal Key Arrangements in Hash Tables.
Algorithmica 14(5): 409-428 (1995) |
| 89 | | Dima Grigoriev,
Marek Karpinski,
Andrew Chi-Chih Yao:
An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX
Electronic Colloquium on Computational Complexity (ECCC) 2(57): (1995) |
| 88 | | Dima Grigoriev,
Michael F. Singer,
Andrew Chi-Chih Yao:
On Computing Algebraic Functions Using Logarithms and Exponentials.
SIAM J. Comput. 24(2): 242-246 (1995) |
| 87 | | Andrew Chi-Chih Yao:
Algebraic Decision Trees and Euler Characteristics.
Theor. Comput. Sci. 141(1&2): 133-150 (1995) |
| 86 | | Johan Håstad,
Alexander A. Razborov,
Andrew Chi-Chih Yao:
On the Shrinkage Exponent for Read-Once Formulae.
Theor. Comput. Sci. 141(1&2): 269-282 (1995) |
| 1994 |
|---|
| 85 | | Andrew Chi-Chih Yao:
A Lower Bound for the Monotone Depth of Connectivity
FOCS 1994: 302-308 |
| 84 | | Andrew Chi-Chih Yao:
Decision tree complexity and Betti numbers.
STOC 1994: 615-624 |
| 83 | | Hing-Fung Ting,
Andrew Chi-Chih Yao:
A Randomized Algorithm for Finding Maximum with O((log n)²) Polynomial Tests.
Inf. Process. Lett. 49(1): 39-43 (1994) |
| 82 | | Andrew Chi-Chih Yao:
Near-Optimal Time-Space Tradeoff for Element Distinctness.
SIAM J. Comput. 23(5): 966-975 (1994) |
| 1993 |
|---|
| 81 | | Andrew Chi-Chih Yao:
Quantum Circuit Complexity
FOCS 1993: 352-361 |
| 80 | | Jin-yi Cai,
Richard J. Lipton,
Robert Sedgewick,
Andrew Chi-Chih Yao:
Towards Uncheatable benchmarks.
Structure in Complexity Theory Conference 1993: 2-11 |
| 79 | | Andrew Chi-Chih Yao:
Groups and Algebraic Complexity (Abstract).
WADS 1993: 35 |
| 78 | | Ravi Kannan,
H. Venkateswaran,
V. Vinay,
Andrew Chi-Chih Yao:
A Circuit-Based Proof of Toda's Theorem
Inf. Comput. 104(2): 271-276 (1993) |
| 1992 |
|---|
| 77 | | Andrew Chi-Chih Yao:
Algebraic Decision Trees and Euler Characteristics
FOCS 1992: 268-277 |
| 76 | | Anders Björner,
László Lovász,
Andrew Chi-Chih Yao:
Linear Decision Trees: Volume Estimates and Topological Bounds
STOC 1992: 170-177 |
| 1991 |
|---|
| 75 | | Andrew Chi-Chih Yao:
Recent Progress in Circuit and Communication Complexity (Abstract).
FCT 1991: 104 |
| 74 | | Sampath Kannan,
Andrew Chi-Chih Yao:
Program Checkers for Probability Generation.
ICALP 1991: 163-173 |
| 73 | | Andrew Chi-Chih Yao:
Weighted Random Assignments with Application to Hashing.
ISA 1991: 42 |
| 72 | | Andrew Chi-Chih Yao:
Lower Bounds to Randomized Algorithms for Graph Properties.
J. Comput. Syst. Sci. 42(3): 267-287 (1991) |
| 71 | | Andrew Chi-Chih Yao:
Lower Bounds for Algebraic Computation Trees with Integer Inputs.
SIAM J. Comput. 20(4): 655-668 (1991) |
| 1990 |
|---|
| 70 | | Andrew Chi-Chih Yao:
On ACC and Threshold Circuits
FOCS 1990: 619-627 |
| 69 | | Andrew Chi-Chih Yao:
Coherent Functions and Program Checkers (Extended Abstract)
STOC 1990: 84-94 |
| 68 | | Claire Kenyon,
Andrew Chi-Chih Yao:
On Evaluating Boolean Functions with Unreliable Tests.
Int. J. Found. Comput. Sci. 1(1): 1-10 (1990) |
| 1989 |
|---|
| 67 | | Andrew Chi-Chih Yao:
Lower Bounds for Algebraic Computation Trees with Integer Inputs
FOCS 1989: 308-313 |
| 66 | | Andrew Chi-Chih Yao:
Circuits and Local Computation
STOC 1989: 186-196 |
| 65 | | Ronald L. Graham,
Andrew Chi-Chih Yao:
On the Improbability of Reaching Byzantine Agreements (Preliminary Version)
STOC 1989: 467-478 |
| 64 | | Andrew Chi-Chih Yao:
On Selecting the k Largest with Median Tests.
Algorithmica 4(2): 293-300 (1989) |
| 63 | | Andrew Chi-Chih Yao:
On the Complexity of Partial Order Productions.
SIAM J. Comput. 18(4): 679-689 (1989) |
| 1988 |
|---|
| 62 | | Andrew Chi-Chih Yao:
Near-Optimal Time-Space Tradeoff for Element Distinctness
FOCS 1988: 91-97 |
| 61 | | Andrew Chi-Chih Yao:
Monotone Bipartite Graph Properties are Evasive.
SIAM J. Comput. 17(3): 517-520 (1988) |
| 1987 |
|---|
| 60 | | Andrew Chi-Chih Yao:
Lower Bounds to Randomized Algorithms for Graph Properties (Extended Abstract)
FOCS 1987: 393-400 |
| 1986 |
|---|
| 59 | | Andrew Chi-Chih Yao:
How to Generate and Exchange Secrets (Extended Abstract)
FOCS 1986: 162-167 |
| 1985 |
|---|
| 58 | | Andrew Chi-Chih Yao:
Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)
FOCS 1985: 1-10 |
| 57 | | Andrew Chi-Chih Yao,
F. Frances Yao:
A General Approach to d-Dimensional Geometric Queries (Extended Abstract)
STOC 1985: 163-168 |
| 56 | | Andrew Chi-Chih Yao:
Uniform Hashing Is Optimal
J. ACM 32(3): 687-693 (1985) |
| 55 | | Andrew Chi-Chih Yao:
On Optimal Arrangements of Keys with Double Hashing.
J. Algorithms 6(2): 253-264 (1985) |
| 54 | | Andrew Chi-Chih Yao,
F. Frances Yao:
On Fault-Tolerant Networks for Sorting.
SIAM J. Comput. 14(1): 120-128 (1985) |
| 53 | | Andrew Chi-Chih Yao:
On the Expected Performance of Path Compression Algorithms.
SIAM J. Comput. 14(1): 129-133 (1985) |
| 52 | | Andrew Chi-Chih Yao:
On the Complexity of Maintaining Partial Sums.
SIAM J. Comput. 14(2): 277-288 (1985) |
| 1983 |
|---|
| 51 | | Andrew Chi-Chih Yao:
Lower Bounds by Probabilistic Arguments (Extended Abstract)
FOCS 1983: 420-428 |
| 50 | | Shafi Goldwasser,
Silvio Micali,
Andrew Chi-Chih Yao:
Strong Signature Schemes
STOC 1983: 431-439 |
| 49 | | Danny Dolev,
Andrew Chi-Chih Yao:
On the security of public key protocols.
IEEE Transactions on Information Theory 29(2): 198-207 (1983) |
| 1982 |
|---|
| 48 | | Shafi Goldwasser,
Silvio Micali,
Andrew Chi-Chih Yao:
On Signatures and Authentication.
CRYPTO 1982: 211-215 |
| 47 | | Andrew Chi-Chih Yao:
Protocols for Secure Computations (Extended Abstract)
FOCS 1982: 160-164 |
| 46 | | Andrew Chi-Chih Yao:
Theory and Applications of Trapdoor Functions (Extended Abstract)
FOCS 1982: 80-91 |
| 45 | | Andrew Chi-Chih Yao:
Space-Time Tradeoff for Answering Range Queries (Extended Abstract)
STOC 1982: 128-136 |
| 44 | | Andrew Chi-Chih Yao:
On Parallel Computation for the Knapsack Problem.
J. ACM 29(3): 898-903 (1982) |
| 43 | | J. Michael Steele,
Andrew Chi-Chih Yao:
Lower Bounds for Algebraic Decision Trees.
J. Algorithms 3(1): 1-8 (1982) |
| 42 | | Robert Sedgewick,
Thomas G. Szymanski,
Andrew Chi-Chih Yao:
The Complexity of Finding Cycles in Periodic Functions.
SIAM J. Comput. 11(2): 376-390 (1982) |
| 41 | | Andrew Chi-Chih Yao,
F. Frances Yao:
On the Average-Case Complexity of Selecting the kth Best.
SIAM J. Comput. 11(3): 428-447 (1982) |
| 40 | | Andrew Chi-Chih Yao:
On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems.
SIAM J. Comput. 11(4): 721-736 (1982) |
| 39 | | Andrew Chi-Chih Yao:
On the Time-Space Tradeoff for Sorting with Linear Queries.
Theor. Comput. Sci. 19: 203-218 (1982) |
| 1981 |
|---|
| 38 | | Danny Dolev,
Andrew Chi-Chih Yao:
On the Security of Public Key Protocols (Extended Abstract)
FOCS 1981: 350-357 |
| 37 | | Andrew Chi-Chih Yao:
On the Parallel Computation for the Knapsack Problem
STOC 1981: 123-127 |
| 36 | | Andrew Chi-Chih Yao:
The Entropic Limitations on VLSI Computations (Extended Abstract)
STOC 1981: 308-311 |
| 35 | | Allan Borodin,
Leonidas J. Guibas,
Nancy A. Lynch,
Andrew Chi-Chih Yao:
Efficient Searching Using Partial Ordering.
Inf. Process. Lett. 12(2): 71-75 (1981) |
| 34 | | Andrew Chi-Chih Yao:
Should Tables Be Sorted?
J. ACM 28(3): 615-628 (1981) |
| 33 | | Andrew Chi-Chih Yao:
A Lower Bound to Finding Convex Hulls.
J. ACM 28(4): 780-787 (1981) |
| 32 | | Andrew Chi-Chih Yao:
An Analysis of a Memory Allocation Scheme for Implementing Stacks.
SIAM J. Comput. 10(2): 398-403 (1981) |
| 1980 |
|---|
| 31 | | Jon Louis Bentley,
Bruce W. Weide,
Andrew Chi-Chih Yao:
Optimal Expected-Time Algorithms for Closest Point Problems.
ACM Trans. Math. Softw. 6(4): 563-580 (1980) |
| 30 | | Andrew Chi-Chih Yao:
A Note on the Analysis of Extendible Hashing.
Inf. Process. Lett. 11(2): 84-86 (1980) |
| 29 | | Edward G. Coffman Jr.,
Kimming So,
Micha Hofri,
Andrew Chi-Chih Yao:
A Stochastic Model of Bin-Packing
Information and Control 44(2): 105-115 (1980) |
| 28 | | Richard J. Lipton,
Arnold L. Rosenberg,
Andrew Chi-Chih Yao:
External Hashing Schemes for Collections of Data Structures.
J. ACM 27(1): 81-95 (1980) |
| 27 | | Andrew Chi-Chih Yao:
New Algorithms for Bin Packing.
J. ACM 27(2): 207-227 (1980) |
| 26 | | Ronald L. Graham,
Andrew Chi-Chih Yao,
F. Frances Yao:
Information Bounds Are Weak in the Shortest Distance Problem.
J. ACM 27(3): 428-444 (1980) |
| 25 | | Andrew Chi-Chih Yao:
An Analysis of (h, k, 1)-Shellsort.
J. Algorithms 1(1): 14-50 (1980) |
| 24 | | Andrew Chi-Chih Yao,
Ronald L. Rivest:
On the Polyhedral Decision Problem.
SIAM J. Comput. 9(2): 343-347 (1980) |
| 23 | | Andrew Chi-Chih Yao:
Bounds on Selection Networks.
SIAM J. Comput. 9(3): 566-582 (1980) |
| 1979 |
|---|
| 22 | | Andrew Chi-Chih Yao:
Some Complexity Questions Related to Distributive Computing (Preliminary Report)
STOC 1979: 209-213 |
| 21 | | Robert Endre Tarjan,
Andrew Chi-Chih Yao:
Storing a Sparse Table.
Commun. ACM 22(11): 606-611 (1979) |
| 20 | | Andrew Chi-Chih Yao:
A Note on a Conjecture of Kam and Ullman Concerning Statistical Databases.
Inf. Process. Lett. 9(1): 48-50 (1979) |
| 19 | | Andrew Chi-Chih Yao:
The Complexity of Pattern Matching for a Random String.
SIAM J. Comput. 8(3): 368-387 (1979) |
| 1978 |
|---|
| 18 | | Andrew Chi-Chih Yao:
Should Tables Be Sorted? (Extended Abstract)
FOCS 1978: 22-27 |
| 17 | | Andrew Chi-Chih Yao,
F. Frances Yao:
On the Average-case Complexity of Selecting k-th Best
FOCS 1978: 280-289 |
| 16 | | Andrew Chi-Chih Yao:
On Random 2-3 Trees.
Acta Inf. 9: 159-170 (1978) |
| 15 | | Andrew Chi-Chih Yao,
Ronald L. Rivest:
k+1 Heads Are Better than k.
J. ACM 25(2): 337-340 (1978) |
| 14 | | Andrew Chi-Chih Yao:
On the Loop Switching Addressing Problem.
SIAM J. Comput. 7(4): 515-523 (1978) |
| 1977 |
|---|
| 13 | | Andrew Chi-Chih Yao:
Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract)
FOCS 1977: 222-227 |
| 12 | | Andrew Chi-Chih Yao,
David Avis,
Ronald L. Rivest:
An Omega(n^2 log n) Lower Bound to the Shortest Paths Problem
STOC 1977: 11-17 |
| 1976 |
|---|
| 11 | | Andrew Chi-Chih Yao,
F. Frances Yao:
The Complexity of Searching an Ordered Random Table (Extended Abstract)
FOCS 1976: 173-177 |
| 10 | | Andrew Chi-Chih Yao,
Ronald L. Rivest:
k+1 Heads Are Better than k
FOCS 1976: 67-70 |
| 9 | | Andrew Chi-Chih Yao:
On the Average Behavior of Set Merging Algorithms (Extended Abstract)
STOC 1976: 192-195 |
| 8 | | Jon Louis Bentley,
Andrew Chi-Chih Yao:
An Almost Optimal Algorithm for Unbounded Searching.
Inf. Process. Lett. 5(3): 82-87 (1976) |
| 7 | | Andrew Chi-Chih Yao,
Foong Frances Yao:
Lower Bounds on Merging Networks.
J. ACM 23(3): 566-571 (1976) |
| 6 | | Andrew Chi-Chih Yao:
On the Evaluation of Powers.
SIAM J. Comput. 5(1): 100-103 (1976) |
| 1975 |
|---|
| 5 | | Andrew Chi-Chih Yao:
On the Complexity of Comparison Problems using Linear Functions (Preliminary Report)
FOCS 1975: 85-89 |
| 4 | | Andrew Chi-Chih Yao:
On Computing the Minima of Quadratic Forms (Preliminary Report)
STOC 1975: 23-26 |
| 3 | | Andrew Chi-Chih Yao:
An O(|E| log log |V|) Algorithm for Finding Minimum Spanning Trees.
Inf. Process. Lett. 4(1): 21-23 (1975) |
| 1974 |
|---|
| 2 | | Andrew Chi-Chih Yao:
Bounds on Selection Networks
FOCS 1974: 110-116 |
| 1 | | Andrew Chi-Chih Yao:
Scheduling Unit-Time Tasks with Limited Resources.
Sagamore Computer Conference 1974: 17-36 |
