STCS Annual Symposium 2024

09:20-09:30: Opening remarks.

The \(k\)-server problem is one of the most fundamental problems in the area of online algorithms. In this problem, an online algorithm needs to maintain a set of \(k\) servers in a metric space. When a request arrives at a certain location, one of the \(k\) servers needs to move to this requested location. The goal is to minimize the total movement cost of all the servers. Over the past three decades, significant progress has been made on this problem, yet many intriguing questions remain open. Notably, progress on the \(k\)-server problem has resulted in the development of new techniques that have advanced the broader field of online algorithms. This talk will survey recent techniques and breakthroughs developed for the \(k\)-server problem.

Challenge the champ tournaments are one of the simplest forms of competition, where a (initially selected) champ is repeatedly challenged by other players. If a player beats the champ, then that player is considered the new (current) champ. Each player in the competition challenges the current champ once in a fixed order. The champ of the last round is considered the winner of the tournament. We investigate a setting where players can be bribed to lower their winning probability against the initial champ. The goal is to maximize the probability of the initial champ winning the tournament by bribing the other players, while not exceeding a given budget for the bribes. We show that the problem is weakly NP-hard and W[1]-hard when parameterized by the number of players. On the algorithmic side, we show that the problem is fixed-parameter tractable (FPT) when parameterized either by the number of different bribe values or the number of different probability values. To this end, we establish several results that are of independent interest. In particular, we show that the product knapsack problem is W[1]-hard when parameterized by the number of items in the knapsack, and that constructive bribery for cup tournaments is W[1]-hard when parameterized by the number of players.

Semigroups and monoids are important and interesting objects of study in algebraic automata theory. A semigroup is a set endowed with an associative binary operation, and a monoid is a semigroup with an identity element. Examples of monoids include the set of strings over an alphabet (with concatenation as the binary operation and the empty string as unit element), the set of nonnegative integers (with addition and 0), and the set of rationals (with multiplication and 1).

Infinite monoids have uncountably many subsets, some of which are "nice" and some are not. For example, in the monoids of strings, we say that regular languages (i.e. languages that are recognized by finite-state automata) are "nice". In general, we are interested in finding subsets of monoids that are recognized by finite monoids. The recognizable subsets of a monoid are of special interest as they have finite representations and exhibit useful closure properties.

In this talk, we look at recognizable subsets of monoids of various sets of numbers. In particular, we will see monoids whose underlying sets are integers, rationals, reals, or complex numbers, each with binary operation addition or multiplication. This is joint work with Arnab Sur.

In Hotelling's model of spatial competition, a unit mass of voters is distributed in the interval \([0,1]\) (with their location corresponding to their political persuasion), and each of \(m\) candidates selects as a strategy their distinct position in this interval. Each voter votes for the nearest candidate, and candidates choose their strategy to maximize their votes. It is known that if there are more than two candidates, equilibria may not exist in this model. It was unknown, however, how close to an equilibrium one could get. Our work studies approximate equilibria in this model, where a strategy profile is an (additive) \(\epsilon\)-equilibria if no candidate can increase their votes by \(\epsilon\), and provides tight or nearly-tight bounds on the approximation \(\epsilon\) achievable.

We show that for 3 candidates, for any distribution of the voters, \(\epsilon \ge 1/12\). Thus, somewhat surprisingly, for any distribution of the voters and any strategy profile of the candidates, at least \(1/12\)th of the total votes is always left ``on the table.'' Extending this, we show that in the worst case, there exist voter distributions for which \(\epsilon \ge 1/6\), and this is tight: one can always compute a \(1/6\)-approximate equilibria in polynomial time. We then study the general case of \(m\) candidates, and show that as \(m\) grows large, we get closer to an exact equilibrium: one can always obtain a \(1/(m+1)\)-approximate equilibria in polynomial time. We show this bound is asymptotically tight, by giving voter distributions for which \(\epsilon \ge 1/(m+3)\).

