for Journals by Title or ISSN
for Articles by Keywords
help
  Subjects -> MATHEMATICS (Total: 867 journals)
    - APPLIED MATHEMATICS (69 journals)
    - GEOMETRY AND TOPOLOGY (19 journals)
    - MATHEMATICS (645 journals)
    - MATHEMATICS (GENERAL) (40 journals)
    - NUMERICAL ANALYSIS (19 journals)
    - PROBABILITIES AND MATH STATISTICS (75 journals)

MATHEMATICS (645 journals)                  1 2 3 4 | Last

Showing 1 - 200 of 538 Journals sorted alphabetically
Abakós     Open Access   (Followers: 3)
Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg     Hybrid Journal   (Followers: 2)
Academic Voices : A Multidisciplinary Journal     Open Access   (Followers: 2)
Accounting Perspectives     Full-text available via subscription   (Followers: 6)
ACM Transactions on Algorithms (TALG)     Hybrid Journal   (Followers: 16)
ACM Transactions on Computational Logic (TOCL)     Hybrid Journal   (Followers: 4)
ACM Transactions on Mathematical Software (TOMS)     Hybrid Journal   (Followers: 6)
ACS Applied Materials & Interfaces     Full-text available via subscription   (Followers: 21)
Acta Applicandae Mathematicae     Hybrid Journal   (Followers: 1)
Acta Mathematica     Hybrid Journal   (Followers: 10)
Acta Mathematica Hungarica     Hybrid Journal   (Followers: 2)
Acta Mathematica Scientia     Full-text available via subscription   (Followers: 5)
Acta Mathematica Sinica, English Series     Hybrid Journal   (Followers: 5)
Acta Mathematica Vietnamica     Hybrid Journal  
Acta Mathematicae Applicatae Sinica, English Series     Hybrid Journal  
Advanced Science Letters     Full-text available via subscription   (Followers: 5)
Advances in Applied Clifford Algebras     Hybrid Journal   (Followers: 3)
Advances in Calculus of Variations     Hybrid Journal   (Followers: 2)
Advances in Catalysis     Full-text available via subscription   (Followers: 5)
Advances in Complex Systems     Hybrid Journal   (Followers: 7)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 15)
Advances in Decision Sciences     Open Access   (Followers: 4)
Advances in Difference Equations     Open Access   (Followers: 1)
Advances in Fixed Point Theory     Open Access   (Followers: 5)
Advances in Geosciences (ADGEO)     Open Access   (Followers: 9)
Advances in Linear Algebra & Matrix Theory     Open Access   (Followers: 1)
Advances in Materials Sciences     Open Access   (Followers: 16)
Advances in Mathematical Physics     Open Access   (Followers: 6)
Advances in Mathematics     Full-text available via subscription   (Followers: 10)
Advances in Numerical Analysis     Open Access   (Followers: 4)
Advances in Operations Research     Open Access   (Followers: 11)
Advances in Porous Media     Full-text available via subscription   (Followers: 4)
Advances in Pure and Applied Mathematics     Hybrid Journal   (Followers: 5)
Advances in Pure Mathematics     Open Access   (Followers: 4)
Advances in Science and Research (ASR)     Open Access   (Followers: 6)
Aequationes Mathematicae     Hybrid Journal   (Followers: 2)
African Journal of Educational Studies in Mathematics and Sciences     Full-text available via subscription   (Followers: 5)
African Journal of Mathematics and Computer Science Research     Open Access   (Followers: 4)
Afrika Matematika     Hybrid Journal   (Followers: 1)
Air, Soil & Water Research     Open Access   (Followers: 7)
AKSIOMA Journal of Mathematics Education     Open Access   (Followers: 1)
Algebra and Logic     Hybrid Journal   (Followers: 2)
Algebra Colloquium     Hybrid Journal   (Followers: 4)
Algebra Universalis     Hybrid Journal   (Followers: 2)
Algorithmic Operations Research     Full-text available via subscription   (Followers: 5)
Algorithms     Open Access   (Followers: 9)
Algorithms Research     Open Access   (Followers: 1)
American Journal of Biostatistics     Open Access   (Followers: 9)
American Journal of Computational and Applied Mathematics     Open Access   (Followers: 3)
American Journal of Mathematical Analysis     Open Access  
American Journal of Mathematics     Full-text available via subscription   (Followers: 7)
American Journal of Operations Research     Open Access   (Followers: 5)
American Mathematical Monthly     Full-text available via subscription   (Followers: 6)
An International Journal of Optimization and Control: Theories & Applications     Open Access   (Followers: 7)
Analele Universitatii Ovidius Constanta - Seria Matematica     Open Access   (Followers: 1)
Analysis     Hybrid Journal   (Followers: 2)
Analysis and Applications     Hybrid Journal   (Followers: 1)
Analysis and Mathematical Physics     Hybrid Journal   (Followers: 4)
Analysis Mathematica     Full-text available via subscription  
Annales Mathematicae Silesianae     Open Access  
Annales mathématiques du Québec     Hybrid Journal   (Followers: 4)
Annales UMCS, Mathematica     Open Access   (Followers: 1)
Annales Universitatis Paedagogicae Cracoviensis. Studia Mathematica     Open Access  
Annali di Matematica Pura ed Applicata     Hybrid Journal   (Followers: 1)
Annals of Combinatorics     Hybrid Journal   (Followers: 3)
Annals of Data Science     Hybrid Journal   (Followers: 8)
Annals of Discrete Mathematics     Full-text available via subscription   (Followers: 6)
Annals of Mathematics     Full-text available via subscription  
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 6)
Annals of Pure and Applied Logic     Open Access   (Followers: 2)
Annals of the Alexandru Ioan Cuza University - Mathematics     Open Access  
Annals of the Institute of Statistical Mathematics     Hybrid Journal   (Followers: 1)
Annals of West University of Timisoara - Mathematics     Open Access  
Annuaire du Collège de France     Open Access   (Followers: 5)
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 2)
Applications of Mathematics     Hybrid Journal   (Followers: 1)
Applied Categorical Structures     Hybrid Journal   (Followers: 2)
Applied Computational Intelligence and Soft Computing     Open Access   (Followers: 12)
Applied Mathematics     Open Access   (Followers: 3)
Applied Mathematics     Open Access   (Followers: 4)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 4)
Applied Mathematics - A Journal of Chinese Universities     Hybrid Journal  
Applied Mathematics Letters     Full-text available via subscription   (Followers: 1)
Applied Mathematics Research eXpress     Hybrid Journal   (Followers: 1)
Applied Network Science     Open Access  
Applied Numerical Mathematics     Hybrid Journal   (Followers: 5)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 4)
Arab Journal of Mathematical Sciences     Open Access   (Followers: 2)
Arabian Journal of Mathematics     Open Access   (Followers: 2)
Archive for Mathematical Logic     Hybrid Journal   (Followers: 1)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 4)
Archive of Numerical Software     Open Access  
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 4)
Arkiv för Matematik     Hybrid Journal   (Followers: 1)
Arnold Mathematical Journal     Hybrid Journal   (Followers: 1)
Artificial Satellites : The Journal of Space Research Centre of Polish Academy of Sciences     Open Access   (Followers: 17)
Asia-Pacific Journal of Operational Research     Hybrid Journal   (Followers: 3)
Asian Journal of Algebra     Open Access   (Followers: 1)
Asian Journal of Current Engineering & Maths     Open Access  
Asian-European Journal of Mathematics     Hybrid Journal   (Followers: 2)
Australian Mathematics Teacher, The     Full-text available via subscription   (Followers: 7)
Australian Primary Mathematics Classroom     Full-text available via subscription   (Followers: 2)
Australian Senior Mathematics Journal     Full-text available via subscription   (Followers: 1)
Automatic Documentation and Mathematical Linguistics     Hybrid Journal   (Followers: 5)
Axioms     Open Access  
Baltic International Yearbook of Cognition, Logic and Communication     Open Access  
Basin Research     Hybrid Journal   (Followers: 3)
BIBECHANA     Open Access  
BIT Numerical Mathematics     Hybrid Journal  
BoEM - Boletim online de Educação Matemática     Open Access  
Boletim Cearense de Educação e História da Matemática     Open Access  
Boletim de Educação Matemática     Open Access  
Boletín de la Sociedad Matemática Mexicana     Hybrid Journal  
Bollettino dell'Unione Matematica Italiana     Full-text available via subscription   (Followers: 1)
British Journal of Mathematical and Statistical Psychology     Full-text available via subscription   (Followers: 20)
Bruno Pini Mathematical Analysis Seminar     Open Access  
Buletinul Academiei de Stiinte a Republicii Moldova. Matematica     Open Access   (Followers: 7)
Bulletin des Sciences Mathamatiques     Full-text available via subscription   (Followers: 4)
Bulletin of Dnipropetrovsk University. Series : Communications in Mathematical Modeling and Differential Equations Theory     Open Access   (Followers: 1)
Bulletin of Mathematical Sciences     Open Access   (Followers: 1)
Bulletin of the Brazilian Mathematical Society, New Series     Hybrid Journal  
Bulletin of the London Mathematical Society     Hybrid Journal   (Followers: 3)
Bulletin of the Malaysian Mathematical Sciences Society     Hybrid Journal  
Calculus of Variations and Partial Differential Equations     Hybrid Journal  
Canadian Journal of Science, Mathematics and Technology Education     Hybrid Journal   (Followers: 17)
Carpathian Mathematical Publications     Open Access   (Followers: 1)
Catalysis in Industry     Hybrid Journal   (Followers: 1)
CEAS Space Journal     Hybrid Journal  
CHANCE     Hybrid Journal   (Followers: 5)
Chaos, Solitons & Fractals     Hybrid Journal   (Followers: 3)
ChemSusChem     Hybrid Journal   (Followers: 7)
Chinese Annals of Mathematics, Series B     Hybrid Journal  
Chinese Journal of Catalysis     Full-text available via subscription   (Followers: 2)
Chinese Journal of Mathematics     Open Access  
Clean Air Journal     Full-text available via subscription   (Followers: 2)
Cogent Mathematics     Open Access   (Followers: 2)
Cognitive Computation     Hybrid Journal   (Followers: 4)
Collectanea Mathematica     Hybrid Journal  
College Mathematics Journal     Full-text available via subscription   (Followers: 1)
COMBINATORICA     Hybrid Journal  
Combustion Theory and Modelling     Hybrid Journal   (Followers: 13)
Commentarii Mathematici Helvetici     Hybrid Journal   (Followers: 1)
Communications in Contemporary Mathematics     Hybrid Journal  
Communications in Mathematical Physics     Hybrid Journal   (Followers: 1)
Communications On Pure & Applied Mathematics     Hybrid Journal   (Followers: 3)
Complex Analysis and its Synergies     Open Access   (Followers: 2)
Complex Variables and Elliptic Equations: An International Journal     Hybrid Journal  
Complexus     Full-text available via subscription  
Composite Materials Series     Full-text available via subscription   (Followers: 9)
Comptes Rendus Mathematique     Full-text available via subscription   (Followers: 1)
Computational and Applied Mathematics     Hybrid Journal   (Followers: 2)
Computational and Mathematical Methods in Medicine     Open Access   (Followers: 2)
Computational and Mathematical Organization Theory     Hybrid Journal   (Followers: 2)
Computational Complexity     Hybrid Journal   (Followers: 4)
Computational Mathematics and Modeling     Hybrid Journal   (Followers: 8)
Computational Mechanics     Hybrid Journal   (Followers: 4)
Computational Methods and Function Theory     Hybrid Journal  
Computational Optimization and Applications     Hybrid Journal   (Followers: 7)
Computers & Mathematics with Applications     Full-text available via subscription   (Followers: 5)
Concrete Operators     Open Access   (Followers: 4)
Confluentes Mathematici     Hybrid Journal  
COSMOS     Hybrid Journal  
Cryptography and Communications     Hybrid Journal   (Followers: 12)
Cuadernos de Investigación y Formación en Educación Matemática     Open Access  
Cubo. A Mathematical Journal     Open Access  
Czechoslovak Mathematical Journal     Hybrid Journal   (Followers: 1)
Demographic Research     Open Access   (Followers: 11)
Demonstratio Mathematica     Open Access  
Dependence Modeling     Open Access  
Design Journal : An International Journal for All Aspects of Design     Hybrid Journal   (Followers: 28)
Developments in Clay Science     Full-text available via subscription   (Followers: 1)
Developments in Mineral Processing     Full-text available via subscription   (Followers: 3)
Dhaka University Journal of Science     Open Access  
Differential Equations and Dynamical Systems     Hybrid Journal   (Followers: 2)
Discrete Mathematics     Hybrid Journal   (Followers: 7)
Discrete Mathematics & Theoretical Computer Science     Open Access  
Discrete Mathematics, Algorithms and Applications     Hybrid Journal   (Followers: 2)
Discussiones Mathematicae Graph Theory     Open Access   (Followers: 1)
Doklady Mathematics     Hybrid Journal  
Duke Mathematical Journal     Full-text available via subscription   (Followers: 1)
Edited Series on Advances in Nonlinear Science and Complexity     Full-text available via subscription  
Electronic Journal of Graph Theory and Applications     Open Access   (Followers: 2)
Electronic Notes in Discrete Mathematics     Full-text available via subscription   (Followers: 2)
Elemente der Mathematik     Full-text available via subscription   (Followers: 3)
Energy for Sustainable Development     Hybrid Journal   (Followers: 9)
Enseñanza de las Ciencias : Revista de Investigación y Experiencias Didácticas     Open Access  
Ensino da Matemática em Debate     Open Access  
Entropy     Open Access   (Followers: 4)
ESAIM: Control Optimisation and Calculus of Variations     Full-text available via subscription   (Followers: 1)
European Journal of Combinatorics     Full-text available via subscription   (Followers: 4)
European Journal of Mathematics     Hybrid Journal   (Followers: 1)
European Scientific Journal     Open Access   (Followers: 2)
Experimental Mathematics     Hybrid Journal   (Followers: 3)
Expositiones Mathematicae     Hybrid Journal   (Followers: 2)
Facta Universitatis, Series : Mathematics and Informatics     Open Access  
Fasciculi Mathematici     Open Access  
Finite Fields and Their Applications     Full-text available via subscription   (Followers: 4)
Fixed Point Theory and Applications     Open Access   (Followers: 1)
Formalized Mathematics     Open Access   (Followers: 2)
Foundations and Trends® in Econometrics     Full-text available via subscription   (Followers: 4)

        1 2 3 4 | Last

