We consider the problem of scheduling $m$ jobs on $n$ unrelated strategic machines to minimize the maximum load of any machine, but the machines are strategic and may misreport processing times to minimize their own load. The pioneering work of Nisan and Ronen gave an $n$-approximate deterministic strategyproof mechanism for this setting, and this was recently shown to be best possible by the breakthrough results of Christodoulou et al. This large approxation guarantee begs the question: how can we avoid these large worst-case results. In this work, we use the powerful framework of algorithms with (machine-learned) predictions to bypass these strong impossibility results. We show how we can predict $O(m+n)$ values to obtain a deterministic strategyproof algorithm whose makespan is within a constant factor of the optimal makespan when the predictions are correct, and $O(n)$ times the optimum no matter how poor the predictions are.

Pattern matching (PM) is the technique of identifying occurrences of a short pattern in a long text, where both, the pattern and text, are a string of characters. Since several applications demand the privacy of the pattern and the text in the process of identifying matches, designing secure solutions for PM is gaining popularity. Moreover, given the variety of applications that consider PM, we design secure solutions for three popular variants of PM---exact, wildcard and approximate. Our solutions are designed using the techniques of secure multiparty computation (MPC) in the two-party semi-honest setting. All of our solutions attain a fast response time, which is the time taken from submission of the input to obtaining the output, and forms a crucial parameter when analysing the performance of any protocol. Moreover, our protocols also provide an improved online communication complexity in comparison to prior works. Since determining if two secret-shared values are equal forms a crucial component in all the PM variants, we design a novel constant-round equality protocol in the two-party semi-honest setting. Our equality protocol outperforms all the prior works in the considered setting and can also be of independent interest. We implement all our protocols on the MPC framework of MOTION2NX to showcase the practicality of the designed solutions. In comparison to prior works that consider DNA matching (over 2-bit characters), our pattern matching protocols see improvements of up to 2 orders of magnitude in response time. Our equality protocol, too, excels over all existing constructions. To analyse the performance of our equality protocol in comparison to prior work, we benchmark it for varying input sizes. We observe that with increasing input sizes, the improvement in response time of our protocol keeps on increasing, with improvements of up to 9.7x for 256-bit inputs.

Consider the problem of securely identifying$\tau$-heavy hitters, where given a set of client inputs, the goal is to identify those inputs which are held by at least$\tau$clients in a privacy-preserving manner. Towards this, we design a novel system$\mathsf {Vogue}$, whose key highlight in comparison to prior works, is that it ensures complete privacy and does not leak any information other than the heavy hitters. In doing so,$\mathsf {Vogue}$aims to achieve as efficient a solution as possible. To showcase these efficiency improvements, we benchmark our solution and observe that it requires around 14 minutes to compute the heavy hitters for$\tau$= 100 on 256-bit inputs when considering 400 K clients. This is in contrast to the state of the art solution that requires over an hour for the same. In addition to the static input setting described above,$\mathsf {Vogue}$also accounts for streaming inputs and provides a protocol that outperforms the state-of-the-art therein. The efficiency improvements witnessed while computing heavy hitters in both, the static and streaming input settings, are attributed to our new secure stable compaction protocol, whose round complexity is independent of the size of the input array to be compacted.

Consider a set of N clients, each of which holds a private input string. An input string that is held by at least τ clients is defined as a τ-heavy hitter. In various application scenarios, data-aggregation servers are interested in learning τ-heavy hitters. To ensure that the servers do not learn anything about client input in the process, the problem of identifying heavy hitters privately is gaining popularity. Towards this, we design a novel system called Vogue, which provides improved efficiency as well as security guarantees over the state-of-the-art system of Poplar. Concretely, Vogue provides up to 27x efficiency improvement over Poplar when considering 400,000 clients who hold 256-bit input strings. Moreover, Vogue overcomes intermediate information leakages present in Poplar and guarantees full security in the presence of a malicious adversary. In the process of designing Vogue, we also design secure and efficient protocols for stable compaction and shuffle, each of which improves over its respective state-of-the-art.