Propositional proof complexity is the field of study of the complexity of proofs for tautological Boolean formulas. Cook and Reckhow introduced this area in their seminal work with the ultimate goal of resolving the question of NP versus coNP using upper/lower bounds for stronger and stronger proof systems. Polynomial Calculus (PC) is one such propositional proof system that has received wide attention since its introduction by Clegg, Edmonds and Impagliazzo. Despite having a reasonable understanding of PC, there has been little progress towards lower bounds for the stronger system \(AC0[p]\)-Frege, which was one of the main motives for defining PC. This indicates that we have to look at systems stronger than PC in order to get new insights.

In this work, we present new size lower bounds for PC proofs in two settings:

1. 1. When the Boolean variables are encoded using \(+1/-1\) (as opposed to \(0/1\)): We prove that for an unsatisfiable formula \(F\), the lifted formula \(F\) composed with a \(1\)-bit indexing gadget \(G\) requires a PC size of \(2^{\Omega(d)}\), where \(d\) is the degree needed to refute \(F\). Our lower bound does not depend on the number of variables \(n\), and holds over every field. The only previously known size lower bounds in this setting were established quite recently in [Sokolov, STOC 2020] using lifting with another (symmetric) gadget. The size lower bound there is \(2^{\Omega((d−d_0)^2/n)}\) (where \(d_0\) is the degree of the initial equations arising from the formula), and is shown to hold only over the reals.
2. 2. When the PC refutation proceeds over a finite field \(F_p\) and is allowed to use extension variables: We show that there is an unsatisfiable \(AC0[p]\) formula with \(N\) variables for which any PC refutation using \(N^{1+\epsilon(1-\delta)}\) extension variables, each of arity at most \(N^{1-\epsilon}\) and size at most \(N^c\), must have size \(\exp(\Omega(N \epsilon \delta / \text{poly} \log N))\). The only previously known lower bounds for PC in this setting are those obtained in [Impagliazzo-Mouli-Pitassi, CCC 2023]; Our result generalises these, and demonstrates a tradeoff between the number and the arity of extension variables.

Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities is an outstanding problem that has received a lot of attention after its introduction by Raz and Tzamaret [Ann. Pure Appl. Log.'08]. Very recently, Efremenko, Garlík and Itsykson [ECCC'23] proved the first exponential lower bounds on the size of ResLin proofs that were additionally restricted to be bottom-regular. We show that there are formulas for which such regular ResLin proofs of unsatisfiability continue to have exponential size even though there exists short proofs of their unsatisfiability in ordinary, non-regular resolution. This is the first super-polynomial separation between the power of general ResLin and and that of regular ResLin for any natural notion of regularity.

Our argument, while building upon the work of Efremenko et al., uses additional ideas from the literature on lifting theorems.

A significant body of information-theoretic cryptography has been devoted to the study of power of randomness in private computation. This has included both in-depth study of randomness complexity of specific functions and results for broad class of functions. In this work, we make further progress by studying randomness complexity in a new simple model of secure computation called Private Sequential Stateless (PSS) model. We show that functions with O(1) randomness complexity in the PSS model are exactly those with constant-width branching program, restricting to "speak-constant-times" protocols and to "read-constant-times" branching programs. Our main construction is a novel PSS protocol for "strongly regular branching programs" (SRBP), and as we show, any constant-width branching program can be converted into a constant-width SRBP yielding one side of our characterization. The converse direction uses ideas from Kushilevitz et al. to translate randomness to communication.

We study the adversarial binary hypothesis testing problem (studied by Brandao, Harrow, Lee & Peres, 2020) in the sequential setting. Associated with each hypothesis is a closed, convex set of distributions. Given the hypothesis, each observation is generated according to a distribution chosen (from the set associated with the hypothesis) by an adversary who has access to past observations. In the sequential setting, the number of observations the detector uses to arrive at a decision is variable; however there is a constraint on the expected number of observations used. We characterize the closure of the set of achievable pairs of error exponents.

