YONSEI
CS
THEORY
STUDENT
GROUP

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.

Fall 2024, Computational Geometry

Organized by Changyeol Lee and Sungmin Kim (Yonsei University)

  1. Line Segment Intersection
  2. Polygon Triangulation
    • Speaker: Seungyeop Baik (Yonsei University)
    • Reference: [notes], [video]
  3. Orthogonal Range Searching
  4. Klee's Measure Problem
  5. Voronoi Diagrams
  6. Delaunay Triangulation

Summer 2024, Miscellaneous Topics

Organized by Changyeol Lee and Sungmin Kim (Yonsei University)

  1. Cartesian tree edit distance
  2. Universal rewriting rules for the Parikh Matrix injectivity problem
  3. On a generalization of iterated and randomized rounding
  4. Problems in Compilers
    • Speaker: Kiwoong Jung (Yonsei University)
    • Reference: [video]
  5. Introduction to VC-dimension and its applications in combinatorial problems

Spring 2024, Information Theory

Organized by Changyeol Lee and Sungmin Kim (Yonsei University)

  1. Information Theory: Phase Zero
  2. Data Compression, Codes and Random Variable Generation
  3. The Channel Coding Theorem
  4. Differential Entropy and the Gaussian Channel
  5. The Rate Distortion Theory
  6. Information Theory and Statistics
  7. Kolmogorov Complexity
  8. Recap session
  9. Kolmogorov complexity, continued
  10. The Multi-Armed Bandit Problem
  11. Information Theory in Practice: the JPEG Algorithm
  12. The JPEG Algorithm, Continued / Network Coding Theory
  13. Rate-Distortion-Perception

Winter 2024, Miscellaneous Topics

Organized by Yongho Shin (Yonsei University)

  1. Asadi et al., Quantum worst-case to average-case reduction for all linear problems
  2. Talks from KSC 2023
  3. Quantum max-cut
  4. Edge-colored clustering in hypergraphs
  5. Jin and Lu, First price auction is 1-e^-2 efficient
  6. 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
    • Speaker: Sicheol Sung (Yonsei University)
    • Reference: [slide], [video]
  • 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

Built with Skeleton