首页>外文期刊>数学、物理、化学、力学>数学>Computational complexity

Computational complexity

SCI

中文名称：计算复杂度

ISSN：1016-3328
出版周期：Quarterly

发文量：288

期刊论文

热门论文

年度选择

更多>>

全选（0）

1.The complexity of approximating the complex-valued Potts model

机译：The complexity of approximating the complex-valued Potts model
- 作者：Andreas Galanis;Leslie Ann Goldberg;Andrés Herrera-Poyatos
- 期刊名称：《Computational complexity》 | 2022年第1期
- Counting Complexity;
- Potts model;
- Ising model;
- Tutte polynomial;
- Approximate Counting;
2.QUANTUM GENERALIZATIONS OF THE POLYNOMIAL HIERARCHY WITH APPLICATIONS TO QMA(2)

机译：QUANTUM GENERALIZATIONS OF THE POLYNOMIAL HIERARCHY WITH APPLICATIONS TO QMA(2)
- 作者：Gharibian Sevag;Santha Miklos;Sikora JamieSundaram AarthiYirka Justin
- 期刊名称：《Computational complexity》 | 2022年第2期
- Complexity theory;
- Quantum computing;
- Polynomial hierarchy;
- QMA(2);
- Semidefinite programming;
- Toda's theorem;
3.IMPROVED HITTING SET FOR ORBIT OF ROABPS

机译：IMPROVED HITTING SET FOR ORBIT OF ROABPS
- 作者：Bhargava Vishwas;Ghosh Sumanta
- 期刊名称：《Computational complexity》 | 2022年第2期
- Polynomial Identity Testing;
- Hitting set;
- Read Once Algebraic Branching Program;
- Orbit;
- Rank Concentration;
- Cone Concentration;
4.NONDETERMINISTIC AND RANDOMIZED BOOLEAN HIERARCHIES IN COMMUNICATION COMPLEXITY

机译：NONDETERMINISTIC AND RANDOMIZED BOOLEAN HIERARCHIES IN COMMUNICATION COMPLEXITY
- 作者：Pitassi Toniann;Shirley Morgan;Watson Thomas
- 期刊名称：《Computational complexity》 | 2021年第2期
- Boolean hierarchies;
- Lifting theorems;
- Query complexity;
5.BLACKBOX IDENTITY TESTING FOR SUM OF SPECIAL ROABPS AND ITS BORDER CLASS

机译：BLACKBOX IDENTITY TESTING FOR SUM OF SPECIAL ROABPS AND ITS BORDER CLASS
- 作者：Bisht Pranav;Saxena Nitin
- 期刊名称：《Computational complexity》 | 2021年第1期
- Identity test;
- hitting-set;
- ROABP;
- blackbox;
- log variate;
- width;
- diagonal;
- derandomization;
- homogeneous;
- sparsity;
- border complexity;
6.Rank and border rank of Kronecker powers of tensors and Strassen's laser method

机译：Rank and border rank of Kronecker powers of tensors and Strassen's laser method
- 作者：Austin Conner;Fulvio Gesmundo;Joseph M. LandsbergEmanuele Ventura
- 期刊名称：《Computational complexity》 | 2022年第1期
- Matrix multiplication complexity;
- Tensor rank;
- Asymptotic rank;
- Laser method;
7.A LOWER BOUND ON DETERMINANTAL COMPLEXITY

机译：A LOWER BOUND ON DETERMINANTAL COMPLEXITY
- 作者：Kumar Mrinal;Volk Ben Lee
- 期刊名称：《Computational complexity》 | 2022年第2期
- Determinantal Complexity;
- Algebraic Complexity Theory;
- Lower Bounds;
- Algebraic Circuits;
8.QUADRATIC LOWER BOUNDS FOR ALGEBRAIC BRANCHING PROGRAMS AND FORMULAS

机译：QUADRATIC LOWER BOUNDS FOR ALGEBRAIC BRANCHING PROGRAMS AND FORMULAS
- 作者：Chatterjee Prerona;Kumar Mrinal;She AdrianVolk Ben Lee
- 期刊名称：《Computational complexity》 | 2022年第2期
- Lower bounds;
- Algebraic circuit complexity;
- Algebraic branching programs;
- Algebraic formulas;
9.Schur Polynomials Do Not Have Small Formulas If the Determinant does not

