Events

Title:Combinatorial rules for the geometry of Hessenberg varieties

progressions

 Abstract:

Hessenberg varieties were introduced by De Mari, Procesi, and Shayman in the early 1990s and lie at the intersection of geometry, representation theory, and combinatorics.  In 2012, Insko and Yong studied a class of Hessenberg varieties using patch ideals, a technique dating back to at least the 1970s from the study of Schubert varieties. In this talk, we will derive patch ideals and use them to study two classes of Hessenberg varieties.  We will see the combinatorics that govern the behaviour of these patch ideals and translate these results to the geometric setting. Based in part on work with Sergio Da Silva, Megumi Harada, and Jenna Rajchgot.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title: A O(log log m) prophet inequality for subadditive combinatorial auctions

Abstract:: I will present the paper "An O(log log m) prophet inequality for subadditive combinatorial auctions", by Dütting, Kesselheim, and Lucier. In the setting of online combinatorial auctions, we have a set of m items and n buyers. Buyers arrive one by one, and our goal is to irrevocably assign a set of items to each buyer as they arrive. An item can only be allocated to one buyer. Each buyer has a subadditive valuation function, which assigns a value to every possible subset of items that can be allocated to the buyer. Our goal is to maximize the social welfare of the final allocation, which is the sum of the valuations of the buyers. The paper provides a O(log log m) prophet inequality for this problem, beating the previous O(log m) barrier. This is the current best known polynomial time algorithm for this problem.

Title: Inapproximability of Sparsest Vector in a Real Subspace

Abstract:We establish strong inapproximability for finding the sparsest nonzero vector in a real subspace (where sparsity refers to the number of nonzero entries). Formally we show that it is NP-Hard (under randomized reductions) to approximate the sparsest vector in a subspace within any constant factor. We recover as a corollary state of the art inapproximability factors for the shortest vector problem (SVP), a foundational problem in lattice based cryptography. Our proof is surprisingly simple, bypassing even the PCP theorem.

Our main motivation in this work is the development of inapproximability techniques for problems over the reals. Analytic variants of sparsest vector have connections to small set expansion, quantum separability and polynomial maximization over convex sets, all of which cause similar barriers to inapproximability. The approach we develop could lead to progress on the hardness of some of these problems.

Joint work with Euiwoong Lee. 

Title: A constant factor approximation for Nash social welfare with subadditive valuations, Part II

Abstract::Social welfare refers to a class of optimization problems where the goal is to allocate subsets of resources $\mathcal{I}$ among agents $\mathcal{A}$ (or people) such that maximizes the overall "happiness" of society in a fair and efficient manner. More specifically, each agent $i \in \mathcal{I}$ has an intrinsic \emph{valuation} function $v_i: 2^{\mathcal{I}}\rightarrow \mathbb{R}$, which is a monotone function with $v_i(\emptyset)=0$, and $v_i$ quantifies the intrinsic value for subsets of items $S\subseteq \mathcal{I}$.

Variations of allocation with different valuation and objective functions has been studied in different areas of computer science, economies, and game theory. In this talk we focus on the Nash social welfare welfare (NSW) problem; given an allocation $\mathcal{S}= (S_i)_{i\in \mathcal{A}}$ the goal is to maximize the geometric mean of agents valuations.

Unfortunately, Nash social welfare problem is NP-hard already in the case of two agents with identical additive valuations, and it is NP-hard to approximate within a factor better than 0.936 for additive valuations and $(1-\frac{1}{e})$ for submodular valuation. 

Moreover, the current best approximation factors of $\simeq 0.992$ for additive valuations and $(\frac{1}{4}-\epsilon)$ for submodular valuations were found by Barman et al (2018) and Garg et al. (2023), respectively.

In this talk, we present a sketch of the algorithm in recent work by Dobzinski et al., which proves the first constant-factor approximation algorithm (with a fairly large constant $\sim \frac{1}{375,000}$) for NSW problem with subadditive valuations accessible via demand queries.

Title: The pathwidth theorem for induced subgraphs

Abstract: We present a full characterization of the unavoidable induced subgraphs of graphs with large pathwidth. This consists of two results. The first result says that for every forest H, every graph of sufficiently large pathwidth contains either a large complete subgraph, a large complete bipartite induced minor, or an induced minor isomorphic to H. The second result describes the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor. If time permits , we will also try to discuss the proof of the first result mentioned above.

Based on joint work with Maria Chudnovsky and Sophie Spirkl.

Title:Valuable partial orders

 Abstract: In the pre-seminar we will review Birkhoff's structure theory for finite distributive lattices and its consequences for the geometry of some algebraic varieties associated with lattices by Hibi. In the seminar itself we will look more closely at the geometry of these varieties, motivating the definition of an interesting class of partial orders and raising several open problems.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title: Constant-Depth Arithmetic Circuits for Linear Algebra Problems

Abstract: What is the computational complexity of the greatest common divisor (GCD) of two univariate polynomials? The Euclidean algorithm provides a polynomial-time solution, and fast variants of the Euclidean algorithm can compute the GCD in nearly-linear time. The GCD can also be expressed in a linear-algebraic form. Basic tasks in linear algebra, such as computing determinants and solving linear systems, can be performed in O(log^2 n) parallel time, and this can be used to compute the GCD in O(log^2 n) parallel time. This algorithm does not take advantage of any structure present in the resulting linear systems, so in principle one could compute the GCD in parallel even faster.

In this talk, I will describe a new algorithm that computes the GCD in O(log n) parallel time by using a combination of polynomial interpolation and Newton's identities for symmetric polynomials. In fact, this algorithm can be implemented as an arithmetic circuit of constant depth. Similar ideas yield constant-depth circuits to compute the resultant, Bézout coefficients, and squarefree decomposition.

Title: A Constant Factor Prophet Inequality for Subadditive Combinatorial Auctions

Abstract: In this talk, I will go through the paper of Correa and Cristi that appeared in STOC 2023. The paper proves a O(1) prophet inequality for online combinatorial auctions with subadditive buyers.

Their techniques involve the use of what they call a Random Score Generator (RSG for short), which is a distribution over prices of the items. Each buyer 'plays' an RSG. The algorithm samples a vector of prices of the items from this RSG for each buyer as they arrive, and assigns to them the set of items for which the sampled prices are larger than prices from another independent sample from the RSGs of all the buyers. A mirroring argument is used to bound the value of the allocation computed by their algorithm, and a novel fixed point argument is used to show the existence of RSGs that guarantee a good approximation.

In contrast to the O(log log m) prophet inequality covered previously in the CO reading group, the algorithm in this paper does not run in polynomial time, and does not involve posted prices.