In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices.In the first part, we consider algorithms for building ...
We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...
We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...
Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022
The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...
We study the computations that Bayesian agents undertake when exchanging opinions over a network. The agents act repeatedly on their private information and take myopic actions that maximize their expected utility according to a fully rational posterior be ...
Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. ...
This paper considers vessel scheduling with pilotage and tugging constraints in berthing operations with channel restrictions at seaports. To our knowledge, pilotage and tugging requirements have not been simultaneously considered in the literature. This w ...
We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021
This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become prohibitively expensive. Processing modern datasets requir ...
Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...
Data cleaning has become an indispensable part of data analysis due to the increasing amount of dirty data. Data scientists spend most of their time preparing dirty data before it can be used for data analysis. Existing solutions that attempt to automate t ...
