The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
The notion of contact algebra is one of the main tools in mereotopology. This paper considers a generalisation of contact algebra (called extended distributive contact lattice) and the so called extended contact algebras which extend the language of contact algebras by the predicates covering and internal connectedness.
Minimal solutions play a crucial role in description of all solutions to a fuzzy relational equation. The reason is that all solutions form a convex set with respect to (fuzzy) set inclusion; therefore, having all extremal solutions, we can represent the entire solution set as a union of intervals bounded from above by the greatest solution and from below by the minimal solutions. However, when computing...
We present a deterministic distributed algorithm that computes a (2δ-1)-edge-coloring, or even list-edge-coloring, in any n-node graph with maximum degree δ, in O(log^8 δ ⋅ log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms} from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e.g.,...
In the set disjointess problem, we have k players, each with a private input X^i ⊆ [n], and the goal is for the players to determine whether or not their sets have a global intersection. The players communicate over a shared blackboard, and we charge them for each bit that they write on the board.We study the trade-off between the number of interaction rounds we allow the players, and the...
We examine the power of statistical zero knowledge proofs (captured by the complexity class SZK) and their variants. First, we give the strongest known relativized evidence that SZK contains hard problems, by exhibiting an oracle relative to which SZK (indeed, even NISZK) is not contained in the class UPP, containing those problems solvable by randomized algorithms with unbounded error. This answers...
We give a deterministic \tilde{O}(\log n)-space algorithm for approximately solving linear systems given by Laplacians of undirected graphs, and consequently also approximating hitting times, commute times, and escape probabilities for undirected graphs. Previously, such systems were known to be solvable by randomized algorithms using O(\log n) space (Doron, Le Gall, and Ta-Shma, 2017) and hence by...
We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in O(\log^3 n) time on n^{O(\log^2 n)} processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani [1987] to obtain a Randomized NC algorithm...
In a non-uniform Constraint Satisfaction problem CSP(Γ), where G is a set of relations on a finite set A, the goal is to find an assignment of values to variables subject to constraints imposed on specified sets of variables using the relations from Γ. The Dichotomy Conjecture for the non-uniform CSP states that for every constraint language \Gm the problem CSP(Γ)...
The approximate degree of a Boolean function f: {-1, 1}^n ↦ {-1, 1} is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits.Specifically, we show how to transform any Boolean function f with approximate...
The random k-SAT model is the most important and well-studied distribution over k-SAT instances. It is closely connected to statistical physics and is a benchmark for satisfiability algorithms. We show that when k = Θ(log n), any Cutting Planes refutation for random k-SAT requires exponential size in the interesting regime where the number of clauses guarantees that the formula is unsatisfiable...
We consider the fundamental derandomization problem of deterministically finding a satisfying assignment to a CNF formula that has many satisfying assignments. We give a deterministic algorithm which, given an n-variable \poly(n)-clause CNF formula F that has at least ≥ 2^n satisfying assignments, runs in time \[ n^{\tilde{O}(\log\log n)^2} \] for ≥ \ge 1/\polylog(n) and outputs...
We develop several efficient algorithms for the classical Matrix Scaling} problem, which is used in many diverse areas, from preconditioning linear systems to approximation of the permanent. On an input n× n matrix A, this problem asks to find diagonal (scaling) matrices X and Y (if they exist), so that X A Y ε-approximates a doubly stochastic matrix, or more generally a matrix...
We present a new distributed} model of probabilistically checkable proofs (PCP). A satisfying assignment x ∊ \{0,1\}^n to a CNF formula \phi is shared between two parties, where Alice knows x_1, \dots, x_{n/2, Bob knows x_{n/2+1},\dots,x_n, and both parties know \phi. The goal is to have Alice and Bob jointly write a PCP that x satisfies \phi, while exchanging little or no information....
We consider properties of edge-colored vertex-ordered graphs} – graphs with a totally ordered vertex set and a finite set of possible edge colors – showing that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries. We also explain how the proof can be adapted to show that any hereditary property of two-dimensional matrices...
Non-malleable commitments, introduced by Dolev, Dwork and Naor (STOC 1991), are a fundamental cryptographic primitive, and their round complexity has been a subject of great interest. And yet, the goal of achieving non-malleable commitments with only one or two rounds} has been elusive. Pass (TCC 2013) captured this difficulty by proving important impossibility results regarding two-round non-malleable...
In the communication problem UR (universal relation), Alice and Bob respectively receive x, y ∊{0,1\}^n with the promise that x≠ y. The last player to receive a message must output an index i such that x_i≠ y_i. We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly \Theta(\min\{n,\log(1/δ)\log^2(\frac...
We provide algorithms that learn simple auctions whose revenue is approximately optimal in multi-item multi-bidder settings, for a wide range of bidder valuations including unit-demand, additive, constrained additive, XOS, and subadditive. We obtain our learning results in two settings. The first is the commonly studied setting where sample access to the bidders distributions over valuations is given,...
For any n-bit boolean function f, we show that the randomized communication complexity of the composed function f o g^n, where g is an index gadget, is characterized by the randomized decision tree complexity of f. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs. quantum) automatically imply analogous separations in communication complexity.
We provide a combinatorial characterization of all testable properties of k-graphs (i.e. k-uniform hypergraphs). Here, a k-graph property P is testable if there is a randomized algorithm which makes a bounded number of edge queries and distinguishes with probability 2/3 between k-graphs that satisfy P and those that are far from satisfying P. For the 2-graph case, such a combinatorial characterization...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.