LOWER BOUNDS FOR SYNCHRONOUS CIRCUITS AND PLANAR CIRCUITS

被引：9
|
作者：
TURAN, G [1 ]
机构：
[1] UNIV ILLNOIS,DEPT MATH STAT & COMP SCI,CHICAGO,IL 60637
来源：
INFORMATION PROCESSING LETTERS | 1989年 / 30卷 / 01期
关键词：
D O I：
10.1016/0020-0190(89)90172-5
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
引用
收藏
页码：37 / 40
页数：4
相关论文
共 50 条
  • [41] LOWER BOUNDS FOR CONSTANT DEPTH CIRCUITS FOR PREFIX PROBLEMS
    CHANDRA, AK
    FORTUNE, S
    LIPTON, R
    LECTURE NOTES IN COMPUTER SCIENCE, 1983, 154 : 109 - 117
  • [42] Exponential lower bounds for depth three Boolean circuits
    R. Paturi
    M. E. Saks
    F. Zane
    computational complexity, 2000, 9 : 1 - 15
  • [43] Lower bounds for lengths of single tests for Boolean circuits
    Popkov, Kirill A.
    DISCRETE MATHEMATICS AND APPLICATIONS, 2019, 29 (01) : 23 - 33
  • [44] Lower bounds and separations for constant depth multilinear circuits
    Raz, Ran
    Yehudayoff, Amir
    TWENTY-THIRD ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2008, : 128 - 139
  • [45] LOWER BOUNDS FOR MODULAR COUNTING BY CIRCUITS WITH MODULAR GATES
    BARRINGTON, DM
    STRAUBING, H
    LATIN '95: THEORETICAL INFORMATICS, 1995, 911 : 60 - 71
  • [46] Log-Concavity and Lower Bounds for Arithmetic Circuits
    Garcia-Marcos, Ignacio
    Koiran, Pascal
    Tavenas, Sebastien
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT II, 2015, 9235 : 361 - 371
  • [47] Depth Lower Bounds against Circuits with Sparse Orientation
    Koroth, Sajin
    Sarma, Jayalal
    COMPUTING AND COMBINATORICS, COCOON 2014, 2014, 8591 : 596 - 607
  • [48] Lower bounds for modular counting by circuits with modular gates
    Barrington, DAM
    Straubing, H
    COMPUTATIONAL COMPLEXITY, 1999, 8 (03) : 258 - 272
  • [49] LOWER BOUNDS FOR THE COMPLEXITY OF RELIABLE BOOLEAN CIRCUITS WITH NOISY GATES
    GACS, P
    GAL, A
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1994, 40 (02) : 579 - 583
  • [50] LOWER BOUNDS ON THRESHOLD AND RELATED CIRCUITS VIA COMMUNICATION COMPLEXITY
    ROYCHOWDHURY, VP
    ORLITSKY, A
    SIU, KY
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1994, 40 (02) : 467 - 474
12345