机译：Schur Polynomials Do Not Have Small Formulas If the Determinant does not
- 作者：Prasad Chaugule;Mrinal Kumar;Nutan LimayeChandra Kanta MohapatraAdrian SheSrikanth Srinivasan
- 期刊名称：《Computational complexity》 | 2023年第1期
- Schur polynomial;
- Jacobian;
- Algebraic independence;
- Generalized Vandermonde determinant;
- Taylor expansion;
- Formula complexity;
- Lower bound;
10.QUANTUM VERSUS RANDOMIZED COMMUNICATION COMPLEXITY, WITH EFFICIENT PLAYERS

机译：QUANTUM VERSUS RANDOMIZED COMMUNICATION COMPLEXITY, WITH EFFICIENT PLAYERS
- 作者：Girish Uma;Raz Ran;Tal Avishay
- 期刊名称：《Computational complexity》 | 2022年第2期
- Quantum;
- Randomized;
- Communication Complexity;
- Exponential Separation;
11.LOWER BOUNDS FOR MATRIX FACTORIZATION

机译：LOWER BOUNDS FOR MATRIX FACTORIZATION
- 作者：Volk Ben Lee;Kumar Mrinal
- 期刊名称：《Computational complexity》 | 2021年第1期
- Algebraic complexity;
- Linear circuits;
- Matrix factorization;
- Lower bounds;
12.Amplification with One NP Oracle Query

机译：Amplification with One NP Oracle Query
- 作者：Thomas Watson
- 期刊名称：《Computational complexity》 | 2022年第1期
- Amplification;
- NP;
- oracle;
13.FACTORIZATION OF POLYNOMIALS GIVEN BY ARITHMETIC BRANCHING PROGRAMS

机译：FACTORIZATION OF POLYNOMIALS GIVEN BY ARITHMETIC BRANCHING PROGRAMS
- 作者：Sinhababu Amit;Thierauf Thomas
- 期刊名称：《Computational complexity》 | 2021年第2期
14.THE HARDEST HALFSPACE

机译：THE HARDEST HALFSPACE
- 作者：Sherstov Alexander A.
- 期刊名称：《Computational complexity》 | 2021年第2期
- Small-bias communication;
- Multiparty communication;
- UPP;
- PP;
- Halfspaces;
- Approximation by polynomials and rational functions;
15.A COST-SCALING ALGORITHM FOR COMPUTING THE DEGREE OF DETERMINANTS

机译：A COST-SCALING ALGORITHM FOR COMPUTING THE DEGREE OF DETERMINANTS
- 作者：Hirai Hiroshi;Ikeda Motoki
- 期刊名称：《Computational complexity》 | 2022年第2期
- Edmonds' problem;
- noncommutative rank;
- Dieudonne determinant;
- Newton polytope;
- partitioned matrix;
16.SMOOTH AND STRONG PCPS

机译：SMOOTH AND STRONG PCPS
- 作者：Paradise Orr
- 期刊名称：《Computational complexity》 | 2021年第1期
- Interactive and probabilistic proof systems;
- Probabilistically;
- checkable proofs;
- Hardness of approximation;
17.Computing zero-dimensional tropical varieties via projections

机译：Computing zero-dimensional tropical varieties via projections
- 作者：Paul G?rlach;Yue Ren;Leon Zhang
- 期刊名称：《Computational complexity》 | 2022年第1期
- tropical geometry;
- tropical varieties;
- computer algebra;
18.IMPROVED BOUNDS ON THE AN-COMPLEXITY OF O(1)-LINEAR FUNCTIONS

机译：IMPROVED BOUNDS ON THE AN-COMPLEXITY OF O(1)-LINEAR FUNCTIONS
- 作者：GOLDREICH O. D. E. D.
- 期刊名称：《Computational complexity》 | 2022年第2期
- Arithmetic circuits;
- multilinear circuits;
- restricted models of computation;
19.NEAR-OPTIMAL LOWER BOUNDS ON REGULAR RESOLUTION REFUTATIONS OF TSEITIN FORMULAS FOR ALL CONSTANT-DEGREE GRAPHS

