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

Randomized graph products, chromatic numbers, and the Lovasz theta-function

COMBINATORICA 1997年第1期17卷 79-90页

作者： Feige, U Department of Applied Math. and Computer Science The Weizmann Institute Rehovot Israel

For a graph G, let alpha(G) denote the size of the largest independent set in G, and let theta(G) denote the Lovasz theta-function on G. We prove that for some c > 0, there exists an infinite family of graphs such that theta(G) > alpha(G)n/2(c root log n), where n denotes the number of vertices in a graph. This disproves a known conjecture regarding the theta function. As part of our proof, we analyse the behavior of the chromatic number in graphs under a randomized version of graph products. This analysis extends earlier work of Linial and Vazirani, and of Berman and Schnitger, and may be of independent interest.

关键词： mathematics Subject Classification (1991) 05 C 15 90 C 35

来源：评论

学校读者我要写书评

暂无评论

Visual cryptography II: Improving the contrast via the cover base

引用

International Workshop on Security Protocols, 1996

作者： Naor, Moni Shamir, Adi Department of Applied Math and Computer Science Weizmann Institute Rehovot76100 Israel

ISBN: (纸本)3540624945

In Eurocrypt 1994 we proposed a a new type of cryptographic scheme, which can decode concealed images without any cryptographic computations, by placing two transparencies on top of each other and using the decoder's (human) visual systems. One of the drawback of that proposal was a toss in contrast: a black pixel is translated in the reconstruction into a black region, but a white pixel is translated into a grey region (half black and half white). In this paper we propose am alternative model for reconstruction with a different set of operation (which we call the "Cover" semi-group) is proposed. In this model we are able to obtain a better contrast than is possible in the previous one. © Springer-Verlag Berlin Heidelberg 1997.

关键词： Pixels

来源：评论

学校读者我要写书评

暂无评论

On the complexity of verifying concurrent transition systems 8th

On the complexity of verifying concurrent transition systems

引用

Proceedings of the 1997 8th International Conference on Concurrency Theory, CONCUR

作者： Harel, David Kupferman, Orna Vardi, Moshe Y. Department of Applied Math. and Computer Science The Weizmann Institute Rehovot 76100 Israel EECS Department UC Berkeley Berkeley 94720-1770 CA United States Rice University Department of Computer Science Houston 77251-1892 TX United States

ISBN: (纸本)3540631410

In implementation verification, we check that an implementation is correct with respect to a specification by checking whether the behaviors of a transition system that models the program's implementation correlate with the behaviors of a transition system that models its specification. In this paper, we investigate the effect of concurrency on the complexity of implementation verification. We consider trace-based and tree-based approaches to the verification of concurrent transition systems, with and without fairness. Our results show that in almost all cases the complexity of the problem is exponentially harder than that of the sequential case. Thus, as in the model-checking verification methodology, the state-explosion problem cannot be avoided.

关键词： Specifications

来源：评论

学校读者我要写书评

暂无评论

Stereoscopic families of permutations, and their applications

Stereoscopic families of permutations, and their application...

引用

Israel Symposium on the Theory of Computing and Systems

作者： U. Feige R. Krauthgamer Department of Applied Math and Computer Science Weizmann Institute of Science Rehovot Israel

A stereoscopic family of permutations maps an m-dimensional mesh into several 1-dimensional lines, in a way that jointly preserves distance information. Specifically, consider any two points and denote their distance on the m-dimensional mesh by d. Then the distance between their images, on the line on which these images are closest together is O(d/sup m/). We initiate a systematic study of stereoscopic families of permutations. We show a construction of these families that involves the use of m+1 images. We also show that under some additional restrictions (namely adjacent points on the image lines originate at points which are not too far away on the mesh), three images are necessary in order to construct such a family for the 2-dimensional mesh. We present two applications for stereoscopic families of permutations. One application is an algorithm for routing on the mesh that guarantees delivery of each packet within a number of steps that depends upon the distance between this packet's source and destination, but is independent of the size of the mesh. Our algorithm is exceptionally simple, involves no queues, and can be used in dynamic settings in which packets are continuously generated. Another application is an extension of the construction of nonexpansive hash functions of Linial and Sasson (STOC 96) from the case of one dimensional metrics to arbitrary dimensions.

