skip to main content

Title: Dynamic Maxflow via Dynamic Interior Point Methods
Award ID(s):
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)
Page Range / eLocation ID:
1215 to 1228
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We investigate how to model the beliefs of an agent who becomes more aware. We use the framework of Halpern and Rego (2013) by adding probability, and define a notion of a model transition that describes constraints on how, if an agent becomes aware of a new formula φ in state s of a model M, she transitions to state s* in a model M*. We then discuss how such a model can be applied to information disclosure. 
    more » « less
  2. null (Ed.)
  3. We introduce Dynamic Speckle Holography (DSH), a new technique that combines imaging and scattering to measure three dimensional maps of displacements as small as ten nanometers over several centimeters, greatly extending the capabilities of traditional imaging systems. We attain this sensitivity by imaging speckle patterns of light collected at three scattering angles and measuring the decay in the temporal correlation due to local motion. We use DSH to measure the strain field of a colloidal gel undergoing fracture and establish the surprising role of internal tension in driving the fracture. 
    more » « less
  4. null (Ed.)
  5. We study a dynamic version of the implicit trace estimation problem. Given access to an oracle for computing matrix-vector multiplications with a dynamically changing matrix A, our goal is to maintain an accurate approximation to A's trace using as few multiplications as possible. We present a practical algorithm for solving this problem and prove that, in a natural setting, its complexity is quadratically better than the standard solution of repeatedly applying Hutchinson's stochastic trace estimator. We also provide an improved algorithm assuming additional common assumptions on A's dynamic updates. We support our theory with empirical results, showing significant computational improvements on three applications in machine learning and network science: tracking moments of the Hessian spectral density during neural network optimization, counting triangles and estimating natural connectivity in a dynamically changing graph. 
    more » « less