Journal Cover Computational Complexity
  [SJR: 0.607]   [H-I: 27]   [4 followers]  Follow
    
   Hybrid Journal Hybrid journal (It can contain Open Access articles)
   ISSN (Print) 1420-8954 - ISSN (Online) 1016-3328
   Published by Springer-Verlag Homepage  [2329 journals]
  • On the connection between interval size functions and path counting
    • Authors: Evangelos Bampas; Andreas-Nikolas Göbel; Aris Pagourtzis; Aris Tentes
      Pages: 421 - 467
      Abstract: We investigate the complexity of hard (#P-complete) counting problems that have easy decision version. By ‘easy decision,’ we mean that deciding whether the result of counting is nonzero is in P. This property is shared by several well-known problems, such as counting the number of perfect matchings in a given graph or counting the number of satisfying assignments of a given DNF formula. We focus on classes of such hard-to-count easy-to-decide problems which emerged through two seemingly disparate approaches: one taken by Hemaspaandra et al. (SIAM J Comput 36(5):1264–1300, 2007), who defined classes of functions that count the size of intervals of ordered strings, and one followed by Kiayias et al. (Lect Notes Comput Sci 2563:453–463, 2001), who defined the classTotP, consisting of functions that count the total number of paths of NP computations. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known #P-complete problems with easy decision are contained in the classes defined by Hemaspaandra et al., but are unlikely to be complete for these classes under reductions under which these classes are downward closed, e.g., parsimonious reductions. This, applied to the #MONSAT problem, partially answers an open question of Hemaspaandra et al. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains hard counting problems.
      PubDate: 2017-06-01
      DOI: 10.1007/s00037-016-0137-8
      Issue No: Vol. 26, No. 2 (2017)
       
  • The Minimum Oracle Circuit Size Problem
    • Authors: Eric Allender; Dhiraj Holden; Valentine Kabanets
      Pages: 469 - 496
      Abstract: We consider variants of the minimum circuit size problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MSCP QBF is known to be complete for PSPACE under ZPP reductions. We show that it is not complete under logspace reductions, and indeed it is not even hard for TC 0 under uniform AC 0 reductions. We obtain a variety of consequences that follow if oracle versions of MCSP are hard for various complexity classes under different types of reductions. We also prove analogous results for the problem of determining the resource-bounded Kolmogorov complexity of strings, for certain types of Kolmogorov complexity measures.
      PubDate: 2017-06-01
      DOI: 10.1007/s00037-016-0124-0
      Issue No: Vol. 26, No. 2 (2017)
       
  • Sunflowers and Testing Triangle-Freeness of Functions
    • Authors: Ishay Haviv; Ning Xie
      Pages: 497 - 530
      Abstract: A function \({f : {\mathbb F}_{2}^{n} \rightarrow {\{0,1\}}}\) is triangle-free if there are no \({x_{1},x_{2},x_{3} \in {\mathbb F}_{2}^{n}}\) satisfying \({x_{1} + x_{2} + x_{3} = 0}\) and \({f(x_{1}) = f(x_{2}) = f(x_{3}) = 1}\) . In testing triangle-freeness, the goal is to distinguish with high probability triangle-free functions from those that are \({\varepsilon}\) -far from being triangle-free. It was shown by Green that the query complexity of the canonical tester for the problem is upper bounded by a function that depends only on \({\varepsilon}\) (Green 2005); however, the best-known upper bound is a tower-type function of \({1/\varepsilon}\) . The best known lower bound on the query complexity of the canonical tester is \({1/\varepsilon^{13.239}}\) (Fu & Kleinberg 2014). In this work we introduce a new approach to proving lower bounds on the query complexity of triangle-freeness. We relate the problem to combinatorial questions on collections of vectors in \({{\mathbb Z}_D^n}\) and to sunflower conjectures studied by Alon, Shpilka & Umans (2013). The relations yield that a refutation of the Weak Sunflower Conjecture over \({{\mathbb Z}_{4}}\) implies a super-polynomial lower bound on the query complexity of the canonical tester for triangle-freeness. Our results are extended to testing k-cycle-freeness of functions with domain \({{\mathbb F}_p^n}\) for every \({k \ge 3}\) and a prime p. In addition, we generalize the lower bound of Fu and Kleinberg to k-cycle-freeness for \({k \geq 4}\) by generalizing the construction of uniquely solvable puzzles due to Coppersmith & Winograd (1990).
      PubDate: 2017-06-01
      DOI: 10.1007/s00037-016-0138-7
      Issue No: Vol. 26, No. 2 (2017)
       
  • On the complexity of computing Kronecker coefficients
    • Authors: Igor Pak; Greta Panova
      Pages: 1 - 36
      Abstract: We study the complexity of computing Kronecker coefficients \({g(\lambda,\mu,\nu)}\) . We give explicit bounds in terms of the number of parts \({\ell}\) in the partitions, their largest part size N and the smallest second part M of the three partitions. When M =  O(1), i.e., one of the partitions is hook-like, the bounds are linear in log N, but depend exponentially on \({\ell}\) . Moreover, similar bounds hold even when \({M=e^{O(\ell)}}\) . By a separate argument, we show that the positivity of Kronecker coefficients can be decided in O(log N) time for a bounded number \({\ell}\) of parts and without restriction on M. Related problems of computing Kronecker coefficients when one partition is a hook and computing characters of S n are also considered.
      PubDate: 2017-03-01
      DOI: 10.1007/s00037-015-0109-4
      Issue No: Vol. 26, No. 1 (2017)
       
  • Sparse affine-invariant linear codes are locally testable
    • Authors: Eli Ben-Sasson; Noga Ron-Zewi; Madhu Sudan
      Pages: 37 - 77
      Abstract: We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field \({\mathbb{F}_q}\) and an extension field \({\mathbb{F}_{q^n}}\) , a property is a set of functions mapping \({\mathbb{F}_{q^n}}\) to \({\mathbb{F}_q}\) . The property is said to be affine-invariant if it is invariant under affine transformations of \({\mathbb{F}_{q^n}}\) , linear if it is an \({\mathbb{F}_q}\) -vector space, and sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et al. (2009) and followed by Kaufman & Lovett (2011). The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial, and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties.
      PubDate: 2017-03-01
      DOI: 10.1007/s00037-015-0115-6
      Issue No: Vol. 26, No. 1 (2017)
       
  • Nondeterministic circuit lower bounds from mildly derandomizing
           Arthur-Merlin games
    • Authors: Barış Aydınlıoğlu; Dieter van Melkebeek
      Pages: 79 - 118
      Abstract: In several settings, derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in any way implies the ability to do so in the canonical way through pseudorandom generators. For the setting of decision problems, Impagliazzo, Kabanets, and Wigderson (2002) implicitly showed the following equivalence: Randomized polynomial-time decision procedures for promise problems can be simulated in \({\sf{NSUBEXP}}\) (the subexponential version of \({\sf{NP}}\) ) with subpolynomial advice on infinitely many input lengths if and only if \({{\sf{NEXP}} \not \subseteq }\) \({\sf{P}/ poly}\) . We establish a full analog in the setting of verification procedures: Arthur-Merlin games for promise problems can be simulated in \({{\sf{\Sigma_{2} SUBEXP}}}\) (the subexponential version of \({\sf{\Sigma_{2} P}}\) ) with subpolynomial advice on infinitely many input lengths if and only if \({\sf{\Sigma_2EXP} \not \subseteq }\) \({\sf{NP}/poly}\) . A key ingredient in our proofs is improved Karp-Lipton style collapse results for nondeterministic circuits. The following are two instantiations that may be of independent interest: Assuming that Arthur-Merlin games can be derandomized in \({{\sf{\Sigma_{2}} P}}\) , we show that (i) \({\sf{PSPACE} \subseteq }\) \({\sf{NP/poly}}\) implies \({\sf{PSPACE} \subseteq \sf{\Sigma_2P}}\) and (ii) \({\sf{coNP} \subseteq {\sf{NP/poly}}}\) implies \({{\sf{PH} \subseteq \sf{P^{\Sigma_2P}}}}\) . Of possible independent interest is a generic framework that we provide, which captures several results in the literature of the form “derandomization implies circuit lower bounds.” In particular, our framework enables a unified view of our result, the one by Impagliazzo et al. (2002) mentioned above, as well as the result by Kabanets and Impagliazzo (2004) that derandomizing polynomial identity testing yields arithmetic circuit lower bounds.
      PubDate: 2017-03-01
      DOI: 10.1007/s00037-014-0095-y
      Issue No: Vol. 26, No. 1 (2017)
       
  • The Value of Help Bits in Randomized and Average-Case Complexity
    • Authors: Salman Beigi; Omid Etesami; Amin Gohari
      Pages: 119 - 145
      Abstract: “Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity. If k instances of a decision problem can be efficiently solved using \({\ell < k}\) help bits, then without access to help bits one can efficiently compute a k-bit vector that is not equal to the k-bit vector of solutions to the k instances. A decision problem with this property is called k-membership comparable. Amir, Beigel, and Gasarch (1990) show that for constant k, all k-membership comparable languages are in P/poly. We extend this result to the setting of randomized computation: We show that for k at most logarithmic, the decision problem is k-membership comparable if using \({\ell}\) help bits, k instances of the problem can be efficiently solved with probability greater than \({2^{\ell-k}}\) . The same conclusion holds if using less than \({k(1 - h(\alpha))}\) help bits (where \({h(\cdot)}\) is the binary entropy function), we can efficiently solve \({1-\alpha}\) fraction of the instances correctly with non-vanishing probability. We note that when k is constant, k-membership comparability implies being in P/poly. Next we consider the setting of average-case complexity: Assume that we can solve k instances of a decision problem using some help bits whose entropy is less than k when the k instances are drawn independently from a particular distribution. Then we can efficiently solve an instance drawn from that distribution with probability better than 1/2. Finally, we show that in the case where k is super-logarithmic, assuming k-membership comparability of a decision problem, one cannot prove that the problem is in P/poly by a “relativizing" proof technique. All previous known proofs in this area have been relativizing.
      PubDate: 2017-03-01
      DOI: 10.1007/s00037-016-0135-x
      Issue No: Vol. 26, No. 1 (2017)
       
  • Information-theoretic approximations of the nonnegative rank
    • Authors: Gábor Braun; Rahul Jain; Troy Lee; Sebastian Pokutta
      Pages: 147 - 197
      Abstract: Common information was introduced by Wyner (IEEE Trans Inf Theory 21(2):163–179, 1975) as a measure of dependence of two random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix in Braun and Pokutta (Proceedings of FOCS, 2013) and Jain et al. (Proceedings of SODA, 2013). Lower bounds on nonnegative rank have important applications to several areas such as communication complexity and combinatorial optimization. We begin a systematic study of common information extending the dual characterization of Witsenhausen (SIAM J Appl Math 31(2):313–333, 1976). Our main results are: (i) Common information is additive under tensoring of matrices. (ii) It characterizes the (logarithm of the) amortized nonnegative rank of a matrix, i.e., the minimal nonnegative rank under tensoring and small \({\ell_1}\) perturbations. We also provide quantitative bounds generalizing previous asymptotic results by Wyner (IEEE Trans Inf Theory 21(2):163–179, 1975). (iii) We deliver explicit witnesses from the dual problem for several matrices leading to explicit lower bounds on common information, which are robust under \({\ell_1}\) perturbations. This includes improved lower bounds for perturbations of the all important unique disjointness partial matrix, as well as new insights into its information-theoretic structure.
      PubDate: 2017-03-01
      DOI: 10.1007/s00037-016-0125-z
      Issue No: Vol. 26, No. 1 (2017)
       
  • Multipartite Quantum Correlation and Communication Complexities
    • Authors: Rahul Jain; Zhaohui Wei; Penghui Yao; Shengyu Zhang
      Pages: 199 - 228
      Abstract: The concepts of quantum correlation complexity and quantum communication complexity were recently proposed to quantify the minimum amount of resources needed in generating bipartite classical or quantum states in the single-shot setting. The former is the minimum size of the initially shared state \({\sigma}\) on which local operations by the two parties (without communication) can generate the target state \({\rho}\) , and the latter is the minimum amount of communication needed when initially sharing nothing. In this paper, we generalize these two concepts to multipartite cases, for both exact and approximate state generation. Our results are summarized as follows. For multipartite pure states, the correlation complexity can be completely characterized by local ranks of sybsystems. We extend the notion of PSD-rank of matrices to that of tensors, and use it to bound the quantum correlation complexity for generating multipartite classical distributions. For generating multipartite mixed quantum states, communication complexity is not always equal to correlation complexity (as opposed to bipartite case). But they differ by at most a factor of 2. Generating a multipartite mixed quantum state has the same communication complexity as generating its optimal purification. But the correlation complexities of these two tasks can be different (though still related by less than a factor of 2). To generate a bipartite classical distribution P(x, y) approximately, the quantum communication complexity is completely characterized by the approximate PSD-rank of P. The quantum correlation complexity of approximately generating multipartite pure states is bounded by approximate local ranks.
      PubDate: 2017-03-01
      DOI: 10.1007/s00037-016-0126-y
      Issue No: Vol. 26, No. 1 (2017)
       
  • On the Structure of Boolean Functions with Small Spectral Norm
    • Authors: Amir Shpilka; Avishay Tal; Ben lee Volk
      Pages: 229 - 273
      Abstract: In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is \({\ \hat{f}\ _1 = \sum_{\alpha} \hat{f}(\alpha) }\) ). Specifically, we prove the following results for functions \({f : \{0, 1\}^n \to \{0, 1\}}\) with \({\ \hat{f}\ _1 = A}\) . There is an affine subspace V of co-dimension at most A 2 such that \({f _V}\) is constant. f can be computed by a parity decision tree of size at most \({2^{A^2} n^{2A}}\) . (A parity decision tree is a decision tree whose nodes are labeled with arbitrary linear functions.) f can be computed by a De Morgan formula of size \({O(2^{A^2} n^{2A + 2})}\) and by a De Morgan formula of depth \({O(A^2 + \log(n) \cdot A)}\) . If in addition f has at most s nonzero Fourier coefficients, then f can be computed by a parity decision tree of depth at most \({A^2 \log s}\) . For every \({\epsilon > 0}\) there is a parity decision tree of depth \({O(A^2 + \log(1/\epsilon))}\) and size \({2^{O(A^2)} \cdot \min \{1/\epsilon^2, \log(1/\epsilon)^{2A}\}}\) that \({\epsilon}\) -approximates f. Furthermore, this tree can be learned (in the uniform distribution model), with probability \({1 - \delta}\) , using \({{\tt poly}(n, {\rm exp}(A^2), 1/\epsilon, \log(1/\delta))}\) membership queries. All the results above (except 3) also hold (with a slight change in parameters) for functions \({f : \mathbb{Z}_p^n \to \{0, 1\}}\) .
      PubDate: 2017-03-01
      DOI: 10.1007/s00037-015-0110-y
      Issue No: Vol. 26, No. 1 (2017)
       
  • Fourier Concentration from Shrinkage
    • Authors: Russell Impagliazzo; Valentine Kabanets
      Pages: 275 - 321
      Abstract: For a class \({\mathcal{F}}\) of formulas (general de Morgan or read-once de Morgan), the shrinkage exponent \({\Gamma_{\mathcal{F}}}\) is the parameter measuring the reduction in size of a formula \({F\in\mathcal{F}}\) after \({F}\) is hit with a random restriction. A Boolean function \({f\colon \{0,1\}^n\to\{1,-1\}}\) is Fourier-concentrated if, when viewed in the Fourier basis, \({f}\) has most of its total mass on “low-degree” coefficients. We show a direct connection between the two notions by proving that shrinkage implies Fourier concentration: For a shrinkage exponent \({\Gamma_{\mathcal{F}}}\) , a formula \({F\in\mathcal{F}}\) of size \({s}\) will have most of its Fourier mass on the coefficients of degree up to about \({s^{1/\Gamma_{\mathcal{F}}}}\) . More precisely, for a Boolean function \({f\colon\{0,1\}^n\to\{1,-1\}}\) computable by a formula of (large enough) size \({s}\) and for any parameter \({r > 0}\) , $$\sum_{A\subseteq [n]\; :\; A \geq s^{1/\Gamma} \cdot r} \hat{f}(A)^2\leq s\cdot{\mathscr{polylog}}(s)\cdot exp\left(-\frac{r^{\frac{\Gamma}{\Gamma-1}}}{s^{o(1)}} \right),$$ where \({\Gamma}\) is the shrinkage exponent for the corresponding class of formulas: \({\Gamma=2}\) for de Morgan formulas, and \({\Gamma=1/\log_2(\sqrt{5}-1)\approx 3.27}\) for read-once de Morgan formulas. This Fourier concentration result is optimal, to within the \({o(1)}\) term in the exponent of \({s}\) . As a standard application of these Fourier concentration results, we get that subquadratic-size de Morgan formulas have negligible correlation with parity. We also show the tight \({\Theta(s^{1/\Gamma})}\) bound on the average sensitivity of read-once formulas of size \({s}\) , which mirrors the known tight bound \({\Theta(\sqrt{s})}\) on the average sensitivity of general de Morgan \({s}\) -size formulas.
      PubDate: 2017-03-01
      DOI: 10.1007/s00037-016-0134-y
      Issue No: Vol. 26, No. 1 (2017)
       
  • Short lists with short programs in short time
    • Authors: Bruno Bauwens; Anton Makhlin; Nikolay Vereshchagin; Marius Zimand
      Abstract: Given a machine U, a c-short program for x is a string p such that U(p) = x and the length of p is bounded by c + (the length of a shortest program for x). We show that for any standard Turing machine, it is possible to compute in polynomial time on input x a list of polynomial size guaranteed to contain a \({\operatorname{O}\bigl({\mathrm{log}} x \bigr)}\) -short program for x. We also show that there exists a computable function that maps every x to a list of size x 2 containing a \({\operatorname{O}\bigl(1\bigr)}\) -short program for x. This is essentially optimal because we prove that for each such function there is a c and infinitely many x for which the list has size at least c x 2. Finally we show that for some standard machines, computable functions generating lists with 0-short programs must have infinitely often list sizes proportional to 2 x .
      PubDate: 2017-04-19
      DOI: 10.1007/s00037-017-0154-2
       
  • Tight Size-Degree Bounds for Sums-of-Squares Proofs
    • Authors: Massimo Lauria; Jakob Nordström
      Abstract: We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size \({n^{\Omega{(d)}}}\) for values of d = d(n) from constant all the way up to \({n^{\delta}}\) for some universal constant \({\delta}\) . This shows that the \({{n^{{\rm O}{(d)}}}}\) running time obtained by using the Lasserre semidefinite programming relaxations to find degree-d SOS proofs is optimal up to constant factors in the exponent. We establish this result by combining NP-reductions expressible as low-degree SOS derivations with the idea of relativizing CNF formulas in Krajíček (Arch Math Log 43(4):427–441, 2004) and Dantchev & Riis (Proceedings of the 17th international workshop on computer science logic (CSL ’03), 2003) and then applying a restriction argument as in Atserias et al. (J Symb Log 80(2):450–476, 2015; ACM Trans Comput Log 17:19:1–19:30, 2016). This yields a generic method of amplifying SOS degree lower bounds to size lower bounds and also generalizes the approach used in Atserias et al. (2016) to obtain size lower bounds for the proof systems resolution, polynomial calculus, and Sherali–Adams from lower bounds on width, degree, and rank, respectively.
      PubDate: 2017-04-19
      DOI: 10.1007/s00037-017-0152-4
       
  • Block-symmetric polynomials correlate with parity better than symmetric
    • Authors: Frederic Green; Daniel Kreymer; Emanuele Viola
      Abstract: We show that degree-d block-symmetric polynomials in n variables modulo any odd p correlate with parity exponentially better than degree-d symmetric polynomials, if \({n \ge cd^2 {\rm log} d}\) and \({d \in [0.995 \cdot p^t - 1,p^t)}\) for some \({t \ge 1}\) and some \({c > 0}\) that depends only on p. For these infinitely many degrees, our result solves an open problem raised by a number of researchers including Alon & Beigel (IEEE conference on computational complexity (CCC), pp 184–187, 2001). The only previous case for which this was known was d = 2 and p = 3 (Green in J Comput Syst Sci 69(1):28–44, 2004). The result is obtained through the development of a theory we call spectral analysis of symmetric correlation, which originated in works of Cai et al. (Math Syst Theory 29(3):245–258, 1996) and Green (Theory Comput Syst 32(4):453–466, 1999). In particular, our result follows from a detailed analysis of the correlation of symmetric polynomials, which is determined up to an exponentially small relative error when \({d = p^t-1}\) .
      PubDate: 2017-04-05
      DOI: 10.1007/s00037-017-0153-3
       
  • List-Decoding Barnes–Wall Lattices
    • Authors: Elena Grigorescu; Chris Peikert
      Abstract: The question of list-decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete linear structure of linear codes and point lattices in \({\mathbb{R}^{N}}\) , and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the study of list decoding for lattices. Namely: for a lattice \({\mathcal{L}\subseteq \mathbb{R}^N}\) , given a target vector \({r \in \mathbb{R}^N}\) and a distance parameter d, output the set of all lattice points \({w \in \mathcal{L}}\) that are within distance d of r. In this work, we focus on combinatorial and algorithmic questions related to list decoding for the well-studied family of Barnes–Wall lattices. Our main contributions are twofold: We give tight combinatorial bounds on the worst-case list size, showing it to be polynomial in the lattice dimension for any error radius bounded away from the lattice’s minimum distance (in the Euclidean norm). We use our combinatorial bounds to generalize the unique-decoding algorithm of Micciancio and Nicolosi (IEEE International Symposium on Information Theory 2008) to work beyond the unique-decoding radius and still run in polynomial time up to the list-decoding radius. Just like the Micciancio–Nicolosi algorithm, our algorithm is highly parallelizable, and with sufficiently many processors, it can run in parallel time only poly-logarithmic in the lattice dimension.
      PubDate: 2017-01-12
      DOI: 10.1007/s00037-016-0151-x
       
  • Affine extractors over large fields with exponential error
    • Authors: Jean Bourgain; Zeev Dvir; Ethan Leeman
      Pages: 921 - 931
      Abstract: We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.
      PubDate: 2016-12-01
      DOI: 10.1007/s00037-015-0108-5
      Issue No: Vol. 25, No. 4 (2016)
       
  • Low-degree test with polynomially small error
    • Authors: Dana Moshkovitz
      Abstract: A long line of work in Theoretical Computer Science shows that a function is close to a low-degree polynomial iff it is locally close to a low-degree polynomial. This is known as low-degree testing and is the core of the algebraic approach to construction of PCP. We obtain a low-degree test whose error, i.e., the probability it accepts a function that does not correspond to a low-degree polynomial, is polynomially smaller than existing low-degree tests. A key tool in our analysis is an analysis of the sampling properties of the incidence graph of degree-k curves and k′-tuples of points in a finite space \({\mathbb{F}^m}\) . We show that the Sliding Scale Conjecture in PCP, namely the conjecture that there are PCP verifiers whose error is exponentially small in their randomness, would follow from a derandomization of our low-degree test.
      PubDate: 2016-12-19
      DOI: 10.1007/s00037-016-0149-4
       
  • Graph Isomorphism, Color Refinement, and Compactness
    • Authors: V. Arvind; Johannes Köbler; Gaurav Rattan; Oleg Verbitsky
      Abstract: Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph G amenable to color refinement if the color refinement procedure succeeds in distinguishing G from any non-isomorphic graph H. Babai et al. (SIAM J Comput 9(3):628–635, 1980) have shown that random graphs are amenable with high probability. We determine the exact range of applicability of color refinement by showing that amenable graphs are recognizable in time \({O((n+m)\log n)}\) , where n and m denote the number of vertices and the number of edges in the input graph. We use our characterization of amenable graphs to analyze the approach to Graph Isomorphism based on the notion of compact graphs. A graph is called compact if the polytope of its fractional automorphisms is integral. Tinhofer (Discrete Appl Math 30(2–3):253–264, 1991) noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing compact graphs and recognizing them in polynomial time remains an open question. Our results in this direction are summarized below: We show that all amenable graphs are compact. In other words, the applicability range for Tinhofer’s linear programming approach to isomorphism testing is at least as large as for the combinatorial approach based on color refinement. Exploring the relationship between color refinement and compactness further, we study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. We show that the corresponding classes of graphs form a hierarchy, and we prove that recognizing each of these graph classes is P-hard. In particular, this gives a first complexity lower bound for recognizing compact graphs.
      PubDate: 2016-12-19
      DOI: 10.1007/s00037-016-0147-6
       
  • On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic
           Logspace
    • Abstract: We show that approximating the second eigenvalue of stochastic operators is BPL-complete, thus giving a natural problem complete for this class. We also show that approximating any eigenvalue of a stochastic and Hermitian operator with constant accuracy can be done in BPL. This work together with related work on the subject reveal a picture where the various space-bounded classes (e.g., probabilistic logspace, quantum logspace and the class DET) can be characterized by algebraic problems (such as approximating the spectral gap) where, roughly speaking, the difference between the classes lies in the kind of operators they can handle (e.g., stochastic, Hermitian or arbitrary).
      PubDate: 2016-12-16
      DOI: 10.1007/s00037-016-0150-y
       
  • Quantum Query Complexity of Almost All Functions with Fixed On-set Size
    • Authors: Andris Ambainis; Kazuo Iwama; Masaki Nakanishi; Harumichi Nishimura; Rudy Raymond; Seiichiro Tani; Shigeru Yamashita
      Abstract: This paper considers the quantum query complexity of almost all functions in the set \({\mathcal{F}}_{N,M}\) of \({N}\) -variable Boolean functions with on-set size \({M (1\le M \le 2^{N}/2)}\) , where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in \({\mathcal{F}}_{N,M}\) except its polynomially small fraction, the quantum query complexity is \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N} \right)}\) for a constant \({c > 0}\) . This is quite different from the quantum query complexity of the hardest function in \({\mathcal{F}}_{N,M}\) : \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N} \right)}\) . In contrast, almost all functions in \({\mathcal{F}}_{N,M}\) have the same randomized query complexity \({\Theta(N)}\) as the hardest one, up to a constant factor.
      PubDate: 2016-06-21
      DOI: 10.1007/s00037-016-0139-6
       
 
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
 
Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs
Your IP address: 54.162.96.103
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-2016