ผลต่างระหว่างรุ่นของ "ผู้ใช้:Jittat"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 35: แถว 35:
 
** '''Paging.''' Fiat, Karp, Luby, McGeoch, Sleator, and Young.  Competitive paging algorithms.  ''Journal of Algorithms,'' 12:685-699, 1991.
 
** '''Paging.''' Fiat, Karp, Luby, McGeoch, Sleator, and Young.  Competitive paging algorithms.  ''Journal of Algorithms,'' 12:685-699, 1991.
 
** '''Byzantine agreement.''' Rabin.  Randomized Byzantine generals.  In ''Proceedings of the 24th Annual Symposium on Foundations of Computer Science,'' page 403-409, 1983.  (Also, see Chor and Dwork.  Randomization in Byzantine agreement. In ''Randomness and Computing'' pages 433-497. JAI Press, 1989)
 
** '''Byzantine agreement.''' Rabin.  Randomized Byzantine generals.  In ''Proceedings of the 24th Annual Symposium on Foundations of Computer Science,'' page 403-409, 1983.  (Also, see Chor and Dwork.  Randomization in Byzantine agreement. In ''Randomness and Computing'' pages 433-497. JAI Press, 1989)
 +
** '''Min-cut.'''
 +
**# David R. Karger, Clifford Stein. A New Approach to the Minimum Cut Problem. ''J. ACM'' 43(4): 601-640 (1996) [http://portal.acm.org/citation.cfm?doid=234533.234534]
 +
**# David R. Karger: Minimum cuts in near-linear time. ''J. ACM'' 47(1): 46-76 (2000) [http://portal.acm.org/citation.cfm?doid=331605.331608]
 +
** '''Derandomization.''' Nisan and Wigderson.  Hardness vs. randomness. ''Journal of Computer and System Sciences,'' 49(2) pages: 149 - 167, 1994. [http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf]
 +
** '''Zero-knowledge.'''
 +
**# Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems. In ''Proceedings of 17th Symposium on the Theory of Computation,'' Providence, Rhode Island. 1985. [http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf]
 +
**# Oded Goldreich, Silvio Micali, Avi Wigderson. Proofs that yield nothing but their validity. ''Journal of the ACM,'' volume 38, issue 3, p.690-728. July 1991. [http://portal.acm.org/citation.cfm?id=116852]
 
** '''Isolating Lemma.''' Mulmuley, Vazirani, and Vazirani.  Matching is as Easy as Matrix Inversion. in ''Proceedings of Symposium on the Theory of Computing,'' 1987.  ''Combinatorica,'' Vol. 7, No. 1, 1987. [http://www.cs.berkeley.edu/~vazirani/pubs/matching.pdf]
 
** '''Isolating Lemma.''' Mulmuley, Vazirani, and Vazirani.  Matching is as Easy as Matrix Inversion. in ''Proceedings of Symposium on the Theory of Computing,'' 1987.  ''Combinatorica,'' Vol. 7, No. 1, 1987. [http://www.cs.berkeley.edu/~vazirani/pubs/matching.pdf]
 
** '''Primality testing.'''
 
** '''Primality testing.'''

รุ่นแก้ไขเมื่อ 16:38, 15 พฤศจิกายน 2550

My bookmarks

Dynamic Programming Languages Bookmark

Teen and Tech bookmark

Media & Interactive

News

Blogs

Twitter

Reading groups

  • Randomized Algorithms. Focus on classic results. Some of the papers and references below are from Motwani and Raghavan.
    • Routing. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11:350-361, 1982. (Should be available at AIT Library)
    • Paging. Fiat, Karp, Luby, McGeoch, Sleator, and Young. Competitive paging algorithms. Journal of Algorithms, 12:685-699, 1991.
    • Byzantine agreement. Rabin. Randomized Byzantine generals. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science, page 403-409, 1983. (Also, see Chor and Dwork. Randomization in Byzantine agreement. In Randomness and Computing pages 433-497. JAI Press, 1989)
    • Min-cut.
      1. David R. Karger, Clifford Stein. A New Approach to the Minimum Cut Problem. J. ACM 43(4): 601-640 (1996) [1]
      2. David R. Karger: Minimum cuts in near-linear time. J. ACM 47(1): 46-76 (2000) [2]
    • Derandomization. Nisan and Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49(2) pages: 149 - 167, 1994. [3]
    • Zero-knowledge.
      1. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems. In Proceedings of 17th Symposium on the Theory of Computation, Providence, Rhode Island. 1985. [4]
      2. Oded Goldreich, Silvio Micali, Avi Wigderson. Proofs that yield nothing but their validity. Journal of the ACM, volume 38, issue 3, p.690-728. July 1991. [5]
    • Isolating Lemma. Mulmuley, Vazirani, and Vazirani. Matching is as Easy as Matrix Inversion. in Proceedings of Symposium on the Theory of Computing, 1987. Combinatorica, Vol. 7, No. 1, 1987. [6]
    • Primality testing.
    • Lovasz Local Lemma.

Other possible topics:

  • Algorithmic Game Theory:
    • Probably following [7]
  • Distributed Computing: selection from [8]
ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=ผู้ใช้:Jittat&oldid=3826"