Prezentácie

• ku koncu semestra si každý zvolí jeden odborný článok z oblasti pravdepodobnostných algoritmov a ten odprezentuje spolužiakom počas prednášky
• cieľom prezentácie je precvičiť si prácu s odbornou literatúrou, prezentovanie a hlavne oboznámiť sa s ďalšími peknými výsledkami, na ktoré žiaľ na prednáške nie je čas

Rezervované články

Tu bude postupne pribúdať zoznam ľudí, rezervovaných článkov a dátumov.

Rady k prezentácii

• na prezentáciu budete mať ≤ 18 minút, pričom tento limit bude striktne dodržiavaný - nechystajte si teda priveľa materiálu, rátajte aspoň 1,5 minúty na slajd
• prezentáciu si skúste povedať doma "na nečisto" a pritom si odstopovať čas
• k dispozícii bude dátový projektor; prezentáciu v pdf formáte si doneste na USB kľúči alebo pošlite mailom deň vopred
• môžete použiť tabuľu, ale s mierou, lebo vysvetľovanie pri tabuli ide pomalšie
• hlavným cieľom je porozprávať niečo zaujímavé z vášho článku vo forme prístupnej vašim spolužiakom
• nemusíte pokryť celý obsah článku a nemusíte použiť rovnaké poradie, označenie alebo príklady, ako autori článku
• nedávajte na slidy veľa textu, použite dostatočne veľký font a dobre viditeľné farby (podobné farby, napr. žltá na bielej, nemusia byť na projektore vôbec viditeľné).
• použite čo najmenej definícií a označenia; pojmy, algoritmy a dôkazy radšej ilustrujte na obrázku alebo príklade, než zložitým textom

Príklady článkov

• sem postupne pribudnú články vhodné na prezentáciu
• môžete si vybrať jeden z nasledujúcich článkov, ale môžete si tiež nájsť vhodný článok sami

Koncentrácia náhodnej premennej

• Impagliazzo, R., & Kabanets, V. (2010). Constructive proofs of concentration bounds. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 617-631.
• Richa, A. W., Mitzenmacher, M., & Sitaraman, R. (2001). The power of two random choices: A survey of techniques and results. COMBINATORIAL OPTIMIZATION, 9, 255-304.
• McDiarmid, C., & Hayward, R. (1992). Strong concentration for quicksort. In Proceedings 3rd ACM-SIAM SODA (Vol. 414, p. 421).
• Karp, R. M. (1994). Probabilistic recurrence relations. Journal of the ACM (JACM), 41(6), 1136-1150.

Triedenie a vyhľadávanie

• Herlihy, M., Lev, Y., Luchangco, V., & Shavit, N. (2006). A provably correct scalable concurrent skip list. In Conference On Principles of Distributed Systems (OPODIS).
• Goodrich, M. T. (2010, January). Randomized Shellsort: A simple oblivious sorting algorithm. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1262-1277). Society for Industrial and Applied Mathematics.
• Bader, D. A. (2004). An improved, randomized algorithm for parallel selection with an experimental study. Journal of Parallel and Distributed Computing,64(9), 1051-1059.

Zdroje náhodných bitov

• Dvir, Z., & Wigderson, A. (2011). Kakeya sets, new mergers, and old extractors. SIAM Journal on Computing, 40(3), 778-792.
• Vazirani, U. V., & Vazirani, V. V. (1985, October). Random polynomial time is equal to semi-random polynomial time. In Foundations of Computer Science, 1985., 26th Annual Symposium on (pp. 417-428). IEEE.
• Kalai, Y. T., Li, X., & Rao, A. (2009, October). 2-source extractors under computational assumptions and cryptography with defective randomness. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on (pp. 617-626). IEEE.
• Trevisan, L. (2001). Extractors and pseudorandom generators. Journal of the ACM, 48(4), 860-879.

Hešovanie

• Broder, A., & Mitzenmacher, M. (2004). Network applications of bloom filters: A survey. Internet Mathematics, 1(4), 485-509.
• Karger, D., et al. (1999). Web caching with consistent hashing. Computer Networks, 31(11), 1203-1213. + teória za tým: Karger, D., et al. (1997). Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (pp. 654-663). ACM.
• Shakhnarovich, G., Darrell, T., & Indyk, P. (2006). Nearest-neighbor methods in learning and vision: theory and practice.
• Har-Peled, S., Indyk, P., & Motwani, R. (2012). Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory OF Computing, 8, 321-350.
  • Pagh, R., & Rodler, F. F. (2004). Cuckoo hashing. Journal of Algorithms, 51(2), 122-144.
