1,721,003 research outputs found
Graph Reconstruction via MIS Queries
Get PDFIn the Graph Reconstruction (GR) problem, a player initially only knows the vertex set V of an input graph G = (V, E) and is required to learn its set of edges E. To this end, the player submits queries to an oracle and must deduce E from the oracle’s answers. Angluin and Chen [Journal of Computer and System Sciences, 2008] resolved the number of Independent Set (IS) queries necessary and sufficient for GR on m-edge graphs. In this setting, each query consists of a subset of vertices U ⊆ V, and the oracle responds with a boolean, indicating whether U is an independent set in G. They gave algorithms that use O(m ⋅ log n) IS queries, which is best possible. In this paper, we initiate the study of GR via Maximal Independent Set (MIS) queries, a more powerful variant of IS queries. Given a query U ⊆ V, the oracle responds with any, potentially adversarially chosen, maximal independent set I ⊆ U in the induced subgraph G[U].We show that, for GR, MIS queries are strictly more powerful than IS queries when parametrized by the maximum degree Δ of the input graph. We give tight (up to poly-logarithmic factors) upper and lower bounds for this problem: 1) We observe that the simple strategy of taking uniform independent random samples of V and submitting those to the oracle yields a non-adaptive randomized algorithm that executes O(Δ² ⋅ log n) queries and succeeds with high probability. This should be contrasted with the fact that Ω(Δ ⋅ n ⋅ log(n/Δ)) IS queries are required for such graphs, which shows that MIS queries are strictly more powerful than IS queries. Interestingly, combining the strategy of taking uniform random samples of V with the probabilistic method, we show the existence of a deterministic non-adaptive algorithm that executes O(Δ³ ⋅ log(n/Δ)) queries.2) Regarding lower bounds, we prove that the additional Δ factor when going from randomized non-adaptive algorithms to deterministic non-adaptive algorithms is necessary. We show that every non-adaptive deterministic algorithm requires Ω(Δ³ / log² Δ) queries. For arbitrary randomized adaptive algorithms, we show that Ω(Δ²) queries are necessary in graphs of maximum degree Δ, and that Ω(log n) queries are necessary, even when the input graph is an n-vertex cycle
When Is Amplification Necessary for Composition in Randomized Query Complexity?
No full textSuppose we have randomized decision trees for an outer function f and an inner function g. The natural approach for obtaining a randomized decision tree for the composed function (f∘ gⁿ)(x¹,…,xⁿ) = f(g(x¹),…,g(xⁿ)) involves amplifying the success probability of the decision tree for g, so that a union bound can be used to bound the error probability over all the coordinates. The amplification introduces a logarithmic factor cost overhead. We study the question: When is this log factor necessary? We show that when the outer function is parity or majority, the log factor can be necessary, even for models that are more powerful than plain randomized decision trees. Our results are related to, but qualitatively strengthen in various ways, known results about decision trees with noisy inputs.THL
Recommended from our members
Testing and Learning in High-Dimensions: Monotonicity Testing, Directed Isoperimetry, and Convex Sets
Get PDFThis thesis studies testing and learning of monotone functions, k-monotone functions, and convex sets over high-dimensional domains. Our primary focus is monotonicity testing, which has been one of the central problems in the field of property testing since its beginnings in the late 90's. Monotonicity testing has generated a lot of interest, partially due to its connection to isoperimetric inequalities, which are a fundamental tool in Boolean function analysis. Our secondary focus is on testing and learning convex sets. Our contributions are presented in four parts summarized as follows:1) We present a nearly optimal non-adaptive monotonicity testing algorithm for Boolean functions over d-dimensional hypergrids and continuous product spaces. Among other technical contributions, a central tool in our proof is a new isoperimetric inequality for Boolean functions over hypergrids.2) Given the impact of isoperimetric inequalities for testing monotonicity of Boolean functions, a natural question is whether these inequalities generalize to larger ranges. We give a black-box reduction showing that the known inequalities in this area generalize to real-valued functions. We use this result to obtain nearly optimal bounds for (non-adaptive, one-sided error) monotonicity testing parameterized by the range size and an improved upper bound for approximating the distance to monotonicity of real-valued functions on the hypercube. 3) We present nearly matching upper and lower bounds for sample-based testing and learning of k-monotone functions over hypercubes and continuous product spaces.4) Motivated by the limited understanding of convexity testing in high-dimensions we initiate the study of convex sets over the ternary hypercube, which is the simplest high-dimensional domain where convexity is a non-trivial property. We obtain (i) nearly tight bounds on the edge-boundary of convex sets in this domain, (ii) new upper and lower bounds for sample-based testing and learning, and (iii) nearly matching upper and lower bounds for non-adaptive testing with one-sided error
Partial Minimum Branching Program Size Problem Is ETH-Hard
Get PDFWe show that assuming the Exponential Time Hypothesis, the Partial Minimum Branching Program Size Problem ({MBPSP}^{*}) requires superpolynomial time. This result also applies to the partial minimization problems for many interesting subclasses of branching programs, such as read-k branching programs and OBDDs.
Combining these results with the recent unconditional lower bounds for {MCSP} [Ludmila Glinskih and Artur Riazanov, 2022], we obtain an unconditional superpolynomial lower bound on the size of Read-Once Nondeterministic Branching Programs (1- NBP) computing the total versions of the minimum BP, read-k-BP, and OBDD size problems.
Additionally we show that it is NP-hard to check whether a given BP computing a partial Boolean function can be compressed to a BP of a given size
A Quantum Unique Games Conjecture
Get PDFAfter the NP-hardness of computational problems such as 3SAT and MaxCut was established, a natural next step was to explore whether these problems remain hard to approximate. While the quantum nonlocal games extensions of some of these problems are known to be hard - indeed undecidable - their inapproximability remains largely unresolved. In this work, we introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial role in studying the inapproximability of quantum constraint satisfaction problems as they do in the classical setting
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Learning discrete Markov Random Fields with nearly optimal runtime and sample complexity
No full textPresented as part of the Workshop on Algorithms and Randomness on May 17, 2018 at 11:30 a.m. in the Klaus Advanced Computing Building, Room 1116.Raghu Meka is an Associate Professor in the Computer Science Department at the University of California, Los Angeles. He is broadly interested in complexity theory, learning and probability theory.Runtime: 47:20 minutesWe give an algorithm for learning the structure of an undirected graphical model that has essentially optimal sample complexity and running time. We make no assumptions on the structure of the graphical model. For Ising models, this subsumes and improves on all prior work. For general t-wise MRFs, these are the first results of their kind.
Our approach is new and uses a multiplicative-weight update algorithm. Our algorithm-- Sparsitron-- is easy to implement (has only one parameter) and holds in the online setting. It also gives the first provably efficient solution to the problem of learning sparse Generalized Linear Models (GLMs).
Joint work with Adam Klivans
Front Matter, Table of Contents, Preface, Conference Organization
No full textFront Matter, Table of Contents, Preface, Conference Organizatio
- …
