dblp.uni-trier.dewww.uni-trier.de

Andrew Chi-Chih Yao Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
128EEAndrew Chi-Chih Yao: Communication Complexity and Its Applications. FAW 2009: 2
127EEXiaoming Sun, Andrew Chi-Chih Yao: On the Quantum Query Complexity of Local Search in Two and Three Dimensions. Algorithmica 55(3): 576-600 (2009)
126EEAndrew 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)
125EEAndrew 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
124EEXiaoming Sun, Andrew Chi-Chih Yao, Christophe Tartary: Graph Design for Secure Multiparty Computation over Non-Abelian Groups. ASIACRYPT 2008: 37-53
123EEAndrew Chi-Chih Yao: Some Perspectives on Complexity-Based Cryptography. ASIACRYPT 2008: 54
122EETsuyoshi 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
121EEAndrew Chi-Chih Yao, Frances F. Yao, Yunlei Zhao: A Note on Universal Composable Zero Knowledge in Common Reference String Model. TAMC 2007: 462-473
120EEAndrew Chi-Chih Yao, Frances F. Yao, Yunlei Zhao: A Note on the Feasibility of Generalized Universal Composability. TAMC 2007: 474-485
119EEFan 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
118EEXiaoming Sun, Andrew Chi-Chih Yao: On the Quantum Query Complexity of Local Search in Two and Three Dimensions. FOCS 2006: 429-438
117EEAndrew Chi-Chih Yao: Recent Progress in Quantum Computational Complexity. TAMC 2006: 89-89
2005
116EEFan 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
115EEAndrew Chi-Chih Yao: On the Communication Complexity of Co-linearity Problems. MFCS 2005: 57
2004
114EENing Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao: Fisher Equilibrium Price with a Class of Concave Utility Functions. ESA 2004: 169-179
113EENing Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao: Dynamic Price Sequence and Incentive Compatibility (Extended Abstract). ICALP 2004: 320-331
112EEXiaoming 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
111EEAndrew Chi-Chih Yao: Graph entropy and quantum sorting problems. STOC 2004: 112-117
2003
110EEAndrew Chi-Chih Yao: Interactive Proofs for Quantum Computation. ISAAC 2003: 1
109EEFan R. K. Chung, Ronald L. Graham, Jia Mao, Andrew Chi-Chih Yao: Finding Favorites Electronic Colloquium on Computational Complexity (ECCC)(078): (2003)
108EEAndrew Chi-Chih Yao: Classical physics and the Church-Turing Thesis. J. ACM 50(1): 100-105 (2003)
2002
107EEAlexander 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)
106EEAndrew Chi-Chih Yao: Classical Physics and the Church-Turing Thesis Electronic Colloquium on Computational Complexity (ECCC)(062): (2002)
105EEAndrew 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
103EEAndrew Chi-Chih Yao: Some perspective on computational complexity (abstract). STOC 2001: 600
2000
102EEDorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao: Quantum bit escrow. STOC 2000: 705-714
1999
101EETomoyuki Yamakami, Andrew Chi-Chih Yao: NQPC = co-C=P. Inf. Process. Lett. 71(2): 63-69 (1999)
1998
100EEDominic Mayers, Andrew Chi-Chih Yao: Quantum Cryptography with Imperfect Apparatus. FOCS 1998: 503-509
99EETomoyuki Yamakami, Andrew Chi-Chih Yao: NQPC = co-C=P CoRR quant-ph/9812032: (1998)
98EEDima 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)
97EETomoyuki Yamakami, Andrew Chi-Chih Yao: NQP = co-C=P Electronic Colloquium on Computational Complexity (ECCC) 5(73): (1998)
1997
96EEAlexander 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
93EEAndrew 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
91EEAndrew 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)
89EEDima 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)
87EEAndrew Chi-Chih Yao: Algebraic Decision Trees and Euler Characteristics. Theor. Comput. Sci. 141(1&2): 133-150 (1995)
86EEJohan 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
84EEAndrew 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
74EESampath 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
56EEAndrew 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
44EEAndrew 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)
34EEAndrew Chi-Chih Yao: Should Tables Be Sorted? J. ACM 28(3): 615-628 (1981)
33EEAndrew 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
31EEJon 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)
28EERichard J. Lipton, Arnold L. Rosenberg, Andrew Chi-Chih Yao: External Hashing Schemes for Collections of Data Structures. J. ACM 27(1): 81-95 (1980)
27EEAndrew Chi-Chih Yao: New Algorithms for Bin Packing. J. ACM 27(2): 207-227 (1980)
26EERonald 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)
15EEAndrew 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)
7EEAndrew 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

Coauthor Index

1Dorit Aharonov [102]
2David Avis [12]
3Jon Louis Bentley [8] [31]
4Anders Björner [76]
5Allan Borodin [35]
6Jin-yi Cai [80]
7Amit Chakrabarti [104]
8Ning Chen [113] [114]
9Fan R. K. Chung (Fan Chung Graham) [109] [116] [119]
10Edward G. Coffman Jr. [29]
11Xiaotie Deng [113] [114]
12Danny Dolev [38] [49]
13Shafi Goldwasser [48] [50]
14Ronald L. Graham [26] [65] [109] [116] [119]
15Dima Grigoriev [88] [89] [98]
16Leonidas J. Guibas [35]
17Johan Håstad [86]
18Micha Hofri [29]
19Tsuyoshi Ito [122]
20Ravi Kannan (Ravindran Kannan) [78]
21Sampath Kannan [74]
22Marek Karpinski [89] [98]
23Hirotada Kobayashi [122]
24Richard J. Lipton [28] [80]
25László Lovász [76]
26Nancy A. Lynch [35]
27Jia Mao [109] [116] [119]
28Claire Mathieu (Claire Kenyon, Claire Kenyon-Mathieu) [68]
29Dominic Mayers [100]
30Silvio Micali [48] [50]
31Daniel Preda [122]
32Alexander A. Razborov [86] [96] [107]
33Ronald L. Rivest [10] [12] [15] [24]
34Arnold L. Rosenberg [28]
35Robert Sedgewick [42] [80]
36Yaoyun Shi [104]
37Michael F. Singer [88]
38Kimming So [29]
39J. Michael Steele [43]
40Xiaoming Sun [112] [113] [114] [118] [122] [124] [127]
41Thomas G. Szymanski [42]
42Amnon Ta-Shma [102]
43Robert Endre Tarjan [21]
44Christophe Tartary [124]
45Hing-Fung Ting (H. F. Ting) [83]
46Umesh V. Vazirani [102]
47H. Venkateswaran [78]
48V. Vinay [78]
49Bruce W. Weide [31]
50Avi Wigderson [96] [107]
51Anthony Wirth [104]
52Tomoyuki Yamakami [97] [99] [101]
53F. Frances Yao (Frances F. Yao, Foong Frances Yao) [7] [11] [17] [26] [41] [54] [57] [92] [95] [120] [121] [125] [126]
54Shengyu Zhang [112]
55Yunlei Zhao [120] [121] [125] [126]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)