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

algorithms and Lower Bounds for Comparator Circuits from Shrinkage

ALGORITHMICA 2023年第7期85卷 2131-2155页

作者： Cavalar, Bruno P. Lu, Zhenjian Univ Warwick Dept Comp Sci Coventry W Midlands England Univ Oxford Dept Comp Sci Oxford England

In this paper, we initiate the study of average-case complexity and circuit analysis algorithms for comparator circuits. Departing from previous approaches, we exploit the technique of shrinkage under random restrictions to obtain a variety of new results for this model. Among them, we show center dot Average-case Lower Bounds For every k = k(n) with k >= log n, there exists a polynomial-time computable function fk on n bits such that, for every comparator circuit C with at most n(1.5)/O (k center dot root log n) gates, we have Pr (x is an element of{0,1}n) [C(x) = fk (x)] <= 1/2 + 1/2(Omega(k)). This average-case lower bound matches the worst-case lower bound of Gal and Robere by letting k = O(log n). center dot # SAT algorithms There is an algorithm that counts the number of satisfying assignments of a given comparator circuit with at most n(1.5)/O (k center dot root log n) gates, in time 2(n-k) center dot poly(n), for any k <= n/4. The running time is non-trivial (i.e., 2(n)/n(omega(1))) when k =omega(log n). center dot Pseudorandom Generators and MCSP Lower Bounds There is a pseudorandom generator of seed length s(2/3+o(1)) that fools comparator circuits with s gates. Also, using this PRG, we obtain an n(1.5-o(1)) lower bound for MCSP against comparator circuits.

关键词： Comparator circuits Average-case complexity satisfiability algorithms Pseudorandom generators

来源：评论

学校读者我要写书评

暂无评论

ON OBDD-BASED algorithms AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES

引用

JOURNAL OF SYMBOLIC LOGIC 2020年第2期85卷 632-670页

作者： Itsykson, Dmitry Knop, Alexander Romashchenko, Andrei Sokolov, Dmitry Russian Acad Sci VA Steklov Math Inst St Petersburg Dept St Petersburg Russia Univ Montpellier CNRS LIRMM Montpellier France

In 2004 Atserias, Kolaitis, and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of an identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based proof systems that additionally contain a rule that allows changing the order in OBDDs. At first we consider a proof system OBDD(boolean AND, reordering) that uses the conjunction (join) rule and the rule that allows changing the order. We exponentially separate this proof system from OBDD(boolean AND) proof system that uses only the conjunction rule. We prove exponential lower bounds on the size of OBDD (boolean AND, reordering) refutations of Tseitin formulas and the pigeonhole principle. The first lower bound was previously unknown even for OBDD(boolean AND) proofs and the second one extends the result of Tveretina et al. from OBDD(boolean AND) to OBDD(boolean AND, reordering). In 2001 Aguirre and Vardi proposed an approach to the propositional satisfiability problem based on OBDDs and symbolic quantifier elimination (we denote algorithms based on this approach as OBDD(boolean AND, 3) algorithms). We augment these algorithms with the operation of reordering of variables and call the new scheme OBDD(boolean AND, 3, reordering) algorithms. We notice that there exists an OBDD(boolean AND, there exists) algorithm that solves satisfiable and unsatisfiable Tseitin formulas in polynomial time (a standard example of a hard system of linear equations over F-2), but we show that there are formulas representing systems of linear equations over F-2 that are hard for OBDD(boolean AND, there exists, reordering) algorithms. Our hard instances are satisfiable formulas representing systems of linear equations over F-2 that correspond to checksum matrices of error correcting codes.

关键词： communication complexity error correcting codes OBDD proof complexity satisfiability algorithms

来源：评论

学校读者我要写书评

暂无评论

New algorithms and Lower Bounds for Circuits With Linear Threshold Gates

引用

THEORY OF COMPUTING 2018年 14卷

作者： Williams, R. Ryan MIT Elect Engn & Comp Sci 77 Massachusetts Ave Cambridge MA 02139 USA

