waashk/dblp huggingface dataset:
mixing time for the solid-on-solid model. we analyze the mixing time of a natural local markov chain (the glauber dynamics) on configurations of the solid-on-solid model of statistical physics. this model has been proposed, among other things, as an idealization of the behavior of contours in the ising model at low temperatures. our main result is an upper bound on the mixing time of o~(n3.5), which is tight within a factor of o~(√n). the proof, which in addition gives insight into the actual evolution of the contours, requires the introduction of several novel analytical techniques that we conjecture will have other applications.
a nearly optimal oracle for avoiding failed vertices and edges. we present an improved oracle for the distance sensitivity problem. the goal is to preprocess a directed graph g = (v,e) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from x to y that does not go through some failed vertex or edge f. the previous best algorithm produces an oracle of size ~o(n2) that has an o(1) query time, and an ~o(n2√m) construction time. it was a randomized monte carlo algorithm that worked with high probability. our oracle also has a constant query time and an ~o(n2) space requirement, but it has an improved construction time of ~o(mn), and it is deterministic. note that o(1) query, o(n2) space, and o(mn) construction time is also the best known bound (up to logarithmic factors) for the simpler problem of finding all pairs shortest paths in a weighted, directed graph. thus, barring improved solutions to the all pairs shortest path problem, our oracle is optimal up to logarithmic factors.
non-monotone submodular maximization under matroid and knapsack constraints. submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including max cut in directed/undirected graphs and in hypergraphs, certain constraint satisfaction problems, maximum entropy sampling, and maximum facility location problems. unlike submodular minimization, submodular maximization is np-hard. in this paper, we give the first constant-factor approximation algorithm for maximizing any non-negative submodular function subject to multiple matroid or knapsack constraints. we emphasize that our results are for non-monotone submodular functions. in particular, for any constant k, we present a (1/k+2+1/k+ε)-approximation for the submodular maximization problem under k matroid constraints, and a (1/5-ε)-approximation algorithm for this problem subject to k knapsack constraints (ε>0 is any constant). we improve the approximation guarantee of our algorithm to 1/k+1+{1/k-1}+ε for k≥2 partition matroid constraints. this idea also gives a ({1/k+ε)-approximation for maximizing a monotone submodular function subject to k≥2 partition matroids, which improves over the previously best known guarantee of 1/k+1.
twice-ramanujan sparsifiers. we prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. as linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. in particular, we prove that for every d > 1 and every undirected, weighted graph g = (v,e,w) on n vertices, there exists a weighted graph h=(v,f,~{w}) with at most ⌈d(n-1)⌉ edges such that for every x ∈ rv, [xt lg x ≤ xt lh x ≤ ((d+1+2√d)/(d+1-2√d)) • xt lg x] where lg and lh are the laplacian matrices of g and h, respectively. thus, h approximates g spectrally at least as well as a ramanujan expander with dn/2 edges approximates the complete graph. we give an elementary deterministic polynomial time algorithm for constructing h.
csp gaps and reductions in the lasserre hierarchy. we study integrality gaps for sdp relaxations of constraint satisfaction problems, in the hierarchy of sdps defined by lasserre. schoenebeck [23] recently showed the first integrality gaps for these problems, showing that for max k-xor, the ratio of the sdp optimum to the integer optimum may be as large as 2 even after ω(n) rounds of the lasserre hierarchy. we show that for the general max k-csp problem, this ratio can be as large as 2k/2k - ε when the alphabet is binary and qk/q(q-1)k - ε when the alphabet size a prime q, even after ω(n) rounds of the lasserre hierarchy. we also explore how to translate gaps for csp into integrality gaps for other problems using reductions, and establish sdp gaps for maximum independent set, approximate graph coloring, chromatic number and minimum vertex cover. for independent set and chromatic number, we show integrality gaps of n/2o(√(log n log log n)) even after 2ω(√(log n log log n)) rounds. in case of approximate graph coloring, for every constant l, we construct graphs with chromatic number ω(2l/2/l2), which admit a vector l-coloring for the sdp obtained by ω(n) rounds. for vertex cover, we show an integrality gap of 1.36 for ω(nδ) rounds, for a small constant δ. the results for csps provide the first examples of ω(n) round integrality gaps matching hardness results known only under the unique games conjecture. this and some additional properties of the integrality gap instance, allow for gaps for in case of independent set and chromatic number which are stronger than the np-hardness results known even under the unique games conjecture.
inaccessible entropy. we put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. specifically, we say that the i'th round of a protocol (a,b) has *accessible entropy* at most k, if no polynomial-time strategy a* can generate messages for a such that the entropy of its message in the i'th round has entropy greater than k when conditioned both on prior messages of the protocol and on prior coin tosses of a*. we say that the protocol has *inaccessible entropy* if the total accessible entropy (summed over the rounds) is noticeably smaller than the real entropy of a's messages, conditioned only on prior messages (but not the coin tosses of a). as applications of this notion, we -- give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions. -- prove that constant-round statistically hiding commitments are necessary for constructing constant-round zero-knowledge proof systems for np that remain secure under parallel composition (assuming the existence of one-way functions).
green's conjecture and testing linear-invariant properties. given a set of linear equations mx=b, we say that a set of integers s is (m,b)-free if it contains no solution to this system of equations. motivated by questions related to testing linear-invariant properties of boolean functions, as well as recent investigations in additive number theory, the following conjecture was raised (implicitly) by green and by bhattacharyya, chen, sudan and xie: we say that a set of integers s ⊆ [n], is ε-far from being (m,b)-free if one needs to remove at least ε n elements from s in order to make it (m,b)-free. the above conjecture states that for any system of homogenous linear equations mx=0 and for any ε >0 there is a constant time algorithm that can distinguish with high probability between sets of integers that are (m,0)-free from sets that are ε-far from being (m,0)-free. or in other words, that for any m there is an efficient testing algorithm for the property of being (m,0)-free. in this paper we confirm the above conjecture by showing that such a testing algorithm exists even for non-homogenous linear equations. as opposed to most results on testing boolean functions, which rely on algebraic and analytic arguments, our proof relies on results from extremal hypergraph theory, such as the recent removal lemmas of gowers, rodl et al. and austin and tao.
non-malleable extractors and symmetric key cryptography from weak secrets. we study the question of basing symmetric key cryptography on weak secrets. in this setting, alice and bob share an n-bit secret w, which might not be uniformly random, but the adversary has at least k bits of uncertainty about it (formalized using conditional min-entropy). since standard symmetric-key primitives require uniformly random secret keys, we would like to construct an authenticated key agreement protocol in which alice and bob use w to agree on a nearly uniform key r, by communicating over a public channel controlled by an active adversary eve. we study this question in the information theoretic setting where the attacker is computationally unbounded. we show that single-round (i.e. one message) protocols do not work when k ≤ n/2, and require poor parameters even when n/2 on the other hand, for arbitrary values of k, we design a communication efficient two-round (challenge-response) protocol extracting nearly k random bits. this dramatically improves the previous construction of renner and wolf [32], which requires θ(λ + log(n)) rounds where λ is the security parameter. our solution takes a new approach by studying and constructing "non-malleable" seeded randomness extractors -- if an attacker sees a random seed x and comes up with an arbitrarily related seed x', then we bound the relationship between r= ext(w;x) and r' = ext(w;x'). we also extend our two-round key agreement protocol to the "fuzzy" setting, where alice and bob share "close" (but not equal) secrets wa and wb, and to the bounded retrieval model (brm) where the size of the secret w is huge.
efficient discrete-time simulations of continuous-time quantum query algorithms. the continuous-time query model is a variant of the discrete query model in which queries can be interleaved with known operations (called "driving operations") continuously in time. we show that any quantum algorithm in this model whose total query time is t can be simulated by a quantum algorithm in the discrete-time query model that makes o(t log t / loglog t) subset o~(t) queries. this is the first such upper bound that is independent of the driving operations (i.e., it holds even if the norm of the driving hamiltonian is very large). a corollary is that any lower bound of t queries for a problem in the discrete-time query model immediately carries over to a lower bound of omega(t loglog t / log t) subset omega~(t) in the continuous-time query model.
non-malleability amplification. we show a technique for amplifying commitment schemes that are non-malleable with respect to identities of length t, into ones that are non-malleable with respect to identities of length ω(2t), while only incurring a constant overhead in round-complexity. as a result we obtain a construction of o(1)log* n-round (i.e., "essentially" constant-round) non-malleable commitments from any one-way function, and using a black-box proof of security.
approximating edit distance in near-linear time. we show how to compute the edit distance between two strings of length n up to a factor of 2(o-tilde(sqrt(log n))) in n(1+o(1)) time. this is the first sub-polynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art n(1/3+o(1)) approximation. previously, approximation of 2õ √log n) was known only for embedding edit distance into l1, and it is not known if that embedding can be computed in less than a quadratic time.
universally utility-maximizing privacy mechanisms. a mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. publishing fully accurate information maximizes utility while minimizing privacy, while publishing random noise accomplishes the opposite. privacy can be rigorously quantified using the framework of differential privacy, which requires that a mechanism's output distribution is nearly the same whether or not a given database row is included or excluded. the goal of this paper is strong and general utility guarantees, subject to differential privacy. we pursue mechanisms that guarantee near-optimal utility to every potential user, independent of its side information (modeled as a prior distribution over query results) and preferences (modeled via a loss function). our main result is: for each fixed count query and differential privacy level, there is a geometric mechanism m* -- a discrete variant of the simple and well-studied laplace mechanism -- that is simultaneously expected loss-minimizing for every possible user, subject to the differential privacy constraint. this is an extremely strong utility guarantee: every potential user u, no matter what its side information and preferences, derives as much utility from m* as from interacting with a differentially private mechanism mu that is optimally tailored to u. more precisely, for every user u there is an optimal mechanism mu for it that factors into a user-independent part (the geometric mechanism m*) followed by user-specific post-processing that can be delegated to the user itself. the first part of our proof of this result characterizes the optimal differentially private mechanism for a fixed but arbitrary user in terms of a certain basic feasible solution to a linear program with constraints that encode differential privacy. the second part shows that all of the relevant vertices of this polytope (ranging over all possible users) are derivable from the geometric mechanism via suitable remappings of its range.
a new line of attack on the dichotomy conjecture. the well known dichotomy conjecture of feder and vardi states that for every finite family γ of constraints csp(γ) is either polynomially solvable or np-hard. bulatov and jeavons reformulated this conjecture in terms of the properties of the algebra pol(γ), where the latter is the collection of those n-ary operations (n= 1,2,...) that keep all constraints in γ invariant. we show that the algebraic condition boils down to whether there are arbitrarily resilient functions in pol(γ). using this characterization and a result of dinur, friedgut and regev, we give an entirely new and transparent proof to the hell-nesetril theorem, which states that for a simple, connected and undirected graph h, the problem csp(h) is np-hard if and only if h is non-bipartite. we also introduce another notion of resilience (we call it strong resilience), and we use it to characterize csp problems that 'do not have the ability to count.' very recently this class has been shown to be equivalent with the the class of bounded width problems, i.e. the class of csps that be described by existential k-pebble games. what emerges from our research, is that certain important algebraic conditions that are usually expressed via identities have equivalent definitions that rely on asymptotic properties of term operations. our new notions have a potential to show hardness of csps (as demonstrated on the hell-nesetril theorem), or to prove their tractability.
tight lower bounds for greedy routing in uniform small world rings. we consider augmented ring-based networks with vertices 0,...,n-1, where each vertex is connected to its left and right neighbor and possibly to some further vertices (called long range contacts). the outgoing edges of a vertex v are obtained by choosing a subset d of {1,2,...n-1}, with 1, n-1 in d, at random according to a probability distribution mu on all such d and then for each i in d connecting v to (v+i) mod n by a unidirectional link. the choices for different v are done independently and uniformly in the sense that the same distribution mu is used for all v. the expected number of long range contacts is l=e(|d|)-2. motivated by kleinberg's (2000) small world graph model and packet routing strategies for peer-to-peer networks, the greedy routing algorithm on augmented rings, where a packet sitting in a node v is routed to the neighbor of v closest to the destination of the package, has been investigated thoroughly, both for the "one-sided case", where packets can travel only in one direction, and the "two-sided case", where there is no such restriction. in this paper, for both the one-sided and the two-sided case and for an arbitrary distribution mu, we prove a lower bound of omega((log n)2/l) on the expected number of hops that are needed by the greedy strategy to route a package between two randomly chosen vertices on the ring. this bound is tight for omega(1)
homology flows, cohomology cuts. we describe the first algorithms to compute maximum flows in surface-embedded graphs in near-linear time. specifically, given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, we can compute a maximum (s,t)-flow in o(g7 n log2 n log2 c) time for integer capacities that sum to c, or in (g log n)o(g) n time for real capacities. except for the special case of planar graphs, for which an o(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. a dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.
on the complexity of communication complexity. we consider the following question: given a two-argument boolean function f, represented as an n x n binary matrix, how hard is it to determine the (deterministic) communication complexity of f? we address two aspects of this question. on the computational side, we prove that, under appropriate cryptographic assumptions (such as the intractability of factoring), the deterministic communication complexity of f is hard to approximate to within some constant. under stronger (yet arguably reasonable) assumptions, we obtain even stronger hardness results that match the best known approximation. on the analytic side, we present a family of (two-argument) functions for which determining the deterministic communication complexity (or even obtaining non-trivial lower bounds on it) implies proving circuit lower bounds for some related functions. such connections between circuit complexity and communication complexity were known before (karchmer &#; wigderson, 1988) only in the more involved context of relations (search problems) but not in the context of functions (decision problems). this result, in particular, may explain the difficulty of analyzing the communication complexity of certain functions such as the "clique vs. independent-set" family of functions, introduced by yannakakis (1988).
holant problems and counting csp. we propose and explore a novel alternative framework to study the complexity of counting problems, called holant problems. compared to counting constrained satisfaction problems (csp), it is a refinement with a more explicit role for the function constraints. both graph homomorphism and csp can be viewed as special cases of holant problems. we prove complexity dichotomy theorems in this framework. because the framework is more stringent, previous dichotomy theorems for csp problems no longer apply. indeed, we discover surprising tractable subclasses of counting problems, which could not have been easily specified in the csp framework. the main technical tool we use and develop is holographic reductions. another technical tool used in combination with holographic reductions is polynomial interpolations. the study of holant problems led us to discover and prove a complexity dichotomy theorem for the most general form of boolean csp where every constraint function takes values in the complex number field {c}.
goal state optimization algorithm considering computational resource constraints and uncertainty in task execution time. a search methodology with goal state optimization considering computational resource constraints is proposed. the combination of ''an extended graph search methodology'' and ''parallelization of task execution and online planning'' makes it possible to solve the problem. the uncertainty of the task execution time is also considered. the problem can be solved by utilizing a random-based and/or a greedy-based graph-searching methodology. the proposed method is evaluated using a rearrangement problem of 20 movable objects with uncertainty in the task execution time, and the effectiveness is shown with simulation results.
location estimation for indoor autonomous vehicle navigation by omni-directional vision using circular landmarks on ceilings. a novel approach to location estimation by omni-directional vision for autonomous vehicle navigation in indoor environments using circular landmark information is proposed. a circular-shaped landmark is attached on a ceiling and an omni-directional camera is equipped on a vehicle to take upward-looking omni-directional images of the landmark. this way of image taking reduces possible landmark shape occlusion and image noise creation, which come from the existence of nearby objects or humans surrounding the vehicle. it is shown that the perspective shape of the circular landmark in the omni-directional image may be approximated by an ellipse by analytic formulas with good shape-fitting effect and fast computation speed. the parameters of the ellipse are then used for estimating the location of the vehicle with good precision for navigation guidance. both simulated and real images were tested and good experimental results confirm the feasibility of the proposed approach.
painting robot with multi-fingered hands and stereo vision. in this paper, we describe a painting robot with multi-fingered hands and stereo vision. the goal of this study is for the robot to reproduce the whole procedure involved in human painting. a painting action is divided into three phases: obtaining a 3d model, composing a picture model, and painting by a robot. in this system, various feedback techniques including computer vision and force sensors are used. as experiments, an apple and a human silhouette are painted on a canvas using this system.
mobile robot localization based on ultra-wide-band ranging: a particle filter approach. this article addresses the problem of mobile robot localization using ultra-wide-band (uwb) range measurements. uwb is a radio technology widely used for communications, that is recently receiving increasing attention for positioning applications. in these cases, the position of a mobile transceiver is determined from the distances to a set of fixed, well-localized beacons. though this is a well-known problem in the scientific literature (the trilateration problem), the peculiarities of uwb range measurements (basically, distance errors and multipath effects) demand a different treatment to other similar solutions, as for example, those based on laser. this work presents a thorough experimental characterization of uwb ranges within a variety of environments and situations. from these experiments, we derive a probabilistic model which is then used by a particle filter to combine different readings from uwb beacons as well as the vehicle odometry. to account for the possible offset error due to multipath effects, the state tracked by the particle filter includes the offset of each beacon in addition to the planar robot pose (x,y,@f), both estimated sequentially. we show navigation results for a robot moving in indoor scenarios covered by three uwb beacons that validate our proposal.