Concepedia

Arithmetic Circuit Complexity

Arithmetic Circuit Complexity is a branch of computational complexity theory that studies the minimum number of arithmetic operations required to compute a given polynomial using directed acyclic graphs composed of gates representing field additions and multiplications, distinguished from Boolean circuit complexity by its focus on algebraic computations over infinite fields.

370

Publications

19.8K

Citations

573

Authors

277

Institutions

Publications per year

2017–2026

38

Variants

Algebraic Circuit Complexity

Parents

Publications

370

Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics

Joseph B. Kruskal · Linear Algebra and its Applications · 1977 · 1.6K citations

, , +15

Practical fast 1-D DCT algorithms with 11 multiplications

Charles M. Loeffler, A. Ligtenberg, G.S. Moschytz · International Conference on Acoustics, Speech, and Signal Processing · 2003 · 640 citations

, , +10

Survey of Stochastic Computing

Armin Alaghi, John P. Hayes · ACM Transactions on Embedded Computing Systems · 2013 · 581 citations

, , +10

A fast Fourier transform compiler

Matteo Frigo · 1999 · 441 citations

, , +13

Lower bounds for resolution and cutting plane proofs and monotone computations

Pavel Pudlák · Journal of Symbolic Logic · 1997 · 419 citations

, , +15

1–5 of 370

Authors

573

  1. NK
    Neeraj Kayal

    Microsoft Research (India), India

    11 publications · 407 citations

    10

    h-index

  2. HJ
    Håkan Johansson

    Linköping University, Sweden

    9 publications · 327 citations

    9

    h-index

  3. MH
    M.A. Hasan

    University of Waterloo, Canada

    9 publications · 790 citations

    9

    h-index

  4. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    8 publications · 435 citations

    8

    h-index

  5. OG
    Oscar Gustafsson

    Linköping University, Sweden

    8 publications · 354 citations

    8

    h-index

1–5 of 573

Institutions

277

  1. Linköping University

    Linköping, Sweden

    15 h-index

    36 publications

    1.3K citations

  2. University of Waterloo

    Waterloo, Canada

    12 h-index

    23 publications

    1.7K citations

  3. Microsoft (United States)

    Redmond, United States

    9 h-index

    20 publications

    834 citations

  4. Concordia University

    Montreal, Canada

    8 h-index

    21 publications

    478 citations

  5. Technion – Israel Institute of Technology

    Haifa, Israel

    8 h-index

    11 publications

    1.1K citations

  6. Centre National de la Recherche Scientifique

    Paris, France

    8 h-index

    15 publications

    317 citations

  7. Weizmann Institute of Science

    Rehovot, Israel

    8 h-index

    10 publications

    479 citations

  8. Rutgers, The State University of New Jersey

    New Brunswick, United States

    8 h-index

    12 publications

    418 citations

1–8 of 277

Venues

  1. IEEE Transactions on Computers

    37 publications · 2.6K citations

    23

    h-index

  2. SIAM Journal on Computing

    21 publications · 1.4K citations

    20

    h-index

  3. Journal of the ACM

    JACM · 8 publications · 513 citations

    8

    h-index

  4. IEEE Transactions on Signal Processing

    8 publications · 348 citations

    8

    h-index

  5. arXiv (Cornell University)

    Repository · 8 publications · 175 citations

    8

    h-index

1–5