Sijing Tu
@sijingtu.bsky.social
I recently graduated from KTH Royal Institute of Technology.
I work on (am interested in) social network analysis, approximation algorithms, information propagation dynamics, opinion formation dynamics.
I work on (am interested in) social network analysis, approximation algorithms, information propagation dynamics, opinion formation dynamics.
A very nice summary by Stefan of our recent publication "Optirefine: densest subgraphs and maximum cuts with k refinements". With @stefanresearch.bsky.social, Aleksa Stankovic, and @aris-gionis.bsky.social
Suppose you are given a non-optimal solution to an algorithmic problem and you want to make a small number of changes to improve its objective function.
We give nearly-optimal approximation algorithms for this problem for Max-Cut and for Densest Subgraph.
link.springer.com/article/10.1...
We give nearly-optimal approximation algorithms for this problem for Max-Cut and for Densest Subgraph.
link.springer.com/article/10.1...
Optirefine: densest subgraphs and maximum cuts with k refinements - Data Mining and Knowledge Discovery
Data-analysis tasks often involve an iterative process, which requires refining previous solutions. For instance, when analyzing social networks, we may obtain initial communities based on noisy metad...
link.springer.com
September 12, 2025 at 1:36 PM
A very nice summary by Stefan of our recent publication "Optirefine: densest subgraphs and maximum cuts with k refinements". With @stefanresearch.bsky.social, Aleksa Stankovic, and @aris-gionis.bsky.social
Reposted by Sijing Tu
I love this paper by Bill Kuszmaul.
His proof of Chernoff bound is much more illuminating than the standard algebraic proof I learned.
His proof of Chernoff bound is much more illuminating than the standard algebraic proof I learned.
A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
The Chernoff bound is one of the most widely used tools in theoretical computer science. It's rare to find a randomized algorithm that doesn't employ a Chernoff bound in its analysis. The standard pro...
arxiv.org
January 12, 2025 at 9:37 AM
I love this paper by Bill Kuszmaul.
His proof of Chernoff bound is much more illuminating than the standard algebraic proof I learned.
His proof of Chernoff bound is much more illuminating than the standard algebraic proof I learned.
Reposted by Sijing Tu
"By strategically targeting a subset of individuals with the appropriate intervention, governments, aid agencies, and NGOs may find a more cost-effective way to diffuse new products." Yes, this is true. For more, see:
www.thelancet.com/journals/lan...
www.science.org/doi/10.1126/...
www.thelancet.com/journals/lan...
www.science.org/doi/10.1126/...
Induction of social contagion for diverse outcomes in structured experiments in isolated villages
Certain people occupy topological positions within social networks that enhance their effectiveness at inducing spillovers. We mapped face-to-face networks among 24,702 people in 176 isolated villages...
www.science.org
December 27, 2024 at 2:40 PM
"By strategically targeting a subset of individuals with the appropriate intervention, governments, aid agencies, and NGOs may find a more cost-effective way to diffuse new products." Yes, this is true. For more, see:
www.thelancet.com/journals/lan...
www.science.org/doi/10.1126/...
www.thelancet.com/journals/lan...
www.science.org/doi/10.1126/...
Reposted by Sijing Tu
Found slides by Ankur Moitra (presented at a TCS For All event) on "How to do theoretical research." Full of great advice!
My favourite: "Find the easiest problem you can't solve. The more embarrassing, the better!"
Slides: drive.google.com/file/d/15VaT...
TCS For all: sigact.org/tcsforall/
My favourite: "Find the easiest problem you can't solve. The more embarrassing, the better!"
Slides: drive.google.com/file/d/15VaT...
TCS For all: sigact.org/tcsforall/
December 13, 2024 at 8:31 PM
Found slides by Ankur Moitra (presented at a TCS For All event) on "How to do theoretical research." Full of great advice!
My favourite: "Find the easiest problem you can't solve. The more embarrassing, the better!"
Slides: drive.google.com/file/d/15VaT...
TCS For all: sigact.org/tcsforall/
My favourite: "Find the easiest problem you can't solve. The more embarrassing, the better!"
Slides: drive.google.com/file/d/15VaT...
TCS For all: sigact.org/tcsforall/
Reposted by Sijing Tu
In work out in December 2024, Matt Jones and I conduct experiments to study the role of leadership within factions of larger groups of people who are struggling to reach consensus on a contentious topic.
www.nature.com/articles/s41... @natureportfolio.bsky.social 1/
www.nature.com/articles/s41... @natureportfolio.bsky.social 1/
Bringing leaders of network subgroups closer together does not facilitate consensus - Scientific Reports
Scientific Reports - Bringing leaders of network subgroups closer together does not facilitate consensus
www.nature.com
December 6, 2024 at 1:32 PM
In work out in December 2024, Matt Jones and I conduct experiments to study the role of leadership within factions of larger groups of people who are struggling to reach consensus on a contentious topic.
www.nature.com/articles/s41... @natureportfolio.bsky.social 1/
www.nature.com/articles/s41... @natureportfolio.bsky.social 1/
Reposted by Sijing Tu
A little tired, so going back to one of my "favorite" results about Poisson random variables: Bennett-style concentration inequalities, both for upper and lower tails.
Now, why do I like it? Besides its usefulness, one of the proofs is really insightful and cute (IMO). (I didn't come up with it.)
Now, why do I like it? Besides its usefulness, one of the proofs is really insightful and cute (IMO). (I didn't come up with it.)
December 5, 2024 at 1:29 AM
A little tired, so going back to one of my "favorite" results about Poisson random variables: Bennett-style concentration inequalities, both for upper and lower tails.
Now, why do I like it? Besides its usefulness, one of the proofs is really insightful and cute (IMO). (I didn't come up with it.)
Now, why do I like it? Besides its usefulness, one of the proofs is really insightful and cute (IMO). (I didn't come up with it.)
Reposted by Sijing Tu
An advent calendar of some of my favourite TCS/Maths talks. Day #1: Avi Wigderson on Reading Alan Turing.
It is a gem of a talk, full of insights about Turing's work, writing style, and influences on mathematics and computer science. Pure joy!
www.youtube.com/watch?v=_Uk_...
It is a gem of a talk, full of insights about Turing's work, writing style, and influences on mathematics and computer science. Pure joy!
www.youtube.com/watch?v=_Uk_...
Reading Alan Turing - Avi Wigderson
YouTube video by Institute for Advanced Study
www.youtube.com
December 1, 2024 at 12:22 PM
An advent calendar of some of my favourite TCS/Maths talks. Day #1: Avi Wigderson on Reading Alan Turing.
It is a gem of a talk, full of insights about Turing's work, writing style, and influences on mathematics and computer science. Pure joy!
www.youtube.com/watch?v=_Uk_...
It is a gem of a talk, full of insights about Turing's work, writing style, and influences on mathematics and computer science. Pure joy!
www.youtube.com/watch?v=_Uk_...
Reposted by Sijing Tu
This conversation is the teaching version of a longstanding debate in TCS: is theory worthwhile per se, or should it always be motivated by applications? In the mid-90s, there was a famous debate about this between two pairs of TCS luminaries: blog.computationalcomplexity.org/2016/06/karp.... 1/
November 27, 2024 at 6:48 PM
This conversation is the teaching version of a longstanding debate in TCS: is theory worthwhile per se, or should it always be motivated by applications? In the mid-90s, there was a famous debate about this between two pairs of TCS luminaries: blog.computationalcomplexity.org/2016/06/karp.... 1/
Reposted by Sijing Tu
Cool paper on political sorting in the US labor market, based on an inventive effort merging LinkedIn profiles with public voter files to create a panel of 35 million Americans with information about employment and political party registration. sahilchinoy.s3.us-west-1.amazonaws.com/chinoy_polit...
November 19, 2024 at 2:21 PM
Cool paper on political sorting in the US labor market, based on an inventive effort merging LinkedIn profiles with public voter files to create a panel of 35 million Americans with information about employment and political party registration. sahilchinoy.s3.us-west-1.amazonaws.com/chinoy_polit...
Reposted by Sijing Tu
Your friends have more friends than you do. This is known as the "friendship paradox."
But, thankfully, your enemies have more enemies than you do, too. In 2023, we called this the "enmity paradox." 1/
But, thankfully, your enemies have more enemies than you do, too. In 2023, we called this the "enmity paradox." 1/
November 23, 2024 at 3:21 PM
Your friends have more friends than you do. This is known as the "friendship paradox."
But, thankfully, your enemies have more enemies than you do, too. In 2023, we called this the "enmity paradox." 1/
But, thankfully, your enemies have more enemies than you do, too. In 2023, we called this the "enmity paradox." 1/
Reposted by Sijing Tu
A quick thread on this short (3 page) paper appearing in SODA, giving a simple algorithm that makes predictions guaranteeing 2*Sqrt{T} "Distance to calibration" against an adversary. The result so simple I can describe it in thread. Joint with Eshwar, @ncollina.bsky.social, and Mirah:
Here is a 3 page paper giving a super-simple deterministic online algorithm that guarantees 2√T distance to calibration. The analysis is only 1 page (the first 2 pages are chit chat). It has a "Follow the perturbed leader" flavor. arxiv.org/abs/2402.11410
November 24, 2024 at 1:29 AM
A quick thread on this short (3 page) paper appearing in SODA, giving a simple algorithm that makes predictions guaranteeing 2*Sqrt{T} "Distance to calibration" against an adversary. The result so simple I can describe it in thread. Joint with Eshwar, @ncollina.bsky.social, and Mirah:
Very interesting findings!
Science of science preprint alert :)
arxiv.org/abs/2411.03938
Where postdoctoral journeys lead
Our data-driven study of how the postdoc period relates to academic careers.
1/3
arxiv.org/abs/2411.03938
Where postdoctoral journeys lead
Our data-driven study of how the postdoc period relates to academic careers.
1/3
Where postdoctoral journeys lead
Postdoctoral training is a career stage often described as a demanding and anxiety-laden time when many promising PhDs see their academic dreams slip away due to circumstances beyond their control. We...
arxiv.org
November 14, 2024 at 1:36 PM
Very interesting findings!
Very interesting findings!
Science of science preprint alert :)
arxiv.org/abs/2411.03938
Where postdoctoral journeys lead
Our data-driven study of how the postdoc period relates to academic careers.
1/3
arxiv.org/abs/2411.03938
Where postdoctoral journeys lead
Our data-driven study of how the postdoc period relates to academic careers.
1/3
Where postdoctoral journeys lead
Postdoctoral training is a career stage often described as a demanding and anxiety-laden time when many promising PhDs see their academic dreams slip away due to circumstances beyond their control. We...
arxiv.org
November 14, 2024 at 1:36 PM
Very interesting findings!
Reposted by Sijing Tu
Here is a @github.com repo where I will share tutorial notebooks on how to retrieve and analyze data from @bsky.app @atproto.com
Feedback, suggestions, and contributions are welcome!
github.com/brianckeegan...
Feedback, suggestions, and contributions are welcome!
github.com/brianckeegan...
GitHub - brianckeegan/bluesky-datascience: Exploratory notebooks for data science using Bluesky data
Exploratory notebooks for data science using Bluesky data - brianckeegan/bluesky-datascience
github.com
November 14, 2024 at 5:05 AM
Here is a @github.com repo where I will share tutorial notebooks on how to retrieve and analyze data from @bsky.app @atproto.com
Feedback, suggestions, and contributions are welcome!
github.com/brianckeegan...
Feedback, suggestions, and contributions are welcome!
github.com/brianckeegan...
Reposted by Sijing Tu
We are hosting the 11th International Conference on Computational Social Science in Sweden
🚀The IC2S2'25 website is LIVE, and submissions are OPEN!
📍Norrköping | July 21-24, 2025
Call for Abstracts (until Feb 24)
Call for Tutorials (until Jan 17)
🔗Explore details & submit: ic2s2-2025.org
🚀The IC2S2'25 website is LIVE, and submissions are OPEN!
📍Norrköping | July 21-24, 2025
Call for Abstracts (until Feb 24)
Call for Tutorials (until Jan 17)
🔗Explore details & submit: ic2s2-2025.org
October 25, 2024 at 12:10 PM
We are hosting the 11th International Conference on Computational Social Science in Sweden
🚀The IC2S2'25 website is LIVE, and submissions are OPEN!
📍Norrköping | July 21-24, 2025
Call for Abstracts (until Feb 24)
Call for Tutorials (until Jan 17)
🔗Explore details & submit: ic2s2-2025.org
🚀The IC2S2'25 website is LIVE, and submissions are OPEN!
📍Norrköping | July 21-24, 2025
Call for Abstracts (until Feb 24)
Call for Tutorials (until Jan 17)
🔗Explore details & submit: ic2s2-2025.org