机译：NEAR-OPTIMAL LOWER BOUNDS ON REGULAR RESOLUTION REFUTATIONS OF TSEITIN FORMULAS FOR ALL CONSTANT-DEGREE GRAPHS
- 作者：Itsykson Dmitry;Riazanov Artur;Smirnov PetrSagunov Danil
- 期刊名称：《Computational complexity》 | 2021年第2期
- Tseitin formula;
- Treewidth;
- Read-once branching program;
- Regular resolution;
- Lower bound;
- Proof complexity;
20.Explicit construction of q+1 regular local Ramanujan graphs, for all prime-powers q

机译：Explicit construction of q+1 regular local Ramanujan graphs, for all prime-powers q
- 作者：Rishabh Batra;Nitin Saxena;Devansh Shringi
- 期刊名称：《Computational complexity》 | 2023年第1期
- Expanders;
- Ramanujan graphs;
- constant locality;
- NC0;
- unique-neighbor expanders;
- finite fields;
- residuosity;
- linear groups;
- Cayley;
- Schreier;
21.AN EXPONENTIAL SEPARATION BETWEEN MA AND AM PROOFS OF PROXIMITY

机译：AN EXPONENTIAL SEPARATION BETWEEN MA AND AM PROOFS OF PROXIMITY
- 作者：Gur Tom;Liu Yang P.;Rothblum Ron D.
- 期刊名称：《Computational complexity》 | 2021年第2期
- Interative proofs;
- proofs of proximity;
22.CORRECTION TO: SMOOTH AND STRONG PCPS

机译：CORRECTION TO: SMOOTH AND STRONG PCPS
- 作者：Paradise Orr
- 期刊名称：《Computational complexity》 | 2021年第1期
23.Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

机译：Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?
- 作者：Ronen Shaltiel
- 期刊名称：《Computational complexity》 | 2023年第1期
- Average-case complexity;
- Yao’s XOR lemma;
- black-box reductions;
24.EXPLICIT LIST-DECODABLE CODES WITH OPTIMAL RATE FOR COMPUTATIONALLY BOUNDED CHANNELS

机译：EXPLICIT LIST-DECODABLE CODES WITH OPTIMAL RATE FOR COMPUTATIONALLY BOUNDED CHANNELS
- 作者：Shaltiel Ronen;Silbak Jad
- 期刊名称：《Computational complexity》 | 2021年第1期
- error correcting codes;
- computationally bounded channels;
- pseudorandomness;
25.Expander-Based Cryptography Meets Natural Proofs

机译：Expander-Based Cryptography Meets Natural Proofs
- 作者：Igor C. Oliveira;Rahul Santhanam;Roei Tell
- 期刊名称：《Computational complexity》 | 2022年第1期
- Pseudorandom Generators;
- One-Way Functions;
- Expanders;
- Circuit Complexity;
26.ON HITTING-SET GENERATORS FOR POLYNOMIALS THAT VANISH RARELY

机译：ON HITTING-SET GENERATORS FOR POLYNOMIALS THAT VANISH RARELY
- 作者：Doron Dean;Ta-Shma Amnon;Tell Roei
- 期刊名称：《Computational complexity》 | 2022年第2期
- Polynomials;
- Hitting-Set Generators;
- Pseudorandom Generators;
- Quantified Derandomization;
- Bounded-Degree Closure;
27.On sets of linear forms of maximal complexity

机译：On sets of linear forms of maximal complexity
- 作者：Michael Kaminski;Igor E. Shparlinski;Michel Waldschmidt
- 期刊名称：《Computational complexity》 | 2023年第1期
- Linear algorithms;
- additive complexity;
- effective Perron theorem;
- common nonzeros of polynomials;
28.DISJOINTNESS THROUGH THE LENS OF VAPNIK-CHERVONENKIS DIMENSION: SPARSITY AND BEYOND

