2009 | ||
---|---|---|
126 | EE | 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 | EE | 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 | EE | Xiaoming Sun, Andrew Chi-Chih Yao, Christophe Tartary: Graph Design for Secure Multiparty Computation over Non-Abelian Groups. ASIACRYPT 2008: 37-53 |
123 | EE | Andrew Chi-Chih Yao: Some Perspectives on Complexity-Based Cryptography. ASIACRYPT 2008: 54 |
122 | EE | 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 | EE | 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 | EE | Andrew Chi-Chih Yao, Frances F. Yao, Yunlei Zhao: A Note on the Feasibility of Generalized Universal Composability. TAMC 2007: 474-485 |
119 | EE | 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 | EE | Xiaoming Sun, Andrew Chi-Chih Yao: On the Quantum Query Complexity of Local Search in Two and Three Dimensions. FOCS 2006: 429-438 |
117 | EE | Andrew Chi-Chih Yao: Recent Progress in Quantum Computational Complexity. TAMC 2006: 89-89 |
2005 | ||
116 | EE | 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 | EE | Andrew Chi-Chih Yao: On the Communication Complexity of Co-linearity Problems. MFCS 2005: 57 |
2004 | ||
114 | EE | 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 | EE | Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao: Dynamic Price Sequence and Incentive Compatibility (Extended Abstract). ICALP 2004: 320-331 |
112 | EE | 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 | EE | Andrew Chi-Chih Yao: Graph entropy and quantum sorting problems. STOC 2004: 112-117 |
2003 | ||
110 | EE | Andrew Chi-Chih Yao: Interactive Proofs for Quantum Computation. ISAAC 2003: 1 |
109 | EE | Fan R. K. Chung, Ronald L. Graham, Jia Mao, Andrew Chi-Chih Yao: Finding Favorites Electronic Colloquium on Computational Complexity (ECCC)(078): (2003) |
108 | EE | Andrew Chi-Chih Yao: Classical physics and the Church-Turing Thesis. J. ACM 50(1): 100-105 (2003) |
2002 | ||
107 | EE | 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 | EE | Andrew Chi-Chih Yao: Classical Physics and the Church-Turing Thesis Electronic Colloquium on Computational Complexity (ECCC)(062): (2002) |
105 | EE | 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 | EE | Andrew Chi-Chih Yao: Some perspective on computational complexity (abstract). STOC 2001: 600 |
2000 | ||
102 | EE | Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao: Quantum bit escrow. STOC 2000: 705-714 |
1999 | ||
101 | EE | Tomoyuki Yamakami, Andrew Chi-Chih Yao: NQPC = co-C=P. Inf. Process. Lett. 71(2): 63-69 (1999) |
1998 | ||
100 | EE | Dominic Mayers, Andrew Chi-Chih Yao: Quantum Cryptography with Imperfect Apparatus. FOCS 1998: 503-509 |
99 | EE | Tomoyuki Yamakami, Andrew Chi-Chih Yao: NQPC = co-C=P CoRR quant-ph/9812032: (1998) |
98 | EE | 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 | EE | Tomoyuki Yamakami, Andrew Chi-Chih Yao: NQP = co-C=P Electronic Colloquium on Computational Complexity (ECCC) 5(73): (1998) |
1997 | ||
96 | EE | 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 | EE | 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 | EE | 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 | EE | Andrew Chi-Chih Yao: Algebraic Decision Trees and Euler Characteristics. Theor. Comput. Sci. 141(1&2): 133-150 (1995) |
86 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Andrew Chi-Chih Yao: Should Tables Be Sorted? J. ACM 28(3): 615-628 (1981) |
33 | EE | 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 | EE | 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 | EE | 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 | EE | Andrew Chi-Chih Yao: New Algorithms for Bin Packing. J. ACM 27(2): 207-227 (1980) |
26 | EE | 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 | EE | 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 | EE | 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 |