Let ACC circle THR be the class of constant-depth circuits comprised of AND, OR, and MODm gates (for some constant m > 1), with a bottom layer of gates computing arbitrary linear threshold functions. This class of circuits can be seen as a "midpoint" between ACC (where we know nontrivial lower bounds) and depth- two linear threshold circuits (where nontrivial lower bounds remain open). We give an algorithm for evaluating an arbitrary symmetric function of 2(no(1)) ACC circle THR circuits of size 2(no(1)), on all possible inputs, in 2(n) . poly (n) time. Several consequences are derived: The number of satisfying assignments to an ACC circle THR circuit of 2(no(1)) size is computable in 2(n-n epsilon) time (where e epsilon > 0 depends on the depth and modulus of the circuit). NEXP does not have quasi- polynomial size ACC circle THR circuits, and NEXP does not have quasi-polynomial size ACC circle SYM circuits. Nontrivial size lower bounds were not known even for AND circle OR circle THR circuits. Every 0-1 integer linear program with n Boolean variables and s linear constraints is solvable in 2(n-Omega n(n/log4(sM(logn)))) . poly (s, n, M) time with high probability, where M <= 2(no(1)) is an upper bound on the bit-length of the coefficients. (For example, 0-1 integer programs with weights in [-2(no(1)), 2(no(1))] and poly (n) constraints can be solved in 2(n-Omega n(n/log4n)) time.) We also present an algorithm for evaluating depth-two linear threshold circuits ( also known as THR circle THR) with exponential weights and 2(n/24) size on all 2(n) input assignments, running in 2n . poly (n) time. This is evidence that non-uniform lower bounds for THR circle THR are within reach.

关键词： circuit complexity satisfiability algorithms linear threshold functions

来源：评论

学校读者我要写书评

暂无评论

The Discrete Minimum Constraint Removal Motion Planning Problem

The Discrete Minimum Constraint Removal Motion Planning Prob...

引用

International Conference on Numerical Analysis and Applied Mathematics (ICNAAM)

作者： Gorbenko, Anna Popov, Vladimir Ural Fed Univ Dept Intelligent Syst & Robot Math & Comp Sci Inst Ekaterinburg 620083 Russia

ISBN: (纸本)9780735412873

Many planning problems for robots are of considerable interest. In this paper, we consider the discrete minimum constraint removal motion planning problem that can be used for a motion planning formulation with explanations for failure. We consider an efficient approach to solve the problem. In particular, we consider an explicit reduction from the decision version of the problem to the satisfiability problem. We present the results of computational experiments for different satisfiability algorithms.

关键词： motion planning NP-complete satisfiability problem satisfiability algorithms

来源：评论

学校读者我要写书评

暂无评论

The Problem of Robot Swarms Control with only Global Signals

The Problem of Robot Swarms Control with only Global Signals

引用

International Conference on Numerical Analysis and Applied Mathematics (ICNAAM)

作者： Gorbenko, Anna Popov, Vladimir Ural Fed Univ Dept Intelligent Syst & Robot Math & Comp Sci Inst Ekaterinburg 620083 Russia

ISBN: (纸本)9780735412873

Problems of swarm robotics are extensively studied in contemporary robotics. In this paper, we consider the problem of robot swarms control with only global signals. We propose an efficient approach to solve the problem. In particular, we consider an explicit reduction from the decision version of the problem to the satisfiability problem. For different satisfiability algorithms, we present the results of computational experiments.

关键词： robot swarm autonomous mobile robot PSPACE-complete satisfiability problem satisfiability algorithms

来源：评论

学校读者我要写书评

暂无评论

On Uniformity and Circuit Lower Bounds

引用

COMPUTATIONAL COMPLEXITY 2014年第2期23卷 177-205页

作者： Santhanam, Rahul Williams, Ryan Univ Edinburgh Sch Informat Edinburgh Midlothian Scotland Stanford Univ Dept Comp Sci Stanford CA 94305 USA

We explore relationships between circuit complexity, the complexity of generating circuits, and algorithms for analyzing circuits. Our results can be divided into two parts: 1. Lower bounds against medium-uniform circuits. Informally, a circuit class is "medium uniform" if it can be generated by an algorithmic process that is somewhat complex (stronger than LOGTIME) but not infeasible. Using a new kind of indirect diagonalization argument, we prove several new unconditional lower bounds against medium-uniform circuit classes, including: For all k, P is not contained in P-uniform SIZE(n (k) ). That is, for all k, there is a language that does not have O(n (k) )-size circuits constructible in polynomial time. This improves Kannan's lower bound from 1982 that NP is not in P-uniform SIZE(n (k) ) for any fixed k. For all k, NP is not in .This also improves Kannan's theorem, but in a different way: the uniformity condition on the circuits is stronger than that on the language itself. For all k, LOGSPACE does not have LOGSPACE-uniform branching programs of size n (k) . Eliminating non-uniformity and (non-uniform) circuit lower bounds. We complement these results by showing how to convert any potential simulation of LOGTIME-uniform NC (1) in ACC (0)/poly or TC (0)/poly into a medium-uniform simulation using small advice. This lemma can be used to simplify the proof that faster SAT algorithms imply NEXP circuit lower bounds and leads to the following new connection: Consider the following task: given a TC (0) circuit C of n (O(1)) size, output yes when C is unsatisfiable, and output no when C has at least 2 (n-2) satisfying assignments. (Behavior on other inputs can be arbitrary.) Clearly, this problem can be solved efficiently using randomness. If this problem can be solved deterministically in 2 (n-omega(log) n) time, then NEXP not subset of TC degrees/poly. Another application is to derandomize randomized TC degrees simulations of NC1 on almost all inputs: Suppose . Then,