机译：DISJOINTNESS THROUGH THE LENS OF VAPNIK-CHERVONENKIS DIMENSION: SPARSITY AND BEYOND
- 作者：Bhattacharya Anup;Chakraborty Sourav;Ghosh ArijitMishra GopinathParaashar Manaswi
- 期刊名称：《Computational complexity》 | 2022年第2期
- Communication complexity;
- VC dimension;
- Sparsity;
- Geometric Set System;
29.NULLSTELLENSATZ SIZE-DEGREE TRADE-OFFS FROM REVERSIBLE PEBBLING

机译：NULLSTELLENSATZ SIZE-DEGREE TRADE-OFFS FROM REVERSIBLE PEBBLING
- 作者：De Rezende Susanna F.;Meir Or;Nordstrom JakobRobere Robert
- 期刊名称：《Computational complexity》 | 2021年第1期
- Proof complexity;
- Nullstellensatz;
- Trade-offs;
- Pebbling;
30.SUBQUADRATIC-TIME ALGORITHMS FOR NORMAL BASES

机译：SUBQUADRATIC-TIME ALGORITHMS FOR NORMAL BASES
- 作者：Giesbrecht Mark;Jamshidpey Armin;Schost Eric
- 期刊名称：《Computational complexity》 | 2021年第1期
- Normal bases;
- Galois groups;
- Polycyclic groups;
- Metacyclic groups;
- Fast algorithms;
31.THE COMPLEXITY OF FINDING FAIR INDEPENDENT SETS IN CYCLES

机译：THE COMPLEXITY OF FINDING FAIR INDEPENDENT SETS IN CYCLES
- 作者：Haviv Ishay
- 期刊名称：《Computational complexity》 | 2022年第2期
- Fair independent sets in cycles;
- the complexity class PPA;
- Schrijver graphs;
32.REVERSIBLE PEBBLE GAMES AND THE RELATION BETWEEN TREE-LIKE AND GENERAL RESOLUTION SPACE

机译：REVERSIBLE PEBBLE GAMES AND THE RELATION BETWEEN TREE-LIKE AND GENERAL RESOLUTION SPACE
- 作者：Toran Jacobo;Woerz Florian
- 期刊名称：《Computational complexity》 | 2021年第1期
- Proof complexity;
- Resolution;
- Tree-like resolution;
- Pebble game;
- Reversible pebbling;
- Prover-Delayer game;
- Raz-McKenzie game;
- Clause space;
- Variable space;
33.Zeros and approximations of Holant polynomials on the complex plane

机译：Zeros and approximations of Holant polynomials on the complex plane
- 作者：Katrin Casel;Philipp Fischbeck;Tobias FriedrichAndreas G?belJ. A. Gregor Lagodzinski
- 期刊名称：《Computational complexity》 | 2022年第2期
- Holant problems;
- approximate counting;
- partition functions;
- graph polynomials;
34.A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory

机译：A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
- 作者：Jin-Yi Cai;Zhiguo Fu;Kurt GirstmairMichael Kowalczyk
- 期刊名称：《Computational complexity》 | 2023年第1期
- Spin systems;
- Holant problems;
- Number Theory;
- Characters;
- Cyclotomic fields;
35.CORRECTION TO: NEAR-OPTIMAL LOWER BOUNDS ON REGULAR RESOLUTION REFUTATIONS OF TSEITIN FORMULAS FOR ALL CONSTANT-DEGREE GRAPHS

机译：CORRECTION TO: NEAR-OPTIMAL LOWER BOUNDS ON REGULAR RESOLUTION REFUTATIONS OF TSEITIN FORMULAS FOR ALL CONSTANT-DEGREE GRAPHS
- 作者：Itsykson Dmitry;Riazanov Artur;Sagunov DanilSmirnov Petr
- 期刊名称：《Computational complexity》 | 2021年第2期
36.A QUASI-LINEAR IRREDUCIBILITY TEST IN Kxy

机译：A QUASI-LINEAR IRREDUCIBILITY TEST IN Kxy
- 作者：Poteaux Adrien;Weimann Martin
- 期刊名称：《Computational complexity》 | 2022年第1期
- Irreducibility test;
- Newton polygon;
- Residual polynomial;
- Puiseux series;
- Approximate roots;
- Algorithm;
- Complexity;
37.LOWER BOUNDS FOR ARITHMETIC CIRCUITS VIA THE HANKEL MATRIX

