Posts

• Recent Posts

  • 2025-03-14 C1: Lower Bounds for Distributed MST
  • 2025-03-07 C1: Distributed Coloring (0-2): Revisit Basic Coloring Algorithms
  • 2025-03-04 C1: Distributed Coloring (2): Rubin's Block Lemma
  • 2025-03-03 C1: Distributed Coloring (1): Degree Choosable Component (DCC)
  • 2025-02-19 T1: Basics on Quantum Computing
  • 2025-02-18 C1: Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
  • 2025-02-12 T1: Finite Field
  • 2025-02-06 T1: PRAM Model: All Basics
  • 2025-01-19 A: My Poem (3): Rainy Day
  • 2025-01-17 T1: Measure Theory 01
• 2025

  • 2025-03

    • 2025-03-14 C1: Lower Bounds for Distributed MST
    • 2025-03-07 C1: Distributed Coloring (0-2): Revisit Basic Coloring Algorithms
    • 2025-03-04 C1: Distributed Coloring (2): Rubin's Block Lemma
    • 2025-03-03 C1: Distributed Coloring (1): Degree Choosable Component (DCC)
  • 2025-02

    • 2025-02-19 T1: Basics on Quantum Computing
    • 2025-02-18 C1: Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
    • 2025-02-12 T1: Finite Field
    • 2025-02-06 T1: PRAM Model: All Basics
  • 2025-01

    • 2025-01-19 A: My Poem (3): Rainy Day
    • 2025-01-17 T1: Measure Theory 01
    • 2025-01-13 T1: The Corruption Method in Communication Complexity (2)
    • 2025-01-09 T1: The Corruption Method in Communication Complexity (1)
• 2024

  • 2024-12

    • 2024-12-31 A: My Poem (2): I suddenly understand the art
    • 2024-12-31 T1: Infimum and Minimum
    • 2024-12-27 C1: Direct Sums in Communication Complexity
    • 2024-12-25 C1: One-Way Communication Complexity
    • 2024-12-21 C1: The Augmented Indexing Problem
    • 2024-12-20 C1: The Indexing Problem: Different Proofs (3)
    • 2024-12-18 T1: The reasons why you do not understand the theory papers
    • 2024-12-15 C1: The Indexing Problem: Different Proofs (2)
    • 2024-12-14 T1: Entropy and Counting
    • 2024-12-12 C1: The Indexing Problem: Different Proofs (1)
  • 2024-11

    • 2024-11-19 C1: Random Walks on Expander Graphs (1)
    • 2024-11-12 T1: The Law of total probability and Tower Rule
    • 2024-11-03 C1: Where does the Isolating Lemma come from?
    • 2024-11-01 C1: Fast Parallel Matrix Inversion Algorithms
  • 2024-10

    • 2024-10-30 C1: Constructing a perfect matching is RNC
    • 2024-10-09 T1: Total Variation Distance
  • 2024-09

    • 2024-09-06 T1: A Paper being Rejected
    • 2024-09-06 T1: A Simple Question on Ruzsa-Szemerédi Graphs
    • 2024-09-02 C1: Multi-party Communication Model Applications (4)
  • 2024-08

    • 2024-08-28 T1: KL Divergence and Mutual Information
    • 2024-08-24 C1: Multi-party Communication Model Applications (3): Welfare maximization with limited interaction
    • 2024-08-21 T1: Some Definitions in Property Testing
    • 2024-08-20 C1: Multi-party Communication Model Applications (2)
    • 2024-08-16 C1: Multi-party Communication Model Applications (1): Lower bounds for distributed sketching of maximal matchings and maximal independent sets
    • 2024-08-14 T1: Multi-party Communication Model (NOF)
    • 2024-08-13 T1: Basics about Mutual Information
    • 2024-08-13 T1: Compress Interactive Communication (2)
    • 2024-08-12 C1: An MIS Lower bound in Semi-Streaming Model
    • 2024-08-01 C1: A Speedup Theorem (a technique for lower bounds)
  • 2024-07

    • 2024-07-31 C1: What Can be Computed Locally?
    • 2024-07-30 T1: Bipartite Expander Graphs
    • 2024-07-25 T1: Basic Techniques in Property Testing
    • 2024-07-25 C1: Network Decomposition (2)
    • 2024-07-24 C1: Monotonicity Testing
    • 2024-07-19 C1: Network Decomposition (Low-Diameter Graph Decomposition)
    • 2024-07-19 T1: Discrepancy (2)
    • 2024-07-18 T1: A Simple Question 2: Parseval's Inequality
    • 2024-07-18 T1: Eigenvectors of a Symmetric Matrix
    • 2024-07-17 T1: A Simple Question 1
    • 2024-07-16 T1: Eigenvalues and Eigenvectors
    • 2024-07-15 T1: Discrepancy (1)
    • 2024-07-14 T1: Vector Norms and Matrix Norms
    • 2024-07-12 T1: Algebraic Matching Algorithms (1)
    • 2024-07-12 T1: What is Determinant
    • 2024-07-10 T1: Distributed Algorithms on Coloring (0)
    • 2024-07-09 T1: Coding Theory (2)
  • 2024-06

    • 2024-06-29 T1: Basics about Entropy
    • 2024-06-28 C1: Distributed Algorithms on Ruling Sets
    • 2024-06-27 C1: Distributed Computation in Node-Capacitated Networks
    • 2024-06-01 T1: Coding Theory (1)
  • 2024-05

    • 2024-05-23 C1: Cell probe complexity - a survey
    • 2024-05-23 C1: Bloom Filter
    • 2024-05-15 A: My Poem (1): Bones
    • 2024-05-12 P1: Open Problems In Theory of Computer Science
    • 2024-05-11 B1: Paradigms for Randomized Algorithms
    • 2024-05-07 T1: Some Facts on Matching (1)
    • 2024-05-06 T1: More than Counting
    • 2024-05-05 T1: Some Inequalities on Random Graphs
    • 2024-05-02 C1: Parallel Balls-into-Bins
  • 2024-04

    • 2024-04-24 C1: Distributed Balls-and-Bins
    • 2024-04-20 C1: Static EDCS
    • 2024-04-10 C1: Combinatorial Correlation Clustering
    • 2024-04-08 C1: Compress Interactive Communication (1)
    • 2024-04-04 C1: EDCS in Distributed Settings
    • 2024-04-02 C1: Communication Complexity of Disjointness using Entropy Theory
    • 2024-04-01 T1: Fooling Sets
  • 2024-03

    • 2024-03-29 C1: Distributional Disjointness (Non information theory)
    • 2024-03-28 C1: Pointer Chasing Problem
    • 2024-03-23 T1: Two Important Distances
    • 2024-03-20 C1: Lower Bounds for Set Disjointness (for product distribution)
    • 2024-03-20 C1: Yao's minimax principle
    • 2024-03-16 C1: A little advice can be very helpful!
    • 2024-03-14 C1: Private Coins and Public Coins
    • 2024-03-02 T1: Measure Theory