On the Construction of Small Fully Testable Circuits with Low Depth (2008)
Görschwin Fey, Anna Bernasconi, Valentina Ciriani, Rolf Drechsler
During synthesis of circuits for Boolean functions area, delay and testability are optimization goals that often contradict each other. Multi-level circuits are often quite small while circuits with...
Quantum Networks on Cubelike Graphs (2008)
Bernasconi, Anna, Godsil, Chris, Severini, Simone
Cubelike graphs are the Cayley graphs of the elementary abelian group (Z_2)^n (e.g., the hypercube is a cubelike graph). We give conditions for perfect state transfer between two particles in quantum...
Testability of SPP three-level logic networks in static fault models (2008)
Valentina Ciriani, Anna Bernasconi
Sum of Pseudoproducts (SPPs) are three-level network structures that give a good compromise between compact representation and small depth of the resulting circuit. In this paper the testability of...
Knitting for fun: a recursive sweater (2008)
Anna Bernasconi, Chiara Bodei, Linda Pagli
Abstract. In this paper we investigate the relations between knitting and computer science. We show that the two disciplines share many concepts. Computer science, in particular algorithm theory, can...
Computing Gröbner Bases in the Boolean Setting with Applications to Counting (2007)
Anna Bernasconi, Bruno Codenotti, Valentino Crespi, Giovanni Resta
We take advantage of the special structure of computations in Z2 to develop algorithms for the computation of Groebner bases and of the Hilbert function in the Boolean setting. Natural sources of...
Computing Groebner Bases in the Boolean Setting with Applications to Counting (2007)
Anna Bernasconi, Bruno Codenotti, Valentino Crespi, Giovanni Resta
We take advantage of the special structure of computations in Z2 to develop algorithms for the computation of Groebner bases and of the Hilbert function in the Boolean setting. Natural sources of...
Computing the Dimension of a Polynomial Ideal (2007)
Anna Bernasconi, Ernst W. Mayr, Michal Mnuk, Martin Raab
Following ideas from [Hei83, DFGS91, MT97] and applying the techniques proposed in [May89, KM96, Kuh98], we present a deterministic algorithm for computing the dimension of a polynomial ideal...
On the Complexity of Some Arithmetic Problems over IF2[T] (2007)
Eric Allender, Anna Bernasconi, Carsten Damm, Michael Saks, Igor Shparlinski
In this paper, we study various combinatorial complexity characteristics of Boolean functions related to some natural arithmetic problems about polynomials over IF2. In particular, we consider the...
Efficient minimization of fully testable 2-SPP networks (2006)
Anna Bernasconi, Valentina Ciriani, Rolf Drechsler, Tiziano Villa
The paper presents a heuristic algorithm for the minimization of 2-SPP networks, i.e., three-level EXOR-AND-OR forms with EXOR gates restricted to fan-in 2. Previous works had presented exact...
DRedSOP: Synthesis of a new class of regular functions (2006)
Anna Bernasconi, Valentina Ciriani, Anna Bernasconi, Valentina Ciriani
In this paper we characterize and study a new class of regular Boolean functions called D-reducible. A D-reducible function, depending on all its n input variables, can be studied and synthesized in...
EXOR Projected Sum of Products (2006)
Anna Bernasconi, Valentina Ciriani, Roberto Cordone, Anna Bernasconi, Valentina Ciriani, Roberto Cordone
In this paper we introduce a new algebraic form for Boolean function representation, called EXOR-Projected Sum of Products (EP-SOP), resulting in a four level network that can be easily implemented...
Fast three-level logic minimization based on autosymmetry (2002)
Anna Bernasconi, Anna Bernasconi, Valentina Ciriani, Valentina Ciriani, Fabrizio Luccio, Fabrizio Luccio, ...
In the framework of SPP minimization, a three level logic synthesis technique developed in recent years, we exploit the \regularity " of Boolean functions to decrease minimization time. Our...
Computing the Dimension of a Polynomial Ideal (2002)
Anna Bernasconi, Ernst W. Mayr, Michal Mnuk, Martin Raab
Following ideas from [Hei83, DFGS91, MT97] and applying the techniques proposed in [May89, KM96, Küh98], we present a deterministic algorithm for computing the dimension of a polynomial ideal...
On a hierarchy of Booleanfunctions hard to compute in constant depth (2001)
Any attempt to find connections between mathematical properties and complexity has a strong relevance to the field of Complexity Theory. This is due to the lack of mathematical techniques to prove...
On Boolean Functions Associated to Bipartite Cayley (2000)
Anna Bernasconi, Bruno Codenotti
In [1] we showed that any Boolean function can be associated to a Cayley graph whose spectrum coincides with the Walsh spectrum of the function, and used this idea to investigate the spectrum of...
A Characterization of Bent Functions in terms of Strongly Regular Graphs (1999)
Anna Bernasconi, Bruno Codenotti, Jeffrey M. VanderKam
In this note we prove that bent functions can be precisely characterized in terms of a special class of strongly regular graphs, thus providing a positive answer to a question raised in the paper...
A Note On The Polynomial Representation Of Boolean Functions Over GF(2) (1998)
Richard Beigel, Anna Bernasconi, Lehrstuhl Eziente Algorithmen
We investigate the representation of Boolean functions as polynomials over the eld GF (2), and prove an interesting characterization theorem: the degree of a Boolean function over GF (2) is equal to...
Circuit and Decision Tree Complexity of Some Number Theoretic Problems (1998)
Anna Bernasconi, Mathematik Informatik, Trierer Forschungsberichte, Trierer Forschungsberichte, Fachbereich Iv, Fachbereich Iv, ...
We extend the area of applications of the Abstract Harmonic Analysis to lower bounds on the circuit and decision tree complexity of Boolean functions related to some number theoretic problems. In...
Stuck-At-Fault Testability of SPP Three-Level Logic Forms (1970)
Valentina Ciriani, Anna Bernasconi, Rolf Drechsler
Recently introduced, three-level logic Sum of Pseudoproducts (SPP) forms allow the representation of Boolean functions with much shorter expressions than standard two-level Sum of Products (SOP)...
On the average sensitivity of testing square-free numbers (1627)
A. Bernasconi, C. Damm, I. Shparlinsky, Anna Bernasconi
Abstract We study combinatorial complexity characteristics of a Boolean function related to a natural number theoretic problem. In particular we obtain a linear lower bound on the average sensitivity...