4 papers
Pseudodeterministic Algorithms for Minimum Cut Problems
Aryan Agarwala, Nithin Varma
In this paper, we present efficient pseudodeterministic algorithms for both the global minimum cut and minimum s-t cut problems. The running time of our algorithm for the global mi…
Linear Matroid Intersection is in Catalytic Logspace
Aryan Agarwala, Yaroslav Alekseev, Antoine Vinciguerra
Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks…
Bipartite Matching is in Catalytic Logspace
Aryan Agarwala, Ian Mertz
Matching is a central problem in theoretical computer science, with a large body of work spanning the last five decades. However, understanding matching in the time-space bounded s…
A Space Lower Bound for Approximate Membership with Duplicate Insertions or Deletions of Nonelements
Aryan Agarwala, Guy Even
Designs of data structures for approximate membership queries with false-positive errors that support both insertions and deletions stipulate the following two conditions: (1) Dupl…