We typically have seminars on Wednesday at noon in Malone 228.  All seminar announcements will be sent to the theory mailing list.

[Theory Seminar] Mohammad Hajiesmaili @ Malone 228
Sep 6 @ 12:00 pm – 1:00 pm

Speaker: Mohammad Hajiesmaili
Affiliation: Johns Hopkins University

Title: Online storage management in electricity market


With unprecedented benefits in terms of efficiency, economy, reliability, and environmental awareness, in the recent years, there has been a rapid proliferation of renewable energy sources such as solar and wind in electric power systems. Despite these benefits, the inherent uncertainty in renewables places severe challenges on the management of the entire energy systems, including electricity market. Leveraging energy storage systems is a promising approach to mitigate the uncertainty of renewables, by charging and discharging during the mismatched periods. Energy storage systems, however, offers a new design space for additional optimization. That is, a storage system can capture energy during periods when the market prices are low and surrender stored energy when energy prices are high.
In this talk, we consider different scenarios of storage management in both supply and demand sides of the electricity market. The uncertainties in both renewable output and electricity market price, emphasizes the need for online solution design. The underlying theoretical problems could be described as extensions of conversion problems in financial markets, i.e., the search for best prices to buy and/or sell assets. The difference with the conversion problems, is that in addition to the uncertainty in the price, our problems suffer from another uncertainty originated from renewable output. We follow online algorithm design and use competitive ratio as the performance measure of our algorithms. We present our recent results in designing competitive online algorithms that achieve constant competitive ratios. In addition, we briefly talk about the case of utilizing aggregate potentials distributed small-scale storage systems, such as EVs or residential storages, to participate in electricity market through an aggregator. This setting is more challenging than the previous one, since the distributed sources also arrive in online manner with heterogeneous profiles.

Overall, we believe that changing the landscape of electric power system from a centralized predictable system to a distributed uncertain system opens a new research direction for leveraging online framework designs in this relatively under-explored area.

[Theory Seminar] Kuan Cheng @ Malone 228
Oct 11 @ 12:00 pm – 1:00 pm

Speaker: Kuan Cheng
Affiliation: Johns Hopkins University

Title: Near-Optimal Secret Sharing and Error Correcting Codes in $\AC^0$


We study the question of minimizing the computational complexity of (robust) secret sharing schemes and error correcting codes. In standard instances of these objects, both encoding and decoding involve linear algebra, and thus cannot be implemented in the class $\AC^0$. The feasibility of non-trivial secret sharing schemes in $\AC^0$ was recently shown by Bogdanov et al.\ (Crypto 2016) and that of (locally) decoding errors in $\AC^0$ by Goldwasser et al.\ (STOC 2007).

In this paper, we show that by allowing some slight relaxation such as a small error probability, we can construct much better secret sharing schemes and error correcting codes in the class $\AC^0$. In some cases, our parameters are close to optimal and would be impossible to achieve without the relaxation. Our results significantly improve previous constructions in various parameters.

Our constructions combine several ingredients in pseudorandomness and combinatorics in an innovative way. Specifically, we develop a general technique to simultaneously amplify security threshold and reduce alphabet size, using a two-level concatenation of protocols together with a random permutation. We demonstrate the broader usefulness of this technique by applying it in the context of a variant of secure broadcast.

Based on a joint work with Yuval Ishai and Xin Li.

[Theory Seminar] Ilan Komargodski @ Malone 228
Oct 25 @ 12:00 pm – 1:00 pm

Speaker: Ilan Komargodski
Affiliation: Cornell Tech

Title: White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

Abstract: Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? This problem is in TFNP, the class of search problems with guaranteed solutions.  If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued.

1) What if one is given a program or circuit (“white-box”) for computing the existence of an edge. Does the search problem remain hard?
2) Can we generically translate all TFNP black-box hardness into white-box hardness?
3) Does the problem remain hard if the black-box instance is small?

We will answer all of these questions and discuss related questions in the setting of property testing.

Joint work with Moni Naor and Eylon Yogev.

[Theory Seminar] Ran Ben Basat
Nov 13 @ 12:00 pm – 1:00 pm

Speaker: Ran Ben Basat
Affiliation: Technion

Title: TBA

Abstract: TBA

[Theory Seminar] Samson Zhou
Nov 29 @ 12:00 pm – 1:00 pm

Speaker: Samson Zhou
Affiliation: Purdue University

Title: TBA

Abstract: TBA