Top-\(2\) methods have become popular in solving the best arm identification (BAI) problem. The best arm, or the arm with the largest mean amongst finitely many, is identified through an algorithm that at any sequential step independently pulls the empirical best arm, with a fixed probability \(\beta\), and pulls the best challenger arm otherwise. The probability of incorrect selection is guaranteed to lie below a specified \(\delta >0\). Information theoretic lower bounds on sample complexity are well known for BAI problem and are matched asymptotically as \(\delta \rightarrow 0\) by computationally demanding plug-in methods. The above top 2 algorithm for any \(\beta \in (0,1)\) has sample complexity within a constant of the lower bound. However, determining the optimal \(\beta\) that matches the lower bound has proven difficult. In this paper, we address this and propose an optimal top-2 type algorithm. We consider a function of allocations anchored at a threshold. If it exceeds the threshold then the algorithm samples the empirical best arm. Otherwise, it samples the challenger arm. We show that the proposed algorithm is optimal as \(\delta \rightarrow 0\). Our analysis relies on identifying a limiting fluid dynamics of allocations that satisfy a series of ordinary differential equations pasted together and that describe the asymptotic path followed by our algorithm. We rely on the implicit function theorem to show existence and uniqueness of these fluid ode's and to show that the proposed algorithm remains close to the ode solution.

This talk is based on joint work with Prof. Sandeep Juneja (Ashoka University) and Dr. Shubhada Agrawal (Carnegie Mellon University).

Finitely many simulatable designs are given and we aim to identify the safest one, i.e., that with the smallest probability of catastrophic failure. We consider this problem in a ranking and selection or equivalently the multi-armed-bandit best-arm-identification framework where we aim to identify the safest design/arm with the lowest probability of failure with probability at least 1 − δ for a pre-specified, small δ . To illustrate the rarity structure crisply, we study the problem in an asymptotic regime where the design failure probabilities shrink to zero at varying rates. In this set-up, we consider the well known information theoretic lower bound on sample complexity, and identify the simplifications that arise due to the rarity framework. A key insight is that sample complexity is governed by the rarity of the second safest design. Lower bound guides and speeds up proposed algorithm, that is intuitive and asymptotically matches the lower bound.

In contemporary deep learning practice, models are often trained to near zero loss i.e. to nearly interpolate the training data. However, the number of parameters in the model is usually far more than the number of data points \(n\), the theoretical minimum needed for interpolation: a phenomenon referred to as overparameterization. In an interesting piece of work that contributes to the considerable research that has been devoted to understand overparameterization, Bubeck and Sellke showed that for a broad class of covariate distributions (specifically those satisfying a natural notion of concentration of measure), overparameterization is necessary for robust interpolation i.e. if the interpolating function is required to be Lipschitz. However, their robustness results were proved only in the setting of regression with square loss. In practice, however many other kinds of losses are used, e.g. cross entropy loss for classification. In this work, we generalize Bubeck and Selke’s result to Bregman divergence losses, which form a common generalization of square loss and cross-entropy loss. Our generalization relies on identifying a bias variance-type decomposition that lies at the heart of the proof and Bubeck and Sellke.

In this talk, we will consider the problem of verifying concurrent programs. In here, we are given a set of programs that communicate through shared memory, a specification and we wish algorithmically check if the programs violate the specification. The programmers, while writing code usually assume that the memory operations are immediate (referred to as sequential consistency). However, the modern day architectures, to optimise the running time, re-order the memory operations in a non-trivial manner. This leads to various memory models such as TSO, PSO and so on. We will walk through some of these memory models during the talk. The recent intel processor introduced persistency mechanism that allows for the writes to be archived. This can then be used to restart the computation in case of a crash. The main focus of the talk will be how to verify programs when persistency is combined with weak memory.

Associated to two given sequences of eigenvalues is a natural polytope, the polytope of augmented hives with the specified boundary data, which is associated to sums of random Hermitian matrices with these eigenvalues. As a first step towards the asymptotic analysis of random hives, we show that if the eigenvalues are drawn from the GUE ensemble, then the associated augmented hives exhibit concentration as the number of eigenvalues tends to infinity.

