Skip to content

Windows On Theory

A Research Blog

  • Home
  • About

Author: Kunal Talwar

Balls and Bins on Graphs

June 12, 2012June 12, 2012 ~ Kunal Talwar ~ 6 Comments

"Balls and Bins?", you ask, "Is there anything left to prove there?" Surprisingly, there are really natural questions that are open. Today I want to talk about one such question. First a quick primer. Balls and Bins processes model randomized allocations processes, used in hashing or more general load balancing schemes. Suppose that I have … Continue reading Balls and Bins on Graphs

Maximizing Submodular Functions (Part 2)

March 26, 2012 ~ Kunal Talwar ~ 6 Comments

Continuing on my last post, today I will talk about recent work by Niv Buchbinder, Moran Feldman, Seffi Naor, and Roy Schwartz that gives a simple 1/2 approximation to the (unconstrained) submodular maximization problem, matching the hardness. Do see the paper (which should be available in a couple of weeks) for full details. Apologies in … Continue reading Maximizing Submodular Functions (Part 2)

Maximizing Submodular Functions (Part 1)

March 22, 2012 ~ Kunal Talwar ~ 8 Comments

In this post and the next, I will talk about the problem of maximizing a submodular function. Submodularity is a natural property of set functions, that captures the diminishing returns property. Formally, let $latex f$ be a set function $latex f : 2^{U} \rightarrow \Re$, and let us assume that $latex U=[n]$.  Then $latex f$ … Continue reading Maximizing Submodular Functions (Part 1)

Posts navigation

Newer posts

Opinions are my own and do not represent Harvard or OpenAI. Follow me on Twitter ( @boazbaraktcs )

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 855 other subscribers

Search This Blog

Top Posts

  • CS 2881 Fall 26: Lecture 5: Economics of AI
  • It’s 2030 and we fucked up. How did it happen?
  • Math after AI
  • CS 2881 Fall 26: Lecture 6: Grading, Reward Hacking, and Alignment
  • The state of AI safety in four fake graphs
  • CS 2881 Fall 26: Lecture 1: Introduction
  • All Watched Over
  • CS 2881 Fall 26: Lecture 2: Cyber Capabilities
  • Factoring RSA Moduli. Part II.
  • CS 2881 Fall 26: Lecture 4: Recursive Self-Improvement and AI Trajectories

Recent Comments

Boaz Barak's avatarBoaz Barak on All Watched Over
Steven Levy's avatarSteven Levy on All Watched Over
Boaz Barak's avatarBoaz Barak on AI is a Meteor. Don’t be…
Huck Bennett's avatarHuck Bennett on AI is a Meteor. Don’t be…
Boaz Barak's avatarBoaz Barak on AI is a Meteor. Don’t be…

Recent Posts

  • CS 2881 Fall 26: Lecture 6: Grading, Reward Hacking, and Alignment November 8, 2026
  • CS 2881 Fall 26: Lecture 5: Economics of AI November 8, 2026
  • CS 2881 Fall 26: Lecture 4: Recursive Self-Improvement and AI Trajectories November 8, 2026
  • CS 2881 Fall 26: Lecture 2: Cyber Capabilities November 8, 2026
  • CS 2881 Fall 26: Lecture 3: Modern LLM Training and Inference October 28, 2026
  • CS 2881 Fall 26: Lecture 1: Introduction September 22, 2026
  • Math after AI August 24, 2026

Archives

RSS

  • RSS - Posts
  • RSS - Comments

RSS Theory jobs

  • Postdoctoral position at the University of Technology Sydney node of the ARC Centre of Excellence MathQuEST at University of Technology Sydney (apply by December 10, 2026)
  • Postdoc Positions in Quantum Computing and AI at Université de Sherbrooke (Quebec, Canada) (apply by December 1 3, 2026)
  • PhD position in Complexity Theory at Georgia Tech (Atlanta, USA) (apply by December 15, 2026)
  • Postdoc position in Complexity Theory at Georgia Tech (Atlanta, USA) (apply by December 1, 2026)
  • Postdoc at Bocconi University (apply by January 15, 2027)
  • Theory and Algorithms: Tenure-Track Assistant Professor in Computer Science at University of New Mexico (apply by December 5, 2026)
  • TENURE-TRACK / TENURED FACULTY AT INSAIT at INSAIT – Institute for Computer Science, Artificial Intelligence and Technology (apply by January 31, 2027)
  • POSTDOC AT INSAIT at INSAIT – Institute for Computer Science, Artificial Intelligence and Technology (apply by January 31, 2027)
  • Ph.D. student at West Virginia University (apply by December 15, 2026)
  • Postdoc at UC Berkeley (apply by December 1, 2026)

RSS Theory matters

  • Conference announcement: Celebrating 100 Years: Avi 70 + CSDM 30
  • Trevisan Award for Expository Work
  • Master’s programs with TCS research opportunities
  • STOC 2026 Experimental Program Announcement
  • FOCS Test of Time Award: Call for Nominations
  • FOCS 2024 Test of Time Awards Nominations
  • Knuth Prize call for nominations
  • New book on Probability
  • Wikipedia edit-a-thon at FOCS
  • PC chair and general chair guidelines for TCS conferences

RSS Theory Dish

  • A Subversive Message of Hope
  • Upcoming workshop at Stanford: Recent Advances in Regularity Lemmas
  • Speeding Up the Process of Mourning
  • Quantum Speedups Require Structure or Depth
  • Condorcet Quintets — A Proof from the Book
  • STOC 2026 Student Travel Grants
  • STOC 2026 Call for Workshops
  • Quickly approximating Shapley Games
  • Choosing the best ring … for MPC!
  • FOCS 2025 CfP is Out

Blog at WordPress.com.
  • Subscribe Subscribed
    Windows On Theory
    Join 855 other subscribers

    Have a WordPress.com account? Log in now.

  • Windows On Theory
    View site in Reader
    Manage subscriptionsSign upLog in
    Report this content
    Collapse this bar