检索结果-内蒙古大学图书馆

29th annual acm-siam symposium on discrete algorithms (SODA)

作者： Chierichetti, Flavio Kumar, Ravi Tomkins, Andrew Sapienza Univ Rome Rome Italy Google Mountain View CA USA

ISBN: (纸本)9781611975031

In this paper we study the well-known family of Random Utility Models, developed over 50 years ago to codify rational user behavior in choosing one item from a finite set of options. In this setting each user draws i.i.d. from some distribution a utility function mapping each item in the universe to a real-valued utility. the user is then offered a subset of the items, and selects the one of maximum utility. A MAX-DIST oracle for this choice model takes any subset of items and returns the probability (over the distribution of utility functions) that each will be selected. A discrete choice algorithm, given access to a MAX-DIST oracle, must return a function that approximates the oracle. We show three primary results. First, we show that any algorithm exactly reproducing the oracle must make exponentially many queries. Second, we show an equivalent representation of the distribution over utility functions, based on permutations, and show that if this distribution has support size k, then it is possible to approximate the oracle using O(nk) queries. Finally, we consider settings in which the subset of items is always small. We give an algorithm that makes less than n((1 - epsilon/2)K) queries, each to sets of size at most (1 - epsilon/2) K, in order to approximate the MAX-DIST oracle on every set of size vertical bar T vertical bar <= K with statistical error at most epsilon. In contrast, we show that any algorithm that queries for subsets of size 2(O)(root log n) must make maximal statistical error on some large sets.

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

Testing Conditional Independence of discrete Distributions 2018

Testing Conditional Independence of Discrete Distributions

引用

50th annual acm SIGACT symposium on the theory of Computing (STOC)

作者： Canonne, Clement L. Diakonikolas, Ilias Kane, Daniel M. Stewart, Alistair Stanford Univ Stanford CA 94305 USA Univ Southern Calif Los Angeles CA USA Univ Calif San Diego La Jolla CA 92093 USA

ISBN: (纸本)9781450355599

We study the problem of testing conditional independence for discrete distributions. Specifically, given samples from a discrete random variable (X, Y, Z) on domain [Lambda(1)] x [Lambda(2)] x [n], we want to distinguish, with probability at least 2/3, between the case that X and Y are conditionally independent given Z from the case that (X, Y, Z) is epsilon-far, in l(1)-distance, from every distribution that has this property. Conditional independence is a concept of central importance in probability and statistics with a range of applications in various scientific domains. As such, the statistical task of testing conditional independence has been extensively studied in various forms within the statistics and econometrics communities for nearly a century. Perhaps surprisingly, this problem has not been previously considered in the framework of distribution property testing and in particular no tester with sublinear sample complexity is known, even for the important special case that the domains of X and Y are binary. the main algorithmic result of this work is the first conditional independence tester with sublinear sample complexity for discrete distributions over [Lambda(1)] x [Lambda(2)] x [n]. To complement our upper bounds, we prove information-theoretic lower bounds establishing that the sample complexity of our algorithm is optimal, up to constant factors, for a number of settings. Specifically, for the prototypical setting when Lambda(1), Lambda(2) = 0(1), we show that the sample complexity of testing conditional independence (upper bound and matching lower bound) is theta (max (n(1/2)/epsilon(2), min(n(7/8)/epsilon, n(6/7)/epsilon(8/7)))) To obtain our tester, we employ a variety of tools, including (1) a suitable weighted adaptation of the "flattening" technique, and (2) the design and analysis of an optimal (unbiased) estimator for the following statistical problem of independent interest: Given a degree-d polynomial Q : R-n -> R and sample access to a d

关键词： Distribution testing property testing probability distributions conditional independence discrete distributions sublinear algorithms hypothesis testing

来源：评论

学校读者我要写书评

暂无评论

Metric embeddings with outliers 28

Metric embeddings with outliers

引用

28th annual acm-siam symposium on discrete algorithms (SODA)

作者： Sidiropoulos, Anastasios Wang, Dingkang Wang, Yusu Ohio State Univ Dept Comp Sci & Engn Columbus OH 43210 USA Ohio State Univ Dept Math 231 W 18th Ave Columbus OH 43210 USA

ISBN: (纸本)9781611974782

We initiate the study of metric embeddings with outliers. Given some finite metric space we wish to remove a small set of points and to find either an isometric or a low-distortion embedding of the remaining points into some host metric space. this is a natural problem that captures scenarios where a small fraction of points in the input corresponds to noise. We present polynomial-time approximation algorithms for computing outlier embeddings into Euclidean space, trees, and ultrametrics. In the case of isometric embeddings the objective is to minimize the number of outliers, while in the case of non-isometrics we have a bi-criteria optimization problem where the goal is to minimize both the number of outliers and the distortion. We complement our approximation algorithms with NP-hardness results for these problems. We conclude with a brief experimental evaluation of our non-isometric outlier embedding on synthetic and real-world data sets.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Linear Diophantine Equations, Group CSPs, and Graph Isomorphism 28

