期刊： SIAM JOURNAL ON COMPUTING, 2021; 50 (2)
In this paper, we study the problem of sampling from a graphical model when the model itself is changing dynamically with time. This problem derives i......
期刊： SIAM JOURNAL ON COMPUTING, 2021; 50 (3)
We present a spectral analysis of a continuous scaling algorithm for matrix scaling and operator scaling. The main result is that if the input matrix ......
期刊： SIAM JOURNAL ON COMPUTING, 2021; 50 (4)
We present self-adjusting data structures for answering point location queries in convex and connected subdivisions. Let n be the number of vertices i......
期刊： SIAM JOURNAL ON COMPUTING, 2021; 50 (2)
In this paper we explore fundamental problems in randomized communication complexity such as computing SetIntersection on sets of size k and EqualityT......
期刊： SIAM JOURNAL ON COMPUTING, 2021; 50 (3)
In the 1970s, Lovasz built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings [Proceedings of FCT, 1979, pp. 5......
期刊： SIAM JOURNAL ON COMPUTING, 2020; 49 (2)
Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum......
期刊： SIAM JOURNAL ON COMPUTING, 2020; 49 (4)
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, ......
期刊： SIAM JOURNAL ON COMPUTING, 2020; 49 (5)
We consider a fundamental problem in microeconomics: selling a single item to a number of potential buyers, whose values are drawn from known independ......
期刊： SIAM JOURNAL ON COMPUTING, 2020; 49 (6)
We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. A deterministic structure processes ......
期刊： SIAM JOURNAL ON COMPUTING, 2019; 48 (2)
We show that every circuit with AND, OR, NOT, and MODm gates, m is an element of Z(+), of polynomial size and depth d can be reduced to a depth-2, SYM......
期刊： SIAM JOURNAL ON COMPUTING, 2019; 48 (2)
A set D of vertices of a graph G is a dominating set if every vertex of G is contained in D or adjacent to some vertex of D. The number of vertices in......
期刊： SIAM JOURNAL ON COMPUTING, 2019; 48 (4)
We give a fully polynomial-time approximation scheme (FPTAS) to count the number 1 4 of q-colorings for k-uniform hypergraphs with maximum degree Delt......
期刊： SIAM JOURNAL ON COMPUTING, 2018; 47 (1)
In the polytope membership problem, a convex polytope K in R-d is given, and the objective is to preprocess K into a data structure so that, given any......
期刊： SIAM JOURNAL ON COMPUTING, 2018; 47 (3)
Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Boolean ......
期刊： SIAM JOURNAL ON COMPUTING, 2018; 47 (3)
We study the problem of setting a price for a potential buyer with a valuation drawn from an unknown distribution D. The seller has "data" about D in ......
