Arrow Research search

Author name cluster

Alexandra Kolla

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers
1 author row

Possible papers

8

FOCS Conference 2022 Conference Paper

Algorithms for the ferromagnetic Potts model on expanders

  • Charlie Carlson
  • Ewan Davies
  • Nicolas Fraiman
  • Alexandra Kolla
  • Aditya Potukuchi
  • Corrine Yap

We give algorithms for approximating the partition function of the ferromagnetic Potts model on d-regular expanding graphs. We require much weaker expansion than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models, using extremal graph theory and applications of Karger’s algorithm to counting cuts that may be of independent interest. It is #BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of #BIS are rare. We believe that these methods can shed more light on other important problems such as sub-exponential algorithms for approximate counting problems.

Details

STOC Conference 2022 Conference Paper

Computational thresholds for the fixed-magnetization Ising model

  • Charlie Carlson
  • Ewan Davies
  • Alexandra Kolla
  • Will Perkins 0001

The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate counting: approximating the partition function of the ferromagnetic Ising model with uniform external field is tractable at all temperatures and on all graphs, due to the randomized algorithm of Jerrum and Sinclair. Here we show that hidden inside the model are hard computational problems. For the class of bounded-degree graphs we find computational thresholds for the approximate counting and sampling problems for the ferromagnetic Ising model at fixed magnetization (that is, fixing the number of +1 and −1 spins). In particular, letting β c (Δ) denote the critical inverse temperature of the zero-field Ising model on the infinite Δ-regular tree, and η Δ,β,1 + denote the mean magnetization of the zero-field + measure on the infinite Δ-regular tree at inverse temperature β, we prove, for the class of graphs of maximum degree Δ: (i) for β β c (Δ), there is an FPRAS and efficient sampling scheme for the fixed-magnetization Ising model for magnetizations η such that |η| >η Δ,β,1 + . (iii) For β > β c (Δ), there is no FPRAS for the fixed-magnetization Ising model for magnetizations η such that |η| <η Δ,β,1 + unless NP=RP.

Details

SODA Conference 2019 Conference Paper

Optimal Lower Bounds for Sketching Graph Cuts

  • Charlie Carlson
  • Alexandra Kolla
  • Nikhil Srivastava
  • Luca Trevisan 0001

We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undirected graph on n vertices up to a 1 + ∊ error must use Ω( n log n / ∊ 2 ) bits of space in the worst case, improving the Ω( n / ∊ 2 ) bound of [ACK + 16] and matching the best known upper bound achieved by spectral sparsifiers [BSS12]. Our proof is based on a rigidity phenomenon for cut (and spectral) approximation which may be of independent interest: any two d– regular graphs which approximate each other's cuts significantly better than a random graph approximates the complete graph must overlap in a constant fraction of their edges.

Details

MFCS Conference 2019 Conference Paper

Spectral Aspects of Symmetric Matrix Signings

  • Charlie Carlson
  • Karthekeyan Chandrasekaran
  • Hsien-Chih Chang
  • Naonori Kakimura
  • Alexandra Kolla

The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of finding symmetric signings of matrices with natural spectral properties. Our results are the following: 1) We characterize matrices that have an invertible signing: a symmetric matrix has an invertible symmetric signing if and only if the support graph of the matrix contains a perfect 2-matching. Further, we present an efficient algorithm to search for an invertible symmetric signing. 2) We use the above-mentioned characterization to give an algorithm to find a minimum increase in the support of a given symmetric matrix so that it has an invertible symmetric signing. 3) We show NP-completeness of the following problems: verifying whether a given matrix has a symmetric signing that is singular or has bounded eigenvalues. However, we also illustrate that the complexity could differ substantially for input matrices that are adjacency matrices of graphs. We use combinatorial techniques in addition to classic results from matching theory.

Details

FOCS Conference 2011 Conference Paper

How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games

  • Alexandra Kolla
  • Konstantin Makarychev
  • Yury Makarychev

In this paper, we study the average case complexity of the Unique Games problem. We propose a semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Unique Games, then she chooses an ε-fraction of all edges, and finally replaces ("corrupts") the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1 - ε)-satisfiable instance, so then the problem is as hard as in the worst case. We show however that we can find a solution satisfying a (1 - δ) fraction of all constraints in polynomial-time if at least one step is random (we require that the average degree of the graph is Ω̃(log k)). Our result holds only for ε less than some absolute constant. We prove that if ε ≥ 1/2, then the problem is hard in one of the models, that is, no polynomial-time algorithm can distinguish between the following two cases: (i) the instance is a (1 - ε)-satisfiable semi-random instance and (ii) the instance is at most δ-satisfiable (for every δ >; 0); the result assumes the 2-to-2 conjecture. Finally, we study semi-random instances of Unique Games that are at most (1 - ε)-satisfiable. We present an algorithm that distinguishes between the case when the instance is a semi-random instance and the case when the instance is an (arbitrary) (1 - δ)-satisfiable instances if ε >; cδ (for some absolute constant c).

Details

STOC Conference 2010 Conference Paper

Subgraph sparsification and nearly optimal ultrasparsifiers

  • Alexandra Kolla
  • Yury Makarychev
  • Amin Saberi
  • Shang-Hua Teng

We consider a variation of the spectral sparsification problem where we are required to keep a subgraph of the original graph. Formally, given a union of two weighted graphs G and W and an integer k, we are asked to find a k-edge weighted graph W k such that G+W k is a good spectral sparsifer of G+W. We will refer to this problem as the subgraph (spectral) sparsification. We present a nontrivial condition on G and W such that a good sparsifier exists and give a polynomial-time algorithm to find the sparsifer. As an application of our technique, we show that for each positive integer k, every n-vertex weighted graph has an (n-1+k)-edge spectral sparsifier with relative condition number at most n/k log n, ~O(log log n) where ~O() hides lower order terms. Our bound nearly settles a question left open by Spielman and Teng about ultrasparsifiers. We also present another application of our technique to spectral optimization in which the goal is to maximize the algebraic connectivity of a graph (e.g. turn it into an expander) with a limited number of edges.

Details
v2026.09.13