Linear Diophantine Equations, Group CSPs, and Graph Isomorph...

引用

28th annual acm-siam symposium on discrete algorithms (SODA)

作者： Berkholz, Christoph Grohe, Martin Humboldt Univ Berlin Germany Rhein Westfal TH Aachen Aachen Germany

ISBN: (纸本)9781611974782

In recent years, we have seen several approaches to the graph isomorphism problem based on "generic" mathematical programming or algebraic (Grobner basis) techniques. For most of these, lower bounds have been established. In fact, it has been shown that the pairs of non-isomorphic CFI-graphs (introduced by Cai, Furer, and Immerman in 1992 as hard examples for the combinatorial Weisfeiler-Leman algorithm) cannot be distinguished by these mathematical algorithms. A notable exception were the algebraic algorithms over the field F-2 for which no lower bound was known. Another, in some way even stronger, approach to graph isomorphism testing is based on solving systems of linear Diophantine equations (that is, linear equations over the integers), which is known to be possible in polynomial time. So far, no lower bounds for this approach were known. Lower bounds for the algebraic algorithms can best be proved in the framework of proof complexity, where they can be phrased as lower bounds for algebraic proof systems such as Nullstellensatz or the (more powerful) polynomial calculus. We give new hard examples for these systems: families of pairs of non-isomorphic graphs that are hard to distinguish by polynomial calculus proofs simultaneously over all prime fields, including F2, as well as examples that are hard to distinguish by the systems-of-linear-Diophantine-equations approach. In a previous paper, we observed that the CFI-graphs are closely related to what we call "group CSPs": constraint satisfaction problems where the constraints are membership tests in some coset of a subgroup of a cartesian power of a base group (Z(2) in the case of the classical CFI-graphs). Our new examples are also based on group CSPs (for Abelian groups), but here we extend the CSPs by a few non-group constraints to obtain even harder instances for graph isomorphism.

关键词： Constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Reordering Buffers with Logarithmic Diameter Dependency for Trees 28

Reordering Buffers with Logarithmic Diameter Dependency for ...

引用

28th annual acm-siam symposium on discrete algorithms (SODA)

作者： Englert, Matthias Racke, Harald Univ Warwick Dept Comp Sci Coventry W Midlands England Univ Warwick Ctr Discrete Math & Its Applicat DIMAP Coventry W Midlands England Tech Univ Munich Dept Informat Munich Germany

ISBN: (纸本)9781611974782

