The minimal complementation property above 0′

Let us say that any (Turing) degree d > 0 satisfies the minimal complementation property (MCP) if for every degree 0 < a < d there exists a minimal degree b < d such that a ∨ b = d (and therefore a ∧ b = 0 ). We show that every degree d ≥ 0 ′ satisfies MCP. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Π11‐Martin‐Löf randomness and Π11‐Solovay completeness

Developing an analogue of Solovay reducibility in the higher recursion setting, we show that results from the classical computably enumerable case can be extended to the new context.     

The 0–1 inverse maximum stable set problem

In this paper we study the 0–1 inverse maximum stable set problem, denoted by IS_{0,1}. Given a graph and a fixed stable set, it is to delete the minimum number of vertices to make this stable set maximum in the new graph. We also consider IS_{0,1} against a specific algorithm such as Greedy and 2opt, aiming to delete the minimum number of vertices so that the algorithm selects the given stable set in the new graph; we denote them by IS_{0,1},greedy and IS_{0,1},2opt, respectively. Firstly, we show that they are NP-hard, even if the fixed stable set contains only one vertex. Secondly, we achieve an approximation ratio of for IS_{0,1},2opt. Thirdly, we study the tractability of IS_{0,1} for some classes of perfect graphs such as comparability, co-comparability and chordal graphs. Finally, we compare the hardness of IS_{0,1} and IS_{0,1},2opt for some other classes of graphs.     

On the Π11‐separation principle

We study the proof‐theoretic strength of the Π₁¹‐separation axiom scheme, and we show that Π₁¹‐separation lies strictly in between the Δ₁¹‐comprehension and Σ₁¹‐choice axiom schemes over RCA₀. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

0–1 laws for maps

A class of finite structures has a 0–1 law with respect to a logic if every property expressible in the logic has a probability approaching a limit of 0 or 1 as the structure size grows. To formulate 0–1 laws for maps (i.e., embeddings of graphs in a surface), it is necessary to represent maps as logical structures. Three such representations are given, the most general being the full cross representation based on Tutte's theory of combinatorial maps. The main result says that if a class of maps has two properties, richness and large representativity, then the corresponding class of full cross representations has a 0–1 law with respect to first‐order logic. As a corollary the following classes of maps on a surface of fixed type have a first‐order 0–1 law: all maps, smooth maps, 2‐connected maps, 3‐connected maps, triangular maps, 2‐connected triangular maps, and 3‐connected triangular maps. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 215–237, 1999     

On (∈, ∈ ∨ q)‐fuzzy filters of R0‐algebras

In this paper, we introduce the notions of (∈, ∈ ∨ q)‐fuzzy filters and (∈, ∈ ∨ q)‐fuzzy Boolean (implicative) filters in R₀‐algebras and investigate some of their related properties. Some characterization theorems of these generalized fuzzy filters are derived. In particular, we prove that a fuzzy set in R₀‐algebras is an (∈, ∈ ∨ q)‐fuzzy Boolean filter if and only if it is an (∈, ∈ ∨ q)‐fuzzy implicative filter. Finally, we consider the concepts of implication‐based fuzzy Boolean (implicative) filters of R₀‐algebras (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On ε‐biased generators in NC0

Cryan and Miltersen (Proceedings of the 26th Mathematical Foundations of Computer Science, 2001, pp. 272–284) recently considered the question of whether there can be a pseudorandom generator in NC⁰, that is, a pseudorandom generator that maps n‐bit strings to m‐bit strings such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m ≥ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k ≥ 4. In fact, they ask whether every NC⁰ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC⁰ generator can sample an ε‐biased space with negligible ε? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2. For large values of k, we construct generators that map n bits to bits such that every XOR of outputs has bias . We also present a polynomial‐time distinguisher for k = 4,m ≥ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m ≥ Ω(2^kn^?k/2?). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2^?Ω(n) and which maps n bits to Ω(n²) bits. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Multi‐term π‐institutions and their equivalence

The notion of a multi‐term π‐institution is introduced and a criterion for the equivalence of two multi‐term π‐institutions in terms of their categories of theories is proved. Moreover, a counterexample that shows that this criterion is false for arbitrary π‐institutions is given. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Properly Σ2 minimal degrees and 0″ complementation

We show that there exists a properly Σ₂ minimal (Turing) degree b , and moreover that b can be chosen to join with 0 ′ to 0 ″ – so that b is a 0 ″ complement for every degree a such that 0 ′ ≤ a < 0 ″. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Characterization of ‐like and c0‐like equivalence relations

In this paper, notions of ‐like and c₀‐like equivalence relations are introduced. We characterize the positions of ‐like and c₀‐like equivalence relations in the Borel reducibility hierarchy by comparing them with equivalence relations and .     

Binary types in ℵ0‐categorical weakly o‐minimal theories

Orthogonality of all families of pairwise weakly orthogonal 1‐types for ?₀‐categorical weakly o‐minimal theories of finite convexity rank has been proved in 6 . Here we prove orthogonality of all such families for binary 1‐types in an arbitrary ?₀‐categorical weakly o‐minimal theory and give an extended criterion for binarity of ?₀‐categorical weakly o‐minimal theories (additionally in terms of binarity of 1‐types). © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Boolean products of R0‐algebras

In this paper, the (weak) Boolean representation of R₀‐algebras are investigated. In particular, we show that directly indecomposable R₀‐algebras are equivalent to local R₀‐algebras and any nontrivial R₀‐algebra is representable as a weak Boolean product of local R₀‐algebras (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Bayesian l0‐regularized least squares

Bayesian l₀‐regularized least squares is a variable selection technique for high‐dimensional predictors. The challenge is optimizing a nonconvex objective function via search over model space consisting of all possible predictor combinations. Spike‐and‐slab (aka Bernoulli‐Gaussian) priors are the gold standard for Bayesian variable selection, with a caveat of computational speed and scalability. Single best replacement (SBR) provides a fast scalable alternative. We provide a link between Bayesian regularization and proximal updating, which provides an equivalence between finding a posterior mode and a posterior mean with a different regularization prior. This allows us to use SBR to find the spike‐and‐slab estimator. To illustrate our methodology, we provide simulation evidence and a real data example on the statistical properties and computational efficiency of SBR versus direct posterior sampling using spike‐and‐slab priors. Finally, we conclude with directions for future research.