机译：LOWER BOUNDS FOR ARITHMETIC CIRCUITS VIA THE HANKEL MATRIX
- 作者：Fijalkow Nathanael;Lagarde Guillaume;Ohlmann PierreSerre Olivier
- 期刊名称：《Computational complexity》 | 2021年第2期
- Arithmetic circuit complexity;
- Lower bounds;
- Parse trees;
- Hankel matrix;
38.How can a complex square root be computed in an optimal way?

机译：How can a complex square root be computed in an optimal way?
- 作者：ThomasLickteig;KaiWerther
- 期刊名称：《computational complexity》 | 1996年第1期
39.An average complexity measure that yields tight hierarchies

机译：An average complexity measure that yields tight hierarchies
- 作者：R.Reischuk;C.Schindelhauer
- 期刊名称：《computational complexity》 | 1996年第2期
40.Simple learning algorithms using divide and conquer

机译：Simple learning algorithms using divide and conquer
- 作者：NaderH.Bshouty
- 期刊名称：《computational complexity》 | 1996年第2期
41.PSEUDORANDOM FUNCTIONS IN TC~0 AND CRYPTOGRAPHIC LIMITATIONS TO PROVING LOWER BOUNDS

机译：PSEUDORANDOM FUNCTIONS IN TC~0 AND CRYPTOGRAPHIC LIMITATIONS TO PROVING LOWER BOUNDS
- 作者：Matthias Krause;Stefan Lucks
- 期刊名称：《Computational complexity》 | 2002年第4期
- Pseudorandomness;
- function generators;
- TC~0;
- lower bounds;
42.Lower bounds for polynomial evaluation and interpolation problems

机译：Lower bounds for polynomial evaluation and interpolation problems
- 作者：VictorShoup;RomanSmolensky
- 期刊名称：《computational complexity》 | 1996年第4期
43.On the complexity of planar Boolean circuits

机译：On the complexity of planar Boolean circuits
- 作者：GyörgyTurán
- 期刊名称：《computational complexity》 | 1995年第1期
44.Tribute to Roman Smolensky

机译：Tribute to Roman Smolensky
- 作者：AllanBorodin
- 期刊名称：《computational complexity》 | 1996年第3期
45.The computational complexity of recognizing permutation functions

机译：The computational complexity of recognizing permutation functions
- 作者：KejuMa;Joachimvon zurGathen
- 期刊名称：《computational complexity》 | 1995年第1期
46.A CHARACTERIZATION OF SPAN PROGRAM SIZE AND IMPROVED LOWER BOUNDS FOR MONOTONE SPAN PROGRAMS

机译：A CHARACTERIZATION OF SPAN PROGRAM SIZE AND IMPROVED LOWER BOUNDS FOR MONOTONE SPAN PROGRAMS
- 作者：Anna Gal
- 期刊名称：《Computational complexity》 | 2002年第4期
- Span programs;
- lower bounds;
- Boolean formula size;
- secret sharing;
47.Easy lower bound for a strange computational model

机译：Easy lower bound for a strange computational model
- 作者：RomanSmolensky
- 期刊名称：《computational complexity》 | 1996年第3期
48.Reflections on “Representations of sets of Boolean functions by commutative rings” by Roman Smolensky

机译：Reflections on “Representations of sets of Boolean functions by commutative rings” by Roman Smolensky
- 作者：JehoshuaBruck
- 期刊名称：《computational complexity》 | 1996年第3期
49.Derandomized graph products

机译：Derandomized graph products
- 作者：NogaAlon;UrielFeige;AviWigdersonDavidZuckerman
- 期刊名称：《computational complexity》 | 1995年第1期
50.Randomization and the computational power of analytic and algebraic decision trees

机译：Randomization and the computational power of analytic and algebraic decision trees
- 作者：DimaGrigoriev;MarekKarpinski;RomanSmolensky
- 期刊名称：《computational complexity》 | 1996年第4期
51.OPTIMALITY OF SIZE-WIDTH TRADEOFFS FOR RESOLUTION