Our main ingredients include a representation due to Speyer of augmented hives involving a supremum of linear functions applied to a product of Gelfand–Tsetlin polytopes; known results by Klartag on the KLS conjecture in order to handle the aforementioned supremum; covariance bounds of Cipolloni–Erdös–Schröder of eigenvalue gaps of GUE; and the use of the theory of determinantal processes to analyze the GUE minor process. This is joint work with Scott Sheffield and Terence Tao.

The Horn problem, proposed by Alfred Horn in 1962, explores the spectrum of the sum of Hermitian matrices. Specifically, given three Hermitian matrices A, B, and C of the same size such that A + B = C, the Horn problem describes the possible relationships among their eigenvalues. Combinatorial hives, introduced by Knutson and Tao, played a crucial role in proving the Horn conjecture. In this talk, we will focus on random double hives generated using two independent random Gelfand-Tsetlin patterns obtained through the minor process on two independent random matrices (with either fixed, or in the case of GUE, random spectra). We will apply a result of Knutson-Tao-Woodward to use the octahedron recurrence to sample random augmented hives, which are random hives with a Gelfand-Tsetlin pattern pasted to one side. Additionally, we will visualize Speyer’s theorem using lozenge tilings. The weights of these lozenge tilings equal the values of a random hive at a certain vertex. Lastly, we will provide a candidate for the asymptotic mean of a random GUE hive.

This is joint work with Hariharan Narayanan.

For the fair division of a set of items among interested agents, envy-freeness is possibly the most favored and widely studied formalization of fairness. For indivisible items, envy-free allocations may not exist in trivial cases, and hence research and practice focus on relaxations, particularly envy-freeness up to one item (EF1), which allows the removal of an item to resolve envy. A significant reason for the popularity of EF1 allocations in theory and practice is its simple fact of existence, which supports research into combining EF1 with other properties such as efficiency, or research into stronger properties such as ex-ante envy-freeness. It is known that EF1 allocations exist for two agents with arbitrary valuations, agents with doubly-monotone valuations, agents with Boolean valuations, and identical agents with negative Boolean valuations. In fact the last two results were shown for the more stringent EFX relaxation. We extend these results to show the existence of EF1 allocations for identical ternary valuations --- when the value of any subset is \(-1\), \(0\), or \(1\), or when the value of any subset is \(0\), \(1\), or \(2\).

A basic problem in optimization is to minimize a linear combination of the sum of convex functions and movement cost (charge for changing actions across time). In the online setting, at each step a new convex function is revealed and an algorithm has to choose its actions without knowing the future functions. The objective is to design an algorithm with small competitive ratio. An interesting question is: can algorithms, that only have gradient information about the convex functions and that too only for prior slots, have performance close to algorithms that have full current information? We answer this in the affirmative.

I will present the compensated coupling: a simple paradigm for designing sequential decision-making policies based on sample-pathwise comparisons against a hindsight benchmark. This approach generalizes many standard results used in studying Markov decision processes and reinforcement learning, but also gives us new policies which are much simpler and more effective than existing heuristics. For a large class of widely-studied sequential decision-making problems -- including network revenue management, dynamic pricing, generalized assignment, online bin packing, online assortment optimization and bandits with knapsacks -- I will illustrate how under a wide range of conditions, our approach achieves additive loss compared to the hindsight optimal which is independent of the horizon and state-space. Time permitting, I will try and describe how we can use this technique to incorporate side information and historical data, and achieve constant regret with as little as a single data trace.

The classical Reed-Muller codes over a finite field \(F_q\) are based on evaluations of \(m\)-variate polynomials of degree at most \(d\) over a product set \(U^m\), for some \(d < |U|\). Because of their good distance properties, as well as the ubiquity and expressive power of polynomials, these codes have played an influential role in coding theory and complexity theory. This is especially so in the setting of \(U\) being \(F_q\) where they possess deep locality properties. However, these Reed-Muller codes have a significant limitation in terms of the rate achievable --- the rate cannot be more than \(1/m! = \exp(-m \log m)\).