关键词： computer science Career development Upper bound Optical network units Wavelength routing

来源：评论

学校读者我要写书评

暂无评论

No feasible interpolation for TC/sup 0/-Frege proofs

No feasible interpolation for TC/sup 0/-Frege proofs

引用

Annual IEEE Symposium on Foundations of computer science

作者： M.L. Bonet T. Pitassi R. Raz Department of LSI Universidad Politécnica de Cataluña Barcelona Spain Department of Computer Science University of Arizona Tucson USA Department of Applied Math Weizmann Institute of Science USA

The interpolation method has been one of the main tools for proving lower bounds for propositional proof systems. Loosely speaking, if one can prove that a particular proof system has the feasible interpolation property, then a generic reduction can (usually) be applied to prove lower bounds for the proof system, sometimes assuming a (usually modest) complexity-theoretic assumption. In this paper, we show that this method cannot be used to obtain lower bounds for Frege systems, or even for TC/sup 0/-Frege systems. More specifically, we show that unless factoring is feasible, neither Frege nor TC/sup 0/-Frege has the feasible interpolation property. In order to carry out our argument, we show how to carry out proofs of many elementary axioms/theorems of arithmetic in polynomial-size TC/sup 0/-Frege. In particular, we show how to carry out the proof for the Chinese Remainder Theorem, which may be of independent interest. As a corollary, we obtain that TC/sup 0/-Frege as well as any proof system that polynomially simulates it, is not automatizable (under a hardness assumption).

关键词： Interpolation Polynomials Circuits Arithmetic Artificial intelligence Business process re-engineering Radio access networks Large scale integration computer science Boolean functions

来源：评论

学校读者我要写书评

暂无评论

Generalized output regulation for linear systems

Generalized output regulation for linear systems

引用

American Control Conference (ACC)

作者： A. Saberi A.A. Stoorvogel Zongli Lin School of Electrical Engineering and Computer Science Washington State University Pullman WA USA Department of Mathematics and Computing Science Eindhovan University of Technology Eindhoven Netherlands Department of Applied Math and Statistics State University of New York Stony Brook Stony Brook NY USA

One of the most important problems in linear multivariable control theory is that of controlling a given plant in order to have its output track (or reject) a reference (or disturbance) signal produced by some external generator, called the exosystem. The disturbance or reference contains only the frequency components of the exosystem. This is called the output regulation problem. We generalize the problem framework in several directions. One is to model disturbances and references by an exosystem that is not, unlike the traditional approach, autonomous but is driven. Another direction is to incorporate the derivative information in the problem formulation. Consequently, we formulate two classes of generalized exact and almost output regulation problems. We provide solvability conditions and the solutions to these problems. Finally, and most importantly, we show that if solvability conditions for regulation are not satisfied, one can design a regulator to achieve "best" tracking (or rejection) of reference (or disturbance) signal is any desired induced norm sense.

关键词： Linear systems Differential equations State feedback Output feedback Regulators Stability Closed loop systems mathematics computer science Statistics

来源：评论

学校读者我要写书评

暂无评论

Design and modeling of a piezo-actuated positioning mechanism

Design and modeling of a piezo-actuated positioning mechanis...

引用

IEEE Conference on Decision and Control

作者： J.M.T.A. Adriaens W.L. de Koning R. Banning Dept. of Appl Math. & Comput. Sci. Delft Univ. of Technol. Netherlands Department of Applied Mathematics and Computer Science Delft University of Technnology Delft Netherlands Delft Institute of Microelectronics and SubmicrontechnologyDepartment of Applied Physics Delft University of Technnology Delft Netherlands

ISBN: (纸本)0780341872

We are involved in the design and control of a 1-dimensional positioning mechanism for a range of 50 /spl mu/m and an accuracy of 30 pm. Only piezoelectric actuators can be used to manage such small displacements. However, these actuators show hysteretic behavior and lengthening saturation. The extremely small displacements are measured by means of capacitive sensors. In order to design a controller a model of the positioning mechanism and the actuators is developed. Contrary to the existing literature, in our model the hysteresis is described by a differential equation. The mechanical characteristics of the design, and therefore also of the model, are chosen such that they are practically realizable and advantageous for controller design. The final nonlinear fifth order state space model is believed to be suitable for a nonlinear control technique like feedback linearization.

