Welcome to Yonsei CS theory student group's webpage!
We aim at exploring various aspects of theoretical computer science
while providing a social community for graduate (or undergraduate)
students who are working on (or interested in) theoretical computer
science in (or out of) Yonsei University.
Any questions are welcomed to
yonsei.cs.theory.students@gmail.com.
Summer 2024, Miscellaneous Topics
Organized by Changyeol Lee and Sungmin Kim (Yonsei University)
- Cartesian tree edit distance
- Universal rewriting rules for the Parikh Matrix injectivity problem
- On a generalization of iterated and randomized rounding
- Problems in Compilers
-
Speaker: Kiwoong Jung (Yonsei University)
-
Reference:
[video]
- Introduction to VC-dimension and its applications in combinatorial problems
Spring 2024, Information Theory
Organized by Changyeol Lee and Sungmin Kim (Yonsei University)
- Information Theory: Phase Zero
- Data Compression, Codes and Random Variable Generation
- The Channel Coding Theorem
- Differential Entropy and the Gaussian Channel
- The Rate Distortion Theory
- Information Theory and Statistics
- Kolmogorov Complexity
- Recap session
- Kolmogorov complexity, continued
- The Multi-Armed Bandit Problem
- Information Theory in Practice: the JPEG Algorithm
- The JPEG Algorithm, Continued / Network Coding Theory
- Rate-Distortion-Perception
Winter 2024, Miscellaneous Topics
Organized by Yongho Shin (Yonsei University)
- Asadi et al., Quantum worst-case to average-case reduction for all linear problems
- Talks from KSC 2023
- Quantum max-cut
- Edge-colored clustering in hypergraphs
- Jin and Lu, First price auction is 1-e^-2 efficient
- String edit distance
-
Speaker: Ingyu Baek (Yonsei University)
-
Reference:
[1]
Fall 2023, Quantum Computing
Organized by
SeungYeop Baik (Yonsei University),
Sicheol Sung (Yonsei University), and
Yongho Shin (Yonsei University)
- Week 1. Cancelled
-
Week 2. Introduction to quantum algorithm
-
Speaker:
SeungYeop Baik (Yonsei University)
-
Reference:
[slide],
[video]
-
Week 3. Grover's algorithm
-
Week 4. Simon's algorithm & quantum Fourier transform
-
Week 5. Shor's algorithm
-
Week 6. Quantum basics (wrap-up)
-
Week 7. Quantum finite state automata
- Week 8. Midterm week
-
Week 9. Computability of quantum devices
- Speaker: Hyunjoon Cheon (Yonsei University)
-
Reference:
[slide],
[video]
-
Week 10. Quantum automata cannot detect biased coins, even in the limit
- Week 11. Cancelled
-
Week 12. Quantum computing models (wrap-up)
-
Week 13. Lattice-based cryptography
- Speaker: Lee Hyeob (Yonsei University)
-
Reference:
[video],
[1]
-
Week 14. Quantum approximate optimization algorithm
- Speaker: Gukryeol Lee (Yonsei University)
-
Reference:
[video],
[1]
-
Week 15. Neural network meets quantum
- Week 16. Final week
Spring 2023, Mechanism Design
Organized by Yongho Shin (Yonsei University) and Hyunjoon Cheon (Yonsei University)
- Week 1. VCG mechanism
- Week 2. Optimal mechanism design for the seller's auction design problem
- Week 3. Auction vs negotiation
- Speaker: JaeHyeok Kwak (Yonsei University)
- Reference: [slide], [1], [2]
- Week 4. Hungarian algorithm through the lens of economics
- Week 5. Reinterpretation of optimal auctions
- Speaker: Joonghyuk Hahn (Yonsei University)
- Reference: [slide], [1]
- Week 6. Recapitulation of optimal auctions
- Week 7. Approximate algorithmic pricing via virtual valuations
- Speaker: SeungYeop Baik (Yonsei University)
- Reference: [slide], [1]
- Week 8. Midterm week
- Week 9. Multi-parameter mechanism design and sequential posted pricing
- Speaker: Hyunjoon Cheon (Yonsei University)
- Reference: [slide], [1]
- Week 10. Price of anarchy for auction revenue
- Speaker: Jaehyun Koo (KAIST)
- Reference: [slide], [1]
- Week 11. Bayesian-Nash equilibrium of combinatorial auction
- Week 12. Non-computability in human consciousness
- Week 13. Bayesian and randomized clock auctions
- Speaker: Sicheol Sung (Yonsei University)
- Reference: [slide], [1]
- Week 14. Learning-augmented mechanism design
- Speaker: Gukryeol Lee (Yonsei University)
- Reference: [slide], [1], [2]
- Week 15. Fixed-price approximations in bilateral trade
- Speaker: Sunghyeon Jo (Seoul National University)
- Reference: [slide], [1]
- Week 16. Final week