In this talk, I will discuss a recent work where we give two explicit constructions of multivariate polynomial evaluation codes which overcome this rate limitation. More concretely, we give explicit evaluation domains \(S\) in \(F_q^m\) on which evaluating \(m\)-variate polynomials of degree at most \(d\) gives a good code. For constant \(m\), these new codes have constant relative distance and rate \(1 - \epsilon\) for any \(\epsilon > 0\). We give two such constructions of evaluation domains, the first based on combinatorial ideas, and the second a bit more algebraic. The underlying structure of these point sets also yields clean unique decoding algorithms for these codes up to half their minimum distance, as well as endows the second construction with some strong and surprising locality properties.

Based on joint work with Swastik Kopparty and Harry Sha.

Multivariate polynomial factorization is a natural algebraic problem with a lot of applications. von zur Gathen, Kaltofen, Trager et al gave us randomized algorithms for factorizing black-box polynomials as well as polynomials given as explicit arithmetic circuits. Derandomization of these algorithms is connected to the derandomization of polynomial identity testing (by a result of Kopparty, Saraf and Shpilka) but the connection is not ""fine-grained""; thus, recent breakthroughs in deterministic PIT for constant-depth circuits have not immediately led to improvements in deterministic factorization of constant-depth circuits.

In this talk, we will see an algorithm that makes some modest progress towards this problem. In particular, we will see a deterministic subexponential time algorithm that takes as input a multivariate polynomial \(f\) computed by a constant-depth circuit over rational numbers, and outputs a list \(L\) of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of \(f\) computable by constant-depth circuits. This list \(L\) might also include circuits that are spurious: they either do not correspond to factors of \(f\) or are not even well-defined, e.g. the input to a division gate is a sub-circuit that computes the identically zero polynomial.

The key technical ingredient of our algorithm is a notion of the pseudo-resultant of \(f\) and a factor \(g\), which serves as a proxy for the resultant of \(g\) and \(f/g\), with the advantage that the circuit complexity of the pseudo-resultant is comparable to that of the circuit complexity of \(f\) and \(g\). This notion, which might be of independent interest, together with the recent results of Limaye, Srinivasan and Tavenas, helps us derandomize one key step of multivariate polynomial factorization algorithms - that of deterministically finding a good starting point for Newton Iteration for the case when the input polynomial as well as the irreducible factor of interest have small constant-depth circuits.

This is joint work with Ramprasad Saptharishi, Mrinal Kumar and Ben Lee Volk.

A polynomial \(f(X)\) over \(\mathbf{F}_q\) is said to be irreducible if it doesn't factor as \(f(X) = g(X) h(X)\) for some non-trivial polynomials \(g(X)\) and \(h(X)\). Irreducible polynomials are analogues of prime numbers over the integers. In this talk, we consider the task of constructing a irreducible polynomial of degree \(d\) over \(\mathbf{F}_q\). By the density of irreducible polynomials in \(\mathbf{F}_q\), a simple strategy of randomly picking a degree \(d\) polynomial and checking if it's irreducible succeeds with high probability. Note that a side effect of the above strategy is that each successful run will very likely generate different irreducible polynomials.

Since there is no known deterministic algorithm for this problem, it is interesting to ask if there is a pseudo-deterministic algorithm for constructing irreducible polynomials. A pseudo-deterministic algorithm is allowed to use randomness, but with high probability it must output a canonical irreducible polynomial. I will present a polynomial-time pseudo-deterministic algorithm for constructing irreducible polynomial of degree \(d\) over finite field \(\mathbf{F}_q\), that runs in time \(\tilde{O}(d^4 \log^4{q})\).

Univariate multiplicity codes are a generalization of Reed-Solomon codes and are among the first families of efficiency list-decodable codes all the way up to capacity (Guruswami-Wang and Kopparty). In this work, we show how these efficient list-decoders for univariate multiplicity codes can in fact be made to run in nearly linear time. Our results also hold for Folded Reed-Solomon codes. An important intermediate step in our nearly-linear time decoding algorithm is obtaining a nearly-linear time solver for ordinary differential equations.

18:00-18:10: Closing Remarks.