We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model t ...
This thesis explores the application of semiclassical methods in the study of states with large quantum numbers for theories invariant under internal symmetries.
In the first part of the thesis, we study zero-temperature superfluids. These provide a gener ...
Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best-known algorithm for k-means in Euclidean space with a provable guarantee is a simple local ...
Stochastic optimization is a popular modeling paradigm for decision-making under uncertainty and has a wide spectrum of applications in management science, economics and engineering. However, the stochastic optimization models one faces in practice are int ...
Symmetry and topology are fundamental properties of nature. Mathematics provides us with a general framework to understand these concepts. On one side, symmetry describes the invariance properties of an object for specific transformations. On the other sid ...
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...
In this paper, we verify the large scale structure consistency relations using N-body simulations, including modes in the highly nonlinear regime. These relations (pointed out by Kehagias & Riotto and Peloso & Pietroni) follow from the symmetry of the dyna ...
In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...