关键词： Magnetic hysteresis Actuators History Differential equations Sensor phenomena and characterization Magnetic materials mathematics computer science Microelectronics Physics

来源：评论

学校读者我要写书评

暂无评论

A fast randomized LOGSPACE algorithm for graph connectivity

引用

THEORETICAL computer science 1996年第2期169卷 147-160页

作者： Feige, U Department of Applied Math and Computer Science The Weizmann Institute Rehovot 76100 Israel

We study the relationship between undirected graph reachability and graph connectivity, in the context of randomized LOGSPACE algorithms. Aleluinas et al. [2] show that graph reachability (checking whether there is a path connecting vertices L and F) can be decided in logarithmic space and polynomial time, by starting a random walk at L, and checking whether F is hit within some time limit. The randomized algorithm has one-sided error (with small probability, it fails to determine that L and F are connected). The reachability algorithm may be used in order to decide (with one-sided error) whether a graph is connected, by running it n - 1 times, each time with a different target vertex F. This increases the running time by a factor of n. In this paper we give an alternative randomized LOGSPACE algorithm for graph connectivity. Its running time varies between O(n(2)) steps and O(n(3)) steps, depending on the structure of the input graph. This matches the fastest known RLOGSPACE algorithm for reachability, up to a constant factor. Our algorithm has two-sided error.

关键词： Computation theory

来源：评论

学校读者我要写书评

暂无评论

A threshold of ln n for approximating set cover 96

A threshold of ln n for approximating set cover

引用

28th Annual ACM Symposium on Theory of Computing, STOC 1996

作者： Feige, Uriel Department of Applied Math and Computer Science Weizmann Institute Rehovot76100 Israel

ISBN: (纸本)0897917855

We prove that (1 - o(l)) ln n is a threshold below which set cover cannot be approximated efficiently, unless NP has slightly superpolynomial time algorithms. This closes the gap (up to low order terms) between the ratio of approximation achievable by the greedy algorithm (which is (1-o(l))ln n), and previous results of Lund and Yannakakis, that showed hardness of approximation within a ratio of (log2 n)/2 0.72 ln n. © 1996 ACM.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Column-based strip packing using ordered and compliant containment 1st

Column-based strip packing using ordered and compliant conta...

引用

1st ACM Workshop on applied Computational Geometry, WACG 1996 held as part of 2nd Federated Computing Research Conference, FCRC 1996

作者： Daniels, Karen Milenkovic, Victor J. Harvard University and University of Miami Division of Applied Sciences United States University of Miami Department of Math and Computer Science United States

ISBN: (纸本)354061785X

The oriented strip packingproblem is very important to manufacturing industries: given a strip of fixed width and a set of many (> 100) nonconvex polygons with 1, 2, 4, or 8 orientations permitted for each polygon, find a set of translations and orientations for the polygons that places them without overlapping into the strip of minimum length. Heuristics are given for two versions of strip packing: 1) translation-only and 2) oriented. The first heuristic uses an algorithm we have previously developed for translational containment: given polygons P1, P2…., Pk and a fixed container C, find translations for the polygons that place them into C without overlapping. The containment algorithm is practica] for k ≤ 10. Two new containment algorithms are presented for use in the second packing heuristic. The first, an ordered containment algorithm, solves containment in time which is only linear in k when the polygons are a) "long" with respect to one dimension of the container and b) ordered with respect to the other dimension. The second algorithm solves compliant containment: given polygons P1, P2,..., Pi+k and a container C such that polygons P1, P2,…, Pi are already placed into C, find translations for Pi+l, Pi+2,…, Pi+k and a nonoverlapping translationa] motion of P1, P2,…, Pi that allows all l + k polygons to fit into the container without overlapping. The performance of the heuristics is compared to the performance of commercial software and/or human experts. The results demonstrate that fast containment algorithms for modest values of k (k ≤ 10) are very useful in the development of heuristics for oriented strip packing of many (k >> 10) polygons. © Springer-Verlag Berlin Heidelberg 1996.

关键词： Containers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：