Majority gates vs. general weighted threshold gates

In this paper we study small depth circuits that contain threshold gates (with or without weights) and parity gates. All circuits we consider are of polynomial size. We prove several results which complete the work on characterizing possible inclusions between many classes defined by small depth circuits. These results are the following:

BPP has subexponential time simulations unlessEXPTIME has publishable proofs

We show thatBPP can be simulated in subexponential time for infinitely many input lengths unless exponential time

Lifting lower bounds for tree-like proofs

It is known that constant-depth Frege proofs of some tautologies require exponential size. No such lower bound result is known for more general proof systems. We consider tree-like sequent calculus proofs in which formulas can contain modular connectives and only the cut formulas are restricted to be of constant depth. Under a plausible hardness assumption concerning small-depth Boolean circuits, we prove exponential lower bounds for such proofs. We prove these lower bounds directly from the computational hardness assumption. We start with a lower bound for cut-free proofs and “lift” it so it applies to proofs with constant-depth cuts. By using the same approach, we obtain the following additional results. We provide a much simpler proof of a known unconditional lower bound in the case where modular connectives are not used. We establish a conditional exponential separation between the power of constant-depth proofs that use different modular connectives. We show that these tree-like proofs with constant-depth cuts cannot polynomially simulate similar dag-like proofs, even when the dag-like proofs are cut-free. We present a new proof of the non-finite axiomatizability of the theory of bounded arithmetic I Δ₀(R). Finally, under a plausible hardness assumption concerning the polynomial-time hierarchy, we show that the hierarchy \({G_i^*}\) of quantified propositional proof systems does not collapse.     

SZK Proofs for Black-Box Group Problems

In this paper we classify several algorithmic problems in group theory in the complexity classes PZK and SZK (problems with perfect/statistical zero-knowledge proofs respectively). Prior to this, these problems were known to be in . As , we have a tighter upper bound for these problems. Specifically:

Logic-based processing of semantically complex natural language discourse

A logic-based system of knowledge representation for natural language discourse has three primary advantages:

Hardness Hypotheses, Derandomization, and Circuit Complexity

We consider hypotheses about nondeterministic computation that have been studied in different contexts and shown to have interesting consequences:

Modulare hierarchische Modellierung als Grundlage der Software- und Systementwicklung

Zusammenfassung  Die Entwicklung komplexer eingebetteter Softwaresysteme, wie sie heute beispielsweise in Telekommunikationssystemen, Fahr- oder Flugzeugen oder mit der Steuersoftware von Automatisierungssystemen im Einsatz sind, erfordert ein strukturiertes, modulares Vorgehen und angemessene Techniken zur pr?zisen Beschreibung von Anforderungen, der Architektur des Systems mit ihren Komponenten, der Schnittstellen zur Systemumgebung und zwischen den internen Komponenten, der Wechselwirkung zwischen gesteuertem und steuerndem Teilsystem und schlie?lich der Implementierung. Mit dem frühzeitigen und durchg?ngigen Einsatz geeigneter Modelle (Stichwort UML (,,Unified Modeling Language“) und MDA (,,Model Driven Architecture“)) werden gro?e Hoffnungen verbunden, die Entwicklungsaufgaben beherrschbarer zu gestalten. Dieser Artikel beschreibt die theoretischen Grundlagen für ein konsequent modellbasiertes Vorgehen in Form eines zusammengeh?rigen, homogenen und dennoch modularen Baukastens von Modellen, der hierfür zwingend erforderlich ist. Besondere Schwerpunkte liegen hierbei auf den Themen

Reverse procurement and auctions for consumers

Web-based bid invitation platforms and reverse auctions are increasingly used by consumers for the procurement of goods and services. An empirical examination shows that with B-2-C these procurement methods generate considerable benefits for the consumer:

Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution

We work with an extension of Resolution, called Res(2), that allows clauses with conjunctions of two literals. In this system there are rules to introduce and eliminate such conjunctions. We prove that the weak pigeonhole principle PHP^cn_n and random unsatisfiable CNF formulas require exponential-size proofs in this system. This is the strongest system beyond Resolution for which such lower bounds are known. As a consequence to the result about the weak pigeonhole principle, Res(log) is exponentially more powerful than Res(2). Also we prove that Resolution cannot polynomially simulate Res(2) and that Res(2) does not have feasible monotone interpolation solving an open problem posed by Krají ek.     

Extensions of structural optimization software to enable multidisciplinary applications

Applications of structural optimization are often multidisciplinary in nature and require nontraditional problem formulations.In the optimization system that has been developed, flexibility in terms of system design and problem formulation have been important aspects. A mathematical programming approach has been adopted where function values and sensitivity information is required from each discipline involved. To be able to deal with the demands of ongoing projects, a number of extensions have been implemented in recent years.The system is today used within the Saab and ABB companies. Four recent applications are presented to illustrate how the extended capabilities have been used.

Information theory and the complexity of boolean functions

This paper explores the connections between two areas pioneered by Shannon: the transmission of information with a fidelity criterion, and the realization of Boolean functions by networks and formulae. We study three phenomena:

AI Bridges and Dreams

This paper is a modified version of my acceptance lecture for the 1986 SPL-Insight Award. It turned into something of a personal credo -describing my view of

Exponential lower bounds for the pigeonhole principle

In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP). We also obtain an (loglogn)-depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle. Our theorem nearly completes the search for the exact complexity of the PHP, as S. Buss has constructed polynomial-size, logn-depth Frege proofs for the PHP. The main lemma in our proof can be viewed as a general Håstad-style Switching Lemma for restrictions that are partial matchings. Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.     

On Approximate Majority and Probabilistic Time

We prove new results on the circuit complexity of approximate majority, which is the problem of computing the majority of a given bit string whose fraction of 1’s is bounded away from 1/2 (by a constant). We then apply these results to obtain new relationships between probabilistic time, BPTime (t), and alternating time, ∑_O(1)Time (t). Our main results are the following:

Optoelectronic device for reading of hidden magnetic information from the holograms

The model of the device of reading (visualization) of the hidden magnetic information from the holograms combined with magneto-optical layer is presented in the article. Ways of magnetic images formation on the protected documentation and their reading by magneto-optical methods are proposed. The reading head with the help of magneto-optical meridional Kerr effect allows to observe visually of “effect of blinking” from the hologram with the hidden magnetic layer. During the work the mathematical analysis magneto-optical Kerr or Faraday effects was carried out. The hidden magnetic image based on:

Conjunction-type standard ML polymorphism

It has been long argued that the well known Milner type inference system implemented in the programming language Standard ML is inadequate [4]. The arguments were presented on the basis of intersection-type inference systems [3]. However no algorithm has been developed. The intersection-type inference systems are closed under-equality [1] and has been proved undecidable [7]. The paper presents a new type inference system using conjunction-types which extends the notion of intersection-types. The algorithm presented in the author's previous paper [9] is easily adoptable into the Standard ML. In this paper we shall discuss the features of the system and its semantic soundness. Unlike the intersection-type inference systems, the conjunction-type inference system is:

Spectrum of multiyear Wolf number rhythms since 1749: A forecast of solar activity dynamics for the 21st century

Conclusions