关键词： Circuit complexity uniformity lower bounds satisfiability algorithms

来源：评论

学校读者我要写书评

暂无评论

A satisfiability Algorithm for Sparse Depth Two Threshold Circuits

A Satisfiability Algorithm for Sparse Depth Two Threshold Ci...

引用

IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS)

作者： Impagliazzo, Russell Paturi, Ramamohan Schneider, Stefan Univ Calif San Diego La Jolla CA 92093 USA

ISBN: (纸本)9780769551357

We give a nontrivial algorithm for the satisfiability problem for threshold circuits of depth two with a linear number of wires which improves over exhaustive search by an exponential factor. The independently interesting problem of the feasibility of sparse 0-1 integer linear programs is a special case. To our knowledge, our algorithm is the first to achieve constant savings even for the special case of Integer Linear Programming. The key idea is to reduce the satisfiability problem to the Vector Domination problem, the problem of checking whether there are two vectors in a given collection of vectors such that one dominates the other component-wise. Our result generalizes to formulas of arbitrary constant depth. We also provide a satisfiability algorithm with constant savings for depth two circuits with symmetric gates where the total weighted fan-in is at most linear in the number of variables. One of our motivations is proving strong lower bounds for TC0 circuits, exploiting the connection (established by Williams) between satisfiability algorithms and lower bounds. Our second motivation is to explore the connection between the expressive power of the circuits and the complexity of the corresponding circuit satisfiability problem.

关键词： Threshold Circuits satisfiability algorithms

来源：评论

学校读者我要写书评

暂无评论

Fighting Perebor: New and Improved algorithms for Formula and QBF satisfiability

Fighting Perebor: New and Improved Algorithms for Formula an...

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Santhanam, Rahul Univ Edinburgh Sch Informat Edinburgh Midlothian Scotland

ISBN: (纸本)9780769542447

We investigate the possibility of finding satisfying assignments to Boolean formulae and testing validity of quantified Boolean formulae (QBF) asymptotically faster than a brute force search. Our first main result is a simple deterministic algorithm running in time 2(n-Omega(n)) for satisfiability of formulae of linear size in n, where n is the number of variables in the formula. This algorithm extends to exactly counting the number of satisfying assignments, within the same time bound. Our second main result is a deterministic algorithm running in time 2(n-Omega(n/log(n))) for solving QBFs in which the number of occurrences of any variable is bounded by a constant. For instances which are "structured", in a certain precise sense, the algorithm can be modified to run in time 2(n-Omega(n)). To the best of our knowledge, no non-trivial algorithms were known for these problems before. As a byproduct of the technique used to establish our first main result, we show that every function computable by linear-size formulae can be represented by decision trees of size 2(n-Omega(n)). As a consequence, we get strong superlinear average-case formula size lower bounds for the Parity function.

关键词： satisfiability algorithms random restrictions average case lower bounds quantified Boolean formulae

来源：评论

学校读者我要写书评

暂无评论

Partial instantiation methods for inference in first-order logic

引用

JOURNAL OF AUTOMATED REASONING 2002年第4期28卷 371-396页

作者： Hooker, JN Rago, G Chandru, V Shrivastava, A Carnegie Mellon Univ Grad Sch Ind Adm Pittsburgh PA 15213 USA Univ Pisa Dept Comp Sci I-56125 Pisa Italy Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Sanchez Comp Associates Bangalore 560003 Karnataka India

satisfiability algorithms for propositional logic have improved enormously in recently years. This improvement increases the attractiveness of satisfiability methods for first-order logic that reduce the problem to a series of ground-level satisfiability problems. R. Jeroslow introduced a partial instantiation method of this kind that differs radically from the standard resolution-based methods. This paper lays the theoretical groundwork for an extension of his method that is general enough and efficient enough for general logic programming with indefinite clauses. In particular we improve Jeroslow's approach by (1) extending it to logic with functions, (2) accelerating it through the use of satisfiers, as introduced by Gallo and Rago, and (3) simplifying it to obtain further speedup. We provide a similar development for a "dual" partial instantiation approach defined by Hooker and suggest a primal-dual strategy. We prove correctness of the primal and dual algorithms for full first-order logic with functions, as well as termination on unsatisfiable formulas. We also report some preliminary computational results.

关键词： satisfiability algorithms primal-dual strategy

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：