• Dietzfelbinger, M., & Schellbach, U. (2009, January). On risks of using cuckoo hashing with simple universal hash classes. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 795-804). Society for Industrial and Applied Mathematics.
• Thorup, M., & Zhang, Y. (2009). Tabulation based 5-universal hashing and linear probing. In Proc. 12th Workshop on Algorithm Engineering and Experiments (ALENEX).

Geometria

• Birn, M., Holtgrewe, M., Sanders, P., & Singler, J. (2010). Simple and fast nearest neighbor search. In 2010 Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments, January (Vol. 16, pp. 43-54).
• Friedmann, O., Hansen, T. D., & Zwick, U. (2010). Subexponential lower bounds for randomized pivoting rules for solving linear programs.

Grafové algoritmy

• Katriel, I., Sanders, P., & Träff, J. L. (2003). A practical minimum spanning tree algorithm using the cycle property. (pp. 679-690). Springer Berlin Heidelberg.
• Aggarwal, A., & Anderson, R. (1987, January). A random NC algorithm for depth first search. In Proceedings of the nineteenth annual ACM symposium on Theory of computing (pp. 325-334). ACM.

Streamové algoritmy

• Charikar, M., Chen, K., & Farach-Colton, M. (2002). Finding frequent items in data streams. Automata, Languages and Programming, 784-784.
• Alon, N., Matias, Y., & Szegedy, M. (1996, July). The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 20-29). ACM.
• Van Durme, B., & Lall, A. (2009, July). Probabilistic counting with randomized storage. In IJCAI’09: Proceedings of the 21st international jont conference on Artifical intelligence (pp. 1574-1579).

SAT

• Paturi, R., Pudlák, P., Saks, M. E., & Zane, F. (2005). An improved exponential-time algorithm for k-SAT. Journal of the ACM (JACM), 52(3), 337-364.
• Karloff, H., & Zwick, U. (1997, October). A 7/8-approximation algorithm for MAX 3SAT?. In Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on (pp. 406-415). IEEE.

Náhodné prechádzky, odporúčacie systémy, PageRank a pod.

• Jeh, G., & Widom, J. (2003, May). Scaling personalized web search. In Proceedings of the 12th international conference on World Wide Web (pp. 271-279). ACM.
  • Gori, M., Pucci, A., Roma, V., & Siena, I. (2007, January). Itemrank: A random-walk based scoring algorithm for recommender engines. In Proceedings of the 20th international joint conference on Artificial intelligence(pp. 2766-2771). Morgan Kaufmann Publishers Inc.
• Gyöngyi, Z., Garcia-Molina, H., & Pedersen, J. (2004, August). Combating web spam with TrustRank. In Proceedings of the Thirtieth international conference on Very large data bases-Volume 30 (pp. 576-587). VLDB Endowment.
• Ng, A. Y., Zheng, A. X., & Jordan, M. I. (2001, September). Stable algorithms for link analysis. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval (pp. 258-266). ACM.
• Brand, M. (2005, May). A random walks perspective on maximizing satisfaction and profit. In SIAM International Conference on Data Mining (pp. 12-19).
• Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5), 604-632.

MCMC

• Gallagher, K., Charvin, K., Nielsen, S., Sambridge, M., & Stephenson, J. (2009). Markov chain Monte Carlo (MCMC) sampling methods to determine optimal models, model resolution and model choice for Earth Science problems. Marine and Petroleum Geology, 26(4), 525-535.
• Hanhijärvi, S., Garriga, G., & Puolamäki, K. (2009). Randomization techniques for graphs.
• Lunter, G., Miklós, I., Drummond, A., Jensen, J. L., & Hein, J. (2005). Bayesian coestimation of phylogeny and sequence alignment. BMC Bioinformatics, 6(1), 83.
• Meyer, I. M., & Miklós, I. (2007). SimulFold: simultaneously inferring RNA structures including pseudoknots, alignments, and trees using a Bayesian MCMC framework. PLoS computational biology, 3(8), e149.
• Bhatnagar, N., Bogdanov, A., & Mossel, E. (2010). The computational complexity of estimating convergence time. arXiv preprint arXiv:1007.0089.

FOJA

• Hromkovič, J., & Schnitger, G. (2010). On probabilistic pushdown automata. Information and Computation, 208(8), 982-995.
• Kiefer, S., Murawski, A., Ouaknine, J., Wachter, B., & Worrell, J. (2011). Language equivalence for probabilistic automata. In Computer Aided Verification (pp. 526-540). Springer Berlin/Heidelberg.
• Dwork, C., & Stockmeyer, L. (1990). A time complexity gap for two-way probabilistic finite-state automata. SIAM Journal on Computing, 19(6), 1011-1023.
• Condon, A., Hellerstein, L., Pottle, S., & Wigderson, A. (1998). On the power of finite automata with both nondeterministic and probabilistic states. SIAM Journal on Computing, 27(3), 739-762.