机译：OPTIMALITY OF SIZE-WIDTH TRADEOFFS FOR RESOLUTION
- 作者：Maria Luisa Bonet;Nicola Galesi
- 期刊名称：《Computational complexity》 | 2002年第4期
- Resolution;
- complexity of proofs;
- automated theorem proving;
52.The electrical resistance of a graph captures its commute and cover times

机译：The electrical resistance of a graph captures its commute and cover times
- 作者：AshokK.Chandra;PrabhakarRaghavan;WalterL.RuzzoRomanSmolenskyPrasoonTiwari
- 期刊名称：《computational complexity》 | 1996年第4期
53.Well-known bound for the VC-dimension made easy

机译：Well-known bound for the VC-dimension made easy
- 作者：RomanSmolensky
- 期刊名称：《computational complexity》 | 1996年第4期
54.Upper and lower bounds for some depth-3 circuit classes

机译：Upper and lower bounds for some depth-3 circuit classes
- 作者：RichardBeigel;AlexisMaciel
- 期刊名称：《computational complexity》 | 1996年第3期
55.On-line learning of linear functions

机译：On-line learning of linear functions
- 作者：NicholasLittlestone;ManfredK.Warmuth;PhilipM.Long
- 期刊名称：《computational complexity》 | 1995年第1期
56.A lower bound for randomized algebraic decision trees

机译：A lower bound for randomized algebraic decision trees
- 作者：DimaGrigoriev;MarekKarpinski;FriedhelmMeyerauf derHeideRomanSmolensky
- 期刊名称：《computational complexity》 | 1996年第4期
57.The privacy of dense symmetric functions

机译：The privacy of dense symmetric functions
- 作者：BennyChor;NettaShani
- 期刊名称：《computational complexity》 | 1995年第1期
58.Weakly complete problems are not rare

机译：Weakly complete problems are not rare
- 作者：DavidW.Juedes
- 期刊名称：《computational complexity》 | 1995年第3期
59.On the oracle complexity of factoring integers

机译：On the oracle complexity of factoring integers
- 作者：UeliM.Maurer
- 期刊名称：《computational complexity》 | 1995年第3期
60.Pseudorandom generators and learning algorithms forAC0

机译：Pseudorandom generators and learning algorithms forAC0
- 作者：MeeraSitharam
- 期刊名称：《computational complexity》 | 1995年第3期
61.Collecting coupons on trees, and the cover time of random walks

机译：Collecting coupons on trees, and the cover time of random walks
- 作者：UrielFeige
- 期刊名称：《computational complexity》 | 1996年第4期
62.Fourier analysis for probabilistic communication complexity

机译：Fourier analysis for probabilistic communication complexity
- 作者：RanRaz
- 期刊名称：《computational complexity》 | 1995年第3期
63.Representations of sets of Boolean functions by commutative rings

机译：Representations of sets of Boolean functions by commutative rings
- 作者：RomanSmolensky
- 期刊名称：《computational complexity》 | 1996年第3期
64.Super-logarithmic depth lower bounds via the direct sum in communication complexity

机译：Super-logarithmic depth lower bounds via the direct sum in communication complexity
- 作者：MauricioKarchmer;RanRaz;AviWigderson
- 期刊名称：《computational complexity》 | 1995年第3期
65.Lower bounds on arithmetic circuits via partial derivatives

机译：Lower bounds on arithmetic circuits via partial derivatives
- 作者：NoamNisan;AviWigderson
- 期刊名称：《computational complexity》 | 1996年第3期
66.Proof complexity in algebraic systems and bounded depth Frege systems with modular counting

机译：Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
- 作者：S.Buss;R.Impagliazzo;J.KrajíčekP.PudlákA.A.RazborovJ.Sgall
- 期刊名称：《computational complexity》 | 1996年第3期
67.How can a complex square root be computed in an optimal way?

机译：How can a complex square root be computed in an optimal way?
- 作者：ThomasLickteig;KaiWerther
- 期刊名称：《computational complexity》 | 1995年第3期

客服邮箱：kefu@zhangqiaokeyan.com

客服微信
服务号