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 条
  • [21] Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
    Roughgarden, Tim
    Vassilvitskii, Sergei
    Wang, Joshua R.
    JOURNAL OF THE ACM, 2018, 65 (06)
  • [22] Lower Bounds for Arithmetic Circuits via the Hankel Matrix
    Fijalkow, Nathanael
    Lagarde, Guillaume
    Ohlmann, Pierre
    Serre, Olivier
    COMPUTATIONAL COMPLEXITY, 2021, 30 (02)
  • [23] Exponential lower bounds for depth three Boolean circuits
    Paturi, R
    Saks, ME
    Zane, F
    COMPUTATIONAL COMPLEXITY, 2000, 9 (01) : 1 - 15
  • [24] 2 LOWER BOUNDS FOR CIRCUITS OVER THE BASIS (AND,V,-)
    JUKNA, SP
    LECTURE NOTES IN COMPUTER SCIENCE, 1988, 324 : 371 - 380
  • [25] LOWER BOUNDS ON MONOTONE ARITHMETIC CIRCUITS WITH RESTRICTED DEPTHS
    JA, JJ
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1985, 11 (12) : 1155 - 1164
  • [26] Depth Lower Bounds against Circuits with Sparse Orientation
    Koroth, Sajin
    Sarma, Jayalal
    FUNDAMENTA INFORMATICAE, 2017, 152 (02) : 123 - 144
  • [27] Algorithms and Lower Bounds for Comparator Circuits from Shrinkage
    Cavalar, Bruno P.
    Lu, Zhenjian
    ALGORITHMICA, 2023, 85 (7) : 2131 - 2155
  • [28] Lower bounds for circuits with few modular and symmetric gates
    Chattopadhyay, A
    Hansen, KA
    AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS, 2005, 3580 : 994 - 1005
  • [29] Lower Bounds for Arithmetic Circuits via the Hankel Matrix
    Fijalkow, Nathanael
    Lagarde, Guillaume
    Ohlmann, Pierre
    Serre, Olivier
    37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020), 2020, 154
  • [30] Lower bounds on arithmetic circuits via partial derivatives
    Nisan, N
    Wigderson, A
    COMPUTATIONAL COMPLEXITY, 1997, 6 (03) : 217 - 234
12345