Teória zložitosti

• Meir, O. (2013). IP= PSPACE Using Error-Correcting Codes. SIAM Journal on Computing, 42(1), 380-403.
  • Gat, E., & Goldwasser, S. (2011). Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications. In Electronic Colloquium on Computational Complexity (ECCC) (Vol. 18, p. 136).
  • Goldreich, O. (2011). In a world of P= BPP. Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 191-232.
• Zuckerman, D. (1996). Simulating BPP using a general weak random source. Algorithmica, 16(4), 367-391.
• Nisan, N., & Zuckerman, D. (1993). Randomness is linear in space. In Symposium on Theory of Computing (pp. 235-244).
• Luby, M., Sinclair, A., & Zuckerman, D. (1993). Optimal speedup of Las Vegas algorithms. Information Processing Letters, 47(4), 173-180.
• Papadimitriou, C. H. (1985). Games against nature. Journal of Computer and System Sciences, 31(2), 288-301.

Interaktívne systémy

• Condon, A., Feigenbaum, J., Lund, C., & Shor, P. Probabilistically Checkable Debate Systems and Nonapproximability Results for PSPACE-Hard Functions. Chicago J. Theoretical Computer Science, 1995(4).
• Condon, A., Feigenbaum, J., Lund, C., & Shor, P. (1997). Random debaters and the hardness of approximating stochastic functions. SIAM Journal on Computing, 26(2), 369-400.
• Dwork, C., & Stockmeyer, L. (1992). Finite state verifiers I: the power of interaction. Journal of the ACM (JACM), 39(4), 800-828.
• Fortnow, L., Rompel, J., & Sipser, M. (1994). On the power of multi-prover interactive protocols. Theoretical Computer Science, 134(2), 545-557.
  • Babai, L., Fortnow, L., & Lund, C. (1991). Non-deterministic exponential time has two-prover interactive protocols. Computational complexity, 1(1), 3-40.

Derandomizácia

• Alon, N., & Naor, M. (1996). Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica, 16(4), 434-449.
• Kinne, J., Van Melkebeek, D., & Shaltiel, R. (2009). Pseudorandom generators and typically-correct derandomization. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 574-587.
• Goldreich, O., Vadhan, S., & Wigderson, A. (2000, January). Simplified derandomization of BPP using a hitting set generator. In Electronic Colloquium on Computational Complexity (Vol. 7, No. 4).
• Aaronson, S., & van Melkebeek, D. (2010, June). A note on circuit lower bounds from derandomization. In Electronic Colloquium on Computational Complexity (ECCC) (Vol. 17, p. 105).
• Arvind, V., & Mukhopadhyay, P. (2008). Derandomizing the isolation lemma and lower bounds for circuit size. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 276-289.
• Sivakumar, D. (2002, May). Algorithmic derandomization via complexity theory. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (pp. 619-626). ACM.
• Naor, J., & Naor, M. (1993). Small-bias probability spaces: efficient constructions and applications. SIAM journal on computing, 22(4), 838-856.
• Alon, N., Goldreich, O., Håstad, J., & Peralta, R. (1992). Simple Constructions of Almost k‐wise Independent Random Variables. Random Structures & Algorithms, 3(3), 289-304.
• Kabanets, V., & Impagliazzo, R. (2003, June). Derandomizing polynomial identity tests means proving circuit lower bounds. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (pp. 355-364). ACM.

Rôzne

• Harvey, N. J., Jones, M. B., Saroiu, S., Theimer, M., & Wolman, A. (2003, March). Skipnet: A scalable overlay network with practical locality properties. In Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems (Vol. 4, pp. 9-9).
• Jansen, A., & Van Durme, B. (2011, December). Efficient spoken term discovery using randomized algorithms. In Automatic Speech Recognition and Understanding (ASRU), 2011 IEEE Workshop on (pp. 401-406). IEEE.
• Chandrasekaran, K., & Karp, R. (2012). Finding the most biased coin with fewest flips. arXiv preprint arXiv:1202.3639.
• Raghavan, P. (1988). Probabilistic construction of deterministic algorithms: approximating packing integer programs. Journal of Computer and System Sciences, 37(2), 130-143.
• Valiant, L. G., & Brebner, G. J. (1981, May). Universal schemes for parallel communication. In Proceedings of the thirteenth annual ACM symposium on Theory of computing (pp. 263-277). ACM.