In the reordering buffer problem a sequence of items located in a metric space arrive online, and have to be processed by a single server moving within the metric space. At any point in time, the first k still unprocessed items from the sequence are available for processing and the server has to select one of these items and process it by visiting its location. the goal is to process all items while minimizing the total distance the server moves. Englert, Racke, Westermann (STOC'07) gave a deterministic O(D . log k)-competitive online algorithm for weighted tree metrics with hop-diameter D. We improve the analysis of this algorithm and significantly improve the dependency on D. Specifically, we show that the algorithm is in fact O(log D+log k)-competitive. Our analysis is quite robust. Even when an optimal algorithm, to which we compare the online algorithm, is allowed to choose between the first h > k unprocessed items, the online algorithm is still O(h . (log D+log h)/k)competitive. For h = (1 + epsilon) . k, with constant epsilon > 0, this is optimal. Our results also imply better competitive ratio for general metric spaces, improving the randomized O(log n . log(2) k) result for n-point metric spaces from STOC'07 to O(log n . log k).

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

Proceedings of the Annual ACM-SIAM Symposium on Discrete Alg...

引用

28th annual acm-siam symposium on discrete algorithms, SODA 2017

ISBN: (纸本)9781611974782

the proceedings contain 181 papers. the topics discussed include: a framework for similarity search with space-time tradeoffs using locality-sensitive filtering;LSH forest: practical algorithms made theoretical;faster approximation schemes for the two-dimensional knapsack problem;split packing: an algorithm for packing circles with optimal worst-case density;local search for max-sum diversification;maximum scatter tsp in doubling metrics;exploring an infinite space with finite memory scouts;parameter-free locality sensitive hashing for spherical range reporting;distance sensitive bloom filters without false negatives;optimal approximate polytope membership;and massively-parallel similarity join, edge-isoperimetry, and distance correlations on the hypercube.

关键词：

来源：评论

学校读者我要写书评

暂无评论

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

引用

acm TRANSACTIONS ON algorithms 2018年第3期14卷 28-28页

作者： Hopkins, Samuel B. Kothari, Pravesh Potechin, Aaron Henry Raghavendra, Prasad Schramm, Tselil Cornell Univ 107 Hoy Rd Ithaca NY 14853 USA UT Austin Austin TX USA Univ Calif Berkeley 253 Cory Hall Berkeley CA 94720 USA Princeton Univ 35 Olden St Princeton NJ 08540 USA Univ Chicago 1100 East 58th St Chicago IL 60637 USA Harvard John A Paulson Sch Engn & Appl Sci Pierce Hall29 Oxford St Cambridge MA 02138 USA

the problem of finding large cliques in random graphs and its "planted" variant, where one wants to recover a clique of size omega >> log (n) added to an Erdos-Renyi graph G similar to G(n, 1/2), have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size omega = Omega(root n). By contrast, information theoretically, one can recover planted cliques so long as omega >> log (n). In this work, we continue the investigation of algorithms from the Sum of Squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson [2] and Deshpande and Montanari [25]. Our main result is that degree four SoS does not recover the planted clique unless omega >> root n/polylog n, improving on the bound omega >> n(1/3) due to Reference [25]. An argument of Kelner shows that the this result cannot be proved using the same certificate as prior works. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by "correcting" the certificate of References [2, 25, 27].

关键词： Sum of Squares method planted clique random matrices

来源：评论

学校读者我要写书评

暂无评论

Recognizing weak embeddings of graphs 18

Recognizing weak embeddings of graphs

引用

Proceedings of the Twenty-Ninth annual acm-siam symposium on discrete algorithms

作者： Hugo A. Akitaya Radoslav Fulek Csaba D. Tóth Tufts University Institute of Science and Technology Klosterneuburg Austria California State University Northridge and Tufts University

ISBN: (纸本)9781611975031

We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ϕ : G → M of a graph G into a 2-manifold M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. this raises the computational problem of deciding whether a given map ϕ : G → M comes from an embedding. A map ϕ : G → M is a weak embedding if it can be perturbed into an embedding φε : G → M with [Equation] for every ε > 0.A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kynčl [14], which reduces to solving a system of linear equations over Z2. It runs in O(n2ω) ≤ O(n4.75) time, where ω ≈ 2.373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually "untangles" the image ψ(G) into an embedding φ(G), or reports that φ is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Reordering Buffers with Logarithmic Diameter Dependency for Trees 17

Reordering Buffers with Logarithmic Diameter Dependency for ...

引用

annual acm-Society for Industrial and Applied Mathmatics symposium on discrete algorithms

作者： Matthias Englert Harald Racke Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP) University of Warwick Department of Informatics Technical University Munich

ISBN: (纸本)9781510836358

In the reordering buffer problem a sequence of items located in a metric space arrive online, and have to be processed by a single server moving within the metric space. At any point in time, the first k still unprocessed items from the sequence are available for processing and the server has to select one of these items and process it by visiting its location. the goal is to process all items while minimizing the total distance the server moves. Englert, Racke, Westermann (STOC'07) gave a deterministic O(D·log k)-competitive online algorithm for weighted tree metrics with hop-diameter D. We improve the analysis of this algorithm and significantly improve the dependency on D. Specifically, we show that the algorithm is in fact O(log D+log k)-competitive. Our analysis is quite robust. Even when an optimal algorithm, to which we compare the online algorithm, is allowed to choose between the first h > k unprocessed items, the online algorithm is still O(h·(log D+log h)/k)-competitive. For h = (1 + ε)·k, with constant ε > 0, this is optimal. Our results also imply better competitive ratio for general metric spaces, improving the randomized O(log n · log~2 k) result for n-point metric spaces from STOC'07 to O(log n·log k).

关键词： metric space Servers algorithms Optimization algorithms DEPENDENCE analysis of algorithm Logarithmic

来源：评论

学校读者我要写书评

暂无评论

Proceedings of the annual acm-siam symposium on discrete algorithms

Proceedings of the Annual ACM-SIAM Symposium on Discrete Alg...

引用

27th annual acm-siam symposium on discrete algorithms, SODA 2016

ISBN: (纸本)9781510819672

the proceedings contain 146 papers. the topics discussed include: locality-sensitive hashing without false negatives;new directions in nearest neighbor searching with applications to lattice sieving;phase transitions in group testing;tight bounds for the distribution-free testing of monotone conjunctions;designing networks with good equilibria under uncertainty;characterization of strongly stable matchings;learning and efficiency in games with dynamic population;on dynamic approximate shortest paths for planar graphs with worst case costs;error amplification for pairwise spanner lower bounds;on notions of distortion and an almost minimum spanning tree with constant average distortion;approximately efficient double auctions with strong budget balance;and interpolating between truthful and non-truthful mechanisms for combinatorial auctions.

关键词：

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：