The Theory Workshop 2022 took place online on May 13 (Friday) at CS1.04.

Please let us know what you thought of the event and how it could be made better for the organisers next year hereLink opens in a new window.

Schedule:

• Tea and Coffee (09:30 – 09:45)
• Opening (09:45 – 10:00)
• Session I (10:00 – 10:50) 
  • Amelia Chui : Lower Bounds for the Shared Memory Switch
  • Gopinath Mishra : Tolerant Bipartite Testing in Dense Graphs (Online Talk)
  • Ari Biswas : Differentially private elections in presence of dishonesty
• Session II (11:10 – 12:00) 
  • Mary Scott : Differentially Private Measures of Statistical Heterogeneity for Vectors
    
  • Namrata : Pattern avoidance in binary trees
  • Patrick O’Hara : Prize-collecting TSP
• Lunch + Photo Session (12:00 – 13:30) CS1.04
• Talk by Mike Paterson (13:30 – 14:00) : Bounded Hanoi
  

• Session III (14:20 – 15:10) 
  • Aditya Prakash : On low levels of index hierarchy in Parity Tree Automata
  • Henry Sinclair-Banks : Coverability in 2-VASS with One Unary Counter
  • Lawqueen Kanesh : Parameterized Fault-Tolerance Oracles
• Session IV (15:30 – 16:20) 
  • Hugo Aaronson : Distribution Free Property Testing
  • Jack O’Connor : Zero Knowledge Distribution Testing
    
  • Marcel De Sena Dall D’Agnol : Streaming zero-knowledge proofs
• Session V (16:40 – 17:30)  
  • Jiatu Li : How (and why) to prove lower bounds for cryptographic primitives?
  • Bruno Pasqualotto Cavalar : Separations between monotone and non-monotone circuit complexity
  • Sam Coy : TBA
• Dinner (18:45 - 20:30) At Radcliffe

For any information about this event, contact organisers: Ninad RajgopalLink opens in a new window, Peter Kiss, Thejaswini K. S

---

Ari Biswas: Differentially private elections in presence of dishonesty

We consider the problem of conducting differentially private plurality elections in presence of malicious actors. Recently, there has been a lot of progress in computing aggregation functions under differential privacy, which has led to alternate statistical privacy paradigms, such as local, shuffle and central differential privacy. Each paradigm has a slightly different definition of what it means to be private. However, regardless of the choice of paradigm, all known efficient implementations assume passive security, which requires that the clients and servers follow protocols exactly as instructed. In such models, a single deviant actor can completely dissolve the guarantees of these protocols, making passive security impractical in many real life settings. In our work, we borrow techniques from secure function evaluation to design algorithms for differentially private plurality voting; in presence of malicious actors who can arbitrarily deviate from the prescribed protocol. We do so while providing the same accuracy guarantees of the algorithms implemented under passive security. Additionally, for many widely accepted benchmark implementations, we show that it is impossible for such algorithms to provide privacy in presence of malicious actors.

---

Mary Scott : Differentially Private Measures of Statistical Heterogeneity for Vectors

This work serves as an exploration of existing and emerging research in Federated Machine Learning systems, in particular those which incorporate differential privacy and/or characterise statistical heterogeneity. Statistical heterogeneity is a term that can be used to describe a dataset if the observed trends from each sample differ from that of the overall population more than would be expected due to random error alone. The possible adaptations of existing measures of skewness have been examined to select a promising candidate that can intelligently select a sample from a statistically heterogeneous dataset to optimise the accuracy of the trends inferred from that sample compared to the dataset. The eventual outcome is to carry out some federated learning or analytics on realistic, statistically heterogeneous data in a differentially private way, and compare its effectiveness with previous methods.

---

Mike Paterson : Bounded Hanoi

A short history of the Tower of Hanoi problem is followed by a presentation of new work which considers the problem where the pegs are of limited capacity. This is joint research with Kazuo Iwama and was published this year in the American Mathematical Monthly.