Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Boolean Function
Communication Complexity
Computational Complexity
Lower Bound
Related Publications
(8)
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
Communication Complexity
A characterization of span program size and improved lower bounds for monotone span programs
Graph Complexity
The Probabilistic Communication Complexity of Set Intersection
Subscribe
Academic
Publications
Applications of matrix methods to the theory of lower bounds in computational complexity
Applications of matrix methods to the theory of lower bounds in computational complexity,10.1007/BF02122698,Combinatorica,Alexander A. Razborov
Edit
Applications of matrix methods to the theory of lower bounds in computational complexity
(
Citations: 48
)
BibTex

RIS

RefWorks
Download
Alexander A. Razborov
We present some criteria for obtaining lower bounds for the formula size of Boolean functions. In the monotone case we get the boundnΩ(logn) for the function “MINIMUM COVER” using methods considerably simpler than all previously known. In the general case we are only able to prove that the criteria yield an exponential
lower bound
when applied to almost all functions. Some connections with graph complexity and
communication complexity
are also given.
Journal:
Combinatorica
, vol. 10, no. 1, pp. 8193, 1990
DOI:
10.1007/BF02122698
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(21)
...Disjointness of bounded size subsets, and in particular of subsets of size log N , was used as an example of a function that exhibits the largest possible (quadratic) gap between deterministic and nondeterministic communication complexity. Razborov [
16
] used this gap...
Eyal Kushilevitz
,
et al.
The Communication Complexity of SetDisjointness with Small Sets and 0...
...Razborov [
Raz90
] uses matrix rank to show superpolynomial lower bounds on monotone formula size, but also shows [Raz92] that his method is limited to O(n) bounds for general formulas...
Troy Lee
.
A New Rank Technique for Formula Size Lower Bounds
...Nowadays we have several powerful techniques to prove lower bounds for monotone circuits: the method of approximations [1]; the method of probabilistic amplifications for estimating the depth of monotone circuits [2]; the rank argument for formulas [
3
] and span programs [4], [5]...
Matthias P. Krieger
.
On the Incompressibility of Monotone DNFs
...{0,1}, DISJn(x,y) = 1 if and only if there exists an integer i, 1 ≤ i ≤ n, so that xi = yi = 1. It is known that R(DISJn) = �(n) [9] [
13
], and Q∗(DISJn) = �( √ n) [14][1]...
Wei Huang
,
et al.
The communication complexity of the Hamming distance problem
...(b) is a result of Razborov [
38
] (see also [26, Example 2.12])...
Martin Grohe
,
et al.
Tight Lower Bounds for Query Processing on Streaming and External Memo...
References
(12)
Relating Monotone Formula Size and Monotone Depth of Boolean Functions
(
Citations: 9
)
Ingo Wegener
Journal:
Information Processing Letters  IPL
, vol. 16, no. 1, pp. 4142, 1983
Fast Parallel Matrix and GCD Computations
(
Citations: 134
)
Allan Borodin
,
Joachim Von Zur Gathen
,
John E. Hopcroft
Journal:
Information and Computation/information and Control  IANDC
, vol. 52, no. 3, pp. 6571, 1982
The gap between monotone and nonmonotone circuit complexity is exponential
(
Citations: 51
)
Éva Tardos
Journal:
Combinatorica
, vol. 8, no. 1, pp. 141142, 1988
A Combinatorial Problem in the kAdic Number System
(
Citations: 6
)
B. Lindstrom
,
H.O. Zetterstrom
Journal:
Proceedings of The American Mathematical Society  PROC AMER MATH SOC
, vol. 18, no. 1, 1967
The monotone circuit complexity of Boolean functions
(
Citations: 128
)
Noga Alon
,
Ravi B. Boppana
Journal:
Combinatorica
, vol. 7, no. 1, pp. 122, 1987
Sort by:
Citations
(48)
On convex complexity measures
(
Citations: 3
)
Pvel Hrubes
,
Stasys Jukna
,
Alexander S. Kulikov
,
Pavel Pudlák
Journal:
Theoretical Computer Science  TCS
, vol. 411, no. 1618, pp. 18421854, 2010
Subspace intersection graphs
Joshua D. Laison
,
Yulan Qing
Journal:
Discrete Mathematics  DM
, vol. 310, no. 23, pp. 34133416, 2010
The Communication Complexity of SetDisjointness with Small Sets and 01 Intersection
(
Citations: 1
)
Eyal Kushilevitz
,
Enav Weinreb
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 6372, 2009
Binary Covering Arrays and Existentially Closed Graphs
(
Citations: 2
)
Charles J. Colbourn
,
Gerzson Kéri
Conference:
International Workshop on Coding and Cryptography  WCC
, pp. 2233, 2009
On covering graphs by complete bipartite subgraphs
(
Citations: 1
)
Stasys Jukna
,
Alexander S. Kulikov
Journal:
Discrete Mathematics  DM
, vol. 309, no. 10, pp. 33993403, 2009