TCS+

The next TCS+ talk will take place this coming Wednesday, November 15th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Palak Jain and Satchit Sivakumar from Boston University will speak about “The Price of Differential Privacy under Continual Observation” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: This talk will be on the accuracy of differentially private mechanisms in the continual release model. A continual release mechanism receives a sensitive dataset as a stream of T inputs and produces, after receiving each input, an output that is accurate for all the inputs received so far.

We describe a ‘sequential embedding’ framework to prove lower bounds for the continual release model via reductions from batch model problems. (In the batch model, the algorithm receives the data as one batch and produces a single output.) We show how this framework can be used to get strong lower bounds for some fundamental problems that are widely studied; these are the first strong lower bounds on the error of continual release mechanisms and witness a polynomial in T separation between the batch model and continual release model. Previous work shows only a logarithmic in T gap between the worst-case error achievable in these two models.

Our lower bounds assume only that privacy holds for streams fixed in advance (the ‘nonadaptive’ setting). We also discuss a model that allows for adaptively selected inputs. It captures dependencies that arise in many applications of continual release. In general, both privacy and accuracy are harder to attain in this model. Nevertheless, we analyze several algorithms in the new model and, in particular, show that some of our lower bounds are matched by the error of simple algorithms whose privacy holds even for adaptively selected streams.

This talk is based on works with Iden Kalemaj, Sofya Raskhodnikova, and Adam Smith (abs/2112.00828 and abs/2306.06723).

The next TCS+ talk will take place this coming Wednesday, November 1st at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Victor Reis from University of Washington will speak about “The Subspace Flatness Conjecture and Faster Integer Programming” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: In a seminal paper, Kannan and Lovász (1988) considered a quantity which denotes the best volume-based lower bound on the covering radius of a convex body with respect to a lattice . Kannan and Lovász proved that and the Subspace Flatness Conjecture by Dadush (2012) claims a factor suffices, which would match the lower bound from the work of Kannan and Lovász.

We settle this conjecture up to a constant in the exponent by proving that . Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush (2012, 2019), we obtain a -time randomized algorithm to solve integer programs in variables. Another implication of our main result is a near-optimal flatness constant of . Joint work with Thomas Rothvoss.

It’s September, and we are back!

The next TCS+ talk, first of our brand new season of TCS+, will take place next Wednesday, September 27th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC (check your timezone here)). Hanlin Ren from University of Oxford will speak about “Polynomial-Time Pseudodeterministic Construction of Primes” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.

We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an *unconditional* polynomial-time randomized algorithm such that, for infinitely many values of , outputs a canonical -bit prime with high probability. More generally, we prove that for every dense property of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying . This improves upon a subexponential-time construction of Oliveira and Santhanam.

Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell, using a variant of the Shaltiel—Umans generator.

If you are attending STOC’23 as part of the TheoryFest next week, don’t forget to have a look at the STOCial Program!

In particular, and to get to the point of this announcement: if you are graduating or will be on the job market soon, consider participating to the Graduating Bits Session on Wednesday: 1-2 slides, 2 minutes, entirely yours to present and pitch your research to the STOC attendees! To register, fill this form before Tuesday evening (up to 25 slots, first-come-first-served).

Following the by-now-well-established tradition, there will also be a “senior/junior lunch” on Thursday, during the 12:30-2pm time slot: put your name here as a “senior” (broadly construed) or a “junior” academic, for informal discussions, academic advice, and general questions over lunch.

See you next week at the TheoryFest!

Clément, on behalf of the STOCial Committee (Barna Saha, Clément Canonne, Elena Grigorescu, and Raghu Meka)

The next TCS+ talk will take place this coming Wednesday, May 31th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Paul Gölz from Harvard University will speak about “News from Algorithmic Democracy: Proportional Representation for Preferences and Demographics” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: How do you fill a knapsack with city projects to fund, in a way that aligns with voters’ preferences? And how do you choose a committee that represents the population’s makeup in terms of gender, age, etc.? Both questions are central to experiments with new forms of democracy in practice, and both have spurred an exploration for the right algorithms in computational social choice. In this talk, I will survey advances along these thrusts: proposed algorithms, guarantees offered and sought after, as well as technical challenges and connections.

The next TCS+ talk will take place this coming Wednesday, May 17th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Justin Gilmer from Google will speak about “A constant lower bound for Frankl’s union-closed sets conjecture.” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: A finite set system is union-closed if for every pair of sets in the system their union is also in the system. Frankl in 1979 conjectured that for any such system there exists an element which is contained in ½ of the sets in that system (the only exception being the family containing just the empty set). In this talk I will discuss how a simple observation regarding the contrapositive of Frankl’s conjecture eventually led to the discovery of an information theoretic approach on the problem and a proof of the first constant lower bound.

The next TCS+ talk will take place this coming Wednesday, May 3rd at 2:30 PM Eastern Time (11:30 AM Pacific Time, 20:30 Central European Time, 18:30 UTC: note the unusual time!). Scott Aaronson from UT Austin will speak about “Certified Randomness from Quantum Supremacy” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing “quantum supremacy” experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n) min-entropy, where n is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits — thereby “bootstrapping” from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol’s output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.

Joint work with Shih-Han Hung. To appear in STOC’2023.
https://arxiv.org/abs/2303.01625

The next TCS+ talk will take place this coming Wednesday, April 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Michal Feldman from Tel Aviv University will speak about “Algorithmic Contract Design” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Contract design captures situations where a principal delegates the execution of a costly task to an agent. To complete the task, the agent chooses an action from a set of costly actions. The principal can only observe the outcome, which is stochastically determined by the chosen action. The principal incentivizes the desired action through a contract, that specifies payments based on the observed outcome. In this talk, I will survey two papers on *combinatorial* contracts, which highlight different sources of complexity that arise in contract design. The first (FOCS’21) is where the agent can choose any subset of a given set of actions; the second (STOC’23) is where the principal motivates a team of agents. We provide (approximation) algorithms and hardness results for the optimal contract problem in these scenarios.

Based on joint work with Tomer Ezra, Paul Duetting and Thomas Kesselheim.

TCS for All (originally TCS Women) invites nominations for speakers in Rising Star talks at the TCS for All Spotlight Workshop at STOC 2023. To be eligible, your nominee has to be a senior PhD student with expected graduation no later than August 2024, or a postdoc in theoretical computer science (all topics represented at STOC are welcome), an underrepresented minority, and not a speaker at a previous TCS Women Spotlight Workshop. Preference will be given to speakers who are currently on the job market for postdoctoral/faculty positions, or who expect to be on the job market in Fall 2023.

You can make your nomination by filling this form by May 7th. TCS for All Spotlight Workshop will be held on Thursday, June 22nd, 2023 (2-4pm), in Orlando, Florida, USA, as part of the 54th Symposium on Theory of Computing (STOC) and TheoryFest! We are happy to announce that our annual inspirational talk will be given by Professor Dana Randall!

For more information, check out the website: https://sigact.org/tcsforall/

The next TCS+ talk will take place this coming Wednesday, April 5th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Yael Kalai from MSR New England will speak about “Efficient Verification of Computation on Untrusted Platforms” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Efficient verification of computation is fundamental to computer science and is at the heart of the P vs. NP question. Recently it has had growing practical significance, especially with the increasing popularity of blockchain technologies and cloud computing. In this talk, I will present schemes for verifying the correctness of a computation. I will discuss their impact on quantum complexity, hardness of approximation, and the complexity of Nash equilibrium.